您的位置: 首页  >  文章  >  redis原理

redis原理

分类: 文章 • 2023-12-21 14:23:16

redis原理总结(很全面)

2018年08月28日 17:48:07 wuyangyang555 阅读数：4724

redis单点吞吐量

单点TPS达到8万/秒，QPS达到10万/秒。

redis的5中存储类型

string、list、set、map（hash）、stored-set

redis的string类型

  1. 能表达3中类型：字符串、整数和浮点数。根据场景相互间自动转型，并且根据需要选取底层的承载方式
  2. value内部以int、sds作为结构存储。int存放整型数据，sds存放字节/字符串和浮点型数据
  3. sds内部结构： 
    • 用buf数组存储字符串的内容，但数组的长度会大于所存储内容的长度。会有一格专门存放”\0”（C标准库）作为结尾，还有预留多几个空的（即free区域），当append字符串的长度小于free区域，则sds不会重新申请内存，直接使用free区域
    • 扩容：当对字符串的操作完成后预期的串长度小于1M时，扩容后的buf数组大小=预期长度*2+1；若大于1M，则buf总是会预留出1M的free空间
    • value对象通常具有两个内存部分：redisObject部分和redisObject的ptr指向的sds部分。创建value对象时，通常需要为redisObject和sds申请两次内存。单对于短小的字符串，可以把两者连续存放，所以可以一次性把两者的内存一起申请了

redis的list类型

  1. list类型的value对象内部以linkedlist或ziplist承载。当list的元素个数和单个元素的长度较小时，redis会采用ziplist实现以减少内存占用，否则采用linkedlist结构
  2. linkedlist内部实现是双向链表。在list中定义了头尾元素指针和列表的长度，是的pop/push操作、llen操作的复杂度为O(1)。由于是链表，lindex类的操作复杂度仍然是O(N)
  3. ziplist的内部结构 
    • 所有内容被放置在连续的内存中。其中zlbytes表示ziplist的总长度，zltail指向最末元素，zllen表示元素个数，entry表示元素自身内容，zlend作为ziplist定界符
    • rpush、rpop、llen，复杂度为O(1);lpush/pop操作由于涉及全列表元素的移动，复杂度为O(N)

redis的map类型

  1. map又叫hash。map内部的key和value不能再嵌套map了，只能是string类型：整形、浮点型和字符串
  2. map主要由hashtable和ziplist两种承载方式实现，对于数据量较小的map，采用ziplist实现
  3. hashtable内部结构 
    • 主要分为三层，自底向上分别是dictEntry、dictht、dict
    • dictEntry：管理一个key-value对，同时保留同一个桶中相邻元素的指针，一次维护哈希桶的内部连
    • dictht：维护哈希表的所有桶链
    • dict：当dictht需要扩容/缩容时，用于管理dictht的迁移
    • 哈希表的核心结构是dictht，它的table字段维护着hash桶，它是一个数组，每个元素指向桶的第一个元素（dictEntry）
    • set值的流程：先通过MurmurHash算法求出key的hash值，再对桶的个数取模，得到key对应的桶，再进入桶中，遍历全部entry，判定是否已有相同的key，如果没有，则将新key对应的键值对插入到桶头，并且更新dictht的used数量，used表示hash表中已经存了多少元素。由于每次插入都要遍历hash桶中的全部entry，所以当桶中entry很多时，性能会线性下降
    • 扩容：通过负载因子判定是否需要增加桶数。负载因子=哈希表中已有元素/哈希桶数的比值。有两个阈值，小于1一定不扩容；大于5一定扩容。扩容时新的桶数目是现有桶的2n倍
    • 缩容：负载因子的阈值是0.1
    • 扩/缩容通过新建哈希表的方式实现。即扩容时，会并存两个哈希表，一个是源表，一个是目标表。通过将源表的桶逐步迁移到目标表，以数据迁移的方式实现扩容，迁移完成后目标表覆盖源表。迁移过程中，首先访问源表，如果发现key对应的源表桶已完成迁移，则重新访问目标表，否则在源表中操作
    • redis是单线程处理请求，迁移和访问的请求在相同线程内进行，所以不会存在并发性问题
  4. ziplist内部结构 
    • 和list的ziplist实现类似。不同的是，map对应的ziplist的entry个数总是2的整数倍，奇数存放key，偶数存放value
    • ziplist实现下，由哈希遍历变成了链表的顺序遍历，复杂度变成O(N)

redis的set类型

  1. set以intset或hashtable来存储。hashtable中的value永远为null，当set中只包含整数型的元素时，则采用intset
  2. intset的内部结构 
    • 核心元素是一个字节数组，从小到大有序存放着set的元素
    • 由于元素有序排列，所以set的获取操作采用二分查找方式实现，复杂度O(log(N))。进行插入时，首先通过二分查找得到本次插入的位置，再对元素进行扩容，再将预计插入位置之后的所有元素向右移动一个位置，最后插入元素，插入复杂度为O(N)。删除类似

redis的sorted-set类型

  1. 类似map是一个key-value对，但是有序的。value是一个浮点数，称为score，内部是按照score从小到大排序
  2. 内部结构以ziplist或skiplist+hashtable来实现

