hash字典, 又称hash表, 也叫映射(Map)或者散列表, 主要存储键值对, 是程序开发语言中最最最常用的数据结构. 也是我们大学计算机专业的必修课. 一般的高级语言都会内置hash字典的实现. 但是C并没有内置, 所以Redis需要自己实现一套hash字典.

redis关于字典的实现, 主要由dict.h和dict.c两个文件实现.

1 C语言基础

static关键字的作用

• static 修饰局部变量, 此变量只能在作用域内访问, 但是变量存储在静态区, 函数执行完后变量不会销毁. 普通局部变量在函数执行完后, 立即销毁
• static 修饰全局变量, 表示此变量只能在当前文件内访问
• static 修饰函数, 表示此函数只能在当前文件内访问

具体细节可以参考黄裕玲的<C语言关键字 static 的用法>

union (共用体)与 struct(结构体)的区别

• 结构体的各个成员会占用不同的内存，互相之间没有影响.
• 共用体的所有成员占用同一段内存，修改一个成员会影响其余所有成员.

结构体占用的内存大于等于所有成员占用的内存的总和（成员之间可能会存在缝隙），共用体占用的内存等于最长的成员占用的内存。共用体使用了内存覆盖技术，同一时刻只能保存一个成员的值，如果对新的成员赋值，就会把原来成员的值覆盖掉。

2 hash字典的结构

hash表一般的实现都是数组+链表来实现. 数组来做hash散列, 链表用来解决hash冲突的问题. 如果我们了解过java的hashMap的话, 不难发现, java7的hashMap的实现跟redis的hash表的实现如出一辙, java8关于hashMap的实现会略复杂一些, 增加了链表转红黑树的内容. 数据结构都是通用的, 如果看过jdk的hashMap的源码, 再看redis的hash表, 基本没什么难度.

redis的hash字典大体结构图如下:

image.png

2.1 hash表节点的结构

//hash表的节点
typedef struct dictEntry {
    //节点的key
    void *key;
    //节点的值 v , v 可以是指针, 也可以是uint64整数, 也可以是int64整数, 还可以是浮点数
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //下一个节点
    struct dictEntry *next;
} dictEntry;

• hash表节点, 主要是包含了k, v键值对和下一个节点的指针, 从结构体我们可以看出, 这是一个hash表节点会组成一个单向链表
• hash表的key是 Void * 指针类型, 也就相当于java的Object, 值 v 是一个共用体, 也可以是uint64整数, 也可以是int64整数, 还可以是浮点数

2.2 hash表结构

//hash表结构体
typedef struct dictht {
    //hash表的指针数组, dictEntry * 表示hash节点的指针, 再加一个 *, 也就是dictEntry ** 表示数组的首地址
    dictEntry **table;
    //hash数组大小, 一般为 2^n
    unsigned long size;
    //hash数组长度掩码, sizemask =  size - 1
    unsigned long sizemask;
    //hash表的kv对的个数
    unsigned long used;
} dictht;

• 由hash表结构, 我们可以看出, redis也是通过数组做hash散列的.
• hash表数组的 size 长度一般为 2^n 的大小, 保证这样的大小可以通&操作来计算出hash槽的位置, 如果数组容量不是2^n的大小, 那么就需要通过取模来获取hash表的槽索引, 取模操作相对&操作性能会差一些.
• szimmask 表示数组掩码, 一般是 size -1, 如: 假如数组长度为8, 那么掩码就为7, 掩码转换成二进制就为 000...00111
• used 表示hash表中kv的个数

2.3 字典类型的结构

//字典类型
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);
    //根据扩容后的数组的内存和负载因子判断是否可以扩容
    int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;

• 字典类型的结构体主要提供相关函数的指针, 用于做扩展, 类似java的抽象方法和接口
• 这样做就相当于实现多态了, 不同的dictType对应的函数指针都不一样

2.4 redis字典的结构

//字典的结构体
typedef struct dict {
    //字典类型的指针
    dictType *type;
    //携带的私有数据
    void *privdata;
    //hash字典的数组, 长度为2, 主要是用于渐进式hash时使用
    dictht ht[2];
    //rehash下一个要迁移的桶索引, rehash 不进行时为 -1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // pauserehash > 0 表示 rehash 是暂停的. 安全的迭代需要停止
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

• 由上面的结构体, 我们可以看出redis的字典是有两个hash表组成的. 常用的hash表是ht[0], 当进行rehash时, 会使用到ht[1]做渐进式重hash.
• privdata 和 type 主要是为了实现多态字典而已设置的, privdata 主要是携带了特定函数需要的一些可选参数, type 则保存了一批可自定义特定函数的指针, redis会根据字典的用途, 在type中设置不同的特定函数
• rehashidx 当字典正在rehash时, 会将下一个要rehash的槽索引记录到当前字段
• pauserehash 表示暂停当前的rehash状态, 安全的迭代和扫描都需要暂停rehash的, 当 pauserehash 大于0时, 则表示rehash暂停, 等于0时表示可以rehash. 为什么暂停需要计数? 因为安全迭代器和扫描都有可能同时存在多个, 所以pauserehash的值是很有可能大于1的

3 字典通用操作实现

3.1 创建字典

/* Create a new hash table */
//创建空字典的指针
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    //分配字典内存
    dict *d = zmalloc(sizeof(*d));

    //初始化字典
    _dictInit(d,type,privDataPtr);
    //返回字段指针
    return d;
}

/* Initialize the hash table */
//初始化hash表
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    //重置第0个hash表
    _dictReset(&d->ht[0]);
    //重置第1个hash表
    _dictReset(&d->ht[1]);
    //设置字典类型
    d->type = type;
    //设置私有数据
    d->privdata = privDataPtr;
    //不进行rehash时, 为-1
    d->rehashidx = -1;
    d->pauserehash = 0;
    return DICT_OK;
}

//hash字典重置
static void _dictReset(dictht *ht)
{
    //清空
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

• 创建字典主要的操作是, 分配字典内存, 并且对字典类型和私有数据进行赋值, 注意, 此时字典的hash表还没初始化的, 其他统计数据都是0

3.2 根据键查询节点

//根据key查询节点
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    //如果字典为空, 则直接返回 NULL
    if (dictSize(d) == 0) return NULL; /* dict is empty */
    //如果字典正在 rehash, 则执行一次rehash步聚
    if (dictIsRehashing(d)) _dictRehashStep(d);
    //计算key的hash值
    h = dictHashKey(d, key);
    //遍历字典的hash表
    for (table = 0; table <= 1; table++) {
        //计算出key所有的hash槽索引
        idx = h & d->ht[table].sizemask;
        //根据hash槽获取首节点
        he = d->ht[table].table[idx];
        //遍历链表, 直到找到key一样的节点
        while(he) {
            //如果找到, 则直接返回找到的节点
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        //如果没找到, 且字典没有rehash, 则直接返回 NULL
        if (!dictIsRehashing(d)) return NULL;
    }
    //没找到, 返回NULL
    return NULL;
}

//获取key对应的值
void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;

    //根据key查询节点
    he = dictFind(d,key);
    //如果节点存在, 则获取节点的值, 否则返回 NULL
    return he ? dictGetVal(he) : NULL;
}

