Sorted Sets in Redis

We do not have to build the map and the tree ourselves. Redis has them. We met Redis as a cache server, and again as the channel between the instances of a WebSocket server. This time, we use it to keep data that is not a cache.

Redis offers a sorted set: a set of members, each with a score, kept in order of score. For the leaderboard, a member is a player ID, and its score is the player’s rating.

What the leaderboard does with it

We keep one sorted set for each time control. Here is what the leaderboard service does with the blitz sorted set, in pseudocode:

When a game ends:
    for each of the two players:
        blitz.setScore(playerId, newRating)

GET /leaderboards/blitz?page=3
    players = blitz.playersRanked(101, 150)
    return players, each with their rank and rating

GET /leaderboards/blitz/players/5512
    rank = blitz.rankOf(5512)
    around = the 5 players ranked above 5512 and the 5 ranked below
    return rank, around

These are the three operations from the previous section.

The Redis commands

In Redis, these operations are commands. The Z at the start of each name marks a sorted-set command.

ZADD blitz 2140 5512

ZADD sets player 5512’s score to 2140 in the sorted set named blitz. If player 5512 is not in the set, it is added. If it is, its score is replaced.

ZREVRANK blitz 5512

ZREVRANK gives player 5512’s rank. REV means the ranks are counted from the highest score down. Redis counts ranks from 0, so the highest score has rank 0. For player 5512, it returns 100. That is rank 101 on our leaderboard.

ZRANGE blitz 100 149 REV WITHSCORES

ZRANGE gives the members between two ranks. With REV, it counts from the highest score down. So 100 to 149 are ranks 101 to 150 on our leaderboard. That is page 3. WITHSCORES returns each member’s score with it.

For player 5512’s neighbors, the leaderboard service takes the rank ZREVRANK returned, 100, and asks for 95 to 105.

How Redis keeps the order

A Redis sorted set uses a map from member to score, like the one in the previous section. For the order, it uses a skip list instead of a search tree. A skip list is a sorted linked list with extra links that skip ahead over many entries at once. Each link records how many entries it skips, and those counts do the job that the subtree sizes did in the tree.

The cost is the same as the tree’s. Setting a score or finding a rank takes logarithmic time: the work grows with $lo g_{2} n$ , which is about 25 for 20 million players. A page takes those steps to find its first player, then one more step for each of its 50 players.