ProHoster > BLOG > administrare > Blocare distribuită folosind Redis

Blocare distribuită folosind Redis

Hei Habr!

Astăzi vă aducem în atenție o traducere a unui articol complex despre implementarea blocării distribuite folosind Redis și vă invităm să vorbiți despre perspectivele Redis ca subiect. Analiza algoritmului Redlock în cauză de la Martin Kleppmann, autorul cărții "Aplicații cu sarcină mare", dat aici.

Blocarea distribuită este o primitivă foarte utilă folosită în multe medii în care diferite procese trebuie să lucreze pe resurse partajate într-un mod care se exclude reciproc.

Există o serie de biblioteci și postări care descriu cum să implementați DLM (Manager de blocare distribuită) folosind Redis, dar fiecare bibliotecă adoptă o abordare diferită și garanțiile pe care le oferă sunt destul de slabe în comparație cu ceea ce se poate realiza cu un design puțin mai sofisticat.

În acest articol vom încerca să descriem un algoritm canonic condiționat care demonstrează cum să implementăm blocarea distribuită folosind Redis. Vom vorbi despre un algoritm numit redlock, implementează un manager de blocare distribuit și, în opinia noastră, 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 proiecte mai complexe sau alternative.

Implementare

Înainte de a trece la descrierea algoritmului, oferim câteva link-uri către implementări gata făcute. Ele pot fi folosite pentru referință.

Securitate și garanții de disponibilitate

Ne vom modela designul cu doar trei proprietăți despre care credem că oferă garanțiile minime necesare pentru a utiliza în mod eficient blocarea distribuită.

  1. Proprietate de securitate: excludere reciprocă. În orice moment, un singur client poate ține lacătul.
  2. Disponibilitate Proprietatea A: Fără blocaje. Este întotdeauna posibil să obțineți în cele din urmă o blocare, chiar dacă clientul care a blocat resursa eșuează sau aterizează pe un alt segment de disc.
  3. Disponibilitate Proprietatea B: Toleranță la erori. Atâta timp cât majoritatea nodurilor Redis rulează, clienții pot obține și elibera blocări.

De ce implementarea bazată pe recuperarea eșecului nu este suficientă în acest caz
Pentru a înțelege ce vom îmbunătăți, să analizăm starea actuală a lucrurilor cu cele mai multe biblioteci de blocare distribuite bazate pe Redis.

Cel mai simplu mod de a bloca o resursă folosind Redis este să creați o cheie în instanță. De obicei, o cheie este creată cu o durată de viață limitată, acest lucru se realizează utilizând caracteristica de expirare furnizată în Redis, așa că mai devreme sau mai târziu această cheie este eliberată (proprietatea 2 din lista noastră). Când clientul trebuie să elibereze resursa, acesta șterge cheia.

La prima vedere, această soluție funcționează destul de bine, dar există o problemă: arhitectura noastră creează un singur punct de eșec. Ce se întâmplă dacă instanța gazdă Redis eșuează? Atunci să adăugăm un sclav! Și îl vom folosi dacă prezentatorul nu este disponibil. Din păcate, această opțiune nu este viabilă. Făcând acest lucru, nu vom putea implementa în mod corespunzător proprietatea de excludere reciprocă de care avem nevoie pentru a asigura securitatea, deoarece replicarea în Redis este asincronă.

Evident, într-un astfel de model apare o condiție de cursă:

  1. Clientul A dobândește o blocare pe master.
  2. Master-ul eșuează înainte ca intrarea cheii să fie transferată către slave.
  3. Adeptul este promovat lider.
  4. Clientul B dobândește o blocare pe aceeași resursă pe care A a blocat-o deja. ÎNCĂLCAREA SECURITATII!

Uneori este complet normal ca în circumstanțe speciale, cum ar fi un eșec, mulți clienți să poată ține lacătul în același timp. În astfel de cazuri, poate fi aplicată o soluție bazată pe replicare. În caz contrar, vă recomandăm soluția descrisă în acest articol.

