Redis源码剖析与实战 学习笔记 Day3 如何实现一个性能优异的Hash表?

哈希表是一种非常关键的数据结构,在计算机系统中发挥着重要作用。
它的底层是数组+链表,通过哈希计算,能以 O(1) 的复杂度快速根据key查询到数据。

image.png

(1) 数据结构-哈希表

假设让我们自己实现一个哈希表,我们要考虑哪些方面?

  1. 哈希表提供的功能
  2. 哈希表操作的时间复杂度为O(1)
  3. 哈希表的容量与扩容

(1.1) 提供的功能

新建哈希表、新增数据、修改数据、删除数据、查询数据

(1.2) 时间复杂度O(1)

要想使时间复杂度为O(1),要通过高效的定位方法,比如hash函数
但是hash函数有个问题,可能会哈希冲突,冲突后有多种方法 链地址法、 开放定位法、 再哈希法,这里我们使用链地址法实现。

    /** 哈希函数 */
    int hash(Object key) {
        int h;
        // h = key.hashCode() 为第一步 取hashCode值
        // h ^ (h >>> 16)  为第二步 高位参与运算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

链式哈希的链不能太长,否则会降低 哈希表性能。
链表哈希的链表太长时可以转换为红黑树提高查询性能。

(1.3) 哈希表容量与扩容

这里我们在创建哈希表的时候支持指定容量
扩容时容量是原来的2倍

    public void resize(){
        //todo
    }

如果容量特别大,内存不够怎么办?


(2) Redis里的哈希表

对于 Redis 键值数据库来说,哈希表既是键值对中的一种值类型,同时,Redis 也使用一个全局 哈希表来保存所有的键值对,从而既满足应用存取 Hash 结构数据需求,又能提供快速查询功能。

在实际应用 哈希表时,当数据量不断增加,它的性能就经常会受到哈希冲突和 rehash 开销的影响。

针对哈希冲突,Redis 采用了链式哈希,在不扩容哈希表的前提下,将具有相同哈希值的数据链接起来,以便这些数据在表中仍然可以被查询到;
对于 rehash 开销,Redis 实现了渐进式 rehash 设计,进而缓解了 rehash 操作带来的额外开销对系统的性能影响。

dict.h 文件定义了 哈希表的结构、哈希项,以及 哈希表的各种操作函数,
dict.c 文件包含了 哈希表各种操作的具体实现代码。

源码 https://github.com/redis/redi...

   https://github.com/redis/redis/blob/6.0/src/dict.c


(2.1) 哈希表结构定义

/** 
 * 这是哈希表结构。
 * 每个字典都有两个这样的字典,因为我们实现了增量重新哈希,从旧表到新表。 
 */
typedef struct dictht {
    dictEntry **table;  // 一维数组的指针
    unsigned long size;  // 哈希表大小
    unsigned long sizemask;  // size-1 = (2^n - 1),比2^n少1,用于计算key对应桶的下标
    unsigned long used;  // 
} dictht;


/**
 * 哈希表节点
 */
typedef struct dictEntry {
    void *key; // 存储的key
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;  // 存储的值
    struct dictEntry *next; // 链表的下一个节点
} dictEntry;

可以看到 哈希表dictht里定义了 二维数组()、哈希表大小、
哈希节点里定义了 键(key)、值(v)、链表的下一个节点(next),其中值(v)是一个联合体,联合体中包含了指向实际值的指针 *val,还包含了无符号的 64 位整数、有符号的 64 位整数,以及 double 类的值。

为什么要使用联合体呢?
这种实现方法是一种节省内存的小技巧,因为当值为整数或双精度浮点数时,由于其本身就是64位,就可以不用指针指向了,而是可以直接存在键值对的结构体中,这样就避免了再用一个指针,从而节省了内存空间。


(2.2) 哈希表提供的功能

操作函数算法复杂度
创建一个新字典dictCreateO(1)
添加新键值对到字典dictAddO(1)
添加或更新给定键的值dictReplaceO(1)
在字典中查找给定键所在的节点dictFindO(1)
在字典中查找给定键的值dictFetchValueO(1)
从字典中随机返回一个节点dictGetRandomKeyO(1)
根据给定键,删除字典中的键值对dictDeleteO(1)
清空并释放字典dictReleaseO(N)
清空并重置(但不释放)字典dictEmptyO(N)
缩小字典dictResizeO(N)
扩大字典dictExpandO(N)
对字典进行给定步数的 rehashdictRehashO(N)
在给定毫秒内,对字典进行rehashdictRehashMillisecondsO(N)


(2.2.1) 创建一个哈希表

/** 创建一个新的哈希表 */
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]); // 重置ht[0]
    _dictReset(&d->ht[1]); // 重置ht[1]
    d->type = type; // 设置哈希表类型
    d->privdata = privDataPtr; // 
    d->rehashidx = -1; // 设置成-1 代表没有进行rehash
    d->iterators = 0; // 
    return DICT_OK;
}
/* Reset a hash table already initialized with ht_init().
 * NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{
    ht->table = NULL; // 哈希表的数组置为null
    ht->size = 0; // 哈希表长度设置为0
    ht->sizemask = 0; // 掩码设置为0
    ht->used = 0; // 已使用空间设置为0
}


(2.2.2) 哈希表添加元素

// file: dict.c

/** 
 * 往哈希表添加一个元素
 * 
 * @param *d
 * @param *key
 * @param *val
 */
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;
}
/* 
 *  低级添加或查找:
 *  此函数添加条目但不是设置值,而是将 dictEntry 结构返回给用户,这将确保按照他的意愿填充值字段。
 *
 *  这个函数也是直接暴露给用户API调用的,主要是为了在hash值里面存储非指针,例如:
 *
 *    entry = dictAddRaw(dict,mykey,NULL);
 *    if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
 *
 *  返回值:
 *    如果键已经存在,则返回 NULL,如果 existing 不为 NULL,则“*existing”将填充现有条目。
 *    如果添加了键,则返回哈希条目以供调用者操作。
 */
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    // 如果正在rehash,进行rehash   这里只迁移一个桶,几乎对性能无影响
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 获取元素下标  如果元素已经存在返回-1 
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* 分配内存并存储新条目。
     * 在顶部插入元素,假设在数据库系统中,最近添加的条目更有可能被更频繁地访问。*/

    // 如果在进行rehash,往ht[1]里添加元素 
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 为新节点分配内存
    entry = zmalloc(sizeof(*entry));
    // 把新节点插入到链表的头部
    entry->next = ht->table[index];
    // 更新链表头结点
    ht->table[index] = entry;
    // 哈希表已使用节点数+1
    ht->used++;

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

