Entwirf ein Echtzeit-Leaderboard für Millionen von Spielern

Question

IT Interview Practice · Accepted Answer

**Nutze ein Redis Sorted Set (ZSET), gekeyt nach Score: Rang und Top-N werden zu eingebauten O(log N)-Operationen, sodass du nie Millionen Rows pro Request sortierst.** Ein ZSET hält Mitglieder automatisch nach Score geordnet; genau das ist ein Leaderboard.

## Architektur

```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)
```

## Wie es funktioniert

- **ZADD** upsertet den Score eines Spielers in O(log N). Redis hält die Reihenfolge über eine **Skip List**, sodass kein Neusortieren nötig ist.
- **Top-N**: `ZREVRANGE board 0 99 WITHSCORES` liefert die Top 100 in O(log N + 100).
- **Dein Rang**: `ZREVRANK board user` gibt die 0-basierte Position; **Around-me** ist `ZREVRANGE rank-5 rank+5` - die Scheibe der Spieler nahe dir.
- **Durability**: Redis ist in-memory. Aktiviere **AOF** (Append-only File) für Replay und spiegle Scores asynchron nach **Postgres** als wahres System of Record, sodass ein Redis-Verlust wiederherstellbar ist.

## Sharding für Millionen von Nutzern

Ein ZSET hält problemlos Dutzende Millionen Mitglieder (speichergebunden, ~100MB für 1 Mio. Einträge). Darüber hinaus, oder für globale Skalierung, **sharde nach Score-Range** (0-1k, 1k-10k…), sodass jeder Shard ein zusammenhängendes Band ist - ein globales Top-N liest nur den obersten Shard. Vermeide Sharding nach User-Hash: Ränge über zufällige Shards zu rekombinieren ist teuer.

## Interview-Perspektive

Der Interviewer möchte sehen, dass du **zur richtigen Datenstruktur greifst** statt zu `ORDER BY score LIMIT 100` auf SQL (das bei jedem Treffer neu sortiert und unter Write-Last stirbt). Gute Antworten benennen ZSET; hervorragende Antworten decken **Around-me-Queries, Gleichstände, Persistenz und Shard-Strategie** ab. Eine klassische Falle: zu vergessen, dass Redis flüchtig ist, und es als Source of Truth zu behandeln - ein Restart löscht das Board, es sei denn, AOF/RDB oder ein DB-Spiegel existiert.

## Trade-offs & Fehler

- **Gleichstände.** Gleiche Scores ordnen lexikografisch nach Member, was zufällig aussieht. Kodiere einen Tiebreaker in den Score (z. B. `score * 1e13 - timestamp`), sodass frühere Erreicher höher ranken.
- **Hot Key.** Ein einzelnes globales ZSET ist ein Key auf einem Shard - ein Write-Hotspot. Puffere/batche `ZADD`s, oder nutze zeit-gebucketete Boards (täglich/wöchentlich), um die Last zu verteilen.
- **Consistency.** Reads können dem async DB-Spiegel um Sekunden hinterherhinken - für Leaderboards in Ordnung, nicht für Auszahlungen; gleiche vor Preisvergabe aus Postgres ab.
- **Speicherkosten.** Millionen Mitglieder kosten echten RAM; lass saisonale Boards mit TTLs ablaufen.
- **Wann nicht:** ein Leaderboard von ein paar Tausend, das jede Minute aktualisiert wird, ist als gecachte SQL-Query in Ordnung - ein Redis ZSET glänzt, wenn Writes konstant sind und der Rang sofort sein muss.

Architektur

Wie es funktioniert

Sharding für Millionen von Nutzern

Interview-Perspektive

Trade-offs & Fehler

Ähnliche Fragen