User:GaborGeorge/sandbox/Sisteme de mare fiabilitate si tolerante la defecte

Sisteme de mare fiabilitate si tolerante la defecte

Atentia asupra fiabilitatii si tolerantei la defecte a crescut foarte mult in ultimii ani din cauza ca tot mai multe sarnici critice, dar nu numai, sunt dependente de calculatoare. Printre acestea se numara: aplicatii financiare, sisteme de control al reactoarelor nucleare, operatiuni medicale, aplicatii de difuzare live de evenimente si sisteme medicale. Astfel ca viata noastra este tot mai mult afectata de gradul de corectitudine al acestor sisteme. Acest lucru contribuie la cresterea numarului de defecte inregistrate si a inconvenientelor aduse de acestea.

Fiabiabilitatea este definita ca probabilitatea ca un sistem sa isi indeplineasca functia intentionata, in conditii de utilizare determinate si pe o perioada de timp precizata.

Un defect sau eroare este reprezentata de un comportament neasteptat al sistemului iar toleranta la defecte este un mecanism ce mascheaza sau restabileste comportamentul asteptat al unui sistem in care a aparut defecte .

Exista multe motive pentru care un sistem informatic poate sa experimenteze erori. In primul rand componentele hardware pot sa cedeze sau sa experimenteze comportamente nedefinite din cauza uzurii, un exemplu ar fi o poarta logica ce ofera aceeasi iesire indiferent de datele de intrare. Un alt exemplu sunt fenomene cosmice (‚cosmic showers’), cum ar fi particule incarcate electric ce provin din spatii si pot provoca schimbarea aleatoare a valorilor unor biti. Cateva cazuri, in care s-au raportat efectele acestora asupra unor supercalculatoare sunt prezentate in articolul . De asemenea, din cauza ca multe sisteme informatice actuale sunt distribuite, canalele de comunicare dintre ele pot pierde sau altera mesajele transmise, ducand la rezulate eronate sau timpi de asteptare crescuti. Totusi, chiar daca componentele hardware ale unui sistem functioneaza perfect, tot raman nenumarate erori aduse din cauza software-ului, cum ar fi coruperea de memorie sau erori de precizie. Un alt factor, ce poate contribui la aparitia unei erori este interventia omului: varsarea de lichide pe echipamente sau lovirea lor poate afecta un sistem informatic, incercarile de compromitere a unui sistem prin programe malitioase sau atacuri DDOS (distributed denile of service). De asemenea, schimbarea mediului in care sistemul opeareaza poate sa aiba efecte nocive (schimbarea temperaturii, cantitatii de praf sau a unimiditatii).

Din pacate, eliminarea completa a defectelor dintr-un sistem informatic este o provocare. Desi marea majoritate a erorilor pot fi descoperite si remediate in fazele de dezvoltare, unele dintre ele pot sa ramana ascunse si sa iasa la iveala dupa ce sistemul este pus sa functioneze intr-un mediu real. Acest lucru poate produce efecte dezastroase, cum ar fi prabasirea unui avion .

In acest studiu, multi termeni au pastrat denumirea din engleza sau daca au fost tradusi a fost oferita si denimirea in engleza, intrucat am considerat ca traducerea lor le-ar afecta adevaratul inteles si ar putea produce confuzie sau neintelegerea lor. De asemenea, accentul a fost pus mai mult asupra sistemelor distribuite, deoarece sunt alcatuite din mai multe procese, aflate pe diferite masini fizice, ce comunica utilizand mesaje transmise pe canale de comunicare. Astfel, acestea au un grad de complexitate mai mare fata de aplicatile centralizate si sunt expuse la mai multe pericole.

Inainte de a prezentat metode de adresare a erorilor, este evidentiata o clasificare a tipurilor de erori ce pot sa apara intr-un sistem informatic.

Modele de defectare

Modelele de defectare incearca sa dea o specificatie precisa asupra erorilor ce pot sa apara in procesele si caile de comunicare ale unui sistem . De-a lungul timpului au fost create diferite taxonomy de defecte, cateva pot fi gasite in . Pentru clasificarea de fata, s-a ales ca defectele sa fie considerate la nivel de proces, unde un process poate sa fie un canal de comunicare sau componenta software sau hardware. Astfel, principalele tipuri de erori sunt:

• Crash failure: este definita prin faptul ca determina un proces sa nu mai poate sa isi execute instructiunile. In sistemele asincrone nu putem fi niciodata siguri ca o astfel de eroare a avut loc, intrucat nu avem un timp maxim in care un proces trebuie sa raspunda. Insa, in sistemele sincrone, se pot folosii cronometre si semnale de tip heartbeat pentru a detecta ca un proces nu se mai executa. Astfel, un process trimite periodic mesaje la procesele vecine, iar cele care nu raspund intr-un interval de timp sunt considerate ca au esuat.
• Omission failure: este caracteriza de un unul sau mai multe mesaje trimise de la un process transmitator la unul receptor, ce nu ajung la destinatie. Acest tip de eroare poate fi cauzat de mediul de transmisie, cand nodurile intermediare din retea nu mai au capacitate de stocare a mesajelor primite, din cauza traficului mare. De asemenea, defectarea efectiva a legaturilor dintre procese poate cauza pierderea mesajelor.
• Tranzitorie (Transient failure): acestea sunt erori a caror conditii de manifestare apar foarte rar sau sunt greu de reprodus. Marea majoriatate a lor se arata dupa ce sistemul este pus in functiune, perturbandu-i stare globala intr-un mod arbitrar, de aceea sunt extrem de greu de prins in etapa de testare a sistemului. Omission failuers sunt un caz special al acestui tip de erori. In este sugerat ca acest tip de eroare apare frecvent. Acestea inglobeaza efectele hazardurilor de mediu (cum ar fi radiatile), a surselor de energie supraincarcate, a componentelor software. In sunt referite ca Heisenbugs, o clasa de erori ce sunt intermitente si cauzate de probleme ce apar in executie, cum ar fi acesare unei zone de memorie nealocat. In contrast, s-a introdus si termenul de Bohrbug, ce este o eoare reproductibila ,vezi pentru o descriere.
• Bizantine failures sau erori arbitrare: cel mai slab si nedorit dintre modelele de eroare, in care se permite orice forma de defect. Ca un exemplu , un proces trimite o valoare tuturor vecinilor sai, urmatoarele sunt comportamente inconsistente: 2 procese primesc valori diferite; fiecare process vecin primeste o alta valoare; o parte din procese nu primesc nici o valoare. Cateva dintre cauzele ce ar putea produce aceste comportamente sunt: defectarea partiala sau totala a unei legaturi de comunicare; probleme de sincronizare, daca toate procesele sunt conectate la acelasi bus de date, din cauza ca timpii acestora nu sunt perfect sincronizati, daca valoare se poate schimba in timp, procesele pot sa nu citeasca valoare la acelasi moment de timp.
• Software failures: exista mai multe tipuri:
  • Erori de cod sau erori umane: ca exemplu, in 23 septembrie 1999 NASA a pierdut un satelit ce orbita in jurul planetei Marte in valoare de 125 de milioane de dolari. Acest lucru s-a datorat faptului ca o echipa de ingineri utiliza unitati de masura metrice iar alta echipa utiliza unitati englezesti si a provocat arderea in atmosfera a satelitului;
  • Erori de software design. In cadrul unei misiuni Mars pathfinder a aterizat cu succes pe suprafata planetei Marte, doar ca sa experimenteze mai tarziu o eroare a sistemului de comunicare din cauza designului sistemului de operare. In urma diagnosticul s-a ajuns la concluzi ca problema a fost datorata mecanizmul de priority inversion, in care un task de prioritate mica poate sa puna in asteptare unul de prioritate mai mare.
  • Memory leaks. Este fenomenul in care procesele nu pot sa elibereze memoria fizica a sistemelui ce le-a fost alocata. Totusi, acestea vor dori tot mai multa memoria, deci cea disponibila va scadea in timp iar cand va devinii suficient de mica, apare un crash al sistemului.
  • Problema specificatilor neadecvate. Daca un sistem ce oferea resultate bune esueaza fara sa fie vreo eroare de hardware sau memory leak, poate sa fie o problema de specificare. Un exemplu este eroare Y2K ce a tinut in suspans mai multe luni milioane de furnizori de servicii la inceput anului 2000. Problema a fost ca, in secolul douazeci programele scrise pentru institutii financiare sau centrale electrice aveau codad anul 19xy ca si xy. Astfel la inceput anului 2000, anul era reprezentat prin 00, ce facea ca sistemul sa il incurce cu anul 1900.

De remarcat este ca erori de crash, omission, transient sau byzantine pot fi provocate de erori de tip software. Daca un program intra intr-o bucla infinita poate mima un crash failure. Sau o problema de software intr-un router poate determina pierderea de pachete si determina omission failures.

• Erori temporale (Temporal failure). Sistemele ce trebuie sa opereze in timp real necesita un interval de timp fix pentru a-si incheia procesarea. Aceasta eroare apare in momentul cand acesti timpi limita nu sunt respectati.
• Erori de securitate (Security failure). Un software-ul malitios poate determina ca un sistem sa aiba un comportament nedefinit. Efectele pot fi: marirea timpului de executie din cauza actiunilor efectuate de virus (spionare de informatii, furt de parole), preluarea controlului sistemul si utilizarea sa pentru a executa alt sarcini, cum ar fi minarea de cripto-monede.

Dupa cum s-a vazut, unele erori se repeta, de regula cele software, in timp ce altele nu, din cauza nefunctionarii temporare a hardware-ului sau a unor conditii rare ce nu au fost prinse la testare. De asemeneaa, rolul omului are un impact major asupra functionarii adecvate a sistemelor. In 1988, majoritatea servicilor pe distante lungi din East Coast au fost intrerupte pentru ca o echipa de constructori a stricat din greseala un cablu de fibra optica din New Jersey, acest lucru a dus la blocarea a 3,5 milioane de apelui. In 1991, o echipa de tehnicieni AT&T din New York nu au raspuns la o alarma de eroare timp de 6 ore. Astfel 5 milioane de gospodarii au ramas fara curent iar 1170 de zboruri au fost anulate sau amanate.

Specificarea erorilor

Pentru a modela un sistem tolerant la erori, specificarea sa trebuie sa cuprinda:

1. Un set de actiuni de sistem S ce reprezinta sistemul fara erori;
2. Un set de actiuni eronate F ce mimeaza comportamentul defectelor.

Sistemul cu erori consta din reuniunea lui S si F. Insa aceasta este doar o simulare a comportamentului defectelor si nu are legatura cu modul in care erorile apar in sistemul fizic. Astfel, se utilizeaza variabile auxiliare ce nu sunt parte din sistemul real. De asemenea, astfel de specificari nu sunt unice pentru un anume sistem.

Un exemplu simplu ar fi un sistem care in lipsa erorilor trimite la infinit acelasi mesaj 'a'. Insa ocazional, o eroare determina ca mesajul sa se schimbe din 'a' in 'b'. Un asemena sistem este modelat specificat in figura 1, preluata din .

Figura 1. Specificarea unui sistem cu erori

Sisteme tolerante la defecte

Este nevoie de definirea urmatoarelor notiuni:

• Liveness – ceva bun se va intampla la un moment dat , adica sistemul poate sa faca progress. Aceasta proprietate nu poate fi incalcata de un numar finit de actiuni intrucat in final actiunea asteptata poate sa fie indeplinita mai tarziu.
• Safety - ceva rau nu se va intampla niciodata. In contrast cu liveness, acesta proprietate poate fi incalcata intr-un numar finit de actiuni, intrucat ceva rau se intampla.

