Tabel hash distribuit

Tabelele hash distribuite ( denumite și DHT -uri ) sunt o clasă de sisteme distribuite descentralizate care parționează apartenența unui set de chei între nodurile participante și pot transmite eficient mesajele către singurul proprietar al unei anumite chei. Fiecare nod este analogul unui slot de matrice dintr-un tabel hash.

DHT-urile sunt de obicei proiectate pentru a gestiona un număr mare de noduri, chiar și în cazurile în care există intrări continue sau defecțiuni bruște ale unora dintre ele. Acest tip de infrastructură poate fi utilizat pentru a implementa servicii mai complexe, cum ar fi sisteme de fișiere distribuite , sisteme de partajare de fișiere peer-to-peer , cache web cooperative , multicast , anycast și servicii de nume de domeniu .

Istorie

Inițial, cercetarea DHT a fost parțial motivată de sisteme peer-to-peer, cum ar fi Napster , Gnutella , Freenet , care se bazau sau se bazează pe resurse distribuite pe Internet pentru a furniza aplicația dorită. În special, aceste sisteme au profitat de creșterea lățimii de bandă și de creșterea spațiului pe hard disk pentru a oferi un sistem de partajare a fișierelor.

Aceste sisteme diferă unele de altele în modul în care au găsit datele conținute de colegii lor respectivi. Napster avea un index într-un server centralizat: fiecare nod, la intrarea sa, trimitea o listă a fișierelor pe care le deținea local către server, care urma să efectueze căutările și să le indice solicitanților nodurile care păstrau datele dorite. Această componentă centralizată a făcut sistemul vulnerabil la atac. Gnutella și rețele similare s-au mutat către un model de inundații; in esenta, fiecare cautare a fost de fapt constituita intr-un mesaj care a fost transmis tuturor celorlalte masini din retea. Deși această metodă a evitat posibilitatea unui singur punct de rupere, mecanismul a fost mult mai puțin eficient decât Napster. În cele din urmă, a existat Freenet care a furnizat un mecanism complet distribuit, dar utilizând o adresare euristică bazată pe chei, în care fiecare fișier era asociat cu o cheie, iar fișierele cu chei similare aveau tendința de a se grupa în seturi de noduri similare. Prin urmare, era probabil ca cererile să fie transmise prin rețea către aceste seturi de noduri fără a fi nevoie să viziteze mulți colegi. Cu toate acestea, Freenet nu a oferit certitudinea găsirii datelor necesare.

Tabelele hash distribuite folosesc un tip mai structurat de rutare bazată pe chei pentru a realiza atât descentralizarea Gnutella și Freenet, cât și eficiența și fiabilitatea căutărilor oferite de Napster. Un dezavantaj este că, ca și în Freenet, DHT-urile oferă căutare numai după titluri exacte și nu după cuvinte cheie, deși acest tip de funcționalitate poate fi plasat pe un strat superior de DHT.

Primele patru DHT - CAN , Chord , Pastry și Tapestry - au fost toate prezentate în același timp, în 2001 . De atunci, acest domeniu de cercetare a fost destul de activ. Dincolo de studiile academice, tehnologia DHT a fost adoptată ca o componentă a BitTorrent , eMule și în Coral Content Distribution Network .

Proprietăți

Caracteristicile DHT subliniază următoarele proprietăți:

• Descentralizare : nodurile formează în mod colectiv sistemul fără nicio coordonare centrală.
• Scalabilitate : sistemul este proiectat pentru o funcționare eficientă chiar și cu sute de milioane de noduri.
• Toleranță la erori : sistemul ar trebui să fie fiabil chiar și în prezența nodurilor care intră, părăsesc rețeaua sau sunt supuse unor defecțiuni cu frecvență înaltă.

Tehnica cheie folosită pentru atingerea acestor obiective este constituită din faptul că fiecare nod trebuie să rămână în contact doar cu un număr mic de alte noduri din rețea - de obicei ... din ceilalți n participanți (vezi mai jos) - în acest fel reteaua este supusa unui volum minim de munca pentru fiecare modificare care se produce in setul de noduri care o constituie.

Unele facilități DHT încearcă să implementeze mecanisme de securitate pentru a împiedica nodurile participante rău intenționate și pentru a permite nodurilor să rămână anonime, deși acest lucru este mai puțin obișnuit decât alte sisteme peer-to-peer (mai ales când vine vorba de partajarea fișierelor).

