redis设计与实现之数据结构篇

简单动态字符串(sds)

从数据结构看sds为buf分配了5个字符和0个free空间,\0是不计算在len内,但是会分配额外的1字节空间,下面讲讲这样设计的好处

  • 数据结构中存了len字段,可以O(1)常数时间获取字符串长度
  • 每次插入元素前都会检查sds空间是否足够,若不满足做适当的扩充,可以避免缓冲区溢出的可能性(C语言中每次插入或者删除字符的时候都要重新分配新的内存来保存新值,是一个很耗时的操作 )
  • sds采用空间预分配和惰性空间释放两种策略减少了内存重分配的次数,看到free字段就知道这是一个额外的空间来在某种程度上减少了重分配的次数,具体如下

    1
    2
    3
    如现有空间足够存放修改后内容,则不进行扩展,直接插入。
    如现有空间不足以存放修改后内容,且修改后sds的len小于1M,则扩展后len=free,比如修改后空间为15 byte,则分配的空间是31:15+15+1byte.
    如现有空间不足以存放修改后内容,且修改后sds的len大于1M,则分配1M的使用空间,则新的空间为20M+1M+1byte
  • 惰性空间释放:用于优化SDS缩减操作.当api对sds进行缩短操作后,程序不会释放缩短后空余出的空间,而是使用free属性把他们记录下来,当我们插入的时候就可以减少内存重分配了(不需要担心,我们以后不添加内容时,造成的内存泄露,因为sds提供了释放空间的API)

  • 二进制安全,不像C语言,C字符串的字符必须某种编码(比如ASCII),并且除末尾外,其余地方不能出现空字符串\0,否则会被提前结束,(\0是c字符串的结束标识符),比如acvf\0sdsdsd\0,只能识别到acvf,而sds是根据len属性来判断字符串的结束,所以不存在是否有\0
  • 由于SDS的buf数组以\0结尾,符合c字符串特征,因此,它可以使用C字符串的一些api

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct listNode{
struct listNode *prev//前置节点
struct listNode *next//后置节点
void *value //节点值
}listNode;
struct list{
listNode *head;//表头节点
listNode *tail;//表尾节点
unsigned long len;//常数时间获取链表长度
void *(*dup)(void *ptr);//节点值复制函数
void *(*free)(void *ptr);//节点值释放函数
void *(*match)(void *ptr,void *key);//节点值对比函数
}list;

链表的实现特性总结如下

  • 双端:每个节点都有prev和next,获取某个节点的前置节点和后置节点的复杂度都是O(1)
  • 无环: 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL , 对链表的访问以 NULL 为终点
  • 带表头指针和表尾指针: 通过 list 结构的 head 指针和 tail 指针, 程序获取链表的表头节点和表尾节点的复杂度为 O(1)
  • 带链表长度计数器: 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数, 程序获取链表中节点数量的复杂度为 O(1)
  • 多态: 链表节点使用 void* 指针来保存节点值, 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数, 所以链表可以用于保存各种不同类型的值

字典

字典又称为符号表、关联数组、映射,是一种用于保存键值对的抽象数据结构,下面看某结构实现

哈希表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictht {
dictEntry **table;//哈希表数组
unsigned long size;//哈希表大小
unsigned long sizemask;//哈希表大小掩码,用于计算索引值,总是等于 size - 1
unsigned long used;//该哈希表已有节点的数量
} dictht;
typedef struct dictEntry {
void *key;//键
union {
void *val;
uint64_t u64;
int64_t s64;
} v;//值
struct dictEntry *next;//指向下个哈希表节点,形成链表
} dictEntry;

