Distributed Locks mit dem Redlock-Algorithmus

1. Warum verteilte Locks noetig sind

Ein Distributed Lock loest ein Problem, das in Single-Server-Anwendungen trivial ist: sicherstellen, dass zu jedem Zeitpunkt nur ein Prozess eine kritische Sektion betritt, wenn diese Prozesse auf unterschiedlichen Maschinen laufen. Ein lokales Mutex hilft hier nicht, weil es nur innerhalb eines Prozessraums wirkt. Typische Szenarien sind das Verhindern doppelter Cron-Jobs auf mehreren Applikationsservern, das Serialisieren von Zahlungsabwicklung fuer denselben Warenkorb, oder das Koordinieren, welcher Worker eine bestimmte Batch-Verarbeitung uebernimmt.

Redis eignet sich fuer Distributed Locks, weil es einen zentralen, schnellen und atomaren Speicherpunkt bietet, auf den alle Prozesse zugreifen koennen. Die Grundoperation ist denkbar simpel: ein Schluessel wird gesetzt, wenn er noch nicht existiert, und traegt eine Ablaufzeit, damit ein abgestuerzter Prozess die Sperre nicht fuer immer haelt. Die Schwierigkeit liegt nicht in dieser Grundoperation, sondern in den Randfaellen, die bei naiver Umsetzung zu doppelten Ausfuehrungen fuehren koennen, obwohl der Lock scheinbar korrekt funktioniert.

Dieser Artikel baut Distributed Locks von der einfachen Single-Instance-Sperre ueber den Redlock-Algorithmus fuer mehrere unabhaengige Redis-Instanzen bis zur kritischen Einordnung auf, wann welches Verfahren angemessen ist und wo zusaetzliche Absicherung wie Fencing Tokens notwendig wird.

2. SET NX PX als Grundbaustein

Die Basis jedes Redis-basierten Distributed Lock ist der Befehl SET key value NX PX milliseconds. Die Option NX sorgt dafuer, dass der Schluessel nur gesetzt wird, wenn er nicht bereits existiert, was das atomare Erwerben der Sperre garantiert. Die Option PX setzt eine Ablaufzeit in Millisekunden, sodass die Sperre auch dann freigegeben wird, wenn der haltende Prozess abstuerzt, bevor er sie explizit freigibt. Als Wert traegt der Schluessel eine zufaellige, eindeutige ID, die den aktuellen Besitzer der Sperre identifiziert.

Diese eindeutige ID ist kein Detail, sondern die Voraussetzung fuer korrektes Entsperren. Ohne sie kann ein Prozess versehentlich die Sperre eines anderen Prozesses aufheben, wenn seine eigene Sperre bereits abgelaufen ist. Das Distributed Lock-Muster mit SET NX PX ist fuer eine einzelne Redis-Instanz ausreichend robust, solange man beim Entsperren die Besitzer-ID prueft, bevor der Schluessel geloescht wird.

# Acquire a lock: only succeeds if the key does not exist yet
redis-cli> SET order-lock:4711 "worker-a3f9c2" NX PX 30000
OK

# A second worker trying the same lock fails immediately
redis-cli> SET order-lock:4711 "worker-b7e1d4" NX PX 30000
(nil)

# The lock auto-expires after 30 seconds if never released,
# preventing a crashed worker from holding it forever
redis-cli> TTL order-lock:4711
(integer) 27

3. Race Conditions beim naiven Entsperren

Der klassische Fehler bei Distributed Locks ist das Entsperren mit einem simplen DEL key, ohne vorher zu pruefen, ob der aufrufende Prozess die Sperre ueberhaupt noch besitzt. Angenommen, Prozess A haelt die Sperre, wird aber durch Garbage Collection oder Netzwerklatenz so lange pausiert, dass die TTL ablaeuft. Prozess B erwirbt daraufhin dieselbe Sperre und beginnt seine kritische Sektion. Wacht Prozess A anschliessend auf und ruft sein eigenes DEL auf, loescht er die Sperre von Prozess B, obwohl er sie selbst laengst verloren hat. Ein dritter Prozess C kann die Sperre dann erwerben, waehrend B noch aktiv ist, und beide befinden sich gleichzeitig in der kritischen Sektion.

