关于redis:Redis的设计与实现3字典

Redis 的数据库应用字典实现, 对数据库的增, 删, 查, 改也是构建在对字典的操作之上的.

字典是哈希键的底层实现之一: 当一个哈希键蕴含的键值对比拟多, 又或者键值对中的元素都是比拟长的字符串时, Redis 将会应用字典作为哈希键的底层实现.

Redis 的字典应用哈希表作为底层实现, 一个哈希表外面能够有多个哈希表节点, 而每个哈希表节点就保留了字典中的一个键值对.

Redis 字典所应用的哈希表由 dict.h/dictht 构造定义：

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

<!–more–>

table 属性是一个数组, 数组中的每个元素都是一个指向 dict.h/dictEntry 构造的指针, 每个 dictEntry 构造保留着一个键值对.

size 属性记录了哈希表的大小, 也即是 table 数组的大小, 而 used 属性则记录了哈希表目前已有节点 (键值对) 的数量.

sizemask 属性的值总是等于 size - 1 , 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引下面.

哈希表节点应用 dictEntry 构造示意, 每个 dictEntry 构造都保留着一个键值对:

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，造成链表
    struct dictEntry *next;
} dictEntry;

key 键
v 值
next 指向下一个哈希表节点指针

值能够是一个 指针, uint64_t 整数, int64_t 整数;
next 能够将多个哈希值雷同的键值对连贯在一次, 以此解决键抵触的问题.

Redis 中的字典由 dict.h/dict 构造示意:

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 公有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

type 属性和 privdata 属性是针对不同类型的键值对, 为创立多态字典而设置的:

type 属性是一个指向 dictType 构造的指针, 每个 dictType 构造保留了一簇用于操作特定类型键值对的函数, Redis 会为用处不同的字典设置不同的类型特定函数;
privdata 属性则保留了须要传给那些类型特定函数的可选参数.

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;

ht 属性是一个蕴含两个项的数组, 数组中的每个项都是一个 dictht 哈希表, 个别状况下, 字典只应用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时应用.

除了 ht[1] 之外, 另一个和 rehash 无关的属性就是 rehashidx : 它记录了 rehash 目前的进度, 如果目前没有在进行 rehash, 那么它的值为 -1.

当要将一个新的键值对增加到字典外面时, 程序须要先依据键值对的键计算出哈希值和索引值, 而后再依据索引值, 将蕴含新键值对的哈希表节点放到哈希表数组的指定索引上
面.

Redis 计算哈希值和索引值的办法如下:

# 应用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
# 应用哈希表的 sizemask 属性和哈希值，计算出索引值
# 依据状况不同，ht[x] 能够是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

当字典被用作数据库或哈希键的底层实现时, Redis 应用 MurmurHash2 算法来计算键的哈希值.

MurmurHash 算法目前的最新版本为 MurmurHash3 , 而 Redis 应用的是 MurmurHash2, 对于 MurmurHash 算法的更多信息能够参考该算法的主页: http://code.google.com/p/smha…

该算法曾经迁徙到 GitHub: https://github.com/aappleby/smhasher

然而, 我在 GitHub 上搜寻 Redis 的相干源码, 发现版本不同, 应用的哈希算法也是不雷同的:

最新版本的 Redis (5.0 已公布), 采纳的是 SipHash 哈希算法, 链接:
https://github.com/antirez/redis/blob/unstable/src/dict.c#L84

往回看, 5.0, 4.0 都是 SipHash 哈希算法:

https://github.com/antirez/redis/blob/5.0/src/dict.c#L84

https://github.com/antirez/redis/blob/4.0/src/dict.c#L84

3.2, 3.0, 2.8, 2.6 都是 MurmurHash2 哈希算法:

https://github.com/antirez/redis/blob/3.2/src/dict.c#L92

https://github.com/antirez/redis/blob/3.0/src/dict.c#L92

https://github.com/antirez/redis/blob/2.8/src/dict.c#L92

https://github.com/antirez/redis/blob/2.6/src/dict.c#L98

而更旧的 2.4 2.2, 作者没有说是什么算法, 然而让我回想到 鸟哥 的一篇文章, 讲的是 PHP 的哈希算法, 看样子很像, 预计是 DJBX33A (Daniel J. Bernstein, Times 33 with Addition) 算法.

PHP 中的 Hash 算法

https://github.com/antirez/redis/blob/2.4/src/dict.c#L88

https://github.com/antirez/redis/blob/2.2/src/dict.c#L88

对于哈希算法的, 还找到了两篇文章:

漫谈非加密哈希算法
我为什么要应用哈希

当有两个或以上数量的键被调配到了哈希表数组的同一个索引下面时, 咱们称这些键产生了抵触（collision）.

Redis 的哈希表应用链地址法 (separate chaining) 来解决键抵触: 每个哈希表节点都有一个 next 指针, 多个哈希表节点能够用 next 指针形成一个单向链表, 被调配到同一个索引上的多个节点能够用这个单向链表连接起来, 这就解决了键抵触的问题.

