redis 源码分析（二）HashTable 下篇

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

redis 源码分析（一）HashTable 上篇： https://www.jianshu.com/p/a57a6e389a03

本文主要介绍 redis HashTable dict 的迭代器部分，同时给出了关于 dict 所有 API 的简要功能介绍，最后列举了 redis 关于 HashTable 的几个命令实现。关于 redis HashTable 特性的介绍，其实在 redis 源码分析（一）HashTable 上篇 已经介绍的很清楚了，本文纯属个人对源码的兴趣，或许阐述的不够清楚，敬请谅解。

一、dictIterator dict 的迭代器

1. 结构体 dictIterator

typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    long long fingerprint;
} dictIterator;

• dictIterator.dict 指明当前迭代器正在迭代的 dict
• dictIterator.index 当前迭代到的 dict.dictht[0/1].table 的下标
• dictIterator.table 当前要迭代的 dict.dictht 的下标
• dictIterator.safe 当前迭代器是否是安全的
• dictIterator.entry 迭代器的当前 dictEntry
• dictIterator.nextEntry 迭代器的下一个 dictEntry
• dictIterator.fingerprint 开始迭代时 dict 的指纹

2. dictFingerprint 获取 dict 指纹

long long dictFingerprint(dict *d) {
    long long integers[6], hash = 0;
    int j;
    integers[0] = (long) d->ht[0].table;
    integers[1] = d->ht[0].size;
    integers[2] = d->ht[0].used;
    integers[3] = (long) d->ht[1].table;
    integers[4] = d->ht[1].size;
    integers[5] = d->ht[1].used;
    for (j = 0; j < 6; j++) {
        hash += integers[j];
        hash = (~hash) + (hash << 21);
        hash = hash ^ (hash >> 24);
        hash = (hash + (hash << 3)) + (hash << 8);
        hash = hash ^ (hash >> 14);
        hash = (hash + (hash << 2)) + (hash << 4);
        hash = hash ^ (hash >> 28);
        hash = hash + (hash << 31);
    }
    return hash;
}

• dict.dictht[0] 和 dict.dictht[1] 的 size used 以及 table 指针的地址，这6个信息参与了 dict 指纹的计算，我们可以理解：当 dict 发生变化时，dict 的指纹也会发生变化。

3. dictGetSafeIterator 和 dictGetIterator 获取 dict 的一个迭代器

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

• 安全迭代器 dictIterator.safe=1
• 不安全迭代器 dictIterator.safe=0
• 安全迭代器和不安全迭代器的区别是：不安全迭代器只能使用 dictNext 方法，安全迭代器能使用与 dict 相关的所有方法

4. dictNext 迭代器下一步

dictEntry *dictNext(dictIterator *iter){
    while (1) {
        if (iter->entry == NULL) {
            dictht *ht = &iter->d->ht[iter->table];
            if (iter->index == -1 && iter->table == 0) {
                if (iter->safe)
                    iter->d->iterators++;
                else
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            iter->index++;
            if (iter->index >= (long) ht->size) {
                if (dictIsRehashing(iter->d) && iter->table == 0) {
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                } else {
                    break;
                }
            }
            iter->entry = ht->table[iter->index];
        } else {
            iter->entry = iter->nextEntry;
        }
        if (iter->entry) {
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }
    return NULL;
}

dictNext 的逻辑是：

• 从 dictIterator.index 开始遍历 dictIterator.dict.dictht[dictIterator.table] 中的 dictEntry
• 如果 dictIterator.index >= dictIterator.dict.dictht[dictIterator.table].size && dictIterator.dict.rehashidx == -1 （迭代器的迭代下标大于等于正在迭代的 dict.dictht[dictIterator.table].size并且 dictIterator.dict 并没有处于 rehash 状态）时，说明迭代完成了。
• 如果 dictIterator.safe == 1 会 dictIterator.dict.iterators++ 即：dict.iterators 记录了自身 安全迭代器 的数量（因为不安全的迭代器不会改变 dict）
• 如果 dictIterator.safe == 0 会在第一次 dictNext 时通过 dictFingerprint 记录 dict 的指纹，当释放迭代器时，会比对当时的 dict指纹 和刚迭代时的 dict指纹，这样就能知道，在整个迭代过程中 dict 是否发生过改变

5. dictReleaseIterator 释放 dict 迭代器

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

dictReleaseIterator 的逻辑比较简单，除了释放自身所在内存外，还会 dict.iterators-- 以维护每个 dict 的迭代器数量

二、dict API 介绍

dict *dictCreate(dictType *type, void *privDataPtr);
int dictExpand(dict *d, unsigned long size);
int dictAdd(dict *d, void *key, void *val);
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing);
dictEntry *dictAddOrFind(dict *d, void *key);
int dictReplace(dict *d, void *key, void *val);
int dictDelete(dict *d, const void *key);
dictEntry *dictUnlink(dict *ht, const void *key);
void dictFreeUnlinkedEntry(dict *d, dictEntry *he);
void dictRelease(dict *d);
dictEntry * dictFind(dict *d, const void *key);
void *dictFetchValue(dict *d, const void *key);
int dictResize(dict *d);
dictIterator *dictGetIterator(dict *d);
dictIterator *dictGetSafeIterator(dict *d);
dictEntry *dictNext(dictIterator *iter);
void dictReleaseIterator(dictIterator *iter);
dictEntry *dictGetRandomKey(dict *d);
dictEntry *dictGetFairRandomKey(dict *d);
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count);
void dictGetStats(char *buf, size_t bufsize, dict *d);
uint64_t dictGenHashFunction(const void *key, int len);
uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len);
void dictEmpty(dict *d, void(callback)(void*));
void dictEnableResize(void);
void dictDisableResize(void);
int dictRehash(dict *d, int n);
int dictRehashMilliseconds(dict *d, int ms);
void dictSetHashFunctionSeed(uint8_t *seed);
uint8_t *dictGetHashFunctionSeed(void);
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction *bucketfn, void *privdata);
uint64_t dictGetHash(dict *d, const void *key);
dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash);

