26 — Real-Time Gaming Leaderboard

“Show the global top 10, and show me my own rank, across 500 million players, updated as scores change.”

A leaderboard is the scoreboard in a game: a list of players ordered by score, with a “you are number 4,182,996” line next to your own name. This chapter builds one for half a billion players.

Four things come out of it:

• what an ordered in-memory index actually costs, per element and per operation;
• why the “top 10” question and the “my rank” question are completely different problems;
• how to answer the hard one approximately in six microseconds, with an error bound you state up front;
• how to stop players from simply telling the server what their score was.

When you finish you should be able to explain to someone who has never built one why ranking is the hard part of a leaderboard and sorting is not.

Vocabulary, once, up front

Six words are used constantly from here on. Learn them now and the rest of the chapter reads without stopping.

• Rank — a player’s position in the ordering. Rank 1 is the best score.
• Percentile — that position expressed as a share of the population, so “top 2%” rather than “rank 9,412,336”.
• Sorted set — a collection of members, each carrying a numeric score, kept permanently in score order. Three operations matter here: insert-or-update a member’s score, read the highest k members, and ask for a given member’s position.
• Redis — the in-memory data store this chapter uses as its concrete reference implementation. Its sorted-set type is called a ZSET.
• Redis commands — ZADD writes a score, ZREVRANK reads a rank counting from the top, ZCOUNT counts members inside a score range, ZUNIONSTORE merges several sorted sets into a new one. These four appear throughout.
• Sharding — splitting one dataset across several machines because it no longer fits on, or can no longer be served by, one. Each slice is a shard.

What goes in and what comes out

The product is three calls. Here is what each one takes and returns.

result carrying events rather than a score is not a stylistic choice; the reasons occupy Cheating server authoritative scoring and the rate limit. And the whole chapter is about the cost of the middle row.

The one distinction the chapter turns on

There are two questions in the opening sentence and they have nothing to do with each other.

Top-10 is a merge of 64 tiny lists and costs microseconds. “What is my rank” is a global aggregate over half a billion rows, and it is the entire chapter.

An aggregate here means a number computed from the whole population rather than from any one row — a count, in this case. That is exactly what makes it resist being split across machines: no single machine holds enough of the population to compute it.

Candidates who reach for Redis ZREVRANK and stop have answered the easy half. The interviewer is waiting to hear what happens when the sorted set no longer fits on one machine.

The argument, in five steps

Each row below names a claim, the number that establishes it, and the section where that number is derived.

1. Framing: what decision, and what breaks

A score arrives, a sorted structure updates, and some number of players want to know where they now stand. That is the whole loop.

Three decisions come out of it:

1. Where does the sorted structure live once it stops fitting on one machine?
2. Is rank exact or approximate — and for which players?
3. Who is allowed to compute the score in the first place?

The table below lists the four events the system handles, how often each one happens, and the specific mistake that ruins it. The third row is the one this chapter is mostly about.

Requirements

The functional list is short; the interesting content is in the non-functional table below it, and specifically in its third row.

Functional

• submit(player_id, match_result) -> the server computes the score. The client never sends one.
• top(board, k) -> the top k entries with score and rank.
• rank(board, player_id) -> the player’s rank, and their percentile.
• around(board, player_id, n) -> the n players immediately above and below.
• Boards are (game, region, window) where window is daily, weekly, monthly, or all-time.

Non-functional

Five targets. Each row gives the number and the reason it is that number rather than some other one:

Three terms in that table are worth pinning down before you use them in an interview:

• p99 — the 99th percentile of the latency distribution: the time that 99 out of 100 requests beat, so one in a hundred is slower. Use percentiles rather than averages, because a player experiences one request at a time and an average hides the bad ones.
• Primary failover — what happens when the machine currently accepting writes dies and one of its replicas is promoted to take over. Durability here is the question of whether a score already accepted survives that promotion.
• Cache — a store is a cache when it can be thrown away and rebuilt from somewhere else. That is exactly the status the sorted set has here, with the score log as the authoritative record.

The requirement that shapes everything is the third one, and it is the one candidates never propose themselves: rank accuracy is not uniform across the board. Saying that early converts an impossible requirement into a tractable one.

Back-of-envelope

Four numbers are given, and everything else is derived from them — including one ratio that rules out an entire family of designs:

500,000,000 registered players, 50,000,000 daily active, 10 score submissions and 5 rank reads per active player per day.

Daily active users, usually shortened to DAU, is the count of distinct players who do anything at all on a given day. It is far smaller than the registered population, and it — not the 500 M — is what every rate below is derived from. Templates from The three numbers you actually need.

The block below turns those four numbers into requests per second. There are 86,400 seconds in a day, so a daily total divided by 86,400 is the average rate; “peak x3” is the assumption that the busiest hour runs at three times the daily average.

submissions/day   50,000,000 x 10          =  500,000,000
submissions/s     500,000,000 / 86,400     =  5,787       peak x3  =  17,361
rank reads/day    50,000,000 x 5           =  250,000,000
rank reads/s      250,000,000 / 86,400     =  2,894       peak x3  =   8,682

Note the ratio: 500 M submissions against 250 M rank reads is 2 writes per read.

That is backwards from almost every other system in this book, where reads outnumber writes many times over. It forbids the obvious answer of precomputing a rank for every player and serving it from a column: you would recompute more often than anyone reads.

Data model: a sorted set, and what it costs per element

The unit of storage is one player’s entry in a sorted set, and counting its bytes produces the figure every storage line in the chapter is built from.

Redis stores a sorted set as two structures side by side: a skiplist and a hash table.

A skiplist is an ordered linked list with express lanes. Every node sits in the bottom-level list. A random subset of nodes also appears in a level above, a smaller subset above that, and so on. A search starts at the top level and drops down as it goes — a series of increasingly local shortcuts — reaching any element in about log n steps instead of n.

A hash table maps a key straight to a slot by doing arithmetic on the key, giving O(1) lookup: constant time regardless of how many elements there are.

Each structure does one job. The skiplist provides ordered traversal and rank. The hash table provides instant “what is this player’s score” lookup. Both hold a pointer to every element, so every player is paid for twice — that is where a lot of the 100 bytes below comes from.

The one parameter that sets both the memory and the cost

The skiplist’s shape comes from a single number. When a node is inserted, it is promoted to the next level up with probability p, and the promotion is retried at each level, so the node’s height is geometrically distributed. Redis uses p = 0.25.

That one number drives both the memory and the cost, and the same value has to be used for both. It does two things at once:

• it fixes the average node height at 1 / (1 - p) = 1.33 levels, which is the memory line below;
• it fixes the search cost at roughly log_{1/p}(n) / p node touches, which is derived in Sorted set arithmetic what zadd and zrevrank actually cost.

Quoting 1.33 levels for the memory and log2 n for the cost is quoting p = 0.25 and p = 0.5 in the same breath about the same structure. It understates the cost by 1.8x.

100 bytes per player

The block below adds up every byte one player occupies, in both structures. Read it as an itemized bill: three lines for the skiplist node, one for the member string, two for the hash table, one for the allocator.

skiplist node: score double 8 + member ptr 8 + backward ptr 8      =  24
forward pointers and spans, p = 0.25, average levels
                            1 / (1 - 0.25) = 1.33
                            1.33 x 16                              =  21
member string, 8-char player id, sds header + jemalloc bin         =  16
dict entry: key ptr 8 + value ptr 8 + next ptr 8                   =  24
dict bucket, amortized at load factor 1                            =   8
allocator overhead                                                 =   7
                                                                      ---
                                                                      100

Line by line:

• The first three lines are the skiplist node: its score (an 8-byte double), its backward and member pointers, and the average 1.33 levels of forward pointers and spans. A span is the count of nodes a pointer jumps over, and it is what makes rank cheap — Sorted set arithmetic what zadd and zrevrank actually cost explains it.
• member string is the player id. sds header is Redis’s own string wrapper (simple dynamic string), and a jemalloc bin is the fixed-size class the memory allocator rounds every request up to, which is why a 9-byte string occupies 16.
• dict entry and dict bucket are the hash table’s overhead: one record per element plus one array slot, at a load factor of 1, meaning the table holds about as many slots as elements.
• The last line is the allocator’s per-object bookkeeping.

