Skippowy graf: dezcentralizowany poszukiwania uporządkowane dla sieci peer-to-peer

Z list zskiptowych do grafów zskiptowych

Klasyczna lista zskiptowa to struktura danych jednostronna: jeden proces przechowuje posortowaną listę elementów, a następnie losowo ewaluuje niektóre elementy na wyższe 'wybrukowane' poziomy, co pozwala wyszukiwaniu skokiem przeskakiwać duże fragmenty listy zamiast chodząc od jednego węzła do drugiego. Wysokość wieży każdego elementu wybierana jest losowo, zwykle rzucając monetą i zatrzymując się po pierwszej reszce, co daje oczekiwany logarytmiczny liczbę poziomów i oczekiwany logarytmiczny koszt wyszukiwania. Graf zskiptowy pyta o trudniejszy problem: a jakby nie było jednej maszyny przechowującej listę, a każdy element był osobnym komputerem na sieci, każdy odpowiadający za siebie? Nie ma centralnego budowniczego, który decyduje o wysokościach wież lub łączeniu poziomów. Zamiast tego każda węzłowa jednostka samodzielnie generuje swój losowy wektor członkostwa, ciąg losowych cyfr (często bitów), całkowicie na własną rękę, bez potrzeby koordynacji ani komunikacji do jego produkcji. Jedna taka oszczędność lokalnej losowości okazuje się wyznaczać całą rolę węzła w emergencji globalnej strukturze. Dwa węzły, które przypadkowo dzielą długą wspólną prefiksową część wektorów członkostw, skojarzą się ze sobą na wielu poziomach; dwa węzły z całkowicie różnymi wektorami tylko kiedyś spotka się na poziomie zero. Ponieważ proces jest symetryczny i lokalny, grafy zskiptowe dziedziczą od list zskiptowych gwarancje logarytmicznej wyszukiwania i wstawiania, jednocześnie usuwając wymaganie, że każdy strony widzi całe obraz. To pojęciowy skok, który sprawia, że grafy zskiptowe są prawdziwie dystrybuowane struktury, a nie tylko sieciowe implementacje jednostronnych: topologia jest emergencją właściwości wielu samodzielnie losowych wyborów, a nie wynikiem kroku planowania centralnego, co dokładnie to, czego potrzebuje system z tysiącami niewierzących, niezawodnych i ciągle zmieniających się węzłów.

Poziomy, wektory członkostwa i ścieżka poszukiwania

Struktura grafu skippowego jest całkowicie określona tym, jak wektory członkostwa podziałują węzły na nadmiarowe listy łączone. Na poziomie 0, każdy z węzłów w sieci należy do jednej dużej listy łącznej, posortowanej według klucza, dokładnie tak jak dolna sztanga skippowego. To gwarantuje, że w najgorszym przypadku można znaleźć dowolny klucz, przesuwając się po poziomie 0, choć wolno. Na poziomie i dla i większych od zera, węzeł należy tylko do listy łącznej zawierającej inne węzły, których wektor członkostwa ma takie same pierwsze i cyfr, jak jego własny, a wewnątrz tej listy węzły są nadal posortowane według klucza. Węzeł o wektorze członkostwa zaczynającym się na '010...' będzie pojawiać się na liście poziomu 1 razem z wszystkimi innymi węzłami, które zaczynają się na '0', a na liście poziomu 2 tylko z węzłami, które zaczynają się na '01', i tak dalej, aż w końcu prawdopodobnie będzie sam lub razem z bardzo mało współwąskimi na jego osobistym maksymalnym poziomie. Ponieważ wektory członkostwa są losowe i około połowy wszystkich węzłów dzieli się na dowolne pierwsze cyfry, listy poziomu 1 są około pół tak duże jak listy poziomu 0, a listy poziomu 2 oczekiwanej wielkości to czwarta część, i tak dalej, z wykładniczym osłabieniem, które odzwierciedla wykładniczą rozkład wysokości wież w skippowym. Poszukiwanie klucza docelowego zaczyna się na najwyższym poziomie żądającego węzła, gdzie listy sąsiadów są krótkie, ale każdy skok pokrywa dużą odległość w przestrzeni kluczowej, a następnie porusza się w kierunku docelowego, opuszczając poziom co gdykolwiek sąsiedzi na bieżącym poziomie nadmiernie przekroczą lub zakończą. To powoduje taki sam oczekiwany liczebny czas skoków O(log n) jak w poszukiwaniu skippowego, ponieważ na każdym poziomie około pół pozostałych kandydatów jest wyeliminowanych, ale każdy pojedynczy skok w grafie skippowym to także prawdziwa wiadomość sieciowa między dwiema niezależnymi, fizycznie oddzielonymi maszynami, a nie dekodowanie wskaźnika w pamięci lokalnej.