字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct dict {
dictType *type;// 类型特定函数,指向 dictType 结构的指针,每个dictType结构保存了一簇用于操作特定类型键值对的函数,Redis 会为用途不同的字典设置不同的类型特定函数。
void *privdata;//私有数据,保存了需要传给那些类型特定函数的可选参数
dictht ht[2];//哈希表,是一个包含两个项的数组,数组中的每个项都是一个dictht哈希表, 一般情况下, 字典只使用ht[0]哈希表, ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用
int rehashidx; //rehash索引,当rehash不在进行时,值为-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;

下图展示一个没有进行rehash的字典

哈希算法

当要将一个新的键值对添加到字典里面时, 程序需要先根据键值对的键计算出哈希值和索引值, 然后再根据索引值, 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面,Redis 计算哈希值和索引值的方法如下

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

下面是一个空字典的结构图


如上图,如果我们要将一个键值对 k0 和 v0 添加到字典里面, 那么程序会先使用语句
1
2
hash = dict->type->hashFunction(k0);//计算键 k0 的哈希值,假设计算得出的哈希值为8
index = hash & dict->ht[0].sizemask = 8 & 3 = 0;//计算出键k0的索引值0,这表示包含键值对k0和v0的节点应该被放置到哈希表数组的索引0位置上

解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时, 我们称这些键发生了冲突(collision),Redis 的哈希表使用链地址法(separate chaining)来解决键冲突: 每个哈希表节点都有一个 next 指针, 多个哈希表节点可以用 next 指针构成一个单向链表, 被分配到同一个索引上的多个节点可以用这个单向链表连接起来, 这就解决了键冲突的问题,如图


k1和k2键冲突的话,直接用单向链表连接起来,并且最新添加的放在表头(原因:dictEntry 节点组成的链表没有指向链表表尾的指针, 所以为了速度考虑, 程序总是将新节点添加到链表的表头位置(复杂度为 O(1)), 排在其他已有节点的前面)

rehash

随着操作的不断执行, 哈希表保存的键值对会逐渐地增多或者减少, 为了让哈希表的负载因子(load factor)维持在一个合理的范围之内, 当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩, Redis 对字典的哈希表执行 rehash 的步骤如下

  • 为字典的 ht[1] 哈希表分配空间, 这个哈希表的空间大小取决于要执行的操作, 以及 ht[0] 当前包含的键值对数量 (也即是 ht[0].used 属性的值)

    1
    2
    如果执行的是扩展操作, 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n (2 的 n 次方幂)
    如果执行的是收缩操作, 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n
  • 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面: rehash 指的是重新计算键的哈希值和索引值, 然后将键值对放置到 ht[1] 哈希表的指定位置上

  • 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 (ht[0] 变为空表), 释放 ht[0] , 将 ht[1] 设置为 ht[0] , 并在 ht[1] 新创建一个空白哈希表, 为下一次 rehash 做准备
  • 哈希表的扩展与收缩,当以下条件中的任意一个被满足时, 程序会自动开始对哈希表执行扩展操作
    1
    2
    3
    4
    服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 1
    服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 5
    当哈希表的负载因子小于 0.1 时, 程序自动开始对哈希表执行收缩操作
    load_factor = ht[0].used / ht[0].size;//负载因子 = 哈希表已保存节点数量 / 哈希表大小

根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行, 服务器执行扩展操作所需的负载因子并不相同, 这是因为在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中, Redis 需要创建当前服务器进程的子进程, 而大多数操作系统都采用写时复制(copy-on-write)技术来优化子进程的使用效率, 所以在子进程存在期间, 服务器会提高执行扩展操作所需的负载因子, 从而尽可能地避免在子进程存在期间进行哈希表扩展操作, 这可以避免不必要的内存写入操作, 最大限度地节约内存

渐进式rehash

rehash 动作并不是一次性、集中式地完成的, 而是分多次、渐进式地完成的,原因在于, 如果 ht[0] 里只保存着四个键值对, 那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht[1] ; 但是, 如果哈希表里保存的键值对数量不是四个, 而是四百万、四千万甚至四亿个键值对, 那么要一次性将这些键值对全部 rehash 到 ht[1] 的话, 庞大的计算量可能会导致服务器在一段时间内停止服务,所以哈希表渐进式 rehash 的详细步骤

1
2
3
4
为 ht[1] 分配空间, 让字典同时持有 ht[0] 和 ht[1] 两个哈希表
在字典中维持一个索引计数器变量 rehashidx , 并将它的值设置为 0 , 表示 rehash 工作正式开始
在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作完成之后, 程序将 rehashidx 属性的值增一
随着字典操作的不断执行, 最终在某个时间点上, ht[0] 的所有键值对都会被 rehash 至 ht[1] , 这时程序将 rehashidx 属性的值设为 -1 , 表示 rehash 操作已完成

渐进式 rehash 的好处在于它采取分而治之的方式, 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上, 从而避免了集中式 rehash 而带来的庞大计算量
因为在进行渐进式 rehash 的过程中, 字典会同时使用 ht[0] 和 ht[1] 两个哈希表, 所以在渐进式 rehash 进行期间, 字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行: 比如说, 要在字典里面查找一个键的话, 程序会先在 ht[0] 里面进行查找, 如果没找到的话, 就会继续到 ht[1] 里面进行查找,另外, 在渐进式 rehash 执行期间, 新添加到字典的键值对一律会被保存到 ht[1] 里面, 而 ht[0] 则不再进行任何添加操作: 这一措施保证了 ht[0] 包含的键值对数量会只减不增, 并随着 rehash 操作的执行而最终变成空表

跳跃表

跳跃表是一种有序数据结构,通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的,支持O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点,另外可以和平衡树相媲美,且实现起来更简单,redis中只有 实现有序集合键、集群节点用作内部数据结构 来个地方,再没有其他用途

跳跃表的实现

位于图最左为zskiplist结构

  • header :指向跳跃表的表头节点
  • tail :指向跳跃表的表尾节点
  • level :记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)
  • length :记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)