Multiply that per-player figure by the population:

all-time board    500,000,000 x 100        =  50,000,000,000    =  50 GB

50 GB of RAM to store 4 GB of actual information. A 4-byte score plus a 4-byte id is 8 bytes per player, so 500,000,000 x 8 = 4,000,000,000 bytes = 4 GB of payload sitting inside 50 GB of structure.

The 12.5x (100 / 8) is what an in-memory ordered index costs. The honest framing is that you are buying O(log n) rank with it — a rank query whose cost grows with the logarithm of the population rather than in proportion to it, so ten times more players costs a few more steps rather than ten times the work.

Split across 64 machines, each one holds:

per shard         50 / 64                  =  0.78 GB
players per shard 500,000,000 / 64         =  7,812,500

Shard by player_id on a hash ring — the technique of mapping both players and machines onto a circle of hash values and giving each player to the next machine clockwise, so that adding one machine to N reassigns only 1/(N+1) of the members instead of reshuffling everybody (ch 05). Each shard holds a complete sorted set over the players it owns.

API sketch

Written as Python type signatures, the four calls fit on a page — and the one detail worth arguing about is in the return value of rank.

from typing import Literal, Protocol

Window = Literal["daily", "weekly", "monthly", "alltime"]


class Leaderboard(Protocol):
    def submit(self, player_id: int, match_id: str, result: dict) -> int:
        """Server-side scoring. `result` is match EVENTS, never a score.
        `match_id` makes the write idempotent -- see section 2.3."""

    def top(self, board: str, window: Window, k: int) -> list[tuple[int, int]]: ...

    def rank(self, board: str, window: Window, player_id: int,
             exact: bool = False) -> dict:
        """Returns {rank, score, percentile, exact: bool}. `exact=True` forces
        the scatter-gather path and may miss the 50 ms budget."""

    def around(self, board: str, window: Window,
               player_id: int, n: int) -> list[tuple[int, int]]: ...

rank returning an exact flag in the response is the design decision made visible: the caller is told which answer it got, so a client rendering “rank 12” and a client rendering “top 3%” can share one endpoint without either of them lying.

High-level architecture

In the diagram below, writes flow down the left side and reads enter from the right. The four boxes worth noticing are the three the score service writes to — the log, the shards, and the histogram — and the cache that fronts every read.

flowchart TB
    G(["game servers<br/>authoritative simulation"]) --> RL["rate limiter<br/>see ch 04"]
    RL --> SS["score service<br/>dedup on match_id"]
    SS --> LOG["append-only score log<br/>system of record, see ch 20"]
    SS --> Z[("ZSET shards, S = 64<br/>hash ring on player_id<br/>0.78 GB each")]
    SS --> HB[("bucket histogram<br/>Fenwick tree, 80 MB<br/>replicated")]
    Z --> HEAD[("exact head board<br/>top 10,000, 1 MB<br/>replicated everywhere")]
    LOG --> RB["rebuild job<br/>RTO 41.7 min"]
    RB --> Z

    Q(["read API"]) --> C["1 s TTL cache<br/>+ single flight"]
    C --> HEAD
    C --> HB
    C -->|"exact = true"| FO["scatter-gather<br/>64 x ZCOUNT"]
    FO --> Z

    style SS fill:#1d3557,color:#fff
    style Z fill:#2d6a4f,color:#fff
    style HB fill:#bc6c25,color:#fff
    style HEAD fill:#40916c,color:#fff
    style LOG fill:#495057,color:#fff

The write path, top to bottom.

Game servers run the authoritative simulation — the copy of the game the operator controls and trusts. They, not the player’s device, report what happened.

Their submissions pass through a rate limiter, which caps how often one account may submit (ch 04), and then into the score service, which deduplicates on match_id so a retried submission cannot count twice.

The score service then writes to three places:

• the append-only score log, the system of record: an ordered, immutable file of every score ever accepted, from which everything else can be rebuilt (ch 20);
• the ZSET shards, the 64 sorted sets hash-ringed on player_id, 0.78 GB each;
• the bucket histogram, a small Fenwick tree of score buckets defined in The hard part is rank not top k, which answers approximate rank out of 80 MB.

Two more boxes hang off those. The exact head board is the top 10,000 players kept as their own 1 MB sorted set, replicated everywhere. The rebuild job reads the log back into the shards after a loss, taking the 41.7 minutes derived in Sorted set arithmetic what zadd and zrevrank actually cost.

The read path, and which of the four routes serves you.

Every read first hits a cache with a 1-second TTL — time to live, the age at which a cached entry is discarded — plus single flight, meaning that when many identical requests miss the cache at once, only one is actually executed and the rest wait on its result.

Past the cache, where a request goes depends on where the player stands:

2. Deep dive

Everything below follows one thread: price the single machine honestly, watch rank break when the data splits, build the structure that replaces it, then fix the three things a real product adds — ties, time windows, and players who lie.

1. Sorted-set arithmetic: what ZADD and ZREVRANK actually cost

Before sharding anything, price a single-machine sorted set honestly — per operation and per element — and ask what runs out first. The answer is not what most people expect.

One machine is trivially correct, and that is the problem

The whole leaderboard on one machine is two commands: ZADD board score member to record a score, ZREVRANK board member to read a rank.

This is trivially correct, and it is worth saying why, because the reason is the thing that stops scaling. Redis executes commands on a single thread, one at a time, against one key. Every submission is therefore serialized against every other — they happen in a definite order with no overlap — and the sorted set is always in exactly one consistent state.

There is no read-modify-write race here: no situation where two writers each read the old value, each compute a new one, and one of the two updates is silently lost. So there is nothing to reconcile afterwards.

Correctness is a consequence of being on one machine. Every scaling step below spends some of it.

Why rank is O(log n): spans

Each forward pointer stores a span — the number of nodes that pointer jumps over — so a member’s rank is simply the sum of the spans along the path the search took to find it.

That is why ZREVRANK costs O(log n) and not O(n). Without spans, the structure would have to walk the bottom-level list and count nodes one at a time.

The constant in front of O(log n)

O(log n) is the shape of the cost. The constant in front of it is what you actually pay, and it comes from p, not from the base-2 logarithm.

The block below works from the tower height down to nanoseconds. log_{1/p} means the logarithm in base 1/p, which is base 4 when p = 0.25. Each node the search touches is one pointer chase into memory, and a memory reference costs about 100 nanoseconds:

levels in the tower, n = 500,000,000
  log_{1/p}(n),  p = 0.25:  log4(500,000,000)             =  14.4
node touches per rank, ~ log_{1/p}(n) / p
                          14.4 / 0.25                     =  57.8
measured on the skiplist in this section, fitted to n
                                                          =  53
memory-stall cost, one reference per node touched ([ch 02])
                          53 x 100 ns                     =  5,300 ns

5.3 microseconds per operation.

The figure usually quoted instead is 2.9 microseconds. It comes from log2(500,000,000) = 29, which is the node-touch count of a skiplist built with p = 0.5 — a different data structure from the one the memory model above was priced against. Measured touch counts run about 1.8x log2 n, and that ratio is 1 / (p log2(1/p)) = 2 in the limit.

Essentially all of the 5.3 microseconds is memory stalls, of two kinds:

• cache misses — the byte the processor wants is not in its fast local memory and must be fetched from main memory, at roughly 100 nanoseconds a time (ch 02);
• TLB misses — even the address translation for the memory page is not cached.

Walking pointers through 50 GB of scattered nodes is the worst possible access pattern for both.

Do not take the constant on trust. Five hundred million nodes will not fit in a notebook, but the growth rate will, and the growth rate is what the disagreement is about. The block below does four things: it builds real skiplists at four sizes (100k to 800k nodes), counts the nodes each rank query reads, fits a straight line of touches against log2 n, and extrapolates that line out to 500 million. The four numbered assertions at the end are the claims being checked.

