Distribueret hash-tabel

DHT ( eng.  d istributed h ash table  - "distribueret hash - tabel ") er en klasse af decentraliserede distribuerede søgetjenestesystemer, der fungerer som en hash-tabel. Som en datastruktur kan en hash-tabel være et associativt array , der indeholder ( nøgle-værdi ) par. Udtrykket DHT er også forbundet med en række principper og algoritmer , der giver dig mulighed for at registrere data, distribuere information mellem et bestemt sæt lagringsknuder og gendanne dem ved distribueret søgning efter nøgle. Et træk ved en distribueret tabel er evnen til at distribuere information blandt et sæt lagerknudepunkter på en sådan måde, at hver deltagende knude kan finde værdien forbundet med en given nøgle. Ansvaret for opretholdelse af forholdet mellem navn og værdi er fordelt på noderne, hvorved ændring af medlemssættet medfører et minimum antal brud. Dette giver dig mulighed for nemt at skalere DHT, samt konstant overvåge tilføjelse og fjernelse af noder og fejl i deres arbejde.

DHT er en ramme, der kan bruges til at bygge mange komplekse tjenester såsom distribuerede filsystemer , peer-to-peer fildistribution og indholdsleveringsnetværk , samarbejdswebcache, multicast , anycast , domænenavnetjeneste og instant messaging . Større distribuerede netværk, der bruger DHT: I2P -netværk , BitTorrent , eDonkey-netværk ( Kad Network ) , YaCy , Tox og Coral Content Distribution Network . Det er muligt at oprette søgemaskiner over DHT-netværket.

Historie

DHT-forskning blev oprindeligt især motiveret af peer-to-peer-systemer såsom I2P , Napster , Gnutella , Freenet , som brugte ressourcer distribueret over internettet til at skabe en enkelt applikation. De brugte især bredbåndsinternet og harddiskplads til at levere en fildistributionstjeneste.

Disse systemer adskiller sig i, hvordan de fandt peer-data:

• Napster havde en central indeksserver: hver node skal efter tilslutning sende en liste over lokalt lagrede filer til serveren, som skal søge og forespørge på de noder, der indeholder resultaterne. Denne centrale komponent gjorde systemet sårbart over for angreb og risici.
• Gnutella og lignende netværk har bevæget sig mod en oversvømmelsesanmodningsmodel - grundlæggende ville hvert opslag resultere i, at der sendes en besked til alle maskiner på netværket. Mens man undgår centraliseret fejl, var denne metode betydeligt mindre effektiv end Napster .
• Endelig var Freenet også fuldstændigt distribueret, men routingen er baseret på en heuristisk nøgle, hvor hver fil har en nøgle tilknyttet sig, og filer med lignende nøgler har en tendens til at klynge sig på et lignende sæt noder. Forespørgslen blev højst sandsynligt sendt til sådanne klynger uden behov for at spørge alle peers. Freenet kunne dog ikke garantere, at dataene ville blive fundet.

DHT'er bruger mere struktureret nøglerouting for at opnå decentraliseringen af ​​I2P , Gnutella og Freenet og effektiviteten og de garanterede resultater af Napster . En ulempe er, at ligesom Freenet understøtter DHT kun søgninger med eksakt match og ikke søgeordssøgninger, selvom disse funktioner kan lægges oven på DHT.

De første fire DHT'er - CAN , Chord , Pastry og Tapestry - blev introduceret omkring 2001 .  Siden da har dette forskningsområde været ret aktivt. Uden for den akademiske verden er DHT-teknologi blevet accepteret som en del af BitTorrent og Coral Content Distribution Network .

Egenskaber

DHT er karakteriseret ved følgende egenskaber:

• Decentralisering : en form for kollektivt nodesystem uden koordinering;
• Skalerbarhed : Systemet vil fungere lige så effektivt med tusinder eller millioner af noder;
• Fejltolerance : Systemet vil være lige så pålideligt (i en vis forstand) med noder, der konstant forbinder, afbryder og kaster fejl.

En nøgleteknik til at nå dette mål er, at enhver node kun skal koordinere med nogle få noder i systemet - typisk O(log n ), hvor n  er antallet af deltagere (se nedenfor) - således at kun en begrænset mængde arbejde er gøres ved hver ændring i antallet af deltagere.