redis客户端与服务器的交互模式

  1. 串行的请求/响应模式 
    • 每一次请求的发送都依赖于上一次请求的相应结果完全接收，同一个连接的每秒吞吐量低
    • redis对单个请求的处理时间通常比局域网的延迟小一个数量级，所以串行模式下，单链接的大部分时间都处于网络等待
  2. 双工的请求/相应模式(pipeline) 
    • 适用于批量的独立写入操作。即可将请求数据批量发送到服务器，再批量地从服务器连接的字节流中一次读取每个响应数据，减少了网络延迟，所以单连接吞吐量较串行会提高一个数量级
  3. 原子化的批量请求/响应模式（事务） 
    • 客户端通过和redis服务器两阶段的交互做到批量命令原子执行的事务效果：入队操作（即服务器端先将客户端发送过来的连接对象暂存在请求队列中）和执行阶段（依次执行请求队列中的所有请求）
    • 一个连接的请求在执行批量请求的过程中，不会执行其他客户端的请求
    • redis的事务不是一致的，没有回滚机制。如果中途失败，则返回错误信息，但已经成功执行的命令不会回滚
    • 事务里面有可能会带有读操作作为条件，由于批量请求只会先入队列，再批量一起执行，所以一般读操作不会跟批量写请求一起执行，这时候就有可能会导致批量写之前和之后读到的数据不一致，这种可以通过乐观锁的可串行化来解决，redis通过watch机制实现乐观锁。具体实现过程看下一题
  4. 发布/订阅模式 
    • 发布端和订阅者通过channel关联
    • channel的订阅关系，维护在reids实例级别，独立于redisDB的key-value体系。所有的channel都由一个map维护，键是channel的名字，value是它所有订阅者client的指针链表
  5. 脚本化的批量执行（脚本模式）

redis通过watch机制实现乐观锁流程

  1. 将本次事务涉及的所有key注册为观察模式
  2. 执行只读操作
  3. 根据只读操作的结果组装写操作命令并发送到服务器端入队
  4. 发送原子化的批量执行命令EXEC试图执行连接的请求队列中的命令
  5. 如果前面注册为观察模式的key中有一个货多个，在EXEC之前被修改过，则EXEC将直接失败，拒绝执行；否则顺序执行请求队列中的所有请求
  6. redis没有原生的悲观锁或者快照实现，但可通过乐观锁绕过。一旦两次读到的操作不一样，watch机制触发，拒绝了后续的EXEC执行

redis的网络协议

redis协议位于TCP层之上，即客户端和redis实例保持双工的连接，交互的都是序列化后的协议数据

redis处理命令的主要逻辑

  1. redis服务器对命令的处理都是单线程的，但是I/O层面却面向多个客户端并发地提供服务，并发到内部单线程的转化通过多路复用框架来实现
  2. 首先从多路服用框架（epoll、evport、kqueue）中select出已经ready的文件描述符（fileDescriptor）
  3. ready的标准是已有数据到达内核（kernel）、已准备好写入数据
  4. 对于上一步已经ready的fd，redis会分别对每个fd上已ready的事件进行处理，处理完相同fd上的所有事件后，再处理下一个ready的fd。有3中事件类型 
    • acceptTcpHandler：连接请求事件
    • readQueryFromClient：客户端的请求命令事件
    • sendReplyToClient：将暂存的执行结果写回客户端
  5. 对来自客户端的命令执行结束后，接下来处理定时任务（TimeEvent）
  6. aeApiPoll的等待时间取决于定时任务处理（TimeEvent）逻辑
  7. 本次主循环完毕，进入下一次主循环的beforeSleep逻辑，后者负责处理数据过期、增量持久化的文件写入等任务

redis的持久化机制

  1. redis主要提供了两种持久化机制：RDB和AOF；
  2. RDB 
    • 默认开启，会按照配置的指定时间将内存中的数据快照到磁盘中，创建一个dump.rdb文件，redis启动时再恢复到内存中。
    • redis会单独创建fork()一个子进程，将当前父进程的数据库数据复制到子进程的内存中，然后由子进程写入到临时文件中，持久化的过程结束了，再用这个临时文件替换上次的快照文件，然后子进程退出，内存释放。
    • 需要注意的是，每次快照持久化都会将主进程的数据库数据复制一遍，导致内存开销加倍，若此时内存不足，则会阻塞服务器运行，直到复制结束释放内存；都会将内存数据完整写入磁盘一次，所以如果数据量大的话，而且写操作频繁，必然会引起大量的磁盘I/O操作，严重影响性能，并且最后一次持久化后的数据可能会丢失；
  3. AOF 
    • 以日志的形式记录每个写操作（读操作不记录），只需追加文件但不可以改写文件，redis启动时会根据日志从头到尾全部执行一遍以完成数据的恢复工作。包括flushDB也会执行。
    • 主要有两种方式触发：有写操作就写、每秒定时写（也会丢数据）。
    • 因为AOF采用追加的方式，所以文件会越来越大，针对这个问题，新增了重写机制，就是当日志文件大到一定程度的时候，会fork出一条新进程来遍历进程内存中的数据，每条记录对应一条set语句，写到临时文件中，然后再替换到旧的日志文件（类似rdb的操作方式）。默认触发是当aof文件大小是上次重写后大小的一倍且文件大于64M时触发；
  4. 当两种方式同时开启时，数据恢复redis会优先选择AOF恢复。一般情况下，只要使用默认开启的RDB即可，因为相对于AOF，RDB便于进行数据库备份，并且恢复数据集的速度也要快很多。
  5. 开启持久化缓存机制，对性能会有一定的影响，特别是当设置的内存满了的时候，更是下降到几百reqs/s。所以如果只是用来做缓存的话，可以关掉持久化。

redis内存分析的设计思路

  1. 主要有3种方式可以实现 
    • keys命令：获取到所有的key，再根据key获取所有的内容。缺点是如果key数量特别多，则会导致redis卡住影响业务
    • aof：通过aof文件获取到所有数据。缺点是有一些redis实例写入频繁，不适合开启aof，并且文件可能特别大，传输、解析效率差
    • rdb：使用bgsave获取rdb文件，然后解析。缺点是bgsave在fork子进程时有可能会卡住主进程。当对于其他两种，在低峰期在从节点做bgsave获取rdb文件，相对安全可靠。
  2. 设计思路： 
    • 在访问低峰期时根据redis获取rdb文件
    • 解析rdb文件
    • 根据相对应的数据结构及内容，估算内容消耗等
    • 统计并生成报表
  3. 开源框架：https://github.com/xueqiu/rdr

