Suprojektuokite realaus laiko lyderių lentelę (leaderboard) milijonams žaidėjų

Question

IT Interview Practice · Accepted Answer

**Naudokite Redis sorted set (ZSET), raktuotą pagal balą: rangas ir top-N tampa O(log N) integruotomis operacijomis, tad niekada nerūšiuojate milijonų eilučių kiekvienai užklausai.** ZSET automatiškai laiko narius surūšiuotus pagal balą; tai būtent yra lyderių lentelė.

## Architektūra

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

## Kaip tai veikia

- **ZADD** įrašo/atnaujina žaidėjo balą per O(log N). Redis palaiko tvarką per **skip list**, tad rūšiuoti iš naujo nereikia.
- **Top-N**: `ZREVRANGE board 0 99 WITHSCORES` grąžina top 100 per O(log N + 100).
- **Jūsų rangas**: `ZREVRANK board user` grąžina 0-pagrindu poziciją; **around-me** yra `ZREVRANGE rank-5 rank+5` — pjūvis žaidėjų šalia jūsų.
- **Patvarumas**: Redis yra atmintyje. Įjunkite **AOF** (append-only file) pakartojimui ir asinchroniškai veidrodžiuokite balus į **Postgres** kaip tikrą įrašų sistemą, kad Redis praradimas būtų atkuriamas.

## Sharding milijonams naudotojų

Vienas ZSET puikiai laiko dešimtis milijonų narių (ribojamas atmintimi, ~100MB 1 mln. įrašų). Virš to, arba globaliam mastui, **skaidykite pagal balų intervalą** (0–1k, 1k–10k…), kad kiekvienas shard būtų ištisinė juosta — globalus top-N skaito tik viršutinį shard. Venkite skaidymo pagal naudotojo hash: rangų suderinimas per atsitiktinius shard yra brangus.

## Interviu perspektyva

Interviuotojas nori pamatyti, kaip **griebiatės tinkamos duomenų struktūros**, o ne `ORDER BY score LIMIT 100` SQL (kuris rūšiuoja iš naujo kiekvienam hit ir žūva nuo įrašymo apkrovos). Geri atsakymai įvardija ZSET; puikūs apima **around-me užklausas, lygiąsias (ties), patvarumą ir shard strategiją**. Klasikiniai spąstai: pamiršti, kad Redis nepatvarus, ir laikyti jį tiesos šaltiniu — perkrovimas nušluoja lentelę, nebent egzistuoja AOF/RDB ar DB veidrodis.

## Kompromisai ir gedimai

- **Lygiosios (ties).** Vienodi balai rūšiuojami pagal narį leksikografiškai, kas atrodo atsitiktinai. Įkoduokite tiebreaker į balą (pvz. `score * 1e13 - timestamp`), kad ankstesni pasiekėjai būtų aukščiau.
- **Karštas raktas.** Vienas globalus ZSET yra vienas raktas viename shard — įrašymo karštas taškas. Buferizuokite/grupuokite `ZADD`, arba naudokite pagal laiką grupuotas lenteles (dienines/savaitines) apkrovai paskleisti.
- **Konsistencija.** Skaitymai gali atsilikti nuo async DB veidrodžio sekundėmis — tinka lyderių lentelėms, ne išmokoms; sutikrinkite iš Postgres prieš skirdami prizus.
- **Atminties kaina.** Milijonai narių kainuoja realų RAM; naikinkite sezonines lenteles su TTL.
- **Kada ne:** kelių tūkstančių lyderių lentelė, atnaujinama kas minutę, tinka kaip kešuota SQL užklausa — Redis ZSET spindi, kai įrašymai nuolatiniai ir rangas turi būti akimirksniu.

Architektūra

Kaip tai veikia

Sharding milijonams naudotojų

Interviu perspektyva

Kompromisai ir gedimai

Susiję klausimai