Redis中string、list的底层数据结构原理

Redis 的五大数据结构使用简介

Redis 有一个比较突出的特点就是数据结构更丰富, 「string、hash、list、set、zset、Redis5.0 新数据结构-stream」

这部分的使用相对简单，大家可以参考 Redis 官网系统学习并使用，接下来我们重点来看看 Redis 数据结构的底层设计

Redis 的命令不区分大小写，但是 key 严格区分大小写！！！

“老师，这部分就过了？”

“”我相信你们，最多花一个小时就看完了所有API了，加油！”

Redis-字符串对象（string）

我们还是通过上一节课的那个例子看一下string类型的底层结构是什么，通过object encoding key 命令来查看具体的存储结构

上图可以看到不同的字符串其内部的结构不一样，一个是embstr、另外一个是raw，

“老师，embstr 是什么意思？三种实现方式有什么区别呢？”

“不急，我们接下来就开始详细讲解”

Redis为了将内存的使用率做到极致，针对字符串对象，提供了三种数据结构

 REDIS_ENCODING_INT（long 类型的整数）
 REDIS_ENCODING_EMBSTR embstr （编码的简单动态字符串）
 REDIS_ENCODING_RAW （简单动态字符串）

接下来我们看一下具体区别

int

我们根据上一节知道每个hashtable中的值作为一个指针会指向redisObject对象，该对象有一个属性是ptr（指针类型），一个指针比如在64位系统中就是用8个字节来存储，这个存储大小正好是一个长整型的存储，所以为了节省内存空间，如果一个字符串内容可转为 long，那么该字符串会被转化为 long 类型，对象 ptr 指向该 long，并将 encoding 设置为 int，这样就不需要重新开辟空间，算是长整形的一个优化

raw

如果字符串对象保存的是一个字符串值，并且这个字符串的长度大于 32 字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为 raw。

embstr

如果字符串对象保存的是一个字符串值，并且这个字符串的长度小于等于 44 字节，那么字符串对象将使用 embstr 编码的方式来保存这个字符串。

3.2版本之后是44个字节，之前是39个字节，这也是因为sds结构的版本变化所导致的。

embstr类型是如何存放字符串的【重点】

我们知道一般cpu从内存中读取数据会先读取到 cache line（缓存行）， 一个缓存行基本占64个字节，其中redisObject最少占16个字节（根据属性的类型计算得出），所以如果要读取一个 redisObject，会发现只读取了16个字节，剩下的48个字节的空间相当于浪费，所以为了提高性能（主要减少了内存读取的次数），所以再RedisObject空间后又开辟48个字节的连续空间，将ptr指向的值存入其中，注意此处存入的是字符串类型，48个字节对应的是sdshdr8存储结构。而 sdshdr8 在不存入数据的情况下，最少要 4 个字节（其中一个字节是字符串尾部的'\0'）,那么还剩余 44 个字节，所以如果在 44 个字节以内字符串就可以放在缓存行里面，从而减少了内存I/O次数

embstr 编码方式的优点：

• embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次。

raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构,而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间， 空间中依次包含 redisObject 和 sdshdr 两个结构

• 释放 embstr 编码的字符串对象只需要调用一次内存释放函数，而释放 raw 编码的字符串对象需要调用两次内存释放函数。
• 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比起 raw ，编码的字符串对象能够更好地利用缓存带来的优势。

Redis-列表对象（list）

3.2 版本前采用ziplist和linkedlist结构

List 是一个有序（按加入的时序排序）的数据结构，一般有序我们会采用数组或者是双向链表，其中双向链表由于有前后指针实际上会很浪费内存。

3.2版本之前采用两种数据结构作为底层实现：

• 压缩列表ziplist
• 双向链表linkedlist

压缩列表相对于双向链表更节省内存，所以再创建列表市，会先考虑压缩列表，并在一定条件下才转化为双向链表，在说明转化条件之前，我们先了解一下什么是压缩列表。

ziplist（为节省内存而设计）

下图是ziplist的数据结构

其中黄色区域用来表示列表的特征，绿色区域就是列表中具体的元素了，ziplist是使用连续的内存块存储的

• zlbytes：表示整个ziplist占用的字节数，一般用于内存重分配或者计算列表尾端
• zltail：到达列表最后一个节点的偏移量，方便直接找到尾部节点
• zllen：列表节点的数量

注意zllen用16个比特位存储，也就是说起长度最大表示65535，所以如果长度超过这个值，只能够通过节点遍历来确定列表元素数量

• entryX：列表中的各节点
• zlend：作用就是用来标记列表尾端，占用一个字节

