🥇Blocchi distribuiti con Redis

Ciao, Habr!

Oggi vi proponiamo una traduzione di un articolo complesso sull'implementazione dei lock distribuiti con Redis e discutiamo della promettente prospettiva di Redis come argomento. L'analisi dell'algoritmo Redlock di Martin Kleppmann, autore del libro "Applicazioni ad alta carico" è fornita. qui.

I lock distribuiti sono un primitivo molto utile, utilizzato in molti ambienti dove diversi processi devono lavorare su risorse condivise secondo il principio dell'esclusione reciproca.

Esistono diverse librerie e articoli che descrivono come implementare un DLM (gestore di lock distribuiti) utilizzando Redis, ma ogni libreria adotta un approccio diverso e le garanzie fornite sono piuttosto deboli rispetto a ciò che può essere ottenuto attraverso una progettazione leggermente più complessa.

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

Implementazioni

Prima di passare alla descrizione dell'algoritmo, riportiamo alcuni link a implementazioni già pronte. Possono essere utilizzate come riferimento.

Redlock-rb (implementazione per Ruby). Esiste anche un 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 lock)
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 dati configurabile)
Redlock4Net (implementazione per C# .NET)
node-redlock (implementazione per NodeJS). Include supporto per il prolungamento dei lock.

Garanzie di sicurezza e disponibilità

Abbiamo intenzione di modellare il nostro progetto con sole tre proprietà, che secondo noi forniscono le garanzie minime necessarie per un uso efficace dei blocchi distribuiti.

Proprietà di sicurezza: Esclusione reciproca. In qualsiasi momento, solo un client può detenere il blocco.
Proprietà di disponibilità A: Assenza di blocchi reciproci. Alla fine, è sempre possibile ottenere un blocco, anche se il client che ha bloccato la risorsa si guasta o si sposta su un'altra parte del disco.
Proprietà di disponibilità B: Resilienza. Finché la maggior parte dei nodi Redis è operativa, i client possono acquisire e rilasciare blocchi.

Perché un'implementazione basata sul ripristino dopo il guasto non è sufficiente in questo caso
Per capire cosa intendiamo migliorare, analizziamo la situazione attuale riguardante la maggior parte delle librerie per blocchi 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, grazie alla funzione expires di Redis, quindi prima o poi questa chiave viene rilasciata (proprietà 2 nella nostra lista). Quando il client ha bisogno di rilasciare la risorsa, elimina la chiave.

A prima vista, questa soluzione sembra funzionare bene, ma c'è un problema: nella nostra architettura si crea un punto singolo di guasto. Cosa succede se l'istanza primaria di Redis fallisce? Aggiungiamo allora una secondaria! E la useremo se quella principale non è disponibile. Sfortunatamente, questa opzione non è praticabile. Facendo così, non possiamo implementare correttamente la proprietà di esclusione reciproca di cui abbiamo bisogno per garantire la sicurezza, poiché la replica in Redis è asincrona.

È chiaro che in un tale modello si verifica una condizione di gara:

Il client A acquisisce il blocco sulla primari.
La primari si guasta prima che la scrittura della chiave venga trasferita alla secondaria.
La secondaria viene promossa a primari.
Il client B acquisisce il blocco della stessa risorsa già bloccata da A. VIOLAZIONE DELLA SICUREZZA!

A volte è del tutto normale che, in circostanze particolari, ad esempio in caso di errore, numerosi clienti possano mantenere un blocco simultaneamente. In tali casi, è possibile applicare una soluzione basata sulla replica. In altri casi, raccomandiamo la soluzione descritta in questo articolo.

Implementazione corretta con un’unica istanza

Prima di provare a superare le limitazioni della configurazione con una singola istanza, come descritto sopra, vediamo come agire correttamente in questo semplice caso, poiché tale soluzione è effettivamente accettabile in quelle applicazioni in cui le condizioni di gara sono occasionalmente tollerabili, e anche perché il blocco su un'unica istanza serve da base per l'algoritmo distribuito qui descritto.

Per acquisire il blocco, procediamo in questo modo:

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). Per la chiave viene impostato il valore “myrandomvalue”. Questo valore deve essere unico per tutti i clienti e tutte le richieste di blocco.
In linea di principio, un valore casuale viene utilizzato per rilasciare in modo sicuro il blocco, attraverso uno script che informa Redis: elimina la chiave solo se esiste e se il valore memorizzato è proprio quello atteso. Questo si ottiene utilizzando 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 evitare la rimozione di un blocco stabilito da un altro cliente. Ad esempio, un cliente può acquisire un blocco, poi bloccarsi durante un'operazione che richiede più tempo rispetto alla durata del primo blocco (in modo che la validità della chiave scada), e successivamente rimuovere un blocco impostato da un altro cliente.
Utilizzare un semplice DEL non è sicuro, poiché un cliente potrebbe rimuovere un blocco impostato da un altro cliente. Al contrario, utilizzando lo script sopra menzionato, ogni blocco è "firmato" con una stringa casuale, quindi solo il cliente che lo ha messo può rimuoverlo.

