Redis是一款优秀的key-value数据库，其中存储的键值对都是有对象(Object)组成，可以存储字符串对象、哈希对象、列表对象、集合对象、有序集合对象;由于C语言中没有相关对象的实现，Redis自身扩种底层的数据结构实现上述对象的存储，本文将对REDIS数据库底层的数据结构进行介绍。
1. SDS字符串
Redis并没有直接采用C语言中字符串表示(以空字符结尾的字符数据，一下简称C字符串)，而是扩展一种名为简单动态字符串(Simple Dynamic String, SDS)的数据结构，并将SDS作为Redis默认字符串表示。其主要出于安全性、效率性考虑。SDS数据结构如下:
typdef struct sdshdr{
//记录buff数组中以使用字节的数量
//相当于sds字符串的长度
int len;
//buff中卫使用字节的数量
int free;
//字节数组用于保存字符串
char *buff;
} SDS;
效率性
C字符串以‘\0’结尾，获取字符串长度需要遍历数组，其时间复杂度O(N),伪代码如下:
int cnt = 0;
while( *buff++ != '\0'){
cnt++;
}
return cnt;
对于SDS字符串来说,sdshr->len即是字符串长度，时间复杂度为O(1).
字符串数据结构是在程序中经常会使用到的数据结构,Redis把字符串长度时间复杂度从O(N)降到O(1),这确保获取字符串长度的工作不会成为Redis的性能瓶颈。
安全性
除了获取字符串的复杂度高之外，C字符串不记录自身长度带来另一个问题是容器造成缓冲区溢出。举个例子,
如果程序执行stcat(s1," world");将s1的内容修改为“hello world”,那么在strcat函数执行之后,s1数据将溢出，s2的数据将被破坏。
与C字符串不同，SDS自动空间分配策略防止发生缓冲区溢出的可能性;当SDS API需要对SDS进行修改时，API首先检查SDS空间是否满足修改的要求,如果不满足的话，API将进行空间扩展至执行修改所需大小,然后执行拼接,伪代码如下：
strcat(SDS dest,SDS src){
if(src->len > dest->free){
//重新分配空间，再复制
}else{
//复制字符串
}
}
此外，当SDS的API对一个SDS进行修改，发生缓冲区扩充时候，redis采用空间预分配机制，即程序不仅分配SDS修改所必须要的空间，还会分配额外的未使用空间。具体策略分为以下两个方面:
- 如果修改后的SDS的长度(len属性)小于1M，则程序在分配缓冲区时，回额外分配len长度同样大小的未使用空间(free属性)。
- 如果修改后的SDS的长度大于1M,则程序在分配缓冲区时，会额外分配1M未使用的空间(free属性)。
二进制安全性
C字符串的长度以’\0’结尾，并且除了结尾字符可以是’\0’，字符串里面不能包含空字符，否则程序最先被程序读入的空字符会被误认为是字符串的结尾，这限制C字符串之鞥保存文本数据，不能保存图像、音频、压缩文件这样的二进制文件。但是Redis采用len属性标志字符串的结尾，这使得Redis可以存储多种类型数据，是二进制安全。
总结
Redis只会使用C字符串作为字面量，大多数情况下Redis使用SDS座位字符串的表示。 比起C字符串，SDS具有如下优点:
- 常熟复杂度获取字符串长度
- 避免缓冲区溢出
- 预分配机制减少修改字符串时内存冲分配次数。
- 二进制安全
2.链表
链表作为一种高效的数据存储结构内嵌在许多高级语言中，但是C语言没有list结构,因此Redis定义一种链表结构,其数据结构如下:
//链表节点
typedef struct {
//前置节点
struct listNode *prev;
//后置节点
struct *listNode *next;
//节点值
void *value;
} listNode;
//链表
typedef struct {
//头指针
listNode *head;
//尾指针
listNode *tail;
//长度
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void *(*free)(void *ptr);
//节点值对比函数
int (*match)(void *ptr,void *key);
}
list结构为链表提供了表头指针head、表尾指针tail以及链表长度计数器le，而dup、free\match函数则是用于实现多态链表所需的类型特定函数。
下图是一个list链表结构示意图:
总结
- 链表是一个双端链表，每个链表节点有一个
listNode结构来表示 - 每个链表使用
list结构来表示，这个结构带有头指针、尾指针以及长度等信息 - Redis链表可以保存各种不同类型的值
- 广泛应用于实现redis各种功能
3.字典
字典又叫关联数组、映射(map),是一种保存键值对的抽象数据结构。字典在Redis中应用相当广泛，器数据库就是使用字典座位底层实现，对数据库的增删改查操作也是构建在对字典的操作之上。 其数据结构如下所示：
typedef struct dictht {
// 哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
unsigned long sizemask;
//该hash表已有节点的数量
unsigned long used;
} dictht;
typedef struct dictEntry {
//键
void *key;
//值
union {
void *val;
uint64_tu64;
int64_ts64;
} v;
//指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
typedef struct dict{
//类型特定函数
dictType *type;
//私有数据
void *pricdata;
//hash表
dictht ht[2];
//rehash索引
int rehashidx;
} dict;
如图是一个例子:
哈希表扩容
哈希表扩容步骤如下:
- 计算扩容后的内存,分配相应存储空间赋值给
ht[1] - 将
ht[0]中元素根据hash算法全部重新映射到ht[1]空间中 - 回收原来
h[0]内存空间 - 将
ht[1]赋值给ht[0]
哈希表中元素个数可能很多,如果一次性进行rehash将会耗费大量时间，阻塞服务端对客户端服务进程，因此哈希表采用一种渐进式hash算法,即是将rehash动作分多次、渐进式地完成。其步骤如下:
- dict数据结构中
rehashidx标志 rehash的位置。 - 为
ht[1]分配内存空间，让字典同时持有ht[0]和ht[1]两个hash表。 - 在rehash期间，每次对字典进行添加、删除、查找、或者更新操作时候程序处理执行指定操作意外，还会顺带将ht[0]哈希表在
rehashidx索引上的所有键值对rehash到ht[1],当rehash完成之后，程序将rehashidx属性的值+1 - 随着字典操作的不断执行，最终
ht[0]内的所有键值对都会被rehash到ht[1],这时将rehashidx置为-1,表示rehash完成。 - 将
ht[1]赋值给ht[0],回收ht[0]空间。
总结
- 字典被广泛应用于实现Redis各种功能
- Redis中的字典使用hash表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用
- 哈希表采用开链方式解决键冲突
- 在对哈希表进行扩展操作时，程序将现有的键值对rehash到新哈希表中，并且这个过程并不是一次性完成的，而是渐进式完成。
4.压缩列表
压缩列表ziplist则是列表键和哈希键的底层实现,当存储的元素较少或者长度较短时候，为节约内存，则使用连续的存储空间存储元素。压缩列表是为了提高内存的使用率，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表尅包含任意多个节点，每个节点可以保存字节数组或者整数值。
其数据结构如下：
typedef struct ziplist{
//记录整个压缩列表占用的字节数
uint32_t zlbytes;
//记录压缩列表的尾节点距离起始节点字节数
uint32_t zltail;
//记录压缩列表包含节点数量
uint16_t zllen;
//存储的元素
zlentry extryX;
//压缩列表结尾特殊标记
uint8_t zlend;
} ziplist;
typedef struct zlentry {
//前一个节点字节长度
uint previous_entry_length;
//编码方式
uint encoding;
//字节数组
uint8_t contents[];
}
如下图是一个例子：
总结
- 压缩列表是一种提高内存使用效率的顺序型数据结构
- 压缩列表可以包含多个节点，每个节点保存一个字节数组或者整数
- 压缩列表被用作列表键和哈希键的底层实现之一。
5.整数集合
整数集合intset是Redis底层存储整数值的集合抽象数据结构，可以保存int16_t 、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素。其数据结构如下:
typedef struct intset{
//编码方式
uint32_t encoding;
//数组长度，即是集合元素个数
uint32_t length;
//保存整数
int8_t contents[];
} intset;
- contents是底层缓冲区实现，保存数据本身,其数据按照大小顺序排列。
- encoding编码方式，标志数据是16位、32位还是64位编码方式。
- length表示contents中存储整数的个数。
下图是一个例子:
当向集合中添加新元素，如果现有编码长度小于新元素的长度，就需要进行集合编码升级，升级分为3步:
- 根据新编码方式,计算底层数组的长度,为新的数组分配内存空间。
- 将原有数组中元素进行扩充编码方式，并放在心数组中合适位置。
- 维护新数组的有序性,并将contents指向新数组,回收旧数组。
总结
- 整数集合是集合键的底层实现之一
- 其底层实现为数组，数组以有序、无重复的方式保存几个元素
- 整数集合支持自动升级编码方式
- 整数集合不支持降级操作
6.跳跃表
在介绍跳跃表之前，先考虑一个问题？如何维护一个有序的链表？
常规的方式就是在插入一个元素时，从头遍历链表进行大小比较，选择合适的位置进行插入，其时间复杂度是O(n),那么怎么借助于链表的有序性减少比较的次数？链表的内存非连续性二分法是无法实现的，但可不可以借助于二分法思想进行关键点比较过滤掉一些无效的数值比较?这就是跳跃表的核心思想。其原理如下
跳跃表分为多个层，每个层之间是一个有序链表，上层元素有一个指针指向下层元素，查找和插入操作自上而下遍历，同一层自左向右遍历。
对于一个有序链表1->3->5->7->9->11,按照上面的想法，我们是否可以借助索引的思想，将链表中一些关键的节点提取出来(此处我们提取出1、5、9)作为一个有序链表，当我们插入元素8时，只需要比较节点5、9之间的元素就可以确定元素8的插入位置，从而省略1-5和9-∞的元素的比较。
更近一步，我们是不是可以将链表1->5->9继续提出关键节点作为更上一层，从而进一步缩减比较次数。(理论上最上一次只有2个节点)
对上上述链表，其效果不是很明显，如果对于10w甚至更长的链表其比较次数将大大降低。
但是同时从上述结构可以看出，跳跃链表是用空间获取时间。
redis中跳跃表结构如下
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
// member 对象
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;
总结
- 跳跃表是有序集合底层实现之一
- 跳跃表中买多个节点可以包含相同的分值，但是每个节点的成员对象必须是唯一的
本文以上主要介绍Redis中常用的5中底层数据结构，其作为五大对象Object的底层实现基本数据结构,理解其原理很容易理解Object实现原理以及常用命令的实现原理。接下来文章将介绍五大对象string、set、sortedset、hash、list、skiplist的实现原理。
参考文献《Redis设计与实现(第二版)》
