Concevoir un classement en temps réel avec Redis sorted set

1. Aperçu

Le tableau de classement (leaderboard) apparaît dans pratiquement tous les jeux en ligne. Le problème semble simple : classer les joueurs par points. Avec des millions de joueurs et des milliers de matchs qui se terminent chaque seconde, ORDER BY score DESC sur une base de données relationnelle ne répond plus.

Cet article parcourt la conception complète : les exigences, le modèle de données sur Redis sorted set, l’API, les flux de traitement, et les difficultés comme les ex-aequo, les mises à jour dupliquées, la cohérence des données et les pics de charge. Après cette lecture, vous pourrez construire un leaderboard fonctionnel en Spring Boot 3 et Redis, tout en connaissant ses limites.

2. Exigences du problème

2.1. Exigences fonctionnelles

• Chaque saison (season) a son propre tableau de classement. Le score d’un joueur est le score maximal obtenu dans un match.
• Voir les top N (généralement 100).
• Voir son propre rang, même en étant classé 3 456 789.
• Voir « autour de moi » : 5 personnes au-dessus et 5 au-dessous.
• Quand deux personnes ont le même score, celui qui l’a atteint en premier est classé au-dessus.

2.2. Échelle et contraintes

• 10 millions de joueurs par saison.
• En moyenne 2 000 résultats de matchs par seconde. Aux heures de pointe ou lors d’événements, cela peut atteindre 20 000/seconde.
• Les lectures sont beaucoup plus fréquentes que les écritures : l’écran top 100 est appelé continuellement.
• Latence de rafraîchissement acceptable : moins de 1-2 secondes après la fin d’un match.
• Un résultat de match peut être renvoyé plusieurs fois en cas de tentative. Les résultats dupliqués ne doivent pas fausser le classement.

3. Pourquoi choisir Redis sorted set

Le sorted set (ZSET) stocke les paires member → score et maintient toujours l’ordre selon le score. En interne, il utilise une skip list combinée à une table de hachage, d’où les caractéristiques suivantes :

Opération	Commande	Complexité
Mettre à jour le score	ZADD	O(log N)
Obtenir le rang	ZREVRANK	O(log N)
Obtenir top N / une plage	ZREVRANGE	O(log N + M)
Obtenir le score d’une personne	ZSCORE	O(1)

Avec N = 10 millions, log N est seulement environ 23 étapes. Comparé à SQL : pour connaître le rang d’une personne, vous devez compter les lignes avec un score plus élevé. Même avec un index, cette requête reste coûteuse à grande échelle.

En termes de mémoire, chaque member consomme environ 80-120 octets, selon la longueur de l’ID. 10 millions de joueurs représentent environ 1 Go, ce qui rentre toujours dans un seul nœud Redis.

4. Architecture générale

Game Server ──► Kafka (topic: match-results) ──► Leaderboard Consumer ──► Redis ZSET
                         │                                                  ▲
                         └──► Persist Consumer ──► PostgreSQL (source de vérité)   │
                                                                            │
Client ──► Leaderboard API (Spring Boot) ── cache des 100 premiers en RAM ────────┘

Il y a trois décisions clés :

1. PostgreSQL est la source de vérité. Redis n’est qu’un index pour les lectures rapides. Si Redis est perdu, vous pouvez le reconstruire à partir de la base de données.
2. Kafka se tient au milieu pour absorber les pics de charge. Le serveur de jeu n’est pas ralenti quand Redis est occupé.
3. L’API de lecture est découplée du flux d’écriture. Les 100 premiers sont mis en cache à court terme en RAM de chaque instance.

Tableau stockant les résultats des matchs dans PostgreSQL :

CREATE TABLE match_results (
    match_id     UUID        NOT NULL,
    player_id    BIGINT      NOT NULL,
    season_id    INT         NOT NULL,
    points       INT         NOT NULL CHECK (points >= 0),
    achieved_at  TIMESTAMPTZ NOT NULL,
    PRIMARY KEY (match_id, player_id)
);
CREATE INDEX idx_season_player ON match_results (season_id, player_id);

La clé primaire (match_id, player_id) rend les réécritures inoffensives : il suffit d’utiliser INSERT ... ON CONFLICT DO NOTHING.

5. Modèle de données sur Redis

5.1. Clé et member

lb:{s12}            → ZSET, member = playerId, score = score encodé
lb:{s12}:dedup:<matchId>:<playerId> → STRING, marquer le résultat traité (TTL 1 jour)

