redis6.0源码分析:字典扩容与渐进式rehash

文章目录

  • 字典
    • 数据结构
      • 结构设计
      • dictType字典类型
      • 为什么字典有两个哈希表?
      • 哈希算法
  • 扩容机制
    • 扩容前置知识
      • 字典存在几种状态?
      • 容量相关的关键字段定义
      • 字典的容量都是2的幂次方
    • 扩容机制
      • 字典什么时候会扩容?
      • 扩容的阈值 & 扩容的倍数
      • 哪些方法会触发扩容?
      • 触发扩容后会怎么扩容?
  • 渐进式rehash
    • 前置知识
      • 为什么要rehash?
      • 渐进式rehash?
    • 什么时候会rehash?
    • rehash流程
      • 被动式迁移
      • 主动式迁移
  • 问题
    • 哈希冲突时,为什么都是头插入?
    • rehash阶段遇到读写事件会发生什么?
      • 读事件
      • 写事件
    • 扩容 & rehash期间,如果新增过快,又到了扩容的阈值会怎么样?
    • rehash每次迁移多少数据?

字典

数据结构

结构设计

redis的字典的结构定义主要分为三块结构体,dict,dictht,dictEntry,它们之间的关系如下:

在这里插入图片描述

从上图中,其实我们可以看出,Redis 的字典设计,是通过数组 + 链表的方式去实现。

代码实现

/* 字典数据结构 */
typedef struct dict {dictType *type;		// 字典类型,会跟 hash 函数等方法的具体实现有关void *privdata;		// 私有数据dictht ht[2];		// 一个字典,含有两个哈希表long rehashidx; 	// 代表 rehashing 到了什么位置,rehashidx = -1 						  // 代表未进行 rehashunsigned long iterators; // 当前正在迭代的迭代器数, number of iterators currently running 
} dict;/* 哈希表, HashTable, 简写 ht */
typedef struct dictht {dictEntry **table; 		// 节点数组,可知 ht 的结构是数组 + 链表构成unsigned long size;		// table 数组的大小,即 ht 的大小// table 大小的掩码,等于 size - 1, 就是用于获取 key 索引运算的// index = hash(key) & size - 1 = hash(key) & sizemaskunsigned long sizemask;unsigned long used; 	// ht 表中已有键值对的个数,并非 table 数组占用个数
} dictht;/* 哈希表节点,单个 Node */
typedef struct dictEntry {void *key; 				// key, 存储哈希表的 keyunion {void *val;uint64_t u64;int64_t s64;double d;} v; 					// value, 存储哈希表的 valuestruct dictEntry *next; // 单链表结构,指向下一个节点,用于解决哈希冲突
} dictEntry;

如果代码不够具象,也可以结合下图一起思考下

在这里插入图片描述

dictType字典类型

dictType 属性的知识点属于额外补充知识啦,跟扩容也没有太大关系。字典类型的概念是为了多态字典而存在的。即每种 DictType 都会实现一簇操作于特定键值的函数。说白了就是 Redis 为用途不同的字典设置了不同类型操作键值的特定函数

typedef struct dict {dictType *type;...
} dict;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 ? 它们的作用和承担的角色分别是什么?

  • 因为 redis 是单进程单线程模型,而且既要支撑一个大容量,还要保持高性能的读写性能,所以不同于 Java HashMap 的扩容是在本体进行。而是由两个哈希表 + 渐进式 rehash 的方式来实现扩容机制的。由此实现平滑扩容,又不阻塞读写
  • 通常时候,字典的数据都是在第一个哈希表 ht[0] 进行的。当字典判断需要扩容的时候,就会停止对 ht[0] 进行写操作,而是对 ht[1] 赋予一个 2 倍大小的新哈希表,并将所有写操作指向 ht[1], 此时表示哈希表扩容完成,随后进入 rehashing 阶段,即开始渐进式数据迁移
  • 在 rehashing 的过程中,ht[0] 会继续保持对原有数据的读操作,而扩容后新写的数据的读操作则在 ht[1] 进行, 直到 ht[0] 的所有数据迁移到 ht[1] 后,则直接 ht[0] = ht[1], 完成整个扩容 & rehash 操作。

所以我们可以简单的总结出两个哈希表分别承担的角色是

  • ht[0] 是日常主要的数据存储表, 对外提供读写能力
  • ht[1] 作为扩容时使用的临时表,保证扩容机制平滑进行

哈希算法

Redis 的字典在 Redis 3.2 以前采用的是 murmurhash2 实现的,在 Redis 4.0 之后则采用 siphash

我们在 src/dict.c 可以看到获取 key 的哈希值是通过 dictHashKey 实现的,所以我们找 dictHashKey 方法

 h = dictHashKey(d, de->key) & d->ht[1].sizemask;

src/dict.h 头文件这么定义了 dictHashKey 方法, 那么 type 是啥玩意?type->hashFunction(key) 又是啥方法?

