{"id":37335,"date":"2019-10-31T22:17:01","date_gmt":"2019-10-31T19:17:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah\/"},"modified":"2019-10-31T22:17:01","modified_gmt":"2019-10-31T19:17:01","slug":"kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","status":"publish","type":"post","link":"https:\/\/prohoster.info\/cs\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Ko\u010dka Schr\u00f6dingera bez krabice: probl\u00e9m konsensu v distribuovan\u00fdch syst\u00e9mech","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

P\u0159edstavme si situaci. V m\u00edstnosti je zam\u010deno 5 ko\u010dek a aby mohly vzbudit sv\u00e9ho majitele, mus\u00ed se nejprve dohodnout, proto\u017ee dve\u0159e mohou otev\u0159\u00edt pouze spole\u010dn\u011b. Pokud je jedna z ko\u010dek Schr\u00f6dingerova ko\u010dka a ostatn\u00ed ko\u010dky nev\u011bd\u00ed o jej\u00edm rozhodnut\u00ed, vyvst\u00e1v\u00e1 ot\u00e1zka: \u201eJak to mohou ud\u011blat?\u201c <\/p>\n

V tomto \u010dl\u00e1nku v\u00e1m jednodu\u0161e vysv\u011btl\u00edm teoretick\u00e9 aspekty sv\u011bta distribuovan\u00fdch syst\u00e9m\u016f a principy jejich fungov\u00e1n\u00ed. Tak\u00e9 povrchn\u011b prozkoum\u00e1m hlavn\u00ed my\u0161lenku, kter\u00e1 le\u017e\u00ed v z\u00e1kladech Paxos’u. <\/p>\n

\"Ko\u010dka
\n<\/a><\/noindex>
\nKdy\u017e v\u00fdvoj\u00e1\u0159i vyu\u017e\u00edvaj\u00ed cloudov\u00e9 infrastruktury, r\u016fzn\u00e9 datab\u00e1ze a pracuj\u00ed ve velk\u00fdch klastrech uzl\u016f, jsou si jisti, \u017ee data budou celistv\u00e1, zabezpe\u010den\u00e1 a v\u017edy dostupn\u00e1. Ale odkud pramen\u00ed tyto z\u00e1ruky?<\/p>\n

V podstat\u011b jsou z\u00e1ruky, kter\u00e9 m\u00e1me, z\u00e1rukami poskytovatele. Ty jsou pops\u00e1ny v dokumentaci p\u0159ibli\u017en\u011b takto: \u201eTato slu\u017eba je dostate\u010dn\u011b spolehliv\u00e1, m\u00e1 stanoven\u00fd SLA, nebojte se, v\u0161e bude fungovat rozd\u011blen\u011b, jak o\u010dek\u00e1v\u00e1te.\u201c <\/p>\n

M\u00e1me tendenci v\u011b\u0159it v to nejlep\u0161\u00ed, nebo\u0165 n\u00e1m chytr\u00e9 hlavy z velk\u00fdch spole\u010dnost\u00ed zajistily, \u017ee v\u0161e bude v po\u0159\u00e1dku. Nept\u00e1me se ot\u00e1zky: pro\u010d to vlastn\u011b m\u016f\u017ee fungovat? Existuje n\u011bjak\u00e9 form\u00e1ln\u00ed zd\u016fvodn\u011bn\u00ed spr\u00e1vnosti fungov\u00e1n\u00ed takov\u00fdch syst\u00e9m\u016f?<\/p>\n

Ned\u00e1vno jsem byl na \u0161kole distribuovan\u00fdch v\u00fdpo\u010dt\u016f<\/a><\/noindex> a byl jsem touto tematikou velmi inspirov\u00e1n. P\u0159edn\u00e1\u0161ky na \u0161kole v\u00edce p\u0159ipom\u00ednaly hodiny matematick\u00e9 anal\u00fdzy ne\u017e n\u011bco spojen\u00e9ho s po\u010d\u00edta\u010dov\u00fdmi syst\u00e9my. Ale pr\u00e1v\u011b takto byly v minulosti dok\u00e1z\u00e1ny nejd\u016fle\u017eit\u011bj\u0161\u00ed algoritmy, kter\u00e9 pou\u017e\u00edv\u00e1me ka\u017ed\u00fd den, ani\u017e bychom o tom p\u0159em\u00fd\u0161leli. <\/p>\n

V\u011bt\u0161ina modern\u00edch distribuovan\u00fdch syst\u00e9m\u016f pou\u017e\u00edv\u00e1 konsenzu\u00e1ln\u00ed algoritmus Paxos a jeho r\u016fzn\u00e9 modifikace. Nejzaj\u00edmav\u011bj\u0161\u00ed je, \u017ee od\u016fvodn\u011bn\u00ed a v podstat\u011b i samotn\u00e1 mo\u017enost existence tohoto algoritmu m\u016f\u017ee b\u00fdt dok\u00e1z\u00e1na jednodu\u0161e pomoc\u00ed pap\u00edru a pera. Na praktick\u00e9 str\u00e1nce se algoritmus aplikuje ve velk\u00fdch syst\u00e9mech, kter\u00e9 pracuj\u00ed s obrovsk\u00fdm po\u010dtem uzl\u016f v cloudu. <\/p>\n

Lehk\u00e1 ilustrace toho, o \u010dem se bude d\u00e1le mluvit: \u00faloha dvou gener\u00e1l\u016f<\/b>Poj\u010fme pro zah\u0159\u00e1t\u00ed probrat \u00falohu dvou gener\u00e1l\u016f<\/a><\/noindex>. <\/p>\n

