Problém dvou generálů

Září 2018, byl jsem unavený, vyčerpaný, zrovna jsem přijel domů a neměl jsem sílu vařit. Tak jsem otevřel jednu donáškovou aplikaci, která je v Británii populární, a objednal pizzu. Jasně, jak se chovají k zaměstnancům, je pochybné, večeře se dá sehnat i etičtěji, ale byl jsem unavený a hladový. Stejně jako řidiči té appky.



Ale byl to večer opakovaných objednávek, chyba v aplikaci způsobila, že někteří Britové dostali identickou objednávku třeba dvakrát, třikrát. A jiní nedostali nic. Já se do toho také málem zamotal. Pro vysvětlení vám musím vyprávět příběh o dvou generálech. ZÁKLADY Problém dvou generálů je klasika počítačové vědy. Představte si údolí, uprostřed údolí stojí důkladně opevněný hrad.



Na okrajích údolí stojí dvě armády. Generálové armád vědí, že bitvu mohou vyhrát jen v případě, že oba zaútočí zároveň. Jedna armáda nebude stačit. Aby vyhráli, potřebují spojit síly z obou stran údolí a domluví se pouze pomocí poslů, které posílají na riskantní cestu údolím. Generál A nebude vědět, kdy má zaútočit, než budou všichni rozestavění.



Jak se ti dva mohou synchronizovat, aby zajistili útok ve stejnou chvíli? Je to problém v kouzelné zemi počítačové vědy, takže návrhy typu semafor nebo dalekohled nefungují. Problém se zdá triviální. Generál A pošle generálovi B zprávu s nějakým časem, třeba v 8. Ale posel musí projít údolím, a pokud ho objeví, na druhou stranu se nedostane a zprávu nedoručí.



Jak bude generál A vědět, že generál B si zprávu přečetl? Posel možná nedorazil a v takovém případě A zaútočí, B ne a prohrají. Mohli by se dohodnout, že B má odeslat potvrzení. A generál A zaútočí pouze, pokud přijde potvrzení. Ale to je stejný problém. Jak bude B vědět, že A dostal potvrzení?



Když posel nedorazí, A nezaútočí, B ano a prohrají. Generál A by tedy mohl poslat potvrzení toho potvrzení, ale jak budou vědět, že prošlo? Generál B by zase mohl poslat potvrzení jako potvrzení toho potvrzení a tak dále. Tenhle problém nejde vyřešit. Možná máte pocit, že to musí jít nějak obejít, třeba poslat 200 poslů.



Jasně, v realitě by to fungovalo, ale tohle je kouzelná země informační a počítačové teorie, za těchto pravidel neexistuje záruka, není to jisté, nejde to zaonačit tak, aby si oba generálové, oba počítače posílající data, byli jistí, že zpráva byla přijata a potvrzena. U počítačů obvykle nejde o tolik, pokud pracujete s počítači na problému, který zahrnuje ohrožení životů, fakt doufám, že nekoukáte na seriál s názvem Základy.



Každopádně jsem si objednával jídlo, sestavil jsem objednávku, zvolil jsem zaplatit, ověřil to palcem, Apple Pay mi ukázal tu svou fajfku a pak mi z aplikace přišla zpráva, že nastal problém a má objednávka neprošla, jestli to chci zkusit znovu. Málem jsem to zkusil. Málem jsem znovu zmáčknul zaplatit, když se mi někde v hlavě ozval hlásek: „Byla tam fajfka, že platba proběhla.“ A já se dost zajímám o počítače, takže jsem si nebyl jistý, jestli jim věřím, že to selhalo.



Tak jsem otevřel historii objednávek. Když se konečně načetla, viděl jsem tam svou objednávku, přišla, ale nepřišlo potvrzení. Nebo se něco pokazilo na serveru aplikace a mají to napsané tak, že měla pocit, že to celé selhalo. Tak jsem napjatě čekal, doufal jsem, že mi přijde jídlo, a říkal si, že vývojáři asi mají špatný den.



A taky že ano. Nebyl jsem jediný. V celé Británii zákazníci aplikace při objednávce zaplatili, dostali zprávu, ať to zkusí znovu. A mnoho z nich to zkoušelo znovu a znovu. Oni byli generál A, server byl generál B a uvízli v reálném, složitém příkladu toho problému. Představte si, že zákazník posílá jednu zprávu za druhou generálovi B, který ji vzorně přijímá, pokaždé strhne peníze neboli zaútočí, ale stalo se něco, co zastavilo potvrzení o přijetí zprávy.



Podle stížností na Twitteru to někdy restaurace pochopila a odeslala objednávku jen jednou. Někdy jim to nedošlo a přijeli tři řidiči se třemi stejnými objednávkami. A někdy nedorazilo žádné jídlo. Zákaznická linka byla zahlcená. Chci zdůraznit, že tohle není vina jednoho vývojáře.



Když se něco tak zásadně pokazí, je to z důvodu dlouhé řady špatných rozhodnutí. Jedna lidská chyba nikdy není základní příčinou. Co mohl tým té appky dělat? Jak ten problém v realitě vyřešit? Zaprvé by asi nikdo neměl mít možnost poslat během pár minut dvě identické objednávky na stejnou kartu do stejné restaurace. To zní, že to by měli ošetřit. Ale skutečným řešením je idempotentní token nebo idempotentní klíč.



To je jedinečná hodnota, kterou aplikace vygeneruje, je to jako ID nákupního košíku a posílá se s objednávkou. Není to jen na nákupy. Idempotentní token se přidává k instrukci na smazání nejstaršího logu nebo k odeslání zprávy. Prostě k věcem, co chcete udělat jen jednou. Server si tento klíč uloží a sleduje podle něj požadavek. Když dorazí další požadavek se stejným klíčem, server už ví, že ten požadavek vykonal.



Nesplní ho tedy znovu, jen ví, že neprošla odpověď a odešle tedy kopii původního potvrzení. To nepomůže, když zprávy vůbec nechodí a spojení úplně selže, ale v reálném světě by si toho lidé všimli. Idempotence znamená, že požadujete to samé vícekrát, ale proběhne to jenom jednou. Tak se řeší problém dvou generálů.



Měl jsem štěstí, udělal jsem objednávku, zaplatil jsem jednou a za půl hodiny mi jídlo dorazilo. Příště si uvařím sám. Překlad: jesterka www.videacesky.cz