La partie {s12} est un hash tag. Sur un Redis Cluster, toutes les clés ayant le même hash tag se trouvent dans le même slot. C’est obligatoire si vous voulez les utiliser ensemble dans un script Lua.

5.2. Gérer les ex-aequo avec un score composite

Redis classe les members ayant le même score par ordre lexicographique du member. Ce type de classement n’a pas de sens pour le jeu. Nous avons besoin que « celui qui atteint en premier soit classé au-dessus », donc nous devons encoder le temps dans le score.

Le score Redis est un double, représentant précisément tous les entiers jusqu’à 2^53. Nous divisons les 53 bits comme suit :

• 21 bits élevés : points (maximum environ 2 millions).
• 32 bits bas : MAX_TIME - nombre de secondes depuis le début de la saison. Celui qui atteint plus tôt aura une valeur plus grande, il sera donc classé au-dessus dans un tri décroissant.

public final class ScoreCodec {

    private static final int TIME_BITS = 32;
    private static final long MAX_TIME = (1L << TIME_BITS) - 1;
    public static final long MAX_POINTS = (1L << 21) - 1;

    private ScoreCodec() {}

    public static long encode(long points, long secondsSinceSeasonStart) {
        if (points < 0 || points > MAX_POINTS) {
            throw new IllegalArgumentException("points hors limites: " + points);
        }
        if (secondsSinceSeasonStart < 0 || secondsSinceSeasonStart > MAX_TIME) {
            throw new IllegalArgumentException("temps hors limites");
        }
        return (points << TIME_BITS) | (MAX_TIME - secondsSinceSeasonStart);
    }

    public static long points(double encoded) {
        return ((long) encoded) >>> TIME_BITS;
    }
}

La fonction encode retourne long. Vous enverrez cette valeur à Redis sous forme de chaîne d’entier pour éviter toute déviation lors du formatage double. Lors de la lecture, points() décale vers la droite de 32 bits pour retrouver le score original. Le cast (long) encoded est exact car la valeur ne dépasse pas 2^53.

Remarque : Si votre jeu a des scores supérieurs à 2 millions, réduisez la résolution du temps, par exemple en minutes au lieu de secondes, pour avoir plus de bits pour les points. Ne dépassez jamais 53 bits. Au-delà, double arrondit, et deux personnes avec des scores différents pourraient obtenir le même score.

Test pour la partie encodage, car c’est le point le plus critique :

class ScoreCodecTest {

    @Test
    void higherPointsAlwaysRankAbove() {
        long late = ScoreCodec.encode(1001, 3_000_000);
        long early = ScoreCodec.encode(1000, 0);
        assertThat(late).isGreaterThan(early);
    }

    @Test
    void samePointsEarlierAchieverRanksAbove() {
        long alice = ScoreCodec.encode(500, 100);
        long bob = ScoreCodec.encode(500, 200);
        assertThat(alice).isGreaterThan(bob);
    }

    @Test
    void decodeSurvivesDoubleRoundTrip() {
        long encoded = ScoreCodec.encode(ScoreCodec.MAX_POINTS, 12_345);
        double fromRedis = (double) encoded;
        assertThat(ScoreCodec.points(fromRedis)).isEqualTo(ScoreCodec.MAX_POINTS);
    }
}

Le troisième test simule le renvoi du score par Redis sous forme double. Ce test vérifie qu’à la valeur limite maximale, le décodage reste correct.

6. Mise à jour du score : atomique et idempotente

Dépendances requises :

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>
<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-web</artifactId>
</dependency>
<dependency>
    <groupId>org.springframework.kafka</groupId>
    <artifactId>spring-kafka</artifactId>
</dependency>

La mise à jour du score a deux exigences qui doivent être satisfaites simultanément :

1. N’écrire que si le nouveau score est plus élevé que le score actuel.
2. Ignorer les résultats de matchs déjà traités.

Si vous utilisez deux commandes séparées comme ZSCORE puis ZADD, deux consumers peuvent s’intercaler. Alors un score plus bas peut écraser un score plus élevé. Nous fusionnons tout dans un script Lua. Redis exécute le script en single-thread et atomiquement.

@Service
public class LeaderboardWriter {

    private static final RedisScript<Long> SUBMIT = RedisScript.of("""
            if not redis.call('SET', KEYS[2], '1', 'NX', 'EX', ARGV[3]) then
              return -1
            end
            local cur = redis.call('ZSCORE', KEYS[1], ARGV[2])
            if cur and tonumber(cur) >= tonumber(ARGV[1]) then
              return 0
            end
            redis.call('ZADD', KEYS[1], ARGV[1], ARGV[2])
            return 1
            """, Long.class);