Nogle DHT-projekter søger at yde beskyttelse mod ondsindede brugere og give deltagerne mulighed for at forblive anonyme, selvom dette er mindre almindeligt end i mange andre P2P- systemer (især ved deling af filer); se Anonyme netværk .

Endelig er DHT nødt til at håndtere mere traditionelle distribuerede systemproblemer såsom belastningsbalancering, dataintegritet og ydeevne (især for at sikre, at operationer såsom routing og datalagring eller opslag gennemføres hurtigt).

Struktur

Strukturen af ​​DHT kan opdeles i flere hovedkomponenter. Det er baseret på et abstrakt nøglerum, såsom et sæt 160-bit strenge (antallet af bit kan variere). Keyspace partitioneringsskemaet fordeler nøgleejerskab blandt de deltagende noder. Overlay-netværket forbinder derefter noderne og hjælper med at finde ejeren af ​​enhver nøgle i nøglerummet.

Med alle komponenterne på plads er en typisk brug af DHT til lagring og visning af information som følger: antag, at nøglerummet er 160-bit strenge. For at gemme en fil med det angivne navn og information i DHT, findes en SHA1 hash (160-bit værdi) fra filnavnet , hvorfra der dannes en 160-bit nøgle k (hash), hvorefter der dannes en besked put(k, data), где data - содержание самого файлаog sendt til enhver deltagende node i DHT. Beskeden går fra en knude til en anden gennem overlejringsnetværket, indtil den når den eneste knude, der er ansvarlig for nøglen k, i overensstemmelse med nøglerumsopdelingsskemaet, hvor parret (k, data) vil blive lagret. Enhver anden klient kan få indholdet af filen ved at lave en nøgle (k), dvs. få en hash af filnavnet , for at finde de data, der er knyttet til nøglen, ved at sende en besked get(k). Beskeden vil igen passere gennem overlejringen til den node, der er ansvarlig for nøglen, som vil svare, at de nødvendige data er tilgængelige.

Keyspace-partitionering og overlay-netværkskomponenterne er beskrevet nedenfor for at præsentere de grundlæggende ideer, der er fælles for de fleste DHT-systemer. Mange udviklinger adskiller sig i detaljer.

Tastaturopdeling

De fleste DHT'er bruger forskellige variationer af konsekvent hashing til at kortlægge nøgler til noder. Kernen i denne opdelingsmetode er funktionen , som definerer det abstrakte koncept for afstanden mellem tasterne og , som ikke har noget at gøre med geografisk afstand eller netværksforsinkelse. Hver node er tildelt en enkelt nøgle, kaldet dens identifikator (ID). Noden med ID ejer alle nøgler , som  er det nærmeste ID beregnet ved hjælp af .

Eksempel. Chord DHT behandler tangenter som punkter på en cirkel, og  er afstanden tilbagelagt med uret rundt om cirklen fra tangenten til . Således er nøglerumscirklen opdelt i sammenhængende segmenter, hvis ender er nodeidentifikatorer. Hvis og er tilstødende ID'er, så indeholder noden med ID alle nøgler mellem og .

Konsekvent hashing har hovedegenskaben, at sletning eller tilføjelse af kun ét sæt nøgler, der tilhører noder af tilstødende ID'er, ikke påvirker andre noder.

DHT og BitTorrent

Både DHT og PEX udfører faktisk hovedfunktionen af ​​en BitTorrent-tracker  - de hjælper fildelingsdeltagere med at lære om hinanden. De kan:

• Hjælp deltagerne med at finde hinanden hurtigere For eksempel er der et peer
  X på fordelingen med en utilgængelig port. Peer Z forbinder til distributionen, som ikke selv kan starte en forbindelse med X og må vente til X finder ud af det. X har lige fået adgang til trackeren og vil gøre det næste gang om en time. Men peer Y vender sig igen til trackeren og lærer om den nye peer Z. Hvis Y samtidig længe har været forbundet og er engageret i fildeling med X, så fortæller den X adressen på denne nye peer Z gennem PEX Der kan være sådanne jævnaldrende Y på distribution en masse. Nu kan X starte en forbindelse med Z uden at vente på den næste anmodning til trackeren, hvilket er særligt vigtigt, hvis Z er afbrudt inden da. Med en stor andel af indgående og udgående distributører reducerer dette ventetiden på, at de begynder at downloade.
  

