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

Question

我不太熟悉Redis。目前，我正在设计一些实时服务，我想依靠它。我希望每分钟〜10000-50000个键SET具有合理的价格，EX并且使用SCAN很少的匹配它们就不会干扰性能瓶颈。

我怀疑的是“输入/输出速率”，并且可能会因与某些SCAN查询匹配的键而泛滥，因此它永远不会终止（即始终以最新的光标位置进行回复并迫使您继续；如果有人消耗掉了x items per second并且有x + y items per second coming in与y > 0）。

显然，我可以将所需的SCAN大小设置足够长的时间。但是我想知道是否存在更好的解决方案，或者它Redis本身是否可以保证SCAN在这种情况下会自动增大尺寸？

Answer 1

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

从SCAN命令>终止保证

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

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

但是在COUNT选项中它说：

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

请记住重要的一点，来自Scan保证：

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

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

使用DBSIZE或INFO keyspace命令，您可以随时获取多少个键：

> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0: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每次扫描计算所需的参数。

假设您将以F10 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/N

PM = 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相应地。