"""A span-carrying skiplist, p = 0.25, measured. The point of this block is
that the SAME p has to price the memory and the cost."""
import math
import random


class SkipNode:
    __slots__ = ("score", "nxt", "span")

    def __init__(self, score, level):
        self.score = score
        self.nxt = [None] * level
        self.span = [0] * level          # nodes this pointer jumps over


class SpanSkiplist:
    """Redis's ZSET index. Rank is the sum of spans on the search path."""
    MAXLEVEL = 32

    def __init__(self, p=0.25, seed=0):
        self.p = p
        self.rng = random.Random(seed)
        self.level, self.n = 1, 0
        self.head = SkipNode(None, self.MAXLEVEL)
        self.touches = 0                 # nodes whose score we had to read

    def _random_level(self):
        level = 1
        while self.rng.random() < self.p and level < self.MAXLEVEL:
            level += 1
        return level

    def insert(self, score):
        update, rank = [self.head] * self.MAXLEVEL, [0] * self.MAXLEVEL
        x = self.head
        for i in range(self.level - 1, -1, -1):
            rank[i] = 0 if i == self.level - 1 else rank[i + 1]
            nxt = x.nxt[i]
            while nxt is not None and nxt.score < score:
                rank[i] += x.span[i]
                x, nxt = nxt, nxt.nxt[i]
            update[i] = x
        level = self._random_level()
        if level > self.level:
            for i in range(self.level, level):
                rank[i], update[i] = 0, self.head
                self.head.span[i] = self.n
            self.level = level
        node = SkipNode(score, level)
        for i in range(level):
            node.nxt[i], update[i].nxt[i] = update[i].nxt[i], node
            node.span[i] = update[i].span[i] - (rank[0] - rank[i])
            update[i].span[i] = (rank[0] - rank[i]) + 1
        for i in range(level, self.level):
            update[i].span[i] += 1
        self.n += 1

    def rank(self, score):
        """Members <= score, by summing spans. Counts every node it reads."""
        x, r = self.head, 0
        for i in range(self.level - 1, -1, -1):
            nxt = x.nxt[i]
            while nxt is not None:
                self.touches += 1
                if nxt.score > score:
                    break
                r += x.span[i]
                x, nxt = nxt, nxt.nxt[i]
        return r


def measure(n, probes=4_000, seed=1):
    sl, rng = SpanSkiplist(seed=seed), random.Random(7)
    for _ in range(n):
        sl.insert(rng.randrange(1 << 40))
    sl.touches = 0
    for _ in range(probes):
        sl.rank(rng.randrange(1 << 40))
    return sl.touches / probes


def fit_per_doubling(points):
    """Least squares of touches against log2(n): touches = a log2 n + b."""
    xs = [math.log2(n) for n, _ in points]
    ys = [t for _, t in points]
    mx, my = sum(xs) / len(xs), sum(ys) / len(ys)
    a = (sum((x - mx) * (y - my) for x, y in zip(xs, ys))
         / sum((x - mx) ** 2 for x in xs))
    return a, my - a * mx


sizes = [100_000, 200_000, 400_000, 800_000]
measured = [(n, measure(n)) for n in sizes]
a, b = fit_per_doubling(measured)

# 1. Rank really is a sum of spans, not a walk.
sl = SpanSkiplist(seed=3)
for s in [50, 10, 90, 30, 70]:
    sl.insert(s)
assert [sl.rank(s) for s in (10, 30, 50, 70, 90)] == [1, 2, 3, 4, 5]
assert sl.rank(60) == 3 and sl.rank(0) == 0

# 2. The structure is a p = 0.25 tower: average height 1 / (1 - p) = 1.33,
#    which is the 21 bytes of pointers and spans in the memory model.
big, rng = SpanSkiplist(seed=11), random.Random(23)
for _ in range(100_000):
    big.insert(rng.randrange(1 << 40))
tower, node = [], big.head.nxt[0]
while node is not None:
    tower.append(len(node.nxt))
    node = node.nxt[0]
assert abs(sum(tower) / len(tower) - 1 / (1 - 0.25)) < 0.02

# 3. Cost is NOT log2 n. It is ~1.8x that, because p = 0.25, not 0.5.
for n, t in measured:
    assert 1.7 < t / math.log2(n) < 2.0, (n, t, t / math.log2(n))

# 4. Extrapolate the fit to the populations the chapter actually quotes.
at_500m = a * math.log2(500_000_000) + b
at_shard = a * math.log2(7_812_500) + b
assert 50 <= at_500m <= 58, at_500m            # the chapter says 53
assert 38 <= at_shard <= 46, at_shard          # the chapter says 42
assert at_500m / math.log2(500_000_000) > 1.7  # ...and 29 is not in that range
assert at_500m > 1.7 * 29

What actually runs out first, and it is not the CPU

Now check whether the processor is the binding constraint — the resource that runs out first.

Multiplying the peak request rate by the cost of one request gives core-seconds per second: how many processor cores’ worth of work arrives each second. A value of 1.0 would mean one core fully saturated. Here, 5.3 microseconds is 0.0000053 seconds:

peak submissions/s                                        =  17,361
core-seconds/s   17,361 x 0.0000053                       =  0.0920

9.2% of one core at peak.

The single-threaded sorted set is nowhere near CPU-bound — nowhere near the point where the processor, rather than memory or network or disk, is what limits throughput. That surprises people, because “single-threaded” sounds like a ceiling.

Note how much slack there is. Even at twice the per-operation cost the conclusion would be identical, which is why the constant above is worth getting right for its own sake and not for this particular calculation.

Four other things bind long before the processor does:

The second and third rows use vocabulary worth unpacking.

Fork and copy-on-write. BGSAVE is how Redis writes a snapshot to disk. It forks: the operating system creates a child process that shares the parent’s memory pages, and the child writes the snapshot out while the parent keeps serving requests. The sharing is copy-on-write — pages stay shared until one side modifies a page, at which point that one page is duplicated. So a process taking heavy writes during a snapshot can end up with two copies of much of its data, doubling RSS (resident set size), the physical memory the process actually occupies.

The alternative is the AOF — append-only file — with everysec: append every command to a log file and flush it to disk once a second. That trades a second of possible loss for no fork at all.

Asynchronous replication. The primary acknowledges a write to the client before the replica has confirmed it. So there is always a window of already-acknowledged writes that exist only on the primary — 17 of them here, at 1 ms of lag and 17,361 writes/s — and they vanish if the primary dies at the wrong moment.

The sorted set is a cache, and here is what rebuilding it costs

The last row of that table is the transition to everything else. The sorted set is a cache of an ordering, not the record of the scores. The append-only log is the record, and the sorted set is rebuildable from it.

Rebuilding means replaying every score back in as a ZADD. Pipelined — many commands sent without waiting for each reply — Redis absorbs roughly 200,000 of those per second:

rebuild rate, pipelined ZADD                              =  200,000 /s
rebuild time   500,000,000 / 200,000                      =  2,500 s
in minutes     2,500 / 60                                 =  41.7

41.7 minutes is the recovery time objective, and it is a number to state before anyone asks. A recovery time objective (RTO) is the target for how long a service may take to come back after losing its state — a commitment, not a measurement.

It is also the argument for keeping a recent snapshot. Replaying a snapshot plus the tail of the log written since it was taken is minutes. Replaying all history from the beginning is not.

2. The hard part is rank, not top-k

Now the center of the chapter. Splitting the sorted set across machines preserves the top-k query exactly and destroys the rank query completely; there are exactly two things you can do about that, and the design picks one.

Split the sorted set across S = 64 shards by player_id. Now watch the two queries diverge.

Top-k survives the split

Top-k still works, exactly, and cheaply.

A member of the global top 10 is by definition among the top 10 of whatever shard holds it. The argument is one line: if ten players on its own shard already beat it, then at least ten players globally beat it, so it was never in the global top 10.

