Redis数据结构：字典

目录

引言

字典不仅是数据库的底层实现，也是Redis中哈希键的底层实现之一（压缩列表是另一种哈希键的底层实现）。

对于字典本身的实现，它是由哈希表这种数据结构来实现的。说到哈希表，必然会牵涉到hash值算法、冲突处理、扩容等诸多问题，本文也主要围绕这几个问题展开。如果你对哈希表这种数据结构相关的概念还不是很熟，可以先阅读这篇文章--数据结构之哈希表。

字典的实现

哈希表定义

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

sizemask 和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面

哈希表节点定义

xxxxxxxxxx
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表; 采用链地址法解决hash冲突。
    struct dictEntry *next;
​
} dictEntry;

字典定义

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

• type 和 privdata

  type 属性和 privdata 属性是为了实现多态设置的。每个 dictType 结构保存了一簇用于操作特定类型键值对的函数。privdata 属性则保存了需要传给那些类型特定函数的可选参数。

  dictType定义

  xxxxxxxxxx
  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属性

  ht属性为字典引用的哈希表，dictht的定义将在下面给出。一般情况下字典只使用ht[0]这个哈希表，ht[1]只会在对哈希表进行rehash时才会使用

• rehashidx属性

  rehashdx记录了rehash当前的进度，如果没有进行rehash，则 rehashdx值为-1

字典结构总览图

哈希算法

决定将元素存储到哈希表数组中的哪一项，需要经过两个步骤：

1. 计算哈希值：调用hash函数计算出hash值
2. 计算索引值：用hash值和sizemask计算出索引值

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

Redis 应对不同场景使用不同的哈希算法：

1. MurmurHash2 32 bit 算法：字典作为数据库实现和哈希键实现时，采用此算法。
2. 基于 djb 算法实现的一个大小写无关散列算法：命令表和Lua脚本缓存场景使用
3. 整型的Hash算法使用的是Thomas Wang’s 32 Bit / 64 Bit Mix Function ，这是一种基于位移运算的散列方法（来自http://blog.jobbole.com/99186/）

处理散列冲突

Redis采用链地址法处理冲突问题，即将哈希值相同的元素构成一个同义词的单链表。具体实现是通过dictEntry中的next指针串起来。

rehash

随着键值对的逐渐增多或减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对太多或者太少时，程序需要对哈希表进行相应的扩展或者收缩，这个过程叫做rehash。

Redis 对字典的哈希表执行 rehash 的步骤如下:

1. 为字典的 ht[1] 哈希表分配空间,空间的大小取决于要执行的操作,以及ht[0]当前包含的键值对数量( used 属性值):

   • 如果执行的是扩展操作,那么 ht[1] 的大小为第一个大于等于ht[0].used*2的 $2^n$ 。比如若used为3，则h[1]大小为8。
   • 如果执行的是收缩操作,那么ht[1]的大小为打一个大于等于ht[0].used 的$2^n$

2. 将保存在 ht[0] 中所有键值对 rehash 到 ht[1] 上面: 任何事指的是重新计算键的哈希值和索引值,然后将键值对放到 ht[1] 哈希表的指定位置.

3. 当 ht[0] 包含的所有键值对都迁移到了ht[1]之后, 释放 ht[0], 再将 ht[1] 设置为 ht[0],并在 ht[1] 后面创建一个空白的哈希表.

rehash触发时间

满足以下条件是，将自动触发扩展操作

1. 服务器目前没有执行BGSAVE或者BGREWRITEAOF命令，且哈希表的负载因子大于等于1
2. 服务器目前正在执行BGSAVE或者BGREWRITEAOF命令，且哈希表的负载因子大于等于5

负载因子计算方法：

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

为什么正在执行和未执行BGSAVE/BGREWRITEAOF时，负载因子要求不同？

因为在执行BGSAVE等操作是，Redis需要创建子进程，而大多操作系统都采用写时复制 来提供子进程的工作效率。所以会提供负载因子，尽可能避免在执行BGSAVE期间触发rehash，这可以避免不必要的内存写入操作，从而节省内存。

渐进式rehash

拓展或者收缩哈希表需要将ht[0]里所有的键值对重新hash到ht[1]中，但是这个rehash动作并不是一次性集中式完成的。而是分多次渐进式完成的。原因也很清楚，就是键值对过多时，一次性rehash肯定会消耗服务器大量的计算资源，可能会对服务器的性能造成影响。

以下是渐进式rehash的步骤：

1. 为ht[1]分配空间
2. 在字典中维持一个索引计数器变量 rehashidx，将它的值设置为0，表示rehash正式开始。
3. 在rehash进行期间，每次对字典进行增删改查时，顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]中，同时将rehashidx增加1
4. 随着rehash的不断进行，最终在某个时间点上，ht[0]上的所有键值对都rehash到ht[1]上了，这时将rehashidx属性置为-1，表示rehash操作完成。

参考

• 书籍《Redis设计与实现》
• http://blog.jobbole.com/99186/