Dystrybuowane Tabele Hashowe Kademlia

Metrika odległości XOR

Podstawa Kademlia polega na funkcji odległości zdefiniowanej nad identyfikatorami węzłów, które są obecnie liczbami 160-bitowymi lub 256-bitowymi generowanymi losowo lub wyliczanymi z klucza publicznego. Odległość między dwoma identyfikatorami A i B to prosto A XOR B, interpretowane jako niepodpisany całkowity. Ta pojedyncza operacja daje Kademlia wszystko, czego potrzebuje: jest symetryczna, co oznacza, że odległość od A do B zawsze równa się odległości od B do A, ponieważ XOR jest symetryczny. Dodatkowo spełnia nierówność trójkąta, więc odległość od A do C nigdy nie przekracza sumy odległości od A do B i od B do C. Te dwie właściwości są krytyczne w praktyce. Symetria oznacza, że gdy węzeł dowiaduje się o kontaktu poprzez przychodzący zapytanie, relacja ma znaczenie w obu kierunkach, co pozwala na prawidłową pracę aktualizacji pasywnych tabel konsultacyjnych. Nierówność trójkąta oznacza, że przestrzeń odległości zachowuje się dostatecznie podobnie do geometrycznej odległości, aby węzły mogły rozsądnie oceniać, które kontakty przyniosą im bliższe docelowemu punktowi bez tego, by dowolny kontakt był nieprawidłowo mylący. Zamiast banalnych podejść takich jak porównywanie identyfikatorów numerycznie lub używanie odległości w formie pętli krzyżowej jak w niektórych innych projektach DHT, XOR jest jednostronny i unikalny: dla każdego węzła A i dowolnej docelowej odległości d istnieje dokładnie jeden węzeł B taki, że A XOR B równa się d. Ta unikalność pozwala na proste podział przestrzeni identyfikatorów na zakresy odległości bez niepewności. Każdy węzeł efektywnie widzi siebie jako środek całej przestrzeni identyfikatorów, z każdym innym węzłem i kluczem położonym na pewnym określonym, dobrze zdefiniowanym odległości XOR. Ponieważ identyfikatory są przydzielane prawie losowo na ogromnej przestrzeni, większość par węzłów jest daleka, a tylko mała część przypadkowo jest bliska dowolnemu danemu węzłowi lub kluczowi, co dokładnie jest właściwością, którą k-bucket jest zaprojektowany do wykorzystania.

K-Buckety i Tabela Routingu

Noda Kademlia nie próbuje zapamiętywać każdego innego węzła w sieci. Zamiast tego utrzymuje tabelę routingu strukturyzowaną jako lista k-bucketów, jednego dla każdej pozycji bitowej w przestrzeni identyfikatorów. K-bucket i przechowuje kontaktów, których odległość XOR od tego węzła wynosi między dwiema do potęgi i a dwiema do potęgi i+1, a każdy k-bucket przechowuje maksymalnie k kontaktów, co w rzeczywistych zastosowaniach zwykle wynosi 20. Ponieważ identyfikatory są efektywnie losowe, około połowa wszystkich innych węzłów spadnie na najbardziej ostatni k-bucket, czterteczna część na drugi do końca, ósma część na trzeci i tak dalej. Dlatego k-bucketi pokrywające duże odległości muszą przechowywać ogromne liczby kontaktów, gdyby nie było ograniczenia. Granica k utrzymuje pamięć w granicach: węzeł zadowolony jest wypełnianie 159-tego k-bucketu tylko 20 z bilionów potencjalnie znanych dalekich węzłów, podczas gdy k-bucket 0 lub 1 pokrywający węzły bardzo bliskie w przestrzeni identyfikatorów może mieć tylko jednego lub dwóch kontaktów, ponieważ tak mało węzłów istnieje w taki blisko. Ta asymetryczna struktura jest sercem efektywności Kademlia. Węzeł wie dużo szczegółów o swoim bezpośrednim otoczeniu i coraz mniej szczegółów o regionach dalej, co dokładnie jest formą informacji potrzebnej do odpowiedzi na zapytania 'kto jest najbliżej tego klucza' efektywnie bez globalnych danych. K-buckety są utrzymywane w nowoczesnym stanie za pomocą polityki wyeliminowania najmniej ostatnio widzianych, a nie najmniej ostatnio używanych: kiedy nowy kontakt dotrze do pełnego k-bucketu, nod pings najstarszy wpis i zastępuje go tylko wtedy, gdy ten stary kontakt nie odpowie. To przeważa długotrwałe, stabilne węzły nad nowymi uczestnikami, ponieważ statystycznie węzły, które są online od dłuższego czasu, prawdopodobnie pozostaną online, co naturalnie skieruje sieć w stronę wiarygodności i odporności na pewne ataki rozprzestrzeniania się informacji, gdzie przeciwnik próbuje wprowadzić wiele nowych złośliwych kontaktów.

Iteracyjne Szukania i Logarytmiczne Skoki

Znalezienie węzłów odpowiadających za dany klucz odbywa się według iteratywnego procedurę nazywaną czasami szukanie węzła. Węzeł wyszukujący zaczyna od wyboru alpha najbliższych kontaktów, które już zna i są najbliżej celowego klucza (zwyczajowo alpha wynosi 3), a następnie zapyta je równolegle o najbardziej bliżne do tego klucza węzły, których znają. Na podstawie odpowiedzi tworzy wyszukujący aktualizowaną listę bliższych węzłów i powtarza proces, zawsze zapytując niezapytane wcześniej węże z najlepszej aktualnej grupy, aż jedna runda nie przyniesie żadnych nowych bliższych kontaktów niż te już znane. Wtedy najbardziej bliższe k węzły są uznawane za autorytetne dla danego klucza. To, co sprawia, że to szybkie, jest struktura wyimkowana przez bufora k: ponieważ znanie węzła staje się coraz rzadsze przy większej odległości, każdy skok w szukaniu tendencja do skaczenia na zakres bufora około połowy mniejszy niż poprzedni, co zmniejsza o około połowę dystans do celu na każdym kroku. To daje oczekiwany koszt wyszukiwania skalujący się z logarytmicznym rozmiarem sieci, a nie rozmiar sieci samego, więc sieć z milionem węzłów zwykle rozwiązuje szukanie w około 20 skokach, a podwójne rozmiar sieci dodaje tylko jeden dodatkowy skok na średnio. To logarytmiczne zachowanie pozwala Kademlia skalować do ogromnych sieci peer-to-peer jak główny DHT BitTorrent, który regularnie ma miliony współczesnych uczestników, podczas gdy utrzymuje niską i przewidywalną latencję wyszukiwania. Paralelizm zapytania o alpha węzłów jednocześnie również poprawia odporność: jeśli jeden kontakt jest wolny, wyłączony lub szkodliwy, wyszukanie nie zaszkodzi czekając na niego, ponieważ inne paralelnie działające gałęzie nadal postępują w kierunku celu.

Samonaprawianie poprzez pasywne aktualizacje