/** 设置key */
#define dictSetKey(d, entry, _key_) do { \
    if ((d)->type->keyDup) \
        (entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
    else \
        (entry)->key = (_key_); \
} while(0)
// file:  dict.h

/** 设置val */
#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)


(2.2.3) 哈希表更新元素

/**
 * 添加或覆盖:
 *  添加一个元素,如果键已经存在则丢弃旧值。
 *  如果该键是从头开始添加的,则返回 1,
 *  如果已经存在具有该键的元素,则返回 0,并且 dictReplace() 刚刚执行了值更新操作。
 */
int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, *existing, auxentry;

    // 添加条目
    entry = dictAddRaw(d,key,&existing);
    if (entry) {
        // 设置值
        dictSetVal(d, entry, val);
        return 1;
    }

    /* 设置新值并释放旧值。 
     * 请注意,按此顺序执行此操作很重要,因为值可能与前一个值完全相同。 
     * 在这种情况下,想想引用计数,你想要递增(设置),然后递减(自由),而不是相反。
     */
    auxentry = *existing;
    // 覆盖值
    dictSetVal(d, existing, val);
    // 释放原来的
    dictFreeVal(d, &auxentry);
    return 0;
}


(2.2.4) 哈希表查找元素

/**
 * 
 * @param *d
 * @param *key
 */
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    // 哈希表为空
    if (dictSize(d) == 0) return NULL; /* dict is empty */
    // 哈希表正在rehash,执行rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // 根据key查找桶 
    h = dictHashKey(d, key);
    // ht[0] ht[1] 都会查,所以 table=0 table<=1 
    for (table = 0; table <= 1; table++) {
        // 获取下标
        idx = h & d->ht[table].sizemask;
        // 链表头结点
        he = d->ht[table].table[idx];
        // 遍历链表
        while(he) {
            // key相同 或 key对比相等
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}


(2.2.5) 哈希表删除元素

/** 
 * 删除一个元素
 * 成功时返回 DICT_OK,如果找不到该元素则返回 DICT_ERR。 
 * 
 * @param *ht
 * @param *key
 */
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
/**
 * 搜索并删除元素。
 * 这是 dictDelete() 和 dictUnlink()的辅助函数,请检查这些函数的顶部注释。
 * 
 * @param *d
 * @param *key 
 * @param nofree 
 */
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    // ht[0] ht[1] 已使用大小为0,返回null
    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

    // 如果正在rehash,执行rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    // 获取hash值
    h = dictHashKey(d, key);
    // ht[0] ht[1] 都会查,所以 table=0 table<=1 
    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 || 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; // 设置next节点为头结点,next有可能是null
                if (!nofree) {
                    // 释放key
                    dictFreeKey(d, he);
                    // 释放val
                    dictFreeVal(d, he);
                    // 释放entry
                    zfree(he);
                }
                // 更新使用元素个数
                d->ht[table].used--;
                return he;
            }
            // 更新前驱节点
            prevHe = he;
            // 处理下一个节点
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }

    // 没有找到key
    return NULL;
}


