Blocco distribuito utilizzando Redis

Ehi Habr!

Oggi portiamo alla vostra attenzione la traduzione di un articolo complesso sull'implementazione del blocco distribuito utilizzando Redis e vi invitiamo a parlare delle prospettive di Redis come argomento. Analisi dell'algoritmo Redlock in questione di Martin Kleppmann, autore del libro "Applicazioni a carico elevato", dato qui.

Il bloccaggio distribuito è una primitiva molto utile utilizzata in molti ambienti in cui diversi processi devono lavorare su risorse condivise in modo mutuamente esclusivo.

Sono disponibili numerose librerie e post che descrivono come implementare DLM (Distributed Lock Manager) utilizzando Redis, ma ciascuna libreria adotta un approccio diverso e le garanzie fornite sono piuttosto deboli rispetto a ciò che è ottenibile con una progettazione leggermente più sofisticata.

In questo articolo proveremo a descrivere un algoritmo canonico condizionale che dimostra come implementare il blocco distribuito utilizzando Redis. Parleremo di un algoritmo chiamato Blocco rosso, implementa un gestore di lock distribuito e, a nostro avviso, questo algoritmo è più sicuro del solito approccio a istanza singola. Ci auguriamo che la community lo analizzi, fornisca feedback e lo utilizzi come punto di partenza per progetti più complessi o alternativi.

Implementazione

Prima di passare alla descrizione dell’algoritmo forniamo diversi link ad implementazioni già pronte. Possono essere utilizzati come riferimento.

