Distribuert hashtabell

Distribuert hashtabell (DHT) er en hashtabell der de enkelte (nøkkel,verdi)-par ligger spredt i et datanett. Den tilbyr de samme funksjoner som en vanlig hashtabell, fjern(nøkkel), finn(nøkkel) og lagre(nøkkel,verdi). I tillegg til at tabellen skal lagre paret basert på oppgitt nøkkel, skal det også foreta lokalisering, avgjøre hvilken node som har lagringsansvar for paret. Vanligvis assosieres DHT med Peer-to-peer datanett, som et mellomlag for ulike datatjenester i applikasjonslaget, som har behov for å lagre små datamengder, indeksert med nøkkel.

Katalogtjenester

DHT kan brukes som en katalogtjeneste i et datanett, der de verdier som lagres i et (nøkkel,verdi)-par er små datamengder inneholdende en adresse, beskrivelse eller måleverdi. I en utvidet betydning kan altså Internettets navnetjeneste (Domain Name System, DNS) oppfattes som en DHT, der lagringsansvaret ligger på ulike steder. DNS er hierarkisk oppbygd med et tilnærmet stabilt sett av ansvarlige deltakere, i motsetning til det flate strukturløse P2P-nett med tidvis stor variasjon i medlemsmassen. Også SNMP, LDAP, X.500, Active Directory og Novell Directory Service kan lagre verdiene distribuert, men også her er strukturen sentralt bestemt og underlagt streng innholdskontroll.

Egenskaper

Arbeidet med å tilrettelegge for rettferdig ansvarsfordeling, adekvat ytelse og pålitelighet, er fortsatt et aktivt forskningsområde innen informatikken. Det som er spesielt vanskelig med ustrukturerte P2P-nett er at antallet deltakende noder (N) kan variere sterkt over tid. Når en node forlater P2P-nettet er det viktig at dens ansvarsområde blir plassert til andre, før noden forsvinner og dens ressurser blir utilgjengelige. Filer skal da kopieres til de som tar over ansvaret. Likens, når en node tilkommer, er det viktig at den får en identitet og ansvar for et utsnitt av de ressurser som skal forvaltes. Filer skal da kopieres over fra de noder der den nye overtar ansvaret. Der det er hyppige endringer i medlemskapet (churn) er det usikkert i hvor stor grad DHT-systemet vil kunne unngå thrashing, altså unngå å bruke vesentlige deler av produksjonskapasiteten til administrasjon (flytting av filer til og fra nye og utflyttede noder).

Eksempler

Content Addressable Network (CAN) er en DHT utviklet ved University of Berkeley i USA (2001). En nøkkel er d-dimensjonal (et d-tuple). Hver node i et CAN har en d-dimensjonal identitet og ansvaret for å lagre et undersett av nøklene (en CAN-sone). I tillegg kjenner en CAN-node til de nærmeste 2d nabosonene. Videresending skjer til den node som ifølge rutetabellen, ligger nærmere i det d-dimensjonale koordinatsystem, og repeteres av neste node, inntil henvendelsen har kommet frem til den ansvarlige, som umiddelbart returnerer svar direkte til den opprinnelige sender. I snitt vil henvendelsen måtte gå gjennom (d/4)n^(1/d) noder. Økt dimensjonalitet gir da raskere svar, men også større rutetabeller som må gjennomsøkes før videresending. CAN var et påtenkt mellomlag for filsystemet OceanStore.

Chord er en DHT utviklet ved Massachusetts Institute of Technology i USA (2000). Hver av de N aktive nodene får en unik 128-bit adresse og lagringsansvar for de nøkler som ligger mellom egen adresse og sin etterfølgers (den med nærmeste 128-bits adresse). Adressene lages ved konsistent hashing av nodens navn eller IP-adresse, og vil over tid sikre at ansvaret spres jevnt. I og med at søkingen medføre at alle N noder blir besøkt, vil Chord også bruke rutetabeller som muliggjør et omtrentlig binært søk. I snitt vil henvendelsen besøke log₂ noder før den når den ansvarlige. Med en million noder, ikke utenkelig dagens Internett, gir dette 20 hopp. Reorganisering vil i snitt medfører (log₂N)² meldinger. Chord fungerer i dag som oppslagsverk for filsystemet CFS (Cooperative File System), også utviklet ved MIT, der CFS lokaliserer filers beliggenhet ved å oppgi en hash av filnavnet til Chord.

Pastry er en DHT utviklet ved Microsoft Research i USA (2001). Også her er adressene 128-bits, men konstruert slik at videresendingen baserer seg på prefix, altså en sammenligning mellom de samme første bit i nøkkel og node. Ytelsen er noenlunde lik, men reorganisering vil skje raskere i Pastry, da rutetabellen også inkluderer direktepekere til de nærmeste nodene. Pastry er oppslagsverk for filsystemet PAST, distribusjonssystemene Scribe og Squirrel.

Kelips er en DHT utviklet ved Cornell University i USA (2002). Nodene deles i G=N^0.5 grupper, og plasseres jevnt (basert på konsistent hashing) utover disse. Med en million noder får man G=1000 grupper. En gitt nøkkel skal lagres i en gitt gruppe, og alle noder i gruppen skal ha lagringsansvar (G kopier) Hver node sprer endringer i sine data til et fåtall av sine naboer i gruppen, som igjen sladrer videre (epidemisk ruting). Etter log₂N meldinger skal alle i gruppen ha blitt oppdatert. Hver node kjenner de fleste i egen gruppe, samt kontaktnoder for alle andre grupper, altså en rutetabell med litt over G linjer. Ved oppslag kan henvendelsen styres direkte til den gruppe som er ansvarlig, hvilket krever en enkelt melding. Kelips krever at nodene jevnlig sladrer om medlemskap og sine endringer, men har den åpenbare fordel at søkingen krever kun en videresending.