{"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\/et\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Schr\u00f6dinger's Cat Without a Box: The Consensus Problem in Distributed Systems","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Kujutage ette. Toas on kinni 5 kassi ja et minna \u00e4ratama peremeest, peavad nad k\u00f5ik koos omavahel kokku leppima, sest nad saavad ukse avada ainult siis, kui k\u00f5ik viis koondavad oma j\u00f5ud selle peale. Kui \u00fcks kass on Schr\u00f6dingeri kass ja teised kassid ei tea tema otsusest, tekib k\u00fcsimus: \"Kuidas nad seda teha saavad?\" <\/p>\n

Selles artiklis r\u00e4\u00e4gin ma lihtsate s\u00f5nadega jaotatud s\u00fcsteemide teoreetilisest poolest ning nende toimimise printsiipidest. Samuti k\u00e4sitlen ma pinnapealselt Paxosi p\u00f5hjalikku ideed. <\/p>\n

\"Schr\u00f6dinger's
\n<\/a><\/noindex>
\nKui arendajad kasutavad pilveteenuseid, erinevaid andmebaase ja t\u00f6\u00f6tavad suure arvu s\u00f5lmedega klastris, usuvad nad, et andmed on kogu aeg terved, ohutud ja alati kergesti k\u00e4ttesaadavad. Aga kust tulenevad need garantiid?<\/p>\n

Koheselt on meil olemas olemasolevad garantiid, ning need on tarnija garantii. Need on dokumenteeritud enam-v\u00e4hem j\u00e4rgmiselt: \"See teenus on piisavalt usaldusv\u00e4\u00e4rne, tal on m\u00e4\u00e4ratud SLA, \u00e4rge muretsege, k\u00f5ik t\u00f6\u00f6tab jaotatult nagu te ootate.\" <\/p>\n

Me kalduvad uskuma parimat, kuna suured ettev\u00f5tted on meid veennud, et k\u00f5ik on h\u00e4sti. Me ei k\u00fcsige endalt: miks see \u00fcldse v\u00f5iks toimida? Kas on olemas mingid formaalsed p\u00f5hjendused selliste s\u00fcsteemide korrektsuse jaoks?<\/p>\n

Hiljuti k\u00e4isin jaotatud arvutuste koolis<\/a><\/noindex> ja see inspireeris mind v\u00e4ga. Koolis toimunud loengud meenutasid pigem matemaatilise anal\u00fc\u00fcsi tunde kui midagi seoses arvutite s\u00fcsteemidega. Kuid just nii on ajalooliselt t\u00f5estatud olulisi algoritme, mida me kasutame igap\u00e4evaselt, ja ei kahtle selles. <\/p>\n

Enamikus kaasaegsetes jaotatud s\u00fcsteemides on kasutusel Paxosi konsensuse algoritm ja selle erinevad modifikatsioonid. Mis on k\u00f5ige huvitavam, on see, et algoritmi olemasolu ja selle \u00f5igustamine on v\u00f5imalik t\u00f5estada lihtsalt pliiatsi ja paberiga. Samuti rakendatakse algoritmi praktikas suurtes s\u00fcsteemides, mis t\u00f6\u00f6tavad tohutu arvu s\u00f5lmedega pilves. <\/p>\n

Kerge illustratsioon sellest, millest edaspidi r\u00e4\u00e4gitakse: kahe kindraliga \u00fclesanne.<\/b>Alustame soojenduseks kahe kindraliga \u00fclesande lahendamisega.<\/a><\/noindex>. <\/p>\n

Meil on kaks armeed \u2013 punased ja valged. Valged v\u00e4ed asuvad piiratavas linnas. Punased v\u00e4ed, mida juhivad kindralid A1 ja A2, on paigutatud linna m\u00f5lemale poole. Punaste eesm\u00e4rk on r\u00fcnnata valget linna ja v\u00f5ita. Kuid iga punase kindrali v\u00e4gi on eraldi v\u00e4iksem valgete omast.<\/p>\n

\"Schr\u00f6dinger's
\n
\nPunaste v\u00f5idu tingimused: m\u00f5lemad kindralid peavad r\u00fcndama samaaegselt, et omada \u00fclekaalu valgete \u00fcle. Selleks peavad kindralid A1 ja A2 omavahel kokku leppima. Kui iga\u00fcks r\u00fcndab eraldi, kaotavad punased. <\/p>\n

Kokkuleppimiseks saavad kindralid A1 ja A2 saata s\u00f5numitoojaid valge linna territooriumi kaudu. S\u00f5numitooja v\u00f5ib edukalt j\u00f5uda liitlase kindrali juurde v\u00f5i v\u00f5ib protivnik teda tabada. K\u00fcsimus: kas on selline suhtlemise j\u00e4rjestus punaste kindralite vahel (s\u00f5numitoojate saatmise j\u00e4rjestus A1-st A2-sse ja A2-st A1-sse), millega nad garanteeritult kokku leppida r\u00fcnnaku ajaks X. Siin m\u00f5istetakse garantii all, et m\u00f5lemad kindralid saavad \u00fcheselt kinnitust, et liitlane (teine kindral) r\u00fcndab kindlalt m\u00e4\u00e4ratud ajal X.<\/p>\n

Oletame, et A1 saadab A2-le s\u00f5numitooja, kes toob s\u00f5numi: \"R\u00fcndame t\u00e4na kesk\u00f6\u00f6l!\". Kindral A1 ei saa r\u00fcnnata ilma kinnituse saanud A2-lt. Kui A1 s\u00f5numitooja j\u00f5uab kohale, saadab kindral A2 kinnituse s\u00f5numiga: \"Jah, r\u00fcndame t\u00e4na valgeid\". Kuid n\u00fc\u00fcd ei tea kindral A2, kas tema vasta s\u00f5numitooja j\u00f5udis kohale v\u00f5i mitte, tal ei ole garanteeritud r\u00fcnnaku samaaegsust. N\u00fc\u00fcd peab \u00fcldiselt A2-le uuesti kinnitus olema.<\/p>\n

Kui anal\u00fc\u00fcsida nende suhtlust edasi, selgub midagi sellist: \u00fcksk\u00f5ik, kui palju s\u00f5numivahetus ts\u00fckleid toimub, ei ole viisi, kuidas kummagi kindrali s\u00f5numeid garanteeritult k\u00e4tte toimetada (eeldusel, et \u00fcksk\u00f5ik milline s\u00f5numitooja v\u00f5ib olla tabatud).<\/p>\n

Kahe kindrali \u00fclesanne on suurep\u00e4rane illustreerimine v\u00e4ga lihtsast jaotatud s\u00fcsteemist, kus on kaks s\u00f5lme ebausaldusv\u00e4\u00e4rse suhtlemisega. See t\u00e4hendab, et meil ei ole 100% garantiid, et nad s\u00fcnkroniseeruvad. Sellistelt probleemidelt r\u00e4\u00e4gitakse t\u00e4iendavalt artikli suuremal hulgal.<\/p>\n

Sissejuhatus jaotatud s\u00fcsteemide m\u00f5istesse.<\/h2>\n

\nJagatud s\u00fcsteem on arvutite r\u00fchm (edaspidi nimetame neid s\u00f5lmedeks), mis saavad vahetada s\u00f5numeid. Iga eraldi s\u00f5lm on autonoomne entiteet. S\u00f5lm suudab iseseisvalt t\u00f6\u00f6\u00fclesandeid t\u00e4ita, kuid teiste s\u00f5lmedega suhtlemiseks peab ta saatma ja vastuv\u00f5tma s\u00f5numeid. <\/p>\n

Kuidas s\u00f5numid t\u00e4pselt teostatakse, milliseid protokolle kasutatakse \u2013 see meid antud kontekstis ei huvita. Oluline on, et jagatud s\u00fcsteemi s\u00f5lmed saavad vahetada andmeid, saates teineteisele s\u00f5numeid.<\/p>\n

Isegi kui m\u00e4\u00e4ratlemine tundub lihtne, tuleb arvestada, et jagatud s\u00fcsteemil on rida atribuutide, mis on meie jaoks olulised.<\/p>\n

Jagatud s\u00fcsteemide atribuudid<\/h4>\n

<\/p>\n

    \n
  1. Samaegne t\u00f6\u00f6tlus<\/b> \u2013 v\u00f5imalus, et s\u00fcsteemis esinevad samaaegsed v\u00f5i konkurentsed s\u00fcndmused. Veelgi enam, me arvestame, et s\u00fcndmused, mis toimuvad kahel erineval s\u00f5lmel, on potentsiaalselt konkurentsed, kuni meil pole selget s\u00fcndmuste j\u00e4rjekorda. Ja tavaliselt pole meil seda.<\/li>\n
  2. Globaalsete kellade puudumine<\/b>. Meil ei ole s\u00fcndmuste selget j\u00e4rjekorda, kuna globaalsed kellad puuduvad. Tavalises inimestemaailmas oleme harjunud, et meil on kellad ja aeg on absoluutne. K\u00f5ik muutub, kui r\u00e4\u00e4kida jagatud s\u00fcsteemidest. Ieven kui supert\u00e4psetel aatomikelladel on drift, v\u00f5ivad esineda olukorrad, kus me ei suuda \u00f6elda, kumb kahest s\u00fcndmusest toimus esimesena. Seet\u00f5ttu ei saa me ka ajale toetuda.<\/li>\n
  3. S\u00f5lmede s\u00f5ltumatu rike s\u00fcsteemis<\/b>. On veel \u00fcks probleem: midagi v\u00f5ib lihtsalt valesti minna, kuna meie s\u00f5lmed ei ole igavesed. K\u00f5vaketas v\u00f5ib rikkuda, virtuaalkompuuter v\u00f5ib pilves taask\u00e4ivituda, v\u00f5rk v\u00f5ib vahelduda ja s\u00f5numid v\u00f5ivad kaduda. Veelgi enam, v\u00f5ivad esineda olukorrad, kus s\u00f5lmed t\u00f6\u00f6tavad, kuid tegutsevad s\u00fcsteemi vastu. Selle viimase klassi probleem on isegi saadud eraldi nime: byzantine generaalide probleem<\/a><\/noindex>. K\u00f5ige populaarsem n\u00e4ide jagatud s\u00fcsteemist, kus esineb selline probleem, on Blockchain. Kuid t\u00e4na me seda spetsiaalset probleemide klassi ei k\u00e4sitle. Meid huvitavad olukorrad, kus lihtsalt \u00fcks v\u00f5i mitu s\u00f5lme v\u00f5ivad rikke p\u00f5hjustada.<\/li>\n
  4. Kommunikatsioonimudelid (s\u00f5numite vahetuse mudelid) s\u00f5lmede vahel<\/b>. Oleme juba tuvastanud, et s\u00f5lmed suhtlevad s\u00f5numite vahetamise kaudu. On kaks tuntud s\u00f5numite vahetuse mudelit: s\u00fcnkroonne ja as\u00fcnkroonne.<\/li>\n<\/ol>\n

    <\/p>\n

    Jagatud s\u00fcsteemide s\u00f5lmede vahelised kommunikatsioonimudelid<\/h4>\n

    \nS\u00fcnkroonne mudel<\/b> \u2013 me teame t\u00e4pselt, et olemas on l\u00f5plik tuntud ajavahemik, mille jooksul s\u00f5num j\u00f5uab garantii alusel \u00fchest s\u00f5lmest teise. Kui see aeg on m\u00f6\u00f6das ja s\u00f5num pole saabunud, saame julgelt \u00f6elda, et s\u00f5lm on v\u00e4lja langenud. Sellises mudelis on meil etteennustatav ooteaeg. <\/p>\n

    As\u00fcnkroonne mudel<\/b> \u2013 as\u00fcnkroonsetes mudelites eeldame, et ooteaeg on piiratud, kuid ei ole olemas sellist ajavahemikku, p\u00e4rast mida saab garantii, et s\u00f5lm on v\u00e4lja langenud. See t\u00e4hendab, et s\u00f5numi ooteaeg s\u00f5lmest v\u00f5ib olla piiratud ajatu. See on oluline m\u00e4\u00e4ratlemine ja me r\u00e4\u00e4gime sellest hiljem. <\/p>\n

    Konsensuse m\u00f5isted jagatud s\u00fcsteemides<\/h2>\n

    \nEnne kui m\u00e4\u00e4ratleme konsensuse m\u00f5iste formaalselt, vaatame n\u00e4idet olukorrast, kus see on vajalik, nimelt \u2013 State Machine Replication<\/b>. <\/p>\n

    Meil on teatud jagatud logi. Me tahaksime, et see oleks j\u00e4rjepidev ja sisaldaks identseid andmeid k\u00f5igis jagatud s\u00fcsteemi s\u00f5lmedes. Kui m\u00f5ni s\u00f5lm saab teada uue v\u00e4\u00e4rtuse, mille ta tahab logisse kirjutada, on tema \u00fclesanne see v\u00e4\u00e4rtus k\u00f5igile teistele s\u00f5lmedele ettepanekuna esitada, et logi uuendataks k\u00f5igil s\u00f5lmedel ning s\u00fcsteem l\u00e4heks uude j\u00e4rjepidevasse olekusse. Oluline on, et s\u00f5lmed oleksid omavahel kokku leppinud: k\u00f5ik s\u00f5lmed on n\u00f5ustunud, et ettepanek uus v\u00e4\u00e4rtus on \u00f5ige, k\u00f5ik s\u00f5lmed on selle v\u00e4\u00e4rtuse vastu v\u00f5tnud, ja ainult sel juhul saavad k\u00f5ik logisse uue v\u00e4\u00e4rtuse kirjutada. <\/p>\n

    Teisis\u00f5nu: \u00fckski s\u00f5lm ei vaidanud, et tal on aktuaalsem teave ja ettepanek, et v\u00e4\u00e4rtus on vale. S\u00f5lmede vaheline kokkulepe ja konsensus \u00fchiselt aktsepteeritud v\u00e4\u00e4rtuste osas on see, mis on konsensus jagatud s\u00fcsteemis. Edasi r\u00e4\u00e4gime algoritmidest, mis v\u00f5imaldavad jagatud s\u00fcsteemil garanteeritult konsensusele j\u00f5uda.
    \n\"Schr\u00f6dinger's
    \nRohkem formaalselt saame konsensuse algoritmi (v\u00f5i lihtsalt konsensuse algoritmi) m\u00e4\u00e4ratleda kui mingit funktsiooni, mis viib jaotatud s\u00fcsteemi seisundist A seisundisse B. Oluline on, et see seisund oleks k\u00f5ikide s\u00f5lmede poolt aktsepteeritud ja k\u00f5ik s\u00f5lmed suudaksid seda kinnitada. Nagu selgub, ei ole see \u00fclesanne sugugi nii triviaalne, nagu esmapilgul v\u00f5ib paista.<\/p>\n

    Konsensuse algoritmi omadused<\/h4>\n

    \nKonsensuse algoritmil peavad olema kolm omadust, et s\u00fcsteem saaks j\u00e4tkata eksisteerimist ja omada mingit progressi seisundist seisundisse liikumisel:<\/p>\n

      \n
    1. Leppimine <\/b> \u2013 k\u00f5ik \u00f5igesti t\u00f6\u00f6tavad s\u00f5lmed peavad aktsepteerima sama v\u00e4\u00e4rtust (selles artiklis nimetatakse seda omadust ka ohutuse omaduseks). K\u00f5ik s\u00f5lmed, mis praegu t\u00f6\u00f6tavad (ei ole rikki l\u00e4inud ega kaotanud \u00fchendust teistega) peavad omavahel leppima ja aktsepteerima mingit l\u00f5plikku \u00fchist v\u00e4\u00e4rtust.\n

      Siinkohal on oluline m\u00f5ista, et s\u00f5lmedes arutletavas jaotatud s\u00fcsteemis on soovi leppida kokku. P\u00fc\u00fcame r\u00e4\u00e4kida s\u00fcsteemidest, kus v\u00f5ib juhtuda, et midagi eba\u00f5nnestub (nt m\u00f5ni s\u00f5lm eba\u00f5nnestub), kuid selles s\u00fcsteemis ei ole s\u00f5lmi, mis t\u00f6\u00f6tavad teadlikult teiste vastu (biitantsed generaatorid). T\u00e4nu sellele omadusele j\u00e4\u00e4b s\u00fcsteem j\u00e4rjekindlaks.<\/li>\n

    2. Integreerimine <\/b> \u2014 kui k\u00f5ik \u00f5igesti t\u00f6\u00f6tavad s\u00f5lmed pakuvad sama v\u00e4\u00e4rtust v<\/b>, siis peab iga \u00f5igesti t\u00f6\u00f6tav s\u00f5lm selle v\u00e4\u00e4rtuse aktsepteerima v<\/b>. <\/li>\n
    3. L\u00f5petamine <\/b>\u2013 k\u00f5ik \u00f5igesti t\u00f6\u00f6tavad s\u00f5lmed l\u00f5puks aktsepteerivad mingi v\u00e4\u00e4rtuse (elavuse omadus), mis v\u00f5imaldab algoritmil s\u00fcsteemis edeneda. Iga eraldi \u00f5igesti t\u00f6\u00f6tav s\u00f5lm peab mingil hetkel aktsepteerima l\u00f5pliku v\u00e4\u00e4rtuse ja kinnitama: \u201eMinule \u2013 see v\u00e4\u00e4rtus on t\u00f5ene, n\u00f5ustun kogu s\u00fcsteemiga.\u201d<\/li>\n<\/ol>\n

      <\/p>\n

      Konsensuse algoritmi n\u00e4ide<\/h4>\n

      \nKuna algoritmi omadused v\u00f5ivad esialgu olla arusaamatud, illustreerime seda k\u00f5ige lihtsama konsensuse algoritmi n\u00e4itega, mis l\u00e4bib etappe s\u00fcmpaatiliselt \u00fclesehitatud s\u00f5numitevahetuss\u00fcsteemis, kus k\u00f5ik s\u00f5lmed toimivad nagu peab, s\u00f5numid ei kao ja mitte midagi ei riku (kas see t\u00f5esti juhtuda v\u00f5ib?).<\/p>\n

        \n
      1. K\u00f5ik algab ettepanekust (Propose). Oletame, et s\u00f5lmele nimega \u201eS\u00f5lm 1\u201d on \u00fchendatud klient, kes alustas tehingut ning edastas s\u00f5lmele uue v\u00e4\u00e4rtuse \u2013 O. Alates sellest punktist hakkame \u201eS\u00f5lme 1\u201d nimetama proposer<\/b>. Kuidas proposer, peab \u201eS\u00f5lm 1\u201d n\u00fc\u00fcd teavitama kogu s\u00fcsteemi, et tal on v\u00e4rsked andmed, ja saadab teistele s\u00f5lmedele s\u00f5numid: \u201eVaadake! Mul on tulnud v\u00e4\u00e4rtus \u201eO\u201d ja ma soovin selle salvestada! Palun kinnitage, et ka teie salvestate \u201eO\u201d oma logisse.\u201d\n

        \"Schr\u00f6dinger's<\/li>\n

      2. J\u00e4rgmine etapp on h\u00e4\u00e4letamine pakutud v\u00e4\u00e4rtuse \u00fcle (Voting). Miks see vajalik on? V\u00f5ib juhtuda, et teistel s\u00f5lmedel on saanud v\u00e4rskemat teavet ja neil on selle sama tehinguga seotud andmeid.\n

        \"Schr\u00f6dinger's
        \n
        \nKui s\u00f5lm \u201eS\u00f5lm 1\u201d saadab oma ettepaneku, siis vaatavad teised s\u00f5lmed oma logidest selle s\u00fcndmuse andmeid. Kui vastuolusid ei esine, teatavad s\u00f5lmed: \u201eJah, minult ei tule selle s\u00fcndmuse kohta teisi andmeid. V\u00e4\u00e4rtus \u201eO\u201d on k\u00f5ige v\u00e4rskem info, mille me oleme saanud.\u201d <\/p>\n

        Muudel juhtudel v\u00f5ivad s\u00f5lmed vastata \u201eS\u00f5lm 1\u201d jaoks: \u201eKuule! Mul on selle tehingu kohta v\u00e4rskemaid andmeid. Mitte \u201eO\u201d, vaid midagi paremat.\u201d<\/p>\n

        H\u00e4\u00e4letuse etapis j\u00f5uavad s\u00f5lmed otsusele: kas k\u00f5ik aktsepteerivad sama v\u00e4\u00e4rtuse v\u00f5i keegi neist h\u00e4\u00e4letab vastu, m\u00e4rgides, et tal on v\u00e4rskemaid andmeid. <\/li>\n

      3. Kui h\u00e4\u00e4letusvoor on \u00f5nnestunud, ja k\u00f5ik olid \u201eja\u201d, siis liigub s\u00fcsteem j\u00e4rgmisse etappi \u2013 v\u00e4\u00e4rtuse aktsepteerimine (Accept). \u201eS\u00f5lm 1\u201d kogub teiste s\u00f5lmede k\u00f5ik vastused ja teatab: \u201eK\u00f5ik on n\u00f5ustunud v\u00e4\u00e4rtusega \u201eO\u201d! N\u00fc\u00fcdsest kuulutan ma ametlikult, et \u201eO\u201d on meie uus v\u00e4\u00e4rtus, k\u00f5igi jaoks \u00fchine! Salvestage see endale, \u00e4rge unustage. Salvestage oma logisse!\u201d\n

        \"Schr\u00f6dinger's<\/li>\n

      4. Teised s\u00f5lmed saadavad kinnituse (Accepted), et nad on salvestanud v\u00e4\u00e4rtuse \u201eO\u201d, ei ole midagi uut sisse tulnud (omaette kahefaasiline kinnitamine). P\u00e4rast seda m\u00e4rkimisv\u00e4\u00e4rset s\u00fcndmust loeme, et jaotatud tehing on t\u00e4idetud.
        \n \"Schr\u00f6dinger's <\/li>\n<\/ol>\n

        \nNii koosneb konsensuse algoritm lihtsas vormis neljast sammust: ettepanek, h\u00e4\u00e4letamine, aktsepteerimine, aktsepteerimise kinnitamine.<\/p>\n

        Kui m\u00f5nes etapis ei \u00f5nnestunud j\u00f5uda konsensusele, k\u00e4ivitub algoritm uuesti, arvestades teavet, mida annavad s\u00f5lmed, kes ei n\u00f5ustunud pakutud v\u00e4\u00e4rtust kinnitama.<\/p>\n

        Konsensuse algoritm as\u00fcnkronses s\u00fcsteemis<\/h2>\n

        \nKuni k\u00f5ik oli sujuv, r\u00e4\u00e4kisime s\u00fcnkroonsest s\u00f5numivahetusmudelile. Kuid me teame, et t\u00e4nap\u00e4eva maailmas oleme k\u00f5ik harjunud tegema as\u00fcnkroonselt. Kuidas siis sarnane algoritm t\u00f6\u00f6tab s\u00fcsteemis, kus on as\u00fcnkroonse s\u00f5numivahetuse mudel, kus me arvame, et vastuse ootamine s\u00f5lmele v\u00f5ib olla l\u00f5pmatult pikk (muide, s\u00f5lme rike v\u00f5ib samuti olla n\u00e4ide, kui s\u00f5lm v\u00f5ib vastata l\u00f5pmatult kaua). <\/p>\n

        N\u00fc\u00fcd, kui me teame, kuidas p\u00f5him\u00f5tteliselt konsensusalgoritm t\u00f6\u00f6tab, on k\u00fcsimus neile uudishimulikele lugejatele, kes on siia j\u00f5udnud: kui palju s\u00f5lmi N s\u00f5lmest as\u00fcnkroonses s\u00f5numivahetuss\u00fcsteemis v\u00f5ib rikki minna, et s\u00fcsteem saaks endiselt konsensusele j\u00f5uda?<\/p><\/blockquote>\n

        \n\u00d5ige vastus ja p\u00f5hjendus on spoileris.<\/b>\u00d5ige vastus: 0<\/b>. Kui v\u00e4hemalt \u00fcks s\u00f5lm as\u00fcnkroonses s\u00fcsteemis rikki l\u00e4heb, ei suuda s\u00fcsteem konsensusele j\u00f5uda. Seda v\u00e4idet t\u00f5estatakse tuntud teoreemi FLP (1985, Fischer, Lynch, Paterson) puhul, mille originaali link on artikli l\u00f5pus: \"Rikkumise korral ei saa saavutada jaotatud konsensust, kui v\u00e4hemalt \u00fcks s\u00f5lm on rikki l\u00e4inud.\"
        \n\"Schr\u00f6dinger's
        \nPoisid, siis on meil probleem, me oleme harjunud, et k\u00f5ik on as\u00fcnkroone. Ja n\u00fc\u00fcd on selline asjaolu. Kuidas edasi elada? <\/p>\n

        Me r\u00e4\u00e4kisime praegu teooriast, matemaatikast. Mida t\u00e4hendab \"konsensus ei saa olla saavutatud\", t\u00f5lkides matemaatilisest keelest meie \u2013 insenerikeelde? See t\u00e4hendab, et \"ei pruugi alati olla saavutatud\", st on olemas selline juhtum, kus konsensus ei ole saavutatav. Mis juhtum see siis on? <\/p>\n

        See on t\u00e4pselt liveness property rikkumine, mida eespool kirjeldati. Meil ei ole \u00fchisele n\u00f5usolekule, ning s\u00fcsteem ei saa edusamme teha (ei saa l\u00f5ppeda piiratud ajas) juhul, kui meil ei ole k\u00f5igilt s\u00f5lmedelt vastust. Sest as\u00fcnkroonses s\u00fcsteemis ei ole meil ennustatavat vastusaega ja me ei saa teada, kas s\u00f5lm on rikki l\u00e4inud v\u00f5i lihtsalt vastab pika aja jooksul.<\/p>\n

        Kuid praktikas saame lahenduse leida. Oletame, et meie algoritm v\u00f5ib vigastuste korral kaua t\u00f6\u00f6tada (potentsiaalselt v\u00f5ib t\u00f6\u00f6tada l\u00f5putult). Kuid enamikus olukordades, kus enamus s\u00f5lmi t\u00f6\u00f6tab t\u00f5rgeteta, saavutame s\u00fcsteemis edusamme. <\/p>\n

        Praktikas puutume kokku osaliselt s\u00fcnkroonsete kommunikatsioonimudelitega. Osalist s\u00fcnkroonsust m\u00f5istetakse nii: tavaliselt on meil as\u00fcnkroonne mudel, kuid ametlikult tuuakse sisse mingi m\u00f5iste \"global stabilization time\" mingist ajast. <\/p>\n

        See ajamoment v\u00f5ib mitte tulla l\u00f5putult kaua, kuid \u00fchel p\u00e4eval peab see kindlasti toimuma. Virtuaalne \u00e4ratus heliseb ja alates sellest hetkest saame ennustada ajavahemikku, mille jooksul s\u00f5numid kohale j\u00f5uavad. Sellest hetkest muutub as\u00fcnkroonne s\u00fcsteem s\u00fcnkroonses s\u00fcsteemiks. Praktikas puutume kokku just selliste s\u00fcsteemidega. <\/p>\n

        Paxos algoritm lahendab konsensuse probleemid<\/h2>\n

        \nPaxos <\/a><\/noindex> on algoritmide perekond, mis lahendab konsensuse probleemi osaliselt s\u00fcnkroonsetes s\u00fcsteemides, kus m\u00f5ned s\u00f5lmed v\u00f5ivad eba\u00f5nnestuda. Paxosi autor on Leslie Lamport.<\/a><\/noindex>Ta esitas 1989. aastal algoritmi olemasolu ja \u00f5igsuse ametliku t\u00f5estuse. <\/p>\n

        Kuid t\u00f5estamine osutus kaugel lihtsaks. Esimene publikatsioon ilmus alles 1998. aastal (33 lehek\u00fclge), kus kirjeldati algoritmi. Nagu selgus, oli see \u00e4\u00e4rmiselt keeruline m\u00f5ista, ja 2001. aastal ilmus artikli selgitus, mis h\u00f5ivas 14 lehte. Publikatsioonide mahud on toodud selleks, et n\u00e4idata, et tegelikult on konsensuse probleem \u00fcsna keeruline ning selliste algoritmide taga on tohutu t\u00f6\u00f6 k\u00f5ige targemate inimeste poolt.<\/p>\n

        Huvitav, et Leslie Lamport ise m\u00e4rkis oma loengus, et teises selgitavas artiklis on \u00fcks v\u00e4ide, \u00fcks rida (ta ei t\u00e4psustanud, milline), mille t\u00f5lgendamine v\u00f5ib olla erinev. Ja seet\u00f5ttu toimib suur hulk t\u00e4nap\u00e4evaseid Paxose rakendusi mitte t\u00e4iesti korrektselt. <\/p><\/blockquote>\n

        \nPaxosi toimimise p\u00f5hjalik k\u00e4sitlus vajab rohkem kui \u00fchte artiklit, seega p\u00fc\u00fcan ma p\u00e4\u00e4seda l\u00fchidalt algoritmi p\u00f5hisisu edastamiseni. Artikli l\u00f5pus leiate lingid edasiseks s\u00fcvenemiseks sellesse teema.<\/p>\n

        Rollen Paxoses<\/h4>\n

        \nPaxose algoritmis on olemas rollide m\u00f5isted. Vaatame kolme peamist (on ka modifikatsioone, kus on lisarolle):<\/p>\n

          \n
        1. Proposers (v\u00f5ivad esineda ka terminid: liidrid v\u00f5i koordinaatorid).<\/b>Need on inimesed, kes saavad teada m\u00f5ne uuest v\u00e4\u00e4rtusest kasutajalt ja v\u00f5tavad juhtrolli. Nende \u00fclesanne on k\u00e4ivitada uue v\u00e4\u00e4rtuse ettepaneku voor ja koordineerida edasised toimingud s\u00f5lmedega. Paxos lubab teatud olukordades mitu liidrit.<\/li>\n
        2. Acceptors (Voters)<\/b>. Need on s\u00f5lmed, mis h\u00e4\u00e4letavad, kas aktsepteerida v\u00f5i tagasi l\u00fckata teatud v\u00e4\u00e4rtus. Nende roll on v\u00e4ga oluline, kuna just nemad otsustavad, milliseks olekuks s\u00fcsteem l\u00e4heb (v\u00f5i ei l\u00e4he) p\u00e4rast konsensuse algoritmi j\u00e4rgmiste etappide l\u00e4biviimist.<\/li>\n
        3. Kasutajad<\/b>. Need on s\u00f5lmed, mis lihtsalt aktsepteerivad ja salvestavad uut aktsepteeritud v\u00e4\u00e4rtust, kui s\u00fcsteemi olek muutub. Nad ei tee otsuseid, vaid saavad andmeid ja saavad neid edasi anda l\u00f5ppkasutajale. <\/li>\n<\/ol>\n

          \n\u00dcks s\u00f5lm v\u00f5ib erinevates olukordades t\u00e4ita mitmeid rolle. <\/p>\n

          Kvoorumi m\u00f5isted<\/h4>\n

          \nEeldame, et meie s\u00fcsteem koosneb N<\/b> s\u00f5lmest. Ja neist v\u00f5ib maksimum F<\/b> s\u00f5lme minna v\u00e4lja. Kui F s\u00f5lme suudab halveneda, peab meie klastris olema v\u00e4hemalt 2F + 1<\/b> acceptor s\u00f5lmed. <\/p>\n

          See on vajalik, et meil oleks alati, isegi halvima olukorra korral, \u201ehead\u201d, korralikult t\u00f6\u00f6tavad s\u00f5lmed, kes moodustavad enamuse. See t\u00e4hendab, et on v\u00e4hemalt F + 1<\/b> \u201ehead\u201d s\u00f5lme, kes on selle poolt, ja l\u00f5plik v\u00e4\u00e4rtus v\u00f5etakse vastu. Vastasel korral v\u00f5ib juhtuda, et meie erinevad kohalikud grupid v\u00f5tavad vastu erinevaid v\u00e4\u00e4rtusi ja ei suuda omavahel kokku leppida. Seep\u00e4rast vajame absoluutset enamust, et v\u00f5ita h\u00e4\u00e4letusel.<\/p>\n

          Paxos konsensuse algoritmi \u00fcldine idee<\/h4>\n

          \nPaxose algoritm koosneb kahest suurest faasist, mis jagunevad omakorda kaheks samaksmiseks:<\/p>\n

            \n
          1. Faas 1a: Ettevalmistamine<\/b>. Ettevalmistuse etapis teatab liider (proposser) k\u00f5ikidele s\u00f5lmedele: \u201eAlustame uut h\u00e4\u00e4letusfaasi. Meil on uus voor. Selle vooru number on n. N\u00fc\u00fcd hakkame h\u00e4\u00e4letama\u201d. Praegu teatab ta lihtsalt uue ts\u00fckli algusest, kuid ei ava uut v\u00e4\u00e4rtust. Loomise \u00fclesanne on alustada uut vooru ja anda k\u00f5igile selle unikaalne number. Vooru number on oluline, see peab olema suurem kui k\u00f5ik eelnevad h\u00e4\u00e4letusnumbrid k\u00f5igilt eelnevatelt liidritelt. Just t\u00e4nu vooru numbrile m\u00f5istavad teised s\u00fcsteemi loksud, kui v\u00e4rsked andmed liider on. T\u00f5en\u00e4oliselt on teistel s\u00f5lmedel juba hilisema vooru h\u00e4\u00e4letamise tulemused ja nad teatavad lihtsalt liidrile, et ta on maha j\u00e4\u00e4nud.<\/li>\n
          2. Faas 1b: Lubadus<\/b>. Kui acceptor s\u00f5lmed on saanud uue h\u00e4\u00e4letusfaasi numbri, on v\u00f5imalikud kaks tulemust: \n