PL 
EnglishDomyślny
Українська💍 Haszowanie spójne — pierścień haszy
Odwzoruj klucze i serwery na pierścień haszy, aby dodanie lub usunięcie węzła zmieniało przypisanie tylko niewielkiej części kluczy. Węzły wirtualne wyrównują obciążenie — to technika stojąca za rozproszonymi cache'ami i DHT.
O haszowaniu spójnym
Haszowanie spójne (consistent hashing) rozwiązuje kluczowy problem systemów rozproszonych: jak przypisywać klucze danych do serwerów tak, aby dodanie lub usunięcie węzła przenosiło jak najmniej kluczy. Technika odwzorowuje zarówno klucze, jak i serwery na pozycje na okrągłym pierścieniu haszy o rozmiarze 2^32. Każdy klucz należy do pierwszego serwera znalezionego zgodnie z ruchem wskazówek zegara od jego pozycji. Przy naiwnym podejściu modulo (hash(klucz) mod N) zmiana N z jednej liczby serwerów na inną może przemapować niemal każdy klucz — co jest katastrofalne dla działającego na żywo cache’a. Haszowanie spójne ogranicza zakłócenia średnio do około 1/N kluczy, ponieważ zmienia właściciela wyłącznie łuk pierścienia sąsiadujący z dodanym lub usuniętym serwerem.
Węzły wirtualne (nazywane też replikami) to praktyczne udoskonalenie: każdy fizyczny serwer jest umieszczany na V pozycjach na pierścieniu zamiast jednej, dzieląc jego własność na wiele małych łuków. To znacząco wygładza rozkład obciążenia — bez węzłów wirtualnych pojedynczy serwer mógłby przypadkowo przejąć 40% kluczy; przy 100 i więcej węzłach wirtualnych rozkład zbliża się do idealnego 1/N na serwer. Dostosuj liczbę serwerów, liczbę węzłów wirtualnych i zbiór kluczy za pomocą suwaków, a następnie dodawaj lub usuwaj serwery, aby zaobserwować, jak niewiele kluczy (podświetlonych na biało) musi się przenieść.
Najczęściej zadawane pytania
Dlaczego haszowanie modulo powoduje masową redystrybucję kluczy przy zmianie liczby serwerów?
Przy hash(klucz) mod N pozycja, na którą mapowany jest każdy klucz, zależy od N. Gdy N się zmienia — powiedzmy z 4 na 5 — modulus zmienia się niemal dla każdego klucza, przemapowując około (N−1)/N ≈ 80% z nich. Haszowanie spójne eliminuje ten problem, oddzielając pozycje kluczy od liczby serwerów: każdy klucz zawsze mapuje się na tę samą pozycję na pierścieniu, a zmienia się jedynie wyszukiwanie zgodnie z ruchem wskazówek zegara, gdy serwer jest dodawany lub usuwany.
Ile dokładnie kluczy przenosi się, gdy do pierścienia dodawany jest serwer?
Gdy nowy serwer S zostaje umieszczony na pozycji p na pierścieniu, przejmuje łuk od poprzedniego serwera (zgodnie z ruchem wskazówek zegara) aż do p. Przenoszone są tylko klucze, które trafiają w ten łuk — przechodzą od poprzedniego właściciela do S. Średnio jest to 1/N wszystkich kluczy, gdzie N to nowa liczba serwerów. Wszystkie pozostałe klucze zostają przy swoich dotychczasowych właścicielach.
Jaki problem rozwiązują węzły wirtualne i ile ich stosować?
Przy jednej pozycji na serwer losowe rozmieszczenie na pierścieniu daje mocno nierówne długości łuków: niektóre serwery mogą otrzymać 3-krotność średniego obciążenia. Umieszczenie każdego fizycznego serwera na V pozycjach węzłów wirtualnych dzieli pierścień na V×N segmentów, uśredniając nierówności. Systemy produkcyjne (Amazon Dynamo, Cassandra) zwykle używają 100–200 węzłów wirtualnych na serwer, przy czym odchylenie standardowe obciążenia spada poniżej 10% średniej.
Jak działa wyszukiwanie klucza w czasie stałym?
Pozycje węzłów wirtualnych są przechowywane w posortowanej tablicy lub zrównoważonym drzewie poszukiwań binarnych. Aby znaleźć właściciela klucza, haszuje się klucz, otrzymując jego pozycję na pierścieniu, a następnie wykonuje wyszukiwanie binarne najmniejszej pozycji węzła wirtualnego, która jest większa lub równa pozycji klucza (zawijając do pozycji 0, jeśli żadna nie zostanie znaleziona). Takie wyszukiwanie działa w czasie O(log(V×N)) — praktycznie stałym dla ustalonych V i N.
Jakie rzeczywiste systemy korzystają z haszowania spójnego?
Amazon Dynamo (2007) spopularyzował haszowanie spójne z węzłami wirtualnymi dla swojego magazynu klucz-wartość; Cassandra odziedziczyła tę samą architekturę. Biblioteki klienckie Memcached (np. algorytm ketama) używają go do dzielenia kluczy cache między pulą serwerów. Sieci dostarczania treści oraz rozproszone tablice haszujące peer-to-peer (DHT), takie jak Chord i Kademlia, również opierają się na haszowaniu pierścieniowym.
Co dzieje się z danymi, gdy serwer ulega awarii i jest usuwany?
Jeśli serwer S ulegnie awarii, jego pozycje węzłów wirtualnych stają się wolne. Klucze, które należały do S, przechodzą teraz na własność kolejnego serwera zgodnie z ruchem wskazówek zegara dla każdego łuku. Jeśli skonfigurowana jest replikacja (zwykle 3 repliki w Cassandrze), dane już istnieją na kolejnych N−1 serwerach zgodnie z ruchem wskazówek zegara, więc klaster nadal obsługuje odczyty bez utraty danych. Kworum zapisu zapewnia spójność podczas przełączania awaryjnego.
Jak haszowanie spójne odnosi się do Chord DHT?
Chord (Stoica i in., 2001) to protokół wyszukiwania peer-to-peer zbudowany bezpośrednio na haszowaniu spójnym. Każdy węzeł otrzymuje pozycję na 160-bitowym pierścieniu SHA-1. Chord dodaje „tabelę palców” (finger table) z O(log N) skrótami na węzeł, dzięki czemu dowolny klucz można zlokalizować w O(log N) skokach — łącząc haszowanie spójne z wydajną rozproszoną strukturą routingu.
Czy haszowanie spójne radzi sobie z serwerami o różnych pojemnościach?
Tak. Przypisując więcej węzłów wirtualnych serwerowi o wyższej pojemności — powiedzmy 200 węzłów wirtualnych maszynie z dwukrotnie większym RAM-em wobec 100 dla standardowego węzła — jego udział w pierścieniu rośnie proporcjonalnie do jego pojemności. To ważone haszowanie spójne jest wykorzystywane przy alokacji tokenów w Cassandrze oraz przez chmurowe load balancery do kierowania większego ruchu na większe instancje.
Czym jest haszowanie spójne z „ograniczonym obciążeniem”?
W 2017 roku Google opublikowało pracę „Consistent Hashing with Bounded Loads”, która dodaje ograniczenie pojemności: żaden serwer nie może posiadać więcej niż (1 + ε) razy średnią liczbę kluczy. Gdy docelowy serwer jest przeciążony, klucz jest przypisywany do kolejnego serwera zgodnie z ruchem wskazówek zegara, rozkładając obciążenie bardziej równomiernie. Ten wariant jest używany w produkcyjnych load balancerach Google.
Jak wybór funkcji haszującej wpływa na rozkład na pierścieniu?
Dobra funkcja haszująca musi równomiernie rozkładać zarówno klucze, jak i etykiety węzłów wirtualnych na 2^32-bitowym pierścieniu. Słabe funkcje haszujące powodują grupowanie, przez co niektóre łuki są znacznie dłuższe niż średnia, nawet przy wielu węzłach wirtualnych. W praktyce popularnymi wyborami ze względu na szybkość i jednorodny rozkład są FNV-1a, MurmurHash3 i xxHash.