Redis享知享学：单机数据库实现：dict属性

本篇主要目的是理解Redis单机数据库中键空间dict的实现机理。

Redis的持久化技术建立在操作系统的COW机制上，Redis如何权衡rehash的时机？rehash时间会产生堵塞服务器的问题，Redis是如何应对这个问题的？渐进式rehash的原理是什么？诸如此类问题将通过本篇文章得到解答。

结构一览

首先看看Redis单机数据库的结构：

typedef struct redisDb {
    // key space，包括键值对象
    dict *dict;                 /* The keyspace for this DB */
    // 保存 key 的过期时间
    dict *expires;              /* Timeout of keys with a timeout set */
    // 正因为某个/某些 key 而被阻塞的客户端
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */
    // 某个/某些接收到 PUSH 命令的阻塞 key
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    // 正在监视某个/某些 key 的所有客户端
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    // 数据库的号码
    int id;
} redisDb;

下面将解析redisDb内各属性。

dict

这个属性中文翻译成“键空间”，是Redis内部的数据结构字典实现的，字典的结构如下：

typedef struct dict {

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

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

    // 哈希表（2个）
    dictht ht[2];       

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

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

} dict;

了解Java HashMap的对这个结构不会陌生，只不过这里拥有两个哈希表：

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

新的键值添加进字典前会经过三个步骤：

• 字典0号哈希表的table属性为空，ht[0]->table分配空间(本人当前使用版本初始大小为4)；
• 如果发生碰撞，处理碰撞；
• 插入新元素若满足rehash条件，则进行rehash；

这里分析一下rehash过程，其它步骤可以参考本站HashMap的源码解析，原理相同。

rehash时机

哈希表的性能依赖一个比率 ratio：used / size，used和size是dictht中的属性：

typedef struct dictht {

    // 哈希表节点指针数组（俗称桶，bucket）
    dictEntry **table;      

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

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

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

} dictht;

rehash分扩展(expand)和收缩(shrink)。本篇文章主要介绍扩展(收缩的原理和扩展基本相同)：

什么时候扩展？这个问题需要提两个变量：

• static int dict_can_resize = 1;
• static unsigned int dict_force_resize_ratio = 5;

它们都是触发扩展的条件变量，为什么有两个触发条件？这就需要对它们使用的环境进行分析。

dict_can_resize

设置dict_can_resize的方法有两个：

• dictEnableResize方法用来置1；
• dictDisableResize方法用来置0；

这两个方法只在一处调用：

void updateDictResizePolicy(void) {
    if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)
        dictEnableResize();
    else
        dictDisableResize();
}

还没有RDB持久化服务的时候，server.rdb_child_pid == -1；还没有AOF持久化服务的时候，server.aof_child_pid == -1。

即调用方法后，若没有子进程的持久化服务存在，dictEnableResize()就调用，将dict_can_resize置1，反之置0。

在扩容的方案中，dict_can_resize作为条件变量时被引用在_dictExpandIfNeeded中：

static int _dictExpandIfNeeded(dict *d)
{
    // 已经在渐进式 rehash 当中，直接返回
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果哈希表为空，那么将它扩展为初始大小
    // O(N)
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */    
    // 如果哈希表的已用节点数 >= 哈希表的大小，
    // 并且以下条件任一个为真：
    //   1) dict_can_resize 为真
    //   2) 已用节点数除以哈希表大小之比大于
    //      dict_force_resize_ratio
    // 那么调用 dictExpand 对哈希表进行扩展
    // 扩展的体积至少为已使用节点数的两倍
    // O(N)
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }

    return DICT_OK;
}

dict_force_resize_ratio

这个时候，我们看到了另一个条件变量dict_force_resize_ratio。这也是整个源代码该变量唯一被引用的地方。

暂时先搁置_dictExpandIfNeeded的内部实现，看看它在整个源代码中的调用链：

dictAdd() / dictReplaceRaw()可能调用 / sentinelObjectiveLeaderIncr()可能调用 ->

dictAddRaw() ->

_dictKeyIndex() ->

_dictExpandIfNeeded()