So each shard’s local top 10 is a sufficient statistic — a summary that carries everything the final answer needs, which means the shard’s remaining millions of rows can be ignored entirely.

merge input     10 x 64                                   =  640 entries

Sort 640 entries, take 10. Exact, one round of fan-out, microseconds of work. Top-k is a selection, and selection is decomposable.

Rank does not survive the split

Rank is not decomposable. Written out, a player’s rank is

rank(p) = 1 + |{q : score_q > score_p}|

— one plus the number of players in the whole population who score higher. That is a count over everybody.

A shard can tell you the player’s rank within that shard, and those numbers do not compose. Summing 64 local ranks counts the player’s own shard-mates correctly and everyone else not at all.

Rank is a global aggregate, and there is no local statistic that reconstructs it. Say that sentence out loud in the interview; it is the one the question is testing.

There are exactly two real answers, A and B below.

Answer A: exact rank by distributed count

Local ranks do not sum, but local counts do. Each shard can answer “how many of my players score above s” with ZCOUNT in O(log(n/S)), and every player above s is counted exactly once, by exactly one shard. Adding the 64 answers gives the exact global count.

This pattern — send the same question to every shard, then combine the answers — is called scatter-gather. Scatter to all 64, gather, add.

Each shard is 64x smaller than the whole board, so a lookup on one is cheaper. Applying the same p = 0.25 fit from Sorted set arithmetic what zadd and zrevrank actually cost to 7.8 million members instead of 500 million gives 42 node touches rather than 53:

players per shard    500,000,000 / 64                     =  7,812,500
node touches, the same p = 0.25 fit as section 2.1        =  42
per-shard CPU        42 x 100 ns                          =  4,200 ns

Throughput is not the problem, and the reason is worth noticing because it is the opposite of what sharding usually does. Each rank read touches every shard exactly once, so the per-shard request rate equals the global rank request rate no matter how many shards you add. Adding shards splits the data but not the query load.

Rates below are in QPS, queries per second, and 4,200 ns is 0.0000042 seconds:

per-shard rank QPS at peak                                =  8,682
per-shard core-seconds/s   8,682 x 0.0000042              =  0.0365

3.7% of a core. So capacity is fine.

The problem is tail latency: not the typical response time, but the slow end of the distribution — the p99 and beyond.

A scatter-gather finishes only when its slowest branch does. Its latency is therefore the maximum of S independent samples, and the chance that at least one of those samples is unlucky grows fast with S. That effect is called tail amplification.

The arithmetic is one line of probability. If any single call has a 1% chance of exceeding its own p99, then the chance that none of S calls does is 0.99^S, and the chance that at least one does is 1 - 0.99^S:

chance one call exceeds its own p99                       =  0.01
at S = 64:
    1 - 0.99^64                                           =  0.4744
at S = 512:
    1 - 0.99^512                                          =  0.9942

At 64 shards, 47% of rank queries pay some shard’s p99 latency; at 512 shards, 99.4% do — the fleet’s p99 has become the query’s median.

That is the scaling wall, and it is a wall of tail amplification, not of throughput.

Hedged requests buy back most of it: once the p95 has elapsed without an answer, send a duplicate of the request to a second replica and take whichever answer returns first. That costs about 5% extra load, because by construction only the slowest 5% of branches ever get duplicated. It works up to a few hundred shards. Past that, fan-out — the pattern of one request becoming S requests — is finished.

Answer B: bucketed approximate rank

Instead of counting players one at a time, keep a histogram of scores: cut the score line into B buckets and store only count[b], the number of players whose score falls in bucket b.

A player’s approximate rank is then the total count in all the buckets above theirs. You know which bucket they are in. You do not know where inside it. So the worst-case absolute rank error is exactly that bucket’s population.

Buckets can be cut two ways:

• Equi-width — each bucket spans the same range of scores.
• Equi-depth — each bucket holds the same number of players, which means the boundaries are the quantiles of the score distribution: the score values that cut the population into equal shares.

Equi-depth is the right choice here, for reasons derived further below. It makes every bucket hold N/B players, so the error is N/B everywhere rather than varying wildly across the board.

Deriving B from the accuracy target

Now work backwards from the accuracy requirement to the number of buckets.

The requirement, from Requirements: exact inside the top 10,000, and within 1% below that. Call r_min the worst rank at which the 1% relative promise has to hold. It is the head board’s boundary — 10,000 — and it must be that boundary and not some other number, or the accuracy you promise and the structure that delivers it are describing different products.

Worst-case error is N/B, one bucket’s population, and it has to be within 1% of r_min:

requirement    N / B  <=  0.01 x r_min,   r_min = 10,000
               N / B  <=  100
B  >=  500,000,000 / 100                                  =  5,000,000

Five million buckets, each holding 500,000,000 / 5,000,000 = 100 players, giving a worst-case error of 100 ranks.

Check that it is affordable. Each bucket costs 8 bytes of boundary plus 8 bytes of count, so 16 bytes:

histogram memory   5,000,000 x 16                         =  80,000,000     = 80 MB

80 MB, replicated, on one machine. Cheap.

The constraint that actually binds: a boundary is a score

Now check the thing that is easy to miss. Ties and score updates will pack a player’s points and a tiebreaking timestamp into a single number, and in the first layout it proposes, only 21 bits are left for the points themselves:

distinct scores available, 21-bit field ([section 2.3])
                   2^21 - 1                               =  2,097,151

A bucket boundary is a score, so B can never exceed the number of distinct scores.

Equi-depth boundaries are quantiles drawn from the observed distribution of actual scores. You cannot draw more distinct boundaries than there are distinct values to draw from. If only 2,097,151 score values exist, then at most 2,097,151 buckets exist, and the error can never fall below one bucket’s population at that count:

error floor    500,000,000 / 2,097,151                    =  238 ranks

238 ranks, whatever B you write down.

So B = 5,000,000 against a 21-bit score field is not merely expensive — it is arithmetically unreachable, and so is any larger B.

The fix is not in the histogram at all. It is in the score field. Take the rebased decomposition of Ties and score updates, which spends 28 bits on the score against a season-length clock: 2^28 = 268,435,456 distinct scores, which leaves B = 5,000,000 with 268,435,456 / 5,000,000 = 53x of room.

The accuracy requirement and the tie-break encoding are the same decision, and this is the join between them.

What a histogram query costs: the Fenwick tree

The histogram has to answer “how many players are in all the buckets above this one”, which is a prefix sum — a running total over a range of the array. Recomputing that by plain addition would be 5 million operations.

A Fenwick tree, also called a binary indexed tree, is the standard structure that avoids it. It stores partial sums at positions chosen by the binary representation of the index, so both a prefix sum and a single-bucket update cost O(log B) steps instead of O(B).

Cost the whole rank query, though, not one call inside it. The block below counts every memory reference a rank() makes: the binary search that finds the bucket, then the Fenwick walks. The last three lines do the same for update(), which runs on every score submission:

_bucket, binary search over the boundary array
                   ceil(log2(5,000,000))                  =  23
_prefix calls inside rank()                               =  4
Fenwick node touches, mean over the four calls            =  40.8
references per rank()     23 + 40.8                       =  63.8
query cost                63.8 x 100 ns                   =  6,380 ns
update(): 2 x (_bucket + _add), mean references           =  69.4
update touches/s          17,361 x 69.4                   =  1,204,853
update core-seconds/s     1,204,853 x 0.0000001           =  0.1205

6.4 microseconds per query, and 12% of a core to keep the tree up to date.

The figure usually quoted instead is 2.3 microseconds for the query and 4.0% of a core for maintenance. It comes from counting ceil(log2(B)) = 23 hops — the worst case of a single _prefix call — as though that were the cost of a whole query. Three things are missing from that count:

1. A rank() makes four _prefix calls, not one. It needs the population total, the prefix at the player’s bucket (twice, once for the count above and once for the bucket’s own population), and the prefix just below it.
2. Each _prefix touches popcount(i + 1) nodes — the number of 1 bits in the index, since the walk strips off one set bit per step. The mean of that over the whole array is about log2(B)/2, not log2(B).
3. _bucket’s binary search over a five-million-entry boundary array is not counted at all, though it is 23 references on its own.

The same accounting at a different size shows the gap is not a one-off. Size the histogram at B = 50,000,000 and it gives 76 references and 7.6 us against the 2.6 us the naive count predicts — 2.9x.

A 6.4-microsecond rank read against a 47%-tail scatter-gather, for 12% of a core of maintenance. That is the trade.

Note how little the correction matters to the decision: the careful count is 2.8x the naive one (63.8 / 23) and the design still clears the 50 ms budget by four orders of magnitude. That is the point of costing something properly even when you expect it to pass — you find out whether the margin is 4x or 4,000x.

Why the top of the board needs different treatment

Take a coarser histogram, B = 100,000. Its buckets each hold 500,000,000 / 100,000 = 5,000 players, so its absolute error is 5,000 ranks everywhere.

Now ask what that same fixed error means relative to the rank being reported:

relative error at rank 10           5,000 / 10            =  500
relative error at rank 100,000      5,000 / 100,000       =  0.05
relative error at rank 10,000,000   5,000 / 10,000,000    =  0.0005

Read those three lines as ratios: an error of 5,000 ranks is 500 times the rank itself at rank 10, five percent of it at rank 100,000, and five hundredths of a percent at rank 10 million.

The same absolute error is 500x wrong for the champion and invisible for the median player.

So the answer is not “exact” or “approximate”. It is exact at the head, bucketed in the tail, with the crossover placed where the bucket population stops mattering. At 100 bytes per element, the exact head board costs:

exact head board, top 10,000
memory        10,000 x 100                                =  1,000,000      = 1 MB

1 MB, maintained by the same writes, replicated to every machine that serves reads. Below rank 10,000 nobody has ever cared about their integer rank; they care about “top 2%”, which is what the histogram gives.

The equi-depth trap

Here is the promised argument for equi-depth over equi-width: the buckets must be equi-depth.

Score distributions in games are brutally skewed — a great many beginners clustered near zero, a thin tail of dedicated players far above. Split a 0-1,000,000 score range into 1,000 uniform-width buckets and the modal bucket, the one with the most players in it, holds a large share of the entire population. Take that share as 5%, which is unremarkable for a game score distribution:

modal bucket share of players (equi-width)                =  0.05
its population    0.05 x 500,000,000                      =  25,000,000
equi-depth population at B = 1,000
                  500,000,000 / 1,000                     =  500,000

25,000,000 against 500,000 — a factor of 50, from the same bucket count.

Since the error is one bucket’s population, equi-width buckets would make the error fifty times worse for exactly the players who sit in the crowded middle.

Getting equi-depth boundaries is a batch job: sort a sample of scores, read off the value at every 1/B of the way through, and republish that boundary array nightly. The shape of the distribution moves far more slowly than any individual score does, which is what makes a nightly refresh sufficient.

The implementation

The class below is the histogram in full. Five methods:

• _bucket finds which bucket a score falls in, by binary search over the boundary array.
• _add and _prefix are the Fenwick tree’s two walks — update one bucket, and sum a prefix.
• update moves a player from their old bucket to their new one: a decrement and an increment.
• rank returns both the approximate rank and the error bound that comes with it, which is the bucket’s own population.

Watch the two + 1s in the constructor.

from typing import Optional


class BucketedRank:
    """Approximate global rank from a Fenwick tree over equi-depth score
    buckets. Error is bounded by one bucket's population, N / B."""

    def __init__(self, boundaries: list[int]):
        self.boundaries = boundaries              # ascending, equi-depth
        # k boundaries cut the score line into k + 1 buckets, and a Fenwick
        # tree over m buckets needs m + 1 slots because it is 1-indexed.
        # `+ 1` here silently drops the top bucket -- the champions.
        self.n_buckets = len(boundaries) + 1
        self.tree = [0] * (self.n_buckets + 1)

    def _bucket(self, score: int) -> int:
        lo, hi = 0, len(self.boundaries)
        while lo < hi:                            # rightmost boundary <= score
            mid = (lo + hi) // 2
            if self.boundaries[mid] <= score:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def _add(self, i: int, delta: int) -> None:
        i += 1
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & (-i)

    def _prefix(self, i: int) -> int:
        i += 1
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)
        return total

    def update(self, old_score: Optional[int], new_score: int) -> None:
        if old_score is not None:
            self._add(self._bucket(old_score), -1)
        self._add(self._bucket(new_score), +1)

    def total(self) -> int:
        return self._prefix(self.n_buckets - 1)

    def rank(self, score: int) -> tuple[int, int]:
        """Returns (approximate rank, worst-case absolute error)."""
        b = self._bucket(score)
        above = self.total() - self._prefix(b)
        in_bucket = self._prefix(b) - (self._prefix(b - 1) if b else 0)
        return above + 1, in_bucket

The two + 1s in the constructor are the whole class, and they are the easiest thing here to get wrong.

Count carefully. k boundaries cut the score line into k + 1 buckets, because there is a bucket below the first boundary and one above the last. So _bucket returns an index anywhere in [0, len(boundaries)], which is len(boundaries) + 1 distinct values. That is the first + 1.

On top of that, a Fenwick tree over m buckets needs an array of m + 1 slots, because the tree is 1-indexed and slot 0 is unused. That is the second.

Miss the outer one — size the array at len(boundaries) + 1 rather than n_buckets + 1 — and two things go wrong at once. _add on the top bucket finds i == len(tree), exits its loop immediately, and drops the increment on the floor. And rank walks off the end of the array.

The bucket that disappears is the highest-scoring one, so the counts that go missing belong to the players most likely to be looking.

The block below is the test for all of that. It checks the sizing, then every rank the class can be asked for including the top bucket, then that the error bound it reports is honest against a brute-force count, then the sizing of B from Requirements’s accuracy requirement, and finally the reference count behind the 6.4 us figure.

# --- the top bucket must exist, and rank() must not raise --------------
br = BucketedRank([100, 200, 300])
assert br.n_buckets == 4                 # 3 boundaries, 4 buckets
assert len(br.tree) == 5

scores = [50, 150, 150, 250, 350, 350, 350]
for s in scores:
    br.update(None, s)
assert [br._bucket(s) for s in (50, 150, 250, 350)] == [0, 1, 2, 3]
assert br.total() == len(scores) == 7    # an undersized tree reports 4 here

# rank() at every bucket, including the top one an undersized tree drops
assert br.rank(350) == (1, 3)            # nobody above; 3 share the bucket
assert br.rank(250) == (4, 1)            # the three 350s are above
assert br.rank(150) == (5, 2)
assert br.rank(50) == (7, 1)

# a score update is a decrement plus an increment, and it stays balanced
br.update(50, 350)
assert br.total() == 7
assert br.rank(350) == (1, 4)            # the mover is now in the top bucket
assert br.rank(50) == (8, 0)             # ...and their old bucket is empty

# --- error is bounded by one bucket's population ----------------------
import random

rng = random.Random(4)
population = sorted(rng.randrange(1_000_000) for _ in range(20_000))
n_buckets = 200
step = len(population) // n_buckets
bounds = sorted({population[i] for i in range(step, len(population), step)})
hist = BucketedRank(bounds)
for s in population:
    hist.update(None, s)
assert hist.total() == len(population)

worst = 0
for s in population[::37]:
    approx, err = hist.rank(s)
    exact = sum(1 for q in population if q > s) + 1
    worst = max(worst, abs(approx - exact))
    assert abs(approx - exact) <= err     # the error bound is honest
assert 0 < worst <= len(population) / n_buckets * 2

# --- and the sizing of B, from section 1's requirement ----------------
import math

