Redis底部的几种存储结构（sds、dict、ziplist、intset、skiplist）

Redis底部的几种存储结构（sds、dict、ziplist、intset、skiplist）

本文作者生活不只*眼前的苟且
本文出处:https://blog.csdn.net/u011734144/article/details/86086749
版权声明：本文为博主原创文章，未经博主允许不得转载。
首先本文参考的是这个系列的文章：
https://mp.weixin.qq.com/s?__biz=MzA4NTg1MjM0Mg==&mid=509777776&idx=1&sn=e56f24bdf2de7e25515fe9f25ef57557&mpshare=1&scene=1
博主写的非常好，非常详细，我个人看完后，对核心部分进行了如下总结
第一层面，从使用者的角度value有这几种结构：（注意，key的结构都是string类型的）
string、list、hash、set、sortedset
第二层面，从内部实现的角度，有如下几种结构：
dict、sds、ziplist、quicklist、skiplist
Redis通过组合第一层面的数据结构来实现第二层面的数据结构

一、dict实现原理
在Redis中，dict是一个基于哈希表的算法，采用拉链法解决冲突，并在装载因子超过预定值时自动扩展，引发重哈希
重哈希：这是一种增量试重哈希，在需要扩展内存时避免一次性对所有key进行重哈希，而是将重哈希操作分散到对每个dict的各个增删该查的操作中去，这种方法能做到每次只对一小部分key进行重哈希，而每次重哈希之间不影响dict的操作。之所以这样设计是为了避免重哈希期间单个请求的响应时间剧烈增加。

为了实现重哈希，dict的数据结构里包含两个哈希表ht[0]和ht[1]，在重哈希期间，数据从第一个哈希表向第二个哈希表迁移，当数据全部从ht[0]迁移到ht[1]上后，整个重哈希就结束， ht[0]变成ht[1]的内容，而ht[1]则重置为空
此外，一个状态rehashidx可标记当前重哈希的状态
下面分三种操作来说明底层执行的逻辑，分别是查找、插入和删除
共同点：三个操作都会触发重哈希过程向前推进至少n步，即重哈希一部分key，从而将整个重哈希分散到每个增删改查操作中
每步重哈希key的数量：一个bucket，即一个dictEntry链表（冲突链表）
a、dict查找
从从ht[0]中查找，如果找到则返回；如果没找到并且当前正在冲哈希，则从ht[1]上查找

b、dict插入
如果正在重哈希，将数据插入到ht[1]，否则插入到ht[0]

c、dict删除
如果正在重哈希，则从ht[0]和ht[1]中查找并删除；否则从ht[0]中查找并删除

二、sds实现原理
全称：Simple Dynamic String
这种存储结构的特点：
可动态扩展内存，sds表示的字符串其内容可以修改也可以追加
二进制安全，sds能存储任意二进制数据，而不仅仅是可打印字符
sds字符串的数据结构：由两部分组成，他们在内存地址上前后相邻，从而节省内存
一个header，通常包含字符串的长度len、最大容量alloc和flags，但是sdshdr5有所不同，sds总共有5种类型的header
一个字符数组，存储真正的有效字符串数据
这种结构的优点：
header和数据相邻，不用分成两块内存空间来单独分配，有利于减少内存碎片，提高存储效率
sds的一些基础函数：

* sdslen(const sds s): 获取sds字符串长度。
* sdssetlen(sds s, size_t newlen): 设置sds字符串长度。
* sdsinclen(sds s, size_t inc): 增加sds字符串长度。
* sdsalloc(const sds s): 获取sds字符串容量。
* sdssetalloc(sds s, size_t newlen): 设置sds字符串容量。
* sdsavail(const sds s): 获取sds字符串空余空间（即alloc - len）。
* sdsHdrSize(char type): 根据header类型得到header大小。
* sdsReqType(size_t string_size): 根据字符串数据长度计算所需要的header类型。

浅谈sds和Redis的string类型的关系：
Redis的命令append底层用sds的sdscatlen实现
Redis的setbit和getrange命令都是先根据key取得整个sds字符串，然后再从字符串选取或修改制定的部分

上面说的是当value存储的是字符串时的情况；当value存储的值是一个数字的时候，它会支持incr/decr操作，此时的内部存储就不是sds了