Dlaczego kolejność przewyższa haszowanie dla zapytań zakresowych

Najważniejszą decyzją projektową oddzielającą graf skippowy od klasycznego rozproszonego tabeli hashowej (DHT) jest to, co zrobione jest z klucza przed jego umieszczeniem w sieci. Tabele hashowe takie jak Chord lub Kademlia przepuszczają każdy klucz przez funkcję haszującą przed decyzją o miejscu, które ono zajmuje, co jest brillianckie z punktu widzenia balansowania obciążenia: haszowanie rozprowadza klucze równomiernie po przestrzeni identyfikatorów, tak że żaden pojedynczy węzeł nie staje się hot spotem, a co więcej, sprawia, że zapytania precyzyjne są szybkie i predykcyjne. Ale haszowanie to operacja jednokierunkowa, a zamieszanie ruiniuje dokładnie to, co uczyniło pierwotne klucze znaczące dla wielu aplikacji – ich relatywną kolejność. Gdy klucz 42 i klucz 43 zostaną haszowane, ich wartości hash mogą znaleźć się w dowolnym miejscu przestrzeni identyfikatorów, sąsiadując lub oddalone o świat, bez związku z faktem, że 42 i 43 były sąsiadami w pierwotnej kolejności. To oznacza, że DHT może efektywnie odpowiedzieć na pytanie 'gdzie jest węzeł odpowiadający exact keyowi', ale nie może efektywnie odpowiedzieć na pytanie 'podaj mi każdy klucz między 42 a 100' bez sprawdzenia prawie każdego węzła. Graf skippowy nigdy nie haszuje klucza; węzły są uporządkowane i połączone według ich rzeczywistych, oryginalnych wartości kluczowych na każdym poziomie. To dokładnie dlaczego struktura obsługuje autentyczne zapytania zakresowe i uporządkowaną nawigację: zapytanie może rozpocząć się w dowolnym miejscu w sieci, używając wielopoziomowych list skiplist do skoków do sąsiedztwa docelowego zakresu, a następnie przejść po poziomie 0 w porządku rosnącym, aby wymyślić każdy pasujący klucz. Praca jest proporcjonalna do liczby znalezionych wyników plus koszty logarytmicznej wyszukiwania, aby dotrzeć tam, zamiast pełnego skanowania sieci. Ta właściwość ma ogromne znaczenie dla aplikacji takich jak rozproszone bazy danych, sieci czujników przesyłających ciągłe pomiary lub systemy plików potrzebujące zapytań prefixowych i zakresowych, dokładnie te obciążenia, gdzie DHT z jedynym zapytaniem precyzyjnym nie spełnia wymagań.

Lepkie zarządzanie ruchem

