键值对字符串

char* 与 SDS

char* 的不足：

• 操作效率低：获取长度需遍历，O(N)复杂度

• 二进制不安全：无法存储包含 \0 的数据

SDS 的优势：

• 操作效率高：获取长度无需遍历，O(1)复杂度（通过len和alloc,快速获取字符长度大小以及跳转到字符串末尾）

• 二进制安全：因单独记录长度字段，所以可存储包含 \0 的数据

• 兼容 C 字符串函数，可直接使用字符串 API

• 紧凑型内存设计（按照字符串类型，len和alloc使用不同的类型节约内存，并且关闭内存对齐来达到内存高效利用，在redis中除了sds，intset和ziplist也有类似的目底）

• 避免频繁的内存分配。除了sds部分类型存在预留空间，sds设计了sdsfree和sdsclear两种字符串清理函数，其中sdsclear，只是修改len为0以及buf为'\0'，并不会实际释放内存，避免下次使用带来的内存开销

SDS中的优化

Redis 在操作 SDS 时，为了避免频繁操作字符串时，每次「申请、释放」内存的开销，还做了这些优化：

• 内存预分配：SDS 扩容，会多申请一些内存（小于 1MB 翻倍扩容，大于 1MB 按 1MB 扩容）

• 多余内存不释放：SDS 缩容，不释放多余的内存，下次使用可直接复用这些内存

这种策略，是以多占一些内存的方式，换取「追加」操作的速度。这个内存预分配策略，详细逻辑可以看 sds.c 的 sdsMakeRoomFor 函数。

SDS在Redis内部模块中的实现

SDS 字符串在 Redis 内部模块实现中也被广泛使用，在 Redis server 和客户端的实现中，能找到使用 SDS 字符串的地方很多：

• Redis 中所有 key 的类型就是 SDS（详见 db.c 的 dbAdd 函数）

• Redis Server 在读取 Client 发来的请求时，会先读到一个缓冲区中，这个缓冲区也是 SDS（详见 server.h 中 struct client 的 querybuf 字段）

• 写操作追加到 AOF 时，也会先写到 AOF 缓冲区，这个缓冲区也是 SDS （详见 server.h 中 struct client 的 aof_buf 字段）

Hash表

dict数据结构

• Redis 中的 dict 数据结构，采用「链式哈希」的方式存储，当哈希冲突严重时，会开辟一个新的哈希表，翻倍扩容，并采用「渐进式 rehash」的方式迁移数据

• Redis 中凡是需要 O(1) 时间获取 k-v 数据的场景，都使用了 dict 这个数据结构，也就是说 dict 是 Redis 中重中之重的「底层数据结构」

• dict 封装好了友好的「增删改查」API，并在适当时机「自动扩容、缩容」，这给上层数据类型（Hash/Set/Sorted Set）、全局哈希表的实现提供了非常大的便利

• 例如，Redis 中每个 DB 存放数据的「全局哈希表、过期key」都用到了 dict：

  // server.h
  typedef struct redisDb {dict *dict;     // 全局哈希表，数据键值对存在这dict *expires;  // 过期 key + 过期时间 存在这...
  }
  

rehash

• 所谓「渐进式 rehash」是指，把很大块迁移数据的开销，平摊到多次小的操作中，目的是降低主线程的性能影响

• 「全局哈希表」在触发渐进式 rehash 的情况有 2 个：

  • 增删改查哈希表时：每次迁移 1 个哈希桶（ dict.c 中的 _dictRehashStep 函数）

  • 定时 rehash：如果 dict 一直没有操作，无法渐进式迁移数据，那主线程会默认每间隔 100ms 执行一次迁移操作。这里一次会以 100 个桶为基本单位迁移数据，并限制如果一次操作耗时超时 1ms 就结束本次任务，待下次再次触发迁移（dict.c 的 dictRehashMilliseconds 函数）

