Redis 迭代器(间断遍历)
文章目录
我们都知道 redis 是单进程、单线程、一个命令执行完、才会执行下一个命令、如果数据库中有海量的数据、当使用 keys 命令,会直接造成服务器的短暂不可用等现象,所以在 redis 2.8.0 之后新增了 scan 操作,也就是 间断遍历。
核心代码在 dict.c中的 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;
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) {
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 = rev(v);
} 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) {
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) {
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 = rev(v);
/* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));
}
return v;
}redis为了做到不遗漏数据且尽量不重复数据,采用了一种叫做 reverse binary iteration(二进制反转) 的方法来进行简短遍历。
核心代码:
v |= ~m1;
v = rev(v);
v++;
v = rev(v);1. 从迭代开始到结束,散列表没有进行 rehash 操作、没有扩容、缩容操作。
gdb

v的值,分别依次为 0、2、1、3。
打印的结果如下:

2、从迭代开始到结束,没有进行 rehash操作,但是进行了扩容和缩容操作。
3、从迭代开始到结束,进行了rehash操作。
在rehash中,会同时存在两种表,一张为ht[0],一张为ht[1],因为两个并都存在数据,redis先对小的表进行数据遍历,然后在对大表进行数据遍历。
do {
/* Emit entries at cursor */
if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
de = t1->table[v & m1];
while (de) {
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 = rev(v);
/* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));总结:redis 采用了一种叫做 reverse binary iteration(二进制反转)的算法,巧妙的利用这个规律,避免了重复数据和遗漏数据。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论