W ostatnich latach, wraz z pojawieniem się koncepcji takich jak cloud computing i big data, systemy rozproszone zyskały na popularności i znaczeniu.
Jeden z takich systemów, rozproszone pamięci podręczne, które zasilają wiele dynamicznych stron i aplikacji internetowych o dużym natężeniu ruchu, zazwyczaj składają się ze szczególnego przypadku rozproszonego haszowania. Wykorzystują one algorytm znany jako spójne haszowanie.
Czym jest spójne haszowanie? Jaka jest motywacja stojąca za nim i dlaczego powinno Cię to obchodzić?
W tym artykule najpierw omówię ogólną koncepcję haszowania i jego cel, a następnie opiszę rozproszone haszowanie i związane z nim problemy. To z kolei doprowadzi nas do naszego tytułowego tematu.
Czym jest haszowanie?
Czym w ogóle jest „haszowanie”? Merriam-Webster definiuje rzeczownik hash jako „siekane mięso zmieszane z ziemniakami i zrumienione”, a czasownik jako „siekać (jak mięso i ziemniaki) na małe kawałki”. Tak więc, szczegóły kulinarne na bok, hash z grubsza oznacza „siekać i mieszać” – i to jest dokładnie to, skąd pochodzi termin techniczny.
Funkcja haszująca jest funkcją, która mapuje jeden kawałek danych – zazwyczaj opisujący jakiś obiekt, często o arbitralnym rozmiarze – na inny kawałek danych, zazwyczaj liczbę całkowitą, znany jako kod haszujący lub po prostu hasz.
Na przykład, niektóre funkcje haszujące przeznaczone do haszowania ciągów znaków, z zakresem wyjściowym 0 .. 100, mogą mapować ciąg Hello do, powiedzmy, liczby 57, Hasta la vista, baby do liczby 33, a każdy inny możliwy ciąg do jakiejś liczby w tym zakresie. Ponieważ istnieje o wiele więcej możliwych wejść niż wyjść, każda dana liczba będzie miała wiele różnych łańcuchów na nią odwzorowanych, zjawisko znane jako kolizja. Dobre funkcje haszujące powinny w jakiś sposób „posiekać i wymieszać” (stąd termin) dane wejściowe w taki sposób, aby wyjścia dla różnych wartości wejściowych były rozłożone możliwie równomiernie w zakresie wyjściowym.
Funkcje haszujące mają wiele zastosowań i dla każdego z nich mogą być pożądane różne właściwości. Istnieje rodzaj funkcji hash znanych jako kryptograficzne funkcje hash, które muszą spełniać restrykcyjny zestaw właściwości i są używane do celów bezpieczeństwa – w tym aplikacji, takich jak ochrona haseł, sprawdzanie integralności i fingerprinting wiadomości, i wykrywanie korupcji danych, między innymi, ale te są poza zakresem tego artykułu.
Niekryptograficzne funkcje hash mają również kilka zastosowań, z których najbardziej powszechne jest ich użycie w tablicach hash, które jest tym, które nas interesuje i które zbadamy bardziej szczegółowo.
Wprowadzenie do tablic hash (Hash Maps)
Wyobraźmy sobie, że musimy przechowywać listę wszystkich członków jakiegoś klubu, jednocześnie będąc w stanie wyszukać każdego konkretnego członka. Moglibyśmy sobie z tym poradzić, przechowując listę w tablicy (lub połączonej liście) i, aby wykonać wyszukiwanie, iterować po elementach, dopóki nie znajdziemy żądanego (moglibyśmy szukać na przykład na podstawie ich nazwiska). W najgorszym przypadku oznaczałoby to sprawdzenie wszystkich członków (jeśli ten, którego szukamy, jest ostatni lub w ogóle go nie ma), lub średnio połowy z nich. W kategoriach teorii złożoności, wyszukiwanie miałoby wtedy złożoność O(n), i byłoby dość szybkie dla małej listy, ale stawałoby się coraz wolniejsze wprost proporcjonalnie do liczby członków.
Jak można to poprawić? Załóżmy, że wszyscy ci członkowie klubu mieli człon ID, który był numerem sekwencyjnym odzwierciedlającym kolejność, w jakiej dołączyli do klubu.
Zakładając, że wyszukiwanie według ID było dopuszczalne, moglibyśmy umieścić wszystkich członków w tablicy, z ich indeksami odpowiadającymi ich ID (na przykład członek z ID=10 byłby na indeksie 10 w tablicy). Pozwoliłoby to nam na bezpośredni dostęp do każdego członka, bez żadnego wyszukiwania. Byłoby to bardzo wydajne, w rzeczywistości tak wydajne, jak to tylko możliwe, odpowiadające najniższej możliwej złożoności, O(1), znanej również jako stały czas.
Ale, co prawda, nasz klubowy członek ID scenariusz jest nieco wymyślony. Co by było, gdyby IDs były dużymi, niesekwencyjnymi lub losowymi liczbami? Albo gdyby wyszukiwanie według ID było niedopuszczalne, a my potrzebowalibyśmy wyszukiwać według nazwy (lub innego pola)? Z pewnością przydałoby się zachować nasz szybki bezpośredni dostęp (lub coś zbliżonego), jednocześnie będąc w stanie obsługiwać arbitralne zestawy danych i mniej restrykcyjne kryteria wyszukiwania.
Tutaj na ratunek przychodzą funkcje haszujące. Odpowiednia funkcja haszująca może zostać użyta do odwzorowania dowolnego fragmentu danych na liczbę całkowitą, która będzie odgrywać podobną rolę jak nasz klubowicz ID, aczkolwiek z kilkoma istotnymi różnicami.
Po pierwsze, dobra funkcja haszująca ma zazwyczaj szeroki zakres wyjściowy (zazwyczaj cały zakres 32- lub 64-bitowej liczby całkowitej), więc budowanie tablicy dla wszystkich możliwych indeksów byłoby albo niepraktyczne, albo po prostu niemożliwe, a także byłoby kolosalnym marnotrawstwem pamięci. Aby przezwyciężyć ten problem, możemy mieć rozsądnie dużą tablicę (powiedzmy, tylko dwa razy tyle elementów, które spodziewamy się przechowywać) i wykonać operację modulo na haszu, aby uzyskać indeks tablicy. Tak więc, indeks byłby index = hash(object) mod N, gdzie N jest rozmiarem tablicy.
Po drugie, hasze obiektów nie będą unikalne (chyba że pracujemy z ustalonym zbiorem danych i niestandardową zbudowaną doskonałą funkcją haszującą, ale nie będziemy tego tutaj omawiać). Będą kolizje (dodatkowo zwiększone przez operację modulo), a zatem prosty bezpośredni dostęp do indeksu nie zadziała. Istnieje kilka sposobów, aby sobie z tym poradzić, ale typowym jest dołączenie listy, powszechnie znanej jako bucket, do każdego indeksu tablicy, aby przechowywać wszystkie obiekty dzielące dany indeks.
Więc, mamy tablicę o rozmiarze N, z każdym wpisem wskazującym na bucket obiektów. Aby dodać nowy obiekt, musimy obliczyć jego hash modulo N i sprawdzić wiadro na wynikowym indeksie, dodając obiekt, jeśli jeszcze go tam nie ma. Aby wyszukać obiekt, robimy to samo, tylko zaglądamy do kubełka, aby sprawdzić, czy obiekt tam jest. Taka struktura nazywana jest tablicą haszującą, i chociaż wyszukiwania wewnątrz kubełków są liniowe, prawidłowo zwymiarowana tablica haszująca powinna mieć rozsądnie małą liczbę obiektów na kubełek, co skutkuje prawie stałym czasem dostępu (średnia złożoność O(N/k), gdzie k jest liczbą kubełków).
W przypadku złożonych obiektów, funkcja haszująca nie jest zwykle stosowana do całego obiektu, ale do klucza. W naszym przykładzie członka klubu, każdy obiekt może zawierać kilka pól (jak imię, wiek, adres, email, telefon), ale moglibyśmy wybrać, powiedzmy, email jako klucz, aby funkcja haszująca była zastosowana tylko do emaila. W rzeczywistości, klucz nie musi być częścią obiektu; powszechne jest przechowywanie par klucz-wartość, gdzie klucz jest zwykle stosunkowo krótkim łańcuchem, a wartość może być arbitralnym fragmentem danych. W takich przypadkach tablica haszująca lub mapa haszująca jest używana jako słownik, i to jest sposób, w jaki niektóre języki wysokiego poziomu implementują obiekty lub tablice asocjacyjne.
Scaling Out: Distributed Hashing
Teraz, gdy już omówiliśmy hashowanie, jesteśmy gotowi przyjrzeć się hashowaniu rozproszonemu.
W niektórych sytuacjach może być konieczne lub pożądane podzielenie tablicy hash na kilka części, hostowanych przez różne serwery. Jedną z głównych motywacji do tego jest ominięcie ograniczeń pamięciowych związanych z użyciem jednego komputera, co pozwala na konstruowanie arbitralnie dużych tablic haszujących (biorąc pod uwagę wystarczającą liczbę serwerów).
W takim scenariuszu obiekty (i ich klucze) są rozdzielane między kilka serwerów, stąd nazwa.
Typowym przypadkiem użycia dla tego jest implementacja pamięci podręcznych, takich jak Memcached.
Takie konfiguracje składają się z puli serwerów buforujących, które hostują wiele par klucz-wartość i są używane do zapewnienia szybkiego dostępu do danych pierwotnie przechowywanych (lub obliczonych) gdzie indziej. Na przykład, aby zmniejszyć obciążenie serwera bazy danych i jednocześnie poprawić wydajność, można zaprojektować aplikację tak, aby najpierw pobierała dane z serwerów pamięci podręcznej, a dopiero jeśli ich tam nie ma – sytuacja znana jako cache miss – wracała do bazy danych, uruchamiając odpowiednie zapytanie i buforując wyniki za pomocą odpowiedniego klucza, tak aby można je było znaleźć następnym razem, gdy będą potrzebne.
Jak odbywa się dystrybucja? Jakie kryteria są używane do określenia, które klucze należy umieścić w których serwerach?
Najprostszym sposobem jest wzięcie hasha modulo liczby serwerów. To znaczy server = hash(key) mod N, gdzie N jest rozmiarem puli. Aby przechowywać lub pobierać klucz, klient najpierw oblicza hash, stosuje operację modulo N i używa wynikowego indeksu do skontaktowania się z odpowiednim serwerem (prawdopodobnie za pomocą tablicy adresów IP). Zauważ, że funkcja haszująca używana do dystrybucji klucza musi być taka sama we wszystkich klientach, ale nie musi być taka sama jak ta używana wewnętrznie przez serwery buforujące.
Zobaczmy przykład. Powiedzmy, że mamy trzy serwery, A, B i C, i mamy kilka kluczy łańcuchowych z ich hashami:
| KEY | HASH | HASH mod 3 |
|---|---|---|
| „john” | 1633428562 | 2 |
| „bill” | 7594634739 | 0 |
| „jane” | 5000799124 | 1 |
| „steve” | 9787173343 | 0 |
| „kate” | 3421657995 | 2 |
Klient chce pobrać wartość dla klucza john. Jego hash modulo 3 to 2, więc musi skontaktować się z serwerem C. Klucz nie został tam znaleziony, więc klient pobiera dane ze źródła i dodaje je. Pula wygląda tak:
| A | B | C |
|---|---|---|
| „john” |
Następnie inny klient (lub ten sam) chce pobrać wartość dla klucza bill. Jego hash modulo 3 to 0, więc musi skontaktować się z serwerem A. Klucz nie został tam znaleziony, więc klient pobiera dane ze źródła i dodaje je. Pula wygląda teraz tak:
| A | B | C |
|---|---|---|
| „bill” | „john” |
Po dodaniu pozostałych kluczy pula wygląda tak:
| A | B | C |
|---|---|---|
| „bill” | „jane” | „john” |
| „steve” | „kate” |
The Rehashing Problem
Ten schemat dystrybucji jest prosty, intuicyjny i działa dobrze. To znaczy, dopóki nie zmieni się liczba serwerów. Co się stanie, jeśli jeden z serwerów ulegnie awarii lub stanie się niedostępny? Oczywiście klucze muszą być ponownie rozprowadzone, aby uwzględnić brakujący serwer. To samo dotyczy sytuacji, gdy do puli dodawany jest jeden lub więcej nowych serwerów; klucze muszą być redystrybuowane tak, aby uwzględniały nowe serwery. Jest to prawdziwe dla każdego schematu dystrybucji, ale problem z naszą prostą dystrybucją modulo polega na tym, że gdy zmienia się liczba serwerów, większość hashes modulo N ulegnie zmianie, więc większość kluczy będzie musiała zostać przeniesiona na inny serwer. Tak więc, nawet jeśli pojedynczy serwer zostanie usunięty lub dodany, wszystkie klucze będą prawdopodobnie musiały zostać ponownie przeprogramowane na inny serwer.
Z naszego poprzedniego przykładu, gdybyśmy usunęli serwer C, musielibyśmy ponownie zhashować wszystkie klucze używając hash modulo 2 zamiast hash modulo 3, a nowe lokalizacje dla kluczy stałyby się:
| KEY | HASH | HASH mod 2 |
|---|---|---|
| „john” | 1633428562 | 0 |
| 1 | ||
| „kate” | 3421657995 | 1 |
| A | B |
|---|---|
| „john” | „bill” |
| „jane” | „steve” |
| „kate” |
Zauważ, że zmieniły się wszystkie kluczowe lokalizacje, nie tylko te z serwera C.
W typowym przypadku użycia, o którym wspomnieliśmy wcześniej (buforowanie), oznaczałoby to, że nagle klucze nie zostaną odnalezione, ponieważ nie będą jeszcze obecne w nowej lokalizacji.
Więc większość zapytań zakończy się brakiem odpowiedzi, a oryginalne dane będą prawdopodobnie musiały zostać ponownie pobrane ze źródła, co spowoduje duże obciążenie serwera źródłowego (zazwyczaj bazy danych). To może bardzo dobrze pogorszyć wydajność poważnie i ewentualnie rozbić serwery pochodzenia.
Rozwiązanie: Consistent Hashing
Jak więc można rozwiązać ten problem? Potrzebujemy schematu dystrybucji, który nie zależy bezpośrednio od liczby serwerów, tak aby podczas dodawania lub usuwania serwerów zminimalizować liczbę kluczy, które muszą zostać przeniesione. Jeden z takich schematów – sprytny, ale zaskakująco prosty – nazywa się spójnym haszowaniem (consistent hashing) i został po raz pierwszy opisany przez Karger et al. z MIT w pracy naukowej z 1997 roku (według Wikipedii).
Consistent Hashing to rozproszony schemat haszowania, który działa niezależnie od liczby serwerów lub obiektów w rozproszonej tablicy haszującej, przypisując im pozycję na abstrakcyjnym okręgu lub pierścieniu haszującym. Pozwala to na skalowanie serwerów i obiektów bez wpływu na cały system.
Wyobraźmy sobie, że odwzorowaliśmy wyjściowy zakres hashowania na krawędź okręgu. Oznacza to, że minimalna możliwa wartość hasza, zero, odpowiadałaby kątowi zero, maksymalna możliwa wartość (jakaś duża liczba całkowita, którą nazwiemy INT_MAX) odpowiadałaby kątowi 2𝝅 radianów (lub 360 stopni), a wszystkie inne wartości hasza liniowo mieściłyby się gdzieś pomiędzy. Moglibyśmy więc wziąć klucz, obliczyć jego hash i dowiedzieć się, gdzie leży on na krawędzi okręgu. Zakładając INT_MAX równe 1010 (dla przykładu), klucze z naszego poprzedniego przykładu wyglądałyby następująco:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „john” | 1633428562 | 58.8 |
| „bill” | 7594634739 | 273.4 |
| „jane” | 5000799124 | 180 |
| „steve” | 9787173343 | 352.3 |
| „kate” | 3421657995 | 123.2 |
Teraz wyobraź sobie, że umieściliśmy serwery również na brzegu okręgu, pseudolosowo przypisując im również kąty. Należy to zrobić w sposób powtarzalny (lub przynajmniej tak, aby wszyscy klienci zgadzali się co do kątów serwerów). Wygodnym sposobem na zrobienie tego jest haszowanie nazwy serwera (lub adresu IP, lub jakiegoś identyfikatora) – tak jak zrobilibyśmy to z każdym innym kluczem – w celu uzyskania jego kąta.
W naszym przykładzie, sprawy mogą wyglądać tak:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „john” | 1633428562 | 58.8 |
| „bill” | 7594634739 | 273.4 |
| „jane” | 5000799124 | 180 |
| „steve” | 9787173343 | 352.3 |
| „kate” | 3421657995 | 123.2 |
| „A” | 5572014558 | 200.6 |
| „B” | 8077113362 | 290.8 |
| „C” | 2269549488 | 81.7 |
Ponieważ mamy klucze zarówno obiektów, jak i serwerów na tym samym okręgu, możemy zdefiniować prostą regułę kojarzenia tych pierwszych z drugimi: Każdy klucz obiektu będzie należał do serwera, którego klucz jest najbliżej, w kierunku przeciwnym do ruchu wskazówek zegara (lub zgodnym z ruchem wskazówek zegara, w zależności od stosowanych konwencji). Innymi słowy, aby dowiedzieć się, który serwer poprosić o dany klucz, musimy zlokalizować klucz na okręgu i poruszać się w kierunku kąta rosnącego, aż znajdziemy serwer.
W naszym przykładzie:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „john” | 1633428562 | 58.7 |
| „C” | 2269549488 | 81.7 |
| „kate” | 3421657995 | 123.1 |
| „jane” | 5000799124 | 180 |
| „A” | 5572014557 | 200.5 |
| „bill” | 7594634739 | 273.4 |
| „B” | 8077113361 | 290,7 |
| „steve” | 787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john” | 1632929716 | 58.7 | „C” | C |
| „kate” | 3421831276 | 123.1 | „A” | A |
| „jane” | 5000648311 | 180 | „A” | A |
| „bill” | 7594873884 | 273.4 | „B” | B |
| „steve” | 9786437450 | 352.3 | „C” | C |
Z perspektywy programowania, to co byśmy zrobili, to utrzymywanie posortowanej listy wartości serwerów (które mogą być kątami lub liczbami w dowolnym przedziale rzeczywistym), i przejście tej listy (lub użycie wyszukiwania binarnego), aby znaleźć pierwszy serwer z wartością większą lub równą wartości żądanego klucza. Jeśli nie znajdziemy takiej wartości, musimy zawinąć się dookoła, biorąc pierwszy z listy.
Aby zapewnić równomierne rozłożenie kluczy obiektów między serwerami, musimy zastosować prostą sztuczkę: przypisać nie jedną, ale wiele etykiet (kątów) do każdego serwera. Tak więc zamiast etykiet A, B i C, moglibyśmy mieć, powiedzmy, A0 .. A9, B0 .. B9 i C0 .. C9, wszystkie rozmieszczone wzdłuż okręgu. Czynnik, o który należy zwiększyć liczbę etykiet (kluczy serwerów), zwany wagą, zależy od sytuacji (i może być nawet inny dla każdego serwera), aby dostosować prawdopodobieństwo trafienia kluczy na każdy z nich. Na przykład, gdyby serwer B był dwa razy mocniejszy od pozostałych, można by mu przypisać dwa razy więcej etykiet, a w efekcie przechowywałby dwa razy więcej obiektów (średnio).
Dla naszego przykładu założymy, że wszystkie trzy serwery mają równą wagę 10 (to działa dobrze dla trzech serwerów, dla 10 do 50 serwerów, waga w zakresie od 100 do 500 będzie działać lepiej, a większe pule mogą potrzebować nawet wyższych wag):
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „C6” | 408965526 | 14.7 |
| „A1” | 473914830 | 17 |
| „A2” | 548798874 | 19.7 |
| „A3” | 1466730567 | 52.8 |
| „C4” | 1493080938 | 53.7 |
| „john” | 1633428562 | 58.7 |
| „B2” | 1808009038 | 65 |
| „C0” | 1982701318 | 71.3 |
| „B3” | 2058758486 | 74.1 |
| „A7” | 2162578920 | 77.8 |
| „B4” | 2660265921 | 95.7 |
| „C9” | 3359725419 | 120.9 |
| „kate” | 3421657995 | 123.1 |
| „A5” | 3434972143 | 123.6 |
| „C1” | 3672205973 | 132.1 |
| „C8” | 3750588567 | 135 |
| „B0” | 4049028775 | 145.7 |
| „B8” | 4755525684 | 171.1 |
| „A9” | 4769549830 | 171.7 |
| „jane” | 5000799124 | 180 |
| „C7” | 5014097839 | 180.5 |
| „B1” | 5444659173 | 196 |
| „A6” | 6210502707 | 223.5 |
| „A0” | 6511384141 | 234.4 |
| „B9” | 7292819872 | 262.5 |
| „C3” | 7330467663 | 263.8 |
| „C5” | 7502566333 | 270 |
| „bill” | 7594634739 | 273.4 |
| „A4” | 8047401090 | 289.7 |
| „C2” | 8605012288 | 309.7 |
| „A8” | 8997397092 | 323.9 |
| „B7” | 9038880553 | 325.3 |
| „B5” | 9368225254 | 337.2 |
| „B6” | 9379713761 | 337.6 |
| „steve” | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john” | 1632929716 | 58.7 | „B2” | B |
| „kate” | 3421831276 | 123.1 | „A5” | A |
| „jane” | 5000648311 | 180 | „C7” | C |
| „bill” | 7594873884 | 273.4 | „A4” | A |
| „steve” | 9786437450 | 352.3 | „C6” | C |
Więc, jaka jest korzyść z całego tego kołowego podejścia? Wyobraźmy sobie, że serwer C jest usunięty. Aby to uwzględnić, musimy usunąć etykiety C0 .. C9 z okręgu. To powoduje, że klucze obiektów wcześniej sąsiadujące z usuniętymi etykietami są teraz losowo oznaczane jako Ax i Bx, przypisując je ponownie do serwerów A i B.
Ale co się dzieje z innymi kluczami obiektów, tymi, które pierwotnie należały do A i B? Nic! To jest właśnie piękno tego rozwiązania: Brak etykiet Cx nie wpływa w żaden sposób na te klucze. Tak więc, usunięcie serwera powoduje, że jego klucze obiektów są losowo ponownie przypisywane do pozostałych serwerów, pozostawiając wszystkie inne klucze nietknięte:
| KEY | HASH | ANGLE (ang. (DEG) |
|---|---|---|
| „A1” | 473914830 | 17 |
| „A2” | 548798874 | 19.7 |
| „A3” | 1466730567 | 52.8 |
| „john” | 1633428562 | 58.7 |
| „B2” | 1808009038 | 65 |
| „B3” | 2058758486 | 74.1 |
| „A7” | 2162578920 | 77.8 |
| „B4” | 2660265921 | 95.7 |
| „kate” | 3421657995 | 123.1 |
| „A5” | 3434972143 | 123.6 |
| „B0” | 4049028775 | 145.7 |
| „B8” | 4755525684 | 171.1 |
| „A9” | 4769549830 | 171.7 |
| „jane” | 5000799124 | 180 |
| „B1” | 5444659173 | 196 |
| „A6” | 6210502707 | 223.5 |
| „A0” | 6511384141 | 234.4 |
| „B9” | 7292819872 | 262.5 |
| „bill” | 7594634739 | 273.4 |
| „A4” | 8047401090 | 289.7 |
| „A8” | 8997397092 | 323.9 |
| „B7” | 9038880553 | 325.3 |
| „B5” | 9368225254 | 337.2 |
| „B6” | 9379713761 | 337.6 |
| „steve” | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john” | 1632929716 | 58.7 | „B2” | B |
| „kate” | 3421831276 | 123.1 | „A5” | A |
| „jane” | 5000648311 | 180 | „B1” | B |
| „bill” | 7594873884 | 273.4 | „A4” | A |
| „steve” | 9786437450 | 352.3 | „A1” | A |
Coś podobnego stanie się, jeśli zamiast usuwać serwer, dodamy jeden. Gdybyśmy chcieli dodać do naszego przykładu serwer D (powiedzmy, jako zamiennik C), musielibyśmy dodać etykiety D0 .. D9. W rezultacie mniej więcej jedna trzecia istniejących kluczy (wszystkie należące do A lub B) zostałaby ponownie przypisana do D, a reszta pozostałaby bez zmian:
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| „D2” | 439890723 | 15.8 |
| „A1” | 473914830 | 17 |
| „A2” | 548798874 | 19.7 |
| „D8” | 796709216 | 28.6 |
| „D1” | 1008580939 | 36.3 |
| „A3” | 1466730567 | 52,8 |
| „D5” | 1587548309 | 57.1 |
| „john” | 1633428562 | 58.7 |
| „B2” | 1808009038 | 65 |
| „B3” | 2058758486 | 74.1 |
| „A7” | 2162578920 | 77.8 |
| „B4” | 2660265921 | 95.7 |
| „D4” | 2909395217 | 104.7 |
| „kate” | 3421657995 | 123.1 |
| „A5” | 3434972143 | 123.6 |
| „D7” | 3567129743 | 128.4 |
| „B0” | 4049028775 | 145.7 |
| „B8” | 4755525684 | 171.1 |
| „A9” | 4769549830 | 171.7 |
| „jane” | 5000799124 | 180 |
| „B1” | 5444659173 | 196 |
| „D6” | 5703092354 | 205.3 |
| „A6” | 6210502707 | 223.5 |
| „A0” | 6511384141 | 234.4 |
| „B9” | 7292819872 | 262.5 |
| „bill” | 7594634739 | 273.4 |
| „A4” | 8047401090 | 289.7 |
| „D0” | 8272587142 | 297.8 |
| „A8” | 8997397092 | 323.9 |
| „B7” | 9038880553 | 325.3 |
| „D3” | 9048608874 | 325.7 |
| „D9” | 9314459653 | 335.3 |
| „B5” | 9368225254 | 337.2 |
| „B6” | 9379713761 | 337.6 |
| „steve” | 9787173343 | 352.3 |
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| „john” | 1632929716 | 58.7 | „B2” | B |
| „kate” | 3421831276 | 123.1 | „A5” | A |
| „jane” | 5000648311 | 180 | „B1” | B |
| „bill” | 7594873884 | 273.4 | „A4” | A |
| „steve” | 9786437450 | 352.3 | „D2” | D |
W ten sposób konsekwentne haszowanie rozwiązuje problem rehashingu.
Ogólnie, tylko k/N kluczy musi zostać przemapowanych, gdy k jest liczbą kluczy, a N jest liczbą serwerów (dokładniej, maksimum początkowej i końcowej liczby serwerów).
Zaobserwowaliśmy, że podczas korzystania z rozproszonego buforowania w celu optymalizacji wydajności, może się zdarzyć, że liczba serwerów buforujących zmienia się (powodem tego może być awaria serwera lub potrzeba dodania lub usunięcia serwera w celu zwiększenia lub zmniejszenia ogólnej pojemności). Używając spójnego haszowania do dystrybucji kluczy między serwerami, możemy być pewni, że jeśli tak się stanie, liczba kluczy, które zostaną ponownie zhaszowane – a zatem wpływ na serwery źródłowe – zostanie zminimalizowana, zapobiegając potencjalnym przestojom lub problemom z wydajnością.
Istnieją klienci dla kilku systemów, takich jak Memcached i Redis, które zawierają wsparcie dla spójnego haszowania po wyjęciu z pudełka.
Alternatywnie, możesz zaimplementować algorytm samodzielnie, w wybranym przez siebie języku, co powinno być stosunkowo łatwe po zrozumieniu koncepcji.
Jeśli nauka o danych cię interesuje, Toptal ma jedne z najlepszych artykułów na ten temat na blogu
.