如何在 Redis 的 ZRANK 中获得相同分数的相同排名？

Question

如果我有5个成员分数如下

a - 1
b - 2
c - 3
d - 3
e - 5

c 的 ZRANK returns 2，d 的 ZRANK returns 3

有没有办法获得相同分数的相同排名？
示例：ZRANK c = 2，d = 2，e = 3
如果是，那么如何在 spring-data-redis 中实现？

Answer 1

排序集合中的排名是唯一的，具有相同分数的元素按词法排序（排序）。

没有执行此操作的 Redis 命令"dense ranking"

但是，您可以使用 Lua 脚本从排序集中获取范围，并将其缩减为您请求的形式。这可能适用于小型数据集，但您必须设计更复杂的东西才能扩展。

Answer 2

您可以使用两个 Sorted Set 来实现目标：一个用于 member to score mapping，另一个用于 分数到排名映射.

添加

将项目添加到 会员得分映射：ZADD mem_2_score 1 a 2 b 3 c 3 d 5 e
将分数添加到 分数到排名映射：ZADD score_2_rank 1 1 2 2 3 3 5 5

搜索

先获取分数：ZSCORE mem_2_score c，这应该是return的分数，即3.
得到分数的排名：ZRANK score_2_rank 3，这应该return密集排名，即2.

为了运行它是原子的，将 Add 和 Search 操作包装成 2 Lua脚本。

Answer 3

任何真正的解决方案都需要满足原始问题中缺少的要求。我的第一个答案假设一个小数据集，但这种方法不会随着密集排名（例如通过 Lua）至少在 O(N) 中完成而扩展。

所以，假设有很多用户有分数，for_stack建议的方向更好，其中结合了多种数据结构。我相信这就是他最后一句话的主旨。

要存储用户的分数，您可以使用哈希。虽然从概念上讲，您可以使用单个密钥来存储所有用户分数的哈希值，但实际上您希望对哈希值进行哈希处理，以便它可以扩展。为了使这个示例简单，我将忽略哈希缩放。

这就是您在 Lua 中添加（更新）用户分数的方式：

local hscores_key = KEYS[1]
local user = ARGV[1]
local increment = ARGV[2]
local new_score = redis.call('HINCRBY', hscores_key, user, increment)

接下来，我们要跟踪每个离散分值的当前用户数，因此我们为此保留另一个哈希值：

local old_score = new_score - increment
local hcounts_key = KEYS[2]
local old_count = redis.call('HINCRBY', hcounts_key, old_score, -1)
local new_count = redis.call('HINCRBY', hcounts_key, new_score, 1)

现在，我们需要维护的最后一件事是每个分数排名，以及一个排序集。每个新分数都添加为 zset 中的成员，并删除没有更多用户的分数：

local zdranks_key = KEYS[3]
if new_count == 1 then
  redis.call('ZADD', zdranks_key, new_score, new_score)
end
if old_count == 0 then
  redis.call('ZREM', zdranks_key, old_score)
end

由于使用了 Sorted Set，这个 3-piece-script 的复杂度为 O(logN)，但请注意，N 是离散分值的数量，而不是系统中的用户。获取用户的密集排名是通过另一个更短更简单的脚本完成的：

local hscores_key = KEYS[1]
local zdranks_key = KEYS[2]
local user = ARGV[1]

local score = redis.call('HGET', hscores_key, user)
return redis.call('ZRANK', zdranks_key, score)

Answer 4

然后是这个 Pull Request - https://github.com/antirez/redis/pull/2011 - which is dead, but appears to make dense rankings on the fly. The original issue/feature request (https://github.com/antirez/redis/issues/943) 引起了一些兴趣所以也许值得恢复它 /cc @antirez :)

Answer 5

unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x;
    unsigned long rank = 0;
    int i;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                sdscmp(x->level[i].forward->ele,ele) <= 0))) {
            rank += x->level[i].span;
            x = x->level[i].forward;
        }

        /* x might be equal to zsl->header, so test if obj is non-NULL */
        if (x->ele && x->score == score && sdscmp(x->ele,ele) == 0) {
            return rank;
        }
    }
    return 0;
}

https://github.com/redis/redis/blob/b375f5919ea7458ecf453cbe58f05a6085a954f0/src/t_zset.c#L475

这是一段代码，redis 用于计算有序集合中的排名。现在，它只是根据 Skiplist 中的位置给出排名（根据分数排序）。

What does the skiplistnode variable "span" mean in redis.h?（什么是跨度？）

如何在 Redis 的 ZRANK 中获得相同分数的相同排名？

How to get same rank for same scores in Redis' ZRANK?

redis

spring-data-redis