Tabel hash distribuit

DHT ( îng . tabel de hash distribuit - „ tabel de hash distribuit”) este o clasă de sisteme de servicii de căutare distribuite descentralizate care funcționează ca un tabel hash. Ca structură de date, un tabel hash poate fi o matrice asociativă care conține perechi ( cheie-valoare ). De asemenea, termenul DHT este asociat cu o serie de principii și algoritmi care vă permit să înregistrați date, distribuirea informațiilor între un anumit set de noduri de stocare și să le restaurați prin căutare distribuită după cheie. O caracteristică a unui tabel distribuit este capacitatea de a distribui informații între un set de noduri de stocare astfel încât fiecare nod participant să găsească valoarea asociată cu o anumită cheie. Responsabilitatea pentru menținerea relației dintre nume și valoare este distribuită între noduri, prin care schimbarea setului de membri determină un număr minim de întreruperi. Acest lucru vă permite să scalați cu ușurință DHT, precum și să monitorizați în mod constant adăugarea și eliminarea nodurilor și a erorilor în activitatea lor.

DHT este un cadru care poate fi folosit pentru a construi multe servicii complexe, cum ar fi sisteme de fișiere distribuite , distribuție de fișiere peer-to-peer și rețele de livrare de conținut , cache web cooperativ, multicast , anycast , serviciu de nume de domeniu și mesagerie instantanee . Rețele distribuite majore care utilizează DHT: rețea I2P , BitTorrent , rețea eDonkey ( Rețea Kad ) , YaCy , Tox and Coral Content Distribution Network . Este posibil să se creeze motoare de căutare prin rețeaua DHT.

Istorie

Cercetarea DHT a fost inițial motivată în special de sisteme peer-to-peer precum I2P , Napster , Gnutella , Freenet , care foloseau resurse distribuite pe Internet pentru a crea o singură aplicație. În special, au folosit internetul în bandă largă și spațiul pe hard disk pentru a oferi un serviciu de distribuție de fișiere.

Aceste sisteme diferă în ceea ce privește modul în care au găsit datele de la egal la egal:

Napster avea un server de index central: fiecare nod, după alăturare, trebuie să trimită o listă de fișiere stocate local către server, care trebuie să caute și să interogheze nodurile care conțin rezultatele. Această componentă centrală a făcut sistemul vulnerabil la atacuri și riscuri.
Gnutella și rețelele similare s-au mutat către un model de solicitare de inundații - practic, fiecare căutare ar avea ca rezultat trimiterea unui mesaj către toate mașinile din rețea. În timp ce evită eșecul centralizat, această metodă a fost semnificativ mai puțin eficientă decât Napster .
În cele din urmă, Freenet a fost și el complet distribuit, dar rutarea se bazează pe o cheie euristică, în care fiecare fișier are o cheie asociată, iar fișierele cu chei similare tind să se grupeze pe un set similar de noduri. Cel mai probabil, cererea a fost trimisă unor astfel de grupuri fără a fi nevoie să interogăți toți colegii. Cu toate acestea, Freenet nu a putut garanta că datele vor fi găsite.

DHT-urile folosesc rutarea cheilor mai structurate pentru a realiza descentralizarea I2P , Gnutella și Freenet , precum și eficiența și rezultatele garantate ale Napster . Un dezavantaj este că, la fel ca Freenet , DHT acceptă doar căutări cu potrivire exactă și nu căutări de cuvinte cheie, deși aceste caracteristici pot fi stratificate peste DHT.

Primele patru DHT - CAN , Chord , Pastry și Tapestry - au fost introduse în jurul anului 2001 . De atunci, acest domeniu de cercetare a fost destul de activ. În afara mediului academic, tehnologia DHT a fost acceptată ca o componentă a BitTorrent și a rețelei de distribuție a conținutului Coral .

Proprietăți

DHT se caracterizează prin următoarele proprietăți:

Descentralizare : o formă de sistem de noduri colective fără coordonare;
Scalabilitate : sistemul va funcționa la fel de eficient cu mii sau milioane de noduri;
Toleranță la erori : Sistemul va fi la fel de fiabil (într-un anumit sens) cu noduri care se conectează, se deconectează și se aruncă în mod constant erori.

O tehnică cheie pentru atingerea acestui obiectiv este ca orice nod să se coordoneze doar cu câteva noduri din sistem - de obicei O(log n ), unde n este numărul de participanți (a se vedea mai jos) - astfel încât să fie doar o cantitate limitată de muncă. efectuat la fiecare modificare a numărului de participanți.

