baiyan
全部视频：【每日学习记录】使用录像设备记录每天的学习
字典是啥
dict，即字典，也被称为哈希表 hashtable。在 redis 的五大数据结构中，有如下两种情形会使用 dict 结构：
- hash：数据量小的时候使用 ziplist，量大时使用 dict
- zset：数据量小的时候使用 ziplist，数据量大的时候使用 skiplist + dict
结合以上两种情况，我们可以看出，dict 也是一种较为复杂的数据结构，通常用在数据量大的情形中。通常情况下，一个 dict 长这样：
在这个哈希表中，每个存储单元被称为一个桶（bucket）。我们向这个 dict(hashtable)中插入一个 ”name” => “baiyan” 的 key-value 对，假设对这个 key“name”做哈希运算结果为 3，那么我们寻找这个 hashtable 中下标为 3 的位置并将其插入进去，得到如图所示的情形。我们可以看到，dict 最大的优势就在于其查找的时间复杂度为 O(1)，是任何其它数据结构所不能比拟的。我们在查找的时候，首先对 key”name“进行哈希运算，得到结果 3，我们直接去 dict 索引为 3 的位置进行查找，即可得到 value”baiyan“，时间复杂度为 O(1)，是相当快的。
redis 中的字典
基本结构
在 redis 中，在普通字典的基础上，为了方便进行扩容与缩容，增加了一些描述字段。还是以上面的例子为基础，在 redis 中存储结构如下图所示：
dictht 的结构如下：
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;在 dictht 中，真正存储数据的地方是 **table 这个 dictEntry 类型二级指针。我们可以把它拆分来看，首先第一个指针可以代表一个数组，即哈希表。而后面的指针代表，在每个在哈希表的存储单元中，存储的都是一个 dictEntry 类型指针，这个指针就指向我们存储 key-value 对的 dictEntry 类型结构的所在位置，如上图所示。
存储最终 key-value 对的 dictEntry 的结构如下：
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;一个存储 key-value 对的 entry，最主要还是这里的 key 和 value 字段。由于存储在 dict 中的 key 和 value 可以是字符串、也可以是整数等等，所以在这里均用一个 void * 指针来表示。我们注意到最后有一个也是同类型 dictEntry 的 next 指针，它就是用来解决我们经常说的 哈希冲突 问题。
哈希冲突
当我们对不同的 key 进行哈希运算之后结果相同时，就碰到了哈希冲突的问题。常用的两种哈希冲突的解决方案有两种：开放定址法与链地址法。redis 使用的是后者。通过这个 next 指针，我们就可以将哈希值相同的元素都串联起来，解决哈希冲突的问题。注意在 redis 的源码实现中，在往 dict 插入元素的时使用的是链表的 头插法，即将新元素插到链表的头部，这样就不用每次遍历到链表的末尾进行插入，降低了插入的时间复杂度。
链地址法所带来的问题
假设我们一直往 dict 中插入元素，那么这个哈希表的所有 bucket 都会被占满，而且在链地址法解决哈希冲突的过程中，每个 bucket 后面的链表会非常长。这样一来，这个链表的时间复杂度就会逐渐退化成 O(n)。对于整体的 dict 而言，其查询效率就会大大降低。为了解决数据量过大导致 dict 性能下降的问题，我们需要对其进行 扩容，来满足后续插入元素的存储需要。
分而治之的 rehash
- 在通常情况下，我们会对哈希表做一个 2 倍的扩容，即由 2 ->4，4->8 等等。假设我们的一个 dict 中已经存储了好多数据，我们还需要向这个 dict 中插入一大堆数据。在后续插入大量数据的过程中，由于我们需要解决 dict 性能下降的问题，我们需要对其进行扩容。由于扩容的时候，需要对所有 key-value 对重新进行哈希运算，并重新分配到相应的 bucket 位置上，我们称这个过程为为rehash。
- 在 rehash 过程中，需要做大量的哈希运算操作，其开销是相当大、而且花费的时间是相当长的。由于 redis 是单进程、单线程的架构，在执行 rehash 的过程中，由于其开销大、时间长，会导致 redis 进程阻塞，进而无法为线上提供数据存储服务，对外部会返回 redis 服务不可用。为了解决一次性 rehash 所导致的 redis 进程阻塞的问题，利用 分而治之 的编程思想，将一次 rehash 操作分散到多个步骤当中去减小 rehash 给 redis 进程带来的资源占用。举一个例子，可能会在后续的 get、set 操作中，进行一次 rehash 操作。为了实现这种操作，redis 其实设计了 两个哈希表 ，一个就是我们之前讲过的对外部提供存取服务的哈希表，而另一个就专门用来做 rehash 操作。这种分而治之的思想，将一次大数据量的 rehash 操作分散到多次完成，叫做 渐进式 rehash：
- 目前是刚刚要进行 rehash 的状态。我们可以看到，在之前画的图的基础上，我们加入了一个新的结构 dict，其中的 ht[2]字段就负责指向两个哈希表。下面一个哈希表的大小为之前的大小 8 *2=16，没有任何元素。关于 dict 的结构如下：
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehash 进程标识。如果值为 - 1 则不在 rehash，否则在进行 rehash */
unsigned long iterators; /* number of iterators currently running */
} dict;- 注意其中的 rehashidx 字段，它代表我们进行 rehash 的进程。注意我们每次进行 get 或 set 等命令的时候，rehash 就会进行一次，即把一个在原来哈希表 ht[0]上的元素挪到新哈希表 ht[1]中，注意一次只移动一个元素，移动完成之后，rehashidx 就会 +1，直到原来哈希表上所有的元素都挪到新哈希表上为止。rehash 完成之后，新哈希表 ht[1]就会被置为 ht[0]，为线上提供服务。而原来的哈希表 ht[0]就会被销毁。rehash 的源码如下：
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 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 */
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;
}
de = d->ht[0].table[d->rehashidx];
/* 将老的哈希表 ht[0]中的元素移动到新哈希表 ht[1]中 */
while(de) {
uint64_t h;
nextde = de->next;
/* 计算新哈希表 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--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* 检查是否 rehash 完成，若完成则置 rehashidx 为 -1 */
if (d->ht[0].used == 0) {zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}rehash 过程中可能存在的问题
rehash 对查找的影响
如果在 rehash 的过程中（例如容量由 4 扩容到 8），如果需要查找一个元素。首先我们会计算哈希值（假设为 3）去找老的哈希表 ht[0]，如果我们发现位置 3 上已经没有了元素，说明这个元素已经被 rehash 过了，到新的哈希表上对应的位置 3 或 7 上寻找即可。
rehash 对遍历的影响
问题
试想这么一种情况：在 rehash 之前，我们使用 SCAN 命令对 dict 进行第一次遍历；而 rehash 结束之后我们进行第二次 SCAN 遍历，会发生什么情况？
在讨论这个问题之前，我们先熟悉一下 SCAN 命令。我们知道在我们执行 keys 这种返回所有 key 值的命令，由于所有 key 加在一块是相当多的，如果一次性全部把它遍历完成，能够让单进程的 redis 阻塞相当长的时间，在这段时间里都无法对外提供服务。为了解决这个问题，SCAN 命令横空出世。它并不是一次性将所有的 key 都返回，而是每次返回一部分 key 并记录一下当前遍历的进度，这里用一个游标去记录。下次再次运行 SCAN 命令的时候，redis 会从游标的位置开始继续往下遍历。SCAN 命令实际上也是一种分而治之的思想，这样一次遍历一小部分，直到遍历完成。SCAN 命令官方解释如下：
SCAN 命令是一个基于游标的 迭代器：SCAN 命令每次被调用之后，都会向用户返回一个新的游标，用户在下次迭代时需要使用这个新游标作为 SCAN 命令的游标参数，以此来延续之前的迭代过程。
SCAN 命令的使用方法如下：
redis 127.0.0.1:6379> scan 0
1) "17"
2) 1) "key:12"
2) "key:8"
3) "key:4"
4) "key:14"
5) "key:16"
6) "key:17"
7) "key:15"
8) "key:10"
9) "key:3"
10) "key:7"
11) "key:1"
redis 127.0.0.1:6379> scan 17
1) "0"
2) 1) "key:5"
2) "key:18"
3) "key:0"
4) "key:2"
5) "key:19"
6) "key:13"
7) "key:6"
8) "key:9"
9) "key:11"
- 在上面这个例子中，第一次迭代使用 0 作为游标，表示开始一次新的迭代。第二次迭代使用的是第一次迭代时返回的游标，也即是命令回复第一个元素的值 17。
- 从上面的示例可以看到，SCAN 命令的回复是一个包含两个元素的数组，第一个数组元素是用于进行下一次迭代的新游标，而第二个数组元素则是一个数组，这个数组中包含了所有被迭代的元素。
- 在第二次调用 SCAN 命令时，命令返回了游标 0，这表示迭代已经结束，整个数据集（collection）已经被完整遍历过了。
- 以 0 作为游标开始一次新的迭代，一直调用 SCAN 命令，直到命令返回游标 0，我们称这个过程为一次完整遍历。
回到正题，我们来解决之前的问题。我们简化一下 dict 的结构，只留下两个基本的哈希表结构，我们现在有 4 个元素：12、13、14、15，假设哈希算法为取余。
- 假设现在我们在没有 rehash 之前，对其使用 SCAN 命令，基于我们之前讲过的知识点，由于 SCAN 是基于游标的增量遍历，我们假设这个 SCAN 命令只遍历到游标为 1 的位置就停止了：
- 我们得到第一次遍历的结果为：12
- 开始进行 rehash。
- rehash 结束，我们再次使用 SCAN 命令对其进行遍历。由于上次返回的游标为 1，我们从 1 的位置继续遍历，只不过这次要在新的哈希表中进行遍历了：
- 第二次 SCAN 命令遍历的结果为：12、13、14、15
那么我们将两次 SCAN 的结果合起来，为 12、12、13、14、15。我们发现，元素 12 被多遍历了一次，与我们的预期不符。所以我们得出结论：在 rehash 过程中执行 SCAN 命令会导致遍历结果出现冗余。
解决方案
为了解决扩容和缩容进行 rehash 的过程中重复遍历的问题，redis 对哈希表的下标做出了如下变化（v 就是哈希表的下标）：
v = rev(v);
v++;
v = rev(v);首先将游标倒置，加一后，再倒置，也就是我们所说的“高位 ++”的操作。这里的这几步操作是来通过前一个下标，计算出哈希表下一个 bucket 的下标。举一个例子：最开始 00 这个 bucket 不用动，之前经过正常的低位 ++ 之后，00 的后面应该为 01。然而现在是高位 ++，原来 01 的位置的下标就会变成 10……. 以此类推。最终，哈希表的下标就会由原来顺序的 00、01、10、11 变成了 00、10、01、11，如图所示：
这样就能够保证我们多次执行 SCAN 命令就不会重复遍历了吗？接下来就是见证奇迹的时刻：
- 首先还是没进行 rehash 之前，对其进行 SCAN。同样的，我们假设这个 SCAN 命令只遍历到游标为 1 的位置就停止了：
- 我们得到第一次遍历的结果：12
-
开始进行 rehash
- rehash 结束，我们再次使用 SCAN 命令对其进行遍历。注意这里，上次返回的游标为 2，我们从 2 的位置继续遍历，也是要在新的哈希表中进行遍历了：
- 我们可以看到，经过一个小的下标的修改，就能够解决 rehash 所带来的 SCAN 重复遍历的问题。对 dict 进行遍历的源码如下：
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;
// 如果 SCAN 的时候没有进行 rehash
if (!dictIsRehashing(d)) {t0 = &(d->ht[0]);
m0 = t0->sizemask;
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) { // 遍历同一个 bucket 上后面挂接的链表
next = de->next;
fn(privdata, de);
de = next;
}
/* Set unmasked bits so incrementing the reversed cursor
* operates on the masked bits */
v |= ~m0;
/* Increment the reverse cursor */
v = rev(v); // 反转 v
v++; // 反转之后即为高位 ++
v = rev(v); // 再反转回来，得到下一个游标值
// 如果 SCAN 的时候正在进行 rehash
} else {t0 = &d->ht[0];
t1 = &d->ht[1];
/* Make sure t0 is the smaller and t1 is the bigger table */
if (t0->size > t1->size) {t0 = &d->ht[1];
t1 = &d->ht[0];
}
m0 = t0->sizemask;
m1 = t1->sizemask;
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) { // 遍历同一个 bucket 上后面挂接的链表
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 */
do {
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
de = t1->table[v & m1];
while (de) { // 遍历同一个 bucket 上后面挂接的链表
next = de->next;
fn(privdata, de);
de = next;
}
/* Increment the reverse cursor not covered by the smaller mask.*/
v |= ~m1;
v = rev(v); // 反转 v
v++; // 反转之后即为高位 ++
v = rev(v); // 再反转回来，得到下一个游标值
/* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));
}
return v;
}有关 rehash 过程对 SCAN 的影响，限于篇幅仅仅展示这种情况。更多的情形请参考：Redis scan 命令原理