Redis有一个SCAN命令,可用于迭代匹配模式等的键.
首先给出游标值为0; 每次调用都会返回一个新的游标值,您将其传递给下一个SCAN调用.值为0表示迭代结束.据说不需要服务器或客户端状态(游标值除外)
我想知道Redis如何实现扫描算法？
mis*_*ion 19
您可以在redis dict.c源文件中找到答案.然后我会引用它的一部分.
迭代的工作方式如下:
该函数保证字典中存在的所有元素在迭代的开始和结束之间返回.但是有些元素可能会多次返回.对于返回的每个元素,回调参数'fn'被调用,'privdata'作为第一个参数,字典entry'de'作为第二个参数.
迭代算法由Pieter Noordhuis设计.主要思想是从高阶位开始递增游标.也就是说,不是正常地增加光标,而是反转光标的位,然后光标递增,最后再次反转这些位.
需要此策略,因为可以在迭代调用之间调整哈希表的大小.dict.c哈希表总是大小为2的幂,它们使用链接,因此给定表中元素的位置是通过计算Hash(key)和SIZE-1之间的按位AND给出的(其中SIZE-1是总是掩码相当于在键的Hash和SIZE之间进行剩余的除法.
例如,如果当前散列表大小为16,则掩码为(二进制)1111.散列表中的键的位置将始终是散列输出的最后四位,依此类推.
如果哈希表增长,元素可以在旧桶的一个倍数中的任何位置:例如,假设我们已经使用4位光标1100进行迭代(掩码是1111,因为哈希表大小= 16).
如果哈希表将被调整为64个元素,那么新的掩码将是111111.通过用？或1100替换为0或1而获得的新桶只能被我们在扫描桶1100时访问过的密钥作为目标.较小的哈希表.
通过首先迭代高位,由于反转计数器,如果表大小变大,则不需要重新启动光标.它将继续使用游标在没有'1100'的情况下进行迭代,并且还没有已经探索过的最后4位的任何其他组合.
类似地,当表大小随时间缩小时,例如从16变为8,如果已经完全探索了较低三位(大小为8的掩码为111)的组合,则不会再次访问它,因为我们确信我们例如,尝试了0111和1111(高位的所有变化),因此我们不需要再次测试它.
是的,这是事实,但我们总是首先迭代较小的表,然后我们测试当前光标到较大表的所有扩展.例如,如果当前光标是101并且我们还有一个大小为16的较大表,我们还在较大的表内测试(0)101和(1)101.这将问题简化为只有一个表,其中较大的表(如果存在)只是较小表的扩展.
这个迭代器是完全无状态的,这是一个巨大的优势,包括不使用额外的内存.这种设计的缺点是: