Facultatea de Informatica Iasi

Chordy. Tabela HashDistribuita

Author:Aurelian Hreapcaaurelian.hreapca@info.uaic.ro

Decembrie 2, 2014

1

1. Abstract

O Tabela Hash Distribuita(DHT) reprezinta un mecanism distribuitsi descentralizat pentru asocierea unei valori hash(cheie) la un continutde un anumit tip. Chordy reprezinta o implementare a protocoluluiChord si suporta o singura operatie, de tipul: data o cheie, asociazacheia cu un nod din retea.

2. Introducere

Una din operatiile importante intr-un sistem peer-to-peer o reprez-inta gasirea eficienta a datelor. Un DHT trebuie sa respecte urma-toarele proprietati: datele pot fi mereu gasite in retea, fiecare nod tre-buie sa detina informatii despre un numar relativ mic de alte noduri,numarul de hop-uri realizate pentru a gasi date este mic si poate su-porta veniri si plecari ale nodurilor. Chordy foloseste pentru asignareacheilor o functie de hash consistenta, Highest Random Weight Hash(HRW). HRW produce o distribuire echilibrata a cheilor pe noduriledin retea, astfel incat la plecarea unui nod sunt necesare un numar micde mutari.

3. Tehnologii utilizate

3.1. Paradigma Peer-To-Peer. O retea P2P reprezinta un sistemdistribuit in care nodurile lucreaza fara coordonarea unui server cen-tral. Desi majoritea sistemelor P2P sunt hibride(avand supernoduri sauservere cu diferite roluri), Chordy se bazeaza pe o arhitectura Peer-To-Peer pura. Venirea unui peer in retea se realizeaza in trei pasi:trimiterea unei cereri catre un nod din retea si alocarea unui identifica-tor(1), trimiterea unei cereri de copiere a tabelei de rutare(2) si gasireacorecta a vecinilor(3). La plecarea unui nod din retea, acesta va trimiteun mesaj catre toate nodurile din tabela sa de rutare.

3.2. Protocolul Chord. In aplicatia Chordy nodurile sunt aranjateintr-un spatiu circular cu 2m pozitii. La sosirea in retea, oricarui nodi se atribuie un identificator unic global(GUID) pe m biti aplicandfunctia hash SHA-1 asupra adresei IP. Un nod este responsabil cu sto-carea tuturor datelor a caror cheie se afla intre identificatorul sau siID-ul succesorului. Fiecare nod va avea conexiuni cu cel mult alte mnoduri. In Chordy, a i-a conexiune a nodului x o reprezinta nodulsuccesor((x + 2i)mod 2m). Aceste conexiuni sunt retinute intr-un fin-ger table.

3.3. Highest Random Weight Hashing (HRW). Reprezinta unalgoritm care permite clientilor sa obtina o intelegere distribuita.

2

3.4. Transmission Control Protocol (TCP). Comunicarea dintreun nod si nodurile din finger table-ul asociat sunt realizate prin TCPdatorita caracterului orientat conexiune, dar in primul rand confir-marii(Acknowledge Number).

4. Arhitectura aplicatiei

4.1. Rutarea.Gasirea datelor. Pentru a gasi date, un nod calculeazavaloarea hash a cheii asociate. Exista trei cazuri:

• nodul sa stocheze cheia respectiva• cheia respectiva sa poata fi gasita direct din finger table-ul

nodului• cheia respectiva sa nu poata fi gasita direct din finger table-ul

nodului.

Pentru cel de-al treilea caz se va afla predecesorul cheii si se vor trimitemesaje catre cel mai apropiat nod de predecesor aflat in finger table.

4.2. Finger Tables. In Finger Table-ul asociat unui nod X se vorretine maxim m noduri si avem urmatoarele relatii:

X.finger[k].start = (X + 2k−1)mod 2m

X.finger[k].interval = (X.finger[k].start, X.finger[k + 1].start)

X.finger[k].node = primul nod cu ≥ X.finger[k].start

succesor(X) = urmatorul nod dupaX pe cerc

predecessor(X) = nodul dinaintea luiX pe cerc

distance(X, Y ) = (X − Y + 2m)mod2m

4.3. Metode. Cateva din functionalitatile Chordy sunt prezentate inrandurile urmatoare:create - Creaza un inel Chord. In caz de eroare va returna un codspecific erorii. In caz de succes va returna GUID-ul asociat.join IP - Se conecteaza la inelul Chord din care face parte peer-ul dela adresa IP . In caz de eroare va returna un cod specific erorii. In cazde succes va returna GUID-ul asociat.leave - Paraseste reteaua chord la care este conectat.put key value - Insereaza o pereche de tipul (cheie, valoare). Va re-turna un cod de eroare/succes.get key - In caz ca exista cheia respectiva va returna valoarea asociata,altfel va returna un cod de eroare.import file - Insereaza toate perechile (cheie, valoare) aflate intr-unfisier XML dat ca argument.

3

5. Detalii de implementare

5.1. Veniri si plecari ale nodurilor. Intr-o retea dinamica, ca ceacreata de Chordy, nodurile vin si pleaca in oricare moment. Pen-tru a pastra eficienta aplicatiei, finger table-urile trebuie sa fie mereucorecte si actualizate. Pentru a simplifica mecanismul de sosire si ple-care fiecare nod va pastra un pointer catre predecesorul sau. Cand unnod soseste se vor realiza 3 actualizari:

• Se initializeaza predecesorul si finger table-ul asociat• Se actualizeaza finger table-urile si predecesorii nodurilor deja

existente pentru a adauga nodul nou venit• Se transfera datele corespunzatoare catre noul nod venit

Complexitatea pentru sosirea/plecarea unui nod este O(m2) pentru uninel cu 2m pozitii.

5.2. Adaugarea si Interogarea. Numarul maxim de mesaje ce tre-buie trimis pentru a gasi succesorul oricarui nod este m. Astfel putemconcluziona ca distanta intre oricare doua noduri este de ordinul O(m)pentru un inel cu 2m pozitii.

5.3. Concurenta. Fiecare nod din inelul Chord poate sustine maimulti clienti concomitent. Acest lucru este realizat prin multiplexareainputului si outputului (select()) si folosirea thread-urilor.

6. Concluzii

6.1. Utilizari. Aplicatia de fata poate fi folosita pentru proiectul Part2Part.De asemenea poate constitui un substituent pentru DNS sau o solutiepentru un sistem de caching distribuit sau chiar un NFS.

6.2. Imbunatatiri. Unele imbunatatiri care pot fi aduse solutiei infaza curenta sunt urmatoarele:

• tratarea unor veniri/plecari simultane• picarea unuia sau mai multor noduri

7. Bibliografie

http://pdos.csail.mit.edu/papers/chord:sigcomm01/chordsigcomm.pdfhttp://www.cs.usfca.edu/ brooks/S06classes/cs682/slides/dht.pdfhttp://thor.info.uaic.ro/ adria/teach/courses/net/cursullaboratorul.php