Design et real-time leaderboard til millioner af spillere

Question

IT Interview Practice · Accepted Answer

**Brug et Redis sorted set (ZSET) nøglet på score: rank og top-N bliver O(log N) indbyggede operationer, så du aldrig sorterer millioner af rows pr. request.** Et ZSET holder medlemmer ordnet efter score automatisk; det er præcis, hvad et leaderboard er.

## Arkitektur

```text
Game svc ──ZADD score──▶ Redis ZSET (sorted by score) ──ZREVRANGE 0 99──▶ Top-100 API
                              │
                              ├─ ZREVRANK user ─▶ "your rank" (around-me: rank±5)
                              └─ AOF/RDB + async ─▶ Postgres (durable source of truth)
```

## Sådan virker det

- **ZADD** upserter en spillers score i O(log N). Redis vedligeholder rækkefølge via en **skip list**, så ingen re-sortering er nødvendig.
- **Top-N**: `ZREVRANGE board 0 99 WITHSCORES` returnerer de øverste 100 i O(log N + 100).
- **Din rank**: `ZREVRANK board user` giver den 0-baserede position; **around-me** er `ZREVRANGE rank-5 rank+5` — skiven af spillere nær dig.
- **Durability**: Redis er in-memory. Aktivér **AOF** (append-only file) til replay, og spejl asynkront scores til **Postgres** som det sande system of record, så et Redis-tab er genoprettelig.

## Sharding til millioner af brugere

Ét ZSET holder titusinder af millioner medlemmer fint (hukommelsesbundet, ~100MB for 1M entries). Ud over det, eller for global skala, **shard efter score-range** (0–1k, 1k–10k…) så hver shard er et sammenhængende bånd — en global top-N læser kun den øverste shard. Undgå sharding efter user hash: at rekombinere ranks over tilfældige shards er dyrt.

## Interview-perspektiv

Intervieweren vil se dig **gribe efter den rette datastruktur** frem for `ORDER BY score LIMIT 100` på SQL (som re-sorterer ved hvert hit og dør under write-belastning). Gode svar navngiver ZSET; fremragende svar dækker **around-me-forespørgsler, ties, persistence og shard-strategi**. En klassisk fælde: at glemme, at Redis er flygtig og behandle det som kilden til sandhed — en genstart udsletter boardet, medmindre AOF/RDB eller et DB-spejl findes.

## Trade-offs & fejl

- **Ties.** Lige scores ordnes efter medlem leksikografisk, hvilket ser tilfældigt ud. Kod en tiebreaker ind i scoren (fx `score * 1e13 - timestamp`) så tidligere præstationer ranker højere.
- **Hot key.** Et enkelt globalt ZSET er én nøgle på én shard — et write-hotspot. Buffer/batch `ZADD`s, eller brug tids-bucketede boards (dagligt/ugentligt) for at sprede belastning.
- **Konsistens.** Reads kan sakke bag det async DB-spejl med sekunder — fint for leaderboards, ikke for udbetalinger; afstem fra Postgres før du tildeler præmier.
- **Hukommelses-omkostning.** Millioner af medlemmer koster reel RAM; udløb sæsonboards med TTL'er.
- **Hvornår ikke:** et leaderboard af nogle få tusinde opdateret hvert minut er fint som en cachet SQL-forespørgsel — Redis ZSET skinner, når writes er konstante og rank skal være øjeblikkelig.

Arkitektur

Sådan virker det

Sharding til millioner af brugere

Interview-perspektiv

Trade-offs & fejl

Relaterede spørgsmål