Qual è questo stringa casuale dovrebbe essere? Penso che debba essere 20 byte da /dev/urandom, ma ci sono modi meno costosi per creare una stringa sufficientemente unica per gli scopi che stai affrontando. Ad esempio, sarebbe ok seminare RC4 con /dev/urandom e poi generare un flusso pseudocasuale basato su di esso. Una soluzione più semplice è legata a una combinazione di tempo Unix in risoluzione microsecondo più l'ID del cliente; non è così sicura, ma potrebbe corrispondere al livello di attività nella maggior parte dei contesti.

Il tempo che utilizziamo come indicatore della vita della chiave è chiamato 'tempo di validità del blocco'. Questo valore è sia la scadenza dopo la quale il blocco verrà automaticamente rilasciato, sia il tempo che il cliente ha per eseguire l'operazione prima che un altro cliente possa, a sua volta, bloccare questa risorsa, senza violare effettivamente le garanzie di esclusione reciproca. Tale garanzia è limitata solo a una certa finestra di tempo, che inizia dal momento dell'acquisizione del blocco.

Quindi, abbiamo discusso un buon modo per acquisire e rilasciare un blocco. Il sistema (se si tratta di un sistema non distribuito composto da un'unica istanza sempre disponibile) è sicuro. Estendiamo questo concetto a un sistema distribuito, in cui non abbiamo tali garanzie.

Algoritmo Redlock

Nella versione distribuita dell'algoritmo, presupponiamo di avere N nodi Redis principali. Questi nodi sono completamente indipendenti l'uno dall'altro, quindi non utilizziamo la replicazione o alcun altro sistema di coordinamento implicito. Abbiamo già descritto come acquisire e rilasciare un blocco in modo sicuro su un'unica istanza. Supponiamo che l'algoritmo, quando si lavora con un'unica istanza, utilizzi proprio questo metodo. Nei nostri esempi, impostiamo N uguale a 5, un valore ragionevole. Ciò significa che avremo bisogno di utilizzare 5 nodi Redis principali su vari computer o macchine virtuali, per garantire che operino principalmente in modo indipendente l'uno dall'altro.

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

Ottiene l'ora corrente in millisecondi.
Cerca di ottenere il blocco su tutte le N istanze in modo sequenziale, utilizzando in ciascun caso lo stesso nome della chiave e valori casuali. Nella fase 2, mentre stabilisce il blocco per ciascuna istanza, il client utilizza un ritardo che è abbastanza breve rispetto al tempo dopo il quale il blocco viene automaticamente rilasciato. Ad esempio, se la durata del blocco è di 10 secondi, il ritardo può variare tra ~ 5-50 millisecondi. In questo modo si evita la situazione in cui il client potrebbe restare a lungo bloccato, cercando di contattare il nodo Redis in caso di guasto: se l'istanza non è disponibile, cerchiamo il prima possibile di connetterci a un'altra istanza.
Per prendere il blocco, il client calcola quanto tempo è trascorso; per farlo, sottrae dal valore attuale del tempo il timestamp ottenuto nel passaggio 1. Soltanto quando il client è riuscito a ottenere il blocco dalla maggior parte delle istanze (almeno 3) e il tempo totale necessario per ottenere il blocco è inferiore al tempo di scadenza del blocco, si considera che il blocco sia stato acquisito.
Se il blocco è stato ottenuto, il tempo di validità viene considerato come il valore originale della durata del blocco meno il tempo trascorso calcolato nel passaggio 3.
Se il client per qualche motivo non riesce a ottenere il blocco (sia perché non riesce a bloccare N/2+1 istanze, sia perché il tempo di validità del blocco risulta negativo), tenterà di sbloccare tutte le istanze (anche quelle che, si pensava, non fosse in grado di bloccare).

L'algoritmo è asincrono?

Questo algoritmo si basa sull'ipotesi che, anche se non ci sono orologi sincronizzati utilizzati da tutti i processi, il tempo locale in ogni processo scorre comunque più o meno alla stessa velocità, e l'errore è ridotto rispetto al tempo totale dopo il quale il blocco viene automaticamente rilasciato. Questa ipotesi ricorda molto la situazione tipica dei computer normali: ogni computer ha un orologio locale e di solito possiamo contare sul fatto che la divergenza temporale tra computer diversi è minima.

In questo momento dobbiamo formulare con maggiore precisione la nostra regola di esclusione reciproca: l'esclusione reciproca è garantita solo a condizione che il cliente che detiene il blocco completi il lavoro entro il tempo in cui il blocco è valido (questo valore è stato ottenuto al passo 3), meno un certo tempo (solo alcuni millisecondi, per compensare la discrepanza temporale tra i processi).

Ulteriori dettagli su sistemi simili che richiedono la concordanza delle discrepanze temporali sono trattati nel seguente articolo interessante: Leases: un meccanismo efficiente e tollerante ai guasti per la coerenza della cache dei file distribuiti.

Nuova tentativo in caso di guasto

Quando un cliente non riesce ad acquisire un blocco, deve riprovare, attendendo un ritardo casuale; ciò viene fatto per desincronizzare più clienti che cercano di acquisire contemporaneamente il blocco della stessa risorsa (il che può portare a una situazione di "brain split", in cui non ci sono vincitori). Inoltre, quanto più velocemente un cliente cerca di acquisire il blocco della maggior parte delle istanze di Redis, più stretto è l'intervallo in cui può verificarsi una situazione di brain split (e minore è la necessità di ritentare). Pertanto, idealmente, il cliente dovrebbe tentare di inviare simultaneamente comandi SET a N istanze utilizzando il multiplexing.

È importante sottolineare quanto sia fondamentale che i clienti che non sono riusciti ad acquisire la maggior parte dei blocchi rilasciino (parzialmente) i blocchi acquisiti, per evitare di dover attendere la scadenza della chiave prima che il blocco della risorsa possa essere nuovamente acquisito (tuttavia, se si verifica una frammentazione della rete e il cliente perde il contatto con le istanze di Redis, sarà necessario pagare un costo per la violazione della disponibilità, mentre si attende la scadenza della chiave).

Rilascio del blocco

Il rilascio del blocco è un’operazione semplice, che richiede solo di sbloccare tutte le istanze, indipendentemente dal fatto che al cliente sembri di aver bloccato con successo una particolare istanza.

Considerazioni sulla sicurezza

L'algoritmo è sicuro? Cerchiamo di immaginare cosa succede in vari scenari.

Per cominciare, supponiamo che il cliente sia riuscito a ottenere il blocco sulla maggior parte delle istanze. Ciascuna di queste istanze conterrà una chiave con lo stesso tempo di vita per tutti. Tuttavia, ciascuna di queste chiavi è stata impostata nel proprio momento, quindi la loro validità scadrà in tempi diversi. 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 set, la cui validità scadrà, esisterà per almeno MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Tutte le altre chiavi scadranno più tardi, quindi possiamo essere certi che tutte le chiavi saranno valide contemporaneamente per almeno questo tempo.

Durante il tempo in cui la maggior parte delle chiavi rimane valida, un altro cliente non potrà acquisire il blocco, poiché N/2+1 operazioni SET NX non possono avere successo se esistono già N/2+1 chiavi. Pertanto, se il blocco è stato acquisito, non sarà possibile riacquisirlo nello stesso momento (ciò violerebbe la proprietà di esclusione reciproca).
In realtà, vogliamo assicurarci che un insieme di clienti, che tentano contemporaneamente di acquisire il blocco, non possa riuscirci tutti insieme.

Se un cliente ha bloccato la maggior parte delle istanze, impiegando circa o più del tempo massimo di durata del blocco, considererà il blocco non valido e sblocccherà le istanze. Pertanto, dobbiamo considerare solo il caso in cui un cliente è riuscito a bloccare la maggior parte delle istanze in un tempo inferiore alla durata di validità. In questo caso, relativamente all'argomento sopra esposto, durante il tempo MIN_VALIDITY nessun cliente dovrebbe essere in grado di riacquisire il blocco. Pertanto, un insieme di clienti potrà bloccare N/2+1 istanze nello stesso intervallo di tempo (che termina al momento del completamento della fase 2), solo quando il tempo per bloccare la maggior parte è stato superiore al tempo TTL, il che rende il blocco non valido.

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

Considerazioni sulla disponibilità

La disponibilità del sistema dipende da tre caratteristiche principali:

Sblocco automatico (poiché la validità delle chiavi scade): alla fine, le chiavi saranno di nuovo disponibili per l'uso nelle prenotazioni.
Il fatto che i clienti di solito si aiutano a vicenda rimuovendo le prenotazioni quando quella necessaria non è stata acquisita, o è stata acquisita e il lavoro è stato completato; quindi, è molto probabile che non dovremo aspettare la scadenza delle chiavi per riacquistarne una.
Il fatto che, quando un cliente deve riprovare a ottenere una prenotazione, attenda un tempo relativamente più lungo di quello richiesto per acquisire la maggior parte delle prenotazioni. Questo riduce la probabilità di una situazione di brain split nella competizione per le risorse.

Tuttavia, è necessario pagare una penalità per la diminuzione della disponibilità, equivalente al tempo TTL nei segmenti di rete, quindi, se ci sono segmenti continui, questa penalità può assumere dimensioni indefinibili. Questo accade ogni volta che un cliente acquisisce una prenotazione e poi viene disconnesso in un altro segmento prima di avere il tempo di rilasciarla.

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

Prestazioni, recupero da guasti e fsync

Molti utilizzano Redis, poiché è necessario garantire elevate prestazioni del server di prenotazione, a livello di latenza necessaria per acquisire e rilasciare le prenotazioni, così come il numero di operazioni di tale acquisizione/rilascio che riescono a essere eseguite al secondo. Per rispettare questo requisito esiste una strategia di comunicazione con N server Redis, per ridurre la latenza. Questa è una strategia di multiplexing (o "multiplexing del povero", in cui il socket viene messo in modalità non bloccante, invia tutti i comandi e legge i comandi in seguito, supponendo che il tempo di turnover tra il cliente e ciascuno degli istanze sia simile).

Tuttavia, è necessario considerare anche la questione relativa alla conservazione a lungo termine dei dati, se puntiamo a creare un modello con un recupero da guasti sicuro.

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

Se attiviamo la scrittura anticipata dei dati (AOF), la situazione migliora leggermente. Ad esempio, possiamo rimuovere il server inviando il comando SHUTDOWN e riavviandolo. Poiché le operazioni di timeout in Redis sono semantically implementate in modo tale che il tempo continua a scorrere anche quando il server è spento, per tutte le nostre richieste va bene. Va bene finché viene garantito uno spegnimento ordinato. E in caso di interruzioni di corrente? Se Redis è configurato di default, con sincronizzazione fsync su disco ogni secondo, è possibile che, dopo il riavvio, non troveremo la nostra chiave. Teoricamente, se vogliamo garantire la sicurezza dei blocchi in caso di riavvio di un'istanza, dobbiamo attivare fsync=always nelle impostazioni di archiviazione persistente. Questo abbatterà completamente le prestazioni, portandole a livelli di sistemi CP, che sono 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 è mantenuta, poiché quando un'istanza si riavvia dopo un guasto, non partecipa più a nessun blocco attivo in quel momento.

Per garantire ciò, è sufficiente assicurarsi che dopo un guasto l'istanza rimanga non disponibile per un tempo leggermente superiore al massimo TTL che utilizziamo. In questo modo, aspetteremo la scadenza e il rilascio automatico di tutte le chiavi che erano attive al momento del guasto.

Utilizzando i riavvii posticipati, è fondamentalmente possibile raggiungere la sicurezza anche in assenza di una persistenza 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 degli istanze, il sistema diventerà globalmente inaccessibile per la durata del TTL (e nessuna risorsa potrà essere bloccata durante questo periodo).

Aumentiamo la disponibilità dell'algoritmo: estendiamo il blocco

Se il lavoro eseguito dai clienti consiste in piccole fasi, è possibile accorciare il tempo di attivazione predefinito del blocco e implementare un meccanismo di estensione dei blocchi. Fondamentalmente, se il cliente è impegnato in calcoli e il valore della durata del blocco rischia di ridursi pericolosamente, è 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 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 entro il tempo di attivazione.

Tuttavia, tecnicamente l'algoritmo non cambia, quindi il numero massimo di tentativi di acquisizione del blocco deve essere limitato, altrimenti si violerebbero le proprietà di disponibilità.

Fonte: habr.com

Lock distribuiti con l'uso di Redis