Untitled

Implementarea sistemelor liniarizabile

Replicarea unui singur lider poate fi liniarizabilă. Dar ar putea exista replici învechite și scenarii de tipul split brain cu liderii și, prin urmare, nu pot fi complet liniarizabile.
Replicarea mai multor lideri nu poate fi liniarizată, deoarece necesită rezolvarea conflictelor, ceea ce înseamnă că nu există o singură copie a datelor Replicarea fără lider poate fi serializată dacă cititorul efectuează reparații de citire înainte de a se întoarce și scriitorul trebuie să citească starea unui cvorum de noduri înainte de a trimite scrierile. Dar, în practică, majoritatea sistemului fără lider nu oferă liniarizare. Dacă o aplicație necesită liniarizare, ea nu va fi disponibilă pentru unele replici în timpul unei partiții de rețea. A fost lucru cu replicile vechi, dar apoi nu este liniarlizabil. Și sistemele liniarizabile nu sunt atât de performante, deoarece timpii de citire și scriere sunt cel puțin proporționali cu întârzierile rețelei. Algoritmii de consens sunt liniarizabili. Au o modalitate de a evita creierul divizat și replicile învechite. Sistemele liniarizabile sunt întotdeauna lente, nu doar în timpul defecțiunilor rețelei. Deci, sistemele sensibile la latență ar putea face unele compromisuri. 

Ordering Guarantees

Ordinea este importantă pentru a oferi cauzalitate. Într-o replicare unică a liderului, toate scrierile trec prin lider pentru a determina ordinea scrierilor. Într-o tranzacție serializabilă, scrierile sunt procesate într-o ordine de serie. Marcajele de timp și ceasurile sunt, de asemenea, o încercare de a ordona scrierile. Dacă a se întâmplă înaintea lui b, atunci a ar fi putut cauza b. Deci ordinea cauzală este a -> b. Dacă un sistem respectă ordinea cauzală, se spune că este consecvent cauzal. Dacă citiți ceva din baza de date, dacă vedeți o bucată de date, ar trebui să puteți vedea orice date care o preced. Sistemul liniarizabil menține ordinea totală, deoarece se comportă ca și cum ar fi o singură bucată de date Două operațiuni sunt consistente dacă se întâmplă în același timp. Dacă două evenimente sunt ordonate dacă sunt legate cauzal, dar sunt incomparabile dacă sunt concurente. Deci cauzalitatea definește o ordine parțială, nu o ordine totală Ceea ce înseamnă că nu există operații concurente într-un depozit de date liniarlizabil. În general, ordonarea cauzală este suficientă pentru majoritatea aplicațiilor. Așadar, pentru a oferi ordinea cauzală, putem folosi numere de succesiune crescătoare monoton pentru a ordona evenimentele. Când este un singur lider, este ușor, dar când există procese de mai multe noduri, există modalități de a face secvența, dar acea secvență nu oferă cauzalitate. O modalitate de a genera numere de secvență care oferă ordinea obișnuită este marcajele de timp Lamport. Aici fiecare nod va genera numere de secvență și, în plus, va avea și id-ul nodului Va fi o pereche de (contor, id de nod). Poate furniza ordine cauzală în felul următor. Fiecare client va trimite întotdeauna contorul maxim pe care l-a văzut între toate nodurile din fiecare cerere. Deci, să presupunem că un nod 1 are un contor de 5 și nodul 2 are un contor maxim de 1. Un client a primit o solicitare de la nodul 1 (cu contorul 5) și a trimis o solicitare la nodul 2 (cu contorul 1), nodul 2 va vedea asta și crește contorul său la 6. În acest fel oferă o ordonare totală a tuturor operațiilor. Dar aceste marcaje temporale nu pot rezolva problema constrângerilor unice, deoarece vom cunoaște ordinea totală după fapt. Când un sistem încearcă să genereze un nume de utilizator unic, atunci trebuie să știe dacă este unic sau nu și dacă alte sisteme procesează deja acel nume de utilizator. Pe lângă cunoașterea ordinii totale, trebuie să știm și când este finalizată. Această idee de a spune când o comandă totală este finalizată se numește difuzare de comandă totală.

