Strona główna / Artykuły / Od Modulo do Hash Ring: skalowanie floty pamięci cache w Node.js bez problemów z obciążeniem

Node.jsSystem DesignCachingDistributed SystemsRedisPerformance

Od Modulo do Hash Ring: skalowanie floty pamięci cache w Node.js bez problemów z obciążeniem

Dowiedz się, dlaczego sharding typu hash-mod-N powoduje problemy w bazach danych przy zmianie węzłów, jak porównują się metody hashingu rendezvous, jump i ring, oraz jak stworzyć zrównoważony pierścień ważony w Node.js.

4407 słów

Klaster pamięci podręcznej, który sprawnie funkcjonował przez miesiące, może zostać sparaliżowany w ciągu zaledwie kilku minut po rutynowej modyfikacji – dodaniu jednego węzła. Przyczyną jest zazwyczaj pojedynczy wiersz kodu klienta, który wybiera serwer za pomocą hash(key) % N. Ten przewodnik wyjaśnia dokładnie, dlaczego ten wiersz zawodzi, porównuje cztery poważne alternatywy, tworzy ring hash spójny o jakości produkcyjnej w Node.js oraz wymienia pułapki operacyjne, przed którymi sam algorytm nie będzie mógł cię chronić.

Wzorzec awarii

Wyobraź sobie zdrową grupę czterech węzłów pamięci podręcznej o stopniu trafień 94%. Ruch sieciowy rośnie przed sezonowym szczytem, więc inżynier dodaje piąty węzeł. Jest to zmiana konfiguracji składająca się z dwóch wierszy, wprowadzana ostrożnie w trakcie normalnego dnia pracy. Około półtorej minuty później baza danych osiąga 100% wykorzystania CPU, a strona staje się niedostępna.

Nikt nie postąpił nieostrożnie. Klient po prostu kierował klucze w taki sam sposób jak zawsze:

const node = nodes[hash(key) % nodes.length];

To wyrażenie rozkłada klucze bardzo równomiernie, więc wygląda poprawnie. Problemem jest to, co dzieje się w momencie zmiany wartości nodes.length, i właśnie tutaj zaczyna się reszta tego przewodnika. Omówienie dotyczy czterech odrębnych problemów, analizuje rzeczywiste alternatywy, a następnie buduje i mierzy strukturę typu ring w Node.js.

Cztery problemy kryjące się za jedną ideą

Hashing spójny jest często przedstawiany jako jeden prosty trik. W praktyce rozwiązuje on cztery odrębne problemy, a implementacja zajmująca się tylko pierwszym z nich i tak zawiedzie w warunkach produkcyjnych ze względu na pozostałe trzy.

Problem 1: zmiana wartości N przemieszcza niemal wszystkie klucze

Z użyciem hash(key) % N zmiana wartości N nie powoduje przemieszczenia zaledwie kilku kluczy – przemieszcza niemal wszystkie z nich.

Pomaga przeanalizować te liczby. Klucz o haszu 1,000,003 odpowiada węźlowi 3 przy użyciu % 4, a przypadkowo odpowiada również węźlowi 3 przy użyciu % 5. Klucz o haszu 1,000,004 odpowiada węźlowi 0 przy użyciu % 4 oraz węźlowi 4 przy użyciu % 5. Te dwa powiązania nie mają ze sobą żadnego związku, więc klucz pozostaje tam, gdzie był, wyłącznie przez przypadek, z prawdopodobieństwem około 1 na N.

Przy analizie miliona kluczy wzorzec jest wyraźny: przechodzenie z 8 na 9 węzłów przemieszcza 88,93% kluczy, a w klastrze składającym się ze stu węzłów dodanie jednego węzła unieważnia około 99% pamięci cache.

Zwróć uwagę, w którą stronę zmierza ta tendencja. Im większy staje się system, tym bardziej destrukcyjne stają się każde kroki skalowania. To awaria, która czeka w ukryciu, dopóki biznes się rozwija.

Każda przeniesiona klucz to nieudana próba dostępu, a każda taka nieudana próba to zapytanie do bazy danych – wszystkie one przychodzą w ciągu kilku sekund. Baza danych przystosowana do obsługi 6% odczytów, które zwykle kończą się niepowodzeniem, nagle otrzymuje prawie wszystkie takie zapytania.

Problem 2: ta sama przegrupowanie, nieplanowane

Przynajmniej pierwszy problem występuje wtedy, gdy decydujesz się na skalowanie. Drugi to ten sam zdarzenie wywołane awarią, w najmniej odpowiednim momencie.