#define dictHashKey(d, key) (d)->type->hashFunction(key)

这个时候就需要翻到 dict 定义中,有一个 dictType 类型,代表字典的类型

typedef struct dict {dictType *type;...
} dict;typedef struct dictType {uint64_t (*hashFunction)(const void *key); // 某种 dictType 类型的 hash functionvoid *(*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;

好的, dict 的 type 是那种呢?我们看到 src/server.cinitServer 函数的一段代码

void initServer(...) {.../* Create the Redis databases, and initialize other internal state. */for (j = 0; j < server.dbnum; j++) {server.db[j].dict = dictCreate(&dbDictType,NULL);server.db[j].expires = dictCreate(&keyptrDictType,NULL);server.db[j].expires_cursor = 0;server.db[j].blocking_keys = dictCreate(&keylistDictType,NULL);server.db[j].ready_keys = dictCreate(&objectKeyPointerValueDictType,NULL);server.db[j].watched_keys = dictCreate(&keylistDictType,NULL);server.db[j].id = j;server.db[j].avg_ttl = 0;server.db[j].defrag_later = listCreate();listSetFreeMethod(server.db[j].defrag_later,(void (*)(void*))sdsfree);}...
}/* Db->dict, keys are sds strings, vals are Redis objects. */
dictType dbDictType = {dictSdsHash,                /* hash function */NULL,                       /* key dup */NULL,                       /* val dup */dictSdsKeyCompare,          /* key compare */dictSdsDestructor,          /* key destructor */dictObjectDestructor   /* val destructor */
};

我们得知 dict 是 db 的存放数据的字典,它传入了 dbDictType 类型。在定义中,我们也得知 hash function 具体实现是 dictSdsHash, 所以我们就找 dictSdsHash 即可, 在 src/server.c 中,我们找到了

uint64_t dictSdsHash(const void *key) {return dictGenHashFunction((unsigned char*)key, sdslen((char*)key));
}

所以得知调用入口是 dictGenHashFunction 方法,回到 src/dict.c 代码如下

//https://github.com/redis/redis/blob/unstable/src/dict.c
uint64_t dictGenHashFunction(const void *key, int len) {return siphash(key,len,dict_hash_function_seed);
}

好的,真相了,那就是 spihash 算法。

扩容机制

在上面了解了 dict 的数据结构的基础上,我们来了解 dict 是如何进行扩容,以及扩容后数据是如何迁移的?但在了解扩容机制和数据迁移之间,我们先来问几个问题

  • dict 存在几种状态?
  • dict 初始化?
  • dict 什么时候扩容?扩容阀值是多少?扩容倍数是多少?
  • 哪些地方会触发扩容?怎么扩容?
  • 扩容后,数据如何 rehash ?
  • 一次扩容后的rehash 过程中,由于 key 写入过快,很快又超过了新的扩容阀值,此时怎么办?

然后我们基于以上的问题,一个一个问题来回答和解析

扩容前置知识

字典存在几种状态?

在了解扩容机制之前,我们可以先小小剧透一下, dict 总共就存在 4 种状态

  • table.size 不变,无扩缩容
  • 扩容中
  • 缩容中
  • rehashing 中

了解了状态后,就可以更好的方便我们理解了

容量相关的关键字段定义

扩容状态码

#define DICT_OK 0					// 成功
#define DICT_ERR 1					// 失败

哈希表初始值

#define DICT_HT_INITIAL_SIZE     4	//  哈希表 (ht) size 的初始值

扩容安全阈值

static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;void dictEnableResize(void) {dict_can_resize = 1;
}void dictDisableResize(void) {dict_can_resize = 0;
}
  • Using dictEnableResize() / dictDisableResize() we make possible to enable/disable resizing of the hash table as needed. This is very important for Redis, as we use copy-on-write and don’t want to move too much memory around when there is a child performing saving operations.
  • Note that even when dict_can_resize is set to 0, not all resizes are prevented: a hash table is still allowed to grow if the ratio between the number of elements and the buckets > dict_force_resize_ratio.

字典的容量都是2的幂次方

/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size)
{unsigned long i = DICT_HT_INITIAL_SIZE;if (size >= LONG_MAX) return LONG_MAX + 1LU;while(1) {if (i >= size)return i;i *= 2;}
}
  • size 是要扩容的大小,进入 _dictNextPower 后,会计算得到一个接近 size 的值,且又是 2 的幂次方

扩容机制

字典什么时候会扩容?

那么我们就看下 sre/dict.c_dictExpandIfNeeded 方法即可,因为字典的扩容时需要这个方法去判断,所以我们可以看到字典有三种扩容的渠道

  • 当字典还没有被初始化,即字典的 hashtable[0] 为空时,那我们就初始化字典的第一个 hashtable