Die Loesung fuer dieses Distributed Lock-Problem ist ein Lua-Script, das Besitzer-ID-Pruefung und Loeschung atomar in einem einzigen Redis-Aufruf kombiniert. Ohne Atomaritaet zwischen GET und DEL besteht sonst wieder ein Zeitfenster, in dem ein anderer Prozess dazwischenfunkt. Dieses Muster ist der Mindeststandard fuer jedes produktive Locking mit Redis, unabhaengig davon, ob eine oder mehrere Instanzen verwendet werden.

-- unlock.lua
-- Only delete the lock if the caller still owns it
-- KEYS[1] = lock key, ARGV[1] = owner token
if redis.call("GET", KEYS[1]) == ARGV[1] then
  return redis.call("DEL", KEYS[1])
else
  return 0 -- lock was not owned by this caller anymore
end

4. Der Redlock-Algorithmus im Detail

Der Redlock-Algorithmus erweitert das Single-Instance-Lock auf mehrere unabhaengige Redis-Instanzen, typischerweise fuenf, um Ausfallsicherheit gegen den Absturz einzelner Knoten zu erreichen. Der Ablauf: der Client versucht nacheinander, dieselbe Sperre mit derselben Besitzer-ID auf allen N Instanzen zu setzen, jeweils mit kurzem Verbindungstimeout. Die Sperre gilt als erworben, wenn sie auf einer Mehrheit der Instanzen erfolgreich gesetzt wurde, also bei N=5 auf mindestens drei, und die dafuer benoetigte Gesamtzeit kleiner als die urspruengliche TTL ist.

Die verbleibende Gueltigkeitsdauer der Sperre wird als urspruengliche TTL minus der verstrichenen Erwerbszeit minus einer Sicherheitsmarge berechnet. Schlaegt der Erwerb auf der Mehrheit fehl, werden alle bereits gesetzten Sperren sofort wieder aufgehoben, um keine Ressourcen unnoetig zu blockieren. Diese Mehrheitslogik ist der Kerngedanke von Redlock: selbst wenn zwei von fuenf Instanzen ausfallen oder nicht erreichbar sind, kann die Sperre trotzdem korrekt erworben werden, solange eine Mehrheit erreichbar bleibt.

# Redlock in principle: same key and token attempted on 5 independent nodes
for host in redis-a redis-b redis-c redis-d redis-e; do
  redis-cli -h "$host" SET order-lock:4711 "worker-a3f9c2" NX PX 30000
done
# Quorum reached if at least 3 of 5 respond OK within a short timeout

# Releasing on every node regardless of which ones succeeded
for host in redis-a redis-b redis-c redis-d redis-e; do
  redis-cli -h "$host" EVAL "if redis.call('GET',KEYS[1])==ARGV[1] then return redis.call('DEL',KEYS[1]) end return 0" \
    1 order-lock:4711 "worker-a3f9c2"
done

5. Redlock Schritt fuer Schritt implementieren

Eine minimale Redlock-Implementierung iteriert ueber die konfigurierten Redis-Clients, versucht auf jedem SET NX PX mit derselben Owner-ID, und zaehlt die Erfolge. Wichtig ist ein kurzes Verbindungstimeout pro Instanz, deutlich kuerzer als die Lock-TTL, damit eine nicht erreichbare Instanz den gesamten Erwerbsprozess nicht ausbremst. Nach dem Versuch auf allen Instanzen wird geprueft, ob die Mehrheit erreicht wurde und ob die verbrauchte Zeit die TTL nicht ueberschritten hat.

Das Freigeben der Sperre erfolgt konsequent auf allen Instanzen, nicht nur auf denen, wo der Erwerb erfolgreich war, weil eine zuvor als nicht erreichbar geltende Instanz zwischenzeitlich wieder online sein und die Sperre halten koennte. Diese Konsistenz beim Entsperren ist ein haeufig uebersehener Teil korrekter Redlock-Implementierungen.

<?php
declare(strict_types=1);

final class Redlock
{
    /** @param \Redis[] $instances Independent Redis instances, typically 5 */
    public function __construct(
        private readonly array $instances,
        private readonly int $connectTimeoutMs = 50
    ) {
    }

