Czy ktoś mógłby wyjaśnić, jak działa DHT?
Nic ciężkiego, tylko podstawy.
Czy ktoś mógłby wyjaśnić, jak działa DHT?
Nic ciężkiego, tylko podstawy.
Odpowiedzi:
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.
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 -
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ń.
hash(x)/Rdaje 34500. Nadal musisz zrobić 34500% 3 .