ht[0].size = 0

  • 当 hashtable[0] 的键值对数量 >= hashtable[0] 数组的 size 时,且全局设置 dict_can_resize = true, 我们就扩容

    d->ht[0].used >= d->ht[0].size && dict_can_resize = true

  • 当 hashtable[0] 的键值对数量 >= hashtable[0] 数组的 size 时, 且键值对数量已经超过数组大小的 5 倍的安全阀值时,就强制触发扩容

    d->ht[0].used >= d->ht[0].size && d->ht[0].used/d->ht[0].size > dict_force_resize_ratio

static int _dictExpandIfNeeded(dict *d)
{// 如果当前处于 rehash 状态,则直接返回 0 (代表无需扩容,已扩容,新扩容成功)if (dictIsRehashing(d)) return DICT_OK;/* If the hash table is empty expand it to the initial size. */// 如果 hashtable[0] 的大小为 0, 代表整个 dict 还没有被初始化,所以先初始	  // 化字典的第一个 hashtable,初始大小是 4if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);// 当 hashtable[0] 的键值数 >= hashtable[0] 的 entry 数组大小// 且 (dict_can_resize = true 或 hashtable[0] 键值数已超过 hashtable 	 // 节点数组大小的 5 倍的安全阀值) 就会触发扩容// 扩容倍数是已有键值数  (ht.used) 的两倍,注意不是 ht 的 sizeif (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;
}

_dictExpandIfNeededdictExpand 的返回值都是 0 (DICT_OK) 或 1 (DICT_ERR),

  • DICT_OK 代表新扩容成功,正在 rehashing ,无需扩容

  • DICT_ERR 代表非法操作,即非法扩容,扩容失败

    • 或是在 rehashing 阶段进入 dictExpand 函数

    • 或是在 dictExpand 阶段传入扩容 size 小于 当前 used

    • 或是在 dictExpand 阶段

扩容的阈值 & 扩容的倍数

扩容阀值是多少?

相较 Java HashMap 的扩容因子为 0.75, 那么 Redis 字典的扩容因子就是 1, 即容量占比百分百才触发扩容。当然从 _dictExpandIfNeeded 函数中,我们可以看到这并不是绝对的,要取决于 dict_can_resize 的设置是否允许。如果不允许扩容时,那么只有等到 键值对数量/数组大小 > 5 时才会触发扩容

dict_force_resize_ratio 为什么是 5 ?
为什么键值对数量会大于数组大小,甚至超过 5 倍,因为字典的底层数据结构是 array + list。 在键值对接近数组 size 的时候,哈希冲突的概率会越来越大,从而在数组的节点中形成链表。之所以 redis 的安全阀值是 5, 因为 redis 觉得这是底线,5 倍阀值的情况下,数组平均每个节点就是 5 个节点的链表了,再往后冲突,字典的查询性能会逐步下降

扩容倍数是多少?

_dictExpandIfNeeded 方法,我们可以看到,字典的扩容倍数是 2 倍

dictExpand(d, d->ht[0].used*2)

哪些方法会触发扩容?

我们来看下什么地方会调用 _dictExpandIfNeeded 方法,可以看到是 _dictkeyIndex, 可以得知这是一个根据 key 获得其索引位置的函数

/* 方法:获得 key 在 hashtable 的索引* 入参:*d 是当前字典,*key 键,hash 是 key 的哈希值,existing 就是 ht 的节点数组* 返回值:* 	1. -1 代表失败* 		- 可能是扩容失败, 有异常,导致不允许后续行为,所以返回 -1* 		- 也可能是键值已存在,并且不打算覆盖旧值,所以返回 -1*  2. 有值,代表该 key 经过计算,在 ht 的 idx 索引位置* 注意:* 	1. 如果 existing 指针指向有值,并且该值在 ht 中存在,existing 会隐式将对应 	*		entry 带出去给外层调用方法*/
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{unsigned long idx, table;dictEntry *he;if (existing) *existing = NULL;// 如果需要扩容,则扩容,如果扩容失败,则返回 -1/* Expand the hash table if needed */if (_dictExpandIfNeeded(d) == DICT_ERR)return -1;// 遍历 dict 的两个哈希表, 因为 key 可能在 ht[0], 也可能在 ht[1]    for (table = 0; table <= 1; table++) {// mod 运算得到 key 的idx = hash & d->ht[table].sizemask;/* Search if this slot does not already contain the given key */he = d->ht[table].table[idx];// 如果 key 存在,则遍历链表,看 key 是否存在 existing 中,如果存在则返回 -1// 如果 key 不存在,则直接返回该 key 要插入的位置 idxwhile(he) {if (key==he->key || dictCompareKeys(d, key, he->key)) {// 如果 existing 有值,则将存在的 entry 赋值给指针,交给外层调用方if (existing) *existing = he;return -1;}he = he->next;}// 如果 dict 不在 rehashing 状态,就不用遍历 ht[1] 了,因为没有数据if (!dictIsRehashing(d)) break;}// 返回 key 在 ht 节点数组的索引return idx;
}

