Redis:实现固定大小的集合/列表来检查重复项

Question

我想使用 Redis 实现以下功能:

1. 我们有即将到来的事件。每个事件都有唯一的 ID
2. 我们想使用它的 ID 检查传入的事件是否重复
3. 我们只想维护最后 X 个事件 ID。 X 编号不是硬编码要求。这意味着拥有几个额外的 ID 不是问题。
4. 每个传入的事件也有时间戳。

不确定如何实现。

1. 我可以使用列表 - 使用 LPUSH 和 LTRIM - 我可以保持固定大小 - 但是，我无法轻松检查重复项。
2. 我可以使用 SET - 它允许我在处理传入事件之前非常容易地检查重复项 - 但是，我不确定如何限制 SET 的大小.

我应该使用哪种数据结构 - 这将使我能够轻松检查重复项并保持修复大小。

我正在使用 StackExchange.Redis 库。

Answer 1

TL;DR 两者都不是 - 使用排序集并将元素的(事件 ID)分数设置为时间戳(即 Unix 纪元)。

正如您所指出的，列表对于检测重复项而言是一个糟糕的选择，因为您将在 O(N) 复杂度中执行此操作。集合非常适合精确重复检测(实际上，也可以使用哈希)，您可以调用 SPOP每当集合的基数 (SCARD) 超过您的 X 时，Y 的 count，或在伪代码中:

y = SCARD key - x
if y > 0 then
  SPOP key y
end

但是，SPOP 是随机的，您提到过您有一个时间戳。在许多情况下，通过仅保留最新的元素而不是不确定的元素来限制集合的大小更为实用。为此，使用 Sorted Set 和 ZREMRANGEBYRANK通过丢弃最旧的事件，您可以将集合的基数 ( ZCARD) 保持在任意 X 值。请注意，排名是从最低到最高，因此您需要使用从 0(第一个得分最低的元素)-X(从最后一个元素开始的第 X+1 个元素，最高-得分元素)，即只有这个:

  ZREMRANGEBYRANK key 0 -x