Implementare corectă cu o singură instanță

Înainte de a încerca să depășim deficiențele configurației cu o singură instanță descrise mai sus, să înțelegem cum să gestionăm corect acest caz simplu, deoarece această soluție este de fapt valabilă în aplicațiile în care o condiție de cursă este acceptabilă din când în când și, de asemenea, pentru că blocarea pe o o singură instanță servește ca bază care este utilizată în algoritmul distribuit descris aici.

Pentru a obține o blocare, procedați astfel:

SET resource_name my_random_value NX PX 30000

Această comandă instalează o cheie doar dacă aceasta nu există deja (opțiune NX), cu o perioadă de valabilitate de 30000 milisecunde (opțiune PX). Tasta este setată la „myrandomvalue" Această valoare trebuie să fie unică pentru toți clienții și pentru toate solicitările de blocare.
Practic, o valoare aleatorie este folosită pentru a elibera în siguranță lacătul, cu un script care îi spune lui Redis: eliminați cheia doar dacă există și valoarea stocată în ea este exact ceea ce era de așteptat. Acest lucru se realizează folosind următorul script Lua:

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

Acest lucru este important pentru a preveni eliminarea unui lacăt deținut de un alt client. De exemplu, un client ar putea să obțină o lacăt, apoi să devină blocat într-o operațiune care durează mai mult decât prima lacăt (astfel încât cheia să aibă timp să expire) și să elimine ulterior lacătul pe care l-a plasat un alt client.
Utilizarea unui simplu DEL este nesigură, deoarece un client poate elimina o blocare deținută de un alt client. În schimb, atunci când se folosește scriptul de mai sus, fiecare lacăt este „semnat” cu un șir aleator, astfel încât numai clientul care a plasat-o anterior îl poate elimina.

Care ar trebui să fie acest șir aleatoriu? Bănuiesc că ar trebui să fie 20 de octeți din /dev/urandom, dar puteți găsi modalități mai puțin costisitoare de a face șirul suficient de unic pentru scopurile dvs. De exemplu, ar fi bine să sesăm RC4 cu /dev/urandom și apoi să generați un flux pseudo-aleatoriu din acesta. O soluție mai simplă implică o combinație de timp Unix în rezoluție de microsecunde plus ID-ul clientului; nu este la fel de sigur, dar probabil că depinde de sarcină în majoritatea contextelor.

Timpul pe care îl folosim ca măsură a duratei de viață a cheii se numește „durata de viață a blocării”. Această valoare este atât perioada de timp înainte ca blocarea să fie eliberată automat, cât și perioada de timp pe care o are un client pentru a finaliza o operațiune înainte ca un alt client să poată, la rândul său, bloca acea resursă, fără a încălca efectiv garanțiile de excludere reciprocă. Această garanție este limitată doar la o anumită fereastră de timp, care începe din momentul achiziționării încuietorii.

Așa că am discutat despre o modalitate bună de a obține și de a elibera un blocaj. Sistemul (dacă vorbim de un sistem nedistribuit format dintr-o singură instanță și întotdeauna disponibilă) este sigur. Să extindem acest concept la un sistem distribuit, unde nu avem astfel de garanții.

Algoritmul Redlock

Versiunea distribuită a algoritmului presupune că avem N maeștri Redis. Aceste noduri sunt complet independente unele de altele, deci nu folosim replicarea sau orice alt sistem implicit de coordonare. Am explicat deja cum să obțineți și să eliberați în siguranță o blocare pe o singură instanță. Considerăm de la sine înțeles că algoritmul, atunci când lucrează cu o singură instanță, va folosi exact această metodă. În exemplele noastre, setăm N la 5, care este o valoare rezonabilă. Astfel, va trebui să folosim 5 master Redis pe diferite computere sau mașini virtuale pentru a ne asigura că acţionează în mare măsură independent unul de celălalt.