redis内存估算

  1. 基础的数据类型：sds、dict、intset、zipmap、adlist、quicklist、skiplist
  2. 举例：以key为hello，value为world，类型是string，它的内存使用： 
    • 一个dictEntry的消耗（有2个指针，一个int64的内存消耗），RedisDB就是一个大dict，每对kv都是其中的一个entry；
    • 一个robj的消耗（有1指针，一个int，以及几个使用位域的字段共消耗4字节），robj是为了在同一个dict内能够存储不同类型的value，而使用的一个通用的数据结构，全名是RedisObject；
    • 存储key的sds消耗（存储header以及字符串长度+1的空间，header长度根据字符串长度不同也会有所不同），sds是Redis中存储字符串使用的数据结构；
    • 存储过期时间消耗（也是存储为一个dictEntry，时间戳为int64）；
    • 存储value的sds消耗，根据数据结构不同而不同；
    • 前四项基本是存储任何一个key都需要消耗的，最后一项根据value的数据结构不同而不同；

redis集群（redis cluster）

  1. redis3以后，节点之间提供了完整的sharding（分片）、replication（主备感知能力）、failover（故障转移）的特性
  2. 配置一致性：每个节点（Node）内部都保存了集群的配置信息，存储在clusterState中，通过引入自增的epoch变量来使得集群配置在各个节点间保持一致
  3. sharding数据分片 
    • 将所有数据划分为16384个分片（slot），每个节点会对应一部分slot，每个key都会根据分布算法映射到16384个slot中的一个，分布算法为slotId=crc16(key)%16384
    • 当一个client访问的key不在对应节点的slots中，redis会返回给client一个moved命令，告知其正确的路由信息从而重新发起请求。client会根据每次请求来缓存本地的路由缓存信息，以便下次请求直接能够路由到正确的节点
    • 分片迁移：分片迁移的触发和过程控制由外部系统完成，redis只提供迁移过程中需要的原语支持。主要包含两种：一种是节点迁移状态设置，即迁移钱标记源、目标节点；另一种是key迁移的原子化命令
  4. failover故障转移 
    • 故障发现：节点间两两通过TCP保持连接，周期性进行PING、PONG交互，若对方的PONG相应超时未收到，则将其置为PFAIL状态，并传播给其他节点
    • 故障确认：当集群中有一半以上的节点对某一个PFAIL状态进行了确认，则将起改为FAIL状态，确认其故障
    • slave选举：当有一个master挂掉了，则其slave重新竞选出一个新的master。主要根据各个slave最后一次同步master信息的时间，越新表示slave的数据越新，竞选的优先级越高，就更有可能选中。竞选成功之后将消息传播给其他节点。
  5. 集群不可用的情况： 
    • 集群中任意master挂掉，且当前master没有slave。
    • 集群中超过半数以上master挂掉。

普通哈希算法和一致性哈希算法对比

  1. 普通哈希：也称硬哈希，采用简单取模的方式，将机器进行散列，这在cache环境不变的情况下能取得让人满意的结果，但是当cache环境动态变化时，这种静态取模的方式显然就不满足单调性的要求（当增加或减少一台机子时，几乎所有的存储内容都要被重新散列到别的缓冲区中）。
  2. 一致性哈希：将机器节点和key值都按照一样的hash算法映射到一个0~2^32的圆环上。当有一个写入缓存的请求到来时，计算Key值k对应的哈希值Hash(k)，如果该值正好对应之前某个机器节点的Hash值，则直接写入该机器节点，如果没有对应的机器节点，则顺时针查找下一个节点，进行写入，如果超过2^32还没找到对应节点，则从0开始查找（因为是环状结构）。为了更可能的满足平衡性，可以引入虚拟节点，即一个实体节点映射到多个虚拟节点。
  3. 参考：http://blog.huanghao.me/?p=14

缓存雪崩，缓存穿透，缓存并发，缓存预热，缓存算法

  1. 缓存雪崩：可能是因为数据未加载到缓存中，或者缓存同一时间大面积的失效，从而导致所有请求都去查数据库，导致数据库CPU和内存负载过高，甚至宕机。解决思路： 
    • 加锁计数（即限制并发的数量，可以用semphore）或者起一定数量的队列来避免缓存失效时大量请求并发到数据库。但这种方式会降低吞吐量。
    • 分析用户行为，然后失效时间均匀分布。或者在失效时间的基础上再加1~5分钟的随机数。
    • 如果是某台缓存服务器宕机，则考虑做主备。
  2. 缓存穿透：指用户查询数据，在数据库没有，自然在缓存中也不会有。这样就导致用户查询的时候，在缓存中找不到，每次都要去数据库中查询。解决思路： 
    • 如果查询数据库也为空，直接设置一个默认值存放到缓存，这样第二次到缓冲中获取就有值了，而不会继续访问数据库。设置一个过期时间或者当有值的时候将缓存中的值替换掉即可。
    • 可以给key设置一些格式规则，然后查询之前先过滤掉不符合规则的Key。
  3. 缓存并发：如果网站并发访问高，一个缓存如果失效，可能出现多个进程同时查询DB，同时设置缓存的情况，如果并发确实很大，这也可能造成DB压力过大，还有缓存频繁更新的问题。解决思路： 
    • 对缓存查询加锁，如果KEY不存在，就加锁，然后查DB入缓存，然后解锁；其他进程如果发现有锁就等待，然后等解锁后返回数据或者进入DB查询。
  4. 缓存预热：目的就是在系统上线前，将数据加载到缓存中。解决思路： 
    • 数据量不大的话，在系统启动的时候直接加载。
    • 自己写个简单的缓存预热程序。
  5. 缓存算法： 
    • FIFO算法：First in First out，先进先出。原则：一个数据最先进入缓存中，则应该最早淘汰掉。也就是说，当缓存满的时候，应当把最先进入缓存的数据给淘汰掉。
    • LFU算法：Least Frequently Used，最不经常使用算法。
    • LRU算法：Least Recently Used，近期最少使用算法。
    • LRU和LFU的区别。LFU算法是根据在一段时间里数据项被使用的次数选择出最少使用的数据项，即根据使用次数的差异来决定。而LRU是根据使用时间的差异来决定的。

