Redis数据结构-HashTable

在《Reids数据结构》这篇文章中，我们说到了Redis中的Set和Hash数据类型底层都使用到了hashtable这个数据结构以及Redis的key-value数据库有一个全局哈希表，这里简单说下关于hashtable的结构。

Redis中的hashtable

hashtable在Redis中被称为dictionary（字典），是一个数组+链表的结构，正是因为这样hashtable查询数据的时间复杂度是O(1)。简单说就是将key通过Hash函数的计算，就能定位数据在表中的位置，通过索引值就可以直接在数组中获取到数据。既然是哈希表那肯定是有哈希冲突的，在数据逐渐增加的情况下，哈希冲突的可能性也在增加。Redis采用了链式哈希来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接起，以便这些数据在表中仍然可以被查询到。（其实就是数组+链表，有点类似Java中的HashMap）。

结构设计

简单来说可以理解成Redis有dictht这么一个结构，这个结构就是一个数组，而数组中的元素则是dictEntry，每个dictEntry元素都有一个指针*next指向哈希冲突的下一个节点形成一个链表。

#	 dictht数组
#   +-----------+
#   | dictEntry |
#   +-----------+         +-----------+         +-----------+
#   | dictEntry |-------->| dictEntry |-------->|  ......   |
#   +-----------+         +-----------+         +-----------+
#   | dictEntry |
#   +-----------+
#   | dictEntry |
#   +-----------+         +-----------+         +-----------+         +-----------+
#   | dictEntry |-------->| dictEntry |-------->| dictEntry |-------->|  ......   |
#   +-----------+         +-----------+         +-----------+         +-----------+
#   | dictEntry |
#   +-----------+
#   | dictEntry |
#   +-----------+

在Redis6.0的源码dict.h第72行中是这样定义dictht的:

/* 这是我们哈希表的结构。每个字典都有两个这样的结构，因为我们实现了增量式重新哈希，用于旧表和新表。*/
typedef struct dictht {
    /* 哈希表的数组 */
    dictEntry **table;
    /* 哈希表的大小 */
    unsigned long size;
    /* 用来计算索引值的哈希表大小掩码 */
    unsigned long sizemask;
    /* 已经使用了的节点数量 */
    unsigned long used;
} dictht;

从源码dict.h第50行中可以看到这个dictht就是一个数组，里面的元素就是指向dictEntry的指针。dictEntry的结构如下：

typedef struct dictEntry {
    /* 键值对中的key */
    void *key;
    /* 键值对中的value */
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    /* 指向下一个节点 */
    struct dictEntry *next;
} dictEntry;

可以看到dictEntry结构里面不仅仅有key和value的指针，还有一个指向下一个节点的指针*next，这就是上面说到的用来解决哈希冲突的链式哈希。如果计算出来哈希相同，那么直接在相同的dictEntry里将下一个节点的指针指向冲突的节点就行了。

但是随着数据量的增加，这个链表可能会越来越长，这就会导致查询时间也随着增加，因为链表的遍历时间复杂度是O(N)，那Redis是怎么解决这个问题的呢？在源码dict.h第79行中可以看到还有一个结构体dict，在这个结构里面定义了两个哈希表：

typedef struct dict {
    dictType *type;
    void *privdata;
    /* 两个哈希表，交替使用 */
    dictht ht[2];
    /* 用来记录字典是否处于rehashing过程中（如果 rehashidx == -1 则表示没有进行 rehashing）*/
    long rehashidx; 
    /* 用来记录当前正在运行的迭代器数量。 */
    unsigned long iterators; 
} dict;

rehash

为什么Redis在dict结构要定义两个哈希表呢？

从上面我们知道，随着数据量增加，Redis中的链式哈希中链表长度也会越来越长，这也使得遍历的时间增加，为了解决这个问题，Redis会进行rehash操作，可以理解为给哈希表扩容，这样来减少哈希冲突，也就变向的减少了链表长度。

Redis中rehash的过程可以分为三个步骤：

1. 首先给ht[1]分配空间，一般是当前哈希表ht[0]的两倍。
2. 把ht[0]的数据迁移到ht[1]中。（Redis大部分操作是单线程的，这里Redis采用了渐进式rehash操作。）
3. 迁移完成后，ht[0]的空间会被释放，并把ht[1]设置给ht[0]，然后在ht[1]创建一个空白的哈希表，为下次rehash做准备。

渐进式rehash

上面Redis在rehash过程中的第2步存在一个问题，那就是Redis大部分操作还是单线程的，这个过程可能会阻塞其他操作，如果是在数据量很大的时候，那可能会花很长时间来完成。所以Redis采用了渐进式rehash操作，简单说就是在每次操作的时候顺便copy到新的哈希表，而且Redis本身也有定时任务来处理。

在这个过程中，Redis中实际同时存在着两个哈希表（ht[0]和ht[1]），所以在这期间对于哈希表的查询操作会在这两张表上进行。比如想要查询一个key，那么Redis会先在ht[0]上查询，如果没有才会到ht[1]上查询。但是这个时候新增的key，也会直接保存到新的哈希表ht[1]中去，而对于ht[0]，不会在添加任何地key上去，这样慢慢地ht[0]就会变成空的哈希表。