Jedną z najpiękniejszych własności Kademlia jest to, że jego tabele routingu automatycznie się lepieje jako efekt uboczny normalnej ruchu sieciowego bez potrzeby dodatkowego protokołu utrzymania. Gdy każdy węzeł otrzymuje dowolną wiadomość od innego węzła, niezależnie od tego, czy jest to zapytanie, które on sam zainicjalizował, odpowiedź na swoje własne zapytanie, czy nawet przychodzące żądanie od czegokolwiek innego, używa tej informacji o kontaktach do aktualizacji odpowiedniego k-kartoteki. Ponieważ metryka XOR jest symetryczna, wiadomość odebrane z węzła X powiadamia odbiorca dokładnie, w jakim kartocie należy się znaleźć, a odbiorca może natychmiast wprowadzić lub odświeży tę pozycję. To oznacza, że popularne, często kontaktowane węzły naturalnie pozostają blisko początku swojej kartoteki, ponieważ każda interakcja odświeża ich pozycję, podczas gdy węzły, które zamarzają, stopniowo starzeją się i są usunięte podczas próby wypełnienia karty na pełną moc. Praktyczny efekt to rodzaj ciągłego, tlenkowego samonaprawiania: gdy węzły dołączają, ich adresy propagują się po sieci jedynie poprzez zapytania i odpowiedzi, które naturalnie występują, a gdy węzły opuszczać lub porzucać, stare pozycje są usuwane ostatecznie wraz z czasem, gdy karty są testowane. Nie ma potrzeby uruchamiania regularnej globalnej spisu i nie ma koordynatora decydującego, kiedy odświeżać co. Aby obsługiwać kartoteki, które widzą niewielki ruch, takie jak te pokrywające odległe regiony przestrzeni ID, której węzeł rzadko ma powód do zapytania, Kademlia dodaje lekki mechanizm odświeżania kartoteki: jeśli karta nie została dotykana przez określony czas, węzeł wybiera losowy identyfikator w zakresie tej karty i wykonuje dla niego wyszukiwanie, co wymusza przepływ nowych informacji o kontaktach. Wspólne z pasywnymi aktualizacjami z normalnego ruchu, to sprawia, że każda część tablic routingu pozostaje prawidłowo aktualna nawet pod ciągłym zamieszaniem, co jest kluczowe dla rzeczywistych wdrożeń takich jak DHT BitTorrent, gdzie węzły połącza się i odłączają ciągle i niepewnie.

Kademlia w Praktyce

Kademlia została wprowadzona w 2002 roku przez Petara Maymounkova i Davida Mazièresa, a jej projekt okazał się wystarczająco trwały, aby służyć wielu z największych systemów peer-to-peer używanych obecnie. DHT BitTorrent główny używa wariantu Kademlia, który pozwala klientom znaleźć serwery udostępniające konkretny torrent bez potrzeby kontaktowania się ze ścisłym punktem kontrolnym, co sprawia, że tak zwane torrenty bez ścisłego punktu kontrolnego są możliwe i umożliwia odkrywanie sieci nawet wtedy, gdy punkt kontrolny jest wyłączony na stałe. IPFS, System Plików InterPlanetary, używa DHT opartego na Kademlia nazywanej libp2p Kademlia do mapowania identyfikatorów zawartości, które są haszami kryptograficznymi treści pliku, do serwerów obecnie przechowujących i dostarczających tę zawartość, co pozwala sieci na routowanie zapytań 'kto ma te dane' bez centralnego indeksu. Ethereum używa protokołu wzbudzonego inspiracji Kademlia nazywanego Protokół Odkrywania Nodów (Node Discovery Protocol) lub discv4/discv5, aby pozwolić na efektywną odkrywanie innych nodów do połączenia się i wymiany bloków oraz transakcji, służy to do zasychrowania warstwy gossipa, która utrzymuje blockchain w synkronizacji. Każdy z tych systemów dostosowuje podstawowe pomysły Kademlia do własnych potrzeb, czasami zmieniając rozmiar identyfikatora, wartość k lub dokładny mechanizm podziału butelek, ale podstawa routingu opartego na odległości XOR i samozakładającego się systemu k-bucketów pozostaje zdecydowanie taka sama. W porównaniu do wcześniejszych projektów DHT, takich jak Chord, który ustawia nody na logicznym pętli i używa tablic palce, lub Pastry i Tapestry, które używają drzew prefix-matching, Kademlia jest często preferowany ze względu na symetryczny metryk, który pozwala eleganckiemu technikowi uczenia się opartego na passivnym ruchu: ruch normalny w poszukiwaniu danych jednocześnie służy do utrzymania tablic routingu, co jest znacznie trudniejsze do osiągnięcia z czystym funkcją odległości jednostronnej lub asymetrycznej. Ta kombinacja prostej matematyki i praktycznego samozakładania jest dużą częścią powodów, dla których Kademlia stała się dominującym projektowaniem DHT w produkcyjnych programach peer-to-peer.

Często zadawane pytania

Wypróbuj na żywo

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