Distribuert hashtabell

Distribuerte hashtabeller ( også referert til som DHT - er) er en klasse av desentraliserte distribuerte systemer som deler medlemskapet til et sett med nøkler blant deltakende noder, og effektivt kan videresende meldinger til den eneste eieren av en bestemt nøkkel. Hver node er analogen til et array-spor i en hash-tabell.

DHT-er er vanligvis designet for å administrere et stort antall noder, selv i tilfeller der det er kontinuerlige innganger eller plutselige feil i noen av dem. Denne typen infrastruktur kan brukes til å implementere mer komplekse tjenester, for eksempel distribuerte filsystemer , peer-to-peer fildelingssystemer , cooperativ web caching , multicast , anycast og domenenavntjenester .

Historie

Opprinnelig var DHT-forskning delvis motivert av peer-to-peer-systemer som Napster , Gnutella , Freenet , som stolte på eller stole på distribuerte ressurser på Internett for å levere ønsket applikasjon. Spesielt utnyttet disse systemene økningen i båndbredde og økningen i harddiskplass for å tilby et fildelingssystem.

Disse systemene skilte seg fra hverandre i hvordan de fant dataene i deres respektive jevnaldrende. Napster hadde en indeks i en sentralisert server: hver node, ved inngangen, sendte en liste over filene den hadde lokalt til serveren, som ville utføre søkene og indikere for rekvirentene nodene som holdt de ønskede dataene. Denne sentraliserte komponenten gjorde systemet sårbart for angrep. Gnutella og lignende nettverk beveget seg mot en flommodell; i hovedsak var hvert søk faktisk utgjort i en melding som ble overført til alle de andre maskinene på nettverket. Selv om denne metoden unngikk muligheten for et enkelt knekkepunkt, var mekanismen langt mindre effektiv enn Napster. Til slutt var det Freenet som ga en fullt distribuert mekanisme, men ved å bruke heuristisk nøkkelbasert adressering der hver fil var assosiert med en nøkkel, og filer med lignende nøkler hadde en tendens til å gruppere seg i lignende nodesett. Det var derfor sannsynlig at forespørsler ville bli videresendt over nettverket til disse nodesettene uten å måtte besøke mange jevnaldrende. Freenet ga imidlertid ikke sikkerhet for å finne de nødvendige dataene.

Distribuerte hashtabeller bruker en mer strukturert type nøkkelbasert ruting for å oppnå både desentralisering av Gnutella og Freenet, og effektiviteten og påliteligheten i søk som tilbys av Napster. En ulempe er at, som i Freenet, tilbyr DHT-er kun søk etter eksakte titler og ikke etter nøkkelord, selv om denne typen funksjonalitet kan plasseres på et høyere lag med DHT.

De fire første DHT-ene - CAN , Chord , Pastry og Tapestry - ble alle presentert samtidig, i 2001 . Siden den gang har dette forskningsområdet vært ganske aktivt. Utover akademiske studier har DHT-teknologi blitt tatt i bruk som en komponent av BitTorrent , eMule og i Coral Content Distribution Network .

Egenskaper

Egenskapene til DHT understreker følgende egenskaper:

Nøkkelteknikken som brukes for å oppnå disse målene består av det faktum at hver node trenger å forbli i kontakt med bare et lite antall andre noder i nettverket - vanligvis ... av de andre n deltakerne (se nedenfor) - på denne måten nettverket utsettes for et minimumsarbeid for hver endring som skjer i settet med noder som utgjør det.

Noen DHT-anlegg prøver å implementere sikkerhetsmekanismer for å hindre ondsinnede deltakende noder og la noder forbli anonyme, selv om dette er mindre vanlig enn andre peer-to-peer-systemer (spesielt når det kommer til fildeling).

Struktur

En DHT er bygget rundt et abstrakt nøkkelrom , for eksempel et 160 - bits strengsett . Keyspace-medlemskap er delt mellom deltakende noder i henhold til et veldefinert partisjonsskjema. Overleggsnettverket kobler sammen nodene, slik at de kan finne eieren av en bestemt nøkkel i nøkkelrommet.

Med disse posisjonene kan den typiske operasjonen til en DHT for å lagre og deretter hente data skje på følgende måte. Anta at tasterommet er et 160-bits sett med strenger. For å lagre en fil preget av filnavnet og dataparametrene i DHT, beregnes først SHA1 - hashen til filnavnet , og produserer dermed en 160-bits k -nøkkel. Deretter kan en put (k, data) melding sendes til hvilken som helst node på DHT-nettverket. Meldingen videresendes fra node til node på tvers av overleggsnettverket til den når den enkelt noden som er ansvarlig for nøkkel k i henhold til reglene for nøkkelromspartisjonering, hvor paret (k, data) er lagret. Enhver annen klient kan deretter hente innholdet i filen ved å beregne hashen til filnavnet for å få k og be en hvilken som helst node på DHT-nettverket om å finne dataene knyttet til k gjennom en get (k) melding . Meldingen vil da bli videresendt gjennom overlegget til noden ansvarlig for k , som vil svare med en kopi av de lagrede dataene.