• 大概的思路是, 计算出给定键key的hash值, 然后先在第一个hash表中获取对应的槽索引, 如果槽存在链表首节点, 则遍历链表, 直到找到节点的key与传入的key相等的节点
• 如果字典正在rehash, 那么第一个hash表没找到, 则会在第二张hash表中查询
• 这里注意key的比较, 优先比较内存地址是否一样, 再用compareKey函数进行对比
• 最终都没找到, 则直接返回 NULL
• 如果字典正在rehash, 查询会执行一步_dictRehashStep(), 也就是迁移一个槽的数据到新的hash表当中

3.3 添加或更新键值对

//添加kv对
/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    //添加一个节点到字段中, 并且返回这个节点
    dictEntry *entry = dictAddRaw(d,key,NULL);

    //如果添加节点不成功, 则返回错误
    if (!entry) return DICT_ERR;
    //将值设置到 entry 中
    dictSetVal(d, entry, val);
    //返回成功
    return DICT_OK;
}

//创建新的节点
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    //如果字典在rehash, 则在处理请求前先搬一部分的key
    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    //获取 key 对应的槽索引, 如果key已经存在, 则返回 -1
    //如果key已经存在, 则返回 NULL
    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. */
    //获取hash表, 如果正在rehash, 则用新的hash表, 否则用旧的hash表
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    //分配 dictEntry 内存
    entry = zmalloc(sizeof(*entry));
    //添加节点到槽的链表头
    entry->next = ht->table[index];
    //将新建的节点放入hash槽中
    ht->table[index] = entry;
    //节点数量加1
    ht->used++;

    /* Set the hash entry fields. */
    //设置 key 到节点中
    dictSetKey(d, entry, key);
    return entry;
}

//返回 key 对应的槽索引
//dictEntry **existing 代表什么意思呢?  为了操作外面的dictEntry指针, 只能将 dictEntry 指针的指针传进来
//也就是 existing 代表 dictEntry指针的指针, *existing 表示dictEntry指针, 也就是 dictEntry *
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    //如果传进来的 existing 指针不为 NULL, 设置 dictEntry 指针 dictEntry * 为 NULL
    if (existing) *existing = NULL;

    /* Expand the hash table if needed */
    //如果需要则扩容, 扩容失败则返回 -1
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    //遍历hash表数组
    for (table = 0; table <= 1; table++) {
        //hash值与hash表的掩码计算出hash槽的索引
        idx = hash & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        //获取槽上的链表
        he = d->ht[table].table[idx];
        while(he) {
            //如果传入的key等于节点上的key
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                //传进来的指针existing不为空, 则将存在的节点指针放入 *existing 指针中返回给外层使用
                if (existing) *existing = he;
                //返回 -1
                return -1;
            }
            //获取链表下一个节点
            he = he->next;
        }
        //如果不是在rehash, 则退出循环
        if (!dictIsRehashing(d)) break;
    }
    //返回hash槽索引
    return idx;
}

//添加kv, 如果存在则覆盖
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 succeed. */
    //添加节点
    entry = dictAddRaw(d,key,&existing);
    //如果添加成功
    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;
}

//添加节点, 如果已存在, 则直接返回已存在的节点
dictEntry *dictAddOrFind(dict *d, void *key) {
    dictEntry *entry, *existing;
    entry = dictAddRaw(d,key,&existing);
    return entry ? entry : existing;
}

添加和更新键值对分两步处理

1. 查询给定key是否存在
2. 存在更新, 不存在则添加

• 查询一下给定的key是否存在这段逻辑基本跟上面3.2查找逻辑差不多, 这里就不重复说明了
• 如果字典已经存在对应的key, 则返回已经存在的节点, 否则创建新节点并且放入对应的hash槽中然后返回新创建节点, 这里注意一下, 新节点是放在链表头的
• 创建新节点时, 如果hash表正在rehash, 则会将节点添加到新hash表ht[1]当中
• dictAddRaw()方法中, 如果字典正在rehash, 会执行一步_dictRehashStep(), 也就是迁移一个槽的数据到新的hash表当中

3.4 删除节点

/* Remove an element, returning DICT_OK on success or DICT_ERR if the
 * element was not found. */
//删除指定key
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}

//移除字典的节点, 不回收内存
dictEntry *dictUnlink(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,1);
}

/* You need to call this function to really free the entry after a call
 * to dictUnlink(). It's safe to call this function with 'he' = NULL. */
//回收节点的内存
void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {
    //如果节点为 NULL, 则直接返回
    if (he == NULL) return;
    //回收 key 的内存
    dictFreeKey(d, he);
    //回收 value 的内存
    dictFreeVal(d, he);
    //回收节点的内存
    zfree(he);
}

/* Search and remove an element. This is an helper function for
 * dictDelete() and dictUnlink(), please check the top comment
 * of those functions. */
//删除一个节点, nofree 表示不回收删除节点的内存
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    //如果hash表为空, 则直接返回 NULL
    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

    //如果hash表正在rehash, 则执行rehash处理
    if (dictIsRehashing(d)) _dictRehashStep(d);
    //计算出key的hash值
    h = dictHashKey(d, key);

    //遍历hash表
    for (table = 0; table <= 1; table++) {
        //根据掩码, 计算出hash槽的索引
        idx = h & d->ht[table].sizemask;
        //获取hash槽的链表首节点
        he = d->ht[table].table[idx];
        //前一个节点引用设置为 NULL, 这个用于记录上一个节点
        prevHe = NULL;
        //如果首节点存在
        while(he) {
            //如果节点的key跟传入的key相等或者调用比较函数比较相等
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                /* Unlink the element from the list */
                //下面if..else主要是目标是将 he 从链表中移除
                //如果上一个节点存在, 则将next指针指向he的next
                if (prevHe)
                    prevHe->next = he->next;
                else
                    //prevHe为NULL, 则表示直接用he的next作为首节点
                    d->ht[table].table[idx] = he->next;
                //如果要释放节点的内存
                if (!nofree) {
                    //回收key的内存
                    dictFreeKey(d, he);
                    //回收val的内存
                    dictFreeVal(d, he);
                    //回收dictEntry的内存
                    zfree(he);
                }
                //减少节点个数
                d->ht[table].used--;
                //返回删除的节点
                return he;
            }
            //记录当前节点为前一个节点
            prevHe = he;
            //获取下一个节点
            he = he->next;
        }
        //如果字典不是 rehash, 则退出循环
        if (!dictIsRehashing(d)) break;
    }
    //没找到, 则返回 NULL
    return NULL; /* not found */
}

