A konzisztens hashing egy olyan hashing technika, amely akkor teljesít igazán jól, ha dinamikus környezetben működik, ahol az elosztott rendszer gyakran skálázódik fel és le. A Consistent Hashing alapkoncepcióját a Consistent Hashing and RandomTrees című dolgozatban mutattuk be: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, de népszerűségét a DynamoDB – Dynamo bemutató híres tanulmánya után nyerte el: Amazon’s Highly Available Key-value Store. Azóta a konzisztens hashing egyre nagyobb teret nyert, és rengeteg felhasználási esetet talált az elosztott rendszerek hatékony tervezésében és skálázásában. A két híres példa, amely kimerítően használja ezt a technikát, a Bit Torrent a peer-to-peer hálózatokhoz és az Akamai a webes gyorsítótárakhoz. Ebben a cikkben mélyen belemerülünk a Consistent Hashing szükségességébe, a belső tulajdonságaiba, és ami még fontosabb, útközben megvalósítjuk a tömbök és a Binary Search segítségével.

Mielőtt belevetnénk magunkat a Consistent Hashing technikába, először tisztázunk néhány dolgot, amelyek közül az egyik a Hash Functions. A Hash-funkciók olyan függvények, amelyek értéket képeznek le egy tetszőleges méretű tartományból egy másik rögzített méretű tartományba, amelyet általában Hash-térnek neveznek. Például az URL-címek 32 bites egész számokra vagy a weboldalak HTML-tartalma egy 256 bájtos karakterláncra való leképezése. Az ilyen hash függvények kimenetként generált értékeket általában kulcsként használják, hogy lehetővé tegyék az eredeti entitás hatékony keresését.

Egy egyszerű hash függvény példája egy olyan függvény, amely egy 32 bites egész számot egy 8 bites egész szám hash térbe képez le. A függvényt a modulo aritmetikai operátorral valósíthatjuk meg, és ezt úgy érhetjük el, hogy veszünk egy modulo 256-öt, amely a tartományba eső számokat ad ki, és 8 bitet vesz fel a reprezentációjához. Egy hash-függvény, amely kulcsokat képez le ilyen egész számtartományra, leggyakrabban a modulo N-et alkalmazza, hogy az értékeket, illetve a hash-térséget a tartományra korlátozza.

Egy jó hash-függvény a következő tulajdonságokkal rendelkezik

• A függvény számítási szempontból hatékony, és a generált értékek könnyen kereshetőek
• A függvény a legtöbb általános felhasználási esetben úgy viselkedik, mint egy pszeudorandom generátor, amely az adatokat egyenletesen, észrevehető korreláció nélkül szórja szét

Most, hogy láttuk, mi az a hash-függvény, nézzük meg, hogyan használhatjuk őket, és hogyan építhetünk egy valamennyire skálázható elosztott rendszert.

Egy elosztott tárolórendszer építése

Tegyük fel, hogy egy olyan elosztott tárolórendszert építünk, amelyben a felhasználók feltölthetnek fájlokat, és igény szerint hozzáférhetnek hozzájuk. A szolgáltatás a következő API-kat tárja a felhasználók elé

• upload a fájl feltöltéséhez
• fetch a fájl lekéréséhez és tartalmának visszaadásához

A színfalak mögött a rendszer rendelkezik Storage Node-okkal, amelyeken a fájlokat tároljuk és elérjük. Ezek a csomópontok a put_file és fetch_file függvényeket teszik közzé, amelyek a fájl tartalmát a lemezre helyezik és onnan hozzák, és a választ elküldik a fő API-kiszolgálónak, amely viszont visszaküldi azt a felhasználónak.

A kezdeti terhelés fenntartása érdekében a rendszer 5 Stogare csomóponttal rendelkezik, amelyek elosztott módon tárolják a feltöltött fájlokat. A több csomópont megléte biztosítja, hogy a rendszer egésze ne legyen túlterhelt, és a tárolás majdnem egyenletesen oszlik el a rendszerben.

