Redis Sorted Set: Leaderboard, Prioritätswarteschlange und Sliding Window

1. Übersicht

Sorted Set (ZSET) ist die flexibelste Datenstruktur von Redis. Jedes Element (Member) hat einen Score-Wert, und Redis hält sie immer nach dem Score sortiert. Dieser Artikel nutzt ZSET, um drei häufige Probleme zu lösen: Leaderboard, Prioritätswarteschlange/verspätete Aufgaben und Sliding-Window-Rate-Limiter. Alles ist in Java 21 mit Spring Boot 3.x geschrieben. Danach weißt du, wie man den Score für jedes Problem richtig wählt und vermeidest die üblichen Race-Condition-Fehler.

2. Wie funktioniert Sorted Set

Ein ZSET hat folgende Eigenschaften:

• Member ist eindeutig. ZADD eines existierenden Member aktualisiert nur seinen Score.
• Score ist eine Dezimalzahl (double). Member mit gleichem Score werden lexikographisch nach dem Member-Namen sortiert.
• Hinzufügen, Löschen, Aktualisieren und Rang abrufen haben alle Zeitkomplexität O(log N). Ein Bereich von Elementen abrufen kostet O(log N + M), wobei M die Anzahl der zurückgegebenen Elemente ist.

Du kannst es schnell mit redis-cli testen:

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 gibt Elemente nach sinkendem Score zurück. ZREVRANK gibt dir die Position von bob (Zählung ab 0) in dieser Reihenfolge.

2.1. Projekt-Setup

Füge die Spring Data Redis Abhängigkeit hinzu. Die beiden Testcontainers-Abhängigkeiten werden für den Test in Abschnitt 6 verwendet:

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

Konfiguriere die Verbindung:

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

Spring Boot erstellt automatisch einen Bean StringRedisTemplate. Alle ZSET-Operationen laufen über opsForZSet().

3. Leaderboard

Aufgabenstellung: Ein Spiel vergibt Punkte an Spieler, du musst die Top N abrufen und die Position eines beliebigen Spielers. Hier ist der Score einfach die Punkte, und der Member ist die Spieler-ID.

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);
    }
}

Erklärung der einzelnen Teile:

• incrementScore entspricht dem ZINCRBY-Befehl. Dieser Befehl ist atomar. Falls der Member noch nicht existiert, behandelt Redis den anfänglichen Score als 0. Du musst nicht den alten Wert lesen, addieren und dann zurückschreiben, daher gibt es keine Race Condition, wenn mehrere Anfragen gleichzeitig Punkte für eine Person hinzufügen.
• reverseRangeWithScores(KEY, 0, n - 1) entspricht ZREVRANGE ... WITHSCORES. Der End-Index ist inklusiv, daher ist Top 10 = 0..9.
• reverseRank gibt null zurück, wenn der Spieler nicht in der Tabelle ist. Wir addieren 1, damit die Rangposition bei 1 beginnt, was benutzerfreundlicher ist.

Zum Testen:

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. Umgang mit gleichen Scores

Wenn zwei Personen den gleichen Punktestand haben, sortiert Redis sie nach dem Member-Namen. Mit ZREVRANGE ist die lexikographische Reihenfolge rückwärts, daher kommt zoe vor anna. Dieses Ergebnis ist selten das, was du geschäftlich möchtest. Falls du willst, dass derjenige, der den Punkt zuerst erreicht hat, oben steht, kannst du die Zeit in den Dezimalteil des Scores codieren:

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;
}

Wer den Punkt früher erreicht hat, hat einen kleineren now-Wert, daher größeren tieBreak und wird höher eingestuft. Beim Anzeigen kannst du Math.floor(score) nehmen, um die echten Punkte zu erhalten.

Hinweis: Score ist ein double und kann Ganzzahlen nur bis 2^53 (etwa 9×10^15) genau darstellen. Wenn du mehrere Werte in einen Score codierst, musst du vorher die Größenordnung berechnen, um Genauigkeitsverlust zu vermeiden. Mit dem obigen Verfahren sollten Punkte unter ein paar Millionen liegen. Außerdem funktioniert dieser Ansatz nicht mit incrementScore, da jede Addition auch den Dezimalteil kumuliert.

4. Prioritätswarteschlange und verspätete Warteschlange

4.1. Priority Queue

Dieses Mal ist der Score die Priorität: je kleinere Zahl, desto höher die Priorität. Damit Jobs mit gleicher Priorität noch in FIFO-Reihenfolge herauskommen, codieren wir noch den Zeitstempel in den 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);
    }
}

Hauptpunkte:

• priority * 1e13 + millis ergibt einen Wert von maximal etwa 9,2×10^13, immer noch weit unter 2^53. Ein Job mit Priorität 0 kommt immer vor einem Job mit Priorität 1, auch wenn er später hinzugefügt wurde.
• popMin entspricht ZPOPMIN. Dieser Befehl ruft den Wert ab und löscht ihn in einem atomaren Schritt. Zwei Worker erhalten niemals denselben Job.
• popMin(key, timeout, unit) entspricht BZPOPMIN. Dieser Befehl blockiert die Verbindung, bis ein Job vorhanden ist oder die Zeit überschritten ist, sodass du das ständige Polling sparst, das CPU verbraucht.

Hinweis: BZPOPMIN hält eine Verbindung während der gesamten Wartezeit offen. Bei Lettuce mit geteilter Verbindung blockiert ein Blocking-Befehl auch andere Befehle. Du solltest einen Connection Pool aktivieren (commons-pool2 hinzufügen und spring.data.redis.lettuce.pool.* konfigurieren) oder eine separate Connection Factory für Worker verwenden.

