Redis基本数据结构 Redis基本数据结构

在翻看Redis各种书籍和博客文章后，感觉还是需要写一下笔记或者心得才好，写到博客上以便以后复习或者查询。
说起redis，大家肯定会想起5种数据类型，这也是Redis能够存储的数据结构，Redis称之为对象的5种数据类型。基于这些对象实现了redis键值对数据库。

String(字符串)
Hash(哈希)
List(列表)
Set(集合)
Zset(有序集合)
在了解这5种对象前，我们有必要介绍redis的基本数据类型.

一、SDS(simple dynamic string) 简单动态字符串

文章图片
SDS结构图
如图是个SDS实例，有以下特点:

buf数组是个字节数组，记录字符串，最后一个字节是个空字符，类似于c语言中字符串（本来redis就是c语言所写，但是redis并未照搬，而是自己实现了特殊的简单动态字符串），但是buf数组长度并不是字符串长度+1，而是有空余空间，图中buf数组有6个字节，前5个字节储存'R','e','d','i','s',最后一个字节储存'\0'.并没有空余空间。
free便记录了buf数组中未使用的字节的数量，注意空字符也算使用，图中没有未使用字节，所以数量是0.
len记录buf数组已使用字节的数量，等于SDS保存的字符串的长度，不包括空字符，图中Redis长度是5，所以len是5.
构造这样的一个数据结构的好处如下：

1. 常数复杂度获取字符串长度
只需要访问len属性即可知道buf储存redis字符串的长度，当然设置和更新SDS长度的工作是SDS的api执行时自动完成的，我们无需手动操作。
2. 防止缓冲区溢出
SDS的API对SDS进行修改时，会先检查空间是否够用，如果不够会进行空间拓展至够用的大小，防止空间不够而产生溢出问题。
3. 减少修改字符串带来的内存重新分配
redis是一个被用于速度要求严格，数据被频繁修改的场合，所以避免频繁内存重新分配不会影响性能。
通过未使用空间，redis实现了空间预分配和惰性空间释放两种优化策略：
3.1空间预分配当SDS的API对一个SDS进行修改时，并且需要对SDS进行空间拓展时候，API不仅会为SDS分配修改所必需的空间，同时也会为SDS分配额外的未使用空间。
其中额外的未使用空间由一下公式决定：

在对SDS修改后，SDS的长度也就是len的值小于1MB，那么API分配和len属性同样大小的未使用空间，比如修改后SDS是10字节，那么API会分配10字节的空余空间，此时，free的值也是10字节，buf数组长度就是10+10+1=21（多余的一字节是空字符）
如果修改后SDS长度大于1MB，那么API分配1MB的空余空间，比如修改后SDS是1.5MB,那么分配1MB对的未使用空间，free是1MB，buf数组长度是1.5MB+1MB+1byte.

3.2惰性空间释放啥叫惰性空间释放，实际上就是不释放，而是用free记录下减少的字节长度，以备将来使用。

文章图片
SDS修改前

文章图片
SDS修改后
可以看到修改后buf'数组空余空间并没有被回收，而是free记录了多出来的空余空间。
4.二进制安全
二进制安全我的理解就是redis字符串的解析并未是按照某种特殊字符来解析的，比如c语言中字符串末尾有一个'\0'来判断字符串结尾，但是redis并没有参照这个标准，它是根据len长度来判断字符串的结尾，否则在字符串中间有一个空格，将会导致字符串的提前结束，总结就是：字符串不是根据某种特殊的标志来解析的，无论输入是什么，总能保证输出是处理的原始输入而不是根据某种特殊格式来处理。
5.兼容部分c字符串函数
可以重用一部分的函数。
二、链表

文章图片
链表节点结构图
多个listNode构成了双端链表

文章图片
双端链表
列表的底层实现就是一个链表，当然redis还有很多地方也使用到了链表，发布与订阅，慢查询，监视器等
列表结构如下：

文章图片
列表结构图

dup函数复制节点保存的值
free函数释放链表保存的值
match函数对比链表保存的值和另一个输入值是否相等

