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

首先是一些上下文，最后是解决方案：

\n\n

来自SCAN 命令 > 终止保证

\n\n

\n

仅当迭代集合的大小保持在给定的最大大小范围内时，才能保证 SCAN 算法终止，否则迭代始终增长的集合可能会导致 SCAN 永远不会终止完整迭代。

\n\n

这很容易直观地看到：如果集合增长，则需要做越来越多的工作才能访问所有可能的元素，并且终止迭代的能力取决于调用 SCAN 的次数和其 COUNT 选项值与\n 集合增长的速率进行比较。

\n

\n\n

但在COUNT 选项中它说：

\n\n

\n

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

\n

\n\n

请务必记住，来自Scan 的保证：

\n\n

\n

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

\n

\n\n

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

\n\n

使用DBSIZE或INFO keyspace命令你可以随时获取你有多少个钥匙：

\n\n

> DBSIZE\n(integer) 200032\n> info keyspace\n# Keyspace\ndb0:keys=200032,expires=0,avg_ttl=0\n

\n\n

另一个信息来源是 undocumented DEBUG htstats index，只是为了感受一下：

\n\n

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

\n\n

表大小是键数的 2 次幂：\n键：200032 => 表大小：262144

\n\n

解决方案：

\n\n

COUNT我们将为每次扫描计算所需的参数。

\n\n

假设您将以F10 Hz（每 100 毫秒）的频率（以 Hz 为单位）调用 SCAN，并且希望在 5 秒（T以 s 为单位）内完成。因此，在本例中，您希望通过N = F*T调用来完成此操作N = 50。

\n\n

在第一次扫描之前，您知道当前进度为 0，因此剩余百分比为RP = 1(100%)。

\n\n

在每次SCAN调用之前（或者如果您想保存调用的往返时间 (RTT)，则在每次调用您想要调整 COUNT 的给定次数之前DBSIZE），您调用DBSIZE以获取 key 的数量K。

\n\n

你将使用COUNT = K*RP/N

\n\n

对于第一次调用，这是COUNT = 200032*1/50 = 4000.

\n\n

对于任何其他调用，您需要计算RP = 1 - ReversedCursor/NextPowerOfTwo(K)。

\n\n

例如，假设您已经拨打了 20 个电话，那么现在N = 30（剩余电话次数）。你打电话DBSIZE并得到了K = 281569。这意味着NextPowerOfTwo(K) = 524288，这是 2^19。

\n\n

您的下一个光标是十进制的 14509 =000011100010101101二进制的。由于表的大小是2^19，所以我们用18位来表示。

\n\n

将这些位反转，得到101101010001110000二进制 = 十进制的 185456。这意味着我们已经覆盖了 524288 个中的 185456 个。并且：

\n\n

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

\n\n

所以你必须调整：

\n\n

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

\n\n

因此，在您的下一次SCAN通话中，您将使用6100. 它的增加是有道理的，因为：

\n\n

\n
• 密钥数量从 200032 个增加到 281569 个。
\n
• 尽管我们只剩下最初估计的 60% 的调用，但进度已经落后，因为 65% 的密钥空间有待扫描。
\n

\n\n

所有这一切都是假设您获得了所有钥匙。如果您进行模式匹配，则需要使用过去来估计要找到的剩余键数量。我们将一个因素PM（匹配百分比）添加到COUNT计算中。

\n\n

COUNT = PM * K*RP/N\n\nPM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))\n

\n\n

如果 20 次调用后，您仅发现keysFound = 2000钥匙，则：

\n\n

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

\n\n

这意味着到目前为止只有 2% 的键与我们的模式匹配，所以

\n\n

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

\n\n

这个算法可能还可以改进，但你明白了。

\n\n

确保对COUNT您开始使用的数字运行一些基准，以测量您花费了多少毫秒，因为您可能需要调整您对在合理时间内SCAN需要多少次调用 ( ) 的期望N不阻塞服务器，并调整你的F和T。

\n