《Redis设计与实现》简读
《Redis设计与实现》核心要点简读
一、数据结构与对象
1. 简单动态字符串(SDS)
-
优势:
- 记录字符串长度,获取长度复杂度O(1)
- 记录已分配内存空间,避免缓冲区溢出
- 空间预分配和惰性释放机制
- 二进制安全,不以
\0判断结束 - 兼容C字符串函数(以
\0结尾)
-
空间预分配与惰性释放:
- 增长时:长度<1M分配2倍空间;长度≥1M分配+1M空间
- 缩短时:不立即释放多余内存,记录在
free属性中 - 最佳实践:修改相同键的值时,尽量保持长度相近,避免频繁内存重分配
2. 链表
- 特点:
- 双向链表,获取前后节点复杂度O(1)
- 无环,头尾指针指向NULL
- 记录头尾节点,获取头尾节点复杂度O(1)
- 记录链表长度,获取长度复杂度O(1)
- 可存储多种类型数据
3. 字典
-
实现机制:
- 链地址法解决哈希冲突(相同索引时添加到链表头)
- 两个哈希表
ht[0]和ht[1](ht[1]用于rehash) - 渐进式rehash:逐步将
ht[0]数据迁移到ht[1] - 负载因子 = 已保存节点数/哈希表大小
-
rehash步骤:
- 扩展(无BGSAVE/BGREWRITEAOF且负载≥1,或有BGSAVE/BGREWRITEAOF且负载≥5):为
ht[1]分配≥当前节点数×2的内存 - 收缩(负载<0.1):为
ht[1]分配≥当前节点数的内存 - 逐步迁移
ht[0]到ht[1] - 释放
ht[0],ht[1]变为ht[0]
- 扩展(无BGSAVE/BGREWRITEAOF且负载≥1,或有BGSAVE/BGREWRITEAOF且负载≥5):为
Redis哈希算法:MurmurHash2
4. 跳跃表
- 用途:有序集合底层实现之一
- 特点:
- 节点按分值排序,分值相同时按对象大小排序
- 每个节点可保存字节数组或整数值
5. 整数集合
-
支持类型:
int16_t(-32768至32767)int32_t(-2147483648至2147483647)int64_t(-9223372036854775808至9223372036854775807)
-
升级机制:
- 根据新元素类型扩展底层数组
- 转换现有元素类型并保持有序
- 添加新元素(小于所有元素放索引0,大于所有元素放索引length-1)
-
最佳实践:向同一整数集合添加相同类型的整数,避免升级操作
6. 压缩链表
- 用途:列表键和哈希键的底层实现之一
- 特点:添加/删除节点可能造成连锁更新,最坏时间复杂度O(N²)
7. 对象与编码
Redis支持5种对象类型,每种类型有不同编码方式:
| 类型 | 编码 | 说明 |
|---|---|---|
| REDIS_STRING | REDIS_ENCODING_INT | 整数值实现的字符串对象 |
| REDIS_STRING | REDIS_ENCODING_EMBSTR | 小于32字节字符串的简单动态字符串实现 |
| REDIS_STRING | REDIS_ENCODING_RAW | 大于32字节字符串的简单动态字符串实现 |
| REDIS_LIST | REDIS_ENCODING_ZIPLIST | 元素长度<64字节且数量<513(默认) |
| REDIS_LIST | REDIS_ENCODING_LINKEDLIST | 双向链表实现 |
| REDIS_HASH | REDIS_ENCODING_ZIPLIST | 元素长度<64字节且数量<513(默认) |
| REDIS_HASH | REDIS_ENCODING_HT | 字典实现 |
| REDIS_SET | REDIS_ENCODING_INTSET | 整数值且数量<513(默认) |
| REDIS_SET | REDIS_ENCODING_HT | 字典实现 |
| REDIS_ZSET | REDIS_ENCODING_ZIPLIST | 元素长度<64字节且数量<128(默认) |
| REDIS_ZSET | REDIS_ENCODING_SKIPLIST | 跳跃表+字典实现 |
查看对象编码命令: