Stałe Haszowanie: Pierścień, który ledwie przetasowuje

Problem z serwerem = hash(klucz) % n

Oczywistym sposobem na rozłożenie kluczy na n serwerów pamięci podręcznej jest serwer = hash(klucz) % n. Jest to pojedyncza linia kodu, która idealnie równomiernie rozprowadza obciążenie – o ile n nigdy się nie zmienia. W momencie dodania szóstego serwera do klastra o pięciu węzłach, reszta operatora modulo odwraca się z %5 na %6 dla zasadniczo każdego klucza i serwer, do którego każdy klucz mapuje, prawie losowo skacze. W oczekiwaniu około (n-1)/n wszystkich kluczy – około 83% dla n=6 – trafia na inny serwer niż wcześniej, mimo że tylko jeden serwer faktycznie się zmienił. Każdy z tych kluczy jest teraz nieudanym trafieniem w pamięć podręczną i wszystkie przychodzą do bazy danych pierwotnej naraz, gdy klastr jest już dodatkowo obciążony ze względu na skalowanie.

Umieszczanie serwerów i kluczy na tym samym pierścieniu

Spójne haszowanie, opublikowane przez Karger'a et al. w MIT w 1997 roku, rozwiązuje to poprzez haszowanie serwerów i kluczy do tego samego obszaru i ułożenie tego obszaru jako okrąg — pierścień haszujący — przebiegający od 0 do 2³²−1 i wracający do 0. Zarówno nazwy serwerów, jak i klucze są przekształcane przez jedną funkcję haszującą (zazwyczaj szybkie, niekryptyczne hasze takie jak MurmurHash3 lub xxHash, ponieważ tutaj liczy się przede wszystkim jednorodność, a nie bezpieczeństwo) aby uzyskać pozycję na tym okręgu. Klucz należy do serwera, który znajduje się w pierwszym miejscu zgodnie z ruchem wskazówek zegara od własnej pozycji klucza — bez modułu, bez stałej tabeli rozmiaru, jedynie "przejdź zgodnie z ruchem wskazówek zegara aż napotkasz serwer."

Tylko sąsiednie łuk się przesuwa

Ta pojedyncza zmiana sposobu obliczania własności ma dramatyczny skutek. Kiedy nowy serwer jest wprowadzany w pozycji P pomiędzy istniejącymi serwerami A i B, tylko klucze, które wcześniej znajdowały się w łuku między A i P, muszą się przemieścić – teraz należą do nowego węzła zamiast kontynuować podróż do B. Każdy klucz gdziekolwiek indziej na pierścieniu nadal znajduje ten sam serwer zgodnie z ruchem wskazówek zegara od niego, ponieważ nic nie zmieniło jego sąsiedztwa. Usuwanie serwera działa w ten sam sposób odwrotnie: jego klucze po prostu przechodzą do następnego serwera zgodnie z ruchem wskazówek zegara. // wyszukiwanie: pierwsza pozycja na pierścieniu >= hash(klucz), binarne przeszukiwanie posortowanych pozycji function getServer(key, sortedPositions, ring) { const pos = hash32(key); let lo = 0, hi = sortedPositions.length - 1; while (lo > 1; // wrap to first node if (sortedPositions[mid] < pos) { lo = mid + 1; } else { hi = mid - 1; } return ring.get(sortedPositions[idx]); } // oczekiwane klucze przemapowane, gdy do pierścienia o n węzłach dołącza lub odchodzi jeden serwer ≈ 1/n Dla pierścienia o pięciu węzłach dodanie szóstego serwera remapuje tylko około 1/6 kluczy zamiast 5/6 – redukcja w przybliżeniu (n-1)× w porównaniu z naiwnym hashamiowaniem modulo, a jest to minimalny teoretyczny limit: nie można zwiększyć pojemności bez przeniesienia niektórych kluczy na nowy serwer, ale consistent hashing gwarantuje, że nigdy nie trzeba przesunąć więcej niż koniecznie.

// lookup: first ring position >= hash(key), binary search over sorted positions
function getServer(key, sortedPositions, ring) {
  const pos = hash32(key);
  let lo = 0, hi = sortedPositions.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (sortedPositions[mid] < pos) lo = mid + 1; else hi = mid;
  }
  const idx = lo >= sortedPositions.length ? 0 : lo;   // wrap to first node
  return ring.get(sortedPositions[idx]);
}
// expected keys remapped when 1 node joins or leaves an n-node ring ≈ 1/n

Wirtualne węzły: wygładzanie nieregularnego pierścienia

Dzięki niewielkiej liczbie fizycznych serwerów, ich losowe położenie na pierścieniu może przypadkowo zgęszczać się w skupiska, pozostawiając jeden serwer odpowiedzialny za ogromny fragment a drugi za prawie nic. Rozwiązaniem jest użycie wirtualnych węzłów: każdy fizyczny serwer jest hashowany do wielu pozycji na pierścieniu (Apache Cassandra domyślnie ustawia to na 256 na węzeł, historycznie często 100-200 w innych systemach), każda stanowi oddzielny, mały fragment. Przy wystarczającej liczbie wirtualnych węzłów na serwer, prawo dużego mnożnika zaczyna działać i każdy fizyczny serwer odpowiada prawie równej całkowitej części pierścienia – a mocniejszy serwer może po prostu otrzymać więcej wirtualnych węzłów, aby absorbować proporcjonalnie większą część obciążenia, czysty mechanizm dla sprzętu o heterogenicznych właściwościach.

Gdzie pojawia się pierścień

Spójne haszowanie stanowi warstwę routingu znajdującą się pod większością elastycznych rozproszonych systemów przechowywania. Klienty Memcached wykorzystują je (poprzez bibliotekę libketama) tak, aby dodanie węzła pamięci podręcznej nie zwalniało całej klastra pamięci podręcznej. Amazon DynamoDB i Apache Cassandra używają partycjonowania pierścieniowego z wirtualnymi węzłami (konfigurowalną liczbę tokenów w Cassandrze) połączone z listą preferencji w kierunku zegara o N-drogach do replikacji. Rozproszone tablice haszowe (DHT), takie jak Chord w sieciach peer-to-peer oraz routowanie żądań CDN w firmach takich jak Akamai, opierają się dokładnie na tej samej idei pierścieniowej — mapują identyfikatory zasobów i identyfikatory węzłów do jednego obszaru, a bliskość decyduje o własności.

Często zadawane pytania

Wypróbuj na żywo

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