用redis实现分布式锁

  1. 主要使用的命令： 
    • setnx key val。当且仅当key不存在时，set一个key为val的字符串，返回1；若key存在，则什么都不做，返回0。
    • expire key timeout。为key设置一个超时时间，单位为second，超过这个时间锁会自动释放，避免死锁。
    • delete key。删除锁
  2. 实现思想： 
    • 使用setnx加锁，如果返回1，则说明加锁成功，并设置超时时间，避免系统挂了，锁没法释放。在finally中delete删除锁释放。
    • 如果需要设置超时等待时间，则可以加个while循环，在获取不到锁的情况下，进行循环获取锁，超时了则退出。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

redis底层原理

2017年11月30日 17:17:20 扶苏qaq 阅读数：20055

Redis对象类型简介

Redis是一种key/value型数据库，其中，每个key和value都是使用对象表示的。比如，我们执行以下代码：

 

[plain] view plain copy print?

  1. redis>SET message "hello redis"  


其中的key是message，是一个包含了字符串"message"的对象。而value是一个包含了"hello redis"的对象。

Redis共有五种对象的类型，分别是：

类型常量 对象的名称
REDIS_STRING 字符串对象
REDIS_LIST 列表对象
REDIS_HASH 哈希对象
REDIS_SET 集合对象
REDIS_ZSET 有序集合对象


Redis中的一个对象的结构体表示如下：
 

[cpp] view plain copy print?

  1. /* 
  2.  * Redis 对象 
  3.  */  
  4. typedef struct redisObject {  
  5.   
  6.     // 类型  
  7.     unsigned type:4;          
  8.   
  9.     // 不使用(对齐位)  
  10.     unsigned notused:2;  
  11.   
  12.     // 编码方式  
  13.     unsigned encoding:4;  
  14.   
  15.     // LRU 时间（相对于 server.lruclock）  
  16.     unsigned lru:22;  
  17.   
  18.     // 引用计数  
  19.     int refcount;  
  20.   
  21.     // 指向对象的值  
  22.     void *ptr;  
  23.   
  24. } robj;  

type表示了该对象的对象类型，即上面五个中的一个。但为了提高存储效率与程序执行效率，每种对象的底层数据结构实现都可能不止一种。encoding就表示了对象底层所使用的编码。下面先介绍每种底层数据结构的实现，再介绍每种对象类型都用了什么底层结构并分析他们之间的关系。

Redis对象底层数据结构

底层数据结构共有八种，如下表所示：

 

编码常量 编码所对应的底层数据结构
REDIS_ENCODING_INT long 类型的整数
REDIS_ENCODING_EMBSTR embstr 编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表和字典

字符串对象

字符串对象的编码可以是int、raw或者embstr。

如果一个字符串的内容可以转换为long，那么该字符串就会被转换成为long类型，对象的ptr就会指向该long，并且对象类型也用int类型表示。

普通的字符串有两种，embstr和raw。embstr应该是Redis 3.0新增的数据结构,在2.8中是没有的。如果字符串对象的长度小于39字节，就用embstr对象。否则用传统的raw对象。可以从下面这段代码看出：

[cpp] view plain copy print?

  1. #define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39  
  2. robj *createStringObject(char *ptr, size_t len) {  
  3.     if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)  
  4.         return createEmbeddedStringObject(ptr,len);  
  5.     else  
  6.         return createRawStringObject(ptr,len);  
  7. }  

embstr的好处有如下几点：

  • embstr的创建只需分配一次内存，而raw为两次（一次为sds分配对象，另一次为objet分配对象，embstr省去了第一次）。
  • 相对地，释放内存的次数也由两次变为一次。
  • embstr的objet和sds放在一起，更好地利用缓存带来的优势。

需要注意的是，redis并未提供任何修改embstr的方式，即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进行修改。

raw和embstr的区别可以用下面两幅图所示：

redis原理

redis原理

列表对象

列表对象的编码可以是ziplist或者linkedlist。

ziplist是一种压缩链表，它的好处是更能节省内存空间，因为它所存储的内容都是在连续的内存区域当中的。当列表对象元素不大，每个元素也不大的时候，就采用ziplist存储。但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性，插入的复杂度是O(N)，即每次插入都会重新进行realloc。如下图所示，对象结构中ptr所指向的就是一个ziplist。整个ziplist只需要malloc一次，它们在内存中是一块连续的区域。

redis原理

linkedlist是一种双向链表。它的结构比较简单，节点中存放pre和next两个指针，还有节点相关的信息。当每增加一个node的时候，就需要重新malloc一块内存。

redis原理

哈希对象

 

哈希对象的底层实现可以是ziplist或者hashtable。

ziplist中的哈希对象是按照key1,value1,key2,value2这样的顺序存放来存储的。当对象数目不多且内容不大时，这种方式效率是很高的。

hashtable的是由dict这个结构来实现的

[cpp] view plain copy print?

  1. typedef struct dict {  
  2.     dictType *type;  
  3.     void *privdata;  
  4.     dictht ht[2];  
  5.     long rehashidx; /* rehashing not in progress if rehashidx == -1 */  
  6.     int iterators; /* number of iterators currently running */  
  7. } dict;  

dict是一个字典，其中的指针dicht ht[2] 指向了两个哈希表