Un sistem ce nu tolereaza defecte este numit fault-intolerant system. In astfel de sisteme, aparitia unui defect violeaza proprietate de liveness sau de safety. Fie P un set de configuratii a sistemului la care se poate ajunge din S (definit anterior). Dandu-se un set de actiuni de erori F, Q (P inclus in Q) reprezinta cel mai mare set de configuratii in care poate ajunge sistemul. Acesta masoara cand de ‚grav’ poate ajunge sistemul.

Nu se poate construi un sistem ce poate tolera orice fel de eroare. Un sistem se numeste F-tolerant daca poate sa ajunga intr-o stare corecta daca toate actiunile din F se termina de executat. Exista patru mari tipuri de moduri de a tolera defecte :

1. Toleranta prin mascare (Masking Tolerance). Un defect este mascat daca manifestarea sa nu are nici un impact asupra sistemului, P = Q. Acest tip de toleranta este importanta pentru sisteme ce pun in pericol viata oamenilor sau pot produce pagube materiale. De exemplu, un avion trebuie sa poata zbura chiar daca unul dintre motoarele sale a cedat, un sistem de monitorizare a pacientilor dintr-un spital trebuie sa poata colecta date corecte chiar daca unul dintre senzori are probleme, intrucat ar putea cauza schimbari nocive in medicamentatia pacientului. Mascarea erorilor pastreaza proprietatile de liveness si safety a sistemului.
2. Toleranta prin ne-mascare (Nonmasking Tolerance). In acest tip de toleranta, o eroare poate sa afecteze temporar aplicatia si incalca proprietatea de siguranta (safety), adica P inclus in Q. Insa, proprietatea de liveness ramane intacta intrucat in final sistemul va reveni la comportamentul normal, vezi figura 2 . Un exemplu, este rutare de pachete de la o sursa la o destinatie intr-o retea. O eroare poate provoca un ciclu in ruta pachetele si le poate bloca pe unele. Insa, algoritmul de rutare reuseste sa rupa ciclul si pachetele reusesc sa ajunga la destinatie. Singura consecinta a fost un timp de propagare mai mare pentru unele pachete. Exista mai multe tipuri de nonmasking tolerance. Primul este backward error recovery, in care se inregistreaza periodic starea intregului sistem (snapshots) pe o susra de stocare stabila (stable storage). In momentul cand un defect se manifesta, sistemul se intoarce (rolls back) la ultima configuratie salvata, pentru a anula efectul produs de eroare, si incepe executia din acea stare. Dificultatea este mentinerea unui istoric corect al operatilor efectuate, astfel incat starile sa fie corecte. Un alt tip este forward error recovery. In momentul cand apare o eroare, sistemul nu incearca sa se intoarca in trecut, intrucat considera ca in cazul majoritatii erorilor sistemul poate sa isi revina natural. Sisteme de acest tip ce pot sa isi revina din orice configuratie initiala se numesc auto-stabilizante (self-stabilizing systems).

   

   Figura 2: Ilustrarea revenirii din esesc

3. Fail-Safe Tolerance. Unele erori pot sa nu aiba efecte adverse asupra unui sistem si pot fi considerate inofensive. Un sistem de tip fail-safe incearca sa evite doar erorile ce il pot face sa ajunga intr-o configuratie cu consecinte catastrofice. Dandu-se o anumita specificatie savety P, sistemul o va conserva in ciuda aparitiei erorilor. Totusi, nu se garanteaza ca sistemul va mai face progres, intrucat uneori, oprirea executiei si lasarea sistemului intr-o stare corecta este cea mai buna metoda de a reactiona la o eroare. Sistemul de control terestru pentru lansare rachetei Ariane 5 a fost conceput sa mascheze eroare unei singure componente, insa daca doua componente ajung sa nu mai functioneze corect, lansarea este amanata, deoarece este mai bine ca racheta sa ramana pe pamant decat sa aiba o problema grava in spatiu.
4. Graceful Degradation. Exista sisteme ce nici nu mascheza erorile si nici nu isi revin complet de pe urma lor. Acestea prezinta un comportament ce se degradeaza in timp fata de comportamentul normal, dar inca produc rezultate acceptabile. Utilizatorii aplicatiei hotarasc cat de mult se pot degrada rezultatele pentru a fi considerate acceptabile. Cateva exemple de astfel de comportament sunt:
   1. Sa presupunem o aplicatie de chemare de taxi. Conditile normale de functionare pot fi: daca un client comanda un taxi, in final trebuie sa primeasca unul, iar cererile trebuie sa fie indeplinite in ordinea in care au fost facute. In cazul in care apare o eroare, un comportament care satisface prima conditie, dar nu pe a doua, poate fi considerat acceptabil.
   2. In timpul rutarii unor pachete intro doua calculatoare dintr-o retea, se determina cea mai scurta cale intre cele doua. In prezenta unei erori, daca se gaseste o cale care nu este cea mai scurta dar este apropiata ca lungime de cea mai scurta, aceasta ar putea fi considerata suficient de buna.

Detectoare de Defecte

Design-ul de sisteme tolerante la erori este mai simplu daca procesele ce au erori pot fi detectate cu incredere. De exemplu: intr-o retea formata din senzori, o statie delega un task de monitorizare a mediului la un set de noduri, ce vor trimite valorile inregistrate inapoi la statie. Daca un nod esueaza si se poate detecta asta, acesta poate fi inlocuit de alt nod. In continuare, accentul va fi pus de detectare de crash-uri.

Un detector de erori (failure detector) este un serviciu ce genereaza o lista de procese ce sunt suspecte ca au esuat. Fiecare proces are un detector local ce coordoneaza impreuna cu detectoarele din celelalte procese acest serviciu. In cazul sistemelor asincrone, deoarece nu exista limite asupra timpilor de raspuns, procesele devin suspecte pe baza unor observatii locale. Un mod prin care un proces poate crea o lista de suspecti este de trimite un mesaj la toate procesele la care are acces, si in functie de timpul lor de raspuns, devin suspecte de esec. Acest mecanism permite ca un proces sa fie doar in unele liste de suspecti, intrucat daca primeste mesaje de la mai multe procese, unele din raspunsurile sale pot sa aiba intarzieri sau sa se piarda.