• Reducer belastningen på trackeren
  Ved at få peer-adresser via DHT eller PEX får klienter sjældnere adgang til trackeren, hvorved belastningen reduceres.

• Supportdistribution i perioder, hvor trackeren ikke er tilgængelig
  . Hvis trackeren er den eneste kilde til information om peers, stopper distributionen gradvist, hvis den ikke fungerer. Ved hjælp af PEX kan klienter udveksle information med hinanden om de peers, som de havde kommunikationssessioner med, og derved bremse processen med at stoppe distributionen. DHT giver dig mulighed for helt at udskifte trackeren.

• DHT giver dig mulighed for at distribuere uden en tracker
  Sådan distribution kaldes trackerless ( trackerless ). En torrent til det oprettes uden en tracker-adresse, og klienter finder hinanden via DHT. Sandt nok skal den, der startede distributionen, samtidig have en rigtig IP-adresse, der er tilgængelig udefra. Når de deltager i sporløse distributioner, får BitTorrent-klienter en vis lighed med eMule ved hjælp af Kad-netværket .

Privat nøgle

I offentlige (åbne) trackere, hvor alle kan downloade en torrent og deltage i distributionen, tjener DHT og PEX til fordel for alle deltagere.

For private (lukkede) trackere er det først og fremmest vigtigt, at kun registrerede brugere kan deltage i distributioner, og at de følger visse regler. På første anmodning fra en klient har en privat tracker mulighed for at forhindre ham i at blive distribueret, simpelthen uden at fortælle ham adresserne på andre deltagende klienter. Derfor er det vigtigt for en privat tracker, at klienter ikke modtager disse adresser via DHT/PEX.

DHT og PEX dukkede op i Azureus- og BitComet-klienterne omkring sommeren 2005. Administratorerne af mange private trackere var utilfredse med denne nye funktionalitet og begyndte derfor at forbyde disse nye klientversioner på trackeren.

Derefter foreslog klientudviklerne en ny nøgle inde i torrent-filen: privat . Hvis det er lig med 1, så er klienten forpligtet til automatisk at deaktivere DHT / PEX for denne torrent, uanset brugerens ønske. Sådan en torrent kaldes en Secure Torrent.

Næsten alle moderne private trackere håndhæver selv private:1 i alle torrents, der er postet på trackeren, og forbyder også flere forældede versioner af klienter, der understøtter DHT eller PEX, men som endnu ikke kender til den private nøgle . Det menes, at tracker-brugere simpelthen ikke kan bruge DHT/PEX på distributioner, og der er ikke noget problem. Faktisk, for ikke at tage hensyn til vurderingen, er det nok at erstatte din adgangsnøgle med en hvilken som helst anden. Og du behøver ikke engang at stjæle den. Det er nok at registrere en anden konto for at tage adgangsnøglen fra den.

DHT og statistik

Dette afsnit gælder kun for private trackere, hvor den private nøgle ikke tvinges ind i torrents , og på nogle distributioner (afhængigt af om distributøren selv har indsat den private nøgle i torrenten ) kan DHT og PEX bruges.

Ofte er der en opfattelse af, at DHT aktiveret i klienten påvirker sporingen af ​​klientstatistikker af trackeren, for eksempel "distribueret via DHT, så statistikken gik forbi trackeren." Det er ikke sandt.

For det første bruges DHT/PEX kun til at få peer-adresser. Der føres hverken fildeling eller bogføring af statistik over dem. Klienten rapporterer kun statistikken over downloadede og uploadede data til trackeren.

Det vil sige, "distribueret via DHT" betyder faktisk "Jeg modtog information om nogle (eller alle) jævnaldrende via DHT, og sandsynligvis har nogle jævnaldrende også fundet mig via DHT."

For det andet, selvom klienter normalt ved, hvor de har deres peer-adresser fra, adskiller ingen klient trafik i "modtaget/sendt til DHT-peers" og "modtaget/sendt til peers modtaget fra trackeren". Selvom det ønskes, ville det være svært for klienten at gøre dette - nogle peers kan modtages både fra trackeren og via DHT eller PEX, og ofte ved klienten ikke, hvordan den peer, der starter forbindelsen til den, har modtaget sin adresse.

