Sisteme distribuite – teorie5. Semantica esecurilor in RPC.

Comunicatie in grup

Noiembrie 6, 2009

Esecuri in comunicare

pierderea de mesajecaderea unui proces

1. Pierderea mesajului cerere2. Pirederea mejajului raspuns3. Caderea serverului4. Caderea clientului

Tipuri de esecuri (1/2)

1. Pierderea unui mesaj cerere: Clientul trebuie sa retransmita mesajul dupa un timeoutProblema: clientul nu poate diferentia diferitele tipuri de esecuri

Ex: daca mesajul rezultat este cel care a fost pierdut, o retransmitere a mesajului cerere poate rezulta in executarea de doua ori a procedurii la distantaEx: proceduri care necesita mult timp vs. selectia unuitimeout scurt

2. Pierderea unui mesaj raspuns:Clientul retrasnmite cererea dupa un timeout.Problema: daca serverul nu recunoaste ce s-a intamplat, executa procedura din nou

Tipuri de esecuri (2/2)

3. Caderea serverului: Daca serverul cade datorita unei erori, trebuie determinatdaca executia partiala a procedrii a produs deja efecte in stare.

Ex. Daca baza de date a fost modificata in timpulprocedurii, problema recuperarii si a continuarii din momentul esecului nu este triviala

4. Caderea clientului: Un proces client care cade in timpul executiei unui RPC este referit ca o invocare orfanaProblema: ce face serverul u rezultatele si unde trebuiesa le trimita

Semantica esecurilorAplicatii diferite pot avea cerinte diferite in ceea ce privestecalitatea serviciului (QoS) in termeni de detectie a esecurilorsi recuperare

Executie: 1 Rezultat: 1

Executie: 1 Rezultat: 1

Executie: 1 Rezultat: 1

Exactly once (Exact odata)

Executie: 0/1 Rezultat: 0

Executie: 1 Rezultat: 1

Executie: 1 Rezultat: 1

At-most-once (Cel mult odata)

Executie: >=0 Rezultat: >=0

Executie: >=1 Rezultat: >=1

Executie: 1 Rezultat: 1

At-least-once (Cel putin odata)

Executie: 0/1 Rezultat: 0

Executie: 0/1 Rezultat: 0

Executie: 1 Rezultat: 1

Maybe (Poate)

Cadereserver

Pierderemesaj

Operatie faraesec

Semanticaesecului

Semantica Maybe

Referita ca si efortul cel mai bun. Nu ofera mecanisme pentru tratareaesecurilorEx. RPC poate fi executat o data sauninciodata la partea serverClientul receptioneaza cel mult un rezultatNu ofera garantiiAtata timp cat nu apar esecuri, RPC esteadersat adecvat

Semantica At-least-once

RPC va fi executat la partea server cel putin odata in cazul pierderii de mesajeDupa un timeout, clientul repeta RPC pana candreceptioneaza un raspuns de la serverO procedura poate fi efectuata de mai multe ori la serverE posibil ca un client sa receptioneze raspunsurimultiple datorate exeutiei repetateNu ofera o confirmare daca serverul cadeAdecvata pentru proceduri idempotente care nu cauzeaza schimbarea starii la server si pot fi executatemai mult decat o data fara a produce pagube

Semantica At-most-once

Procedura va fi executata cel mult odata –atat in cazul pierderii de mesaje cat si a caderii serveruluiDaca serverul nu cade, sunt garantate exact o executie si exact un rezultatNecesita un protocol complex de gestiune a mesajelor si numerotare

Semantica Exactly once

Cazul ideal, nu este usor de atinsInvocarea de catre un client va rezulta intr-o singuraexecutie la partea server si va fi furmizat un singurrezultatDezirabila pentru tranzactii bancareCazul cel mai simplu: operatii idempotente

Cazul unei simple infomrari care doar citeste data de la serverul de la distanta fara a schimba starea serverului

Executia repetata si numeroase mesaje rezultat nu sunto problema

Comunicarea in grup

RPC: doua parti, clientul si serverulContra-exemplu: un grup de servere de fisiere care coopereaza pentru a oferi un singur sistem de fisiere tolerant la esecuri

