字典

字典(dictionary), 又名映射(map)或关联数组(associative array), 是一种抽象数据结构, 由一集键值对(key-value pairs)组成, 各个键值对的键各不相同, 程序可以添加新的键值对到字典中, 或者基于键进行查找、更新或删除等操作。

字典应用

字典的主要用途有以下两个:

  • 实现数据库键空间(key space);
  • 用作 Hash 类型键的底层实现之一;

    哈希表实现

实现字典的方法有很多种:

  • 最简单的就是使用链表或数组,但是这种方式只适用于元素个数不多的情况下;
  • 要兼顾高效和简单性,可以使用哈希表;
  • 如果追求更为稳定的性能特征,并希望高效地实现排序操作的话,则可使用更为复杂的平衡树;

在众多可能的实现中, Redis 选择了高效、实现简单的哈希表,作为字典的底层实现。


/*
 * 字典
 *
 * 每个字典使用两个哈希表,用于实现渐进式 rehash
 */
typedef struct dict {

    // 特定于类型的处理函数
    dictType *type;

    // 类型处理函数的私有数据
    void *privdata;

    // 哈希表(2 个)
    dictht ht[2];

    // 记录 rehash 进度的标志,值为 -1 表示 rehash 未进行
    int rehashidx;

    // 当前正在运作的安全迭代器数量
    int iterators;

} dict;

/*
 * 哈希表
 */
typedef struct dictht {

    // 哈希表节点指针数组(俗称桶,bucket)
    dictEntry **table;

    // 指针数组的大小
    unsigned long size;

    // 指针数组的长度掩码,用于计算索引值
    unsigned long sizemask;

    // 哈希表现有的节点数量
    unsigned long used;

} dictht;

/*
 * 哈希表节点
 */
typedef struct dictEntry {

    // 键
    void *key;

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

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

} dictEntry;

哈希碰撞

dictht 使用链地址法来处理键碰撞: 当多个不同的键拥有相同的哈希值时,哈希表用一个链表将这些键连接起来。

哈希算法

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

  • MurmurHash2 32 bit 算法:这种算法的分布率和速度都非常好, 具体信息请参考 MurmurHash 的主页: http://code.google.com/p/smhasher/ 。
  • 基于 djb 算法实现的一个大小写无关散列算法:具体信息请参考 http://www.cse.yorku.ca/~oz/hash.html 。

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

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

创建新字典

新创建的两个哈希表都没有为 table 属性分配任何空间:

  • ht[0]->table 的空间分配将在第一次往字典添加键值对时进行;
  • ht[1]->table 的空间分配将在 rehash 开始时进行;

添加键值对到字典

字典为空

发生碰撞

在哈希表实现中, 当两个不同的键拥有相同的哈希值时, 称这两个键发生碰撞(collision), 而哈希表实现必须想办法对碰撞进行处理。

字典哈希表所使用的碰撞解决方法被称之为链地址法: 这种方法使用链表将多个哈希值相同的节点串连在一起, 从而解决冲突问题。

触发了 rehash 操作

为了在字典的键值对不断增多的情况下保持良好的性能, 字典需要对所使用的哈希表(ht[0])进行 rehash 操作: 在不修改任何键值对的情况下,对哈希表进行扩容, 尽量将比率维持在 1:1 左右。

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

  • 自然 rehash : ratio >= 1 ,且变量 dict_can_resize 为真。
  • 强制 rehash : ratio 大于变量 dict_force_resize_ratio (目前版本中, dict_force_resize_ratio 的值为 5 )。

数据库就是字典, 数据库里的哈希类型键也是字典, 当 Redis 使用子进程对数据库执行后台持久化任务时(比如执行 BGSAVE 或 BGREWRITEAOF 时), 为了最大化地利用系统的 copy on write 机制, 程序会暂时将 dict_can_resize 设为假, 避免执行自然 rehash , 从而减少程序对内存的触碰(touch)。

Rehash 执行过程

  • 创建一个比 ht[0]->table 更大的 ht[1]->table ;
  • 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ;
  • 将原有 ht[0] 的数据清空,并将 ht[1] 替换为新的 ht[0] ;

