ProHoster > Blog > amministrazione > Blocco distribuito utilizzando Redis

Blocco distribuito utilizzando Redis

Ehi Habr!

Oggi vi offriamo la traduzione di un articolo complesso sull'implementazione di lock distribuiti utilizzando Redis e vi suggeriamo di approfondire le prospettive di Redis come argomento. Analisi dell'algoritmo Redlock in questione da parte di Martin Kleppman, autore del libro "Applicazioni ad alto carico", è dato qui.

I blocchi distribuiti sono una primitiva molto utile utilizzata in molti ambienti in cui diversi processi devono lavorare su risorse condivise in modo reciprocamente esclusivo.

Esistono numerose librerie e post che descrivono come implementare un DLM (Distributed Lock Manager) utilizzando Redis, ma ogni libreria adotta un approccio diverso e le garanzie che fornisce sono piuttosto deboli rispetto a quanto si può ottenere con una progettazione leggermente più sofisticata.

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

Implementazione

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

Garanzie di sicurezza e disponibilità

Modelliamo il nostro progetto con solo tre proprietà che riteniamo forniscano le garanzie minime necessarie per utilizzare efficacemente i blocchi distribuiti.

  1. Proprietà di sicurezza: mutua esclusione. Solo un client può mantenere un blocco in un dato momento.
  2. Proprietà di disponibilità A: nessun deadlock. È sempre possibile ottenere un blocco, anche se il client che ha bloccato la risorsa fallisce o viene spostato su un segmento di disco diverso.
  3. Proprietà di disponibilità B: tolleranza agli errori. Finché la maggior parte dei nodi Redis è attiva, i client sono in grado di acquisire e rilasciare blocchi.

Perché un'implementazione basata su failover non è sufficiente in questo caso
Per capire cosa miglioreremo, analizziamo lo stato attuale della maggior parte delle librerie di blocco distribuite basate su Redis.

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

A prima vista, questa soluzione funziona, ma c'è un problema: la nostra architettura introduce un singolo punto di errore. Cosa succede se l'istanza master di Redis fallisce? Aggiungiamo allora uno slave! E usiamolo se il master non è disponibile. Purtroppo, questa non è un'opzione praticabile. Così facendo, non saremo in grado di implementare correttamente la proprietà di mutua esclusione necessaria per la sicurezza, perché la replica in Redis è asincrona.

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

  1. Il client A acquisisce un blocco sul master.
  2. Il master fallisce prima che l'immissione della chiave venga trasmessa allo slave.
  3. Il seguace viene promosso a leader.
  4. Il client B acquisisce un blocco sulla stessa risorsa che è già bloccata da A. VIOLAZIONE DELLA SICUREZZA!

A volte è perfettamente normale che più client mantengano un blocco contemporaneamente in circostanze particolari, come un guasto. In questi casi, è possibile utilizzare una soluzione basata sulla replica. In caso contrario, consigliamo la soluzione descritta in questo articolo.

Implementazione corretta con una singola istanza

Prima di provare a superare le carenze della configurazione a istanza singola descritta sopra, vediamo come gestire correttamente questo semplice caso, perché una soluzione del genere è effettivamente accettabile nelle applicazioni in cui le condizioni di gara sono occasionalmente accettabili e perché il blocco a istanza singola è la base dell'algoritmo distribuito qui descritto.

Per acquistare una serratura, procederemo come segue:

SET resource_name my_random_value NX PX 30000

Questo comando installa la chiave solo se non esiste già (opzione NX), con un tempo di scadenza 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.
In pratica, il valore casuale viene utilizzato per rilasciare il blocco in modo sicuro, tramite uno script che dice a Redis di eliminare la chiave solo se esiste e se il valore in essa memorizzato è esattamente quello previsto. Questo si ottiene con il seguente script Lua:

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

Questo è importante per evitare che un blocco impostato da un altro cliente venga rimosso. Ad esempio, un cliente potrebbe acquistare un lucchetto, poi essere bloccato fuori durante un'operazione che dura più a lungo del primo blocco (in modo che la chiave scada) e in seguito rimuovere il lucchetto impostato da un altro cliente.
Utilizzare un semplice DEL non è sicuro, perché un client può eliminare un blocco impostato da un altro client. Al contrario, utilizzando lo script sopra, ogni blocco viene "firmato" con una stringa casuale, quindi solo il client che lo ha precedentemente impostato può eliminarlo.

Quale dovrebbe essere questa stringa casuale? Immagino che dovrebbe essere di 20 byte da /dev/urandom, ma esistono modi più economici per rendere la stringa sufficientemente univoca per i tuoi scopi. Ad esempio, puoi usare il seed RC4 da /dev/urandom, quindi generare un flusso pseudo-casuale da questo. Una soluzione più semplice prevede una combinazione di tempo Unix con risoluzione in microsecondi più un ID client; non è altrettanto sicuro, ma probabilmente adeguato per la maggior parte dei contesti.