Structura

Un DHT este construit în jurul unui spațiu de taste abstract , cum ar fi un set de șiruri de 160 de biți . Calitatea de membru Keyspace este împărțită între nodurile participante în conformitate cu o schemă de partiționare bine definită. Rețeaua de suprapunere conectează nodurile, permițându-le să găsească proprietarul unei anumite chei în spațiul de taste.

Cu aceste poziții, operațiunea tipică a unui DHT pentru a stoca și apoi a prelua date se poate întâmpla în felul următor. Să presupunem că spațiul de taste este un set de șiruri de 160 de biți. Pentru a stoca un fișier caracterizat prin numele fișierului și parametrii de date în DHT, mai întâi se calculează hash-ul SHA1 al numelui fișierului , producând astfel o cheie k de 160 de biți . Ulterior, un mesaj put (k, date) poate fi trimis la orice nod din rețeaua DHT. Mesajul este transmis de la nod la nod prin rețeaua de suprapunere până când ajunge la nodul unic care este responsabil pentru cheia k conform regulilor de partiționare a spațiului de cheie, unde este stocată perechea (k, date) . Orice alt client poate prelua apoi conținutul fișierului calculând la rândul său hash-ul numelui fișierului pentru a obține k și cere oricărui nod din rețeaua DHT să găsească datele asociate cu k printr-un mesaj get (k) . Mesajul va fi apoi transmis prin suprapunere la nodul responsabil pentru k , care va răspunde cu o copie a datelor stocate.

Fiecare dintre aceste componente este descrisă mai jos pentru a stabili principiile de bază comune majorității DHT-urilor; unele mecanisme pot diferi în detaliu.

Partiționare keyspace

Multe DHT-uri folosesc o variantă de hashing consistent pentru a mapa cheile la noduri. Această tehnică folosește o funcție care definește noțiunea abstractă a distanței dintre cheie și cheie . Fiecărui nod i se atribuie o cheie care se numește identificator (ID). Toate cheile pentru care i este cel mai apropiat ID aparțin unui nod cu ID i , măsurat cu . $\ delta (k_ {1}, k_ {2})$$k_1$$k_2$$\delta$

Exemplu . Algoritmul Chord consideră cheile ca puncte pe un cerc și este distanța parcursă (în sensul acelor de ceasornic) pe cerc între și . Prin urmare, spațiul de taste circular este împărțit în segmente învecinate ale căror puncte finale sunt identificatorii de nod. Dacă și sunt două ID-uri adiacente, atunci nodul cu ID deține toate cheile care se încadrează între și . $\ delta (k_ {1}, k_ {2})$$k_1$$k_2$$i_ {1}$$eu_ {2}$$eu_ {2}$$i_ {1}$$eu_ {2}$

Hashingul consecvent are caracteristica fundamentală că eliminarea sau adăugarea unui nod modifică doar setul de chei deținute de nodurile cu ID-uri adiacente, fără a implica toate celelalte noduri. Acest lucru este spre deosebire de un tabel hash tradițional , în care adăugarea sau eliminarea unei găleți determină o remapare a aproape întregului spațiu de taste. Deoarece fiecare modificare a setului de chei pentru care este responsabil un nod corespunde de obicei unei mișcări intense (în ceea ce privește lățimea de bandă) de la nod la nod a obiectelor stocate în DHT, este necesară o minimizare a acestor mișcări de reorganizare pentru a face față eficient. cu colegii care au un comportament foarte dinamic (număr mare de intrări, ieșiri sau defecțiuni).

Rețea suprapusă

Fiecare nod menține un set de legături către celelalte noduri ( vecinii săi ). Împreună, aceste noduri formează rețeaua de suprapunere și sunt organizate într-un mod structurat, dând astfel formă topologiei rețelei .

Toate topologiile DPT împărtășesc o variantă a celei mai esențiale proprietăți: pentru fiecare cheie k , fie nodul deține k , fie are o legătură către un nod care este mai aproape de k în ceea ce privește distanța în spațiul cheie, așa cum este definit mai sus. În acest moment, este ușor să redirecționați un mesaj către proprietarul oricărei chei k folosind următorul algoritm lacom : la fiecare pas următor, transmite mesajul către vecinul al cărui ID este cel mai apropiat de k . Când nu există vecin cu aceste caracteristici, atunci am ajuns la cel mai apropiat nod de fapt, care trebuie să fie proprietarul lui k conform celor definite mai sus. Acest tip de rutare este uneori denumit rutare bazată pe chei .

