Consistent Hashing on hashing-tekniikka, joka toimii todella hyvin, kun sitä käytetään dynaamisessa ympäristössä, jossa hajautettu järjestelmä skaalautuu ja skaalautuu usein. Consistent Hashingin ydinkonsepti esiteltiin artikkelissa Consistent Hashing and RandomTrees: Distributed Caching Protocols for Relieving Hot Spots on World Wide Web, mutta se saavutti suosiota sen jälkeen, kun DynamoDB – Dynamo esiteltiin kuuluisassa julkaisussa: Amazon’s Highly Available Key-value Store. Sittemmin johdonmukainen hashing sai vetovoimaa ja löysi lukuisia käyttötapauksia hajautettujen järjestelmien tehokkaassa suunnittelussa ja skaalaamisessa. Kaksi kuuluisaa esimerkkiä, joissa tätä tekniikkaa käytetään kattavasti, ovat Bit Torrent vertaisverkoissa ja Akamai verkkokätköissä. Tässä artikkelissa sukellamme syvälle Consistent Hashing -tekniikan tarpeeseen, sen sisäisiin ominaisuuksiin ja mikä tärkeintä, toteutamme sen matkan varrella käyttäen matriiseja ja binäärihakua.

Ennen kuin hyppäämme Consistent Hashing -tekniikan ytimeen, selvitämme ensin muutaman asian, joista yksi on Hash-funktiot. Hash-funktiot ovat mitä tahansa funktioita, jotka kartoittavat arvoa mielivaltaisen kokoisesta alueesta toiseen kiinteän kokoiseen alueeseen, jota yleensä kutsutaan Hash-avaruudeksi. Esimerkiksi URL-osoitteet 32-bittisiin kokonaislukuihin tai verkkosivujen HTML-sisältö 256 tavun merkkijonoon. Näiden hash-funktioiden tulosteena syntyviä arvoja käytetään tyypillisesti avaimina, jotta alkuperäisen olion tehokas haku olisi mahdollista.

Esimerkki yksinkertaisesta hash-funktiosta on funktio, joka kartoittaa 32-bittisen kokonaisluvun 8-bittiseen kokonaisluvun hash-avaruuteen. Funktio voitaisiin toteuttaa käyttämällä aritmeettista operaattoria modulo, ja voimme saavuttaa tämän ottamalla modulo 256, joka tuottaa luvut alueella , joka ottaa 8-bittisen esityksensä. Hash-funktio, joka kuvaa avaimet tällaiseen kokonaislukualueeseen, käyttää useimmiten modulo N:tä, jotta arvot tai hash-avaruus voidaan rajoittaa alueelle .

Hyvällä hash-funktiolla on seuraavat ominaisuudet

• Funktio on laskennallisesti tehokas ja sen tuottamia arvoja on helppo hakea
• Funktio käyttäytyy useimmissa yleisissä käyttötapauksissa kuin pseudosatunnaisgeneraattori, joka levittää dataa tasaisesti ilman havaittavaa korrelaatiota

Nyt kun olemme nähneet, mikä hash-funktio on, katsomme, miten voisimme käyttää niitä ja rakentaa jonkin verran skaalautuvan hajautetun järjestelmän.

Hajautetun tallennusjärjestelmän rakentaminen

Esitettäköön, että rakennamme hajautetun tallennusjärjestelmän, jossa käyttäjät voivat ladata tiedostoja ja käyttää niitä pyydettäessä. Palvelu paljastaa käyttäjille seuraavat API:t

• upload tiedoston lataamiseen
• fetch tiedoston hakemiseen ja sen sisällön palauttamiseen

Kulissien takana järjestelmällä on Storage Nodeja, joihin tiedostot tallennetaan ja joita käytetään. Nämä solmut paljastavat funktiot put_file ja fetch_file, jotka asettavat ja hakevat tiedoston sisällön levylle/levyltä ja lähettävät vastauksen API-pääpalvelimelle, joka puolestaan lähettää sen takaisin käyttäjälle.

Alkuperäisen kuormituksen ylläpitämiseksi järjestelmässä on 5 Stogare-solmua, jotka tallentavat ladatut tiedostot hajautetusti. Useiden solmujen avulla varmistetaan, että koko järjestelmä ei ole ylikuormitettu ja että tallennus jakautuu lähes tasaisesti eri puolille.

Kun käyttäjä kutsuu upload-funktiota tiedoston polun kanssa, järjestelmän on ensin tunnistettava tallennussolmu, joka vastaa tiedoston säilyttämisestä, ja tämä tehdään soveltamalla hash-funktiota polkuun ja hakemalla puolestaan tallennussolmun indeksi. Kun olemme saaneet tallennussolmun, luemme tiedoston sisällön ja laitamme tiedoston solmuun kutsumalla solmun put_file-funktiota.

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

Tässä käytetty hash-funktio yksinkertaisesti laskee tavut yhteen ja ottaa moduulin 5:llä (koska järjestelmässä on viisi tallennussolmua) ja tuottaa siten tuloksen hash-avaruuteen . Tämä tulostusarvo edustaa nyt sen tallennuskoneen indeksiä, joka vastaa tiedoston säilyttämisestä.

Esitettäköön, että meillä on 5 tiedostoa ’f1.txt’, ’f2.txt’, ’f3.txt’, ’f4.txt’, ’f5.txt’, jos sovellamme hash-funktiota näihin, saamme selville, että ne on tallennettu tallennussolmuihin E, A, B, C ja D vastaavasti.

Toiminta muuttuu mielenkiintoiseksi, kun järjestelmä saa jonkin verran vetovoimaa ja se täytyy skaalata 7 solmuun, mikä tarkoittaa, että nyt hash-funktion pitäisi tehdä mod 7 mod 5:n sijasta. Hash-funktion muuttaminen merkitsee tiedostojen ja tallennussolmujen kartoittamisen ja yhdistämisen muuttamista. Meidän on ensin hallinnoitava uusia assosiaatioita ja katsottava, mitkä tiedostot on siirrettävä solmusta toiseen.

Uuden hash-funktion avulla samat viisi tiedostoa ’f1.txt’, ’f2.txt’, ’f3.txt’, ’f4.txt’, ’f5.txt’ assosioituvat nyt säilytyssolmuihin D, E, F, G, A. Tästä näemme, että hash-funktion muuttaminen edellyttää jokaisen viiden tiedoston siirtämistä eri solmuun.

Jos meidän on muutettava hash-funktiota joka kerta, kun skaalaamme suuremmaksi tai pienemmäksi, ja jos tämä edellyttää, että meidän on siirrettävä paitsi kaikki, myös puolet datasta, prosessista tulee erittäin kallis ja pidemmällä aikavälillä mahdoton toteuttaa. Tarvitsemme siis keinon minimoida datan siirtäminen, jota tarvitaan skaalautumisen tai skaalautumisen aikana, ja tähän sopii Consistent Hashing, joka minimoi tarvittavan tiedonsiirron.

Consistent Hashing

Ylläolevan järjestelmän suurin kipupiste on se, että se on altis tapahtumille, kuten skaalautumisille ja skaalautumisille, koska se vaatii paljon muutoksia assosiaatioissa. Näitä assosiaatioita ohjaa puhtaasti taustalla oleva Hash-funktio, ja näin ollen jos voisimme jotenkin tehdä tästä hash-funktiosta riippumattoman järjestelmän tallennussolmujen lukumäärästä, poistaisimme tämän ongelman.

Konsistentti Hashing ratkaisee tämän tilanteen pitämällä Hash-avaruuden valtavana ja vakiona, jossain :n luokassa, ja tallennussolmu ja objektit kuvaavat kumpikin yhtä tämän valtavan Hash-avaruuden paikkaa. Toisin kuin perinteisessä järjestelmässä, jossa tiedosto yhdistettiin tallennussolmuun sen indeksin kohdalla, johon se hashattiin, tässä järjestelmässä tiedoston ja tallennussolmun välisen törmäyksen mahdollisuus on äärettömän pieni, ja siksi tarvitsemme toisenlaisen tavan määritellä tämä assosiaatio.