    /**
     * Attempts to acquire a lock across a majority of instances.
     * Returns the owner token on success, or null on failure.
     */
    public function acquire(string $resource, int $ttlMs): ?string
    {
        $token = bin2hex(random_bytes(16));
        $quorum = (int) (count($this->instances) / 2) + 1;
        $start = microtime(true);
        $acquired = 0;

        foreach ($this->instances as $redis) {
            try {
                if ($redis->set($resource, $token, ['NX', 'PX' => $ttlMs])) {
                    $acquired++;
                }
            } catch (\RedisException) {
                // Unreachable instance counts as a failed acquisition
            }
        }

        $elapsedMs = (microtime(true) - $start) * 1000;
        $validityMs = $ttlMs - $elapsedMs - 10; // safety margin

        if ($acquired >= $quorum && $validityMs > 0) {
            return $token;
        }

        $this->release($resource, $token);
        return null;
    }

    /** Releases the lock on every instance, regardless of prior success. */
    public function release(string $resource, string $token): void
    {
        $script = <<<'LUA'
        if redis.call("GET", KEYS[1]) == ARGV[1] then
          return redis.call("DEL", KEYS[1])
        end
        return 0
        LUA;

        foreach ($this->instances as $redis) {
            try {
                $redis->eval($script, [$resource, $token], 1);
            } catch (\RedisException) {
                // Ignore unreachable instances during release
            }
        }
    }
}

6. Kleppmanns Kritik an Redlock

Martin Kleppmann hat 2016 in seiner vielzitierten Analyse zwei fundamentale Probleme an Redlock aufgezeigt. Erstens: Redlock verlaesst sich auf synchronisierte Uhren und begrenzte Prozesspausen, um Sicherheit zu garantieren. Ein Garbage-Collection-Stop, ein Netzwerk-Timeout oder ein OS-Scheduling-Delay kann jedoch dazu fuehren, dass ein Prozess deutlich laenger pausiert als die TTL der Sperre, ohne dass er das selbst bemerkt. Wacht der Prozess auf, glaubt er faelschlich, die Sperre noch zu halten, obwohl sie laengst an einen anderen Prozess vergeben wurde. Redlock kann diese Art von Fehler nicht ausschliessen, weil es kein System zur Erkennung von Prozesspausen gibt.

Zweitens argumentiert Kleppmann, dass Redlock weder ein reines Effizienz-Lock noch ein echtes Korrektheits-Lock im Sinne verteilter Konsenssysteme wie ZooKeeper oder etcd ist. Fuer reine Effizienz, also das Vermeiden doppelter, aber ungefaehrlicher Arbeit, ist ein einfacheres Single-Instance-Lock oft ausreichend und weniger komplex. Fuer echte Korrektheitsgarantien, etwa beim Schreiben in ein Dateisystem oder bei finanziellen Transaktionen, empfiehlt Kleppmann Systeme mit expliziten Fencing Tokens statt reinem Redlock. Diese Kritik bedeutet nicht, dass Redlock nutzlos ist, sondern dass sein Einsatzbereich bewusst eingegrenzt werden muss.

7. Fencing Tokens als Ergaenzung

Ein Fencing Token ist eine monoton steigende Zahl, die bei jedem Lock-Erwerb vom Lock-Service ausgegeben wird und bei jedem Zugriff auf die geschuetzte Ressource mitgeschickt wird. Die geschuetzte Ressource, etwa ein Speichersystem oder eine Datenbank, akzeptiert nur Schreibvorgaenge mit einem Token, das hoeher ist als das zuletzt gesehene. Wacht ein pausierter Prozess auf und versucht mit einem veralteten, niedrigeren Token zu schreiben, lehnt die Ressource den Zugriff ab, selbst wenn der Prozess faelschlich glaubt, die Sperre noch zu besitzen.

Dieses Muster loest genau das Problem, das Kleppmann an Distributed Locks ohne Fencing kritisiert: es verlagert die Korrektheitsgarantie vom Lock selbst auf die Ressource, die geschuetzt werden soll. Redis unterstuetzt Fencing Tokens nicht nativ, aber ein einfacher INCR-Zaehler pro Ressource kann als Tokenquelle dienen, solange die geschuetzte Ressource die Pruefung der Reihenfolge tatsaechlich implementiert. Ohne diese Pruefung auf Ressourcenseite bleibt jedes Locking-Schema, egal wie ausgefeilt, letztlich nur eine Optimierung fuer den Normalfall.

8. Wann ein einfaches Lock ausreicht

