{"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\/pl\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Kot Schr\u00f6dingera bez pude\u0142ka: problem konsensusu w rozproszonych systemach","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Wyobra\u017amy sobie. W pokoju jest 5 kot\u00f3w zamkni\u0119tych, i aby obudzi\u0107 swojego w\u0142a\u015bciciela, musz\u0105 si\u0119 wszyscy razem porozumie\u0107, poniewa\u017c drzwi mog\u0105 otworzy\u0107 tylko pi\u0119cioro z nich opieraj\u0105c si\u0119 na nich. Je\u015bli jeden z kot\u00f3w to kot Schrodingera, a pozosta\u0142e koty nie wiedz\u0105 o jego decyzji, pojawia si\u0119 pytanie: \u201eJak mog\u0105 to zrobi\u0107?\u201d <\/p>\n

W tym artykule w przyst\u0119pny spos\u00f3b om\u00f3wi\u0119 teoretyczne podstawy \u015bwiata system\u00f3w rozproszonych oraz zasady ich dzia\u0142ania. Zajm\u0119 si\u0119 tak\u017ce powierzchownie g\u0142\u00f3wn\u0105 ide\u0105 le\u017c\u0105c\u0105 u podstaw Paxosa. <\/p>\n

\"Kot
\n<\/a><\/noindex>
\nKiedy programi\u015bci korzystaj\u0105 z chmur obliczeniowych, r\u00f3\u017cnych baz danych i pracuj\u0105 w klastrach z du\u017c\u0105 liczb\u0105 w\u0119z\u0142\u00f3w, s\u0105 pewni, \u017ce dane b\u0119d\u0105 integralne, bezpieczne i zawsze dost\u0119pne. Ale sk\u0105d te gwarancje?<\/p>\n

W zasadzie gwarancje, kt\u00f3re mamy, to gwarancje dostawcy. S\u0105 one opisane w dokumentacji mniej wi\u0119cej w ten spos\u00f3b: \u201eTa us\u0142uga jest wystarczaj\u0105co niezawodna, ma okre\u015blony SLA, nie martw si\u0119, wszystko b\u0119dzie dzia\u0142a\u0107 rozproszono tak, jak oczekujesz.\u201d <\/p>\n

Mamy tendencj\u0119 do wiary w to, co najlepsze, poniewa\u017c m\u0105drzy panowie z du\u017cych firm zapewniali nas, \u017ce wszystko b\u0119dzie w porz\u0105dku. Nie zadajemy sobie pytania: a dlaczego w\u0142a\u015bciwie to mo\u017ce dzia\u0142a\u0107? Czy istnieje jakie\u015b formalne uzasadnienie poprawno\u015bci dzia\u0142ania takich system\u00f3w?<\/p>\n

Niedawno by\u0142em na szkole dotycz\u0105cej oblicze\u0144 rozproszonych<\/a><\/noindex> i bardzo mnie zainspirowa\u0142a ta tematyka. Wyk\u0142ady w szkole przypomina\u0142y bardziej zaj\u0119cia z analizy matematycznej ni\u017c co\u015b zwi\u0105zanego z systemami komputerowymi. Jednak w\u0142a\u015bnie w ten spos\u00f3b udowadniano najwa\u017cniejsze algorytmy, z kt\u00f3rych korzystamy na co dzie\u0144, nawet o tym nie wiedz\u0105c. <\/p>\n

W wi\u0119kszo\u015bci nowoczesnych system\u00f3w rozproszonych stosuje si\u0119 algorytm konsensusu Paxos i jego r\u00f3\u017cne modyfikacje. Najlepsze jest to, \u017ce zasady oraz sama mo\u017cliwo\u015b\u0107 istnienia tego algorytmu mog\u0105 by\u0107 udowodnione po prostu za pomoc\u0105 d\u0142ugopisu i kartki. Jednocze\u015bnie w praktyce algorytm ten stosuje si\u0119 w du\u017cych systemach dzia\u0142aj\u0105cych na ogromnej liczbie w\u0119z\u0142\u00f3w w chmurach. <\/p>\n

Lekkie zobrazowanie tego, o czym b\u0119dzie mowa dalej: problem dw\u00f3ch genera\u0142\u00f3w<\/b>Rozpocznijmy rozgrzewk\u0119 od analizy problemu dw\u00f3ch genera\u0142\u00f3w<\/a><\/noindex>. <\/p>\n

Mamy dwie armie - rud\u0105 i bia\u0142\u0105. Bia\u0142e wojska stacjonuj\u0105 w obl\u0119\u017conym mie\u015bcie. Rud\u0105 armi\u0105 dowodz\u0105 genera\u0142owie A1 i A2, kt\u00f3rzy znajduj\u0105 si\u0119 po dw\u00f3ch stronach miasta. Zadaniem rudych jest zaatakowa\u0107 bia\u0142e miasto i zwyci\u0119\u017cy\u0107. Jednak\u017ce armia ka\u017cdego rudego genera\u0142a jest mniejsza od bia\u0142ych.<\/p>\n

\"Kot
\n
\nWarunki zwyci\u0119stwa dla rudych: obaj genera\u0142owie musz\u0105 zaatakowa\u0107 jednocze\u015bnie, aby mie\u0107 przewag\u0119 liczebn\u0105 nad bia\u0142ymi. W tym celu genera\u0142owie A1 i A2 musz\u0105 si\u0119 ze sob\u0105 porozumie\u0107. Je\u015bli ka\u017cdy zaatakuje osobno, rudzi przegraj\u0105. <\/p>\n

Aby si\u0119 porozumie\u0107, genera\u0142owie A1 i A2 mog\u0105 wysy\u0142a\u0107 do siebie pos\u0142a\u0144c\u00f3w przez terytorium bia\u0142ego miasta. Pos\u0142aniec mo\u017ce dotrze\u0107 z powodzeniem do sojuszniczego genera\u0142a lub mo\u017ce zosta\u0107 przechwycony przez przeciwnika. Pytanie: czy istnieje taka sekwencja komunikacji mi\u0119dzy rudymi genera\u0142ami (sekwencja wysy\u0142ania pos\u0142a\u0144c\u00f3w od A1 do A2 i z powrotem od A2 do A1), w kt\u00f3rej oni gwarantuj\u0105 sobie porozumienie o ataku o godzinie X? Tutaj przez gwarancje rozumiemy, \u017ce obaj genera\u0142owie b\u0119d\u0105 mieli jednoznaczne potwierdzenie, \u017ce sojusznik (drugi genera\u0142) na pewno zaatakuje o ustalonej godzinie X.<\/p>\n

Za\u0142\u00f3\u017cmy, \u017ce A1 wysy\u0142a pos\u0142a\u0144ca do A2 z wiadomo\u015bci\u0105: 'Zaatakujmy dzisiaj o p\u00f3\u0142nocy!'. Genera\u0142 A1 nie mo\u017ce zaatakowa\u0107 bez potwierdzenia od genera\u0142a A2. Je\u015bli pos\u0142aniec od A1 dotar\u0142, genera\u0142 A2 wysy\u0142a potwierdzenie z wiadomo\u015bci\u0105: 'Tak, zaatakujmy dzi\u015b bia\u0142ych'. Ale teraz genera\u0142 A2 nie wie, czy jego pos\u0142aniec dotar\u0142, nie ma gwarancji, czy atak b\u0119dzie jednoczesny. Teraz genera\u0142 A2 znowu potrzebuje potwierdzenia.<\/p>\n

Je\u015bli dalej rozpisywa\u0107 ich komunikacj\u0119, oka\u017ce si\u0119, \u017ce niezale\u017cnie od liczby cykli wymiany wiadomo\u015bci, nie ma sposobu, aby gwarantowa\u0107 obojgu genera\u0142om, \u017ce ich wiadomo\u015bci zosta\u0142y odebrane (zak\u0142adaj\u0105c, \u017ce jakikolwiek z pos\u0142a\u0144c\u00f3w mo\u017ce by\u0107 przechwycony).<\/p>\n

Zadanie dw\u00f3ch genera\u0142\u00f3w jest doskona\u0142\u0105 ilustracj\u0105 bardzo prostej rozproszonej systemu, gdzie s\u0105 dwa w\u0119z\u0142y z niezawodn\u0105 komunikacj\u0105. Oznacza to, \u017ce nie mamy 100% gwarancji, \u017ce si\u0119 zsynchronizuj\u0105. O podobnych problemach, ale w szerszej skali, mowa dalej w artykule.<\/p>\n

Wprowadzamy poj\u0119cie system\u00f3w rozproszonych<\/h2>\n

\nRozproszony system to grupa komputer\u00f3w (w dalszej cz\u0119\u015bci b\u0119dziemy nazywa\u0107 je w\u0119z\u0142ami), kt\u00f3re mog\u0105 wymienia\u0107 si\u0119 wiadomo\u015bciami. Ka\u017cdy pojedynczy w\u0119ze\u0142 to autonomiczna jednostka. W\u0119ze\u0142 mo\u017ce samodzielnie przetwarza\u0107 zadania, ale aby wsp\u00f3\u0142pracowa\u0107 z innymi w\u0119z\u0142ami, musi wysy\u0142a\u0107 i odbiera\u0107 wiadomo\u015bci. <\/p>\n

Jak dok\u0142adnie s\u0105 realizowane wiadomo\u015bci, jakie protoko\u0142y s\u0105 u\u017cywane \u2013 to nie interesuje nas w tym kontek\u015bcie. Wa\u017cne jest to, \u017ce w\u0119z\u0142y rozproszonego systemu mog\u0105 wymienia\u0107 si\u0119 danymi, wysy\u0142aj\u0105c wiadomo\u015bci mi\u0119dzy sob\u0105.<\/p>\n

Samo okre\u015blenie wydaje si\u0119 do\u015b\u0107 proste, ale nale\u017cy uwzgl\u0119dni\u0107, \u017ce rozproszony system ma szereg atrybut\u00f3w, kt\u00f3re b\u0119d\u0105 dla nas istotne.<\/p>\n

Atrybuty system\u00f3w rozproszonych<\/h4>\n

<\/p>\n

    \n
  1. Zdarzenia wsp\u00f3\u0142bie\u017cne<\/b> \u2013 mo\u017cliwo\u015b\u0107 wyst\u0105pienia jednoczesnych lub konkurencyjnych zdarze\u0144 w systemie. Co wi\u0119cej, b\u0119dziemy uwa\u017ca\u0107, \u017ce zdarzenia, kt\u00f3re mia\u0142y miejsce na dw\u00f3ch r\u00f3\u017cnych w\u0119z\u0142ach, s\u0105 potencjalnie konkurencyjne, dop\u00f3ki nie mamy jasnej kolejno\u015bci wyst\u0119powania tych zdarze\u0144. A zazwyczaj takiej kolejno\u015bci nie mamy.<\/li>\n
  2. Brak globalnego zegara<\/b>. Nie mamy jasnej kolejno\u015bci zdarze\u0144 z powodu braku globalnego zegara. W zwyk\u0142ym \u015bwiecie ludzkim jeste\u015bmy przyzwyczajeni do posiadania zegar\u00f3w i absolutnego czasu. Wszystko zmienia si\u0119, gdy m\u00f3wimy o systemach rozproszonych. Nawet najbardziej precyzyjne zegary atomowe maj\u0105 dryft i mog\u0105 wyst\u0105pi\u0107 sytuacje, w kt\u00f3rych nie mo\u017cemy stwierdzi\u0107, kt\u00f3re z dw\u00f3ch zdarze\u0144 mia\u0142o miejsce wcze\u015bniej. Dlatego te\u017c nie mo\u017cemy polega\u0107 na czasie.<\/li>\n
  3. Niezale\u017cna awaria w\u0119z\u0142\u00f3w systemu<\/b>. Jest jeszcze jeden problem: co\u015b mo\u017ce p\u00f3j\u015b\u0107 nie tak po prostu dlatego, \u017ce nasze w\u0119z\u0142y nie s\u0105 wieczne. Dysk twardy mo\u017ce ulec awarii, wirtualna maszyna w chmurze mo\u017ce si\u0119 zrestartowa\u0107, sie\u0107 mo\u017ce na chwil\u0119 znikn\u0105\u0107 i wiadomo\u015bci mog\u0105 zosta\u0107 utracone. Co wi\u0119cej, mog\u0105 wyst\u0105pi\u0107 sytuacje, w kt\u00f3rych w\u0119z\u0142y dzia\u0142aj\u0105, ale dzia\u0142aj\u0105 przeciwko systemowi. Ostatnia klasa problem\u00f3w zyska\u0142a nawet osobn\u0105 nazw\u0119: problem bizantyjskich genera\u0142\u00f3w<\/a><\/noindex>. Najbardziej znanym przyk\u0142adem systemu rozproszonego z takim problemem jest Blockchain. Jednak dzi\u015b nie b\u0119dziemy rozpatrywa\u0107 tej szczeg\u00f3lnej klasy problem\u00f3w. Nas b\u0119d\u0105 interesowa\u0107 sytuacje, w kt\u00f3rych po prostu jeden lub kilka w\u0119z\u0142\u00f3w mog\u0105 ulega\u0107 awarii.<\/li>\n
  4. Modele komunikacji (modele wymiany wiadomo\u015bci) mi\u0119dzy w\u0119z\u0142ami<\/b>. Ju\u017c ustalili\u015bmy, \u017ce w\u0119z\u0142y komunikuj\u0105 si\u0119 poprzez wymian\u0119 wiadomo\u015bci. Istniej\u0105 dwa znane modele wymiany wiadomo\u015bci: synchroniczny i asynchroniczny.<\/li>\n<\/ol>\n

    <\/p>\n

    Modele komunikacji mi\u0119dzy w\u0119z\u0142ami w systemach rozproszonych<\/h4>\n

    \nModel synchroniczny<\/b> \u2013 dok\u0142adnie wiemy, \u017ce istnieje pewna znana delta czasu, w ci\u0105gu kt\u00f3rej wiadomo\u015b\u0107 gwarantowanie dociera od jednego w\u0119z\u0142a do drugiego. Je\u015bli ten czas minie, a wiadomo\u015b\u0107 nie dotrze, mo\u017cemy \u015bmia\u0142o powiedzie\u0107, \u017ce w\u0119ze\u0142 jest uszkodzony. W takim modelu mamy przewidywalny czas oczekiwania. <\/p>\n

    Model asynchroniczny<\/b> \u2013 w modelach asynchronicznych zak\u0142adamy, \u017ce czas oczekiwania jest ograniczony, ale nie istnieje taka delta czasu, po kt\u00f3rej mo\u017cna gwarantowa\u0107, \u017ce w\u0119ze\u0142 jest uszkodzony. Tzn. czas oczekiwania na wiadomo\u015b\u0107 od w\u0119z\u0142a mo\u017ce by\u0107 dowolnie d\u0142ugi. To wa\u017cna definicja, o kt\u00f3rej b\u0119dziemy rozmawia\u0107 dalej. <\/p>\n

    Poj\u0119cie konsensusu w systemach rozproszonych<\/h2>\n

    \nZanim formalnie zdefiniujemy poj\u0119cie konsensusu, rozwa\u017cmy przyk\u0142ad sytuacji, w kt\u00f3rej jest on nam potrzebny, a mianowicie \u2013 Replikacja maszyny stanowej<\/b>. <\/p>\n

    Mamy pewien rozproszony dziennik. Chcieliby\u015bmy, aby by\u0142 on sp\u00f3jny i zawiera\u0142 identyczne dane na wszystkich w\u0119z\u0142ach systemu rozproszonego. Kiedy kt\u00f3ry\u015b z w\u0119z\u0142\u00f3w dowiaduje si\u0119 o nowej warto\u015bci, kt\u00f3r\u0105 zamierza zapisa\u0107 w dzienniku, jego zadaniem staje si\u0119 zaproponowanie tej warto\u015bci wszystkim pozosta\u0142ym w\u0119z\u0142om, aby dziennik zosta\u0142 zaktualizowany na wszystkich w\u0119z\u0142ach, a system przeszed\u0142 w nowe sp\u00f3jne estado. Przy tym wa\u017cne jest, aby w\u0119z\u0142y uzgodni\u0142y ze sob\u0105: wszystkie w\u0119z\u0142y zgodzi\u0142y si\u0119, \u017ce zaproponowana nowa warto\u015b\u0107 jest poprawna, wszystkie w\u0119z\u0142y t\u0119 warto\u015b\u0107 przyj\u0119\u0142y, i tylko w takim przypadku wszystkie mog\u0105 zapisa\u0107 now\u0105 warto\u015b\u0107 w dzienniku. <\/p>\n

    Innymi s\u0142owy: \u017caden z w\u0119z\u0142\u00f3w nie zaprotestowa\u0142, \u017ce ma bardziej aktualne informacje, a proponowana warto\u015b\u0107 jest b\u0142\u0119dna. Uzgodnienie mi\u0119dzy w\u0119z\u0142ami i zgoda co do jednej poprawnie przyj\u0119tej warto\u015bci to konsensus w systemie rozproszonym. Nast\u0119pnie b\u0119dziemy m\u00f3wi\u0107 o algorytmach, kt\u00f3re pozwalaj\u0105 systemowi rozproszonemu na gwarantowane osi\u0105gni\u0119cie konsensusu.
    \n\"Kot
    \nBardziej formalnie mo\u017cemy okre\u015bli\u0107 algorytm osi\u0105gania konsensusu (lub po prostu algorytm konsensusu) jako funkcj\u0119, kt\u00f3ra przekszta\u0142ca rozproszony system ze stanu A w stan B. Przy czym ten stan jest akceptowany przez wszystkie w\u0119z\u0142y, a wszystkie w\u0119z\u0142y mog\u0105 go potwierdzi\u0107. Jak si\u0119 okazuje, zadanie to wcale nie jest tak trywialne, jak mog\u0142oby si\u0119 wydawa\u0107 na pierwszy rzut oka.<\/p>\n

    W\u0142a\u015bciwo\u015bci algorytmu konsensusu<\/h4>\n

    \nAlgorytm konsensusu musi mie\u0107 trzy w\u0142a\u015bciwo\u015bci, aby system m\u00f3g\u0142 istnie\u0107 i odnosi\u0107 jaki\u015b post\u0119p w przechodzeniu z jednego stanu do drugiego:<\/p>\n

      \n
    1. Zgoda <\/b> \u2013 wszystkie poprawnie dzia\u0142aj\u0105ce w\u0119z\u0142y musz\u0105 przyj\u0105\u0107 t\u0119 sam\u0105 warto\u015b\u0107 (w artyku\u0142ach to w\u0142a\u015bciwo\u015b\u0107 r\u00f3wnie\u017c wyst\u0119puje jako w\u0142a\u015bciwo\u015b\u0107 bezpiecze\u0144stwa). Wszystkie w\u0119z\u0142y, kt\u00f3re obecnie dzia\u0142aj\u0105 (nie uleg\u0142y awarii i nie straci\u0142y po\u0142\u0105czenia z innymi) musz\u0105 doj\u015b\u0107 do porozumienia i przyj\u0105\u0107 pewn\u0105 wsp\u00f3ln\u0105 warto\u015b\u0107 ko\u0144cow\u0105.\n

      Tutaj wa\u017cne jest zrozumienie, \u017ce w\u0119z\u0142y w rozwa\u017canym przez nas rozproszonym systemie chc\u0105 doj\u015b\u0107 do porozumienia. M\u00f3wi\u0105c pro\u015bciej, mamy na my\u015bli systemy, w kt\u00f3rych co\u015b mo\u017ce zawie\u015b\u0107 (na przyk\u0142ad mo\u017ce zadzia\u0142a\u0107 jaki\u015b w\u0119ze\u0142), ale w tym systemie z pewno\u015bci\u0105 nie ma w\u0119z\u0142\u00f3w, kt\u00f3re dzia\u0142a\u0142yby przeciwko innym (problem genera\u0142\u00f3w bizantyjskich). Dzi\u0119ki tej w\u0142a\u015bciwo\u015bci system pozostaje sp\u00f3jny.<\/li>\n

    2. Integralno\u015b\u0107 <\/b> \u2014 je\u015bli wszystkie poprawnie dzia\u0142aj\u0105ce w\u0119z\u0142y proponuj\u0105 t\u0119 sam\u0105 warto\u015b\u0107 v<\/b>, to znaczy ka\u017cdy poprawnie dzia\u0142aj\u0105cy w\u0119ze\u0142 musi przyj\u0105\u0107 t\u0119 warto\u015b\u0107 v<\/b>. <\/li>\n
    3. Zako\u0144czenie <\/b>\u2013 wszystkie poprawnie dzia\u0142aj\u0105ce w\u0119z\u0142y w ko\u0144cu przyjm\u0105 pewn\u0105 warto\u015b\u0107 (w\u0142a\u015bciwo\u015b\u0107 \u017cywotno\u015bci), co pozwala algorytmowi na post\u0119p w systemie. Ka\u017cdy pojedynczy poprawnie dzia\u0142aj\u0105cy w\u0119ze\u0142 powinien pr\u0119dzej czy p\u00f3\u017aniej przyj\u0105\u0107 warto\u015b\u0107 ko\u0144cow\u0105 i potwierdzi\u0107 to: \u201eDla mnie \u2013 ta warto\u015b\u0107 jest prawdziwa, zgadzam si\u0119 z ca\u0142ym systemem\u201d.<\/li>\n<\/ol>\n

      <\/p>\n

      Przyk\u0142ad dzia\u0142ania algorytmu konsensusu<\/h4>\n

      \nDop\u00f3ki w\u0142a\u015bciwo\u015bci algorytmu mog\u0105 by\u0107 nieco niezrozumia\u0142e. Dlatego zilustrujemy na przyk\u0142adzie, jakie etapy przechodzi najprostszy algorytm konsensusu w systemie z synchronizowanym modelem wymiany wiadomo\u015bci, w kt\u00f3rym wszystkie w\u0119z\u0142y dzia\u0142aj\u0105 poprawnie, wiadomo\u015bci nie gin\u0105, a nic si\u0119 nie psuje (czy rzeczywi\u015bcie co\u015b takiego zdarza si\u0119?).<\/p>\n

        \n
      1. Wszystko zaczyna si\u0119 od propozycji r\u0119ki i serca (Propose). Za\u0142\u00f3\u017cmy, \u017ce do w\u0119z\u0142a o nazwie \u201eW\u0119ze\u0142 1\u201d pod\u0142\u0105czy\u0142 si\u0119 klient i rozpocz\u0105\u0142 transakcj\u0119, przesy\u0142aj\u0105c w\u0119z\u0142owi now\u0105 warto\u015b\u0107 \u2013 O. Od tego momentu b\u0119dziemy nazywa\u0107 \u201eW\u0119ze\u0142 1\u201d proposer<\/b>. Jako proposer \u201eW\u0119ze\u0142 1\u201d musi teraz poinformowa\u0107 ca\u0142y system, \u017ce ma \u015bwie\u017ce dane, i rozsy\u0142a wszystkim innym w\u0119z\u0142om wiadomo\u015b\u0107: \u201eZobaczcie! Otrzyma\u0142em warto\u015b\u0107 \u201eO\u201d i chc\u0119 j\u0105 zapisa\u0107! Prosz\u0119 o potwierdzenie, \u017ce r\u00f3wnie\u017c zapiszecie \u201eO\u201d w swoim logu.\u201d\n

        \"Kot<\/li>\n

      2. Nast\u0119pny etap to g\u0142osowanie nad proponowan\u0105 warto\u015bci\u0105 (Voting). Po co to jest? Mo\u017ce zdarzy\u0107 si\u0119, \u017ce inne w\u0119z\u0142y otrzyma\u0142y bardziej aktualne informacje i maj\u0105 dane dotycz\u0105ce tej samej transakcji.\n

        \"Kot
        \n
        \nKiedy w\u0119ze\u0142 \u201eW\u0119ze\u0142 1\u201d wysy\u0142a swoj\u0105 propozycj\u0119, pozosta\u0142e w\u0119z\u0142y sprawdzaj\u0105 w swoich logach dane dotycz\u0105ce tego wydarzenia. Je\u015bli nie ma \u017cadnych sprzeczno\u015bci, w\u0119z\u0142y og\u0142aszaj\u0105: \u201eTak, nie mam innych danych dotycz\u0105cych tego zdarzenia. Warto\u015b\u0107 \u201eO\u201d to najnowsza informacja, jak\u0105 zdobyli\u015bmy\u201d. <\/p>\n

        W przeciwnym razie w\u0119z\u0142y mog\u0105 odpowiedzie\u0107 \u201eW\u0119z\u0142owi 1\u201d: \u201eS\u0142uchaj! Mam bardziej aktualne dane dotycz\u0105ce tej transakcji. Nie \u201eO\u201d, a co\u015b lepszego.\u201d<\/p>\n

        Na etapie g\u0142osowania w\u0119z\u0142y podejmuj\u0105 decyzj\u0119: albo wszyscy akceptuj\u0105 jedn\u0105 warto\u015b\u0107, albo kto\u015b z nich g\u0142osuje przeciw, sygnalizuj\u0105c, \u017ce ma bardziej aktualne dane. <\/li>\n

      3. Je\u015bli runda g\u0142osowania zako\u0144czy\u0142a si\u0119 sukcesem, a wszyscy byli \u201eza\u201d, system przechodzi do nowego etapu \u2013 akceptacji warto\u015bci (Accept). \u201eW\u0119ze\u0142 1\u201d zbiera wszystkie odpowiedzi od innych w\u0119z\u0142\u00f3w i og\u0142asza: \u201eWszyscy zgodzili si\u0119 na warto\u015b\u0107 \u201eO\u201d! Teraz oficjalnie og\u0142aszam, \u017ce \u201eO\u201d to nasza nowa warto\u015b\u0107, wsp\u00f3lna dla wszystkich! Zapiszcie j\u0105 sobie, nie zapomnijcie. Zapiszcie w swoim logu!\u201d\n

        \"Kot<\/li>\n

      4. Pozosta\u0142e w\u0119z\u0142y przesy\u0142aj\u0105 potwierdzenie (Accepted), \u017ce zapisa\u0142y warto\u015b\u0107 \u201eO\u201d, nic nowego w tym czasie nie wp\u0142yn\u0119\u0142o (swojego rodzaju dwuetapowe potwierdzenie). Po tym znacz\u0105cym wydarzeniu uwa\u017camy, \u017ce rozproszona transakcja zosta\u0142a zrealizowana.
        \n \"Kot <\/li>\n<\/ol>\n

        \nW ten spos\u00f3b algorytm konsensusu w prostym przypadku sk\u0142ada si\u0119 z czterech krok\u00f3w: propose, g\u0142osowanie (voting), akceptacja (accept), potwierdzenie akceptacji (accepted).<\/p>\n

        Je\u015bli na kt\u00f3rym\u015b etapie nie uda\u0142o nam si\u0119 osi\u0105gn\u0105\u0107 porozumienia, algorytm uruchamia si\u0119 ponownie, uwzgl\u0119dniaj\u0105c te informacje, kt\u00f3re przeka\u017c\u0105 w\u0119z\u0142y, kt\u00f3re odm\u00f3wi\u0142y potwierdzenia proponowanej warto\u015bci.<\/p>\n

        Algorytm konsensusu w asynchronicznym systemie<\/h2>\n

        \nDo tej pory wszystko by\u0142o p\u0142ynne, poniewa\u017c m\u00f3wili\u015bmy o synchronicznym modelu wymiany wiadomo\u015bci. Ale wszyscy wiemy, \u017ce w dzisiejszym \u015bwiecie przyzwyczaili\u015bmy si\u0119 do dzia\u0142ania asynchronicznie. Jak wi\u0119c podobny algorytm dzia\u0142a w systemie z asynchronicznym modelem wymiany wiadomo\u015bci, gdzie zak\u0142adamy, \u017ce czas oczekiwania na odpowied\u017a od w\u0119z\u0142a mo\u017ce by\u0107 dowolnie d\u0142ugi (swoj\u0105 drog\u0105, awaria w\u0119z\u0142a r\u00f3wnie\u017c mo\u017cna uwa\u017ca\u0107 za przyk\u0142ad, kiedy w\u0119ze\u0142 mo\u017ce odpowiada\u0107 dowolnie d\u0142ugo). <\/p>\n

        Teraz, kiedy wiemy, jak zasadniczo dzia\u0142a algorytm konsensusu, zadanie dla dociekliwych czytelnik\u00f3w, kt\u00f3rzy dotarli do tego miejsca: ile w\u0119z\u0142\u00f3w w systemie z N w\u0119z\u0142ami i asynchronicznym modelem wiadomo\u015bci mo\u017ce ulec awarii, aby system wci\u0105\u017c m\u00f3g\u0142 osi\u0105gn\u0105\u0107 konsensus?<\/p><\/blockquote>\n

        \nPoprawna odpowied\u017a i uzasadnienie s\u0105 w spoilerze.<\/b>Poprawna odpowied\u017a: 0<\/b>. Je\u015bli przynajmniej jeden w\u0119ze\u0142 w asynchronicznym systemie ulega awarii, system nie b\u0119dzie w stanie osi\u0105gn\u0105\u0107 konsensusu. To stwierdzenie zosta\u0142o udowodnione w znanej w pewnych kr\u0119gach twierdzeniu FLP (1985, Fischer, Lynch, Paterson, link do orygina\u0142u na ko\u0144cu artyku\u0142u): \u201eNiemo\u017cno\u015b\u0107 osi\u0105gni\u0119cia rozproszonego konsensusu przy awarii przynajmniej jednego w\u0119z\u0142a\u201d.
        \n\"Kot
        \nCh\u0142opaki, mamy problem, przyzwyczaili\u015bmy si\u0119, \u017ce wszystko mamy asynchronicznie. A teraz takie co\u015b. Jak \u017cy\u0107 dalej? <\/p>\n

        Teraz m\u00f3wili\u015bmy o teorii, o matematyce. Co to znaczy \u201ekonsensus nie mo\u017ce by\u0107 osi\u0105gni\u0119ty\u201d, t\u0142umacz\u0105c z j\u0119zyka matematycznego na nasz \u2013 in\u017cynieryjny? Oznacza to, \u017ce \u201enie zawsze mo\u017cna osi\u0105gn\u0105\u0107\u201d, tzn. istnieje taki przypadek, w kt\u00f3rym konsensus nie jest osi\u0105galny. A co to za przypadek? <\/p>\n

        To w\u0142a\u015bnie naruszenie w\u0142a\u015bciwo\u015bci liveness, opisanej powy\u017cej. Nie mamy og\u00f3lnego porozumienia, a system nie mo\u017ce mie\u0107 post\u0119pu (nie mo\u017ce zako\u0144czy\u0107 si\u0119 w ograniczonym czasie), gdy nie mamy odpowiedzi od wszystkich w\u0119z\u0142\u00f3w. Poniewa\u017c w asynchronicznym systemie nie mamy przewidywalnego czasu odpowiedzi i nie mo\u017cemy wiedzie\u0107, czy w\u0119ze\u0142 uleg\u0142 awarii, czy po prostu d\u0142ugo odpowiada.<\/p>\n

        Ale w praktyce mo\u017cemy znale\u017a\u0107 rozwi\u0105zanie. Niech nasz algorytm mo\u017ce dzia\u0142a\u0107 d\u0142ugo w przypadku awarii (potencjalnie mo\u017ce dzia\u0142a\u0107 w niesko\u0144czono\u015b\u0107). Jednak w wi\u0119kszo\u015bci sytuacji, gdy wi\u0119kszo\u015b\u0107 w\u0119z\u0142\u00f3w dzia\u0142a poprawnie, b\u0119dziemy mieli post\u0119p w systemie. <\/p>\n

        W praktyce mamy do czynienia z cz\u0119\u015bciowo synchronicznymi modelami komunikacji. Cz\u0119\u015bciowa synchronizacja rozumiana jest tak: w og\u00f3lnym przypadku mamy model asynchroniczny, ale formalnie wprowadza si\u0119 pewne poj\u0119cie 'global stabilization time' pewnego momentu czasu. <\/p>\n

        Ten moment czasu mo\u017ce nie nadej\u015b\u0107 przez dowolnie d\u0142ugi czas, ale pewnego dnia musi nast\u0105pi\u0107. Rozlegnie si\u0119 wirtualny budzik i od tego momentu mo\u017cemy przewidzie\u0107 r\u00f3\u017cnic\u0119 czasu, w jakiej wiadomo\u015bci dotr\u0105. Od tego momentu system przekszta\u0142ca si\u0119 z asynchronicznego w synchroniczny. W praktyce mamy do czynienia w\u0142a\u015bnie z takimi systemami. <\/p>\n

        Algorytm Paxos rozwi\u0105zuje problemy konsensusu<\/h2>\n

        \nPaxos <\/a><\/noindex> \u2013 to rodzina algorytm\u00f3w, kt\u00f3re rozwi\u0105zuj\u0105 problem konsensusu dla cz\u0119\u015bciowo synchronizowanych system\u00f3w, przy za\u0142o\u017ceniu, \u017ce niekt\u00f3re w\u0119z\u0142y mog\u0105 ulega\u0107 awarii. Autorem Paxosa jest Leslie Lamport<\/a><\/noindex>. Zaproponowa\u0142 on formalny dow\u00f3d istnienia i poprawno\u015bci algorytmu w 1989 roku. <\/p>\n

        Jednak dow\u00f3d okaza\u0142 si\u0119 wcale nietrywialny. Pierwsza publikacja zosta\u0142a wydana dopiero w 1998 roku (33 strony) z opisem algorytmu. Okaza\u0142o si\u0119, \u017ce by\u0142a ona skrajnie trudna do zrozumienia, a w 2001 roku opublikowano wyja\u015bnienie do artyku\u0142u, kt\u00f3re zajmowa\u0142o 14 stron. Obj\u0119to\u015bci publikacji s\u0105 podane, aby pokaza\u0107, \u017ce problem konsensusu jest naprawd\u0119 skomplikowany, a za takimi algorytmami stoi ogromna praca najinteligentniejszych ludzi.<\/p>\n

        Ciekawe, \u017ce sam Leslie Lamport w swoim wyk\u0142adzie zauwa\u017cy\u0142, \u017ce w drugiej publikacji-wyja\u015bnieniu znajduje si\u0119 jedno stwierdzenie, jedna linijka (nie sprecyzowa\u0142 jaka), kt\u00f3ra mo\u017ce by\u0107 r\u00f3\u017cnie interpretowana. I z tego powodu wiele wsp\u00f3\u0142czesnych realizacji Paxosa nie dzia\u0142a ca\u0142kowicie poprawnie. <\/p><\/blockquote>\n

        \nSzczeg\u00f3\u0142owe om\u00f3wienie dzia\u0142ania Paxosa zajmie niejedn\u0105 artyku\u0142, dlatego postaram si\u0119 bardzo kr\u00f3tko przedstawi\u0107 g\u0142\u00f3wn\u0105 ide\u0119 algorytmu. W linkach na ko\u0144cu mojego artyku\u0142u znajdziesz materia\u0142y do dalszego zg\u0142\u0119biania tego tematu.<\/p>\n

        Role w Paxos<\/h4>\n

        \nW algorytmie Paxos istnieje poj\u0119cie r\u00f3l. Rozwa\u017cmy trzy podstawowe (s\u0105 warianty z dodatkowymi rolami):<\/p>\n

          \n
        1. Propozycje (mo\u017cna spotka\u0107 r\u00f3wnie\u017c terminy: liderzy lub koordynatorzy)<\/b>. To s\u0105 ludzie, kt\u00f3rzy poznaj\u0105 nowe znaczenie od u\u017cytkownika i przyjmuj\u0105 rol\u0119 lidera. Ich zadaniem jest zainicjowanie rundy przedstawiania nowego znaczenia i koordynacja dalszych dzia\u0142a\u0144 w\u0119z\u0142\u00f3w. Co ciekawe, Paxos dopuszcza istnienie kilku lider\u00f3w w okre\u015blonych sytuacjach.<\/li>\n
        2. Akceptory (G\u0142osuj\u0105cy)<\/b>. To w\u0119z\u0142y, kt\u00f3re g\u0142osuj\u0105 za przyj\u0119ciem lub odrzuceniem danego znaczenia. Ich rola jest niezwykle istotna, poniewa\u017c to od nich zale\u017cy decyzja: w jakie w stanie przechodzi (lub nie przechodzi) system po danym etapie algorytmu konsensusu.<\/li>\n
        3. Ucz\u0105cy si\u0119<\/b>. W\u0119z\u0142y, kt\u00f3re po prostu przyjmuj\u0105 i zapisuj\u0105 nowe uzgodnione znaczenie, gdy stan systemu si\u0119 zmienia. Nie podejmuj\u0105 decyzji, po prostu otrzymuj\u0105 dane i mog\u0105 je przekaza\u0107 ko\u0144cowemu u\u017cytkownikowi. <\/li>\n<\/ol>\n

          \nJeden w\u0119ze\u0142 mo\u017ce pe\u0142ni\u0107 kilka r\u00f3l w r\u00f3\u017cnych sytuacjach. <\/p>\n

          Poj\u0119cie kworum<\/h4>\n

          \nZak\u0142adamy, \u017ce mamy system z N<\/b> w\u0119z\u0142ami. I z nich maksymalnie F<\/b> w\u0119z\u0142\u00f3w mo\u017ce ulec awarii. Je\u015bli F w\u0119z\u0142\u00f3w ulega awarii, to w naszym klastrze powinno by\u0107 co najmniej 2F + 1<\/b> w\u0119z\u0142\u00f3w acceptor\u00f3w. <\/p>\n

          Jest to konieczne, aby\u015bmy zawsze, nawet w najgorszym przypadku, mieli wi\u0119kszo\u015b\u0107 \u201edobrych\u201d, prawid\u0142owo dzia\u0142aj\u0105cych w\u0119z\u0142\u00f3w. To znaczy, \u017ce F + 1<\/b> \u201edobrych\u201d w\u0119z\u0142\u00f3w, kt\u00f3re si\u0119 zgodzi\u0142y, i ko\u0144cowe znaczenie zostaje zaakceptowane. W przeciwnym razie mo\u017ce wyst\u0105pi\u0107 sytuacja, w kt\u00f3rej r\u00f3\u017cne lokalne grupy przyjm\u0105 r\u00f3\u017cne znaczenia i nie b\u0119d\u0105 mog\u0142y si\u0119 ze sob\u0105 porozumie\u0107. Dlatego potrzebujemy absolutnej wi\u0119kszo\u015bci, aby wygra\u0107 w g\u0142osowaniu.<\/p>\n

          Og\u00f3lna idea dzia\u0142ania algorytmu konsensusu Paxos<\/h4>\n

          \nAlgorytm Paxos zak\u0142ada dwie g\u0142\u00f3wne fazy, kt\u00f3re z kolei dziel\u0105 si\u0119 na dwa kroki ka\u017cda:<\/p>\n

            \n
          1. Faza 1a: Przygotowanie<\/b>. Na etapie przygotowania lider (proposer) informuje wszystkie w\u0119z\u0142y: \u201eZaczynamy nowy etap g\u0142osowania. Mamy now\u0105 rund\u0119. Numer tej rundy to n. Teraz zaczniemy g\u0142osowa\u0107\u201d. Na razie po prostu og\u0142asza rozpocz\u0119cie nowego cyklu, ale nie podaje nowej warto\u015bci. Celem tego etapu jest zainicjowanie nowej rundy i poinformowanie wszystkich o jej unikalnym numerze. Numer rundy jest wa\u017cny, musi by\u0107 wi\u0119kszy ni\u017c wszystkie poprzednie numery g\u0142osowa\u0144 od wszystkich poprzednich lider\u00f3w. To w\u0142a\u015bnie dzi\u0119ki numerowi rundy inne w\u0119z\u0142y w systemie b\u0119d\u0105 rozumie\u0107, jak \u015bwie\u017ce s\u0105 dane u lidera. Prawdopodobnie inne w\u0119z\u0142y ju\u017c maj\u0105 wyniki g\u0142osowania z du\u017co p\u00f3\u017aniejszych rund i po prostu poinformuj\u0105 lidera, \u017ce pozostaje w tyle.<\/li>\n
          2. Faza 1b: Obietnica<\/b>. Kiedy w\u0119z\u0142y-acceptory otrzymaj\u0105 numer nowego etapu g\u0142osowania, mo\u017cliwe s\u0105 dwa scenariusze: \n