Il tempo che utilizziamo come proxy per la durata di una chiave è chiamato "durata del blocco". Questo valore rappresenta sia il tempo trascorso il quale il blocco verrà automaticamente rilasciato, sia il tempo che un client deve eseguire un'operazione prima che un altro client possa a sua volta bloccare la risorsa senza violare effettivamente la garanzia di mutua esclusione. Questa garanzia è limitata solo da una certa finestra temporale, che inizia al momento dell'acquisizione del blocco.

Abbiamo quindi discusso un buon modo per acquisire e rilasciare un lock. Il sistema (se parliamo di un sistema non distribuito costituito da una singola istanza sempre disponibile) è sicuro. Estendiamo questo concetto a un sistema distribuito, dove non abbiamo tali garanzie.

Algoritmo Redlock

La versione distribuita dell'algoritmo presuppone la presenza di N master Redis. Questi nodi sono completamente indipendenti l'uno dall'altro, quindi non utilizziamo la replicazione o altri sistemi di coordinamento impliciti. Abbiamo già descritto come acquisire e rilasciare in modo sicuro un lock su una singola istanza. Diamo per scontato che l'algoritmo utilizzi questo metodo quando lavora con una singola istanza. Nei nostri esempi, impostiamo N a 5, che è un valore ragionevole. Pertanto, dovremo utilizzare 5 master Redis su computer o macchine virtuali diversi per garantire che agiscano in modo ampiamente indipendente l'uno dall'altro.

Per acquistare una serratura, il cliente esegue le seguenti operazioni:

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

L'algoritmo è asincrono?

Questo algoritmo si basa sul presupposto che, sebbene non esista un orologio sincronizzato su cui operano tutti i processi, l'ora locale in ogni processo scorre comunque approssimativamente alla stessa velocità e l'errore è piccolo rispetto al tempo totale trascorso il quale il blocco viene automaticamente rilasciato. 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 varianza oraria tra computer diversi sia minima.

A questo punto, dobbiamo formulare la nostra regola di mutua esclusione con maggiore attenzione: la mutua esclusione è garantita solo se il client che detiene il blocco termina entro il tempo di validità del blocco (il valore ottenuto nel passaggio 3), meno un po' di tempo aggiuntivo (solo pochi millisecondi per compensare il ritardo temporale tra i processi).

Il seguente interessante articolo fornisce maggiori dettagli su tali sistemi che richiedono un coordinamento basato sul ritardo temporale: Leases: un meccanismo efficiente e tollerante agli errori per la coerenza della cache dei file distribuiti.

Riprova in caso di errore

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

Vale la pena sottolineare qui quanto sia importante che i client che non riescono ad acquisire la maggior parte dei loro blocchi rilascino (parzialmente) i blocchi acquisiti, in modo da non dover attendere la scadenza della chiave prima che un blocco sulla risorsa possa essere acquisito nuovamente (sebbene si verifichi una frammentazione della rete e il client perda la connettività alle istanze Redis, si verifica una penalità per il problema di disponibilità durante l'attesa della scadenza della chiave).

Rilasciare il blocco

Il rilascio di un blocco è un'operazione semplice che richiede semplicemente lo sblocco di tutte le istanze, indipendentemente dal fatto che il client ritenga di essere riuscito a bloccare con successo una particolare istanza.

Considerazioni sulla sicurezza

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

Innanzitutto, supponiamo che il client sia riuscito a ottenere un blocco sulla maggior parte delle istanze. Ognuna di esse 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. Tuttavia, se la prima chiave è stata installata in un momento non peggiore di T1 (il momento scelto prima di contattare il primo server) e l'ultima chiave è stata installata in un momento non peggiore di T2 (il momento in cui è stata ricevuta la risposta dall'ultimo server), allora siamo sicuri che la prima chiave del set che scade esisterà almeno MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFTTutte le altre chiavi scadranno in seguito, quindi possiamo essere certi che tutte le chiavi saranno valide contemporaneamente per almeno questo periodo di tempo.

Durante il periodo in cui la maggior parte delle chiavi rimane valida, un altro client non sarà in grado di acquisire il blocco, poiché N/2+1 operazioni SET NX non possono avere successo se esistono già N/2+1 chiavi. Pertanto, una volta acquisito un blocco, è impossibile riacquisirlo contemporaneamente (ciò violerebbe la proprietà di mutua esclusione).
Tuttavia, vogliamo assicurarci che più clienti non riescano ad acquistare una serratura contemporaneamente.

Se il client ha bloccato la maggior parte delle istanze in un tempo prossimo o superiore alla durata massima del blocco, considererà il blocco non valido e sbloccherà le istanze. Pertanto, dobbiamo considerare solo il caso in cui il client è riuscito a bloccare la maggior parte delle istanze in un tempo inferiore alla scadenza. In questo caso, rispetto all'argomentazione precedente, in MIN_VALIDITY Nessun client dovrebbe essere in grado di riacquisire il blocco. Pertanto, più client saranno in grado di bloccare N/2+1 istanze contemporaneamente (che termina al completamento della fase 2) solo quando il tempo per bloccare la maggioranza è maggiore del tempo TTL, il che invalida il blocco.

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

