Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Top-K & leaderboards

Answering a player's "what is my rank?" among 30 million: why an index makes the top 10 cheap and a rank expensive, sorted sets that keep the order on every write, ties, time windows, merging per-shard answers, and count-min sketches for global heavy hitters over a stream.

Position 2,340,117

A player finishes a match of a puzzle game with 1,520 points and taps the trophy icon. She wants one answer: where am I? The screen should say #2,340,117 of 30 million, with the players just above and just below her, under the top 10.

The top 10 is the easy half. With an index on score, SELECT … ORDER BY score DESC LIMIT 10 reads ten index entries and stops. Her rank is the hard half. SELECT COUNT(*) FROM players WHERE score > 1520 walks every index entry above her, 2.3 million of them, and a beginner near the bottom walks almost 30 million. A rank query over an ordinary index costs time in proportion to the rank, O(rank), and most players sit deep in the list.

The writes make it worse. Every finished match changes a score and rewrites that player's index entry, and matches end in bursts, when a tournament round closes or an event starts. So a leaderboard, which looks like a read feature, is decided on the write side: which structure keeps the order up to date on every write, so that both the top 10 and any player's rank are cheap to read?

A set that knows positions

A sorted set does. Redis's ZSET keeps each member with a score, in score order, in a skip list whose links also record how many members each one jumps over, so it reaches a position by counting along a few links instead of walking every member. Three commands cover her screen:

  • ZINCRBY lb:global 30 player:42 adds 30 points and moves the player into place, in O(log N).
  • ZREVRANGE lb:global 0 9 WITHSCORES returns the top 10.
  • ZREVRANK lb:global player:42 returns her position, counted from 0, in O(log N); a ZREVRANGE from five places above it to five below gives her neighbours.

Thirty million members at roughly 100 bytes each is about 3 GB, which fits on one node: its size alone does not call for sharding this leaderboard. The top-10 key, though, is read by every results screen at once, a hot key; the cheapest of the defences in Hot keys & cache stampedes is to cache the top 10 for a second.

Memory is fast and forgets on a crash, so the sorted set is the serving copy, not the truth. The truth is the events, player 42 scored 30, appended to a log or a table. A lost Redis node is rebuilt by replaying them into a fresh set, which takes over once it has caught up with the log; replayed onto a live set, events it already holds would count twice. Replaying only what a crash left out needs a record of which events the set already holds, such as each event's id written in the same atomic step as its increment; without one, the safe repair is that full rebuild. One sorted set holding every score with nothing behind it is a single point of loss with no way back.

Score events in, ranked reads out

The API appends the durable event, then applies the ZINCRBY; a crash between the two is repaired by replaying events — reads never touch the database.

Two players on 1,520

Another player reaches 1,520 two days after her. Redis orders members with equal scores by their names, which is deterministic but means nothing to players: they expect whoever got there first to rank higher. The usual fix packs the tiebreak into the score itself, score × 2^20 + (MAX − timestamp), so the earlier achiever gets the larger number and a rank query stays a single call.

Three details decide whether that works. Count timestamp in seconds from the window's start and make MAX the window's length, so the low 20 bits cover about 12 days; widen them for a longer window. Keep the packed number under 2^53, where a Redis score, a double, stops being exact. And re-pack the low bits on every update, with a Lua script that reads the current score, re-packs it and ZADDs the result, because a plain ZINCRBY keeps the first write's timestamp.

This week, not all time

Players care about this week more than all time. A weekly leaderboard is a sorted set per bucket, lb:2026-w44, updated alongside the global one and given an expiry so old weeks clear themselves. A last 24 hours leaderboard is a sliding window, approximated by a ZUNIONSTORE of the last 24 hourly buckets (its edge is accurate to the hour), recomputed on a schedule, say once a minute, into a key that reads come from. Those hourly buckets hold plain points, not packed scores, because a union adds the tiebreak bits too and they would spill into the points; ties in it fall back to name order. Run that union on every request and the busiest screen in the game merges 24 sets thousands of times a second. Where recency only needs to weigh, not cut off, a decayed score that adds points × e^(t/τ) on each write (t the write's time, τ how fast old points fade, so later points weigh more) avoids the rebuild, at the price of rescaling every score now and then as the multiplier grows.

Per-region leaderboards and the merge

Per-region leaderboards, or a game far larger than this one, split players across shards, by region or by a hash of the player ID, with a sorted set on each (how to pick that key is the question Sharding & partitioning answers). The top 10 survives the split. Each player lives in exactly one shard, so the global top 10 is always inside the union of the shards' top 10s: ask each shard for 10, merge the top-K of each shard, keep 10.

Her global rank does not merge that cheaply. It is one more than the sum, over every shard, of how many players there have a higher packed score than hers, which counts the tiebreak too, one ZCOUNT per shard on every rank request. A game that shows global and regional ranks often writes each score twice instead, to its region's set and to a global one, and pays the second write to keep each rank a single call.

Trending searches: keys you cannot count one by one

The game's level browser has a search box, and the home screen shows what players searched for most in the last completed five-minute window, refreshed as each window closes. Every string anyone types is a key: level names, typos, a code pasted once. Exact counters for unbounded keys need an entry for every distinct string in the window, and a burst of one-off strings can push that past the memory you budgeted. With an open key space, an approximate answer in fixed memory is the right tool, where approximate is acceptable: nobody notices that the 9th trending search is really the 11th, but a prize paid on an approximate rank would be a dispute.

A count-min sketch holds the counts. It is a few rows of counters, each row with its own hash function. Counting a key adds 1 to the counter its hash picks in every row; estimating it takes the smallest of those counters. Other keys sharing a counter can only push it up, so the estimate is never below the true count, and the overcount is bounded: with 2,000 counters per row it stays under about 0.14% of all searches counted, and with 5 rows that bound holds in more than 99% of cases. That is 10,000 counters, around 40 KB, however many distinct strings arrive.

A sketch cannot list its keys, so it is paired with a heap of the heavy hitters, fifty here: after counting a search, estimate it: a search already in the heap gets its new estimate, a new one goes in while the heap has room, and after that it takes the smallest entry's place only if its estimate is larger.

One process cannot take every search, so the stream is partitioned by a hash of the term, and each processor keeps its own sketch and heap over a tumbling 5-minute window. Every window a merger takes each local top 50 and publishes the top 10; since each term is counted on one processor only, the global top 10 is inside the union of the local lists, up to the sketch's error. Memory stays in kilobytes to a few megabytes per processor, at a thousand searches a second or a million. Window boundaries, late events and keeping counts through a processor crash belong to Stream processing: windows, watermarks & state, and the Trending Topics Challenge is this half on its own, per region, with bot bursts to dampen.

Sketch per partition, merge for the answer

Her rank, on the Gaming Leaderboard Challenge

The Gaming Leaderboard Challenge wants scores from game servers, global and per-region top-N leaderboards, a player's rank with neighbours, and daily, weekly and all-time leaderboards under bursty submissions. Spend the run on the write path: one durable event and one sorted-set update per score, the read path labelled ZREVRANGE and ZREVRANK, never a database sort, and an edge from the event store back into the sorted set for the rebuild. Then decide how the global leaderboard relates to the regional ones, merged top 10s or a second write, and write that choice on the edge.

Practice this