Hver av disse komponentene er beskrevet nedenfor for å etablere de grunnleggende prinsippene som er felles for de fleste DHT-er; noen mekanismer kan variere i detalj.

Tastaturpartisjonering

Mange DHT-er bruker en eller annen variant av konsekvent hashing for å kartlegge nøkler til noder. Denne teknikken bruker en funksjon som definerer den abstrakte forestillingen om avstand mellom nøkkelen og nøkkelen . Hver node er tildelt en nøkkel som kalles en identifikator (ID). Alle nøkler som i er nærmeste ID tilhører en node med ID i , målt med .

Eksempel . Chord - algoritmen anser tastene som punkter på en sirkel, og er avstanden tilbakelagt (med klokken) på sirkelen mellom og . Derfor er det sirkulære nøkkelrommet delt inn i sammenhengende segmenter hvis endepunkter er nodeidentifikatorene. Hvis og er to tilstøtende IDer, eier noden med ID alle nøklene som faller mellom og .

Konsekvent hashing har den grunnleggende egenskapen at fjerning eller tillegg av en node endrer bare settet med nøkler som eies av nodene med tilstøtende IDer, uten å involvere alle de andre nodene. Dette er i motsetning til en tradisjonell hash-tabell , der tillegg eller fjerning av en bøtte forårsaker en remapping av nesten hele tasterommet. Siden hver endring i nøkkelsettet som en node er ansvarlig for typisk tilsvarer en intens (med hensyn til båndbredde) node-til-node-bevegelse av objekter lagret i DHT, er en minimering av disse omorganiseringsbevegelsene nødvendig for å håndtere effektivt med jevnaldrende som har en svært dynamisk oppførsel (høyt antall innganger, utganger eller funksjonsfeil).

Overlegg nettverk

Hver node opprettholder et sett med koblinger til de andre nodene (dens naboer ). Sammen danner disse nodene overleggsnettverket, og er organisert på en strukturert måte, og gir dermed form til nettverkstopologien .

Alle DPT-topologier deler en eller annen variant av den mest essensielle egenskapen: for hver nøkkel k eier enten noden k eller har en kobling til en node som er nærmere k når det gjelder avstand i nøkkelrommet, som definert ovenfor. På dette tidspunktet er det derfor enkelt å videresende en melding til eieren av en hvilken som helst nøkkel k ved å bruke følgende grådige algoritme : ved hvert påfølgende trinn videresender den meldingen til naboen hvis ID er nærmest k . Når det ikke er noen nabo med disse egenskapene, så har vi nådd den faktisk nærmeste noden, som må være eier av k i henhold til det som er definert ovenfor. Denne typen ruting blir noen ganger referert til som nøkkelbasert ruting .

Utover den underliggende riktigheten av denne typen ruting, er det to nøkkelbegrensninger i topologien for at det maksimale antallet påfølgende trinn i en bane (forsinkelse) er lavt, slik at forespørselen oppfylles raskt, og at det maksimale antallet av naboer til hver node (graden av noden) er lav, for å holde vedlikeholdskostnadene lav. Det er en avveining mellom disse to kriteriene som er grunnleggende i grafteori . Noen vanlige valg er vist nedenfor, der n er antall noder i DHT:

Det tredje valget er det vanligste, selv om det ikke er det beste når det gjelder avveining av grad/forsinkelse, da denne topologien typisk gir større fleksibilitet når det gjelder valg av naboer. Dette er nyttig for eksempel for å velge naboer som er topologikompatible og som samtidig er like når det gjelder latens i det underliggende fysiske nettverket.

I tillegg til rutingsalgoritmene er det flere algoritmer som utnytter strukturen til overleggsnettverket til en DHT for å sende en melding til alle nodene, eller til en undergruppe av nodene, til selve DHT [1] . Disse algoritmene brukes av applikasjoner til å utføre multicast-operasjoner på overlegget, for å utføre rekkeviddespørringer eller for å samle inn statistikk. To systemer basert på denne tilnærmingen er Structella [2] , som implementerer flom og random walk på overlegget til et Pastry-nettverk, og DQ-DHT, som implementerer en dynamisk spørringsalgoritme på et Chord [3] -nettverk .

Eksempler

Applikasjoner som bruker DHT-er

Artikler

Merknader

  1. ^ Ali Ghodsi. "Distribuert k-ary System: Algorithms for Distributed Hash Tables" , Arkivert 22. mai 2007 på Internet Archive. KTH-Royal Institute of Technology, 2006.
  2. ^ Manuel Costa, Antony Rowstron. Miguel Castro, Manuel Costa og Antony Rowstron, bør vi bygge Gnutella på et strukturert overlegg? ( PDF ), i ACM SIGCOMM Computer Communication Review , vol. 34, n. 1, 1. januar 2004, s. 131, DOI : 10.1145 / 972374.972397 .
  3. ^ Domenico Talia , Paolo Trunfio. Domenico Talia og Paolo Trunfio, Enabling Dynamic Querying over Distributed Hash Tables , i Journal of Parallel and Distributed Computing , vol. 70, nei. 12, desember 2010, s. 1254-1265, DOI : 10.1016 / j.jpdc.2010.08.012 .

Eksterne lenker