位于 zskiplist 结构右方的是四个 zskiplistNode 结构, 该结构包含以下属性

  • 层(level):节点中用 L1 、 L2 、 L3 等字样标记节点的各个层, L1 代表第一层, L2 代表第二层,以此类推。每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行
  • 后退(backward)指针:节点中用 BW 字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用
  • 分值(score):各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列
  • 成员对象(obj):各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象

跳跃表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct zskiplistNode {
struct zskiplistNode *backward;//后退指针
double score;//分值
robj *obj;//成员对象
struct zskiplistLevel {
struct zskiplistNode *forward;//前进指针
unsigned int span;//跨度
} level[];//层
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;//表头节点和表尾节点,header 和 tail 指针分别指向跳跃表的表头和表尾节点, 通过这两个指针, 程序定位表头节点和表尾节点的复杂度为 O(1)
unsigned long length;//表中节点的数量,通过使用 length 属性来记录节点的数量, 程序可以在 O(1) 复杂度内返回跳跃表的长度
int level;//表中层数最大的节点的层数,level 属性则用于在 O(1) 复杂度内获取跳跃表中层高最大的那个节点的层数量, 注意表头节点的层高并不计算在内
} zskiplist;

跳跃表节点的 level 数组可以包含多个元素, 每个元素都包含一个指向其他节点的指针, 程序可以通过这些层来加快访问其他节点的速度, 一般来说, 层的数量越多, 访问其他节点的速度就越快
每次创建一个新跳跃表节点的时候, 程序都根据幂次定律 (power law,越大的数出现的概率越小) 随机生成一个介于 1 和 32 之间的值作为 level 数组的大小, 这个大小就是层的“高度”
每个层都有一个指向表尾方向的前进指针(level[i].forward 属性), 用于从表头向表尾方向访问节点
层的跨度(level[i].span 属性)用于记录两个节点之间的距离

  • 两个节点之间的跨度越大, 它们相距得就越远
  • 指向 NULL 的所有前进指针的跨度都为 0 , 因为它们没有连向任何节点

节点的后退指针(backward 属性)用于从表尾向表头方向访问节点: 跟可以一次跳过多个节点的前进指针不同, 因为每个节点只有一个后退指针, 所以每次只能后退至前一个节点
节点的分值(score 属性)是一个 double 类型的浮点数, 跳跃表中的所有节点都按分值从小到大来排序
节点的成员对象(obj 属性)是一个指针, 它指向一个字符串对象, 而字符串对象则保存着一个 SDS 值
为啥 redis 使用跳表(skiplist)而不是使用 red-black?

整数集合

整数集合的实现

整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,redis就会使用此结构实现,用于保存整数值的集合抽象数据结构, 它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值, 并且保证集合中不会出现重复元素

1
2
3
4
5
typedef struct intset {
uint32_t encoding;//编码方式
uint32_t length;//集合包含的元素数量
int8_t contents[];//保存元素的数组,整数集合的底层实现,整数集合的每个元素都是 contents 数组的一个数组项(item), 各个项在数组中按值的大小从小到大有序地排列, 并且数组中不包含任何重复项
} intset;

对于encoding,有如下解释

  • 如果 encoding 属性的值为 INTSET_ENC_INT16 , 那么 contents 就是一个 int16_t 类型的数组, 数组里的每个项都是一个 int16_t 类型的整数值 (最小值为 -32,768 ,最大值为 32,767 )
  • 如果 encoding 属性的值为 INTSET_ENC_INT32 , 那么 contents 就是一个 int32_t 类型的数组, 数组里的每个项都是一个 int32_t 类型的整数值 (最小值为 -2,147,483,648 ,最大值为 2,147,483,647 )
  • 如果 encoding 属性的值为 INTSET_ENC_INT64 , 那么 contents 就是一个 int64_t 类型的数组, 数组里的每个项都是一个 int64_t 类型的整数值 (最小值为 -9,223,372,036,854,775,808 ,最大值为 9,223,372,036,854,775,807 )
    如上图,展示了另一个整数集合示例
  • encoding 属性的值为 INTSET_ENC_INT16 , 表示整数集合的底层实现为 int16_t 类型的数组, 而集合保存的都是 int16_t 类型的整数值
  • length 属性的值为 5 , 表示整数集合包含五个元素
  • contents 数组按从小到大的顺序保存着集合中的五个元素
  • 因为每个集合元素都是 int16_t 类型的整数值, 所以 contents 数组的大小等于 sizeof(int16_t) 5 = 16 5 = 80 位

    升级

    每当我们要将一个新元素添加到整数集合里面, 并且新元素的类型比整数集合现有所有元素的类型都要长时, 整数集合需要先进行升级(upgrade), 然后才能将新元素添加到整数集合里面,升级整数集合并添加新元素共分为三步进行
  • 根据新元素的类型, 扩展整数集合底层数组的空间大小, 并为新元素分配空间
  • 将底层数组现有的所有元素都转换成与新元素相同的类型, 并将类型转换后的元素放置到正确的位上, 而且在放置元素的过程中, 需要继续维持底层数组的有序性质不变
  • 将新元素添加到底层数组里面