Pentru a obține o blocare, clientul efectuează următoarele operații:

  1. Obține ora curentă în milisecunde.
  2. Încearcă secvențial să obțină o blocare pe toate N instanțe, folosind același nume de cheie și valori aleatorii în toate cazurile. În Etapa 2, când clientul configurează o blocare pe o instanță, clientul folosește o întârziere pentru a-l obține, care este suficient de scurtă în comparație cu timpul după care blocarea este eliberată automat. De exemplu, dacă durata blocării este de 10 secunde, atunci întârzierea ar putea fi în intervalul de ~5-50 milisecunde. Acest lucru elimină situația în care clientul ar putea rămâne blocat mult timp încercând să ajungă la un nod Redis eșuat: dacă instanța este indisponibilă, atunci încercăm să ne conectăm la o altă instanță cât mai curând posibil.
  3. Pentru a lua un lacăt, clientul calculează cât timp a trecut; Pentru a face acest lucru, scade din valoarea reală a timpului marcajul de timp care a fost obținut la pasul 1. Dacă și numai dacă clientul a reușit să obțină blocarea pentru majoritatea instanțelor (cel puțin 3) și timpul total necesar pentru a face acest lucru. obținerea blocării, mai mică decât durata blocării, se consideră că blocarea a fost obținută.
  4. Dacă a fost obținută o blocare, durata blocării este considerată ca fiind durata inițială a blocării minus timpul scurs calculat la pasul 3.
  5. Dacă clientul nu reușește să obțină blocarea dintr-un anumit motiv (fie nu a putut bloca N/2+1 instanțe, fie durata blocării a fost negativă), atunci va încerca să deblocheze toate instanțele (chiar și pe cele pe care credea că nu le poate bloca ).

Algoritmul este asincron?

Acest algoritm se bazează pe presupunerea că, deși nu există un ceas sincronizat pe care să funcționeze toate procesele, ora locală din fiecare proces continuă să curgă aproximativ în același ritm, iar eroarea este mică în comparație cu timpul total după care blocarea este eliberat automat. Această ipoteză este foarte asemănătoare cu situația tipică pentru computerele obișnuite: fiecare computer are un ceas local și, de obicei, putem conta pe faptul că diferența de timp între diferite computere este mică.

În acest moment, trebuie să formulăm cu mai multă atenție regula noastră de excludere reciprocă: excluderea reciprocă este garantată numai dacă clientul care deține lacătul iese în perioada în care lacătul este valabil (această valoare obținută la pasul 3), minus ceva mai mult timp (în total câteva milisecunde pentru a compensa diferența de timp dintre procese).

Următorul articol interesant spune mai multe despre astfel de sisteme care necesită coordonarea intervalelor de timp: Leasing: un mecanism eficient tolerant la erori pentru consistența cache-ului de fișiere distribuite.

Reîncercați în caz de eșec

Când un client nu reușește să obțină o blocare, trebuie să încerce din nou după o întârziere aleatorie; aceasta se face pentru a desincroniza mai mulți clienți care încearcă să obțină o blocare pe aceeași resursă în același timp (ceea ce poate duce la o situație de „creier divizat” în care nu există câștigători). În plus, cu cât un client încearcă mai repede să obțină o blocare pentru majoritatea instanțelor Redis, cu atât mai îngustă este fereastra în care poate apărea o situație de creier divizat (și mai puțină necesitatea reîncercărilor). Prin urmare, în mod ideal, clientul ar trebui să încerce să trimită comenzi SET la N instanțe simultan folosind multiplexarea.

Merită să subliniem aici cât de important este ca clienții care nu reușesc să achiziționeze majoritatea încuietorilor să elibereze încuietorile (parțial) achiziționate, astfel încât să nu fie nevoiți să aștepte ca cheia să expire înainte ca lacătul de pe resursă să poată fi achiziționat din nou (deși dacă are loc fragmentarea rețelei și clientul pierde contactul cu instanțe Redis, atunci trebuie să plătiți o penalizare de disponibilitate în timp ce așteptați ca cheia să expire).

Eliberați încuietoarea

