Redlock: Verteilte Locks über mehrere Redis-Knoten

1. Übersicht

Wenn mehrere Instanzen eines Service dieselbe Ressource verarbeiten, zum Beispiel den Bestand für eine Order reduzieren, brauchst du einen distributed lock. Ein Lock auf einem einzigen Redis-Knoten ist einfach, aber wenn dieser Knoten ausfällt, ist der Lock weg. Redlock ist ein Algorithmus, den der Redis-Autor (antirez) vorgeschlagen hat, um Locks über mehrere unabhängige Redis-Knoten zu erwerben.

Dieser Artikel zeigt, wie Redlock funktioniert, wie du es mit Jedis selbst implementierst und wie du Tests mit Testcontainers schreibst. Der letzte Teil analysiert die Kontroverse zwischen Martin Kleppmann und antirez. Nach dem Lesen wirst du wissen, wann Redlock ausreichend ist und wann du ein anderes Tool wählen solltest.

2. Warum ein einzelner Redis-Knoten nicht ausreicht

Ein einfacher Lock auf einem Knoten benötigt nur einen Befehl:

SET lock:order:42 "c3a1-uuid" NX PX 30000

NX bedeutet, dass nur gesetzt wird, wenn der Schlüssel nicht existiert. PX 30000 setzt eine TTL von 30 Sekunden, damit der Lock automatisch abläuft, wenn der Client abstürzt. Der Wert ist ein zufälliges Token, das sicherstellt, dass nur der Client, der den Lock hält, ihn löschen darf.

Das Problem liegt in der Verfügbarkeit. Wenn du master–replica-Replikation verwendest, kann folgendes Szenario auftreten:

1. Client A erwirbt den Lock auf dem master.
2. Der master fällt aus, bevor der Schlüssel zum replica repliziert wird (Redis-Replikation ist asynchron).
3. Das replica wird zum neuen master befördert, aber der Lock-Schlüssel ist dort nicht vorhanden.
4. Client B kann sich denselben Lock erwirben.

Jetzt halten sowohl A als auch B den Lock. Redlock wurde entwickelt, um dieses Szenario zu handhaben.

3. Der Redlock-Algorithmus

Redlock verwendet N unabhängige Redis-Knoten ohne Replikation und ohne Clustering untereinander. Üblicherweise N = 5. Der Client erwirbt den Lock in folgenden Schritten:

1. Notiere die Startzeit.
2. Sende SET key token NX PX ttl nacheinander an alle N Knoten. Jeder Request hat einen kurzen Timeout (mehrere Zehner Millisekunden), damit ein ausgefallener Knoten den Client nicht blockiert.
3. Berechne die verstrichene Zeit. Der Lock gilt als erfolgreich erworben, wenn beide Bedingungen erfüllt sind:
   • erfolgreich auf mindestens N/2 + 1 Knoten (quorum) erworben,
   • die verstrichene Zeit kleiner als die TTL ist.
4. Die tatsächliche Gültigkeitsdauer des Locks ist ttl - elapsed - drift, wobei drift Uhrenabweichungen zwischen den Knoten kompensiert.
5. Bei Fehler sendet der Client ein Unlock-Kommando an alle Knoten, auch an die, von denen er denkt, dass er den Lock nicht erworben hat.

Die Kernidee ist, dass zwei Clients nicht gleichzeitig die Mehrheit der Knoten kontrollieren können.

4. Redlock mit Jedis implementieren

4.1. Abhängigkeit

<dependency>
    <groupId>redis.clients</groupId>
    <artifactId>jedis</artifactId>
    <version>5.1.0</version>
</dependency>

4.2. Die Redlock-Klasse

import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;
import redis.clients.jedis.exceptions.JedisException;
import redis.clients.jedis.params.SetParams;

import java.util.List;
import java.util.Optional;
import java.util.UUID;

public class Redlock {

    private static final String UNLOCK_SCRIPT = """
        if redis.call('get', KEYS[1]) == ARGV[1] then
            return redis.call('del', KEYS[1])
        else
            return 0
        end
        """;
    private static final double CLOCK_DRIFT_FACTOR = 0.01;

    private final List<JedisPool> nodes;
    private final int quorum;

    public Redlock(List<JedisPool> nodes) {
        this.nodes = nodes;
        this.quorum = nodes.size() / 2 + 1;
    }