删除节点也分两步实现

• 查询节点是否存在, 查找的思路跟上面查询和新建的逻辑基本一致
• 节点存在则删除, 不存在则处理

这里的删除有两种, 一种是直接回收节点内存, 另一种是将节点从字典中移除, 但是待后续需要再回收节点的内存.

删除节点之前也会做一次渐进rehash.

3.5 释放字典内存

//清空字典
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
    unsigned long i;

    /* Free all the elements */
    //如果hash表的hash数组已经初始化且hash表中有元素, 则遍历处理
    for (i = 0; i < ht->size && ht->used > 0; i++) {
        //he 当前节点, nextHe 表示下一个节点
        dictEntry *he, *nextHe;

        //如果有传callback函数, 则每清空65535个槽, 则执行回调方法一次
        //为什么要这么处理这个回调呢 ? 主要为了避免hash表太大, 一直删除会阻塞, 通过回调方法, 删除阻塞过程中能够处理新的请求 https://www.modb.pro/db/72930
        if (callback && (i & 65535) == 0) callback(d->privdata);

        //获取首节点不存在, 如果首节点不存在则不处理
        if ((he = ht->table[i]) == NULL) continue;
        //如果节点存在
        while(he) {
            //获取下一个节点
            nextHe = he->next;
            //回收当前节点key的内存
            dictFreeKey(d, he);
            //回收当前节点val的内存
            dictFreeVal(d, he);
            //回收节点的内存
            zfree(he);
            //减少节点数量
            ht->used--;
            //获取下一个节点
            he = nextHe;
        }
    }
    /* Free the table and the allocated cache structure */
    //释放hash表
    zfree(ht->table);
    /* Re-initialize the table */
    //重置字典
    _dictReset(ht);
    //返回 OK
    return DICT_OK; /* never fails */
}

/* Clear & Release the hash table */
//回收字典内存
void dictRelease(dict *d)
{
    //清空hash表
    _dictClear(d,&d->ht[0],NULL);
    //清空rehash中的hash表
    _dictClear(d,&d->ht[1],NULL);
    //回收字典内存
    zfree(d);
}

• 释放字典内存之前, 先清空hash表
• 清空hash表, 会遍历hash表的所有节点, 回收key的内存, val的内存以及节点本身的内存, 并且重置hash表的统计数据

4 字典扩容

redis的字典扩容跟java的HashMap扩容实现有点不一样, java的HashMap扩容是一次性完成的. redis是一个单线程的高性能的内存数据库, 如果字典中有大量的key, 那么当字典rehash时, 会就阻塞现有的客户端请求, 影响服务器的性能. 因此, redis的扩容(缩容)是渐进式的逐步的, 并不会一次性全部迁移完成.

4.1 hash表扩容或缩容

/* Resize the table to the minimal size that contains all the elements,
 * but with the invariant of a USED/BUCKETS ratio near to <= 1 */
//字典表调整大小
int dictResize(dict *d)
{
    //字段数组最小长度
    unsigned long minimal;

    //如果字段不可以调整大小或正在rehash, 则返回错误
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    //获取hash表的元素数量
    minimal = d->ht[0].used;
    //如果元素数量小于最小初始化大小
    if (minimal < DICT_HT_INITIAL_SIZE)
        //则默认用初始化大小
        minimal = DICT_HT_INITIAL_SIZE;
    //字典扩容
    return dictExpand(d, minimal);
}

/* Expand or create the hash table,
 * when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1).
 * Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */
//扩容或者创建字典
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
    if (malloc_failed) *malloc_failed = 0;

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    //如果字典正在rehash, 或者已有节点数大于扩容数组的大小, 则直接返回错误
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; /* the new hash table */
    //计算要扩容的容量
    unsigned long realsize = _dictNextPower(size);

    /* Rehashing to the same table size is not useful. */
    //如果要扩容的容量跟原来的一样, 则返回错误
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    //设置新的容量
    n.size = realsize;
    n.sizemask = realsize-1;
    //如果要避免分配失败报错
    if (malloc_failed) {
        //尝试分配hash数组
        n.table = ztrycalloc(realsize*sizeof(dictEntry*));
        //设置是否分配失败, n.table == NULL 就是分配失败
        *malloc_failed = n.table == NULL;
        //如果分配失败, 则返回错误
        if (*malloc_failed)
            return DICT_ERR;
    } else
        //分配hash数组, 分配失败则终止程序
        n.table = zcalloc(realsize*sizeof(dictEntry*));

    //设置节点数为0
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    //如果字典的hash表为 NULL, 则表示这是首次初始化
    if (d->ht[0].table == NULL) {
        //将hash表放到hash数组中第0位中
        d->ht[0] = n;
        return DICT_OK;
    }

    //如果非首次初始化, 则放到hash数组第1位, 用于rehash
    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    //设置从hash表中的第0位进行迁移
    d->rehashidx = 0;
    //返回成功
    return DICT_OK;
}

//如果扩容失败, 报内存溢出
/* return DICT_ERR if expand was not performed */
int dictExpand(dict *d, unsigned long size) {
    return _dictExpand(d, size, NULL);
}

//字典尝试扩容, 扩容失败则返回错误
/* return DICT_ERR if expand failed due to memory allocation failure */
int dictTryExpand(dict *d, unsigned long size) {
    //是否失败
    int malloc_failed;
    //扩容
    _dictExpand(d, size, &malloc_failed);
    //如果失败, 则返回错误, 否则返回成功
    return malloc_failed? DICT_ERR : DICT_OK;
}

• 数组扩容缩容的主要方法是_dictExpand() , 大概的思路是, 根据调整容量的大小 size , 计算出新hash表容量的大小, 然后创建新的hash表, 并且将新的hash表放到ht[1]中, 并且设置 rehashidx=0, 也就是从第0个桶开始做rehash迁移
• 这里新hash表的数组大小必须符合2^n, 这样做的好处理是, 可以直接用&操作来做hash取模, 相对于%取模性能会好很多
• 如果hash表ht[0]未初始化, 则直接初始化到ht[0]