Węzeł wyczerpuje swoją pamięć, host zostaje zakończony lub podział sieci uniemożliwia połączenie jednego węzła z połową sieci. Liczba węzłów spada z 8 na 7, a każdy klient, działając samodzielnie, przekierowuje około 87% swoich kluczy na pozostałe węzły.

Sytuacja jest teraz ponura: stracono 12,5% pojemności pamięci cache, baza danych musi radzić sobie z 87% nieudanych prób odczytu, a siedem pozostałych węzłów przejmuje ruch utraconego węzła w tym samym czasie, gdy są ponownie wypełniane niemal każdym kluczem. Częstym skutkiem jest załamanie drugiego węzła, co zmusza do kolejnej pełnej przemiany mapowania, a to z kolei powoduje upadek trzeciego węzła.

Routowanie modulo przekształca awarię jednego węzła w powiązaną awarię obejmującą cały klastr, która sama się wzmacnia. To właśnie ta kaskada, a nie zimna pamięć cache, stanowi prawdziwe zagrożenie.

Problem 3: prosty pierścień jest bardzo nierównowagowy

Oczywistym rozwiązaniem problemu 1 jest umieszczenie węzłów i kluczy w jednej przestrzeni liczbowej oraz przydzielanie każdemu kluczu temu węzłowi, który znajduje się po nim zgodnie z ruchem wskazówek zegara. To jest istota spójnego haszowania i faktycznie eliminuje konieczność masowej przetasowywania.

Jednak przy naiwnym wdrożeniu słabo równoważy obciążenie. Węzły znajdują się tam, gdzie wypadną ich hashe, więc odległości między nimi są losowe, a losowe odległości rzadko się pokrywają. Gdy każdy hash umieszcza po czterech węzłach, w jednym pomiarze jeden węzeł posiadał 45% przestrzeni kluczy, a inny zaledwie 13%, co daje różnicę 3,4 raza – przy czym nie ma żadnego błędu.

Nierównowaga ta jest również trwała. Wynika ona z samych nazw węzłów, więc ten sam węzeł, na przykład cache-04, pozostaje intensywnie wykorzystywany, dopóki nie zostanie przemianowany, a każdy, kto to sprawdza, znajduje kod działający dokładnie tak, jak został napisany.

W większym skali sytuacja się pogarsza. Przy jednym punkcie pierścienia na węzeł przy 8 węzłach najbardziej obciążony węzeł miał 434% swojej sprawiedliwej części, a najmniej obciążony – 3,7%. To w praktyce oznacza jeden przeciążony serwer i siedem bezczynnych.

Problem 4: każdy klient musi się zgodzić

Najmniej widoczny problem dotyczy autorytetu. Coś musi powiązać klucz z węzłem i musi dostarczyć tę samą odpowiedź na każdym komputerze, który o to pyta.

Jedną z opcji jest usługa koordynatora przechowująca autorytatywną mapę fragmentów. Wtedy albo każde wyszukiwanie wymaga dwóch ruchów w sieci, albo klienci cacheują tę mapę, a wtedy potrzebny jest sposób na jej unieważnienie. Jeśli dwa klienci będą mieć różne wersje mapy, choćby na chwilę, jeden może zapisać user:42 do węzła A, podczas gdy drugi odczyta to z węzła B. Nic nie jest tracione, co być może jest jeszcze gorsze – istnieją teraz dwa możliwe wartości.

To, czego potrzebujesz, to mapowanie, które jest czystą funkcją klucza oraz aktualnej listy członków. Żaden koordynator, żaden serwis wyszukiwania, żaden wspólny stan – każdy klient wykona te same obliczenia i dojdzie do tego samego rezultatu. Hashing spójny zapewnia dokładnie to, dlatego przewyższa tablice wyszukiwania pomimo większej elastyczności tych ostatnich.

Konkretne scenariusze i opcje

Aby uczynić porównanie bardziej konkretnym, rozważmy ten system.

System. API do e-commerce przechowuje w pamięci tymczasowej dane sesji i profili w grupie węzłów Redis. Maksymalne obciążenie wynosi około 40 000 zapytań na sekundę dotyczących 25 milionów kluczy, przy stopniu trafności 94%. Baza danych funkcjonuje tylko dzięki tym 6% przypadków, w których zapytania nie są udane. (Aby ponownie zapoznać się z podstawami mechanizmów cache’owania, zobacz Podstawy cache’owania w Redis.)