那么谁又在调用 _dictkeyIndex 呢?是 *dictAddRaw方法,这个方法又是干嘛的呢?它就是向字典插入一个数据的基础方法,会有很多操作方法调用它,来看看

/* 方法:向 dict 插入一个键值对, 并返回新增的节点 entry* 返回值:* 	1. NULL 代表键已存在,不更新*  2. 有值,代表键不存在,并新增成功*/
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{long index;dictEntry *entry;dictht *ht;// 如果当前处于 rehashing 状态,则主动去迁移一个键值数据if (dictIsRehashing(d)) _dictRehashStep(d);/* Get the index of the new element, or -1 if* the element already exists. */// 如果该键值已经存在,则 dictKeyIndex 会返回 -1, 则直接返回 null, 代表没有新增// 如果该键值不存在,属于新增,则将该 key 在 entry 数组的索引返回,并赋值给 indexif ((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. */// 如果处于 rehashing 状态,则向第二个哈希表 ht[1] 插入数据, 反之 ht[0]	ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];// 分配一个 entry 新节点, 并对 ht->table[index] 链表进行头插入 ,used + 1entry = zmalloc(sizeof(*entry));entry->next = ht->table[index];ht->table[index] = entry;ht->used++;// 暂不关心,不影响理解,有兴趣看 src/dict.h/* Set the hash entry fields. */dictSetKey(d, entry, key);// 返回新增节点return entry;
}

我们知道了 *dictAddRaw 是字典的基本插入方法,那么谁会调用它呢?

  • int dictAdd(dict *d, void *key, void *val)
  • int dictReplace(dict *d, void *key, void *val)
  • dictEntry *dictAddOrFind(dict *d, void *key)
// 如果不存在则插入,存在则插入失败
/* 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;dictSetVal(d, entry, val);return DICT_OK;
}
/* Add or Overwrite:* Add an element, discarding the old value if the key already exists.* Return 1 if the key was added from scratch, 0 if there was already an* element with such key and dictReplace() just performed a value update* operation.* * 如果存在则更新,不存在则插入* 新增返回 1, 更新返回 0  */
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.* * 由 dictAddRaw 隐式返回旧值 entry 的 existing 指向,所以我们可以对 existing 指向的 entry 进行新值更新 * * */auxentry = *existing;dictSetVal(d, existing, val);dictFreeVal(d, &auxentry);return 0;
}
/* Add or Find:* dictAddOrFind() is simply a version of dictAddRaw() that always* returns the hash entry of the specified key, even if the key already* exists and can't be added (in that case the entry of the already* existing key is returned.* 没啥好说的** See dictAddRaw() for more information. */
dictEntry *dictAddOrFind(dict *d, void *key) {dictEntry *entry, *existing;entry = dictAddRaw(d,key,&existing);return entry ? entry : existing;
}
  • 单纯的对应 redis 的命令,dictAdd 和 dictReplace 就可以实现 setIfpresent, setIfabsent, set 等命令了

触发扩容后会怎么扩容?

在我们知道了触发扩容的时机,扩容的阀值,扩容的倍数,以及会导致触发扩容的方法后。我们就要来看看扩容的中重头戏了,那就是怎么扩容? ,主要依赖 dictExpand 方法,所以重点看

/* 方法:Expand or create the hash table, 扩容或新建哈希表* 参数:* 	1. *d: 要操作的字典* 	2. size: 想为 *d 字典扩容到 size 大小* 返回值:*  1. DICT_ERR 1 扩容或初始化 ht 失败* 		- 正处于 rehashing ,数据未完全迁移,无法进行下一次扩容* 		- ht[0].used > size, 扩容无意义* 		- ht[0].size == realsize, ht[0] 的 size 已经达到 realsize, 没有扩  	*         容的意义* 	2. DICT_OK  0 扩容或初始化 ht 成功* */
int dictExpand(dict *d, unsigned long size)
{/* the size is invalid if it is smaller than the number of* elements already inside the hash table */// 如果正在处于 rehashing,则返回 1,代表刚刚已进行过扩容,并且数据仍未完成全	  	// 部迁移,无法进行下一次扩容,扩容失败// 或 ht[0] 已有的键值对数量已经大于 size, 则代表将字典继续扩容到 size 大小  		 // 已经没有意义,返回 1, 表示此次扩容无意义if (dictIsRehashing(d) || d->ht[0].used > size)return DICT_ERR;// 到达这里,代表允许扩容,并且将 size 调整到接近 2 的幂次方的一个数值dictht n; /* the new hash table */unsigned long realsize = _dictNextPower(size);// 如果此时的 ht[0] /* 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;n.table = zcalloc(realsize*sizeof(dictEntry*));n.used = 0;// 如果 ht[0] == null, 代表该字典还没有被使用,这是第一次进行初始化,所以将 	// n 赋值给 ht[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. */if (d->ht[0].table == NULL) {d->ht[0] = n;return DICT_OK;}// 如果不是第一次初始化,则将扩容后的新哈希表赋值给 ht[1],并更新 rehashidx 	// = 0 ,代表开始 rehashing, 从 0 开始/* Prepare a second hash table for incremental rehashing */d->ht[1] = n;d->rehashidx = 0;// 扩容成功return DICT_OK;
}

