Distribuerad hashtabell

DHT ( eng.  d istributed h ash table -  "distribuerad hashtabell ") är en klass av decentraliserade distribuerade söktjänstsystem som fungerar som en hashtabell. Som en datastruktur kan en hashtabell vara en associativ array som innehåller ( nyckel-värde ) par. Termen DHT är också associerad med ett antal principer och algoritmer som låter dig spela in data, distribuera information mellan en viss uppsättning lagringsnoder och återställa dem genom distribuerad sökning med nyckel. En egenskap hos en distribuerad tabell är förmågan att distribuera information mellan en uppsättning lagringsnoder på ett sådant sätt att varje deltagande nod kan hitta värdet som är associerat med en given nyckel. Ansvaret för att upprätthålla förhållandet mellan namn och värde är fördelat mellan noderna, varvid förändring av uppsättningen av medlemmar orsakar ett minsta antal avbrott. Detta gör att du enkelt kan skala DHT, samt ständigt övervaka tillägg och borttagning av noder och fel i deras arbete.

DHT är ett ramverk som kan användas för att bygga många komplexa tjänster som distribuerade filsystem , peer-to-peer fildistribution och innehållsleveransnätverk , kooperativ webbcache, multicast , anycast , domännamnstjänst och snabbmeddelanden . Större distribuerade nätverk som använder DHT: I2P -nätverk , BitTorrent , eDonkey-nätverk ( Kad Network ) , YaCy , Tox och Coral Content Distribution Network . Det är möjligt att skapa sökmotorer över DHT-nätverket.

Historik

DHT-forskning motiverades till en början särskilt av peer-to-peer-system som I2P , Napster , Gnutella , Freenet , som använde resurser distribuerade över Internet för att skapa en enda applikation. I synnerhet använde de bredbandsinternet och hårddiskutrymme för att tillhandahålla en fildistributionstjänst.

Dessa system skiljer sig åt i hur de hittade peer-data:

• Napster hade en central indexserver: varje nod måste, efter att ha gått med, skicka en lista med lokalt lagrade filer till servern, som måste söka och fråga noderna som innehåller resultaten. Denna centrala komponent gjorde systemet sårbart för attacker och risker.
• Gnutella och liknande nätverk har gått mot en översvämningsförfrågan-modell - i princip skulle varje uppslag resultera i att ett meddelande skickas till alla maskiner i nätverket. Samtidigt som man undviker centraliserade misslyckanden var denna metod betydligt mindre effektiv än Napster .
• Slutligen distribuerades även Freenet fullständigt, men routingen är baserad på en heuristisk nyckel, där varje fil har en nyckel kopplad till sig, och filer med liknande nycklar tenderar att klustras på en liknande uppsättning noder. Förfrågan skickades med största sannolikhet till sådana kluster utan att alla kamrater behövde enkätas. Freenet kunde dock inte garantera att data skulle hittas.

DHT:er använder mer strukturerad nyckelrouting för att uppnå decentraliseringen av I2P , Gnutella och Freenet , och effektiviteten och garanterade resultaten av Napster . En nackdel är att, precis som Freenet , stöder DHT endast exakt matchande sökningar och inte sökordssökningar, även om dessa funktioner kan läggas ovanpå DHT.

De fyra första DHT:erna – CAN , Chord , Pastry och Tapestry – introducerades runt 2001 .  Sedan dess har detta forskningsområde varit ganska aktivt. Utanför akademin har DHT-teknik accepterats som en komponent i BitTorrent och Coral Content Distribution Network .

Egenskaper

DHT kännetecknas av följande egenskaper:

• Decentralisering : en form av kollektivt nodsystem utan samordning;
• Skalbarhet : systemet kommer att fungera lika effektivt med tusentals eller miljontals noder;
• Feltolerans : Systemet kommer att vara lika tillförlitligt (i någon mening) med noder som ständigt ansluter, kopplar bort och kastar fel.

En nyckelteknik för att uppnå detta mål är att vilken nod som helst ska samordnas med endast ett fåtal noder i systemet – typiskt O(log n ), där n  är antalet deltagare (se nedan) – så att endast en begränsad mängd arbete är göras för varje förändring av antalet deltagare.

