Distributed hash table

Een distributed hash table, ofwel gedistribueerde hashtabel, is een soort van gedecentraliseerd distributiesysteem waarin men zoekopdrachten kan uitvoeren, gelijkaardig aan een hashtabel. In een DHT correspondeert elk item met een numerieke sleutel. Elke participerende node kan dan ook op een efficiënte wijze de waarde opzoeken voor een gegeven sleutel. De verantwoordelijkheid voor het onderhouden van de relatie tussen sleutel en waarde wordt verdeeld onder de nodes. Dit gebeurt op zulke wijze dat wanneer er een verandering plaatsvindt bij een van de deelnemers, er een minimale hoeveelheid aan storing plaatsvindt. Dit zorgt ervoor dat DHT schaalt naar zeer grote aantallen nodes en dat ze continu nieuwe, vertrekkende en falende nodes kan afhandelen.

Distributed hash tables

DHT’s vormen een infrastructuur die gebruikt kan worden om complexe diensten aan te bieden, zoals gedistribueerde bestandssystemen en peer-to-peer bestandsdeling, coöperatieve web caching, multicast, DNS en instant messaging. Bekende gedistribueerde netwerken die gebruikmaken van DHT zijn onder andere BitTorrent, het Kad Network, de Storm botnet, YaCy en het Coral Content Distribution Network.

Eigenschappen

DHT’s leggen de nadruk op volgende eigenschappen:

• Decentralisatie: de nodes vormen samen het systeem zonder enige vorm van centrale coördinatie.
• Schaalbaarheid: het systeem zou efficiënt moeten functioneren, zelfs met duizenden of miljoenen nodes.
• Fouttolerantie: het systeem zou betrouwbaar moeten zijn, zelfs met nodes die continu toetreden, vertrekken of falen.

De belangrijkste techniek om deze doelen te bereiken is dat een van de nodes moet coördineren, meestal met een beperkt aantal anderen – vaak zijn dit O(log n) van de n deelnemers – zodat er slechts een beperkte hoeveelheid werk uitgevoerd moet bij iedere verandering van een deelnemer.

Sommige DHT-ontwerpen proberen op te treden tegen deelnemers met slechte bedoelingen en laten toe aan deelnemers om anoniem te blijven, hoewel dit minder voorkomend is dan bij andere peer-to-peer systemen (voor file sharing).

DHT moet nog met meer problemen van traditionele gedistribueerde systemen rekening houden, zoals belastingsverdeling, data-integriteit en problemen met prestaties (in het bijzonder het verzekeren dat operaties zoals routering en dataopslag snel afgehandeld worden).

Structuur

De structuur van DHT kan opgedeeld worden in verschillende hoofdonderdelen. De grondslag is een abstracte sleutelruimte, bijvoorbeeld een set van 160-bit strings. Een sleutelruimte partitioneringsschema splitst het eigendom van deze sleutelruimte over de deelnemende nodes. Een overlay-netwerk die de nodes verbindt, laat hen toe om de eigenaar van een gegeven sleutel in de sleutelruimte te vinden.

Eens al deze componenten aanwezig zijn, gaat een typisch gebruiksscenario van DHT voor opslag en opzoekingen als volgt. Veronderstel dat de sleutelruimte een set is van 160-bit strings. Om een bestand met een gegeven bestandsnaam en data op te slaan in DHT, wordt de sha-1 hash van de bestandsnaam gegenereerd, die een 160-bit sleutel k voortbrengt en er wordt een boodschap put(k,data) naar een node van de DHT gestuurd. De boodschap wordt dan van node naar node gestuurd door het overlay-netwerk totdat het die ene node bereikt die verantwoordelijk is voor sleutel k zoals gespecificeerd door de sleutelruimte partitionering. Die node bewaart vervolgens de sleutel en de data. Een andere cliënt kan vervolgens de inhoud van het bestand verkrijgen door de bestandsnaam te hashen om k te genereren en een andere DHT node te vragen om de data te vinden die geassocieerd is met k door een boodschap get(k). De boodschap zal opnieuw geroute worden door het overlay-netwerk naar de node verantwoordelijk voor k, die op zijn beurt zal antwoorden met de opgeslagen data.

DHT implementaties

De grootste verschillen tussen de verschillende praktische DHT-implementaties zijn de volgende

• De adresruimte is een parameter van DHT. Verscheidene DHT’s gebruiken een 128-bit of 160-bit ruimte.
• Sommige DHT’s gebruiken andere hashfuncties dan SHA1.
• In de echte wereld, de sleutel k zou een hash van de inhoud van het bestand in plaats van de bestandsnaam kunnen zijn . Op deze manier kan het bestand nog steeds teruggevonden worden als de bestandsnaam veranderd wordt.
• Sommige DHT’s kunnen ook andere types objecten publiceren. Bijvoorbeeld: een sleutel k zou node ID kunnen zijn en de geassocieerde data zou kunnen beschrijven hoe deze node te kunnen contacteren. Dit laat toe om informatie over aanwezigheid te publiceren zoals vaak gebruikt in IM-applicaties.
• Redundantie kan toegevoegd worden om de betrouwbaarheid te verbeteren. Het (k,data) sleutelpaar kan opgeslagen worden in meer dan een node. Gewoonlijk zullen er in plaats van één node, i geschikte nodes geselecteerd worden, waarbij i een implementatie-specifieke van DHT.

Sommige geavanceerde DHT’s voeren eerst iteratieve opzoekingen uit door de DHT om een set geschikte nodes te selecteren en vervolgens alleen naar deze nodes put(k,data) boodschappen te sturen. Zo wordt het nutteloos verkeer aanzienlijk verminderd, omdat de gepubliceerde boodschappen alleen naar de nodes gezonden worden die geschikt lijken om de sleutel k op te slaan.