Redis数据结构底层知识总结

共计 4719 个字符，预计需要花费 12 分钟才能阅读完成。

Redis 数据结构底层总结

本篇文章是基于 作者黄建宏 写的书 Redis 设计与实现 而做的笔记

数据结构与对象

Redis 中数据结构的底层实现包括以下对象：

String

Redis 中并没有直接使用 C 语言中的字符串，而是在其基础之上实现了字符串的数据结构，叫做 简单动态字符串（SDS）。

其内部的定义为：

/* Redis 简单动态字符串的数据结构 */
struct sdshdr {
    // 字符长度，记录 buf 数组中已使用的字节数量
    unsigned int len;
    // 当前可用空间，记录 buf 数组中未使用的字节数量
    unsigned int free;
    // 具体存放字符的 buf
    char buf[];
};

SDS 和 C 字符串的区别

1. 常数复杂度获取字符串长度

   因为 SDS 纪录了自身字符串中已经使用的长度和未使用的长度，所以可以在 O(1)的时间复杂度内获取到字符串长度，然而 C 字符串不得不通过遍历整个字符串才能获取到长度，其花费的则是 O(N)。

2. 杜绝缓冲区溢出

   和 C 字符串不同的是，SDS 会利用纪录下来的长度去检查自身是否还有足够的空间去容纳新的需求，如果不满足的话，会先进行扩容，然后才执行新的操作。

3. 减少修改字符串时带来的内存重分配次数

   C 字符串中每次进行增加和缩短的操作时，都会涉及到内存的重新分配，SDS 利用未使用空间来实现 空间预分配和惰性空间释放 这两种优化策略。

   • 空间预分配

     用于优化 SDS 的字符串 增长 操作：当要涉及到对 SDS 进行空间扩展的时候，程序不仅仅会为 SDS 分配修改所需要的空间，还会为 SDS 分配额外的未使用空间，好处在于在下次扩容的时候，如果未使用空间还足够使用的话，就使用未使用空间进行扩容。

   • 惰性空间

     用于优化 SDS 的字符串 缩短 操作：当要缩短 SDS 保存的字符串时，程序并不会立即使用内存重分配来回收缩短后多出来的字节，而是将其回收起来纪录到 free 空间中，以便将来继续使用。

4. 二进制安全

   C 字符串中判断结束的条件是遇见空字符，不同的是，SDS 则选择了通过自身的 len 属性的值来判断字符串是否结束，这样做的目的在于使得 SDS 不仅仅能够存储字符串，还能存储二进制。

5. 兼容部分 C 字符串函数

   通过遵循 C 字符串以空字符结尾的惯例，SDS 可以在有需要的时候重用 C 语言中的 string 函数库，比如对比函数，追加函数等等，从而实现代码的重用。

链表

链表提供了高效的结点重排能力，以及顺序性的结点访问方式，并且可以通过增删结点来灵活的调整链表的长度。

链表结点

每个链表结点使用的是一个 listNode 结构表示：

typedef struct listNode{
    // 前置结点
    struct listNode *prev;
    // 后置结点
    struct listNode * next;
    // 结点值
    void * value;  
}

链表

在此基础之上，Redis 通过封装了 listNode 实现双端链表，如下：

typedef struct list{
    // 表头节点
    listNode  * head;
    // 表尾节点
    listNode  * tail;
    // 链表长度
    unsigned long len;
    // 节点值复制函数
    void *(*dup) (void *ptr);
    // 节点值释放函数
    void (*free) (void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
}

list 结构为链表提供了表头指针 head、表尾指针 tail，以及链表长度计数器 len，而 dup、free 和 match 成员则是用于实现 多态链表 所需的类型特定函数：

• dup 函数用于 复制 链表结点所保存的值；
• free 函数用于 释放 链表结点所保存的值；
• match 函数用于 对比 链表结点所保存的值和另一个输入值是否相等；

Redis 的链表实现的特性总结如下：

• 双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是 O（1）。
• 无环：表头节点的 prev 指针和表尾节点的 next 都指向 NULL，对链表的访问时以 NULL 来做判断是否截止。
• 带表头指针和表尾指针：因为链表带有 head 指针和 tail 指针，程序获取链表头结点和尾节点的时间复杂度为 O(1)。
• 带链表长度计数器：链表中存有记录链表长度的属性 len。
• 多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表可以用来保存各种不同类型的值。

字典

字典由哈希表组成，而哈希表又由哈希结点组成。

哈希表结点

和链表一样，Redis 也自己实现了哈希表结点结构和哈希表结构，如下：

哈希表结点：

typeof struct dictEntry{
   // 键
   void *key;
   // 值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;
}

每个 dictEntry 结构都保存着一个键值对，分别对应属性 key 和 value，同时，next 属性是指向另外一个哈希表结点的指针，作用就是将多个哈希值相同的哈希结点连接起来，以此来解决键冲突的问题。

哈希表

Redis 在 dictEntry 的基础之上封装实现了哈希表，如下：

typedef struct dictht {
   // 哈希表数组
   dictEntry **table;
   // 哈希表大小
   unsigned long size;
   // 哈希表大小掩码，用于计算索引值
   unsigned long sizemask;
   // 该哈希表已有节点的数量
   unsigned long used;
}

其中需要提到的是 sizemark，这个属性和哈希值一起决定一个键应该被放到 table 数组中的哪个索引上面。

字典

Redis 在哈希表的基础上封装了 dictht 实现字典，如下：

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privedata;
    // 哈希表
    dictht  ht[2];
    // rehash 索引
    int rehashidx;
}

