在网上看了不少文章都是指导使用方式,要不就是老版本的redis结构,干脆我就自己看源码瞅瞅怎么个事。
本文主要说明的是数据结构和hash的基本操作原理,不是API文档,有想知道的API请自行查阅文档和代码。
关键词: ziplist、hashtable、listpack、rehash、dict。
数据结构
先说明 ziplist 和 listpack 的关系,Redis版本导致直接使用的数据结构不同,ziplist废弃了!
顺便说一句,ziplist是 老版本 hash/list/zset 底层结构,同时废弃的还有 zipmap(hash),linkedlist(list)。
Ziplist
从 ziplist 的注释中可以得到这些信息,已经说的很完善了,我来翻译一下。
数据结构成下表所示的紧凑排列,ziplist 信息均为无符号数 unsigned,全都按小端序(低位存低地址)排列。
zlbytes | zltail | zllen | entry | entry | …… | entry | zlend |
---|
zlbytes(u32int) | 用于存储ziplist占用的字节数,包括 zlbytes 字段本身的四个字节。 |
---|---|
zltail(u32int) | 指向 ziplist entry 尾部的偏移量,用来操作末尾元素。 |
zllen(u16int) | 元素数量,占 2 Bytes。所以最多只能存65535,如果有更多元素的话只能遍历才知道具体数量了(注: 所以别配置那么大)。 |
zlend(u8int) | 指向 ziplist 末尾,只有这个变量是单字节255。 |
Entry
主要由前两段来作为描述 entry 的元数据,特殊情况下 encoding 直接描述 data,例如small int,这时就不存在data部分。
prevlen | encoding | [entry-data] |
---|
变量 | 解释 |
---|---|
prevlen | 表示前面的entry length, 用来倒序遍历。大小为 0-253,那就是单字节u8int。不然就会消耗 5 字节,第一个字节设置为 0xFE(254) 表示后续有大数字长度,后面 4 个字节表示长度。 |
encoding | data 的编码方式,即 type,如果是string 则会表示string的payload。 第一个字节是type,特殊type值255是zlend。 第二个字节如果是string可能会表达大小,后续字节表示数据。 如果是int的话,第一个字节表示 type 就足够了,后面跟着数据字节。具体编码规则请参考文档。 |
示例↓
Listpack
hash 的新结构,代替了 ziplist。原因大概就是由于一个crash,大家发现ziplist太复杂了,有点臃肿难以审查,干脆换个结构吧,于是 listpack 诞生了。<tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>
同样采用小端序。
变量 | 解释 |
---|---|
tot-bytes | u32int,表示整个结构的大小包括自身。这个变量是为了能倒序访问。 |
num-elements | u16int,表示元素数量。和zllen一样,只能表达65535,多了就得遍历才知道。 |
Element(Entry)
和 ziplist 类似,如果 data 太小也会存在于 encoding 中,从而只有两段。
变量 | 解释 |
---|---|
encoding-type | 高位4bits用来表示类型,如果太小可能用不到4bits。后面表示数据和ziplist的大致相似,具体类型编码请参考文档。同时encoding也充当正序访问的len使用,解析encoding可以得到entry大小。 |
element-tot-len | 表示element大小,用来倒序访问。由特殊的大端序存储多字节大小,具体编码方式参考文档。 |
HashTable
hash结构包括了以下几种结构。
dictEntry
struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; /* Next entry in the same hash bucket. */
};
typedef struct {
void *key;
dictEntry *next;
} dictEntryNoValue;
可以看到entry基本由kv和next指针构成。使用链表法来解决hash冲突
dict
struct dict {
// 这里存储这一些表信息。例如是否有value
dictType *type;
dictEntry **ht_table[2];
unsigned long ht_used[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
/* Keep small vars at end for optimal (minimal) struct padding */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
void *metadata[];
};
dict结构我们可以看到,其中包含了类型、两个table、rehash状态标志位、两个table已使用的节点数和元数据。两个表是因为是渐进式rehash,简单来说就是扩容时慢慢迁移表,避免大规模的数据迁移。
dict Iterator
typedef struct dictIterator {
dict *d;
long index;
int table, safe;
dictEntry *entry, *nextEntry;
/* unsafe iterator fingerprint for misuse detection. */
unsigned long long fingerprint;
} dictIterator;
其中safe标志位表示这个迭代器是否为安全迭代器。安全迭代器不会进行rehash且不能操作数据。
(非)安全迭代器
直接看注释可以知道安全迭代器可以正常操作数据,而非安全迭代器只能查看。
google了一下大佬的回答大概是这个意思: redis 基于 Copy-On-Write 进行 dump,如果任何地方发生改动就会触发副本,所以这个时候就需要非安全迭代器进行访问,来将数据迁移完成,避免不必要的复制出现。
Hash 逻辑构成
数据结构切换
根据配置的参数可以决定什么时候发生紧凑结构 ziplist/listpack => hashtable 的转换,只要达到 entry 数量或者是 value 大小,都会立刻触发不可逆的转向 hashtable。下图就可以看出。
直接看注释
void hashTypeConvertListpack(robj *o, int enc) {
serverAssert(o->encoding == OBJ_ENCODING_LISTPACK);
if (enc == OBJ_ENCODING_LISTPACK) {
/* Nothing to do... */
} else if (enc == OBJ_ENCODING_HT) {
hashTypeIterator *hi;
dict *dict;
int ret;
// 初始化一个dict
hi = hashTypeInitIterator(o);
dict = dictCreate(&hashDictType);
/* Presize the dict to avoid rehashing */
dictExpand(dict,hashTypeLength(o));
// 开始迁移数据
while (hashTypeNext(hi) != C_ERR) {
sds key, value;
// 通过listpackAPI获取KV后迁移到dict
key = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_KEY);
value = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_VALUE);
ret = dictAdd(dict, key, value);
if (ret != DICT_OK) {
// 异常记录
sdsfree(key); sdsfree(value); /* Needed for gcc ASAN */
hashTypeReleaseIterator(hi); /* Needed for gcc ASAN */
serverLogHexDump(LL_WARNING,"listpack with dup elements dump",
o->ptr,lpBytes(o->ptr));
serverPanic("Listpack corruption detected");
}
}
// 释放内存
hashTypeReleaseIterator(hi);
zfree(o->ptr);
// 更新结构指针和标识成Hash,至此完成转换
o->encoding = OBJ_ENCODING_HT;
o->ptr = dict;
} else {
serverPanic("Unknown hash encoding");
}
}
Rehash
redis 的渐进式 rehash 是通过多个每次至多 1ms 的 rehash 组成。
触发条件
rehash调用也是有条件的,还记得前文dict的pauserehash
吗,这个变量就是标记能否进行rehash的变量,
rehash还需要确定rehash的许可,目前有三种状态: Enable
(默认)、Forbid
、AVOID
。
其中Forbid
是由于是 fork 线程所以不需要进行 hash ,AVOID
是被 fork 的线程所在的状态,但是也判断如果两个表的大小是否在5倍以内的话不进行 rehash,因为是基于 Copy-On-Write 模式的,不过差距太大还是得进行 rehash。
文章来源:https://www.toymoban.com/news/detail-829531.html
函数执行过程
核心方法: int dictRehash(dict *d, int n)
返回1表示 rehash 进行中,0表示已完成。n是单次迁移的bucket
数量,目前只有1和100,前者是主动修改了kv由迭代器触发,后者是渐进rehash的固定数量。文章来源地址https://www.toymoban.com/news/detail-829531.html
- 首先会根据 hash表的 resize 状态来判断能否进行 rehash。
- 对于比较稀疏的hash表来说,访问空节点是一种浪费。所以每次rehash最多访问 n*10 个空节点就会提前结束。
- 通过
rehashidx
继续 rehash - 每次搬一个 bucket 节点,搬的过程中处理两个表的大小。rehash不仅仅是扩容也可能是缩容。
- 如果 rehash 全部完成了就释放空表内存并且重置标记位否则就return 1表示还得继续
/* 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. */
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
unsigned long s0 = DICTHT_SIZE(d->ht_size_exp[0]);
unsigned long s1 = DICTHT_SIZE(d->ht_size_exp[1]);
if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;
if (dict_can_resize == DICT_RESIZE_AVOID &&
((s1 > s0 && s1 / s0 < dict_force_resize_ratio) ||
(s1 < s0 && s0 / s1 < dict_force_resize_ratio)))
{
return 0;
}
while(n-- && d->ht_used[0] != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);
while(d->ht_table[0][d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht_table[0][d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {
uint64_t h;
nextde = dictGetNext(de);
void *key = dictGetKey(de);
/* Get the index in the new hash table */
if (d->ht_size_exp[1] > d->ht_size_exp[0]) {
h = dictHashKey(d, key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
} else {
/* We're shrinking the table. The tables sizes are powers of
* two, so we simply mask the bucket index in the larger table
* to get the bucket index in the smaller table. */
h = d->rehashidx & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
}
if (d->type->no_value) {
if (d->type->keys_are_odd && !d->ht_table[1][h]) {
/* Destination bucket is empty and we can store the key
* directly without an allocated entry. Free the old entry
* if it's an allocated entry.
*
* TODO: Add a flag 'keys_are_even' and if set, we can use
* this optimization for these dicts too. We can set the LSB
* bit when stored as a dict entry and clear it again when
* we need the key back. */
assert(entryIsKey(key));
if (!entryIsKey(de)) zfree(decodeMaskedPtr(de));
de = key;
} else if (entryIsKey(de)) {
/* We don't have an allocated entry but we need one. */
de = createEntryNoValue(key, d->ht_table[1][h]);
} else {
/* Just move the existing entry to the destination table and
* update the 'next' field. */
assert(entryIsNoValue(de));
dictSetNext(de, d->ht_table[1][h]);
}
} else {
dictSetNext(de, d->ht_table[1][h]);
}
d->ht_table[1][h] = de;
d->ht_used[0]--;
d->ht_used[1]++;
de = nextde;
}
d->ht_table[0][d->rehashidx] = NULL;
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
if (d->ht_used[0] == 0) {
if (d->type->rehashingCompleted) d->type->rehashingCompleted(d);
zfree(d->ht_table[0]);
/* Copy the new ht onto the old one */
d->ht_table[0] = d->ht_table[1];
d->ht_used[0] = d->ht_used[1];
d->ht_size_exp[0] = d->ht_size_exp[1];
_dictReset(d, 1);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
参考资料
- Redis源码: v7.2.x unstable
- listpack/listpack.md at master · antirez/listpack
- what’s the difference of safe/non-safe dict itereator in redis’ dict implementation?
到了这里,关于Redis Hash数据结构探秘的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!