🥇Lock distribuiti con Redis

Ciao, Habr!

Oggi vi presentiamo la traduzione di un complesso articolo sull'implementazione di locking distribuiti utilizzando Redis e vogliamo discutere delle prospettive di Redis come argomento. L'analisi dell'algoritmo Redlock di Martin Kleppmann, autore del libro "Applicazioni ad alta intensità di carico", è fornita qui.

Le locking distribuiti sono un primitivo molto utile, utilizzato in molti ambienti in cui diversi processi devono lavorare su risorse condivise secondo il principio dell'esclusione mutua.

Esistono diverse librerie e articoli che descrivono come implementare il DLM (gestore di locking distribuiti) utilizzando Redis, ma ogni libreria utilizza un proprio approccio e le garanzie fornite sono piuttosto deboli rispetto a ciò che può essere raggiunto tramite una progettazione leggermente più complessa.

In questo articolo cercheremo di descrivere un algoritmo convenzionale, dimostrando come implementare locking distribuiti utilizzando Redis. Parleremo dell'algoritmo chiamato Redlock, implementa un gestore di blocchi distribuiti e, a nostro avviso, questo algoritmo è più sicuro rispetto all'approccio tradizionale con un'unica istanza. Speriamo che la comunità lo analizzi, fornisca un riscontro e lo utilizzi come punto di partenza per implementare progetti più complessi o alternativi.

Implementazioni

Prima di passare alla descrizione dell'algoritmo, vorremmo fornire alcuni link a implementazioni già pronte. Queste possono essere usate come riferimento.