    public Optional<LockHandle> tryLock(String resource, long ttlMillis) {
        String token = UUID.randomUUID().toString();
        long start = System.nanoTime();

        int acquired = 0;
        for (JedisPool pool : nodes) {
            if (lockInstance(pool, resource, token, ttlMillis)) {
                acquired++;
            }
        }

        long elapsed = (System.nanoTime() - start) / 1_000_000;
        long drift = (long) (ttlMillis * CLOCK_DRIFT_FACTOR) + 2;
        long validity = ttlMillis - elapsed - drift;

        if (acquired >= quorum && validity > 0) {
            return Optional.of(new LockHandle(resource, token, validity));
        }
        unlockAll(resource, token);
        return Optional.empty();
    }

    public void unlock(LockHandle handle) {
        unlockAll(handle.resource(), handle.token());
    }

    private boolean lockInstance(JedisPool pool, String resource, String token, long ttl) {
        try (Jedis jedis = pool.getResource()) {
            return "OK".equals(jedis.set(resource, token, SetParams.setParams().nx().px(ttl)));
        } catch (JedisException e) {
            return false; // Knoten ausgefallen oder Timeout: gilt als nicht erworben
        }
    }

    private void unlockAll(String resource, String token) {
        for (JedisPool pool : nodes) {
            try (Jedis jedis = pool.getResource()) {
                jedis.eval(UNLOCK_SCRIPT, List.of(resource), List.of(token));
            } catch (JedisException ignored) {
                // Wenn der Knoten nicht antwortet, läuft der Schlüssel automatisch ab
            }
        }
    }

    public record LockHandle(String resource, String token, long validityMillis) {}
}

Wichtige Punkte:

• quorum = N/2 + 1. Mit 3 Knoten ist das quorum 2. Mit 5 Knoten ist das quorum 3.
• lockInstance fängt Exceptions ab und gibt false zurück. Ein ausgefallener Knoten reduziert nur die Stimmen, zerstört aber nicht die ganze Operation.
• validity ist die Zeit, während der du den Lock wirklich halten darfst. Diese Zeit ist immer kleiner als die TTL.
• Unlock verwendet ein Lua-Script, damit die Operation „Token vergleichen und dann löschen” atomar abläuft. Wenn du GET und DEL mit zwei separaten Befehlen ausführst, kannst du versehentlich einen Lock löschen, den ein anderer Client gerade erworben hat.
• Bei Fehler sendet unlockAll an alle Knoten. Der Grund ist, dass ein SET-Befehl auf dem Server erfolgreich sein könnte, aber die Antwort beim Client timeout kriegt.

4.3. Knoten mit kurzem Timeout initialisieren

import redis.clients.jedis.JedisPoolConfig;

List<JedisPool> pools = List.of(
        new JedisPool(new JedisPoolConfig(), "redis-1", 6379, 50),
        new JedisPool(new JedisPoolConfig(), "redis-2", 6379, 50),
        new JedisPool(new JedisPoolConfig(), "redis-3", 6379, 50));
Redlock redlock = new Redlock(pools);

Der letzte Parameter ist das Timeout von 50 ms. Wenn du das Standard-Timeout von 2 Sekunden verwendest, könnte ein hängender Knoten fast die gesamte TTL des Locks aufbrauchen.

4.4. Verwendung in InventoryService

public class InventoryService {

    private final Redlock redlock;
    private final InventoryRepository repository;

    public InventoryService(Redlock redlock, InventoryRepository repository) {
        this.redlock = redlock;
        this.repository = repository;
    }

    public boolean reserve(String sku, int quantity) {
        var handle = redlock.tryLock("lock:sku:" + sku, 10_000);
        if (handle.isEmpty()) {
            return false; // Caller sollte mit Backoff erneut versuchen
        }
        try {
            int stock = repository.findStock(sku);
            if (stock < quantity) return false;
            repository.updateStock(sku, stock - quantity);
            return true;
        } finally {
            redlock.unlock(handle.get());
        }
    }
}

Das Unlock muss immer in finally stehen. Der Code innerhalb des Lock-Bereichs muss innerhalb von validityMillis abgeschlossen sein. Wenn die Operation länger dauern kann, brauchst du einen Mechanismus zur Lock-Verlängerung (Watchdog) oder musst die Arbeit aufteilen.

5. Tests mit Testcontainers schreiben

<dependency>
    <groupId>org.testcontainers</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>1.20.1</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

@Testcontainers
class RedlockTest {

    @Container static GenericContainer<?> r1 = redis();
    @Container static GenericContainer<?> r2 = redis();
    @Container static GenericContainer<?> r3 = redis();