Vissa DHT-projekt strävar efter att ge skydd mot skadliga användare och tillåta deltagare att förbli anonyma, även om detta är mindre vanligt än i många andra P2P- system (särskilt när man delar filer); se Anonyma nätverk .

Slutligen måste DHT ta itu med mer traditionella distribuerade systemproblem som lastbalansering, dataintegritet och prestanda (i synnerhet för att säkerställa att operationer som routing och datalagring eller uppslagningar slutförs snabbt).

Struktur

Strukturen av DHT kan delas upp i flera huvudkomponenter. Den är baserad på ett abstrakt tangentutrymme, till exempel en uppsättning 160-bitars strängar (antalet bitar kan variera). Keyspace-partitioneringsschemat fördelar nyckelägande mellan de deltagande noderna. Överlagringsnätverket kopplar sedan ihop noderna och hjälper till att hitta ägaren till valfri nyckel i tangentutrymmet.

Med alla komponenter på plats är en typisk användning av DHT för att lagra och visa information följande: anta att tangentutrymmet är 160-bitars strängar. För att lagra en fil med det angivna namnet och informationen i DHT, hittas en SHA1-hash (160-bitars värde) från filnamnet , från vilken en 160-bitars nyckel k (hash) bildas, varefter ett meddelande bildas put(k, data), где data - содержание самого файлаoch skickas till valfri deltagande nod i DHT. Meddelandet går från en nod till en annan genom överlagringsnätverket tills det når den enda nod som är ansvarig för nyckeln k, i enlighet med nyckelutrymmespartitioneringsschemat, där paret (k, data) kommer att lagras. Vilken annan klient som helst kan få innehållet i filen genom att skapa en nyckel (k), dvs få en hash av filnamnet , för att hitta data som är associerade med nyckeln genom att skicka ett meddelande get(k). Meddelandet kommer återigen att passera genom överlägget till noden som är ansvarig för nyckeln, som kommer att svara att den erforderliga informationen är tillgänglig.

Keyspace-partitioneringen och överläggsnätverkskomponenterna beskrivs nedan för att presentera de grundläggande idéerna som är gemensamma för de flesta DHT-system. Många utvecklingar skiljer sig åt i detaljer.

Tangentrymdspartitionering

De flesta DHT:er använder olika varianter av konsekvent hashing för att mappa nycklar till noder. Kärnan i denna partitioneringsmetod är funktionen , som definierar det abstrakta konceptet av avståndet mellan nycklarna och , som inte har något att göra med geografiskt avstånd eller nätverksfördröjning. Varje nod tilldelas en enda nyckel, som kallas dess identifierare (ID). Noden med ID äger alla nycklar för vilka  är närmaste ID beräknat med .

Exempel. Chord DHT behandlar tangenter som punkter på en cirkel, och  är avståndet som tillryggalagts medurs runt cirkeln från tangenten till . Sålunda är tangentutrymmescirkeln uppdelad i angränsande segment vars ändar är nodidentifierare. Om och är angränsande ID, så innehåller noden med ID alla nycklar mellan och .

Konsekvent hashning har den huvudsakliga egenskapen att radering eller tillägg av endast en uppsättning nycklar som tillhör noder av angränsande ID:n inte påverkar andra noder.

DHT och BitTorrent

Både DHT och PEX utför faktiskt huvudfunktionen hos en BitTorrent-spårare  - de hjälper fildelningsdeltagare att lära sig om varandra. Dom kan:

• Hjälp deltagarna att hitta varandra snabbare Till exempel finns det ett peer
  X på distributionen med en otillgänglig port. Peer Z ansluter till distributionen, som inte själv kan starta en koppling med X och måste vänta tills X får reda på det. X har precis kommit åt spåraren och kommer att göra det nästa gång om en timme. Men peer Y vänder sig återigen till spåraren och lär sig om den nya peer Z. Om samtidigt Y själv länge har varit ansluten och är engagerad i fildelning med X, då berättar den för X adressen till denna nya peer Z genom PEX Det kan finnas sådana jämnåriga Y på distribution en hel del. Nu kan X starta en anslutning med Z utan att vänta på nästa begäran till spåraren, vilket är särskilt viktigt om Z är bortkopplad då. Med en stor andel inkommande och utgående distributörer minskar detta väntan på att de ska börja ladda ner.
  

