渐进式解析 Redis 源码 - 字典

2018-11-13 阅读量

字典是构建 Redis 底层结构的重要数据结构，比如命令表 commands、数据库、哈希键等，尤其数据库部分，对数据库的增、删、查、改都是建立在对字典的操作上

字典是一种保存键值对的抽象数据结构；在字典中，一个键 key 与一个值 value 进行关联，组成键值对，一般又称符号表 / 关联数组 / map 映射等；字典中的键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对等等；通常高级语言都会内置实现好的字典数据结构，比如 PHP 的关联数组、Java 的 MAP 等都是如此

在 Redis 中，比较典型的例子比如命令 SET foo1 test，即为操作 key 为 foo1 的字典；而哈希类型的数据，比如 HMSET person name "kety" age 20 weight "75kg" height 20，即为操作 key 为 person 的字典，而值也是由字典结构数据组成，key=name | key=age | key=weight | key=height

字典数据结构

Redis 字典模块主要由 dict 、 dictht 、 dictEntry 三个结构组成，当然还有一个标记数据类型的 dictType

// 字典结构
typedef struct dict {
    // 字典类型，保存一些用于操作特定类型键值对的函数，跟 下面的 privdata 一样都是为了实现 多态性字典而设置的为 特殊类型数据服务的
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表，一般有两部分，正常哈希表数据部分 + rehash重置哈希表的暂存数据部分
    dictht ht[2];
    /* 是否正在进行哈希重置，默认为不重置 rehashidx == -1 */
    long rehashidx;
    /* 正在运行的迭代器数 */
    unsigned long iterators;
} dict;
// 哈希表结构
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表长度
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值，一般是 size-1
    unsigned long sizemask;
    // 已经使用的哈希表节点数量
    unsigned long used;
} dictht;
// 哈希表节点结构
typedef struct dictEntry {
    // 键值
    void *key;
    // 数据内容，不过依然支持多态，可以存储 指针、int 、double 多种类型
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一个 hash 节点的地址；因为 哈希表使用了 链地址法 解决冲突，所以这里为一个链表；关于 hashtable 我们在 http://www.web-lovers.com/memcached-source-storage.html#%E4%BB%80%E4%B9%88%E6%98%AFhashtable 已经有过介绍
    struct dictEntry *next;
} dictEntry;
// 字典类型，存储各种类型对应的操作函数
typedef struct dictType {
    // 计算 hash 值函数
    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;

由下图可以看出各个数据结构的关系
Redis 字典

字典 dict 结构中 ht[0]、ht[1] 每个代表一个 dictht 哈希表，一般情况下只使用 ht[0] 哈希表，只有在 rehash 的时候才使用 ht[1]，同时 rehashidx 也记录了当前 rehash 进度，默认没有 rehash 的时候 rehashidx=-1；
而 rehash 操作是因为随着操作不断的执行保存的键值对不断增多或者减少，为了保证负载因子( load factor = ht[0].used / ht[0].size ) 始终维持在一个合理的范围内，当键值对数量太大或者太小的时候对哈希表进行扩展或者收缩；rehash 的步骤如下：
- 为 ht[1] 哈希表分配空间，分配空间大小取决于要执行的操作，以及 ht[0] 键值对数量（ht[0].used）；如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2ⁿ；如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2ⁿ
- 将所有 ht[0] 中的键值对 rehash 到 ht[1] 上，rehash 就是重新计算哈希值和ht[1] 上的位置
- 当 ht[0] 上的所有键值对都转移到 ht[1] 上的时候，释放 ht[0] 空表，将 ht[1] 命名为 ht[0]，重建空白 ht[1]，等待下一次 rehash
- rehash 的过程跟我们的教程一样，都是渐进式的，分多次的，特别是有上亿键值对的时候
  - 为 ht[1] 分配空间，同时持有 ht[0] 和 ht[1] 两个表
  - 在字典中维持一个索引计数器 rehashidx，设置为0，代表 rehash 操作正式开始
  - 在 rehash 期间，每次对字典进行增删改查的时候，程序除了本身应该做的增删改查运算，还会顺带将 ht[0] 上的 rehashidx 索引的键值对转移到 ht[1]，当此次 rehash 操作过后，rehashidx 增加1
  - 随着字典操作的不断执行，ht[0] 上所有键值对都会转移到 ht[1] 上，rehashidx 设置为 -1
  - 当然，在 rehash 期间，肯定还会有对数据的增删改查操作，如果是删改查操作，则会同时操作 ht[0] 和 ht[1]，而如果是增加操作，则只能在 ht[1] 上
哈希表ht（什么是hashtable ）使用的是 链地址法 解决 hash冲突问题，所以 dictEntry* 为链表结构，每个 dictEntry 节点都会有一个 next 属性存储下一个节点位置，这里有个地方需要注意，每次链表上的节点插入都是头插法 ；而 sizemask 属性的值用来计算 hash 值，决定放在 hashtable 的哪个位置上，一般属性值为 size - 1
哈希表节点 dictEntry 的 v 属性支持多态性，多个字段可以存储指针 / int / double 多种类型
字典 dict 中 type 和 privadata 属性都是为多态字典而设立的，type 属性结构体为 dictType，保存了一簇用于操作指定类型键值对的函数，而 privdata 属性则保存的需要传给 type 指定函数的可选参数

下面我们就 Redis 字典的一些典型的 API 进行解析~~~

源码解析

由于有些方法里的代码量比较大，我们这里按照典型的代码片段进行解析，同志们可以根据文章提示的代码位置和代码里面的关键词在源码中搜素，可能数据结构一些元素看不太懂什么意思，没关系，先混个脸熟，后面看完回头再看过来就明白了

dict创建函数为 dictCreate()，主要逻辑为申请空间、初始化属性

添加键值对相关函数 dictAdd()、dictAddRaw()、dictReplace()

dictAdd() 为添加键值对主函数，dictAddRaw() 为添加只有 key 的键值对方便后续赋值

/* dict.c: line 265 */
// 添加键值对主函数
int dictAdd(dict *d, void *key, void *val)
{
    // 添加一个 只有 key 的键值对，即 空值的 字典
    dictEntry *entry = dictAddRaw(d,key,NULL);
    if (!entry) return DICT_ERR;
    // 设置字典键值，这里需要注意一下 val 的结构类型为 robj，内容则存于 robj->ptr
    dictSetVal(d, entry, val);
    return DICT_OK;
}
// 添加 只有 key 的键值对
// 传递 existing 参数是为了获取 节点 dictEntry 地址，这个目前一般都是在 replace 的时候使用
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;
    // 如果正在进行 rehash，那么先执行 rehash，这点儿验证了上面我们说的 rehash 是随着其他操作进行的
    if (dictIsRehashing(d)) _dictRehashStep(d);
    /* Get the index of the new element, or -1 if
     * the element already exists. */
    // 查找 hashtable 的索引地址，如果键值对已经存在则返回 -1，如果不存在返回 hashtable 索引地址
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;
    /* Allocate the memory and store the new entry.
     * Insert the element in top, with the assumption that in a database
     * system it is more likely that recently added entries are accessed
     * more frequently. */
    // 如果 正在进行 rehash 即取 ht[1]，否则取 ht[0]
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 申请节点
    entry = zmalloc(sizeof(*entry));
    // 头插法，将 节点插入到 哈希表相对应位置链表的前端
    entry->next = ht->table[index];
    ht->table[index] = entry;
    // used 增加
    ht->used++;
    /* Set the hash entry fields. */
    // 为 节点添加 key 值
    dictSetKey(d, entry, key);
    return entry;
}

