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 的字典
哈希表的数据结构
```c 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]` 步骤如下：
1. 分配空间：如果是扩展，那么`ht[1]`的大小是第一个大于等于`ht[0].used\*2`的2的n次方幂；如果是收缩，那么ht[1]的大小是第一个大于等于ht[0].used的2的n次方幂
2. 将保存在 ht[0] 中的所有键值对rehash到ht[1]上面，重新计算哈希值和索引值，放到ht[1]上
3. 将ht[0]全部迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]上shel创建一个空的哈希表
- 以下任意两个条件满足时，程序会自动开始进行扩展操作
1. 服务器目前没有执行 *BGSAVE* 命令或 *BGREWRITEAOF* 命令，并且哈希表的负载因子大于等于1
2. 服务其目前执行 *BGSAVE* 命令或 *BGREWRITEAOF* 命令，并且哈希表的负载因子大于等于5
- 负载因子: `load_factor = ht[0].used / ht[0].size`
- 负载因子小于0.1时，程序自动开始进行哈希表执行收缩操作
### 渐进式rehash
- 需要 rehash 的值可能非常多，一次性全部rehash可能会导致服务器一段时间内停止工作
- 渐进式 rehash 的步骤
1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
2. 在字典中维持一个索引计数器变量rehashidx，设值为0，表示rehash开始
3. rehash期间，每次对字典进行添加、删除、查找或更新操作时，程序还会顺带将ht[0]哈希表在rehashidx上的所有键值对rehash到ht[1]，完成后将rehashidx加1
4. 随着字典操作不断进行，在某个时间点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
使用跳跃表和字典实现的有序集合对象
Last updated
Was this helpful?