Design a Leaderboard

A leaderboard ranks players by score and answers two queries: who are the top N players, and what is the rank of a given player. Scores change constantly, and ranks must reflect those changes quickly. The design question is how to keep a sorted structure with fast updates and fast rank lookups as the number of players grows from thousands to hundreds of millions.

Requirements

Functional

• Update a player's score (set, or increment by a delta after a match).
• Get the top N players (for example, top 100).
• Get a player's rank and score.
• Get a window of players around a given player (for example, 5 above and 5 below).
• Multiple boards: global, per region, per game mode, and time-windowed (daily, weekly, monthly, season).

Non-functional

• Reads and updates in a few milliseconds to tens of milliseconds.
• Near-real-time visibility of new scores (seconds).
• High availability; slight staleness in rank for mid-table players is acceptable.
• Scalable to hundreds of millions of players.
• Durability of scores (the leaderboard can be rebuilt from the score source of truth).

Estimation

Assumptions: 100 million players, 25 million DAU, each playing 10 matches a day, each match producing one score update.

• Updates: 25 x 10^6 x 10 = 250 x 10^6 per day ≈ 2,900 updates/s average, roughly 10,000/s at peak.

• Reads: each DAU opens the leaderboard 5 times a day: 125 x 10^6/day ≈ 1,450 reads/s average; peak about 5,000/s. Most reads are top-N, which is highly cacheable.

• Memory for one global board: each entry holds a player ID (8 bytes), a score (8 bytes), and structure overhead. In an in-memory sorted structure assume about 64 bytes per entry including overhead: 100 x 10^6 x 64 B = 6.4 GB. This fits on one large-memory server, but the write throughput and availability requirements still call for replication.

• Multiple boards (regions, modes, time windows) multiply this by the number of boards each player appears in, for example 10, giving about 64 GB.

• Bandwidth: a top-100 response with names is about 100 x 60 B = 6 KB; 5,000 reads per second is about 30 MB/s uncached, trivial after a cache. Update events are about 100 B: 10,000 per second is 1 MB/s into the stream.

• Durable storage: 250 x 10^6 match events per day x 100 B = 25 GB per day if every event is retained (about 9 TB per year); keep raw events 7 to 30 days and only the current total per player and board long term (100 x 10^6 x 3 boards x 50 B = 15 GB).

• Real Redis overhead per ZSET member is closer to 80 to 120 bytes than 64 (hash entry plus skip list node plus string), so plan for 10 GB per 100 million members and size with headroom of 2x for fork-based snapshots (copy-on-write).

What the numbers imply: 10,000 updates per second is about a tenth of one Redis node's capacity, so throughput does not force sharding; memory (64 GB across boards) and blast radius do. Reads are dominated by top-N, so a 1 to 5 second cache absorbs the bulk and leaves Redis for personal rank lookups (perhaps 1,000 per second). Write amplification from time windows (4 windows means 4 ZADDs per event, about 40,000 per second) is the number that actually matters: pipeline them.

API design

POST /v1/boards/{board}/scores   {player_id, score | delta, match_id}
GET  /v1/boards/{board}/top?n=100
GET  /v1/boards/{board}/players/{id}          -> {rank, score}
GET  /v1/boards/{board}/players/{id}/around?k=5

The score update includes a match_id for idempotency, so a retried request does not add the same delta twice (idempotency). Scores should be submitted by trusted game servers, not clients, to prevent cheating.

Data model

Two stores serve different roles.

Why a relational table is not enough. Rank of a player is 1 + count(players with a higher score). With a SQL index on score, SELECT COUNT(*) WHERE score > X scans index entries and is O(N) in the worst case. This is acceptable for thousands of rows but too slow for millions at request rate. A structure that keeps subtree sizes (an order-statistic tree) or a skip list with span counts answers rank in O(log N).

Redis sorted set. A Redis sorted set (ZSET) stores members with a floating-point score, ordered by score, implemented as a hash table plus a skip list with span information (Redis and Memcached). Complexities:

The following Java program models the same idea with JDK collections: a TreeSet of (score, player) entries plus a HashMap from player to score. Updates remove the old entry and insert the new one. (A TreeSet gives ordered iteration but not O(log N) rank; production stores such as Redis add subtree counts for that. Here rank is computed by iteration for clarity.)

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.OptionalInt;
import java.util.TreeSet;

public class Main {
    record Entry(String player, long score) {
        @Override
        public String toString() {
            return player + "=" + score;
        }
    }

    static final class Leaderboard {
        // Ordered ascending by (score, player).
        private final TreeSet<Entry> byScore =
                new TreeSet<>(Comparator.comparingLong(Entry::score).thenComparing(Entry::player));
        private final Map<String, Long> scores = new HashMap<>();