    static GenericContainer<?> redis() {
        return new GenericContainer<>("redis:7-alpine").withExposedPorts(6379);
    }

    static Redlock newClient() {
        return new Redlock(Stream.of(r1, r2, r3)
                .map(c -> new JedisPool(new JedisPoolConfig(),
                        c.getHost(), c.getMappedPort(6379), 200))
                .toList());
    }

    @Test
    void secondClientCannotAcquireWhileFirstHoldsLock() {
        Redlock clientA = newClient();
        Redlock clientB = newClient();

        var lockA = clientA.tryLock("lock:order:42", 5_000);
        var lockB = clientB.tryLock("lock:order:42", 5_000);

        assertThat(lockA).isPresent();
        assertThat(lockA.get().validityMillis()).isLessThan(5_000);
        assertThat(lockB).isEmpty();

        clientA.unlock(lockA.get());
        assertThat(clientB.tryLock("lock:order:42", 5_000)).isPresent();
    }

    @Test
    void stillAcquiresWhenOneNodeIsDown() {
        Redlock client = newClient();
        r3.stop();

        assertThat(client.tryLock("lock:order:99", 5_000)).isPresent();
    }
}

Der erste Test überprüft die gegenseitige Ausschließlichkeit: B schlägt fehl, während A den Lock hält, und kann ihn sofort nach dem Unlock von A erwerben. Der zweite Test zeigt, dass Redlock auch bei Ausfall von 1 von 3 Knoten funktioniert, da die verbleibenden 2 Knoten das quorum erfüllen. Dieser Test stoppt den Container vollständig, daher solltest du ihn am Ende platzieren oder in eine separate Klasse verschieben.

6. Was ist mit Redisson?

In der Praxis schreiben wenige Leute Redlock selbst. Redisson bot einst RedissonRedLock an, das mehrere RLock von unabhängigen Clients akzeptiert.

Hinweis: In neueren Redisson-Versionen sind RedissonRedLock und RedissonMultiLock veraltet markiert. Redisson empfiehlt die Verwendung der regulären RLock, die einen Watchdog mit automatischer Verlängerung hat und zu Replikas synchronisieren kann, oder RFencedLock, wenn du ein Fencing-Token brauchst. Überprüfe deine Redisson-Version, bevor du eine API wählst.

Das auch die populärste Bibliothek Redlock aufgegeben hat, führt uns zu der Kontroverse.

7. Kontroverse: Kleppmann vs antirez

7.1. Martin Kleppmans Argument

Kleppmann, Autor von Designing Data-Intensive Applications, zeigt, dass Redlock für Probleme, die Korrektheit erfordern, nicht sicher ist. Es gibt zwei Hauptgründe.

Process Pause. Betrachte folgendes Szenario:

t=0     Client A erwirbt den Lock (TTL 10s)
t=1     A wird durch GC Stop-the-World für 15 Sekunden unterbrochen
t=10    Lock läuft auf allen Knoten ab
t=11    Client B erwirbt den Lock, schreibt Daten in die DB
t=16    A wacht auf, denkt immer noch, dass es den Lock hält, überschreibt Bs Daten

Kein auf TTL basierender Lock-Algorithmus kann dieses Szenario verhindern. Das Überprüfen von validity unmittelbar vor dem Schreiben hilft auch nicht, da die Pause direkt nach der Überprüfung auftreten kann. Pause wird nicht nur durch GC verursacht. Page Faults, VM-Migration oder verspätete Netzwerkpakete haben die gleiche Auswirkung.

Abhängigkeit von der Uhr. Redlock geht davon aus, dass die Uhren auf den Knoten ungefähr gleichmäßig laufen. Wenn die Uhr eines Knotens springt, z. B. durch aggressives NTP-Tuning oder manuelle Zeiteinstellung durch einen Admin, können die Schlüssel auf diesem Knoten vorzeitig ablaufen. Konkretes Szenario mit 5 Knoten:

A erwirbt den Lock auf Knoten 1, 2, 3
Die Uhr von Knoten 3 springt nach vorne, Schlüssel auf Knoten 3 läuft ab
B erwirbt den Lock auf Knoten 3, 4, 5
=> Sowohl A als auch B halten das quorum

Kleppmans Schlussfolgerung: Für Sicherheit brauchst du ein Fencing-Token, also eine monoton steigende Nummer zusammen mit dem Lock. Redlock stellt diese Nummer nicht zur Verfügung, da sein Token eine zufällige Zeichenfolge ist.

7.2. Wie sieht ein Fencing-Token aus?