(2.3) 哈希表扩容

哈希表扩容是指 rehash 操作,其实就是指扩大 哈希表空间。

Redis rehash流程

  1. Redis里保存了两个 Hash表 ht[0]和 ht[1],用于 rehash 时交替保存数据;
  2. 在正常服务请求阶段,所有的键值对写入哈希表 ht[0];
  3. 当进行 rehash 时,键值对被迁移到哈希表 ht[1]中;
  4. 当迁移完成后,ht[0]的空间会被释放,并把 ht[1]的地址赋值给 ht[0],ht[1]的表大小设置为 0

这样一来,又回到了正常服务请求的阶段,ht[0]接收和服务请求,ht[1]作为下一次 rehash 时的迁移表。

typedef struct dict {
    dictType *type; // 类型
    void *privdata; //
    dictht ht[2]; // 2个哈希表
    long rehashidx; // rehashidx == -1 则rehashing没有进行  
    unsigned long iterators; // 当前正在运行的迭代器数
} dict;

在rehashing时,rehashidx对应要操作的 ht[0].table[rehashidx] 的桶


(3) rehash

rehash的整体流程
在

(3.1) rehash的触发条件-什么时候发生rehash

  1. 在哈希表为空时,调用_dictExpandIfNeeded会触发哈希表初始化,默认大小为4。
  2. 在哈希表不为空时,触发rehash需要同时满足2个条件:

    • 已使用桶数量:哈希表桶容量 达到了 1:1 的比例 (ht[0].used > ht[0].size)
    • 允许调整哈希表的大小(dict_can_resize=1) 或者 元素/桶 > 5 (dict_force_resize_ratio>5)

具体代码如下:

// file: dict.c 

/** 
 * 如果需要扩展哈希表
 *
 * @param *d
 */
