Search
Jedním ze základních požadavků na distribuovaný systém je schopnost dosahovat spolehlivých výsledků výpočtu i za předpokladu, že dochází ke zpomalování čí úplné ztrátě zpráv, nebo i vypadávání celých procesů. V mnoha případech je podmínkou pro to, aby byl tento požadavek splněný, možnost shodnout se na hodnotě některé z proměnných, která je během výpočtu použita. Této shodě se v distribuovaných systémech říka konsenzus. Mezi reálné aplikace konsenzu patří například synchronizace hodin, výpočet PageRanku používaný Googlem, kontrola shluků mobilních robotů, vyvažování zátěže nebo replikace dat v distribuované databáze. A právě poslední zmíněný příklad bude úlohou, kterou budete v rámci semestrální práce řešit.
Algoritmus, který budete pro tento účel využívat, se nazývá Raft a byl probírán na přednášce. Jeho jednotlivé části pak byly odvozeny detailněji na cvičeních. Raft je příkladem algoritmu k dosažení konsenzu, který se stará o správu a replikaci logu, což z něj dělá dobrý stavební prvek pro distribuovanou databázi. Připomínáme, že kompletní pseudokód a vysvětlení algoritmu můžete najít zde. K lepšímu pochopení algoritmu můžou posloužit zdroje k nalezení zde. Z posledního zdroje by se Vám mohla hodit i tato pěkná visualizace fungování Raftu:
Distribuvaný systém, se kterým budete pracovat, se skládá z dvou typů procesů: klientský proces a serverový proces. Procesů obou typů může být v systému mnoho. Můžete počítat s tím, že spojení mezi klienty a servery jsou spolehlivé a zprávy se na nich neztrácí, ani nedochází k jejich zpoždění. Klientské procesy jsou také spolehlivé a nevypadávají. Hlavním úkolem každého serverového procesu je udržovat svou vlastní kopii databáze (logu), konzistentní s databázemi ostatních serverových procesů. Serverový proces musí mít přehled o tom, který serverový proces je aktuálním lídrem, aby tomu mohl přizpůsobit své chování (stav). Za každých okolností, když potvrdíte klientovi nějaký požadavek jako zpracovaný (committed), je skutečně zpracovaný a tak i zůstane. Nemůže se stát, že byste klientovi řekli, že jste uložili nějáka data a ta by se pak ztratila.
V našem případě je databáze reprezentována jako zobrazení z klíče - K, reprezentovaného jako String, na hodnotu - H, reprezentovanou rovněž jako String, jedná se tedy o velice jednoduchou key/value databázi, která je v našem případě reprezentována rozhraním Map<String, String>. Klient nad touto databází může vykonávat 3 operace - GET, APPEND, PUT, které jsou popsány níže.
String
GET
APPEND
PUT
Klientské procesy mohou mít na kterýkoli ze serverových procesů následující požadavky:
ClientRequestWhoIsLeader
ClientRequestWithContent
getContent()
getOperation()
null
Každý klientský požadavek má vlastní ID, reprezentované jako String. Toto ID lze zjistit voláním getRequestId() na přijaté zprávě. Je důležité, abyste při odpověďi na klientský požadavek, použili jako ID odpovědi identifikátor požadavku, jinak nebude klient schopný odlišit, na který požadavek mu došla odpověď.
getRequestId()
Stáhněte si balíček sem_02.zip. Vaším hlavním úkolem bude naimplementovat serverový proces, jehož hlavní třídou je třída ClusterProcess. Tato třída je již v balíčku předimplementována. Jako u předchozích domácích úloh z distribuovaných výpočtů i zde platí, že když se proces probudí, může zpracovat přijaté zprávy v metodě act. Serverové procesy musí být schopné reagovat na požadavky klientských procesů. Konkrétně musí:
ClusterProcess
act
ServerResponseLeader
ServerResponseConfirm
ServerResponseWithContent
Mimo třídu ClusterProcess můžete implementovat i řadu dalších tříd. Jistě budete potřebovat třídy pro jednotlivé typy zpráv v Raftu, hodit se mohou také třídy starající se o logy jednotlivých procesů. Jako u každé programovací úlohy, je dobré si Váš návrh tříd nejdříve pořádně rozmyslet a až poté začít implementovat. Tím můžete předejít případným budoucím problémům s laděním celého algoritmu.
Vaší implementaci můžete testovat pomocí scénářů definovaných ve třídě RaftRun v balíčku evaluation. Ve třídě Scenario v témže balíčku najdete popis parametrů distribuovaného prostředí. Doporučujeme si zkusit s parametry zahýbat a analyzovat, jak si Váš algoritmus se vznikajícími problémy poradí. My Váš kód budeme testovat na scénářích s různými nastaveními těchto prametrů.
RaftRun
evaluation
Scenario
Za úlohu můžete získat maximálně 14 bodů v závislosti na kvalitě a schopnostech Vašeho řešení. Body se Vám budou nasčítávat podle následujících podúloh.
Všechny zazipované soubory z balíčku student odevzdávejte do systému BRUTE do neděle 3.6.2018 23:59 CET.
student