Exista doua proprietati de baza ale unui detector de erori:

1. completness – fiecare proces esuat este suspect;
2. accurary – nici un proces corect nu este suspect.

Pentru ca un detector sa fie util este nevoie sa incerce sa respecte ambele proprietati, intrucat daca suspecteaza toate celelalte procese atunci este respecta a prima proprietate iar daca nu suspecteaza nimic atunci o respecta pe a doua. De remarcat ca prima proprietate este una de liveness, intrucat este bine si daca procesele nu devin suspecte exact in momentele cand au esuat. Accuracy, in schimb este o proprietate de safety.

Exista doua forme de completness:

1. strong completness – fiecare proces esuat devine pana la urma suspect de toate procesele corecte si ramane suspect de atunci incolo;
2. weak compleatness: fiecare process esuat este pana la urma suspectat de cel putin un proces corect si ramane suspect dupa aceea.

Acestea nu depind de modul in care se construiesc listele de suspecti. Fiecare proces isi creaza propria lista de suspecti pe baza istoriei de comunicatie la un anumit timp. Apoi, daca un proces primeste un mesaj de la un membru al listei sale de suspecti sau invata de la alt process ca acel suspect nu a esuat, il va scoate din lista. Astfel, se poate implementat strong completeness utilizand weak completeness,.

In mod similar se pot defini doua forme de accuracy:

1. strong accuracy: un proces corect nu este niciodata suspect;
2. weak accuracy: exista cel putin un proces corect care nu este niciodata suspect.

Ambele pot fi mai departe divizate utilizind atributul eventually, marcat prin ‹›. Un detector este eventually strongly accurate daca exista un moment de timp de la care nici un proces corect nu mai este suspect, pana atunci orice proces corect poate intra si iesi dintr-o lista de suspecti de un numar nelimitat de ori. Similar, un detector este eventually weakly accurate daca exista un moment de timp de la care cel putin un proces corect nu mai este suspectat niciodata, iar pana atunci, orice proces corect putea fi suspect. Utilizand proprietatile descrise pana acum se pot definii patru clase de detectoare de erori:

1. Perfect P – complete si strongly accurate;
2. Strong S – complete si weakly accurate;
3. Eventually perfect ‹›P – complete is eventually strongly accurate;
4. Eventually strong ‹›S – complet si eventually weakly accurate.

Diferite tipuri de detectoare de erori pot if utilizate pentru rezolvarea unor probleme de consens, vezi pentru exemple.

Desi s-au prezentat diferite tipuri de detectorare de erori si proprietati ale acestora, implementarile lor vor depinde intr-un mod sau altul de cronometre si informatii secundare propagate de la alte procese despre suspectii observati. Cu cat timpul de observare este mai mare, cu atat lista de suspecti va fi mai bine estimata.

Detectia de erori in sistemele sincrone.

Mecanizmele de tolerare a erorilor depind de asumptile asupra gradului de sincronizare dintre componente sistemului, cum ar fi: ceasuri de sincronizare, timpi minimi sau maximi de executare δ a unor pasi. In cazul erorilor de tip crash, daca ar fi aceste asumptii ar fi imposibil de diferentiat intre un process ce are o problema si unul ce necesita mai mult timp pentru a-si face treaba. Insa, cand se cunosc informatii legate de aceste limite, se pot utiliza cronometre pentru a detecta crash failures. Daca consideram omission failures, daca nu se sunt folosite canele de comunicare FIFO(first in first out) sau nu se cunoaste un timp de transmisie maxim, nu se pot detecta. Daca se utilizeaza canale FIFO, si un transmitator trimite doua mesaje consecutiv, etichetate cu numerele de secventa i si j, iar un receptor primeste doua mesaje consecutive cu numerele de secventa i si j si j ≠ i + 1, atunci se poate afirma ca s-a produs o eroare. In cazul in canalelor non-FIFO, daca receptorul primeste un mesaj cu un numar de secventa i iar mesajul etichetat cu i – 1 nu apare intr-un timp δ, atunci este detectata o eroare.

Design-ul de sisteme tolerante la erori necesita cunostinte legate de comportamentul asteptat al aplicatiei, scenarii de erori ce pot sa apara si tipul de toleranta dorit. In continuare sunt prezentate cateva metode de a tolera anumite defecte.

Tehnici de asigurare a tolerantei la defecte.

Memoria RAM isi pierde continutul odata ce ramane fara alimentare iar un hard disk poate sa isi piarda continutul in cazul unui crash. Pentru a putea face ca tranzactile sa fie durabile (o tranzactie este o operatie ce implica cel putin doua entitati ), vrem sa avem o sursa de stocare incoruptibila pentru a o folosi la revenirea intr-o stare corecta in cazul unui esec. Acest mecanism se numeste stocare stabila.

Operatii atomice

Reprezinta un set de actiuni ce se executa in maniera atomica, fie toate operatile sunt executate cu succes, fie stare sistemului ramane aceeasi si nu se executa nici una. Un proces ce executa o actiune atomica nu este constient de activitati din exterior si nu poate observa exteriorul. In plus, orice proces exterior nu poate sa vada vrea schimbare a starii interne ale unei actiuni atomice

Fail stop processors

Un procesor de tip fail stop isi opreste automat executia ca raspuns la orice eroare interna si face asta inainte ca efectele erorii sa devina visibile. Astfel, nu se va executa nici o actiune incorecta. De asemenea, continutul memoriei volatile se va pierde.

Stocare stabila (stable storage).

Pentru a implementa acest mecanism este nevoie de o pereche de hard disk-uri normale. Considerand un obiect A compus din mai multe componente A0, A1, A2, ...., An-1. O tranzactie da o valoare noua xi fiecarei componente Ai. Aceasta operatie este atomica, fie toate Ai = x reusesc fie niciuna nu are efect. In mod normal un esec al procesului ce face schimbare valorilor poate permite ca o parte dintre asignari sa fie facute, violand proprietatea de atomicitate.

