Redis 的底层数据结构（跳跃表）

字典相对于数组，链表来说，是一种较高层次的数据结构，像我们的汉语字典一样，可以通过拼音或偏旁唯一确定一个汉字，在程序里我们管每一个映射关系叫做一个键值对，很多个键值对放在一起就构成了我们的字典结构。

有很多高级的字典结构实现，例如我们 Java 中的 HashMap 底层实现，根据键的 Hash 值均匀的将键值对分散到数组中，并在遇到哈希冲突时，冲突的键值对通过单向链表串联，并在链表结构超过八个节点裂变成红黑树。

那么 redis 中是怎么实现的呢？我们一起来看一看。

一、字典结构定义

Redis 中的字典相关结构都定义在 dict.h 文件中，dict 表示一个字典结构：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx;
    unsigned long iterators;
} dict;

其中，type 字段指向 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;

hashFunction 哈希函数指针，当我们通过 set 命令往字典中存储数据时，会先用键值对的键作为参数传入哈希函数，得到一个较为散列均匀的值，然后才会实际的进行数据的存储。这里就会用到哈希函数，如果你需要为你的字典结构提供不同的散列方式，在初始化字典的时候为 dictType 中哈希函数进行一个实现就好。

keyDup 是一个键的复制函数，valDup是一个键值对的值的复制函数，keyCompare 是一个键的比较大小的函数，keyDestructor 销毁一个键，valDestructor 销毁一个键值对的值。都是一个多态的呈现，具体实现需要使用者自行提供。

接着看 dict 结构，privdata 指针存储了字典结构一些附属额外信息，ht 是一个 dictht 结构的数组，dictht 就是一个哈希表结构，我们等下看这个结构。rehashidx 字段用于 rehash 过程中记录正在转移的键。iterators 字段记录了当前字典正在进行中的迭代器，具体的再看。

dictht 就是我们的哈希表结构，

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

table 是一个指向 dictEntry 的二维数组，每个 dictEntry 其实就表述一个键值对，为什么是一个二维的结构呢？

其实正常情况下，我们的字典是这样保存数据的：

每个 dictEntry 内部会保存一个 key/value 的键值对，然后我们通过 table 指针可以遍历所有的键值对，但是如果某个键值对的键进行哈希之后并计算得到应该存储的位置被别的节点捷足先登了，也就是我们常说的哈希冲突了，怎么办？

redis 中的做法，甚至于大部分字典结构实现都是选择将冲突的节点串联成链表，于是字典结构就变成这样了。

同一条链表上的节点键的哈希值必定是相同的，也正是因为相同才会被串在一起，从逻辑上看，字典结构如上图所展示的那样，但抽象到我们的代码层，就是一个二维数组的结构，第一维放的就是节点指针的指针，第二维指向的就是指向我们键值对结构的指针，每一个 dictEntry 结构都会有一个 next 指针，在遇到哈希冲突的时候可以串联所有冲突节点。

除此之外，dictht 中的 size 属性用于描述整个哈希字典表最大可寻址大小，也就是二维数组中第一维度的最大长度，sizemask 属性始终等于 size-1 表述的是一种大小掩码的概念，用于确定节点最初在数组中的位置，used 记录了整张哈希表中已经存储的键值对节点数量。

其中，dict 字典结构中 ht 是一个只有两个元素的数组，正常情况下我们使用 ht[0] 字典表，ht[1] 用在我们渐进 rehash 过程中转移 ht[0] 中所有节点中。

最后，我们再来看这个 dictEntry 键值对结构：

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

key 是一个指向任意结构的指针，代表我们的 key 可以使用我们 redis 中任意对象类型，v 是一个 union 类型，它可以是一个指针，也可以是 uint64_t 或 int64_t 类型，也可以是一个 double 类型。根据实际使用中，value 的不同值，使用不同的字段属性。

next 指针指向另一个 dictEntry 结构，用于发生哈希冲突时，链接下一个键值对节点。

以上就是 redis 中字典结构主要结构类型，从里至外封装了三层，dict 描述一个字典，其中的 dictht 描述哈希表，其中的 dictEntry 描述键值对结构。迭代器回头我们单独说说。

