Redis 源码实现美文共赏

redis 源码分析（一）HashTable 上篇

2019-08-02  本文已影响0人  猿来是八阿哥

转载请注明出处：https://www.jianshu.com/p/a57a6e389a03

redis 中的 HashTable 实现，是一个叫 dict 的结构体以及其相关的操作函数。本文将对 dict 中重要的结构体、操作方法进行介绍，阐述其实现逻辑，对于 redis 生命周期内对 dict 的其他操作，我会进一步的补充。另外，为了让源码能被更好的理解，我在必要的地方进行了改写，虽然这样可能使得源码不再可以正确运行，甚至无法通过语法检测。

一、重要的结构体

1. dict 

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

2. 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;

3. dictht 

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

4. dictEntry 

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

二、重要的操作方法

1. dictCreate 用于创建一个空的 dict 

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 实例，这个 dict 的各个属性都处于初始值，甚至连 dict.dictht[0].table 和 dict.dictht[1].table 都还是 null。
此时的 dict 用 javascript 对象表示，有点儿像：

{
    "privdata": null,
    "rehashidx": -1,
    "iterators": 0,
    "dictType": {
        "hashFunction": function(key){return parse_int(key)%10;},
        "keyDup": function(privdata, key){},
        "valDup": function(privdata, value){return value;},
        "keyCompare": function(privdata, key1, key2){return key1===key2;},
        "keyDestructor": function(privdata, key){unset kye;},
        "valDestructor": function(privdata, obj){unset obj;}
    },
    "dictht": [
        {
            "size": 0,
            "sizemask": 0,
            "used": 0,
            "table": null,
        },
        {
            "size": 0,
            "sizemask": 0,
            "used": 0,
            "table": null,
        }
    ]
}

2.dictExpand 对 dict 进行“扩容”

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;
}
int dictExpand(dict *d, unsigned long size){
    if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR;
    dictht n;
    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;
}

由源码可见：

① dict.dictht[0] 触发增加容量的条件是：
② dict.dictht[0] 增加容量到多少：
③ 扩容意外：
④ 当 dict 扩容成功后，dict 将开启 rehash

3. dictAdd 向 dict 中存入一对 key=>value 

