Redis sorted set : leaderboard, file d'attente prioritaire et sliding window

1. Vue d’ensemble

Sorted set (ZSET) est la structure de données la plus flexible de Redis. Chaque élément (member) est associé à un score, et Redis les maintient toujours triés selon le score. Cet article utilise ZSET pour résoudre trois problèmes courants : le classement (leaderboard), la file d’attente prioritaire/planifiée et le rate limiter de type sliding window. Tout est écrit en Java 21 avec Spring Boot 3.x. Après la lecture, vous saurez comment choisir le score pour chaque problème et éviter les erreurs de race condition courantes.

2. Comment fonctionne sorted set

Un ZSET a les propriétés suivantes :

• Le membre est unique. ZADD sur un membre existant ne met à jour que son score.
• Le score est un nombre réel double. Les membres avec le même score sont triés selon l’ordre lexicographique du membre.
• L’ajout, la suppression, la mise à jour et l’obtention du rang ont tous une complexité O(log N). L’obtention d’une plage d’éléments coûte O(log N + M), où M est le nombre d’éléments retournés.

Vous pouvez tester rapidement avec redis-cli :

ZADD scores 120 alice 95 bob 150 carol
ZREVRANGE scores 0 1 WITHSCORES
ZREVRANK scores bob

1) "carol"
2) "150"
3) "alice"
4) "120"
(integer) 2

ZREVRANGE retourne les éléments par score décroissant. ZREVRANK indique la position de bob (en commençant à 0) dans cet ordre.

2.1. Configuration du projet

Ajoutez la dépendance Spring Data Redis. Les deux dépendances Testcontainers sont utilisées pour la partie test de la section 6 :

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>
<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-testcontainers</artifactId>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.testcontainers</groupId>
    <artifactId>junit-jupiter</artifactId>
    <scope>test</scope>
</dependency>

Configuration de la connexion :

spring.data.redis.host=localhost
spring.data.redis.port=6379

Spring Boot crée automatiquement un bean StringRedisTemplate. Toutes les opérations ZSET passent par opsForZSet().

3. Leaderboard

Problème : un jeu ajoute des points aux joueurs, il faut récupérer les top N et le classement d’une personne quelconque. Ici, le score est les points, le membre est l’ID du joueur.

public record PlayerScore(String player, double score) {}

@Service
public class LeaderboardService {

    private static final String KEY = "leaderboard:game:2048";
    private final ZSetOperations<String, String> zSet;

    public LeaderboardService(StringRedisTemplate redis) {
        this.zSet = redis.opsForZSet();
    }

    public double addPoints(String player, double points) {
        return zSet.incrementScore(KEY, player, points);
    }

    public List<PlayerScore> top(int n) {
        Set<ZSetOperations.TypedTuple<String>> tuples =
                zSet.reverseRangeWithScores(KEY, 0, n - 1);
        if (tuples == null) {
            return List.of();
        }
        return tuples.stream()
                .map(t -> new PlayerScore(t.getValue(), t.getScore()))
                .toList();
    }

    public Optional<Long> rankOf(String player) {
        Long rank = zSet.reverseRank(KEY, player);
        return Optional.ofNullable(rank).map(r -> r + 1);
    }
}

Explication de chaque partie :

• incrementScore correspond à la commande ZINCRBY. Cette commande est atomique. Si le membre n’existe pas encore, Redis considère le score initial comme 0. Vous n’avez pas besoin de lire l’ancien score, d’ajouter et de réécrire, donc il n’y a pas de race condition quand plusieurs requêtes ajoutent des points à la même personne.
• reverseRangeWithScores(KEY, 0, n - 1) correspond à ZREVRANGE ... WITHSCORES. L’index de fin est inclus, donc les 10 meilleurs sont 0..9.
• reverseRank retourne null si le joueur n’est pas dans le classement. On ajoute 1 pour que le classement commence à 1, ce qui est plus convivial pour l’utilisateur.

Essayons :

leaderboard.addPoints("alice", 120);
leaderboard.addPoints("bob", 95);
leaderboard.addPoints("carol", 150);
leaderboard.addPoints("bob", 60);

System.out.println(leaderboard.top(3));
System.out.println(leaderboard.rankOf("alice"));