Amikor a felhasználó a upload funkciót hívja meg a fájl elérési útvonalával, a rendszernek először azonosítania kell azt a tárolási csomópontot, amely a fájl tárolásáért felelős, és ezt úgy tesszük, hogy egy hash függvényt alkalmazunk az elérési útvonalra, és így megkapjuk a tárolási csomópont indexét. Miután megkaptuk a tárolási csomópontot, beolvassuk a fájl tartalmát, és a csomópont put_file függvényének meghívásával elhelyezzük a fájlt a csomóponton.

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

Az itt használt hash függvény egyszerűen összeadja a bájtokat, és a modulót 5-tel veszi (mivel 5 tárolási csomópont van a rendszerben), és így a kimenetet a hash térben generálja. Ez a kimeneti érték most annak a tárolónak az indexét jelenti, amely a fájl tárolásáért felelős.

Tegyük fel, hogy 5 fájlunk van ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ ha ezekre alkalmazzuk a hash függvényt, akkor azt találjuk, hogy az E, A, B, C, és D tároló csomópontokon vannak tárolva.

A dolgok akkor válnak érdekessé, amikor a rendszer némi vonzerőt nyer, és 7 csomópontra kell skálázni, ami azt jelenti, hogy most a hash függvénynek mod 5 helyett mod 7 kell tennie. A hash-függvény megváltoztatása a fájlok és a tárolási csomópontok leképezésének és társításának megváltoztatását jelenti. Először is adminisztrálnunk kell az új társításokat, és meg kell néznünk, hogy mely fájlokat kell áthelyezni egyik csomópontból a másikba.

Az új hash függvénnyel ugyanaz az 5 fájl ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ mostantól a D, E, F, G, A tárolási csomópontokhoz lesz társítva. Itt láthatjuk, hogy a hash-függvény megváltoztatásához az 5 fájl mindegyikét át kell helyeznünk egy másik csomópontra.

Ha a hash-függvényt minden alkalommal meg kell változtatnunk, amikor felfelé vagy lefelé skálázunk, és ha ehhez nem az összes, hanem akár az adatok felét is át kell helyeznünk, a folyamat szuperdrágává és hosszabb távon megvalósíthatatlanná válik. Szükségünk van tehát egy olyan módszerre, amellyel minimalizálhatjuk a skála fel- és leépítések során szükséges adatmozgatást, és itt jön be a képbe a Consistent Hashing, amely minimalizálja a szükséges adatátvitelt.

Consistent Hashing

A fenti rendszer fő fájdalmas pontja, hogy hajlamos az olyan eseményekre, mint a skála fel- és leépítések, mivel sok módosítást igényel a társításokban. Ezeket az asszociációkat tisztán a mögöttes Hash-funkció vezérli, és ezért ha valahogy függetleníteni tudnánk ezt a hash-funkciót a rendszerben lévő tárolócsomópontok számától, akkor megoldanánk ezt a hibát.

A konzisztens Hashing úgy oldja meg ezt a helyzetet, hogy a Hash Space hatalmas és állandó, valahol nagyságrendű, és a tárolócsomópont és az objektumok egyaránt ennek a hatalmas Hash Space-nek az egyik slotjához tartoznak. A hagyományos rendszerrel ellentétben, ahol a fájl a tárolási csomóponthoz azon az indexen volt hozzárendelve, ahová a fájl hashelésre került, ebben a rendszerben a fájl és a tárolási csomópont közötti ütközés esélye végtelenül kicsi, ezért más módon kell meghatározni ezt a hozzárendelést.

Az ütközés alapú megközelítés helyett a következőképpen határozzuk meg a hozzárendelést: a fájl ahhoz a tárolási csomóponthoz lesz hozzárendelve, amely a hashelt helyétől közvetlenül jobbra van. Az asszociáció ilyen módon történő definiálása segít nekünk