Figura 3: Modelul de stable storage

Mecanizmul de stable storate memtine doua copii ale obiectului A (doua copii pentru fiecare componenta) si pune la dispozitie doua operatii asupra lui A: update si inspect. Aceste copii sunt notate A0 si A1 (vezi figura 3 ]). Cand P executa update, modifica cele doua copii alternativ si le asigneaza (1) o eticheta de timp T si (2) o valoare de checksum S, ce depinde de x si T. O eroare de fail-stop poate oprii operatie de update in orice pas. Cand procesul Q, executa inspect, verifica amble copii, si pe baza timpilor si valorilor de checksum puse la update, alege valoare corecta pentru A. Pasii de schimbare a valorii lui A sunt afisati in figura 4 .

Figura 4: Pasii de executie pentru schimbarea unei valori utilizand stable storage

Daca operatile 1, 2 sau 3 esueaza, A1 detine valoarea corecta iar daca 4, 5 sau 6 esueaza A0 detine valoarile corecte.

Checkpointing si Rollback Recovery

Consideram o tranzactie distribuita in care fiecare proces are acces la stocare stabila pentru as salva starea locala. O eroare poate efecta unul sau mai multe procese, astfel stare globala a sistemului devine inconsistenta. Checkpointing este un mecanism ce face posibil ca tranzactiile sa isi revina din asemenea configuratii inconsistente prin backward error recovery. In timpul executiei unei tranzantii, starile proceselor participant sunt salvate periodic prin mecanizmul de stable storage. Aceste fragmente formeaza impreuna un checkpoint. In cazul in care apare o eroare, sistemul se va intoarece (rolls back) la cel mai recent checkpoint, ce il va intoarce intr-o stare consistenta. Aceasta tehnica poate fi aplicata in orice sistem ce foloseste mesaje pentru a le permite componentelor sa interactioneze. O forma simpla de checkpointing este atunci cand fiecare process hotareste independent cand sa isi salveze stare si se numeste checkpointing independent sau necoordonat. Insa o colectie de stari pot sa nu reprezinte o stare consistenta a sistemului, unele mesaje pot sa fie considerate primite de destinatar, dar netrimise de transmitator. Pentru a putea ajunge la o stare consistenta este novoie de un rollback inteligent, in care sa fie cautata cea mai apropiata stare consistenta dintr-o colectie de checkpoints. Pentru a ilustra aceasta problema, consideram exemplul din figura 5 :

Figura 5: Exemplu de executie al unui sistem cu 3 procese ce comunica prin mesaje. Axa orizontala reprezinta timpul. Bulinele reprezinta momentele de timp cand fiecare proces si-a salvat stare. Steluta marcheaza esecut procesului R.

P, Q si R reprezinta procese, ce comunica prin mesaje in timp. Fiecare proces isi salveaza starea de trei ori, momentele in care o fac sunt marcate prin buline negre. Sa presupunem ca procesul R are un esec, marcat print stealuta, dupa trimiterea mesajului m7. Astfel, el revine la ultima stare salvata r2, ceea ce anuleaza transmiterea lui m7. De accea, si receptia lui m7 la procesul Q trebuie anulata, deci Q va reveni in starea q2. Totusi asta elimina mesajul m5 trimis de Q la P, iar P va trebui sa revina in starea p2. Din pacate, revenirea nu se incheie, stare (p2, q2, r2) nu este consistenta, intrucat este anulata transmisia mesajului m4, dar acesta este consisderat primit in stare r2 al lui R.Astfel, R va trebui sa revina in starea r1, care va anula mesajul m6 si il va determina pe Q sa revina in q1, si se continua pana se va ajunge in stare globala (p0, q0, r0), ce este valida pentru ca nu a fost trimis nici un mesaj inca. Acest mecanism are un efect de domino, schimbarea starii unui proces le poate determina si pe celelalte sa o faca, si are potentialul de a pierde foarte mult progres al sistemului. Aceasta problema ar fi putut fi rezolvata mai usor, daca procesul R si-ar fi salvat stare dupa trimiterea lui m7, atunci sistemul putea reveni in stare consistenta (p2, q2, r2). Insa pentru a putea face acest lucru, ar fi fost nevoie ca toate cele trei procese sa colaboreze pentru a hotara cand ar trebui fiecare sa faca checkpoint. Acesta varianta se numeste checkpointing coordonat. In capitolul 8 din sunt prezentati cativa algoritmi de acest fel. Totusi exista cateva limitari in momentul cand sistemul comunica cu mediul exterior. De exemplu, nu i se poate cere unei imprimante sa stearga o parte din caracterele ce le-a printat deja. Pentru a rezolva astfel de cazuri, mesajele trimise mediului exterior sunt salvate. In continuare se prezinta acest mecanism.

Salvarea de Mesaje (Mesage Logging)

Este o tehnica pentru a imbunatatii eficienta revenirii din esec bazata pe checkpointing. Dupa cum s-a prezentat, checkpointing-ul necesita salvarea de stari in stable storage, si reveniri frecvente la stari consistente. Aceastea pot produce intarzieri nedorite ale sistemului. Chiar daca se foloseste coordonarea proceselor pentru a evita efectul de domino, si acesta presupune intarzieri de sincronizare. Logarea de mesaje ajuta prin factul ca, daca se incepe de la un checkpoint consistent P, sistemul poate reveni intr-un punct mai recent de esec prin reluarea mesajelor salvate in stable storage in aceeasi ordine in care s-au petrecut inainte de esec. Mesajele pot fi salvate fie de transmitator fie de receptor. Totusi, si aceasta salvare de mesaje necesita timp, iar o decizie importanta de design este daca un proces trebuie sa astepte pana un mesaj este salvat inainte sa il proceseze.