    private final StringRedisTemplate redis;

    public LeaderboardWriter(StringRedisTemplate redis) {
        this.redis = redis;
    }

    public long submit(MatchResult r) {
        String board = "lb:{s" + r.seasonId() + "}";
        String dedup = board + ":dedup:" + r.matchId() + ":" + r.playerId();
        long score = ScoreCodec.encode(r.points(), r.secondsSinceSeasonStart());
        return redis.execute(SUBMIT, List.of(board, dedup),
                Long.toString(score), Long.toString(r.playerId()), "86400");
    }
}

public record MatchResult(UUID matchId, long playerId, int seasonId,
                          int points, long secondsSinceSeasonStart) {}

Le script retourne trois valeurs :

• -1 : doublon. SET NX a échoué car ce résultat de match a déjà été traité.
• 0 : pas un nouveau record, le tableau est inchangé.
• 1 : record mis à jour.

Vous pouvez utiliser ce code de retour pour compter les métriques ou envoyer une notification « Vous venez de monter en rang ! ».

Remarque : Redis 6.2+ a ZADD key GT score member pour n’écrire que si le score est plus grand. Si vous n’avez pas besoin de déduplication, vous pouvez utiliser cette commande à la place du script. Ici, le script est toujours nécessaire car nous devons fusionner la vérification des doublons dans la même opération atomique.

Si la règle du jeu est d’accumuler les points (ZINCRBY) au lieu de prendre le score maximal, l’idempotence devient obligatoire. Raison : ajouter deux fois est immédiatement faux. Dans ce cas, la partie temps du score composite doit aussi être mise à jour à chaque ajout, donc le script sera plus complexe.

7. API de lecture

@RestController
@RequestMapping("/seasons/{seasonId}/leaderboard")
public class LeaderboardController {

    private final StringRedisTemplate redis;

    public LeaderboardController(StringRedisTemplate redis) {
        this.redis = redis;
    }

    public record Entry(long rank, long playerId, long points) {}

    @GetMapping("/players/{playerId}/around")
    public List<Entry> around(@PathVariable int seasonId, @PathVariable long playerId,
                              @RequestParam(defaultValue = "5") int radius) {
        String key = "lb:{s" + seasonId + "}";
        Long rank = redis.opsForZSet().reverseRank(key, Long.toString(playerId));
        if (rank == null) {
            return List.of();
        }
        long start = Math.max(0, rank - radius);
        return range(key, start, rank + radius);
    }

    List<Entry> range(String key, long start, long end) {
        var tuples = redis.opsForZSet().reverseRangeWithScores(key, start, end);
        List<Entry> result = new ArrayList<>();
        long rank = start + 1;
        for (var t : tuples) {
            result.add(new Entry(rank++, Long.parseLong(t.getValue()),
                    ScoreCodec.points(t.getScore())));
        }
        return result;
    }
}

reverseRank retourne le rang à partir de 0 en ordre décroissant, donc le rang affiché est égal à rank + 1. Si le joueur n’a pas de score dans la saison, la fonction retourne null et l’API renvoie une liste vide. Appeler /seasons/12/leaderboard/players/42/around donnera le résultat suivant :

[{"rank":3456784,"playerId":901,"points":1520},
 ...
 {"rank":3456789,"playerId":42,"points":1518},
 ...
 {"rank":3456794,"playerId":77,"points":1515}]

Les deux commandes reverseRank et reverseRangeWithScores ne sont pas atomiques ensemble. Entre les deux commandes, le tableau peut changer légèrement. Pour un écran de classement, un écart de quelques centaines de millisecondes est acceptable. Si vous avez besoin d’une précision absolue, fusionnez-les dans un script Lua.

8. Points difficiles et solutions

8.1. Hot key dans les top 100

Chaque client appelle top 100, et tout converge vers une seule clé sur un seul nœud Redis. L’ajout de répliques aide partiellement. Cependant, le moyen le plus efficace est de mettre en cache en RAM de chaque instance API et de rafraîchir chaque seconde :

@Component
public class TopCache {

    private final LeaderboardController reader;
    private volatile List<LeaderboardController.Entry> top100 = List.of();

    public TopCache(LeaderboardController reader) {
        this.reader = reader;
    }

    @Scheduled(fixedRate = 1000)
    void refresh() {
        top100 = reader.range("lb:{s12}", 0, 99);
    }

    public List<LeaderboardController.Entry> get() {
        return top100;
    }
}