_dictKeyIndex() 获取 key 在 hashtable 所在的索引地址

/* dict.c: line 961 */
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    // 如果 existing 存在则 置位空，这个就是为了通过 指针方式 带回 dictEntry 节点地址
    if (existing) *existing = NULL;
    /* Expand the hash table if needed */
    // 如果需要的话扩展哈希表，有两种情况 空表 和 扩展因子比较大的时候
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    // 处理 ht[0] 和 ht[1]
    for (table = 0; table <= 1; table++) {
        // 获取哈希表位置
        idx = hash & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        // 获取哈希表对应位置的链表开头地址
        he = d->ht[table].table[idx];
        // 循环链表，查找 key 值
        while(he) {
            // dictCompareKeys 这个宏其实有两种情况，如果定义了多态 type 的 keyCompare 函数就使用，如果没有就直接对比 key 字符串
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                // 如果有传递 existing 指针，则返回首地址节点，不过这里一般使用在 key 已经存在的情况
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        // 如果没有正在进行 rehash，则不用遍历 ht[1]
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

dictReplace() 函数主要是将指定的键值对添加到字典里，如果键已经存在于字典中，那么新值取代原值

/* dict.c: line 961 */
int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, *existing, auxentry;
    /* Try to add the element. If the key
     * does not exists dictAdd will suceed. */
    // 添加只有 key 的键值对
    entry = dictAddRaw(d,key,&existing);
    // 如果已经存在返回 entry 返回的是 NULL，如果不存在 返回新建的 节点
    if (entry) {
        // 设置值
        dictSetVal(d, entry, val);
        return 1;
    }
    /* Set the new value and free the old one. Note that it is important
     * to do that in this order, as the value may just be exactly the same
     * as the previous one. In this context, think to reference counting,
     * you want to increment (set), and then decrement (free), and not the
     * reverse. */
    // 原节点地址
    auxentry = *existing;
    // 设置新值
    dictSetVal(d, existing, val);
    // 释放旧值
    dictFreeVal(d, &auxentry);
    return 0;
}

查找键值对相关函数 dictFind()、dictFetchValue()、dictGetRandomKey()

dictFind() 为查找 dictEntry 节点函数，dictFetchValue() 为查找值函数

/* dict.c: line 961 */
// 查找 dictEntry 节点
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; /* dict is empty */
    // 如果正在进行 rehash，那么先执行 rehash，这点儿验证了上面我们说的 rehash 是随着其他操作进行的
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // 获取 hash 结果值
    h = dictHashKey(d, key);
    // 遍历 ht[0] 和 ht[1]
    for (table = 0; table <= 1; table++) {
        // 计算所处 哈希表索引地址
        idx = h & d->ht[table].sizemask;
        // 哈希表索引对应的链表开头地址
        he = d->ht[table].table[idx];
        while(he) {
            // dictCompareKeys 这个宏其实有两种情况，如果定义了多态 type 的 keyCompare 函数就使用，如果没有就直接对比 key 字符串
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        // 如果没有正在进行 rehash，则不用遍历 ht[1]
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}
// 查找节点值
void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;
    // 查找 dictEntry 节点
    he = dictFind(d,key);
    // 获取 dictEntry 节点值
    return he ? dictGetVal(he) : NULL;
}

dictGetRandomKey() 随机获取键值对

/* dict.c: line 610 */
dictEntry *dictGetRandomKey(dict *d)
{
    dictEntry *he, *orighe;
    unsigned long h;
    int listlen, listele;
    // 如果是空表
    if (dictSize(d) == 0) return NULL;
    // 如果正在进行 rehash，那么先执行 rehash，这点儿验证了上面我们说的 rehash 是随着其他操作进行的
    if (dictIsRehashing(d)) _dictRehashStep(d);
    if (dictIsRehashing(d)) {
        // 如果正在 rehash，则需要从 ht[0] 和 ht[1] 两个表中进行着手
        do {
            /* We are sure there are no elements in indexes from 0
             * to rehashidx-1 */
            // 正在 rehash 的时候，0 ~ rehashidx-1 中是没有数据的，所以获取随机 链表地址的时候 是从 rehashidx 开始的
            h = d->rehashidx + (random() % (d->ht[0].size +
                                            d->ht[1].size -
                                            d->rehashidx));
            // 如果获取的 h 位置 大于 ht[0].size 则从 ht[1] 中获取，否则从 ht[0] 中获取
            he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
                                      d->ht[0].table[h];
        } while(he == NULL);
    } else {
        // 如果没有 rehash，则从 ht[0] 中获取
        do {
            // 获取随机 idx 值
            h = random() & d->ht[0].sizemask;
            // 获取哈希表 idx 位置的地址
            he = d->ht[0].table[h];
        } while(he == NULL);
    }
    /* Now we found a non empty bucket, but it is a linked
     * list and we need to get a random element from the list.
     * The only sane way to do so is counting the elements and
     * select a random index. */
    listlen = 0;
    orighe = he;
    // while 循环 索引位置链表的长度
    while(he) {
        he = he->next;
        listlen++;
    }
    // 随机获取链表的一个位置
    listele = random() % listlen;
    he = orighe;
    // 获取随机位置的链表节点数据
    while(listele--) he = he->next;
    return he;
}

键值对相关函数 dictDelete()、dictDeleteNoFree()、dictGenericDelete()

dictDelete() 为节点删除主函数，不过实际执行函数为 dictGenericDelete()

/* dict.c: line 364 */
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;
    // 空表，返回 NULL
    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
    // 如果正在进行 rehash，那么先执行 rehash，这点儿验证了上面我们说的 rehash 是随着其他操作进行的
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // 获取 key 的 hash 值
    h = dictHashKey(d, key);
    // 遍历 ht[0] 和 ht[1]
    for (table = 0; table <= 1; table++) {
        // 计算在哈希表的位置 idx
        idx = h & d->ht[table].sizemask;
        // 节点链表
        he = d->ht[table].table[idx];
        prevHe = NULL;
        // 遍历节点链表的所有 节点
        while(he) {
            // dictCompareKeys 这个宏其实有两种情况，如果定义了多态 type 的 keyCompare 函数就使用，如果没有就直接对比 key 字符串
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                /* Unlink the element from the list */
                // 解链
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                // 释放
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                    zfree(he);
                }
                d->ht[table].used--;
                return he;
            }
            prevHe = he;
            he = he->next;
        }
        // 如果 正在进行 rehash 即取 ht[1]，否则取 ht[0]
        if (!dictIsRehashing(d)) break;
    }
    return NULL; /* not found */
}

