Redis 数据结构详解

本文以 Redis 6.2 版本为例

SDS（Simple Dynamic String）

为什么不使用 C 语言的字符串（C 语言字符串的缺陷）

C 语言的字符串实际上是一个字符数组，char 指针只是指向字符数组的起始位置，结尾位置用以'\0'字符表示

1. C 语言并不存储字符串长度，获取字符串长度时需要通过遍历来实现，判断当前字符是否为'\0'，如果不是，就累加计数，如果是就结束遍历。这样有两个不好的地方
   1. 获取字符串长度的时间复杂度为 O(N) ，不高效
   2. 如果字符数组中间有一个'\0'字符，那么就会提前结束遍历 —> 字符串中不能有'\0'字符 —> C 语言字符串只能保存文本数据，不能存储二进制数据（图片、音频、视频等）
2. 容易发生缓冲区溢出问题
   1. C 语言不记录字符串长度，也不记录字符串的缓冲区大小，当进行一些字符串操作时，比如使用char *strcat(char *dest, const char *sr/c)时，strcat会假定已经留足内存给 dest 字符串了，会直接将 dest 拼接到 src 后面，而当 src 字符串分配给 dest 的内存不足时，就会发生溢出问题。
   2. 所以使用strcat拼接字符串时，需要自己判断 src 的内存是否足够，不够的话需要手动扩容
3. 无法高效地实现字符串操作
   1. 使用strcat进行拼接操作时，需要先手动判断内存是否足够，不够的话需要进行内存重分配
   2. 使用trim进行截断操作后，也需要进行内存重分配，释放掉多余的内存空间

      内存重分配：涉及到复杂的算法，可能还需要执行系统调用，通常来说是一个比较耗时的操作

Redis 3.2 版本之前的 SDS

1. 结构设计

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    unsigned int len;
    // 记录 buf 数组中剩余可用字节数量
    unsigned int free;
    // 字节数组（柔性数组），用于保存字符串
    char buf[];
};

2. 结构各属性的优点（与 C 语言字符串相比）

• len：记录了保存的字符串的长度，这样就能高效地获取字符串的长度，时间复杂度为 O(1) ，并且不依赖'\0'来进行读写，保证了二进制安全
• free：记录了数组中的剩余可用字节，避免频繁的内存重分配，节省时间
• buf[]：仍然以'\0'字符来结尾，并采用柔性数组来保存字符串，SDS 向上层暴露的指针是指向 buf 数组的指针（而非指向结构体本身的指针），这样可以读取 SDS 中字符串的内容就可以向读取 C 语言字符串一样，复用 C 语言库中原有的操作函数。

  柔性数组简单介绍：柔性数组是 C99 引入的一个新特性，允许定义结构体的时候创建一个空数组，之后根据需要动态扩展数组，柔性数组不占用内存，需要多少申请多少，所以减少了内存碎片的产生 注意：柔性数组必须作为结构体的最后一个成员，并且除了柔性数组外，结构体内至少有一个其他类型的成员

3. 对于频繁的内存重分配问题所提供的解决方案

① 空间预分配

当对字符串进行修改时，如果需要拓展内存空间，那么程序除了会为 SDS 扩展修改所需要的内存空间，还会额外多分配未使用空间给 SDS，这样就可以减少内存重分配的次数，避免大量耗时操作
分配规则：

• 如果修改后的 SDS 长度 < 1MB，那么会额外分配与len一样大的未使用空间给 SDS（翻倍扩容）

• 如果修改后的 SDS 长度 >= 1MB，那么会额外分配 1MB 的未使用空间给 SDS

  ② 惰性空间释放

  当进行字符串缩短操作的时候，并不会立即进行内存重分配来释放空间，而是用free属性记录剩余的字节数量，避免了过多的内存重分配，并且为之后可能进行的字符串增长操作提供了优化（之后增长就可以使用剩余的未使用空间，而不用因为空间不足而进行内存重分配）。并且不用担心会有内存浪费问题，SDS 提供了相应的 API，在有需要的时候可以使用 API 释放内存空间

  Redis 6.2 版本的 SDS（3.2 版本之后的）

  对于 Redis 3.2 版本之前的 SDS，不足的地方在于每个 SDS 都需要 4 字节的 int 类型的len和free来保存字符串长度，那么对于较短的字符串来说，4 字节有点过于浪费了，并不需要这么大的空间来存储，所以 Redis 3.2 之后的版本对头部的结构进行了优化，设计了 5 种类型来针对不同长度的字符串进行存储，越短的 SDS 使用越小的 header，这样能尽可能的 节省内存

  这五种类型共有的属性：len、alloc、flags、buf[]