Klienten rapporterer til trackeren de samlede data om de mængder, der er downloadet og givet til alle peers, som han kommunikerede med, uanset om klienten lærte om individuelle peers gennem trackeren, DHT eller PEX, eller om denne peer overhovedet startede forbindelsen selv . Det vil sige, at selvom "venstre" brugere (som ikke har adgang til trackeren) vises på distributionen på grund af DHT / PEX, vil klienten stadig rapportere til trackeren alt, hvad de har downloadet og givet væk.

Den korrekte bogføring af statistikker afhænger kun af trackerens tilstand: trackeren virker - statistikken tages i betragtning, hvis den ikke virker - tages den ikke i betragtning. Kun i tilfælde af en langsigtet ikke-fungerende tracker kan DHT / PEX spille en indirekte rolle og forhindre fildeling i gradvist at dø ud på en sådan "distribution uden at tage højde for statistik".

Sådan virker DHT

Den distribuerede netværksimplementering i BitTorrent-klienter er baseret på en variant af DHT kaldet Kademlia . Generelt betyder DHT (Distributed hash table) et decentraliseret distribueret system til at kombinere et stort antal konstant forsvindende og opståede noder og effektivt overføre meddelelser mellem dem. Forskellige mere komplekse systemer er bygget på basis af DHT-strukturer, såsom P2P -fildeling , cooperative web-caching, DNS-tjenester osv.

DHT bruger UDP-protokollen . BitTorrent-klienter "lytter" på det samme UDP-portnummer, som de bruger til indgående TCP - forbindelser. Hvis du aktivt bruger DHT, så er det ønskeligt at åbne denne UDP-port for adgang udefra, men ikke nødvendigt - DHT vil fungere sådan.

Hver tilsluttet klient er en separat node i DHT-netværket. Den har sit eget unikke ID (identifikator), tilfældigt udvalgt fra den samme 160-bit plads som infohash' og torrents.

Hver node vedligeholder en routingtabel, der indeholder kontaktoplysninger for mange af de "nærmeste" noder på den, og for nogle få mere fjerntliggende. "Nærheden" af to noder beregnes ud fra "ligheden" af deres ID'er og har intet at gøre med deres geografiske nærhed.

Når en node ønsker at finde peers til en distribution, sammenligner den distributionens infohash med ID'erne for de noder, den kender, og sender derefter en anmodning til den node, hvis ID minder mest om den infohash. Denne node returnerer adressen på den node, hvis ID er endnu tættere på torrentens infohash.

Derefter sender vores node en anmodning til den nye node og modtager fra den adressen på den næste node, hvis ID er endnu mere lig torrentens infohash.

Således strømmer anmodninger fra klienter, der deltager i distributionen af ​​en torrent med en bestemt infohash, gradvist til de noder, hvis ID'er mest ligner denne infohash. Disse noder husker tidligere anmodninger, og alle efterfølgende forespørgende noder vil blive returneret adresser på tidligere peers fra samme distribution.

Ulemper

1. Der er flere inkompatible protokoller, der betjener forskellige netværk.
2. Driften af ​​klienten som en DHT-node skaber en stor belastning på routeren (routeren).
3. Hashes udgives åbent, hvilket tillader interaktiv sporing af distributioner (hvilket er hvad copyright-indehavere bruger). [1] [2] [3]

Relaterede artikler

• Magnet link
• Kademlia

Noter

1. ↑ Forskere spionerer på BitTorrent-brugere i realtid . Hentet 30. september 2017. Arkiveret fra originalen 21. august 2017. (ubestemt)
2. ↑ DHT-protokol . Hentet 29. maj 2010. Arkiveret fra originalen 20. maj 2015. (ubestemt)
3. ↑ Udvidelse til peers til at sende metadatafiler . Dato for adgang: 29. maj 2010. Arkiveret fra originalen 10. maj 2016. (ubestemt)

Links

• Beskrivelse af DHT-protokollen (Oversættelse)  (russisk)
• Beskrivelse af DHT-protokollen på BitTorrent.org 
•  på Azureus Wiki
• på BitComets  hjemmeside