The Design and Implementation of Redis
第二章 简单动态字符串
simple dynamic string(SDS)
O(1)时间获取长度
杜绝了缓存区溢出
空间预分配
SDS 长度小于1MB,就分配同样大小未使用空间
SDS 长度大于1MB,就分配1MB未使用空间
惰性空间释放,不立刻释放未使用内存
二进制安全,读取会和写入完全一样
兼容部分 C 字符串函数,最后以
0
结尾
第三章 Redis 的链表
广泛用于实现 Redis 的各种功能,比如列表键、发布与订阅、慢查询、监视器等
双端
无环,表头的 prev 和表尾的 next 都是 NULL
带表头指针和表尾指针,可从头也可从尾遍历
带长度计数器
多态,用
void*
来保存节点值,可保存各种类型
第四章 Redis 的字典
哈希表的数据结构
typedef struct dictht {
// 哈希表数组
dictEntry ** table;
// 哈希表大小
unsigned long size;
// 哈希表大小的掩码,与运算可直接获得索引
// 值是 size-1
unsigned long sizemask;
// 已有节点数量
unsigned long used;
} dictht;
typedef struct dictEntry {
// 键
void *key;
//值
union{
void* val;
uint64_t u64;
int64_t s64;
} v;
// 指向下一个节点,形成链表,以处理冲突(collision)
struct dictEntry *next;
} dictEntry;
字典的数据结构
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据,作为参数传给某些需要的函数
void *private;
// 哈希表,用两个,以便 rehash
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行中时,值为-1
int terhashidx;
} 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;
哈希算法
// 使用字典设置的哈希函数,计算 key 的哈希值
hash = dict->type->hashFunction(key);
// 根据 sizemask 计算索引
// 根据情况不同,ht[x] 可以是 ht[0] 或 ht[1]
index = hash & dict->ht[x].sizemask;
Redis 使用 MurmurHash
解决键冲突
每个
dictEntry
实际上是一个链表
rehash
随着操作不断执行,哈希表保存的键值对会逐渐增多或减少,为了让哈希表的负载银子(load factor)维持在一个合理范围内,当哈希表保存的键值对数量太多或太少时,程序需要对哈希表进行扩展或收缩
从
ht[0]
rehash 到ht[1]
步骤如下:分配空间:如果是扩展,那么
ht[1]
的大小是第一个大于等于ht[0].used*2
的2的n次方幂;如果是收缩,那么ht[1]的大小是第一个大于等于ht[0].used的2的n次方幂将保存在 ht[0] 中的所有键值对rehash到ht[1]上面,重新计算哈希值和索引值,放到ht[1]上
将ht[0]全部迁移到ht[1]后,释放ht[0],将ht[1]设置为ht[0],并在ht[1]上shel创建一个空的哈希表
以下任意两个条件满足时,程序会自动开始进行扩展操作
服务器目前没有执行 BGSAVE 命令或 BGREWRITEAOF 命令,并且哈希表的负载因子大于等于1
服务其目前执行 BGSAVE 命令或 BGREWRITEAOF 命令,并且哈希表的负载因子大于等于5
负载因子:
load_factor = ht[0].used / ht[0].size
负载因子小于0.1时,程序自动开始进行哈希表执行收缩操作
渐进式rehash
需要 rehash 的值可能非常多,一次性全部rehash可能会导致服务器一段时间内停止工作
渐进式 rehash 的步骤
为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表
在字典中维持一个索引计数器变量rehashidx,设值为0,表示rehash开始
rehash期间,每次对字典进行添加、删除、查找或更新操作时,程序还会顺带将ht[0]哈希表在rehashidx上的所有键值对rehash到ht[1],完成后将rehashidx加1
随着字典操作不断进行,在某个时间点ht[0]会全部rehash到ht[1],程序将rehashidx设置为-1,表示已完成
好处是分而治之,避免了集中式rehash带来的庞大计算量
渐进式rehash期间,新添加的键值对都会被保存到ht[1]上,删除、查找、更新操作会在两个哈希表上进行
第五章 跳跃表 skiplist
支持平均O(logN),最坏O(N)的查找
实现比平衡树简单的多,所以不少程序使用跳跃树代替平衡树
Redis 使用跳跃表作为有序集合键的底层实现之以
只有两个地方用到:一个是实现有序集合键,另一个是在集群节点中用作内部数据结构
跳跃表的实现
header : 头节点
tail : 尾节点
level : 记录目前跳跃内,层数最大的那个节点的层数(表头节点的层数不算在内)
length : 记录跳跃表的长度,即跳跃表目前包含的几点数量(表头节点不算在内)
typedef struct zskiplistNode {
// 后退指针,与层无关,始终指向前一个节点
struct zskiplistNode *backward;
// 分值
double score;
//成员对象
robj *obj;
//层
struct zskiplistLevel {
//前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
每一个节点的层高是1-32之间的随机数
跳跃表的结构如下
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplist *headr, *tail;
// 表中节点数量
unsigned long length;
// 表中最大层数的节点的层数
int level;
};
第六章 整数集合(intset)
有序且不重复
typedef struct intset {
// 编码方式,如int16,int32,int64
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组,取决于编码方式
int8_t contents[];
};
整数升级
16位升级为32位,先升级空间,复制值,再改变编码方式
每次添加新元素都可能会引起升级
整数降级
整数不会被自动降级
第七章 压缩列表(ziplist)
每个列表项要么是小整数值,要么是长度比较短的字符串
属性 | 类型 | 长度 | 用途 |
---|---|---|---|
zlbytes | uint32_t | 4字节 | 记录压缩列表的长度,用于重新分配内存或计算zlend |
zltail | uint32_t | 4字节 | 记录尾节点的偏移,以快速取得尾节点 |
zllen | uint16_t | 2字节 | 记录节点的数量 |
entryX | 列表节点 | 不定 | 节点,长度取决于内容 |
zlend | uint_8 | 1字节 | 0xFF,标记压缩列表的结束 |
节点
每个节点由
previous_entry_length
、encoding
、content
三部分组成previous_entry_length
的长度可以是1个字节或5个字节。前一节点的长度小于254,就只用1个字节;前一节点的长度大于等于254时,占5个字节,第一个字节是0xFE,后四个字节是前一个节点的长度利用
previous_entry_length
可实现从尾到头的遍历encoding
编码 | 编码长度 | content属性的值 |
---|---|---|
00bbbbbb | 1字节 | 长度小于等于63的字节数组 |
01bbbbbb bbbbbbbb | 2字节 | 长度小于等于16383的字节数组 |
10000000 4字节长度 | 5字节 | 长度小于等于4294967295的字节数组 |
11000000 | 1字节 | int16_t |
11010000 | 1字节 | int32_t |
11100000 | 1字节 | int64_t |
11110000 | 1字节 | 24位有符号整数 |
11111110 | 1字节 | int_8 |
1111xxxx | 1字节 | 无content,已经保存了介于0-12之间的值 |
连锁更新
某个节点的插入,使其长度超过了254,需要扩充
previous_entry_length
到5个字节,导致之后的节点都发生了这样的扩充删除节点也可能会导致后方节点的
previous_entry_length
扩充尽管连锁更新的复杂度很高,但造成性能问题的几率很低,需要连续的长度在250-253字节的节点
第八章 对象
可以针对不同的使用场景为对象设置多种不同的数据结构实现,从而优化在不同场景下的效率
Redis 的对象实现了基于引用计数的内存共享和内存回收机制
Redis 的对象带有访问时间记录信息,可记录数据库键的空转时长,在服务器启用 maxmemory 时,空转时长较大的键可能会被优先删除
对象的类型与编码
typedef struct redisObject {
// 类型
unsigned type:4;
// 编码
unsigned encoding:4;
// 指向底层实现数据结构的指针
void *ptr;
// ...
} robj;
对象 | 对象type属性的值 | TYPE命令的输出 |
---|---|---|
字符串对象 | REDIS_STRING | "string" |
列表对象 | REDIS_LIST | "list" |
哈希对象 | REDIS_HASH | "hash" |
集合对象 | REDIS_SET | "set" |
有序集合对象 | REDIS_ZSET | "zset" |
底层实现
类型 | 编码 | 对象 |
---|---|---|
REDIS_STRING | REDIS_ENCODING_INT | 使用整数值实现的字符串对象 |
REDIS_STRING | REDIS_ENCODING_EMBSTR | 使用embstr编码的简单动态字符串 |
REDIS_STRING | REDIS_ENCODING_RAW | 简单动态字符串 |
REDIS_LIST | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的列表对象 |
REDIS_LIST | REDIS_ENCODING_LINKEDLIST | 使用双端链表实现的列表对象 |
REDIS_HASH | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的哈希对象 |
REDIS_HASH | REDIS_ENCODING_HT | 使用字典实现的哈希对象 |
REDIS_SET | REDIS_INTSET | 使用整数集合实现的集合对象 |
REDIS_SET | REDIS_ENCODING_HT | 使用字典实现的集合对象 |
REDIS_ZSET | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的有序集合对象 |
REDIS_ZSET | REDIS_ENCODING_SKIPLIST | 使用跳跃表和字典实现的有序集合对象 |