字典删除相关函数 dictRelease()、_dictClear()

dictRelease() 为字典删除的主函数，主要逻辑为清除 ht[0] 和 ht[1]、释放字典，而 _dictClear() 为清除函数

/* dict.c: line 442 */
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
    unsigned long i;
    // 循环 free 所有节点
    /* Free all the elements */
    for (i = 0; i < ht->size && ht->used > 0; i++) {
        dictEntry *he, *nextHe;
        // 处理私有数据，(i & 65535) == 0 是为了跳过 0 的位置
        if (callback && (i & 65535) == 0) callback(d->privdata);
        // 跳过空链表
        if ((he = ht->table[i]) == NULL) continue;
        // 遍历链表节点
        while(he) {
            nextHe = he->next;
            // 释放key对象
            dictFreeKey(d, he);
            // 释放节点值对象
            dictFreeVal(d, he);
            // 释放节点
            zfree(he);
            ht->used--;
            he = nextHe;
        }
    }
    /* Free the table and the allocated cache structure */
    zfree(ht->table);
    /* Re-initialize the table */
    // 重置字典结构
    _dictReset(ht);
    return DICT_OK; /* never fails */
}

rehash算法主要有两种方式：

一种为上面我们经常会提到的跟随其他操作的 rehash，调用的是 _dictRehashStep() 函数，我们一般常用的还是这种

