Consistent Hashing jest techniką haszowania, która działa naprawdę dobrze, gdy działa w dynamicznym środowisku, gdzie system rozproszony skaluje się w górę i w dół często. Podstawowa koncepcja Consistent Hashing została przedstawiona w artykule Consistent Hashing and RandomTrees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, ale popularność zyskała po słynnym artykule wprowadzającym DynamoDB – Dynamo: Amazon’s Highly Available Key-value Store. Od tego czasu spójne haszowanie zyskało na popularności i znalazło wiele zastosowań w projektowaniu i skalowaniu systemów rozproszonych. Dwa znane przykłady, które wyczerpująco wykorzystują tą technikę to Bit Torrent, dla sieci peer-to-peer oraz Akamai, dla cache’u stron internetowych. W tym artykule zanurzymy się głęboko w potrzebę Consistent Hashing, jego wnętrze, a co ważniejsze po drodze zaimplementujemy go używając tablic i Binary Search.

Zanim wskoczymy w podstawową technikę Consistent Hashing, najpierw musimy wyjaśnić kilka rzeczy, jedną z nich są Hash Functions. Funkcje Hash to dowolne funkcje, które mapują wartość z domeny o arbitralnej wielkości do innej domeny o stałej wielkości, zwykle nazywanej przestrzenią Hash. Na przykład, mapowanie adresów URL do 32-bitowych liczb całkowitych lub zawartości HTML stron internetowych do 256-bajtowego łańcucha. Wartości generowane na wyjściu tych funkcji haszujących są zwykle używane jako klucze umożliwiające efektywne wyszukiwanie oryginalnej jednostki.

Przykładem prostej funkcji haszującej jest funkcja, która mapuje 32-bitową liczbę całkowitą na 8-bitową przestrzeń haszującą. Funkcja może być zaimplementowana przy użyciu operatora arytmetycznego modulo i możemy to osiągnąć biorąc modulo 256, który daje liczby w zakresie zajmując 8 bitów do jego reprezentacji. Funkcja haszująca, która mapuje klucze do takich liczb całkowitych, częściej niż nie stosuje operatora modulo N tak, aby ograniczyć wartości, lub przestrzeń haszowania, do zakresu .

Dobra funkcja haszująca ma następujące właściwości

• Funkcja jest wydajna obliczeniowo, a wygenerowane wartości są łatwe do odszukania
• Funkcja, dla większości ogólnych przypadków użycia, zachowuje się jak generator pseudolosowy, który równomiernie rozkłada dane bez zauważalnej korelacji

Teraz, gdy zobaczyliśmy, czym jest funkcja haszująca, przyjrzymy się, jak moglibyśmy ich użyć i zbudować nieco skalowalny system rozproszony.

Budowanie rozproszonego systemu przechowywania

Powiedzmy, że budujemy rozproszony system przechowywania, w którym użytkownicy mogą przesyłać pliki i mieć do nich dostęp na żądanie. Usługa eksponuje następujące interfejsy API dla użytkowników

• upload aby przesłać plik
• fetch aby pobrać plik i zwrócić jego zawartość

Za kulisami system ma węzły magazynowania, na których pliki są przechowywane i dostępne. Węzły te wystawiają funkcje put_file i fetch_file, które umieszczają i pobierają zawartość pliku na/z dysku i wysyłają odpowiedź do głównego serwera API, który z kolei wysyła ją z powrotem do użytkownika.

Aby utrzymać początkowe obciążenie, system ma 5 węzłów Stogare, które przechowują przesłane pliki w sposób rozproszony. Posiadanie wielu węzłów zapewnia, że system, jako całość, nie jest przytłoczony, a przechowywanie jest rozłożone prawie równomiernie.

Gdy użytkownik wywołuje funkcję upload ze ścieżką pliku, system musi najpierw zidentyfikować węzeł magazynowania, który będzie odpowiedzialny za przechowywanie pliku i robimy to poprzez zastosowanie funkcji hash do ścieżki i z kolei uzyskanie indeksu węzła magazynowania. Po uzyskaniu węzła magazynowania, czytamy zawartość pliku i umieszczamy ten plik na węźle poprzez wywołanie funkcji put_file węzła.

# storage_nodes holding instances of actual storage node objectsstorage_nodes = def hash_fn(key): """The function sums the bytes present in the `key` and then take a mod with 5. This hash function thus generates output in the range . """ return sum(bytearray(key.encode('utf-8'))) % 5def upload(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we put the file on the node and return return node.put_file(path)def fetch(path): # we use the hash function to get the index of the storage node # that would hold the file index = hash_fn(path) # we get the StorageNode instance node = storage_nodes # we fetch the file from the node and return return node.fetch_file(path)