[cpp] view plain copy print?

  1. typedef struct dictht {  
  2.     dictEntry **table;  
  3.     unsigned long size;  
  4.     unsigned long sizemask;  
  5.     unsigned long used;  
  6. } dictht;  

dicht[0] 是用于真正存放数据，dicht[1]一般在哈希表元素过多进行rehash的时候用于中转数据。

dictht中的table用语真正存放元素了，每个key/value对用一个dictEntry表示，放在dictEntry数组中。

redis原理

 

集合对象

集合对象的编码可以是intset或者hashtable。

intset是一个整数集合，里面存的为某种同一类型的整数，支持如下三种长度的整数：

[cpp] view plain copy print?

  1. #define INTSET_ENC_INT16 (sizeof(int16_t))  
  2. #define INTSET_ENC_INT32 (sizeof(int32_t))  
  3. #define INTSET_ENC_INT64 (sizeof(int64_t))  

intset是一个有序集合，查找元素的复杂度为O(logN)，但插入时不一定为O(logN)，因为有可能涉及到升级操作。比如当集合里全是int16_t型的整数，这时要插入一个int32_t，那么为了维持集合中数据类型的一致，那么所有的数据都会被转换成int32_t类型，涉及到内存的重新分配，这时插入的复杂度就为O(N)了。是intset不支持降级操作。

有序集合对象

有序集合的编码可能两种，一种是ziplist，另一种是skiplist与dict的结合。

ziplist作为集合和作为哈希对象是一样的，member和score顺序存放。按照score从小到大顺序排列。它的结构不再复述。

skiplist是一种跳跃表，它实现了有序集合中的快速查找，在大多数情况下它的速度都可以和平衡树差不多。但它的实现比较简单，可以作为平衡树的替代品。它的结构比较特殊。下面分别是跳跃表skiplist和它内部的节点skiplistNode的结构体：

 

[cpp] view plain copy print?

  1. /* 
  2.  * 跳跃表 
  3.  */  
  4. typedef struct zskiplist {  
  5.     // 头节点，尾节点  
  6.     struct zskiplistNode *header, *tail;  
  7.     // 节点数量  
  8.     unsigned long length;  
  9.     // 目前表内节点的最大层数  
  10.     int level;  
  11. } zskiplist;  
  12. /* ZSETs use a specialized version of Skiplists */  
  13. /* 
  14.  * 跳跃表节点 
  15.  */  
  16. typedef struct zskiplistNode {  
  17.     // member 对象  
  18.     robj *obj;  
  19.     // 分值  
  20.     double score;  
  21.     // 后退指针  
  22.     struct zskiplistNode *backward;  
  23.     // 层  
  24.     struct zskiplistLevel {  
  25.         // 前进指针  
  26.         struct zskiplistNode *forward;  
  27.         // 这个层跨越的节点数量  
  28.         unsigned int span;  
  29.     } level[];  
  30. } zskiplistNode;  

head和tail分别指向头节点和尾节点，然后每个skiplistNode里面的结构又是分层的(即level数组)

用图表示，大概是下面这个样子：

redis原理

每一列都代表一个节点，保存了member和score，按score从小到大排序。每个节点有不同的层数，这个层数是在生成节点的时候随机生成的数值。每一层都是一个指向后面某个节点的指针。这种结构使得跳跃表可以跨越很多节点来快速访问。

前面说到了，有序集合ZSET是有跳跃表和hashtable共同形成的。

[cpp] view plain copy print?

  1. typedef struct zset {  
  2.     // 字典  
  3.     dict *dict;  
  4.     // 跳跃表  
  5.     zskiplist *zsl;  
  6. } zset;  

为什么要用这种结构呢。试想如果单一用hashtable，那可以快速查找、添加和删除元素，但没法保持集合的有序性。如果单一用skiplist，有序性可以得到保障，但查找的速度太慢O（logN）。

结尾

简单介绍了Redis的五种对象类型和它们的底层实现。事实上，Redis的高效性和灵活性正是得益于对于同一个对象类型采取不同的底层结构，并在必要的时候对二者进行转换；以及各种底层结构对内存的合理利用。

 

 

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

分享30道Redis面试题，面试官能问到的我都找到了

2018年09月11日 21:22:51 JAVA高级进阶 阅读数：398

redis原理

1、什么是Redis？简述它的优缺点？

Redis本质上是一个Key-Value类型的内存数据库，很像memcached，整个数据库统统加载在内存当中进行操作，定期通过异步操作把数据库数据flush到硬盘上进行保存。

因为是纯内存操作，Redis的性能非常出色，每秒可以处理超过 10万次读写操作，是已知性能最快的Key-Value DB。

Redis的出色之处不仅仅是性能，Redis最大的魅力是支持保存多种数据结构，此外单个value的最大限制是1GB，不像 memcached只能保存1MB的数据，因此Redis可以用来实现很多有用的功能。

比方说用他的List来做FIFO双向链表，实现一个轻量级的高性 能消息队列服务，用他的Set可以做高性能的tag系统等等。

另外Redis也可以对存入的Key-Value设置expire时间，因此也可以被当作一 个功能加强版的memcached来用。 Redis的主要缺点是数据库容量受到物理内存的限制，不能用作海量数据的高性能读写，因此Redis适合的场景主要局限在较小数据量的高性能操作和运算上。

2、Redis相比memcached有哪些优势？

(1) memcached所有的值均是简单的字符串，redis作为其替代者，支持更为丰富的数据类型

(2) redis的速度比memcached快很多

(3) redis可以持久化其数据

3、Redis支持哪几种数据类型？

String、List、Set、Sorted Set、hashes

4、Redis主要消耗什么物理资源？

内存。

5、Redis的全称是什么？

Remote Dictionary Server。

6、Redis有哪几种数据淘汰策略？

noeviction:返回错误当内存限制达到并且客户端尝试执行会让更多内存被使用的命令（大部分的写入指令，但DEL和几个例外）