Törmäyspohjaisen lähestymistavan sijasta määrittelemme assosiaatio seuraavasti: tiedosto yhdistetään tallennussolmuun, joka on välittömästi oikealla sen hashattuun paikkaan nähden. Määrittelemällä assosiaatio tällä tavalla autamme meitä

• pitämään hash-funktion riippumattomana tallennussolmujen määrästä
• pitämään assosiaatiot suhteellisina eikä absoluuttisten törmäysten ohjaamina

Konsistentti hashing vaatii keskimäärin vain k/n yksikköä dataa siirrettäväksi skaalauksen aikana; missä k on avainten kokonaismäärä ja n on järjestelmän solmujen lukumäärä.

Erittäin naiivi tapa toteuttaa tämä on varata joukko, jonka koko on yhtä suuri kuin Hash-avaruus, ja sijoittaa tiedostot ja tallennussolmut kirjaimellisesti joukkoon hashattuun paikkaan. Saadaksemme assosiaation iteroimme kohteen hashed-sijainnista oikealle päin ja etsimme ensimmäisen Storage Noden. Jos päädymme matriisin loppuun emmekä löydä yhtään tallennussolmua, palaamme takaisin indeksiin 0 ja jatkamme hakua. Lähestymistapa on hyvin helppo toteuttaa, mutta kärsii seuraavista rajoituksista

• vaatii valtavasti muistia pitämään näin suurta arraya
• assosiaation löytäminen iteroimalla joka kerta oikealle on O(hash_space)

Parempi tapa toteuttaa tämä on käyttää kahta arraya: yksi Storage Nodeja pitämään, nimeltään nodes ja toinen Storage Nodejen sijainteja hash-avaruudessa, nimeltään keys. Näiden kahden matriisin välillä on yksi yhteen – tallennussolmu nodes on hash-avaruuden kohdassa keys. Molemmat matriisit pidetään lajiteltuina keys-matriisin mukaisesti.

Hash-funktio Consistent Hashingissa

Määritellään total_slots koko tämän hash-avaruuden kooksi, joka on tyypillisesti suuruusluokkaa 2^256, ja hash-funktio voitaisiin toteuttaa ottamalla SHA-256, jota seuraa mod total_slots. Koska total_slots on valtava ja vakio, seuraava hash-funktion toteutus on riippumaton järjestelmässä olevien Storage Nodes -solmujen todellisesta määrästä, eivätkä tapahtumat, kuten skaalautuminen ja skaalautuminen, vaikuta siihen.

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

Uuden solmun lisääminen järjestelmään

Kun on tarve skaalata ja lisätä järjestelmään uusi solmu, meidän tapauksessamme uusi Storage Node, me

• löydämme solmun sijainnin, jossa se sijaitsee Hash-avaruudessa
• täydennämme uuden solmun tiedoilla, joita sen on tarkoitus palvella
• lisäämme solmun Hash-avaruuteen

Kun uusi solmu lisätään järjestelmään, se vaikuttaa vain tiedostoihin, jotka hash-hajautetaan sijainnissa vasemmalla ja jotka on liitetty oikealla olevaan solmuun siitä sijainnista, johon uusi solmu sopii. Kaikkiin muihin tiedostoihin ja assosiaatioihin ei ole vaikutusta, mikä minimoi siirrettävien tietojen ja muutettavien kartoitusten määrän.

Yllä olevasta kuvasta nähdään, että kun solmujen B ja E väliin lisätään uusi solmu K, muutetaan segmentissä B-K olevien tiedostojen assosiaatioita ja osoitetaan ne solmuun K. Segmenttiin B-K kuuluvat tiedot löytyisivät solmusta E, johon ne aiemmin assosioitiin. Näin ollen ainoat tiedostot, joihin tämä vaikuttaa ja jotka on siirrettävä, ovat segmentissä B-K, ja niiden assosiaatio muuttuu solmusta E solmuun K.

Toteuttaaksemme tämän matalalla tasolla käyttämällä nodes– ja keys-matriisia, saamme ensin uuden solmun sijainnin Hash-avaruudessa käyttämällä hash-funktiota. Sen jälkeen etsitään pienimmän sijaintia suuremman avaimen indeksi lajitellusta keys-matriisista käyttäen binäärihakua. Tämä indeksi on se, mihin avain ja uusi Storage-solmu sijoitetaan keys– ja nodes-matriisissa.

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

