Dodanie jednego serwera może wymusić przeniesienie prawie wszystkich kluczy — chyba że użyjemy consistent hashing
Najprostszy sharding przez `hash(key) mod N` działa dobrze, dopóki liczba serwerów się nie zmienia. Gdy z czterech shardów robi się pięć, dla większości kluczy wynik modulo jest inny, więc ogromna część danych zmienia właściciela. Consistent hashing zaprojektowano tak, aby zmiana liczby węzłów powodowała możliwie małe przetasowanie. W klasycznej pracy Kargera i współautorów funkcja zmienia przypisanie minimalnie, gdy zmienia się zakres. Dzięki temu skalowanie klastra nie musi oznaczać masowej migracji całego magazynu.
Modulo jest pięknie proste
Liczymy hash klucza, a potem resztę z dzielenia przez liczbę shardów. Dla N serwerów otrzymujemy liczbę od 0 do N−1. Rozkład może być bardzo równy i implementacja jest banalna.
Problem zaczyna się przy zmianie N
Klucz, dla którego `hash mod 4 = 2`, nie musi mieć `hash mod 5 = 2`. Właściwie dla ogromnej części przestrzeni wynik się zmieni. Dodanie pojemności wymaga więc przenoszenia danych na wiele maszyn naraz, co generuje ruch sieciowy i obciążenie dysków dokładnie podczas skalowania.
Consistent hashing zmienia model przypisania
Klucze i węzły umieszcza się w logicznej przestrzeni haszy, często przedstawianej jako pierścień. Klucz należy do najbliższego odpowiedniego węzła według ustalonej reguły. Dodanie serwera przejmuje tylko fragment sąsiedniej przestrzeni, zamiast globalnie zmieniać wynik wszystkich kluczy.
Idea powstała dla rozproszonych cache'y internetowych
Klasyczna praca Kargera i współautorów dotyczyła rozproszonych protokołów cache'owania i hot spotów w sieci. Autorzy definiowali consistent hashing jako funkcję, która zmienia się minimalnie, gdy zmienia się jej zakres. Później ta idea stała się podstawą wielu rozproszonych magazynów i systemów shardingu.
Skalowalność to także koszt reorganizacji
Łatwo powiedzieć, że system skaluje się przez „dodanie serwera”. Prawdziwe pytanie brzmi, co musi się wydarzyć z istniejącymi danymi. Jeśli każde skalowanie wywołuje migrację większości zbioru, sam proces rozbudowy może stać się największym źródłem obciążenia. Consistent hashing redukuje właśnie ten ukryty koszt.
Wirtualne węzły pomagają wyrównać rozkład
Prosty pierścień z jednym punktem na fizyczny serwer może dawać nierówne fragmenty przestrzeni haszy. Praktyczne implementacje często reprezentują serwer wieloma wirtualnymi pozycjami, dzięki czemu jego udział w przestrzeni jest sumą wielu mniejszych kawałków. Ułatwia to równoważenie pojemności i przenoszenie części obciążenia przy zmianach klastra.
Consistent hashing nie rozwiązuje hot key
Nawet idealnie równy podział przestrzeni kluczy nie gwarantuje równego ruchu. Jeśli jeden klucz jest milion razy popularniejszy od innych, wciąż może przeciążyć jego właściciela. Potrzebne są dodatkowe techniki: cache, replikacja gorących danych lub specjalne partycjonowanie. Consistent hashing rozwiązuje problem stabilnego przypisania przy zmianie członkostwa, nie wszystkie problemy load balancingu.
Consistent hashing jest również odporniejszy na usunięcie węzła. Gdy serwer znika, jego zakres przejmuje ograniczona liczba sąsiadów zamiast wymuszać globalne przeliczenie wszystkich kluczy. To pomaga zarówno przy skalowaniu, jak i przy awariach. Jednak sama migracja nadal kosztuje: trzeba przenieść lub odtworzyć dane, zachować odpowiednią liczbę replik i kontrolować chwilowe nierówności. Algorytm zmniejsza zakres perturbacji, ale nie sprawia, że zmiana członkostwa staje się darmowa.
Rozmieszczenie replik dodatkowo komplikuje pierścień. Danych nie wystarczy trzymać na jednym węźle wyznaczonym przez hash; dla odporności trzeba umieścić kopie na kolejnych lub odpowiednio dobranych failure domains. Przy dodaniu serwera zmienia się więc nie tylko właściciel primary, ale potencjalnie zestaw replik. Dobre implementacje planują migrację tak, by podczas rebalance nie zejść poniżej wymaganego poziomu redundancji.