Redis字典设计详解

Redis 是一个高性能的  key-value 内存数据库，与  Memcached 只能存储字符串数据类型不一样，它支持存储的数据结构类型包括：字符串（string）、链表（lists）、哈希表（hash）、集合（set）、有序集合（zset）等。

Redis 的高性能得益于其  I/O事件驱动 模型，当然本文并不是讨论  Redis 的所有知识点，下面主要介绍  Redis 的核心数据结构： 字典 的设计和实现。

哈希表介绍

Redis 本质上就是在字典上挂载着各种数据结构，我们先来看看  字典 这种数据结构。Redis 中 的  字典  其实是就是  哈希表（HashTable） ，我们来看看  哈希表  的定义：

哈希表（HashTable）是根据键值(Key)而直接进行访问的数据结构。也就是说，它通过把键值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

先来看看 哈希表 数据结构的原理图：

上图比较清晰的描述了 哈希表 的原理，主要的步骤如下：

• 通过Hash函数把key映射到哈希表的某个位置

• 如果有不同的key被映射到同一个位置（冲突），采用拉链法（使用链表存储）来处理。

Redis字典介绍

Redis的字典基本遵从了哈希表的设计，当然在通用性和性能上改进了一些地方，下面我们来解释一下Redis字典的设计。

首先我们来看看在Redis中字典数据结构的定义：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

我们通过下图来整理一下这几个结构体的关系：

在Redis中，字典是通过结构体 dict 来表示的，而  dict 结构又会引用  dictht 和  dictEntry 这些结构，下面介绍一下这些结构体的各个字段作用。

dict结构

• type ：是用户自定义的函数列表，主要用于插入数据到字典时进行的一些操作，比如计算key哈希值的  hashFunction 函数句柄。

• privdata ：创建字典时指定的私有数据，一般提供给  type 字段中的函数句柄使用。

• ht[2] ：类型为  dictht 结构的数组，这个数组有两个元素，而  dictht 结构主要用于保存数据，至于为什么需要两个  dictht 结构是因为rehash的需要。

• rehashidx ：rehash操作过程中最后一次处理的桶索引。

• iterators ：用于迭代字典中的数据。

dictht结构

• table ：类型为  dictEntry 结构指针的数组，用于保存数据，每个  key-value 的数据对通过类型为  dictEntry 的结构来存储。

• size ：table数组的大小。

• sizemark ：用于取模，得到一个  0 ～ size 的索引值。

• used ：表示字典中有多少个元素。

dictEntry结构

• key ：数据的键，主要用于查找数据。

• v ：数据的值，数据主要通过这个字段来存储。

• next ：用于解决Hash冲突，把冲突的key连接起来（拉链法）。

字典的创建

接下来分析啊一下在Redis中怎么创建一个字典，创建一个字典是通过 dictCreate() 函数来实现的：

dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));

    _dictInit(d,type,privDataPtr);
    return d;
}

int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}

static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

dictCreate() 函数申请了一个类型为  dict 的结构，然后通过调用  _dictInit() 函数对其进行初始化操作，总体过程比较简单。下面来看看在Redis中怎么创建一个字典的：

dictType commandTableDictType = {
    dictSdsCaseHash,            /* hash function */
    NULL,                       /* key dup */
    NULL,                       /* val dup */
    dictSdsKeyCaseCompare,      /* key compare */
    dictSdsDestructor,          /* key destructor */
    NULL                        /* val destructor */
};

void initServerConfig(void) {
    ...
    server.commands = dictCreate(&commandTableDictType,NULL);
    ...
}

创建字典时，需要提供类型为 dictType 的参数，这个参数主要定义了插入数据到字典时进行的一些操作，比如插入数据时key是否要进行复制的keyDup函数，我们来看看  dictType 的定义：

typedef struct dictType {
    uint64_t (*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;

dictType 结构的每个字段都是一个函数指针，下面说明一下各个字段的作用：

• hashFunction ：用于计算键的哈希值

• keyDup ：用于复制数据的键

• valDup ：用于复制数据的值

• keyCompare ：用于比较键是否相等

• keyDestructor ：用于释放复制出来的键的内存

• valDestructor ：用于释放复制出来的值的内存

插入数据到字典

插入数据到字典是通过 dictAdd() 函数实现的，代码如下：

int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictAdd() 函数主要还是通过调用  dictAddRaw() 函数来完成插入操作， dictAddRaw() 函数的代码如下：

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d); // 如果需要rehash, 进行rehash操作

    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    dictSetKey(d, entry, key);
    return entry;
}

dictAddRaw() 函数主要完成以下几个工作：

