Skip to content

Design a real-time gaming leaderboard

TL;DR

  • A leaderboard is a ranking problem, not a storage problem: 500M score submissions a day fit in ~50 GB of sorted sets, and the hard part is answering "what is my rank" in O(log n) instead of O(n).
  • The cruxes: (1) the sorted set and the complexity of each operation, (2) sharding beyond one node — by member with scatter-gather, or by score range, (3) real-time updates without pushing per-user ranks, (4) periodic boards as separate keys with a TTL, plus tie-breaking, validation and rebuild.
  • The global top 100 is one 5 KB object cached for a second; the per-player rank is the query that actually costs money.

Problem statement and clarifying questions

"Design a leaderboard for a game: the global top 100, plus each player's own rank and the players around them." The interesting question is not where scores live — it is which read you must serve, because the top 100 is trivially cacheable and "my rank" is not.

Question Assumption taken
Scale? 50M DAU, 10 matches per player per day, 500M registered accounts.
Which reads? Global top 100, a player's own rank and score, and the 5 players either side of them.
Which boards? All-time, monthly, weekly and daily, each also per region.
Score semantics? A player's best score in the period, not a running sum.
How fresh must the board be? Sub-second for the player's own rank; one second of staleness on the global top is fine.
Are ties possible? Constantly — round numbers cluster. Break them deterministically by player id.
Can clients submit scores? No. The game server submits, with the match id as an idempotency key.
Is losing the board acceptable? Losing the board yes, losing the scores no: the score log is the system of record.

Requirements

Functional

  • Submit a score for a match; keep the best score per player per period.
  • Return the top N (up to 1,000) for any board and period, with rank, player and score.
  • Return one player's rank, score and percentile, plus the window of players around them.
  • Paginate deep into the board without offset arithmetic.
  • Expire closed periods automatically and rebuild any board from the score log.

Non-functional

  • Scale: ~15k submissions/s and ~30k board reads/s at peak; 500M members on the all-time board.
  • Latency: p99 under 100 ms for rank and top-N; a score is reflected within 1 s.
  • Consistency: read-your-writes for the submitting player; a second of staleness for everyone else.
  • Durability: a score is durable before the API acknowledges. The sorted sets are a derived, rebuildable index.
  • Availability: 99.9% for reads; serve the last cached top-N during a shard failure rather than an error.
  • Fairness: an impossible score is rejected at write time, not curated afterwards.

Out of scope

Matchmaking and skill rating (Elo/TrueSkill), the anti-cheat model itself, rewards, social features, and the game servers.

Estimation

From the latency and estimation tables: a day is ~10^5 s, peak is 3x average, a UUID is 16 B, a long is 8 B, and a single-threaded Redis instance sustains ~100k ops/s.

Quantity Arithmetic Result
Write QPS 50M DAU x 10 matches / 10^5 ~5k/s average, ~15k/s peak
Read QPS 50M DAU x 20 board views / 10^5 ~10k/s average, ~30k/s peak
Entry size 16 B member + 8 B score = 24 B payload, ~4x for skip-list pointers and the hash entry ~100 B per member
All-time board 500M members x 100 B ~50 GB — one large node holds it
All boards 50 GB + 3 shorter periods holding only the 50M who played (~5 GB each) ~65 GB, ~130 GB with one replica
Redis ops 15k writes x 4 period keys + 30k reads ~90k ops/s against ~100k/s per instance — 8 shards for headroom
Score log 500M/day x 50 B (member, score, match id, timestamp) 25 GB/day, ~9 TB/year, ~27 TB at replication factor 3
Top-N bandwidth 30k/s x 100 rows x ~50 B 150 MB/s = 1.2 Gbps before caching
Top-N cache One 5 KB object per board and period, 1 s TTL ~20 KB of cache absorbs 30k reads/s down to ~1/s

Say it out loud: memory is not the constraint, operations are. 500M players cost 50 GB, which fits on one machine, but 90k ops/s against a single-threaded instance leaves no headroom for a launch spike, so you shard for throughput and blast radius rather than space. And the top-N read collapses to nothing under a one-second cache, because everybody asks for the same 100 rows.

API design