Toate protocoalele de salvare de mesaje au un tel comun: odata ce un proces isi revine din esec, starea lui trebuie sa fie consistenta cu al celorlalte. Daca acest lucru nu se intampla, procesul devine orfan. De aceea, astfel de protocoale trebuie sa garanteze ca daca se intampla o revenire din esec, niciun proces nu devine orfan. Sa luam urmatorul exemplu din figura 6 .

Figura 6: Exemplu de executie a unui sistem distribuit format din 4 procese.

, in care sunt schimbate trei mesaje intre processele 0, 1, 2 si 3. Daca mesajele m1 si m3 au putut fi salvate de procesele ce le-au primit, dar m2 nu, starea sistemului nu poate fi reconstruita mai departe de primirea mesajului m1. Din cauza ca procesul 3 a primit deja mesajul m3, iar trimiterea acestuia nu poate fi refacuta din istoric, acesta devine orfan. Daca insa, m2 ar fi salvat in istoric, procesul 3 nu ar mai deveni orfan.

Exista doua tipuri principare de protocoale de salvare de mesaje:

• pesimiste – inainte de a procesa un mesaj primit, un proces trebuie sa fi salvat toate mesajele primite anterior;
• optimiste – acestea implica un grad de risc prin faptul ca nu se salveaza toate mesajele. In acest caz, daca la revenirea din esec exista procese orfane se face rollback la o stare consistenta.

In cazul sistemelor nedeterministice, doua rulari ale sistemul pot ajunge in doua stari consistente diferite, intrucat ordinea in care mesajele sunt transmise si primita poate sa difere. Revenirea in astfel de sisteme, utilizand salvarea de mesaje, evidentiaza ultima rulare a sistemului si nu creaza nedeterminism suplimentar.

Replicare

Replicarea este cheia pentru a oferii availability si toleranta la defecte in sistemele distribuite si nu numai. Ea presupune duplicarea unor componente ale sistemului si sincronizarea lor, un exemplu sunt bazele de date. Astfel, daca una din replici experimenteaza un esec, celelalte pot sa o mascheze si sa mentina automat sistemul activ. Adevarul este ca nu se pot crea sisteme ce tolereaza defecte fara componente replicate.

Totusi vrem ca replicarea sa fie transparenta, un client nu ar trebuie sa fie constient de faptul ca existe mai multe copii ale datelor sau mai multe componente care fac acelasi lucru. Si se asteapta, ca atunci cand cere un serviciu, sa primesca un singur rezultat, chiar daca acel raspuns este optinut de mai multe copii.

Replicare pasiva.

In acest tip de replicare, in orice moment o singura replica este activa, restul sunt de rezerva, vezi figura 7.

Figura 7: Modelul general pentru replicarea pasiva

Clientul cere componentei de front end un serviciu, aceasta va redirectiona cererea replicii principale, ce o va executa. Daca pentru a indeplinii cererea sunt implicate si modificari ale unor valori, atunci aceastea sunt transmise prin mesaje la restul replicilor pentru a le actualiza. Apoi replica principala va returna rezultatul. Daca componenta de front end nu primeste raspuns intr-un anumit timp, se presupune ca replica principala a esuat, si va retransmite cererea la replica ce i-a luat locul.

Pentru a putea functiona avand pana la f crash failures, sistemul de replicare pasiva necesita f + 1 replici. Front end-ul trebuie doar sa poata avea abilitatea sa descopere noua replica activa, in cazul in care cea principala nu raspunde. Totusi, exista o incarcare mare pentru replica principala, care trebuie sa raspunda la toate cererile de la client si sa se asigura ca informatiile din replicile de rezerva raman la zi.

Replicare Activa

In acest mod de replicare, copiile joaca acelasi rol si functioneaza ca un grup. Componentele de front end trimit cererile de la client la toate replicile, si acestea le vor procesa independent, vezi figura 8 , dar identic si vor raspunde.

Figura 8: Modelul general pentru replicarea activa

Componenta de front end va primii toate raspunsurile si va construi un raspuns pentru client. Daca o replica esueaza, ea nu va afecta raspunsul, intrucat celelalte replici vor oferi raspunsuri. Replicarea activa poate tolera si byzantine failures, pe langa crash failures, pentru ca front end-ul primeste toate raspunsurile si le poate compara pentru a gasi anomalii si a le evita, prin vot majoritar. Replicile sunt considerate state machines, cererile pentru componente de front end si replici sunt primite in maniera FIFO. De asemenea, nici o cerere noua nu este procesata pana cea veche nu se termina. Ecest lucru face ca replicile sa fie mereu sincronizate.

Exemple de abordari pentru a tolera defecte.

Toleranta la crash failures.

Una dintre cele mai simple metode de a tolera erori de tip crash este replicarea proceselor sau modulelor functionale. Considerand un process B ce primeste ca intrare o valoare x, executa operatia y = f(x) si trimite rezultatul la un proces C. Daca B devine nefunctional, atunci C nu primeste valoarea lui y. Pentru a masca eroarea lui B, acesta este inlocuit cu doua copii B0 si B1, ambele legate cu procesul C. Aceasta abordare evidentiata in figura 9a , se numeste double modular redundancy (DMR) si poate masca un crash. In cazul general, daca se utilizeaza n > 1 replici ale lui B, este posibila tolerarea a pana la n – 1 replici.

Figura 9: a) Double modular redundancy (DMR); b) Triple modular redundancy (TMR).

Un alt mod prin care poate fi mascata defectarea lui B este utilizarea a trei copii si un mecanism de votare V. Daca una dintre replici este defecta, din cauza unui crash sau unei erori arbitrare, procesul C va primii valoarea corecta a lui y pentru ca votul majoritatii va exclude valoarea eronata. Totusi, este posibil ca si componenta de votare V sa esueza, asa ca ea este considerata ca o parte a componentei C, astfel daca C esueaza, atunci rezultatul votului nu mai conteaza. Aceasta este metoda triple modular redundancy (TMR), vezi figura 9b, si poate masca o eroare de orice tip din B. Generalizarea ei este n-modular redundancy si poate masca m erori arbitrare, atata timp cat n >= 2 * m + 1.