• dictCreate 初始化一个 dict（此时 dict.dictht[0].table 和 dict.dictht[1].table 都还是 null）
• dictExpand 对 dict 进行扩容（第一次对刚初始化的 dict 进行扩容时，会扩容到 4 个 dictEntry 大小）
• dictAdd 向 dict 中放入一对 key=>value（底层会调 dictAddRaw）
• dictAddRaw 在 dict.dictht[0/1].table key 应该存储的位置放一个空 dictEntry
• dictAddOrFind 和 dictAddRaw 的区别是：dictAddRaw 当 key 应该存储的位置上已经有 dictEntry 时会返回这个 dictEntry，而 dictAddRaw 则会报错
• dictReplace 替换 key 的 value。如果 key 不存在，等同于 dictAdd
• dictDelete 删除 key
• dictUnlink 删除 key，区别在于 dictDelete 会删除 key 对应的 dictEntry 所在列表后，立即释放掉 dictEntry，而 dictUnlink 则会将 dictEntry 返回，但用户使用完 dictEntry 后，需要手动调用 dictFreeUnlinkedEntry 释放
• dictFreeUnlinkedEntry 释放 dictUnlink 返回的 dictEntry
• dictRelease 删除并释放 dict （重点是需要释放 dict.dictht[0/1].table）
• dictFind 在 dict 中查找 key
• dictFetchValue 获取 key 的 value（底层调用 dictFind 实现）
• dictResize 带条件的 dictExpand
• dictGetIterator 获取一个不安全的迭代器
• dictGetSafeIterator 获取一个安全的迭代器
• dictNext 顺着迭代器访问下一个 dictEntry
• dictReleaseIterator 释放迭代器
• dictGetRandomKey 随机获取一个 key 的 dictEntry
• dictGetFairRandomKey 从 dictGetSomeKeys 的一组 dictEntry 中随机返回一个
• dictGetSomeKeys 随机获取指定数量个 key 的 dictEntry 数组
• dictGetStats 输出 HashTable 的 stats 信息，包含：table size number of elements different slots max chain length avg chain length (counted) avg chain length (computed) 等信息
• dictGenHashFunction 返回一个 siphash HashFunction
• dictGenCaseHashFunction 返回一个 siphash_nocase HashFunction
• dictEmpty 清空 dict，清空后的 dict 比 dictCreate 后的 dict 的区别是：清空后的 dict，dict.dictht[0/1].table 是个空数组，而非 null
• dictEnableResize 设置 dict_can_resize 为 1
• dictDisableResize 设置 dict_can_resize 为 0
• dictRehash rehash 指定个下标
• dictRehashMilliseconds rehash 指定时间
• dictScan 遍历 dict，和 dictIterator 的区别是，dictScan 直接给出了 next 的回调函数。用 php 数组 作比：dictIterator 是 foreach，dictScan 是 array_walk
• dictGetHash 计算一个 key 的 hash 值（dict.dictht[0/1].table的下标）

三、redis dict 几个相关命令的实现

1. 结构体

#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4

#define OBJ_ENCODING_RAW 0
#define OBJ_ENCODING_INT 1
#define OBJ_ENCODING_HT 2
#define OBJ_ENCODING_ZIPMAP 3
#define OBJ_ENCODING_LINKEDLIST 4
#define OBJ_ENCODING_ZIPLIST 5
#define OBJ_ENCODING_INTSET 6
#define OBJ_ENCODING_SKIPLIST 7
#define OBJ_ENCODING_EMBSTR 8
#define OBJ_ENCODING_QUICKLIST 9
#define OBJ_ENCODING_STREAM 10
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS;
    int refcount;
    void *ptr;
} robj;

2. hsetnx(key, field, value)

功能：如果 key 是 HashTable 且 field 不存在时，将 key.field 设置为 value

robj *o;
if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
hashTypeTryConversion(o,c->argv,2,3);
if (hashTypeExists(o, c->argv[2]->ptr)) {
    addReply(c, shared.czero);
} else {
    hashTypeSet(o,c->argv[2]->ptr,c->argv[3]->ptr,HASH_SET_COPY);
    addReply(c, shared.cone);
    signalModifiedKey(c->db,c->argv[1]);
    notifyKeyspaceEvent(NOTIFY_HASH,"hset",c->argv[1],c->db->id);
    server.dirty++;
}

hsetnx 的逻辑是（以 key robj.encoding=OBJ_ENCODING_HT为例）：

• hashTypeLookupWriteOrCreate 先在 db 中寻找 key 的 robj，如果找不到会创建一个 type=OBJ_HASH, encoding=OBJ_ENCODING_ZIPLIST 的 robj 并放到 db 中（因为 key 如果不存在 hsetnx 必然成功）
• hashTypeTryConversion 如果 key 对应的 robj.type == OBJ_ENCODING_ZIPLIST 且 filed 或者 value 的 encoding 是 OBJ_ENCODING_RAW 或 OBJ_ENCODING_EMBSTR 且长度大于了 64，会将 key 的 robj.type 改为 OBJ_ENCODING_HT
• hashTypeExists 会调用 dictFind 来查找 key
• hashTypeSet 如果 dictFind 找到了就修改 dictEntry.v，如果没找到就 dictAdd 一个
• addReply 返回操作结果

3. hset(key, field, value) 或 hmset(key, field1, value1, field2, value2,...)

功能：向 HashTable key 存入 key=>value

int i, created = 0;
robj *o;
if ((c->argc % 2) == 1) {
    addReplyError(c,"wrong number of arguments for HMSET");
    return;
}
if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
hashTypeTryConversion(o,c->argv,2,c->argc-1);
for (i = 2; i < c->argc; i += 2)
    created += !hashTypeSet(o,c->argv[i]->ptr,c->argv[i+1]->ptr,HASH_SET_COPY);
char *cmdname = c->argv[0]->ptr;
if (cmdname[1] == 's' || cmdname[1] == 'S') {
    addReplyLongLong(c, created);
} else {
    addReply(c, shared.ok);
}

hset 和 hmset 的逻辑是：

• hset 和 hmset 的 redisCommand 是同一个 Command 实现

{"hset",hsetCommand,-4,
     "write use-memory fast @hash",
     0,NULL,1,1,1,0,0,0},
{"hmset",hsetCommand,-4,
     "write use-memory fast @hash",
     0,NULL,1,1,1,0,0,0},

• 查询或创建 key 的 robj
• 如果需要的话转化 robj.encoding
• 根据 hset 的参数个数循环 hashTypeSet
• hashTypeSet 的逻辑同 hsetnx：如果 dictFind 到就修改 dictEntry.v，如果找不到就 dictAdd
• hset 的返回值是 created，hmset 的返回值是 shared.ok 即字符串 OK

4. hincrby key field increment

功能：为 HashTable key 下的 field 的 value 增加 increment 。如果 key 下的 field 的 value 不是整数类型，会报错：(error) ERR hash value is not an integer

long long value, incr, oldvalue;
    robj *o;
    sds new;
    unsigned char *vstr;
    unsigned int vlen;
    if (getLongLongFromObjectOrReply(c,c->argv[3],&incr,NULL) != C_OK) return;
    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
    if (hashTypeGetValue(o,c->argv[2]->ptr,&vstr,&vlen,&value) == C_OK) {
        if (vstr) {
            if (string2ll((char*)vstr,vlen,&value) == 0) {
                addReplyError(c,"hash value is not an integer");
                return;
            }
        }
    } else {
        value = 0;
    }
    oldvalue = value;
    if ((incr < 0 && oldvalue < 0 && incr < (LLONG_MIN-oldvalue)) ||
        (incr > 0 && oldvalue > 0 && incr > (LLONG_MAX-oldvalue))) {
        addReplyError(c,"increment or decrement would overflow");
        return;
    }
    value += incr;
    new = sdsfromlonglong(value);
    hashTypeSet(o,c->argv[2]->ptr,new,HASH_SET_TAKE_VALUE);

hincrby 的逻辑是：

• getLongLongFromObjectOrReply 获取指定参数的 long long （整数型）值。
• 查询或创建 key 的 robj
• 获取 HashTable key 下的 field 值，如果不能转化成 long long，报错：hash value is not an integer
• 对 increment 后的值做上下限判断，防止溢出
• 下限是 -9223372036854775808 上限是 9223372036854775807
• 将 increment 后的值转化成 long long 类型，然后 hashTypeSet
• 返回 increment 后的值