• fenntartani a hash-függvény függetlenségét a tárolási csomópontok számától
• az asszociációk relatívak maradnak, és nem az abszolút ütközések vezérlik őket

A konzisztens zárolás átlagosan csak k/n egységnyi adat migrálását igényli a fel- és leskálázás során; ahol k a kulcsok teljes száma és n a rendszerben lévő csomópontok száma.

Egy nagyon naiv módja ennek megvalósítására az, hogy kiosztunk egy a Hash Space-nek megfelelő méretű tömböt, és a fájlokat és a tároló csomópontokat szó szerint a tömbben helyezzük el a hashelt helyen. Az asszociáció megszerzéséhez az elem hashelt helyétől jobbra iterálunk, és megkeressük az első Storage Node-ot. Ha elérjük a tömb végét, és nem találunk egyetlen Storage Node-ot sem, akkor visszakerülünk a 0. indexhez, és folytatjuk a keresést. A megközelítés nagyon könnyen megvalósítható, de a következő korlátoktól szenved

• nagy memóriát igényel egy ekkora tömb tartásához
• az asszociáció megtalálása a minden alkalommal jobbra történő iterálással O(hash_space)

A megvalósítás jobb módja, ha két tömböt használunk: egyet a Tárolási csomópontok tárolására, melynek neve nodes, és egy másikat a Tárolási csomópontok pozícióinak tárolására a hash-térben, melynek neve keys. A két tömb között egy az egyhez megfelelés van – a nodes tárolási csomópont a keys pozícióban van a hash-térben. Mindkét tömböt a keys tömbnek megfelelően rendezve tartjuk.

Hashtagfüggvény a konzisztens hasholásban

A teljes hash-tér méreteként total_slots definiáljuk, ami jellemzően 2^256 nagyságrendű, és a hash-függvényt úgy lehet megvalósítani, hogy az SHA-256-ot egy mod total_slots követi. Mivel a total_slots hatalmas és állandó, a következő hash-funkció megvalósítása független a rendszerben lévő tárolási csomópontok tényleges számától, és így nem befolyásolják az olyan események, mint a skála-növelés és -csökkentés.

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

Új csomópont hozzáadása a rendszerhez

Ha szükség van a rendszer skálázására és egy új csomópont, esetünkben egy új Storage Node hozzáadására, mi

• megkeressük a csomópont pozícióját, ahol a Hash Space-ben található
• feltöltjük az új csomópontot azokkal az adatokkal, amelyeket ki kell szolgálnia
• hozzáadjuk a csomópontot a Hash Space-ben

Mikor egy új csomópontot adunk hozzá a rendszerben, az csak azokra az állományokra van hatással, amelyek az új csomópont által elfoglalt pozíciótól balra lévő és a jobb oldalon lévő csomóponthoz tartozó hash-helyen vannak. Az összes többi fájl és társítás érintetlen marad, így minimálisra csökkentve a migrálandó adatok és a módosítandó leképezések mennyiségét.

A fenti ábrából látható, hogy amikor egy új, K csomópontot adunk hozzá a B és E csomópontok közé, megváltoztatjuk a B-K szegmensben található fájlok társításait, és a K csomóponthoz rendeljük őket. A B-K szegmenshez tartozó adatok az E csomópontban találhatók, amelyhez korábban társítva voltak. Így az egyetlen érintett és migrációt igénylő fájl a B-K szegmensben található; és a társításuk az E csomópontról a K csomópontra változik.

Az nodes és keys tömb segítségével történő alacsony szintű megvalósítás érdekében először a hash függvény segítségével megkapjuk az új csomópont pozícióját a Hash térben. Ezután megkeressük a rendezett keys tömbben a pozíciónál nagyobb legkisebb kulcs indexét a bináris keresés segítségével. Ez az index lesz az, ahová a kulcs és az új tároló csomópont kerül a keys, illetve a nodes tömbben.

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

