【Redis-02】Redis数据结构与对象原理 -上篇

Redis本质上是一个数据结构服务器，使用C语言编写，是基于内存的一种数据结构存储系统，它可以用作数据库、缓存或者消息中间件。

我们经常使用的redis的数据结构有5种，分别是：string(字符串)、list(列表)、hash(哈希)、set(集合)、sorted set(有序集合)，下面基于redis 5.0 版本查看这5种数据结构的底层实现原理。

首先redis是支持key-value键值对存储的内存型数据库，它的所有key都是字符串的类型，value的类型是上面5种类型中的一种，但是在底层，不管是哪一种类型，都是通过redisObject对象来实现的。比如我们在redis中执行了如下命令，创建一个键值对时:

那我们在redis中其实是创建了两个redisObject对象，一个是”msg”的字符串对象（键对象），另一个是”hello”的字符串对象（值对象）。

1.redisObject对象

1.1 redisObject数据结构

首先看下redisObject的源码:

对应下侧的图示，有5个属性

其中，标红的type、encoding、ptr是和数据保存相关的：

type：redisObject的类型，即我们熟悉的5种数据类型，使用type命令可以查询。
encoding：表示type对应类型的真正实现结构类型编码，使用object encoding 命令可查询。
lru：表示lru的算法实现，此处暂不讨论。
refcount：引用计数，表示当前对象正在被多少个数据结构所共享，使用object refcount可查询。
ptr：prt指针指向此类型真正的数据结构实现，和encoding所表示的数据结构是一致的。

下面两个图，分别是type属性和encoding属性的取值范围：

1.2 举个例子

我们还是执行 => set msg hello，这里我们关注值对象”hello”，它基于redisObject的实现结构是这样的（上图），然后我们执行命令查看一下（下图）

值对象”hello”的redisObject结构，type属性对应的是string，encoding属性对应的是embstr，prt指向的是真实的底层数据结构，通过对应的命令可以查看。

1.3 redisObject的优势

redis为什么要使用redisObject这种结构去实现上面提到的5种类型呢？

redis可以在执行命令之前，通过对象的类型（type）来判断当前命令是否合法，比如存储的是字符串类型，但是传入了 hlen 命令
redis可以根据不同的使用场景，为某一种类型的对象设置不同的数据结构实现，而不是给某一个类型固定死一种数据结构编码，比如 string 的redisObject，在字符串的长度≤44字节时，encoding = embstr，而长度 > 44字节时， encoding = raw，这样其实能提高redis的灵活性和执行效率。

1.4 type与encoding的对应关系

下面，我们先从右侧这几个底层结构入手，了解一下他们的实现原理是什么。

2.encoding-简单动态字符串sds

redis使用了一种名为简单动态字符串（simple dynamic string）的类型作为字符串类型的默认实现，而不是直接复用C语言的字符串。传统的C字符串是使用’\0’表示字符数组的结尾（NULL结束符），但是sds在C字符串的基础上进行了封装，是典型的以空间换时间的效率提升方案，sds的源码及两种header的字符串实现方案如下图：

2.1 5种类型的header

长度在0和2^5-1之间，选用SDS_TYPE_5类型的header。
长度在2^5和28-1之间，选用SDS_TYPE_8类型的header。
长度在2^8和216-1之间，选用SDS_TYPE_16类型的header。
长度在2^16和232-1之间，选用SDS_TYPE_32类型的header。
长度大于2^{32的，选用SDS_TYPE_64类型的header，能表示的最大长度为2}64-1。

2.1.1 sds的结构

sds一共有5种以上类型的header，除了sdshdr5之外，其余的4种header都有以下4个属性结构，分别是：

len：表示字符串的真正长度（不包含NULL结束符在内）
alloc: 表示字符串的最大容量（不包含NULL结束符在内）
flags: 占用一个字节。其中的最低3个bit用来表示header的类型，0到5的取值分别代表sdshdr5到sdshdr64。
buf数组：真正有效的字符串数据，以及字符串之后的空余未使用字节。

shshdr5是不包含len和alloc属性的，它的flags低3位表示header，高5位用来表示它的最大长度len，所以sdshdr5是不能够动态扩展长度的，一般用于存储静态的短字符串，如key 键的字符串对象。

在初始化的时候，如果字符串长度小于32，key和value的header的类型是不一样的，具体可参考： https://cloud.tencent.com/developer/article/1837860

2.2 sds的扩缩容

有如下的字符串hello，header类型是sdshdr8

2.2.1 扩容

