redis - 使用 Redis 检查一个集合中的哪些键存在于另一个排序集合中的最佳方法是什么

Question

假设我有一组在线用户，可能包含 20,000 个条目。

接下来，假设每个用户都有自己关注的一组人。

当用户登录时，我想查看他们以下列表中的哪些用户在线。

据我所知，有两个选项。

MULTI
ZINTERSTORE temp 2 online, following
ZRANGE temp 0 -1
DEL temp
MULTI EXEC

或者，我可以让列表用户跟随列表，然后遍历所有用户，为每个用户触发一个 ISMEMBER 调用:

    SMEMBERS following


   MULTI
   foreach(following as fol){
      ISMEMBER online fol
   }
  MULTI EXEC

这两种方法都不适合我。有没有更好的办法？如果不是，如果我们假设一个普通用户在他们的关注列表中有 200 人，平均在线人数为 20,000，那么以上哪一个会表现最好。

提前致谢。

Answer 1

redis 文档有助于正确理解您的问题解决方案。

使用 ZINTERSTORE 查看第一个解决方案它需要时间复杂度:O(N * K) + O(M * log(M)) 在最坏的情况下，N 是最小的输入排序集，K 是输入排序集的数量M 是结果排序集中的元素数。当您需要将拥有 20,000 名关注者的人与 20,000 名平均在线人数进行比较时，这一点至关重要。

您的第二个解决方案要好得多。基于ISMEMBER (O(1)) 它需要时间复杂度 O(N) 在最坏的情况下，N 是最小的输入集。

关于用户在线处理还有一个有趣的解决方案。你应该知道 SETBIT和 GETBIT - 它最多可以处理 2^32 位或用户(如果您的用户具有常规 ID)。例如 - id 为 1 的用户 - 第 1 位，345 - 第 345 位等等。在这种情况下，您只有 512mb 的内存用于最多 4,294,967,296 个用户和 O(1) 时间复杂度来获取/设置他们的状态。并使用您的第二种方法将您排序的关注者集与在线数据相交。

如果使用 redis >= 2.6，你应该尝试使用 LUA 来优化第二类解决方案。例如，map/reduce 在我的笔记本电脑上为 200,000 个键 foreach 只需要大约 720 毫秒。然后更少200 位用户为 1 毫秒。