Konzistentní hašování je technika hašování, která se velmi dobře osvědčuje při provozu v dynamickém prostředí, kde se distribuovaný systém často škáluje a snižuje. Základní koncept konzistentního hašování byl představen v článku Consistent Hashing and RandomTrees: Distributed Caching Protocols for Relieving Hot Spots on World Wide Web, ale popularitu získala až po slavném článku představujícím DynamoDB – Dynamo: Amazon’s Highly Available Key-value Store (Vysoce dostupné úložiště klíčových hodnot společnosti Amazon). Od té doby se konzistentní hashování prosadilo a našlo spoustu případů použití při navrhování a efektivním škálování distribuovaných systémů. Dva slavné příklady, které tuto techniku vyčerpávajícím způsobem používají, jsou Bit Torrent pro své peer-to-peer sítě a Akamai pro své webové cache. V tomto článku se ponoříme do hloubky potřeby Consistent Hashing, jeho vnitřností a co je důležitější, po cestě jej implementujeme pomocí polí a binárního vyhledávání.

Než se vrhneme na jádro techniky Consistent Hashing, nejprve si ujasníme několik věcí, z nichž jednou jsou hashovací funkce. Hashovací funkce jsou libovolné funkce, které mapují hodnotu z libovolně velké oblasti do jiné oblasti s pevnou velikostí, obvykle nazývané Hashovací prostor. Například mapování adres URL na 32bitová celá čísla nebo obsahu HTML webových stránek na 256bajtový řetězec. Hodnoty generované jako výstup těchto hashovacích funkcí se obvykle používají jako klíče umožňující efektivní vyhledávání původní entity.

Příkladem jednoduché hashovací funkce je funkce, která mapuje 32bitové celé číslo do 8bitového celočíselného hashovacího prostoru. Funkce by mohla být implementována pomocí aritmetického operátoru modulo a toho můžeme dosáhnout tak, že vezmeme modulo 256, čímž získáme čísla v rozsahu zabírající pro svou reprezentaci 8 bitů. Hašovací funkce, která mapuje klíče na takový celočíselný obor, častěji použije modulo N tak, aby omezila hodnoty, resp. hašovací prostor, na rozsah .

Dobrá hašovací funkce má následující vlastnosti

• Funkce je výpočetně efektivní a generované hodnoty se snadno vyhledávají
• Funkce se pro většinu obecných případů použití chová jako pseudonáhodný generátor, který rovnoměrně rozprostře data bez znatelné korelace

Teď, když jsme viděli, co je to hašovací funkce, se podíváme na to, jak bychom je mohli použít a vytvořit trochu škálovatelný distribuovaný systém.

Budování distribuovaného úložného systému

Řekněme, že budujeme distribuovaný úložný systém, ve kterém mohou uživatelé nahrávat soubory a přistupovat k nim na požádání. Služba vystavuje uživatelům následující API

• upload pro nahrání souboru
• fetch pro načtení souboru a vrácení jeho obsahu

V zákulisí má systém úložné uzly, na kterých jsou soubory uloženy a ke kterým se přistupuje. Tyto uzly vystavují funkce put_file a fetch_file, které vkládají a získávají obsah souboru na/z disku a posílají odpověď hlavnímu serveru API, který ji zase posílá zpět uživateli.

Pro udržení počáteční zátěže má systém 5 uzlů Stogare, které ukládají nahrané soubory distribuovaným způsobem. Existence více uzlů zajišťuje, že systém jako celek není přetížen a úložiště je rozděleno téměř rovnoměrně.

Když uživatel vyvolá funkci upload s cestou k souboru, systém musí nejprve identifikovat uzel úložiště, který bude zodpovědný za uložení souboru, a to provedeme tak, že na cestu použijeme hashovací funkci a následně získáme index uzlu úložiště. Jakmile získáme úložný uzel, přečteme obsah souboru a umístíme tento soubor na uzel vyvoláním funkce put_file uzlu.

# 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)

Hashovací funkce použitá nad tímto místem jednoduše sečte bajty a provede modulo podle 5 (protože v systému je 5 úložných uzlů), a tím vygeneruje výstup v prostoru hash . Tato výstupní hodnota nyní představuje index úložného modulu, který bude zodpovědný za uložení souboru.

Řekněme, že máme 5 souborů ‚f1.txt‘, ‚f2.txt‘, ‚f3.txt‘, ‚f4.txt‘, ‚f5.txt‘, pokud na ně aplikujeme hashovací funkci, zjistíme, že jsou uloženy v uzlech úložiště E, A, B, C, respektive D.