• dict 在负载因子超过 1 时（used: bucket size >= 1），会触发 rehash。但如果 Redis 正在 RDB 或 AOF rewrite，为避免父进程大量写时复制，会暂时关闭触发 rehash。但这里有个例外，如果负载因子超过了 5（哈希冲突已非常严重），依旧会强制做 rehash（重点）

• dict 在 rehash 期间，查询旧哈希表找不到结果，还需要在新哈希表查询一次

• SipHash 哈希算法是在 Redis 4.0 才开始使用的，3.0-4.0 使用的是 MurmurHash2 哈希算法，3.0 之前是 DJBX33A 哈希算法

问题解答

• redis的dict结构核心就是链式hash，其原理其实和JDK的HashMap类似（JDK1.7之前的版本，1.8开始是红黑树或链表），这里就有一个问题为什么Redis要使用链式而不引入红黑树呢，或者直接使用红黑树？

  • hash冲突不使用红黑树：redis需要高性能，如果hash冲突使用红黑树，红黑树和链表的转换会引起不必要的开销（hash冲突不大的情况下红黑树其实比链表沉重，还会浪多余的空间）

  • dict不采用红黑树：在负载因子较低，hash冲突较低的情况下，hash表的效率O(1)远远高于红黑树

  • 当采用渐进式rehash的时候，以上问题都可以解决

• 何为渐进式rehash？本质原理是什么？当内存使用变小会缩容吗？

  • 渐进式rehash的本质是分治思想，通过把大任务划分成一个个小任务，每个小任务只执行一小部分数据，最终完成整个大任务的过程

  • 渐进式rehash可以在不影响运行中的redis使用来完成整改hash表的扩容（每次可以控制只执行1ms）

  • 初步判定会，因为dictResize中用于计算hash表大小的minimal就是来源于实际使用的大小，并且htNeedsResize方法中（used*100/size < HASHTABLE_MIN_FILL）来判断是否触发缩容来节约内存，而缩容也是渐进式rehash

渐进式rehash怎么去执行？

在了解渐进式rehash之前，我们需要了解一个事情，就是正在运行执行任务的redis，其实本身就是一个单线程的死循环（不考虑异步以及其他fork的场景），其循环的方法为aeMain(),位于ae.c文件中，在这个循环中每次执行都会去尝试执行已经触发的时间事件和文件事件，而渐进式rehash的每个小任务就是位于redis，serverCron时间事件中，redis每次循环的时候其实都会经过如下所示的调用流程：

• serverCron -> updateDictResizePolicy (先判断是否能执行rehash，当AOF重写等高压力操作时候不执行)

• serverCron -> databasesCron -> incrementallyRehash -> dictRehashMilliseconds -> dictRehash (dictRehashMilliseconds默认要求每次rehash最多只能执行1ms)

• 通过这种方式最终完成整改hash表的扩容

SDS

redisObject

• 要想理解 Redis 数据类型的设计，必须要先了解 redisObject。Redis 的 key 是 String 类型，但 value 可以是很多类型（String/List/Hash/Set/ZSet等），所以 Redis 要想存储多种数据类型，就要设计一个通用的对象进行封装，这个对象就是 redisObject。

• 代码中定义如下：

  // server.h
  typedef struct redisObject {unsigned type:4;unsigned encoding:4;unsigned lru:LRU_BITS;int refcount;void *ptr;
  } robj;
  

• 其中，最重要的 2 个字段：

  • type：面向用户的数据类型（String/List/Hash/Set/ZSet等）

  • encoding：每一种数据类型，可以对应不同的底层数据结构来实现（SDS/ziplist/intset/hashtable/skiplist等）

• 举例说明

  • 例如 String，可以用 embstr（嵌入式字符串，redisObject 和 SDS 一起分配内存），也可以用 rawstr（redisObject 和 SDS 分开存储）实现。

  • 又或者，当用户写入的是一个「数字」时，底层会转成 long 来存储，节省内存。

  • 同理，Hash/Set/ZSet 在数据量少时，采用 ziplist 存储，否则就转为 hashtable 来存。