Difuzarea totală a comenzii poate fi utilizată pentru a rezolva problema unicității. Scrieți o solicitare de nume de utilizator în jurnal folosind o operație de comparare și setare. Citiți jurnalul Dacă solicitarea dvs. a fost prima solicitare când ați citit, atunci puteți efectua tranzacția. Dacă solicitarea unui alt nod a fost prima solicitare din jurnal, atunci anulați tranzacția deoarece numele de utilizator este deja luat. Implementarea operațiunii de comparare și setare atomică necesită consens dacă mai multe noduri solicită același nume de utilizator. Dacă avem un increment liniarlizabil și obținem un registru, atunci este posibil să avem o comandă totală difuzată. Fiecare mesaj care trebuie trimis prin difuzarea ordinului total trebuie să obțină un număr de secvență din registrul liniizabil și să-l atașeze la mesaj și să-l trimită la toate nodurile. Dacă un nod livrează un mesaj cu secvența 4 și primește un mesaj cu secvența 6, știe că trebuie să aștepte secvența 5 înainte de a putea livra 6. Pentru marcajele de timp lamport, contorul poate avea lacune pentru, de ex. dacă un nod vede 6, pentru următorul mesaj va trimite 7, dar nu va aștepta 5, dar cu difuzarea ordinului total, trebuie să aștepte 5. Implementarea comparației liniizabile și a difuzării ordinului stabilit sau total necesită ambele consens. Este necesar consensul pentru alegerea liderului pentru a evita liderii multipli și creierul divizat. Este necesar un consens pentru a selecta și a conveni asupra unui singur lider. Atomic commit — Într-o bază de date care acceptă tranzacții pe mai multe noduri, dacă eșuează pe unele noduri, atunci toate nodurile ar trebui să fie de acord să comite sau să deruleze înapoi pe toate nodurile pentru a menține atomicitatea tranzacției.

2 Phase Commit
Pentru o tranzacție pe mai multe noduri, nu este posibil să existe o tranzacție atomică dacă fiecare nod își poate face propriul proces de commit/rollback. Trebuie să treacă printr-un proces de comitere în 2 faze. În acest caz, există un coordonator care să coordoneze tranzacția. Aplicația poate trimite modificările pe mai multe noduri. Odată ce tranzacția este gata să se comite, coordonatorul începe faza 1 numită pregătire, în care fiecare nod se va pregăti pentru comite scriind-o în jurnal și când ambele noduri sunt ok să comite, coordonatorul va începe faza 2, scrie tranzacția în jurnalele sale și trimiteți ok-ul la ambele noduri. Ambele noduri commit apoi tranzacția. Dacă vreunul dintre noduri nu a spus ok tranzacției în faza 1, atunci coordonatorul abandonează tranzacția. Dacă oricare dintre noduri sau rețea eșuează în timpul tranzacției, coordonatorul abandonează. Dacă coordonatorul eșuează înainte de a confirma faza 2, ambele noduri vor aștepta ca coordonatorul să trimită ok-ul. În caz contrar, ei nu pot să avorteze sau să se angajeze, deoarece a face ceva unilateral va încălca atomicitatea. Deci se va bloca până când coordonatorul își revine și emite commit-ul sau rollback-ul. Există ceva numit 3PC (comitare în trei faze) care presupune un sistem cu întârzieri de rețea limitate și timpi de răspuns mărginiți. Practic, dacă prăbușirea unui nod poate fi detectată corect, atunci 3PC poate oferi tranzacții neblocante. Dar asta nu poate fi presupus în general. În practică, comiterea în 2 etape este implementată prin tranzacții distribuite XA (care este un coordonator api cu care interfață mai multe aplicații). După cum sa discutat mai sus, în timpul eșecului coordonatorului, există posibilitatea ca încuietorile să fie ținute pe termen nelimitat. Și fie utilizatorii admin trebuie să rezolve blocajele, fie aplicațiile pot folosi euristica pentru a anula sau a se angaja unilateral. XA poate lucra cu diferite aplicații, baze de date și o coadă de mesaje etc. Dacă o tranzacție este într-un sistem distribuit omogen, cum ar fi o bază de date, poate funcționa bine. dar cu sisteme distribuite eterogene, sunt mai dificile, deoarece trebuie să lucreze cu tehnologii diferite și nu pot fi optimizate. Dezavantajele 2PC Dacă un coordonator nu este replicat și rulează pe o singură mașină, acesta devine un singur punct de eșec Aplicația devine cu stare, deoarece trebuie să mențină starea în jurnalul coordonatorului Deoarece trebuie să funcționeze cu sisteme disparate, are doar funcții de bază. Nu pot detecta blocajele și nu funcționează cu SSI (izolarea instantanee serializabile) Pentru sistemele distribuite, 2PC va amplifica defecțiunile în loc să ajute la construirea de sisteme tolerante la erori.