Dincolo de corectitudinea de bază a acestui tip de rutare, există două constrângeri cheie în topologie pentru ca numărul maxim de pași succesivi în orice cale (întârziere) să fie scăzut, astfel încât solicitarea să fie îndeplinită rapid și numărul maxim de vecini ai fiecarui nod (gradul nodului) este scazut, pentru a mentine la un nivel redus costul general de intretinere. Există un compromis între aceste două criterii, care este fundamental în teoria grafurilor . Unele opțiuni comune sunt prezentate mai jos, unde n este numărul de noduri din DHT:

• Grad , extensie$O (1)$$O (\ log n)$
• Grad , extensie$O (\ log n)$$O (\ log n / \ log \ log n)$
• Grad , extensie$O (\ log n)$$O (\ log n)$
• Grad , extensie$O (n ^ {{1/2}})$$O (1)$

A treia alegere este cea mai comună, deși nu este cea mai bună în ceea ce privește compromisul grad/întârziere, deoarece această topologie permite de obicei o mai mare flexibilitate în ceea ce privește alegerea vecinilor. Acest lucru este util, de exemplu, pentru alegerea vecinilor care sunt conformi cu topologia și, în același timp, similari în ceea ce privește latența în rețeaua fizică subiacentă.

Pe lângă algoritmii de rutare, există mai mulți algoritmi care exploatează structura rețelei de suprapunere a unui DHT pentru a trimite un mesaj către toate nodurile, sau către un subset de noduri, ale DHT-ului însuși . Acești algoritmi sunt utilizați de aplicații pentru a efectua operațiuni de multicast pe suprapunere, pentru a efectua interogări de interval sau pentru a colecta statistici. Două sisteme bazate pe această abordare sunt Structella , care implementează inundarea și mersul aleator pe suprapunerea unei rețele Pastry, și DQ-DHT, care implementează un algoritm de interogare dinamică pe o rețea Chord .

Exemple

Protocoale și implementări DHT

• Coardă
• Kademlia
• ( RO ) Bamboo , pe bamboo-dht.org .
• ( RO ) Bunshin , pe planet.urv.es .
• ( EN ) CAN (Content Addressable Network)
• ( EN ) Sistemul DKS , pe dks.sics.se. Preluat la 8 mai 2019 (arhivat din original pe 20 ianuarie 2012) .
• ( RO ) Implementarea JGroups DHT , pe jgroups.org .
• Patiserie , pe freepastry.org . _ _
• ( RO ) Tapiserie și implementare nouă numită Chimera.

Aplicații care folosesc DHT -uri

• BitTorrent : Distribuția fișierelor. BitTorrent utilizează opțional un DHT ca tracker distribuit pentru a oferi o întâlnire între clienții care descarcă un anumit fișier.
• Rețeaua de distribuție a conținutului Coral
• eMule : partajarea fișierelor.
• NEOnet : partajarea fișierelor.
• Overnet : partajarea fișierelor.
• Transmitere : Open Source Bittorent Client .

Articole

• ( EN ) Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris și Ion Stoica. Căutarea datelor în sistemele P2P . În Comunicarea ACM, februarie 2003.
• ( RO ) Gurmeet Singh Manku. Dipsea: un tabel hash distribuit modular . Teză de doctorat (Universitatea Stanford), august 2004.
• ( RO ) Moni Naor și Udi Wieder. Arhitecturi noi pentru aplicații P2P: abordarea continuu-discretă . Proc. SPAA, 2003.

Link- uri externe

• DHT pe Torrent Wiki , pe torrent.culturaliberap2p.it . Preluat la 27 iulie 2010 (arhivat din original pe 24 august 2010) .
• ( EN ) Distributed Hash Tables, partea 1 de Brandon Wiley.
• ( EN ) Distributed Hash Tables leagă pagina Carles Pairot despre cercetarea DHT și P2P.
• ( RO ) Sloppy Hashing și Self-Organizing Clusters : publicații din proiectul Coral Content Distribution Network .
• ( EN ) Proiectul IRIS (Infrastructură pentru sisteme de internet rezistente)
• ( RO ) Diverse publicații DHT Pagina lui El-Ansary despre cercetarea DHT.