234-265 Flashcards
bjasniti „izolovanje neispravnosti“ i „toleranciju neispravnosti“.
- Izolovanje naispravnosti – obezbeđivanje da neispravnost jedne komponente ne utiče na
funkcionalnost ostalih komponenti. Posledica: funkcija koju je obezbeđivala neispravna
komponenta nije raspoloživa dok se problemi ne otklone i komponenta ne postane
operativna. - Tolerancija neispravnosti – u slučaju neispravnosti neke od komponenti, druge komponente
preuzimaju njene funkcije. Posledice: povećana fleksibilnost i pouzdanost sistema; povećana
složenost i cena sistema.
Objasniti osnovne aspekte pouzdanosti sistema
Pozdanost sistema čine:
* Raspoloživost sistema – sposobnost sistema da primi zahtev. Relativno nisko trajanje
perioda kada sistem ne radi. Ili retko dolazi do neispravnosti ili se one brzo uklanjaju
* Odgovornost sistema – sposobnost sistema da odgovori na zahtev. Sistem ili uopšte neće
imati neispravnosti tokom rada ili će one biti prevazilažene u hodu tako da ne bude prekida
operativnosti. Ili retko dolazi do neispravnosti ili je sistem u potpunosti sposoban da se
dovoljno brzo oporavi da one ne ometaju rad
Šta je replikacija podataka i koje su njene osnovne karakteristike?
Replikacija je svako udvajanje komponente računarskog sistema koje donosi neki nivo
redundantnosti
Objasniti vrste izvora replikacije
Predmeti replikacije mogu biti: podaci, procesi, objekti, poruke. Nas prvenstveno zanima replikacija
podataka (baza podataka, tabela, fragment tabele, globalni katalog baze podataka, sistem datoteka,
pojedinačna datoteka).
Koji su osnovni ciljevi replikacije?
Dva osnovna motiva su podizanje performansi (ostvaruje se kroz raspodelu opterećenja na replike) i
pouzdanosti (implementacija tolerancije neispravnosti i prepoznavanje neispravnosti).
Koja su ograničenja replikacije?
Osnovnu cenu replikacije predstavljaju:
* Dodatna cena prostora zbog redundantnosti čuvanja podataka
* Povećana cena pisanja zbog menjanja podataka na više lokacija
* Povećan obim prenosa podataka radi replikacije
* Cena dodatne obrade usled implementacije replikacije
Ograničenje efikasnosti - ako je ograničena raspoloživost jedne kopije A, onda je ograničena i
raspoloživost repliciranog sistema.
Koji su osnovni načini implementacije replikacije podataka?
- Čitaj jedan piši sve (ROWA)
- Konsenzus kvoruma (KK) – glasanje
- Konsenzus kvoruma u uređenim mrežama
Šta je protokol ROWA? Kako se u osnovi implementira?
ROWA – “čitaj jedan, piši sve”. Samo primarna kopija se čita, a sve kopije se menjaju. Tolerišu
otkaze lokacija kada je u pitanju čitanje. Ne tolerišu otkaze lokacija kada je u pitanju pisanje. Ne
toloerišu otkaze komunikacija
Šta je ROWA? Koje su osnovne varijante ovog protokola?
ROWA – “čitaj jedan, piši sve”. Varijante:
* osnovni ROWA protokol
* ROWA-A, sa menjanjem raspoloživih kopija
* ROWA sa primarnom kopijom
* ROWA sa tokenima pravih kopija
Objasniti detaljno osnovni protokol ROWA.
Prevodi svaku operaciju čitanja u jednu operaciju čitanja, na jednoj od kopija. Prevodi svaku
operaciju pisanja u N operacija pisanja, po jednu na svakoj kopiji. Kontroler konkurentnosti na svakoj lokaciji sinhronizuje pristup kopijama – svaka promena mora da uspe na svim lokacijama ili
ni na jednoj. U slučaju otkazivanja neke lokacije čitanje je i dalje moguće, ali pisanje nije moguće
do oporavka neispravne lokacije
Objasniti detaljno protokol ROWA-A.
“Read One Write All Available”. Razlika u odnosu na osnovni protokol – pisanje se izvodi ne na
svim nego na svim raspoloživim kopijama. U slučaju otkazivanja neke lokacije čitanje je i dalje
moguće, pisanje je i dalje moguće, a neispravne lokacije mogu da postanu raspoložive tek nakon
oporavka uz puno prepisivanje svih izmena nastalih tokom neoperativnog perioda.
„Algoritam raspoloživih kopija“ – sinhronizuje neuspehe i oporavke kontrolisanjem raspoloživosti
kopija. Operacije pisanja se šalju svim kopijama – ako neka lokacija nije operativna, od nje nema
odziva u dopuštenim okvirima; ako jeste, onda je operacija pisanja obrađena ili odbačena.
Pre potvrđivanja transakcije koordinator započinje primenu dvofaznog protokola validacije:
* „validacija propuštenih pisanja“ – proverava se da li su sve kopije koje su propustile neko
pisanje još uvek neoperativne
* „validacija pristupa“ – proverava da li su sve kopije koje su čitale ili pisale još raspoložive
Koje su prednosti protokola ROWA-A u odnosu na osnovni
protokol ROWA? Ograničenja?
Prednost protokola ROWA-A je što je u slučaju otkaza pisanje i dalje moguće, što nije slučaj kod
osnovnog protokola.
Problemi: svakoj neispravnoj lokaciji se šalju bar dva zahteva i na svaki se čeka najviše dopušteno
vreme, time se potencijalno gubi značajno vreme i smanjuje odzivnost sistema; iako bezbedan,
postupak dvofazne validacije nije efikasan.
Objasniti detaljno protokol ROWA sa primarnom kopijom.
Razlika u odnosu na osnovni protokol: jedna kopija se proglašava za „primarnu“; ostale kopije su
„rezervne“; čitanje se izvodi samo sa primarne kopije; pisanje se izvodi na primarnoj i svim
raspoloživim rezervnim kopijama. Ovaj protokol ne podiže performanse čitanja i unapređuje samo
pouzdanost sistema.
Ako primarna kopija postane neoperativna, izabrana rezervna kopija postaje nova primarna. Da bi
ovo bilo moguće potrebno je da bude moguće nedvosmisleno razlikovati neoperativnost primarne
kopije od problema u komunikaciji.
Ako rezervna kopija postane neoperativna, ona ne može postati primarna sve dok ne bude u
potpunosti oporavljena i može preuzeti neke uloge rezervne i nakon delimičnog oporavka.
Koje su prednosti protokola ROWA sa primarnom kopijom u
odnosu na osnovni protokol ROWA?
Ovaj protokol ne podiže performanse čitanja, unapređuje samo pouzdanost sistema. Najčešće
upotrebljiv jer je jednostavan
Objasniti detaljno protokol ROWA sa tokenima “pravih” kopija
Razlika u odnosu na osnovni protokol: svaki podatak, u bilo kom trenutku vremena, ima ili jedan
ekskluzivan token ili skup deljivih tokena; operacija pisanja mora da dobije ekskluzivan token;
operacija čitanja mora da dobije bar deljivi token. „Uzimanje“ tokena obuhvata, po potrebi, i
ažuriranje podatka.
Pri pisanju: kada kopija mora da izvrši operaciju pisanja, ona locira i uzima ekskluzivan token za
konkretan podatak. Ako on ne postoji, ona locira i proglašava za neispravne sve deljive tokene za
konkretan podatak i pravi novi ekskluzivan umesto njih.
Pri čitanju: kada kopija mora da izvrši operaciju čitanja, kopija locira deljivi token, kopira njegovu
vrednost i pravi i čuva novi deljivi token. Ako ne postoji deljivi token, ona locira ekskluzivan token
i konvertuje ga u deljivi i zatim postupa kao u prethodnom slučaju.
Token ima objedinjenu semantiku nalik na „lokalni katanac“ na „distribuiranom podatku“.
Predstavlja mehanizam za prepoznavanje konflikata između više pisanja ili između pisanja i čitanja.
U slučaju problema samo lokacije koje imaju token na nekom podatku mogu koristiti taj podatak.
Ako su svi tokeni na podatku locirani na neoperativnoj lokaciji, taj podatak nije raspoloživ.
Nakon pisanja, promena bi trebalo da se distribuira. To se postiže različitim mehanizmima.
Koji od protokola ROWA se najčešće upotrebljava u praksi?
Zašto?
Iako je ROWA-A algoritam relativno jednostavan i ima nekih slabosti, ipak je jedan od najčešće
upotrebljavanih, naravno, samo u slučajevima gde je jedini cilj podizanje nivoa pouzdanosti
Šta je konsenzus kvoruma? Po čemu se razlikuje od protokola
ROWA?
Razlika: dopušta pisanje na podskupu operativnih lokacija; čitanja se izvode sa podskupa lokacija
koji mora da ima neprazan presek sa kvorumom pisanja.
Pravilo preseka kvoruma obezbeđuje da će svako čitanje moći da se odvija sa najsvežije pisanim
vrednostima. Za lokaciju koja učestvuje u operaciji se kaže da je glasala za operaciju.
Opisati opšte karakteristike konsenzusa kvoruma.
Ova tehnika maskira neispravnosti, bez dodatnih zahteva pri oporavku neispravnih lokacija
(efikasnije nego u slučaju validacije u dva koraka). Kvorumi mogu biti: statički (određeni glasanjem
pri podizanju sistema) ili dinamički (ako lokacije mogu da se rekonfigurišu)
Koje su vrste konsenzusa kvoruma? U čemu je osnovna razlika
među vrstama?
- KK sa uniformnom većinom
- KK sa težinskom većinom
- KK sa težinskom većinom za direktorijume
- Uopšteni KK za apstraktne tipove podataka
- Hibrid ROWA/KK
Objasniti detaljno konsenzus kvoruma sa uniformnom većinom.
Operacija čitanja ili pisanja uspeva akko većina lokacija odobri izvršavanje. Ne moraju sve lokacije
koje su glasale i da izvrše operaciju na svojim kopijama podataka – čitanje je dovoljno da se izvrši
na jednoj kopiji; pisanje mora da se izvrši na večini kopija. Počiva na prepoznavanju eventualnih
konflikata od strane upravljača konkurentnošću na pojedinačnim lokacijama.
Postiže se otpornost na neispravnosti: na lokacijama ili u komunikaciji.
Cena je relativno visoka i pri čitanju i pri pisanju. Bar polovina+1 lokacija mora učestvovati u
svakoj operaciji kroz glasanje.
Objasniti detaljno konsenzus kvoruma sa težinskom većinom.
Predstavlja uopštenje algoritma KK sa uniformnom većinom:
* svaka kopija ds podatka d dobija nenegativnu težinu tako da suma svih težina na jednom
podatku bude u
* sam podatak d dobija prag čitanja r i prag pisanja w, tako da važi: r+w>u i w>u/2
* kvorum čitanja (ili pisanja) podataka dje svaki skup kopija čija je težina bar r (ili w)
Za ustanovljavanje aktuelnosti kopija se obično upotrebljava mehanizam verzija podataka. Svaka
kopija podatka je označena brojem verzije, koji se inicijalno postavlja na 0.
Svaka operacija pisanja w[d] se prevodu u skup pojedinačnih operacija pisanja w[ds] na svim
kopijama u nekom kvorumu pisanja: čitanje svih kopija u kvorumu, čitanje njihovih verzija,
povećavanje maksimalnog broja verzije, pisanje svih kopija sa novim brojem verzije.
Svaka operacija čitanja r[d] se prevodu u skup pojedinačnih operacija čitanja r[ds] na svim
kopijama u nekom kvorumu čitanja: čitanje svih kopija, čitanje njihovih verzija, kopija sa najvećim
brojem verzije predstavlja rezultat.
Zbog većinskog glasanja, u svakom kvorumu čitanja sigurno postoji tekuća kopija podatka.
Načelno se ne zahteva složen algoritam oporavka. Algoritam je fleksibilan.
2
Objasniti razlike između konsenzusa kvoruma sa uniformnom
većinom i konsenzusa kvoruma sa težinskom većinom.
U slučaju ujednačenih vrednosti parametara r i w algoritam se svodi na KK sa uniformnom
većinom
Koje su specifičnosti konsenzusa kvoruma za direktorijume i
apstraktne tipove podataka?
Direktorijum je preslikavanje prostora ključeva u prostor vrednosti. Primenjuje se i na nerelacione
baze zasnovane na katalozima. Menja se granularnost operacija tako da se ne izvršavaju na
„velikim“ direktorijumima nego na njihovim manjim delovima.
Apstraktni tipovi podataka – sličan problem kao za direktorijume.
Objasniti detaljno hibridni protokol ROWA / konsenzus kvoruma.
Objasniti motivaciju za njegovu primenu.
Osnovna slabost metoda KK je neopravdano visoka cena u slučaju retkih otkazivanja komunikacija.
Hibridni pristup redukuje cenu kroz: primenu metoda ROWA tokom pouzdanih operativnih perioda;
primenu metoda KK u uslovima postojanja otkaza lokacija ili komunikacija; transakcije mogu da
započnu rad u normalnom režimu i da tokom rada pređu u režim otkaza.
Postojanje otkaza se prepoznaje kroz propuštena pisanja:
* Ako transakcija prepozna da je bilo izostajanja pisanja neke kopije podatka koju je već
čitala, ona mora da bude prekinuta
* Ako transakcija prepozna da je bilo izostajanja pisanja neke kopije pre čitanja sa te kopije,
onda mora da pređe u režim KK i da čita sa kopija koje nisu propustile pisanje
Ako transakcija T uputi zahtev za pisanje i dođe do izostajanja pisanja na nekoj kopiji: samo
transakcija T to lako uočava i menja režim; da bi druge transakcije to doznale potrebni su dodatni
mehanizmi.
Šta je konsenzus kvoruma u uređenim mrežama? Motivacija?
Savremeni algoritmi replikacije pored tolerisanja neispravnosti stavljaju u prvi plan i optimizaciju
troškova. Pokušava se postizanje smanjivanja broja lokacija koje odlučuju u glasanju uvođenjem
logičke strukture u skup lokacija
Koji su osnovni algoritmi koji se upotrebljavaju u konsenzusu
kvoruma u uređenim mrežama?
- Algoritam √n
- Protokol matrice (GRID)
- Asimptotska visoka raspoloživost
- Drvo kvoruma
- KK sa hijerarhijskom težinskom
većinom - KK sa višedimenzionalnom težinskom
većinom
Objasniti protokol GRID. Koje su mu osnovne karakteristike?
Skupovi lokacija se uređuju u obliku matrice sa N kolona i M vrsta, tako da je M*N≤n. Jedan
kvorum čitanja obuhvata lokacije sa po tačno jednom lokacijom iz svake kolone. Kvorum pisanja se
sastoji od svih lokacija jednog kvoruma čitanja i jedne kolone. Cilj je ravnomerno raspoređivanje
opterećenja.
Skup lokacija G je C-pokrivanje ako svaka kolona ima neprazan presek sa G.
Operacija čitanja bira proizvolju permutaciju πr koja se sastoji od M lokacija u proizvoljnom redu r.
πr određuje redosled komuniciranja radi postavljanja katanaca za čitanje na C-pokrivaču. Ako uspe,
garantuje se da jedna od kopija ima najsvežiju vrednost. Ako ne uspe, pokušava se slično na
narednoj vrsti dok se ne dobije katanac. Ako ne uspe ni na jednoj vrsti, operacija se prekida i
katanci se oslobađaju.
Operacija pisanja: najpre zaključava C-pokrivač koristeći protokol čitanja; zatim zaključava sve
lokacije proizvoljne kolone c u redosledu određenom permutacijom πc; da bi neka dva pisanja radila
konkurentno, svako od njih mora da zaključa po C-pokrivač i jednu kolonu, pa se mora prepoznati
konflikt.