Wymagania:

  1. Zwiększenie liczby węzłów z 8 do 12 przed rozpoczęciem sprzedaży bez wywoływania fal nieudanych zapytań
  2. Zdolność do funkcjonowania po utracie jednego węzła przy ograniczonej, akceptowalnej sferze wpływu
  3. Równomierne rozłożenie obciążenia, tak aby żaden węzeł nie pracował ponad około 120% swojego udziału
  4. Zapewnienie, by żaden koordynator nie znajdował się na ścieżce odczytu
  5. Uwzględnienie różnorodnego sprzętu: niektóre węzły mają 64 GB, inne 16 GB i nie powinny przenosić takiego samego obciążenia

Kilka algorytmów może spełniać niektóre lub wszystkie z tych warunków. Różnią się między sobą istotnie, a zła decyzja ma poważne konsekwencje.

Opcja A: hashing modulo

hash(key) % N zapewnia doskonałą równowagę, wymaga jednej instrukcji i nie zużywa pamięci.

Bezpośrednio nie spełnia wymagań nr 1 i 2. Zasługuje na wzmiankę, ponieważ to właśnie taki algorytm wszyscy piszą najpierw, i działa perfekcyjnie aż do chwili, gdy przestaje to być prawdą.

Należy go wybrać wtedy, gdy N rzeczywiście nigdy się nie zmienia, na przykład przy dzieleniu zadań partialnych między ustaloną liczbę pracowników lub przy shardingu w obrębie pojedynczego procesu.

Opcja B: koordynator i tabela wyszukiwania

Należy utrzymywać wyraźne powiązanie między zakresami kluczy a węzłami w magazynie danych, takim jak etcd lub ZooKeeper. Systemy takie jak Vitess i HBase działają mniej więcej w ten sposób.

Korzyść jest rzeczywista: pełna kontrola. Możesz przenieść pojedynczy „gorący” fragment danych, stopniowo przywracać równowagę w określonym zakresie, obserwując przy tym wskaźniki, lub przypisać konkretnego użytkownika do określonego sprzętu. Żaden podejście oparte na haszowaniu nie oferuje nic z tego, a po osiągnięciu pewnej skali na pewno będziesz tego potrzebować.

Cena jest równie realna: konieczność utrzymywania działającego systemu konsensusu, trudność w utrzymywaniu aktualnych kopii mapy w pamięci podręcznej oraz obowiązkowa zależność od ścieżki odczytu.

Wybierz to wtedy, gdy przenoszysz dane trwałe, a nie tymczasowe wpisy z pamięci podręcznej, i gdy musisz kontrolować proces migracji, zamiast pozwalać, by wszystko zmieniło się jednocześnie.

Opcja C: haszowanie typu rendezvous (HRW)

Najwyższe wyniki haszowania z użyciem losowych wag porównują każdy klucz z każdym węzłem i wybierają zwycięzcę:

function rendezvous(key, nodes) {
  let best = null, bestScore = -1;
  for (const node of nodes) {
    const score = mix(hash(key), hash(node));
    if (score > bestScore) { bestScore = score; best = node; }
  }
  return best;
}

To jest cały algorytm. Nie ma tu pierścienia, żadnych węzłów wirtualnych, żadnej uporządkowanej struktury i nie ma nic do odbudowywania, gdy zmienia się przynależność.

Pod względem dwóch najważniejszych metryk również przewyższa rozwiązanie oparte na pierścieniu. Przejście z 8 na 9 węzłów spowodowało przeniesienie 11,09% kluczy, przy teoretycznym minimalnym wartości 11,11%, a równowaga była niemal doskonała bez żadnej konfiguracji.

Niedogodnością jest czas obliczeniowy O(N) na każde wyszukiwanie, ponieważ każdy klucz jest hasowany względem każdego węzła, a ten koszt szybko rośnie wraz ze wzrostem liczby węzłów.

Wybierz to, gdy masz mniej niż około 30 węzłów. Wiele zespołów korzysta z około ośmiu węzłów pamięci podręcznej i dla nich najlepszym rozwiązaniem byłby hashing typu rendezvous: jest prostszy w implementacji i zrozumieniu, a także lepiej zapewnia równowagę. Rozwiązanie oparte na pierścieniu jest bardziej znane, ale niekoniecznie lepsze.

Opcja D: spójny hash z skokiem

Ten algorytm, opublikowany przez Google w 2014 roku, mieści się w około dziesięciu liniach kodu, nie wymaga pamięci, niemal idealnie zachowuje równowagę i przemieszcza minimalną liczbę kluczy.