[PlayerScore[player=bob, score=155.0], PlayerScore[player=carol, score=150.0], PlayerScore[player=alice, score=120.0]]
Optional[3]

3.1. Gestion des égalités

Quand deux personnes ont le même score, Redis les trie par ordre lexicographique du membre. Avec ZREVRANGE, l’ordre lexicographique est inversé, donc zoe vient avant anna. Ce résultat ne correspond rarement à l’intention métier. Si vous voulez que celui qui a obtenu le score en premier soit classé avant, vous pouvez encoder l’heure dans la partie décimale du score :

public double addPointsWithTieBreak(String player, long points) {
    long now = System.currentTimeMillis();
    double tieBreak = 1.0 - (now / 1e13);
    double score = points + tieBreak;
    zSet.add(KEY, player, score);
    return score;
}

La personne qui obtient le score plus tôt a un now plus petit, donc tieBreak plus grand et est classée au-dessus. Lors de l’affichage, vous prenez Math.floor(score) pour obtenir les vrais points.

Attention : le score est un double, qui ne représente précisément que les entiers jusqu’à 2^53 (environ 9×10^15). Quand vous fusionnez plusieurs valeurs dans un score, vous devez calculer à l’avance la taille pour ne pas perdre de précision. Avec la méthode ci-dessus, points devrait être inférieur à quelques millions. De plus, cette méthode ne fonctionne pas avec incrementScore, car chaque ajout accumulerait aussi la partie décimale.

4. File d’attente prioritaire et file d’attente planifiée

4.1. File d’attente prioritaire

Cette fois, le score est la priorité : plus le nombre est petit, plus la priorité est élevée. Pour que les jobs au même niveau de priorité sortent toujours dans l’ordre FIFO, on ajoute un timestamp au score :

@Service
public class JobQueue {

    private static final String KEY = "queue:email-jobs";
    private final ZSetOperations<String, String> zSet;

    public JobQueue(StringRedisTemplate redis) {
        this.zSet = redis.opsForZSet();
    }

    public void enqueue(String jobId, int priority) {
        if (priority < 0 || priority > 9) {
            throw new IllegalArgumentException("priority must be 0..9");
        }
        double score = priority * 1e13 + System.currentTimeMillis();
        zSet.add(KEY, jobId, score);
    }

    public Optional<String> poll() {
        var tuple = zSet.popMin(KEY);
        return Optional.ofNullable(tuple).map(ZSetOperations.TypedTuple::getValue);
    }

    public Optional<String> take(Duration timeout) {
        var tuple = zSet.popMin(KEY, timeout.toSeconds(), TimeUnit.SECONDS);
        return Optional.ofNullable(tuple).map(ZSetOperations.TypedTuple::getValue);
    }
}

Points clés :

• priority * 1e13 + millis donne une valeur maximale d’environ 9.2×10^13, bien en dessous du seuil 2^53. Un job de priorité 0 sort toujours avant un job de priorité 1, même s’il a été ajouté après.
• popMin correspond à ZPOPMIN. Cette commande extrait et supprime un élément en une seule étape atomique. Deux workers ne reçoivent jamais le même job.
• popMin(key, timeout, unit) correspond à BZPOPMIN. Cette commande bloque la connexion jusqu’à ce qu’il y ait un job ou que le timeout soit atteint, vous évitez donc le polling continu qui consomme du CPU.

Attention : BZPOPMIN maintient une connexion pendant tout le temps d’attente. Avec Lettuce par défaut utilisant une connexion partagée, la commande blocking bloquera aussi les autres commandes. Vous devriez activer le pool de connexions (ajouter commons-pool2 et configurer spring.data.redis.lettuce.pool.*) ou utiliser une factory de connexion séparée pour les workers.

4.2. File d’attente planifiée

Vous voulez envoyer un email de rappel de paiement dans 30 minutes ? Utilisez le score comme le moment d’exécution (epoch millis). Un worker vérifie régulièrement les jobs avec un score inférieur ou égal au moment actuel.

La manière suivante est incorrecte : appeler rangeByScore puis remove. Deux workers pourraient lire le même job avant de pouvoir le supprimer. On fusionne les deux étapes dans un script Lua pour que Redis les exécute de façon atomique :

@Service
public class DelayedJobQueue {