M\u00e1me dv\u011b arm\u00e1dy \u2013 \u010dervenou a b\u00edlou. B\u00edl\u00e9 s\u00edly s\u00eddl\u00ed ve obl\u00e9han\u00e9m m\u011bst\u011b. \u010cerven\u00e9 s\u00edly veden\u00e9 gener\u00e1ly A1 a A2 jsou um\u00edst\u011bny na obou stran\u00e1ch m\u011bsta. \u00dakolem \u010derven\u00fdch je za\u00fato\u010dit na b\u00edl\u00e9 m\u011bsto a zv\u00edt\u011bzit. Nicm\u00e9n\u011b arm\u00e1da ka\u017ed\u00e9ho \u010derven\u00e9ho gener\u00e1la zvl\u00e1\u0161\u0165 je men\u0161\u00ed ne\u017e arm\u00e1da b\u00edl\u00fdch.<\/p>\n

\"Ko\u010dka
\n
\nPodm\u00ednky v\u00edt\u011bzstv\u00ed pro \u010derven\u00e9: oba gener\u00e1lov\u00e9 mus\u00ed za\u00fato\u010dit sou\u010dasn\u011b, aby m\u011bli po\u010detn\u00ed v\u00fdhodu nad b\u00edl\u00fdmi. K tomu se mus\u00ed gener\u00e1lov\u00e9 A1 a A2 dohodnout. Pokud ka\u017ed\u00fd za\u00fato\u010d\u00ed samostatn\u011b, \u010derven\u00ed prohraj\u00ed. <\/p>\n

Aby se dohodli, mohou gener\u00e1lov\u00e9 A1 a A2 pos\u00edlat posly jeden k druh\u00e9mu p\u0159es \u00fazem\u00ed b\u00edl\u00e9ho m\u011bsta. Posel m\u016f\u017ee \u00fasp\u011b\u0161n\u011b dorazit k spojeneck\u00e9mu gener\u00e1lovi nebo m\u016f\u017ee b\u00fdt zajat nep\u0159\u00edtelem. Ot\u00e1zka zn\u00ed: existuje takov\u00e1 sekvence komunikac\u00ed mezi \u010derven\u00fdmi gener\u00e1ly (sekvence pos\u00edl\u00e1n\u00ed posl\u016f od A1 k A2 a naopak od A2 k A1), p\u0159i kter\u00e9 se zaru\u010den\u011b dohodnou na \u00fatoku v hodin\u011b X. Zde se pod z\u00e1rukami rozum\u00ed, \u017ee oba gener\u00e1lov\u00e9 budou m\u00edt jednozna\u010dn\u00e9 potvrzen\u00ed, \u017ee jejich spojence (druh\u00e9ho gener\u00e1la) ur\u010dit\u011b za\u00fato\u010d\u00ed ve stanoven\u00e9m \u010dase X.<\/p>\n

P\u0159edpokl\u00e1dejme, \u017ee A1 pos\u00edl\u00e1 posla k A2 s vzkazem: \u201eZa\u00fato\u010dme dnes o p\u016flnoci!\u201c. Gener\u00e1l A1 nem\u016f\u017ee za\u00fato\u010dit bez potvrzen\u00ed od gener\u00e1la A2. Pokud posel od A1 dorazil, gener\u00e1l A2 pos\u00edl\u00e1 potvrzen\u00ed s vzkazem: \u201eAno, poj\u010fme dnes zni\u010dit b\u00edl\u00e9\u201c. Ale nyn\u00ed gener\u00e1l A2 nev\u00ed, zda jeho posel dorazil \u010di nikoliv, nem\u00e1 \u017e\u00e1dn\u00e9 z\u00e1ruky, zda bude \u00fatok sou\u010dasn\u00fd. Nyn\u00ed pot\u0159ebuje gener\u00e1l A2 znovu potvrzen\u00ed.<\/p>\n

Pokud podrobn\u011bji pop\u00ed\u0161eme jejich komunikaci, zjist\u00ed se n\u00e1sleduj\u00edc\u00ed: kolik cykl\u016f v\u00fdm\u011bny zpr\u00e1v by nebylo, neexistuje zp\u016fsob, jak zaru\u010den\u011b informovat oba gener\u00e1ly o tom, \u017ee jejich zpr\u00e1vy byly p\u0159ijaty (za p\u0159edpokladu, \u017ee jak\u00fdkoli z posel m\u016f\u017ee b\u00fdt chycen).<\/p>\n

\u00dakol dvou gener\u00e1l\u016f je skv\u011blou ilustrac\u00ed velmi jednoduch\u00e9ho distribuovan\u00e9ho syst\u00e9mu, kde jsou dva uzly s nespolehlivou komunikac\u00ed. To znamen\u00e1, \u017ee nem\u00e1me 100% z\u00e1ruku toho, \u017ee se synchronizuj\u00ed. O podobn\u00fdch probl\u00e9mech jen v \u0161ir\u0161\u00edm m\u011b\u0159\u00edtku d\u00e1le v \u010dl\u00e1nku.<\/p>\n

Zav\u00e1d\u00edme pojem distribuovan\u00fdch syst\u00e9m\u016f.<\/h2>\n

\nDistribuovan\u00fd syst\u00e9m je skupina po\u010d\u00edta\u010d\u016f (d\u00e1le je budeme naz\u00fdvat uzly), kter\u00e9 mohou vz\u00e1jemn\u011b komunikovat prost\u0159ednictv\u00edm zpr\u00e1v. Ka\u017ed\u00fd jednotliv\u00fd uzel je ur\u010ditou autonomn\u00ed entitou. Uzel m\u016f\u017ee samostatn\u011b zpracov\u00e1vat \u00fakoly, ale aby mohl interagovat s jin\u00fdmi uzly, mus\u00ed pos\u00edlat a p\u0159ij\u00edmat zpr\u00e1vy. <\/p>\n

Jak konkr\u00e9tn\u011b jsou zpr\u00e1vy realizov\u00e1ny a jak\u00e9 protokoly se pou\u017e\u00edvaj\u00ed \u2013 to n\u00e1s v tomto kontextu nezaj\u00edm\u00e1. D\u016fle\u017eit\u00e9 je, \u017ee uzly distribuovan\u00e9ho syst\u00e9mu si mohou vz\u00e1jemn\u011b vym\u011b\u0148ovat data pos\u00edl\u00e1n\u00edm zpr\u00e1v.<\/p>\n