Unele proiecte DHT caută să ofere protecție împotriva utilizatorilor rău intenționați și să permită participanților să rămână anonimi, deși acest lucru este mai puțin obișnuit decât în multe alte sisteme P2P (în special atunci când partajează fișiere); vezi Rețele anonime .

În cele din urmă, DHT trebuie să se ocupe de probleme mai tradiționale ale sistemului distribuit, cum ar fi echilibrarea încărcăturii, integritatea datelor și performanța (în special, asigurându-se că operațiunile precum rutarea și stocarea datelor sau căutările sunt finalizate rapid).

Structura

Structura DHT poate fi împărțită în mai multe componente majore. Se bazează pe un keyspace abstract, cum ar fi un set de șiruri de 160 de biți (numărul de biți poate varia). Schema de partiționare a spațiului cheie distribuie proprietatea cheii între nodurile participante. Rețeaua de suprapunere conectează apoi nodurile, ajutând la găsirea proprietarului oricărei chei din spațiul de taste.

Cu toate componentele la locul lor, o utilizare tipică a DHT pentru stocarea și afișarea informațiilor este următoarea: să presupunem că spațiul de taste este șiruri de 160 de biți. Pentru a stoca un fișier cu numele și informațiile date în DHT, din numele fișierului se găsește un hash SHA1 (valoare de 160 de biți) , din care se formează o cheie k (hash) de 160 de biți, după care se formează un mesaj put(k, data), где data - содержание самого файлаși trimis la orice nod participant în DHT. Mesajul trece de la un nod la altul prin rețeaua de suprapunere până când ajunge la singurul nod responsabil pentru cheia k, în conformitate cu schema de partiționare a spațiului de taste, unde va fi stocată perechea (k, date). Orice alt client poate obține conținutul fișierului făcând o cheie (k), adică obținând un hash al numelui fișierului , pentru a găsi datele asociate cheii prin trimiterea unui mesaj get(k). Mesajul va trece din nou prin suprapunere către nodul responsabil pentru cheie, care va răspunde că datele necesare sunt disponibile.

Componentele rețelei de partiționare și suprapunere a spațiului de cheie sunt descrise mai jos pentru a prezenta ideile de bază comune majorității sistemelor DHT. Multe evoluții diferă în detalii.

Partiționare keyspace

Majoritatea DHT-urilor folosesc diverse variante de hashing consistent pentru a mapa cheile la noduri. În centrul acestei metode de partiționare se află funcția , care definește conceptul abstract al distanței dintre taste și , care nu are nimic de-a face cu distanța geografică sau cu întârzierea rețelei. Fiecărui nod i se atribuie o singură cheie, numită identificatorul său (ID). Nodul cu ID deține toate cheile pentru care este cel mai apropiat ID calculat folosind . $\delta(k_1, k_2)$ $k_{1}$ $k_{2}$ $în$ $k_m$ $în$ $\delta(k_m, i_n)$

Exemplu. Chord DHT tratează cheile ca puncte pe un cerc și reprezintă distanța parcursă în sensul acelor de ceasornic în jurul cercului de la cheie la . Astfel, cercul keyspace este împărțit în segmente învecinate ale căror capete sunt identificatori de nod. Dacă și sunt ID-uri adiacente, atunci nodul cu ID conține toate cheile între și . $\delta(k_1, k_2)$ $k_{1}$ $k_{2}$ $i_1$ $i_2$ $i_2$ $i_1$ $i_2$

Hashingul consecvent are proprietatea principală că ștergerea sau adăugarea unui singur set de chei aparținând nodurilor ID-urilor adiacente nu afectează alte noduri.

DHT și BitTorrent

Atât DHT, cât și PEX îndeplinesc de fapt funcția principală a unui tracker BitTorrent - ajută participanții la partajarea fișierelor să învețe unul despre celălalt. Ei pot:

Ajutați participanții să se găsească mai repede . De exemplu, există un peer
X pe distribuție cu un port indisponibil. Peer Z se conectează la distribuție, care nu poate începe ea însăși o conexiune cu X și trebuie să aștepte până când X află despre asta. X tocmai a accesat trackerul și o va face în următoarea oră. Dar peer-ul Y se întoarce din nou la tracker și află despre noul peer Z. Dacă, în același timp, Y însuși a fost conectat de mult timp și este angajat în partajarea fișierelor cu X, atunci îi spune lui X adresa acestui nou peer Z prin PEX . Pot exista astfel de colegi Y pe distribuție o mulțime de. Acum X poate începe o conexiune cu Z fără a aștepta următoarea solicitare către tracker, ceea ce este deosebit de important dacă Z este deconectat până atunci. Cu o proporție mare de distribuitori de intrare și de ieșire, acest lucru reduce așteptarea ca aceștia să înceapă descărcarea.

