栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

Redis`SCAN`:如何在可能匹配的新密钥之间保持平衡并确保在合理的时间内最终结果?

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Redis`SCAN`:如何在可能匹配的新密钥之间保持平衡并确保在合理的时间内最终结果?

首先提供一些上下文,最后给出 解决方案

从SCAN命令>终止保证

只有在迭代集合的大小保持在给定的最大大小范围内时,才能保证SCAN算法终止;否则,对始终增长的集合进行迭代可能会导致SCAN从不终止完整迭代。

这很容易直观地看出:如果集合增长了,为了访问所有可能的元素,将会有越来越多的工作要做,而终止迭代的能力取决于对SCAN的调用次数及其COUNT选项值与集合的增长率。

但是在COUNT选项中它说:

重要提示:无需为每次迭代使用相同的COUNT值。调用者可以根据需要自由地将计数从一个迭代更改为另一个迭代,只要在下一个调用中传递的光标是在上一次对该命令的调用中获得的光标即可。

请记住重要的一点,来自Scan保证:

  • 给定的元素可能会多次返回。由应用程序来处理重复元素的情况,例如仅使用返回的元素来执行在多次重新应用时安全的操作。
  • 在整个迭代过程中不经常出现在集合中的元素可能会返回,也可能不会返回:它是未定义的。

解决方案的关键在于光标本身。请参阅了解Redis的SCAN光标。 可以推断出扫描进度的百分比,因为光标实际上是表大小的索引的位反转。

使用

DBSIZE
INFO keyspace
命令,您可以随时获取多少个键:

> DBSIZE(integer) 200032> info keyspace# Keyspacedb0:keys=200032,expires=0,avg_ttl=0

另一个信息来源是未记录的

DEBUG htstats index
,只是为了获得一种感觉:

> DEBUG htstats 0[Dictionary HT]Hash table 0 stats (main hash table): table size: 262144 number of elements: 200032 different slots: 139805 max chain length: 8 avg chain length (counted): 1.43 avg chain length (computed): 1.43 Chain length distribution:   0: 122339 (46.67%)   1: 93163 (35.54%)   2: 35502 (13.54%)   3: 9071 (3.46%)   4: 1754 (0.67%)   5: 264 (0.10%)   6: 43 (0.02%)   7: 6 (0.00%)   8: 2 (0.00%)[Expires HT]No stats available for empty dictionaries

该表的大小是键数目之后的2的幂。键:200032 =>表大小:262144

解决方案:

我们将为

COUNT
每次扫描计算所需的参数。

假设您将以

F
10 Hz(每100 ms)的频率(以Hz为单位)呼叫SCAN,并且您希望在5秒内
T
以s为单位进行扫描。因此
N = F*T
N =50
在此示例中,您希望在调用中完成此操作。

在第一次扫描之前,您知道当前进度为0,因此剩余百分比为

RP = 1
(100%)。

在每次

SCAN
通话之前(或者如果要保存
DBSIZE
通话的往返时间(RTT),则在要调整COUNT的每个给定通话次数之前),请致电
DBSIZE
以获取按键数
K

您将使用

COUNT = K*RP/N

第一次通话是

COUNT = 200032*1/50 = 4000

对于其他任何电话,您都需要计算

RP = 1 - ReversedCursor/NextPowerOfTwo(K)

例如,假设您已经进行了20个通话,那么现在

N = 30
(剩余通话数量)。你打来电话
DBSIZE
K =281569
。这意味着
NextPowerOfTwo(K) = 524288
,这是2 ^ 19。

下一个光标是十进制= 14509 =

000011100010101101
二进制。由于表的大小为2 ^ 19,因此我们用18位表示它。

反转这些位,

101101010001110000
以十进制形式获取二进制= 185456。这意味着我们已覆盖524288个中的185456个。并且:

RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%

所以你必须调整:

COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100

因此,在下一个

SCAN
通话中,您将使用
6100
。使其增加是有道理的,因为:

  • 密钥数量已从200032增加到281569。
  • 尽管我们仅剩余60%的初始呼叫估计,但是进度落后了,因为65%的密钥空间有待扫描。

所有这些都是假设您正在获取所有密钥。 如果您是模式匹配
,则需要使用过去来估计要找到的剩余键数。我们将一个因素

PM
(匹配百分比)添加到
COUNT
计算中。

COUNT = PM * K*RP/NPM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))

如果在拨打20次电话后,您仅找到

keysFound = 2000
按键,则:

PM = 2000 / ( 281569 * 185456 / 524288) = 0.02

这意味着到目前为止,只有2%的键与我们的模式匹配,因此

COUNT = PM * K*RP/N = 0.02 * 6100 = 122

该算法可能可以改进,但是您可以理解。

确保在

COUNT
开始使用的号码上运行一些基准测试,以衡量您
SCAN
花费的毫秒数,因为您可能需要降低对
N
在合理的时间内完成此操作所需的呼叫次数()的期望阻塞服务器和调整
F
,并
T
相应地。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/385995.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号