• 所以，redisObject 的作用在于：

  • 为多种数据类型提供统一的表示方式

  • 同一种数据类型，底层可以对应不同实现，节省内存

  • 支持对象共享和引用计数，共享对象存储一份，可多次使用，节省内存

• redisObject 更像是连接「上层数据类型」和「底层数据结构」之间的桥梁。

String

• String 类型的实现，底层对应 3 种数据结构：

  • embstr：小于 44 字节，嵌入式存储，redisObject 和 SDS 一起分配内存，只分配 1 次内存

  • rawstr：大于 44 字节，redisObject 和 SDS 分开存储，需分配 2 次内存

  • long：整数存储（小于 10000，使用共享对象池存储，但有个前提：Redis 没有设置淘汰策略，详见 object.c 的 tryObjectEncoding 函数）

ziplist

• ziplist 的特点：

  • 连续内存存储：每个元素紧凑排列，内存利用率高

  • 变长编码：存储数据时，采用变长编码（满足数据长度的前提下，尽可能少分配内存）

  • 寻找元素需遍历：存放太多元素，性能会下降（适合少量数据存储）

  • 级联更新：更新、删除元素，会引发级联更新（因为内存连续，前面数据膨胀/删除了，后面要跟着一起动）

• List、Hash、Set、ZSet 底层都用到了 ziplist。

intset

intset 的特点：

• Set 存储如果都是数字，采用 intset 存储

• 变长编码：数字范围不同，intset 会选择 int16/int32/int64 编码（intset.c 的 _intsetValueEncoding 函数）

• 有序：intset 在存储时是有序的，这意味着查找一个元素，可使用「二分查找」（intset.c 的 intsetSearch 函数）

• 编码升级/降级：添加、更新、删除元素，数据范围发生变化，会引发编码长度升级或降级

SDS使用嵌入式字符串的条件

• SDS 判断是否使用嵌入式字符串的条件是 44 字节

• jemalloc 分配内存机制，jemalloc 为了减少分配的内存空间大小不是2的幂次，在每次分配内存的时候都会返回2的幂次的空间大小，比如我需要分配5字节空间，jemalloc 会返回8字节，15字节会返回16字节。其常见的分配空间大小有：8, 16, 32, 64, ..., 2kb, 4kb, 8kb。

• 但是这种方式也可能会造成，空间的浪费，比如我需要33字节，结果给我64字节，为了解决这个问题jemalloc将内存分配划分为，小内存（small_class）和大内存（large_class）通过不同的内存大小使用不同阶级策略，比如小内存允许存在48字节等方式。

• 嵌入式字符串会把 redisObject 和 SDS 一起分配内存，那在存储时结构是这样的：

  • redisObject：16 个字节

  • SDS：sdshdr8（3 个字节）+ SDS 字符数组（N 字节 + \0 结束符 1 个字节）

• Redis 规定嵌入式字符串最大以 64 字节存储，所以 N = 64 - 16(redisObject) - 3(sdshr8) - 1(\0)， N = 44 字节。

redis充分提高内存利用率的手段

• 淘汰不再使用的内存空间

• 紧凑型的内存设计

  • 设计实现了SDS

  • 设计实现了ziplist

  • 设计实现了intset

  • 搭配redisObject

  • 设计了嵌入式字符串

• 实例内存共享

  • 设计了共享对象（共享内存大部是常量实例）

有序集合

ZSet

• ZSet 当数据比较少时，采用 ziplist 存储，每个 member/score 元素紧凑排列，节省内存

• 当数据超过阈值（zset-max-ziplist-entries、zset-max-ziplist-value）后，转为 hashtable + skiplist 存储，降低查询的时间复杂度

• hashtable 存储 member->score 的关系，所以 ZSCORE 的时间复杂度为 O(1)

skiplist

• skiplist 是一个「有序链表 + 多层索引」的结构，把查询元素的复杂度降到了 O(logN)，服务于 ZRANGE/ZREVRANGE 这类命令

• skiplist 的多层索引，采用「随机」的方式来构建，也就是说每次添加一个元素进来，要不要对这个元素建立「多层索引」？建立「几层索引」？都要通过「随机数」的方式来决定

• 每次随机一个 0-1 之间的数，如果这个数小于 0.25（25% 概率），那就给这个元素加一层指针，持续随机直到大于 0.25 结束，最终确定这个元素的层数（层数越高，概率越低，且限制最多 64 层，详见 t_zset.c 的 zslRandomLevel 函数）

• 这个预设「概率」决定了一个跳表的内存占用和查询复杂度：概率设置越低，层数越少，元素指针越少，内存占用也就越少，但查询复杂会变高，反之亦然。这也是 skiplist 的一大特点，可通过控制概率，进而控制内存和查询效率

• skiplist 新插入一个节点，只需修改这一层前后节点的指针，不影响其它节点的层数，降低了操作复杂度（相比平衡二叉树的再平衡，skiplist 插入性能更优）

问题解答

• 关于 Redis 的 ZSet 为什么用 skiplist 而不用平衡二叉树实现的问题，原因是：

  • skiplist 更省内存：25% 概率的随机层数，可通过公式计算出 skiplist 平均每个节点的指针数是 1.33 个，平衡二叉树每个节点指针是 2 个（左右子树）

  • skiplist 遍历更友好：skiplist 找到大于目标元素后，向后遍历链表即可，平衡树需要通过中序遍历方式来完成，实现也略复杂

  • skiplist 更易实现和维护：扩展 skiplist 只需要改少量代码即可完成，平衡树维护起来较复杂

• 在使用跳表和哈希表相结合的双索引机制时，在获得高效范围查询和单点查询的同时，有哪些不足之处？

  • 这种发挥「多个数据结构」的优势，来完成某个功能的场景，最大的特点就是「空间换时间」，所以内存占用多是它的不足。

  • 不过也没办法，想要高效率查询，就得牺牲内存，鱼和熊掌不可兼得。

  • 不过 skiplist 在实现时，Redis 作者应该也考虑到这个问题了，就是上面提到的这个「随机概率」，Redis 后期维护可以通过调整这个概率，进而达到「控制」查询效率和内存平衡的结果。当然，这个预设值是固定写死的，不可配置，应该是 Redis 作者经过测试和权衡后的设定，我们这里只需要知晓原理就好。

• redis作为一款优化到极致的中间件，不会单纯使用一种数据类型去实现一个功能，而会根据当前的情况选择最合适的数据结构，比如zset就是dict + skiplist，甚至当元素较少的时候zsetAdd方法会优先选择ziplist而不直接使用skiplist，以到达节约内存的效果（当小key泛滥的时候很有效果），当一种数据结构存在不足的情况下，可以通过和其它数据结构搭配来弥补自身的不足（软件设计没有银弹，只有最合适）

• redis仰仗c语言指针的特性，通过层高level数组实现的skiplist从内存和效率上来说都是非常优秀的，如果对比JDK的ConcurrentSkipListMap的实现（使用了大量引用和频繁的new操作），指针的优势无疑显现出来了

• skiplist的随机率层高。既保证每层的数量相对为下一层的一半，又保证了代码执行效率

quicklist，listpack

ziplist

• ziplist 设计的初衷就是「节省内存」，在存储数据时，把内存利用率发挥到了极致：

  • 数字按「整型」编码存储，比直接当字符串存内存占用少

  • 数据「长度」字段，会根据内容的大小选择最小的长度编码

  • 甚至对于极小的数据，干脆把内容直接放到了「长度」字段中（前几个位表示长度，后几个位存数据）

• 但 ziplist 的劣势也很明显：

  • 寻找元素只能挨个遍历，存储过长数据，查询性能很低

  • 每个元素中保存了「上一个」元素的长度（为了方便反向遍历），这会导致上一个元素内容发生修改，长度超过了原来的编码长度，下一个元素的内容也要跟着变，重新分配内存，进而就有可能再次引起下一级的变化，一级级更新下去，频繁申请内存

quicklist

