{"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\u00f6dingeri kass ilma karbita: konsensuse probleem jaotatud s\u00fcsteemides","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Nii, kujutame ette. Toas on lukus 5 kassi, ning et minna \u00e4ratama peremeest, peavad nad k\u00f5ik koos omavahel kokkuleppele j\u00f5udma, sest nad saavad ust avada ainult viiekesi sellele peale vajudes. Kui \u00fcks kassidest on Schr\u00f6dingeri kass ja teised kassid ei tea tema otsusest, siis tekib k\u00fcsimus: \"Kuidas nad seda saavad teha?\" <\/p>\n

\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u044f\u0437\u044b\u043a\u043e\u043c \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u0432\u0430\u043c \u043e \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0435\u0439 \u043c\u0438\u0440\u0430 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0451\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c \u0438 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0430\u0445 \u0438\u0445 \u0440\u0430\u0431\u043e\u0442\u044b. \u0410 \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u0432\u0435\u0440\u0445\u043d\u043e\u0441\u0442\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u044e \u0433\u043b\u0430\u0432\u043d\u0443\u044e \u0438\u0434\u0435\u044e, \u043b\u0435\u0436\u0430\u0449\u0443\u044e \u0432 \u043e\u0441\u043d\u043e\u0432\u0435 Paxos’\u0430. <\/p>\n

\"Schr\u00f6dingeri
\n<\/a><\/noindex>
\nKui arendajad kasutavad pilve infrastruktuure, erinevaid andmebaase ja t\u00f6\u00f6tavad suure arvu s\u00f5lmedega klastrites, on nad kindlad, et andmed on terviklikud, turvalised ja alati kergesti k\u00e4ttesaadavad. Kuid kust tulevad need garantiid?<\/p>\n

Tegelikult, mida me usaldame \u2013 need on tarnijate garantiid. Need on dokumenteeritud umbes j\u00e4rgmise viisil: \"See teenus on piisavalt usaldusv\u00e4\u00e4rne, sellel on m\u00e4\u00e4ratud SLA, \u00e4rge muretsege, k\u00f5ik t\u00f6\u00f6tab jaotatult nagu teie ootused on.\" <\/p>\n

Kaldume uskuma parimat, sest nutikad onud suurtest ettev\u00f5tetest on meid rahustanud, et k\u00f5ik l\u00e4heb h\u00e4sti. Me ei sea endale k\u00fcsimust: miks see ometi v\u00f5ib t\u00f6\u00f6tada? Kas on olemas mingi formaalne t\u00f5end selliste s\u00fcsteemide t\u00f6\u00f6 korrektsuse kohta?<\/p>\n

Hiljuti k\u00e4isin jagatud arvutuskohtade koolis<\/a><\/noindex> ja olin selle teemaga v\u00e4ga inspireeritud. Loengud koolis meenutasid rohkem matemaatilise anal\u00fc\u00fcsi tunde, kui midagi, mis on seotud arvutis\u00fcsteemidega. Kuid just nii t\u00f5estati kunagi meie igap\u00e4evaselt kasutatavaid t\u00e4htsaid algoritme, isegi sellest aimamata. <\/p>\n

Enamikus kaasaegsetes jagatud s\u00fcsteemides kasutatakse konsensuse algoritmi Paxos ja selle erinevaid varieeruvaid versioone. K\u00f5ige \u00e4gedam on see, et selle algoritmi \u00f5igustamine ja selle olemasolu v\u00f5imaluse t\u00f5estamine on v\u00f5imalik lihtsalt pliiatsi ja paberiga. Samas rakendatakse algoritmi praktikas suurtes s\u00fcsteemides, mis t\u00f6\u00f6tavad tohutu hulga s\u00f5lmedega pilvedes. <\/p>\n

Kergesti m\u00f5istetav illustratsioon sellest, millest edaspidi jutt l\u00e4heb: kahe kindraliga probleem<\/b>Alustuseks vaadake kahe kindraliga probleemi<\/a><\/noindex>. <\/p>\n

Meil on kaks armee - punane ja valge. Valged v\u00e4ed paiknevad piiratud linnas. Punased v\u00e4ed, mida juhivad kindralid A1 ja A2, asuvad linnast m\u00f5lemal poole. Punaste \u00fclesanne on r\u00fcnnata valget linna ja v\u00f5ita. Siiski on iga punase kindrali v\u00e4gi eraldi v\u00e4iksem kui valgete v\u00e4gi.<\/p>\n

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

Kokkulepeteks v\u00f5ivad kindralid A1 ja A2 saata omavahel s\u00f5numitoojaid l\u00e4bi valge linna teritoriumi. S\u00f5numitooja v\u00f5ib j\u00f5uda liitlase kindrali juurde v\u00f5i v\u00f5idakse ta kinni p\u00fc\u00fcda vastase poolt. K\u00fcsimus: kas on olemas selline suhtlemise j\u00e4rjestus punaste kindralite vahel (s\u00f5numitoojate saatmise j\u00e4rjestus A1-lt A2-le ja vastupidi A2-lt A1-le), mille korral nad garantii alusel lepivad kokku r\u00fcnnakus kell X. Siin m\u00f5istetakse garanteerimise all, et m\u00f5lemad kindralid saavad selge kinnituse, et liitlane (teine kindral) r\u00fcndab kindlasti m\u00e4\u00e4ratud ajal X.<\/p>\n

Oletame, et A1 saadab A2-le s\u00f5numitooja s\u00f5numiga: \"R\u00fcndame t\u00e4na kesk\u00f6\u00f6l!\". Kindral A1 ei saa r\u00fcnnata ilma kindral A2 kinnituse. Kui s\u00f5numitooja A1-st on kohale j\u00f5udnud, saadab kindral A2 kinnituse s\u00f5numiga: \"Jah, r\u00fcndame t\u00e4na valgeid.\" Kuid n\u00fc\u00fcd ei tea kindral A2, kas tema s\u00f5numitooja on kohale j\u00f5udnud v\u00f5i mitte, tal pole garanteeringut, kas r\u00fcnnak toimub samaaegselt. N\u00fc\u00fcd vajab A2 uuesti kinnitust.<\/p>\n

Kui nende suhtlemist edasi lahti seletada, selgub j\u00e4rgnev: s\u00f5ltumata sellest, kui palju s\u00f5numite vahetamise ts\u00fckleid on, ei ole v\u00f5imalik kindlalt teavitada m\u00f5lemat kindralit, et nende s\u00f5numid on k\u00e4tte saadud (tingimusel, et \u00fcksk\u00f5ik milline s\u00f5numitooja v\u00f5ib olla kinni peetud).<\/p>\n

Kahe kindrali probleem on suurep\u00e4rane illustreerimine v\u00e4ga lihtsast jaotatud s\u00fcsteemist, kus on kaks s\u00f5lme ebausaldusv\u00e4\u00e4rse kommunikatsiooniga. See t\u00e4hendab, et meil ei ole 100% garantiid, et nad s\u00fcnkroniseeruvad. Sellistest probleemidest ainult suuremas ulatuses r\u00e4\u00e4gitakse hiljem artiklis.<\/p>\n

Sisseviimine jaotatud s\u00fcsteemide m\u00f5istet<\/h2>\n

\nJaotatud s\u00fcsteem on arvutite r\u00fchm (edaspidi nimetame neid s\u00f5lmedeks), mis saavad omavahel s\u00f5numeid vahetada. Iga eraldi s\u00f5lm on mingi autonoomne entiteet. S\u00f5lm v\u00f5ib iseseisvalt \u00fclesandeid t\u00f6\u00f6tleda, kuid et suhelda teiste s\u00f5lmedega, peab ta saatma ja vastu v\u00f5tma s\u00f5numeid. <\/p>\n

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

Kuna m\u00e4\u00e4ratlemine ei tundu keeruline, peame siiski arvestama, et jaotatud s\u00fcsteemil on mitmeid atribuute, mis on meile olulised.<\/p>\n

Jaotatud s\u00fcsteemide atribuuti<\/h4>\n

<\/p>\n

    \n
  1. Konkureerimine<\/b> \u2013 v\u00f5imalus, et s\u00fcsteemis v\u00f5ivad tekkida samaaegsed v\u00f5i konkurentsiv\u00f5imelised s\u00fcndmused. Veelgi enam, me arvestame, et s\u00fcndmused, mis toimuvad kahes erinevas s\u00f5lmes, on potentsiaalselt konkurentsiv\u00f5imelised, kuni meil pole kindlat s\u00fcndmuste tekkimise j\u00e4rjekorda. Ja reeglina pole meil seda olemas.<\/li>\n
  2. Globaalsete kellade puudumine<\/b>. Meil pole kindlat s\u00fcndmuste j\u00e4rjekorda, kuna puuduvad globaalne kellad. Tavalises inimmaailmas oleme harjunud, et meil on kellad ja aeg on absoluutne. K\u00f5ik muutub, kui r\u00e4\u00e4gime jaotatud s\u00fcsteemidest. I \u0434\u0430\u0436\u0435 \u0441\u0432\u0435\u0440\u0445\u0442\u043e\u0447\u043d\u044b\u0435 \u0430\u0442\u043e\u043c\u043d\u044b\u0435 \u0447\u0430\u0441\u043e\u0432 \u0438\u043c\u0435\u044e\u0442 \u0434\u0440\u0435\u0439\u0444, \u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438, \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u043a\u0430\u043a\u043e\u0435 \u0438\u0437 \u0434\u0432\u0443\u0445 \u0441\u043e\u0431\u044b\u0442\u0438\u0439 \u043f\u0440\u043e\u0438\u0437\u043e\u0448\u043b\u043e \u0440\u0430\u043d\u044c\u0448\u0435. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u043e\u043b\u0430\u0433\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u0432\u0440\u0435\u043c\u044f \u043c\u044b \u0442\u043e\u0436\u0435 \u043d\u0435 \u043c\u043e\u0436\u0435\u043c.<\/li>\n
  3. S\u00fcsteemi s\u00f5lmede s\u00f5ltumatu rike<\/b>. On veel \u00fcks probleem: midagi v\u00f5ib valesti minna lihtsalt seet\u00f5ttu, et meie s\u00f5lmed ei ole igavesed. K\u00f5vaketas v\u00f5ib rikkeda, pilves oleva virtuaali v\u00f5ib taask\u00e4ivitada, v\u00f5rk v\u00f5ib murranguda ja s\u00f5numid v\u00f5ivad kaduda. Veelgi enam, on v\u00f5imalik, et s\u00f5lmed t\u00f6\u00f6tavad, kuid t\u00f6\u00f6tavad samal ajal s\u00fcsteemi vastu. Viimane probleemide klass on isegi eraldi nime saanud: probleem Byzantine generaalide<\/a><\/noindex>. K\u00f5ige populaarsem jaotatud s\u00fcsteem, kus selline probleem esineb, on Blockchain. Kuid t\u00e4na me ei k\u00e4sitle seda erilisest probleemi klassist. Meid huvitavad olukorrad, kus lihtsalt \u00fcks v\u00f5i mitu s\u00f5lme v\u00f5ivad rikki minna.<\/li>\n
  4. Kommunikatsioonimudelid (s\u00f5numite vahetamise mudelid) s\u00f5lmede vahel<\/b>Oleme juba v\u00e4lja selgitanud, et s\u00f5lmed suhtlevad omavahel s\u00f5numite vahetamise teel. On kaks tuntud s\u00f5numite vahetamise mudelit: s\u00fcnkroonne ja as\u00fcnkroonne.<\/li>\n<\/ol>\n

    <\/p>\n

    S\u00f5lmede vaheliste kommunikatsioonimudelite jagatud s\u00fcsteemides<\/h4>\n

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

    As\u00fcnkroonne mudel<\/b> \u2013 as\u00fcnkroonsetes mudelites arvame, et ooteaeg on l\u00f5plik, kuid ei eksisteeri sellist ajavahet, p\u00e4rast mida saaks garanteerida, et s\u00f5lm on v\u00e4lja langenud. St. s\u00f5numi ootamine \u00fchest s\u00f5lmest v\u00f5ib kesta nii kaua, kui tahes. See on oluline m\u00e4\u00e4ratlemine ja me r\u00e4\u00e4kime sellest edasi. <\/p>\n

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

    \nEnne konsensuse m\u00f5iste ametlikku m\u00e4\u00e4ratlemist vaatame n\u00e4idet olukorrast, kus see on vajalik, nimelt \u2013 Oleku Masina Korrutamine<\/b>. <\/p>\n

    Meil on teatud jagatud logi. Soovime, 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 plaanib logisse salvestada, on tema \u00fclesanne pakkuda see v\u00e4\u00e4rtus k\u00f5igile teistele s\u00f5lmedele, et logi saaks uuendatud k\u00f5igis s\u00f5lmedes ja s\u00fcsteem liiguks uude j\u00e4rjepidevasse olekusse. Oluline on, et s\u00f5lmed omavahel kokkulepiksid: k\u00f5ik s\u00f5lmed n\u00f5ustuvad, et pakutud uus v\u00e4\u00e4rtus on \u00f5ige, k\u00f5ik s\u00f5lmed aktsepteerivad selle v\u00e4\u00e4rtuse, ja ainult siis saavad k\u00f5ik logisse kirjutada uue v\u00e4\u00e4rtuse. <\/p>\n

    Teisis\u00f5nu: \u00fckski s\u00f5lm ei ole vaielnud vastu, et tal on v\u00e4rskemat teavet ja pakutud v\u00e4\u00e4rtus on vale. S\u00f5lmedevaheline kokkulepe ja n\u00f5usolek \u00fchtse \u00f5igesti vastuv\u00f5etud v\u00e4\u00e4rtuse osas ongi konsensus jagatud s\u00fcsteemis. J\u00e4tkame r\u00e4\u00e4kides algoritmidest, mis v\u00f5imaldavad jagatud s\u00fcsteemil konsensust tagada.
    \n\"Schr\u00f6dingeri
    \nRohkem formaalselt saame konsensuse saavutamise algoritmi (v\u00f5i lihtsalt konsensuse algoritmi) m\u00e4\u00e4ratleda kui teatud funktsiooni, mis viib jaotatud s\u00fcsteemi seisundist A seisundisse B. Samuti on see seisund k\u00f5igi s\u00f5lmede poolt tunnustatud ja k\u00f5ik s\u00f5lmed saavad selle kinnitada. Kuidas selgub, on see \u00fclesanne kaugel triviaalsest, nagu esmapilgul v\u00f5ib tunduda.<\/p>\n

    Konsensuse algoritmi omadused<\/h4>\n

    \nKonsensuse algoritm peab omama kolme omadust, et s\u00fcsteem j\u00e4tkaks eksistentsi ja saavutaks mingit edasiminekut seisundi muutmisel:<\/p>\n

      \n
    1. Kokkulepe <\/b> \u2013 k\u00f5ik korralikult t\u00f6\u00f6tavad s\u00f5lmed peavad aktsepteerima sama v\u00e4\u00e4rtust (artiklites nimetatakse seda omadust sageli turvalisuse omaduseks). K\u00f5ik praegu toimivad s\u00f5lmed (mis ei ole rikki l\u00e4inud ja ei ole kaotanud \u00fchendust teistega) peavad saavutama kokkuleppe ja aktsepteerima mingit l\u00f5plikku \u00fchist v\u00e4\u00e4rtust.\n

      Siin on oluline m\u00f5ista, et k\u00e4sitletavas jaotatud s\u00fcsteemis soovivad s\u00f5lmed kokkuleppele j\u00f5uda. See t\u00e4hendab, et praegu r\u00e4\u00e4gime s\u00fcsteemidest, kus midagi v\u00f5ib lihtsalt eba\u00f5nnestuda (n\u00e4iteks m\u00f5ni s\u00f5lm v\u00f5ib eba\u00f5nnestuda), kuid selles s\u00fcsteemis ei ole s\u00f5lmi, mis t\u00f6\u00f6tavad teadlikult teiste vastu (b\u00fctsantsi kindralite probleem). Selle omaduse t\u00f5ttu j\u00e4\u00e4b s\u00fcsteem j\u00e4rjepidevaks.<\/li>\n

    2. Integriteet <\/b> \u2013 kui k\u00f5ik korralikult t\u00f6\u00f6tavad s\u00f5lmed pakuvad sama v\u00e4\u00e4rtust, v<\/b>, siis peab iga korralikult t\u00f6\u00f6tav s\u00f5lm selle v\u00e4\u00e4rtuse omaks v\u00f5tma. v<\/b>. <\/li>\n
    3. L l\u00f5pp <\/b>\u2013 k\u00f5ik korralikult t\u00f6\u00f6tavad s\u00f5lmed l\u00f5puks aktsepteerivad mingit v\u00e4\u00e4rtust (aktiivsuse omadus), mis v\u00f5imaldab algoritmil s\u00fcsteemis edasiminekut. Iga \u00fcksik korralikult t\u00f6\u00f6tav s\u00f5lm peab varem v\u00f5i hiljem aktsepteerima l\u00f5pliku v\u00e4\u00e4rtuse ja kinnitama seda: \"Minu jaoks on see v\u00e4\u00e4rtus t\u00f5ene, ma n\u00f5ustun kogu s\u00fcsteemiga.\"<\/li>\n<\/ol>\n

      <\/p>\n

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

      \nKuna algoritmi omadused v\u00f5ivad olla mitte t\u00e4ielikult arusaadavad, illustreerime n\u00e4itega, milliseid etappe l\u00e4bib lihtsaim konsensuse algoritm s\u00fcnkroonse s\u00f5numivahetuse mudelis, kus k\u00f5ik s\u00f5lmed t\u00f6\u00f6tavad nagu peab, s\u00f5numid ei kao ja midagi ei riku (kas t\u00f5esti juhtub ka nii?).<\/p>\n

        \n
      1. K\u00f5ik algab k\u00e4e ja s\u00fcdame ettepanekust (Propose). Oletame, et s\u00f5lme nimega \"S\u00f5lm 1\" on \u00fchendatud klient ja alustanud tehingut, edastades s\u00f5lmele uue v\u00e4\u00e4rtuse \u2013 O. Sellest hetkest alates nimetame \"S\u00f5lm 1\". proposer<\/b>. N\u00fc\u00fcd peab proposer \"S\u00f5lm 1\" teavitama kogu s\u00fcsteemi, et tal on v\u00e4rskeid andmeid, ja ta saadab k\u00f5igile teistele s\u00f5lmedele s\u00f5numid: \"Vaadake! Minule on tulnud v\u00e4\u00e4rtus \"O\", ja ma tahan selle salvestada! Palun kinnitage, et te salvestate ka \"O\" oma logisse.\"\n

        \"Schr\u00f6dingeri<\/li>\n

      2. J\u00e4rgmiseks staadiumiks on h\u00e4\u00e4letamine ettepaneku \u00fcle (Voting). Miks see vajalik on? V\u00f5ib juhtuda, et teistele s\u00f5lmedele on saadetud v\u00e4rskemat teavet ja neil on andmed selle sama tehingu kohta.\n

        \"Schr\u00f6dingeri
        \n
        \nKui s\u00f5lm \"S\u00f5lm 1\" saadab oma ettepaneku, kontrollivad \u00fclej\u00e4\u00e4nud s\u00f5lmed oma logides selle s\u00fcndmuse andmeid. Kui vastuolusid ei esine, kuulutavad s\u00f5lmed: \"Jah, mul ei ole selle s\u00fcndmuse kohta muid andmeid. V\u00e4\u00e4rtus \"O\" on k\u00f5ige v\u00e4rskem teave, mida me oleme saanud.\" <\/p>\n

        Mistahes muul juhul v\u00f5ivad s\u00f5lmed vastata \"S\u00f5lmele 1\": \"Kuule! Mul on selle tehingu kohta v\u00e4rskemaid andmeid. Ei ole \"O\", vaid midagi paremat.\"<\/p>\n

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

      3. Kui h\u00e4\u00e4letusvoor on l\u00e4binud edukalt ja k\u00f5ik olid \"poolt\", liigub s\u00fcsteem uude etappi \u2013 v\u00e4\u00e4rtuse aktsepteerimise (Accept). \"S\u00f5lm 1\" kogub k\u00f5ikide teiste s\u00f5lmede vastused ja teatab: \"K\u00f5ik n\u00f5ustusid v\u00e4\u00e4rtusega \"O\"! N\u00fc\u00fcd kuulutan ametlikult, et \"O\" on meie uus v\u00e4\u00e4rtus, \u00fchtne k\u00f5igile! Salvestage see oma m\u00e4rkmetesse, \u00e4rge unustage. Salvestage oma logisse!\"\n

        \"Schr\u00f6dingeri<\/li>\n

      4. Teised s\u00f5lmed saadavad kinnituse (Accepted), et nad on salvestanud v\u00e4\u00e4rtuse \"O\", midagi uut ei ole vahepeal saabunud (teatud m\u00f5ttes kahesammuline kinnitamine). P\u00e4rast seda olulist s\u00fcndmust peame jaotatud tehingu l\u00e4bituks.
        \n \"Schr\u00f6dingeri <\/li>\n<\/ol>\n

        \nNii koosneb konsensuse algoritm lihtsaimal juhul neljast sammust: propose, h\u00e4\u00e4letamine (voting), aktsepteerimine (accept), aktsepteerimise kinnitamine (accepted).<\/p>\n

        Kui m\u00f5nes etapis ei ole meil \u00f5nnestunud kokku leppida, k\u00e4ivitatakse algoritm uuesti, arvesse v\u00f5ttes teavet, mida esitavad s\u00f5lmed, kes keeldusid ettepaneku v\u00e4\u00e4rtuse kinnitamist.<\/p>\n

        Konsensusalgoritm as\u00fcnkroonsetes s\u00fcsteemis<\/h2>\n

        \nEnne seda oli k\u00f5ik sujuv, kuna jutt k\u00e4is s\u00fcnkroonsest s\u00f5numite vahetuse mudelist. Kuid me teame, et t\u00e4nap\u00e4eva maailmas oleme k\u00f5ik harjunud as\u00fcnkroonselt tegutsema. Kuidas siis sarnane algoritm t\u00f6\u00f6tab s\u00f5numite as\u00fcnkroonses vahetusmudelis, kus me arvame, et vastuse ootamine s\u00f5lme v\u00f5ib olla piiramatu (muide, s\u00f5lme rike on samuti juhul, kui s\u00f5lm v\u00f5ib vastata piiramatu aja v\u00e4ltel). <\/p>\n

        N\u00fc\u00fcd, kui 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\u00fcnkroonse s\u00f5numite mudeliga v\u00f5ivad v\u00e4lja langeda, et s\u00fcsteem saaks endiselt konsensusele j\u00f5uda?<\/p><\/blockquote>\n

        \n\u00d5ige vastus ja p\u00f5hjendus on spoileri all.<\/b>\u00d5ige vastus: 0<\/b>. Kui v\u00e4hemalt \u00fcks s\u00f5lm as\u00fcnkroonses s\u00fcsteemis v\u00e4lja langeb, ei suuda s\u00fcsteem konsensusele j\u00f5uda. Seda v\u00e4idet on t\u00f5estatud tuntud teoreemi FLP (1985, Fischer, Lynch, Paterson, original link artikli l\u00f5pus): \u00abKonsensuse saavutamise v\u00f5imatus v\u00e4hemalt \u00fche s\u00f5lme v\u00e4ljalangemise korral\u00bb.
        \n\"Schr\u00f6dingeri
        \nKallid, siis on meil probleem, oleme ju harjunud, et k\u00f5ik on as\u00fcnkroonse. Ja siin on selline olukord. Kuidas edasi elada? <\/p>\n

        Oleme just r\u00e4\u00e4kinud teooriast, matematikast. Mida t\u00e4hendab see \u00abkonsensus ei saa olla saavutatud\u00bb, t\u00f5lgituna matemaatilisest keelest meie \u2013 inseneride keelde? See t\u00e4hendab, et \u00abei pruugi alati olla saavutatud\u00bb, st on olemas olukord, kus konsensus ei ole saavutatav. Mis see olukord siis on? <\/p>\n

        See on just nimelt eluj\u00f5ulisuse omaduse rikkumine, mida \u00fclal mainiti. Meil ei ole \u00fchist kokkulepet ja s\u00fcsteem ei saa edeneda (ei saa l\u00f5ppeda kindla aja jooksul), kui meil pole vastuseid k\u00f5ikidelt s\u00f5lmedelt. Kuna as\u00fcnkroonses s\u00fcsteemis ei ole meil ettearvatavat vastusaega, ei saa me teada, kas s\u00f5lm on rikki l\u00e4inud v\u00f5i lihtsalt vastab kaua.<\/p>\n

        Kuid praktikas saame leida lahenduse. Oletame, et meie algoritm v\u00f5ib t\u00f6\u00f6tada kaua t\u00f5rgete korral (potentsiaalselt v\u00f5ib t\u00f6\u00f6tada l\u00f5pmatuses). Kuid enamikus olukordades, kui enamus s\u00f5lmi t\u00f6\u00f6tab korrektselt, saame s\u00fcsteemis edeneda. <\/p>\n

        Praktikas me tegeleme osaliselt s\u00fcnkroonsete kommunikatsioonimudelitega. Osaline s\u00fcnkroonilisus t\u00e4histab, et \u00fcldiselt on meil as\u00fcnkrooniline mudel, kuid ametlikult m\u00e4\u00e4ratakse kindlaks m\u00f5isted \u00abglobal stabilization time\u00bb teatud ajahetkest. <\/p>\n

        See ajahetk ei pruugi kesta l\u00f5putult, kuid \u00fchel p\u00e4eval peab see siiski saabuma. Virtuaalne \u00e4ratuskell heliseb ja alates sellest hetkest saame ennustada aega, mille jooksul s\u00f5numid kohale j\u00f5uavad. Sellest hetkest muutub s\u00fcsteem as\u00fcnkroonilisest s\u00fcnkroonseks. Praktikas tegeleme just selliste s\u00fcsteemidega. <\/p>\n

        Paxose algoritm lahendab konsensuse probleeme.<\/h2>\n

        \nPaxos <\/a><\/noindex> \u2013 \u044d\u0442\u043e \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0435\u0448\u0430\u044e\u0442 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u043a\u043e\u043d\u0441\u0435\u043d\u0441\u0443\u0441\u0430 \u0434\u043b\u044f \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u043e \u0441\u0438\u043d\u0445\u0440\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u043f\u0440\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0438 \u0447\u0442\u043e \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u0443\u0437\u043b\u044b \u043c\u043e\u0433\u0443\u0442 \u0432\u044b\u0445\u043e\u0434\u0438\u0442\u044c \u0438\u0437 \u0441\u0442\u0440\u043e\u044f. \u0410\u0432\u0442\u043e\u0440\u043e\u043c Paxos’\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f Leslie Lamport<\/a><\/noindex>. Ta pakkus 1989. aastal v\u00e4lja algoritmi olemasolu ja \u00f5igsuse ametliku t\u00f5estuse. <\/p>\n

        Kuid t\u00f5estamine osutus kaugel sellest, et oleks triviaalne. Esimene publikatsioon ilmus alles 1998. aastal (33 lehek\u00fclge) algoritmi kirjeldusega. Selgus, et see oli \u00e4\u00e4rmiselt keeruline m\u00f5istetavaks ja 2001. aastal avaldati artikli selgitus, mis h\u00f5lmas 14 lehek\u00fclge. Avalduste maht on toodud selleks, et n\u00e4idata, et konsensuse probleem on tegelikult v\u00e4ga keeruline ja selliste algoritmide taga on tohutu t\u00f6\u00f6 tarkade inimeste seas.<\/p>\n

        Huvitav on see, et Leslie Lamport ise m\u00e4rkis oma loengus, et teises selgitavas artiklis on \u00fcks v\u00e4ide, \u00fcks lause (mida ta ei t\u00e4psustanud), mida v\u00f5ib t\u00f5lgendada erinevalt. Selle t\u00f5ttu t\u00f6\u00f6tab suur hulk t\u00e4nap\u00e4evaseid Paxose rakendusi mitte t\u00e4iesti korrektselt. <\/p><\/blockquote>\n

        \n\u041f\u043e\u0434\u0440\u043e\u0431\u043d\u044b\u0439 \u0440\u0430\u0437\u0431\u043e\u0440 \u0440\u0430\u0431\u043e\u0442\u044b Paxos’\u0430 \u043f\u043e\u0442\u044f\u043d\u0435\u0442 \u043d\u0435 \u043d\u0430 \u043e\u0434\u043d\u0443 \u0441\u0442\u0430\u0442\u044c\u044e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u044f \u043f\u043e\u0441\u0442\u0430\u0440\u0430\u044e\u0441\u044c \u043e\u0447\u0435\u043d\u044c \u043a\u043e\u0440\u043e\u0442\u043a\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u043e\u0441\u043d\u043e\u0432\u043d\u0443\u044e \u0438\u0434\u0435\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0412 \u0441\u0441\u044b\u043b\u043a\u0430\u0445 \u0432 \u043a\u043e\u043d\u0446\u0435 \u043c\u043e\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 \u0432\u044b \u043d\u0430\u0439\u0434\u0435\u0442\u0435 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u044b \u0434\u043b\u044f \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0433\u043e \u043f\u043e\u0433\u0440\u0443\u0436\u0435\u043d\u0438\u044f \u0432 \u044d\u0442\u0443 \u0442\u0435\u043c\u0443.<\/p>\n

        Rollid Paxoses<\/h4>\n

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

          \n
        1. Proposers (v\u00f5ib kohata ka termineid: juhid v\u00f5i koordinaatorid)<\/b>Need on inimesed, kes saavad kasutajalt uut v\u00e4\u00e4rtust ja v\u00f5tavad juhtrolli. Nende \u00fclesanne on alustada vooru uue v\u00e4\u00e4rtuse esitamiseks ja koordineerida edasisi samme s\u00f5lmedes. Paxos lubab teatud olukordades mitme juhi olemasolu.<\/li>\n
        2. Aktseptorid (Valijad)<\/b>Need on s\u00f5lmed, mis h\u00e4\u00e4letavad \u00fche v\u00f5i teise v\u00e4\u00e4rtuse vastuv\u00f5tmise v\u00f5i tagasi l\u00fckkamise \u00fcle. Nende roll on v\u00e4ga oluline, sest just nemad otsustavad, millisesse olekusse (v\u00f5i mitte) s\u00fcsteem p\u00e4rast konsensusalgoritmi j\u00e4rgmist etappi liigub.<\/li>\n
        3. \u00d5ppijad<\/b>Need on s\u00f5lmed, mis lihtsalt vastu v\u00f5tavad ja salvestavad uut vastuv\u00f5etud v\u00e4\u00e4rtust, kui s\u00fcsteemi olek on muutunud. Nad ei tee otsuseid, nad lihtsalt saavad andmeid ja v\u00f5ivad neid edastada 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 meil on s\u00fcsteem, mis koosneb N<\/b> s\u00f5lmest. Ja neist v\u00f5ib maksimaalselt F<\/b> s\u00f5lme v\u00e4ljuda. Kui F s\u00f5lme v\u00e4ljuda, peab meie klastris olema v\u00e4hemalt 2F + 1<\/b> \u0443\u0437\u043b\u043e\u0432 acceptor’\u043e\u0432. <\/p>\n

          See on vajalik, et meil oleks alati, isegi halvimates olukordades, \u201ehead\u201c, korrektselt toimivad s\u00f5lmed, kes omavad enamust. See t\u00e4hendab, et meil on F + 1<\/b> \u201ehead\u201c s\u00f5lme, kes n\u00f5ustusid, ja l\u00f5plik v\u00e4\u00e4rtus v\u00f5etakse vastu. Vastupidisel juhul v\u00f5ib esineda olukord, kus erinevad kohalikud grupid aktsepteerivad erinevaid v\u00e4\u00e4rtusi ja ei suuda omavahel kokku leppida. Seet\u00f5ttu on vajalik absoluutne enamus, et h\u00e4\u00e4letuses v\u00f5ita.<\/p>\n

          Paxose konsensusalgoritmi \u00fcldine idee<\/h4>\n

          \nPaxose algoritm eeldab kahte suurt etappi, mis jagunevad omakorda kaheks sammuks:<\/p>\n

            \n
          1. Faas 1a: Valmistamine<\/b>. Eeln Preparation, esindaja (proposer) teatab k\u00f5igile s\u00f5lmedele: \"Alustame uut h\u00e4\u00e4letusfaasi. Meil on uus voor. Selle vooru number on n. N\u00fc\u00fcd hakkame h\u00e4\u00e4letama.\" Praegu teavitab ta lihtsalt uue ts\u00fckli algusest, kuid ei edasta uut v\u00e4\u00e4rtust. Selle etapi \u00fclesanne on algatada uus voor ja teavitada k\u00f5iki selle ainulaadsest numbrist. Vooru number on oluline, see peab olema suurem kui k\u00f5ik varasemad h\u00e4\u00e4letusnumbrid k\u00f5igilt varasematelt esindajatelt. Just t\u00e4nu vooru numbrile saab s\u00fcsteemi teised s\u00f5lmed aru, kui v\u00e4rsked on esindaja andmed. T\u00f5en\u00e4oliselt on teistel s\u00f5lmedel juba olemas h\u00e4\u00e4letustulemused palju hilisemast voorust ja nad lihtsalt \u00fctlevad esindajale, et ta on ajast maas.<\/li>\n
          2. Faas 1b: Lubadus<\/b>. \u041a\u043e\u0433\u0434\u0430 \u0443\u0437\u043b\u044b-acceptor’\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u043d\u043e\u043c\u0435\u0440 \u043d\u043e\u0432\u043e\u0433\u043e \u044d\u0442\u0430\u043f\u0430 \u0433\u043e\u043b\u043e\u0441\u043e\u0432\u0430\u043d\u0438\u044f, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u0434\u0432\u0430 \u0438\u0441\u0445\u043e\u0434\u0430: \n