• Minska belastningen på spåraren
  Genom att erhålla peer-adresser via DHT eller PEX får klienter tillgång till spåraren mer sällan, vilket minskar belastningen.

• Supportdistribution under perioder då spåraren inte är tillgänglig
  Om spåraren är den enda informationskällan om peers, kommer distributionen gradvis att stoppas om den inte fungerar. Med hjälp av PEX kan klienter utbyta information med varandra om de kamrater som de hade kommunikationssessioner med, och därigenom sakta ner processen att stoppa distributionen. DHT låter dig byta ut trackern helt.

• DHT låter dig distribuera utan en tracker
  . Sådan distribution kallas trackerless ( trackerless ). En torrent för det skapas utan spårningsadress och klienter hittar varandra via DHT. Det är sant att samtidigt måste personen som startade distributionen ha en riktig IP-adress som är tillgänglig utifrån. När de deltar i spårlösa distributioner får BitTorrent-klienter en viss likhet med eMule som använder Kad-nätverket .

Privat nyckel

I offentliga (öppna) spårare, där vem som helst kan ladda ner en torrent och delta i distributionen, tjänar DHT och PEX alla deltagare.

För privata (stängda) spårare är det först och främst viktigt att endast registrerade användare kan delta i distributioner och att de följer vissa regler. På en klients första begäran har en privat spårare möjlighet att förhindra att han distribueras, helt enkelt utan att berätta för honom adresserna till andra deltagande klienter. Därför är det viktigt för en privat spårare att klienter inte får dessa adresser via DHT/PEX.

DHT och PEX dök upp i Azureus- och BitComet-klienterna runt sommaren 2005. Administratörerna för många privata spårare var missnöjda med denna nya funktionalitet och började därför förbjuda dessa nya klientversioner på spåraren.

Sedan föreslog klientutvecklarna en ny nyckel inuti torrentfilen: privat . Om det är lika med 1, är klienten skyldig att automatiskt inaktivera DHT / PEX för denna torrent, oavsett användarens önskemål. En sådan torrent kallas en Secure Torrent.

Nästan alla moderna privata spårare upprätthåller själva private:1 i alla torrenter som publiceras på spåraren, och förbjuder även flera föråldrade versioner av klienter som stöder DHT eller PEX, men som ännu inte känner till den privata nyckeln . Man tror att trackeranvändare helt enkelt inte kan använda DHT/PEX på distributioner, och det är inga problem. Faktum är att för att inte ta hänsyn till betyget räcker det att ersätta ditt lösenord med någon annan. Och du behöver inte ens stjäla den. Det räcker med att registrera ett annat konto för att ta lösenordet från det.

DHT och statistik

Det här avsnittet gäller bara för privata spårare där den privata nyckeln inte tvingas in i torrents , och på vissa distributioner (beroende på om distributören själv infogade den privata nyckeln i torrenten ) kan DHT och PEX användas.

Ofta finns det en åsikt att DHT aktiverat i klienten påverkar spårningen av klientstatistik av spåraren, till exempel "distribuerad via DHT, så statistiken gick förbi spåraren." Det är inte sant.

För det första används DHT/PEX endast för att få peer-adresser. Varken fildelning eller någon redovisning av statistik över dem förs. Klienten rapporterar statistiken över nedladdade och uppladdade data endast till spåraren.

Det vill säga, "distribueras via DHT" betyder faktiskt "Jag fick information om några (eller alla) kamrater via DHT, och förmodligen hittade vissa kamrater mig också via DHT."

För det andra, även om klienter vanligtvis vet var de fick sina peer-adresser ifrån, skiljer ingen klient upp trafik i "mottagen/skickad till DHT-peers" och "mottagen/skickad till peers mottagna från trackern". Även om så önskas skulle det vara svårt för klienten att göra detta – en del peers kan tas emot både från trackern och via DHT eller PEX, och ofta vet inte klienten hur peeren som startar kopplingen till den fått sin adress.

