Určení pořadí událostí v distribuovaném systému není jednoduché, protože pojem “teď” je relativní. Tento článek zkoumá výzvy spojené s dosažením konsenzu v distribuovaných systémech a proč se spoléhat na osvědčené algoritmy, jako jsou Raft nebo Paxos, může být nezbytné.
Ukazuje se, že znalost chronologického pořadí dvou událostí je docela užitečná věc.
Pokud prodáváte vstupenky do kina a jsou dva zájemci o jedno sedadlo, potřebujete vědět, kdo byl první. Tomu člověku prodáte vstupenku a druhému odmítnete. Pokud máte jen jedno prodejní okénko, je to snadné. Kupující tvoří frontu a pořadí prodeje vstupenek je tímto určeno. Problém s tímto přístupem je, že neškáluje, a pokud chcete zaplnit velké kino nebo provozujete multiplex, jste v problémech. Fronta by byla příliš dlouhá.
Decentralizace
Potřebujete více prodejních okének. Potřebujete distribuovaný systém. Bohužel se ukazuje, že určit společné pořadí událostí v distribuovaném systému, na kterém by se všichni shodli, je docela obtížné.
Můžete rozdělit dostupné vstupenky mezi jednotlivé kanceláře a například prodávat liché řady v jedné kanceláři a sudé řady v druhé. Tomu se říká sharding a má to své vlastní problémy. Příkladem problému, který budete muset řešit, je: Co když zákazník chce dvě vstupenky, jednu v liché řadě a druhou v sudé, ale jen pokud jsou obě dostupné. Název, sharding, sedí. Shardy (neboli střepy) mají ostré hrany a snadno se můžete pořezat.
Alternativně můžete mít více kanceláří, ale jen jednu knihu vstupenek, kde zaznamenáváte nákupy. Všichni prodejci vstupenek budou tuto knihu předávat mezi sebou. Tomu se říká zamykání nebo použití semaforů. Je to trochu lepší než jedna fronta, protože můžete provádět platby a komunikovat se zákazníky paralelně, ale efektivně stále můžete obsloužit jen jednoho zákazníka v daný okamžik, ačkoliv tento čas je alespoň zkrácen.
Časování
Jedním z očividných přístupů k určení pořadí událostí je zaznamenání přesného času, kdy k události došlo, a pozdější použití tohoto času k seřazení záznamů v jednom společném deníku. Pokud má událost A dřívější časovou značku než událost B, znamená to, že A se stala první a B druhá. Bohužel, tento přístup má dvě vady.
Prvním problémem je, že to pomáhá jen zpětně. V našem příkladu s prodejem vstupenek, vědět, že Joe koupil vstupenku první a Mary druhá, řeší problém jen částečně. Joeho vpustíte dovnitř, ale Mary budete muset vrátit peníze, a nebude šťastná, protože jste jí zkazili rande.
Druhým a pravděpodobně důležitějším problémem je, že nejsme schopni měřit čas dostatečně přesně. Určitě ne natolik, aby všichni aktéři v distribuovaném systému měli stejný čas. “Ale máme NTP,” říkáte. “Bylo to určené k tomu, aby udržovalo čas v síti synchronizovaný,” říkáte. Ano, ale ne dostatečně dobře. Alespoň ne dost dobře na účely určování skutečného pořadí událostí. Pokud si přečtete slavný článek Google o Spanneru, jedním z poznatků je, že i v silně synchronizovaném clusteru je rozdíl mezi uzly obvykle mezi 1 a 7 milisekundami. To je hodně, vzhledem k tomu, že moderní CPU může provést asi sto milionů instrukcí v každé milisekundě.
Zaznamenání času je tedy k ničemu při určování správného pořadí věcí a my nejenže potřebujeme zaznamenat skutečné pořadí pro pozdější přezkoumání–potřebujeme vědět, že jedna věc se stala, než dovolíme, aby se stala jiná věc. Co nám tedy zbývá? Je to v podstatě systém drbů na Beverly Hills High.
Něco se stalo
Podívejme se na výměnu potřebnou k tomu, aby bylo spolehlivě zaznamenáno, že se v distribuovaném systému tří agentů něco stalo. Jak je v těchto scénářích obvyklé, pojmenujeme je Alice, Bob a Charlie.
- X se stalo a ví o tom pouze Alice.
- Alice pošle zprávu Bobovi a Charliemu, že X se stalo. Takže Alice ví o X a také ví, že poslala zprávu Bobovi a Charliemu.
- Bob přijme zprávu a zaznamená X ve svém deníku. Nyní Alice a Bob vědí o X a Alice ví, že řekla Bobovi a Charliemu.
- Bob pošle potvrzení o přijetí zprávy zpět Alice. Nyní Alice a Bob vědí o X a Alice ví, že řekla Charliemu a Bob ví, že poslal potvrzení Alici.
- Alice obdrží potvrzení od Boba. Nyní Alice a Bob vědí o X a Alice ví, že řekla Charliemu a Alice ví, že Bob ví o X. Bob v tuto chvíli neví, že Alice ví, že on ví o X.
- Pro stručnost, řekněme, že Charlie dělá totéž, co Bob v krocích 3 až 5. Takže nyní Alice, Bob a Charlie všichni vědí o X a Alice již ví, že všichni vědí o X.
- Nyní může Alice říci Charliemu, že ví, že Bob již ví o X. Alternativně může Bob říci Charliemu přímo a naopak. Samozřejmě, Charlie musí potvrdit Alici, že nyní ví, že Bob ví o X.
- Alice pošle potvrzení o potvrzení zpět Bobovi. Poté, co to Bob obdrží, může si být jistý, že Alice ví, že on ví o X.
- Po stejném druhu výměny mezi Alicí a Charliem se konečně můžeme dostat k požadovanému koncovému stavu ve skupině: Všichni vědí, že se X stalo a také všichni vědí, že všichni o tom vědí.
Chápete. Je to složité. V distribuovaných systémech neexistuje žádné “teď”. Nebo spíše, pokud definujete “teď” jako hranici mezi tím, co bylo, a tím, co bude, “teď” se může lišit mezi účastníky. A protože síť není spolehlivá, může být jakákoliv zpráva ztracena nebo přijata vícekrát.
Zjednodušený průběh
Výše uvedený průběh, ač již zjednodušený, protože nepopisuje všechny potřebné zprávy, lze zjednodušit na tyto základní milníky.
- Někdo ví o X
- Všichni ví o X
- Někdo ví, že všichni ví o X
- Všichni ví, že všichni ví o X
A to, děti, je důvod, proč nemůžeme mít pěkné věci. Systémy pro dosažení distribuovaného konsenzu jsou složité a nehezké. Ani nepřemýšlejte o tom, že si vymyslíte vlastní. Stejně jako “nevyvíjejte si vlastní kryptografii”, měli byste se spoléhat na osvědčené algoritmy konsenzu, jako je Raft nebo Paxos, a ideálně používat respektovanou knihovnu, která je implementuje. Nebo použijte Zookeeper.
Toto je ve skutečnosti pokračování tématu, kterého jsem se dotkl ve svém předchozím článku Poučení o odolnosti z leteckých katastrof. Pravděpodobně první otázka, kterou byste si měli položit, je: “Opravdu potřebuji distribuovaný systém?” Nebo přesněji řečeno, má smysl ho zaplatit? Někdy je odpověď ano. Ale jen někdy.
Comments