现在比如要执行 append msg ‘gentleman’，要追加9个字符，但是上面空余的只有5个字节。

如果原来字符串中的空余空间够用，那它追加之后，什么也不做，然后返回原地址；
如果不够用需要分配空间，它会比实际请求的多分配一些：如果扩容后的len的长度小于1MB，那么程序分配和len属性同样大小的未使用空间，如果len的长度大于1MB，那么会分配1MB的未使用空间，最大512MB。
按分配后的空间大小，可能需要更换header类型（原来header的alloc字段太短，表达不了增加后的容量）
如果需要更换header，那么整个字符串空间（包括header）都需要重新分配，并拷贝原来的数据到新的位置。
如果不需要更换header，原来的地址位置有足够的空余空间完成重新分配，那么它返回的新地址与传入的旧地址相同；否则，它会分配新的地址块，并进行数据搬迁；

上图在进行扩容后( append msg ‘gentleman’ )就会变为下面的结构，其中header的类型不变，但是len=14，alloc=28，数组总长度变为 = 28 + 1(结束符) 个字节

2.2.2 缩容

有扩容就有缩容，如果sds的操作使得字符串的长度缩短，redis并不会立即回收缩短后空余出来的字节，而是基于sds的惰性空间释放策略，等待这部分空间将来被使用，尽量减少内存重分配的次数。当然redis也提供了相应的api，在有需要的时候，可以调用某些函数完成空余空间的释放，只保留被使用的部分，使得alloc = len。

综上，redis使用sds的优势在于，首先sds在执行字符串拼接等操作的时候，比如sdscat，空余的字节空间可以减少内存重分配的次数，内存重分配涉及到复杂的算法，涉及到系统调用，比较耗时。其次，sds相对于传统C字符串，获取字符串长度的时间复杂度，从O(N)降到O(1)，可以直接读取len的值。

3. encoding-字典dict

字典在redis中应用是非常广泛的，redis的数据库就是使用字典来作为底层实现的，比如我们执行了 set msg hello，数据库会创建一个键是msg，值是hello的键值对，保存在代表数据库的字典里面。

3.1 三种数据结构

3.1.1 哈希表节点 dictEntry

key：键； value：值； next：指向另一个哈希表节点的指针

3.1.2 哈希表 dictht

table：哈希表数组
size：哈希表大小，数组长度
sizemask：值总是等于size – 1，这个属性与key的哈希值计算得出key位于table的哪个索引位置
used：记录了哈希表目前已有节点（键值对）的数量

3.1.3 字典 dict

type + privdata：针对不同类型的键值对，为创建多态字典而设置的，本次不讨论。
ht：包含2个dictht哈希表的数组，一般情况下只使用ht[0]，ht[1]只在rehash的时候使用。
rehashidx：用于记录增量式rehash时的进度，非rehash期间值是-1。
iterators：当前正在进行遍历的iterator的个数，本次不讨论。

3.2 键值对的插入

使用字典设置的哈希函数，计算key的哈希值；
使用哈希表的 sizemask 属性和上面计算出来的哈希值，计算出哈希表的索引值；
如果哈希表此索引位置上没有任何节点，直接插入；如果已经有了其他节点，产生了键的冲突，会形成一个单向链表，新添加的节点总是位于表头的位置，即头插法（时间复杂度是O(1)）

3.3 哈希表的扩缩容

随着对字典的不断操作，哈希表的中键值对会不断增多或减少，这时候，redis就会对哈希表进行相应的扩展或者收缩，可以让负载因子 (ht[0].used / ht[0].size)维持在一个合理的范围内。

3.3.1 扩容

触发条件：

如果没有执行 bgsave 或者 bgrewriteaof 命令时，哈希表的负载因子≥1
在执行bgsave 或者 bgrewriteaof 命令时，哈希表的负载因子 ≥5
扩容后大小：ht[1].size = 大于等于 ht[0].used * 2 的最小2n（2的n次幂）

3.3.2 缩容

触发条件：哈希表的负载因子 ≤0.1
缩容后大小：h[1].size = 大于等于 ht[0].used 的最小2n（2的n次幂）

3.3.3 rehash

根据实际的情况，计算扩缩容后的ht[1].size大小，并且给ht[1]分配空间；
将ht[0]上的所有键值对，重新计算在ht[1]的索引位置，并将键值对迁移到对应位置；
等ht[0]上的所有键值对都迁移到ht[1]上后，ht[0]变成空表，释放ht[0]，将ht[1]设置成ht[0]，然后给新的ht[1]创建一个空白的哈希表。