Klienten rapporterar till trackern den totala informationen om de volymer som laddats ner och getts till alla peers som han kommunicerade med , oavsett om klienten lärde sig om individuella peers via trackern, DHT eller PEX, eller om den peeren ens startade anslutningen själv . Det vill säga, även om "vänster" användare (som inte kommer åt spåraren) dyker upp på distributionen på grund av DHT / PEX, kommer klienten fortfarande att rapportera till spåraren allt som de har laddat ner och gett bort.

Den korrekta redovisningen av statistik beror bara på spårarens tillstånd: spåraren fungerar - statistiken tas med i beräkningen, om den inte fungerar - tas den inte med i beräkningen. Endast i fallet med en långvarig icke-fungerande tracker kan DHT / PEX spela en indirekt roll, vilket förhindrar fildelning från att gradvis dö ut på en sådan "distribution utan att ta hänsyn till statistik".

Hur DHT fungerar

Den distribuerade nätverksimplementeringen i BitTorrent-klienter är baserad på en variant av DHT som kallas Kademlia . Generellt sett betyder DHT (Distributed hash table) ett decentraliserat distribuerat system för att kombinera ett stort antal ständigt försvinnande och uppträdande noder och effektivt överföra meddelanden mellan dem. Olika mer komplexa system är byggda på basis av DHT-strukturer, såsom P2P -fildelning , kooperativ webbcache, DNS-tjänster, etc.

DHT använder UDP-protokollet . BitTorrent-klienter "lyssnar" på samma UDP-portnummer som de använder för inkommande TCP- anslutningar. Om du aktivt använder DHT är det önskvärt att öppna denna UDP-port för åtkomst utifrån, men inte nödvändigt - DHT kommer att fungera så.

Varje ansluten klient är en separat nod i DHT-nätverket. Den har sitt eget unika ID (identifierare), slumpmässigt valt från samma 160-bitars utrymme som infohash'and torrents.

Varje nod upprätthåller en routingtabell som innehåller kontaktinformation för många av de "närmast" noderna till den, och för några mer avlägsna. "Närheten" för två noder beräknas utifrån "likheten" mellan deras ID och har ingenting att göra med deras geografiska närhet.

När en nod vill hitta peers för en distribution jämför den distributionens infohash med ID:n för noderna den känner till, och skickar sedan en förfrågan till den nod vars ID liknar den infohash mest. Den noden returnerar adressen till den nod vars ID är ännu närmare torrentens infohash.

Sedan skickar vår nod en förfrågan till den nya noden och får från den adressen till nästa nod, vars ID är ännu mer lik torrentens infohash.

Således flödar förfrågningar från klienter som deltar i distributionen av en torrent med en viss infohash gradvis till de noder vars ID är mest lik denna infohash. Dessa noder kommer ihåg tidigare förfrågningar, och alla efterföljande förfrågande noder kommer att returneras adresser till tidigare kamrater från samma distribution.

Nackdelar

1. Det finns flera inkompatibla protokoll som betjänar olika nätverk.
2. Driften av klienten som en DHT-nod skapar en stor belastning på routern (routern).
3. Hashes publiceras öppet, vilket möjliggör interaktiv spårning av distributioner (vilket är vad upphovsrättsinnehavare använder). [1] [2] [3]

Relaterade artiklar

• Magnet länk
• Kademlia

Anteckningar

1. ↑ Forskare spionerar på BitTorrent-användare i realtid . Hämtad 30 september 2017. Arkiverad från originalet 21 augusti 2017. (obestämd)
2. ↑ DHT-protokoll . Hämtad 29 maj 2010. Arkiverad från originalet 20 maj 2015. (obestämd)
3. ↑ Tillägg för peers att skicka metadatafiler . Tillträdesdatum: 29 maj 2010. Arkiverad från originalet 10 maj 2016. (obestämd)

Länkar

• Beskrivning av DHT-protokollet (översättning)  (ryska)
• Beskrivning av DHT-protokollet på BitTorrent.org 
•  på Azureus Wiki
• på BitComets  webbplats