Nicht jede Anwendung braucht die Komplexitaet von Redlock ueber fuenf Instanzen. Wenn eine kurzzeitige Doppelverarbeitung tolerierbar ist, etwa weil die eigentliche Operation idempotent ist oder ein nachgelagerter Deduplizierungsschritt existiert, reicht ein einfaches Single-Instance-Lock mit SET NX PX vollkommen aus. Typisches Beispiel: ein taeglicher Reporting-Job, der auf mehreren Applikationsservern per Cron gestartet wird, aber nur einmal laufen soll. Laeuft er im seltenen Fehlerfall doch zweimal, entsteht hoechstens doppelte Rechenzeit, kein Datenschaden.

Der Umstieg auf Redlock lohnt sich erst, wenn die Ausfallsicherheit einer einzelnen Redis-Instanz nicht ausreicht, etwa weil die Sperre auch dann noch korrekt funktionieren muss, wenn ein Redis-Knoten ausfaellt. Fuer Anwendungsfaelle, bei denen doppelte Ausfuehrung echten Schaden anrichtet, etwa doppelte Zahlungsfreigaben, ist selbst Redlock allein laut Kleppmann nicht ausreichend, hier ist die Kombination mit Fencing Tokens oder ein Wechsel zu einem Konsenssystem die richtige Wahl.

9. Praxis: Bibliotheken und Betriebserfahrung

In der Praxis implementiert kaum jemand Redlock komplett von Grund auf, sondern nutzt etablierte Bibliotheken wie Redisson fuer Java, redlock-rb fuer Ruby oder php-redlock fuer PHP, die Retry-Logik, Fencing-Unterstuetzung und Watchdog-Mechanismen zur automatischen TTL-Verlaengerung bereits mitbringen. Ein Watchdog verlaengert die Sperre periodisch, solange der haltende Prozess noch aktiv ist, und reduziert damit das Risiko, dass eine legitime, aber laenger laufende Operation durch eine zu kurze TTL unterbrochen wird.

Beim Betrieb von Redlock in Produktion zeigt sich, dass die fuenf Instanzen wirklich unabhaengig sein muessen, nicht nur als Replikas eines Primary-Setups. Werden sie ueber Sentinel oder Cluster mit automatischem Failover betrieben, kann ein Failover mitten im Lock-Zyklus zu genau den Inkonsistenzen fuehren, die Redlock eigentlich verhindern soll, weil ein neuer Primary die auf dem alten Primary gesetzte Sperre nicht kennt. Fuer echte Unabhaengigkeit sollten die Instanzen auf getrennter Hardware ohne Replikation zueinander laufen.

# Watchdog pattern: periodically extend TTL while the holder is alive
while kill -0 "$WORKER_PID" 2>/dev/null; do
  redis-cli EVAL "if redis.call('GET',KEYS[1])==ARGV[1] then return redis.call('PEXPIRE',KEYS[1],ARGV[2]) end return 0" \
    1 order-lock:4711 "worker-a3f9c2" 30000
  sleep 10
done

# Checking independence: instances must not be replicas of each other
redis-cli -h redis-a INFO replication | grep role
role:master

10. Zusammenfassung

Distributed Locks mit Redis reichen von der einfachen SET-NX-PX-Sperre auf einer Instanz bis zum Redlock-Algorithmus ueber mehrere unabhaengige Instanzen. Fuer die meisten Anwendungsfaelle mit toleranter Fehlerkonsequenz reicht das einfache Lock mit korrekter Besitzer-Pruefung beim Entsperren vollkommen aus. Redlock erhoeht die Ausfallsicherheit, loest aber laut Kleppmanns Analyse nicht das grundsaetzliche Problem von Prozesspausen und Uhrendrift, das jedem zeitbasierten Lock innewohnt.

Wo echte Korrektheit erforderlich ist, etwa bei kritischen Schreibvorgaengen auf gemeinsam genutzten Ressourcen, gehoert ein Fencing Token dazu, das die Reihenfolge auf Seiten der Ressource selbst durchsetzt. Die Entscheidung zwischen einfachem Lock, Redlock und einem echten Konsenssystem wie ZooKeeper sollte auf Basis der tatsaechlichen Schadenshoehe einer doppelten Ausfuehrung getroffen werden, nicht auf Basis der theoretisch hoechsten verfuegbaren Absicherung.

11. FAQ: Distributed Locks mit Redlock