static int _dictExpandIfNeeded(dict *d)
{
    // 增量rehash正在进行中,返回   通过 rehashidx != -1 判断
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果哈希表为空,则将其扩展到初始大小。 初始大小默认为4 
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* 
     * 如果 已使用桶数量:哈希表桶容量 达到了 1:1 的比例,
     * 并且我们被允许调整哈希表的大小(全局设置) 或者 应该避免它但是元素/桶之间的比例超过了“安全”阈值 5 ,
     * 我们调整大小使桶的数量为原来2倍。
     * 
     * If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))  // dict_force_resize_ratio 默认为5 
    {
        // 扩容
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

dict_can_resize 变量值默认是1,可以在 dictEnableResize、 dictDisableResize 函数中设置

// file: dict.c 

/* 
 * 使用 dictEnableResize() / dictDisableResize() 我们可以根据需要启用/禁用哈希表的大小调整。 
 * 这对 Redis 来说非常重要,因为我们使用写时复制,并且不想在有子进程正在执行保存操作时移动太多内存。
 *
 * 请注意,即使将 dict_can_resize 设置为 0,也不会阻止所有调整大小:
 *   如果元素数量与桶数之间的比率 > dict_force_resize_ratio,则哈希表仍然允许增长。
 */
static int dict_can_resize = 1;

void dictEnableResize(void) {
    dict_can_resize = 1;
}

void dictDisableResize(void) {
    dict_can_resize = 0;
}

dict_force_resize_ratio 值在 dict.c 文件中定义,默认是5

在哪些函数里调用了_dictExpandIfNeeded

_dictExpandIfNeeded 是被 _dictKeyIndex 函数调用的
_dictKeyIndex 函数又会被 dictAddRaw 函数调用
dictAddRaw 会被 dictAdd dictRelace dictAddorFind sentinelLeaderIncr setTypeAdd zunionInterGenericCommand 函数调用

当我们往 Redis 中写入新的键值对或是修改键值对时,Redis 都会判断下是否需要进行 rehash。
这里你可以参考下面给出的示意图,其中就展示了 _dictExpandIfNeeded 被调用的关系。


(3.2) rehash如何执行?

为什么要实现渐进式rehash?

因为哈希表在执行rehash时,由于哈希表扩容,key对应的位置会改变,很多key就需要从原来的位置复制到新的位置。
而在键复制时,由于Redis主线程无法执行其他请求,会阻塞主线程,如果要复制的键特别多,Redis在执行哈希表扩容时,此时Redis Server对外是不可用的,这个是我们不能接受的。

为了避免Redis Server在哈希表扩容时不可用,提出了渐进式 rehash 的方法。
相当于把一次要干的很多事情分成多次要做的小事情。 把一次要复制的100万个key 转换为 10万次每次复制10个key,这样既不影响其他请求,也把哈希表扩容了。

渐进式rehash在代码层面是如何实现的呢?
有两个关键函数:dictRehash 和 _dictRehashStep。

/* 
 * 执行N步增量rehashing。 
 * 如果仍有键从旧哈希表移动到新哈希表,则返回 1,否则返回 0。
 *
 * 请注意,重新散列步骤包括将一个桶(在使用链表时可能有不止一个键)从旧哈希表移动到新哈希表,
 * 但是由于哈希表的一部分可能由空白组成,因此不能保证 这个函数甚至会重新散列一个桶,
 * 因为它总共最多访问 N*10 个空桶,避免它所做的工作量将不受限制,并且该函数可能会阻塞很长时间。
 *
 * @param *d
 * @param n
 */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; // 最多访问10倍的空桶 一个桶对应一个数组下标
    // 如果哈希表没有进行rehashing 返回0
    if (!dictIsRehashing(d)) return 0;
    
    // 循环
    // n>0 并且 哈希表里已使用元素 > 0 时,进行
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        // 避免ht[0]数组下标越界 
        assert(d->ht[0].size > (unsigned long)d->rehashidx);

        // 哈希表ht[0]对应数组下标的元素为null 也就是 桶对应的元素为null
        while(d->ht[0].table[d->rehashidx] == NULL) {
            // 全局rehashidx+1  这里的rehashidx 就是要操作的 ht[0].table的下标对应的桶
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        // 获取ht[0].table[rehashidx] 对应的桶
        de = d->ht[0].table[d->rehashidx];

        // 反转链表-尾插法
        // 遍历链表  将这个桶中的所有键从旧的ht[0] 移到新的ht[1] 
        while(de) {
            uint64_t h;
            
            nextde = de->next; // 下一个链表节点
            // 获取key在新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--; // 更新ht[0]已使用个数
            d->ht[1].used++; // 更新ht[1]已使用个数

            de = nextde; // 指向下一个链表节点
        }
        // 把ht[0].table[d->rehashidx] 对应桶的链表置空  
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++; // 更新rehashidx
    }

    // 判断ht[0]的数据是否全部迁移完成 
    if (d->ht[0].used == 0) {
        // 释放ht[0]内存空间
        zfree(d->ht[0].table);
        // 把ht[0]指向ht[1],以便接受正常的请求
        d->ht[0] = d->ht[1];
        // 重置ht[1]的大小为0
        _dictReset(&d->ht[1]);
        // 设置全局哈希表的rehashidx标识为-1,表示rehash结束
        d->rehashidx = -1;
        //返回0,表示ht[0]中所有元素都迁移完
        return 0;
    }

    //返回1,表示ht[0]中仍然有元素没有迁移完
    return 1;
}
/**
 * 此函数仅执行一个重新散列步骤,并且仅当没有安全迭代器绑定到我们的散列表时。 
 * 当在重新散列中间有迭代器时,不能弄乱两个散列表,否则某些元素可能会丢失或重复。
 *
 * 此函数由字典中的常见查找或更新操作调用,以便哈希表在主动使用时自动从 H1 迁移到 H2。
 *
 * @param *d
 */
static void _dictRehashStep(dict *d) {
    // rehash一个桶的数据
    if (d->iterators == 0) dictRehash(d,1);
}
/* 
 * 以 ms+"delta" 毫秒rehash。 
 * "delta" 的值大于0,多数情况下小于1。 
 * 确切的上限取决于 dictRehash(d,100) 的运行时间。
 * 
 * @param *d
 * @param ms
 */
