{"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\/hu\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Schr\u00f6dinger macsk\u00e1ja doboz n\u00e9lk\u00fcl: a konszenzus probl\u00e9m\u00e1ja elosztott rendszerekben","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

K\u00e9pzelj\u00fck el. Egy szob\u00e1ban \u00f6t macska van bez\u00e1rva, \u00e9s ahhoz, hogy fel\u00e9lessz\u00e9k a gazd\u00e1t, k\u00f6z\u00f6sen kell meg\u00e1llapodniuk, hogy ezt megtegy\u00e9k, hiszen az ajt\u00f3t csak \u00f6ten nyomva tudj\u00e1k kinyitni. Ha az egyik macska Schr\u00f6dinger macsk\u00e1ja, \u00e9s a t\u00f6bbi macska nem tud a d\u00f6nt\u00e9s\u00e9r\u0151l, felmer\u00fcl a k\u00e9rd\u00e9s: \u201eHogyan tudj\u00e1k ezt megtenni?\u201d <\/p>\n

Ebben a cikkben egyszer\u0171 nyelven mes\u00e9lek a disztrib\u00faci\u00f3s rendszerek elm\u00e9leti \u00f6sszetev\u0151ir\u0151l \u00e9s ezek m\u0171k\u00f6d\u00e9si alapelveir\u0151l. Ezen k\u00edv\u00fcl felsz\u00ednesen \u00e1ttekintem a Paxos alapgondolat\u00e1t. <\/p>\n

\"Schr\u00f6dinger
\n<\/a><\/noindex>
\nAmikor a fejleszt\u0151k felh\u0151infrastrukt\u00far\u00e1kat, k\u00fcl\u00f6nb\u00f6z\u0151 adatb\u00e1zisokat haszn\u00e1lnak, nagy sz\u00e1m\u00fa csom\u00f3pont klasztereiben dolgoznak, biztosak abban, hogy az adatok integr\u00e1ltak, meg\u0151rz\u00f6ttek \u00e9s mindig hozz\u00e1f\u00e9rhet\u0151k lesznek. De honnan van ez a garancia?<\/p>\n

Val\u00f3j\u00e1ban a garanci\u00e1k, amelyek a birtokunkban vannak, a szolg\u00e1ltat\u00f3 garanci\u00e1i. Ezeket a dokument\u00e1ci\u00f3ban k\u00f6r\u00fclbel\u00fcl \u00edgy \u00edrj\u00e1k le: \u201eEz a szolg\u00e1ltat\u00e1s el\u00e9g megb\u00edzhat\u00f3, van egy megadott SLA-ja, ne agg\u00f3djon, minden \u00fagy fog m\u0171k\u00f6dni, ahogy v\u00e1rja.\u201d <\/p>\n

hajlamosak vagyunk b\u00edzni a legjobban, hiszen az okos b\u00e1csik a nagy c\u00e9gekb\u0151l megnyugtattak minket, hogy minden rendben lesz. Nem k\u00e9rdezz\u00fck meg magunkt\u00f3l: de hogy is m\u0171k\u00f6dhet egy\u00e1ltal\u00e1n ez? Vannak form\u00e1lis indokl\u00e1sok e rendszerek helyess\u00e9g\u00e9re?<\/p>\n

Nemr\u00e9giben ell\u00e1togattam a elosztott sz\u00e1m\u00edt\u00e1stechnikai iskol\u00e1ra<\/a><\/noindex> \u00e9s nagyon inspir\u00e1l\u00f3dtam a t\u00e9m\u00e1t\u00f3l. Az iskol\u00e1ban a leck\u00e9k ink\u00e1bb a matematikai anal\u00edzis \u00f3r\u00e1ra hasonl\u00edtottak, mint ami a sz\u00e1m\u00edt\u00f3g\u00e9pes rendszerekkel kapcsolatos. De pontosan \u00edgy bizony\u00edtott\u00e1k azokat a fontos algoritmusokat, amelyeket nap mint nap haszn\u00e1lunk, an\u00e9lk\u00fcl hogy tudn\u00e1nk. <\/p>\n

A legt\u00f6bb modern elosztott rendszerben a Paxos konszenzus algoritmus \u00e9s annak k\u00fcl\u00f6nf\u00e9le m\u00f3dos\u00edt\u00e1sai haszn\u00e1latosak. A legjobb az eg\u00e9szben, hogy ennek az algoritmusnak a megalapozotts\u00e1ga \u00e9s gyakorlatilag a l\u00e9tez\u00e9s\u00e9nek lehet\u0151s\u00e9ge egyszer\u0171en k\u00e9zzel \u00e9s pap\u00edrral bizony\u00edthat\u00f3. Ugyanakkor a gyakorlatban az algoritmust nagy rendszerekben alkalmazz\u00e1k, amelyek hatalmas sz\u00e1m\u00fa csom\u00f3ponton futnak a felh\u0151kben. <\/p>\n

Egy k\u00f6nnyed illusztr\u00e1ci\u00f3 arr\u00f3l, amir\u0151l a k\u00f6vetkez\u0151 r\u00e9szben sz\u00f3 lesz: a k\u00e9t t\u00e1bornok feladata<\/b>Kezdj\u00fck egy kis bemeleg\u00edt\u00e9ssel a k\u00e9t t\u00e1bornok feladat\u00e1nak elemz\u00e9s\u00e9vel<\/a><\/noindex>. <\/p>\n

K\u00e9t hadsereggel rendelkez\u00fcnk - v\u00f6r\u00f6ssel \u00e9s feh\u00e9rrel. A feh\u00e9r csapat az ostromolt v\u00e1rosban van. A v\u00f6r\u00f6s csapat A1 \u00e9s A2 t\u00e1bornokok vezet\u00e9s\u00e9vel a v\u00e1ros k\u00e9t oldal\u00e1n helyezkedik el. A v\u00f6r\u00f6s\u00f6k feladata t\u00e1madni a feh\u00e9r v\u00e1rost \u00e9s gy\u0151zni. Azonban A1 \u00e9s A2 serege egyenk\u00e9nt kisebb, mint a feh\u00e9r csapat\u00e9.<\/p>\n

\"Schr\u00f6dinger
\n
\nA v\u00f6r\u00f6s\u00f6k gy\u0151zelm\u00e9nek felt\u00e9tele: mindk\u00e9t t\u00e1bornoknak egyidej\u0171leg kell t\u00e1madnia ahhoz, hogy sz\u00e1mukra el\u0151nyt jelentsen a feh\u00e9rrel szemben. Ehhez A1-nek \u00e9s A2-nek meg kell \u00e1llapodnia egym\u00e1ssal. Ha egyenk\u00e9nt t\u00e1madnak, a v\u00f6r\u00f6s\u00f6k vesz\u00edteni fognak. <\/p>\n

A meg\u00e1llapod\u00e1s \u00e9rdek\u00e9ben A1 \u00e9s A2 t\u00e1bornokok fut\u00e1rokat k\u00fcldhetnek egym\u00e1snak a feh\u00e9r v\u00e1ros ter\u00fclet\u00e9n kereszt\u00fcl. A fut\u00e1r sikeresen eljuthat a sz\u00f6vets\u00e9ges t\u00e1bornokhoz, vagy elfoghatja az ellens\u00e9g. K\u00e9rd\u00e9s: van-e olyan kommunik\u00e1ci\u00f3s sorrend a v\u00f6r\u00f6s t\u00e1bornokok k\u00f6z\u00f6tt (a fut\u00e1rok k\u00fcld\u00e9s\u00e9nek sorrendje A1-t\u0151l A2-ig \u00e9s viszont A2-t\u0151l A1-ig), amely garant\u00e1lja, hogy meg\u00e1llapodnak a t\u00e1mad\u00e1sr\u00f3l X \u00f3rakor. Itt a garancia azt jelenti, hogy mindk\u00e9t t\u00e1bornok egy\u00e9rtelm\u0171 meger\u0151s\u00edt\u00e9st kap arr\u00f3l, hogy a sz\u00f6vets\u00e9gese (a m\u00e1sik t\u00e1bornok) bizonyosan t\u00e1mad a megadott X id\u0151pontban.<\/p>\n

Tegy\u00fck fel, hogy A1 fut\u00e1rt k\u00fcld A2-nek a k\u00f6vetkez\u0151 \u00fczenettel: 'T\u00e1madjunk ma \u00e9jf\u00e9lkor!'. A1 t\u00e1bornok nem tud t\u00e1madni A2 t\u00e1bornok meger\u0151s\u00edt\u00e9se n\u00e9lk\u00fcl. Ha A1 fut\u00e1ra eljutott, A2 t\u00e1bornok meger\u0151s\u00edt\u00e9st k\u00fcld az \u00fczenettel: 'Igen, t\u00e1madjunk ma \u00e9s gy\u0151zz\u00fck le a feh\u00e9reket'. De most A2 t\u00e1bornok nem tudja, hogy a fut\u00e1ra eljutott-e vagy sem, nincs garanci\u00e1ja arra, hogy a t\u00e1mad\u00e1s egyidej\u0171 lesz. Ez\u00e9rt A2 t\u00e1bornoknak \u00fajra meger\u0151s\u00edt\u00e9sre van sz\u00fcks\u00e9ge.<\/p>\n

Ha tov\u00e1bb r\u00e9szletezz\u00fck a kommunik\u00e1ci\u00f3jukat, kider\u00fcl, hogy b\u00e1rmennyi \u00fczenetv\u00e1lt\u00e1s k\u00f6rforg\u00e1s\u00e1nak eset\u00e9n nincs m\u00f3d arra, hogy garant\u00e1ltan \u00e9rtes\u00edts\u00fck mindk\u00e9t t\u00e1bornokot arr\u00f3l, hogy az \u00fczeneteik meg\u00e9rkeztek (figyelembe v\u00e9ve, hogy b\u00e1rmelyik fut\u00e1rt elkaphatj\u00e1k).<\/p>\n

A k\u00e9t t\u00e1bornok feladata kit\u0171n\u0151 p\u00e9ld\u00e1ja egy nagyon egyszer\u0171 elosztott rendszernek, ahol k\u00e9t csom\u00f3pont van megb\u00edzhatatlan kommunik\u00e1ci\u00f3val. Ez\u00e9rt nincs 100%-os garanci\u00e1nk arra, hogy szinkroniz\u00e1l\u00f3dnak. Az ehhez hasonl\u00f3 probl\u00e9m\u00e1kr\u00f3l egy nagyobb l\u00e9pt\u00e9k\u0171 megk\u00f6zel\u00edt\u00e9sben a cikk k\u00e9s\u0151bbi r\u00e9sz\u00e9ben lesz sz\u00f3.<\/p>\n

Bevezetj\u00fck az elosztott rendszerek fogalm\u00e1t<\/h2>\n

\nA elosztott rendszer sz\u00e1m\u00edt\u00f3g\u00e9pek csoportja (tov\u00e1bbiakban csom\u00f3pontok), amelyek k\u00e9pesek \u00fczeneteket cser\u00e9lni. Minden egyes csom\u00f3pont egy f\u00fcggetlen entit\u00e1s. A csom\u00f3pont \u00f6n\u00e1ll\u00f3an k\u00e9pes feladatokat feldolgozni, de ahhoz, hogy interakci\u00f3ba l\u00e9phessen m\u00e1s csom\u00f3pontokkal, \u00fczeneteket kell k\u00fcldenie \u00e9s fogadnia. <\/p>\n

Azt, hogy az \u00fczenetek hogyan vannak megval\u00f3s\u00edtva, milyen protokollokat haszn\u00e1lnak \u2013 ez a kontextusunkban nem \u00e9rdekes. Fontos, hogy az elosztott rendszer csom\u00f3pontjai adatokat cser\u00e9lhetnek egym\u00e1ssal \u00fczenetek k\u00fcld\u00e9s\u00e9vel.<\/p>\n

Az \u00f6n\u00e1ll\u00f3 defin\u00edci\u00f3 nem t\u0171nik t\u00fal bonyolultnak, de figyelembe kell venni, hogy az elosztott rendszernek sz\u00e1mos attrib\u00fatuma van, amelyek fontosak sz\u00e1munkra.<\/p>\n

Az elosztott rendszerek attrib\u00fatumai<\/h4>\n

<\/p>\n

    \n
  1. Versenyk\u00e9pess\u00e9g<\/b> \u2013 a rendszerben egyidej\u0171 vagy versenyk\u00e9pes esem\u00e9nyek bek\u00f6vetkez\u00e9s\u00e9nek lehet\u0151s\u00e9ge. S\u0151t, azt is felt\u00e9telezz\u00fck, hogy a k\u00e9t k\u00fcl\u00f6nb\u00f6z\u0151 csom\u00f3ponton t\u00f6rt\u00e9nt esem\u00e9nyek potenci\u00e1lisan versenyk\u00e9pesek, am\u00edg nincs vil\u00e1gos sorrendje ezeknek az esem\u00e9nyeknek. \u00c1ltal\u00e1ban ez nincs meg.<\/li>\n
  2. Glob\u00e1lis \u00f3r\u00e1k hi\u00e1nya<\/b>. Nincs vil\u00e1gos sorrend az esem\u00e9nyekben a glob\u00e1lis \u00f3r\u00e1k hi\u00e1nya miatt. A norm\u00e1lis emberi vil\u00e1gban megszoktuk, hogy vannak \u00f3r\u00e1ink \u00e9s abszol\u00fat id\u0151nk. Minden megv\u00e1ltozik, amikor elosztott rendszerekr\u0151l van sz\u00f3. M\u00e9g a szuperpontos atom\u00f3r\u00e1knak is van driftje, \u00e9s lehetnek olyan helyzetek, amikor nem tudjuk megmondani, melyik esem\u00e9ny t\u00f6rt\u00e9nt el\u0151bb. Ez\u00e9rt az id\u0151re alapozni sem tudunk.<\/li>\n
  3. A rendszer csom\u00f3pontjainak f\u00fcggetlen hib\u00e1ja<\/b>. Van m\u00e9g egy probl\u00e9ma: valami rosszul s\u00fclhet el, egyszer\u0171en az\u00e9rt, mert a csom\u00f3pontjaink nem \u00f6r\u00f6k \u00e9let\u0171ek. Meghib\u00e1sodhat a merevlemez, \u00fajraindulhat a felh\u0151ben l\u00e9v\u0151 virtu\u00e1lis g\u00e9p, a h\u00e1l\u00f3zat elmehet, \u00e9s az \u00fczenetek elveszhetnek. S\u0151t, el\u0151fordulhatnak olyan helyzetek is, amikor a csom\u00f3pontok m\u0171k\u00f6dnek, de a rendszer ellen dolgoznak. E probl\u00e9m\u00e1k utols\u00f3 oszt\u00e1lya k\u00fcl\u00f6n nevet is kapott: a biz\u00e1nci t\u00e1bornokok probl\u00e9m\u00e1ja<\/a><\/noindex>. Az ilyen probl\u00e9m\u00e1val rendelkez\u0151 elosztott rendszer legn\u00e9pszer\u0171bb p\u00e9ld\u00e1ja a Blockchain. De ma nem fogunk foglalkozni e k\u00fcl\u00f6nleges probl\u00e9m\u00e1k oszt\u00e1ly\u00e1val. Azok a helyzetek fognak \u00e9rdekelni minket, amikor egyszer\u0171en egy vagy t\u00f6bb csom\u00f3pont meghib\u00e1sodhat.<\/li>\n
  4. A csom\u00f3pontok k\u00f6z\u00f6tti kommunik\u00e1ci\u00f3s modellek (\u00fczenetv\u00e1lt\u00e1si modellek)<\/b>. M\u00e1r kider\u00edtett\u00fck, hogy a csom\u00f3pontok \u00fczenetv\u00e1lt\u00e1ssal kommunik\u00e1lnak. K\u00e9t ismert \u00fczenetv\u00e1lt\u00e1si modell l\u00e9tezik: szinkron \u00e9s aszinkron.<\/li>\n<\/ol>\n

    <\/p>\n

    A csom\u00f3pontok k\u00f6z\u00f6tti kommunik\u00e1ci\u00f3s modellek a elosztott rendszerekben<\/h4>\n

    \nSzinkron modellek<\/b> \u2013 pontosan tudjuk, hogy van egy v\u00e9gleges tiszt\u00e1zott id\u0151eltol\u00e1s, amely alatt az \u00fczenet garant\u00e1ltan eljut egy csom\u00f3pontb\u00f3l a m\u00e1sikba. Ha ez az id\u0151 lej\u00e1rt, \u00e9s az \u00fczenet nem \u00e9rkezett meg, b\u00e1tran mondhatjuk, hogy a csom\u00f3pont meghib\u00e1sodott. Ilyen modellben kisz\u00e1m\u00edthat\u00f3 v\u00e1rakoz\u00e1si id\u0151vel rendelkez\u00fcnk. <\/p>\n

    Aszinkron modellek<\/b> \u2013 az aszinkron modellekben azt felt\u00e9telezz\u00fck, hogy a v\u00e1rakoz\u00e1si id\u0151 v\u00e9ges, de nincs olyan id\u0151eltol\u00e1s, amely ut\u00e1n biztosan garant\u00e1lhatjuk, hogy a csom\u00f3pont meghib\u00e1sodott. Vagyis a v\u00e1rakoz\u00e1si id\u0151 b\u00e1rmilyen hossz\u00fa lehet. Ez egy fontos meghat\u00e1roz\u00e1s, \u00e9s err\u0151l majd tov\u00e1bb fogunk besz\u00e9lni. <\/p>\n

    A konszenzus fogalma az elosztott rendszerekben<\/h2>\n

    \nMiel\u0151tt form\u00e1lisan defini\u00e1ln\u00e1nk a konszenzus fogalm\u00e1t, n\u00e9zz\u00fcnk meg egy p\u00e9ld\u00e1t arra, hogy mikor van sz\u00fcks\u00e9g r\u00e1, nevezetesen - \u00c1llapotg\u00e9p replik\u00e1ci\u00f3<\/b>. <\/p>\n

    Van egy elosztott napl\u00f3nk. Szeretn\u00e9nk, ha konzisztens lenne, \u00e9s minden csom\u00f3ponton azonos adatok lenn\u00e9nek az elosztott rendszerben. Amikor valamelyik csom\u00f3pont \u00faj \u00e9rt\u00e9ket ismer meg, amelyet be kellene \u00edrni a napl\u00f3ba, az a feladata, hogy ezt az \u00e9rt\u00e9ket javasolja az \u00f6sszes t\u00f6bbi csom\u00f3pontnak, hogy a napl\u00f3 friss\u00fclj\u00f6n minden csom\u00f3ponton, \u00e9s a rendszer \u00faj konzisztens \u00e1llapotba l\u00e9pjen. Fontos, hogy a csom\u00f3pontok meg\u00e1llapodjanak egym\u00e1ssal: minden csom\u00f3pont egyet\u00e9rtsen az \u00faj javasolt \u00e9rt\u00e9k helyess\u00e9g\u00e9ben, minden csom\u00f3pont ezt az \u00e9rt\u00e9ket elfogadja, \u00e9s csak ebben az esetben \u00edrhatnak be az \u00faj \u00e9rt\u00e9ket a napl\u00f3ba. <\/p>\n

    M\u00e1s szavakkal: egyik csom\u00f3pont sem kifog\u00e1solta, hogy van egy aktu\u00e1lisabb inform\u00e1ci\u00f3ja, \u00e9s hogy a javasolt \u00e9rt\u00e9k hib\u00e1s. A csom\u00f3pontok k\u00f6z\u00f6tti meg\u00e1llapod\u00e1s \u00e9s az egys\u00e9gesen adott \u00e9rt\u00e9kr\u0151l alkotott egyet\u00e9rt\u00e9s jelenti a konszenzust az elosztott rendszerben. Ezt k\u00f6vet\u0151en azokr\u00f3l az algoritmusokr\u00f3l fogunk besz\u00e9lni, amelyek lehet\u0151v\u00e9 teszik az elosztott rendszer sz\u00e1m\u00e1ra, hogy garant\u00e1ltan el\u00e9rje a konszenzust.
    \n\"Schr\u00f6dinger
    \nForm\u00e1lisan a konszenzus algoritmus\u00e1t (vagy egyszer\u0171en csak konszenzus algoritmusnak) \u00fagy hat\u00e1rozhatjuk meg, mint egy funkci\u00f3t, amely egy elosztott rendszert A \u00e1llapotb\u00f3l B \u00e1llapotba vezet. Ezt az \u00e1llapotot minden csom\u00f3pont elismeri, \u00e9s minden csom\u00f3pont meg tudja er\u0151s\u00edteni. Mint kider\u00fcl, ez a feladat egy\u00e1ltal\u00e1n nem olyan trivialis, mint els\u0151 pillant\u00e1sra t\u0171nhet.<\/p>\n

    A konszenzus algoritmus tulajdons\u00e1gai<\/h4>\n

    \nA konszenzus algoritmus h\u00e1rom tulajdons\u00e1ggal kell rendelkezzen ahhoz, hogy a rendszer tov\u00e1bb l\u00e9tezzen, \u00e9s valamilyen el\u0151rehalad\u00e1st mutasson az \u00e1llapotok k\u00f6z\u00f6tti v\u00e1lt\u00e1s sor\u00e1n:<\/p>\n

      \n
    1. Meg\u00e1llapod\u00e1s <\/b> \u2013 minden helyesen m\u0171k\u00f6d\u0151 csom\u00f3pontnak ugyanazt az \u00e9rt\u00e9ket kell elfogadnia (ez a tulajdons\u00e1g a cikkekben biztons\u00e1gi tulajdons\u00e1gk\u00e9nt is megjelenik). Minden olyan csom\u00f3pont, amely jelenleg m\u0171k\u00f6dik (nem hib\u00e1sodott meg, \u00e9s nem vesz\u00edtette el a kapcsolatot a t\u00f6bbiekkel), meg kell \u00e1llapodnia, \u00e9s el kell fogadnia egy k\u00f6z\u00f6s v\u00e9gs\u0151 \u00e9rt\u00e9ket.\n

      Fontos meg\u00e9rteni, hogy a sz\u00e1munkra vizsg\u00e1lt elosztott rendszer csom\u00f3pontjai meg szeretn\u00e9nek \u00e1llapodni. Teh\u00e1t most olyan rendszerekr\u0151l besz\u00e9l\u00fcnk, ahol el\u0151fordulhat, hogy valami meghib\u00e1sodik (p\u00e9ld\u00e1ul egy csom\u00f3pont le\u00e1ll), de ebben a rendszerben nincsenek olyan csom\u00f3pontok, amelyek sz\u00e1nd\u00e9kosan dolgoznak m\u00e1sok ellen (a biz\u00e1nci t\u00e1bornokok feladata). E tulajdons\u00e1g miatt a rendszer konzisztens marad.<\/li>\n

    2. Integrit\u00e1s <\/b> \u2013 ha minden helyesen m\u0171k\u00f6d\u0151 csom\u00f3pont ugyanazt az \u00e9rt\u00e9ket javasolja v<\/b>, akkor minden helyesen m\u0171k\u00f6d\u0151 csom\u00f3pontnak el kell fogadnia ezt az \u00e9rt\u00e9ket v<\/b>. <\/li>\n
    3. Termin\u00e1ci\u00f3 <\/b>\u2013 minden helyesen m\u0171k\u00f6d\u0151 csom\u00f3pont v\u00e9g\u00fcl elfogad egy \u00e9rt\u00e9ket (\u00e9letk\u00e9pess\u00e9gi tulajdons\u00e1g), ami lehet\u0151v\u00e9 teszi, hogy az algoritmus el\u0151rehaladjon a rendszerben. Minden egyes helyesen m\u0171k\u00f6d\u0151 csom\u00f3pontnak el\u0151bb-ut\u00f3bb el kell fogadnia a v\u00e9gs\u0151 \u00e9rt\u00e9ket, \u00e9s azt meg kell er\u0151s\u00edtenie: \u201eSz\u00e1momra ez az \u00e9rt\u00e9k igaz, egyet\u00e9rtek az eg\u00e9sz rendszerrel.\u201d<\/li>\n<\/ol>\n

      <\/p>\n

      A konszenzus algoritmus m\u0171k\u00f6d\u00e9s\u00e9nek p\u00e9ld\u00e1ja<\/h4>\n

      \nMik\u00f6zben a tulajdons\u00e1gok tal\u00e1n nem teljesen vil\u00e1gosak, illusztr\u00e1ljuk egy p\u00e9ld\u00e1n kereszt\u00fcl, hogy milyen szakaszokat j\u00e1r be a legegyszer\u0171bb konszenzus algoritmus egy szinkron \u00fczenetk\u00fcld\u00e9si modellben, ahol minden csom\u00f3pont megfelel\u0151en m\u0171k\u00f6dik, az \u00fczenetek nem vesznek el \u00e9s semmi nem hib\u00e1sodik meg (t\u00e9nyleg l\u00e9tezik ilyen?).<\/p>\n

        \n
      1. Minden egy aj\u00e1nlattal kezd\u0151dik (Propose). Tegy\u00fck fel, hogy a \"1. csom\u00f3hoz\" egy kliens csatlakozott \u00e9s elkezdte a tranzakci\u00f3t, \u00e1tadva a csom\u00f3nak egy \u00faj \u00e9rt\u00e9ket \u2013 O. Ett\u0151l kezdve a \"1. csom\u00f3t\" \u00fagy h\u00edvjuk, javasol\u00f3<\/b>. Mint javasol\u00f3, a \"1. csom\u00f3nak\" most \u00e9rtes\u00edtenie kell az eg\u00e9sz rendszert arr\u00f3l, hogy friss adatai vannak, \u00e9s az \u00f6sszes t\u00f6bbi csom\u00f3nak \u00fczeneteket k\u00fcld: \u201eN\u00e9zz\u00e9tek! \u00c9rkezett hozz\u00e1m az \u201eO\u201d \u00e9rt\u00e9k, \u00e9s szeretn\u00e9m azt r\u00f6gz\u00edteni! K\u00e9rem, er\u0151s\u00edts\u00e9tek meg, hogy ti is r\u00f6gz\u00edtitek az \u201eO\u201d-t a napl\u00f3tokba.\u201d\n

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

      2. A k\u00f6vetkez\u0151 szakasz a felaj\u00e1nlott \u00e9rt\u00e9k szavaz\u00e1sa (Voting). Mire van sz\u00fcks\u00e9g r\u00e1? El\u0151fordulhat, hogy m\u00e1s csom\u00f3k frissebb inform\u00e1ci\u00f3t kaptak, \u00e9s van adom\u00e1nyunk ugyanarra a tranzakci\u00f3ra.\n

        \"Schr\u00f6dinger
        \n
        \nAmikor a \"1. csom\u00f3\" elk\u00fcldi a javaslat\u00e1t, a t\u00f6bbi csom\u00f3 ellen\u0151rzi a napl\u00f3ikban az adatokat err\u0151l az esem\u00e9nyr\u0151l. Ha nincsenek ellentmond\u00e1sok, a csom\u00f3k kihirdetik: \u201eIgen, nekem nincsenek m\u00e1s adataim ezzel az esem\u00e9nnyel kapcsolatban. Az \u201eO\u201d \u00e9rt\u00e9k a legfrissebb inform\u00e1ci\u00f3, amit kaptunk.\u201d <\/p>\n

        B\u00e1rmely m\u00e1s esetben a csom\u00f3k v\u00e1laszolhatnak a \"1. csom\u00f3nak\": \u201eFigyelj! Van nekem frissebb adatom err\u0151l a tranzakci\u00f3r\u00f3l. Nem \u201eO\u201d, hanem valami jobb.\u201d<\/p>\n

        A szavaz\u00e1si szakaszban a csom\u00f3k d\u00f6nt\u00e9sre jutnak: vagy mindenki elfogad egy \u00e9rt\u00e9ket, vagy valaki k\u00f6z\u00fcl\u00fck ellene szavaz, jelezve, hogy neki frissebb adatai vannak. <\/li>\n

      3. Ha a szavaz\u00e1si k\u00f6r sikeresen lezajlott, \u00e9s mindenki \u201eigen\u201d szavazott, a rendszer egy \u00faj szakaszba l\u00e9p \u2013 az \u00e9rt\u00e9k elfogad\u00e1sa (Accept). A \"1. csom\u00f3\" \u00f6sszegy\u0171jti a t\u00f6bbi csom\u00f3 v\u00e1laszait, \u00e9s bejelenti: \u201eMindenki egyet\u00e9rt az \u201eO\u201d \u00e9rt\u00e9kkel! Most hivatalosan bejelentem, hogy az \u201eO\u201d \u2013 a mi \u00faj, mindenki sz\u00e1m\u00e1ra egys\u00e9ges \u00e9rt\u00e9k\u00fcnk! Jegyezz\u00e9tek fel, ne felejts\u00e9tek el. R\u00f6gz\u00edts\u00e9tek a napl\u00f3tokba!\u201d\n

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

      4. A t\u00f6bbi csom\u00f3 meger\u0151s\u00edt\u00e9st k\u00fcld (Accepted), hogy r\u00f6gz\u00edtett\u00e9k az \u201eO\u201d \u00e9rt\u00e9ket, \u00e9s semmi \u00faj inform\u00e1ci\u00f3 nem \u00e9rkezett eddig (egyfajta k\u00e9tszakaszos elk\u00f6telez\u00e9s). Ezt a jelent\u0151s esem\u00e9nyt k\u00f6vet\u0151en azt tekintj\u00fck, hogy a elosztott tranzakci\u00f3 megt\u00f6rt\u00e9nt.
        \n \"Schr\u00f6dinger <\/li>\n<\/ol>\n

        \n\u00cdgy a konszenzusalgoritmus egy egyszer\u0171 esetben n\u00e9gy l\u00e9p\u00e9sb\u0151l \u00e1ll: javaslat, szavaz\u00e1s (voting), elfogad\u00e1s (accept), az elfogad\u00e1s meger\u0151s\u00edt\u00e9se (accepted).<\/p>\n

        Ha valamilyen l\u00e9p\u00e9sn\u00e9l nem tudunk konszenzusra jutni, az algoritmus \u00fajraindul, figyelembe v\u00e9ve azokat az inform\u00e1ci\u00f3kat, amelyeket a javasolt \u00e9rt\u00e9ket meger\u0151s\u00edteni nem tud\u00f3 csom\u00f3k szolg\u00e1ltatnak.<\/p>\n

        Konszenzus algoritmus aszinkron rendszerekben<\/h2>\n

        \nEddig minden sim\u00e1n ment, hiszen szinkron \u00fczenetv\u00e1lt\u00e1si modellr\u0151l volt sz\u00f3. De tudjuk, hogy a modern vil\u00e1gban mindent aszinkron m\u00f3don szoktunk csin\u00e1lni. Hogyan m\u0171k\u00f6dik akkor hasonl\u00f3 algoritmus egy aszinkron \u00fczenetv\u00e1lt\u00e1si modell\u0171 rendszerben, ahol azt felt\u00e9telezz\u00fck, hogy a v\u00e1laszra val\u00f3 v\u00e1rakoz\u00e1s ideje tetsz\u0151legesen hossz\u00fa lehet (p\u00e9ld\u00e1ul egy csom\u00f3pont meghib\u00e1sod\u00e1sa is lehet olyan eset, amikor a csom\u00f3pont b\u00e1rmennyire hossz\u00fa ideig nem v\u00e1laszol). <\/p>\n

        Most, hogy tudjuk, hogyan m\u0171k\u00f6dik elvileg a konszenzus algoritmus, k\u00e9rd\u00e9s azokhoz a k\u00edv\u00e1ncsi olvas\u00f3khoz, akik ideig eljutottak: h\u00e1ny csom\u00f3pont lehet a N csom\u00f3pontb\u00f3l \u00e1ll\u00f3 rendszerben, amely kiv\u00e1lhat ahhoz, hogy a rendszer m\u00e9g mindig el\u00e9rhesse a konszenzust?<\/p><\/blockquote>\n

        \nA helyes v\u00e1lasz \u00e9s az indokl\u00e1s a spoiler m\u00f6g\u00f6tt.<\/b>A helyes v\u00e1lasz: 0<\/b>. Ha legal\u00e1bb egy csom\u00f3pont meghib\u00e1sodik az aszinkron rendszerben, a rendszer nem tud el\u00e9rni konszenzust. Ezt az \u00e1ll\u00edt\u00e1st bizony\u00edtja a neves FLP-t\u00e9tel (1985, Fischer, Lynch, Paterson, az eredeti hivatkoz\u00e1s a cikk v\u00e9g\u00e9n): \"A megosztott konszenzus el\u00e9rhetetlens\u00e9ge legal\u00e1bb egy csom\u00f3pont meghib\u00e1sod\u00e1sakor\".
        \n\"Schr\u00f6dinger
        \nNos, akkor probl\u00e9m\u00e1nk van, hiszen megszoktuk, hogy minden aszinkron. Most mi lesz? Hogyan tov\u00e1bb? <\/p>\n

        Most a te\u00f3ri\u00e1r\u00f3l, a matematik\u00e1r\u00f3l besz\u00e9lt\u00fcnk. Mit jelent, hogy \u201ea konszenzus nem \u00e9rhet\u0151 el\u201d, ha matematikai nyelvr\u0151l a mi m\u00e9rn\u00f6ki nyelv\u00fcnkre ford\u00edtunk? Ez azt jelenti, hogy \u201enem mindig \u00e9rhet\u0151 el\u201d, azaz l\u00e9tezik olyan eset, amikor a konszenzus nem \u00e9rhet\u0151 el. Mi lenne ez az eset? <\/p>\n

        Ez \u00e9ppen a kor\u00e1bban eml\u00edtett liveness property megs\u00e9rt\u00e9se. Nincs k\u00f6z\u00f6s egyet\u00e9rt\u00e9s, \u00e9s a rendszer nem k\u00e9pes el\u0151rehaladni (nem tud a v\u00e9ges id\u0151n bel\u00fcl befejez\u0151dni), ha nincs v\u00e1lasz minden csom\u00f3pontt\u00f3l. Mert aszinkron rendszerben nincs kisz\u00e1m\u00edthat\u00f3 v\u00e1laszid\u0151, \u00e9s nem tudjuk, hogy a csom\u00f3pont meghib\u00e1sodott, vagy egyszer\u0171en csak lassan v\u00e1laszol.<\/p>\n

        De a gyakorlatban tal\u00e1lhatunk megold\u00e1st. Legyen a algoritmusunk k\u00e9pes hossz\u00fa ideig m\u0171k\u00f6dni meghib\u00e1sod\u00e1sok eset\u00e9n (potenci\u00e1lisan v\u00e9gtelen ideig m\u0171k\u00f6dhet). De a legt\u00f6bb helyzetben, amikor a legt\u00f6bb csom\u00f3pont megfelel\u0151en m\u0171k\u00f6dik, el\u0151rehalad\u00e1st fogunk el\u00e9rni a rendszerben. <\/p>\n

        A gyakorlatban r\u00e9szben szinkron kommunik\u00e1ci\u00f3s modellekkel foglalkozunk. A r\u00e9szleges szinkronit\u00e1st \u00fagy \u00e9rtj\u00fck, hogy \u00e1ltal\u00e1noss\u00e1gban van egy aszinkron modell\u00fcnk, de form\u00e1lisan bevezetj\u00fck a \"glob\u00e1lis stabiliz\u00e1ci\u00f3s id\u0151\" fogalm\u00e1t egy adott pillanatra vonatkoz\u00f3an. <\/p>\n

        Ez a pillanat b\u00e1rmennyi ideig elmaradhat, de egyszer el kell j\u00f6nnie. Megsz\u00f3lal egy virtu\u00e1lis \u00e9breszt\u0151\u00f3ra, \u00e9s ett\u0151l a pillanatt\u00f3l kezdve meg tudjuk j\u00f3solni az id\u0151delta-t, amely alatt az \u00fczenetek meg\u00e9rkeznek. Ett\u0151l a pillanatt\u00f3l a rendszer aszinkronb\u00f3l szinkronba v\u00e1lt. A gyakorlatban pontosan ilyen rendszerekkel foglalkozunk. <\/p>\n

        A Paxos algoritmus megoldja a konszenzus probl\u00e9m\u00e1it.<\/h2>\n

        \nPaxos <\/a><\/noindex> \u2013 ez egy algoritmuscsal\u00e1d, amely a konszenzus probl\u00e9m\u00e1j\u00e1t oldja meg r\u00e9szben szinkroniz\u00e1lt rendszerekben, felt\u00e9ve, hogy egyes csom\u00f3pontok meghib\u00e1sodhatnak. A Paxos szerz\u0151je Leslie Lamport<\/a><\/noindex>. \u0150 1989-ben form\u00e1lis bizony\u00edt\u00e9kot javasolt a algoritmus l\u00e9tez\u00e9s\u00e9re \u00e9s helyess\u00e9g\u00e9re. <\/p>\n

        De a bizony\u00edt\u00e1s nem volt \u00e9ppen trivi\u00e1lis. Az els\u0151 publik\u00e1ci\u00f3 csak 1998-ban jelent meg (33 oldal) az algoritmus le\u00edr\u00e1s\u00e1val. Kider\u00fclt, hogy rendk\u00edv\u00fcl nehezen \u00e9rthet\u0151 volt, \u00e9s 2001-ben megjelent egy k\u00eds\u00e9r\u0151 cikk, amely 14 oldalon kereszt\u00fcl magyar\u00e1zta az eredeti \u00edr\u00e1st. A publik\u00e1ci\u00f3k terjedelm\u00e9t az\u00e9rt eml\u00edtj\u00fck, hogy bemutassuk, val\u00f3j\u00e1ban a konszenzus probl\u00e9m\u00e1ja nem annyira egyszer\u0171, \u00e9s ilyen algoritmusok m\u00f6g\u00f6tt \u00f3ri\u00e1si munka \u00e1ll az okos emberek r\u00e9sz\u00e9r\u0151l.<\/p>\n

        \u00c9rdekes, hogy mag\u00e1t Leslie Lamportot az el\u0151ad\u00e1s\u00e1ban megjegyezte, hogy a m\u00e1sodik k\u00eds\u00e9r\u0151 cikkben van egy olyan \u00e1ll\u00edt\u00e1s, egy mondat (nem pontos\u00edtotta, melyik), amelyet k\u00fcl\u00f6nb\u00f6z\u0151en lehet \u00e9rtelmezni. \u00c9s emiatt sok modern Paxos megval\u00f3s\u00edt\u00e1s nem m\u0171k\u00f6dik teljesen helyesen. <\/p><\/blockquote>\n

        \nA Paxos m\u0171k\u00f6d\u00e9s\u00e9nek r\u00e9szletes elemz\u00e9se nem egy cikk t\u00e9m\u00e1ja, ez\u00e9rt megpr\u00f3b\u00e1lom nagyon r\u00f6viden \u00e1tadni az algoritmus alapgondolat\u00e1t. A cikkem v\u00e9g\u00e9n tal\u00e1lhat\u00f3k a tov\u00e1bbi elm\u00e9ly\u00fcl\u00e9shez sz\u00fcks\u00e9ges anyagok.<\/p>\n

        Szerepek a Paxosban<\/h4>\n

        \nA Paxos algoritmusban l\u00e9teznek szerepek. Tekints\u00fck a h\u00e1rom alapvet\u0151 szerepet (vannak m\u00f3dos\u00edt\u00e1sok tov\u00e1bbi szerepekkel):<\/p>\n

          \n
        1. Javasl\u00f3k (m\u00e1s kifejez\u00e9sek: vezet\u0151k vagy koordin\u00e1torok)<\/b>. Ezek olyan emberek, akik \u00faj jelent\u00e9st tanulnak a felhaszn\u00e1l\u00f3t\u00f3l, \u00e9s \u00e1tv\u00e1llalj\u00e1k a vezet\u0151 szerepet. Feladatuk, hogy elind\u00edts\u00e1k az \u00faj jelent\u00e9s javaslati k\u00f6r\u00e9t \u00e9s koordin\u00e1lj\u00e1k a csom\u00f3pontok tov\u00e1bbi tev\u00e9kenys\u00e9geit. A Paxos lehet\u0151v\u00e9 teszi, hogy bizonyos helyzetekben t\u00f6bb vezet\u0151 is legyen.<\/li>\n
        2. Elfogad\u00f3k (Szavaz\u00f3k)<\/b>. Ezek olyan csom\u00f3pontok, amelyek szavaznak egy adott \u00e9rt\u00e9k elfogad\u00e1s\u00e1ra vagy elutas\u00edt\u00e1s\u00e1ra. Szerep\u00fck nagyon fontos, mert rajtuk m\u00falik a d\u00f6nt\u00e9s, hogy a rendszer melyik \u00e1llapotba l\u00e9p (vagy nem l\u00e9p) a konszenzus algoritmus k\u00f6vetkez\u0151 f\u00e1zis\u00e1ban.<\/li>\n
        3. Tanul\u00f3k<\/b>. Olyan csom\u00f3pontok, amelyek egyszer\u0171en elfogadj\u00e1k \u00e9s r\u00f6gz\u00edtik az \u00faj elfogadott \u00e9rt\u00e9ket, amikor a rendszer \u00e1llapota megv\u00e1ltozik. \u0150k nem hoznak d\u00f6nt\u00e9seket, csak adatokat kapnak \u00e9s \u00e1tadhatj\u00e1k azokat a v\u00e9gfelhaszn\u00e1l\u00f3nak. <\/li>\n<\/ol>\n

          \nEgy csom\u00f3pont t\u00f6bb szerepet is bet\u00f6lthet k\u00fcl\u00f6nb\u00f6z\u0151 helyzetekben. <\/p>\n

          A kv\u00f3rum fogalma<\/h4>\n

          \nFelt\u00e9telezz\u00fck, hogy van egy N<\/b> csom\u00f3pontb\u00f3l \u00e1ll\u00f3 rendszer\u00fcnk. Ezek k\u00f6z\u00fcl legfeljebb F<\/b> csom\u00f3pont hib\u00e1sodhat meg. Ha F csom\u00f3pont elromlik, akkor a klaszter\u00fcnkben legal\u00e1bb 2F + 1<\/b> acceptor csom\u00f3pontok. <\/p>\n

          Ez sz\u00fcks\u00e9ges ahhoz, hogy mindig, m\u00e9g a legrosszabb helyzetben is a \"j\u00f3\", helyesen m\u0171k\u00f6d\u0151 csom\u00f3pontok t\u00f6bbs\u00e9ge legyen. Vagyis F + 1<\/b> \"j\u00f3\" csom\u00f3pont, amely elfogadta, \u00e9s a v\u00e9gs\u0151 \u00e9rt\u00e9k elfogad\u00e1sra ker\u00fcl. Ellenkez\u0151 esetben el\u0151fordulhat, hogy k\u00fcl\u00f6nb\u00f6z\u0151 helyi csoportok elt\u00e9r\u0151 \u00e9rt\u00e9keket fogadnak el, \u00e9s nem tudnak egym\u00e1ssal megegyezni. Ez\u00e9rt abszol\u00fat t\u00f6bbs\u00e9gre van sz\u00fcks\u00e9g\u00fcnk a szavaz\u00e1s megnyer\u00e9s\u00e9hez.<\/p>\n

          A Paxos konszenzus algoritmus munk\u00e1j\u00e1nak \u00e1ltal\u00e1nos elk\u00e9pzel\u00e9se<\/h4>\n

          \nA Paxos algoritmus k\u00e9t nagy f\u00e1zist felt\u00e9telez, amelyeket mindkett\u0151t k\u00e9t l\u00e9p\u00e9sre bontanak:<\/p>\n

            \n
          1. 1. f\u00e1zis: El\u0151k\u00e9sz\u00edt\u00e9s<\/b>. A felk\u00e9sz\u00fcl\u00e9si szakaszban a vezet\u0151 (proposer) \u00e9rtes\u00edti az \u00f6sszes csom\u00f3pontot: \u201e\u00daj szavaz\u00e1si szakaszt kezd\u00fcnk. Van egy \u00faj fordul\u00f3. Ennek a fordul\u00f3nak a sz\u00e1ma \u2013 n. Most elkezdj\u00fck a szavaz\u00e1st.\u201d Jelenleg csak a \u00faj ciklus kezdet\u00e9r\u0151l t\u00e1j\u00e9koztat, de nem k\u00f6zli az \u00faj \u00e9rt\u00e9ket. Ennek a szakasznak a feladata, hogy kezdem\u00e9nyezzen egy \u00faj fordul\u00f3t \u00e9s \u00e9rtes\u00edtse mindenkit a saj\u00e1t egyedi sz\u00e1m\u00e1r\u00f3l. A fordul\u00f3sz\u00e1m fontos, ez egy olyan \u00e9rt\u00e9k, amely nagyobb kell, hogy legyen minden kor\u00e1bbi szavaz\u00e1si sz\u00e1mn\u00e1l, amelyet a kor\u00e1bbi vezet\u0151k bonyol\u00edtottak. \u00c9ppen a fordul\u00f3sz\u00e1m miatt tudj\u00e1k a rendszer m\u00e1s csom\u00f3pontjai, hogy a vezet\u0151 adatai mennyire frissek. Val\u00f3sz\u00edn\u0171, hogy m\u00e1s csom\u00f3pontoknak m\u00e1r vannak szavaz\u00e1si eredm\u00e9nyei sokkal k\u00e9s\u0151bbi fordul\u00f3kb\u00f3l, \u00e9s egyszer\u0171en k\u00f6zlik a vezet\u0151vel, hogy lemaradt.<\/li>\n
          2. 1b. f\u00e1zis: \u00cdg\u00e9ret<\/b>. Amikor az acceptor csom\u00f3pontok megkapt\u00e1k az \u00faj szavaz\u00e1si szakasz sz\u00e1m\u00e1t, k\u00e9t kimenetel lehets\u00e9ges: \n