Eliberarea unei blocări este o operațiune simplă care necesită pur și simplu deblocarea tuturor instanțelor, indiferent dacă clientul pare să fi blocat cu succes o anumită instanță.

Considerații de securitate

Este algoritmul sigur? Să încercăm să ne imaginăm ce se întâmplă în diferite scenarii.

Pentru început, să presupunem că clientul a putut obține o blocare în majoritatea cazurilor. Fiecare instanță va conține o cheie cu aceeași durată de viață pentru toți. Cu toate acestea, fiecare dintre aceste chei a fost instalată la un moment diferit, așa că vor expira în momente diferite. Dar, dacă prima cheie a fost instalată la un moment nu mai rău decât T1 (ora pe care o alegem înainte de a contacta primul server), iar ultima cheie a fost instalată la un moment nu mai rău decât T2 (momentul la care a fost primit răspunsul) de pe ultimul server), atunci suntem încrezători că prima cheie din set care expiră va supraviețui 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 cel puțin pentru această perioadă.

În timpul în care majoritatea cheilor rămân valabile, un alt client nu va putea achiziționa lacătul, deoarece operațiunile N/2+1 SET NX nu pot avea succes dacă există deja N/2+1 chei. Prin urmare, odată ce un lacăt a fost dobândit, este imposibil să îl dobândești din nou în același moment (acest lucru ar încălca proprietatea de excludere reciprocă).
Cu toate acestea, dorim să ne asigurăm că mai mulți clienți care încearcă să obțină o blocare în același timp nu pot reuși în același timp.

Dacă clientul a blocat majoritatea instanțelor pentru aproximativ sau mai mult decât durata maximă de blocare, va considera blocarea nevalidă și va debloca instanțele. Prin urmare, trebuie să luăm în considerare doar cazul în care clientul a reușit să blocheze majoritatea instanțelor într-un timp mai mic decât data expirării. În acest caz, referitor la argumentul de mai sus, în timp MIN_VALIDITY niciun client nu ar trebui să poată redobândi blocarea. Prin urmare, mulți clienți vor putea bloca N/2+1 instanțe în același timp (care se termină la sfârșitul etapei 2) numai atunci când timpul de blocare a majorității a fost mai mare decât timpul TTL, ceea ce face ca blocarea să fie invalidă.

Puteți oferi o dovadă formală de securitate, puteți indica algoritmi similari existenți sau puteți găsi o eroare în cele de mai sus?

Considerații privind accesibilitatea

Disponibilitatea sistemului depinde de trei caracteristici principale:

  1. Eliberați automat încuietorile (pe măsură ce cheile expiră): în cele din urmă, cheile vor fi disponibile din nou pentru a fi folosite pentru încuietori.
  2. Faptul că, de obicei, clienții se ajută între ei prin eliminarea încuietorilor atunci când lacătul dorit nu a fost achiziționat, sau a fost achiziționat și lucrarea a fost finalizată; deci probabil că nu va trebui să așteptăm ca cheile să expire pentru a redobândi lacătul.
  3. Faptul că, atunci când un client trebuie să încerce din nou să achiziționeze o lacăt, așteaptă un timp comparativ mai lung decât perioada necesară pentru a achiziționa majoritatea lacătelor. Acest lucru reduce probabilitatea ca o situație de creier divizat să apară atunci când concurează pentru resurse.

Cu toate acestea, există o penalizare de disponibilitate egală cu TTL-ul segmentelor de rețea, deci dacă există segmente învecinate, penalitatea poate fi nedefinită. Acest lucru se întâmplă ori de câte ori un client dobândește o blocare și apoi smulge un alt segment înainte de a-l putea elibera.

În principiu, având în vedere infinite segmente de rețea contigue, un sistem poate rămâne indisponibil pentru o perioadă infinită de timp.

Performanță, failover și fsync