/* dict.c: line 160 */
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

另外一种为定时循环进行 rehash 操作，函数为 dictRehashMilliseconds()

/* dict.c: line 241 */
int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;
    while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

不过无论哪种方式的 rehash 操作，最终还是调用了 dictRehash() 函数，返回 0 代表已经完全转移完毕，返回1 代表未转移完毕

/* dict.c: line 188 */
int dictRehash(dict *d, int n) {
    // 访问空位置次数最大值，以为 rehash 转移都是 一部分一部分转移的，因为有一些位置是空的，所以并不能保证每一步都至少有一个位置转移，所以我们规定这个操作只能访问最多 n*10 个空位置，否则太多遍历会造成阻塞时间过久
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    // 如果没有进行 rehash，则直接返回
    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 */
        // rehashidx不能大于哈希表大小
        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 */
            // 通过重新计算 hash 确定在 ht[1] 中的新位置
            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) {
        // 释放 ht[0]
        zfree(d->ht[0].table);
        // ht[1] 改成 ht[0]
        d->ht[0] = d->ht[1];
        // 重置 ht[1] 和 rehashidx，留作下次使用
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }
    /* More to rehash... */
    return 1;
}

本文作者： wettper
本文链接： http://www.web-lovers.com/redis-source-dict.html
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！

字典 数据结构

源码解析

字典数据结构