Redis设计与实现-底层数据结构

正文

本文简单介绍五种不同类型的对象,剖析底层数据结构,总结优点和缺点,帮助大家理解和记忆

SDS简单动态字符串

定义如下:

1
2
3
4
5
6
7
8
9
10
11
struct sdshdr {
//记录buf数组中已使用字节的数量
//等于SDS所保存字符串的长度
int len;

//记录buf数组中未使用字节的数量
int free;

// 字节数组,用于保存字符串
char buf[];
}

C 语言使用长度未N+1的字符数组来表示长度为N的字符串,并且字符数组的最后一个元素总是’\0’。

这样的设计有几个坏处:

  1. 每次获取字符串长度的操作复杂度为O(n),通过遍历字符数组获得。
  2. 对于一些二进制数据,包含一些特殊字符,乃至于’\0’字符,无法保存
  3. 缓冲区溢出。s1为”redis”, s2为”cluster”, 二者内存相连,一旦s1发生变更为更长的字符串如’redis_test’,则会影响s2的值
  4. 每次扩展和截断字符串,都需要进行耗时严重的内存重分配操作

SDS的结构则完美避开了这些风险:

  1. 通过len记录了字符串长度,每次获取长度操作为O(1)
  2. 由于不需要根据末尾的空字符判定字符串结束,所以支持复杂的二进制数据
  3. 杜绝缓冲区溢出,在修改字符串之前会首先根据len判断空间是否足够,不够的话,进行空间大小的修改
  4. 扩展字符串采用空间预分配策略,截断字符串采用惰性空间释放策略。

空间预分配

  1. 如果对SDS进行修改时,len的值小于1MB,那么预分配和len同样大小的未使用空间,即free == len
  2. 如果len的值大于1MB,那么程序会固定分配1MB的free

惰性空间释放

  1. 当需要进行截断操作时,程序并不立即使用内存重分配收回多余内存,而是使用free来记录多出来的字节,并等待将来的使用
  2. SDS存在api可以真正删除未使用的空间

链表

redis实现的c语言本身没有内置链表,因此redis自己实现了一套。

定义如下(注意,是双向链表):

1
2
3
4
5
6
7
8
9
10
typedef struct listNode {
//前置节点
struct listNode *prev;

//后置节点
struct listNode *next;

//节点的值
void *value;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct list {
//表头节点
listNode *head;

//表尾节点
listNode *tail;

//链表节点数量
unsigned long length;

//表头值复制函数
void *(*dup)(void *ptr);

//表头值释放函数
void *(*free)(void *ptr);

//节点值对比函数
void *(*match)(void *ptr, void *key);

}

redis链表的特点:

  1. 双向
  2. 无环
  3. 带表头指针和表尾指针,获取复杂度为O(1)
  4. 带链表长度计数器,获取复杂度为O(1)

字典

redis实现的c语言本身没有内置字典(键值对),因此redis自己实现了一套。

字典使用哈希表实现。

哈希表整体实现使用拉链法实现。

每个字典包含了一个长度为2的哈希表数组ht,这个数组一般只使用ht[0]的哈希表,ht[1]只会在对ht[0]rehash时使用。

如果两个键hash之后发生冲突,则在相同的索引下,构成一个链表,新节点位于头部(因为没有指向链表尾部的指针)。

当哈希表需要扩展和收缩时,策略是:

  1. 为ht[1]分配空间,如果是扩展操作,则大小为第一个大于等于ht[0]已经使用的节点数的2倍数的2的n 次幂(有点绕,比如已经使用了5,那么应该扩展为5 * 2 = 10 < 16 即16的空间)
  2. 如果是收缩操作,则大小为第一个大于等于ht[0]已经使用的节点数的2的n 次幂(比如已经使用了5,那么应该扩展为5 < 8 即8的空间)
  3. 将ht[0]上的键值对重新rehash计算索引,转移到ht[1]上
  4. 释放ht[0], 将ht[1]设置为hr[0],并为ht[1]新创建一个空白哈希表,为下一次rehash做准备

正常情况下,扩容复杂因子为1,收缩复杂因子为5。(还有非正常情况)

在将ht[0]上的值rehash到ht[1]上时,采用渐进式rehash,策略是:

  1. 字典中维护rehashindx,默认-1
  2. 每次对字典的增删改查操作之后,都会执行一次rehash,把rehashindx对应索引的键值对,重新hash到ht[1]上,直到全部结束
  3. 好处是,避免了集中式的rehash而带来的巨大计算量,而是分多次,渐进式的完成操作。

需要注意的是,在此期间:

  1. 查找操作,会ht[0], ht[1]都查,优先查ht[0],如果找不到,才会查ht[1]
  2. 添加操作,只会添加到ht[1]
  3. 删除和修改操作则是两个哈希表都会执行

这样做保证了ht[0]只会越来越少,直至变成空表。

跳跃表

跳跃表是一种有序数据结构,平均O(logN),最坏O(N)复杂度的节点查找。

跳跃表节点结构如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct zskiplistNode {
//后退指针
struct zskiplistNode *backward;

//分值
double *score;

//成员对象
robj *obj;

//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode; *forward

//跨度
unsigned int span;
} level[];

} zskiplistNode
  1. 层。每次新创建一个新跳跃表节点的时候,会随机声称一个介于1到32之间的值作为level数组的大小
  2. 前进指针。用于从表头向表尾方向访问节点
  3. 跨度。用于记录两个跳跃表节点之前的跨度值(是否能一步到位)
  4. 后退指针。从表尾向表头方向访问
  5. 分值。跳跃表中所有节点都按照分值从小到大排序
  6. 成员对象。一个sds字符串对象

跳跃表结构如下:

1
2
3
4
5
6
7
8
9
10
11
typedef struct zskiplist {
//表头节点和表尾节点
structz skiplistNode *header, *tail;

//表中节点的数量
unsigned long length;

//表中节点层数最大的节点的层数
int level;

} zkiplist;

整数集合

如果当一个集合只包含整数值元素,并且整个集合数量不多时,redis会使用整数集合来作为集合键的底层实现

1
2
3
4
5
6
7
8
9
10
11
typedef struct intset {
//编码方式
uint32_t encoding;

//集合包含的元素数量
uint32_t length;

//保存元素的数组,从小到大有序存储
int8_t contents[];

} intset;

contents虽然声明了是int8_t,但实际真正的取值取决于encoding

当新增一个新元素时,如果该元素类型比整数集合现有所有元素类型都长,则需先进行升级操作,然后再添加

  1. 根据新元素类型,扩展整数集合底层数组的空间大小,并为新元素分配空间
  2. 将底层数组所有的元素转化成与新元素相同的类型,并将类型转化后的元素放置到正确的位上,而且再放置元素的过程中,需要继续维持底层数组的有序性质不变
  3. 将新元素添加到底层数组里

由于以上原因,向整数集合添加新元素的时间复杂度为O(N)

注意,一旦升级,编码就会一直保持升级后的状态,整数集合不支持降级。

压缩列表

压缩列表是列表键和哈希键的底层实现之一。

当一个列表键或者哈希键,值包含少量列表项,且要么为小整数,要么为长度较短的字符串,则redis会采用压缩列表作为其底层实现方式。

为什么压缩节点能够节省内存呢?

您的支持将鼓励我继续创作!