文章图片
list和listNode组成的链表
可以看出链表特性有以下几点：
双端：链表节点都带有prev和next指针，分别指向前端节点和后置节点。
无环：表头节点的prev指向NULL，表尾节点的next指向NULL。
链表长度记录：使用list结构的len顺序ing记录对list持有的链表节点进行计数。
多态：链表节点使用void*指针来保存节点值，通过list结构的三个函数来设置特定类型函数，所以链表可以保存不同类型的值。

三、字典字典又叫做符号表(symbol table),关联数组(associative array)或映射(map),是一种保存键值对(key-value pair)的数据结构，字典也是哈希键的底层实现之一。
了解字典前，我们需要了解哈希表，结构如下:
1.哈希表

文章图片
哈希表结构 2.哈希节点
哈希表节点用dictEntry结构表示:

文章图片
哈希表节点结构
一个完整的哈希表结构如下图：

文章图片
哈希表
图中对属性均有介绍，这里不再多赘述。
值得注意的是dictEntry中的next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值sizemask(也就是索引值)相同的键值对连接在一起，以此解决键冲突的问题。 3.字典
讲完哈希表和哈希节点，这时我们看向字典的结构图。

文章图片
字典结构

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，redis会为用途不同的字典设置不同的类型特定函数。
privdata则保存了需要传给那些类型特定函数的参数

文章图片
dictType结构图
哈希表ht是一个长度是2的数组，一般情况下字典只使用ht[0]哈希表，ht[1]哈希表是在对ht[0]哈希表进行rehash时使用。
最后一个属性便是rehashidx，它记录rehash的进程，如果当前没有在rehash，那么值为-1.
下图是一个没有在rehash状态下的字典

文章图片
没有rehash状态下的字典

4.哈希算法
新的键值对加入字典时，程序根据键值对的键计算出哈希值和索引值，然后放入哈希数组里面，当前redis使用的是MurmurHash2算法。
5.键冲突
前面说到next属性指向另一个相同hash值哈希表节点的指针来解决键冲突，注意，后面加上来的那个冲突键是添加到链表的表头位置，
如图：没有键冲突的哈希表

文章图片
没有冲突的哈希表
加入(k2-v2)会产生冲突键的哈希表

文章图片
产生冲突的哈希表
可以看到(k2-v2)这个产生冲突的键值对被加入了相同hash值的链表的表头位置。 6.rehash
首先有一个参数是负载因子:
load_factor = ht[0].used / ht[0].size
下面两种情况满足一种时，将进行哈希表的拓展操作:

服务器没有执行BGSAVE和BGREWRITEAOF命令，并且负载因子大于等于1,
服务器在执行BGSAVE和BGREWRITEAOF命令，并且负载因子大于等于5

满足下面条件时，将进行哈希表的收缩操作

哈希表的负载因子小于0.1

rehash涉及到空间大小的分配，规则如下：
1.为字典的ht[1]分配空间

如果执行的是扩展操作，那么ht[1]的大小是第一个大于等于ht[0].used * 2 的2
的n次幂(比如ht[0].used * 2等于8,8是第一个大于等于2的3次幂的数字)
如果是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2的n次幂。
2.将保存在ht[0]中的所有值对rehash到ht[1]上面。
3.当ht[0]包含的键值对都迁移到ht[1]上后，释放ht[0]，然后将ht[1]设为ht[0],将ht[1]指向空白哈希表，为下一次rehash做准备。
完整执行一次rehash图解如下：
没有rehash前

文章图片
执行rehash前
ht[0].used * 2 = 8,8是第一个大于等于2的3次幂的数字，所以ht[1]的大小是8,
第一次rehash

文章图片
第一次rehash
ht[0]的键值对全部rehash

文章图片
全部rehash
释放ht[0],将ht[1]设置为ht[0],并将ht[1]分配空的哈希表

文章图片
完成rehash