Jego ograniczenie ma charakter strukturalny. Mapuje klucz na numer pojemnika w przedziale [0, N) i nie posiada koncepcji tożsamości węzła. Pojemniki mogą być dodawane lub usuwane jedynie na końcu tego przedziału; nie ma sposobu, aby usunąć węzeł numer 3 z środka przy jednoczesnym zachowaniu stabilności reszty.

Należy go wybrać wtedy, gdy pojemniki są wzajemnie zamienialne i zmienia się tylko ich liczba, np. przy dzieleniu zbiórki danych między elastycznie skalowalną grupę węzłów. Jest niewystarczający, gdy do sieci dołączają lub odchodzą określone nazwane serwery, co dokładnie odpowiada zachowaniu węzłów pamięci podręcznej.

Opcja E: pierścień haszowy z węzłami wirtualnymi

To jest klasyczny projekt. Węzły i klucze dzielą się jednym okrężnym przestrzenią adresową, a klucz należy do pierwszego węzła znajdującego się zgodnie z ruchem wskazówek zegara od niego.

Wybierz go wtedy, gdy flota jest na tyle duża, że liniowy koszt wyszukiwań punktów spotkań staje się zbyt duży, a także gdy potrzebujesz węzłów o różnych wagach oraz możliwości usunięcia dowolnego węzła.

Wybór odpowiedniego rozwiązania dla danego scenariusza

Po przeprowadzeniu pomiarów na 8 do 9 węzłach przy milionie kluczy, wszystkie alternatywy poza metodą modulo zbliżają się do teoretycznego minimum, a równowaga pierścienia w dużej mierze zależy od liczby wirtualnych węzłów otrzymywanych przez każdy serwer. W tym systemie e-commerce, z mieszanką sprzętu, węzłami o nazwach, które mogą ulec awarii, oraz flotą liczącą około 30 węzłów, pierścień jest właściwym wyborem. Reszta tego przewodnika opisuje, jak go prawidłowo zbudować.

Jak działa pierścień

Odkładajmy na bok tablice i reszty. Wyobraźmy sobie krąg oznaczony numerami od 0 do 2³² − 1, który łączy się u góry.

Cały algorytm składa się z dwóch reguł:

  1. Haszujmy każdą nazwę węzła na tym kręgu, tak że cache-01 znajduje się tam, gdzie umieści go jego hasz.
  2. Haszujmy każdy klucz na tym samym kręgu, a następnie poruszajmy się zgodnie z ruchem wskazówek zegara. Pierwszy dotknięty węzeł posiada ten klucz.

Kluczowym założeniem jest to, że węzły i klucze dzielą się jednym przestrzenią adresową. Wszystko inne wynika z tego, w tym fakt, dlaczego dodawanie nowego węzła nie jest kosztowne.

Dlaczego zmiany w przynależności pozostają lokalne

Gdy umieścimy nowy węzeł na kręgu, znajdzie się on pomiędzy dwoma istniejącymi. Przejmuje on kontrolę tylko nad odcinkiem pomiędzy sobą a swoim sąsiadem ruchem przeciwnym do ruchu wskazówek zegara.

Klucze znajdujące się poza tym łukiem nie są dotknięte i trafiają do swojego poprzedniego właściciela dokładnie tak jak wcześniej. Nowy node otrzymuje średnio 1/(N+1) okręgu, dzięki czemu ta część kluczy się przesuwa. Przy zmianie z 8 na 9 wyniosło to 11,06%, przy minimalnym poziomie 11,11%, w porównaniu z 88,93% przy zastosowaniu metody modulo przy tej samej zmianie i zestawie kluczy.

Usunięcie działa w odwrotnym kierunku: łuk usuniętego node przechodzi na jego następcę ruchem zgodnym z ruchem wskazówek zegara. Przy zmniejszeniu liczby node z 8 na 7 przesunięto 12,60% kluczy, co jest bliskie teoretycznym 12,50%. Skutki są ograniczone i do zniesienia, a pozostałe sześć node pozostaje nietkniętych.

Wirtualne node naprawiają nierównowagę

Z powrotem do problemu 3: cztery node w czterech losowych pozycjach tworzą bardzo nierówne łuki.

Rozwiązanie jest zaskakująco proste: nie umieszczaj każdego węzła tylko raz. Umieść go 160 razy pod 160 nazwami pochodnymi, takimi jak cache-01#0 i cache-01#1. Każda nazwa pochodna trafia w inne miejsce, więc każdy fizyczny węzeł posiada 160 małych, rozproszonych łuków zamiast jednego dużego, a prawo wielkich liczb sprawia, że sytuacja się wyrównuje.