Clientul expediaza un mesaj la toate servererelepentru a se asigura ca cererea este onorata chiardaca unul dintre acestea cedeazaRPC nu poate trata comunicarea de la un expeditor la mai multi receptori (in afara cazului in care efectueaza RPC-uri separate cu fiecaredintre ele)

Grup= colectie de procese care actioneaza imprena intr-o modalitate specificasistemeului sau utilizatorului. Scop: permite proceselor sa trateze colectii de procese ca o singuraabstractizare -> un proces poate trimite un mesaj la un grup de serverefara a a cunoaste cate sunt si unde sunt (caracteristici ce se pot schimbade la un apel la altul) Proprietate cheie: cand un mesaj este expediat la un grup specific, totimembrii grupului il receptioneaza

forma de comunicare unul-la mai multi in contrast cu comunicareapunct-la-punct

Dinamicitate (analogie cu organizarea sociala !)Grupuri noi pot fi create, grupuri vechi pot fi distruse. Un proces se poate alatura unui grup sau il poate parasiUn proces poate fi membru la mai multe grupuri in acelasi timp

-> Sunt necesare mecanisme pentru a administra grupurile si apartenentala grupuri

Implementari ale comunicarii in grup1. Tehnica multi-casting (difuzare multipla)

Crearea unui adrese speciale de retea (de exemplu indicare prinsetarea bitilor celor mai semnificativi pe 1), la care asculta masinimultiple Cand este expediat un pachet la una dintre aceste adrese, esteautomat livrat la toate masinile care asculta la respectiva adresaImplementarea grupuriloe utilizand multi-casting este imediata: asignarea fiecarui grup la adrese multi-cast diferite

2. Tehnica broad-casting (difuzare larga)Pachelete care contin o anukita adresa sunt livrate la toatemasinilePoate fi utilizata pentru a implementa grupurile, dar este mai putineficienta:

Fiecare masina primeste fiecare difuzare si softwareul sau trebuie saverifice daca pachetul ii este adresatDaca nu, pachetul este ignorat, dar un anumit timp este pierdut pentrua tratarea intreruperii

Necesita doar un pachet care ajunge la toti membrii grupului

Implementari ale comunicarii in grup

1. Multi-casting2. Broad-casting, daca multicasting nu este permis3. Uni-casting (transmitere punct-la-punct),

daca mc sau bc nu sunt permiseExpedierea unui mesaj de la un singur expeditor la un singur destinatarExpeditorul transmite pachete separate pentru fiecarememru din grup. Pentru un grup cu n membrii, sunt necesare n pachete, spre deosebire de un pachet cand este utilizat mc sau bcDesi mai putin eficienta, aceasta implementare estefunctionala daca grupurile sunt mici

Designul comunicarilor in grupDrept cazuri de transmitere de mesaje:

Cu buffer vs. fara bufferCu blocare vs. fara blocareEtc

Optiuni aditionaleGrupuri inchise vs. Grupuri deschise. Grupuri de semeni vs. Grupuri ierarhice

Alte problemeApartenenta la grupAdresarea grupuluiPrimitivele Send si ReceiveAtomicitateOrdonarea mesajelorGrupuri cu suprapunereScalabilitate

Grupuri inchise vs Grupuri deschise

Grupuri inchise: In care numai membrii grupului pot trimite mesaje la grup.Cei din exteriori nu pot trimite mesaje la grup ca tot, desipot trimite mesaje la membrii individualiExemplu: O colectie de procese care lucreaza impreunapentru un joc de sah pot forma un grup inchis; au propriulscop si nu interactioneza cu lumea inconjuratoare.

Grupuri deschise: fiecare proces din sistem poate trimite la oricare grupExemplu: grup de servere replicate; este important ca proceserel care nu sunt membre (clientii) sa poate expediamesaje la grup.

Grupuri de semeni vs. Grupuri ierarhiceGrupuri de semeni (Peer Groups)

Toate procesele sunt egale. Nici un proces nu este sef si toate deciziile sunt loate in colectivGrupul este simetric si nu are un punct singular de esecDaca procesesele esueaza, grupul devine mai mic, dar continuaDezavantaj: procesul de decizie este complicat – pentru a decide orice, estenecesar un vot ceea ce duce la intarzieri si surplus in timp