7.渐进式rehash
上面所说的rehash并不是一次性执行完毕，而是分多次，渐进式将ht[0]中的键值对rehash到ht[1]中。
以下是步骤：
1.为ht[1]分配空间，让字典同时拥有ht[0]和ht[1]
2.在字典中维持一个rehashidx，并将它设置成0，表示rehash正式开始
3.在rehash期间，每次对字典的增删改查会分别在两个表上执行，查找的时候会先在ht[0]，如果没有再去ht[1]，同时新添加的字典值会被添加到ht[1]中，保证ht[0]只减不增。
4.rehash完毕。
四、跳跃表(skiplist) 跳跃表是一种有序，效率高的数据结构，是有序集合键的底层实现之一。
跳跃表结构由多个跳跃表节点结构组成。

//跳跃表节点结构 typedef struct zskiplistNode { //成员变量 robj obj; //分值 double score; //后退指针 struct zskiplistNode *backward; //层 struct zskiplistLevel { //前进指针 struct zskiplistNode *forward; //跨度 unsigned int span; } level[]; } zskiplistNode; //跳跃表结构 typedef struct zskiplist { //表头结点和表尾节点 struct zskiplistNode *header, *tail; //表中节点的数量 unsigned long length; //表中层数最大的节点的层数 int level; } zskiplist;

了解结构图后，我们看向这样一张图片，看懂了这个图，也就了解了跳跃表的结构。

文章图片
跳跃表图
结合上面的结构代码和这张图来解释图中内容。
跳跃表节点结构

zskiplistLevel 层

这是一个数组，数组中的每个元素都包含一个指向其他节点的指针，每次创建一个跳跃表节点的时候，根据幂次定律随机生成一个1~32的数作为level数组的大小，这个大小便是层的高度。
图中从左到右4个节点层的高度分别是32，4，2，5。

struct zskiplistNode *forward 前进指针

虚线表示的便是前进指针，表示出了表头到表尾遍历所有节点的路径，到达表尾时，指针指向NULL。

unsigned int span 跨度

跨度用来表示两个节点之间的距离，图中方向箭头上面的数字便是跨度，指向NULL的箭头的跨度是0.可以看到前进指针可以跨越多个节点。

struct zskiplistNode *backward 后退指针

图中BW就是后退指针，跟前进指针不同，每个节点只有一个后退指针，所以每次后退只能后退至前一个节点。

分值和成员

分值是double类型，跳跃表中的分支按照从小打到排列，图中的1,23就是分值
成员变量是一个指针，它指向一个字符串对象，字符串对象存着一个SDS值，图中的o1,o2,o3就是成员变量，各个节点的成员变量必须是唯一的，但是多个节点保存的分值是可以一样的，分值一样的时候节点将按照成员变量在字典序中的排序来排列。
跳跃表结构

header 表头结点

指向跳跃表的表头节点，图中有32层的便是表头节点(表头结点也是有后退指针和分值以及对象的，这里省略了)

tail 表尾指针

指向跳跃表的表尾节点

level 层数

记录跳跃表内层数最大的那个节点的层数(表头节点的层数不计算在内)

length 表中节点的数量

跳跃表的长度，也就是跳跃表中包含节点的数量(表头节点不计算在内)
多说一句，表头结点的长度固定是32，但是很多计算都不把表头节点计算在内。
五、整数集合(intset)

文章图片
整数集合结构
content数组中的值从小到大有序排列，数组中不包含任何重复值。我们看到contents数组虽然是定义成了int8_t，但是具体的数据类型取决于encoding编码方式，它并不保存int8_t类型的整数。

encoding是INTSET_ENC_INT16，contents是一个int16_t类型整数数组(-32768~32767)
encoding是INTSET_ENC_INT32，contents是一个int32_t类型整数数组(-2147483648~2147483647)
encoding是INTSET_ENC_INT64，contents是一个int16_t类型整数数组(-9223372036854775808~9223372036854775807)

1.升级

文章图片
添加前