N, R_MIN, BITS_21, BITS_28 = 500_000_000, 10_000, 2 ** 21 - 1, 2 ** 28
B = math.ceil(N / (0.01 * R_MIN))
assert B == 5_000_000                     # not 50,000,000: r_min is 10,000
assert B * 16 == 80_000_000               # 80 MB, not 800 MB
assert N // B == 100                      # 100 ranks of error, not 10

# a bucket boundary IS a score, so B is capped by the distinct score count
assert B > BITS_21, "a 21-bit score cannot support 5,000,000 buckets"
assert N // BITS_21 == 238, "the real error floor under a 21-bit score"
assert BITS_28 > 50 * B, "section 2.3's rebased 28-bit field has room"

# --- what a rank() query actually costs -------------------------------
def prefix_touches(i):
    """_prefix(i) walks i+1 down by its low set bit: popcount(i+1) nodes."""
    return bin(i + 1).count("1")


probe = BucketedRank(list(range(1, 4_096)))       # 4,096 buckets
seen = []
probe._prefix = lambda i, f=probe._prefix: (seen.append(i), f(i))[1]
probe.update(None, 2_000)
seen.clear()
probe.rank(2_000)
assert len(seen) == 4, "rank() makes four _prefix calls, not one"
assert sum(prefix_touches(i) for i in seen) == sum(
    bin(i + 1).count("1") for i in seen)


def rank_references(b, n_buckets):
    """Binary search in _bucket, plus the four _prefix walks."""
    calls = [n_buckets - 1, b, b] + ([b - 1] if b else [])
    return (math.ceil(math.log2(n_buckets))
            + sum(prefix_touches(i) for i in calls))


rng = random.Random(3)
sample = [rng.randrange(B) for _ in range(200_000)]
mean_refs = sum(rank_references(b, B) for b in sample) / len(sample)
assert 63 < mean_refs < 65, mean_refs                  # the chapter says 63.8
assert mean_refs > 2.5 * math.ceil(math.log2(B))       # ...not 23 hops
assert 6.0 < mean_refs / 10 < 6.8                      # microseconds

Pick B by default, fall back to A on request. The histogram serves the 50 ms budget with orders of magnitude to spare. The exact=True scatter-gather exists for the profile page and for disputes, where a slow answer is acceptable and a wrong one is not.

3. Ties and score updates

What happens when two players have the same score? The fix is not a detail: the way you encode the tiebreak decides how accurate The hard part is rank not top k’s histogram is allowed to be.

The default tiebreak is indefensible

Two players with 50,000 points. Who is ranked higher?

Redis orders equal scores lexicographically by member — comparing the member strings character by character. So your leaderboard’s tiebreak is currently “whoever has the alphabetically smaller player id”. Deterministic, but arbitrary, and it will be noticed.

The convention players expect is first to reach the score ranks higher.

Packing the tiebreak into the score

Fix it inside the score rather than around it.

A Redis sorted-set score is an IEEE-754 double, the 64-bit floating-point format every language calls a double. A double has 53 bits of significand, which means it represents every integer up to 2^53 exactly and starts silently rounding above that.

Those 53 bits are a budget. The trick is to spend them on two fields at once — points in the high bits, a timestamp in the low bits — so that ordinary numeric comparison sorts first by points and then by time.

Here is one way to split the budget:

score field       21 bits    max  2^21 - 1                =  2,097,151 points
timestamp field   32 bits    inverted seconds since epoch
                  --
                  53 bits

And here is the arithmetic that packs them into one number, plus the check that the largest possible result still fits:

composite  =  score x 4,294,967,296  +  (4,294,967,295 - t_seconds)
max composite, score at max and t = 0
           2,097,151 x 4,294,967,296          =  9,007,194,959,773,696
         +             4,294,967,295          =  9,007,199,254,740,991
2^53                                          =  9,007,199,254,740,992

Three things to notice in that block.

Multiplying the points by 4,294,967,296, which is 2^32, shifts them above the 32 timestamp bits, so the two fields never interfere.

The largest composite the layout can produce is 2^53 - 1, exactly one below the double’s exact-integer ceiling. The 21/32 split uses the budget precisely, so no rounding ever occurs and ordering is exact.

Storing 4,294,967,295 - t_seconds rather than t_seconds inverts the clock: an earlier submission produces a larger composite, so equal scores sort by who got there first.

Rebasing the clock to buy score bits

If 2.1M points is too small a ceiling, rebase the clock. Measure seconds from the start of the season instead of from 1970, so far fewer timestamp bits are needed and the points field can grow into what is left:

season length   2^25 seconds  33,554,432 / 86,400         =  388 days
score bits      53 - 25                                   =  28 bits
                2^28                                      =  268,435,456 points

268M points and a 388-day season, from the same 53 bits. Which decomposition you pick is a product question; that you must pick one is an engineering fact, and stating the 2^53 constraint is what shows you know why.

This is not only a ceiling question, and that is the part to volunteer. The width of the score field is also the number of distinct scores, and The hard part is rank not top k’s histogram cannot have more buckets than there are distinct scores to draw boundaries from.

• 21 bits gives 2,097,151 distinct scores, which floors the approximate rank error at 238 whatever B you budget for.
• 28 bits gives 268,435,456, and the B = 5,000,000 the accuracy requirement asks for fits with 53x to spare.

So the rebased layout is not the exotic option, it is the one the accuracy requirement forces. Noticing that the tie-break encoding and the rank accuracy are the same decision is worth more than either number on its own.

The timestamp needs one authority

The timestamp must come from a single source, not from whichever machine happened to run the match.

Two game servers whose clocks differ by 200 ms will order simultaneous submissions by clock error rather than by arrival. Worse, a clock that steps backwards — which happens whenever a machine’s time is corrected — reorders history that has already been published.

Use the score service’s own receive time, or a monotonic sequence, meaning one guaranteed never to go backwards, from a Snowflake-style identifier generator (Deep dive 2 clock skew leap seconds and the rewind covers the backwards-clock case and its fixes).

Which write command, and why it matters

Update semantics matter as much as ordering. An operation is idempotent when doing it twice leaves the same state as doing it once — the property that makes a retry safe when you do not know whether the first attempt landed.

Two board types, two commands, and only one of them is safe to retry:

ZADD ... GT writes the new score only if it is greater than the stored one, so replaying it changes nothing. ZINCRBY adds a delta, so replaying it adds the delta again.

ZADD GT is the design you want, precisely because at-least-once delivery is what a network gives you. A message may arrive more than once; the only thing you can choose is whether that matters.

When the product demands a cumulative board, you have re-created the counting problem from Exactly once honestly. Two fixes, both from that chapter: deduplicate on match_id before the increment, or make the write an absolute set rather than an add. Naming that connection out loud is worth doing in an interview.

4. Time-windowed boards, and the storage multiplier

Every real leaderboard product also wants daily, weekly and monthly boards, and a 16.4x storage multiplier hides in the obvious implementation of them.

Sizing one board of each kind

Daily, weekly, monthly, all-time. Each is a separate sorted set over a separate population: a daily board only holds players who played that day. So each is sized from the DAU rather than from the 500 M registered total.

The multipliers 3.5x and 8x are the assumption that the distinct players seen over a week are 3.5 times a single day’s DAU, and over a month, 8 times. Not 7x and 30x, because the same people come back. Everything is then multiplied by the 100 bytes per element from Data model a sorted set and what it costs per element:

all-time   500,000,000 x 100                              =  50,000,000,000  = 50 GB
daily      50,000,000 x 100                               =   5,000,000,000  = 5 GB
weekly     distinct players over 7 days, 3.5 x DAU
           50,000,000 x 3.5                               =  175,000,000
           175,000,000 x 100                              =  17,500,000,000  = 17.5 GB
monthly    8 x DAU   50,000,000 x 8                       =  400,000,000
           400,000,000 x 100                              =  40,000,000,000  = 40 GB

The 16.4x multiplier hiding in the obvious implementation

To materialize something is to store it as real, precomputed data rather than deriving it when asked.

Materialize the history the obvious way — keep 30 dailies, 8 weeklies and 12 monthlies all live in memory, alongside the all-time board — and multiply each board’s size by how many of them you keep:

dailies    5 x 30                                         =  150 GB
weeklies   17.5 x 8                                       =  140 GB
monthlies  40 x 12                                        =  480 GB
all-time                                                  =   50 GB
total      150 + 140 + 480 + 50                           =  820 GB
multiplier 820 / 50                                       =  16.4

16.4x, and 620 GB of it is history almost nobody reads. That 620 GB is the weeklies plus the monthlies (140 + 480), of which only the current week and the current month get any traffic at all.

The fix is to notice that a weekly board is derivable from its dailies, so only the current window needs to be live:

30 dailies + current week + current month + all-time
           150 + 17.5 + 40 + 50                           =  257.5 GB
reduction  820 / 257.5                                    =  3.18

Costing the merge job properly

Derive weekly boards from their dailies with ZUNIONSTORE, the Redis command that merges several sorted sets into a new one. Cost it from its documented complexity, not from the input size alone.

ZUNIONSTORE is O(N) + O(M log M), where:

• N is the total number of elements across all the inputs — it has to touch each one;
• M is the number of elements in the result — it has to sort the destination set it just built.

Both terms have to be counted, and the second one dominates. Assume a microsecond per operation:

the O(N) term, element merges
                 7 x 50,000,000                           =  350,000,000
result size M, distinct players over 7 days
                 3.5 x 50,000,000                         =  175,000,000
the O(M log M) term
                 log2(175,000,000)                        =  27.4
                 175,000,000 x 27.4                       =  4,795,000,000
total operations 350,000,000 + 4,795,000,000              =  5,145,000,000
at 1 us each                                              =  5,145 s
in minutes       5,145 / 60                               =  85.8
against the O(N)-only estimate
                 5,145 / 350                              =  14.7

86 minutes, and the sort term is 4,795,000,000 / 5,145,000,000 = 93% of it.

Counting only the merge term gives 350 seconds, which is 14.7x optimistic — the difference between a job that finishes inside an overnight window and one that is still running when the players come back.

The design conclusion survives either way, because this is a scheduled job and never a request. What the real figure changes is the scheduling. You cannot run seven of these one after another in a maintenance window, so run them per region, and prefer the incremental form: ZUNIONSTORE week week today merges a single day into a standing weekly board, which makes both N and M about one board’s worth instead of seven.

AGGREGATE MAX, never the default SUM

The aggregate function is not optional. When ZUNIONSTORE finds the same member in several inputs it has to combine their scores, and it defaults to AGGREGATE SUM, adding them.

That is meaningless here, and it fails in two separate ways.

First, the scores being merged are the composite score x 2^32 + inverted_time values of Ties and score updates. Adding two composites carries their timestamps up into the points field and invents a score nobody achieved.

Second, it blows the 2^53 exactness budget. Seven maximal composites sum to about 7 x 9,007,199,254,740,991, which is 6.3e16 — well past the range where a double represents integers exactly. The result silently rounds on top of being wrong.

The correct call is AGGREGATE MAX, which selects the player’s best single-day composite and keeps both the score and its tiebreak intact.

The block below demonstrates both failures on a two-player example: Alice scored 1,000 once, Bob scored 600 on each of two days. Under MAX Alice wins, which is right. Under SUM Bob wins with 1,201 points — a score nobody ever had, and note the stray +1 that the two timestamps carried up out of the low 32 bits.

# A composite score packs points and an inverted timestamp; see section 2.3.
def composite(points, t_seconds):
    return points * 4_294_967_296 + (4_294_967_295 - t_seconds)


def points_of(c):
    return c // 4_294_967_296


# One player scored 1,000 once. Another scored 600 on each of two days.
alice = [composite(1_000, 10)]
bob = [composite(600, 10), composite(600, 20)]

assert points_of(max(alice)) == 1_000 and points_of(max(bob)) == 600
assert max(alice) > max(bob)                       # AGGREGATE MAX: Alice wins

# AGGREGATE SUM, the default, ranks Bob above Alice on a score he never had.
assert sum(bob) > sum(alice)
# 1,201, not 1,200: the two inverted timestamps carry out of the low
# 32 bits and straight into the score field. SUM corrupts both halves.
assert points_of(sum(bob)) == 1_201                # a score nobody ever had

# ...and SUM leaves the range where a double is an exact integer.
MAX_COMPOSITE = composite(2_097_151, 0)
assert MAX_COMPOSITE < 2 ** 53                     # one composite is exact
assert 7 * MAX_COMPOSITE > 2 ** 53                 # seven summed are not
assert float(7 * MAX_COMPOSITE) != 7 * MAX_COMPOSITE

# The cost model that produced 86 minutes rather than 350 seconds.
import math

N_TERM = 7 * 50_000_000
M = int(3.5 * 50_000_000)
M_TERM = M * math.log2(M)
assert round(math.log2(M), 1) == 27.4
assert round((N_TERM + M_TERM) / 60 / 1_000_000) == 86      # minutes
assert round((N_TERM + M_TERM) / N_TERM, 1) == 14.7

86 minutes is fine at 03:00 and fatal in a request.

So the policy, in four lines:

• dailies are the primitive everything else is built from;
• weeklies and monthlies are rolled nightly and incrementally;
• closed windows are snapshotted to disk and dropped from memory;
• the all-time board is the only one that never expires.

Set a time-to-live on each daily key equal to the retention period and let Redis delete them on schedule, rather than writing a cleanup job that can fall behind.

The daily board’s boundary is a timezone

One correctness note that catches people. A player in Auckland and a player in Los Angeles do not share a Tuesday, so “today’s board” is ambiguous until you say whose today.

Two acceptable answers:

• the board is explicitly on Coordinated Universal Time (UTC), and the interface says so;
• or the board is per-region, and a regional board is a different key.

The third option — per-player timezone — makes the board non-comparable between two players, which means it is not a leaderboard. Pick one of the first two.

5. Cheating: server-authoritative scoring, and the rate limit

Last, integrity: who computes a score, why signing it on the client does not help, and what the layered defence costs. Server-authoritative means the server, not the player’s device, is the authority on what happened in a match.

The score must be computed by a server you control, from match events. This is a hard requirement, not a hardening measure.

A score computed on the player’s device is an integer supplied by an adversary who owns the debugger, the memory, and the binary.

Match events are the raw record of play — inputs, timings, outcomes — which the server can replay under the game’s own rules to derive a score for itself.

The counter-argument to pre-empt

A candidate always offers this one: “we sign the score with a key in the client.”

The key is in the binary. Extracting it is an afternoon’s work. A signed score is still an attacker-supplied integer, now carrying a valid signature and an audit trail that says it is genuine — strictly worse than an unsigned one, because it defeats your own anomaly detection.

The same goes for obfuscation, checksums, and anti-tamper. They raise the cost of the first exploit and zero the cost of every copy of it.

What actually works, in layers

Five layers, in order of how much they buy you:

1. The client submits events, the server simulates. Inputs, timestamps, and outcomes; the server replays them under the game’s rules and derives the score. This is expensive and it is the only thing that is actually a defense.
2. Plausibility bounds. If the game’s theoretical maximum is 1,000 points/minute, a submission implying more than that since the player’s last one is rejected outright, not flagged. Cheap, and it catches the naive 90%.
3. Rate-limit submissions with a token bucket: a counter that refills at a fixed rate up to a maximum capacity, spending one token per request and rejecting requests when it is empty, so the long-run rate is capped while a short burst is still allowed (Token bucket has the mechanics). Derive the parameters from legitimate behaviour rather than from capacity:

legitimate submissions/day                                =  10
seconds between them   86,400 / 10                        =  8,640
bucket: capacity 5, refill 1 per 60 s
worst case/day         86,400 / 60                        =  1,440
over legitimate rate   1,440 / 10                         =  144

Read that block as a worst case for one stolen account: a bucket refilling once every 60 seconds allows at most 86,400 / 60 = 1,440 submissions in a day, against the 10 an honest player makes.