Endpoint Request Response Notes
POST /v1/boards/{board}/scores {player_id, score, match_id}, header Idempotency-Key: match_id 202 {stored_score, best} The game server calls it, never the client. A replay of the same match id is a no-op.
GET /v1/boards/{board}/top?period=daily&limit=100 — 200 {entries: [{rank, player_id, score}], as_of} Cached 1 s at the edge; limit capped at 1,000. as_of shows staleness honestly.
GET /v1/boards/{board}/players/{id}?period=daily — 200 {rank, score, percentile} Per-player, so it is not shareable cache. This is the expensive read.
GET /v1/boards/{board}/around/{id}?radius=5 — 200 {entries} The relative board: 11 rows centred on the player, which is what mid-table players look at.
GET /v1/boards/{board}/page?cursor=...&limit=50 — 200 {entries, next_cursor} The cursor encodes (score, player_id), never an offset: ranks shift under you between pages.

Data model

Scores are events; boards are derived indexes keyed by period.

erDiagram
    GAME ||--o{ BOARD : defines
    PERIOD ||--o{ BOARD : buckets
    BOARD ||--o{ BOARD_ENTRY : ranks
    PLAYER ||--o{ BOARD_ENTRY : appears_in
    PLAYER ||--o{ SCORE_EVENT : submits
    MATCH ||--o{ SCORE_EVENT : produces
    SHARD ||--o{ BOARD_ENTRY : stores
    GAME {
        string game_id PK
        string name
        decimal max_score
    }
    PERIOD {
        string name PK
        int bucket_s
        int ttl_s
    }
    BOARD {
        string board_key PK "game:region:period:bucket"
        string game_id
        timestamp opens_at
        timestamp expires_at
    }
    BOARD_ENTRY {
        string board_key PK
        bigint player_id PK
        decimal score
        timestamp updated_at
    }
    PLAYER {
        bigint player_id PK
        string handle
        string region
    }
    SCORE_EVENT {
        uuid event_id PK
        bigint player_id
        uuid match_id "idempotency key"
        decimal score
        timestamp created_at
    }
    MATCH {
        uuid match_id PK
        string game_id
        timestamp finished_at
    }
    SHARD {
        int shard_id PK
        string address
        int member_count
    }
  • BOARD_ENTRY lives in Redis sorted sets: key game:region:period:bucket, member player_id, score score. Partition by crc32(player_id) mod N; the sort key is the score itself.
  • SCORE_EVENT is the system of record: an append-only log partitioned by player_id, with match_id unique for idempotency.
  • PLAYER is a normal profile store, read through a cache to hydrate handles and avatars after ranking.
  • No relational index serves this well: ORDER BY score DESC LIMIT 100 OFFSET 5000 scans 5,100 rows per query at 30k QPS, and a covering index still counts rows to produce a rank.

High-level design

v1: a score service that validates and durably logs, writers that update the sorted sets, and a board service that reads them.

flowchart LR
    subgraph clients["Clients"]
        c_game["Game clients and servers"]
    end
    subgraph edge["Edge"]
        e_cdn["CDN: top-N JSON, 1 s TTL"]
        e_gw["API gateway<br/>auth, rate limit"]
    end
    subgraph services["Services"]
        s_score["Score service<br/>validation, idempotency"]
        s_board["Board service<br/>top, rank, around"]
    end
    subgraph async["Async"]
        a_kafka[["Kafka: score-accepted"]]
        a_writer["Board writers"]
        a_rebuild["Rebuild and rollup job"]
    end
    subgraph data["Data"]
        d_redis[("Redis sorted sets<br/>one key per board and period")]
        d_log[("Score event log")]
        d_prof[("Player profiles")]
    end
    c_game --> e_cdn
    c_game --> e_gw
    e_gw --> s_score --> d_log
    s_score --> a_kafka --> a_writer --> d_redis
    e_gw --> s_board --> d_redis
    s_board --> d_prof
    a_rebuild --> d_log
    a_rebuild --> d_redis

Write path: validate, log durably, acknowledge, then update every period's board.

sequenceDiagram
    autonumber
    actor P as Player client
    participant GS as Game server
    participant SC as Score service
    participant LOG as Score log
    participant K as Kafka
    participant BW as Board writer
    participant R as Redis shard
    P->>GS: match finished
    GS->>SC: POST score with match_id as idempotency key
    SC->>SC: validate range, rate and server-authoritative result
    SC->>LOG: append score event, the source of truth
    LOG-->>SC: ok
    SC-)K: publish score-accepted
    SC-->>GS: 202 accepted
    K-->>BW: consume, partitioned by player_id
    loop for each period: alltime, monthly, weekly, daily
        BW->>R: ZADD board key, greater-than flag only
    end
    opt the top 100 changed
        BW-)K: publish leaderboard-changed
    end

Read path: the shared top-N is a cache hit; the personal rank is a scatter-gather.

sequenceDiagram
    autonumber
    actor P as Player client
    participant CDN as CDN
    participant BS as Board service
    participant R1 as Redis shard 1
    participant RN as Redis shard N
    participant PR as Profile cache
    P->>CDN: GET top with limit 100
    alt cached within 1 s
        CDN-->>P: 200 cached board
    else miss
        CDN->>BS: fetch
        par scatter
            BS->>R1: local top 100
        and
            BS->>RN: local top 100
        end
        BS->>BS: merge N sorted lists, take 100
        BS->>PR: hydrate handles and avatars
        BS-->>CDN: entries plus as_of
        CDN-->>P: 200
    end
    P->>BS: GET my rank
    BS->>R1: score, then count above that score on every shard
    BS-->>P: rank, score, percentile

The shape to notice: writes are cheap and single-shard, the shared read caches to almost nothing, and the only genuinely distributed operation is turning a score into a global rank.

Deep dive: the sorted set and why rank is O(log n)

The probing question is "how do you produce a rank without counting rows?"

Structure Insert / update Rank of a member Page at offset k
Relational table with an index on score O(log n) O(n) — count the rows above O(k + m) scan
Sorted array O(n) shift O(log n) binary search O(m)
Balanced BST with subtree sizes O(log n) O(log n) O(log n + m)
Skip list with span counters plus a hash map O(log n) expected O(log n) O(log n + m)

The last two match in complexity; a skip list wins on simplicity, which is why Redis sorted sets use one. The structure is really two: a skip list ordered by (score, member) and a dict from member to score, so ZSCORE is O(1) while ZREVRANK is a search.

The trick that makes rank cheap is the span: each forward pointer records how many level-0 steps it skips. Summing the spans you traverse during a search yields the rank at no extra cost, and following spans downward lets you jump straight to rank 5,000 rather than walking to it.

code/hld/leaderboard_sorted_set.py — the skip list
class SortedSet:
    """A skip list with span counters, plus a dict from member to score.

    Complexity, which is the whole reason this structure and not a sorted list:

    * ``add`` / ``remove`` / ``score_of`` / ``rank`` - O(log n) expected (``score_of`` O(1))
    * ``top(k)`` - O(k): the level-0 list is already in board order
    * ``page(start, count)`` - O(log n + count) by following spans, not O(start + count)

    ``span[i]`` is the number of level-0 steps a level-``i`` pointer skips. Summing the spans
    you traverse while searching gives the rank for free, which is exactly what a SQL
    ``ORDER BY score DESC LIMIT ... OFFSET 5000`` cannot do without scanning 5,000 rows.
    """

    _MAX_LEVEL = 16
    _P = 0.25

    def __init__(self, rng: random.Random | None = None) -> None:
        self._rng = rng or random.Random()
        self._head = _Node("", 0.0, [None] * self._MAX_LEVEL, [0] * self._MAX_LEVEL)
        self._level = 1
        self._length = 0
        self._scores: dict[str, float] = {}

    def __len__(self) -> int:
        return self._length

    def __contains__(self, member: object) -> bool:
        return member in self._scores

    def score_of(self, member: str) -> float | None:
        """O(1) - this is why a sorted set is two structures and not one."""
        return self._scores.get(member)

    def add(self, member: str, score: float) -> None:
        """Insert a member, or move one that is already present. O(log n) expected."""
        current = self._scores.get(member)
        if current is not None:
            if current == score:
                return
            self._unlink(member, current)
        self._link(member, score)
        self._scores[member] = score

    def remove(self, member: str) -> bool:
        current = self._scores.pop(member, None)
        if current is None:
            return False
        self._unlink(member, current)
        return True

    def count_above(self, score: float, member: str = "") -> int:
        """How many members sort strictly before ``(score, member)``.

        With the default empty member this counts members with a strictly greater score,
        which is what a shard contributes to a global rank it does not own.
        """
        key = order_key(score, member)
        node, traversed = self._head, 0
        for level in reversed(range(self._level)):
            nxt = node.forward[level]
            while nxt is not None and order_key(nxt.score, nxt.member) < key:
                traversed += node.span[level]
                node = nxt
                nxt = node.forward[level]
        return traversed

    def rank(self, member: str) -> int:
        """0-based rank on this set. O(log n)."""
        score = self._scores.get(member)
        if score is None:
            raise NotFoundError(f"{member!r} is not on this board")
        return self.count_above(score, member)

    def top(self, limit: int) -> list[Entry]:
        """The first ``limit`` entries in board order. O(limit)."""
        if limit <= 0:
            raise ValidationError("limit must be positive")
        out: list[Entry] = []
        node = self._head.forward[0]
        while node is not None and len(out) < limit:
            out.append(Entry(node.member, node.score))
            node = node.forward[0]
        return out

    def page(self, start: int, count: int) -> list[Entry]:
        """``count`` entries beginning at 0-based rank ``start``. O(log n + count)."""
        if start < 0 or count <= 0:
            raise ValidationError("start must be non-negative and count positive")
        target = start + 1  # spans count level-0 steps, so ranks are 1-based inside the walk
        node, traversed = self._head, 0
        for level in reversed(range(self._level)):
            nxt = node.forward[level]
            while nxt is not None and traversed + node.span[level] <= target:
                traversed += node.span[level]
                node = nxt
                nxt = node.forward[level]
        if traversed != target:
            return []
        out: list[Entry] = []
        cursor: _Node | None = node
        while cursor is not None and len(out) < count:
            out.append(Entry(cursor.member, cursor.score))
            cursor = cursor.forward[0]
        return out

    # -- internals -------------------------------------------------------------------
    def _random_level(self) -> int:
        level = 1
        while level < self._MAX_LEVEL and self._rng.random() < self._P:
            level += 1
        return level

    def _link(self, member: str, score: float) -> None:
        update: list[_Node] = [self._head] * self._MAX_LEVEL
        rank_at = [0] * self._MAX_LEVEL
        key = order_key(score, member)
        node = self._head
        for level in reversed(range(self._level)):
            rank_at[level] = 0 if level == self._level - 1 else rank_at[level + 1]
            nxt = node.forward[level]
            while nxt is not None and order_key(nxt.score, nxt.member) < key:
                rank_at[level] += node.span[level]
                node = nxt
                nxt = node.forward[level]
            update[level] = node
        level_count = self._random_level()
        if level_count > self._level:
            for level in range(self._level, level_count):
                rank_at[level] = 0
                update[level] = self._head
                self._head.span[level] = self._length
            self._level = level_count
        fresh = _Node(member, score, [None] * level_count, [0] * level_count)
        for level in range(level_count):
            fresh.forward[level] = update[level].forward[level]
            update[level].forward[level] = fresh
            fresh.span[level] = update[level].span[level] - (rank_at[0] - rank_at[level])
            update[level].span[level] = (rank_at[0] - rank_at[level]) + 1
        for level in range(level_count, self._level):
            update[level].span[level] += 1
        self._length += 1

    def _unlink(self, member: str, score: float) -> None:
        update: list[_Node] = [self._head] * self._MAX_LEVEL
        key = order_key(score, member)
        node = self._head
        for level in reversed(range(self._level)):
            nxt = node.forward[level]
            while nxt is not None and order_key(nxt.score, nxt.member) < key:
                node = nxt
                nxt = node.forward[level]
            update[level] = node
        target = node.forward[0]
        if target is None or target.member != member:
            return
        for level in range(self._level):
            if update[level].forward[level] is target:
                update[level].span[level] += target.span[level] - 1
                update[level].forward[level] = target.forward[level]
            else:
                update[level].span[level] -= 1
        while self._level > 1 and self._head.forward[self._level - 1] is None:
            self._level -= 1
        self._length -= 1

Two details worth raising unprompted. First, ties must be broken deterministically: order by (score descending, player_id ascending). Without a total order, two players on 9,800 points swap places between reads, the client flickers, and a cursor built from the last row of a page can skip or repeat rows. Second, an update is a delete plus an insert — the member moves in the ordering — which is why a hot player re-ranking hundreds of times per second is a real write cost and why you use the "only if greater" form of ZADD for best-score boards.

Deep dive: sharding beyond one node

At ~90k ops/s a single instance is at capacity, and one instance is also one failure domain for every board. Two ways to split it:

Scheme Write Top-K read Rank read Fails when
Partition by member hash Single shard, O(log n) Scatter-gather: N local top-Ks merged Sum of per-shard counts above the score Every read touches every shard
Partition by score range Single shard, but ranges must be rebalanced Read the top range only Count in higher ranges plus a local rank Scores drift upward, so ranges become hot and need constant splitting
One writer, many read replicas Single node, replicated Cheap Cheap Write ceiling unchanged; replicas serve stale ranks

Partition by member hash. The correctness argument for top-K is short and worth stating: the global top K is a subset of the union of the shards' local top Ks, because a member in the global top K cannot be below rank K inside its own shard. So N lists of K merge into the answer, and the cost is N x K entries moved plus a k-way merge. Global rank is the same idea in reverse — each shard answers "how many members do you hold above this score", and the answer is the sum.

How the fan-out looks.

flowchart LR
    lb_req["top(100) request"] --> lb_fan["Board service"]
    lb_fan -->|"local top 100"| lb_s1[("Shard 1")]
    lb_fan -->|"local top 100"| lb_s2[("Shard 2")]
    lb_fan -->|"local top 100"| lb_s3[("Shard 3")]
    lb_fan -->|"local top 100"| lb_s4[("Shard 4")]
    lb_s1 --> lb_merge["k-way merge, take 100"]
    lb_s2 --> lb_merge
    lb_s3 --> lb_merge
    lb_s4 --> lb_merge
    lb_merge --> lb_out["Ranked page"]

Score-range partitioning makes the top-K read trivial but is a trap: scores only rise, so the top range grows without bound and every rebalance moves members. Hash partitioning keeps load even and pays a bounded, parallel fan-out instead.

code/hld/leaderboard_sorted_set.py — scatter-gather over shards
class ShardedLeaderboard:
    """N sorted sets partitioned by a stable hash of the member id.

    Sharding by member spreads writes evenly and keeps ``submit`` a single-shard O(log n)
    operation. The price is on the read side: every global answer is a scatter-gather.
    ``top(k)`` is correct because the global top K is a subset of the union of the shards'
    local top Ks, so N lists of K merge into the answer. ``rank`` is a sum, because a global
    rank is "how many members does each shard hold above my score".

    One lock per shard, so writes to different shards never contend.
    """

    def __init__(self, shards: int = 4, seed: int | None = None, max_score: float = 1e9) -> None:
        if shards <= 0:
            raise ValidationError("a leaderboard needs at least one shard")
        self._max_score = max_score
        self._sets = [
            SortedSet(random.Random(seed + i) if seed is not None else None) for i in range(shards)
        ]
        self._locks = [threading.Lock() for _ in range(shards)]

    def __len__(self) -> int:
        return sum(len(s) for s in self._sets)

    @property
    def shard_count(self) -> int:
        return len(self._sets)

    def shard_for(self, member: str) -> int:
        """CRC32 rather than ``hash()``: the placement must survive a process restart."""
        return zlib.crc32(member.encode()) % len(self._sets)

    def submit(self, member: str, score: float, *, best_only: bool = True) -> float:
        """Record a score and return the stored value.

        Validation is the unglamorous half of the crux. A score of ``inf`` or 10^12 is not a
        bug you fix later - it is an entry nobody can ever displace, and support deletes it
        by hand. ``best_only`` makes the write idempotent for replays: re-delivering the same
        event cannot lower a player's best.
        """
        if not member:
            raise ValidationError("member id is required")
        if not math.isfinite(score) or score < 0:
            raise ValidationError(f"score must be a finite non-negative number, got {score!r}")
        if score > self._max_score:
            raise ValidationError(f"score {score:g} exceeds the ceiling {self._max_score:g}")
        index = self.shard_for(member)
        with self._locks[index]:
            current = self._sets[index].score_of(member)
            if best_only and current is not None and current >= score:
                return current
            self._sets[index].add(member, score)
            return score

    def score_of(self, member: str) -> float:
        index = self.shard_for(member)
        with self._locks[index]:
            score = self._sets[index].score_of(member)
        if score is None:
            raise NotFoundError(f"{member!r} is not on this board")
        return score

    def top(self, limit: int = 10) -> list[RankedEntry]:
        """Scatter to every shard, merge the local top lists, take the first ``limit``."""
        if limit <= 0:
            raise ValidationError("limit must be positive")
        pages = []
        for index, sset in enumerate(self._sets):
            with self._locks[index]:
                pages.append(sset.top(limit))
        merged = heapq.merge(*pages, key=lambda e: order_key(e.score, e.member))
        return [
            RankedEntry(rank, entry.member, entry.score)
            for rank, entry in enumerate(itertools.islice(merged, limit))
        ]

    def rank(self, member: str) -> int:
        """Global 0-based rank: sum over shards of "members you hold above this key"."""
        score = self.score_of(member)
        total = 0
        for index, sset in enumerate(self._sets):
            with self._locks[index]:
                total += sset.count_above(score, member)
        return total

    def neighbours(self, member: str, radius: int = 2) -> list[RankedEntry]:
        """The relative board: the ``radius`` players either side of this one.

        Every global neighbour of a member sits within ``radius`` positions of that member's
        split point *inside its own shard*, so one window per shard is a superset of the
        answer. Merge the windows, then slice around the member.
        """
        if radius < 0:
            raise ValidationError("radius must be non-negative")
        score = self.score_of(member)
        window: list[Entry] = []
        for index, sset in enumerate(self._sets):
            with self._locks[index]:
                local = sset.count_above(score, member)
                window.extend(sset.page(max(0, local - radius), 2 * radius + 1))
        window.sort(key=lambda e: order_key(e.score, e.member))
        centre = next(i for i, entry in enumerate(window) if entry.member == member)
        low = max(0, centre - radius)
        rank = self.rank(member)
        return [
            RankedEntry(rank - (centre - low) + offset, entry.member, entry.score)
            for offset, entry in enumerate(window[low : centre + radius + 1])
        ]

sharded over 4 shards, members per shard: [0, 2, 3, 5]
scatter-gather top 5:
  #1  hal  9990
  #2  ana  9800
  #3  cy   9800
  #4  eli  8850
  #5  ivy  8100
global rank('ivy') = 4 (sum of per-shard count_above)
relative board around 'ivy': #3 cy, #4 eli, #5 ivy, #6 bo, #7 fin

The neighbours query is the subtle one: every global neighbour of a player sits within radius positions of that player's split point inside its own shard, so one small window per shard is a superset of the answer. Merge the windows and slice around the player.

Deep dive: real-time rank updates

"Make it live for a million spectators" is where candidates over-engineer. Do the arithmetic first: 1M viewers each receiving a 5 KB board once a second is 5 GB/s, which is a bigger problem than the leaderboard itself.

Approach Traffic Freshness Use it for
Client polls the cached top-N every second One CDN hit per client per second, ~0 origin load 1 s The default for everybody
Server-sent events pushing the whole board on change Only when the board changes, but full payload Instant Esports overlays, a few thousand viewers
Pub/sub of deltas (rank changes only) Smallest, but stateful per connection Instant The finals of a tournament
Push per-player ranks to every player 50M distinct messages Instant Never

Take the first as the baseline and add SSE only for the small, high-value audience. The board writer publishes leaderboard-changed only when the composition of the top N changes, which at 15k writes/s is a rare event once the board settles: a submission that leaves a player at rank 40,000 changes nothing anybody is watching.

Per-player rank stays request-response. It cannot be broadcast (50M distinct answers) and it cannot be shared-cached (one value per player), but it is one ZSCORE plus N ZCOUNT-style calls at O(log n) each, which Redis serves inside the 100 ms budget. The one-second cache TTL on the shared board doubles as a rate limiter: however hard clients poll, the origin sees at most one read per board per second.

For read-your-writes, the submit response carries the new rank computed on the write path, so the player who just finished a match sees it immediately even if the cached board is a second behind.

Deep dive: periodic boards, persistence and validation

"Where does the daily board come from?" It is not a filter over the all-time board — a sorted set is indexed by score, and no index can answer "scores submitted since midnight". So a daily board is a different key, game:eu:daily:19677, and each submission writes every period's current key. The write amplification is exactly the number of periods you offer, which is why four periods turn 15k submissions/s into 60k Redis writes/s.

Retirement is a TTL derived from the bucket, not from the last write, so a late submission cannot extend yesterday's board:

code/hld/leaderboard_sorted_set.py — one board per period, expired by bucket
@dataclass(frozen=True, slots=True)
class Period:
    """One board family: how wide a bucket is, and how long a closed bucket survives."""

    name: str
    bucket_s: int  # 0 means the board never rotates (all-time)
    ttl_s: int = 0

    def key(self, now: float) -> str:
        if self.bucket_s == 0:
            return self.name
        return f"{self.name}:{int(now // self.bucket_s)}"

    def expires_at(self, now: float) -> float | None:
        """End of the bucket plus the grace period, computed from the bucket, not the write.

        Deriving the expiry from the bucket index keeps it idempotent: a late submission
        cannot extend yesterday's board by another day.
        """
        if self.bucket_s == 0:
            return None
        return float((int(now // self.bucket_s) + 1) * self.bucket_s + self.ttl_s)


class PeriodicLeaderboards:
    """One board per period, keyed ``<name>:<bucket>``, retired by TTL rather than by a job.

    A daily board is not a filter over the all-time board - there is no index that could
    answer "scores submitted since midnight" from a sorted set keyed by score. So a submit
    writes every period's current key, which is why the write amplification is exactly the
    number of periods you offer.
    """

    def __init__(
        self,
        periods: Sequence[Period],
        clock: Clock | None = None,
        shards: int = 4,
        seed: int | None = None,
    ) -> None:
        if not periods:
            raise ValidationError("at least one period is required")
        self._periods = tuple(periods)
        self._clock = clock or SystemClock()
        self._shards = shards
        self._seed = seed
        self._boards: dict[str, ShardedLeaderboard] = {}
        self._expiry: dict[str, float] = {}
        self._lock = threading.Lock()

    def submit(self, member: str, score: float) -> list[str]:
        """Write the score into every period's current board; return the keys touched."""
        now = self._clock.now()
        keys: list[str] = []
        for period in self._periods:
            key = period.key(now)
            self._board(key, period, now).submit(member, score)
            keys.append(key)
        return keys

    def board(self, name: str) -> ShardedLeaderboard:
        key = next(p.key(self._clock.now()) for p in self._periods if p.name == name)
        with self._lock:
            if key not in self._boards:
                raise NotFoundError(f"board {key!r} has no scores yet")
            return self._boards[key]

    def keys(self) -> list[str]:
        with self._lock:
            return sorted(self._boards)

    def expire(self) -> list[str]:
        """Drop every board whose bucket closed more than its grace period ago."""
        now = self._clock.now()
        with self._lock:
            dead = sorted(key for key, at in self._expiry.items() if at <= now)
            for key in dead:
                del self._boards[key]
                del self._expiry[key]
        return dead

    def _board(self, key: str, period: Period, now: float) -> ShardedLeaderboard:
        with self._lock:
            board = self._boards.get(key)
            if board is None:
                board = ShardedLeaderboard(self._shards, seed=self._seed)
                self._boards[key] = board
                expiry = period.expires_at(now)
                if expiry is not None:
                    self._expiry[key] = expiry
            return board

submit writes keys ['alltime', 'daily:19675']
submit writes keys ['alltime', 'daily:19677']
keys held: ['alltime', 'daily:19675', 'daily:19677']
expire() drops ['daily:19675'], leaving ['alltime', 'daily:19677']

Persistence. Treat the sorted sets as a rebuildable index and the score log as the system of record. Redis snapshots plus an append-only file shorten recovery, but the guarantee comes from the log: replaying a day is 500M events at 25 GB, a few minutes with pipelined batch writes, and replaying the all-time board is a scheduled job that runs from the columnar archive. Say explicitly that you would accept losing a board and rebuilding it, because that decision is what lets you keep the fast path in memory.

Validation. Scores arrive from a game server, never a client, and are checked before they are logged: a finite non-negative value under the game's ceiling, a rate limit per player, and a match_id that must be unused. Beyond that, keep suspicious accounts on a shadow board — their scores are recorded but not published — so an investigation never requires deleting rows from a live ranking that other players have already seen.

Scaling, bottlenecks and failure modes

v2: a Redis cluster of 8 shards with replicas, a partitioned write path, and regional caches in front of the shared board.

flowchart LR
    subgraph clients["Clients"]
        c_app["Game clients, 50M DAU"]
    end
    subgraph edge["Edge"]
        e_cdn["CDN: top-N per board, 1 s TTL"]
        e_gw["Regional gateways"]
    end
    subgraph write["Write path"]
        w_score["Score service, autoscaled"]
        w_kafka[["Kafka, partitioned by player_id"]]
        w_writer["Board writers, idempotent"]
    end
    subgraph read["Read path"]
        r_board["Board service: scatter-gather"]
        r_local[("Per-region top-N cache")]
    end
    subgraph data["Data"]
        d_shards[("Redis cluster: 8 shards<br/>1 replica each, key per period")]
        d_log[("Score log: 25 GB/day")]
        d_cold[("Object storage: sealed periods")]
    end
    c_app --> e_cdn --> r_local
    c_app --> e_gw --> w_score --> w_kafka --> w_writer --> d_shards
    w_score --> d_log
    e_gw --> r_board --> d_shards
    r_board --> r_local
    d_log --> d_cold
  • A hot board key. Sharding spreads members evenly, but the daily global board is one logical key read by everyone. The 1 s cache protects it; without it, 30k/s of top-N reads land on the shards.
  • Fan-out amplification. Every rank read touches all 8 shards, so Redis sees 8x the request rate. Cap limit, pipeline the shard calls, and use a per-request deadline so one slow shard cannot hold the fan-out open.
  • Spikes. A tournament turns 15k writes/s into 100k. Kafka absorbs it and the board lags by seconds, which is the right degradation here.
  • Shard loss. Promote the replica; meanwhile serve the last cached top-N and mark ranks approximate, since the missing shard's members are absent from the count.
  • Rebalancing. Use consistent hashing with virtual nodes so a resize migrates one slice, and rebuild moved members from the score log rather than migrating live sorted sets.

Trade-offs summary

Decision Chosen Alternatives Why
Structure Skip-list sorted set plus hash map SQL index; sorted array O(log n) rank and O(log n + m) deep pages; O(1) score lookup
Ordering Score descending, player id ascending Score only Ties are constant; without a total order pages repeat or skip rows
Sharding Hash of the player id Score ranges Scores only rise, so ranges become permanently hot
Global reads Scatter-gather with a k-way merge A single global node Bounded, parallel, and it survives one node dying
Shared board Cached 1 s at the edge Live per request One 5 KB object absorbs 30k reads/s and rate-limits the origin
Live updates Poll the cache, SSE for a small audience Push per-player ranks 50M distinct ranks cannot be broadcast
Periods One key per period plus TTL Filter the all-time board by time A score-ordered index cannot answer a time predicate
Durability Score log is the source of truth Redis persistence alone Boards are derived, so losing one costs a rebuild, not data

Interviewer follow-ups

How do you paginate to rank 500,000?

Not with OFFSET. Spans let the sorted set jump to a rank in O(log n), so a shard serves "50 rows from rank 500,000" directly. Across shards the cursor is the (score, player_id) of the last row, so the next page is "everything strictly after this key" — stable as ranks shift underneath.

Two players have the same score. Who is first?

Whoever the tie-break rule says, and the rule must be part of the sort key. Player id ascending is the cheapest deterministic choice; "who reached the score first" is friendlier, and is implemented by storing a composite score of score * 2^k - timestamp so a single float still orders correctly.

What if a player's rank must reflect their submission instantly?

Compute it on the write path and return it in the 202. The submitting service already knows the new score, so one rank query against the shards gives read-your-writes for the one player who cares, while everyone else reads the cached board.

How would you support 'top 100 among my friends'?

Not from the global board. Fetch the friend ids (a few hundred), read their scores with one batched call per shard, and sort in the service. The board answers "score of these members", which is O(1) per member, instead of trying to rank a subset globally.

Redis restarts and the board is empty. What happens?

Reads degrade to the cached top-N while a rebuild job replays the score log into fresh keys. Because the board is derived, recovery is a throughput problem, not a correctness one: 25 GB replays in minutes with pipelined batches, and the all-time board is seeded from the nightly snapshot.

How is this different from a top-K heavy hitters service?

A leaderboard tracks an exact, bounded set of members with an exact score each; heavy hitters approximates counts over an unbounded key space with a sketch. Say which one you have: if a member's score must be exactly right and displayed next to their name, sketches are out.

Interview tip

Split the reads in your first sentence: "the global top 100 is one small object that caches for a second, so the design is really about serving 30k per-player rank queries." That immediately separates the easy half from the hard half and takes you straight to sorted sets and scatter-gather.

Common mistake

Reaching for SELECT ... ORDER BY score DESC LIMIT 100 OFFSET n and moving on. It gives you the top 100 and nothing else: a player's rank costs a count over every row above them, deep pages scan everything they skip, and at 30k QPS the database is the whole design. Name the complexity out loud before you choose the structure.

45-minute pacing

Minutes What to say and draw
0-5 Clarify: 50M DAU, best score per period, top 100 plus my rank plus neighbours, ties broken deterministically, server-submitted scores.
5-10 Estimation: 15k writes/s, 30k reads/s, ~100 B per entry, ~50 GB all-time, ~90k Redis ops/s. State that operations, not memory, force sharding.
10-15 API (submit with idempotency, top-N, my rank, around, cursor page) and the data model: one sorted-set key per board and period, score log as the record.
15-22 v1 diagram; narrate the write path (validate, log, ack, then update each period key) and the read path (cached top-N versus scatter-gather rank).
22-35 Deep dives: sorted set complexity and tie-breaking; sharding by member with scatter-gather versus score ranges, with the top-K correctness argument.
35-41 Real-time updates without broadcasting ranks; periodic keys with TTL; rebuild from the log; score validation.
41-45 Bottlenecks (hot board key, 8x fan-out, spikes, shard loss) and the trade-offs table.