Die Idee ist, dass der Storage Schreibvorgänge mit alten Tokens selbst ablehnt:

public class FencedInventoryRepository {

    private final JdbcTemplate jdbc;

    public FencedInventoryRepository(JdbcTemplate jdbc) {
        this.jdbc = jdbc;
    }

    public boolean updateStock(String sku, int newStock, long fencingToken) {
        int rows = jdbc.update("""
                UPDATE inventory SET stock = ?, last_token = ?
                WHERE sku = ? AND last_token < ?
                """, newStock, fencingToken, sku, fencingToken);
        return rows == 1;
    }
}

Anwendung auf das GC-Szenario oben: B schreibt mit Token 34, A wacht auf und schreibt mit Token 33. Das UPDATE von A beeinflusst 0 Zeilen, daher bleiben Bs Daten erhalten. Der Schlüsselpunkt ist, dass es der Storage, nicht der Lock, ist, der Korrektheit garantiert. Das Token muss von einem System mit Consensus stammen, wie ZooKeeper (zxid) oder etcd (revision).

7.3. Die Antwort von antirez

antirez antwortet mit folgenden Hauptpunkten:

• Wenn der Storage bereits compare-and-set-artiges Token-Checking unterstützt, kannst du das zufällige Token zum Überprüfen verwenden, und dann ist ein Lock nahezu überflüssig.
• Redlock hat einen Zeitmessungsschritt nach dem Locking, daher werden Netzwerkverzögerungen während des Locking erkannt. Eine Pause nach diesem Schritt unterliegt tatsächlich jedem TTL-basierten Lock.
• Die Annahmen über die Uhr sind vernünftig, wenn du es richtig betreibst: Lass NTP nicht plötzlich die Zeit springen (verwende Slew-Modus) und stelle die Zeit nicht manuell ein.

Bisher hat keine Seite wirklich “gewonnen”. Allerdings stimmt die Community Kleppmans Klassifizierung zu, die im nächsten Abschnitt dargelegt wird.

8. Wann man es verwenden sollte und wann nicht

Frag dich selbst: Was passiert, wenn zwei Clients gleichzeitig einen Lock halten?

• Efficiency Lock (um Duplikate zu vermeiden): doppelte Report-E-Mails versenden, dieselbe Cron-Job zweimal ausführen, Cache neu berechnen. Gelegentliche Duplikate sind akzeptabel. In diesem Fall reicht ein einzelner Redis-Knoten mit SET NX PX aus. Redlock kostet 3–5 mal mehr Infrastruktur ohne nennenswerte Verbesserung.
• Correctness Lock (Fehler beschädigt Daten): Geldabzüge, Bestandsreduktion, Rechnungsnummernvergabe. Redlock reicht nicht aus. Du solltest etcd oder ZooKeeper mit Fencing-Token verwenden, oder besser noch, die Beschränkungen in die Datenbank verlagern mit optimistic locking (@Version in JPA), SELECT ... FOR UPDATE oder unique constraints.

Hinweis: Häufige Fehler bei der Verwendung von Redlock:

• Redis Cluster oder master–replica als Redlock-„Knoten” verwenden. Knoten müssen vollständig unabhängig sein.
• Connection Timeout auf Standard-Länge belassen.
• Mit DEL statt Lua-Script mit Token-Überprüfung unlocking durchführen.
• Persistence aktivieren, aber fsync=always nicht konfigurieren, oder Node-Neustarts nicht verzögern. Ein Node-Neustart und Schlüsselverlust können dazu führen, dass zwei Clients das quorum erreichen. antirez empfiehlt, dass neu gestartete Knoten mindestens so lange warten wie die längste TTL, bevor sie wieder teilnehmen.

9. Fazit

Redlock erwirbt Locks über die Mehrheit von N unabhängigen Redis-Knoten und berechnet die Gültigkeitsdauer, um Netzwerkverzögerungen und Uhrenabweichungen zu kompensieren. Du hast gesehen, wie man es mit Jedis implementiert, wie man sicher mit Lua-Scripts unlocked und wie man mit Testcontainers testet.

Redlock basiert immer noch auf TTL und Uhren, daher kann es Process Pauses oder Uhrensprünge nicht verhindern. Daher reicht für Locks, die nur Duplikate vermeiden, ein einzelner Redis-Knoten aus. Für Locks, die Datenkorrektheit schützen, brauchst du Fencing-Tokens von einem Consensus-System oder musst die Datenbank die Beschränkungen selbst verwalten.