#define dictIsRehashing(d) ((d)->rehashidx != -1)
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing){
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;
    if (_dictExpandIfNeeded(d) == DICT_ERR) return -1;
    for (table = 0; table <= 1; table++) {
        idx = hash & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || d.dictType.keyCompare(d.privdata, key, he->key)) {
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){
    long index;
    dictEntry *entry;
    dictht *ht;
    if (dictIsRehashing(d)) _dictRehashStep(d);
    if ((index = _dictKeyIndex(d, key, d.dictType.hashFunction(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;
}
#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \
        (entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
    else \
        (entry)->v.val = (_val_); \
} while(0)
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;
}

由源码可以得到，在 dict 中存入一个键值对有两个步骤：

① 在 key 应该存放的位置，先放一个 v=null 的 dictEntry
② 如果放置空 dictEntry 成功，再对 dictEntry 进行赋值

需要注意的是：如果 dict 开启了 rehash，则 dictAdd 将会把 key=>value 存放到 dict.dictht[1].table 中

4. dictReplace 覆盖 key 的 value

int dictReplace(dict *d, void *key, void *val){
    dictEntry *entry, *existing, auxentry;
    if (entry) {
        dictSetVal(d, entry, val);
        return 1;
    }
    auxentry = *existing;
    dictSetVal(d, existing, val);
    dict.dictType.valDestructor(&auxentry);
    return 0;
}

dictReplace 的实现和 dictAdd 的实现很相似，区别在于 dictReplace 会尝试调用 dict.dictType.valDestructor(&auxentry) 将被替换的值进行删除

5. dictRehash dictRehashMilliseconds 对 dict 进行 rehash

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;
}
int dictRehash(dict *d, int n) {
    int empty_visits = n*10;
    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;
}

由源码可知，redis rehash 的过程是：

6. dictFind 在 dict 中查找指定 key

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);
    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 || dict.dictType.keyCompare(key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

在 dict 中查找的过程相对简单：

7. dictGenericDelete 从 dict 中删除 key

static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;
    if (d->ht[0].used == 0 && 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];
        prevHe = NULL;
        while(he) {
            if (key==he->key || dict.dictType.keyCompare(d, key, he->key)) {
                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;
        }
        if (!dictIsRehashing(d)) break;
    }
    return NULL;
}

在 dict 中删除 key 就是在找到 key 所在 dictEntry 单向链表的结点后，执行链表的删除，同时更新 dict.dictht[0/1].used--

8. dictUnlink 在链表中删除 key 但不释放内存

void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {
    if (he == NULL) return;
    dictFreeKey(d, he);
    dictFreeVal(d, he);
    zfree(he);
}
dictEntry *dictUnlink(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,1);
}

dictUnlink 和 dictDelete 的区别是：是否立即释放要删除的 dictEntry 内存（注意：在 dictUnlink 时，其实已经完成了 dictEntry 的链表删除）。dictUnlink 的意义在于：在真正释放 dictEntry 前，可以执行用户逻辑，比如：输出一下 key 的 value，再删除。

entry = dictFind(key);
print entry.v;
dictDelete(key)

entry = dictUnlink(key);
print entry.v;
dictFreeUnlinkedEntry(entry);

两种写法的区别是：不使用 dictUnlink 时，在 dictFind 和 dictDelete 中分别执行了一次查询操作；使用 dictUnlink 时，只在 dictUnlink 中执行了一次查询操作。

9. dictRelease 删除并释放整个 dict 

int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
    unsigned long i;
    for (i = 0; i < ht->size && ht->used > 0; i++) {
        dictEntry *he, *nextHe;
        if (callback && (i & 65535) == 0) callback(d->privdata);
        if ((he = ht->table[i]) == NULL) continue;
        while(he) {
            nextHe = he->next;
            dict.dictType.keyDestructor(d, he);
            dict.dictType.valDestructor(d, he);
            zfree(he);
            ht->used--;
            he = nextHe;
        }
    }
    zfree(ht->table);
    _dictReset(ht);
    return DICT_OK;
}
void dictRelease(dict *d){
    _dictClear(d,&d->ht[0],NULL);
    _dictClear(d,&d->ht[1],NULL);
    zfree(d);
}

三、结论

四、设计问答

1. 为什么要对 dict 进行扩容？扩容后 rehash 的意义是什么？

dict.dictht.table 的默认大小是 4，当 key=>value 数据大于 4 时，必然出现多个 key 的 hash 值相同，在 dict.dictht[0].table 中的下标一致，从而导致 dict.dictht.table 其实是一个越来越长的链表，此时对 dict 的操作会退化为对链表的操作，即：时间复杂度从 O(1) 逐渐趋于 O(n)。对 dict 扩容后，使得存储相同数量 key=>value 时产生的 hash 冲突变少，从而链表长度变短，进而操作的 时间复杂度从 O(n) 逐渐趋于 O(1)

2. 为什么要 一次 rehash n 个下标，而不是一次性把所有下标都 rehash 完？

redis 是一个单线程（不考虑持久化线程）的应用，如果一次性 rehash 完所有下标，会导致 redis 在一定时间内无法提供服务，于是 redis 巧妙的将 这个一大段时间分摊到了每次操作这个 dict 都执行一部分的一小段时间，既保证了服务可用，又能完成 rehash 过程，提高性能。

3. 为什么扩容条件是 5 倍？为什么扩容到 大于 dict.dictht[0].used 2倍的第一个 2^n?

我猜测，5倍 应该是一个经验值，即避免了频繁扩容、hash导致的性能下降，又避免了 时间复杂度从 O(1) 逐渐趋于 O(n) 的可能。而扩容至 大于 dict.dictht[0].used 2倍的第一个 2^n 应该和选用的 Hash Function 有关，毕竟 redis 的 Hash Function 中大量使用了 << 和 '>>'

本来想在本篇中继续介绍 dict.iterator 以及 redis dict 相关命令的实现方式的，限于篇幅太长，会在 redis 源码分析（一）HashTable 下篇 中继续介绍，敬请期待。
另外，码字不易，喜欢的朋友点个赞，谢谢。

上一篇 下一篇

猜你喜欢

热点阅读