4.2 渐进式rehash实现

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
//字典 rehash 过程, n 表示迁移桶的数量
int dictRehash(dict *d, int n) {
    //最多遍历空桶的数量
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    //如果字典不是rehash状态, 直接返回迁移失败
    if (!dictIsRehashing(d)) return 0;

    //如果迁移桶的数量不为空, 且hash表没迁移完. 注意: 这里是先读取n再--
    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 */
        //断言hash表桶的个数是大于已经rehash的桶索引. rehashidx 最大为 ht[0].size - 1
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        //如果要迁移的桶的链表首节点为 NULL, 则表示此桶为空. 这个循环主要上去掉空桶
        while(d->ht[0].table[d->rehashidx] == NULL) {
            //准备迁移下一个桶
            d->rehashidx++;
            //如果已经超过规定处理的最大空桶数量, 则直接返回迁移成功
            if (--empty_visits == 0) return 1;
        }
        //获取rehash上面的链表首节点
        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表中的槽的索引
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            //将节点设置到新的hash表中
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            //旧hash表数量减少
            d->ht[0].used--;
            //新hash表数量增加
            d->ht[1].used++;
            //攻取下一个节点
            de = nextde;
        }
        //清空旧节点的hash槽
        d->ht[0].table[d->rehashidx] = NULL;
        //设置下一个要迁移处理的hash槽
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    //处理完, 判断一下hash表是否迁移完成
    if (d->ht[0].used == 0) {
        //迁移完成
        //回收旧hash表的数组
        zfree(d->ht[0].table);
        //用新hash表替换旧hash表, 赋值相当于拷贝
        d->ht[0] = d->ht[1];
        //重置临时的hash表
        _dictReset(&d->ht[1]);
        //清空下一个rehash的索引
        d->rehashidx = -1;
        return 0;
    }

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

//获取当前毫秒时间
long long timeInMilliseconds(void) {
    struct timeval tv;

    gettimeofday(&tv,NULL);
    return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
}

/* Rehash in ms+"delta" milliseconds. The value of "delta" is larger 
 * than 0, and is smaller than 1 in most cases. The exact upper bound 
 * depends on the running time of dictRehash(d,100).*/
//指定时间rehash
int dictRehashMilliseconds(dict *d, int ms) {
    //如果rehash是暂停的, 则不处理
    if (d->pauserehash > 0) return 0;

    //获取当前时间戳
    long long start = timeInMilliseconds();
    //统计rehash桶的个数
    int rehashes = 0;

    //rehash 100 个桶
    while(dictRehash(d,100)) {
        //增加统计
        rehashes += 100;
        //如果执行时间大于给定的时间, 则退出
        if (timeInMilliseconds()-start > ms) break;
    }
    //返回rehash桶的个数
    return rehashes;
}

/* This function performs just a step of rehashing, and only if hashing has
 * not been paused for our hash table. When we have iterators in the
 * middle of a rehashing we can't mess with the two hash tables otherwise
 * some element can be missed or duplicated.
 *
 * This function is called by common lookup or update operations in the
 * dictionary so that the hash table automatically migrates from H1 to H2
 * while it is actively used. */
//执行一步渐进式rehash
static void _dictRehashStep(dict *d) {
    //如果rehash不是暂停的, 则执行rehash迁移
    if (d->pauserehash == 0) dictRehash(d,1);
}

• 渐进式rehash的主要逻辑在 dictRehash() 方法中, 方法参数 n 表示迁移桶的数量. 这个方法对空桶遍历做了优化, 每次rehash迁移, 最多只能处理 n * 10 个空桶.
• 迁移的思路: 从 rehashidx 开始迁移, 最多迁移 n 个桶, 如果超过遍历空桶的最大数量, 则直接返回迁移成功, 否则, 遍历桶上的链表, 然后将链表每个节点根据新的hash表ht[1]的大小做rehash, 最后将节点从原hash表移除, 添加到新hash表对应的槽中. 当每个槽迁移完成时, 清空桶的节点指针, 将 rehashidx 加1, 表示下一个要迁移的桶. 如果旧hash表全部迁移完成, 则用新hash表替换旧hash表, 并且回收旧hash表的内存, 将rehashidx重置为-1.
• _dictRehashStep()方法表示进行一次渐进式rehash, 也就是迁移一个桶的数据
• dictRehashMilliseconds()方法, 表示根据时间限定进行rehash, 每次处理100个桶, 直接超过给定时间为止

5 字典迭代器实现

5.1 迭代器的结构

typedef struct dictIterator {
    //字典的指针
    dict *d;
    //当前正在迭代的hash槽索引下标
    long index;
    //table表示正在迭代的hash表数组ht的索引, safe 表示是否安全
    int table, safe;
    //entry表示当前已返回的节点, nextEntry表示下一个节点
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    //字典当前状态的签名, 64位的hash值
    long long fingerprint;
} dictIterator;

• 迭代器可以分安全迭代和非安全迭代. 安全的迭代中会将rehash暂停
• 非安全迭代, 会在释放迭代器内存时, 判断字典是否发生了变化, 如果发生变化, 则报异常
• fingerprint 是一个64位的hash值, 是根据字典的内存地址生成的, 代表着字典当前的状态, 非安全迭代中, 如果字典内存发生了新的变化, 则 fingerprint 的值也会跟着变, 用于非安全迭代的快速失败
• table 字段表示遍历的hash表, 值是0和1
• safe 表示迭代器是否安全
• index 表示已经过遍历的hash槽索引
• *entry表示当前已经遍历过的节点, *nextEntry表示下一个要遍历的节点

5.2 迭代器的实现

创建迭代器

//获取字典迭代器
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);

    //设置save为1
    i->safe = 1;
    return i;
}

• 迭代器的创建比较简单, 就是分配内存, 并且初始化数据
• 安全迭代器和普通迭代器的数据结构上的区别是, 多了 safe=1

遍历迭代器的下一个节点

