Part 4 of 8 · 2 min read
Sorted sets
The right structure.
Redis is an in-memory store, so reads and writes are fast. It has a sorted set: a collection of unique members, each with a score, kept in score order all the time. A member appears once. Scores may repeat.
How it works inside. A sorted set uses two structures. A hash table maps each member to its score, so a lookup is fast. A skip list keeps members ordered by score.
A skip list is a sorted linked list with extra index levels on top. Each level skips every other node of the level below, like express stops on a train line. A search starts at the top, moves along the fast levels, and drops down when it would overshoot. This gives roughly logarithmic time, like a binary search.
A worked example (made up). A plain sorted list of 1,000,000 players needs about 1,000,000 steps in the worst case. With index levels, a search takes about 20 steps, since the base-2 logarithm of 1,000,000 is about 20.
Because the structure keeps order on every insert, the work is spread across updates, and a rank is a quick lookup.
Commands.
ZINCRBY key 1 member: add 1 to the member's score, or create it with 1. Logarithmic time.ZREVRANGE key 0 9 WITHSCORES: the top 10 with their scores.ZREVRANK key member: the rank of a member, counting from the highest.ZREVRANGE key (rank-4) (rank+4): a player with four above and four below.
Monthly sets. Each month gets its own key, such as leaderboard_feb_2021. Old months move to history storage.
Flows. A win calls ZINCRBY on the current month. The top 10 calls ZREVRANGE, then looks up names and pictures for those ten ids in a database (or a small cache). A rank request calls ZREVRANK.
Sorted set
A sorted set is a collection of unique members, each with a score, that is always kept in score order.
Example: adding ("mary1934", 120) and ("bob_7", 119) leaves mary1934 first, and asking for her rank returns 0 (first place).
Read it as
A sorted set is a scoreboard that reorders itself the moment a number changes, so no one ever sorts the table.
Check yourself: 1. Which two structures make up a sorted set? 2. Which command returns the top 10? 3. Why is ranking quick in a sorted set?