因为 dictEntry 节点组成的链表没有指向链表表尾的指针, 为了速度思考, 程序总是将新节点增加到链表的表头地位, 排在已有节点后面, 操作的复杂度为 O(1).

当哈希表保留的键值对数量太多或者太少时, 程序须要对哈希表的大小进行相应的扩大或者膨胀.

扩大和膨胀哈希表的工作能够通过执行 rehash (从新散列) 操作来实现, Redis 对字典的哈希表执行 rehash 的步骤如下:

为字典的 ht[1] 哈希表调配空间, 这个哈希表的空间大小取决于要执行的操作, 以及 ht[0] 以后蕴含的键值对数量 (也即是 ht[0].used 属性的值):
- 如果执行的是扩大操作, 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n (2 的 n 次方幂);
- 如果执行的是膨胀操作, 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n .
将保留在 ht[0] 中的所有键值对 rehash 到 ht[1] 下面: rehash 指的是从新计算键的哈希值和索引值, 而后将键值对搁置到 ht[1] 哈希表的指定地位上.
当 ht[0] 蕴含的所有键值对都迁徙到了 ht[1] 之后 (ht[0] 变为空表), 开释 ht[0] , 将 ht[1] 设置为 ht[0] , 并在 ht[1] 新创建一个空白哈希表, 为下一次 rehash 做筹备.

当以下条件中的任意一个被满足时, 程序会主动开始对哈希表执行扩大操作:

服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 1;
服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令, 并且哈希表的负载因子大于等于 5. (感觉书错了, 应该是 0.5 …)

其中哈希表的负载因子能够通过公式计算得出:

# 负载因子 = 哈希表已保留节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

依据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行, 服务器执行扩大操作所需的负载因子并不相同, 这是因为在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中, Redis 须要创立以后服务器过程的子过程, 而大多数操作系统都采纳写时复制 (copy-on-write) 技术来优化子过程的应用效率, 所以在子过程存在期间, 服务器会进步执行扩大操作所需的负载
因子, 从而尽可能地防止在子过程存在期间进行哈希表扩大操作, 这能够防止不必要的内存写入操作, 最大限度地节约内存.

另一方面, 当哈希表的负载因子小于 0.1 时, 程序主动开始对哈希表执行膨胀操作.

为防止 rehash 对服务器性能造成影响, 服务器不是一次性将 ht[0] 外面的所有键值对全副 rehash 到 ht[1] , 而是分屡次, 渐进式地将 ht[0] 外面的键值对缓缓地 rehash 到 ht[1].

以下是哈希表渐进式 rehash 的具体步骤:

为 ht[1] 调配空间, 让字典同时持有 ht[0] 和 ht[1] 两个哈希表;
在字典中维持一个索引计数器变量 rehashidx , 并将它的值设置为 0 , 示意 rehash 工作正式开始;
在 rehash 进行期间, 每次对字典执行增加, 删除, 查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作实现之后, 程序将 rehashidx 属性的值增 1;
随着字典操作的一直执行, 最终在某个工夫点上, ht[0] 的所有键值对都会被 rehash 至 ht[1] , 这时程序将 rehashidx 属性的值设为 -1 , 示意 rehash 操作已实现.

渐进式 rehash 的益处在于它采取分而治之的形式, 将 rehash 键值对所需的计算工作均滩到对字典的每个增加, 删除, 查找和更新操作上, 从而防止了集中式 rehash 而带来的宏大计算量.

函数	作用	工夫复杂度
dictCreate	创立一个新的字典.	O(1)
dictAdd	将给定的键值对增加到字典外面.	O(1)
dictReplace	将给定的键值对增加到字典外面, 如果键曾经存在于字典，那么用新值取代原有的值.	O(1)
dictFetchValue	返回给定键的值.	O(1)
dictGetRandomKey	从字典中随机返回一个键值对.	O(1)
dictDelete	从字典中删除给定键所对应的键值对.	O(1)
dictRelease	开释给定字典，以及字典中蕴含的所有键值对.	O(N)，N 为字典蕴含的键值对数量.

字典被宽泛用于实现 Redis 的各种性能, 其中包含数据库和哈希键;
Redis 中的字典应用哈希表作为底层实现, 每个字典带有两个哈希表, 一个用于平时应用, 另一个仅在进行 rehash 时应用.
当字典被用作数据库的底层实现, 或者哈希键的底层实现时, Redis 应用 MurmurHash2 算法来计算键的哈希值;
哈希表应用链地址法来解决键抵触, 被调配到同一个索引上的多个键值对会连接成一个单向链表;
在对哈希表进行扩大或者膨胀操作时, 程序须要将现有哈希表蕴含的所有键值对 rehash 到新哈希表外面, 并且这个 rehash 过程并不是一次性地实现的, 而是渐进式地实现的.

文章来源于自己博客，公布于 2018-05-12，原文链接：https://imlht.com/archives/125/

关于redis:Redis的设计与实现3字典

1. 哈希表

2. 哈希表节点

3. 字典

4. 哈希算法

5. 解决键抵触

6. rehash

7. 哈希表的扩大与膨胀

8. 渐进式 rehash

9. 字典 API

10. 总结