Dziwkoście sieci peer-to-peer nie są statyczne; maszyny dołączają, zatrzymują się, wyłączają i ponownie dołączają regularnie, co naukowcy nazywają ruchem. Dobry system rozproszony musi nadal działać i utrzymywać swoje gwarancje wydajności podczas tego ciągłego przepływu. Skip grafy zarządzają ruchem lepiej z powodów strukturalnych: ponieważ położenie każdego węzła w hierarchii jest wyznaczane jedynie na podstawie własnego, lokalnie generowanego i niezależnego wektora członkostwa, dołączanie lub opuszczenie węzła wpływa tylko na małą grupę sąsiadów, z którymi dzielą oni listę członkostwa na każdym poziomie, a nigdy nie na ogólny strukturę ani centralnie zarządzany indeks. Gdy nowy węzeł dotrze do sieci, generuje wektor członkostwa, używa istniejącego węzła jako punktu wejścia, wykonuje wyszukiwanie logarytmicznej głębokości, aby znaleźć swoje poprawne miejsce uporządkowane na poziomie 0, a następnie działa na górę, łącząc się z każdym poziomem listy łańcuchowej tam, gdzie jego wektor prefiksu pasuje, co stanowi oczekiwane O(log n) ilość pracy, dotykając tylko małej, lokalnej grupy istniejących węzłów. Wyjście jest zarządzane symetrycznie: sąsiedzi zauważają, że węzeł został usunięty, co zwykle wynika z okresowych sprawdzeń życia lub niepowodzenia wyszukiwań, a ich listy łańcuchowe są naprawiane do przepływu przez brak, ponownie odcinek lokalny i ograniczony naprawy, a nie globalne przebudowanie. Porównaj to z strukturami zależnymi od ogólnie zgody i centralnie obliczonej struktury, gdzie pojedyncze zmiany mogą wymagać ponownego obliczenia dużych części struktury. Ponieważ skip grafy rozprowadzają samodzielne generowanie losowości, jest również lepka degradacja podczas obciążenia: nawet jeśli naprawa ląduje nieco za opóźnieniem wobec przypływu ruchu, wyszukiwania degenerują płynnie ku wiarygodnej listy poziomu 0 zamiast całkowicie zakończyć się niepowodzeniem, ponieważ nadmiar poziomów pokrywających się oznacza, że zwykle istnieją wiele niezależnych ścieżek w kierunku dowolnej danej.

Gdzie są używane skippowe grafy w praktyce

Skippowe grafy wprowadzono przez Jamesa Aspnesa i Gauri Shah w początku lat 2000-nych jako odpowiedź na konkretną brakującą część szybko rozwijającej się literatury DHT: nikt nie posiadał struktury dezentralizowanej, która zachowuje oba logarytmiczne koszty wyszukiwania i zdolność do wykonania zapytań zakresowych i uporządkowanych. Ta kombinacja sprawiła, że skippowe grafy były atrakcyjne dla indeksowania bazy danych rozproszonej, gdzie aplikacje wymagają regularnie zapytań 'zakresu', a nie tylko dokładnych wyszukiwań, oraz dla systemów odkrywania zasobów, w których klienti szukają usług pasujących do zakresu kryteriów, takich jak dostępne pamięć lub przepustowość. Wpływ skippowych grafów obejmował projektowanie sieci połączeń strukturalnych, systemów plików rozproszonej potrzebujących wyszukiwania typu przedrostka i systemy publikacji-subskrypcji peer-to-peer, gdzie subskrybenci rejestrują zainteresowania w zakresach tematów lub wartości. Relatywnie i wpływowy pokrewiec skippowe sieć (SkipNet) osiągał podobne cele, skupiając się na lokalności treści i kontroli administracyjnej, pokazując, że jądro pomysłu, warstwowanie wielu list losowych kluczowanych przez wspólny przedrostek identyfikatorów niezależnie wygenerowanych, jest szablonem elastycznym, a nie jednym zaciętym protokołem. Warto być szczerymi w sprawie trade-off: utrzymanie wielu poziomów na każdym węźle kosztuje więcej stanu i wiadomości o utrzymaniu niż niektóre DHT, a skippowe grafy zazwyczaj założone są na przyzwoitą współpracę sieci, a nie aktywnie przeciwniczną, co jest inaczej dla niektórych wariantów DHT osłonionych przed szkodliwym routingu. Nie mniej jednak, dla dowolnego systemu, dla którego zachowanie kolejności kluczy i odpowiadanie zapytaniom zakresowych ma taką samą wagę co szybkie wyszukiwanie, skippowy graf pozostaje jednym z najczystszych ilustracji tego, jak lokalna losowość niezależna na każdym uczestniku może dodawać do spójnej i efektywnej struktury globalnej, naprawdę bez lidera.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Skip Graph: Decentralized Ordered Search for Peer-to-Peer Networks i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.