4.2. Delayed Queue

Möchtest du eine Zahlungserinnerung nach 30 Minuten senden? Nutze einen Score als Zeitpunkt der Ausführung (epoch milliseconds). Worker rufen regelmäßig Jobs mit einem Score kleiner oder gleich der aktuellen Zeit ab.

Der folgende Code ist falsch: rangeByScore aufrufen und dann remove. Zwei Worker können denselben Job lesen, bevor er gelöscht wird. Wir packen beide Schritte in ein Lua-Skript, damit Redis es atomar ausführt:

@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);
    }
}

Das Skript ruft maximal einen fälligen Job ab und löscht ihn. In Lua wird return false in nil konvertiert, daher erhält die Java-Seite null. Der Worker könnte ein @Scheduled(fixedDelay = 500) sein und pollDue in einer Schleife aufrufen, bis die Warteschlange leer ist.

Hinweis: Nach dem Pop ist der Job aus Redis verschwunden. Falls der Worker abstürzt, ist der Job verloren. Wenn du at-least-once garantieren musst, verschiebe den Job in eine “processing” ZSET mit einem Deadline-Score und lösche ihn erst nach erfolgreichem Abschluss. Wenn die Anforderungen noch komplizierter sind, solltest du Redis Streams oder einen echten Message Broker in Betracht ziehen.

5. Sliding-Window-Rate-Limiter

Fixed Window (Anfragen pro Minute zählen) hat ein Problem an den Grenzen. Beispiel: 100 Anfragen um 00:59 und 100 um 01:00 passen beide durch, das sind 200 Anfragen in 2 Sekunden. Sliding Window behebt das, indem Zeitstempel jeder Anfrage in einem ZSET gespeichert werden:

1. Anfragen älter als now - window löschen (ZREMRANGEBYSCORE).
2. Verbleibende Anfragen zählen (ZCARD).
3. Falls unter dem Limit, die aktuelle Anfrage mit Score = now hinzufügen.

Alle drei Schritte müssen atomar laufen, also nutzen wir wieder 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);
    }
}

Erklärung:

• Member ist eine zufällige UUID. Falls du den Zeitstempel als Member verwendest, überschreiben zwei Anfragen in derselben Millisekunde sich gegenseitig und werden als eine gezählt.
• PEXPIRE hilft Redis, die Schlüssel von inaktiven Kunden selbst zu löschen.
• Du musst einen Clock Bean deklarieren (z.B. Clock.systemUTC()). Das Injizieren von Clock macht Tests einfacher. Falls du mehrere Anwendungsinstanzen hast, sollten ihre Uhren synchronisiert sein, oder du holst die Zeit direkt im Skript via redis.call('TIME').

Hinweis: Jede Anfrage braucht ein Element im ZSET. Mit großen Limits, z.B. 100.000 Anfragen/Stunde pro Kunde, wächst der Speicher schnell. Dann solltest du einen Sliding-Window-Counter (Schätzung aus zwei Fixed Windows) oder Token Bucket nutzen.

Im Cluster Mode wird das Skript nur Keys im gleichen Hash Slot anfassen. Die Skripte in diesem Artikel nutzen pro Aufruf nur einen Key, daher kein Problem.

6. Testing mit Testcontainers

Der untenstehende Test läuft mit echtem Redis in Docker. @ServiceConnection konfiguriert Host und Port für Spring automatisch.

@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();
    }
}

Der letzte Test überprüft zwei Dinge: Die vierte Anfrage von c-42 wird abgelehnt, und Limits werden pro Kunde berechnet. Um zu testen, dass das Fenster “rutscht”, solltest du eine Clock einfügen, die man verstellen kann (z.B. eine selbstgeschriebene MutableClock), die Zeit um 10 Sekunden vorrücken und dann erneut tryAcquire aufrufen.

7. Wann man Sorted Set nicht verwenden sollte

• Braucht Dauerhaftigkeit wie eine Message Queue: ZSET hat keine Acknowledgements, Consumer Groups oder Retries. Redis Streams, RabbitMQ oder Kafka sind besser geeignet.
• Ein ZSET wird zu groß: Millionen Elemente in einem Schlüssel sind ein “Big Key”. Operationen wie DEL, Slot-Migration oder Replikation werden langsam. Du solltest Keys nach Saison, Region oder Tag aufteilen (leaderboard:2026-10).
• Score braucht absolute Genauigkeit: z.B. Währung mit vielen Dezimalstellen. double hat Fehler, daher speichere in der kleinsten Einheit (Euro, Cent) als Ganzzahl.
• Ungefähre Zählung ist ausreichend: Falls du nur wissen musst “wie viele eindeutige Benutzer ungefähr”, verbraucht HyperLogLog viel weniger Speicher.

8. Fazit

Sorted Set löst viele Probleme nur durch die richtige Wahl des Score. Mit Leaderboard ist Score die Punkte und du nutzt ZINCRBY, ZREVRANGE, ZREVRANK. Mit Prioritätswarteschlange ist Score Priorität gepaart mit Zeitstempel, kombiniert mit ZPOPMIN/BZPOPMIN. Mit verspäteter Warteschlange ist Score der Ausführungszeitpunkt. Mit Rate Limiter ist Score der Zeitstempel jeder Anfrage.

Zwei Dinge sind zu merken. Erstens müssen alle Sequenzen von “lesen dann schreiben” in atomaren Befehlen oder Lua-Skripten verpackt sein. Zweitens immer die Genauigkeitsgrenzen des double prüfen, wenn du mehrere Werte in einen Score codierst. Mit diesen beiden Regeln kannst du Sorted Set selbstbewusst in Produktionssystemen nutzen.