文章图片
添加后
我们添加的很大很大的数需要64位来存储，此时所有元素都转换成与新元素相同的类型也就是INTSET_ENC_INT64，并在转换中仍然保持有序性。每次添加新元素时都可能升级，升级需要对所有元素升级，所以添加的复杂度是O(N)，因为intset中的数值是以升序排列存储的, 插入与删除的复杂度均为O(n). 查找使用二分法, 复杂度为O(log_2(n))也就是O(lgn)
我在一些书上看到升级带来的优点有灵活性，节约内存，但我仍然觉得这个升级带来的开销还是比较大的，毕竟涉及到分配内存的事情都需要降低性能。同时intset不支持降级。
六、压缩列表(ziplist) 压缩列表是列表建和哈希键的底层实现之一。
听名字就可以看出来这个数据结构的作用，就是节省内存，所以当列表键只包含少量列表项，并且每个列表项要么是小整数，要么就是长度比较短的字符串，此时压缩列表就可以作为列表键的实现之一。
压缩列表是一块连续的内存空间，值是小端序排列(高字节保存在内存的高地址,大端序是高字节保存在内存的低地址)
下面两张图能让你很好地理解压缩列表：

文章图片
压缩列表示例

文章图片
属性介绍表

zlbytes属性是0x50 ，也就是十进制80，表示压缩列表总长是80
zltail是0x3c，十进制60，也就是此时p指针加上60就是entry3这个表尾节点的地址
zllen是0x3,十进制3，表示压缩列表有三个。但是在这张表中所说，如果属性值小于65535，则是真正的，否则需要遍历压缩列表才能计算出属性。

关于entry结构如下：

文章图片
压缩列表节点图

previous_entry_length：看名字就知道这是前一个entry的长度，这个属性的长度是1字节所以5个字节。
-- 1字节：表示前一个节点的长度小于254字节
-- 5字节：表示前一个节点的长度大于254字节，此时这个属性的第一个字节被设置成0xFE(十进制254)，后面的4个字节才是前一个字节真正的长度。
下面两张图表示了前一个字节长度分别小于254字节和大于254字节的情况。

文章图片
小于254字节

文章图片
大于254字节
大于254字节时，此时后面的四字节00002766(十进制10086)才是前一个节点真正的长度。

关于encoding，根据后面content数据类型不一样，encoding也会不一样。

文章图片
字节数组
encoding长度是1,2,5字节，值得最高位是00，01，10，此时表示储存的是字节数组。数组长度由编码除去最高两位

文章图片
整数数组
encoding长度是1字节，值得开头是11开头，此时表示储存的是整数数组。数组长度由编码除去最高两位前面说到ziplist基本不浪费内存，并且previous_entry_length记录了前一个字节的长度，倘若对压缩列表增删会出现什么情况，也就是极端情况下的连锁更新。
1.连锁更新
考虑这样一种情况，所有的节点长度均小于254字节，并且处于250--253(这样previous_entry_length由1字节变为5字节时，会超过254字节)，此时的previous_entry_length都是1个字节，但是此时插入一个大于254字节的节点到列表表头，原先表头节点变为第二个节点，第二个节点的previous_entry_length此时需要变为5个字节来存储新的表头结点，比原先增加了4个字节，来到了254--257，超过254，这样后面的节点的previous_entry_length也需要更新，这样连锁更新造成的影响很大，最坏情况下需要执行N次空间重新分配，每次空间重新分配的最坏复杂度是O(N),所以连锁更新的最坏复杂度是O(N2)。删除时也会在这种极端情况下产生这种问题。
当然上述情况是很极端的，其实也可以忽略不计。
七、对象我们说完redis基本的数据结构后，终于可以来到开头所说的对象这来了，redis五大对象:

String(字符串)
Hash(哈希)
List(列表)
Set(集合)
Zset(有序集合)

redis每一个对象都由一个redisObject结构表示，该结构中和保存数据有关的属性如下

文章图片
redisObject 1.类型
type记录了对象的类型，是以下当中的一个。

文章图片
对象类型
我们知道redis是键值对数据库，其中键总是一个字符串对象，而值则是上图中的5种中的一种。
2.编码
编码和我们前面的基本数据类型对应上了。