接下来重点看一下列表中每个节点是如何存储的

  typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;    // prevrawlen是前一个节点的长度，prevrawlensize是指prevrawlen的大小，有1字节和5字节两种
    unsigned int lensize, len;  // len为当前节点长度 lensize为编码len所需的字节大小
    unsigned int headersize;    // 当前节点的header大小
    unsigned char encoding; // 节点的编码方式
    unsigned char *p;   // 指向节点的指针
} zlentry;
  
void zipEntry(unsigned char *p, zlentry *e) {   // 根据节点指针返回一个enrty
    ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);    // 获取prevlen的值和长度
    ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);  // 获取当前节点的编码方式、长度等
    e->headersize = e->prevrawlensize + e->lensize; // 头大小
    e->p = p;
}

完整的zlentry由以下3各部分组成：

• prevrawlen: 记录前一个节点所占内存的字节数，方便查找上一个元素地址

根据图中可以看到prevrawlen是变长编码的，如果上一个节点长度小于254个字节，则只是用一个字节存储prevrawlen，如果大于等于254，那么第一个字节用254标记，后面四个字节表示上一个节点长度

• lensize, len：记录当前节点所占内存字节数，以及内容的存储类型，方便解析，其具体对应关系可参考上图文本框中内容
• content：保存了当前节点的值。

知道了ziplist原理后，我们来看一下在压缩列表转化成双向链表的条件：

• 如果添加的字符串元素长度超过默认值64
• zip包含的节点数超过默认值512 这两个条件是可以修改的，在redis.conf中

list-max-ziplist-value 64 
list-max-ziplist-entries 512  
复制代码

ziplist 的缺点

ziplist 最大的确定就是连锁更新问题

因为在 ziplist 中，每个 zlentry 都存储着前一个节点所占的字节数，而这个数值又是变长编码的。假设存在一个压缩列表，其包含 e1、e2、e3、e4.....，e1 节点的大小为 253 字节，那么 e2.prevrawlen 的大小为 1 字节，如果此时在 e2 与 e1 之间插入了一个新节点 e，e 编码后的整体长度（包含 e1 的长度）为 254 字节，此时 e2.prevrawlen 就需要扩充为 5 字节；如果 e2 的整体长度变化又引起了 e3.prevrawlen 的存储长度变化，那么 e3 也需要扩.......如此递归直到表尾节点或者某一个节点的 prevrawlen 本身长度可以容纳前一个节点的变化。其中每一次扩充都需要进行空间再分配操作。删除节点亦是如此，只要引起了操作节点之后的节点的 prevrawlen 的变化，都可能引起连锁更新，引发内存 realloc。

连锁更新在最坏情况下需要进行 N 次空间再分配，而每次空间再分配的最坏时间复杂度为 O(N)，因此连锁更新的总体时间复杂度是 O(N^2)。

基于上述来看ziplist的缺点大于优点，所以3.2版本之后采用了另外一个数据结构为quicklist

3.2版本之后升级为 quicklist(双向链表)

quicklist是3.2版本之后引入的。

根据上文谈到，ziplist会引入频繁的内存申请和释放，而linkedlist由于指针也会造成内存的浪费，而且每个节点是单独存在的，会造成很多内存碎片，所以结合两个结构的特点，设计了quickList。

quickList 是一个 ziplist 组成的双向链表。每个节点使用 ziplist 来保存数据。本质上来说，quicklist 里面保存着一个一个小的 ziplist。结构如下：

quickList

根据图中可以看到每一个ziplist都是一个很小的集合，ziplist太短，内存碎片越多，太长，分配大块连续内存空间的难度就越大，这个范围也是可以配置的

• -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。
• -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。
• -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。
• -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（默认值）
• -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

list-max0ziplist-size -2

这个设置的值是可以通过配置文件看到，默认8kb最好（-2对应的就是8kb，可以参考下图中的注释）

我们知道list比较适合于用在热点数据中，一般最容易被访问的是列表两端的数据，中间的访问频率很低，如果符合这个场景，list还有一个配置，可以对中间节点进行压缩

• 0: 是个特殊值，表示都不压缩。这是Redis的默认值。
• 1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。
• 2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。
• 以此类推

list-compress-depth 0

总结

本节内容主要讲解了Redis中string、list对象底层结构，string通过int、raw、embstr三种结构来表示，而list在3.2版本之后采用quicklist的数据结构，我们可以看到在节省内存、提高查询效率方面都体现了优秀的设计，这些都可以作为我们日后设计及开发中的宝贵经验！