Toleranta la omission failures.

Se presupune un process S ce trimite o secventa de mesaje m[0], m[1], m[2], ... la un receptor R (vezi figura 10 ).

Figura 10: Canalreliable intre S si R.

Daca nu este cunoscut timpul maxim de propagare a mesajelor si canalele nu sunt de tip FIFO, atunci receptorul trebuie sa ii confirme transmitatorul ca a primit un mesaj. Pentru a detecta ca un mesaj nu a ajunge, procesul S poate face o presupunere asupra timpului de propagare si isi va seta un cronometru. Daca transmitatorul nu primeste confirmarea dupa un acest timp, va retransmite mesajul. In cazul in care S asteapta prea putin pentru o confirmare, va transmite mesaje duplicate. Astfel, pentru a avea un canal reliable acesta trebuie sa fie:

1. Fara pierderi: in final R primeste un mesaj transmis de S;
2. Fara duplicate: R primeste un mesaj transmi de S exact o data;
3. Fara reordonare: R mereu primeste mesajul m[i] inaintea lui m[i + 1].

Pentru un implementa un canal reliable exista cateva abordari, vezi pentru detalii:

Stop-and-wait sau protocolul lui Stenning.

Acesta implementeaza un canal de comunicare fiabil. Modul de functionare este urmatorul. Transmitaroul trimite un mesaj si asteapta pana primeste un mesaj de confirmare, fara sa trimita un alt mesaj. Daca nu primeste o confirmare intr-un timp predefinit, va retransmite pachetul. Receptorul la trimirea unui mesaj va trimite un mesaj de confirmare. Daca acesta va primii acelasi mesaj de mai multe ori, inseamna ca mesajul de confirmare a fost pierdut si il va retransmite iarasi. Acest portocol are dezavantajul ca introduce timpi de asteptare suplimentari in transmitator, intrucat acesta nu poate trimite un nou pachet pana cel vechi nu este confirmat.

Fereastra glisante (Sliding Window Protocol).

Este un protocol de nivel transport si este o generalizare a protocolului lui Stenning, utilizand aceleasi mecanizme pentru pierderea si reordonarea mesajelor. Principala imbunatatire este ca transmitatorul S continua sa trimita mesaje, cel mult w (dimensiunea ferestrei) mesaje, fara sa trebuiasca sa primeasca vreo confirmare de la receptorul R. Daca nu se primeste confirmare pentru cele w mesaje intr-un anumit timp maxim, S va retransmite toate cele w mesaje. Acest comportament este evidentiat in figura 11 , pentru o fereastra de dimensiune 4.

Figura 11: Protocolul Sliding Window pentru o dimensiune a ferestrei egala cu 4.

Alternating Bit Protocol.

Este un caz special a abordarii anterioare, in care w = 1. Functioneaza doar pentru canale FIFO. Numele ii vine de la faptul ca adauga un alternativ un bit de 0 sau 1 mesajelor inainte de a le transmite. Se presupune figura 12 : S a trimis un mesaj m[0] spre R si i-a atasat un bit cu valoarea 0. S foloseste un cronometru, ce il va determina sa retransmita acelasi mesaj. S va transmite acelasi mesaj pana primeste un mesaj de confirmare ack in care este atasat un bit de 0, apoi pentru urmatorul mesaj va atasa un bit de 1, apoi de 0 si tot asa. Cand R primeste un mesaj, va trimite o confirmare la care va adauga un bit cu o valoare egala cu bitul din acel mesaj. Mesaje consecutive cu aceleasi valoare pentru acel bit vor reprezenta mesaje duplica, acest lucru este garantat de canalele FIFO.

Figura 12: Exemplu de rulare al Alternating Bit Protocol

Transmission control protocol TCP

Este cel mai folosit protocol de management pentru conexiuni in internet. Suporta conexiuni end-to-end intre doua procese ce ruleaza pe doua calculatoare ce pot fi, sau nu, in aceeasi retea. Foloseste mecanizmul de fereastra glisanta si se descurca cu mesaje pierdute sau reordonate. Legatura dintre este creata printr-o etapa de realizare de conexiune si terminata de de o etapa de inchidere a conexiunii.

O problema este abilitatea de a genera numere de secvente unice pentru mesaje. Un numar de secventa este sigur (safe) daca este diferit de oricare ce a mai fost atasat la un mesaj care inca este in tranzit. Modul de generare a acestor numere pot sa nu garanteze unicitatea totala, insa au o propabilitatea mare sa o faca. Acestea pot fi imbunatatite daca sistemul cunoaste limita superioara δ a timpului de propagare a mesajului pe canal, intrucat fiecare numar de secventa poate fi refolosit dupa un interval de 2 * δ. Faza de conectare este evidentiata in figura 13 .

Figura 13: Etapa de realizare a unei conexiuni in TCP

Transmitatorul S trimite un mesaj de sincronizare (SYN, seq = x), x este numarul de secventa, pentru a cere o conexiune. Receptorul R accepta conexiunea prin propunearea unui nou numar de secventa seq=y si lipirea lui de x, astfel ca S sa stie ca este un raspuns pentru cererea lui. Partea din mesaj ack=x+1 reflecta acceptarea cererii de conexiune ce a avut numarul de secventa x. Daca receptorul raspunde cu un mesaj (seq = y, ack = z) si z /= x + 1, transmitatorul considera ca este un mesaj gresit, il ignora si continua sa astepta dupa mesajul corect. Pentru a realiza conexiunea, transmitatorul S trimite un mesaj (ack, y+1) inapoi la receptor, pentru a indica ca accepta numarul de secventa y. Acest mecanism se numeste three-way handshake. Transmitatorul incepe sa trimita date incepand cu numarul de secventa x + 1. Daca una dintre parti doreste sa inchida conexiunea, va trimite un pachet FIN. Conexiunea se va termina cand un mesaj de confirmare ack este transmis de R si primit de S. Daca un pachet este pierdut, se retransmite dupa o perioada de timp.

Sistem tolerant la defecte - Chubby