Věci začnou být zajímavé, když systém získá určitý tah a je třeba jej rozšířit na 7 uzlů, což znamená, že nyní by hashovací funkce měla provést mod 7 místo mod 5. Změna hashovací funkce znamená změnu mapování a přiřazení souborů k uzlům úložiště. Nejprve musíme spravovat nové asociace a zjistit, které soubory je třeba přesunout z jednoho uzlu do druhého.

S novou hashovací funkcí bude nyní stejných 5 souborů ‚f1.txt‘, ‚f2.txt‘, ‚f3.txt‘, ‚f4.txt‘, ‚f5.txt‘ asociováno s úložnými uzly D, E, F, G, A. Zde vidíme, že změna hashovací funkce vyžaduje, abychom každý z pěti souborů přesunuli do jiného uzlu.

Pokud musíme měnit hashovací funkci pokaždé, když škálujeme nahoru nebo dolů, a pokud to vyžaduje, abychom přesunuli ne všechna, ale dokonce polovinu dat, stává se tento proces superdrahým a v delším časovém horizontu neproveditelným. Potřebujeme tedy způsob, jak minimalizovat přesun dat, který je nutný při zvyšování nebo snižování měřítka, a právě sem se hodí Consistent Hashing, který minimalizuje nutný přenos dat.

Consistent Hashing

Hlavní bolestí výše uvedeného systému je, že je náchylný k událostem, jako je zvyšování a snižování měřítka, protože vyžaduje mnoho změn asociací. Tyto asociace jsou řízeny čistě základní hashovací funkcí, a proto pokud bychom mohli nějakým způsobem učinit tuto hashovací funkci nezávislou na počtu úložných uzlů v systému, vyřešili bychom tento nedostatek.

Konsistentní hashování řeší tuto situaci tím, že udržuje obrovský a konstantní hashovací prostor, někde v řádu , a úložný uzel i objekty se mapují na jeden ze slotů v tomto obrovském hashovacím prostoru. Na rozdíl od tradičního systému, kde byl soubor asociován s úložným uzlem na indexu, na který byl hashován, je v tomto systému pravděpodobnost kolize mezi souborem a úložným uzlem nekonečně malá, a proto potřebujeme jiný způsob definování této asociace.

Místo použití přístupu založeného na kolizi definujeme asociaci takto – soubor bude asociován s úložným uzlem, který se nachází bezprostředně napravo od jeho hashovaného umístění. Definování asociace tímto způsobem nám pomáhá

• udržet hašovací funkci nezávislou na počtu úložných uzlů
• udržet asociace relativní a neřízené absolutními kolizemi

Konzistentní hašování v průměru vyžaduje pouze k/n jednotek dat, které je třeba migrovat při zvyšování a snižování měřítka; kde k je celkový počet klíčů a n je počet uzlů v systému.

Velmi naivní způsob implementace spočívá v alokaci pole o velikosti rovnající se hashovacímu prostoru a dosazení souborů a úložných uzlů do pole doslova na hashované místo. Abychom získali asociaci, iterujeme od hashovaného umístění položky směrem doprava a najdeme první úložný uzel. Pokud dojdeme na konec pole a nenajdeme žádný Úložný uzel, zakroužkujeme zpět na index 0 a pokračujeme v hledání. Tento přístup je velmi snadno implementovatelný, ale trpí následujícími omezeními

• vyžaduje obrovskou paměť pro uložení tak velkého pole
• nalezení asociace iterací pokaždé doprava je O(hash_space)

Lepším způsobem implementace je použití dvou polí: jednoho pro uložení Úložných uzlů, nazvaného nodes, a druhého pro uložení pozic Úložných uzlů v hash prostoru, nazvaného keys. Mezi oběma poli existuje korespondence jedna ku jedné – Úložný uzel nodes se nachází na pozici keys v hash prostoru. Obě pole jsou udržována seřazená podle pole keys.

Hašovací funkce v konzistentním hašování

Definujeme total_slots jako velikost celého tohoto hašovacího prostoru, typicky řádově 2^256, a hašovací funkci bychom mohli implementovat tak, že vezmeme SHA-256 následovaný mod total_slots. Protože total_slots je obrovská a konstantní, je následující implementace hašovací funkce nezávislá na skutečném počtu uzlů úložiště přítomných v systému, a proto zůstává neovlivněna událostmi, jako je zvětšování a zmenšování.

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

Přidání nového uzlu v systému

Když je potřeba škálovat a přidat nový uzel v systému, v našem případě nový uzel úložiště, zjistíme

• pozici uzlu, kde se nachází v prostoru Hash
• naplníme nový uzel daty, která má obsluhovat
• přidáme uzel do prostoru Hash