二、渐进式 rehash 迁移数据

redis 的 rehash 和 Java 以及其他哈希的实现稍微可能有点不同，由于 redis 是单线程的，不需要写大量的并发语句来保证数据一致性，但是单线程处理也会导致一次 rehash 过程会非常缓慢，客户端阻塞太久。那么 redis 具体是怎么做的呢？

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;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        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];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            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++;
    }

    /* Check if we already rehashed the whole table... */
    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;
    }

    /* More to rehash... */
    return 1;
}

rehashidx 的值默认为 -1，表示当前字典未处于 rehash 阶段，其他场合该字段的值等于当前正在转移桶的索引。

新版本的 dictRehash 需要多传一个参数 n，这个参数用于控制单次最多转移空桶数量。什么意思呢，具体我们看一张图：

有这么一个字典结构，其中索引值为 2 和 3 的两个桶是空的，也即里面没有放我们的键值对节点。正常情况下，一次 rehash 只会转移一个桶，但如果上一次转移了索引为 1 的那个桶，下一次来会遍历后面一个桶，如果继续为空就继续向后遍历，直到找到一个存储了我们节点的非空桶，极端情况下，如果字典表中只有最后一个桶有节点，那么一次的 rehash 就要遍历所有的桶，时间复杂度 O(n)，这会导致客户端等待过长时间，所以新版本中额外传一个参数 n 用于控制最多遍历的空桶数。

相关代码段如下：

while(d->ht[0].table[d->rehashidx] == NULL) {
    d->rehashidx++;
    if (--empty_visits == 0) return 1;
}

方法的尾部会进行一个校验，如果当前桶转移结束后，当前字典的 rehash 过程完全结束，那么修改 ht[0] 指针引用，让他指向新的字典表 ht[1]，并设置 rehashidx 为 -1，标记整个字典 rehash 结束。

以上就是 redis 中 rehash 的全过程，还是比较简单的，那为什么说它是渐进式的呢，我们看一下添加和查询键值对的方法。

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

    if (dictIsRehashing(d)) _dictRehashStep(d);

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

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

这就是我们调用 set 命令，底层为我们添加键值对的方法，函数的最开头逻辑就是调用 dictIsRehashing 方法判断当前的字典表是否处于 rehash 状态，也即判断 rehashidx 是否不等于 -1 了。_dictRehashStep 方法实现：

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

默认情况下，一次 rehash 过程，redis 允许最多 10 空桶的访问就要返回，不得逗留。值得注意的是，方法的后续逻辑会判断当前字典如果正在进行 rehash，那么新的键值对将不再向 ht[0] 中添加，而直接转而添加到 ht[1] 中。

我们再看看查询键值对的 get 命令底层 API 调用，底层会调用 dictFind 方法。

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

    if (d->ht[0].used + d->ht[1].used == 0) return NULL;
    if (dictIsRehashing(d)) _dictRehashStep(d);
    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;
}

可以看到，同样也是有 dictIsRehashing 方法的判断，如果字典处于 rehash 状态，即需要去完成一个桶的转移，然后才能返回。值得注意的是，方法的中间逻辑是嵌套在一个 for 循环中的，供两次循环，第一次从 ht[0] 中搜索我们给定 key 的键值对，如果没有找到，第二次循环将从 ht[1] 中搜索我们要查询的键值对。

之所以说 redis 的 rehash 是渐进式的，就是因为即便它处于 rehash 状态下，所有节点的插入、查询甚至于删除都是不受影响的，直至整个 rehash 结束，redis 释放原先 ht[0] 占用无用内存。

ps：redis 中的字典实现相对于 Java 中的实现要简单不少，主要还是因为 redis 是单线程调用的，不需要使用额外的并发语句控制。

三、字典迭代器

迭代器是用于迭代遍历字典中所有的节点的一个工具，有两种，一种是安全迭代器，一种是不安全迭代器。安全迭代器就是指，你在迭代的过程中，允许你对字典结构进行修改，也即允许你添加、删除、修改字典中的键值对节点。不安全迭代器即不允许对字典中任何节点进行修改。