我们知道 dict 就是 redis 的字典数据结构,它有两个 ht, 当 ht[0].used 达到阀值,就会触发字典的扩容,而扩容就是新分配一个 2*ht[0].used 大小的哈希表给 ht[1], 以此循环完成扩容。既然我们知道了 ht[0], ht[1] 是如何搭配工作,完成字典的扩容,那么扩容之后,数据又是如何从旧哈希表迁移到新哈希表的呢?

看后面的 rehash 机制吧

渐进式rehash

前置知识

为什么要rehash?

为什么要 rehash ? 如果你是 Java 技术栈,那么你肯定了解过 HashMap 的数据 rehash ,一种巧妙的二进制操作,就将数据从一个数组迁移到另一个数组里。同理 Redis 字典扩容后也需要一种手段,将数据从一个容器迁移到另一个容器中,只不过 Redis 迁移的方式与 Java 不一致而已

渐进式rehash?

  • 因为 Redis 的字典和 Java 的 HashMap 定位不同, Redis 承载了更大量的数据,并承诺提供高性能的读写,而类 Java 的一次性同步数据迁移会消费大量的时间,而 Redis 又是单进程单线程模型,更不允许因为主线程因为 rehash 而出现长时的阻塞。
  • 所以 Redis 灵机一动,既然无法一次性全量迁移,那么我就一次迁移一部分,直到完成全部数据的迁移,这样单次数据迁移的时间就大大缩小,从而不影响读写,又能保证数据平滑迁移, 所以这也就是渐进式迁移数据的过程

什么时候会rehash?

我们想知道什么时候回开始出发 rehash ? 我们回想下在看扩容的代码时,也就是 dictExpand方法时,最下面有段代码

int dictExpand(dict *d, unsigned long size) {.../* Prepare a second hash table for incremental rehashing */d->ht[1] = n;d->rehashidx = 0;...
}

当把字典的 rehashidx 字典置为 0 时,也就代表了字典开始进行 rehash 了

/* 字典数据结构 */
typedef struct dict {...dictht ht[2];		// 一个字典,含有两个哈希表long rehashidx; 	// 代表 rehashing 到了什么位置,rehashidx = -1 代表							// 未进行 rehash...
} dict;

我们再来看到 src/dict.h 的 dictIsRehashing 方法,可以知道,通过判断 rehashidx 是否等于 -1 就能判断当前字典是否处于 rehashing 状态,也能进一步证明 rehashidx = 0 时,代表 rehash 正式开始进行

// src/dict.h
#define dictIsRehashing(d) ((d)->rehashidx != -1)

rehash流程

那么字典是如何进行渐进式 rehash 的呢?它主要分为两种方式进行

  • [被动式触发] :每次外部调用的 CRUD 都会触发一次数据迁移,每次迁移一份数据
  • [主动式触发] :定时任务,每次扫描一点数据进行迁移

被动式迁移