        void update(String player, long score) {
            var old = scores.put(player, score);
            if (old != null) {
                byScore.remove(new Entry(player, old));
            }
            byScore.add(new Entry(player, score));
        }

        /** The n highest entries, highest first. */
        List<Entry> top(int n) {
            var result = new ArrayList<Entry>();
            for (var e : byScore.descendingSet()) {
                if (result.size() == n) {
                    break;
                }
                result.add(e);
            }
            return result;
        }

        /** 1-based rank, highest score first; equal scores share a rank. O(n) here. */
        OptionalInt rank(String player) {
            var score = scores.get(player);
            if (score == null) {
                return OptionalInt.empty();
            }
            int above = 0;
            for (var e : byScore) {
                if (e.score() > score) {
                    above++;
                }
            }
            return OptionalInt.of(above + 1);
        }
    }

    public static void main(String[] args) {
        var lb = new Leaderboard();
        lb.update("ann", 300);
        lb.update("bob", 500);
        lb.update("cy", 400);
        lb.update("ann", 450);
        System.out.println(lb.top(3));
        System.out.println("rank of ann: " + lb.rank("ann"));
        System.out.println("rank of zed: " + lb.rank("zed"));
    }
}

[bob=500, ann=450, cy=400]
rank of ann: OptionalInt[2]
rank of zed: OptionalInt.empty

rank returns an OptionalInt because an unknown player is a normal result. Players with equal scores share a rank, while top breaks ties by player name, highest name first.

High-level design

flowchart LR
    GS[Game servers] -->|score events| API[Leaderboard API]
    Client[Player clients] --> API
    API --> Q[[Event stream]]
    Q --> W[Score writers]
    W --> DB[(Score database)]
    W --> R[(Redis sorted sets)]
    API -->|rank, top-N| R
    API --> Prof[(Player profile store)]
    API --> Cache[(Top-N cache)]

Components

• Leaderboard API validates requests and serves reads from Redis. For top-N it enriches player IDs with names from the profile store.
• Event stream (Kafka or similar) buffers score events, absorbing spikes and enabling replay.
• Score writers update the durable score database and the sorted sets. Updates are keyed by player, so events for one player are processed in order.
• Redis sorted sets hold the ranking indexes. Replicas serve reads.
• Score database is the source of truth; the sorted sets can be rebuilt from it.

Update and read paths:

sequenceDiagram
    participant G as Game server
    participant A as API
    participant S as Score writer
    participant D as Score DB
    participant R as Redis ZSET
    participant P as Player client
    G->>A: score update (match_id)
    A->>S: enqueue event
    S->>D: upsert, dedupe by match_id, get new total
    S->>R: ZADD board new_total player
    P->>A: get my rank
    A->>R: ZREVRANK and ZSCORE
    R-->>A: rank, score
    A-->>P: rank 1,204,332

Deep dive

Scaling beyond one sorted set

A single Redis instance handles tens of thousands of simple operations per second and holds tens of GB, which covers many boards. When one board's size or traffic exceeds one node, there are two approaches.

Score-range partitioning. Split the sorted set into shards by score range, for example shard 1 holds scores 0-999, shard 2 holds 1000-1999. Top-N reads query the highest shard first. A player's global rank is the sum of the sizes of all higher shards (ZCARD each) plus the rank within their own shard. Updates touch at most two shards (remove from the old shard, insert into the new one). The weakness is skew: score distributions are uneven, so ranges must be rebalanced.

Hash partitioning by player. Distribute players over shards by hash of player ID (sharding). Updates go to one shard. Top-N requires asking every shard for its local top N and merging: the global top N is contained in the union of the local top Ns. Exact global rank of an arbitrary player needs counting players with higher scores on every shard, which is a fan-out query.

Chosen: stay on a single sorted set per board (with a replica) until it passes roughly 100 to 200 million members or 50,000 ops per second, because every sharded variant adds either skew handling or fan-out reads. Beyond that, prefer score-range sharding for exact rank on a game with a bounded score range, and hash sharding when scores are unbounded or skewed. Score-range hot-shard handling: most players cluster in low scores, so choose boundaries from the observed score histogram (equal player counts per shard, not equal score widths) and re-split a shard that exceeds about 30 percent of members; moving a boundary means moving only the members in that range. For hash sharding, 16 shards with local top-100 gives a merge of 1,600 candidates, which is cheap; the cost is 16 parallel requests per exact-rank query, so tail latency is the slowest of 16 (p99 of the max), which is why exact rank is restricted to the top tier.

Approximate ranks. For hundreds of millions of players, showing a player at rank 41,203,118 versus 41,203,500 has little value. Systems often show exact ranks only for the top thousands and an estimated rank or percentile beyond. Percentile can be estimated from a histogram of scores in buckets maintained with counters, which costs O(1) per update and O(buckets) per query.