int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds(); // ms时间戳
    int rehashes = 0;
    
    while(dictRehash(d,100)) { // 一次rehash 100个桶
        rehashes += 100;
        // 超过指定时间,break
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

dictAddRaw -> _dictRehashStep
dictGenericDelete -> _dictRehashStep
dictFind -> _dictRehashStep
dictGetRandomKey -> _dictRehashStep
dictGetSomeKeys -> _dictRehashStep

_dictRehashStep -> dictRehash
incrementallyRehash -> dictRehashMilliseconds -> dictRehash

(3.3) 渐进式hash时,增删改查操作哪个ht?

当部分bucket 执行 rehash,部分bucket还没有执行rehash,这时增删查请求操作是对ht[1]操作,还是ht[0] ?

在新增操作时,调用dictAdd,会调用dictAddRaw,有一行代码专门对rehash做了处理,会保存到ht[1],ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

在更新操作时,调用dictReplace,也会调用dictAddRaw,原理同上

在删除操作时,调用dictDelete方法,会对ht[0]和ht[1]都做删除, for (table = 0; table <= 1; table++) 这行代码就是要对2个哈希表分表处理

查询操作,调用dictFind方法,也是会对两个ht都查询,for (table = 0; table <= 1; table++),先查ht[0],查到了返回,没有查到再查ht[1]

(3.4) rehash扩容后有多大-rehash的结果

在 Redis 中,rehash 对 哈希表空间的扩容是通过调用 dictExpand 函数来完成的。

dictExpand 函数的参数有两个,一个是要扩容的 哈希表,另一个是要扩到的容量


/**
 * 扩展或创建哈希表
 * 
 * @param *d 要扩容的哈希表
 * @param size 扩容后的容量
 */
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); // 获取扩容后的大小 (realsize >= size 并且 realsize是2的幂次方)

    // 扩容后的大小 = 当前大小,返回错误
    if (realsize == d->ht[0].size) return DICT_ERR;

    // 为新的哈希表分配内存 并 将所有指针初始化为NULL
    n.size = realsize; // 大小
    n.sizemask = realsize-1; //  
    n.table = zcalloc(realsize*sizeof(dictEntry*));  // 分配内存
    n.used = 0;  // 未使用

    // 这是第一次初始化吗? 如果是这样,那不是真正的重新哈希,我们只是设置第一个哈希表,以便它可以接受keys。  
    if (d->ht[0].table == NULL) { // 未初始化
        d->ht[0] = n;
        return DICT_OK;
    }

    // 为 增量哈希 准备第二个哈希表 // Prepare a second hash table for incremental rehashing
    d->ht[1] = n; // 设置哈希表
    d->rehashidx = 0; // 设置 rehash index
    return DICT_OK;
}
/* 哈希表的容量是2的幂次方 */
static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE; // 哈希表初始大小默认是4 

    // 如果要扩容的大小已经超过最大值,则返回最大值加1
    if (size >= LONG_MAX) return LONG_MAX + 1LU;

    // 这里是计算2的幂次方 获取一个>=size 的最小2的幂次方
    while(1) {
        // 如果扩容大小大于等于要扩容的值,就返回当前值
        if (i >= size)
            return i;
        i *= 2;
    }
}

为什么哈希表的容量要是2的幂次方?
因为容量是2的幂次方,进行计算可以转换为位运算,位运算计算比较快。


(4) Redis里的Hash函数

Hash 函数会影响 哈希表的查询效率及哈希冲突情况,那么,你能从 Redis 的源码中,找到 哈希表使用的是哪一种 Hash 函数吗?

在rehash时,dictRehash函数里 从老的ht[0]把数据迁移到ht[1]的时候,需要计算key的hash,与sizemask计算获取数组下标,对应代码是 h = dictHashKey(d, de->key) & d->ht[1].sizemask;

dictHashKey(d, de->key) 调用了哈希函数,点进这个方法

调用 #define dictHashKey(d, key) (d)->type->hashFunction(key),也就是使用的 hashFunction(key) 这个函数

想了想,Hash有多种实现,而且struct dict也定义了dictType *type

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;

看到这儿时,找了一下引用dictType的地方,发现有很多,排除掉redis-cli.c sentinel.c 感觉 dict.c 和 server.c里的概率更大
看了一下server.c里的引用,有setDictType zsetDictType dbDictType 而且注释里写着 /* hash function */
看了dictSdsHash,对应 dictGenHashFunction

uint64_t dictGenHashFunction(const void *key, int len) {
    return siphash(key,len,dict_hash_function_seed);
}