rehash触发条件

Redis什么时候才会进行rehash呢？

扩容

在源码dict.c第958行有这么一个函数_dictExpandIfNeeded：

/* 如果需要，扩展哈希表 */
static int _dictExpandIfNeeded(dict *d){
    /* 如果正在rehash那么就直接返回 */
    if (dictIsRehashing(d)) return DICT_OK;
    /* 如果哈希表为空，则将其扩展到初始大小 */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    /* 如果哈希表ht[0]中保存的key个数与哈希表大小的比例已经达到1:1，即保存的节点数已经大于等于哈希表大小，
     * 并且当前redis的服务允许执行rehash（此时Redis没有在执行`bgsave`或者`bgrewiteaof`命令的时候）。
     * 或者保存的节点数与哈希表大小的比例超过了安全阈值（默认值为5），
     * 则将哈希表大小扩容为原来的两倍 */
    if ((dict_can_resize == DICT_RESIZE_ENABLE &&
         d->ht[0].used >= d->ht[0].size) ||
        (dict_can_resize != DICT_RESIZE_FORBID &&
         d->ht[0].used / d->ht[0].size > dict_force_resize_ratio)){
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

从上面源码中的注释可以看到rehash触发条件主要有两个：

1. 当used>=size（哈希表中已经使用了的节点数量大于等于哈希表的大小）并且此时Redis没有在执行bgsave或者bgrewiteaof命令时，会触发rehash。
2. 或者当used/size>dict_force_resize_ratio（哈希表中已经使用了的节点数量和哈希表的大小的比例超过5）时，不管此时Redis是否在执行bgsave或者bgrewiteaof命令，都会强制进行rehash操作。

缩容

在数据量增加的时候，Redis会进行rehash，这个时候是扩容2倍，那么当数据减少的时候呢？

Redis在数据量减少的时候也会进行缩容，以便节约空间。在源码server.c第1700行有databasesCron这么一个函数用来处理Redis数据库中我们需要增量执行的“后台”操作，例如活动键过期、resize、rehash等。这里主要看resize部分：

void databasesCron(void) {
    /* 通过随机抽样使键过期。对于Slave服务器来说不需要，因为Master服务器会同步DEL命令。*/    
    if (server.active_expire_enabled) {
        if (iAmMaster()) {
            activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
        } else {
            expireSlaveKeys();
        }
    }
    /* 逐步对键进行碎片整理。 */
    activeDefragCycle();
    /* 在没有BGSAVE或者BGREWRITEAOF执行时，对哈希表进行 rehash */
    if (!hasActiveChildProcess()) {
        /* 使用全局计数器，这样如果在给定的DB上停止计算，我们就能在下一个定时任务从后续的DB开始*/
        static unsigned int resize_db = 0;
        static unsigned int rehash_db = 0;
        int dbs_per_call = CRON_DBS_PER_CALL;
        int j;
        /* 不能超过拥有的DB最大数量 */
        if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;
        /* Resize调整大小 */
        for (j = 0; j < dbs_per_call; j++) {
            tryResizeHashTables(resize_db % server.dbnum);
            resize_db++;
        }
        /* Rehash */
        if (server.activerehashing) {
            for (j = 0; j < dbs_per_call; j++) {
                int work_done = incrementallyRehash(rehash_db);
                if (work_done) {
                    /* 如果已经rehash了一部分，在这里停止并在下一个计划循环中继续进行。*/
                    break;
                } else {
                    /* 如果这个DB不需要rehash，接着尝试下一个*/
                    rehash_db++;
                    rehash_db %= server.dbnum;
                }
            }
        }
    }
}

可以看到缩容的时候也会选在没有bgsave或者bgrewiteaof执行的时候。可以看到主要是tryResizeHashTables这个函数在调整大小，这个函数源码在server.c第1436行：

int htNeedsResize(dict *dict) {
    long long size, used;
    size = dictSlots(dict);
    used = dictSize(dict);
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}
/* 如果哈希表中已用槽位的百分比达到 HASHTABLE_MIN_FILL，我们会重新调整哈希表的大小，以节省内存 */
void tryResizeHashTables(int dbid) {
    if (htNeedsResize(server.db[dbid].dict))
        dictResize(server.db[dbid].dict);
    if (htNeedsResize(server.db[dbid].expires))
        dictResize(server.db[dbid].expires);
}

HASHTABLE_MIN_FILL和DICT_HT_INITIAL_SIZE分别定义在server.h第168行和dict.h第76行中：

/* 每个hashtable的初始大小 */
#define DICT_HT_INITIAL_SIZE     4
/* 哈希表参数 */
#define HASHTABLE_MIN_FILL        10      /* 最小哈希表填充 10% */

可以看到HASHTABLE_MIN_FILL和DICT_HT_INITIAL_SIZE分别是10和4，那么从htNeedsResize就可以得知当哈希表的大小大于初始容量且保存的key数量与哈希表的大小的比例小于0.1的时候需要缩容。