• len：保存字符串的长度

• alloc：保存给该字符串分配的空间（剩余的未使用空间 = alloc - len）
• flags：标识字符串所属的类型（sds 类型）
• buf[]：字节数组，保存实际的字符串

  五种类型的结构设计

  struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 低 3 位存储类型，高 5 位存储长度 */
    char buf[];
  };
  struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用长度，用 1 字节存储 */
    uint8_t alloc; /* 总长度，用 1 字节存储 */
    unsigned char flags; /* 低 3 位存储类型，高 5 位预留 */
    char buf[]; /* 柔性数组，存放实际的字符串 */
  };
  struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* 已使用长度，用 2 字节存储 */
    uint16_t alloc; /* 总长度，用 2 字节存储 */
    unsigned char flags; /* 低 3 位存储类型，高 5 位预留 */
    char buf[]; /* 柔性数组，存放实际的字符串 */
  };
  struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* 已使用长度，用 4 字节存储 */
    uint32_t alloc; /* 总长度，用 4 字节存储 */
    unsigned char flags; /* 低 3 位存储类型，高 5 位预留 */
    char buf[]; /* 柔性数组，存放实际的字符串 */
  };
  struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* 已使用长度，用 8 字节存储  */
    uint64_t alloc; /* 总长度，用 8 字节存储 */
    unsigned char flags; /* 低 3 位存储类型，高 5 位预留 */
    char buf[]; /* 柔性数组，存放实际的字符串 */
  };

  所以除了sdshdr5使用了flags的高五位来存储长度，其他 4 种类型的flags的高五位都没有使用到

结构体定义源码中的__attribute__ ((__packed__))表示结构体不再遵循字节对齐原则，而是采用紧凑的方式来排列每个字段成员，也就是按照每个成员实际的长度来存放，这样 不仅节省了内存，还能够通过偏移量来访问结构体中的变量 以sdshdr32为例，原来按照字节对齐原则，会按最宽的数据类型来对齐，也就是 4 字节，那么总共需要 4 * 3 = 12 个字节来存放，而现在紧凑地排列字段成员，只需要 4 + 4 + 1 = 9 个字节来存放，节省了 12 - 9 = 3 个字节的空间，并且 SDS 暴露给上层的指针指向 buf 数组，那么 buf 向前偏移一个字节就能得到flags的值，从而得到 sds 的类型

总结：SDS 与 C 语言字符串的区别（Redis 6.2 版本）

链表LinkedList

结构设计

/**
*  【链表节点】结构
*/
typedef struct listNode {
    struct listNode *prev;    //指向前一个节点
    struct listNode *next;    //指向后一个节点
    void *value;    //节点的值
} listNode;
/**
*  【链表】结构
*
*  dup、free、match 这3个函数可以自定义实现
*/
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;

优点

1. 通过len来记录链表长度，获取链表长度的时间复杂度为 O(1)
2. 链表节点结构中有prev和next，访问前一个节点和后一个节点的时间复杂度都为 O(1)
3. 链表结构中有head和tail指针，访问链表头节点和尾节点的时间复杂度都为 O(1)

4. 节点值使用 void* 指针来保存，所以链表节点可以保存不同类型的值

   缺点

5. 链表节点之间的内存不连续，这样不利于充分利用 CPU 缓存来加速访问

6. 每个链表节点都要分配一样的链表节点结构，链表节点结构的内存开销比较大

压缩列表ziplist

压缩列表就是为了 节省内存 而设计的，是一种内存紧凑型的数据结构，占用一块连续的内存空间，这样有利于充分利用 CPU 缓存来加快访问速度，并且压缩列表会根据数据的不同长度来使用不同类型的结构存储元素，元素长度是动态的、不固定的

列表结构设计

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
type         uint32_t  uint32_t uint16_t                                    uint8_t
size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                         ZIPLIST_ENTRY_TAIL