暂时考虑添加键值对的情况：dictAdd()，它是最普遍的操作。最终它会调用_dictExpandIfNeeded方法，添加键值对后，d->ht[0].used >= d->ht[0].size如果成立，则继续判断 && 后的条件语句，也就是：

(dict_can_resize ||
 d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)

dict_can_resize为1，直接执行rehash扩展方法dictExpand()；如果dict_can_resize为0，但是只要used / size大于5，程序仿佛抱怨“对不起，实在太大了，必须马上rehash”，不论dict_can_resize是什么值，都执行rehash扩展方法。

现在一切都清楚了，dict_can_resize是一个用来降低rehash优先级的标志位。而如果比率太大，大于5，那么rehash的优先级就摆在了前面。

为什么要这样处理？used / size >= 1比起used / size > dict_force_resize_ratio的“门槛”低很多，如果不设置一个dict_can_resize标志位，那么当子进程进行持久化服务的时候，可能会面临频繁的rehash，造成过大的资源开销，Redis的持久化服务运用了操作系统的写时复制(COW)技术，关于父子进程，国外网友回答到：“All processes are sharing the same set of pages and each one gets its own private copy when it wants to modify a page.”

rehash基本原理

先确定扩容大小。前文的代码中，一旦确定要扩容，返回的是dictExpand(d, d->ht[0].used*2)的值。在该函数内部实际上调用了_dictNextPower方法，并赋值给realsize，这就是扩容后的哈希表的大小。在Java的HashMap容器的源码中有一个和_dictNextPower类似的方法，该方法返回不小于传入参数的最小2的次方数。

接下来简单叙述rehash流程

• 按照前文确定的扩容大小给ht[1]分配空间；
• ht[0]->table的节点迁移到ht[1]->table；
• 执行迁移后的“善后”工作；

“善后”用代码描述：

if (d->ht[0].used == 0) {

    // 释放 ht[0] 的哈希表数组
    zfree(d->ht[0].table);

    // 将 ht[0] 指向 ht[1]
    d->ht[0] = d->ht[1];

    // 清空 ht[1] 的指针
    _dictReset(&d->ht[1]);

    // 关闭 rehash 标识
    d->rehashidx = -1;

    // 通知调用者， rehash 完毕
    return 0;
}

这个过程用代码描述还是比较清晰的。

渐进式rehash

ht[0]->table的节点迁移到ht[1]->table不是一次性、集中性的完成，主要是因为如果数据量太大，服务器会阻塞等待，所以它是一种渐进式的方式来进行。怎么渐进式进行？就是把rehash的整个过程分散到多个步骤中去。

我个人觉得代码中比较有新意的地方：作者明白复制一个哈希表的内容到另一个扩容的哈希表不是目的，目的是减少增删改查数据的开销，以及不造成服务器长时间的阻塞。那么每次可以只将一个表的内容转移一部分到扩容的表，此时两个表可以同时使用。当然，后续客户端命令产生的新的数据，直接保存在扩容表上。

rehash的核心操作都封装在dictRehash方法里，但它的调用主要又是依靠_dictRehashStep和dictRehashMilliseconds方法。

前面提到的多个步骤，对于_dictRehashStep()来说，指的是：dictAddRaw、dictGenericDelete、dictFind、dictGetRandomKey四个方法的调用步骤，只要dictIsRehashing方法返回true(该方法主要判断rehash是否正在进行)，就会执行_dictRehashStep()。每次迁移ht[0]->table索引从0递增第一个不为空的链表的所有节点到ht[1]->table。

dictRehashMilliseconds则需要传入一个参数时常的阻塞时间，在这个规定时间内迁移尽可能多的数据。

参考

Redis 设计与实现：国内解析Redis的开源资料；

fork()后copy on write的一些特性：介绍了操作系统内COW实现原理；

How does copy-on-write in fork() handle multiple fork?：国外问答网站关于fork处理中COW技术的精简回答；

［OS］ fork() 和 vfork() ［copy on write］：痞客邦的网友回答；

Redis持久化RDB和AOF相比较

解密Redis持久化：该内容来源于Redis作者博文；

安装附录

用HomeBrew安装：brew isntall redis

启动命令：redis-server；

启动客户端：redis-cli；

如果有中文乱码，输入如下命令：

redis-cli --raw