Salut, Habr!
Astăzi, vă propunem un articol complex despre implementarea blocajelor distribuite folosind Redis și discutăm despre perspectivele lui Redis ca temă. Analizăm algoritmul Redlock de Martin Kleppmann, autorul cărții "", se prezintă .
Blocajele distribuite sunt un primitiv foarte util, utilizat în multe medii în care procese diferite trebuie să lucreze asupra resurselor partajate pe baza excluderii reciproce.
Există o serie de biblioteci și articole care descriu cum să implementați DLM (manager de blocaje distribuite) folosind Redis, dar fiecare bibliotecă folosește o abordare proprie, iar garanțiile oferite sunt destul de slabe comparativ cu ceea ce se poate obține printr-un design puțin mai complex.
În acest articol, ne vom strădui să descriem un algoritm considerat canonic, demonstrând cum se pot implementa blocajele distribuite folosind Redis. Vom vorbi despre algoritmul numit Redlock, care implementează un manager de blocaje distribuite și, din punctul nostru de vedere, acest algoritm este mai sigur decât abordarea obișnuită cu o singură instanță. Sperăm că comunitatea îl va analiza, va oferi feedback și îl va folosi ca punct de plecare pentru realizarea unor proiecte mai complexe sau alternative.
Implementări
Înainte de a trece la descrierea algoritmului, vom oferi câteva linkuri către implementări deja realizate. Acestea pot fi utilizate ca referință.
- (implementare pentru Ruby). Există, de asemenea, Redlock-rb, care adaugă un pachet (gem) pentru ușurința distribuită, și nu numai pentru acest scop.
- (implementare pentru Python).
- (implementare pentru Asyncio Python).
- (implementare pentru PHP).
- (o altă implementare pentru PHP)
- (bibliotecă PHP pentru blocaje)
- (implementare pentru Go).
- (implementare pentru Java).
- (implementare pentru Perl).
- (implementare pentru C++).
- (implementare pentru C#/.NET).
- (implementare pentru C#/.NET). Cu suport pentru extensii async și blocare.
- (implementare pentru C# .NET cu stocare de date configurabilă)
- (implementare pentru C# .NET)
- (implementare pentru NodeJS). Include suport pentru prelungirea blocajelor.
Garanții de securitate și disponibilitate
Ne propunem să modelăm proiectul nostru cu doar trei proprietăți, care, în opinia noastră, oferă garanțiile minime necesare pentru utilizarea eficientă a blocărilor distribuite.
- Proprietate de securitate: Excludere reciprocă. În orice moment, doar un singur client poate deține o blocare.
- Proprietate de disponibilitate A: Lipsa blocajelor circulare. În cele din urmă, blocarea poate fi obținută întotdeauna, chiar dacă clientul care a blocat resursa eșuează sau este mutat pe un alt segment al discului.
- Proprietate de disponibilitate B: Rezistență la erori. Atâta timp cât majoritatea nodurilor Redis funcționează, clienții pot obține și elibera blocări.
De ce o implementare bazată pe recuperarea după erori este insuficientă în acest caz.
Pentru a înțelege ce anume dorim să îmbunătățim, haideți să analizăm situația actuală cu majoritatea bibliotecilor pentru blocări distribuite bazate pe Redis.
Cel mai simplu mod de a bloca un resurs utilizând Redis este de a crea o cheie în instanță. De obicei, cheia este creată cu un timp limitat de viață, ceea ce se realizează prin intermediul funcției expires oferite de Redis, astfel încât, mai devreme sau mai târziu, această cheie va fi eliberată (proprietatea 2 din lista noastră). Când clientul trebuie să elibereze resursa, acesta șterge cheia.
La prima vedere, această soluție funcționează bine, dar există o problemă: în arhitectura noastră apare un singur punct de eșec. Ce se va întâmpla dacă instanța principală Redis eșuează? Atunci să adăugăm o instanță secundară! Și o vom folosi atunci când principalul nu este disponibil. Din păcate, această variantă nu este viabilă. Procedând astfel, nu putem implementa corect proprietatea de excludere reciprocă de care avem nevoie pentru a asigura securitatea, deoarece replicarea în Redis este asincronă.
Este evident că într-un astfel de model apare o stare de competiție:
- Clientul A obține o blocare pe instanța principală.
- Instanța principală eșuează înainte de a transmite înregistrarea cheii la instanța secundară.
- Instanța secundară devine instanța principală.
- Clientul B obține blocarea aceleași resurse, care deja este blocată de A. ÎNCĂLCARE A SĂNĂTĂȚII!
Uneori, este complet normal ca, în circumstanțe speciale, de exemplu în cazul unei erori, mai mulți clienți să dețină simultan o blocare. În aceste cazuri se poate aplica o soluție bazată pe replicare. În celelalte cazuri, recomandăm soluția descrisă în acest articol.
Implementarea corectă cu un singur instanță
Înainte de a încerca să depășim dezavantajele configurației cu un singur instanță, descrisă mai sus, să analizăm cum să acționăm corect în acest caz simplu, deoarece această soluție este de fapt acceptabilă în acele aplicații unde starea de concurență este ocazional permisă și, de asemenea, deoarece blocarea pe un singur instanță servește drept bază folosită în algoritmul distribuit descris aici.
Pentru a obține blocarea, vom proceda astfel:
SET resource_name my_random_value NX PX 30000
Această comandă setează cheia, doar dacă aceasta nu există deja (opțiunea NX), cu o durată de 30000 de milisecunde (opțiunea PX). Pentru cheie se setează valoarea "myrandomvalue". Această valoare trebuie să fie unică în toate clienții și toate solicitările de blocare.
În principiu, valoarea aleatoare este utilizată pentru a elibera în siguranță blocarea, folosind un script care informează Redis: șterge cheia, doar dacă aceasta există, și valoarea stocată în ea este exact ceea ce a fost așteptat. Acest lucru se realizează cu ajutorul următorului script în Lua:
if redis.call("get", KEYS[1]) == ARGV[1] then
return redis.call("del", KEYS[1])
else
return 0
endEste important să nu se permită eliberarea blocării efectuate de un alt client. De exemplu, un client poate obține o blocare, apoi poate rămâne blocat în timpul unei operațiuni care durează mai mult decât perioada inițială de blocare (astfel încât perioada de valabilitate a cheii să expire), și ulterior să elimine blocarea pusă de un alt client.
Utilizarea simplului DEL nu este sigură, deoarece clientul poate șterge blocarea pusă de un alt client. Pe de altă parte, utilizarea scriptului descris mai sus, fiecare blocare este "semnată" cu un șir aleatoriu, astfel încât să o poată elimina doar clientul care a pus-o anterior.
Ce ar trebui să fie această stringă aleatorie? Cred că ar trebui să fie 20 de bytes din /dev/urandom, dar există și modalități mai puțin costisitoare de a face o stringă suficient de unică pentru scopurile pe care le ai. De exemplu, ar fi bine să semeni RC4 cu /dev/urandom și apoi să generezi un flux pseudo-aleator pe baza lui. O soluție mai simplă implică combinarea timpului unix în rezoluție de microsecunde plus ID-ul clientului; nu este atât de sigură, dar probabil se aliniază nivelului de cerințe din majoritatea contextelor.
Timpul pe care îl folosim ca indicator al duratei de viață a cheii se numește „timp de acțiune a blocării”. Acesta este, de asemenea, termenul după care blocarea se va elibera automat și timpul pe care îl are clientul pentru a efectua operațiunea înainte ca un alt client să poată, la rândul său, să blocheze această resursă, fără a încălca efectiv garanțiile de exclusivitate. Această garanție este limitată doar de o fereastră specifică de timp care începe din momentul obținerii blocării.
Așadar, am discutat despre o modalitate bună de a obține și elibera o blocare. Sistemul (dacă ne referim la un sistem nedistribuit care constă dintr-un singur și mereu disponibil instanță) este sigur. Să extindem această concepție la un sistem distribuit, în care nu avem astfel de garanții.
Algoritmul Redlock
În versiunea distribuită a algoritmului, se presupune că avem N instanțe principale de Redis. Aceste noduri sunt complet independente unele de altele, astfel încât nu utilizăm replicarea sau orice alt sistem de coordonare implicit. Am explicat deja cum să obții și să eliberezi în siguranță o blocare pe o singură instanță. Acceptăm ca axiomatic faptul că algoritmul, atunci când lucrează cu o instanță unică, va folosi această metodă. În exemplele noastre, stabilim N egal cu 5, un număr destul de rezonabil. Astfel, va trebui să folosim 5 instanțe principale de Redis pe diferite computere sau mașini virtuale pentru a garanta că acestea vor acționa în principal independent unele de altele.
Pentru a obține o blocare, clientul efectuează următoarele operațiuni:
- Obține timpul curent în milisecunde.
- Își încearcă în mod constant să obțină o blocare pe toate cele N instanțe, folosind aceeași denumire de cheie și valori aleatorii în toate cazurile. În etapa 2, la setarea blocării pentru fiecare instanță, clientul folosește o întârziere, care este destul de scurtă în comparație cu timpul după care blocarea este eliminată automat. De exemplu, dacă durata blocării este de 10 secunde, atunci întârzierea poate varia între ~ 5-50 milisecunde. Astfel, se evită situația în care clientul ar putea rămâne blocat o lungă perioadă de timp, încercând să se conecteze la un nod Redis care a cedat: dacă instanța nu este disponibilă, încercăm cât mai curând posibil să ne conectăm la o altă instanță.
- Pentru a obține blocarea, clientul calculează cât timp a trecut; pentru aceasta, el scade din valoarea curentă a timpului marca de timp obținută în pasul 1. Atunci și doar atunci când clientul a reușit să obțină blocarea pe majoritatea instanțelor (cel puțin 3), iar timpul total necesar pentru a obține blocarea este mai mic decât timpul de valabilitate al blocării, se consideră că obținerea blocării a avut loc.
- Dacă blocarea a fost obținută, termenul de valabilitate al acesteia este considerat a fi valoarea inițială a duratei blocării minus timpul scurs, calculat în pasul 3.
- Dacă clientului, dintr-un anumit motiv, nu i-a reușit să obțină blocarea (fie că nu a putut bloca N/2+1 instanțe, fie că timpul de valabilitate al blocării a fost negativ), atunci va încerca să deblocheze toate instanțele (chiar și pe cele despre care s-a crezut că nu le putea bloca).
Este algoritmul asincron?
Acest algoritm se bazează pe asumția că, deși nu există ceasuri sincronizate la care să lucreze toate procesele, timpul local din fiecare proces curge totuși aproximativ în aceeași viteză, iar eroarea este mică în comparație cu timpul total după care blocarea este eliminată automat. Această presupunere este foarte similară situației caracteristice computerelor obișnuite: fiecare computer are ceasuri locale, iar de obicei ne putem baza pe faptul că devierile de timp între diferite computere sunt mici.
În această etapă, trebuie să formulăm mai clar regula noastră de excludere reciprocă: excluderea reciprocă este garantată doar cu condiția ca clientul care reține blocajul să finalizeze activitatea în timpul în care blocajul este activ (această valoare este obținută la pasul 3), minus un timp suplimentar (de câteva milisecunde, pentru a compensa abaterile de timp între procese).
Mai multe informații despre astfel de sisteme, care necesită alinierea abaterii de timp, se spun în următorul articol interesant: .
Reîncercarea în caz de eșec
Când clientul nu reușește să obțină blocajul, acesta trebuie să încerce din nou, suportând o întârziere aleatorie; acest lucru se face pentru a desincroniza mai mulți clienți care încearcă simultan să achiziționeze blocajul aceluiași resursă (ceea ce poate duce la situația „creierului împărțit”, în care nu există câștigători). În plus, cu cât clientul încearcă mai repede să obțină blocajul de la majoritatea instanțelor Redis, cu atât fereastra în care poate apărea situația de creier împărțit devine mai strânsă (și cu atât mai puțin necesare sunt reîncercările). Prin urmare, în ideal, clientul ar trebui să încerce să trimită simultan comenzi SET către N instanțe prin multiplexare.
Este important să subliniem cât de esențial este ca clienții care nu au reușit să obțină majoritatea blocajelor să elibereze (parțial) blocajele deja obținute, pentru a nu fi nevoie să aștepte expirarea cheii, înainte ca blocajul asupra resursei să poată fi obținut din nou (însă, dacă apare o fragmentare a rețelei și clientul pierde conexiunea cu instanțele Redis, atunci se plătește o penalizare pentru încălcarea disponibilității, în timp ce se așteaptă expirarea cheii).
Eliberarea blocajului
Eliberarea blocajului este o operațiune simplă, care necesită doar deblocarea tuturor instanțelor, indiferent dacă clientul crede că a reușit să blocheze cu succes o instanță specifică.
Considerații de securitate
Este algoritmul sigur? Să încercăm să ne imaginăm ce se întâmplă în diferite scenarii.
Să presupunem mai întâi că clientul a reușit să obțină blocarea asupra majorității instanțelor. Fiecare dintre aceste instanțe va conține o cheie cu aceeași durată de viață pentru toate. Cu toate acestea, fiecare dintre aceste chei a fost setată într-un moment diferit, astfel că termenul lor de valabilitate va expira la momente diferite. Dar, dacă prima cheie a fost setată într-un moment nu mai rău de T1 (timpul pe care îl alegem înainte de a contacta primul server), iar ultima cheie a fost setată într-un moment nu mai rău de T2 (timpul în care am primit răspunsul de la ultimul server), atunci suntem siguri că prima cheie din mulțimea a cărei valabilitate va expira va exista cel puțin MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Toate celelalte chei vor expira mai târziu, așa că putem fi siguri că toate cheile vor fi valabile simultan pentru cel puțin acest timp.
În timpul în care majoritatea cheilor rămân valabile, un alt client nu va putea obține blocarea, deoarece operațiunile N/2+1 SET NX nu pot termina cu succes dacă există deja N/2+1 chei. Prin urmare, dacă blocarea a fost obținută, nu o va putea obține din nou în același moment (acest lucru ar încălca proprietatea de excludere mutuală).
Adevărul este că vrem să ne asigurăm că un grup de clienți care încearcă în același timp să obțină blocarea nu vor putea reuși simultan.
Dacă un client a blocat majoritatea instanțelor, consumând un timp similar sau mai mare decât timpul maxim de durată a blocării, atunci va considera că blocarea este invalidă și va debloca instanțele. Prin urmare, trebuie să luăm în considerare doar situația în care clientul a reușit să blocheze majoritatea instanțelor într-un timp mai scurt decât durata de valabilitate. În acest caz, în ceea ce privește argumentul de mai sus, pentru timpul MIN_VALIDITY niciun client nu ar trebui să fie capabil să obțină din nou blocarea. Prin urmare, mai mulți clienți vor putea bloca N/2+1 instanțe în același timp (care se finalizează în momentul încheierii etapei 2) doar atunci când timpul pentru blocarea majorității a fost mai mare decât timpul TTL, ceea ce face ca blocarea să devină invalidă.
Iar tu poți oferi o dovadă formală a securității, să precizezi algoritmii similari existenți sau să găsești o eroare în explicația dată?
Considerații privind disponibilitatea
Disponibilitatea sistemului depinde de trei caracteristici principale:
- Dezactivarea automată a blocării (deoarece valabilitatea cheilor expiră): în cele din urmă, cheile vor fi disponibile din nou pentru a fi utilizate pentru blocări.
- Faptul că clienții se ajută reciproc, îndepărtând blocările atunci când blocarea necesară nu a fost achiziționată, fie a fost achiziționată, iar lucrarea s-a încheiat; prin urmare, este foarte posibil să nu trebuiască să așteptăm expirarea cheilor pentru a reachiziționa blocarea.
- Faptul că, atunci când clientul trebuie să încerce din nou să obțină blocarea, așteaptă o perioadă relativ mai lungă decât perioada necesară pentru a achiziționa majoritatea blocărilor. Astfel scade probabilitatea apariției unei situații de „minte divizată” în competiția pentru resurse.
Cu toate acestea, trebuie să plătim o penalizare pentru reducerea disponibilității, echivalentă cu timpul TTL în segmentele rețelei, astfel încât, dacă există segmente continue, această penalizare poate atinge o dimensiune nesigură. Acest lucru se întâmplă de fiecare dată când clientul achiziționează o blocare și apoi se deconectează în alt segment înainte de a reuși să o elibereze.
În principiu, cu segmente continue infinite în rețea, sistemul poate rămâne indisponibil pentru o perioadă infinită de timp.
Performanță, recuperare în caz de defecțiune și fsync
Multe persoane folosesc Redis, deoarece este necesar să asigure o performanță înaltă a serverului de blocare, la nivelul întârzierilor necesare pentru achiziționarea și eliberarea blocărilor, precum și a numărului de operațiuni de achiziție/eliberare care pot fi realizate pe secundă. Pentru a satisface această cerință, există o strategie de comunicare cu N servere Redis pentru a reduce întârzierea. Această strategie este multiplexarea (sau „multiplexarea săracului”, unde socketul este setat în mod neblocat, trimite toate comenzile și citește comenzile mai târziu, presupunând că timpul de rotație între client și fiecare dintre instanțe este similar).
Adevărat, trebuie să luăm în considerare și problema stocării pe termen lung a datelor, dacă dorim să creăm un model cu recuperare fiabilă în caz de defecțiuni.
În principiu, pentru a clarifica problema, să presupunem că configurăm Redis fără stocare persistentă a datelor. Clientul reușește să blocheze 3 din 5 instanțe. Una dintre instanțele pe care clientul a reușit să o blocheze se repornește, iar în acel moment apar din nou 3 instanțe pentru același resurs, pe care le putem bloca, iar alt client poate, la rândul său, să blocheze instanța repornită, încălcând proprietatea de securitate care presupune exclusivitatea blocărilor.
Dacă activăm salvarea anticipată a datelor (AOF), situația se îmbunătățește puțin. De exemplu, putem să ridicăm serverul, trimițând comanda SHUTDOWN și repornindu-l. Deoarece operațiile de expirare în Redis sunt implementate astfel încât timpul continuă să curgă și atunci când serverul este oprit, totul este în regulă cu toate cererile noastre. Este în regulă atâta timp cât se asigură o oprire normală. Dar ce facem în cazul întreruperilor de alimentare? Dacă Redis este configurat implicit, cu fsync sincronizat pe disc la fiecare secundă, este posibil ca după repornire să nu mai găsim cheia noastră. Teoretic, dacă vrem să garantăm securitatea blocărilor în orice repornire a instanței, trebuie să activăm fsync=always în setările de stocare persistentă a datelor. Aceasta va afecta complet performanța, ajungând la nivelul sistemelor CP care sunt utilizate tradițional pentru implementarea sigură a blocărilor distribuite.
Dar situația este mai bună decât pare la prima vedere. În principiu, securitatea algoritmului se menține, deoarece, atunci când o instanță se repornește după o defecțiune, aceasta nu mai participă la nicio blocare activă în acel moment.
Pentru a garanta acest lucru, este suficient să ne asigurăm că, după o defecțiune, instanța rămâne inaccesibilă pentru o perioadă care depășește ușor maximul TTL pe care îl folosim. Astfel, vom aștepta expirarea și eliberarea automată a tuturor cheilor care au fost active în momentul defecțiunii.
Folosind repornirile întârziate, este în principiu posibil să se obțină siguranța și în absența unei stocări pe termen lung în Redis. Trebuie să menționăm că acest lucru poate duce la penalizări pentru nerespectarea disponibilității. De exemplu, în cazul în care majoritatea instanțelor eșuează, sistemul va deveni global inaccesibil pe durata TTL (și niciun resursă nu va putea fi blocată în acest timp).
Creștem disponibilitatea algoritmului: extindem blocarea
Dacă activitatea desfășurată de clienți constă în etape mici, atunci este posibil să scurtăm timpul de valabilitate a blocării stabilit implicit și să implementăm un mecanism de extindere a blocărilor. În principiu, dacă clientul este ocupat cu calcule, iar valoarea duratei de viață a blocării scade periculos, se poate trimite tuturor instanțelor un script Lua care extinde TTL-ul cheii, dacă cheia mai există și valoarea sa este în continuare aleatoare, obținută atunci când a fost obținută blocarea.
Clientul trebuie să considere blocarea că fiind recapturată doar în cazul în care a reușit să blocheze majoritatea instanțelor în timpul valabilității.
Adevărul este că, din punct de vedere tehnic, algoritmul nu se schimbă, prin urmare numărul maxim de încercări repetate de a obține blocarea trebuie să fie limitat, altfel vor fi afectate proprietățile de disponibilitate.
Sursa: habr.com