• 判断是否正在进行rehash操作（ dictIsRehashing() 判断为真），如果是就调用  _dictRehashStep() 函数进行rehash。

• 通过调用 _dictKeyIndex() 函数计算key对应所在哈希表的位置（索引） index 。

• 如果正在rehash，那么就使用ht数组的第二个哈希表，否则就用第一个（原因下面会说明）。

• 创建一个 dictEntry 结构用于保存数据的键和值。

dictAddRaw() 函数会返回一个类型为  dictEntry 结构的值，然后  dictAdd() 函数通过调用  dictSetVal() 函数设置其值。

Rehash操作

当哈希表中的数据个数超过一定数量时，哈希冲突的链表过长，从而导致查询效率降低，这个时候就需要Rehash操作。Rehash操作是将哈希表的数组扩大，从而减少哈希冲突的比率。当然扩大哈希表的数组会导致之前的映射关系无效，所以需要把旧数据重新迁移到新的哈希表数组中。下面描述了Rehash的过程：

Redis在插入数据到字典时，会通过 _dictExpandIfNeeded() 函数来判断是否需要进行Rehash操作， _dictExpandIfNeeded() 函数代码如下：

static int _dictExpandIfNeeded(dict *d)
{
    if (dictIsRehashing(d)) return DICT_OK;

    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    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;
}

_dictExpandIfNeeded() 函数主要完成3个工作：

• 通过 dictIsRehashing() 来判断字典是否正在Rehash操作，如果是就直接返回OK，不需要再进行Rehash。

• 如果字典的第一个哈希表的大小为0，表示需要对第一个哈希表进行初始化。

• 如果第一个哈希表的元素个数大于等于哈希表的大小，那么就对第一个哈希表进行Rehash操作（把哈希表的大小扩大为原来的2倍）。

进行Rehash操作通过调用 dictExpand() 函数来完成， dictExpand() 函数代码如下：

int dictExpand(dict *d, unsigned long size)
{
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);

    if (realsize == d->ht[0].size) return DICT_ERR;

    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

dictExpand() 函数比较简单，就是申请一个更大的哈希数组，如果第一个哈希表的哈希数组为空，那么就把第一个哈希表的哈希数组设置为新的哈希数组。否则将第二个哈希表的哈希数组设置为新的哈希数组。

这里有个问题，为什么需要两个哈希表呢？这是因为如果哈希表的元素个数比较多的时候Rehash一次的时间会比较长，这样就有可能导致阻塞Redis的服务。所以Redis通过对数据分批Rehash的方式来解决这个问题，也就是说把一次长耗时的操作分为多次短耗时的操作，这样就不会对Redis的服务造成太大的影响。而分批Rehash的关键就在于第二个哈希表。

从 dictExpand() 函数的实现来看，并没有在这里对数据进行Rehash操作，只是把哈希数组扩大2倍而已，那么Rehash操作在什么时候进行呢？对数据进行Rehash操作的触发点有很多个，如插入、删除和查找，当然最后都会调用  dictRehash() 函数来完成，我们来看看  dictRehash() 函数的实现：

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        while(de) {
            uint64_t h;

            nextde = de->next;
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    return 1;
}

dictRehash() 函数的第二个参数是指定了每次要对多少个槽进行Rehash（也就是冲突链表），Rehash操作就是遍历第一个哈希表的所有数据，然后重新计算key的哈希值，保存到第二个哈希表中，并且从第一个哈希表中删除。当第一个哈希表的元素个数为0时，就将第一个哈希表替换成第二个哈希表，并且完成Rehash操作。

查找数据

要在字典中查找某个key的值通过 dictFind() 函数完成， dictFind() 函数代码如下：

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* 字典为空 */
    if (dictIsRehashing(d)) _dictRehashStep(d); // 是否需要进行rehash操作
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

通过上面的介绍， dictFind() 函数的实现也比较容易理解，主要进行了如下操作：

• 如果字典为空（第一个和第二个哈希表都为空），那么就返回NULL。

• 如果正在进行Rehash操作，那么就调用 _dictRehashStep() 对数据进行分批Rehash。

• 计算key的哈希值，并且先在第一个哈希表中查找是否存在，如果存在就返回key对应的值。

• 如果key不在第一个哈希表中，那么就要判断当前是否正在Rehash操作，如果是就在第二哈希表中查找key是否存在。因为在Rehash的过程中，key有可能被移动到第二个哈希表中。

总结

本文主要介绍了哈希表和Redis字典的设计与实现，Redis字典是对传统哈希表的一种扩展实现，能够减少Rehash操作对服务造成的阻塞。