• zlbytes：整个压缩列表占用的内存字节数（常用于内存重分配或者计算zlend的位置）
• zltail：起始地址到尾节点的偏移量（用于计算尾节点的位置）
• zllen：压缩列表保存的节点数（当zllen<UINT16_MAX (65535)时， zllen的值就是压缩列表包含的节点数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出）
• entry：压缩列表里保存的节点，节点的长度会由所保存的内容来决定

• zlend：标识列表的结束位置（固定为 0xFF，十进制的 255）

  列表节点结构设计

  typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
  } zlentry;

  压缩列表的每个节点entry其实都是一个zlentry，主要由 3 部分组成

• prevrawlen：前一个节点的长度

• encoding：编码，记录节点保存数据的类型及长度
• content：节点的实际内容（数据）

prevrawlen也是变长编码，有两种情况

• 前一个节点的长度 < 254 时，prevrawlen占 1 个字节
• 前一个节点的长度 >= 254 时，prevrawlen占 5 个字节，第一个字节为固定值0xFE(254)（不用 255 ，是因为 255 给zlend用了）

  优点

1. 节省内存，根据保存内容的不同采用不同的类型来保存
2. 内存空间连续，可以利用 CPU 缓存加快访问速度

3. 可以正序遍历也可以倒序遍历，获取头结点和尾节点的时间复杂度都为 O(1)

   缺点

4. 除了第一个和最后一个节点外，获取其他节点需要顺序查找，一个一个遍历，时间复杂度为 O(N)

5. 由于内存连续，一旦插入或者删除节点，需要重新进行内存重分配，可能会引发连锁更新问题

   连锁更新问题

6. 模拟

假设最开始时，entry1的长度在 0 ~ 253 之间，entry2的长度为 253，entry1的下一个节点是entry2，所以entry2.prevrawlen的大小为 1 字节
这时要在entry1和entry2中插入一个entryX，entryX的长度为 256 > 254，所以entry2.prevrawlen的大小需要从 1 个字节变成 5 个字节，那么entry2的长度就变为 257 > 254，那么entry3.prevrawlen的大小也需要从 1 个字节变成 5 个字节，如果接下去entry3的长度变化又导致了下一个节点连续的变化……
上面那种情况可能会导致一直到最后一个节点都需要扩展，而每一次扩展都需要进行一次内存重分配。删除节点的时候也是一样的，只要引起了prevrawlen占用空间的变化，那么就可能会引起连锁更新

1. 最坏情况

最坏情况下需要进行 N 次内存重分配，而内存重分配的最坏时间复杂度为 O(N)，那么连锁更新的最坏时间复杂度就为 O(N 2)

1. 总结

压缩列表虽然节省了许多内存，但只适合存储节点少的情况，节点一多极有可能导致连锁更新问题

快速列表quicklist

quicklist相当于linkedlist+ziplist，quicklist实际上是一个链表，链表的每个元素是一个压缩列表，通过控制每个压缩列表的节点数来尽量降低 连锁更新 带来的性能影响

结构设计

//【链表】结构
typedef struct quicklist {
    quicklistNode *head;        //头结点
    quicklistNode *tail;        //尾节点
    unsigned long count;        //所有压缩列表中的总元素个数
    unsigned long len;          //quicklistNodes的个数
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;
//【链表节点】结构
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];    //柔性数组，用于存储实际内容
} quicklistLZF;

quicklistNode 的 count 等字段后面跟着一个冒号和一个数字，这时 C 语言结构体中 位域 的语法，它告诉编译器，这个字段所使用的位的宽度，可以把数据以位的形式紧凑存储，并允许程序员对此结构的位进行操作

关于节点**quicklistNode**
prev和next分别指向前一个节点和后一个节点
zl：如果节点没有被压缩，那么zl指向一个压缩列表，如果被压缩了，那么zl指向一个quicklistLZF
sz：size，压缩列表的字节大小
count：压缩列表的元素个数
encoding：标识节点的编码方式，1 表示ziplist，2 表示quicklistLZF
container：1 表示直接存储数据（实际上还未实现），2 表示使用ziplist存储数据

quicklist结构图

添加元素过程：会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到quicklistNode结构里的压缩列表，如果不能容纳，才会新建一个新的quicklistNode结构。

参考资料

1. 《Redis 设计与实现》
2. rollingRobin：https://www.cnblogs.com/rollingRobin/p/16002143.html
3. 消失er：https://zhuanlan.zhihu.com/p/102422311