Distribuert hasjtabell

Distribuerte Hash Tables , kjent under forkortelsen DHT ( Distribuerte Hash Tables ) , er en type hashtabeller som lagrer nøkkelverdi-par og tillater spørring av verdien knyttet til en nøkkel, der dataene lagres på en distribuert måte i en serie av noder ( distribuerte systemer ) og gir en effektiv søketjeneste som gjør det mulig å finne verdien knyttet til en nøkkel. For sistnevnte bruker de et rutesystem som gjør det mulig å effektivt finne noden hvor informasjonen som trengs er lagret.

Ansvaret for å opprettholde kartleggingen av nøkler til verdier er fordelt mellom nodene, slik at en endring i settet med deltakere forårsaker et minimum av forstyrrelser. Dette lar DHT-er skalere til ekstremt store antall noder, og håndtere konstante feil, nodeankomster og nodefall.

DHT-er danner en infrastruktur som kan brukes til å bygge mer komplekse tjenester, for eksempel distribuerte filsystemer , peer-to-peer fildeling , innholdsleveringssystemer, cooperativ web caching , multicast , anycast , DNS -tjenester og meldingstjenester. snapshot . Viktige distribuerte nettverk som bruker DHT inkluderer BitTorrent -protokollen distribuerte sporere, Kad -nettverket , Storm -botnettet , YaCy , Coral Content Distribution Network , Retroshare , etc...

Historikk

Søk via DHT-er ble opprinnelig motivert av peer-to-peer-systemer som Napster , Gnutella og Freenet , som utnyttet distribuerte ressurser på Internett for å tilby en enkelt applikasjon. Spesielt utnyttet de den økende båndbredden og diskkapasiteten til å tilby en fildelingstjeneste.

Forskjellen mellom disse systemene var i hvordan de fant dataene som jevnaldrende hadde:

DHT-er bruker nøkkelbasert ruting som inkluderer de desentraliserte fordelene med Gnutella og Freenet, og effektiviteten og garanterte resultatene til Napster. En ulempe er at DHT-er, som Freenet, kun støtter eksakte søk, men det er mulig å implementere søkeordsøkefunksjonalitet som et lag over DHT-er.

De fire første DHT-ene - CAN , Chord , Pastry og Tapestry - dukket opp omtrent samtidig i 2001. Siden den gang har denne formen for søk vært mye brukt, hovedsakelig siden BitTorrent inkorporerte dem.

Egenskaper

DHT-er fremhever følgende egenskaper:

En nøkkelteknikk som brukes for å oppnå disse målene er at enhver node må koordinere med bare noen få noder i systemet - oftest O(log n) av de n deltakerne (se nedenfor) - slik at ved en endring i sammensetningen bare krever en begrenset mengde arbeid. Noen DHT-design søker å være sikre mot ondsinnede deltakere [2] og lar deltakerne forbli anonyme, selv om dette er mindre vanlig enn i mange andre peer-to-peer-systemer (spesielt for fildeling), se peer-to-peer. anonymous to-peer . Til slutt må DHT-er håndtere mer tradisjonelle distribuerte systemproblemer , for eksempel systembelastningsbalansering , dataintegritet og ytelse (spesielt sikre at operasjoner som dataruting og lagring eller gjenoppretting utføres fullt ut).

DHT-nettverk er bra for:

er dårlige for:

Struktur

Strukturen til en DHT kan brytes ned i et stort antall komponenter. Basen er et abstrakt nøkkelrom . Et nøkkelromspartisjoneringsskjema deler dette nøkkelrommet mellom nodene . Et overleggsnettverk kobler sammen nodene, slik at innehaveren av en hvilken som helst nøkkel i nøkkelrommet kan bli funnet .

Når disse komponentene er på plass, kan DHT brukes til lagring og henting på følgende måte: Anta at nøkkelrommet er en serie med 160-biters strenger . For å lagre en fil med et navn og data i DHT, blir SHA1-hashen brukt på filnavnet, og oppnår en 160-biters "K" -nøkkel. En put(K, data) melding sendes deretter til nodene som deltar i DHT. Meldingen sendes fra node til node gjennom nettverket til den når noden som er ansvarlig for nøkkelen "K" , spesifisert i nøkkelrommet . (K, data) -paret er lagret i denne noden . Hvis en klient ønsker å få innholdet i filen, må den hash filnavnet, som produserer nøkkelen "K" ; Med dette genereres en get(K) melding, som rutes til den når den ansvarlige noden, som vil svare med de lagrede dataene. Deretter beskrives komponentene i nøkkelrommet og nettverket, med sikte på å fange hovedideen til DHT-ene; mange design er forskjellige i detaljer.

Tastaturpartisjonering

De fleste DHT-er bruker en eller annen variant av hash-hash for å kartlegge nøkler til noder. Denne teknikken implementerer en funksjon δ(k1,k2) som definerer en abstrakt forestilling om avstanden mellom nøkkelen k1 og k2 , som ikke er relatert til geografisk avstand eller nettverkslatens. Hver node er tildelt en unik nøkkel kalt ID. En node med ID "i" eier alle nøklene der "i" er den nærmeste ID, målt med funksjonen δ .