Mulți oameni folosesc Redis deoarece au nevoie de performanțe ridicate ale serverului de blocare în ceea ce privește latența necesară pentru a achiziționa și elibera blocările și numărul de achiziții/lansări care pot fi finalizate pe secundă. Pentru a îndeplini această cerință, există o strategie de comunicare cu serverele N Redis pentru a reduce latența. Aceasta este o strategie de multiplexare (sau „multiplexarea săracului”, în care socket-ul este pus în modul neblocant, trimite toate comenzile și citește comenzile mai târziu, presupunând că timpul de călătorie dus-întors între client și fiecare instanță este similară) .

Cu toate acestea, trebuie să luăm în considerare și considerația asociată stocării de date pe termen lung, dacă ne străduim să creăm un model cu recuperare fiabilă din defecțiuni.

Practic, pentru a clarifica problema, să presupunem că configurăm Redis fără stocare de date pe termen lung. Clientul reușește să blocheze 3 din 5 instanțe. Una dintre instanțele pe care clientul a reușit să le blocheze este repornită, iar în acest moment există din nou 3 instanțe pentru aceeași resursă, pe care le putem bloca, iar un alt client poate, la rândul său, să blocheze instanța repornită, încălcând proprietatea de securitate care presupune exclusivitatea încuietorilor.

Dacă activați data înainte (AOF), situația se va îmbunătăți ușor. De exemplu, puteți promova un server trimițând comanda SHUTDOWN și repornindu-l. Deoarece operațiunile de expirare în Redis sunt implementate semantic în așa fel încât timpul să continue să curgă chiar și atunci când serverul este oprit, toate cerințele noastre sunt în regulă. Acest lucru este normal atâta timp cât este asigurată o oprire normală. Ce să faci în caz de pene de curent? Dacă Redis este configurat implicit, cu sincronizarea fsync pe disc la fiecare secundă, atunci este posibil ca după o repornire să nu avem cheia noastră. Teoretic, dacă dorim să garantăm securitatea blocării în timpul oricărei reporniri a instanței, ar trebui să o activăm fsync=always în setările pentru stocarea pe termen lung a datelor. Acest lucru va distruge complet performanța, până la nivelul sistemelor CP care sunt utilizate în mod tradițional pentru a implementa în siguranță blocaje distribuite.

Dar situația este mai bună decât pare la prima vedere. În principiu, securitatea algoritmului este păstrată deoarece atunci când instanța este repornită după o eroare, aceasta nu mai participă la nicio blocare care este activă în prezent.

Pentru a ne asigura acest lucru, trebuie doar să ne asigurăm că, după o defecțiune, instanța rămâne indisponibilă pentru o perioadă de timp care depășește ușor TTL maxim pe care îl folosim. În acest fel vom aștepta până la data de expirare și eliberarea automată a tuturor cheilor care erau active în momentul eșecului.

Folosind reporniri întârziate, este, în principiu, posibil să se obțină securitate chiar și în absența oricărei persistențe pe termen lung în Redis. Rețineți, totuși, că acest lucru poate duce la o amendă pentru încălcarea accesibilității. De exemplu, dacă majoritatea instanțelor eșuează, sistemul va deveni indisponibil la nivel global pentru TTL (și nicio resursă nu poate fi blocată în acest timp).

Creștem disponibilitatea algoritmului: extindem blocarea

Dacă munca efectuată de clienți constă în pași mici, este posibil să se reducă durata implicită a blocării și să se implementeze un mecanism de extindere a blocărilor. În principiu, dacă clientul este ocupat cu calculul și valoarea de expirare a blocării este periculos de scăzută, puteți trimite un script Lua la toate instanțele care extinde TTL-ul cheii dacă cheia încă există și valoarea ei este încă o valoare aleatorie obținută atunci când lacătul a fost dobândit.

Un client ar trebui să ia în considerare o blocare a fi redobândită numai dacă a reușit să blocheze majoritatea instanțelor în perioada de valabilitate.

Adevărat, din punct de vedere tehnic, algoritmul nu se modifică, așa că numărul maxim de încercări repetate de a obține încuietori trebuie limitat, altfel proprietățile de accesibilitate vor fi încălcate.

Sursa: www.habr.com

Adauga un comentariu