allkeys-lru: 尝试回收最少使用的键（LRU），使得新添加的数据有空间存放。

volatile-lru: 尝试回收最少使用的键（LRU），但仅限于在过期集合的键,使得新添加的数据有空间存放。

allkeys-random: 回收随机的键使得新添加的数据有空间存放。

volatile-random: 回收随机的键使得新添加的数据有空间存放，但仅限于在过期集合的键。

volatile-ttl: 回收在过期集合的键，并且优先回收存活时间（TTL）较短的键,使得新添加的数据有空间存放。

7、Redis官方为什么不提供Windows版本？

因为目前Linux版本已经相当稳定，而且用户量很大，无需开发windows版本，反而会带来兼容性等问题。

8、一个字符串类型的值能存储最大容量是多少？

512M

9、为什么Redis需要把所有数据放到内存中？

Redis为了达到最快的读写速度将数据都读到内存中，并通过异步的方式将数据写入磁盘。

所以redis具有快速和数据持久化的特征。如果不将数据放在内存中，磁盘I/O速度为严重影响redis的性能。

在内存越来越便宜的今天，redis将会越来越受欢迎。 如果设置了最大使用的内存，则数据已有记录数达到内存限值后不能继续插入新值。

10、Redis集群方案应该怎么做？都有哪些方案？

1.codis。

目前用的最多的集群方案，基本和twemproxy一致的效果，但它支持在 节点数量改变情况下，旧节点数据可恢复到新hash节点。

2.redis cluster3.0自带的集群，特点在于他的分布式算法不是一致性hash，而是hash槽的概念，以及自身支持节点设置从节点。具体看官方文档介绍。

3.在业务代码层实现，起几个毫无关联的redis实例，在代码层，对key 进行hash计算，然后去对应的redis实例操作数据。 这种方式对hash层代码要求比较高，考虑部分包括，节点失效后的替代算法方案，数据震荡后的自动脚本恢复，实例的监控，等等。

11、Redis集群方案什么情况下会导致整个集群不可用？

有A，B，C三个节点的集群,在没有复制模型的情况下,如果节点B失败了，那么整个集群就会以为缺少5501-11000这个范围的槽而不可用。

12、MySQL里有2000w数据，redis中只存20w的数据，如何保证redis中的数据都是热点数据？

redis内存数据集大小上升到一定大小的时候，就会施行数据淘汰策略。

13、Redis有哪些适合的场景？

（1）会话缓存（Session Cache）

最常用的一种使用Redis的情景是会话缓存（session cache）。用Redis缓存会话比其他存储（如Memcached）的优势在于：Redis提供持久化。当维护一个不是严格要求一致性的缓存时，如果用户的购物车信息全部丢失，大部分人都会不高兴的，现在，他们还会这样吗？

幸运的是，随着 Redis 这些年的改进，很容易找到怎么恰当的使用Redis来缓存会话的文档。甚至广为人知的商业平台Magento也提供Redis的插件。

（2）全页缓存（FPC）

除基本的会话token之外，Redis还提供很简便的FPC平台。回到一致性问题，即使重启了Redis实例，因为有磁盘的持久化，用户也不会看到页面加载速度的下降，这是一个极大改进，类似PHP本地FPC。

再次以Magento为例，Magento提供一个插件来使用Redis作为全页缓存后端。

此外，对WordPress的用户来说，Pantheon有一个非常好的插件 wp-redis，这个插件能帮助你以最快速度加载你曾浏览过的页面。

（3）队列

Reids在内存存储引擎领域的一大优点是提供 list 和 set 操作，这使得Redis能作为一个很好的消息队列平台来使用。Redis作为队列使用的操作，就类似于本地程序语言（如Python）对 list 的 push/pop 操作。

如果你快速的在Google中搜索“Redis queues”，你马上就能找到大量的开源项目，这些项目的目的就是利用Redis创建非常好的后端工具，以满足各种队列需求。例如，Celery有一个后台就是使用Redis作为broker，你可以从这里去查看。

（4）排行榜/计数器

Redis在内存中对数字进行递增或递减的操作实现的非常好。集合（Set）和有序集合（Sorted Set）也使得我们在执行这些操作的时候变的非常简单，Redis只是正好提供了这两种数据结构。

所以，我们要从排序集合中获取到排名最靠前的10个用户–我们称之为“user_scores”，我们只需要像下面一样执行即可：

当然，这是假定你是根据你用户的分数做递增的排序。如果你想返回用户及用户的分数，你需要这样执行：

ZRANGE user_scores 0 10 WITHSCORES

Agora Games就是一个很好的例子，用Ruby实现的，它的排行榜就是使用Redis来存储数据的，你可以在这里看到。

（5）发布/订阅

最后（但肯定不是最不重要的）是Redis的发布/订阅功能。发布/订阅的使用场景确实非常多。我已看见人们在社交网络连接中使用，还可作为基于发布/订阅的脚本触发器，甚至用Redis的发布/订阅功能来建立聊天系统！

14、Redis支持的Java客户端都有哪些？官方推荐用哪个？

Redisson、Jedis、lettuce等等，官方推荐使用Redisson。

15、Redis和Redisson有什么关系？

Redisson是一个高级的分布式协调Redis客服端，能帮助用户在分布式环境中轻松实现一些Java的对象 (Bloom filter, BitSet, Set, SetMultimap, ScoredSortedSet, SortedSet, Map, ConcurrentMap, List, ListMultimap, Queue, BlockingQueue, Deque, BlockingDeque, Semaphore, Lock, ReadWriteLock, AtomicLong, CountDownLatch, Publish / Subscribe, HyperLogLog)。

16、Jedis与Redisson对比有什么优缺点？

Jedis是Redis的Java实现的客户端，其API提供了比较全面的Redis命令的支持；

