字典在 Redis 的应用
字典在我们平时的编程中是一种非常常见的数据结构, 它有着结构简单, 查找快速的优点, 而在 Redis 中, 字典的应用更是十分广泛. Redis 本身是一个 key-value 型的 nosql 数据库, 因此数据库本身就是由字典而构成的, 数据库的 curd 都是在此基础上进行的. 除此之外, Redis 的 map 类型也是由字典这个结构实现的.
字典的实现
c 语言不像我们平时用习惯的高级编程语言一样, 它没有内置字典结构, 因此 Redis 自身实现了一套字典结构, 下面我们来简单分析下实现字典的几个结构体.
1. 哈希表
- typedef struct dictht {
- // 哈希表数组
- dictEntry **table;
- // 哈希表大小
- unsigned long size;
- // 哈希表大小掩码, 用于计算索引值
- // 总是等于 size - 1
- unsigned long sizemask;
- // 该哈希表已有节点的数量
- unsigned long used;
- } dictht;
这里要注意的就是, table 字段是一个可以保存多个 dictEntry 的数组, 也就是一个哈希表里面会有多个哈希的实体类, 也可以成为哈希节点.
2. 哈希节点
- typedef struct dictEntry {
- // 键
- void *key;
- // 值
- union {
- void *val;
- uint64_t u64;
- int64_t s64;
- } v;
- // 指向下个哈希表节点, 形成链表
- struct dictEntry *next;
- } dictEntry;
v 字段表示哈希节点的值, 使用 union 结构体表示这个值可以使 void 指针类型, 也可以是 uint64_t 或者 int64_t 整数, 这里我猜想是为了其他操作系统而做的一个兼容吧. 尽管大部分哈希函数具有很强的防碰撞性, 但是也会遇到哈希值相同的键值对, 这个时候 next 字段就发挥作用了, 它会把相同哈希值的键值对整理成一个单向链表结构来方便查找.
3. 字典
- 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;
type 字段提供了一组类型的操作函数:
- 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;
这组函数可以让不同类型的键值对能够使用不同的方法进行复制, 对比等操作, 真正让 Redis 实现了多态字典.
我们还可以见到, 字典结构体内部包含了两个哈希表的数组, 为什么需要两个哈希表呢? 这就引入了一个 rehash 的概念了.
字典的 rehash
当哈希表中的哈希节点, 也就是键值对的数量越来越多或者越来越少的时候, 原来分配的哈希表将会进行伸缩, Redis 会维护一个哈希表的负载因子, 其中计算方式是: 负载因子 = 哈希表的使用数量 / 哈希表的长度
当符合以下两个条件任何一个的时候就会进行 reshash 操作:
服务器没有执行 BGSAVE 或者 BGREWRITEAOF 命令, 并且这个负载因子大于等于 1 的时候.
服务器在执行 BGSAVE 或者 BGREWRITEAOF 命令, 并且负载因子超过 5.
为什么在执行备份命令的时候, 负载因子要比没有执行备份的时候大呢? 原因就是 Redis 在执行 BGSAVE 之类的备份命令时候, 会 fork 一个子进程进行备份, 而目前大部分操作系统都会采用 copy on write 也就是写时复制的技术, 如果此时过多的去进行 rehash 会导致内存占用过多.
rehash 的步骤:
为哈希表数组 ht[1] 进行空间分配. 分配的原则是: 扩容则分配 ht[0].used*2, 收缩则分配 ht[0]*used/2.
重新计算 ht[0] 中的所有键值对, 然后逐步迁移到 ht[1] 中.
当 ht[0] 所有键值对都迁移完毕之后, 释放 ht[0] 所占空间, 把 ht[1] 取代到 ht[0] 的位置, 并且新创建一个空白的哈希表, 也就是新的 ht[1], 整个 rehash 步骤到此结束.
渐进式 rehash
上面我们简单介绍了 rehash 的步骤, 但是如果真是那么简单去实现的话, 其实是有缺陷的. 试想想, 如果哈希表中拥有大量的键值对, 一次性去进行 rehash 把大量的键值对进行迁移, 势必会导致性能低下, 并且影响 Redis 的读写性能甚至导致服务被停止. 因此, rehash 是渐进的, 并且是不能影响正常的 Redis 读写服务的. 以下就是渐进式 rehash 的一个过程:
为 ht[1] 分配空间, 分配的规则上面已经写了, 这里就不再重复描述.
此时字典会拥有 ht[0] 和 ht[1] 两个哈希表, 字段 rehashidx 就能产生作用了. rehashidx 默认值是 - 1, 当它变为 0 说明 rehash 正式开始.
rehash 开始, Redis 会把 ht[0] 中 rehashidx 索引中的键值对进行 rehash 到 ht[1], 每次 rehash 完成都会让 rehashidx 递增 1, 然后重复这个过程.
在这个过程中, 我们难免会对 Redis 进行增删改查的操作, 这个时候同时拥有两个哈希表的作用就发挥出来了. 对于查找, 删除, 修改操作, Redis 会现在 ht[0] 中进行, 如果找不到才会到 ht[1] 进行对应操作, 而增加这些操作则会直接在 ht[1] 中进行, 主要是让 ht[0] 只减不增, 这样到了某个时刻, ht[0] 的所有键值对一定会全部迁移到 ht[1].
领悟
Redis 这个字典的结构实现清晰明了, 特别是其中的 rehash 机制很值得我去学习, 这个对于一些数据迁移并且不能影响正常服务的编程实现非常有借鉴意义.
文章参考自:<<Redis 设计与实现 >> 第二版
来源: http://www.jianshu.com/p/2aec6a05ac24