Redis的数据结构

Redis 的键值对中的 key 就是字符串对象，而 value 可以是字符串对象，也可以是集合数据类型的对象

redis的键值数据库

String（SDS）

C语言字符数组以"\0"结尾标识字符串的结束

C语言实现的字符数组有两个缺陷

• a. 获取字符串长度的时间复杂度为 O（N）
• b. 字符串的结尾是以 “\0” 字符标识，字符串里面不能包含有 “\0” 字符 ，因此不能保存二进制数据

（redis中的SDS结构）

Redis 的 SDS 结构在原本字符数组之上，增加了三个元数据：len、alloc、flags，用来解决 C 语言字符串的缺陷

链表（List）--->压缩链表--->quickList

链表节点

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

链表

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

链表的优势与缺陷

Redis 的链表实现优点如下：

• listNode 链表节点的结构里带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的 时间复杂度只需O(1) ，而且这两个指针都可以指向 NULL，所以链表是无环链表；
• list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)；
• list 结构因为提供了链表节点数量 len，所以获取链表中的 节点数量的时间复杂度只需O(1) ；
• listNode 链表节使用 void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数，因 此链表节点可以保存各种不同类型的值 ；

最终实现zipList(压缩列表)-->quickList

压缩列表在表头有三个字段：

• zlbytes ，记录整个压缩列表占用对内存字节数；

• zltail ，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；

• zllen ，记录压缩列表包含的节点数量；

• zlend ，标记压缩列表的结束点，固定值 0xFF（十进制255）。 压缩列表节点包含三部分内容：

• prevlen ，记录了 「前一个节点」 的长度，目的是为了实现从后向前遍历；

• encoding ，记录了当前节点实际数据的 「类型和长度」 ，类型主要有两种：字符串和整数。

• data ，记录了当前节点的实际数据，类型和长度都由 encoding 决定；

压缩列表连锁更新所面对的问题

压缩列表除了查找复杂度高的问题，还有一个问题。 压缩列表 新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配 。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降 。

前面提到，压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配：

• 如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；
• 如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；

哈希表

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

哈希节点
typedef struct dictEntry {
    //键值对中的键
    void *key;
  
    //键值对中的值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

渐进式 rehash （避免因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求）

为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况，所以 Redis 采用了渐进式 rehash，也就是将数据的迁移的 工作不再是一次性迁移完成，而是分多次迁移。

渐进式 rehash 步骤如下：

1. 给 「哈希表 2」 分配空间；

2. 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会 顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上；

3. 随着处理客户端发起的哈希表操作请求数量越多，最终 在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作

rehash 触发条件

介绍了 rehash 那么多，还没说什么时情况下会触发 rehash 操作呢？

rehash 的触发条件跟 负载因子（load factor） 有关系。

负载因子可以通过下面这个公式计算：

触发 rehash 操作的条件，主要有两个：

• 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是 没有执行 RDB 快照或没有进行 AOF 重写 的时候，就会进行 rehash 操作。

• 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会 强制进行 rehash 操作。

整数集合

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

整数集合升级操作

整数集合会有一个升级规则，就是当我们将一个新元素加入到整数集合里面，如果 新元素的类型（int32_t）比整数集合现有所有元素的类型（int16_t）都要长 时，整数集合需要 先进行升级 ，也就是 按新元素的类型（int32_t）扩展 contents 数组的空间大小，然后才能将新元素加入到整数集合里 ，当然升级的过程中，也要维持整数集合的有序性。

添加新元素65535占用4个字节32位的长度 在原本空间的大小之上再扩容多 80 位（4x32-3x16=80），这样就能保存下 4 个类型为 int32_t 的元素。

保证有序性不变

好处：

添加更大的元素时才进行元素类型升级的操作，节省空间（但是不支持降级）

跳表（ZSet）

//跳表
typedef struct zset {
    dict *dict;  //哈希表   用于以常数复杂度获取元素权重
    zskiplist *zsl; //跳表
} zset;

//跳表节点
typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

//跳表头节点
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

如果要查找「元素：abcd，权重：4」的节点，查找的过程是这样的：

● 先从头节点的最高层开始 ，L2 指向了「元素：abc，权重：3」节点，这个节点的权重比要查找节点的小，所以要访问该层上的下一个节点；

● 但是该层的下一个节点是空节点（ leve[2]指向的是空节点），于是就会跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[1];

● 「元素：abc，权重：3」节点的 leve[1] 的下一个指针指向了「元素：abcde，权重：4」的节点，然后将其和要查找的节点比较。虽然「元素：abcde，权重：4」的节点的权重和要查找的权重相同，但是当前节点的 SDS 类型数据「大于」要查找的数据，所以会继续跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[0]；

● 「元素：abc，权重：3」节点的 leve[0] 的下一个指针指向了「元素：abcd，权重：4」的节点，该节点正是要查找的节点，查询结束。

跳表节点层数设置

跳表的相邻两层的节点数量的 比例会影响跳表的查询性能。

举个例子，下图的跳表，第二层的节点数量只有 1 个，而第一层的节点数量有 6 个。

这时，如果想要查询节点 6，那基本就跟链表的查询复杂度一样，就需要在第一层的节点中依次顺序查找，复杂度就是O(N)了。所以，为了降低查询复杂度，我们就需要维持相邻层结点数间的关系。

跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)。

下图的跳表就是，相邻两层的节点数量的比例是2 : 1。

那怎样才能维持相邻两层的节点数量的比例为 2 : 1 呢？

如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。

Redis 则采用一种巧妙的方法是，跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。

具体的做法是，跳表在创建节点时候，会生成范围为 [0-1]的一个随机数 ，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。

这样的做法，相当 于每增加一层的概率不超过 25% ，层数越高，概率越低，层高最大限制是 64。

虽然我前面讲解跳表的时候，图中的跳表的「头节点」都是 3 层高，但是其实如果层高最大限制是 64，那么在创建跳表「头节点」的时候，就会直接创建 64 层高的头节点。

如下代码，创建跳表时，头节点的 level 数组有 ZSKIPLIST_MAXLEVEL个元素（层），节点不存储任何 member 和 score 值，level 数组元素的 forward 都指向NULL， span值都为0。

为什么用跳表而不用平衡树

• 从内存占用上来比较，跳表比平衡树更灵活一些。 平衡树每个节点包含 2 个指针（分别指向左右子树） ，而跳 表每个节点包含的指针数目平均为 1/(1-p) ，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。

• 在做范围查找的时候，跳表比平衡树操作要简单。在 平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点 。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单， 只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。

• 从算法实现难度上来比较，跳表比平衡树要简单得多。 平衡树的插入和删除操作可能引发子树的调整 ，逻辑复杂， 而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速 。

quicklist

typedef struct quicklist {
    //quicklist的链表头
    quicklistNode *head;      //quicklist的链表头
    //quicklist的链表尾
    quicklistNode *tail; 
    //所有压缩列表中的总元素个数
    unsigned long count;
    //quicklistNodes的个数
    unsigned long len;       
    ...
} quicklist;

通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。

listpack

listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

原文链接： https://www.xiaolincoding.com/redis/data_struct/data_struct.html