    private static final String KEY = "queue:delayed";
    private static final RedisScript<String> POP_DUE = new DefaultRedisScript<>("""
            local jobs = redis.call('ZRANGEBYSCORE', KEYS[1], '-inf', ARGV[1], 'LIMIT', 0, 1)
            if #jobs == 0 then return false end
            redis.call('ZREM', KEYS[1], jobs[1])
            return jobs[1]
            """, String.class);

    private final StringRedisTemplate redis;

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

    public void schedule(String jobId, Instant runAt) {
        redis.opsForZSet().add(KEY, jobId, runAt.toEpochMilli());
    }

    public Optional<String> pollDue(Instant now) {
        String job = redis.execute(POP_DUE, List.of(KEY), String.valueOf(now.toEpochMilli()));
        return Optional.ofNullable(job);
    }
}

Le script extrait au maximum un job qui a atteint sa deadline puis le supprime. En Lua, return false est converti en nil, donc Java côté reçoit null. Un worker peut être une méthode @Scheduled(fixedDelay = 500) qui appelle pollDue en boucle jusqu’à ce que ce soit vide.

Attention : Après le pop, le job a quitté Redis. Si le worker meurt à mi-chemin, le job est perdu. Quand vous avez besoin de garantir at-least-once, vous déplacez le job vers un ZSET “processing” avec le score comme deadline, puis le supprimez quand c’est terminé. Si la requirement est encore plus complexe, envisagez Redis Streams ou un vrai message broker.

5. Rate limiter de type sliding window

Fixed window (compter les requêtes par minute) a une faiblesse à la limite. Exemple : 100 requêtes à 00:59 et 100 requêtes à 01:00 passent toutes les deux, soit 200 requêtes en 2 secondes. Sliding window résout cela en gardant le timestamp de chaque requête dans un ZSET :

1. Supprimer les requêtes plus anciennes que now - window (ZREMRANGEBYSCORE).
2. Compter les requêtes restantes (ZCARD).
3. Si on n’a pas atteint la limite, ajouter la requête actuelle avec le score now.

Les trois étapes doivent s’exécuter de façon atomique, donc on utilise encore Lua :

@Service
public class SlidingWindowRateLimiter {

    private static final RedisScript<Long> SCRIPT = new DefaultRedisScript<>("""
            local key    = KEYS[1]
            local now    = tonumber(ARGV[1])
            local window = tonumber(ARGV[2])
            local limit  = tonumber(ARGV[3])
            redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
            if redis.call('ZCARD', key) < limit then
                redis.call('ZADD', key, now, ARGV[4])
                redis.call('PEXPIRE', key, window)
                return 1
            end
            return 0
            """, Long.class);

    private final StringRedisTemplate redis;
    private final Clock clock;

    public SlidingWindowRateLimiter(StringRedisTemplate redis, Clock clock) {
        this.redis = redis;
        this.clock = clock;
    }

    public boolean tryAcquire(String customerId, int limit, Duration window) {
        Long allowed = redis.execute(SCRIPT,
                List.of("rate:" + customerId),
                String.valueOf(clock.millis()),
                String.valueOf(window.toMillis()),
                String.valueOf(limit),
                UUID.randomUUID().toString());
        return Long.valueOf(1L).equals(allowed);
    }
}

Explication :

• Le membre est un UUID aléatoire. Si vous utilisiez le timestamp comme membre, deux requêtes dans le même milliseconde se remplaceraient mutuellement et ne seraient comptées qu’une fois.
• PEXPIRE aide Redis à nettoyer automatiquement la clé des clients inactifs.
• Vous devez déclarer un bean Clock (par exemple Clock.systemUTC()). Injecter Clock rend les tests plus faciles. Cependant, s’il y a plusieurs instances d’application, leurs horloges doivent être synchronisées, ou vous récupérez l’heure directement dans le script avec redis.call('TIME').

Attention : Chaque requête consomme un élément du ZSET. Avec une limite élevée, par exemple 100.000 requêtes/heure pour chaque client, la mémoire augmente rapidement. Dans ce cas, vous devriez utiliser un sliding window counter (estimation à partir de deux fixed windows) ou token bucket.

En cluster mode, le script ne peut toucher que les clés du même hash slot. Les scripts de cet article n’utilisent qu’une clé à la fois, donc pas de problème.