3.3.4 增量式（渐进式）rehash

前面提到在rehash期间，ht[0]中所有的键值对要迁移到ht[1]上面，但是如果ht[0]上面有上亿个键值对，那么一次全部rehash是需要消耗很长时间的，会造成redis的卡顿或者短时间的不可用，所以这个rehash的动作并不是一次性集中完成的，而是采用了一种渐进式的rehash过程。具体步骤如下：

给ht[1]哈希表分配空间，空间大小跟扩容和收缩具体操作有关系，开始rehash后，设置 rehashidx = 0；
遇到增删改查命令时，除了执行命令本身，还会将ht[0]在 rehashidx 下标处的所有值rehash到ht[1]上面，之后 rehashidx = rehashidx + 1；
第二步骤不断执行，rehashidx 每次 + 1
在某个时间点上，所有ht[0] 的键值对都 rehash 到 ht[1] 上后，设置rehashidx = -1
将ht[1]设置为ht[0]，然后给 ht[1] 的新建一张空白哈希表。

3.3.5 rehash期间的增删改查

新增键值对，会直接保存到ht[1]上面
删除、更新、查询会分别在ht[0]和ht[1]上查找

4 encoding-压缩列表ziplist

压缩列表是redis为了节约内存而开发的，由一些列特殊编码组成的连续内存块的顺序型数据结构。可以将他理解成一个特殊的双向链表，可以用于存储字符串和整数，能够以0（1）的时间复杂度在压缩列表的两端进行 push 和 pop 操作。

4.1 压缩列表的数据结构

我们来看下每项都代表什么含义：

zlbytes：占用4个字节，用来记录整个ziplist结构占用的字节数，也包含自身的4个字节；
zltail：占用4个字节，用来记录最后一个节点的起始地址距离当前ziplist起始地址的字节数偏移量，这个属性的存在使得我们查找最后一个entry的时间复杂度从O(N)降低到O(1)，可以更方便的在表头和表尾进行 push 和 pop。
zllen：占用2个字节，记录了当前压缩列表的节点数量：当这个属性值≤65535时，表示节点的真实个数，当这个属性值 = 65535时，不再表示节点真实个数，而是需要遍历整个压缩列表来获取节点数量。
entry：列表节点，长度不定，由真实保存的内容决定的。
zlend：占用1个字节，固定值255，用于标识整个压缩列表的结束。
在这些数据项中，entry用于保存真实的数据，可以是数字和字符串，它的数据结构包含如下几项：
prevrawlen：表示当前节点相邻前一个节点占用的字节数，这个字段的用处是为了让ziplist可以实现从后向前遍历。这个字段采用变长编码，如果长度是1字节，表示前一个节点的长度＜254个字节；如果长度是5个字节，表示前一个节点长度≥254，5个字节中第一个字节会被设置成固定值254，后面的4个字节表示前一个节点的真实长度。
len：表示当前节点保存的数据类型及占用的字节长度。共有9种取值类型，其中1字节高位00/01/10开头表示的字符串，2字节和5字节表示的也是字符串，1字节高位11开头的是整数，具体可参考 http://zhangtielei.com/posts/blog-redis-ziplist.html
data：真实的数据项，和len是对应的

4.2 举例分析

借用网上摘抄的案例，上面博客链接可参考

byte[0-3]：4个字节表示zlbytes，因为采用小端存储模式，图中采用16进制表示，0x00000021表示当前ziplist占用33个字节；
byte[4-7]：4个字节表示zltail，表示最后一个节点（数字20）起始位置距离当前压缩列表起始位置的字节偏移量，0x0000001D即偏移了29个字节；
byte[8-9]：2个字节表示当前压缩列表的节点的个数，有4个；
byte[10-15]：6个字节表示第一个节点，prevrawlen取值0，因为它没有前一个节点，len=4表示当前节点data占用4个字节，后面4个字节表示字符串“name”；
byte[16-23]：8个字节表示第二个节点，prevrawlen取值06，正好是前一个节点name占用的6个字节，len=6 当前data占用6个字节，后面6个字节表示字符串“tielei”；
byte[24-28]：5个字节表示第三个节点，prevrawlen取值08，正好是前一个节点tielei占用的8个字节，len=3 当前data占用的3个字节，后面3个字节表示字符串“age”；
byte[29-31]：3个字节表示第四个节点，prevrawlen取值05，表示前一个节点age占用的5个字节，len是16进制的FE表示整数，后面1个字节表示整数20；
byte[32]：1个字节表示最后一个结束符FF，即255，当程序遍历遇到这个值的时候，就知道已经到达了ziplist的结尾。