渐进式 rehash

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

渐进式 rehash 主要由 _dictRehashStepdictRehashMilliseconds 两个函数进行:

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

_dictRehashStep

每次执行 _dictRehashStep , ht[0]->table 哈希表第一个不为空的索引上的所有节点就会全部迁移到 ht[1]->table 。

在 rehash 开始进行之后(d->rehashidx 不为 -1), 每次执行一次添加、查找、删除操作, _dictRehashStep 都会被执行一次:

dictRehashMilliseconds

dictRehashMilliseconds 可以在指定的毫秒数内, 对字典进行 rehash 。

当 Redis 的服务器常规任务执行时, dictRehashMilliseconds 会被执行, 在规定的时间内, 尽可能地对数据库字典中那些需要 rehash 的字典进行 rehash , 从而加速数据库字典的 rehash 进程(progress)。

其他措施

在哈希表进行 rehash 时, 字典还会采取一些特别的措施, 确保 rehash 顺利、正确地进行:

  • 因为在 rehash 时,字典会同时使用两个哈希表,所以在这期间的所有查找、删除等操作,除了在 ht[0] 上进行,还需要在 ht[1] 上进行。
  • 在执行添加操作时,新的节点会直接添加到 ht[1] 而不是 ht[0] ,这样保证 ht[0] 的节点数量在整个 rehash 过程中都只减不增。

字典的收缩

上面关于 rehash 的章节描述了通过 rehash 对字典进行扩展(expand)的情况, 如果哈希表的可用节点数比已用节点数大很多的话, 那么也可以通过对哈希表进行 rehash 来收缩(shrink)字典。

收缩 rehash 和上面展示的扩展 rehash 的操作几乎一样,执行以下步骤:

  • 创建一个比 ht[0]->table 小的 ht[1]->table ;
  • 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ;
  • 将原有 ht[0] 的数据清空,并将 ht[1] 替换为新的 ht[0] ;

扩展 rehash 和收缩 rehash 执行完全相同的过程, 一个 rehash 是扩展还是收缩字典, 关键在于新分配的 ht[1]->table 的大小:

  • 如果 rehash 是扩展操作,那么 ht[1]->table 比 ht[0]->table 要大;
  • 如果 rehash 是收缩操作,那么 ht[1]->table 比 ht[0]->table 要小;

字典的收缩规则由 redis.c/htNeedsResize 函数定义:

/*
 * 检查字典的使用率是否低于系统允许的最小比率
 *
 * 是的话返回 1 ,否则返回 0 。
 */
int htNeedsResize(dict *dict) {
    long long size, used;

    // 哈希表大小
    size = dictSlots(dict);

    // 哈希表已用节点数量
    used = dictSize(dict);

    // 当哈希表的大小大于 DICT_HT_INITIAL_SIZE
    // 并且字典的填充率低于 REDIS_HT_MINFILL 时
    // 返回 1
    return (size && used && size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < REDIS_HT_MINFILL));
}

在默认情况下, REDIS_HT_MINFILL 的值为 10 , 也即是说, 当字典的填充率低于 10% 时, 程序就可以对这个字典进行收缩操作了。

字典的迭代

字典带有自己的迭代器实现 —— 对字典进行迭代实际上就是对字典所使用的哈希表进行迭代:

  • 迭代器首先迭代字典的第一个哈希表,然后,如果 rehash 正在进行的话,就继续对第二个哈希表进行迭代。
  • 当迭代哈希表时,找到第一个不为空的索引,然后迭代这个索引上的所有节点。
  • 当这个索引迭代完了,继续查找下一个不为空的索引,如此反覆,直到整个哈希表都迭代完为止。
/*
 * 字典迭代器
 */
typedef struct dictIterator {

    dict *d;                // 正在迭代的字典

    int table,              // 正在迭代的哈希表的号码(0 或者 1)
        index,              // 正在迭代的哈希表数组的索引
        safe;               // 是否安全?

    dictEntry *entry,       // 当前哈希节点
              *nextEntry;   // 当前哈希节点的后继节点

} dictIterator;