Eksempel: DHT-akkorden behandler tangenter som punkter på en sirkel og δ(k1,k2) er avstanden rundt sirkelen fra k1 til k2 med klokken. Dermed er det sirkulære nøkkelrommet delt inn i sammenhengende segmenter hvis endepunkter er nodeidentifikatorene. Hvis i1 og i2 er to tilstøtende identifikatorer, eier noden med ID i2 alle nøklene mellom i1 og i2 .

Hashing har egenskapen at fjerning eller tillegg av en node bare endrer nøklene til noder med tilstøtende IDer, og de andre nodene påvirkes ikke. I en tradisjonell hash-tabell betyr tillegg eller fjerning av en node at nesten hele nøkkelplassen blir omfordelt. Siden enhver endring vanligvis skyldes intens båndbreddebruk forårsaket av å flytte objekter lagret i DHT fra en node til en annen, er det nødvendig å minimere slik omorganisering for å effektivt støtte høye nodeankomst- og feilrater. Locality hashing prøver å sikre at lignende nøkler tildeles kjente objekter. Dette kan tillate en mer effektiv utførelse av søket, og tillate områdesøk i logaritmisk tid.

Overlegg nettverk

Hver node opprettholder en serie lenker til andre noder (dens naboer eller rutetabell ). Sammen danner disse koblingene nettverket. En node velger sine naboer i henhold til en spesifikk struktur, kalt "nettverkstopologien" . Alle DHT-topologier deler en eller annen variant av følgende egenskap: for enhver nøkkel "k", hender det at noden har en ID som har "k" eller har en lenke til en node hvis ID er nærmere "k", i form av avstanden definert i nøkkelrommet. På denne måten er det enkelt å rute en melding til eieren av en hvilken som helst nøkkel "k" ved å bruke en "grådig" algoritme , som ikke nødvendigvis er globalt optimal. Algoritmen består i å suksessivt videresende meldingen til naboen hvis ID er nærmest "k", og når den naboen ikke eksisterer, er det fordi den nærmeste noden med "k" er nådd. Denne rutingstilen kalles ofte "nøkkelbasert ruting". Utover nøyaktigheten til grunnleggende ruting , er to viktige begrensninger på topologien å sikre at maksimalt antall hopp på en hvilken som helst bane (banelengde) er lavt slik at forespørsler fullføres raskt; og at det maksimale antallet naboer til enhver node er minimalt, slik at vedlikeholdskostnadene ikke er for store.

Noen vanlige alternativer for å evaluere effektiviteten til DHT-er er graden/lengden på banen til noden som inneholder informasjonen som søkes. er antall noder til DHT, ved bruk av Big-O-notasjon :

Grad veilengde Merk
mest vanlig, men ikke optimal

Det vanligste alternativet er grad/stilengde , det er ikke optimalt med tanke på lengde, men det gir større fleksibilitet i valg av naboer. Ulike DHT-er bruker fleksibiliteten til å velge naboer som er nære når det gjelder underliggende nettverksforsinkelse.

Maksimal lengde på nettverket er nært knyttet til dets diameter, det er antall hopp på den lengste banen, mellom de korteste banene mellom nodene. I verste fall er rutelengden til nettverket minst like stor som diameteren og kan være større siden den grådige rutingalgoritmen kanskje ikke finner den korteste veien.

Algoritmer for overleggsnettverk

I tillegg til ruting, er det mange algoritmer som utnytter overleggsnettverksstrukturen for å sende en melding til alle noder, eller et undersett av noder, i en DHT. Disse algoritmene brukes i applikasjoner for å utføre multicasting, spørringer eller for å samle inn statistikk.

Ruting i én dimensjon

DHT-implementeringer er forskjellige i blant annet datastrukturen de bruker for oppslag i .

Chord, for eksempel, bruker en skip-liste- lignende struktur . Referanser til noen av nodene opprettholdes på en slik måte at en node er halvparten av avstanden, en en fjerdedel, og så videre følger potensene 2. Noden som mottar forespørselen videresender den til noden med ID høyere og mindre enn nøkkelen.

En ny node kommer inn i systemet ved å gjøre et oppslag på IDen (den kan velges tilfeldig fra nøkkelrommet), for å finne noden som er ansvarlig for IDen, oppdaterer den sin etterfølger og forgjenger for å peke på den nye noden. Dermed blir noden med i nettverket. Kademlia, Pastry og Tapestry bruker en lignende lenkestruktur.

En variant av akkorden fra år 2013 bruker Bruijn-sekvenser , ifølge hvilke den bare krever at hver node vet om to andre, og dermed holde søket inne .

Ruting i flere dimensjoner

På den annen side kan CAN for eksempel bruke et n-dimensjonalt kartesisk rom. Plassen er delt inn i hyperrektangler kalt soner og hver node er ansvarlig for nøklene som tilhører en sone. I likhet med rutetabellen har hver node referanser til sine naboer i det kartesiske planet. En ny node for å bli med i DHT velger tilfeldig et punkt i rommet og bruker oppslag for å finne ut hvem som er noden som er ansvarlig for partisjoneringssonen, og noden annonserer seg selv til naboer som oppdaterer rutetabellene sine.

Real-world implementeringer av DHT og deres forskjeller og forbedringer i forhold til den grunnleggende modellen

De mest bemerkelsesverdige forskjellene funnet i praktiske tilfeller av DHT-implementeringer inkluderer følgende:

Eksempler

Applikasjoner som bruker DHT