基本上涉及到查询,删除,修改,新增的方法都有判断该字典是否处于 rehashing 状态,如果处于 rehashing 状态,就调用 _dictRehashStep(d) 进行数据迁移; 例子如下,太多了,就不一一列出来了

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) {...if (dictIsRehashing(d)) _dictRehashStep(d);...
}    
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {...if (dictIsRehashing(d)) _dictRehashStep(d);...
}    
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {...if (dictIsRehashing(d)) _dictRehashStep(d);...

我们看到 _dictRehashStep(d) 是一个入口,那么我们就深入看下去,每次 CRUD 会触发一个怎么样的数据迁移,迁移多少

/* This function performs just a step of rehashing, and only if there are* no safe iterators bound to 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. */
static void _dictRehashStep(dict *d) {if (d->iterators == 0) dictRehash(d,1);
}

我们先忽略 iterators 的存在,通常等于 0,总之它调用了 dictRehash 方法, 并且每次只迁移哈希表数组的一个槽位 (因为链表存在,可能迁移多个键值对),继续往下看

  • 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, 对数据进行迁移* 参数:*d:要操作的字典,n:迁移 n 个数组槽位* 返回值:* 	1. 返回 1,代表还有数据要迁移*  2. 返回 0,代表所有数据已经迁移完了**/
int dictRehash(dict *d, int n) {// 原文注释说有说明, 最多遍历 n*10 个空桶, 避免过于耗时,因为数组中可能有很多	 // 连续为空的数组槽位// 避免此次 rehash 过于耗时int empty_visits = n*10; /* Max number of empty buckets to visit. */// 如果 rehashing 已经结束,或没有开始,那么返回 0 ,代表迁移完毕,或无需迁移if (!dictIsRehashing(d)) return 0;// 遍历 n 次,条件是 ht[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 代表数据迁移已经迁移到 ht[0] 的rehashidx 位置了,所以 		 // rehashidx 不会大于 ht[0].size 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;}// 如果非空桶,则此槽位有数据,遍历该槽位的链表,将该链表的数据 rehash, 			// 迁移到 ht[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 */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;}// 每迁移一个槽位,就将 ht[0] 原数据回收, rehashidx++d->ht[0].table[d->rehashidx] = NULL;d->rehashidx++;}/* Check if we already rehashed the whole table... */// 当发现 ht[0] 已经没有任何数据了,则回收 ht[0] 指向的空间if (d->ht[0].used == 0) {zfree(d->ht[0].table);// 并将 ht[0] 重新指向已完成扩容和数据迁移的新哈希表 ht[1]d->ht[0] = d->ht[1];_dictReset(&d->ht[1]);// 并表示 rehashing 状态已结束,完成数据迁移d->rehashidx = -1;return 0;}// 如果跳过了上面的判断,则代表还有很多数据有待迁移/* More to rehash... */return 1;
}
  • 我们可以看到字典的扩容的终止操作其实是在 rehash 方法中完成的,即 ht[0] 指针被重新指向,且字典的 rehashidx = -1
  • 而且被动式 rehash 只会迁移一个数组槽位的数据,(因为链表,所以迁移的键值对可能大于 1 个)

主动式迁移

入口在 src/server.c 文件里,我们看到 databaseCron方法, 我们可以还知道该方法是一个定时任务方法,会执行诸如键过期, resizeing, rehashing 等操作,不过我们不想看这么多,就省略非重点代码

/* This function handles 'background' operations we are required to do* incrementally in Redis databases, such as active key expiring, resizing,* rehashing. */
void databasesCron(void) {.../* Rehash */if (server.activerehashing) {for (j = 0; j < dbs_per_call; j++) {int work_done = incrementallyRehash(rehash_db);if (work_done) {/* If the function did some work, stop here, we'll do* more at the next cron loop. */break;} else {/* If this db didn't need rehash, we'll try the next one. */rehash_db++;rehash_db %= server.dbnum;}}}}
}

我们看到了会执行 incrementallyRehash 方法,继续往下看

/* Our hash table implementation performs rehashing incrementally while* we write/read from the hash table. Still if the server is idle, the hash* table will use two tables for a long time. So we try to use 1 millisecond* of CPU time at every call of this function to perform some rehashing.** The function returns 1 if some rehashing was performed, otherwise 0* is returned. */
int incrementallyRehash(int dbid) {// 字典 rehashing/* Keys dictionary */if (dictIsRehashing(server.db[dbid].dict)) {dictRehashMilliseconds(server.db[dbid].dict,1);return 1; /* already used our millisecond for this loop... */}// 过期字典 rehashing/* Expires */if (dictIsRehashing(server.db[dbid].expires)) {dictRehashMilliseconds(server.db[dbid].expires,1);return 1; /* already used our millisecond for this loop... */}return 0;
}

(额外知识点, redis 过期类型键会存在另外一个的字典一起维护数据) 我们看到普通的字典会通过 dictRehashMilliseconds 进行 rehashing , 并传入了 1 的参数。所以让我们从 src/server.h 回到 src/dict.c , 继续往下看

/* 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).* * 执行 x ms 的 rehash, 并返回 rehash 槽位的个数* */
int dictRehashMilliseconds(dict *d, int ms) {long long start = timeInMilliseconds();int rehashes = 0;// 每次 rehash 100 个数组槽位,被被动式多 100 倍呢// 直到数据完全被迁移完成或 if 打断while(dictRehash(d,100)) {// 累计槽位rehashes += 100;// 如果已经过了 ms 毫秒,则打断if (timeInMilliseconds()-start > ms) break;}return rehashes;
}

从上看可以看到, 主动式每次至少扫描 100 个数组槽位,每次扫描 x ms 时间。反正就是两个退出条件,要么超时,要么迁移完

说明:

  这种主动式迁移是redis处理完网络事件之后才做的,即此时redis处于空闲的时间,开始处理定时事件,然后每次rehash100个数组槽位,移动完100个之后,若超过1ms,则退出定时事件重新等待网络事件;否则继续移动继续判断是否超过1ms。

问题

哈希冲突时,为什么都是头插入?

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) {...ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];entry = zmalloc(sizeof(*entry));entry->next = ht->table[index];...
}

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.

  • 在头插入的源码中有一段官方注释,是这么说明的,用户最近插入的数据,有更大的概率被频繁访问,有点类似 LRU 的思想;既然新增数据更有概率被访问,那么自然就会将新增数据放在链表的头结点,以减少遍历链表的时间复杂度呀!
  • 当然我个人认为,还有第二个原因就是,当哈希冲突,直接插入头结点可以避免遍历,相比尾插入,少了一个遍历链表的过程,也就提高了写性能啊