三、robj实现原理(redisObject)
Redis中的数据的key都是string类型，value可以是多种类型，比如string，list，hash等
那么这个从key到value的映射关系，内部是用一个前面讲的dict来维护的，dict的key因为都是string类型，所以用sds来表达就足够了，而value比较复杂，为了在同一个dict内能存储不同类型的value，就定义了一种通用的数据结构robj，全名是redisObject
比如，如果value是一个list，那么它的内部存储结构是一个quicklist；如果value是一个string，那么它的内部存储结构一般情况下是sds，当然实际更复杂一点，比如当string类型的value是数字时，redis内部还会把它转换成long来节省内存，

一个robj类型包含如下5个字段：
type：对象的数据类型，可能的取值OBJ_STRING、OBJ_LIST、OBJ_SET、OBJ_ZSET、OBJ_HASH，分别对应Redis对外暴露的5种数据结构
encoding：对象的内部标识方式，不同的表示方式占用的内存不同，对查找性能也有影响
lru：做lru算法用
refcount：引用计数，它允许robj对象在某些情况下被共享
ptr：数据指针，指向真正的数据，比如一个代表string的robj，它的pt可能指向一个sds结构；一个代表list的robj，它的ptr可能指向一个quicklist

robj对象的作用：
为多种数据类型提供统一的表示方式
允许同一类型的数据采用不同的内部表示，从而在某些情况下尽量节省内存
支持对象共享和引用计数，当对象被共享的时候，只占用一份内存拷贝，进一步节省空间

深谈sds和Redis的string类型的关系：
确切的说，string在Redis中是用一个robj来表示的
用来表示string的robj，如果string是数字，那么会被转换成long存储
在对string进行incr/decr等操作的时候，若内部是OBJ_ENCODING_INT编码，则直接加减；否则，会先试图把sds存储的字符串转成long型再加减
在对一个内部表示成long型的string执行append、setbit或getrange操作的时候，针对的仍然是string的值（即仍然操作的是十进制表示的字符串），比如字符串“32”，它是整数，执行这几个操作的时候，直接操作的字符串“32”对应位，而不是32对应的整形0x0000000000000020的位

四、ziplist实现原理
ziplist是一个经过特殊编码的双向链表，设计的目标是为了提高存储效率，ziplist可以用于存储字符串或者整数，其中整数是按照二进制表示进行编码的，而不是编码成字符串序列。

ziplist不是普通的双向链表，普通的双向链表每一项都占用独立的一块内存，各项之间用地址指针连接起来，这会造成大量的内存碎片，而且地址指针也占用额外的内存。 ziplist是将表中每一项放在前后连续的地址空间中，一个ziplist整体占用一大块内存，它是一个表（list），但其实不是一个链表

另外，ziplist为了在细节上节省内存，对于值的存储采用了变长的编码方式，即对于大的整数，就多用一些字节来存储，对于小的整数就少用一些字节存

ziplist的数据结构定义：
…
这各个部分在内存上是前后相邻的
.：表示ziplist占用的字节总数
.：表示最后一个entry的位置，可方便找到最后一个entry，从而可在ziplist末尾快速的执行push或pop
.：表示数据项entry的个数
.：真正存放数据的数据项，长度不定
.：ziplist最后一个字节，是一个结束标记

再来看下数据项的具体构成：

.：表示前一项占用的字节总数，主要是为了让ziplist能从后向前遍历，采用变长编码
.：表示当前数据项的数据长度，采用变长编码
.：实际的数据

变长编码： prevrawlen和len两个字段是变长编码，基于相关data的长度，这两个字段的长度是不同的

hash与ziplist的关系：
hash结构随着数据量的增大，其底层数据结构的实现会发生变化，存储效率也就不同了
在hash中field比较少时，各个value值也比较小的时候，hash采用ziplist来实现；而随着field增多和value值增大，hash可能会变成dict来实现。
那么到底插入多少后才会从ziplist转成dict呢？跟redis的如下两个配置有关：

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

Redis的hash这样设计的原因，是因为ziplist变得很大的时候，它有如下缺点：
.每次插入或修改引发的realloc（扩容）操作会有更大的概率造成内存拷贝，从而降低性能
.一旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更大的一块数据
.当ziplist数据项过多的时候，在它上面查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历