Uuden solmun poistaminen järjestelmästä

Kun on tarpeen pienentää ja poistaa olemassa oleva solmu järjestelmästä, me

• löydämme poistettavan solmun sijainnin Hash-avaruudesta
• täydennämme oikeanpuoleisen solmun tiedoilla, jotka liittyivät poistettavaan solmuun
• poistamme solmun Hash-avaruudesta

Kun solmu poistetaan järjestelmästä, se vaikuttaa vain itse solmuun liittyviin tiedostoihin. Kaikkiin muihin tiedostoihin ja assosiaatioihin ei ole vaikutusta, mikä minimoi siirrettävän datan ja muutettavan kartoituksen määrän.

Yllä olevasta kuvasta nähdään, että kun solmu K poistetaan järjestelmästä, muutetaan solmuun K liittyvien tiedostojen assosiaatioita solmuun, joka sijaitsee sen välittömässä oikeassa reunassa olevaan i.eli solmuun E. Näin ollen ainoat tiedostot, joihin tämä vaikuttaa ja jotka tarvitsevat siirtoa, ovat ne, jotka liittyvät solmuun K.

Toteuttaaksemme tämän matalalla tasolla käyttämällä nodes– ja keys-matriisia, saamme indeksin, jossa solmu K sijaitsee keys-matriisissa, käyttämällä binäärihakua. Kun meillä on indeksi, poistamme avaimen keys-massasta ja tallennussolmun nodes-massasta, joka on läsnä kyseisessä indeksissä.

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

Elementin liittäminen solmuun

Nyt kun olemme nähneet, miten johdonmukainen hashaus auttaa pitämään datan siirtymisen skaalautumisen ja skaalautumisen aikana minimissään, on aika katsoa, miten tehokkaasti löydämme ”oikean solmun” tietylle elementille. Yhdistyksen löytämiseksi tehtävän operaation on oltava supernopea ja tehokas, koska sitä kutsutaan jokaisen järjestelmässä tapahtuvan lukemisen ja kirjoittamisen yhteydessä.

Toteuttaaksemme tämän matalalla tasolla hyödynnämme jälleen binäärihakua ja suoritamme tämän operaation O(log(n)):ssa. Välitämme kohteen ensin hash-funktiolle ja haemme paikan, jossa kohde on hashattu hash-avaruudessa. Tämän jälkeen tätä sijaintia haetaan binäärihaulla keys-matriisissa saadaksemme ensimmäisen avaimen indeksin, joka on suurempi kuin sijainti (saatu hash-funktiosta). jos keys-matriisissa ei ole yhtään sijaintia suurempaa avainta, palaamme takaisin ja palautamme 0. indeksin. Näin saatu indeksi on kohtaan liittyvän tallennussolmun indeksi nodes-matriisissa.

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

Lähdekoodi, jossa on Consistent Hashingin toteutus Pythonissa, löytyy osoitteesta github.com/arpitbbhayani/consistent-hashing.

Johtopäätökset

Consistent Hashing on yksi tärkeimmistä algoritmeista, joiden avulla voimme skaalautua vaakasuuntaisesti ja hallita mitä tahansa hajautettua järjestelmää. Algoritmi ei toimi ainoastaan sharded-järjestelmissä, vaan se löytää sovelluksensa myös kuorman tasauksessa, datan osioinnissa, palvelinpohjaisten tahmeiden istuntojen hallinnassa, reititysalgoritmeissa ja monissa muissa. Monet tietokannat ovat Consistent Hashingille velkaa skaalautuvuutensa, suorituskykynsä ja kykynsä käsitellä valtavaa kuormitusta.

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

Muita artikkeleita, joista saatat pitää:

• 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

Tämä artikkeli on alunperin julkaistu blogissani – Consistent Hashing.

Jos pidit lukemastasi, tilaa uutiskirjeeni ja saat postauksen suoraan postilaatikkoosi ja kerro minulle @arpit_bhayani.

Tilaa Arpitin uutiskirje

.