Reduceți încărcarea pe tracker
Obținând adrese peer prin DHT sau PEX, clienții accesează tracker-ul mai rar, reducând astfel încărcarea.

Distribuirea suportului în perioadele de indisponibilitate a trackerului
Dacă trackerul este singura sursă de informații despre colegi, atunci distribuția se va opri treptat dacă este inoperabilă. Folosind PEX , clienții pot face schimb de informații între ei despre colegii cu care au avut sesiuni de comunicare, încetinind astfel procesul de oprire a distribuției. DHT vă permite să înlocuiți complet trackerul.

DHT vă permite să distribuiți fără un tracker
. O astfel de distribuție se numește trackerless ( trackerless ). Un torrent pentru acesta este creat fără o adresă de urmărire și clienții se găsesc reciproc prin DHT. Adevărat, în același timp, persoana care a început distribuția trebuie să aibă o adresă IP reală, accesibilă din exterior. Când participă la distribuții fără tracker, clienții BitTorrent capătă o anumită asemănare cu eMule folosind rețeaua Kad .

Cheie privată

În sistemele de urmărire publice (deschise), de unde oricine poate descărca un torrent și poate participa la distribuție, DHT și PEX servesc tuturor participanților.

Pentru trackerele private (închise), este în primul rând important ca numai utilizatorii înregistrați să poată participa la distribuții și să respecte anumite reguli. La prima solicitare a unui client, un tracker privat are posibilitatea de a-l împiedica să fie distribuit, pur și simplu fără a-i spune adresele altor clienți participanți. Prin urmare, este important pentru un tracker privat ca clienții să nu primească aceste adrese prin DHT/PEX.

DHT și PEX au apărut în clienții Azureus și BitComet în vara lui 2005. Administratorii multor trackere private au fost nemulțumiți de această nouă funcționalitate și, prin urmare, au început să interzică aceste noi versiuni de client pe tracker.

Apoi, dezvoltatorii clientului au propus o nouă cheie în interiorul fișierului torrent: private . Dacă este egal cu 1, atunci clientul este obligat să dezactiveze automat DHT/PEX pentru acest torrent, indiferent de dorința utilizatorului. Un astfel de torrent se numește Secure Torrent.

Aproape toate trackerele private moderne impun private:1 în toate torrentele postate pe tracker și, de asemenea, interzic mai multe versiuni învechite de clienți care acceptă DHT sau PEX, dar nu știu încă despre cheia privată . Se crede că utilizatorii de tracker pur și simplu nu pot folosi DHT / PEX pe distribuții și nu există nicio problemă. De fapt, pentru a nu ține cont de rating, este suficient să-ți înlocuiești cheia de acces cu oricare alta. Și nici măcar nu trebuie să-l furi. Este suficient să înregistrați un alt cont pentru a prelua cheia de acces de la acesta.

DHT și statistici

Această secțiune se aplică doar trackerelor private în care cheia privată nu este forțată în torrent , iar pentru unele distribuții (în funcție de dacă distribuitorul însuși a introdus cheia privată în torrent ) pot fi utilizate DHT și PEX.

Adesea, există o părere că DHT activat în client afectează urmărirea statisticilor clientului de către tracker, de exemplu, „distribuit prin DHT, astfel încât statisticile au trecut de tracker”. Nu este adevarat.

În primul rând, DHT/PEX este folosit doar pentru a obține adrese de la egal la egal. Nu se ține nici partajarea fișierelor, nici o contabilitate a statisticilor asupra acestora. Clientul raportează statisticile datelor descărcate și încărcate numai către tracker.

Adică, „distribuit prin DHT” înseamnă de fapt „Am primit informații despre unii (sau toți) colegii prin DHT și, probabil, unii colegi m-au găsit și prin DHT”.

În al doilea rând, deși clienții știu de obicei de unde și-au luat adresele de la egal la egal, niciun client nu separă traficul în „primit/trimis către colegii DHT” și „primit/trimis către colegii primit de la tracker”. Chiar dacă se dorește, i-ar fi dificil pentru client să facă acest lucru - unii colegi pot fi primiți atât de la tracker, cât și prin DHT sau PEX și, de multe ori, clientul nu știe cum și-a primit adresa peer-ul care începe conexiunea la acesta.

Clientul raportează trackerului datele totale despre volumele descărcate și date tuturor colegilor cu care a comunicat , indiferent dacă clientul a aflat despre colegii individuali prin tracker, DHT sau PEX sau dacă acel peer chiar a început conexiunea în sine. . Adică, chiar dacă utilizatorii „stângați” (care nu accesează trackerul) apar pe distribuție din cauza DHT/PEX, clientul va raporta în continuare trackerului tot ceea ce au descărcat și dat.