Redlock-rb (implementazione per Ruby). Esiste anche fork Redlock-rb, che aggiunge un pacchetto (gem) per facilitare la distribuzione, e non solo per questo.
Redlock-py (implementazione per Python).
Aioredlock (implementazione per Asyncio Python).
Redlock-php (implementazione per PHP).
PHPRedisMutex (un'altra implementazione per PHP)
cheprasov/php-redis-lock (libreria PHP per i blocchi)
Redsync (implementazione per Go).
Redisson (implementazione per Java).
Redis::DistLock (implementazione per Perl).
Redlock-cpp (implementazione per C++).
Redlock-cs (implementazione per C#/.NET).
RedLock.net (implementazione per C#/.NET). Con supporto per estensioni async e lock.
ScarletLock (implementazione per C# .NET con archiviazione dei dati configurabile)
Redlock4Net (implementazione per C# .NET)
node-redlock (implementazione per NodeJS). Include supporto per l'estensione dei lock.

Garanzie di sicurezza e disponibilità

Intendiamo modellare il nostro progetto con solo tre proprietà, che secondo noi offrono le garanzie minime necessarie per un uso efficace dei lock distribuiti.

Proprietà di sicurezza: Esclusione mutua. In un dato momento, solo un client può detenere il lock.
Proprietà di disponibilità A: Assenza di deadlock. È sempre possibile acquisire un lock, anche se il client che ha bloccato la risorsa non risponde o si trova in un'altra parte del disco.
Proprietà di disponibilità B: Resilienza agli errori. Finché la maggior parte dei nodi Redis funziona, i clienti possono acquisire e rilasciare i lock.

Perché le implementazioni basate sul ripristino da failure non sono sufficienti in questo caso
Per capire cosa intendiamo migliorare, analizziamo la situazione attuale delle maggiori librerie per lock distribuiti basate su Redis.

Il modo più semplice per bloccare una risorsa utilizzando Redis è creare una chiave nell'istanza. Di solito, la chiave viene creata con un tempo di vita limitato, questo si ottiene tramite la funzionalità expires fornita da Redis, quindi prima o poi questa chiave viene liberata (proprietà 2 nella nostra lista). Quando il client ha bisogno di liberare la risorsa, elimina la chiave.

A prima vista, questa soluzione sembra funzionare, ma c'è un problema: nella nostra architettura c'è un unico punto di guasto. Cosa succede se l'istanza principale di Redis fallisce? Aggiungiamo allora una secondaria! E la utilizzeremo se quella principale non è disponibile. Purtroppo, questa soluzione non è praticabile. In questo modo, non saremo in grado di implementare correttamente la proprietà di esclusione reciproca, necessaria per garantire la sicurezza, poiché la replicazione in Redis è asincrona.

È evidente che in questo modello si verifica una condizione di competizione:

Il client A acquisisce il blocco sull'istanza principale.
La principale fallisce prima che la registrazione nella chiave venga trasferita alla secondaria.
La secondaria viene promossa a principale.
Il client B acquisisce il blocco sulla stessa risorsa già bloccata da A. VIOLAZIONE DELLA SICUREZZA!

A volte è perfettamente normale che, in circostanze particolari, come un guasto, molti clienti possano trattenere simultaneamente un blocco. In questi casi, si può applicare una soluzione basata sulla replicazione. In altri casi, raccomandiamo la soluzione descritta in questo articolo.

Implementazione corretta con un'unica istanza

Prima di cercare di superare i limiti della configurazione con un'unica istanza, come descritto sopra, vediamo come agire correttamente in questo semplice caso, poiché tale soluzione è in realtà ammissibile in quelle applicazioni dove la condizione di gara è occasionalmente accettabile, e anche perché il blocco di una singola istanza funge da base per l'algoritmo distribuito descritto qui.

Per acquisire il blocco, procediamo come segue:

SET resource_name my_random_value NX PX 30000

Questo comando imposta la chiave solo se non esiste già (opzione NX), con una durata di 30000 millisecondi (opzione PX). Viene assegnato il valore “myrandomvalue”. Questo valore deve essere unico per tutti i clienti e tutte le richieste di blocco.
In pratica, un valore casuale viene utilizzato per rilasciare in modo sicuro il blocco, tramite uno script che comunica a Redis: elimina la chiave solo se esiste, e il valore conservato in essa è esattamente ciò che ci si aspettava. Questo si ottiene con il seguente script in Lua:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

È importante per evitare che venga rimosso un blocco impostato da un altro cliente. Ad esempio, un cliente può acquisire un blocco, poi bloccarsi durante un'operazione che richiede più tempo della durata del primo blocco (così che la scadenza della chiave può scadere), e successivamente rimuovere il blocco impostato da un altro cliente.
Usare un semplice DEL non è sicuro, poiché un cliente potrebbe rimuovere un blocco impostato da un altro cliente. Al contrario, utilizzando lo script sopra, ogni blocco è "firmato" con una stringa casuale, quindi può essere rimosso solo da quel cliente che lo ha impostato in precedenza.

Qual è la stringa casuale che dovrebbe essere? Presumo che dovrebbe essere di 20 byte da /dev/urandom, ma ci sono modi meno costosi per creare una stringa sufficientemente unica per gli scopi che hai di fronte. Ad esempio, va bene seminare RC4 da /dev/urandom e poi generare un flusso pseudo-casuale basato su di esso. Una soluzione più semplice coinvolge la combinazione del tempo Unix in risoluzione microsecondaria più l'ID del cliente; non è così sicura, ma probabilmente si adatta al livello di compiti nella maggior parte dei contesti.

Il tempo che utilizziamo come indicatore della durata di vita della chiave si chiama «tempo di scadenza del blocco». Questo valore è sia il termine oltre il quale il blocco verrà automaticamente rilasciato, sia il tempo che ha il cliente per completare l'operazione prima che un altro cliente possa, a sua volta, bloccare questa risorsa, senza violare effettivamente le garanzie di mutua esclusione. Tale garanzia è limitata solo a una certa finestra temporale che inizia dal momento dell'acquisto del blocco.

Abbiamo quindi discusso un buon modo di acquisire e rilasciare un blocco. Il sistema (nel caso di un sistema non distribuito, composto da un'unica istanza sempre disponibile) è sicuro. Espandiamo questo concetto a un sistema distribuito, nel quale non abbiamo tali garanzie.

Algoritmo Redlock

Nella versione distribuita dell'algoritmo assumiamo di avere N nodi Redis leader. Questi nodi sono completamente indipendenti l'uno dall'altro, quindi non utilizziamo la replica o alcun altro sistema di coordinamento implicito. Abbiamo già spiegato come acquisire e rilasciare un blocco in modo sicuro su un'unica istanza. Accettiamo come dato che l'algoritmo, quando lavora con un'unica istanza, utilizzerà proprio questo metodo. Nei nostri esempi fissiamo N a 5, un valore decisamente ragionevole. Pertanto, dobbiamo utilizzare 5 nodi Redis leader su computer o macchine virtuali differenti, per garantire che essi operino principalmente in modo indipendente l'uno dall'altro.

Per acquisire un blocco, il cliente esegue le seguenti operazioni:

Ottiene l'ora attuale in millisecondi.
Cerca di ottenere sequenzialmente il blocco su tutte le N istanze, utilizzando lo stesso nome di chiave e valori casuali in tutti i casi. Nella fase 2, mentre imposta il blocco per ogni istanza, il cliente utilizza un ritardo sufficientemente breve rispetto al tempo dopo il quale il blocco viene automaticamente rimosso. Ad esempio, se la durata del blocco è di 10 secondi, il ritardo può essere compreso tra ~ 5-50 millisecondi. In questo modo si esclude la situazione in cui il cliente potrebbe rimanere bloccato a lungo, cercando di contattare un nodo Redis non disponibile: se un'istanza non è disponibile, cerchiamo di connetterci il prima possibile a un'altra istanza.
Per ottenere il blocco, il cliente calcola quanto tempo è trascorso; per fare questo sottrae dal valore attuale del tempo l'ordine temporale ottenuto al passo 1. Solo quando il cliente riesce ad ottenere il blocco sulla maggior parte degli istanze (almeno 3) e il tempo totale impiegato per ottenere il blocco è inferiore alla durata del blocco, si considera che il blocco sia stato acquisito.
Se il blocco è stato ottenuto, il periodo di validità è considerato il valore iniziale della durata del blocco meno il tempo trascorso, calcolato nel passo 3.
Se il cliente non riesce a ottenere il blocco per qualche motivo (o non riesce a bloccare N/2+1 istanze, o il tempo di validità del blocco risulta negativo), tenterà di sbloccare tutte le istanze (anche quelle che si pensava non potesse bloccare).

L'algoritmo è asincrono?

Questo algoritmo si basa sull'ipotesi che, sebbene non ci siano orologi sincronizzati che controllano tutti i processi, il tempo locale in ogni processo scorra comunque più o meno alla stessa velocità, e che l'errore sia ridotto rispetto al tempo totale dopo il quale il blocco viene automaticamente rimosso. Questa ipotesi ricorda molto una situazione comune ai computer tradizionali: ogni computer ha i propri orologi locali, e solitamente possiamo contare sul fatto che la deviazione temporale tra diversi computer sia minima.

A questo punto dobbiamo formulare in modo più preciso la nostra regola di esclusione reciproca: l'esclusione reciproca è garantita solo se il cliente che detiene il blocco termina il lavoro entro il periodo di validità del blocco (questo valore è stato ottenuto nel passo 3), meno un ulteriore intervallo di tempo (solo pochi millisecondi, per compensare la deviazione temporale tra i processi).

Ulteriori informazioni su sistemi simili, che richiedono la coordinazione della deviazione temporale, sono fornite nel seguente articolo interessante: Leases: un meccanismo efficiente e tollerante ai guasti per la coerenza della cache di file distribuiti.

Riprova in caso di errore

Quando un cliente non riesce ad ottenere un blocco, deve riprovare a farlo, attendendo un ritardo casuale; questo viene fatto per disincronizzare più clienti che tentano contemporaneamente di acquisire il blocco dello stesso risorsa (cosa che potrebbe portare a una situazione di "brain split", nella quale non ci sono vincitori). Inoltre, più velocemente il cliente cerca di acquisire il blocco della maggior parte delle istanze Redis, più stretto è il finestra nella quale può sorgere la situazione di brain split (e minore è la necessità di ripetute tentativi). Pertanto, idealmente, il cliente dovrebbe tentare di inviare contemporaneamente comandi SET a N istanze tramite multiplexing.

È importante sottolineare quanto sia fondamentale per i clienti che non sono riusciti ad acquisire la maggior parte delle serrature liberare (parzialmente) le serrature acquisite, affinché non sia necessario attendere la scadenza della chiave prima che la serratura sul recurso possa essere nuovamente acquisita (ovviamente, se si verifica una frammentazione della rete e il cliente perde la connessione con le istanze Redis, sarà necessario pagare una penalità per violazione della disponibilità durante l'attesa della scadenza della chiave).

Liberazione della serratura

Liberare la serratura è un'operazione semplice, che richiede solo di sbloccare tutte le istanze, indipendentemente dal fatto che il cliente ritenga di aver effettivamente bloccato una specifica istanza.

Considerazioni sulla sicurezza

L'algoritmo è sicuro? Proviamo a immaginare cosa avviene in vari scenari.

Iniziamo supponendo che il cliente sia riuscito a ottenere il blocco sulla maggior parte delle istanze. Ognuna di queste istanze conterrà una chiave con lo stesso tempo di vita per tutte. Tuttavia, ognuna di queste chiavi è stata impostata in momenti diversi, quindi anche le loro scadenze saranno diverse. Ma, se la prima chiave è stata impostata in un momento non peggiore di T1 (il tempo che scegliamo prima di contattare il primo server), e l'ultima chiave è stata impostata in un momento non peggiore di T2 (il tempo in cui è stata ricevuta la risposta dall'ultimo server), allora siamo certi che la prima chiave nel gruppo che scadrà avrà una durata minima di MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Tutte le altre chiavi scadranno dopo, quindi possiamo essere certi che tutte le chiavi saranno valide contemporaneamente per almeno questo tempo.

Durante il periodo in cui la maggior parte delle chiavi rimane valida, un altro cliente non potrà acquisire il blocco, poiché le operazioni N/2+1 SET NX non possono avere successo se già esistono N/2+1 chiavi. Pertanto, se il blocco è stato acquisito, non può essere riacquistato nello stesso momento (ciò violerebbe la proprietà di esclusione reciproca).
In effetti, vogliamo assicurarci che un gran numero di clienti che cercano di acquisire un blocco non possano riuscire a farlo contemporaneamente.

Se un cliente ha bloccato la maggior parte delle istanze impiegando un tempo pari o superiore alla durata massima del blocco, allora considererà il blocco non valido e sbloccherà le istanze. Pertanto, dobbiamo tenere conto solo del caso in cui il cliente riesca a bloccare la maggior parte delle istanze in un tempo inferiore alla durata. In questo caso, per quanto riguarda l'argomento sopra esposto, durante il tempo MIN_VALIDITY Nessun cliente dovrebbe essere in grado di riacquistare un blocco. Pertanto, un gran numero di clienti potrà bloccare N/2+1 istanze contemporaneamente (che termina al momento della fine della fase 2), solo quando il tempo per il blocco della maggioranza è stato maggiore del tempo TTL, rendendo il blocco non valido.

Potete fornire una dimostrazione formale di sicurezza, citare algoritmi simili esistenti, o trovare un bug nel resoconto presentato?

Considerazioni sulla disponibilità

La disponibilità del sistema dipende da tre caratteristiche principali:

Rimozione automatica del blocco (poiché la validità delle chiavi scade): alla fine, le chiavi saranno nuovamente disponibili per essere utilizzate per i blocchi.
Il fatto che i clienti solitamente si aiutino a vicenda rimuovendo i blocchi quando il blocco necessario non è stato acquisito, oppure è stato acquisito ma il lavoro è stato completato; quindi è probabile che non dobbiamo attendere la scadenza delle chiavi per riacquistare il blocco.
Il fatto che, quando un cliente deve riprovare ad acquisire un blocco, attenda per un tempo relativamente più lungo rispetto al periodo necessario per acquisire la maggior parte dei blocchi. Questo riduce la probabilità di una situazione di conflitto per le risorse.

Tuttavia, è necessario pagare una pena per la riduzione della disponibilità, pari al tempo di TTL nei segmenti di rete, quindi, se ci sono segmenti continui, questa pena può assumere una dimensione indefinita. Ciò accade ogni volta che un cliente acquisisce un blocco e poi viene scollegato in un altro segmento prima di avere la possibilità di rilasciarlo.

In linea di principio, con segmenti di rete continui infiniti, il sistema può rimanere non disponibile per un periodo di tempo infinito.

Prestazioni, ripristino dopo un guasto e fsync

Molti utilizzano Redis per garantire alte prestazioni nei server di locking, a livello di latenza necessaria per acquisire e rilasciare il lock, così come nel numero di operazioni di acquisizione/rilascio che è possibile eseguire al secondo. Per soddisfare questa esigenza, esiste una strategia di comunicazione con N server Redis per ridurre la latenza. Si tratta di una strategia di multiplexing (o 'poor man's multiplexing', in cui il socket viene impostato in modalità non bloccante, invia tutti i comandi e li legge successivamente, assumendo che il tempo di andata e ritorno tra il client e ciascun'istanza sia simile).

Tuttavia, è necessario tenere conto anche della questione legata alla memorizzazione a lungo termine dei dati, se si intende creare un modello con un affidabile ripristino dopo i guasti.

In linea di principio, per chiarire il problema, supponiamo di configurare Redis senza alcun tipo di storage persistente. Il cliente riesce a bloccare 3 delle 5 istanze. Una delle istanze bloccate dal cliente viene riavviata e in quel momento si creano nuovamente 3 istanze per la stessa risorsa, che possiamo bloccare, mentre un altro cliente può a sua volta bloccare l'istanza riavviata, violando la proprietà di sicurezza che prevede l'esclusività dei blocchi.

Abilitando il salvataggio anticipato dei dati (AOF), la situazione migliorerà leggermente. Ad esempio, è possibile aumentare il server inviando il comando SHUTDOWN e riavviandolo. Poiché le operazioni di scadenza in Redis sono implementate semanticamente in modo tale che il tempo continua a scorrere anche quando il server è spento, tutte le nostre esigenze sono soddisfatte. Va bene finché si garantisce uno spegnimento regolare. E in caso di interruzioni di corrente? Se Redis è configurato per impostazione predefinita, con la sincronizzazione fsync su disco ogni secondo, è possibile che, dopo il riavvio, non si riesca a trovare la nostra chiave. In teoria, se vogliamo garantire la sicurezza dei blocchi in caso di qualsiasi riavvio dell'istanza, dobbiamo attivare fsync=always nelle impostazioni di salvataggio persistente. Questo ucciderà completamente le performance, riducendole a livelli di sistemi CP, tradizionalmente utilizzati per implementare in sicurezza blocchi distribuiti.

Tuttavia, la situazione è migliore di quanto sembri a prima vista. In linea di principio, la sicurezza dell'algoritmo è mantenuta, poiché quando un'istanza viene riavviata dopo un guasto, essa non partecipa più a nessun blocco attivo al momento.

Per garantire questo, è sufficiente assicurarsi che, dopo il guasto, l'istanza rimanga non disponibile per un periodo leggermente superiore al massimo TTL che utilizziamo. In questo modo attenderemo la scadenza e la liberazione automatica di tutte le chiavi che erano attive al momento del guasto.

Utilizzando riavvii differiti, è fondamentalmente possibile raggiungere la sicurezza anche in assenza di una conservazione a lungo termine in Redis. Va notato, però, che questo potrebbe comportare una penalità per violazione della disponibilità. Ad esempio, in caso di guasto della maggior parte delle istanze, il sistema diventerà globalmente non disponibile per la durata del TTL (e nessuna risorsa potrà essere bloccata durante questo periodo).

Aumentiamo la disponibilità dell'algoritmo: prolungando il blocco

Se il lavoro svolto dai clienti è suddiviso in tappe minori, è possibile ridurre il tempo di blocco predefinito e implementare un meccanismo di estensione dei blocchi. In linea di principio, se il cliente è impegnato in operazioni di calcolo e il tempo di validità del blocco sta diminuendo pericolosamente, è possibile inviare a tutte le istanze uno script Lua che estende il TTL della chiave, se la chiave esiste ancora e il suo valore è ancora casuale, ottenuto quando è stato acquisito il blocco.

Il cliente deve considerare il blocco nuovamente acquisito solo nel caso in cui sia riuscito a bloccare la maggior parte delle istanze durante il tempo di validità.

Tuttavia, tecnicamente l'algoritmo non cambia, quindi il numero massimo di tentativi di acquisizione dei blocchi deve essere limitato, altrimenti verranno compromesse le proprietà di disponibilità.

Fonte: habr.com

Sblocco distribuito con l'uso di Redis