升级之后新元素的摆放位置,因为引发升级的新元素的长度总是比整数集合现有的所有元素的长度都大,所以这个新元素的值要么就大于所有现有元素,要么就小于所有现有元素

  • 在新元素小于所有现有元素的情况下,新元素会被放置在底层数组的最开头(index=0)
  • 在新元素大于所有现有元素的情况下,新元素会被放置在底层数组的最末尾(index=length-1)

降级

整数集合不支持降级操作, 一旦对数组进行了升级, 编码就会一直保持升级后的状态

压缩列表

压缩列表(ziplist)是列表键和哈希键的底层实现之一,当一个列表键只包含少量的列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,redis就会使用压缩列表来做列表键的底层实现

压缩列表的构成

压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构


结构如上图

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值, 其中, 字节数组可以是以下三种长度的其中一种

  • 长度小于等于 63 (2^{6}-1)字节的字节数组
  • 长度小于等于 16383 (2^{14}-1) 字节的字节数组
  • 长度小于等于 4294967295 (2^{32}-1)字节的字节数组

而整数值则可以是以下六种长度的其中一种

  • 4 位长,介于 0 至 12 之间的无符号整数
  • 1 字节长的有符号整数
  • 3 字节长的有符号整数
  • int16_t 类型整数
  • int32_t 类型整数
  • int64_t 类型整数

每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成

  • 节点的 previous_entry_length 属性以字节为单位, 记录了压缩列表中前一个节点的长度

    1
    2
    3
    如果前一节点的长度小于 254 字节, 那么 previous_entry_length 属性的长度为 1 字节: 前一节点的长度就保存在这一个字节里面
    如果前一节点的长度大于等于 254 字节, 那么 previous_entry_length 属性的长度为 5 字节: 其中属性的第一字节会被设置为 0xFE (十进制值 254), 而之后的四个字节则用于保存前一节点的长度
    压缩列表的从表尾向表头遍历操作就是使用这一原理实现的: 只要我们拥有了一个指向某个节点起始地址的指针, 那么通过这个指针以及这个节点的 previous_entry_length 属性, 程序就可以一直向前一个节点回溯, 最终到达压缩列表的表头节点
  • 节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度

    1
    2
    一字节、两字节或者五字节长, 值的最高位为 00 、 01 或者 10 的是字节数组编码: 这种编码表示节点的 content 属性保存着字节数组, 数组的长度由编码除去最高两位之后的其他位记录
    一字节长, 值的最高位以 11 开头的是整数编码: 这种编码表示节点的 content 属性保存着整数值, 整数值的类型和长度由编码除去最高两位之后的其他位记录
  • 节点的 content 属性负责保存节点的值, 节点值可以是一个字节数组或者整数, 值的类型和长度由节点的 encoding 属性决定

连锁更新

考虑一种情况就是,一个列表里全是介于某个临界值的且连续多个的节点,如果在表头插入一个大于这个节点的值,那么节点中的previous_entry_length就会发生大批量的更改来达到效果,同理,小于这个临界值也会发生同样的效果,这就叫连锁更新,因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作, 而每次空间重分配的最坏复杂度为 O(N) , 所以连锁更新的最坏复杂度为 O(N^2)
要注意的是, 尽管连锁更新的复杂度较高, 但它真正造成性能问题的几率是很低的

  • 压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点, 连锁更新才有可能被引发, 在实际中, 这种情况并不多见
  • 即使出现连锁更新, 但只要被更新的节点数量不多, 就不会对性能造成任何影响: 比如说, 对三五个节点进行连锁更新是绝对不会影响性能的

以上原因, ziplistPush 等命令的平均复杂度仅为 O(N) , 在实际中, 我们可以放心地使用这些函数, 而不必担心连锁更新会影响压缩列表的性能

至此redis的数据结构就已经完事儿了,接下来会复习redis中的二进制位数组(据我了解这个bit是一个很有实用场景的东西,尤其在节约内存方面)