Redisson实现了分布式和可扩展的Java数据结构，和Jedis相比，功能较为简单，不支持字符串操作，不支持排序、事务、管道、分区等Redis特性。Redisson的宗旨是促进使用者对Redis的关注分离，从而让使用者能够将精力更集中地放在处理业务逻辑上。

17、Redis如何设置密码及验证密码？

设置密码：config set requirepass 123456

授权密码：auth 123456

18、说说Redis哈希槽的概念？

Redis集群没有使用一致性hash,而是引入了哈希槽的概念，Redis集群有16384个哈希槽，每个key通过CRC16校验后对16384取模来决定放置哪个槽，集群的每个节点负责一部分hash槽。

19、Redis集群的主从复制模型是怎样的？

为了使在部分节点失败或者大部分节点无法通信的情况下集群仍然可用，所以集群使用了主从复制模型,每个节点都会有N-1个复制品.

20、Redis集群会有写操作丢失吗？为什么？

Redis并不能保证数据的强一致性，这意味这在实际中集群在特定的条件下可能会丢失写操作。

21、Redis集群之间是如何复制的？

异步复制

22、Redis集群最大节点个数是多少？

16384个。

23、Redis集群如何选择数据库？

Redis集群目前无法做数据库选择，默认在0数据库。

24、怎么测试Redis的连通性？

ping

25、Redis中的管道有什么用？

一次请求/响应服务器能实现处理新的请求即使旧的请求还未被响应。这样就可以将多个命令发送到服务器，而不用等待回复，最后在一个步骤中读取该答复。

这就是管道（pipelining），是一种几十年来广泛使用的技术。例如许多POP3协议已经实现支持这个功能，大大加快了从服务器下载新邮件的过程。

26、怎么理解Redis事务？

事务是一个单独的隔离操作：事务中的所有命令都会序列化、按顺序地执行。事务在执行的过程中，不会被其他客户端发送来的命令请求所打断。

事务是一个原子操作：事务中的命令要么全部被执行，要么全部都不执行。

27、Redis事务相关的命令有哪几个？

MULTI、EXEC、DISCARD、WATCH

28、Redis key的过期时间和永久有效分别怎么设置？

EXPIRE和PERSIST命令。

29、Redis如何做内存优化？

尽可能使用散列表（hashes），散列表（是说散列表里面存储的数少）使用的内存非常小，所以你应该尽可能的将你的数据模型抽象到一个散列表里面。

比如你的web系统中有一个用户对象，不要为这个用户的名称，姓氏，邮箱，密码设置单独的key,而是应该把这个用户的所有信息存储到一张散列表里面。

30、Redis回收进程如何工作的？

一个客户端运行了新的命令，添加了新的数据。

Redi检查内存使用情况，如果大于maxmemory的限制, 则根据设定好的策略进行回收。

一个新的命令被执行，等等。

所以我们不断地穿越内存限制的边界，通过不断达到边界然后不断地回收回到边界以下。

如果一个命令的结果导致大量内存被使用（例如很大的集合的交集保存到一个新的键），不用多久内存限制就会被这个内存使用量超越。

大家有对 Spring，MyBatis，Netty源码分析，高并发、高性能、分布式、微服务架构的原理，JVM性能优化、分布式架构等技术感兴趣的朋友可以加我的Java高级qq群：698581634，里面会分享这些成为架构师必备的知识体系，主要针对Java开发人员提升自己，突破瓶颈，相信你来学习，会有提升和收获。在这个群里会有你需要的内容  朋友们请抓紧时间加入进来吧。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

redis相关原理及面试官由浅到深必问的15大问题（高级）

2018年06月19日 10:28:00 java进阶架构师 阅读数：5155

0.redis是什么？

redis是nosql(也是个巨大的map) 单线程，但是可处理1秒10w的并发（数据都在内存中）

使用java对redis进行操作类似jdbc接口标准对mysql，有各类实现他的实现类，我们常用的是druid

其中对redis，我们通常用Jedis(也为我们提供了连接池JedisPool)

在redis中,key就是byte[](string)

redis的数据结构(value):

String,list,set,orderset,hash

每种数据结构对应不同的命令语句~

1.redis怎么使用？

先安装好redis，然后运行，在pom文件中引入依赖，在要使用redis缓存的类的mapper.xml文件配置redis的全限定名。引入redis的redis.properties文件（如果要更改配置就可以使用）

2.应用场景:

String :

1存储json类型对象,2计数器,3优酷视频点赞等

list(双向链表)

1可以使用redis的list模拟队列,堆,栈

2朋友圈点赞(一条朋友圈内容语句,若干点赞语句)

规定:朋友圈内容的格式:

1,内容: user:x:post:x content来存储;

2,点赞: post:x:good list来存储;(把相应头像取出来显示)

hash(hashmap)

1保存对象

2分组

3.为什么redis是单线程的都那么快？

1.数据存于内存

2.用了多路复用I/O

3.单线程

5.redis也可以进行发布订阅消息吗？

可以，（然后可以引出哨兵模式（后面会讲）怎么互相监督的，就是因为每隔2秒哨兵节点会发布对某节点的判断和自身的信息到某频道，每个哨兵订阅该频道获取其他哨兵节点和主从节点的信息，以达到哨兵间互相监控和对主从节点的监控）和很多专业的消息队列系统（例如Kafka、RocketMQ）相比，Redis的发布订阅略显粗糙，例如无法实现消息堆积和回溯。但胜在足够简单。

redis原理

6.redis能否将数据持久化，如何实现？

能，将内存中的数据异步写入硬盘中，两种方式：RDB（默认）和AOF

RDB持久化原理：通过bgsave命令触发，然后父进程执行fork操作创建子进程，子进程创建RDB文件，根据父进程内存生成临时快照文件，完成后对原有文件进行原子替换（定时一次性将所有数据进行快照生成一份副本存储在硬盘中）