5 encoding-跳跃表skiplist

跳跃表是一种有序的数据结构，支持平均O(log n)，最坏O(n)时间复杂度的节点查找，同各类平衡树、哈希表一样也是一种查找算法的实现。redis中使用跳跃表作为有序集合底层实现的一种方式。

5.1 传统跳跃表结构

上面一层的节点数量是下面一层节点数量的一半，这样在查找的时候类似于二分查找，时间复杂度可以降低到O(log n)，但是在插入或者删除数据的时候，为了维持这种节点数量1:2的关系，就必须把插入节点之后的所有节点都重新调整层数，这样时间复杂度重新蜕化成O(n)。

下图展示了一个查找数字23的路径图：

5.2 zskiplist结构

redis使用的zskiplist与传统跳跃表不同，它并不要求上下两层节点的数量有严格的对应关系，每个节点的层数是通过计算一个随机数来得到的。如下图所示：

5.2.1 zskiplist的实现

redis的跳跃表是通过zskiplist和zskiplistNode两个结构定义的，其中zskiplist用于保存跳跃表的相关信息，而zskiplistNode用于表示每个跳跃表的节点。两者的具体结构如下：

zskiplist：

header/tail：指向跳跃表的头和尾结点，程序获取头尾节点的时间复杂度就是O(1)；
length：记录跳跃表的长度，也就是节点的数量（是不包含表头节点的）；
level：所有节点中的最大层高数（不包含头结点）
头结点默认高度是64（低版本是32），初始化时默认生成，不代表任何具体的数据，分值为0，其他都是NULL。

zskiplistNode：

ele：对应的成员对象，是一个字符串，保存着sds值，在同一个跳跃表中，成员对象必须是唯一的，否则后者会覆盖前者；
score：分值，是一个double类型的浮点数，允许重复，跳跃表中所有的节点都是按照score从小到大来进行排序的，如果分值相同的多个节点，会再按照ele的字典序来排列；
backward：后退指针，用于从表尾向表头方向访问节点，每个节点只能有一个后退指针，且跨度只能是1；
level：层，包含多个元素的柔性数组，每个元素都包含一个forward的前进指针和span的跨度。每次创建节点的时候，会随机生成一个介于1~64的随机层高数，数字越大概率越低，这就是数组的大小。
→ forward：前进指针，每个层都包含一个指向表尾方向的前进指针，与后退指针不同的是，前进指针有多个，指向相同层高的下一个节点。
→ span：层的跨度用于记录前进指针中两个节点之间的距离，跨度越大表示相距越远，所有指向NULL的前进指针跨度都是0。

程序在查找某个节点的时候，并不是挨个遍历的，所以span这个属性在用于记录所要查找的节点的“排位”的时候就显得十分重要，也是某些rank命令（zrank/zrevrank）能实现的主要依据。

5.3 zskiplist与传统跳跃表的不同

允许分值重复，这在传统的跳跃表中是不允许的，节点的唯一性不仅由score决定，还包括数据本身；
层高并不是严格按照某种比例关系限定的；
最底层的链表是双向的，支持表尾到表头方向的查找顺序。

6 encoding-整数集合intset

6.1 数据结构

整数集合是redis中用于保存整数值的抽象数据结构，它可以保存2个字节、4个字节、8个字节的整数值，并且整个集合中不会出现重复元素，与ziplist相似，是一块连续的内存空间。我们先来看下redis中intset的代码结构：

encoding：编码类型，表示整数集合中每个元素用几个字节存储，有3种的取值情况，INTSET_ENC_INT16表示每个元素用2个字节存储，INTSET_ENC_INT32表示每个元素用4个字节存储，INTSET_ENC_INT64表示每个元素用8个字节存储。因此，intset中存储的整数最多只能占用64bit，也就是(-263 ~ 263-1)。
length：记录了整数集合中元素的数量，也就是contents数组的长度。
contents：是整数集合的底层实现，整数集合的每个元素都是content数组的数据项，各个项在数组中从小到大有序排列，并且不会有任何重复项。数组占用总字节数 = encoding * length。

6.2 encoding的升级与降级

需要注意的是，随着元素的增加，encoding的值是可能会发生变化的，比如最开始encoding类型是 INTSET_ENC_INT16 (-32768~32767)，但是如果我们add 了 32768，那么encoding的类型就会升级成 INTSET_ENC_INT32。