• 想要缓解 ziplist 的问题，比较简单直接的方案就是，多个数据项，不再用一个 ziplist 来存，而是分拆到多个 ziplist 中，每个 ziplist 用指针串起来，这样修改其中一个数据项，即便发生级联更新，也只会影响这一个 ziplist，其它 ziplist 不受影响，这种方案就是 quicklist

   qucklist: ziplist1(也叫quicklistNode) <-> ziplist2 <-> ziplist3 <-> ... 
  

List

• List 数据类型底层实现，就是用的 quicklist，因为它是一个链表，所以 LPUSH/LPOP/RPUSH/RPOP 的复杂度是 O(1)

• List 中每个 ziplist 节点可以存的元素个数/总大小，可以通过 list-max-ziplist-size 配置：

  • 正数：ziplist 最多包含几个数据项

  • 负数：取值 -1 ~ -5，表示每个 ziplist 存储最大的字节数，默认 -2，每个ziplist 8KB

  • ziplist 超过上述配置，添加新元素就会新建 ziplist 插入到链表中。

• List 因为更多是两头操作，为了节省内存，还可以把中间的 ziplist「压缩」，具体可看 list-compress-depth 配置项，默认配置不压缩

listpack

• 要想彻底解决 ziplist 级联更新问题，本质上要修改 ziplist 的存储结构，也就是不要让每个元素保存「上一个」元素的长度即可，所以才有了 listpack

• listpack 每个元素项不再保存上一个元素的长度，而是优化元素内字段的顺序，来保证既可以从前也可以向后遍历

• listpack 是为了替代 ziplist 为设计的，但因为 List/Hash/ZSet 都严重依赖 ziplist，所以这个替换之路很漫长，目前只有 Stream 数据类型用到了 listpack。set底层是intset和dict实现的，并没有使用到ziplist。

Stream使用的Radix Tree

Radix Tree的优势和不足

作为有序索引，Radix Tree 也能提供范围查询，和 B+ 树、跳表相比，你觉得 Radix Tree 有什么优势和不足么？

1. Radix Tree 优势

   Stream 在存消息时，推荐使用默认自动生成的「时间戳+序号」作为消息 ID，不建议自己指定消息 ID，这样才能发挥 Radix Tree 公共前缀的优势。

   • 本质上是前缀树，所以存储有「公共前缀」的数据时，比 B+ 树、跳表节省内存

   • 没有公共前缀的数据项，压缩存储，value 用 listpack 存储，也可以节省内存

   • 查询复杂度是 O(K)，只与「目标长度」有关，与总数据量无关

   • 这种数据结构也经常用在搜索引擎提示、文字自动补全等场景

2. Radix Tree 不足

   • 如果数据集公共前缀较少，会导致内存占用多

   • 增删节点需要处理其它节点的「分裂、合并」，跳表只需调整前后指针即可

   • B+ 树、跳表范围查询友好，直接遍历链表即可，Radix Tree 需遍历树结构

   • 实现难度高比 B+ 树、跳表复杂

每种数据结构都是在面对不同问题场景下，才被设计出来的，结合各自场景中的数据特点，使用优势最大的数据结构才是正解。

B+树和跳跃表的关联

• B+树和跳跃表这两种数据结构在本身设计上是有亲缘关系的，其实如果把B+树拉直来看不难发现其结构和跳跃表很相似，甚至B+树的父亲结点其实类似跳跃表的level层级。

• 在当前计算机硬件存储设计上，B+树能比跳表存储更大量级的数据，因为跳表需要通过增加层高来提高索引效率，而B+树只需要增加树的深度。此外B+树同一叶子的连续性更加符合当代计算机的存储结构。然而跳表的层高具有随机性，当层高较大的时候磁盘插入会带来一定的开销，且不利于分块。

Redis不使用B+树而选择跳表

因为数据有序性的实现B+树不如跳表，跳表的时间性能是优于B+树的（B+树不是二叉树，二分的效率是比较高的）。此外跳表最低层就是一条链表，对于需要实现范围查询的功能是比较有利的，而且Redis是基于内存设计的，无需考虑海量数据的场景。