Új csomópont eltávolítása a rendszerből

Ha egy meglévő csomópontot kell lekicsinyíteni és eltávolítani a rendszerből, mi

• megkeressük az eltávolítandó csomópont pozícióját a Hash térből
• feltöltjük a jobb oldali csomópontot az eltávolítandó csomóponthoz tartozó adatokkal
• eltávolítjuk a csomópontot a Hash térből

Mikor egy csomópontot eltávolítunk a rendszerből, az csak a csomóponthoz tartozó fájlokat érinti. Minden más fájl és asszociáció érintetlen marad, így minimálisra csökkentve a migrálandó adatok és a módosítandó leképezések mennyiségét.

A fenti ábrából látható, hogy amikor a K csomópontot eltávolítjuk a rendszerből, a K csomóponthoz tartozó fájlok asszociációit a tőle közvetlenül jobbra i fekvő csomópontra módosítjuk.azaz az E csomópontra. Így csak a K csomóponthoz kapcsolódó fájlok érintettek és migrálásra szorulnak.

Azért, hogy ezt alacsony szinten megvalósítsuk a nodes és a keys tömb használatával, bináris kereséssel megkapjuk az indexet, ahol a K csomópont a keys tömbben található. Miután megkaptuk az indexet, eltávolítjuk a kulcsot a keys tömbből és a tárolási csomópontot a nodes tömbből, amely az indexen jelen van.

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

Egy elem hozzárendelése egy csomóponthoz

Most, miután láttuk, hogy a konzisztens hashing hogyan segít abban, hogy az adatok migrációja – a skála fel- és leépítések során – minimálisra csökkenjen; itt az ideje megnézni, hogyan tudjuk hatékonyan megtalálni egy adott elemhez a “megfelelő csomópontot”. Az asszociáció megtalálására szolgáló műveletnek szupergyorsnak és hatékonynak kell lennie, mivel ez olyasvalami, ami minden egyes olvasásnál és írásnál, ami a rendszerben történik, meghívásra kerül.

Az alacsony szintű megvalósításhoz ismét kihasználjuk a bináris keresést, és ezt a műveletet a O(log(n))-ben hajtjuk végre. Először átadjuk az elemet a hash függvénynek, és lekérjük azt a pozíciót, ahol az elem a hash térben hash-olt. Ezt a pozíciót ezután binárisan megkeressük a keys tömbben, hogy megkapjuk az első olyan kulcs indexét, amely nagyobb, mint a pozíció (amit a hash függvénytől kaptunk). ha nincs a pozíciónál nagyobb kulcs a keys tömbben, akkor visszakerülünk és visszaadjuk a 0. indexet. Az így kapott index lesz a nodes tömbben az elemhez tartozó tárolási csomópont indexe.

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

A forráskódot a konzisztens zárolás Python nyelven történő megvalósításával a github.com/arpitbbhayani/consistent-hashing.

Következtetés

A konzisztens zárolás az egyik legfontosabb algoritmus, amely segít nekünk bármilyen elosztott rendszer horizontális skálázásában és kezelésében. Az algoritmus nem csak sharded rendszerekben működik, hanem a terheléselosztásban, az adatok particionálásában, a szerver alapú ragadós munkamenetek kezelésében, az útválasztási algoritmusokban és még sok másban is alkalmazást talál. Rengeteg adatbázis köszönheti skálázhatóságát, teljesítményét és a hatalmas terhelés kezelésének képességét a Consistent Hashingnek.

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

További cikkek, amelyek érdekelhetik:

• Python Caches 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

This article was originally published on my blog – Consistent Hashing.

Ha tetszett, amit olvastál, iratkozz fel a hírlevelemre, hogy közvetlenül a postaládádba kapd meg a bejegyzést, és adj egy felkiáltást @arpit_bhayani.

.