文章图片
底层数据结构对象编码
下面这张图则是不同类型和编码的对象。

文章图片
不同类型和编码的对象可以看出来这5种对象每个都使用了至少两个编码类型，下面我们对这5种对象展开来说：
3.字符串对象
字符串对象编码可以是int,raw,embstr
字符串对象保存整数10086，此时是int编码

文章图片
int编码保存10086
【Redis基本数据结构】字符串对象保存字符串值，长度大于32，此时编码是raw，并且字符串对象使用简单动态字符串SDS来保存。

文章图片
raw编码的字符串对象字符串对象保存字符串值，长度小于32，此时编码是embstr

文章图片
embstr编码的字符串对象 embstr编码和raw编码区别在于embstr只调用一次内存分配释放函数来进行内存分配，同时分配的内容是在一个连续内存上面。
3.1编码转换 int编码的字符串对象(整数数据结构实现)我们是可以转换成一个真正存储的值也是字符串的一个字符串对象(实际上就是给当前对象做一个追加字符串值的操作),此时int编码转换成raw。
redis并未对embstr编码的字符串对象编写修改程序，也就是这个编码的字符串对象是只读的，当我们对embstr编码的字符串对象修改时，都会变成一个raw编码的字符串对象。
4.哈希对象
哈希对象的底层实现有两种, 一种是字典, 一种是压缩列表. 分别对应编码hashtable与ziplist
当使用ziplist编码的哈希对象使用压缩列表，每次有新的键值对加入哈希对象中时，保存键的压缩列表节点会进入压缩列表表尾，然后再将保存值的压缩列表节点推入列表表尾，这样保存了一对键值对的两个节点总在一起，保存键的节点在前，保存值的节点在后。
如图是一个压缩列表编码的哈希对象

文章图片
ziplist编码的哈希对象另一方面，hashtable编码的哈希对象中每个键值对都是用字典键值对来保存数据，如下：

文章图片
hashtable编码的哈希对象 4.1编码转换哈希对象可以同时满足以下两个条件时使用ziplist编码，不能满足时需要使用hashtable编码。

哈希对象保存的所有键值对的键和值的字符串长度都小于64字节。
哈希对象的键值对数量小于512个。

5.集合对象
集合对象的底层实现有两种, 分别是整数集合(intset)和字典(dict). 分别对应编码宏中的intset和hashtable，使用intset作为底层实现的数据结构时, 集合中存储的只能是整数. 而当使用dict作为集合对象的底层实现时, 是将数据全部存储于dict的键中, 值字段为NULL。
intset编码的集合对象

文章图片
intset编码的集合对象 hashtable编码的集合对象

文章图片
hashtable编码的集合对象 5.1编码转换集合对象可以同时满足以下两个条件时使用intset编码，不能满足时需要使用hashtable编码。

集合对象保存的都是整数值
集合对象保存的元素数量不能超过512

6.有序集合
有序集合的底层实现有两种, 一种是使用压缩列表作为底层实现, 另外一种比较特殊, 底层使用了两种数据结构: 字典与跳跃表. 前者对应的编码为ziplist, 后者对应的编码为skiplist
使用压缩列表(有序)作为底层实现时，每个集合元素使用两个紧挨在一起的压缩列表来保存，第一个节点保存元素的成员，第二个元素保存元素的分值。分值按照从小到大排序。

文章图片
使用ziplist编码的有序集合使用字典与跳跃表数据结构作为底层实现时，首先跳跃表按照分值大小有序的保存了所有的集合元素，每个跳跃节点保存一个值，object属性保存了元素的成员，score属性保存了元素的分值，以便于进行范围型操作。
其次字典为有序集合创建了一个从成员到分值的映射，字典的每一个键值对都保存一个集合元素，字典的键保存与元素的成员，字典的值则是元素的分值，通过这个字典，根据成员查找分值的复杂度是O(1)。
两种数据通过指针来贡献相同的元素的成员和分值，所以不产生重复成员或者分值。
下图是字典和跳跃表编码的有序集合