Redis数据结构

Author

2022-12-08 297 words 2 minutes

Contents

redis 底层数据结构

list的底层数据结构,redis3.2之后,使用quicklist代替ziplist
redis7.0开始不再使用ziplist,使用listpack代替
对于有序集合，两种实现方式:压缩列表ziplist(listpack)、跳表skiplist.

redis.conf配置中有关于zset到底使用那个数据结构两个配置项,
```
1) "zset-max-ziplist-value"
2) "64"
3) "zset-max-ziplist-entries"
4) "128"
```
也就是收当zset集合中元素个数不超过128且所有元素值大小不超过64时，使用压缩列表，否则使用跳表。同理，hash也有这两个配置项。同样对于hash类型，也存在相似的配置
```
"hash-max-listpack-value"
"64"
"hash-max-listpack-entries"
"512"
```
当set的value为整数且个数不多时set-max-intset-entries使用intset。

sds

sds

object encoding key 命令用于查看key的底层存储的数据结构。 type key返回的是基本类型。

redis 多有的key类型以及value类型/复杂结构的value元素也都是字符串。redis字符串底层实现为sds。

sds优点:

O(1)时间获取字符串长度。
二进制安全,允许字符串中出现’\0’这个特殊字符，sds可以存储图像,音频等类型的编码。由于获取长度不会以’\0’为结尾，所以是二进制安全的。
相比于C字符串，减少了动态扩展中的内存再分配次数。在redis中string变化的场景比较多，所以这一特性很重要。
兼容C函数， sds->buf 本质是C字符数组

hashtable

字典

linkedlist

双向链表

ziplist

在linkedlist基础上,使用连续内存，对不同的数据类型采用不同的encoding表示。本质是可以存储整数或字符串的数组或者是说具有连续内存分配的双向链表。是为了节省内存而设计的顺序型数据结构。

zltail+entry-pre_len时为了实现逆序遍历
head 中的zlen虽然数值上只能达到2^16-1=65535,但是实际entry可以大于这个数，当zlen等于65535时，需要遍历压缩列表获取entry数量
entry的pre_len 是否扩展取决于上一个节点长度是否大于等于254(0xff位结束标志,0xfe位pre_len扩展标志)
entry的encoding通过前两位来区分content是怎样的字符/整数
flag=0xff,标记结束。已经有标记entry数量的zllen,为什么还需要结束标记位??

由上述结构可知,entry的encoding字段大小会因为增删发生改变，最坏的情况下会引起一系列连续的改动，称为连锁更新。

listpack

ziplist在entry头encoding设计引起的连锁更新在高并发写操作中会降低redis性能，设计了更加紧凑的listpack。redis7.0开始，不再使用ziplist.

与ziplist的不同点:

head中删除tail偏移量
entry中不再记录前一节点长度，改为记录当前节点长度，entry不会再发生连锁更新的问题
encoding规则和大小与ziplist不同

quicklist

redis3.2开始,list的底层实现使用quicklist代替ziplist(listpack)。我们知道ziplist(listpack)在双端链表的基础上使用连续内存和压缩节点信息的方式达到节省内存的目的, 但是其缺点也很明显，多余较长的ziplist(listpack)，增删时存在较多的内存拷贝操作.ziplist同时由于entry中会记录前一节点长度的原因也会引起连锁更新，在元素较多时性能由影响。而quicklist 是结合了链表的方便插入删除特点和ziplist(listpack)节省内存的特点，进行的折中，将ziplist(listpack)作为quicklist节点，采用双端链表的形式串起来。

quicklist的节点定义如下:

typedef struct quicklistNode {
 struct quicklistNode *prev;
 struct quicklistNode *next;
 unsigned char *entry;
 size_t sz;             /* entry size in bytes */
 unsigned int count : 16;     /* count of items in listpack */
 unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
 unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */
 unsigned int recompress : 1; /* was this node previous compressed? */
 unsigned int attempted_compress : 1; /* node can't compress; too small */
 unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */
 unsigned int extra : 9; /* more bits to steal for future usage */
 } quicklistNode;

entry指向的是(ziplist)listpack结构存储的数据域.每个节点的最大容量见配置文件中的list-max-listpack-size

quicklist定义:

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all listpacks */
    unsigned long len;          /* number of quicklistNodes */
    signed 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;

示意图如下:

当插入新的值时，由于Node节点由最大容量的问题，所以Node节点存在新建节点的操作。

skiplist

跳表，基础底层数据类型中唯一的有序结构,在有序链表上增加几层类似索引的节点，为应对增删引起的索引节点的调整，使用了随机层数。

跳表的每个节点定义如下:

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

score分值,用于排序;
ele, 对象属性
backward, 指向下一个节点的指针
level[], 索引节点数组，每个索引节点由两个属性，forward:前向指针,指向上一个索引节点. span 跨度，描述两索引节点的距离。

整个跳表是由zskiplistNode 链接而成的链表+头节点。

head, tail:分别指向链表的首节点、尾节点
length: 节点总数目
level: 索引节点的最高层数

intset

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;