优点：是一个紧凑压缩的二进制文件，Redis加载RDB恢复数据远远快于AOF的方式。

缺点：由于每次生成RDB开销较大，非实时持久化，

AOF持久化原理：开启后，Redis每执行一个修改数据的命令，都会把这个命令添加到AOF文件中。

优点：实时持久化。

缺点：所以AOF文件体积逐渐变大，需要定期执行重写操作来降低文件体积，加载慢

7.主从复制模式下，主挂了怎么办？redis提供了哨兵模式（高可用）

何谓哨兵模式？就是通过哨兵节点进行自主监控主从节点以及其他哨兵节点，发现主节点故障时自主进行故障转移。

redis原理

8.哨兵模式实现原理？（2.8版本或更高才有）

1.三个定时监控任务：

1.1 每隔10s，每个S节点（哨兵节点）会向主节点和从节点发送info命令获取最新的拓扑结构

1.2 每隔2s，每个S节点会向某频道上发送该S节点对于主节点的判断以及当前Sl节点的信息，

同时每个Sentinel节点也会订阅该频道，来了解其他S节点以及它们对主节点的判断（做客观下线依据）

1.3 每隔1s，每个S节点会向主节点、从节点、其余S节点发送一条ping命令做一次心跳检测(心跳检测机制)，来确认这些节点当前是否可达

2.主客观下线：

2.1主观下线：根据第三个定时任务对没有有效回复的节点做主观下线处理

2.2客观下线：若主观下线的是主节点，会咨询其他S节点对该主节点的判断，超过半数，对该主节点做客观下线

3.选举出某一哨兵节点作为领导者，来进行故障转移。选举方式：raft算法。每个S节点有一票同意权，哪个S节点做出主观下线的时候，就会询问其他S节点是否同意其为领导者。获得半数选票的则成为领导者。基本谁先做出客观下线，谁成为领导者。

4.故障转移（选举新主节点流程）：

.

redis原理

9.redis集群（采用虚拟槽方式，高可用）原理（和哨兵模式原理类似，3.0版本或以上才有）？

1.Redis集群内节点通过ping/pong消息实现节点通信，消息不但可以传播节点槽信息，还可以传播其他状态如：主从状态、节点故障等。因此故障发现也是通过消息传播机制实现的，主要环节包括：主观下线（pfail）和客观下线（fail）

2.主客观下线：

2.1主观下线：集群中每个节点都会定期向其他节点发送ping消息，接收节点回复pong消息作为响应。如果通信一直失败，则发送节点会把接收节点标记为主观下线（pfail）状态。

2.2客观下线：超过半数，对该主节点做客观下线

3.主节点选举出某一主节点作为领导者，来进行故障转移。

4.故障转移（选举从节点作为新主节点）

10.缓存更新策略（即如何让缓存和mysql保持一致性）？

redis原理

10.1 key过期清除（超时剔除）策略

惰性过期（类比懒加载，这是懒过期）：只有当访问一个key时，才会判断该key是否已过期，过期则清除。该策略可以最大化地节省CPU资源，却对内存非常不友好。极端情况可能出现大量的过期key没有再次被访问，从而不会被清除，占用大量内存。

定期过期：每隔一定的时间，会扫描一定数量的数据库的expires字典中一定数量的key，并清除其中已过期的key。该策略是前两者的一个折中方案。通过调整定时扫描的时间间隔和每次扫描的限定耗时，可以在不同情况下使得CPU和内存资源达到最优的平衡效果。

(expires字典会保存所有设置了过期时间的key的过期时间数据，其中，key是指向键空间中的某个键的指针，value是该键的毫秒精度的UNIX时间戳表示的过期时间。键空间是指该Redis集群中保存的所有键。)

问：比如这么个场景，我设计了很多key，过期时间是5分钟，当前内存占用率是50%。但是5分钟到了，内存占用率还是很高，请问为什么？

Redis中同时使用了惰性过期和定期过期两种过期策略，即使过期时间到了，但是有部分并没有真正删除，等待惰性删除。

为什么有定期还要有惰性呢？其实很简单，比如10万个key就要过期了，Redis默认是100ms检查一波。如果他检查出10万个即将要清除，那他接下来的时间基本都是在干这些清空内存的事了，那肯定影响性能，所以他只会部分删除，剩下的等惰性

10.2 Redis的内存淘汰策略

Redis的内存淘汰策略是指在Redis的用于缓存的内存不足时，怎么处理需要新写入且需要申请额外空间的数据。

noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。

allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。

allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。

volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。

volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。

volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。

11.缓存粒度控制？

redis原理

12.如何防止缓存穿透？

（缓存穿透指的是查询一个根本不存在的数据，缓存层不命中，又去查存储层，又不命中。但如果有大量这种查询不存在的数据的请求过来，会对存储层有较大压力，若是恶意攻击，后果就）

redis原理

12.1：缓存空值存在的问题：

redis原理

12.2：布隆过滤器：

redis原理

布隆过滤器存在的问题：相对来说布隆过滤器搞起来代码还是比较复杂的，现阶段我们暂时还不需要，后面实在需要再考虑去做，什么阶段做什么样的事情，不是说这个系统一下子就能做的各种完美。

13.无底洞优化？

造成原因：redis分布式越来越多，导致性能反而下降，因为键值分布到更多的 节点上，所以无论是Memcache还是Redis的分布式，批量操作通常需要从不 同节点上获取，相比于单机批量操作只涉及一次网络操作，分布式批量操作 会涉及多次网络时间。 即分布式过犹不及。

redis原理

14.雪崩优化

如果缓存层由于某些原因不能提供服务，于是所有的请求都会达到存储层，存储层的调用量会暴增，造成存储层也会级联宕机的情况。

redis原理

15.热点key优化

当前key是一个热点key（例如一个热门的娱乐新闻），并发量非常大。

redis原理

相关推荐