//获取下一个节点
dictEntry *dictNext(dictIterator *iter)
{
    //死循环
    while (1) {
        //如果当前节点为空
        if (iter->entry == NULL) {
            //获取要遍历的hash表
            dictht *ht = &iter->d->ht[iter->table];
            //如果hash数组table的索引为-1或者ht数组索引为0, 则表示第一次进来遍历
            if (iter->index == -1 && iter->table == 0) {
                //如果是安全的遍历, 则要暂停rehash
                if (iter->safe)
                    dictPauseRehashing(iter->d);
                else
                    //不安全的遍历, 则给字典计算一个指纹(相当于校验和)
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            //索引加1
            iter->index++;
            //如果当前索引大于hash数组长度
            if (iter->index >= (long) ht->size) {
                //判断当前字典是不是在rehash, 并且还没有把所有hash表遍历完
                if (dictIsRehashing(iter->d) && iter->table == 0) {
                    //索引加1, 遍历一下个hash表
                    iter->table++;
                    //hash表的索引重置为0
                    iter->index = 0;
                    //获取第二个hash表
                    ht = &iter->d->ht[1];
                } else {
                    break;
                }
            }
            //获取hash槽的首节点
            iter->entry = ht->table[iter->index];
        } else {
            //获取下一个节点
            iter->entry = iter->nextEntry;
        }
        //如果节点不为NULL
        if (iter->entry) {
            /* We need to save the 'next' here, the iterator user
             * may delete the entry we are returning. */
            //先记录下一个节点, 方便使用. 当前节点 entry 有可能被删除
            iter->nextEntry = iter->entry->next;
            //返回当前节点
            return iter->entry;
        }
    }
    //没找到, 则返回 NULL
    return NULL;
}

• 死循环遍历, 直到找一个节点或者已经遍历了所有hash槽都没找到, 则退出循环
• 如果当前节点不为空, 则表示之前有遍历过, 则直接获取下一个节点, 如果存在则直接返回并且记录下下个节点, 否则查找一个hash槽
• 第一次进入迭代器, 如果迭代器是安全的, 则将rehash暂停加1, 非安全迭代器, 则计算fingerprint的值
• 遍历槽索引加1, 如果索引超出hash表数组的长度, 则判断是否正在rehash, 如果正在rehash, 则遍历新的hash表, 并且重置index为0
• 最后都没找到, 则返回 NULL

5.3 回收迭代器内存

//回收迭代器
void dictReleaseIterator(dictIterator *iter)
{
    //如果迭代器已经开始遍历
    if (!(iter->index == -1 && iter->table == 0)) {
        //判断是否按全
        if (iter->safe)
            //减少rehash停顿数量
            dictResumeRehashing(iter->d);
        else
            //断言当前签名与迭代器记录的状态必须一致, 不一致表示用户进行了非法操作
            assert(iter->fingerprint == dictFingerprint(iter->d));
    }
    //回收迭代器的内存
    zfree(iter);
}

• 回收迭代器内存之前, 如果迭代器是安全的, 则减小rehash暂停数量, 非安全的迭代器判断签名是否一致, 快速失败

6 随机采集键值对

6.1 随机采集一个key值

/* Return a random entry from the hash table. Useful to
 * implement randomized algorithms */
//从字典中获取一个随机的key. 可能会出现不公平的情况
//算法大概的思路是: 随机获取一个hash槽, 然后从槽的链表中随机获取一个节点
dictEntry *dictGetRandomKey(dict *d)
{
    dictEntry *he, *orighe;
    unsigned long h;
    //listlen 链表长度, listele 链表随机的位置
    int listlen, listele;

    //如果字典为空, 则直接返回 NULL
    if (dictSize(d) == 0) return NULL;
    //如果字典正在 rehash, 则执行rehash的迁移
    if (dictIsRehashing(d)) _dictRehashStep(d);
    //如果当前字典正在rehash
    if (dictIsRehashing(d)) {
        //循环随机获取, 直接到hash槽有节点存在为止
        do {
            /* We are sure there are no elements in indexes from 0
             * to rehashidx-1 */
            //获取一个随机数, 然后根据两个hash表的长度计算hash槽.
            // randomULong() % (dictSlots(d) - d->rehashidx) 保证随机值不包括 rehashidx 之前的, 注意, 这里是取模不是&
            h = d->rehashidx + (randomULong() % (dictSlots(d) - d->rehashidx));
            //如果算出来的随机hash槽大于旧hash表的长度, 则表示要获取新hash表的随机槽首节点, 否则获取旧hash表的随机槽首节点
            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, 只有一个hash表
        do {
            //生成随机数, 计算随机hash槽
            h = randomULong() & d->ht[0].sizemask;
            //获取随机hash槽的首节点
            he = d->ht[0].table[h];
            //节点为NULL, 则继续随机
        } 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. */
    //链表长度设置为0
    listlen = 0;
    //先将首节点暂存起来
    orighe = he;
    //遍历所有节点, 统计链表长度
    while(he) {
        he = he->next;
        listlen++;
    }
    //随机获取链表上的位置
    listele = random() % listlen;
    //遍历链表, 获取指定位置的节点
    he = orighe;
    while(listele--) he = he->next;
    //返回随机的节点
    return he;
}

• 如果字典为空, 则直接返回 NULL
• 如果字典正在rehash, 则执行一次渐进式rehash
• 如果字典正则rehash, 则在两张hash表中随机获取一个hash槽, 如果字典没有rehashing, 则在ht[0]的hash表中随机获取一个hash槽
• 遍历槽的链表, 统计链表的长度, 然后生成一个随机位置, 然后获取链表的对应位置的值

随机获取key算法思路总结
随机获取一个hash槽, 在槽链表中随机获取一个节点

6.2 随机采集一批键值对

/* This function samples the dictionary to return a few keys from random
 * locations.
 *
 * It does not guarantee to return all the keys specified in 'count', nor
 * it does guarantee to return non-duplicated elements, however it will make
 * some effort to do both things.
 *
 * Returned pointers to hash table entries are stored into 'des' that
 * points to an array of dictEntry pointers. The array must have room for
 * at least 'count' elements, that is the argument we pass to the function
 * to tell how many random elements we need.
 *
 * The function returns the number of items stored into 'des', that may
 * be less than 'count' if the hash table has less than 'count' elements
 * inside, or if not enough elements were found in a reasonable amount of
 * steps.
 *
 * Note that this function is not suitable when you need a good distribution
 * of the returned items, but only when you need to "sample" a given number
 * of continuous elements to run some kind of algorithm or to produce
 * statistics. However the function is much faster than dictGetRandomKey()
 * at producing N elements. */
//随机采集指定数量的节点. 有可能返回的数量达不到 count 的个数. 如果要返回一些随机key, 这个函数比 dictGetRandomKey 快很多
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {
    unsigned long j; /* internal hash table id, 0 or 1. */
    //hash表的数量, 值为1或者2
    unsigned long tables; /* 1 or 2 tables? */
    //stored 表示已经采集的节点数, maxsizemask 表示容量的最大hash表的掩码
    unsigned long stored = 0, maxsizemask;
    //采集次数上限
    unsigned long maxsteps;

    //最多只能返回字典的总节点数.
    if (dictSize(d) < count) count = dictSize(d);
    //采集次数上限为元素个数的10倍
    maxsteps = count*10;

    /* Try to do a rehashing work proportional to 'count'. */
    //根据返回key的个数, 执行渐进式rehash操作
    for (j = 0; j < count; j++) {
        if (dictIsRehashing(d))
            _dictRehashStep(d);
        else
            break;
    }

    //如果字典正在rehash, 则需要遍历两个hash表, 否则就遍历一个
    tables = dictIsRehashing(d) ? 2 : 1;
    //获取hash表0的掩码作为最大掩码
    maxsizemask = d->ht[0].sizemask;
    //如果hash表数量大于1, 表示字典现在是rehash状态
    //如果字典是rehash状态, 则对比两个hash表的掩码, 取最大的作为 maxsizemask
    if (tables > 1 && maxsizemask < d->ht[1].sizemask)
        maxsizemask = d->ht[1].sizemask;

    /* Pick a random point inside the larger table. */
    //获取随机数然后计算出一个随机hash槽.
    unsigned long i = randomULong() & maxsizemask;
    //统计遍历了空的hash槽个数
    unsigned long emptylen = 0; /* Continuous empty entries so far. */
    //如果采样的key已经足够或者达到采样上限, 则退出循环
    while(stored < count && maxsteps--) {
        //遍历hash表数组进行采集
        for (j = 0; j < tables; j++) {
            /* Invariant of the dict.c rehashing: up to the indexes already
             * visited in ht[0] during the rehashing, there are no populated
             * buckets, so we can skip ht[0] for indexes between 0 and idx-1. */
            //跳过已经迁移到新hash表的hash槽索引
            //tables == 2 字典表示正在rehash
            //j == 0 , 表示目前正在遍历旧hash表
            //i < (unsigned long) d->rehashidx 表示i属于已经迁移的hash槽索引
            if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) {
                /* Moreover, if we are currently out of range in the second
                 * table, there will be no elements in both tables up to
                 * the current rehashing index, so we jump if possible.
                 * (this happens when going from big to small table). */
                //如果当前随机索引大于hash表1的长度, 表示只能在hash表0中获取, 那么跳过 rehashidx 前面已经迁移的槽
                if (i >= d->ht[1].size)
                    i = d->rehashidx;
                else
                    //i 小于 rehashidx, 但是没有大于hash表1的容量, 直接跳过hash表0, 从hash表1中采样
                    continue;
            }
            //如果随机hash槽索引大于当前hash表数组的长度, 则不处理
            if (i >= d->ht[j].size) continue; /* Out of range for this table. */
            //获取hash表的首节点
            dictEntry *he = d->ht[j].table[i];

            /* Count contiguous empty buckets, and jump to other
             * locations if they reach 'count' (with a minimum of 5). */
            //如果首节点为 NULL
            if (he == NULL) {
                //统计空的hash槽
                emptylen++;
                //如果空的hash槽个数超过5且超过 count, 重新生成随机hash槽索引, 并且重置空的hash槽统计
                if (emptylen >= 5 && emptylen > count) {
                    i = randomULong() & maxsizemask;
                    emptylen = 0;
                }
            } else {
                //首节点不为空, 重置空的hash槽统计
                emptylen = 0;
                //遍历链表
                while (he) {
                    /* Collect all the elements of the buckets found non
                     * empty while iterating. */
                    //将节点放进 dictEntry * 数组
                    *des = he;
                    //数组指针移动到下一个索引
                    des++;
                    //获取下一个节点
                    he = he->next;
                    //获取的节点数加1
                    stored++;
                    //如果获取的节点数已经满足, 则直接反回
                    if (stored == count) return stored;
                }
            }
        }
        //获取下一个hash槽位置
        i = (i+1) & maxsizemask;
    }
    return stored;
}

• 数据采集次数的上限为 count*10 , 也就是如果你采集5个节点, 如果采集50次也采集不够5个节点, 则直接返回已经采集的数据
• 如果字典正在rehash, 则执行 count 次渐进式rehash
• 根据采集上限和采集节点个数进行遍历, 大体的思路是, 采集获取一个hash槽, 然后遍历链表的节点, 直到满足给定的元素个数, 这里与随机采集一个key的实现不同, 他不会对链表的节点进行随机获取. 如果链表数据不够, 则直接获取一个槽的节点数据进行填充. 如果遍历的空hash槽超过5个, 则会重新随机一个hash槽, 然后重新上述步骤
• 当字典正在rehash时, 会根据随机索引i是否大于 rehashidx 来做优化, 这里的逻辑有点绕. 当正在遍历第一个hash表ht[0]时, 如果i < rehashidx, 则判断i是否大于第二个hash表的数组长度, 如果大于等于第二张hash表的数组长度, 则只能在第一个hash表ht[0]中获取随机槽节点, 那么就可以跳过被rehash迁移的槽索引, 如果i小于第二级hash表ht[i]的长度, 则直接跳过第一张hash表ht[0], 然后从第二张hash表ht[1]中获取随机槽

image.png

吐槽: 这段逻辑纠结了很久, 一直想不通为啥要写这段优化, 后面将continue与上面for循环结合起来一想, 才明白, 原来是跳过了第一张hash表. 再次强调, 看源码就跟看文章一样, 可以通过上下文来解决当前代码的作用

6.3 公平地随机采集一个key

/* This is like dictGetRandomKey() from the POV of the API, but will do more
 * work to ensure a better distribution of the returned element.
 *
 * This function improves the distribution because the dictGetRandomKey()
 * problem is that it selects a random bucket, then it selects a random
 * element from the chain in the bucket. However elements being in different
 * chain lengths will have different probabilities of being reported. With
 * this function instead what we do is to consider a "linear" range of the table
 * that may be constituted of N buckets with chains of different lengths
 * appearing one after the other. Then we report a random element in the range.
 * In this way we smooth away the problem of different chain lengths. */
#define GETFAIR_NUM_ENTRIES 15
//公平地获取一个随机key.
//为什么比 dictGetRandomKey 公平一点呢?. dictGetRandomKey 由于不同的槽, 链表的长度可能不一样, 就会导致概率的分布不一样
//dictGetSomeKeys 返回的长度是固定的, 从固定的链表长度中随机节点, 相对于 dictGetRandomKey 链表长度不固定会公平一点
dictEntry *dictGetFairRandomKey(dict *d) {
    //节点数组
    dictEntry *entries[GETFAIR_NUM_ENTRIES];
    //随机获取15个节点
    unsigned int count = dictGetSomeKeys(d,entries,GETFAIR_NUM_ENTRIES);
    /* Note that dictGetSomeKeys() may return zero elements in an unlucky
     * run() even if there are actually elements inside the hash table. So
     * when we get zero, we call the true dictGetRandomKey() that will always
     * yield the element if the hash table has at least one. */
    //如果没有获取到, 则随机返回一个key
    if (count == 0) return dictGetRandomKey(d);
    //在这一组节点中, 生成随机索引
    unsigned int idx = rand() % count;
    //在这一组节点中, 随机获取一个
    return entries[idx];
}

刚开始我也想不明白, 为什么这个方法会比 dictGetRandomKey() 公平呢? 后面看了上文英文的注释, 大概明白作者的意思:

• 为什么比 dictGetRandomKey 公平一点呢?. dictGetRandomKey 由于不同的槽, 链表的长度可能不一样, 就会导致概率的分布不一样
• dictGetSomeKeys 返回的长度是固定的, 从固定的链表长度中随机节点, 相对于 dictGetRandomKey 链表长度不固定会公平一点

至于这个分布概率, 我也没有测试过, 感兴趣的朋友可以自己测试一下

7 字典表scan扫描(难点)

先埋个关子, 这个算法很有意思, 非常精妙!!!! 准备好开车哈

7.1 scan命令

redis 有个 scan 命令, 用于迭代数据库中的数据库键, 我们看一下他的用法:

SCAN cursor [MATCH pattern] [COUNT count]

scan 命令接收三个参数, 第一个参数 cursor 是游标, 第一次给0就行, 第二个参数 pattern 是键的匹配模式, 第三个参数 count 是返回多少个元素. 每次遍历, 将上次扫描返回游标传入, 就可以继续往下迭代, 直到cusor为0时结束.

7.1 字典扫描算法

7.1.1 正常低位序遍历算法的问题

看到上面的命令, 你想到何种方法来实现? 遍历一个稳定不变的字典, 并不是什么难的事情, 但是redis的字典不一样, rehash会导致redis的字典变大或缩小, 那么在rehash之后就会导致redis节点元素的位置发生变动.

问题一: 小表变大表, 会重复扫描
假如我们的游标是正常的顺序遍历, 刚扫描完第0号槽, 返回一个游标1, 然后redis发生rehash扩容, 字典的数组长度由8变32, 原本同一个hash槽的链表元素, 会分散到多个hash槽当中, 如: 旧表二进制中 001 号槽中的节点元素在rehash后, 会落到新表的 00001 , 01001 , 10001 , 11001 , 也就是高两位发生变化, 底三位不变, 如果我们还是按照正常的游标顺序遍历, 从 00001 开始遍历, 那么在扫描后面三个 01001 , 10001 , 11001 二进制位时, 就很可能会导致我们会重复扫描到已经扫描过的数据.

问题二: 大表变小表, 会漏数据
假如我们的游标是正常的顺序遍历, 刚扫描完第8号槽, 返回一个游标9, 然后redis发生rehash扩容, 字典的数组长度由32变8, 原本同一个hash槽的链表, 会由多个hash槽合并到一个hash槽当中, 如: 旧表的二进制中00001 , 01001 , 10001 , 11001 号槽的节点元素在rehash后, 会落到新表 001 号槽当中, 旧表的 01000 , 10000 , 11000 , 00000 , 会落在新表000的位置, 也就是删除高两位, 底三位不变, 原来返回的游标01001 (9)在新表是001 , 如果我们还是按照正常的游标顺序遍历 , 从 001 开始遍历, 很可能我们会漏掉一些未扫描的数据( 11000 , 10000 )

那如何保证字典中原有的元素都可以被遍历？又如何能尽可能少的重复迭代呢？

• 开始遍历那一刻的所有元素，只要不被删除，肯定能被遍历到，不管字典扩展还是缩小.
• 该算法可能会返回重复元素，但是已经把返回重复元素的可能性降到了最低

7.1.2 redis的scan算法原理

redis通过高位序遍历扫描, 可以完美实现上面两条基本要求.

低位序访问
就是我们正常的顺序, 从小到大, 也就是按低位顺序聚合在一起的, 如:
000(0) -> 001(1) -> 010(2) -> 011(3) -> 100(4) -> 101(5) -> 110(6) -> 111(7)

高位序访问
这个访问顺序有点不一样, 是按高位顺序来聚合数据, 如:
000(0) -> 100(4) -> 010(2) -> 110(6) -> 001(1) -> 101(5) -> 011(3) -> 111(7)

为什么高进位序访问, 能够减少重复扫描返回的key ?
高进位序访问是将原来的二进制反转, 然后加1进位, 再将二进制反转回来, 这样访问就相当于将所有hash槽按低位聚集, 并且以低位反序由小到大进行排序, 无论hash表rehash时由大变小, 还是由小变大, 原来相对于大表的低位都是不变的, 因此低位反序由小到大的顺序都是固定的.

Dict(8)与Dict(16)的对比

image.png

我们举两个例子
字典扩容:
如上图, 我们的字典容量刚开始是8, 然后我们从0开始扫描, 然后扫描了0, 4, 2, 6 四个槽后返回游标1, 此时字典扩容为16, 那么下次访问新的hash表时, 我们依然从1开始扫描, 也不会重复扫描到以前的槽, 并且也不会漏掉未扫描的槽.

**字典缩容: **
如上图, 我们的字典容量刚开始是16, 然后我们从0开始扫描, 然后扫描了0, 8, 4, 12, 2 五个槽后返回游标10, 此时字典缩容为8, 那么下次访问新的hash表时, 我们依然从10号槽开始扫描, 10号槽重hash后就是新表的2号槽, 小表(新表)的2号槽是由大表的2号槽和10号槽合并的, 所以我们可能会扫描到一些重复的槽, 如已经扫描过的2号槽, 但是不会漏掉未扫描的槽.

7.2 redis关于dictscan的实现

//字典扫描
unsigned long dictScan(dict *d,
                       unsigned long v,
                       dictScanFunction *fn,
                       dictScanBucketFunction* bucketfn,
                       void *privdata)
{
    dictht *t0, *t1;
    const dictEntry *de, *next;
    unsigned long m0, m1;

    //如果字典为空, 则不处理
    if (dictSize(d) == 0) return 0;

    /* This is needed in case the scan callback tries to do dictFind or alike. */
    //如果字典正在rehash, 则停顿rehash
    dictPauseRehashing(d);

    //如果字典没有在rehash
    if (!dictIsRehashing(d)) {
        //获取hash表0的指针
        t0 = &(d->ht[0]);
        //获取hash表0的掩码
        m0 = t0->sizemask;

        /* Emit entries at cursor */
        //如果桶的回调函数存在, 则用回调函数处理要获取的桶
        if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
        //获取桶上的首节点
        de = t0->table[v & m0];
        //如果节点存在, 则遍历链表上的节点, 并且使用 fn 函数处理
        while (de) {
            next = de->next;
            fn(privdata, de);
            de = next;
        }

        /* Set unmasked bits so incrementing the reversed cursor
         * operates on the masked bits */
        //假如hash表0长度为8, 那么m0就应该为前29位为0, 后三位为1, 也就是 ...000111
        //~m0 也就是, ...111000, v |= ~m0 就相当于保留低位的数据, v最终结果为, 高29位为1, 低3位为实际数据, ...111xxx
        v |= ~m0;

        /* Increment the reverse cursor */
        //反转游标, 就变成 xxx111...111
        v = rev(v);
        //游标加1, 因为低位都是1, 加1之后, 就会进1, 最终相当于实际数据加1, 其实就相当于xx(x + 1)000...000
        v++;
        //再次返回转回原来的顺序
        v = rev(v);

    } else {
        //获取字段的hash表0的引用
        t0 = &d->ht[0];
        //获取字典的hash表1的引用
        t1 = &d->ht[1];

        /* Make sure t0 is the smaller and t1 is the bigger table */
        //判断那个hash表的容量最小, 小容量的hash表为t0
        if (t0->size > t1->size) {
            t0 = &d->ht[1];
            t1 = &d->ht[0];
        }

        //获取t0的掩码
        m0 = t0->sizemask;
        //获取t1的掩码
        m1 = t1->sizemask;

        /* Emit entries at cursor */
        //如果 bucketfn 函数不为null, 则使用bucketfn对链表进行处理
        if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
        //获取游标对应的首节点
        de = t0->table[v & m0];
        //遍历链表
        while (de) {
            //获取下一个节点
            next = de->next;
            //处理当前节点
            fn(privdata, de);
            de = next;
        }

        /* Iterate over indices in larger table that are the expansion
         * of the index pointed to by the cursor in the smaller table */
        //处理大hash表t1
        //小表的槽, 在按大表重hash后的槽都是相对固定的
        // 假如小表容量是8, 则他的槽二进制就是三位, 如: 001, 010等等, 我们以abc表示3位二进制变量
        // 当扩容到32, 则他们二进制位为5位, 如: 00010, 01010等, 我们以xxabc来表示5位后的二进制变量
        // 也就是扩容后, 落在二进制abc的值, 很有可能会重hash后会落在xxabc中,
        // 所以我们扫描小表的abc后, 再将abc作为后缀, 穷举xxabc中的xx, 就可以获取rehash两张表中原来在同一个槽的key值
        //如果是大表变小表同理
        do {
            /* Emit entries at cursor */
            //首先用桶函数处理
            if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
            //获取游标在大表t1对应的槽
            de = t1->table[v & m1];
            //遍历槽上的链表, 使用函数处理获得的节点
            while (de) {
                next = de->next;
                fn(privdata, de);
                de = next;
            }

            //为什么这里能直接往上递增呢?
            //假如是小表变大表, 上个游标xxabc的xx肯定是00, 所以在读大表时, 可以直接倒序往上加, 直到xx再次变00, 也就是穷举xx
            //假如是大表变小表, 上个游标xxabc的xx很可能不为00, 假如为01, 那么就代表着00和10是被访问过的了(因为大表变小表, 当前游标之前的都被扫描过了), 最终才会返回01的, 所以遍历大表时高位序遍历不仅能把迁移的节点后槽遍历完, 还不重复
            //可以参考 https://www.infoq.cn/article/piaabmlotbqcjkrt7l2v   https://tech.meituan.com/2018/07/27/redis-rehash-practice-optimization.html
            //以前是 v = (((v | m0) + 1) & ~m0) | (v & m0);   //BUG
            /* Increment the reverse cursor not covered by the smaller mask.*/
            //假如m1为...011111, ~m1就是...100000, v |= ~m1 就相当于 ...1xxabc
            v |= ~m1;
            //反转, 结果是 abcxx11...111
            v = rev(v);
            v++;
            v = rev(v);

            /* Continue while bits covered by mask difference is non-zero */
            //如果m0是...000111, m1是...011111, 那么 m0^m1就是...011000, 也就是只保留m1的高位
            //v & (m0 ^ m1) 就是, 当v相对于m0的高位都为0时, 退出循环
        } while (v & (m0 ^ m1));
    }

    //减少停顿rehash的状态
    dictResumeRehashing(d);

    return v;
}

• 进入扫描之前, 如果字典正在rehash, 则暂时rehash状态加1
• redis的dictscan主要处理两种情况, 第一是字典没有在rehash状态, 那么直接根据传入的游标, 扫描对应的hash槽, 然后遍历节点给回调函数进行处理, 最后反转游标二进制位, 加1, 再反转形成新游标返回.
• 第二种情况是, 字典正在rehash, 那么字典中就相当于有两个hash表, 也就是原来同一个槽的数据可能会分散到两张hash表多个槽中, 但是这些分散的槽的位置都是相对原来的槽位置变化固定的, 我们可以根据传入的游标先在小表中扫描节点处理, 然后再扫描游标在大表rehash后的槽, 这就保证了数据不遗漏.
• 返回新游标之前, 先减少停顿rehash的状态
• 注意: 3.2版以前, 在rehash时, 遍历大表的hash槽 v = (((v | m0) + 1) & ~m0) | (v & m0); 的逻辑是有bug的, 具体情况可以参考美团针对Redis Rehash机制的探索和实践, 新逻辑如何解决这个bug, 我在代码注释上有写.

7.3 神奇的二进制反转算法(rev)解读

// 对 v 进行二进制逆序操作, 这个算法有点意思, 可以看一下 https://www.cnblogs.com/gqtcgq/p/7247077.html
static unsigned long rev(unsigned long v) {
    //CHAR_BIT 一般是8位, sizeof 表示v的字节, long是4个字节, 也就是 s=32, 也就是二进制的 100000
    unsigned long s = CHAR_BIT * sizeof(v); // bit size; must be power of 2
    //~0UL 相当于32个1
    unsigned long mask = ~0UL;
    //s >>= 1 第一次移动之后就是 010000, 也就是16, 第三次为8, 依次类推4, 2, 1, 最多向右移动6次就为0了, 也就是说while有5次的遍历操作
    while ((s >>= 1) > 0) {
        //mask << s相当于左移s位, 也就是保留低s位, 最终变成高s位为1, 低s位为0
        //mask ^= (mask << s), mask结果为只有低s位都为1, 高s位都是0, 如: 也就是高16位都为0, 低16位都为1
        mask ^= (mask << s);
        //(v >> s) & mask相当于将高s位移动到低s位
        //~mask表示高s位都是1, 低s位都是0, (v << s) & ~mask 相当将低s位移动到高s位
        //将两者 | , 表示将高s位与低s位互换了
        v = ((v >> s) & mask) | ((v << s) & ~mask);
    }
    //返回倒置的二进制
    return v;
}

• 这个算法对于32位long的反转大概思路是, 先对调相邻的16位, 再对调相邻的8位, 再对调相邻的4位, 再对调相邻的2位, 最终完成反转.
• redis实现的方法要反转的位是动态计算的, 可以是64位也可以是32位.
• 如果有时间, 可以自己演算一下, 详细的演算可以参考: 翻转整数的二进制位
• leetCode上也有对应的算法题哈, 颠倒二进制位