rehash阶段遇到读写事件会发生什么?

读事件

  • 当处于 rehashing 阶段时,读线程需要帮忙搬迁数据,同时会遍历两张哈希表
dictEntry *dictFind(dict *d, const void *key)
{dictEntry *he;uint64_t h, idx, table;if (dictSize(d) == 0) return NULL; /* dict is empty */// 如果处理 rehashing, 帮忙搬迁数据,一个槽位即可if (dictIsRehashing(d)) _dictRehashStep(d);h = dictHashKey(d, key);// 遍历两个 tablefor (table = 0; table <= 1; table++) {idx = h & d->ht[table].sizemask;he = d->ht[table].table[idx];while(he) {if (key==he->key || dictCompareKeys(d, key, he->key))return he;he = he->next;}// 如果没有 reshing, 就直接 Return, 不用迭代遍历 ht[1] 了// 如果处理 reshing, 则需要继续遍历 ht[1]if (!dictIsRehashing(d)) return NULL;}return NULL;
}

写事件

  • 当初 rehashing 时,写线程要帮忙搬迁数据
    • 如果是插入操作则将数据写到新表中,即 ht[1],而不是旧表
    • 如果是删除操作,根据读的情况,不用想都是要遍历两张表,找到元素并删除
	// 如果处于 rehashing 状态,则向第二个哈希表 ht[1] 插入数据, 反之 ht[0]	ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

扩容 & rehash期间,如果新增过快,又到了扩容的阈值会怎么样?

答案就是 “不会马上扩容,会等待本次扩容结束,再进行下一次扩容”。

什么意思?也就是说当前处于 rehashing 的字典,因为本次扩容的生命周期没有完全结束,所以不会立即触发下一次的扩容,而是继续将数据往 ht[1] 写入,其结果无非就是导致 ht[1] 的哈希冲突概率逐渐加大,直到 ht[0] 的数据全部迁移到 ht[1] 中,并将 ht[0] 重指向 ht[1] 所指向的哈希表, 结束 rehashing 状态,并在本次扩容结束的下一次写入操作,立马触发字典的下一次扩容

rehash每次迁移多少数据?

  • 当由 CRUD 被动式触发的数据迁移,每次只会迁移 1 个数组槽位的数据,而一个数据槽位会含有 n 个键值对数据,具体 n 是多少呢,就看哈希冲突有多强烈了
  • 当由定时任务主动式扫描触发的数据迁移,每次会迁移 1 毫秒的数据,这毫秒内,至少迁移 100 个数组槽位,时间有空余就迁移更多批次,没有空余,执行完第一批 100 个槽位就停下

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/171817.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

STM32 ADC数模转换器

STM32 ADC数模转换器 ADC简介 ADC&#xff08;Analog-Digital Converter&#xff09;模拟-数字转换器 ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量&#xff0c;建立模拟电路到数字电路的桥梁 STM32主要是数字电路&#xff0c;数字电路只有高低电平&#xf…

Node.js 的适用场景

目录 ​编辑 前言 适用场景 1. 实时应用 用法 代码 理解 2. API 服务器 用法 代码示例 理解 3. 微服务架构 用法 代码示例 理解 总结 前言 Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境&#xff0c;它使得 JavaScript 可以脱离浏览器运行在服务器…

2023 MathorCup(妈妈杯) 数学建模挑战赛B题完整解题思路+模型+代码

2023妈妈杯数学建模B题完整版思路、模型代码已出&#xff01;&#xff01;&#xff01; 云顶数模最新完整版解题思路、模型代码&#xff0c;供大家参考~~ B题目 解题思路 详细模型解析&#xff1a;

从零开始的LINUX(三)

bc&#xff1a;进行浮点数运算 uname&#xff1a;查看当前的操作系统 ctrlc&#xff1a;中止当前正在执行的程序 ctrld&#xff1a;退出xshell shutdown&#xff1a;关机 reboot&#xff1a;重启 shell外壳&#xff1a; 作用&#xff1a;1、命令解释&#xff08;将输入的程序…

高速下载b站视频的解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

linux--

一、crond 任务调度 1、原理示意图 2、crontab 进行定时任务的设置 2.1. 概述 任务调度&#xff0c;是指系统在某个时间执行的特定的命令或程序。任务调度分类&#xff1a; 系统工作: 有些重要的工作必须周而复始地执行。如病毒扫描等 个别用户工作:个别用户可能希望执行某些…

WWW::Mechanize库使用HTTP如何做爬虫?

在使用Perl的WWW::Mechanize库进行爬虫时&#xff0c;需要注意以下几点&#xff1a; 1、设置User-Agent&#xff1a;有些网站会根据User-Agent来判断请求是否来自爬虫&#xff0c;因此在使用WWW::Mechanize之前&#xff0c;最好设置一个合适的User-Agent&#xff0c;以模拟真实…