N’oubliez pas d’activer @EnableScheduling. Avec 50 instances API, Redis ne reçoit que 50 requêtes top 100 par seconde, peu importe le nombre de millions de clients. Dans l’exemple, la saison est codée en dur pour la simplicité. En pratique, vous devriez obtenir la saison actuelle à partir de la configuration.

8.2. Pics d’écriture

Lorsqu’un événement se termine, des dizaines de milliers de matchs peuvent se fermer simultanément. Kafka joue le rôle de tampon. Le consumer traite par batch et envoie les commandes via un pipeline pour réduire le nombre d’aller-retours réseau :

@KafkaListener(topics = "match-results", batch = "true", groupId = "leaderboard")
public void onBatch(List<MatchResult> results) {
    results.forEach(writer::submit);
}

Si vous avez besoin d’être encore plus rapide, vous pouvez regrouper les appels execute dans redis.executePipelined(...). Nous partitionnons aussi le topic par playerId. De cette façon, tous les résultats d’un joueur sont traités séquentiellement sur la même partition, réduisant les contentions. Le script Lua reste correct même en cas de contention.

Quand Redis est lent, le consumer lag augmente, mais le serveur de jeu n’est pas affecté. Les joueurs ne voient que le classement se rafraîchir avec un délai de quelques secondes.

8.3. Cohérence entre Redis et la base de données

Redis peut perdre des données si le nœud meurt avant de pouvoir fsync. Comme PostgreSQL est la source de vérité, vous avez besoin d’un job pour reconstruire le tableau :

SELECT player_id,
       MAX(points) AS best,
       MIN(achieved_at) FILTER (WHERE points = best_points) AS first_at
FROM (
    SELECT player_id, points, achieved_at,
           MAX(points) OVER (PARTITION BY player_id) AS best_points
    FROM match_results
    WHERE season_id = 12
) t
GROUP BY player_id;

Le job écrit le résultat dans une clé temporaire comme lb:{s12}:rebuild, puis utilise RENAME pour remplacer la vraie clé atomiquement. Les utilisateurs ne voient jamais le tableau vide à mi-chemin. Ce job est aussi utilisé régulièrement pour la réconciliation. Si le nombre de members dans Redis diffère de la base de données, vous le détecterez.

8.4. Tableaux par jour, semaine et nettoyage

Le tableau du jour utilise la clé lb:{s12}:d:2026-10-12 avec EXPIRE 3 jours. Le tableau hebdomadaire peut être agrégé à partir des tableaux quotidiens avec ZUNIONSTORE ... AGGREGATE MAX. À la fin de la saison, vous capturez les top 1000 dans la base de données pour les récompenses, puis supprimez la grande clé avec UNLINK au lieu de DEL pour éviter de bloquer Redis.

8.5. Classement des amis

Avec une liste d’environ 200 amis, utilisez ZMSCORE lb:{s12} id1 id2 ... pour obtenir les scores de tous dans une seule commande, puis triez-les en Java. Pas besoin de créer un ZSET séparé pour chaque personne.

9. Quand NE PAS utiliser cette conception

• L’échelle dépasse un nœud. Un ZSET ne peut pas être partitionné sur plusieurs nœuds Cluster. S’il y a des centaines de millions de joueurs dans le même classement, vous devez partitionner par plage de points ou par région, et accepter que le rang global soit seulement une approximation.
• Critères de classement multidimensionnels complexes. Par exemple points, puis taux de victoire, puis nombre de matchs. Alors 53 bits ne suffisent pas pour tout encoder.
• Besoin de rang exact à des fins financières. Les récompenses en argent réel doivent être recalculées à partir de la base de données au moment de la clôture. Ne prenez pas directement depuis Redis.
• Peu de joueurs. Quelques dizaines de milliers de lignes, PostgreSQL avec un index (season_id, points DESC) suffisent, et vous avez un système de moins à exploiter.

10. Conclusion

Redis sorted set permet la mise à jour, l’obtention du rang et l’obtention des top N avec un coût O(log N). C’est la base naturelle d’un leaderboard temps réel.

La partie difficile réside dans les détails :

• Encoder les ex-aequo dans le score sans dépasser 53 bits.
• Utiliser les scripts Lua pour à la fois n’écrire que les records et être idempotent.
• Placer Kafka devant pour absorber les pics de charge.
• Mettre en cache les top 100 en RAM pour éviter les hot keys.
• Garder PostgreSQL comme source de vérité pour pouvoir reconstruire Redis à tout moment.

Lors de l’implémentation, vous devez d’abord écrire des tests pour ScoreCodec. Une erreur de dépassement de bit ici faussera l’ensemble du classement sans aucun message d’erreur.