• Redlock-RB (implementazione per Ruby). C'è anche forchetta Redlock-rb, che aggiunge un pacchetto (gem) per facilitare la distribuzione, e non solo per quello.
• Redlock-py (Implementazione di Python).
• Airedlock (implementazione per Asyncio Python).
• Redlock-php (implementazione per PHP).
• PHPRedisMutex (un'altra implementazione per PHP)
• cheprasov/php-redis-lock (Libreria PHP per serrature)
• Sincronizzazione rossa (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 asincrone e di blocco.
• ScarletLock (implementazione per C# .NET con archivio dati configurabile)
• Redlock4Net (implementazione per C# .NET)
• nodo-redlock (implementazione per NodeJS). Include il supporto per l'estensione delle serrature.

Garanzie di sicurezza e disponibilità

Modelleremo il nostro progetto con solo tre proprietà che riteniamo forniscano le garanzie minime necessarie per utilizzare in modo efficace il blocco distribuito.

1. Proprietà di sicurezza: Mutua esclusione. In qualsiasi momento, solo un client può mantenere il blocco.
2. Proprietà di disponibilità A: nessun deadlock. È sempre possibile acquisire eventualmente un blocco, anche se il client che ha bloccato la risorsa fallisce o si ferma su un segmento del disco diverso.
3. Proprietà di disponibilità B: tolleranza agli errori. Finché la maggior parte dei nodi Redis è in esecuzione, i client sono in grado di acquisire e rilasciare blocchi.

Perché in questo caso l'implementazione basata sul ripristino dopo un errore non è sufficiente
Per capire cosa miglioreremo, analizziamo lo stato attuale delle cose con la maggior parte delle librerie di chiusura distribuite basate su Redis.

Il modo più semplice per bloccare una risorsa utilizzando Redis è creare una chiave nell'istanza. In genere, viene creata una chiave con una durata limitata, ciò si ottiene utilizzando la funzionalità di scadenza fornita in Redis, quindi prima o poi questa chiave viene rilasciata (proprietà 2 nel nostro elenco). Quando il client deve rilasciare la risorsa, elimina la chiave.

A prima vista, questa soluzione funziona abbastanza bene, ma c’è un problema: la nostra architettura crea un singolo punto di errore. Cosa succede se l'istanza Redis dell'host fallisce? Aggiungiamo allora uno schiavo! E lo useremo se il presentatore non è disponibile. Purtroppo questa opzione non è praticabile. In questo modo non saremo in grado di implementare correttamente la proprietà di mutua esclusione necessaria per garantire la sicurezza, poiché la replica in Redis è asincrona.

Ovviamente, in un modello del genere si verifica una condizione di competizione:

1. Il client A acquisisce un lock sul master.
2. Il master fallisce prima che l'immissione della chiave venga trasferita allo slave.
3. Il follower viene promosso a leader.
4. Il client B acquisisce un blocco sulla stessa risorsa che A ha già bloccato. VIOLAZIONE DELLA SICUREZZA!

A volte è del tutto normale che in circostanze particolari, ad esempio in caso di guasto, più client possano mantenere il blocco contemporaneamente. In questi casi è possibile applicare una soluzione basata sulla replica. Altrimenti, consigliamo la soluzione descritta in questo articolo.

Implementazione corretta con una singola istanza

Prima di tentare di superare i limiti della configurazione a istanza singola sopra descritti, capiamo come gestire correttamente questo semplice caso, poiché questa soluzione è effettivamente valida in applicazioni in cui una race condition è di volta in volta accettabile, e anche perché il blocco su un la singola istanza funge da base utilizzata nell'algoritmo distribuito qui descritto.

Per acquisire un blocco, procedere come segue:

SET resource_name my_random_value NX PX 30000

Questo comando installa una chiave solo se non esiste già (opzione NX), con un periodo di validità di 30000 millisecondi (opzione PX). La chiave è impostata su “myrandomvalue" Questo valore deve essere univoco per tutti i client e tutte le richieste di blocco.
Fondamentalmente, viene utilizzato un valore casuale per rilasciare il blocco in modo sicuro, con uno script che dice a Redis: rimuovi la chiave solo se esiste e il valore memorizzato in essa è esattamente quello previsto. Ciò si ottiene utilizzando il seguente script Lua:

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

Ciò è importante per evitare che un blocco mantenuto da un altro client venga rimosso. Ad esempio, un client potrebbe acquisire un blocco, quindi rimanere bloccato in un'operazione che dura più a lungo del primo blocco (in modo che la chiave abbia il tempo di scadere) e successivamente rimuovere il blocco inserito da un altro client.
L'utilizzo di un semplice DEL non è sicuro poiché un client può rimuovere un blocco mantenuto da un altro client. Al contrario, quando si utilizza lo script precedente, ogni lucchetto viene “firmato” con una stringa casuale, quindi solo il client che lo ha inserito in precedenza può rimuoverlo.

Quale dovrebbe essere questa stringa casuale? Immagino che dovrebbe essere 20 byte da /dev/urandom, ma puoi trovare modi meno costosi per rendere la stringa sufficientemente unica per i tuoi scopi. Ad esempio, andrebbe bene eseguire il seeding di RC4 con /dev/urandom e quindi generare da esso un flusso pseudo-casuale. Una soluzione più semplice prevede una combinazione di tempo Unix con risoluzione in microsecondi più l'ID client; non è così sicuro, ma probabilmente è all'altezza del compito nella maggior parte dei contesti.

Il tempo che utilizziamo come misura della durata della chiave è chiamato "durata della serratura". Questo valore rappresenta sia la quantità di tempo prima che il blocco venga rilasciato automaticamente, sia la quantità di tempo a disposizione di un client per completare un'operazione prima che un altro client possa a sua volta bloccare quella risorsa, senza violare effettivamente le garanzie di mutua esclusione. Questa garanzia è limitata solo ad un certo periodo di tempo, che inizia dal momento dell'acquisto della serratura.

Quindi abbiamo discusso un buon modo per acquisire e rilasciare un lucchetto. Il sistema (se parliamo di sistema non distribuito e costituito da un'unica istanza sempre disponibile) è sicuro. Estendiamo questo concetto ad un sistema distribuito, dove non abbiamo tali garanzie.

Algoritmo Redlock

La versione distribuita dell'algoritmo presuppone che abbiamo N master Redis. Questi nodi sono completamente indipendenti l'uno dall'altro, quindi non utilizziamo la replica o qualsiasi altro sistema di coordinamento implicito. Abbiamo già spiegato come acquisire e rilasciare in modo sicuro un blocco su una singola istanza. Diamo per scontato che l'algoritmo, quando lavora con una singola istanza, utilizzerà esattamente questo metodo. Nei nostri esempi impostiamo N su 5, che è un valore ragionevole. Dovremo quindi utilizzare 5 master Redis su computer o macchine virtuali diversi per garantire che agiscano in modo ampiamente indipendente l'uno dall'altro.

Per acquisire un lock, il client esegue le seguenti operazioni:

1. Ottiene l'ora corrente in millisecondi.
2. Tenta in sequenza di ottenere un blocco su tutte le N istanze, utilizzando in tutti i casi lo stesso nome di chiave e valori casuali. Nella Fase 2, quando il client imposta un blocco per istanza, per acquisirlo utilizza un ritardo sufficientemente breve rispetto al tempo trascorso il quale il blocco viene rilasciato automaticamente. Ad esempio, se la durata del blocco è di 10 secondi, il ritardo potrebbe essere compreso tra circa 5 e 50 millisecondi. Questo elimina la situazione in cui il client potrebbe rimanere bloccato per lungo tempo nel tentativo di raggiungere un nodo Redis guasto: se l'istanza non è disponibile, allora proviamo a connetterci ad un'altra istanza il prima possibile.
3. Per effettuare un lock, il client calcola quanto tempo è trascorso; Per fare ciò, sottrae dal valore temporale effettivo il timestamp ottenuto nel passaggio 1. Se e solo se il client è riuscito a ottenere il blocco sulla maggior parte delle istanze (almeno 3) e il tempo totale impiegato per ottenere il blocco, inferiore alla durata del blocco, il blocco si considera ottenuto.
4. Se è stato acquisito un blocco, la durata del blocco viene considerata pari alla durata del blocco originale meno il tempo trascorso calcolato nel passaggio 3.
5. Se il client non riesce a ottenere il blocco per qualche motivo (non è stato in grado di bloccare N/2+1 istanze o la durata del blocco era negativa), tenterà di sbloccare tutte le istanze (anche quelle che pensava di non poter bloccare ).

L'algoritmo è asincrono?

Questo algoritmo si basa sul presupposto che, sebbene non esista un orologio sincronizzato su cui tutti i processi funzionerebbero, l'ora locale in ciascun processo scorre ancora approssimativamente allo stesso ritmo e l'errore è piccolo rispetto al tempo totale dopo il quale il blocco viene bloccato. rilasciato automaticamente. Questo presupposto è molto simile alla situazione tipica dei computer comuni: ogni computer ha un orologio locale e di solito possiamo contare sul fatto che la differenza oraria tra i diversi computer è piccola.

A questo punto dobbiamo formulare con maggiore attenzione la nostra regola di mutua esclusione: la mutua esclusione è garantita solo se il client che detiene il lock esce durante il tempo in cui il lock è valido (questo valore ottenuto nel passaggio 3), meno un po' di tempo in più (totale qualche millisecondi per compensare la differenza di tempo tra i processi).

Il seguente interessante articolo fornisce ulteriori informazioni su tali sistemi che richiedono il coordinamento degli intervalli di tempo: Leasing: un efficiente meccanismo di tolleranza agli errori per la coerenza della cache dei file distribuiti.

Riprovare in caso di fallimento

Quando un client non riesce ad acquisire un blocco, deve riprovare dopo un ritardo casuale; questo viene fatto per de-sincronizzare più client che tentano di acquisire un blocco sulla stessa risorsa contemporaneamente (il che può portare a una situazione di "cervello diviso" in cui non ci sono vincitori). Inoltre, quanto più velocemente un client tenta di acquisire un blocco sulla maggior parte delle istanze Redis, tanto più ristretta è la finestra in cui può verificarsi una situazione split-brain (e minore è la necessità di nuovi tentativi). Pertanto, idealmente, il client dovrebbe provare a inviare comandi SET a N istanze simultaneamente utilizzando il multiplexing.

Vale la pena sottolineare qui quanto sia importante che i client che non riescono ad acquisire la maggior parte dei lock rilascino i lock (parzialmente) acquisiti, in modo da non dover attendere la scadenza della chiave prima di poter acquisire nuovamente il lock sulla risorsa (tuttavia se si verifica una frammentazione della rete e il client perde il contatto con le istanze Redis, dovrai pagare una penalità di disponibilità durante l'attesa della scadenza della chiave).

Rilascia la serratura

Il rilascio di un blocco è un'operazione semplice che richiede semplicemente lo sblocco di tutte le istanze, indipendentemente dal fatto che il client sembri aver bloccato con successo una particolare istanza.

Considerazioni sulla sicurezza

L'algoritmo è sicuro? Proviamo a immaginare cosa succede nei diversi scenari.

Per cominciare, supponiamo che il client sia riuscito a ottenere un blocco sulla maggior parte delle istanze. Ogni istanza conterrà una chiave con la stessa durata per tutte. Tuttavia, ciascuna di queste chiavi è stata installata in un momento diverso, quindi scadranno in momenti diversi. Ma, se la prima chiave è stata installata in un momento non peggiore di T1 (l'ora che scegliamo prima di contattare il primo server) e l'ultima chiave è stata installata in un momento non peggiore di T2 (l'ora in cui è stata ricevuta la risposta dall'ultimo server), allora siamo sicuri che almeno la prima chiave del set che scade sopravviverà MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Tutte le altre chiavi scadranno più tardi, quindi possiamo essere sicuri che tutte le chiavi saranno valide contemporaneamente almeno per questo periodo.

Durante il periodo in cui la maggior parte delle chiavi rimane valida, un altro client non sarà in grado di acquisire il blocco, poiché le operazioni N/2+1 SET NX non possono avere esito positivo se esistono già N/2+1 chiavi. Pertanto, una volta acquisito un lock, non è possibile acquisirlo nuovamente nello stesso momento (questo violerebbe la proprietà di mutua esclusione).
Tuttavia, vogliamo assicurarci che più client che tentano di acquisire un blocco contemporaneamente non possano riuscire contemporaneamente.

Se il client ha bloccato la maggior parte delle istanze per circa o più della durata massima del blocco, considererà il blocco non valido e sbloccherà le istanze. Dobbiamo quindi prendere in considerazione solo il caso in cui il client sia riuscito a bloccare la maggior parte delle istanze in un tempo inferiore alla data di scadenza. In questo caso, per quanto riguarda l'argomento di cui sopra, nel corso del tempo MIN_VALIDITY nessun client dovrebbe essere in grado di riacquisire il blocco. Pertanto, molti client saranno in grado di bloccare N/2+1 istanze nello stesso tempo (che termina alla fine della fase 2) solo quando il tempo per bloccare la maggior parte delle istanze è maggiore del tempo TTL, il che rende il blocco non valido.

Puoi fornire una prova formale di sicurezza, indicare algoritmi simili esistenti o trovare un bug in quanto sopra?

Considerazioni sull'accessibilità

La disponibilità del sistema dipende da tre caratteristiche principali:

1. Rilascia automaticamente i lucchetti (quando le chiavi scadono): le chiavi saranno infine nuovamente disponibili per essere utilizzate per i lucchetti.
2. Il fatto che i clienti solitamente si aiutano a vicenda rimuovendo i lucchetti quando il lucchetto desiderato non è stato acquisito, oppure è stato acquisito e il lavoro è stato completato; quindi è probabile che non dovremo aspettare la scadenza delle chiavi per riacquisire la serratura.
3. Il fatto che quando un client deve riprovare ad acquisire un lock, attende un tempo relativamente più lungo rispetto al periodo richiesto per acquisire la maggior parte dei lock. Ciò riduce la probabilità che si verifichi una situazione di divisione del cervello quando si compete per le risorse.

Esiste però una penalità di disponibilità pari al TTL dei segmenti di rete, quindi se vi sono segmenti contigui la penalità può essere indefinita. Ciò si verifica ogni volta che un client acquisisce un blocco e quindi si sposta su un altro segmento prima di poterlo rilasciare.

In linea di principio, dati infiniti segmenti di rete contigui, un sistema può rimanere indisponibile per un periodo di tempo infinito.

Prestazioni, failover e fsync

Molte persone utilizzano Redis perché necessitano di prestazioni elevate del server di blocco in termini di latenza richiesta per acquisire e rilasciare blocchi e di numero di acquisizioni/rilasci che possono essere completati al secondo. Per soddisfare questo requisito, esiste una strategia per comunicare con i server N Redis per ridurre la latenza. Questa è una strategia di multiplexing (o "multiplexing dei poveri", in cui il socket viene messo in modalità non bloccante, invia tutti i comandi e legge i comandi in seguito, presupponendo che il tempo di andata e ritorno tra il client e ciascuna istanza sia simile) .

Tuttavia, se vogliamo creare un modello con un recupero affidabile in caso di guasti, dobbiamo anche tenere conto delle considerazioni legate all’archiviazione dei dati a lungo termine.

Fondamentalmente, per chiarire il problema, supponiamo di configurare Redis senza alcuna memorizzazione dei dati a lungo termine. Il client riesce a bloccare 3 istanze su 5. Una delle istanze che il client è riuscito a bloccare viene riavviata e in questo momento ci sono nuovamente 3 istanze per la stessa risorsa, che possiamo bloccare, e un altro client può, a sua volta, bloccare l'istanza riavviata, violando la proprietà di sicurezza che presuppone l'esclusività delle serrature.

Se abiliti i dati anticipati (AOF), la situazione migliorerà leggermente. Ad esempio, puoi promuovere un server inviando il comando SHUTDOWN e riavviandolo. Poiché le operazioni di scadenza in Redis sono implementate semanticamente in modo tale che il tempo continui a scorrere anche quando il server è spento, tutti i nostri requisiti vanno bene. Ciò è normale purché sia ​​garantito un arresto normale. Cosa fare in caso di interruzioni di corrente? Se Redis è configurato per impostazione predefinita, con fsync che si sincronizza sul disco ogni secondo, è possibile che dopo un riavvio non avremo la nostra chiave. In teoria, se vogliamo garantire la sicurezza del blocco durante il riavvio di qualsiasi istanza, dovremmo abilitare fsync=always nelle impostazioni per l'archiviazione dei dati a lungo termine. Ciò distruggerà completamente le prestazioni, fino al livello dei sistemi CP tradizionalmente utilizzati per implementare in modo sicuro i blocchi distribuiti.

Ma la situazione è migliore di quanto sembri a prima vista. In linea di principio, la sicurezza dell'algoritmo viene preservata perché quando l'istanza viene riavviata dopo un errore, non partecipa più ad alcun blocco attualmente attivo.

Per garantire ciò, dobbiamo solo assicurarci che dopo un guasto l'istanza rimanga non disponibile per un periodo di tempo leggermente superiore al TTL massimo che utilizziamo. In questo modo aspetteremo fino alla data di scadenza e al rilascio automatico di tutte le chiavi attive al momento del guasto.

Utilizzando il riavvio ritardato è in linea di principio possibile garantire la sicurezza anche in assenza di una persistenza a lungo termine in Redis. Tieni presente, tuttavia, che ciò potrebbe comportare una multa per violazione dell'accessibilità. Ad esempio, se la maggior parte delle istanze fallisce, il sistema diventerà globalmente non disponibile per il TTL (e nessuna risorsa potrà essere bloccata durante questo periodo).

Aumentiamo la disponibilità dell'algoritmo: estendiamo il blocco

Se il lavoro svolto dai client consiste in piccoli passaggi, è possibile ridurre la durata del blocco predefinito e implementare un meccanismo per estendere i blocchi. In linea di principio, se il client è impegnato nell'elaborazione e il valore di scadenza del blocco è pericolosamente basso, è possibile inviare uno script Lua a tutte le istanze che estende il TTL della chiave se la chiave esiste ancora e il suo valore è ancora un valore casuale ottenuto quando il il blocco è stato acquisito.

Un client dovrebbe prendere in considerazione la riacquisizione di un blocco solo se è riuscito a bloccare la maggior parte delle istanze entro il periodo di validità.

È vero, tecnicamente l'algoritmo non cambia, quindi il numero massimo di tentativi ripetuti per acquisire i lock deve essere limitato, altrimenti le proprietà di accessibilità verranno violate.

Fonte: habr.com