Grupuri ierarhiceUn proces este cordonator si celelalte sunt lucratori.Cand este generata o cerere de lucru fie de catre un client extern sau de unul dintrelucratori, este trimisa la coordonator care decide care lucraryor este cel mai adecvatsa efectueze lucru si i-l expediazaPierderae coordonatorului duce intregul grup la o oprire, dar atat timp cat functioneaza deciziile se iau fara a deranja pe altiiEx: un grup ierarhic este indicat pentru un program de sah:

Coordonatorul considera situatia curenta, genereaza toate miscarile posibile din aceasta sile trmite lucratorilor pentru evaluareCa urmare a evaluarii noile situatii sunt expediate la coordonator pentru a le evaluaCand un lucrator nu este ocupat, cere coordonatorului de lucruCoordonatorul contrleaza strategia de cautare

Apartenenta la grup

Anumite metode sunt necesarepentru a crea si sterge grupuri, pentru a permite proceselor sa se alature sau saparaseasca grupuri

Abordari:1. Exista un server de grup la care sunt transmise toate

cererile2. Administreaza apartenenta la grup intr-o modalitate

distribuita. Intr-un grup deschis,un outsider poate trimite un mesajla toti membrii grupului pentru a-si anunta prezentaIntr-un grup inchis, este necesar ceva similarPentru a parasi grupul, un membru trimite mesaj catrefiecare membru

Adresarea grupului – abordari1. Fiecare grup are o adresa unica, precum o adresa de proces.

Permis multi-cast-ul: adresa de grup poate fi asociata cu o adresamulti-castPermis broad-cast-ul: mesajul poate fi difuzat. Numai uni-cast-ul est permis: necesar o lista de masini care au procese ce apartin grupului.

2. Cere expeditorului sa ofere o lista explicita a tuturor destinatiilor3. Fiecare mesaj este expediat la membrii grupului prin una din

metodele descrise anterior, dar in plus :Fiecare mesaj contine un predicat (expresie Booleana) de evaluat.Predicatul poate include numarul masinii destinatare, variabilelesale locale si alti factori. Daca predicatul este evaluat prin TRUE, mesajul este acceptat. Daca este evalaut prin FALSE, mesajul este ignorat. Exemplu: expediaza un mesaj numai la acele masini care au celputin 4M de memorie libera si sunt dispuse sa preia noul proces

Primitivele Send si Receive

1. Uneste cele doua forme de comunicare : group & point2point?

Send: Parametru -- destinatie

O adresa de proces, un singur mesaj este trimis la un proces.O adresa de grup (sau o referinta la o lista de destinatii), un mesajeste trimis la toti membrii grupului

Receive:Complet cand soseste un mesaj punct-la-pounct sau de grup

2. Proceduri noi de biblioteca:group-send group-receive

Atomicitate

Dezirabila deoarece face programarea sistemelordistribuite mai usoara. Un proces care expediaza un mesaj la un grup nu trebuie sa-si faca griji ce sa faca daca unul dintremembrii nu l-a primitExemplu – intr-un sistem de baze de date distribuitesi cu replicare:

Un proces expediaza un mesaj la toate masinile care detinbaza de date pentru o noua inregistrare in baza de date

Are certitudinea ca data a fost scrisa in toate replicile

Ordonarea mesajelorOrdonarea in timp global:

Se asteapta ca toate mesajele sa fie licrate instantaneu si in ordinea in care au fost exepdiateToate destinatiile obtin toate mesajele in exact acceasi ordineIgnora din motive de convenienta faptul ca nu exista un timp global absolut!

Ordonarea in timp absolut nu este intotdeauna uso de implementat! Anumite sisteme ofera variatiuni pe aceasta tema. De exemplu: Ordonare in timp consistenta:

Daca doua mesaje, fie A si B sunt expediate apropriat in timp, sistemulpreia unul dintre acestea ca fiind “primul“ si il livreaza la toti membriigrupului urmat de celalalt. Se intampla ca cel ales sa nu fie cel real, dar compotarea sistemuluinu depinde de acestaMesajele ajung la toti membrii grupului in aceeasi ordine, dar ordineanu neaparat este ordinea reala in care au fost expediate.

Grupuri cu suprapunere

Desi exsita o ordonoare in timp in fiecare grup, nu estein mode necesar si o coordonare intre grupuri multipleAnumite sisteme suporta ordonarea in timp intre grupurisuprapuse, altele nuImplementarea ordonarii in timp intre grupuri diferite estedificila