【java】建筑施工一体化智慧工地信息管理系统源码

智慧工地系统是一种利用人工智能和物联网技术来监测和管理建筑工地的系统。它可以通过感知设备、数据处理和分析、智能控制等技术手段&#xff0c;实现对工地施工、设备状态、人员安全等方面的实时监控和管理。 一、智慧工地让工程施工智能化 1、内容全面&#xff0c;多维度数…

Python算法练习 10.28

leetcode 700 二叉搜索树中的搜索 给定二叉搜索树&#xff08;BST&#xff09;的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则返回 null 。 示例 1: 输入&#xff1a;root [4,2,7,1,…

macOS鼠标管理操作增强BetterMouse简体中文

BetterMouse是一款专为Mac用户设计的鼠标增强工具&#xff0c;旨在帮助用户更好地掌握和管理鼠标操作。它提供了全局鼠标手势、高度可定制的鼠标设置选项以及一些有用的鼠标增强功能&#xff0c;如鼠标放大镜、鼠标轨迹和应用程序切换功能。这些功能可以大大提高用户的工作效率…

MyBaties存储和查询json格式的数据(实体存储查询版本)

最近在做的功能&#xff0c;由于别的数据库有值&#xff0c;需要这边的不同入口的进来查询&#xff0c;所以需要同步过来&#xff0c;如果再继续一个一个生成列对应处理感觉不方便&#xff0c;如果没有别的操作&#xff0c;只是存储和查询&#xff0c;那就可以用MySql支持的jso…

【linux】麒麟v10安装Redis哨兵集群(ARM架构)

安装redis单示例的请看&#xff1a;麒麟v10安装Redis&#xff08;ARM架构&#xff09; 安装服务器 ​Hostname​IP addressmaster,sentinel192.168.0.1slave1,sentinel192.168.0.2slave2,sentinel192.168.0.3 下载安装包 &#xff08;三台都操作&#xff09; wget https://re…

[17]JAVAEE-HTTP协议

目录 一、什么是HTTP协议 什么时候会用到HTTP协议&#xff1f; HTTP协议的工作流程 二、HTTP的报文格式 抓包 HTTP请求报文格式 1.首行 2.header 常见键值对&#xff1a; 3.空行 4.正文&#xff08;body&#xff09;&#xff08;有的时候可以没有&#xff09; HTTP…

Unity的碰撞检测(四)

温馨提示&#xff1a;本文基于前一篇“Unity的碰撞检测(三)”继续探讨两个游戏对象具备刚体的触发检测&#xff0c;阅读本文则默认已阅读前文。 &#xff08;一&#xff09;测试说明 在基于两个游戏对象都具备触发器和刚体且属性一致的条件下&#xff0c;若二者刚体的BodyType…

开始学习Go编程

探索Go编程中的语法、数据类型和控制流 Go&#xff0c;又称为Golang&#xff0c;因其简单性、性能和效率而广受欢迎。在本文中&#xff0c;我们将深入研究构成Go编程语言基础的基本概念。从理解其语法和数据类型到掌握控制流和函数&#xff0c;我们将为您提供启动Go编程之旅所…

2015年亚太杯APMCM数学建模大赛A题海上丝绸之路发展战略的影响求解全过程文档及程序

2015年亚太杯APMCM数学建模大赛 A题 海上丝绸之路发展战略的影响 原题再现 一带一路不是实体或机制&#xff0c;而是合作与发展的理念和主张。凭借现有有效的区域合作平台&#xff0c;依托中国与有关国家现有的双边和多边机制&#xff0c;利用古丝绸之路的历史象征&#xff0…

算法训练营第三天 | 203.移除链表元素、707.设计链表 、206.反转链表

关于链表我们应该了解什么&#xff1a; 代码随想录 在实际开发中&#xff0c;遇到指针我们要做好防御性编程。 问题&#xff08; 一 &#xff09; 题目描述 &#xff1a; 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点…

【LeetCode:2558. 从数量最多的堆取走礼物 | 大根堆】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

LaTeX:在标题section中添加脚注footnote

命令讲解 先导包&#xff1a; \usepackage{footmisc} 设原标题为&#xff1a; \section{标题内容} 更改为&#xff1a; \section[标题内容]{标题内容\protect\footnote{脚注内容}} 语法讲解&#xff1a; \section[]{} []内为短标题&#xff0c;作为目录和页眉中的标题。…

在类库中使用ASP.NET Core API

解决办法1 官方文档 解决办法2 将类库修改为web项目&#xff0c;然后设置输出为类库形式即可 <Project Sdk"Microsoft.NET.Sdk.Web"><PropertyGroup><TargetFramework>netcoreapp3.1</TargetFramework><OutputType>Library</O…