Distribuované hešovacie tabulky

Obsah

Úvod
Vlastnosti
Štrukúra
Zoznam literatúry

Úvod

Distribuované hešovacie tabulky (Distributed hash tables - DHTs) je trieda decentralizovaného, distribuovaného systému a algoritmus vyvinutého za účelom sprostredkovávať merateľnú, samoorganizujúcu infraštruktúru s jasným programovým prepojením. Takto navrhnutá infraštruktúra môže byť neskôr použitá na podporu komplexnejších služieb. DHTs sa využívajú na ukladanie dát ako aj smerovanie a šírenie informácií. DHTs sú pomenovaná podľa hešovacích tabuliek pretože prideľujú zodpovednosť za časť dát podľa hešovacej funkcie (SHA-1). Každý uzol sa chová ako blok v hešovacej tabuľke. DHT predstavuje efektívny vyhľadávací algoritmus (alebo sieťový smerovací algoritmus) umožňujúci podieľajúcemu uzlu rýchle zistenie ktorý z ostatných strojov je zodpovedný za zadnú časť dát.

Vlastnosti

V rámci DHT je cieľom splniť čo najviac z nasledovných vlastností:

Decentralizovaná práca: každý uzol by mal byť schopný nezávislej alebo kolektívnej práce od celého systému bez akéhokoľvek centrálneho správcu.
Rozšíriteľnosť: systém by mal efektívne pracovať aj pri vysokom počte uzlov.
Rozloženie záťaže: kľúče (dáta) by mali byť rozumne rozdelené medzi rôznych účastníkov a to hlavne v prípade keď sa líšia ich možnosti a väzby.
Odolnosť voči chybám: systém by mal byť spoľahlivý (v určitom zmysle) aj keby niektorý uzol zlyhal alebo opustil systém.
Výkonnosť: operácie ako sú smerovanie a uloženie a získanie dát by mali byť prevedené rýchlo.
Integrovateľnosť dát: malo by byť ľahké overenie správnosti dát uložených alebo získaných zo systému.
Kópie dát: systém automaticky vytvára viacnásobné kópie dôležitých dát za účelom ochrany pred ich stratou, zvýšenia dostupnosti a zníženia smerovacích oneskorení.
Bezpečnosť/Robustnosť: systém by mal pokračovať správne aj keby (veľká) časť uzlov sa snažila prekaziť korektnú funkčnosť
Anonymita: systém by nemal umožniť pozorovateľom získanie informácií o ich jednotlivých častiach a ich úlohách v rámci systému.

Štrukúra

Uzly v DHT su usporiadané vo vrstvených sieťach so špecifickou topológiou (ako je napr kruhová alebo hyperkubická) nad priestorom (v reálnom intervale [0,1)). Každý uzol ma logický identifikátor ktorý určí jeho logickú polohu vo vrstvení. Spojený protokol umožňuje novému uzlu zavedenie do existujúceho systému, väčšinou kontaktovaní uzla o ktorom sa predpokladá / vie že je už časťou systému. V rámci tohto protokolu je nový uzol predstavený skupine susedov a pričom taktiež dozerá na vytvorenie smerovacej tabuľky (routing table) v novom uzle.
Smerovacie tabuľky používane v DHT uzloch efektívne určia ktorý ďalší uzol je zodpovedný za určitú časť dát. Dátam je pridelený kľúč ( v rovnakom identifikačnom priestore) a pradený najbližší uzol vo vrstvení. Definícia ,najbližší" sa mení v závislosti od DHT a použitej topológie pričom to nemusí mať priamu súvislosť s fyzickou vzdialenosťou medzi uzlami - napr. keď DHT usporiada uzly do Euklidovského priestoru a výber môže jednoducho závisieť od najmenšej euklidovskej vzdialenosti ku kľúču. Smerovacia tabuľka (routing table) umožňuje každému uzlu samostatné a veľmi efektívne nájdenie najbližšieho uzla pri zadanom kľúči, udávajúc sa v O(log n) preskokov (a v niektorých prípadoch aj O(1) preskokov). Tento štýl smerovania sa niekedy nazýva aj key based routing.

DHT môžeme z iného pohľadu taktiež brať vo všeobecnosti ako dvojvrstvový model: smerovacia úroveň ktorá sprostredkováva send(správa, názov) operácie a úroveň hešovacej tabuľky, ktorá stavia operácie get(názov) a put(názov, hodnota) nad send(správa, názov) (aj keď v reáli send() je zapracovaný do get() a put()).

Niektoré modifikácie všeobecného DHT sa môžu líšiť. Na príklad v prípade ,Name-Dropper" a Zamotané uzly kde sa v prípade zamotaných uzlov spojenia organizujú do dvoch tried: nepotvrdené spojenie (o ktorých sa už počulo ale nebola od nich prijatá žiadna informácia) a potvrdené (o ktorých bola prijatá informácia z prvej ruky). Uzol si kontinuálne vyberá nepotvrdené uzly a vytvára komunikáciu - hanshaking. Oba uzly si pridajú ten druhý do svojej potvrdenej sade uzlov a ešte si pridá potvrdené uzly druhého uzla do svojej sady nepotvrdených uzlov.

V skutočnosti potvrdené a nepotvrdené sady sú rozdelené do vrstiev záležiacich od ich dĺžky prefixu. Vo vrstve k sú spojenia s názvami ktorých najdlhší spoločný prefix (v porovnaní s názvom vlastného uzla) ma dĺžku k. Uzol patrí do viacerých komunít: komunita všetkých uzlov, komunita uzlov zdieľajúca 1 bit prefixu, komunita uzlov zdieľajúci 2 bity prefixu, atď. Uzol sa efektívne zúčastňuje pri zisťovaní štruktúry spojov v každej z komunít.

Zoznam literatúry