Time-windowed boards

Daily, weekly, and monthly boards are separate sorted sets whose key includes the window, such as board:game1:2026-W39. A score update writes to every active window's key (write amplification equals the number of windows). Old windows get a TTL, or are archived to the database and expired from memory. At the window boundary a new key is created automatically on first write, avoiding a reset job. Season boards can be materialized at season end and stored as static data.

Ties, consistency, and durability

Sorted sets order equal scores by member name, which is deterministic but arbitrary. A fair tie-break (earlier achievement ranks higher) is implemented by encoding the timestamp into the score, for example score * 2^k + (max_time - time) within the double's exact integer range (about 2^53). Redis replicas replicate asynchronously, so a failover can lose the last few writes; because the score database is the source of truth, the sorted set is repaired by replaying the event stream from a checkpoint. Redis persistence (AOF/RDB) shortens the rebuild.

The writer must not apply a delta to Redis twice when it retries after a crash between the database write and the Redis write. A safe pattern is to compute the new total score in the database transaction (deduplicated by match_id) and then set that absolute value in Redis with ZADD, which is idempotent. ZINCRBY is only safe when each event is applied exactly once.

Caching top-N

The top-100 board is read far more often than it changes in a meaningful way. Cache the rendered top list for a short TTL (1-5 seconds) at the API or CDN layer. This removes most read load from Redis and keeps its capacity for personal rank lookups. See caching fundamentals.

Numbers: the cached object is about 6 KB per board; with 1,000 active boards that is 6 MB, so memory is a non-issue and TTL is the only knob. A 2-second TTL with 5,000 reads per second means one Redis read per board per 2 seconds instead of 5,000 per second. Alternative: invalidate on change, which is wasteful because the top 100 changes many times per second on a busy board. Use request coalescing (one refresh in flight per key) so expiry does not cause a stampede, and serve stale for up to a few seconds on Redis errors. Enrich names from a separate profile cache (TTL minutes) rather than storing them in the ZSET.

Consistency model

The read path is eventually consistent: an event reaches Redis after the stream and writer, typically under a second, up to the consumer lag under load. Consistency for one player is guaranteed by keying the stream by player_id (one partition, one consumer, ordered). Reading your own rank right after a match is the case users notice: return the new score from the update response and have the client show it locally, or read from the Redis primary for that user for about 5 seconds.

Failure modes

At 10x scale (1 billion players, 100,000 updates per second): one node per board no longer fits (about 100 GB per board), so shard, and the fan-out cost of exact rank forces the switch to approximate ranks outside the top tier. Rebuild time from the database grows to hours, so replicas and snapshots become the primary recovery path rather than rebuild. The stream needs at least 100 partitions to keep per-player ordering at that rate.

Bottlenecks and scaling

• Hot board. A global board receives all writes on one key. Batch updates in the writer (aggregate deltas for a player over a short window) and use pipelining.
• Memory. Multiplied by windows and regions. Limit boards to active players (drop zero-score or inactive members).
• Read fan-out on sharded boards. Cache top-N; restrict exact rank to the top tier.
• Rebuild time. Keep snapshots and replay only recent events.
• Cheating. Accept scores only from authenticated game servers, rate-limit per player (rate limiting algorithms), and validate plausibility.

Trade-offs and follow-up questions

• Exactness vs cost. Exact global rank for all players requires order-statistic structures on one node or fan-out queries; approximate ranks reduce cost sharply.
• Real-time vs batched. Updating on every event gives immediate ranks; periodic batch recomputation is simpler and cheaper but stale.
• Follow-ups:
  • Friends-only board? With about 200 friends, fetch each friend's score (ZSCORE per friend, pipelined, or a MGET-style read from the score store) and sort in the service. A per-user ZSET fans out every update to all followers, which is only worth it for very read-heavy, small-graph cases.
  • "Rank as of yesterday"? Snapshot the board at the window boundary (a ZUNIONSTORE/copy into a dated key with a TTL, or dump to object storage) and query the snapshot.
  • Player who has never played? Absent from the set; ZREVRANK returns nil, show unranked.
  • Bans and score decreases? ZREM on ban, plus a tombstone in the score database so a replay does not re-add; a decrease is a ZADD of the new total. Rank shifts for everyone below are implicit in the structure.
  • Millions of players tied at score 0? Do not insert until first score; tie-break by encoded timestamp for the rest.
  • What if the game wants exact rank for 500 million players? Use range sharding with a maintained histogram for the shard-size prefix sums (rank = prefix count of higher shards + local ZREVRANK), which is O(log N) plus one lookup, at the cost of rebalancing.
  • Why not plain SQL? Rank needs an order-statistic count; COUNT(*) WHERE score > X is O(N) per lookup, and with 5,000 reads per second on 100 million rows that is not viable without a counting index structure.