type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0]哈希表，ht[1]哈希表只会在对 ht[0]哈希表进行 rehash 时使用，而 rehashidx 则决定了 rehash 的进度，如果没有进行 rehash，其值则为 -1。

哈希算法

当要把一个新的键值对添加到字典里面时，程序先要根据键值对中的键值计算出哈希值，再计算出索引值，然后将包含新键值对的哈希表结点放到哈希表数组的指定索引上面。

Redis 使用 murmurhash 算法来计算哈希值

解决键冲突

键冲突：存在两个或者两个以上的键被分配到了哈希表数组的同一个索引上面。

解决办法：Redis 的哈希表使用 开链法 来解决冲突，每个哈希表结点都存在一个 next 指针，多个哈希表值可以用 next 指针来构成一个单向链表，被分配到同一个索引上的多个结点可以用这个单向链表连接起来，从而解决键冲突问题。

需要注意的是，因为考虑到下次方便再次读取，因此总是将冲突的新结点插入到链表的表头位置，也就是已有其他结点的前面。

rehash

当哈希表的负载因子（已有数量/表数量）达到一个阀值以后，再次保存新的键值对时，冲突的几率将逐渐增加，因此需要进行响应的扩展（收缩）。

以扩展为例，程序需要经过以下步骤（腾笼换鸟）：

1. 扩展空间：为字典的 ht[1]哈希表分配空间，其空间将会被扩展到第一个大于等于 ht[0].used*2^n 的整数值；
2. 数据迁移：将保存在 ht[0]上的所有键值对迁移到 ht[1]中；
3. 交换：迁移完后，释放掉 ht[0]，将现在的 ht[1]设置为 ht[0]，并且为 ht[1]新创建一个空白哈希表，实现了相互交换的过程；

渐进式 rehash

为了避免一次性交换所造成的性能影响，Redis 采用的是渐进式 rehash，也就是说，将会 分多次、渐进式 的完成数据的迁移。所以会同时存在两个哈希表数组，并不会急着一次性的将数 ht[0]的数据迁移到 ht[1]中，而是在每次操作的同时，将部分的 ht[0]中的数据保存到 ht[1]中，采用愚公移山的方式最终将 ht[0]中的数据搬完，为了避免 ht[0]中的数据不断增加，相关的增加的操作都会作用在 ht[1]之上，最后，搬完后的操作和之前的操作是一致的。

它的 优点 在于：采用了分而治之的方式，将 rehash 键值对所需的操作均摊到字典的每个添加、删除、查找和更新操作之上，从而避免集中式 rehash 而带来的庞大计算量。

我认为它的缺点也是存在的，譬如在查询的时候，可能在 ht[0]中查找不到，还得跑到 ht[1]中查找，无形中增加了开销。

跳跃表

跳跃表是一种有序数据结构，它通过在每个结点中维持多个指向其它结点的指针，从而达到快速访问结点的目的。其查找的时间复杂度平均可以达到 O(logn)，最坏 O(N)，还可以通过顺序性操作来批量处理结点。

目前，Redis 中只有两个地方用到了跳跃表，一个是 有序集合键 ，另外一个是 集群结点 中用作内部数据结构。

跳跃表由多个跳跃结点组成：

跳跃表结点

typedef struct zskiplistNode{
    // 层
    struct zskiplistLevel{
    // 前进指针
    struct zskiplistNode *forward;
    // 跨度
    unsigned int span;
    } level[];
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
}

1. 层：level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针。
2. 前进指针：用于指向表尾方向的前进指针
3. 跨度：用于记录两个节点之间的距离
4. 后退指针：用于从表尾向表头方向访问节点
5. 分值和成员：跳跃表中的所有节点都按分值从小到大排序。成员对象指向一个字符串，这个字符串对象保存着一个 SDS 值

跳跃表

typedef struct zskiplist {
     // 表头节点和表尾节点
     structz skiplistNode *header,*tail;
     // 表中节点数量
     unsigned long length;
     // 表中层数最大的节点的层数
     int level;
}zskiplist;

其搜索的步骤为，先通过头结点定位到跳跃表结点，然后通过层去定位到下一个跳跃表结点的位置，直到找到给定分值的结点。

整数集合

前提：当一个集合只包含整数值元素，并且这个集合的元素数量不多时。

typedef struct intset{
    // 编码方式
    uint32_t enconding;
   // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组    
    int8_t contents[];
}

因为可能存在存入的整数不符合已存在集合中的编码格式，因此需要使用 升级策略 来解决。

1. 扩展空间：根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
2. 转换编码：将底层数组现有的所有元素都转换成新的编码格式，重新分配空间
3. 添加：将新元素加入到底层数组中

一旦对数组进行了升级，编码就会一直保存升级后的状态。

压缩列表

压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个结点，每个结点可以保存一个字节数或者一个整数值。

本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-09/146889.htm