Chord: Znalezienie dowolnego klucza w sieci P2P w O(log n) skoków

Problem: znalezienie jednego klucza wśród miliona węzłów, bez katalogu

Sieć peer-to-peer nie ma centralnej serwera, na który moglibyśmy zapytać „kto ma klucz X?” — to by tylko powróciło do pojedynczego punktu fałszowania, który P2P próbuje uniknąć. Tabele haszujące rozproszone rozwiązują ten problem, przypisując każdemu węzłowi i kluczu pozycję w tym samym przestrzeni adresowej oraz deterministyczne zasady, które określają, który węzeł jest odpowiedzialny za dany klucz. Dzięki temu każdy węzeł może znaleźć właściciela dowolnego klucza bez katalogu, korzystając tylko z lokalnej informacji i ograniczonego numeru skoków.

Chord, opublikowany przez Stoicę, Morrisa, Karger, Kaashoeka i Balakrishnan w MIT w 2001 roku, jest najprostszym z klasycznych projektów Tabeł Haszujących Rozproszonej (wraz z Pastry, Kademlia i CAN). Cała jej struktura opiera się na jednym pojęciu: haszowanie wszystkiego — adresów IP węzłów oraz nazw kluczy — za pomocą funkcji haszującej spójnej (SHA-1 w oryginalnym artykule) do tego samego koła identyfikatora o rozmiarze 2^m.

Pętla i zasada succesor

Po tym, jak każdy węzeł i klucz ma identyfikator m-bity na pętli 0..2^m-1, odpowiedzialność kierowana jest jednym przepisem: klucz k należy do pierwszego węzła, którego identyfikator jest równy lub natychmiast po k, poruszając się w kierunku zegara — nazywane succesor(k). Ta pojedyncza deterministyczna zasada stanowi całą specyfikację „kto ma co”; nie ma niczego do negocjowania ani zgody.

ring size = 2^m               (m = 160 with SHA-1, in the original paper)
nodeID    = hash(IP address)
keyID     = hash(key name)
owner(key) = the first node whose ID >= keyID, walking clockwise around the ring
             (wrapping past 2^m-1 back to 0 if necessary)

Proste routingu jest poprawne, ale wolne

Jeśli każdy węzeł wiedziałby tylko swojego bezpośredniego sucesora na pętli, nadal można było znaleźć dowolny klucz — wystarczy przechodzić w kierunku zegara node po node pytanym: „czy jesteś właścicielem tego klucza?”. Ale to wymaga O(n) skoków dla n węzłów, co jest bezużyteczne na prawdziwych skalach: sieć z milionem węzłów potrzebowałaby do jednej operacji wyszukiwania aż miliona przesylanych wiadomości.

Tablice palce: trik O(log n)

Przyczyną Chordu jest tablica palców: każdy węzeł przechowuje do m wskaźników, gdzie i-ty palec wskazuje na sucesora (nodeID + 2^(i-1)) mod 2^m. W prostych słowach, węzeł przechowuje skróty do około czwartej części okręgu, ósmej, szesnastej i tak dalej aż do najbliższego sąsiada — podwójne odległości, dokładnie jak wskaźniki w liście przeskocznej lub poziomy binarnego wyszukiwania.

palce[i] = sucesor( (nodeID + 2^(i-1)) mod 2^m ) dla i = 1..m // szukanie(key) na węźle n: jeśli key jest między n a n.successor: zwróć n.successor // znaleziono to inaczej: przesuń zapytanie do palca najbardziej przed key // największa skok, który nie przeskoczy (ten węzeł powtarza tę samą regułę) Każdy skok co najmniej połowia dystans pozostały na okręgu do klucza docelowego, ponieważ wybrany palec jest najbliższym poprzednim węzłem do docelowego wśród wszystkich O(log n) kandydatów — więc liczba skoków do rozstrzygnięcia dowolnego zapytania to O(log n), a każdy węzeł musi przechowywać tylko O(log n) stan routingu zamiast znaczyć się dla każdego innego węzła w sieci. Dla sieci z milionem węzłów to około 20 skoków zamiast do miliona — różnica między zapytaniem rozwiązującym się w kilkunastu milisekundach a tym, które nie rozwiąże się przez całe życie człowieka.

finger[i] = successor( (nodeID + 2^(i-1)) mod 2^m )   for i = 1..m

// lookup(key) at node n:
if key is between n and n.successor:  return n.successor        // found it
else:  forward the query to the finger farthest before key      // biggest jump that doesn't overshoot
        (that node repeats the same rule)

Nody dołączają i opuszczają ciągle — to jest norma, nie wyjątkowość

Sieci peer-to-peer doznajują ciągłego ruchu: nody dołączają, opuszczone i zdarza się im awaria bez ostrzeżenia, znacznie częściej niż serwery w centrum danych. Chord zarządza tym dwiema mechanizmami działającymi razem. Po pierwsze, każda nod podtrzymuje mały listę sukcesorów (nie tylko jednego sukcesora), tak że jeśli jego bezpośredni sukcesor zginie, może przełączyć się na najlepszy możliwy zastępca bez przerwania pętli. Po drugie, kontynuacyjny protokół stabilizacji działa w tle: co określony czas każda nod sprawdza, czy wskaźnik poprzednika swojego sukcesora jest bardziej dokładny niż jej własny, a następnie informuje swojego sukcesora o swoim istnieniu, naprawiając pętlę i odświeżając tabele palców nawet podczas dołączania i opuszczań nodów.

Dzięki kontynuacyjnej nature stabilizacji, pętla może być na krótko niezgodna bezpośrednio po wypuknięciu ruchu — wyszukiwanie w trakcie naprawy może wymagać kilku dodatkowych skoków, lub rzadko nawet zakończyć się niepowodzeniem — ale oryginalny artykuł Chord udowodnia, że dopóki prędkość ruchu nie przekroczy prędkości stabilizacji, pętla samoczynnie naprawia się i poprawność jest zachowana, tylko z tymczasową ograniczoną stratą w szybkości wyszukiwania.

Oszczędzanie kluczy przy dołączaniu węzła: dlaczego tylko O(1/n) kluczy się przesuwa

Właściwość, która sprawia, że Chord (oraz ogólnie mówiąc oszczędzanie kluczy przy zmianie konsystentnego hashingu) jest atrakcyjna w porównaniu do standardowej tabeli haszującej rozdzielonej między n serwerami, to co się dzieje, gdy zwiększa się lub zmniejsza wartość n. W przypadku standardowego haszenia modulo — server = hash(key) mod n — dodanie lub usunięcie jednego serwera zmienia docelowy adres prawie dla każdego klucza, ponieważ n zmieniło się w mianowniku. Na okręgu konsystentnego hashingu, dołączony węzeł przejmuje kontroli nad ciągłą łancuchem kluczy między sobą a jego nowym poprzednikiem — pozostali węzły pozostają niezmieniwsze. Oczekiwana liczba przesuniętych kluczy podczas dołączania lub odejścia wynosi O(1/n) wszystkich kluczów, a nie O(wszystkich), co jest głównym powodem dla czego DHT są w stanie być używane w systemach dodając i usuwających pojemność regularnie.

Gdzie to pojawia się poza udostępnianiem plików

Idei Chorda są bezpośrednim przodka większości systemów produkcyjnych, których inżynierzy używają bez myślenia o DHT (Distributed Hash Table): Amazon's Dynamo (a także Cassandra i Riak) używa zgodnej haszowania na okręgu do podziału danych; biblioteki klientów memcached używają zgodnego haszowania, aby ustalić, który serwer bufora ma kontrolę nad danym kluczem; tryb bez śledza w BitTorrent działa na Kademlii, siostrze DHT z nieco innym (XOR) miarą odległości, ale tą samą ideą routingu logarytmicznego. Mechanizmy konkretnych mekanizmów pętli i stacji palcowych mogą się różnić, ale podstawowy traktat — ograniczona stan routingu, logarytmiczne skoki, minimalna interwencja przy zmianie członków — to ta sama zagadnienie, które Chord rozwiązał pierwszy i najprościej.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz P2P Network: Chord Distributed Hash Table — Finger-Table Routing i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.