Redis 排序集

Redis 排序集简介

Redis 排序集是按关联分数排序的唯一字符串（成员）的集合。 当多个字符串具有相同的分数时，字符串将按字典顺序排序。 排序集的一些用例包括：

  • 排行榜。例如，您可以使用排序集轻松维护大型在线游戏中最高分的有序列表。
  • 速率限制器。特别是，您可以使用排序集来构建滑动窗口速率限制器，以防止过多的 API 请求。

您可以将排序集视为 Set 和 一个 Hash。与集合一样，排序集由唯一的、不重复的 string 元素，所以从某种意义上说，排序集也是一个集。

然而，虽然 sets 内的元素没有排序，但 排序集与浮点值相关联，称为 Score（这就是为什么该类型也类似于哈希的原因，因为每个元素 映射到一个值）。

此外，排序集中的元素是按顺序获取的（因此它们不是 ordered on request，order 是数据结构的一个特性，用于 表示排序集）。它们根据以下规则进行排序：

  • 如果 B 和 A 是具有不同分数的两个元素，则如果 A.score > B.score，则 A > B。
  • 如果 B 和 A 的分数完全相同，则如果 A 字符串的字典顺序大于 B 字符串，则 A > B。B 和 A 字符串不能相等，因为排序集只有唯一的元素。

让我们从一个简单的例子开始，我们将添加所有的赛鸽和他们在第一场比赛中获得的分数：

As you can see ZADD is similar to SADD, but takes one additional argument (placed before the element to be added) which is the score. ZADD is also variadic, so you are free to specify multiple score-value pairs, as shown in the example above.

With sorted sets it is trivial to return a list of racers sorted by their score because actually they are already sorted.

Implementation note: Sorted sets are implemented via a dual-ported data structure containing both a skip list and a hash table, so every time we add an element Redis performs an O(log(N)) operation. That's good, so when we ask for sorted elements, Redis does not have to do any work at all, it's already sorted. Note that the ZRANGE order is low to high, while the ZREVRANGE order is high to low:

Note: 0 and -1 means from element index 0 to the last element (-1 works here just as it does in the case of the LRANGE command).

It is possible to return scores as well, using the WITHSCORES argument:

Operating on ranges

Sorted sets are more powerful than this. They can operate on ranges. Let's get all the racers with 10 or fewer points. We use the ZRANGEBYSCORE command to do it:

We asked Redis to return all the elements with a score between negative infinity and 10 (both extremes are included).

To remove an element we'd simply call ZREM with the racer's name. It's also possible to remove ranges of elements. Let's remove racer Castilla along with all the racers with strictly fewer than 10 points:

ZREMRANGEBYSCORE is perhaps not the best command name, but it can be very useful, and returns the number of removed elements.

Another extremely useful operation defined for sorted set elements is the get-rank operation. It is possible to ask what is the position of an element in the set of ordered elements. The ZREVRANK command is also available in order to get the rank, considering the elements sorted in a descending way.

Lexicographical scores

In version Redis 2.8, a new feature was introduced that allows getting ranges lexicographically, assuming elements in a sorted set are all inserted with the same identical score (elements are compared with the C memcmp function, so it is guaranteed that there is no collation, and every Redis instance will reply with the same output).

The main commands to operate with lexicographical ranges are ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX and ZLEXCOUNT.

For example, let's add again our list of famous racers, but this time using a score of zero for all the elements. We'll see that because of the sorted sets ordering rules, they are already sorted lexicographically. Using ZRANGEBYLEX we can ask for lexicographical ranges:

Ranges can be inclusive or exclusive (depending on the first character), also string infinite and minus infinite are specified respectively with the + and - strings. See the documentation for more information.

This feature is important because it allows us to use sorted sets as a generic index. For example, if you want to index elements by a 128-bit unsigned integer argument, all you need to do is to add elements into a sorted set with the same score (for example 0) but with a 16 byte prefix consisting of the 128 bit number in big endian. Since numbers in big endian, when ordered lexicographically (in raw bytes order) are actually ordered numerically as well, you can ask for ranges in the 128 bit space, and get the element's value discarding the prefix

Updating the score: leaderboards

Just a final note about sorted sets before switching to the next topic. Sorted sets' scores can be updated at any time. Just calling ZADD against an element already included in the sorted set will update its score (and position) with O(log(N)) time complexity. As such, sorted sets are suitable when there are tons of updates.

Because of this characteristic a common use case is leaderboards. The typical application is a Facebook game where you combine the ability to take users sorted by their high score, plus the get-rank operation, in order to show the top-N users, and the user rank in the leader board (e.g., "you are the #4932 best score here").

Examples

  • There are two ways we can use a sorted set to represent a leaderboard. If we know a racer's new score, we can update it directly via the ZADD command. However, if we want to add points to an existing score, we can use the ZINCRBY command.

You'll see that ZADD returns 0 when the member already exists (the score is updated), while ZINCRBY returns the new score. The score for racer Henshaw went from 100, was changed to 150 with no regard for what score was there before, and then was incremented by 50 to 200.

Basic commands

  • ZADD adds a new member and associated score to a sorted set. If the member already exists, the score is updated.
  • ZRANGE returns members of a sorted set, sorted within a given range.
  • ZRANK returns the rank of the provided member, assuming the sorted is in ascending order.
  • ZREVRANK returns the rank of the provided member, assuming the sorted set is in descending order.

See the complete list of sorted set commands.

Performance

Most sorted set operations are O(log(n)), where n is the number of members.

Exercise some caution when running the ZRANGE command with large returns values (e.g., in the tens of thousands or more). This command's time complexity is O(log(n) + m), where m is the number of results returned.

Alternatives

Redis sorted sets are sometimes used for indexing other Redis data structures. If you need to index and query your data, consider the JSON data type and the Redis Query Engine features.

Learn more

RATE THIS PAGE
Back to top ↑