Contabilitatea corectă a statisticilor depinde doar de starea trackerului: tracker-ul funcționează - statisticile sunt luate în considerare, dacă nu funcționează - nu este luată în considerare. Numai în cazul unui tracker pe termen lung care nu funcționează, DHT / PEX poate juca un rol indirect, împiedicând partajarea fișierelor să dispară treptat pe o astfel de „distribuție fără a lua în considerare statisticile”.

Cum funcționează DHT

Implementarea rețelei distribuite în clienții BitTorrent se bazează pe o variantă de DHT numită Kademlia . În general, DHT (Distributed hash table) înseamnă un sistem distribuit descentralizat pentru combinarea unui număr mare de noduri care dispar și apar în mod constant și transferă eficient mesajele între ele. Diverse sisteme mai complexe sunt construite pe baza structurilor DHT, cum ar fi partajarea fișierelor P2P , stocarea în cache web cooperativă, serviciile DNS etc.

DHT utilizează protocolul UDP . Clienții BitTorrent „ascultă” pe același număr de port UDP pe care îl folosesc pentru conexiunile TCP de intrare . Dacă utilizați în mod activ DHT, atunci deschiderea acestui port UDP pentru acces din exterior este de dorit, dar nu este necesară - DHT va funcționa așa.

Fiecare client conectat este un nod separat în rețeaua DHT. Are propriul său ID unic (identificator), selectat aleatoriu din același spațiu de 160 de biți ca infohash și torrente.

Fiecare nod menține un tabel de rutare care conține informații de contact pentru multe dintre cele mai „apropiate” noduri de el și pentru câteva mai îndepărtate. „Apropierea” a două noduri este calculată din „asemănarea” ID-urilor lor și nu are nimic de-a face cu proximitatea lor geografică.

Când un nod dorește să găsească egali pentru o distribuție, compară infohash-ul acelei distribuții cu ID-urile nodurilor pe care le cunoaște, apoi trimite o solicitare nodului al cărui ID este cel mai asemănător cu acel infohash. Nodul respectiv îi returnează adresa nodului al cărui ID este și mai aproape de infohash-ul torrentului.

Apoi nodul nostru trimite o cerere noului nod și primește de la acesta adresa următorului nod, al cărui ID este și mai asemănător cu infohash-ul torrentului.

Astfel, solicitările clienților care participă la distribuția unui torrent cu un anumit infohash curg treptat către nodurile ale căror ID-uri sunt cel mai asemănătoare cu acest infohash. Aceste noduri își amintesc solicitările anterioare și toate nodurile solicitante ulterioare vor fi returnate adrese ale colegilor anteriori din aceeași distribuție.

Dezavantaje

Există mai multe protocoale incompatibile care deservesc rețele diferite.
Funcționarea clientului ca nod DHT creează o sarcină mare pe router (router).
Hashe-urile sunt publicate în mod deschis, ceea ce permite urmărirea interactivă a distribuțiilor (care este ceea ce folosesc deținătorii de drepturi de autor). [1] [2] [3]

Articole înrudite

Note

↑ Cercetătorii spionează utilizatorii BitTorrent în timp real . Preluat la 30 septembrie 2017. Arhivat din original la 21 august 2017. (nedefinit)
↑ Protocolul DHT . Consultat la 29 mai 2010. Arhivat din original pe 20 mai 2015. (nedefinit)
↑ Extensie pentru ca peers să trimită fișiere de metadate . Data accesului: 29 mai 2010. Arhivat din original pe 10 mai 2016. (nedefinit)

Link -uri

Descrierea protocolului DHT (traducere) (rusă)
Descrierea protocolului DHT la BitTorrent.org
pe Wiki Azureus
pe site-ul BitComet

Protocolul de schimb de fișiere BitTorrent ( programe client )
Autorii	Persoane Eric Clinker Bram Cohen Navin Companii BitTorrent Inc. Vuse, Inc.
Tehnologie	suprasămânță Schimb peer (PEX) Tabel hash distribuit (DHT) Broadcatching Criptare protocol ADN Multitracker Retracker anunta racla Cutia de semințe
Următoarele	The Pirate Bay isoHunt Mininova RuTracker.org pornolab.net free-torrents.org Demonoid 1337x
Motoare	IPB IPBTT phpBB 2 Torrent Pier Torrent Pier II phpBB3 ppkBB3cker xbtBB3cker SMF SMF Simplu Tracker TBDev Alte xbtit BTITeam Tracker TorrentTrader Torrent Hoster Tracker
Articole similare	TorrentFreak