Consensus
În consens, unul sau nodurile de mod propun valori, iar algoritmul decide o valoare. Mai formal, trebuie să fie îndeplinite următoarele proprietăți Nu există două noduri care decid diferit Niciun nod nu decide de două ori pentru aceeași decizie Dacă un nod decide valoarea v, atunci valoarea v a fost propusă de un anumit nod. Fiecare nod care nu se prăbușește decide în cele din urmă o valoare. Cei mai cunoscuți algoritmi de consens sunt Vizualizați replicare ștampilată VSR Paxos Plută Zab Acești algoritmi decid o secvență de valori care îi face ca algoritmi de difuzare în ordine totală. În fiecare rundă nodurile propun ce valoare vor să trimită în continuare și decid următorul mesaj în ordine totală. Acești algoritmi se așteaptă să funcționeze atunci când este disponibil un cvorum de noduri. Pentru a alege un lider, avem nevoie de consens. Când un lider este în jos, ei încep un proces electoral care are un număr de epocă. Când spunem că vine un lider vechi dintr-o epocă anterioară și încearcă să scrie ceva, nodurile care l-au ales lider într-o epocă nouă nu vor fi de acord cu asta și, prin urmare, scrierea eșuează. Practic, este un proces în două etape. Mai întâi un lider va fi ales prin consens și când liderul dorește să scrie ceva, din nou trebuie să fie de acord și unul dintre nodurile care a participat la alegerea liderului trebuie să fie de acord cu această scriere. Dacă vreunul dintre nod cunoaște un lider diferit, nu va fi de acord și, prin urmare, cvorumul nu poate avea loc și scrierea eșuează. Limitările consensului: Procesul electoral este ca o replicare sincronă Este nevoie de majoritate strictă pentru a funcționa Deoarece se bazează pe expirări pentru a detecta nodurile eșuate, erorile tranzitorii de rețea pot cauza alegeri frecvente de lider și performanțe groaznice Raft este deosebit de sensibil la problemele de rețea. Dacă există o conexiune de rețea slabă, conducerea se ridică continuu și sistemul nu funcționează.
Servicii de membru și coordonare: Zookeeper și etcd sunt concepute pentru a păstra cantități mici de date în memorie. Aceste date sunt replicate pe mai multe noduri printr-un algoritm de difuzare a ordinului total tolerant la erori Are următoarele caracteristici Operații atomice liniarizabile Folosind o operație de comparare și setare atomică, poate fi implementată o blocare. Dacă mai multe noduri încearcă să seteze valoarea, doar unul va reuși. Blocările distribuite sunt implementate ca contracte de închiriere care expiră și în cele din urmă sunt eliberate dacă clientul eșuează. Ordinea totală a operațiunilor Când o resursă este protejată printr-un lacăt sau un închiriere, are nevoie de un simbol de gard pentru a preveni clienții să intre în conflict între ei în cazul unei întreruperi a procesului. Zookeeperr implementează acest lucru ordonând total toate operațiunile și oferind fiecărei operațiuni un ID de tranzacție care crește monoton numit zxid și o versiune cversion Detectarea eșecului Clienții mențin o sesiune de lungă durată pe serverele Zookeeper. Dacă există o defecțiune temporară sau un nod de îngrijitor al grădinii zoologice se defectează, sesiunea este activă. Dar dacă bătăile inimii eșuează pentru o perioadă de timp mai mare decât cea configurată, Zookeeper va expira sesiunea și poate fi configurat să elibereze toate blocajele și închirierile deținute de acel client. [Aceștia se numesc noduri efemere în zookeeper] Schimbarea notificărilor Clienții pot citi încuietorile și valorile stabilite de alți clienți și, de asemenea, pot urmări modificările aduse acestora. Astfel, un client poate afla când un nou nod s-a alăturat clusterului și, de asemenea, când un nod părăsește clusterul (pierderea nodurilor efemere). Așadar, clientul le poate obține fără sondaj, doar abonându-se la modificări. Cazuri de utilizare Lucru de alocare către noduri — Pentru a identifica un lider într-un scenariu de bază de date și, de asemenea, într-un scenariu de planificare a sarcinilor. Dacă există multe noduri, Zookeeperul nu trebuie să facă alegerea liderului pe toate nodurile, poate funcționa doar cu 3 sau 5 noduri, dar poate servi toți clienții. Zookeeper este util pentru a salva numai date care nu se schimbă des. Dacă trebuie să replicați starea aplicației, utilizați o altă aplicație numită Apache BookKeeper. 2. Descoperirea serviciului — Într-un mediu de centru de date în cloud, atunci când apare un nou serviciu, acesta se poate înregistra la zookeeper, astfel încât punctele sale finale să poată fi găsite de alte servicii. Nu are nevoie de consens, dar poate fi util pentru alte servicii să găsească liderul, deoarece ZK îl știe deja. 3. Servicii de membru — Un serviciu de membru determină care noduri sunt active și fac parte dintr-un cluster. Un mecanism de detectare a defecțiunilor cu un mecanism de consens poate ajuta la determinarea nodurilor care fac parte dintr-un cluster și care nu.