dictIterator 结构的定义如下：

typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;
} dictIterator;

字段 d 指向一个即将被迭代的字典结构，index 记录了当前迭代到字典中的桶索引，table 取值为 0 或 1，表示当前迭代的是字典中哪个哈希表，safe 标记当前迭代器是安全的或是不安全的。 entry 记录的是当前迭代的节点，nextEntry 的值等于 entry 的 next 指针，用于防止当前节点接受删除操作后续节点丢失情况。fingerprint 保存了 dictFingerprint 函数根据当前字典的基本信息计算的一个指纹信息，稍有一丁点变动，指纹信息就会发生变化，用于不安全迭代器检验。

安全迭代器获取方式：

dictIterator *dictGetIterator(dict *d)
{
    dictIterator *iter = zmalloc(sizeof(*iter));

    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

不安全迭代器获取方式：

dictIterator *dictGetSafeIterator(dict *d) {
    dictIterator *i = dictGetIterator(d);

    i->safe = 1;
    return i;
}

下面我们看看迭代器的核心方法，dictNext 用于获取字典中下一个节点。

dictEntry *dictNext(dictIterator *iter)
{
    while (1) {
        //如果迭代器初次工作，entry 必定为 null
        if (iter->entry == NULL) {
            //拿到迭代器 d 字段保存的字典
            dictht *ht = &iter->d->ht[iter->table];
            if (iter->index == -1 && iter->table == 0) {
                if (iter->safe)
                    //给字典的 iterators 字段自增，禁止 rehash操作
                    iter->d->iterators++;
                else
                    //计算并保存指纹信息
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            //迭代器开始工作，指向 0 号桶
            iter->index++;
            //如果 index 大于等于 size，即最后一个桶迭代结束
            if (iter->index >= (long) ht->size) {
                if (dictIsRehashing(iter->d) && iter->table == 0) {
                    //当前字典结构正在 rehash 且 ht[0] 已经遍历结束
                    //继续遍历 ht[1]
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                } else {
                    //否则表示迭代工作确实全部结束
                    break;
                }
            }
            //根据 index 取出节点
            iter->entry = ht->table[iter->index];
        } else {
            //如果 entry 不等于 null，尝试遍历它的后续节点
            iter->entry = iter->nextEntry;
        }
        //到这里，迭代器已经拿到下一个节点了
        if (iter->entry) {
            //记录 nextEntry 节点的值
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }
    return NULL;
}

大部分逻辑都已经注释上了，整个方法是一个死循环，如果 entry 等于 null，要么是迭代器初次工作，要么是迭代到一个桶的最后节点处了。如果是后者，会进入 if 逻辑中，判断是否整个字典全部迭代结束，如果不是取下一个桶。

如果字典未处于 rehash 状态，自增 iterators 属性的操作会禁止后续节点操作触发 rehash，如果已经处于 rehash 过程了，也不慌，当前 ht[0] 迭代结束后，再去迭代早于迭代器工作前已经被转移到 ht[1] 的那些节点。因为如果你是安全迭代器的话，iterators 一自增之后，后续节点就不会触发 rehash 迁移节点，所以不会重复迭代数据。

迭代器迭代结束之后需要释放关闭释放迭代器，redis 中对应方法：

void dictReleaseIterator(dictIterator *iter)
{
    if (!(iter->index == -1 && iter->table == 0)) {
        if (iter->safe)
            iter->d->iterators--;
        else
            assert(iter->fingerprint == dictFingerprint(iter->d));
    }
    zfree(iter);
}

如果是安全的迭代器，自减 iterators，不安全迭代器会重新计算指纹并与迭代器最开始工作时计算的指纹比较，并通过 assert 断言判断指纹是否一致，如果不一致则说明你在不安全的迭代器中执行了修改字典结构的方法，程序报错并退出。

以上就是 redis 字典中基础的两个安全与非安全迭代器用法及其原理，终究是不允许边 rehash 边遍历的，其实 redis 中还有一种高级遍历方式，大家叫它 scan 遍历，它允许边 rehash 边迭代，比较高级，我们后续会分析它的源码，敬请期待！

---