Przy badaniu miliona kluczy na 8 węzłach równowaga stale się poprawia wraz ze wzrostem liczby replik. 160 to zwykła wartość domyślna, ponieważ mniej więcej w tym momencie krzywa poprawy się wyrównuje, jednak 500 nadal daje znacznie lepsze wyniki. Punkt pierścieniowy wymaga około 12 bajtów (4 bajty na pozycję plus 8 bajtów na odniesienie do właściciela), więc osiem węzłów z 500 replikami zajmuje mniej niż 50 KB. Jeśli równowaga jest dla ciebie ważniejsza niż ta ilość pamięci, wybierz większą liczbę; to obliczenie, którego niewiele zespołów się przejmuje.

Węzły wirtualne sprawiają również, że ważenie jest praktycznie bezkosztowe. Węzeł z dwukrotnie większą ilością pamięci otrzymuje dwukrotność punktów, a więc mniej więcej dwukrotny ruch. Przy wagach 4:4:1:1 uzyskane wartości wyniosły odpowiednio 40,6%, 41,1%, 9,4% i 9,0%, podczas gdy ideał to 40/40/10/10.

Wdrożenie struktury pierścieniowej w Node.js

Wdrożenie polega na czterech krokach: haszowaniu nazw węzłów wirtualnych, umieszczaniu ich, sortowaniu oraz używaniu wyszukiwania binarnego do znalezienia właściciela klucza. Poniższa klasa przechowuje informacje o przynależności do Map, odbudowuje posortowane tablice w momencie zmiany przynależności oraz udostępnia metodę get(key) do wyszukiwań.

export class ConsistentHashRing {
  #positions = new Uint32Array(0); // sorted ring positions
  #owners = []; // owners[i] owns #positions[i]
  #nodes = new Map(); // id -> { weight, points }

  constructor({ replicas = 160, hash = defaultHash } = {}) {
    if (replicas < 1) throw new RangeError("replicas must be >= 1");
    this.replicas = replicas;
    this.hash = hash;
  }

  addNode(id, weight = 1) {
    if (typeof id !== "string" || id.length === 0)
      throw new TypeError("node id must be a non-empty string");
    if (weight <= 0) throw new RangeError("weight must be > 0");
    if (this.#nodes.has(id)) return this;
    this.#nodes.set(id, {
      weight,
      points: Math.max(1, Math.round(this.replicas * weight)),
    });
    this.#rebuild();
    return this;
  }

  removeNode(id) {
    if (this.#nodes.delete(id)) this.#rebuild();
    return this;
  }

  #rebuild() {
    const pairs = [];
    for (const [id, { points }] of this.#nodes) {
      for (let i = 0; i < points; i++)
        pairs.push([this.hash(`${id}#${i}`), id]);
    }
    pairs.sort((a, b) => a[0] - b[0]);
    this.#positions = Uint32Array.from(pairs, (p) => p[0]);
    this.#owners = pairs.map((p) => p[1]);
  }

  /** Index of the first ring point >= h, wrapping to 0. */
  #successor(h) {
    const pos = this.#positions;
    let lo = 0,
      hi = pos.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (pos[mid] < h) lo = mid + 1;
      else hi = mid;
    }
    return lo === pos.length ? 0 : lo;
  }

  get(key) {
    if (this.#positions.length === 0) return null;
    return this.#owners[this.#successor(this.hash(key))];
  }
}

Trzy decyzje projektowe zasługują na uwagę.

Masy równoległe zamiast tablicy obiektów. Przechowywanie pozycji w Uint32Array umożliwia wykonywanie wyszukiwania binarnego na kompaktowej, ciągłej pamięci, która pozostaje w pamięci podręcznej CPU. Przy 8 węzłach i 160 replikach mamy 1 280 punktów, co stanowi około 5 KB, a wyszukiwanie wymaga około 11 porównań.

Zjawisko „wrap-around” w wyrażeniu lo === pos.length ? 0 : lo. Klucz, którego hasz przekracza ostatni punkt, należy do pierwszego węzła na kręgu. Pominięcie tego warunku jest najczęstszym błędem w domowych strukturach tego typu: wynik jest poprawny dla niemal każdego klucza, ale w tajemniczy sposób błędny dla nielicznych kluczy znajdujących się na górze zakresu.

Odbudowa struktury po zmianie przynależności, a nie przy wyszukiwaniu. Zmiany przynależności zdarzają się rzadko, podczas gdy wyszukiwania odbywają się dziesiątki tysięcy razy na sekundę, więc sortowanie 1 280 wpisów od czasu do czasu nie kosztuje nic znaczącego.

