字典

Redis 是一个键值对数据库， 数据库中的 键值对 由 字典 保存： 每个数据库都有一个对应的字典， 这个字典被称之为 键空间 key space

• 当用户添加一个键值对到数据库时（不论键值对是什么类型）， 程序就将该键值对添加到键空间
• 当用户从数据库中删除键值对时， 程序就会将这个键值对从键空间中删除

举个例子，执行 FLUSHDB 可以清空键空间里的所有键值对数据：

redis> FLUSHDB
OK

执行 DBSIZE 则返回键空间里现有的键值对：

redis> DBSIZE
(integer) 0

后面章节会对键空间以及数据库的实现作详细的介绍

大部分针对数据库的命令， 比如 DBSIZE 、 FLUSHDB 、 RANDOMKEY ， 等等， 都是构建于对字典的操作之上的

而那些创建、更新、删除和查找键值对的命令， 也无一例外地需要在键空间上进行操作

Redis 的 Hash 类型键使用以下两种数据结构作为底层实现:

• 字典

• 压缩列表

  因为压缩列表比字典更节省内存， 所以程序在创建新 Hash 键时， 默认使用压缩列表作为底层实现
  
  当有需要时， 程序才会将底层实现从压缩列表转换到字典
  

当用户操作一个 Hash 键时， 键值在底层就可能是一个哈希表：

redis> HSET book name "The design and implementation of Redis"
(integer) 1

redis> HSET book type "source code analysis"
(integer) 1

redis> HSET book release-date "2013.3.8"
(integer) 1

redis> HGETALL book
1) "name"
2) "The design and implementation of Redis"
3) "type"
4) "source code analysis"
5) "release-date"
6) "2013.3.8"

以后《哈希表》章节给出了关于哈希类型键的更多信息， 并介绍了压缩列表和字典之间的转换条件

字典所使用的哈希表实现由 dict.h/dictht 类型定义：

/*
 * 哈希表
 */
typedef struct dictht {
    dictEntry **table; // 哈希表节点指针数组（俗称桶，bucket）
    unsigned long size; // 指针数组的大小
    unsigned long sizemask; // 指针数组的长度掩码，用于计算索引值
    unsigned long used; // 哈希表现有的节点数量
} dictht;

table 属性是个数组， 数组的每个元素都是个指向 dictEntry 结构 的 指针 。每个 dictEntry 都保存着一个 键值对 ， 以及一个指向 另一个 dictEntry 结构 的 指针 ：

/*
 * 哈希表节点
 */
typedef struct dictEntry {
    void *key; // 键

    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v; // 值

    struct dictEntry *next; // 链往后继节点
} dictEntry;

next 属性指向另一个 dictEntry 结构， 多个 dictEntry 可以通过 next 指针串连成链表， 从这里可以看出， dictht 使用 链地址法 来处理键碰撞： 当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。下图展示了一个由 dictht 和数个 dictEntry 组成的哈希表例子：

如果再加上之前列出的 dict 类型，那么整个字典结构可以表示如下：

在上图的字典示例中， 字典虽然创建了两个哈希表， 但正在使用的只有 0 号哈希表， 这说明字典未进行 rehash 状态

Redis 目前使用两种不同的哈希算法：

• MurmurHash2 32 bit 算法：这种算法的分布率和速度都非常好

  具体信息请参考 MurmurHash 的主页： http://code.google.com/p/smhasher/ 
  

• 基于 djb 算法 实现的一个大小写无关散列算法

  具体信息请参考 http://www.cse.yorku.ca/~oz/hash.html 
  

使用哪种算法取决于具体应用所处理的数据：

• 命令表以及 Lua 脚本缓存都用到了算法 2
• 算法 1 的应用则更加广泛：数据库、集群、哈希键、阻塞操作等功能都用到了这个算法

当第一次往空字典里添加键值对时， 程序会根据 dict.h/DICT_HT_INITIAL_SIZE 里指定的大小为 d->ht[0]->table 分配空间

在目前的版本中， DICT_HT_INITIAL_SIZE 的值为 4 

