Real-time leaderboard

Why does the board slow down every time someone looks at it?

The app’s home screen should show this week’s ten best cooks, and each cook’s own dashboard should say where she stands: “You are 214th of 2,000 this week.” Reviews arrive all day, so the board should move as they do.

The first version is one query. It adds up the stars each cook earned since Monday, sorts all 2,000 cooks, and takes the top ten. The dashboard runs the same query and counts how many cooks sit above.

At lunch on a weekday, 200,000 customers open the home screen. The query runs about 300 times a second, each time reading the week’s reviews and sorting the cooks again. Estimate the work before reading on. Sorting 2,000 cooks is about 22,000 comparisons, so 300 runs a second is over six million comparisons a second, to produce an answer that barely changes between two runs.

The board is also wrong in a quieter way. Points add up, so a cook with four hundred reviews averaging 4.8 sits far above one with three five-star reviews. That much is fair. But points reward volume: the busiest cook wins even when her food is ordinary.

A Redis sorted set is the standard answer for a board like this, and it is worth knowing why. It adds a review in a few dozen steps and answers “what is my rank?” in a few dozen more, for 2,000 cooks or 200,000. The question is how a list can stay in order while the scores in it keep changing, without reading the whole list each time one cook’s score changes.

The skip list inside a sorted set

The sorted set from lesson 3.6 orders members by a score and is implemented as a skip list plus a hash table. The skip list decides what every board operation costs, so it is worth looking inside.

Skip list

A sorted linked list with extra “express” lists on top. Each node gets a random height; level k holds only the nodes at least k tall. A search starts at the top and drops down, so it skips most of the list.

For example: With heights decided by a coin that comes up with probability 1/4, about a quarter of the cooks reach level 2, a sixteenth reach level 3, and 2,000 cooks need about six levels.

Updating a cook’s points is a delete and an insert in the skip list, both found by one search, plus a hash-table write so the member can be found by name in O(1). That is why ZINCRBY and ZREVRANK are O(log N), and why reading the top ten (ZRANGE board 0 9 REV) costs O(log N + 10): the list is already in order.

What should the score be?

The data structure is settled. What remains is which number to sort the cooks by.

The smoothed average is (C × m + sum of stars) / (C + number of reviews), with m = 4.2, the city’s average, and C = 20, as if every cook started the week with twenty average reviews. Each review adds its stars and one to a count in a hash (HINCRBY twice), computes the new average and writes it with ZADD, all in one Lua script so two reviews cannot interleave.

What to remember

1. A sorted set is a skip list plus a hash table: updates, rank and top-k in O(log N), and the board is always already sorted.
2. A skip list is a sorted list with random-height “express” levels; a search starts on the top level and drops down a level whenever the next node would overshoot, so the cost grows with log n.
3. Decide the score before the structure: points reward volume, a smoothed average rewards quality. Fold time into the score if ties must go to the first.
4. Use one key per week (or other period) and let it expire some weeks later. The board is a copy that can be rebuilt from the reviews.

Keep the list sorted as facts arrive; never re-sort it on every read.

In the real world

The board in the lab has 16 cooks and one coin per name. Real sorted sets add what the toy leaves out: small sets are stored packed (a listpack) and convert to a skip list past 128 members by default, as lesson 3.6 showed, and every node keeps spans so rank is counted on the way down.

The pattern outlives Redis: keep a structure that is already in the order you read, and update it in O(log n) as facts arrive, instead of sorting on every read.