nosql|Redis的底层数据结构数据结构|redis

一、Redis的数据结构简介
二、简单动态字符串SDS
三、链表
四、字典
五、跳跃表
六、整数集合
七、压缩列表
八、总结

一、Redis的数据结构简介 Redis 的底层数据结构一共有6种，分别为：简单动态字符串（SDS）、链表、字典、跳跃表、整数集合、压缩列表。
Redis的数据类型一共有5种，分别为：字符串对象、列表对象、哈希对象、集合对象、有序集合对象。这五大数据类型（数据对象）都是由一种或几种数据结构组成。
在命令行中，可以使用 OBJECT ENCODING key来查看key的数据结构。
二、简单动态字符串SDS redis是使用C语言编写的，但是string数据类型并没有使用C语言的字符串，而是重新编写一个简单的动态字符串（simple dynamic string，缩写为SDS）。

/* * 保存字符串对象的结构 */ struct sdshdr {// buf 中已占用空间的长度 int len; // buf 中剩余可用空间的长度 int free; // 数据空间 char buf[] };

使用SDS保存字符串Redis，具体表示如下：

文章图片

图片来自《Redis设计与实现》黄健宏著
各字段含义分别为：
free表示buf数组中剩余的空间数量。
len记录了buf数组中已存储的字节长度。
buf数组是一个char类型的数据，记录具体存储的字符串，并且以 ‘\0’(空字符) 作为结束标识符。
与C语言的字符串相比，SDS定义多出两个属性free、len，redis作者为何不直接使用C语言的字符串呢？原因为：
1、获取字符串长度复杂度为O(1)
由于C语言没有存储字符串长度，每次获取字符串长度时，需要循环整个字符串进行计算，时间复杂度为O(N)。
SDS记录了存储的字符串的长度，获取字符串长度时，直接获取len的属性值即可，时间复杂度为O(1)。SDS中设置和更新长度是API中自动完成，无需手动进行操作。
2、杜绝缓冲区溢出
C语言在进行两个字符串拼接时，一旦没有分配足够的内存空间，就会造成溢出。
SDS在修改字符串时，会先根据len的值，检查内存空间是否足够。如果不足，会先分配内存空间，再进行字符串修改。这样，就杜绝了缓冲区溢出。
3、减少修改字符串时带来的内存重新分配次数
C语言不记录字符串长度，所以当修改字符串时，会重新分配内存。如果是正常字符串，内存空间不够，则会产生溢出。如果是缩短字符串，不重新分配内容空间，则会产生泄露。
SDS采用空间预分配和惰性释放空间两种优化策略：
空间预分配：对字符串进行增长操作，会分配出多余的未使用空间，为以后扩展作准备。在一定程度上，这可以减少内存重新分配的次数。
惰性释放空间：对字符串经过缩短操作，并不会立即释放这些空间，而是使用free来记录这些空间的数量。当进行增长操作时，这些记录的空间就可以被重新利用。SDS提供了相应API进行手动释放空间，所以不会造成内存浪费。
4、二进制安全
C语言的字符串中不能包含空字符（因为C语言是以空字符判断字符串结尾的），所以不能保存一些二进制文件（有可能包含空字符，如图片）。
SDS是以len来判断字符串结尾，所以SDS结构可以存储图片等，并且都是以二进制方式进行处理。
5、兼容部分C字符串函数
SDS结构中，buf字段保存的字符串同样是以空字符结尾，所以可以兼容C语言的部分字符串操作API。
总结：

文章图片

表来源：《Redis设计与实现》
三、链表 Redis使用C语言编写，但C语言并没有内置链表这种数据结构，所以redis构建了自己的链表实现。
链表使用非常广泛，如列表键、发布与订阅、慢查询、监视器等。构成链表结构的节点为链表节点，数据结构为：

typedef struct listNode { // 前置节点 struct listNode * prev; // 后置节点 struct listNode * next; // 节点的值 void * value; }listNode;

多个listNode可以通过prev和next指针构成双端链表，使用list持有链表，数据结构为：

typedef struct list { // 表头节点 listNode * head; // 表尾节点 listNode * tail; // 链表所包含的节点数量 unsigned long len; // 节点值复制函数 void *(*dup)(void *ptr); // 节点值释放函数 void (*free)(void *ptr); // 节点值对比函数 int (*match)(void *ptr,void *key); } list;

各字段含义分别为：
head 表头指针。
tail 表尾指针。
len 链表长度计数器
dup、free、match 多态链表所需的类型特定的函数。
Redis链表结构示例图，如下所示：

文章图片

Redis链表实现的特性如下：
1、双端
链表节点带有prev和next指针，可以快速获取前置和后置节点，时间复杂度都是O(1)。
2、无环
头节点prev指针和尾节点next指针都指向null，对链表访问以NULL为终点。
3、带表头指针和表尾指针
可以快速获取表头节点和表尾节点。
4、有链表长度计数器
可以快速获取链表长度。
5、多态
链表可以保存各种不同类型的值，通过list的dup、free、match三个属性，为节点设计“值类型特定的函数”。
四、字典字典又称为符号表（symbol table）、关联数组（associative array）或者映射（map）。字典中存储key-value键值对，并且key不重复。字典在Redis中广泛应用，例如Redis数据库的底层实现就是字典。
Redis使用的C语言没有内置这种数据结构，所以Redis构建了自己的字典实现。
字典使用哈希表作为底层实现，一个哈希表包含多个哈希节点，每个哈希节点保存一个键值对。
哈希表节点的数据结构，如下所示：

typedef struct dictEntry { // 键 void *key; // 值 union{ void *val; uint64_tu64; int64_ts64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;

各字段含义分别为：
key属性保存着键值对中的键。
v属性保存着键值对中的值，可以是指针val、uint64_t整数、int64_t整数。
next是指向另一个哈希表节点的指针，用以解决多个哈希值冲突问题。
哈希表的数据结构，如下所示：

typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值。总是等于size-1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used; } dictht;

各字段含义分别为：
table是一个数组，数组元素是dictEntry结构的指针，每个dictEntry保存一个键值对。
size 记录哈希表的大小。
sizemask 值总是等于size-1，这个属性和哈希值一起决定“一个键应该被放到table数组的哪个索引上”。
used 记录哈希表目前已有节点的数量。
hash表结构示例图，如下所示：

文章图片

一个大小为4的空哈希表
下图展示的是“在哈希表中，将两个索引值相同的键连在一起”。

文章图片

字典数据结构，如下所示：

typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdata; // 哈希表 dictht ht[2]; // rehash索引 //当rehash不在进行时，值为-1 in trehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict; typedef struct dictType { // 计算哈希值的函数 unsigned int (*hashFunction)(const void *key); // 复制键的函数 void *(*keyDup)(void *privdata, const void *key); // 复制值的函数 void *(*valDup)(void *privdata, const void *obj); // 对比键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj); } dictType;

字典数据结构中，各字段值含义分别为：
type 属性是一个指向dictType结构的指针，每个dictType机构保存了一簇用于操作特定类型键值对的函数。Redis会为“用途不同的字典”设置“不同的类型特定函数”。
privdata 属性保存了需要传给那些类型特定函数的可选参数。
ht 属性是一个长度为2的数组，数组中的每个元素都是一个哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在进行rehash时使用。
trehashidx 属性记录了rehash目前的进度。如果没有进行rehash，则它的值为-1。
下图所示为普通状态下的字典结构。

文章图片

当一个新的键值对要添加到字典中去时，会涉及到一系列的操作，如计算索引、解决冲突、扩容等。下面对这些操作进行描述。
1、哈希算法
添加键值对时，首先要根据“键值对中的键”计算出哈希值和索引值，然后再根据索引值进行放入。伪代码如下所示：

#使用字典设置的哈希函数，计算键key的哈希值。 hash = dict->type->hashFunction(key); #使用哈希表的sizemask属性和哈希值，计算出索引值。根据情况不同，ht[x]可以是ht[0]或者ht[1]。 index = hash & dict->ht[x].sizemask;

2、解决键冲突
当“有两个或以上数量的键值”被分配到了“哈希表数组的同一个索引上”时，就发生了键冲突。
Redis的哈希表使用单向链表解决键冲突问题，每个新的键总是添加到单项链表的表头。
3、rehash（扩展或收缩）
哈希表具有负载因子（load factor），其始终需要保持在一个合理的范围之内。当hashI表保存的键值对过多或过少时，就需要对哈希表进行rehash（重新散列）操作，步骤许下：
(1) 为字典的ht[1]分配空间，空间大小：如果是扩展操作，则为ht[0].used * 2 ，也就是扩展为当前哈希表已使用空间的1倍；如果是收缩，则减小1倍。
(2) 将ht[0]内的数据重新计算哈希值和索引，并放到新分配的ht[1]空间上。
(3) 全部迁移完成后，将ht[1]设置为ht[0]，释放ht[0]，并创建一个空白的哈希表为ht[1]，为下次rehash做准备。
4、哈希表的扩展与收缩触发条件
哈希表扩展条件：
(1) 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
(2) 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。
以上条件中任意一条被满足，程序自动开始对哈希表进行扩展；
负载因子算法：负载因子 = 哈希表已保存的节点数量 / 哈希表大小。
哈希表收缩条件：
当负载因子小于0.1时，程序自动进行收缩操作。
5、渐进式rehash
渐进式rehash就是：在ht[0]的键值对向ht[1]迁移的过程中，如果数据量过大，则不能一次性迁移；否则，会对服务器性能造成影响，而是分成多次，渐进式的进行迁移。
在rehash期间，会维持一个索引计数器rehashidx，并把迁移工作分配到每次的添加、删除、查找、更新操作中，当rehash工作完成后，rehashidx会增加1。ht[0]的值全部迁移完成后，程序会将rehashidx这是为-1，标识最终的rehash完成。
6、渐进式rehash期间的表操作
在渐进式rehash期间，ht[0]和ht[1]中都有数据。当查找时，会先在ht[0]中进行，若在ht[0]中没找到，则继续到ht[1]中找。添加操作一律会添加到ht[1]中。
五、跳跃表跳跃表（skiplist）数据结构特点是：每个节点中有多个指向其他节点的指针，从而快速访问节点。
跳跃表zskiplist由跳跃表节点zskiplistNode组成。
跳跃表节点的数据结构，如下所示：

typedef struct zskiplistNode { // 层 struct zskiplistLevel { // 前进指针 struct zskiplistNode *forward; // 跨度 unsigned int span; } level[]; // 后退指针 struct zskiplistNode *backward; // 分值 double score; // 成员对象 robj *obj; } zskiplistNode;

各字段含义如下所示：
层：为一个数组，数组中的每个数据都包含前进指针和跨度。
前进指针：指向表尾方向的其他节点的指针，用于从表头方向到表尾方向快速访问节点。
跨度：记录两个节点之间的距离，跨度越大，两个节点相聚越远。所有指向NULL的前进指针的跨度都为0。
后退指针：用于从表尾节点向表头节点访问，每个节点都有后退指针，并且每次只能后退一个节点。
分值：节点的分值是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大排列。
成员对象：是一个指向字符串的指针，字符串则保存着一个SDS值。
跳跃表的数据结构，如下所示：

typedef struct zskiplist { // 表头节点和表尾节点 structz skiplistNode *header, *tail; // 表中节点的数量 unsigned long length; // 表中层数最大的节点的层数 int level; } zskiplist;

各字段含义如下所示：
header指向跳跃表的表头节点。
tail指向跳跃表的表尾节点。
level记录节点中的最大层数（不含表头节点）。
length记录跳跃表的长度，即跳跃表目前包含的节点数量（不含表头节点）。

跳跃表节点由很多层构成（L1、L2 ...），每个层都带有两个属性：前进指针和跨度。
每个跳跃表节点都包含成员对象（obj）、分值（score）、后退指针（backward）。头结点也包含这些属性，但不会被用到。
此处只是介绍跳跃表的结构相关内容。关于跳跃表节点中层的形成、对象的插入、删除、查询等操作的原理，在此处不做详解。
下图所示为一个跳跃表结构示例。

文章图片

六、整数集合整数集合（intset）是集合键的底层实现之一。当一个集合只包含整数元素，并且元素的个数不多时，Redis就会使用整数集合作为集合键的底层实现。
整数集合可以保存int16_t、int32_t、int64_t的整数值，并且不会出现重复元素。
整数集合的数据结构，如下所示：

typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[]; } intset;

各字段含义如下所示：
encoding编码方式有三种INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64，分别对应的是int16_t、int32_t、int64_t类型。
length记录整数集合的元素数量，即contents数组的长度。
contents数组存储的是集合中的每个元素，类型是int8_t，但存储数据的实际类型取决于编码方式encoding。
整数集合的升级操作
整数集合中原来保存的是小类型（如：int16_t）的整数，当插入比其类型大（如int_64_t）的整数时，会把“整数集合里元素的数据类型”都转换成“大的数据类型”，这个过程称为升级。
升级整数集合并添加新元素步骤如下：
（1）根据新元素的类型，扩展整数集合底层数据的空间大小，并为新元素分配空间。
（2）将现有的所有元素的类型转换成与新元素相同的类型，在保持原有数据有序性不变的情况下，把转换后的元素放在正确的位置上。
（3）将新元素添加到数组里。
新元素引发升级的条件是：“新元素的数据类型”比“所有元素的数据类型”都大。

当小于所有元素时，新元素放在底层数组的最开头。
当大于所有元素时，新元素放在底层数据的最末尾。

升级操作的好处

提升整数的灵活性，可以任意的向集合中放入3中不同类型的整数，而不用担心类型错误。
节约内存，整数集合中只有大类型出现的时候，才会进行升级操作。

整数集合不支持降级操作。
七、压缩列表压缩列表（ziplist）是Redis为了节约内存而开发，是一系列特殊编码的连续内存块组成的顺序型数据结构。
一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。
压缩列表的结构，如下图所示。

文章图片

各字段含义分别为：

文章图片

每个压缩列表含有若干个节点，而每个节点都由三部分构成（previous_entry_length、encoding、content）。
压缩列表节点的结构，如下图所示：

文章图片

各字段含义分别为：

previous_entry_length 存储的是前一个节点的长度，由于压缩列表内存块连续，使用此属性值，可以计算前一个节点的地址。压缩列表就是使用这一原理进行遍历。如果前一节点长度小于254字节，那么previous_entry_length属性本身长度为1字节，存储的值就是前一节点的长度；如果大于254个字节，那么previous_entry_length属性本身长度为5个字节，前一个字节为0xFE(十进制254)，“之后四个字节”存储“前一节点的长度”。
encoding 记录本节点的content属性所保存数据的类型及长度，其本身长度为1字节、2字节或5字节。值的最高位为00、01或10的是字节数组的编码，最高位以11开头的是整数编码。
content 保存节点的值，可以是一个字节数组或者整数。

连锁更新
对压缩列表进行添加节点或删除节点时，有可能会引发连锁更新。
由于每个节点的 previous_entry_length 存在两种长度（1字节或5字节），当所有节点previous_entry_length都为1个字节时，若新节点的长度大于254个字节，那么新节点的后一个节点的previous_entry_length原来为1个字节，无法保存新节点的长度，这时就需要对其进行空间扩展，即“新节点的后一个节点的previous_entry_lengthprevious_entry_length属性”由原来的1个字节增加4个字节，变为5个字节。如果增加后原节点的长度超过了254个字节，则后续节点也要空间扩展。以此类推，最极端的情况是一直扩展到最后一个节点完成。这种现象称为连锁更新。在日常应用中，全部连锁更新的情况属于非常极端的，不常出现。

八、总结 Redis的底层数据结构共有6种，分别为：简单动态字符串（SDS）、链表、字典、跳跃表、整数集合、压缩列表。
在redis命令下，可以使用 OBJECT ENCODING 命令，查看键值对象的底层编码方式。
【nosql|Redis的底层数据结构】思考：Redis字典底层结构实现与java(1.6之前) 中的hashmap非常相像，都是使用单项链表解决键冲突问题。jdk1.8以上已经是用红黑树解决多个键冲突问题，不知redis的键冲突是否也可以用红黑树来解决？