CSE Roadmap

Common tier · about 4 hours · 8 parts

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?