Funkcja haszująca użyta tutaj po prostu sumuje bajty i bierze modulo przez 5 (ponieważ istnieje 5 węzłów magazynowania w systemie) i w ten sposób generuje wyjście w przestrzeni haszującej . Ta wartość wyjściowa reprezentuje teraz indeks magazynu, który będzie odpowiedzialny za przechowywanie pliku.

Say mamy 5 plików 'f1.txt’, 'f2.txt’, 'f3.txt’, 'f4.txt’, 'f5.txt”, jeśli zastosujemy do nich funkcję haszującą, okaże się, że są one przechowywane odpowiednio na węzłach E, A, B, C i D.

Rzeczy stają się interesujące, gdy system zyskuje trochę przyczepności i musi być skalowany do 7 węzłów, co oznacza, że teraz funkcja haszująca powinna zrobić mod 7 zamiast mod 5. Zmiana funkcji hashującej pociąga za sobą zmianę mapowania i kojarzenia plików z węzłami pamięci masowej. Musimy najpierw zarządzać nowymi skojarzeniami i zobaczyć, które pliki muszą być przeniesione z jednego węzła do drugiego.

Z nową funkcją skrótu te same 5 plików 'f1.txt’, 'f2.txt’, 'f3.txt’, 'f4.txt’, 'f5.txt’ będą teraz powiązane z węzłami magazynowania D, E, F, G, A. Tutaj widzimy, że zmiana funkcji skrótu wymaga od nas przeniesienia każdego z 5 plików do innego węzła.

Jeśli musimy zmieniać funkcję skrótu za każdym razem, gdy skalujemy w górę lub w dół i jeśli wymaga to od nas przeniesienia nie wszystkich, ale nawet połowy danych, proces staje się super drogi i w dłuższej perspektywie niewykonalny. Potrzebujemy więc sposobu na zminimalizowanie ruchu danych wymaganego podczas skalowania w górę lub w dół, i to właśnie tutaj Consistent Hashing pasuje i minimalizuje wymagany transfer danych.

Consistent Hashing

Głównym problemem powyższego systemu jest to, że jest on podatny na zdarzenia takie jak skalowanie w górę i w dół, ponieważ wymaga wielu zmian w asocjacjach. Asocjacje te są napędzane przez bazową funkcję Hash, a zatem jeśli moglibyśmy w jakiś sposób uniezależnić tę funkcję od liczby węzłów magazynowych w systemie, rozwiązujemy tę wadę.

Consistent Hashing zajmuje się tą sytuacją poprzez utrzymywanie ogromnej i stałej przestrzeni Hash, gdzieś w kolejności , a węzeł magazynowy i obiekty mapują do jednego z gniazd w tej ogromnej przestrzeni Hash. W przeciwieństwie do tradycyjnego systemu, w którym plik był powiązany z węzłem magazynowania przy indeksie, do którego został zhashowany, w tym systemie szanse na kolizję między plikiem a węzłem magazynowania są nieskończenie małe i dlatego potrzebujemy innego sposobu na zdefiniowanie tego stowarzyszenia.

Zamiast używać podejścia opartego na kolizji, definiujemy stowarzyszenie jako – plik będzie powiązany z węzłem magazynowania, który jest obecny bezpośrednio po prawej stronie jego zhashowanej lokalizacji. Zdefiniowanie asocjacji w ten sposób pomaga nam

• utrzymać funkcję haszującą niezależną od liczby węzłów magazynowych
• utrzymać asocjacje względne, a nie napędzane przez bezwzględne kolizje

Consistent Hashing średnio wymaga tylko k/n jednostek danych do migracji podczas skalowania w górę i w dół; gdzie k to całkowita liczba kluczy, a n to liczba węzłów w systemie.

Bardzo naiwnym sposobem implementacji tego jest zaalokowanie tablicy o rozmiarze równym przestrzeni Hash i umieszczenie plików i węzła magazynowania dosłownie w tablicy w lokalizacji hashowanej. Aby uzyskać skojarzenie, wykonujemy iterację od hashowanej lokalizacji elementu w prawo i znajdujemy pierwszy węzeł magazynowy. Jeśli dojdziemy do końca tablicy i nie znajdziemy żadnego węzła, wracamy do indeksu 0 i kontynuujemy wyszukiwanie. Podejście to jest bardzo łatwe do zaimplementowania, ale cierpi na następujące ograniczenia

