文章目录
Redis底层数据结构
- Redis底层数据结构是Redis基本数据类型和诸多功能实现的基础，字典和跳跃表是最重要的两种数据结构。
一、字典
- Redis中的字典是一种以Hash表为基础的数据结构，在Redis的很多功能实现中都使用到了字典。我们来看看Hash表和字典在Redis源码中的定义等信息。下面代码在Redis源码的src/dict.h文件中，可阅读参考文章[2]。
1.1 Hash表节点Entry
- dictEntry是hash表存储的单个元素，类似于Java的HashMap中的Entry
/*
* 哈希表节点
*/
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
1.2 Hash表dictht
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
/*
* 哈希表，使用拉链法解决哈希冲突(每个字典都使用两个哈希表，从而实现渐进式 rehash )
*/
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
1.3 字典dict
- dict是Redis的字典，其中包含两个哈希表dictht，这是为了方便进行rehash操作。在扩容时，将其中一个dictht上的键值对rehash到另一个dictht上面，完成之后释放空间并交换两个dictht 的角色。其实字典本身的数据结构特点和Hash表是一样的，内部保存2个
Hash表以及rehashindex等辅助信息是便于实现渐进式rehash。
/*
* 字典
*/
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量
int iterators; /* number of iterators currently running */
} dict;
- 字典的rehash操作不是一次性完成，而是采用渐进方式，这是为了避免一次性执行过多的rehash操作给服务器带来过大的负担。渐进式rehash通过记录dict的rehashidx完成，它从0开始每执行一次rehash都会递增。例如在一次rehash中，要把dict[0] rehash到 dict[1]，会把dict[0]上table[rehashidx]的键值对rehash到dict[1]上，dict[0]的table[rehashidx]指向null，并令rehashidx++。在rehash期间，每次对字典执行添加、删除、查找或者更新操作时，都会执行一次渐进式rehash。采用渐进式rehash 会导致字典中的数据分散在两个dictht 上，因此对字典的查找操作也需要到对应的dictht去执行。
1.4 字典reHash
- 下面是字典结构的rehash操作函数。我对比了源码，这个是Redis2.8及一下的版本源码，3.0及以上版本源码略有不同。
/* Performs N steps of incremental rehashing. Returns 1 if there are still
* keys to move from the old to the new hash table, otherwise 0 is returned.
*
* 执行 N 步渐进式 rehash 。
*
* 返回 1 表示仍有键需要从 0 号哈希表移动到 1 号哈希表，
* 返回 0 则表示所有键都已经迁移完毕。
*
* Note that a rehashing step consists in moving a bucket (that may have more
* than one key as we use chaining) from the old to the new hash table.
*
* 注意，每步 rehash 都是以一个哈希表索引（桶）作为单位的，
* 一个桶里可能会有多个节点，
* 被 rehash 的桶里的所有节点都会被移动到新哈希表。
*
* T = O(N)
*/
int dictRehash(dict *d, int n) {
// 只可以在 rehash 进行中时执行
if (!dictIsRehashing(d)) return 0;
// 进行 N 步迁移
// T = O(N)
while(n--) {
dictEntry *de, *nextde;
/* Check if we already rehashed the whole table... */
// 如果 0 号哈希表为空，那么表示 rehash 执行完毕
// T = O(1)
if (d->ht[0].used == 0) {
// 释放 0 号哈希表
zfree(d->ht[0].table);
// 将原来的 1 号哈希表设置为新的 0 号哈希表
d->ht[0] = d->ht[1];
// 重置旧的 1 号哈希表
_dictReset(&d->ht[1]);
// 关闭 rehash 标识
d->rehashidx = -1;
// 返回 0 ，向调用者表示 rehash 已经完成
return 0;
}
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
// 确保 rehashidx 没有越界
assert(d->ht[0].size > (unsigned)d->rehashidx);
// 略过数组中为空的索引，找到下一个非空索引
while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
// 指向该索引的链表表头节点
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
// 将链表中的所有节点迁移到新哈希表
// T = O(1)
while(de) {
unsigned int h;
// 保存下个节点的指针
nextde = de->next;
/* Get the index in the new hash table */
// 计算新哈希表的哈希值，以及节点插入的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 插入节点到新哈希表
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
// 更新计数器
d->ht[0].used--;
d->ht[1].used++;
// 继续处理下个节点
de = nextde;
}
// 将刚迁移完的哈希表索引的指针设为空
d->ht[0].table[d->rehashidx] = NULL;
// 更新 rehash 索引
d->rehashidx++;
}
return 1;
}
1.5 小结
- 字典也是和Hash表一样的k-v存储集合，但是是基于Hash表来实现的。
- 在字典的内部维护了2个Hash表，来实现渐进式rehash。rehash的时候不是一次性完成，而是渐进式的将元素从一个Hash表迁移到另一个Hash表，注意一次迁移的不是一个k-v对结构dictEntry，而是按照桶为单位进行迁移的。
- 在Redis的本身源码中，字典是很多基础功能实现的基础数据结构，比如在Redis集群中使用字典来保存集群的所有服务器节点信息，在Redis中默认包含16个数据库，每一个库对应一个redisDb的数据结构，在redisDb内部就是通过一个dict字典来保存该库下的全部键值对
- 字典可以理解为一个优化后的Hash表，其功能和Hash几乎一样，但是做rehash的时候性能更好，以空间换取了时间。
二、跳跃表
-
跳跃表是一种数据结构，它基于多指针有序链表实现的，可以看成多个有序链表。在Redis中它是有序集合的底层实现之一。另外在Redis中一些涉及到排序的场景也会使用到跳跃表，比如Redis分片集群中使用跳跃表保存了槽和key之间的关系，以槽为分值键为成员对槽进行排序，便于进行区间操作，或者处理槽和键之间的关系和对槽进行rehash。
-
Redis中的有序集合是一种以跳跃表为基础的数据结构，我们来看看跳跃表和有序集合在Redis源码中的定义等信息。下面代码在Redis源码的src/redis.h文件中，可阅读参考文章[2]。
2.1 跳跃表节点zskiplistNode
- zskiplistNode是对应跳跃表节点的数据结构。节点除了包含目标的key之外，还包含分值、前后指针、跨度等信息。
/* ZSETs use a specialized version of Skiplists */
/*
* 跳跃表节点
*/
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
2.2 跳跃表zskiplist
- zskiplist是对应跳跃表的数据结构。包含一个跳跃表的头尾节点指针、节点数量和最大层数。
/*
* 跳跃表
*/
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
2.3 有序集合zset
- zset是对应有序集合的数据结构。zset内部维护一个字典来保证按照成员取出分值，提示维护一个跳跃表来支持按照分值操作成员，比如排序等。
/*
* 有序集合
*/
typedef struct zset {
// 字典，键为成员，值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;
// 跳跃表，按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
// 以及范围操作
zskiplist *zsl;
} zset;
2.4 跳跃表操作
- 跳表的查找，插入等操作，可以阅读参考文章[4]
2.5 小结
- 跳跃表也是一种加速查找的数据结构，内部通过多层指针和双向指针来实现加速查找，在排序和范围操作时性能较好，并基于它实现了Redis中的有序集合。相比于红黑树这样的查找结构，有下面优点，为什么Redis中不使用红黑树呢？后面给了一个表格
A.插入快。因为不需要进行旋转等操作来维护平衡性；
B.更容易实现。实现比红黑树简单许多；
C.支持无锁操作。
| 对比项 | 红黑树复杂度 | 跳表复杂度 |
|---|---|---|
| 插入元素 | O(log n) | O(log n) |
| 删除元素 | O(log n) | O(log n) |
| 查找元素 | O(log n) | O(log n) |
| 有序输出元素 | O(log n) | O(log n) |
| 区间操作元素 | 不如跳表 | 性能很好 |
- 区间操作时，红黑树定位到端点后，再从首位置开始每次都要查找后继节点，相对来说是比较耗时的。跳表的区间操作，定位到2端的元素之后，顺序遍历即可，显然性能更好
三、参考
- [1] CS-Notes/Redis
- [2] Redis源码-带注释
- [3] Redis 设计与实现-黄健宏
- [4] 拜托，面试别再问我跳表了！