Redis `SCAN` : how to maintain a balance between newcomming keys that might match and ensure eventual result in a reasonable time?

Question

我不太熟悉 Redis .目前我正在设计一些实时服务，我想依赖它。我预计每分钟 ~10000-50000 个 key 是 SET有一些合理的EX并使用 SCAN 匹配它们很少足以不打扰性能瓶颈。

我怀疑的是“输入/输出速率”以及可能与某些匹配的键的溢出 SCAN查询，因此它永远不会终止(即总是用最新的光标位置回复并强制您继续；如果使用 x items per second 并且有 x + y items per second coming in 和 y > 0 ，这很容易发生)。

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

Answer 1

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

来自 SCAN command > Guarantee of termination

The SCAN algorithm is guaranteed to terminate only if the size of the iterated collection remains bounded to a given maximum size, otherwise iterating a collection that always grows may result into SCAN to never terminate a full iteration.

This is easy to see intuitively: if the collection grows there is more and more work to do in order to visit all the possible elements, and the ability to terminate the iteration depends on the number of calls to SCAN and its COUNT option value compared with the rate at which the collection grows.

但在 The COUNT option 中它说:

Important: there is no need to use the same COUNT value for every iteration. The caller is free to change the count from one iteration to the other as required, as long as the cursor passed in the next call is the one obtained in the previous call to the command.

重要的是要记住，来自 Scan guarantees :

• A given element may be returned multiple times. It is up to the application to handle the case of duplicated elements, for example only using the returned elements in order to perform operations that are safe when re-applied multiple times.
• Elements that were not constantly present in the collection during a full iteration, may be returned or not: it is undefined.

解决方案的关键在于游标本身。见 Making sense of Redis’ SCAN cursor 。 可以推导出扫描进度的百分比，因为游标实际上是表大小的索引的位反转。

使用 DBSIZE 或 INFO keyspace 命令，您可以随时获取您拥有的 key 数量:

> 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 参数。

假设您将以 10 Hz(每 100 毫秒)的频率( F 单位为 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 。它增加是有道理的，因为:

key 数量从 200032 增加到 281569。

虽然我们只有 60% 的初始估计剩余调用数，但由于 65% 的键空间等待扫描，因此进度落后。

所有这些都是假设你得到了所有的 key 。 如果您是模式匹配 ，您需要使用过去来估计要找到的剩余 key 数量。我们将 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。