• wymaga ogromnej pamięci do przechowywania tak dużej tablicy
• znalezienie skojarzenia przez iterację za każdym razem w prawo jest O(hash_space)

Lepszym sposobem implementacji tego jest użycie dwóch tablic: jednej do przechowywania Węzłów Przechowywania, zwanej nodes i drugiej do przechowywania pozycji Węzłów Przechowywania w przestrzeni hash, zwanej keys. Pomiędzy tymi dwiema tablicami istnieje korespondencja jeden do jednego – węzeł magazynowy nodes jest obecny na pozycji keys w przestrzeni hash. Obie tablice są utrzymywane posortowane zgodnie z tablicą keys.

Funkcja haszująca w Consistent Hashing

Zdefiniujemy total_slots jako rozmiar tej całej przestrzeni haszującej, typowo rzędu 2^256, a funkcja haszująca mogłaby zostać zaimplementowana przez pobranie SHA-256, po którym następuje mod total_slots. Ponieważ total_slots jest ogromna i stała, poniższa implementacja funkcji haszującej jest niezależna od rzeczywistej liczby węzłów magazynowania obecnych w systemie, a zatem pozostaje bez wpływu na zdarzenia, takie jak skalowanie i skalowanie w dół.

def hash_fn(key: str, total_slots: int) -> int: """hash_fn creates an integer equivalent of a SHA256 hash and takes a modulo with the total number of slots in hash space. """ hsh = hashlib.sha256() # converting data into bytes and passing it to hash function hsh.update(bytes(key.encode('utf-8'))) # converting the HEX digest into equivalent integer value return int(hsh.hexdigest(), 16) % total_slots

Dodawanie nowego węzła w systemie

Gdy zachodzi potrzeba skalowania i dodania nowego węzła w systemie, w naszym przypadku nowego Storage Node, my

• znajdujemy pozycję węzła w przestrzeni Hash
• populujemy nowy węzeł danymi, które ma obsługiwać
• dodajemy węzeł w przestrzeni Hash

Gdy nowy węzeł jest dodawany w systemie, ma to wpływ tylko na pliki, które hashują w lokalizacji po lewej stronie i są skojarzone z węzłem po prawej stronie pozycji, w której nowy węzeł się zmieści. Wszystkie inne pliki i skojarzenia pozostają nienaruszone, co minimalizuje ilość danych do migracji i mapowania, które muszą zostać zmienione.

Z powyższej ilustracji wynika, że gdy nowy węzeł K jest dodawany między węzłami B i E, zmieniamy skojarzenia plików obecnych w segmencie B-K i przypisujemy je do węzła K. Dane należące do segmentu B-K można znaleźć w węźle E, z którym były wcześniej skojarzone. Tak więc jedyne pliki, których to dotyczy i które wymagają migracji, znajdują się w segmencie B-K; a ich skojarzenie zmienia się z węzła E na węzeł K.

Aby zaimplementować to na niskim poziomie przy użyciu tablic nodes i keys, najpierw uzyskujemy pozycję nowego węzła w przestrzeni Hash przy użyciu funkcji hash. Następnie znajdujemy indeks najmniejszego klucza większego niż pozycja w posortowanej tablicy keys za pomocą wyszukiwania binarnego. Ten indeks będzie miejscem, w którym klucz i nowy węzeł Storage zostaną umieszczone odpowiednio w tablicy keys i nodes.

def add_node(self, node: StorageNode) -> int: """add_node function adds a new node in the system and returns the key from the hash space where it was placed """ # handling error when hash space is full. if len(self._keys) == self.total_slots: raise Exception("hash space is full") key = hash_fn(node.host, self.total_slots) # find the index where the key should be inserted in the keys array # this will be the index where the Storage Node will be added in the # nodes array. index = bisect(self._keys, key) # if we have already seen the key i.e. node already is present # for the same key, we raise Collision Exception if index > 0 and self._keys == key: raise Exception("collision occurred") # Perform data migration # insert the node_id and the key at the same `index` location. # this insertion will keep nodes and keys sorted w.r.t keys. self.nodes.insert(index, node) self._keys.insert(index, key) return key

Usuwanie nowego węzła z systemu

Gdy zachodzi potrzeba zmniejszenia skali i usunięcia istniejącego węzła z systemu, my

• znajdujemy pozycję węzła do usunięcia w przestrzeni Hash
• populujemy węzeł po prawej stronie danymi, które były powiązane z węzłem do usunięcia
• usuwamy węzeł z przestrzeni Hash

Gdy węzeł jest usuwany z systemu, ma to wpływ tylko na pliki powiązane z samym węzłem. Wszystkie inne pliki i skojarzenia pozostają nienaruszone, co minimalizuje ilość danych do migracji i mapowania wymagającego zmiany.