Při přidání nového uzlu v systému to ovlivní pouze soubory, které mají hash na místě nalevo a jsou spojeny s uzlem napravo, od pozice, do které se nový uzel vejde. Všechny ostatní soubory a asociace zůstávají neovlivněny, čímž se minimalizuje množství dat, která je třeba migrovat, a mapování, které je třeba změnit.

Z výše uvedeného obrázku vidíme, že při přidání nového uzlu K mezi uzly B a E změníme asociace souborů přítomných v segmentu B-K a přiřadíme je k uzlu K. Data patřící do segmentu B-K bychom mohli najít v uzlu E, ke kterému byla dříve přiřazena. Jediné soubory, kterých se to týká a které je třeba migrovat, se tedy nacházejí v segmentu B-K; a jejich asociace se mění z uzlu E na uzel K.

Abychom to mohli realizovat na nízké úrovni pomocí pole nodes a keys, nejprve získáme pozici nového uzlu v hash prostoru pomocí hash funkce. Poté najdeme index nejmenšího klíče většího než pozice v setříděném poli keys pomocí binárního vyhledávání. Na tomto indexu bude umístěn klíč a nový uzel Úložiště v poli keys, respektive 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

Odstranění nového uzlu ze systému

Pokud je potřeba zmenšit a odstranit stávající uzel ze systému, nalezneme

• pozici uzlu, který má být odstraněn, v prostoru Hash
• doplníme uzel napravo daty, která byla spojena s odstraňovaným uzlem
• odstraníme uzel z prostoru Hash

Při odstranění uzlu ze systému to ovlivní pouze soubory spojené se samotným uzlem. Všechny ostatní soubory a asociace zůstávají nedotčeny, čímž se minimalizuje množství dat, která je třeba migrovat, a mapování, které je třeba změnit.

Z výše uvedeného obrázku vidíme, že při odstranění uzlu K ze systému změníme asociace souborů přidružených k uzlu K na uzel, který leží bezprostředně vpravo od něj, i.tj. uzlu E. Tedy jediné soubory, které jsou ovlivněny a potřebují migraci, jsou soubory spojené s uzlem K.

Abychom to mohli realizovat na nízké úrovni pomocí pole nodes a keys, získáme index, kde leží uzel K v poli keys, pomocí binárního vyhledávání. Jakmile máme index, odstraníme klíč z pole keys a uzel úložiště z pole nodes přítomný na tomto indexu.

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

Přiřazení položky k uzlu

Teď, když jsme viděli, jak důsledné hashování pomáhá udržet migraci dat, během rozšiřování a snižování, na minimu; je čas podívat se, jak efektivně můžeme najít „uzel vpravo“ pro danou položku. Operace pro nalezení asociace musí být superrychlá a efektivní, protože je to něco, co bude vyvoláno při každém jednotlivém čtení a zápisu, ke kterému v systému dojde.

Pro implementaci na nízké úrovni opět využijeme binární vyhledávání a tuto operaci provedeme v O(log(n)). Nejprve předáme položku hashovací funkci a načteme pozici, na které je položka zaheslována v hash prostoru. Tuto pozici pak binárně prohledáme v poli keys, abychom získali index prvního klíče, který je větší než pozice (získaná z hashovací funkce). pokud v poli keys není žádný klíč větší než pozice, zakroužkujeme zpět a vrátíme 0. index. Takto získaný index bude indexem uzlu úložiště v poli nodes, který je spojen s danou položkou.

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

Zdrojový kód s implementací konzistentního hašování v jazyce Python bylo možné nalézt na adrese github.com/arpitbbhayani/consistent-hashing.

Závěr

Konzistentní hašování je jedním z nejdůležitějších algoritmů, které nám pomáhají horizontálně škálovat a spravovat jakýkoli distribuovaný systém. Algoritmus nefunguje pouze v sharded systémech, ale své uplatnění nachází také při vyvažování zátěže, rozdělování dat, správě serverových sticky relací, směrovacích algoritmech a mnoha dalších. Mnoho databází vděčí za svůj rozsah, výkon a schopnost zvládnout obrovskou zátěž právě konzistentnímu hašování.

• Hashovací funkce – Wikipedia
• Konzistentní hašování – Wikipedia
• Konzistentní hašování – Stanford
• Konzistentní hašování a náhodné stromy
• Dynamo:

Další články, které by vás mohly zajímat:

• Python Cache Integers
• Frakční kaskádování – zrychlení binárního vyhledávání
• Sémantika kopírování při zápisu
• Co dělá MySQL LRU cache odolnou proti skenování
• Building Finite State Machines with Python Coroutines

Tento článek byl původně publikován na mém blogu – Consistent Hashing.

Pokud se vám přečtené líbilo, přihlaste se k odběru mého newsletteru, aby vám byl příspěvek doručen přímo do schránky, a dejte mi vědět @arpit_bhayani.

.