以下是字典空白时的样子：

以下是往空白字典添加了第一个键值对之后的样子：

在哈希表实现中， 当两个不同的键拥有相同的哈希值时， 称这两个键发生 碰撞 collision

哈希表实现必须想办法对碰撞进行处理

字典哈希表所使用的碰撞解决方法被称之为 链地址法 ： 这种方法使用 链表 将多个哈希值相同的节点串连在一起， 从而解决冲突问题。假设现在有一个带有三个节点的哈希表，如下图：

对于一个新的键值对 key4 和 value4 ， 如果 key4 的哈希值和 key1 的哈希值相同， 那么它们将在哈希表的 0 号索引上发生碰撞。通过将 key4-value4 和 key1-value1 两个键值对用链表连接起来， 就可以解决碰撞的问题：

对于使用链地址法来解决碰撞问题的哈希表 dictht 来说， 哈希表的性能取决于 大小 size属性 与 保存节点数量 used属性 之间的 比率 ：

• 哈希表的大小与节点数量，比率在 1:1 时，哈希表的 性能最好
• 如果 节点数量比哈希表的大小要大很多 的话，那么哈希表就会退化成 多个链表 ，哈希表本身的性能优势便不复存在；

举个例子， 下面这个哈希表， 平均每次失败查找只需要访问 1 个节点（非空节点访问 2 次，空节点访问 1 次）：

而下面这个哈希表， 平均每次失败查找需要访问 5 个节点：

为了在字典的键值对不断增多的情况下保持良好的性能， 字典需要对所使用的哈希表（ht[0]）进行 rehash 操作

在不修改任何键值对的情况下，对哈希表进行扩容， 尽量将比率维持在 1:1 左右

dictAdd 在每次向字典添加新键值对之前， 都会对哈希表 ht[0] 进行检查， 对于 ht[0] 的 size 和 used 属性， 如果它们之间的比率 \(ratio = used / size\) 满足以下任何一个条件的话， rehash 过程就会被 激活 ：

1. 自然 rehash ： \(ratio >= 1 ，且变量 \text{dict_can_resize} 为真\)

2. 强制 rehash ： \(ratio 大于变量 \text{dict_force_resize_ratio}\)

   目前版本中， dict_force_resize_ratio 的值为 5 
   

什么时候 dict_can_resize 会为假?

当 Redis 使用子进程对数据库执行后台持久化任务时（比如执行 BGSAVE 或 BGREWRITEAOF 时）

为了最大化地利用系统的 copy on write 机制， 程序会暂时将 dict_can_resize 设为假

避免执行自然 rehash ， 从而减少程序对内存的触碰。当持久化任务完成之后， dict_can_resize 会重新被设为真

另一方面， 当字典满足了强制 rehash 的条件时， 即使 dict_can_resize 不为真（有 BGSAVE 或 BGREWRITEAOF 正在执行）， 这个字典一样会被 rehash 

作为例子， 以下四个小节展示了一次对哈希表进行 rehash 的完整过程

rehash 程序并不是在激活之后，就马上执行直到完成的， 而是分多次、渐进式地完成的

假设这样一个场景：在一个有很多键值对的字典里， 某个用户在添加新键值对时触发了 rehash 过程，

如果这个 rehash 过程必须将所有键值对迁移完毕之后才将结果返回给用户， 这样的处理方式将是非常不友好的

另一方面， 要求服务器必须阻塞直到 rehash 完成， 这对于 Redis 服务器本身也是不能接受的

为了解决这个问题， Redis 使用了 渐进式 incremental 的 rehash 方式： 通过将 rehash 分散到多个步骤中进行， 从而避免了集中式的计算。渐进式 rehash 主要由 _dictRehashStep 和 dictRehashMilliseconds 两个函数进行：

• __dictRehashStep_ 用于对 数据库字典 、以及 哈希键的字典 进行 被动 rehash
• dictRehashMilliseconds 则由 Redis 服务器常规任务程序 server cron job 执行，用于对 数据库字典 进行 主动 rehash