Este un serviciu crucial din infrastructura companiei Google ce ofera stocare si coordonarea de servicii pentru alte servicii din infrastrutura lor, incluzand GFS si Bigtable. Acesta ofera patru capabilitari:

1. Ofera lacate distribuite pentru sincronizarea activitatilor intr-un mediu distribuit la scara mare;
2. Ofera un sistem de stocare de incredere pentru fisiere mici;
3. Poate fi utilizat pentru selectia unui lider dintr-un set de copii;
4. Este folosit ca name service in Google.

Una dintre mecanismele sale include tehnici de asigurare a consensului, cel folosit de ei este Paxos. Este o familie de protocoale ce pun la dispozitie ajungerea la consens intr-un sistem distribuit. Prin consens intelegem, problema in care mai multe replici ale unui proces propun fiecare o actiune pentru urmatorul pas. Obiectivul consensului este de a face ca un set de replici ale unui proces sa ajunga la un acord pentru a modifica o valoare comuna, avand in vedere ca unele dintre replici pot sa ruleze la viteze diferite sau pot sa fi experimentat erori si sa propuna valori gresite. Se considera ca replicile au acces la o forma de stocare persistenta si stabila ce se mentine daca apare un esec, de asemenea mesajele pot sa fie pierdute, reordonate sau duplicate. Totusi este necesar ca odata ce un mesaj este transmis, el ajunge fara a fi corupt, insa poate dura un timp arbitrar de lung pentru a fi transmis. Astfel este un algoritm bun pentru sisteme asincrone distribuite. Paxos garanteaza ca raspunsul final este corect, dar nu garanteaza ca algoritmul se va termina. Fiecare replica poate sa propuna o valoare cu scopul de a obtine un acord asupra valorii finale. Algoritmul garanteaza ca ajunge la consens daca majoritatea replicilor ruleaza pentru suficient timp. Algoritm este descris prin urmatorii pasi, vezi :

1. Algoritmul se bazeaza pe abilitatea de a alege un coordonator pentru a lua o decizie. Intrucat coordonatorii pot sa esueza, modul de alegere a lor permite exista a mai multi coordonatori deodata, noi si vechi, cu scopu de a recunoaste si elimina mesaje de la coordonatorii vechi. Pentru a indentifica coordonatorul corect, este facuta o ordonare prin utilizarea de numere de secventa. Fiecare replica mentine cel mai mare numar de secventa ce l-a intalnit pana in acel moment, iar daca doreste sa fie noul coordonator, va alege un numar mai mare ce il va trimite la toate replicile intr-un mesaj de propunere (propose message). Este clar, ca modul de alegere a numerelor de secventa trebuie sa faca ca doua replici sa nu poate alege aceleasi numar. Un mod a garanta aste este de a asigna fiecarei replici un identificator i_r, intre 0 si n-1, si apoi selectarea celui mai mic numar s ce este mai mare decat numerele de secventa vazute pana acum, astfel incat s mod n = i_r ( daca n este 5, si suntem la replica i_r cu numar 3 si ultimul numar de secventa a fost 20, ulmatorul numar ales va fi 23). Daca o replica primeste un mesaj de propunere si nu au mai vazut un numar de secventa mai mare, fie va raspunde cu o mesaj prin care promite ca nu va interactiona cu alti coordonatori (mai vechi), sau va trimite un mesaj de neconfirmare prin care indica ca nu vor vota pentru acest coordonator. Mesajele de promisiune vor contine cea mai recenta valoare de care transmitator stie ca este propusa pentru raspunsul final, aceasta poate fi nula daca nu s-au observat propuneri. Daca se primesc un numar majoritar de mesaje de promisiune, replica ce le-a primit devine coordonator cu o majoritate de replici ce o sustin;
2. Coordonatorul ales trebuie sa selecteze o valoare si sa trimita mesaje de acceptare cu aceasta valoare la majoritatea ce l-a ales. Daca existau valori in mesajele de promisiune atunci coordonatorul trebuie sa aleaga una din ele, altfel poate propune singur o valoare. Fiecare membru din majoritatea trebuie sa accepte valoare primita de la coordonator si sa confirme acest lucru. Coordonatorul va astepta, poate nelimitat, pentru ca o majoritate a replicilor sa confirme acceptarea acestei valori.
3. Daca o majoritate a replicilor au confirmat, atunci un acord a fost indeplinit. Coordonatorul trimite un mesaj de comitere la toate replicile pentru a le anunta acordul statibil. Altfel, coordonatorul abandoneaza propunerea si incearca iarasi.

Un exemplu de consens fara erori este in figura 14 .

Figura 14: Exemplu de rulare al algoritmului Paxos cand nu apar erori

Algoritmul este safe in prezenta erorilor, cum ar fi esuarea unui coordonator sau a alteri replici sau probleme de pierdere, reordonare sau mesaje duplicate sau intarziate, intrucat ceea ce conteaza este gasirea unei majoritati.

Paxos poate esua terminarea daca doi proposers concureaza si fiecare genereaza permanent numere de secventa mai mari. Pentru o descriere a Multi-Paxos si a dificultatilor ce apar pentru a face algoritmul sa functioneaze in sistemul Chubby, de la Google, vezi .

Conluzii.

Exista foarte multe tipuri de erori ce pot sa compromita functionarea corecta a unui sistem. Exista de asemenea foarte multe metode care incearca sa memtina sistemele intr-o stare buna cat de mult posibil, o parte din ele au fost exemplificate in acest studiu, insa sunt doar o mica parte, vezi pentru informatii suplimentare. Am vazut ca multe tehnici necesita replicarea unor componente si unele asumpii asupra unor timpi superior de raspuns a lor. Totusi, nu este posibila crearea unui sistem care sa nu experimenteze niciodata o eroare. Acest lucru este acceptat si de aceea, ce conteaza cu adevarat este gasirea de metode care sa poate controla frecventa cu care defectele se manifesta si detectarea lor inainte de putea provoca un dezastru.