Proste podstawowe wyjaśnienie Distributed Hash Table (DHT)

177

Czy ktoś mógłby wyjaśnić, jak działa DHT?

Nic ciężkiego, tylko podstawy.

Gustavo Carreno
źródło

Odpowiedzi:

237

Ok, to dość prosty pomysł. DHT zapewnia interfejs podobny do słownika, ale węzły są rozproszone w sieci. Sztuczka z DHT polega na tym, że węzeł, który ma przechowywać określony klucz, jest znajdowany przez haszowanie tego klucza, więc w efekcie twoje zasobniki tablicy skrótów są teraz niezależnymi węzłami w sieci.

Daje to dużą odporność na awarie i niezawodność oraz prawdopodobnie pewne korzyści w zakresie wydajności, ale także wywołuje wiele bólów głowy. Na przykład, co się dzieje, gdy węzeł opuszcza sieć w wyniku awarii lub w inny sposób? I jak redystrybuować klucze, gdy węzeł łączy się, aby obciążenie było z grubsza zrównoważone. Pomyśl o tym, jak zresztą równomiernie rozprowadzasz klucze? A kiedy łączy się węzeł, jak uniknąć ponownego łączenia wszystkiego? (Pamiętaj, że będziesz musiał to zrobić w normalnej tabeli haszującej, jeśli zwiększysz liczbę segmentów).

Jednym z przykładów DHT, który rozwiązuje niektóre z tych problemów, jest logiczny pierścień n węzłów, z których każdy bierze odpowiedzialność za 1 / n przestrzeni kluczy. Po dodaniu węzła do sieci znajduje on miejsce na pierścieniu, aby usiąść między dwoma innymi węzłami i przejmuje odpowiedzialność za niektóre klucze w swoich węzłach siostrzanych. Piękno tego podejścia polega na tym, że żaden z pozostałych węzłów w pierścieniu nie jest dotknięty; tylko dwa węzły siostrzane muszą redystrybuować klucze.

Na przykład, powiedzmy, że w pierścieniu z trzema węzłami pierwszy węzeł ma klucze 0-10, drugi 11-20, a trzeci 21-30. Jeśli pojawi się czwarty węzeł i wstawi się między węzły 3 i 0 (pamiętaj, że są w pierścieniu), może wziąć odpowiedzialność za powiedzmy połowę przestrzeni kluczy 3, więc teraz zajmuje się 26-30, a węzeł 3 zajmuje się 21 -25.

Istnieje wiele innych struktur nakładkowych, takich jak ta, które używają routingu opartego na treści w celu znalezienia właściwego węzła, w którym ma być przechowywany klucz. Lokalizowanie klucza w pierścieniu wymaga przeszukiwania pierścienia po jednym węźle naraz (chyba że prowadzisz lokalną tablicę przeglądową, która jest problematyczna w DHT obejmującym tysiące węzłów), co jest routingiem O (n) -hop. Inne struktury - w tym pierścienie rozszerzone - gwarantują routing O (log n) -hop, a niektóre roszczą sobie routing O (1) -hop kosztem większej konserwacji.

Przeczytaj stronę wikipedii, a jeśli naprawdę chcesz dowiedzieć się więcej, sprawdź tę stronę kursu na Harvardzie, która ma dość obszerną listę lektur.

HenryR
źródło
23
+1 Dobra odpowiedź. W trzecim akapicie masz na myśli („Jednym z przykładów DHT, który rozwiązuje niektóre z tych problemów, jest logiczny pierścień n węzłów”) to Consistent Hashing. To naprawdę ciekawy temat, używany w Apache Cassandra, rozproszonej bazie danych stworzonej przez Facebooka. Link do artykułu (warto go przeczytać): cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf
santiagobasulto
5
Protokół wyszukiwania oparty na pierścieniu, który jest dość łatwy do zrozumienia, to Chord: pdos.csail.mit.edu/papers/chord:sigcomm01
ThomasWeiss
Czy możesz wyjaśnić, w jaki sposób klucz-wartość są przechowywane w węźle? Czy będzie to jakaś forma tablicy mieszającej czy bazy danych?
Wand Maker,
@HenryR, czy „pierścień węzłów” nie jest po prostu strukturą drzewa?
Pacerier
Uniwersytet Illinois uczy protokołu akordów co semestr w ramach zajęć poświęconych systemom rozproszonym, jeśli ktoś chce więcej materiałów do czytania - course.engr.illinois.edu/ece428/sp2018/lectures.html
Siddhartha
11

DHT zapewniają użytkownikowi ten sam typ interfejsu, co zwykła tablica haszująca (wyszukiwanie wartości według klucza), ale dane są rozproszone w dowolnej liczbie połączonych węzłów. Wikipedia ma dobre podstawowe wprowadzenie, które zasadniczo bym zwrócił, jeśli napiszę więcej -

http://en.wikipedia.org/wiki/Distributed_hash_table

Piotr
źródło
7

Chciałbym dodać do użytecznej odpowiedzi HenryR, ponieważ właśnie miałem wgląd w spójne haszowanie. Zwykłe / naiwne wyszukiwanie skrótu jest funkcją dwóch zmiennych, z których jedną jest liczba segmentów. Piękno spójnego haszowania polega na tym, że eliminujemy z równania liczbę segmentów „n”.

W naiwnym haszowaniu, pierwsza zmienna jest kluczem obiektu, który ma być przechowywany w tabeli. Nazwiemy klucz „x”. Druga zmienna to liczba segmentów „n”. Tak więc, aby określić, w którym wiadrze / maszynie znajduje się obiekt, musisz obliczyć: hash (x) mod (n). Dlatego zmieniając liczbę segmentów, zmieniasz również adres, pod którym przechowywany jest prawie każdy obiekt.

Porównaj to ze spójnym haszowaniem. Zdefiniujmy „R” jako zakres funkcji skrótu. R jest po prostu jakąś stałą. W spójnym haszowaniu adres obiektu znajduje się w hash (x) / R. Ponieważ nasze wyszukiwanie nie jest już funkcją liczby segmentów, w efekcie zmieniamy liczbę segmentów z mniejszą liczbą przemapowań.

http://michaelnielsen.org/blog/consistent-hashing/

thebiggestlebowski
źródło
1
I tak musiałbyś zmodyfikować, prawda? Powiedzmy, że masz 3 serwery. hash(x)/Rdaje 34500. Nadal musisz zrobić 34500% 3 .
Pacerier
Twój post na blogu jest niejasny przy okazji, powinieneś wymienić migawkę krok po kroku działającego przykładu, w którym węzły są dodawane i usuwane wraz z dodawanymi i usuwanymi wierszami.
Pacerier