Samotn\u00e1 definice vypad\u00e1 docela jednodu\u0161e, ale mus\u00edme br\u00e1t v \u00favahu, \u017ee distribuovan\u00fd syst\u00e9m m\u00e1 \u0159adu atribut\u016f, kter\u00e9 budou pro n\u00e1s d\u016fle\u017eit\u00e9.<\/p>\n

Atributy distribuovan\u00fdch syst\u00e9m\u016f<\/h4>\n

<\/p>\n

    \n
  1. Sou\u010dasnost<\/b> \u2013 schopnost vzniku sou\u010dasn\u00fdch nebo konkuren\u010dn\u00edch ud\u00e1lost\u00ed v syst\u00e9mu. Dob\u0159e, budeme p\u0159edpokl\u00e1dat, \u017ee ud\u00e1losti, kter\u00e9 nastaly na dvou r\u016fzn\u00fdch uzlech, jsou potenci\u00e1ln\u011b konkuren\u010dn\u00ed, dokud nem\u00e1me jasn\u00fd po\u0159\u00e1dek jejich vzniku. A obvykle ho nem\u00e1me.<\/li>\n
  2. Nedostatek glob\u00e1ln\u00edch hodin<\/b>. Nem\u00e1me jasn\u00fd po\u0159\u00e1dek ud\u00e1lost\u00ed kv\u016fli absenci glob\u00e1ln\u00edch hodin. V b\u011b\u017en\u00e9m lidsk\u00e9m sv\u011bt\u011b jsme zvykl\u00ed na to, \u017ee m\u00e1me hodiny a \u010das je absolutn\u00ed. V\u0161e se m\u011bn\u00ed, kdy\u017e jde o distribuovan\u00e9 syst\u00e9my. I u superp\u0159esn\u00fdch atomov\u00fdch hodin doch\u00e1z\u00ed k odchylk\u00e1m a mohou nastat situace, kdy nem\u016f\u017eeme \u0159\u00edct, kter\u00e1 ze dvou ud\u00e1lost\u00ed nastala d\u0159\u00edve. Proto se na \u010das tak\u00e9 spolehnout nem\u016f\u017eeme.<\/li>\n
  3. Nez\u00e1visl\u00fd selh\u00e1n\u00ed uzl\u016f syst\u00e9mu<\/b>. Existuje tak\u00e9 dal\u0161\u00ed probl\u00e9m: n\u011bco se m\u016f\u017ee pokazit jednodu\u0161e proto, \u017ee na\u0161e uzly nejsou v\u011b\u010dn\u00e9. M\u016f\u017ee selhat pevn\u00fd disk, virtu\u00e1ln\u00ed stroj v cloudu se m\u016f\u017ee restartovat, m\u016f\u017ee se p\u0159eru\u0161it s\u00ed\u0165 a zpr\u00e1vy se ztrat\u00ed. Nav\u00edc mohou nastat situace, kdy uzly funguj\u00ed, ale p\u0159itom pracuj\u00ed proti syst\u00e9mu. Posledn\u00ed t\u0159\u00edda probl\u00e9m\u016f dostala dokonce zvl\u00e1\u0161tn\u00ed n\u00e1zev: probl\u00e9m byzantsk\u00fdch gener\u00e1l\u016f<\/a><\/noindex>. Nejzn\u00e1m\u011bj\u0161\u00edm p\u0159\u00edkladem distribuovan\u00e9ho syst\u00e9mu s takov\u00fdm probl\u00e9mem je Blockchain. Ale dnes se nebudeme zab\u00fdvat touto zvl\u00e1\u0161tn\u00ed t\u0159\u00eddou probl\u00e9m\u016f. Zaj\u00edmat n\u00e1s budou situace, kdy se jednodu\u0161e jeden nebo v\u00edce uzl\u016f m\u016f\u017ee porouchat.<\/li>\n
  4. Modely komunikace (modely v\u00fdm\u011bny zpr\u00e1v) mezi uzly<\/b>. Zjistili jsme, \u017ee uzly komunikuj\u00ed prost\u0159ednictv\u00edm v\u00fdm\u011bny zpr\u00e1v. Existuj\u00ed dva zn\u00e1m\u00e9 modely v\u00fdm\u011bny zpr\u00e1v: synchronn\u00ed a asynchronn\u00ed.<\/li>\n<\/ol>\n

    <\/p>\n

    Modely komunikace mezi uzly v distribuovan\u00fdch syst\u00e9mech<\/h4>\n

    \nSynchronn\u00ed model<\/b> \u2013 p\u0159esn\u011b v\u00edme, \u017ee existuje kone\u010dn\u00e1 zn\u00e1m\u00e1 doba, za kterou zpr\u00e1va zaru\u010den\u011b doraz\u00ed z jednoho uzlu na druh\u00fd. Pokud tato doba uplyne a zpr\u00e1va nep\u0159ijde, m\u016f\u017eeme s jistotou \u0159\u00edci, \u017ee uzel selhal. V takov\u00e9m modelu m\u00e1me p\u0159edv\u00eddatelnou dobu \u010dek\u00e1n\u00ed. <\/p>\n

    Asynchronn\u00ed model<\/b> \u2013 v asynchronn\u00edch modelech p\u0159edpokl\u00e1d\u00e1me, \u017ee doba \u010dek\u00e1n\u00ed je kone\u010dn\u00e1, ale neexistuje takov\u00e1 doba, po kter\u00e9 bychom mohli garantovat, \u017ee uzel selhal. Tzn. doba \u010dek\u00e1n\u00ed na zpr\u00e1vu z uzlu m\u016f\u017ee b\u00fdt jak dlouh\u00e1, jak jen pot\u0159eba. Toto je d\u016fle\u017eit\u00e9 ur\u010den\u00ed, a o tom si promluv\u00edme d\u00e1le. <\/p>\n

    Pojem konsensu v distribuovan\u00fdch syst\u00e9mech<\/h2>\n

    \nNe\u017e form\u00e1ln\u011b definujeme pojem konsensu, pod\u00edvejme se na p\u0159\u00edklad situace, kdy ho pot\u0159ebujeme, a to konkr\u00e9tn\u011b \u2013 Replikace stavov\u00e9ho stroje<\/b>. <\/p>\n

    M\u00e1me n\u011bjak\u00fd distribuovan\u00fd log. R\u00e1di bychom, aby byl konzistentn\u00ed a obsahoval identick\u00e1 data na v\u0161ech uzlech distribuovan\u00e9ho syst\u00e9mu. Kdy\u017e n\u011bkter\u00fd z uzl\u016f zjist\u00ed novou hodnotu, kterou m\u00e1 zapsat do logu, jeho \u00fakolem je navrhnout tuto hodnotu v\u0161em ostatn\u00edm uzl\u016fm, aby se log aktualizoval na v\u0161ech uzlech a syst\u00e9m p\u0159e\u0161el do nov\u00e9ho konzistentn\u00edho stavu. P\u0159i tom je d\u016fle\u017eit\u00e9, aby se uzly dohodly: v\u0161echny uzly souhlasily, \u017ee navr\u017een\u00e1 nov\u00e1 hodnota je spr\u00e1vn\u00e1, v\u0161echny uzly tuto hodnotu p\u0159ijaly, a pouze v tomto p\u0159\u00edpad\u011b mohou v\u0161echny zapsat do logu novou hodnotu. <\/p>\n

    Jin\u00fdmi slovy: \u017e\u00e1dn\u00fd z uzl\u016f neprotestoval, \u017ee by m\u011bl aktu\u00e1ln\u011bj\u0161\u00ed informace a \u017ee navrhovan\u00e1 hodnota je nespr\u00e1vn\u00e1. Dohoda mezi uzly a souhlas o jedin\u00e9 spr\u00e1vn\u011b p\u0159ijat\u00e9 hodnot\u011b je konsensus v distribuovan\u00e9m syst\u00e9mu. D\u00e1le se budeme bavit o algoritmech, kter\u00e9 umo\u017e\u0148uj\u00ed distribuovan\u00e9mu syst\u00e9mu zaru\u010den\u011b dosahovat konsensu.
    \n\"Ko\u010dka
    \nForm\u00e1ln\u011b m\u016f\u017eeme definovat algoritmus dosa\u017een\u00ed konsensu (nebo jednodu\u0161e algoritmus konsensu) jako funkci, kter\u00e1 p\u0159en\u00e1\u0161\u00ed distribuovan\u00fd syst\u00e9m ze stavu A do stavu B. Tento stav je p\u0159itom akceptov\u00e1n v\u0161emi uzly a v\u0161echny uzly jej mohou potvrdit. Jak se ukazuje, \u00fakol nen\u00ed tak trivi\u00e1ln\u00ed, jak se na prvn\u00ed pohled zd\u00e1.<\/p>\n

    Vlastnosti algoritmu konsensu<\/h4>\n

    \nAlgoritmus konsensu mus\u00ed m\u00edt t\u0159i vlastnosti, aby syst\u00e9m mohl pokra\u010dovat v existenci a m\u011bl n\u011bjak\u00fd pokrok p\u0159i p\u0159echodu z jednoho stavu do druh\u00e9ho:<\/p>\n

      \n
    1. Dohoda <\/b> \u2013 v\u0161echny spr\u00e1vn\u011b funguj\u00edc\u00ed uzly mus\u00ed p\u0159ijmout stejnou hodnotu (v \u010dl\u00e1nc\u00edch se tato vlastnost tak\u00e9 naz\u00fdv\u00e1 vlastnost ochrany). V\u0161echny uzly, kter\u00e9 moment\u00e1ln\u011b funguj\u00ed (nezhroubily se a neztratily spojen\u00ed s ostatn\u00edmi), by m\u011bly dosp\u011bt k dohod\u011b a p\u0159ijmout n\u011bjakou kone\u010dnou spole\u010dnou hodnotu.\n

      Je d\u016fle\u017eit\u00e9 ch\u00e1pat, \u017ee uzly v n\u00e1mi zva\u017eovan\u00e9m distribuovan\u00e9m syst\u00e9mu cht\u011bj\u00ed dos\u00e1hnout dohody. O tom mluv\u00edme o syst\u00e9mech, kde m\u016f\u017ee n\u011bco selhat (nap\u0159\u00edklad m\u016f\u017ee selhat n\u011bjak\u00fd uzel), ale v tomto syst\u00e9mu jist\u011b nejsou uzly, kter\u00e9 by \u00famysln\u011b pracovaly proti jin\u00fdm (\u00fakol byzantsk\u00fdch gener\u00e1l\u016f). D\u00edky t\u00e9to vlastnosti z\u016fst\u00e1v\u00e1 syst\u00e9m konzistentn\u00ed.<\/li>\n

    2. Integrita <\/b> \u2013 pokud v\u0161echny spr\u00e1vn\u011b funguj\u00edc\u00ed uzly nab\u00edzej\u00ed stejnou hodnotu v<\/b>, pak ka\u017ed\u00e9 spr\u00e1vn\u011b funguj\u00edc\u00ed uzel mus\u00ed tuto hodnotu p\u0159ijmout v<\/b>. <\/li>\n
    3. Ukon\u010den\u00ed <\/b>\u2013 v\u0161echny spr\u00e1vn\u011b funguj\u00edc\u00ed uzly nakonec p\u0159ijmou n\u011bjakou hodnotu (vlastnost \u017eivotnosti), co\u017e umo\u017e\u0148uje algoritmu m\u00edt pokrok v syst\u00e9mu. Ka\u017ed\u00fd jednotliv\u00fd spr\u00e1vn\u011b funguj\u00edc\u00ed uzel by m\u011bl d\u0159\u00edve \u010di pozd\u011bji p\u0159ijmout kone\u010dnou hodnotu a potvrdit to: \"Pro m\u011b je tato hodnota pravdiv\u00e1, souhlas\u00edm se v\u0161emi v syst\u00e9mu.\"<\/li>\n<\/ol>\n

      <\/p>\n

      P\u0159\u00edklad fungov\u00e1n\u00ed algoritmu konsensu<\/h4>\n

      \nZat\u00edmco vlastnosti algoritmu mohou b\u00fdt m\u00e9n\u011b z\u0159ejm\u00e9. Proto to ilustrujeme na p\u0159\u00edkladu, jak\u00e9 f\u00e1ze proch\u00e1z\u00ed nejjednodu\u0161\u0161\u00ed algoritmus konsensu v syst\u00e9mu se synchronn\u00edm modelem v\u00fdm\u011bny zpr\u00e1v, kde v\u0161echny uzly funguj\u00ed spr\u00e1vn\u011b, zpr\u00e1vy se neztr\u00e1c\u00ed a nic se nerozbije (skute\u010dn\u011b se tohle st\u00e1v\u00e1?).<\/p>\n

        \n
      1. V\u0161echno za\u010d\u00edn\u00e1 n\u00e1vrhem ruky a srdce (Propose). P\u0159edpokl\u00e1dejme, \u017ee se k uzlu s n\u00e1zvem \u201eUzel 1\u201c p\u0159ipojil klient a zah\u00e1jil transakci, p\u0159i\u010dem\u017e uzlu p\u0159edal novou hodnotu \u2013 O. Od t\u00e9to chv\u00edle budeme \u201eUzel 1\u201c naz\u00fdvat proposer<\/b>. Jako proposer nyn\u00ed \u201eUzel 1\u201c mus\u00ed informovat cel\u00fd syst\u00e9m, \u017ee m\u00e1 \u010derstv\u00e9 \u00fadaje, a rozes\u00edl\u00e1 v\u0161em ostatn\u00edm uzl\u016fm zpr\u00e1vy: \u201ePod\u00edvejte se! P\u0159i\u0161la mi hodnota \u201eO\u201c, a chci ji zapsat! Pros\u00edm, potvr\u010fte, \u017ee tak\u00e9 zap\u00ed\u0161ete \u201eO\u201c do sv\u00e9ho logu.\u201c\n

        \"Ko\u010dka<\/li>\n

      2. Dal\u0161\u00ed f\u00e1ze \u2013 hlasov\u00e1n\u00ed o navr\u017een\u00e9 hodnot\u011b (Voting). K \u010demu je to dobr\u00e9? M\u016f\u017ee se st\u00e1t, \u017ee ostatn\u00edm uzl\u016fm p\u0159i\u0161ly aktu\u00e1ln\u011bj\u0161\u00ed informace a maj\u00ed \u00fadaje k t\u00e9to same transakci.\n

        \"Ko\u010dka
        \n
        \nKdy\u017e uzel \u201eUzel 1\u201c ode\u0161le sv\u016fj n\u00e1vrh, ostatn\u00ed uzly zkontroluj\u00ed ve sv\u00fdch log\u00e1ch \u00fadaje o t\u00e9to ud\u00e1losti. Pokud nejsou \u017e\u00e1dn\u00e9 rozporu, uzly vyhl\u00e1s\u00ed: \u201eAno, nem\u00e1m \u017e\u00e1dn\u00e9 jin\u00e9 \u00fadaje k t\u00e9to ud\u00e1losti. Hodnota \u201eO\u201c je nejnov\u011bj\u0161\u00ed informace, kterou jsme z\u00edskali.\u201c <\/p>\n

        V opa\u010dn\u00e9m p\u0159\u00edpad\u011b mohou uzly odpov\u011bd\u011bt \u201eUzlu 1\u201c: \u201ePoslouchej! M\u00e1m aktu\u00e1ln\u011bj\u0161\u00ed \u00fadaje o t\u00e9to transakci. Ne \u201eO\u201c, ale n\u011bco lep\u0161\u00edho.\u201c<\/p>\n

        Ve f\u00e1zi hlasov\u00e1n\u00ed uzly dosp\u011bj\u00ed k rozhodnut\u00ed: bu\u010f v\u0161ichni p\u0159ij\u00edmaj\u00ed jednu hodnotu, nebo n\u011bkdo z nich hlasuje proti a nazna\u010d\u00ed, \u017ee m\u00e1 aktu\u00e1ln\u011bj\u0161\u00ed \u00fadaje. <\/li>\n

      3. Pokud kolo hlasov\u00e1n\u00ed prob\u011bhlo \u00fasp\u011b\u0161n\u011b a v\u0161ichni byli \u201epro\u201c, syst\u00e9m p\u0159ech\u00e1z\u00ed do nov\u00e9 f\u00e1ze \u2013 p\u0159ijet\u00ed hodnoty (Accept). \u201eUzel 1\u201c shrom\u00e1\u017ed\u00ed v\u0161echny odpov\u011bdi ostatn\u00edch uzl\u016f a ozn\u00e1m\u00ed: \u201eV\u0161ichni souhlasili s hodnotou \u201eO\u201c! Nyn\u00ed ofici\u00e1ln\u011b prohla\u0161uji, \u017ee \u201eO\u201c je na\u0161e nov\u00e1 hodnota, jednotn\u00e1 pro v\u0161echny! Zapi\u0161te si to do sv\u00e9 kn\u00ed\u017eky, nezapome\u0148te. Zapi\u0161te to do sv\u00e9ho logu!\u201c\n

        \"Ko\u010dka<\/li>\n

      4. Ostatn\u00ed uzly po\u0161lou potvrzen\u00ed (Accepted), \u017ee si zapsali hodnotu \u201eO\u201c, b\u011bhem t\u00e9to doby nep\u0159i\u0161lo nic nov\u00e9ho (jak\u00e9si dvouf\u00e1zov\u00e9 potvrzen\u00ed). Po t\u00e9to v\u00fdznamn\u00e9 ud\u00e1losti pova\u017eujeme, \u017ee distribuovan\u00e1 transakce byla \u00fasp\u011b\u0161n\u011b dokon\u010dena.
        \n \"Ko\u010dka <\/li>\n<\/ol>\n

        \nTud\u00ed\u017e konsenzu\u00e1ln\u00ed algoritmus v jednoduch\u00e9m p\u0159\u00edpad\u011b sest\u00e1v\u00e1 ze \u010dty\u0159 krok\u016f: propose, hlasov\u00e1n\u00ed (voting), p\u0159ijet\u00ed (accept), potvrzen\u00ed p\u0159ijet\u00ed (accepted).<\/p>\n

        Pokud b\u011bhem n\u011bjak\u00e9ho kroku nedok\u00e1\u017eeme dos\u00e1hnout shody, algoritmus se spou\u0161t\u00ed znovu, p\u0159i\u010dem\u017e se zohled\u0148uje informace, kterou poskytnou uzly, kter\u00e9 odm\u00edtly potvrdit navr\u017eenou hodnotu.<\/p>\n

        Konsensu\u00e1ln\u00ed algoritmus v asynchronn\u00edm syst\u00e9mu<\/h2>\n

        \nDo t\u00e9to doby to bylo hladk\u00e9, proto\u017ee jsme hovo\u0159ili o synchronn\u00edm modelu v\u00fdm\u011bny zpr\u00e1v. Ale jak v\u00edme, v sou\u010dasn\u00e9m sv\u011bt\u011b jsme v\u0161ichni zvykl\u00ed na asynchronn\u00ed proveden\u00ed. Jak v\u0161ak funguje analogick\u00fd algoritmus v syst\u00e9mu s asynchronn\u00edm modelem v\u00fdm\u011bny zpr\u00e1v, kde pova\u017eujeme, \u017ee doba \u010dek\u00e1n\u00ed na odpov\u011b\u010f uzlu m\u016f\u017ee b\u00fdt libovoln\u011b dlouh\u00e1 (mimochodem, v\u00fdpadek uzlu lze tak\u00e9 pova\u017eovat za p\u0159\u00edklad situace, kdy uzel m\u016f\u017ee odpov\u00eddat libovoln\u011b dlouho). <\/p>\n

        Nyn\u00ed, kdy\u017e v\u00edme, jak v z\u00e1sad\u011b funguje konsensu\u00e1ln\u00ed algoritmus, ot\u00e1zka pro ty zv\u00eddav\u00e9 \u010dten\u00e1\u0159e, kte\u0159\u00ed se dostali na toto m\u00edsto: kolik uzl\u016f v syst\u00e9mu z N uzl\u016f s asynchronn\u00edm modelem zpr\u00e1v m\u016f\u017ee selhat, aby syst\u00e9m st\u00e1le mohl dos\u00e1hnout konsensu?<\/p><\/blockquote>\n

        \nSpr\u00e1vn\u00e1 odpov\u011b\u010f a od\u016fvodn\u011bn\u00ed je za spoilerem.<\/b>Spr\u00e1vn\u00e1 odpov\u011b\u010f: 0<\/b>. Pokud jak\u00fdkoli uzel v asynchronn\u00edm syst\u00e9mu sel\u017ee, syst\u00e9m nem\u016f\u017ee dos\u00e1hnout konsensu. Toto tvrzen\u00ed bylo prok\u00e1z\u00e1no v zn\u00e1m\u00e9 teorem\u011b FLP (1985, Fischer, Lynch, Paterson, odkaz na origin\u00e1l na konci \u010dl\u00e1nku): \u201eNemo\u017enost dosa\u017een\u00ed distribuovan\u00e9ho konsensu p\u0159i selh\u00e1n\u00ed alespo\u0148 jednoho uzlu\u201c.
        \n\"Ko\u010dka
        \nChlapci, m\u00e1me tedy probl\u00e9m, zvykl\u00ed jsme na to, \u017ee v\u0161e je asynchronn\u00ed. A te\u010f toto. Jak d\u00e1l \u017e\u00edt? <\/p>\n

        Pr\u00e1v\u011b jsme mluvili o teorii, o matematice. Co znamen\u00e1 \u201ekonsensus nem\u016f\u017ee b\u00fdt dosa\u017een\u201c, kdy\u017e to p\u0159evedeme z matematick\u00e9ho jazyka do na\u0161eho \u2013 in\u017een\u00fdrsk\u00e9ho? Znamen\u00e1 to, \u017ee \u201ene v\u017edy m\u016f\u017ee b\u00fdt dosa\u017een\u201c, tj. existuje p\u0159\u00edpad, kdy konsensus nen\u00ed dosa\u017eiteln\u00fd. A jak\u00fd je to p\u0159\u00edpad? <\/p>\n

        To je p\u0159esn\u011b poru\u0161en\u00ed vlastnosti liveness, popsan\u00e9 v\u00fd\u0161e. Nem\u00e1me obecn\u00fd souhlas a syst\u00e9m nem\u016f\u017ee m\u00edt pokrok (nem\u016f\u017ee skon\u010dit za kone\u010dn\u00fd \u010das), kdy\u017e nem\u00e1me odpov\u011b\u010f od v\u0161ech uzl\u016f. Proto\u017ee v asynchronn\u00edm syst\u00e9mu nem\u00e1me p\u0159edv\u00eddatelnou dobu odpov\u011bdi a nem\u016f\u017eeme v\u011bd\u011bt, zda uzel selhal nebo jen dlouho odpov\u00edd\u00e1.<\/p>\n

        Ale v praxi m\u016f\u017eeme naj\u00edt \u0159e\u0161en\u00ed. Nech\u0165 n\u00e1\u0161 algoritmus m\u016f\u017ee fungovat dlouho v p\u0159\u00edpad\u011b selh\u00e1n\u00ed (potenci\u00e1ln\u011b m\u016f\u017ee fungovat nekone\u010dn\u011b). Ale v v\u011bt\u0161in\u011b situac\u00ed, kdy v\u011bt\u0161ina uzl\u016f spr\u00e1vn\u011b funguje, budeme m\u00edt pokrok v syst\u00e9mu. <\/p>\n

        V praxi se setk\u00e1v\u00e1me s \u010d\u00e1ste\u010dn\u011b synchronn\u00edmi komunika\u010dn\u00edmi modely. \u010c\u00e1ste\u010dn\u00e1 synchronnost se ch\u00e1pe takto: obecn\u011b m\u00e1me asynchronn\u00ed model, ale form\u00e1ln\u011b se zav\u00e1d\u00ed ur\u010dit\u00fd pojem \u201eglobal stabilization time\u201c jako n\u011bjak\u00fd \u010dasov\u00fd okam\u017eik. <\/p>\n

        Tento \u010dasov\u00fd okam\u017eik nemus\u00ed nastat neomezen\u011b dlouho, ale jednou mus\u00ed nastat. Zazvon\u00ed virtu\u00e1ln\u00ed bud\u00edk a od tohoto okam\u017eiku m\u016f\u017eeme p\u0159edpov\u011bd\u011bt \u010dasovou prodlevu, za kterou zpr\u00e1vy doraz\u00ed. Od tohoto momentu se syst\u00e9m z asynchronn\u00edho st\u00e1v\u00e1 synchronn\u00edm. V praxi se skute\u010dn\u011b zab\u00fdv\u00e1me pr\u00e1v\u011b takov\u00fdmi syst\u00e9my. <\/p>\n

        Algoritmus Paxos \u0159e\u0161\u00ed probl\u00e9my konsensu.<\/h2>\n

        \nPaxos <\/a><\/noindex> \u2013 je to rodina algoritm\u016f, kter\u00e9 \u0159e\u0161\u00ed probl\u00e9m konsensu pro \u010d\u00e1ste\u010dn\u011b synchronn\u00ed syst\u00e9my, za p\u0159edpokladu, \u017ee n\u011bkter\u00e9 uzly mohou selhat. Autorem Paxos’u je Leslie Lamport<\/a><\/noindex>. Ten navrhl form\u00e1ln\u00ed d\u016fkaz existence a spr\u00e1vnosti algoritmu v roce 1989. <\/p>\n

        Ale d\u016fkaz se uk\u00e1zal b\u00fdt zdaleka netrivi\u00e1ln\u00ed. Prvn\u00ed publikace byla vyd\u00e1na a\u017e v roce 1998 (33 stran) a obsahovala popis algoritmu. Jak se uk\u00e1zalo, byla velmi slo\u017eit\u00e1 na pochopen\u00ed a v roce 2001 bylo publikov\u00e1no vysv\u011btlen\u00ed k \u010dl\u00e1nku, kter\u00e9 zabralo 14 stran. Objem publikac\u00ed je uveden, aby uk\u00e1zal, \u017ee probl\u00e9m konsensu nen\u00ed v\u016fbec jednoduch\u00fd, a za takov\u00fdmi algoritmy stoj\u00ed obrovsk\u00e1 pr\u00e1ce t\u011bch nejchyt\u0159ej\u0161\u00edch lid\u00ed.<\/p>\n

        Zaj\u00edmav\u00e9 je, \u017ee s\u00e1m Leslie Lamport ve sv\u00e9 p\u0159edn\u00e1\u0161ce poznamenal, \u017ee ve druh\u00e9m \u010dl\u00e1nku-vysv\u011btlen\u00ed je jedno tvrzen\u00ed, jedna v\u011bta (neup\u0159esnil kterou), kter\u00e1 m\u016f\u017ee b\u00fdt interpretov\u00e1na r\u016fzn\u011b. A kv\u016fli tomu velk\u00e9 mno\u017estv\u00ed sou\u010dasn\u00fdch implementac\u00ed Paxosu nefunguje zcela spr\u00e1vn\u011b. <\/p><\/blockquote>\n

        \nPodrobn\u00e1 anal\u00fdza fungov\u00e1n\u00ed Paxos’u by mohla zaplnit v\u00edce ne\u017e jeden \u010dl\u00e1nek, a proto se pokus\u00edm velmi stru\u010dn\u011b p\u0159edat z\u00e1kladn\u00ed my\u0161lenku algoritmu. V odkaze na konci m\u00e9ho \u010dl\u00e1nku najdete materi\u00e1ly pro dal\u0161\u00ed prohlouben\u00ed t\u00e9to t\u00e9matiky.<\/p>\n

        Role v Paxosu<\/h4>\n

        \nV algoritmu Paxos existuje pojem rol\u00ed. Pod\u00edvejme se na t\u0159i z\u00e1kladn\u00ed (existuj\u00ed modifikace s dal\u0161\u00edmi rolemi):<\/p>\n

          \n
        1. Proposers (tak\u00e9 se mohou pou\u017e\u00edvat term\u00edny: l\u00edd\u0159i nebo koordin\u00e1to\u0159i)<\/b>To jsou lid\u00e9, kte\u0159\u00ed se dozv\u011bd\u00ed o n\u011bjak\u00e9m nov\u00e9m hodnot\u011b od u\u017eivatele a p\u0159ij\u00edmaj\u00ed roli l\u00eddra. Jejich \u00fakolem je zah\u00e1jit kolo navrhov\u00e1n\u00ed nov\u00e9 hodnoty a koordinovat dal\u0161\u00ed kroky uzl\u016f. Paxos nav\u00edc umo\u017e\u0148uje m\u00edt v ur\u010dit\u00fdch situac\u00edch n\u011bkolik l\u00eddr\u016f.<\/li>\n
        2. P\u0159ij\u00edma\u010di (volitel\u00e9)<\/b>To jsou uzly, kter\u00e9 hlasuj\u00ed pro p\u0159ijet\u00ed nebo odm\u00edtnut\u00ed ur\u010dit\u00e9 hodnoty. Jejich rol\u00ed je velmi d\u016fle\u017eit\u00e1, proto\u017ee pr\u00e1v\u011b od nich z\u00e1vis\u00ed rozhodnut\u00ed: do jak\u00e9ho stavu se syst\u00e9m po dan\u00e9 f\u00e1zi algoritmu konsensu dostane (nebo nedostane).<\/li>\n
        3. U\u010d\u00edc\u00ed se uzly<\/b>To jsou uzly, kter\u00e9 pouze p\u0159ij\u00edmaj\u00ed a zapisuj\u00ed novou p\u0159ijatou hodnotu, kdy\u017e dojde ke zm\u011bn\u011b ve stavu syst\u00e9mu. Nep\u0159ij\u00edmaj\u00ed rozhodnut\u00ed, pouze z\u00edsk\u00e1vaj\u00ed data a mohou je p\u0159edat koncov\u00e9mu u\u017eivateli. <\/li>\n<\/ol>\n

          \nJeden uzel m\u016f\u017ee v r\u016fzn\u00fdch situac\u00edch vykon\u00e1vat v\u00edce rol\u00ed. <\/p>\n

          Pojem kv\u00f3ra<\/h4>\n

          \nP\u0159edpokl\u00e1d\u00e1me, \u017ee m\u00e1me syst\u00e9m slo\u017een\u00fd z N<\/b> uzl\u016f. A z nich maxim\u00e1ln\u011b F<\/b> uzl\u016f m\u016f\u017ee selhat. Pokud F uzl\u016f sel\u017ee, znamen\u00e1 to, \u017ee v na\u0161em klastru by m\u011blo b\u00fdt alespo\u0148 2F + 1<\/b> uzl\u016f acceptor’\u016f. <\/p>\n

          To je pot\u0159eba, aby jsme v\u017edy, i v nejhor\u0161\u00edm p\u0159\u00edpad\u011b, m\u011bli v\u011bt\u0161inu 'dobr\u00fdch' spr\u00e1vn\u011b funguj\u00edc\u00edch uzl\u016f. To znamen\u00e1, \u017ee F + 1<\/b> 'dobr\u00fdch' uzl\u016f, kter\u00e9 souhlasily, a fin\u00e1ln\u00ed hodnota bude p\u0159ijata. Jinak m\u016f\u017ee nastat situace, kdy r\u016fzn\u00e9 m\u00edstn\u00ed skupiny p\u0159ijmou r\u016fzn\u00e9 hodnoty a nedok\u00e1\u017eou se mezi sebou dohodnout. Proto pot\u0159ebujeme absolutn\u00ed v\u011bt\u0161inu, abychom vyhr\u00e1li hlasov\u00e1n\u00ed.<\/p>\n

          Obecn\u00e1 my\u0161lenka fungov\u00e1n\u00ed algoritmu konsensu Paxos<\/h4>\n

          \nAlgoritmus Paxos p\u0159edpokl\u00e1d\u00e1 dv\u011b velk\u00e9 f\u00e1ze, kter\u00e9 se zase d\u011bl\u00ed na dva kroky ka\u017ed\u00e1:<\/p>\n

            \n
          1. F\u00e1ze 1a: P\u0159\u00edprava<\/b>. V p\u0159\u00edpravn\u00e9 f\u00e1zi l\u00eddr (proposer) informuje v\u0161echny uzly: \u201eZa\u010d\u00edn\u00e1me nov\u00e9 kolo hlasov\u00e1n\u00ed. M\u00e1me nov\u00e9 kolo. \u010c\u00edslo tohoto kola je n. Nyn\u00ed za\u010dneme hlasovat.\u201c Zat\u00edm jen oznamuje za\u010d\u00e1tek nov\u00e9ho cyklu, ale nezve\u0159ej\u0148uje novou hodnotu. \u00dakolem t\u00e9to f\u00e1ze je iniciovat nov\u00e9 kolo a ozn\u00e1mit v\u0161em jeho unik\u00e1tn\u00ed \u010d\u00edslo. \u010c\u00edslo kola je d\u016fle\u017eit\u00e9, mus\u00ed b\u00fdt v\u011bt\u0161\u00ed ne\u017e v\u0161echna p\u0159edchoz\u00ed \u010d\u00edsla hlasov\u00e1n\u00ed od v\u0161ech p\u0159edchoz\u00edch l\u00eddr\u016f. Pr\u00e1v\u011b d\u00edky \u010d\u00edslu kola ostatn\u00ed uzly v syst\u00e9mu pochop\u00ed, jak aktu\u00e1ln\u00ed jsou data u l\u00eddra. Je pravd\u011bpodobn\u00e9, \u017ee ostatn\u00ed uzly ji\u017e maj\u00ed v\u00fdsledky hlasov\u00e1n\u00ed z mnohem pozd\u011bj\u0161\u00edch kol a jednodu\u0161e \u0159eknou l\u00eddrovi, \u017ee zaspal.<\/li>\n
          2. F\u00e1ze 1b: Slib<\/b>. Kdy\u017e uzly-acceptor’y obdr\u017e\u00ed \u010d\u00edslo nov\u00e9 f\u00e1ze hlasov\u00e1n\u00ed, m\u016f\u017ee nastat dva v\u00fdsledky: \n