发现使用的siphash.c文件里的siphash

这个方法不太容易看懂

uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k) {
#ifndef UNALIGNED_LE_CPU
    uint64_t hash;
    uint8_t *out = (uint8_t*) &hash;
#endif
    uint64_t v0 = 0x736f6d6570736575ULL;
    uint64_t v1 = 0x646f72616e646f6dULL;
    uint64_t v2 = 0x6c7967656e657261ULL;
    uint64_t v3 = 0x7465646279746573ULL;
    uint64_t k0 = U8TO64_LE(k);
    uint64_t k1 = U8TO64_LE(k + 8);
    uint64_t m;
    const uint8_t *end = in + inlen - (inlen % sizeof(uint64_t));
    const int left = inlen & 7;
    uint64_t b = ((uint64_t)inlen) << 56;
    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;

    for (; in != end; in += 8) {
        m = U8TO64_LE(in);
        v3 ^= m;

        SIPROUND;

        v0 ^= m;
    }

    switch (left) {
    case 7: b |= ((uint64_t)in[6]) << 48; /* fall-thru */
    case 6: b |= ((uint64_t)in[5]) << 40; /* fall-thru */
    case 5: b |= ((uint64_t)in[4]) << 32; /* fall-thru */
    case 4: b |= ((uint64_t)in[3]) << 24; /* fall-thru */
    case 3: b |= ((uint64_t)in[2]) << 16; /* fall-thru */
    case 2: b |= ((uint64_t)in[1]) << 8; /* fall-thru */
    case 1: b |= ((uint64_t)in[0]); break;
    case 0: break;
    }

    v3 ^= b;

    SIPROUND;

    v0 ^= b;
    v2 ^= 0xff;

    SIPROUND;
    SIPROUND;

    b = v0 ^ v1 ^ v2 ^ v3;
#ifndef UNALIGNED_LE_CPU
    U64TO8_LE(out, b);
    return hash;
#else
    return b;
#endif
}

总结

1、Redis 中的 dict 数据结构,采用「链式哈希」的方式存储,当哈希冲突严重时,会开辟一个新的哈希表,翻倍扩容,并采用「渐进式 rehash」的方式迁移数据

2、所谓「渐进式 rehash」是指,把很大块迁移数据的开销,平摊到多次小的操作中,目的是降低主线程的性能影响

3、Redis 中凡是需要 O(1) 时间获取 k-v 数据的场景,都使用了 dict 这个数据结构,也就是说 dict 是 Redis 中重中之重的「底层数据结构」

4、dict 封装好了友好的「增删改查」API,并在适当时机「自动扩容、缩容」,这给上层数据类型(Hash/Set/Sorted Set)、全局哈希表的实现提供了非常大的便利

5、例如,Redis 中每个 DB 存放数据的「全局哈希表、过期key」都用到了 dict:

6、「全局哈希表」在触发渐进式 rehash 的情况有 2 个:

  • 增删改查哈希表时:每次迁移 1 个哈希桶(文章提到的 dict.c 中的 _dictRehashStep 函数)
  • 定时 rehash:如果 dict 一直没有操作,无法渐进式迁移数据,那主线程会默认每间隔 100ms 执行一次迁移操作。这里一次会以 100 个桶为基本单位迁移数据,并限制如果一次操作耗时超时 1ms 就结束本次任务,待下次再次触发迁移(文章没提到这个,详见 dict.c 的 dictRehashMilliseconds 函数)

(注意:定时 rehash 只会迁移全局哈希表中的数据,不会定时迁移 Hash/Set/Sorted Set 下的哈希表的数据,这些哈希表只会在操作数据时做实时的渐进式 rehash)

7、dict 在负载因子超过 1 时(used: bucket size >= 1),会触发 rehash。但如果 Redis 正在 RDB 或 AOF rewrite,为避免父进程大量写时复制,会暂时关闭触发 rehash。但这里有个例外,如果负载因子超过了 5(哈希冲突已非常严重),依旧会强制做 rehash(重点)

8、dict 在 rehash 期间,查询旧哈希表找不到结果,还需要在新哈希表查询一次

参考资料

https://weikeqin.com/tags/redis/
[1] Redis源码剖析与实战 - 03 如何实现一个性能优异的Hash表?
[2] Redis设计与实现 - 字典

Redis源码剖析与实战 - 03 如何实现一个性能优异的Hash表? https://time.geekbang.org/col...

评论

暂无评论