A compromised account gets 144x the honest rate and no more.

Note what the limit is not for. Aggregate capacity is a non-issue at 17,361 peak writes/s. The bucket exists to bound a single account’s blast radius. Its capacity of 5 exists so that a player finishing five quick matches back to back is not throttled.

4. Anomaly quarantine, not rejection. Flag scores above the historical p99.99 — the one-in-ten-thousand score — for the player’s cohort, the comparable group they are judged against, such as players at the same level. By definition that flags one submission in 10,000, and there are 500,000,000 submissions a day:

flags/day   500,000,000 submissions x 0.0001              =  50,000

50,000 flags/day is far past human review, so the flag cannot mean “reject” or “escalate”.

It means quarantine: the score is accepted, recorded, and withheld from the public board pending an automated replay check. Rejecting outright punishes the genuinely exceptional player, which is a worse product failure than briefly delaying a cheater.

5. Idempotency as an integrity control. Deduplicating on match_id stops replay attacks, in which an attacker resends a genuine past submission to be credited for it again, and the ZADD GT of Ties and score updates makes a replayed submission a no-op even if the deduplication misses it. Two independent mechanisms for the same attack is the right amount here, because a replayed high score is indistinguishable from a legitimate one at the storage layer.

3. Bottlenecks and scaling

Scaling here is a growth ladder: at each population, something different runs out first. The most useful row is the first, because it says not to build most of this chapter until you have to.

The hot-key row deserves the explicit connection.

A hot key is a single item that receives a disproportionate share of all traffic. What consistent hashing does not fix establishes that it is not a partitioning problem at all: one key has one hash and therefore one owner, no matter how many virtual nodes — the extra hash-ring positions each machine is given to smooth out its share — you configure.

Sharding cannot help. Only caching can.

The top-10 board is the textbook instance, and it is also the easiest one. The top 10 of a 500-million-player board barely changes from second to second, so a 1-second cache is nearly free in staleness and enormous in load relief.

4. Failure modes

What breaks, what an operator actually observes when it breaks, and the mitigation — each linked to wherever it was derived.

5. Alternatives rejected

Seven designs a reasonable person proposes instead, and the number or the structural fact that kills each one.

6. Interviewer pushback

Seven questions an interviewer asks when they want to know whether you understand your own design, each answered the way you would say it out loud.

“Just use ZADD and ZREVRANK. Why is this a system design question?”

Because ZREVRANK is O(log n) on one machine and undefined across sixty-four. Top-10 shards perfectly — a global top-10 member is in its own shard’s top 10, so I merge 640 entries. Rank does not shard, because it is a count over the whole population and no per-shard statistic reconstructs it. Everything past the first five minutes of this problem is that distinction.

“So how do you answer ‘my rank’ at 500 million players?”

Two ways, and I would ship both. Exactly, by scattering a ZCOUNT to all 64 shards and summing — counts compose even though ranks do not, and it costs 3.7% of a core per shard. But the query finishes when the slowest branch does, so at 64 shards 47% of reads pay some shard’s p99 and at 512 shards 99.4% do. So the default path is a Fenwick tree over 5 million equi-depth score buckets: 80 MB, one hop, 6.4 microseconds, and a worst-case error of one bucket’s population, which is 100 ranks.

“Your approximate rank is off by 100. Tell me that is acceptable at rank 3.”

It is not, which is why the head is exact. The same absolute error is 500x wrong at rank 10 and 0.05% wrong at rank 10 million — so accuracy has to be specified as a function of rank, not as a single number. I keep the top 10,000 as an exact sorted set; it is 1 MB and replicates everywhere. Below that, nobody asks for an integer rank, they ask for a percentile, and the histogram answers that with three significant figures.

“How many buckets, and where did that come from?”

From the accuracy requirement, backwards, and r_min has to be the head board’s boundary — otherwise the accuracy I promise and the structure I built to deliver it are describing different products. Worst-case rank error in a bucketed scheme is the bucket’s population, N/B. The head is exact to rank 10,000 and I want 1% below that, so N/B <= 0.01 x 10,000 = 100, so B >= 5,000,000. At 16 bytes per bucket that is 80 MB, which fits easily. The check people skip is that a bucket boundary is a score: B can never exceed the number of distinct score values, and a 21-bit score field only has 2,097,151 of them, which floors the error at 500,000,000 / 2,097,151 = 238 ranks no matter what B I write down. So the accuracy requirement is what forces the rebased 28-bit score field, not the other way round. And the buckets must be equi-depth — equi-width buckets on a skewed score distribution put 25 million players in the modal bucket instead of 500,000.

“A player and a rival both hit 50,000. Who is first?”

By default, whoever has the alphabetically smaller player id, because Redis breaks score ties lexicographically by member — which is deterministic and indefensible. I pack the tiebreak into the score: 21 bits of points and 32 bits of inverted timestamp, which is 53 bits, exactly the integer precision of the double that Redis uses for a score. The largest composite the layout can produce is 9,007,199,254,740,991, which is 2^53 - 1, so nothing ever rounds. Earlier submission wins ties, and if 2.1 million points is too low a ceiling I rebase the clock to the season start and get 28 bits of score instead.

“Weekly and monthly boards too. What does that cost?”

820 GB if I materialize 30 dailies, 8 weeklies and 12 monthlies — a 16.4x multiplier over the 50 GB all-time board, and most of it is history nobody reads. So dailies are the only primitive I keep hot; weeklies and monthlies are ZUNIONSTORE ... AGGREGATE MAX rolls at 03:00. And I would cost that from the real complexity, O(N) + O(M log M): 350 million element merges plus a sort of the 175-million-element result, which is 5.1 billion operations and 86 minutes, not the 350 seconds you get from the merge term alone. Still a job and never a request, but 86 minutes is a scheduling constraint, so I roll incrementally — yesterday into a standing weekly — rather than seven-way every night. MAX rather than the default SUM, because the scores are composites and summing them adds timestamps into the score field. Keeping only the current week and month live brings storage to 257.5 GB.

“Someone is submitting a billion-point score. What stops them?”

Nothing at the storage layer, which is the point: the client cannot be allowed to compute a score at all. The server replays match events under the game rules. Then plausibility bounds reject anything implying more than the theoretical maximum rate, and a token bucket at capacity 5 refilling once a minute caps a compromised account at 1,440 submissions a day against a legitimate 10 — 144x, and bounded. Statistical anomalies get quarantined rather than rejected, because 50,000 flags a day is well past human review and rejecting outright punishes the genuinely exceptional player.

The assumption ledger

Every design is a set of assumptions with a diagram attached, and the diagram is only correct relative to them. Collected in one place, everything the design has leaned on can be stated in twenty seconds — along with what replaces the design when each assumption fails.

Sort each assumption into one of three bins:

• State it — you are free to pick, and being wrong costs a re-derivation and nothing more.
• Ask it — the answer moves a policy or a threshold, and it is worth an interviewer’s time.
• Load-bearing — if it is wrong the design is not suboptimal, it is invalid. A box appears or disappears, rather than the count inside a box changing.

The one-line test, from ch 03: move the assumption an order of magnitude in each direction and ask whether the set of boxes changes, or only the number of machines inside them.

If you take one row from this table, take the first.

The chapter’s central structural choice — an in-memory sorted set as the live ordering — is not driven by the 50 ms latency budget. Several other designs meet that too. It is driven by the assumption that a player’s score changes constantly and the new position must be visible within a second.

That single assumption rules out every cheaper option at once:

• it kills the nightly precomputed rank column, which is only 145 seconds of compute and would otherwise win outright;
• it kills the streaming quantile sketch, because a score change is a delete followed by an insert and sketches cannot delete;
• and it is what makes 50 GB of RAM a reasonable thing to buy.

Relax it to “rank may be a day old” and the sorted set is unnecessary.

The table’s last column is the useful one in an interview: it says what you would build instead if the assumption turned out to be false.

Cheat sheet

Everything above, compressed to the lines worth having in memory when the whiteboard is in front of you.