五、quicklist实现原理
Redis对外暴露的List数据类型，底层实现用的就是quicklist
quicklist的实现是一个双向链表，链表的每一个节点都是一个ziplist， 为什么quicklist要这样设计呢？其实也是一个空间和时间的折中
.双向链表便于在表的两端进行push和pop操作，但是它的内存开销比较大。首先它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片
.ziplist由于是一整块连续内存，所以存储效率很高，但是它不利于修改操作，每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，进一步降低性能

这样设计的问题，到底一个quicklist节点包含多长的ziplist合适？这是一个找平衡的问题：
.每个quicklist节点上的ziplist越短，则内存碎片越多，极端情况是一个ziplist只包含一个数据项，这就退化成了普通的双向链表
.每个quicklist节点上的ziplist越长，则为一个ziplist分配大块连续内存的难度就越大，有可能出现内存里有很多小块的内存空间，但却找不到一块足够大的空闲空间分给ziplist。极端情况是整个quicklist只有一个节点，这就退化成了一个ziplist了

这个平衡问题可基于如下Redis参数配置：

list-max-ziplist-size -2

六、skiplist（跳跃表）
skiplist是为了实现sorted set这种对外的数据结构，其结构如下：
redis数据结构浅析 - 图1
比较好的策略是：上下相邻的两层链表节点个数的关系是2：1，如果要维护这种比例关系，当插入节点的时候，就需要把它后面的所有节点重新调整，删除也是，这会让时间复杂度蜕化成O(n)。
skiplist采用的策略：它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个新插入的节点随机出一个层数，因此插入操作只需要修改插入节点前后的指针，而不需要对很多节点进行调整，这降低了复杂度，这是它在插入性能上明显优于平衡树的方案

实际应用中skiplist每个节点应该包含key和value两部分，列表是按照key进行排序的，查找过程也是根据key在比较

在Redis中，skiplist被用于实现暴露给外部的sorted set，但是准确的说，sorted set底层不仅适用了skiplist，还是用了ziplist和dict
总结来说：
.当数据较少时，sorted set是用一个ziplist来实现，插入时插入两个数据项：数据在前，score在后，查找时顺序查找
.当数据多的时候，sorted set由zset实现，即由一个dict+一个skiplist来实现。 dict用来查询数据到分数的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）

那么什么时候开始切换实现方式呢？基于如下两个配置：两个条件满足一个就会切换zset

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

zset的结构定义如下：可以看到它就是基于dict+ziplist

typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;

另外，Redis中对skiplist做了扩展：（Redis中的skiplist和经典的skiplist的比较）
.分数允许重复，即skiplist的key允许重复（分数是skiplist中的key），这在经典的skiplist中是不允许的
.在比较时，不仅比较分数（skiplist的key），还比较数据本身
.第1层链表不是一个单向链表，而是一个双向链表，这是为了方便以倒序方式获取一个范围内的元素

七、intset实现原理
它是整数的集合，确切的说是整数组成的有序集合，从而便于在上面进行二分查找，从而快速判断一个元素是否属于这个集合，它在内存分配上与ziplist类似，是连续的一整块内存空间，并且对于大整数和小整数采取不同的编码，进来对内存进行优化，其结构如下：

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

encoding：数据编码，表示每个整数用几个字节来存储
length：表示intset中的元素个数
contents：数据元素

intset和ziplist的比较：
.ziplist可以存储任意二进制串，intset只能存储整数
.ziplist是无序的，而intset是从小到大有序的，因此在ziplist上查找只能遍历，而在intset上可以进行二分查找，性能更高
.ziplist可以对每个数据项进行不同的变长编码，而intset只能整体用一个统一的编码，所以intset随着新元素的添加，需要根据元素大小决定是否对数据编码进行升级

Redis的Set的底层实现：
.当Set中添加的元素都是整型切元素数据较少时，Set使用intset作为底层数据结构
.否则，Set底层使用dict作为数据结构（即元素不是整型或者元素是整型但是数据已经较多了用dict）

这通过如下参数来配置：

set-max-intset-entries 512

最后总结下第一层面的数据类型和第二层面的数据类型对应关系：

第一层面（使用者）	第二层面（底层）
String	sds、long
Hash	ziplist、dict
List	quicklist
Set	intset、dict
ZSet	skiplist、ziplist、dict