Redis `SCAN`:如何在可能匹配的新键之间保持平衡并确保在合理的时间内最终结果? [英] Redis `SCAN`: how to maintain a balance between newcomming keys that might match and ensure eventual result in a reasonable time?
问题描述
我对 Redis 不太熟悉.目前我正在设计一些实时服务，我想依赖它.我希望每分钟约 10000-50000 个键是 SET 与一些合理的 EX 并使用 SCAN 匹配它们很少足以不影响性能瓶颈.
I am not that familiar with Redis. At the moment I am designing some realtime service and I'd like to rely on it. I expect ~10000-50000 keys per minute to be SET with some reasonable EX and match over them using SCAN rarely enough not to bother with performance bottlenecks.
我怀疑的是输入/输出速率"和可能与某些 SCAN 查询匹配的键可能会溢出，因此它永远不会终止(即总是用最新的光标位置回复并强制您继续; 如果一个人每秒消耗 x 个项目 并且有 x + y 个项目每秒进入 并且 y > 0，那么这很容易发生).
The thing I doubt is "in/out rate" and possible overflooding with keys that might match some SCAN query and thus it never terminates (i.e. always replies with latest cursor position and forces you to continue; that could happen easily if one consumes x items per second and there are x + y items per second coming in with y > 0).
显然，我可以将所需的 SCAN 大小设置得足够长；但我想知道是否存在更好的解决方案，或者 Redis 本身是否保证 SCAN 在这种情况下会自动增加大小?
Obviously, I could set desired SCAN size long enough; but I wonder if there exists a better solution or does Redis itself guarantees that SCAN will grow size automatically in such a case?
推荐答案
首先是一些上下文，解决方案在最后:
SCAN 算法只有在迭代集合仍然限制在给定的最大大小，否则迭代一个总是增长的集合可能会导致 SCAN 永远不会终止一个完整的迭代.
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.
这很容易直观地看出:如果集合增长，就会有更多为了访问所有可能的元素，还有更多的工作要做，以及终止迭代的能力取决于调用次数将 SCAN 及其 COUNT 选项值与收藏不断增加.
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.
但是在 COUNT 选项中它说:
重要提示:没有必要对每一个都使用相同的 COUNT 值迭代.调用者可以自由地从一次迭代中更改计数到另一个根据需要，只要光标传入下一个调用是在上一次调用命令时获得的调用.
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.
重要的是要记住，来自扫描保证:
Important to keep in mind, from Scan guarantees:
- 一个给定的元素可能会被多次返回.这取决于处理重复元素情况的应用程序，例如只使用返回的元素来执行操作多次重新申请时是安全的.
- 没有的元素在完整迭代期间不断出现在集合中，可能是是否返回:未定义.
解决方案的关键在于游标本身.请参阅了解 Redis 的 SCAN 游标.可以推导出扫描进度的百分比，因为游标实际上是表大小的索引的位反转.
The key to a solution is in the cursor itself. See Making sense of Redis’ SCAN cursor. It is possible to deduce the percent of progress of your scan because the cursor is really the bits-reversed of an index to the table size.
使用 DBSIZE 或 INFO keyspace 命令，您可以随时获取您拥有的密钥数量:
Using DBSIZE or INFO keyspace command you can get how many keys you have at any time:
> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0
另一个信息来源是未记录的DEBUG htstats index，只是为了感受一下:
Another source of information is the undocumented DEBUG htstats index, just to get a feeling:
> 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
The table size is the power of 2 following your number of keys: Keys: 200032 => Table size: 262144
我们将为每次扫描计算所需的 COUNT 参数.
We will calculate a desired COUNT argument for every scan.
假设您将以 10 Hz(每 100 毫秒)的频率(F 以 Hz)调用 SCAN，并且您希望在 5 秒内完成(T ins).因此，您希望在 N = F*T 调用中完成此操作，在此示例中为 N = 50.
Say you will be calling SCAN with a frequency (F in Hz) of 10 Hz (every 100 ms) and you want it done in 5 seconds (T in s). So you want this finished in N = F*T calls, N = 50 in this example.
在第一次扫描之前，您知道当前进度为 0，因此您的剩余百分比为 RP = 1 (100%).
Before your first scan, you know your current progress is 0, so your remaining percent is RP = 1 (100%).
在每次 SCAN 调用之前(或者如果你想保存 DBSIZE 的往返时间(RTT)，你想要调整你的 COUNT 的每个给定数量的调用call)，你调用DBSIZE 来获取key的数量K.
Before every SCAN call (or every given number of calls that you want to adjust your COUNT if you want to save the Round Trip Time (RTT) of a DBSIZE call), you call DBSIZE to get the number of keys K.
您将使用 COUNT = K*RP/N
对于第一次调用，这是COUNT = 200032*1/50 = 4000.
For the first call, this is COUNT = 200032*1/50 = 4000.
对于任何其他调用，您需要计算 RP = 1 - ReversedCursor/NextPowerOfTwo(K).
For any other call, you need to calculate RP = 1 - ReversedCursor/NextPowerOfTwo(K).
例如，假设您已经完成了 20 个调用，那么现在 N = 30(剩余调用次数).您调用了 DBSIZE 并得到 K = 281569.这意味着 NextPowerOfTwo(K) = 524288，这是 2^19.
For example, let say you have done 20 calls already, so now N = 30 (remaining number of calls). You called DBSIZE and got K = 281569. This means NextPowerOfTwo(K) = 524288, this is 2^19.
您的下一个光标是十进制的 14509 = 000011100010101101 二进制.由于表大小为 2^19，我们用 18 位表示.
Your next cursor is 14509 in decimal = 000011100010101101 in binary. As the table size is 2^19, we represent it with 18 bits.
您反转位并得到二进制的 101101010001110000 = 十进制的 185456.这意味着我们已经涵盖了 524288 个中的 185456 个.并且:
You reverse the bits and get 101101010001110000 in binary = 185456 in decimal. This means we have covered 185456 out of 524288. And:
RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%
所以你必须调整:
COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100
所以在您的下一个 SCAN 调用中，您使用 6100.它增加是有道理的，因为:
So in your next SCAN call you use 6100. Makes sense it increased because:
- 密钥数量从 200032 个增加到 281569 个.
- 虽然我们只有 60% 的初始估计剩余调用数，但由于 65% 的键空间等待扫描，因此进度落后.
所有这些都假设您已获得所有密钥.如果您是模式匹配，您需要使用过去来估计要找到的剩余密钥数量.我们将 PM(匹配百分比)作为因子添加到 COUNT 计算中.
All this was assuming you are getting all keys. If you're pattern-matching, you need to use the past to estimate the remaining amount of keys to be found. We add as a factor PM (percent of matches) to the COUNT calculation.
COUNT = PM * K*RP/N
PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))
如果在 20 次调用后，您只找到 keysFound = 2000 个键，则:
If after 20 calls, you have found only keysFound = 2000 keys, then:
PM = 2000 / ( 281569 * 185456 / 524288) = 0.02
这意味着到目前为止只有 2% 的键与我们的模式匹配，所以
This means only 2% of the keys are matching our pattern so far, so
COUNT = PM * K*RP/N = 0.02 * 6100 = 122
这个算法可能可以改进，但你懂的.
This algorithm can probably be improved, but you get the idea.
确保在您开始使用的 COUNT 数字上运行一些基准测试，以测量您的 SCAN 花费的毫秒数，因为您可能需要在不阻塞服务器的情况下，在合理的时间内调整您对需要多少次调用 (N) 的期望，并调整您的 F 和 T 相应地.
Make sure to run some benchmarks on the COUNT number you'll use to start with, to measure how many milliseconds is your SCAN taking, as you may need to moderate your expectations about how many calls you need (N) to do this in a reasonable time without blocking the server, and adjust your F and T accordingly.
这篇关于Redis `SCAN`:如何在可能匹配的新键之间保持平衡并确保在合理的时间内最终结果?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