Considerazioni sull'accessibilità

La disponibilità di un sistema dipende da tre caratteristiche principali:

  1. Sblocco automatico (alla scadenza delle chiavi): le chiavi saranno di nuovo disponibili per essere utilizzate per le serrature.
  2. Il fatto che i clienti solitamente si aiutino a vicenda rimuovendo le serrature quando la serratura che desiderano non è stata acquisita, oppure è stata acquisita e il lavoro è stato completato; quindi è probabile che non dovremo aspettare che le chiavi scadano per riacquisire una serratura.
  3. Il fatto che quando un client deve riprovare ad acquisire un lock, attenda un periodo di tempo relativamente più lungo rispetto a quello necessario per la maggior parte dei lock. Ciò riduce la probabilità di una situazione di "split brain" derivante dalla contesa per le risorse.

Tuttavia, esiste una penalità per il degrado della disponibilità pari al tempo TTL sui segmenti di rete, quindi in presenza di segmenti contigui, questa penalità può diventare indefinita. Questo accade ogni volta che un client acquisisce un blocco e viene poi escluso da un altro segmento prima di poterlo rilasciare.

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

Prestazioni, failover e fsync

Molti utenti utilizzano Redis perché desiderano un server di lock ad alte prestazioni, in termini di latenza richiesta per acquisire e rilasciare i lock e di numero di tali acquisizioni/rilasci che possono essere eseguiti al secondo. Per soddisfare questo requisito, esiste una strategia per comunicare con N server Redis al fine di ridurre la latenza. Si tratta di una strategia di multiplexing (o "multiplexing del povero", in cui il socket è impostato in modalità non bloccante, invia tutti i comandi e li legge in un secondo momento, presupponendo che il tempo di andata e ritorno tra il client e ciascuna istanza sia simile).

Tuttavia, se vogliamo creare un modello con un ripristino affidabile in caso di guasto, dobbiamo anche tenere conto dell'archiviazione dei dati a lungo termine.

In pratica, per chiarire il problema, ipotizziamo di configurare Redis senza alcun tipo di archiviazione dati persistente. Un client riesce a bloccare 3 delle 5 istanze. Una delle istanze che il client è riuscito a bloccare viene riavviata e, a quel punto, ci sono di nuovo 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 prevede l'esclusività dei blocchi.

Abilitando la persistenza anticipata (AOF), la situazione migliora leggermente. Ad esempio, è possibile avviare il server inviando il comando SHUTDOWN e riavviandolo. Poiché le operazioni di scadenza di Redis sono implementate semanticamente in modo tale che il tempo continui a scorrere anche quando il server è offline, tutto funziona correttamente con tutti i nostri requisiti. Finché è garantito uno spegnimento regolare. Ma cosa fare in caso di interruzioni di corrente? Se Redis è configurato di default, con la sincronizzazione fsync su disco ogni secondo, è possibile che dopo un riavvio la chiave venga persa. In teoria, se vogliamo garantire la sicurezza dei blocchi durante qualsiasi riavvio dell'istanza, dovremmo abilitare fsync=always nelle impostazioni di conservazione dei dati a lungo termine. Ciò comprometterà completamente le prestazioni, al livello di sistemi CP tradizionalmente utilizzati per l'implementazione sicura di blocchi distribuiti.

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

Per garantire ciò, dobbiamo semplicemente accertarci che, dopo un errore, l'istanza rimanga non disponibile per un periodo di tempo leggermente superiore al TTL massimo che stiamo utilizzando, in modo che tutte le chiavi attive al momento dell'errore scadano e vengano rilasciate automaticamente.

Utilizzando riavvii ritardati, è possibile, in linea di principio, garantire la sicurezza anche in assenza di persistenza a lungo termine in Redis. Si noti, tuttavia, che ciò potrebbe comportare una penalità per violazione della disponibilità. 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).

Aumentare la disponibilità dell'algoritmo: estendere il blocco

Se il lavoro svolto dai client consiste in piccoli passi, è possibile ridurre la durata predefinita del blocco e implementare un meccanismo per estendere i blocchi. In linea di principio, se un client è impegnato a elaborare e il valore della durata del blocco è pericolosamente basso, è possibile inviare uno script Lua a tutte le istanze che estenda il TTL della chiave, se la chiave esiste ancora e il suo valore è ancora quello casuale ottenuto al momento dell'acquisizione del blocco.

Un cliente dovrebbe considerare un blocco da riacquisire solo se ha bloccato con successo la maggior parte delle istanze entro il periodo di validità.

È vero che tecnicamente l'algoritmo non cambia, quindi il numero massimo di tentativi ripetuti di acquisizione dei blocchi deve essere limitato, altrimenti le proprietà di disponibilità verranno violate.

Fonte: habr.com