【2022.5.28】Redis源码

字符串源码

字符串由两个部分组成，一个是redis对象通用结构体 RedisObject ，一个是字符串特有的 SDS(Simple Dynamic String) 简单动态字符串结构体

1
2
3
4
5
6
7
8
9

//RedisObject 16Bytes
struct RedisObject{
	int4 type; //对象类型，如字符串 4bits
	int4 encoding;  //编码类型  4bits
	int24 lru;   //LRU信息，用于淘汰key 24bits
	int32 refcount;   //引用计数器 4Bytes
  void *ptr;    //指向实际存储位置的指针，也就是指向SDS的指针 根据系统位数不同64位系统是 8Bytes

}

1
2
3
4
5
6
7

//SDS >=3Bytes
struct SDS<T>{
	T capacity;  //分配的数组的长度，content的长度
	T len;  //实际存储的字符串的长度
	byte flags;  //标志位
	byte[] contents; //内容数组
}

字符串的编码分为两种： embstr 和 raw

embstr

使用 malloc 方法申请空间， jemalloc 分配空间大小是2/4/8/16/32/64字节，因为embstr最小需要19Bytes，所以给 embstr 最小分配32字节空间，稍微长一些就是64字节空间，Redis的逻辑是当embstr空间大于64字节时，转为 raw 存储

因为字符串为了便于使用 glibc 函数处理，以及便于调试打印输出，所以在实际存储中，会在字符串数组末尾加入 NULL 字符，占用1Byte

embstr编码下，字符串的最大字符数是：64-19-1=44Bytes

raw

与embstr不同，embstr是调用一次malloc函数申请空间，raw是调用两次malloc函数，申请两块不连续的空间，使用 RedisObject 中的 *ptr 指针进行指向SDS，在字符串大于44Bytes时会使用raw格式存储

扩容策略

当字符串小于1MB时，扩容contents数组时加倍扩容，而大于1MB时，每次扩容多分配1MB空间

字典结构

字典结构应用到的地方由很多，比如redis作为远程字典服务器本身就是一个由key和value大字典，而在zset集合中score和value值也是一个字典，以及key的过期时间存储也是由字典实现。

1
2
3
4
5
6
7
8
9
10
11
12

//redisDB 
struct RedisDb{
	dict* dict;  //所有的key key->value
	dict* expires; //所有的key的过期时间  key->long(timestamp)
	...
}

//zset
struct zset {
	dict *dict;  //所有value value->score
	zskiplist *zsl;  //跳表
}

字典结构中主要是有两个hashtable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//dict
struct dict {
	...
	dictht ht[2];  //两个hashtable，用于在扩容时作为渐进式搬运的临时ht
}

//dictht
struct dict {
	dictEntry** table;   //指向数组的指针
	long size;  //第一维数组的长度
  long used;  //hash表中的元素个数
  ...  
}

//dictEntry
struct dictEntry {
	void* key;
	void* val;
	dictEntry* next;  //指向下一个entry的指针
}

hash中的关键逻辑

• 渐进式rehash：因为rehash是一个 O(n) 时间复杂度的操作，redis在rehash中维护两个hashtable，一个旧一个新，新增的entry会新增到新hash中，并且旧hash会逐渐在hset、hdel逻辑中主动搬运，如果没有这些操作，也会在定时任务中进行搬运。
• hash函数会保证尽可能的使得元素在hashtable中均匀分布，但是如果有针对性的hash攻击，也会使得查找退化到O(n)
• 扩容逻辑：hash元素总数等于数组长度时开始扩容，尽量保证查找效率为 O(1) ，扩容为原数组大小的两倍，但如果在 bgsave 过程中，则会推延扩容直到元素总数达到数组长度的5倍，就会触发强制扩容
• 缩容逻辑：hash元素总数小于数组长度的10%时，触发缩容，缩容不会考虑 bgsave

压缩列表（ziplist）

有序集合 zset 在元素较少 （<128）&（len<64） 时，会使用 ziplist ，这个数据结构没有空隙，所有元素都是紧挨着存放。

查找时间复杂度： O(n)

插入时间复杂度： O(n)

压缩链表结构

1
2
3
4
5
6
7

struct ziplist {
	int32 zlbytes; //整个列表占用的字节数
	int32 zltail_offset;  //最后一个元素距离压缩列表起始位置的偏移量，用于定位最后一个节点
	int16 zllength;  //元素个数
  T[] entries; //元素内容数组
  int8 zlend;  //标记压缩列表的结束，魔法值，为0xFF
}

元素结构

1
2
3
4
5

struct entry {
	int<var> prevlen;  //前一个entry的字节长度
  int<var> encoding;  //元素类型编码
  optional byte[] content; //元素内容
}

ziplist关键逻辑：

• 级联更新：元素结构体中的prevlen是会根据前一个元素的改变实时更新的，会触发级联更新
• 元素结构体中的prevlen在字符串小于 254 时，使用一个字节，超出则使用5个字节
• encoding设计十分复杂，可以表示数据类型、数据长度，甚至可以直接存储极小的整数（0-12）
• 新增元素时需要重新分配内存

intset小整数集合

在 set 集合元素都是整数且元素较少 <512 时，会使用 intset 进行存储， intset 支持16、32、64位整数，结构为紧凑型数组。

1
2
3
4
5

struct intset<T> {
	int32 encoding; //决定整数是多少位的，16/32/64
  int32 length;  //元素个数
  int<T> contents; //整数数组
}

快速列表

快速列表结合了 ziplist 和 linkedlist ，在元素少时，只使用 ziplist ，元素较多时，把 ziplist 使用 双向循环指针 链接起来，成为一个由 ziplist 作为元素的 linkedlist 。

关键逻辑：

• ziplist节点本身也是可以压缩的，使用的是 LZF算法 压缩，可以选择压缩深度，所谓的压缩深度就是从首尾算起多少个元素可以不压缩，深度为0就是不压缩，深度大于0时越大压缩的ziplist越少。
• 一个ziplist存储有空间限制，可以通过 list-max-ziplist-size 设定，默认为8KB

跳跃列表

数据结构 zset 是复合结构，其中的结构包含了一个 hash字典 和 一个 skiplist跳跃列表 ，其中 skiplist 是比较复杂的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//zslnode 跳表节点
struct zslnode {
	string value;
	double score;
  zslnode*[] forwards; //多层链接指针
	zslnode* backward; //回溯指针
}

//zsl 跳表
struct zsl {
	zslnode* header; //跳跃列表表头指针(kv head)
	int maxLevel;  //跳表最高层
  map<string, zslnode*> ht; //hash结构键值对
}

随机层数

对于每一个新插入的元素，会调用一个随机算法来计算他最高处于哪个层，理论上每升一层的概率是50%，但是redis为了限制层高，把这个概率设置为了25%，也就是实际上redis中的跳表比理论的更矮。

插入过程

1. 首先找到搜索路径
2. 创建新节点，随机获取当前节点的层高
3. 把节点的指针指向到对应的前后节点

更新过程

1. 找到对应的节点，如果需要更新，就删除
2. 插入新节点

删除过程

1. 获取节点
2. 删除节点

元素排名

rank 是通过存储在 forward指针中的span（跨度）属性计算的，具体是在获取节点时，获取到搜索路径，将搜索路径中的span相加，就获得了排名了