Replikacja, czyli znalezienie kolejnych właścicieli klucza, polega na ruchu zgodnie z ruchem wskazówek zegara, który obejmuje odrębne węzły fizyczne. Słowo „odrębne” ma znaczenie, ponieważ sąsiednie punkty na pierścieniu często należą do tego samego serwera:

getReplicas(key, count = 1) {
  const n = this.#positions.length;
  if (n === 0) return [];
  const wanted = Math.min(count, this.#nodes.size);
  const out = [];
  const start = this.#successor(this.hash(key));
  for (let step = 0; step < n && out.length < wanted; step++) {
    const owner = this.#owners[(start + step) % n];
    if (!out.includes(owner)) out.push(owner);
  }
  return out;
}

Zauważ, że zmienna wanted jest ograniczona liczbą węzłów fizycznych, więc próba utworzenia większej liczby replik niż istniejących serwerów nie może trwać wiecznie – proces zatrzymuje się po jednym pełnym obiegu w każdym przypadku.

Rozważne doborowanie funkcji hash

Wiele tutoriali pomija tę część, a właśnie ona dostarcza najbardziej pouczających wyników w całym ćwiczeniu.

Większość implementacji pierścieni używa domyślnie MD5. Funkcja ta działa, ale jest wolna: pierścień wykorzystujący ją osiągał jedynie 423 000 zapytań na sekundę, a analiza wydajności pokazała, że niemal cały czas był poświęcony na obliczenia w MD5.

Zastąpienie go szybkim, niekryptograficznym haszem FNV-1a zwiększyło przepustowość o około 15 razy. Jednak równowaga upadła: odchylenie standardowe obciążenia na każdym węźle wzrosło z 10,4% do 30,7%

Analiza obliczonych pozycji kilku wirtualnych węzłów ujawnia przyczynę:

cache-01#0 → 4037809751
cache-01#1 → 4021032132
cache-01#2 → 4071364989
cache-01#3 → 4054587370
cache-01#4 → 3970699275

Wszystkie one znajdują się w wąskim przedziale wokół 4,0 miliarda. FNV-1a charakteryzuje się słabym zachowaniem typu avalanche, co oznacza, że podobne dane dają podobne wyniki. Nazwy wirtualnych węzłów różnią się jedynie sufiksem, więc zamiast rozproszyć 160 punktów po okręgu, każdy węzeł gromadzi je w jednym ciasnym klastrze. Optymalizacja pod kątem szybkości po cichu przywróciła problem nr 3.

Rozwiązaniem jest przepuszczenie wyniku FNV przez mechanizm mieszania bitów, który stanowi ostatni krok w algoritmie MurmurHash3:

function fnv1a(str) {
  let h = 0x811c9dc5;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

// Scrambles the bits so near-identical inputs land far apart.
function fmix32(h) {
  h ^= h >>> 16;
  h = Math.imul(h, 0x85ebca6b);
  h ^= h >>> 13;
  h = Math.imul(h, 0xc2b2ae35);
  h ^= h >>> 16;
  return h >>> 0;
}

export const defaultHash = (str) => fmix32(fnv1a(str));

fmix32 naprzemiennie stosuje przesunięcia, operacje XOR i mnożenie, dzięki czemu zmiana w dowolnym bicie wejściowym rozprzestrzenia się na wszystkie bity wyjściowe. Math.imul wykonuje prawdziwe mnożenie liczb całkowitych 32-bitowych, a >>>> 0 przekształca wynik z powrotem na liczbę bezznakową 32-bitową, która pasuje do Uint32Array. Dzięki około dziesięciu dodatkowym operacjom łączny hash charakteryzował się lepszą równowagą w porównaniu z MD5, przy jednoczesnym szybszym działaniu o około 13 razy.

Ta lekcja ma zastosowanie nie tylko w przypadku haszowania: gdy zastępujesz jakiś komponent szybszym, sprawdź właściwość, której nie optymalizowałeś. FNV-1a to doskonale przyjęty hash; po prostu nie nadaje się do tego zadania, a w jego opisie nie ma żadnych ostrzeżeń.

Zmiana „pierścienia” na klienta pamięci cache

Sam pierścień nie jest klientem cache’u. Kod produkcyjny musi radzić sobie z awariami, a pierścień oferuje prostą strategię: przechodzenie do następnego węzła zgodnie z ruchem wskazówek zegara.

Poniższy wrapper przyjmuje mapę nazwanych klientów, buduje z nich pierścień i przy każdej próbie get testuje kolejno pierwszych failoverDepth właścicieli. Węzeł, który wywoła błąd, jest oznaczany jako niedostępny na czas downtimeMs i usuwany z pierścienia, a następnie ponownie dodawany po upływie określonego czasu kary.

export class ShardedCache {
  #ring; #clients; #down = new Map();

  constructor(clients, { replicas = 160, failoverDepth = 2, downtimeMs = 10_000 } = {}) {
    this.#clients = new Map(Object.entries(clients));
    this.#ring = new ConsistentHashRing({ replicas });
    for (const id of this.#clients.keys()) this.#ring.addNode(id);
    this.failoverDepth = failoverDepth;
    this.downtimeMs = downtimeMs;
  }

  #markDown(id) {
    this.#down.set(id, Date.now() + this.downtimeMs);
    this.#ring.removeNode(id);
  }

  #reviveExpired() {
    const now = Date.now();
    for (const [id, until] of this.#down) {
      if (now >= until) { this.#down.delete(id); this.#ring.addNode(id); }
    }
  }

  async get(key) {
    this.#reviveExpired();
    for (const id of this.#ring.getReplicas(key, this.failoverDepth)) {
      try {
        return { value: await this.#clients.get(id).get(key), node: id };
      } catch {
        this.#markDown(id);
      }
    }
    return { value: null, node: null, allDown: true };
  }
}

Uruchomienie tego kodu na czterech symulowanych węzłach przechowujących 10 000 kluczy, a następnie usunięcie jednego z nich dało następujący wynik:

Keys per node:  cache-01 2213 | cache-02 2462 | cache-03 2923 | cache-04 2402

Killing cache-02...
  served from cache: 7538
  cache misses:      2462
  hard failures:     0
  healthy nodes:     cache-01, cache-03, cache-04

  24.6% of traffic became a miss.

To wykres przedstawia twój plan przepustowości. W flotylli składającej się z czterech węzłów jeden awarię powoduje dodatkowe obciążenie bazy danych o 24,6% operacji odczytu, natomiast flotylla z ośmioma węzłami ogranicza to do 12,5%. Jeśli baza danych nie jest w stanie poradzić sobie z obciążeniem 1/N całkowitego obciążenia odczytu przychodzącego jednocześnie, prawdziwym problemem jest przepustowość bazy danych, a nie pamięć cache, przy czym konsystentne hashowanie zamienia ten problem z fatalnego na widoczny. Należy również zauważyć, że nie było żadnych awarii trudnych do naprawienia: żądania dotyczące kluczy nieaktywnego węzła trafiały do następnego węzła i stawały się zwykłymi nieudanymi próbami odczytu.

Potknięcia w produkcji, których algorytm nie obejmuje

Istnieje kilka problemów, które leżą poza zakresem algorytmu i i tak będą stanowić dla ciebie zagrożenie.

Nierówności w wersjach pierścienia

Pierścień jest przydatny tylko wtedy, gdy każdy klient oblicza ten sam wynik. Wprowadzaj zmiany w składzie floty stopniowo – przez kilka minut połowa floty będzie widziała 8 węzłów, a druga połowa 9. Te dwie grupy będą się nie zgadzać co do około 11% kluczy. Dla pamięci podręcznej oznacza to krótki spadek wskaźnika trafień; dla systemów przyjmujących zapisy oznacza to różnice w danych. Wersjonuj zestaw elementów floty, rozpowszechniaj go przez jeden kanał i odnotowuj wersję w swoich metrykach, aby można było zaobserwować odchylenia zamiast ich zgadywać.

Zbyt pochopne usuwanie węzłów

Nie usuwaj węzła po jednym timeoutie. Węzeł, który ciągle wychodzi i wraca, powoduje burzę zmian, ponieważ każda transzycja przemieszcza 1/N kluczy. Zanim węzeł zostanie usunięty, należy oczekiwać kilku kolejnych niepowodzeń w określonym oknie czasowym, a następnie ostrożnie go ponownie przyjąć. W powyższym przykładzie użyto stałej kary w wysokości dziesięciu sekund; kod produkcyjny powinien stosować eksponencjalne opóźnienia oraz sprawdzanie stanu, zanim pozwoli węzłowi ponownie wejść.

Klucze popularne nie są zrównoważone

Hashing spójny rozkłada klucze równomiernie, ale nic nie mówi o zapytaniach. Gdy jakiś produkt nagle staje się niezwykle popularny, jego wpis znajduje się na jednym serwerze, który przegrzewa się, mimo że system hashingu pełni swoją funkcję. Istnieją dwa rozwiązania: mała pamięć cache wewnątrz procesu przed systemem hashingu dla najczęściej używanych kluczy, lub wariant ograniczonych obciążeń hashingu spójnego opracowany przez Google, który ogranicza ilość danych, jaką może przyjąć każdy węzeł, a nadmiar przekazuje dalej zgodnie z kierunkiem ruchu wskazówek zegara.

Ponowne mapowanie to nie migracja

Wszystko powyżej zakłada, że utrata klucza kosztuje jedynie błąd wyszukiwania w pamięci podręcznej. Jeśli pierścień przekazuje dane trwałe, „11% kluczy przeniesionych” oznacza, że 11% tych danych musi zostać fizycznie skopiowanych do nowego węzła, zanim będą mogły być tam odczytane – zazwyczaj odbywa się to poprzez odczyty lub zapisy do obu lokalizacji, aż skopiowanie zostanie ukończone. Pierścień określa co musi zostać przeniesione; sam nie przyczynia się do tego procesu. Właśnie dlatego systemy takie jak Vitess polegają na koordynatorze: muszą kontrolować migrację, a nie tylko ją obliczać.

Liczba replik jest w praktyce trwała

Zmiana wartości replicas z 160 na 500 powoduje przesunięcie wszystkich pozycji w pierścieniu oraz ponowne rozlosowanie niemal wszystkich kluczy, co ma takie same skutki zakłócające jak zmiana modułu. Traktuj to jako decyzję projektową podejmowaną raz na zawsze, jeszcze przed dodaniem danych do użytku, a jeśli masz wątpliwości, wybierz wyższą wartość.

Gdy pierścień jest niewłaściwym narzędziem

Częścią umiejętności inżynierskich jest rozpoznawanie momentu, gdy imponujące rozwiązanie jest niewłaściwe.

  • Mniej niż około 30 węzłów: użyj hashingu typu rendezvous. Wymaga mniej kodu, lepiej się równoważy i nie wymaga dostosowywania liczby replik. Jedyną zaletą tego rozwiązania jest szybkość wyszukiwania na poziomie O(log N), która przy takiej skali ma już charakter teoretyczny.
  • Zmiennicze pojemniki, w których zmienia się tylko ich liczba: użyj hashingu typu jump – wystarczy dziesięć linijek kodu i nie potrzeba pamięci.
  • Dane trwałe, które wymagają kontrolowanego przemieszczania: użyj koordynatora. Tylko wyraźna mapa umożliwia przesunięcie pojedynczego fragmentu danych przy jednoczesnym monitorowaniu jego wpływu, czego hashing nie może zapewnić.
  • N, które naprawdę nigdy się nie zmienia: % N jest wystarczające. Nie twórz złożonych mechanizmów dla zmiany, która się nie wydarzy.

Pierścień zyskuje na znaczeniu, gdy węzły są nazwane, heterogeniczne, liczne i podatne na awarie. To niemal idealnie opisuje flotę pamięci podręcznych, dlatego tak wiele rozproszonych pamięci podręcznych jest budowanych na jej podstawie.

Główne wnioski

  • Idea jest prosta: umieść klucze i serwery w jednym przestrzeni adresowej, aby zmiana członkostwa wpływała tylko na określony obszar, a nie na całość.
  • Łączenie tras modułowe przekształca każdą sytuację skalowania oraz awarię węzła w niemal całkowite opróżnienie pamięci podręcznej, a skutki te rosną wraz z rozmiarem klastra.
  • Hashing typu rendezvous jest często lepszym wyborem dla małych flot; należy zastosować model pierścienia, gdy ważne są rozmiar, wagi oraz dowolne usuwanie elementów.
  • Bez węzłów wirtualnych jeden serwer może obsługiwać kilka razy większy obciążenie niż przypada mu zasłużenie. Liczbę replik należy ustalić z góry, ponieważ jej późniejsza zmiana powoduje przetasowanie całej struktury.
  • Szybki hash o słabej zdolności awaryjnej może w ciszy ponownie spowodować brak równowagi; zawsze mierz rozkład, a nie tylko szybkość.
  • Utrata jednego węzła powoduje, że około 1/N zapytań trafia do bazy danych. Ustaw rozmiar bazy danych zgodnie z tym, zachowuj ostrożność przy zmianach składu węzłów, usuwaj je ostrożnie i traktuj klucze o wysokim obciążeniu osobno.

    • Sam pierścień to zaledwie kilkadziesiąt linijek kodu. Inżynieria, która zapewnia jego niezawodność w produkcji, to wszystko, co go otacza.

    Literatura pokrewna

    Wszystkie artykułyWyślij brief