Z powyższej ilustracji widzimy, że kiedy węzeł K jest usuwany z systemu, zmieniamy skojarzenia plików skojarzonych z węzłem K na węzeł leżący bezpośrednio po jego prawej stronie tj.e. węzeł E. Tak więc jedyne pliki dotknięte i potrzebuje migracji są te związane z węzłem K.

Aby zaimplementować to na niskim poziomie przy użyciu nodes i keys tablicy, dostajemy indeks, gdzie węzeł K leży w tablicy keys przy użyciu wyszukiwania binarnego. Gdy mamy już indeks, usuwamy klucz z tablicy keys i węzeł magazynowania z tablicy nodes obecny na tym indeksie.

def remove_node(self, node: StorageNode) -> int: """remove_node removes the node and returns the key from the hash space on which the node was placed. """ # handling error when space is empty if len(self._keys) == 0: raise Exception("hash space is empty") key = hash_fn(node.host, self.total_slots) # we find the index where the key would reside in the keys index = bisect_left(self._keys, key) # if key does not exist in the array we raise Exception if index >= len(self._keys) or self._keys != key: raise Exception("node does not exist") # Perform data migration # now that all sanity checks are done we popping the # keys and nodes at the index and thus removing the presence of the node. self._keys.pop(index) self.nodes.pop(index) return key

Kojarzenie elementu z węzłem

Teraz, gdy zobaczyliśmy, jak spójne haszowanie pomaga w utrzymaniu migracji danych, podczas skalowania i zmniejszania skali, do absolutnego minimum; nadszedł czas, aby zobaczyć, jak efektywnie możemy znaleźć „węzeł po prawej stronie” dla danego elementu. Operacja znalezienia skojarzenia musi być super szybka i wydajna, ponieważ jest to coś, co będzie wywoływane dla każdego pojedynczego odczytu i zapisu, który ma miejsce w systemie.

Aby zaimplementować to na niskim poziomie, ponownie wykorzystamy wyszukiwanie binarne i wykonamy tę operację w O(log(n)). Najpierw przekazujemy element do funkcji hashującej i pobieramy pozycję, w której element jest hashowany w przestrzeni hashowania. Pozycja ta jest następnie przeszukiwana binarnie w tablicy keys w celu uzyskania indeksu pierwszego klucza, który jest większy od pozycji (uzyskanej z funkcji haszującej). jeśli nie ma kluczy większych od pozycji, w tablicy keys, zawracamy i zwracamy indeks 0. Uzyskany w ten sposób indeks będzie indeksem węzła składowania w tablicy nodes związanego z danym elementem.

def assign(self, item: str) -> str: """Given an item, the function returns the node it is associated with. """ key = hash_fn(item, self.total_slots) # we find the first node to the right of this key # if bisect_right returns index which is out of bounds then # we circle back to the first in the array in a circular fashion. index = bisect_right(self._keys, key) % len(self._keys) # return the node present at the index return self.nodes

Kod źródłowy z implementacją Consistent Hashing w Pythonie można znaleźć na stronie github.com/arpitbbhayani/consistent-hashing.

Podsumowanie

Consistent Hashing jest jednym z najważniejszych algorytmów pomagających nam w poziomym skalowaniu i zarządzaniu dowolnym systemem rozproszonym. Algorytm ten nie tylko sprawdza się w systemach sharded, ale również znajduje zastosowanie w równoważeniu obciążenia, partycjonowaniu danych, zarządzaniu sesjami sticky na serwerze, algorytmach routingu i wielu innych. Wiele baz danych zawdzięcza swoją skalę, wydajność i zdolność do obsługi ogromnego obciążenia właśnie Consistent Hashing.

• Hash Functions – Wikipedia
• Consistent Hashing – Wikipedia
• Consistent Hashing – Stanford
• Consistent Hashing and RandomTrees
• Dynamo: Amazon’s Highly Available Key-value Store

Inne artykuły, które mogą Ci się spodobać:

• Python Cache Integers
• Fractional Cascading – Speeding up Binary Searches
• Copy-on-Write Semantics
• What makes MySQL LRU cache scan resistant
• Building Finite State Machines with Python Coroutines

Ten artykuł został pierwotnie opublikowany na moim blogu – Consistent Hashing.

Jeśli podobało Ci się to, co przeczytałeś, zapisz się do mojego newslettera i otrzymaj ten post dostarczony bezpośrednio do Twojej skrzynki odbiorczej i daj mi znać @arpit_bhayani.

.