6. Tests avec Testcontainers

Le test ci-dessous s’exécute avec un vrai Redis dans Docker. @ServiceConnection configure automatiquement le host et le port pour Spring.

@SpringBootTest
@Testcontainers
class SortedSetFeaturesTest {

    @Container
    @ServiceConnection(name = "redis")
    static GenericContainer<?> redis =
            new GenericContainer<>("redis:7-alpine").withExposedPorts(6379);

    @Autowired LeaderboardService leaderboard;
    @Autowired JobQueue jobQueue;
    @Autowired SlidingWindowRateLimiter limiter;
    @Autowired StringRedisTemplate template;

    @BeforeEach
    void flush() {
        template.getConnectionFactory().getConnection().serverCommands().flushAll();
    }

    @Test
    void leaderboardOrdersByScoreDescending() {
        leaderboard.addPoints("alice", 120);
        leaderboard.addPoints("bob", 95);
        leaderboard.addPoints("bob", 60);

        assertThat(leaderboard.top(2))
                .extracting(PlayerScore::player)
                .containsExactly("bob", "alice");
        assertThat(leaderboard.rankOf("alice")).contains(2L);
        assertThat(leaderboard.rankOf("nobody")).isEmpty();
    }

    @Test
    void higherPriorityJobComesFirst() {
        jobQueue.enqueue("newsletter", 5);
        jobQueue.enqueue("password-reset", 0);

        assertThat(jobQueue.poll()).contains("password-reset");
        assertThat(jobQueue.poll()).contains("newsletter");
        assertThat(jobQueue.poll()).isEmpty();
    }

    @Test
    void rateLimiterRejectsAfterLimit() {
        Duration window = Duration.ofSeconds(10);

        assertThat(limiter.tryAcquire("c-42", 3, window)).isTrue();
        assertThat(limiter.tryAcquire("c-42", 3, window)).isTrue();
        assertThat(limiter.tryAcquire("c-42", 3, window)).isTrue();
        assertThat(limiter.tryAcquire("c-42", 3, window)).isFalse();
        assertThat(limiter.tryAcquire("c-99", 3, window)).isTrue();
    }
}

Le dernier test vérifie deux choses : la quatrième requête de c-42 est rejetée, et la limite est calculée séparément pour chaque client. Pour tester le “glissement” de la fenêtre, vous pouvez injecter une Clock ajustable (par exemple une classe MutableClock que vous écrivez), avancer le temps de 10 secondes puis rappeler tryAcquire.

7. Quand ne pas utiliser sorted set

• Besoin de durabilité comme un message queue : ZSET n’a pas d’acknowledgement, de consumer group ou de retry. Redis Streams, RabbitMQ ou Kafka sont plus appropriés.
• Un ZSET trop volumineux : des dizaines de millions d’éléments dans une clé causent un “big key”. Les opérations DEL, migration de slot ou replication sont toutes lentes. Vous devriez diviser la clé par saison, par région, ou par jour (leaderboard:2026-10).
• Le score doit être précis : par exemple la monnaie avec plusieurs chiffres décimaux. double a des erreurs d’arrondi, vous devriez stocker l’unité la plus petite (centime, cent) sous forme d’entier.
• Un compte approximatif suffit : si vous avez juste besoin de savoir “environ combien d’utilisateurs uniques”, HyperLogLog consomme beaucoup moins de mémoire.

8. Conclusion

Sorted set résout de nombreux problèmes en choisissant simplement le bon score. Avec leaderboard, le score est les points et vous utilisez ZINCRBY, ZREVRANGE, ZREVRANK. Avec priority queue, le score est la priorité mélangée avec un timestamp, combinée avec ZPOPMIN/BZPOPMIN. Avec delayed queue, le score est le moment d’exécution. Avec rate limiter, le score est le moment de chaque requête.

Deux choses à retenir. Premièrement, chaque séquence d’opérations “lire puis écrire” doit être encapsulée dans une commande atomique ou un script Lua. Deuxièmement, vérifiez toujours les limites de précision de double quand vous fusionnez plusieurs valeurs dans un score. Maîtriser ces deux points, vous pouvez utiliser ZSET avec confiance dans un système en production.