6.2.1 升级

通过升级这种的方式，intset可以最大程度的节约内存的使用。升级的过程会包含以下步骤：

首先会计算新增元素的类型，如果当前encoding可以表示，则根据元素大小确定插入的位置（按照从小到大的顺序）。
如果元素的类型需要调整，会根据元素的个数和新的类型长度，确定contents数组的大小，重新分配空间。
对之前存在的所有元素进行类型转换，转换类型后放置在新的数组的正确位置上，放置过程中，继续维持底层数组的有序性质不变，最后将新增的元素添加到数组里面。

6.2.2 降级

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保存在升级后的状态。也就是encoding从INTSET_ENC_INT32变成 INTSET_ENC_INT64后，即使删除某些较大的元素，剩余元素可以使用 INTSET_ENC_INT32表示了，encoding的编码类型也不会变回去了。

7 encoding-快速列表quicklist

快速列表是redis列表list的唯一实现方式，我们可以把quicklist简单的理解成一个双向链表。它有这样的一些特性，支持在列表的头尾插入和删除元素，时间复杂度都是O(1)，但是在列表中间存取元素，需要对列表进行遍历，时间复杂度是O(n)。我们看一下官方对quicklist的描述：A doubly linked list of ziplists，是一个节点是ziplist的双向链表，前面我们已经提到了ziplist，结合压缩列表的特性，我们分析一下quicklist的特点。

ziplist是一块内存连续的空间，而且能维持插入元素的先后顺序，而双向链表同样也可以通过指针维护插入元素的先后顺序。但是这两个结构都有各自的优缺点，qucklist最终结合两者的特性，实现了redis对外暴露的list的数据结构，具体如下：

双向列表很方便的在两端进行push或pop元素，但是内存使用效率不高，首先除了保存真实数据，还要额外保存前后两个指针，其次每个节点都是单独一块内存，通过指针相连，非常容易产生内存碎片。
压缩列表在内存上是一整块连续的内存，存储效率更高。但是每当有数据变动都会有一次内存的重分配，如果数据量比较大，性能会更低。

7.1 每个压缩列表的节点数

于是，结合了双向链表和ziplist，quicklist就应用而生了。但是这里还有一个问题，比如现在总共有20个元素，如果每个ziplist里面有4个节点，有5个ziplist，这样的组合是可以的；如果每个ziplist里面有10个节点，有2个ziplist，这样的组合也是可以的。该如何去确定这个平衡，也要在内存使用效率上去综合分析：

如果每个ziplist中节点数量过多，极端情况下，所有节点集中在一个ziplist中，这样quicklist就蜕化成一个ziplist了；
如果每个ziplist中节点数量过少，极端情况下，每个ziplist中只包含一个节点，这样quicklist就蜕化成一个双向的linkedlist了；

redis在配置文件redis.conf中，设定了1个参数，其中 list-max-ziplist-size -2 是来决定这个平衡的。

这里默认值是-2，其他情况下，这个值可正可负。正数表示，每个ziplist中entry个数不能超过这个值，而负数只能取值 -1到-5，表示每个ziplist大小不能超过一定的字节数，如下：

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

7.2 中间数据项的压缩

redis还提供了一个配置项，用于决定是否对quicklist的元素进行压缩，以及压缩多少个，list-compress-depth 0，默认是0，表示不压缩，其他的正整数表示从quicklist的头部和尾部开始，分别跨过多少元素，对剩下的元素进行压缩。这里压缩的是一整个ziplist，而不是ziplist中的某个节点。通过压缩这些节点，可以进一步节省内存。

7.3 quicklist的三种代码结构

快速列表的实现是由3个部分组成的，分别是quicklist表示整个快速列表的元数据，quicklistNode表示每个ziplist节点，而quicklistLZF表示的是经过压缩后的ziplist节点。

7.3.1 quicklist

这是当前快速列表的元数据信息。

7.3.2 quicklistNode

这是每个quicklist的节点。

7.3.3 quicklistLZF

这是每个quicklist节点压缩后的状态。

7.4 quicklist的图示

我们来看一个案例，下面这个快速列表表示了每个ziplist中节点最大个数是3，两端的2个节点之外节点都被压缩了。

综上，6种底层的数据结构已经比较清晰了，我们再看下，基于这些数据结构，我们常用的5种类型是怎么实现的。可以点击看下一篇【Redis-03】Redis数据结构与对象原理 -下篇