Consistent hashing is een hashing techniek die heel goed presteert wanneer ze wordt gebruikt in een dynamische omgeving waar het gedistribueerde systeem regelmatig op- en afschaalt. Het kernconcept van Consistent Hashing werd geïntroduceerd in de paper Consistent Hashing and RandomTrees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, maar het won aan populariteit na de beroemde paper waarin DynamoDB werd geïntroduceerd – Dynamo: Amazon’s Highly Available Key-value Store. Sindsdien heeft het consistent hashen aan tractie gewonnen en een ton aan use cases gevonden in het efficiënt ontwerpen en schalen van gedistribueerde systemen. De twee bekende voorbeelden die deze techniek uitputtend gebruiken zijn Bit Torrent, voor hun peer-to-peer netwerken en Akamai, voor hun web caches. In dit artikel duiken we diep in de noodzaak van Consistent Hashing, de internals ervan, en nog belangrijker, onderweg implementeren we het met arrays en Binary Search.

Voordat we in de kern van de Consistent Hashing techniek springen, moeten we eerst een paar dingen ophelderen, een daarvan is Hash Functies. Hash Functies zijn alle functies die een waarde toewijzen van een willekeurig groot domein naar een ander domein met een vaste grootte, meestal de Hash Ruimte genoemd. Bijvoorbeeld URL’s toewijzen aan 32-bits gehele getallen of HTML-inhoud van webpagina’s aan een tekenreeks van 256 bytes. De waarden die als uitvoer van deze hash-functies worden gegenereerd, worden gewoonlijk als sleutels gebruikt om efficiënt zoeken naar de oorspronkelijke entiteit mogelijk te maken.

Een voorbeeld van een eenvoudige hash-functie is een functie die een 32-bits geheel getal in een 8-bits geheel getal in de hash-ruimte omzet. De functie zou kunnen worden geïmplementeerd met behulp van de rekenkundige operator modulo en we kunnen dit bereiken door een modulo 256 te nemen die getallen oplevert in het bereik die 8 bits in beslag nemen voor de representatie ervan. Een hash-functie, die sleutels aan zo’n geheel getalgebied koppelt, past meestal de modulo N toe om de waarden, of de hash-ruimte, te beperken tot een bereik .

Een goede hash-functie heeft de volgende eigenschappen

• De functie is rekenkundig efficiënt en de gegenereerde waarden zijn gemakkelijk op te zoeken
• De functie gedraagt zich, voor de meeste algemene gebruikssituaties, als een pseudorandom-generator die gegevens gelijkmatig verspreidt zonder merkbare correlatie

Nu we hebben gezien wat een hash-functie is, bekijken we hoe we ze zouden kunnen gebruiken om een enigszins schaalbaar gedistribueerd systeem te bouwen.

Bouwen van een gedistribueerd opslagsysteem

Stel dat we een gedistribueerd opslagsysteem bouwen waarin gebruikers bestanden kunnen uploaden en op aanvraag kunnen openen. De dienst stelt de volgende API’s ter beschikking van de gebruikers

• upload om het bestand te uploaden
• fetch om het bestand op te halen en de inhoud terug te sturen

Achter de schermen heeft het systeem Storage Nodes waarop de bestanden worden opgeslagen en geopend. Deze knooppunten stellen de functies put_file en fetch_file ter beschikking die de bestandsinhoud op de schijf zetten en ophalen en het antwoord naar de API-server sturen die het op zijn beurt naar de gebruiker terugstuurt.

Om de aanvankelijke belasting te ondersteunen, heeft het systeem 5 Stogare-knooppunten die de geüploade bestanden op een gedistribueerde manier opslaan. Het hebben van meerdere nodes zorgt ervoor dat het systeem, als geheel, niet wordt overweldigd, en de opslag is bijna gelijkmatig verdeeld over.

Wanneer de gebruiker de functie upload aanroept met het pad van het bestand, moet het systeem eerst het opslagknooppunt identificeren dat verantwoordelijk zal zijn voor het vasthouden van het bestand en we doen dit door een hash-functie toe te passen op het pad en op zijn beurt de index van het opslagknooppunt te krijgen. Zodra we het opslagknooppunt hebben, lezen we de inhoud van het bestand en plaatsen dat bestand op het knooppunt door de put_file functie van het knooppunt aan te roepen.

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

De hier gebruikte hash-functie telt eenvoudig de bytes op en neemt de modulo door 5 (aangezien er 5 opslagknooppunten in het systeem zijn) en genereert zo de uitvoer in de hash-ruimte . Deze output waarde vertegenwoordigt nu de index van het opslagsysteem dat verantwoordelijk zal zijn voor het bewaren van het bestand.

Stel we hebben 5 bestanden ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ als we de hash functie hierop toepassen vinden we dat ze zijn opgeslagen op opslag nodes E, A, B, C, en D respectievelijk.

Dingen worden interessant als het systeem wat tractie krijgt en het moet worden geschaald naar 7 nodes, wat betekent dat nu de hash functie mod 7 moet doen in plaats van een mod 5. Het veranderen van de hash-functie impliceert het veranderen van de mapping en de associatie van bestanden met opslag nodes. We moeten eerst de nieuwe associaties beheren en zien welke bestanden van het ene naar het andere knooppunt moeten worden verplaatst.

Met de nieuwe hash-functie zullen dezelfde 5 bestanden ‘f1.txt’, ‘f2.txt’, ‘f3.txt’, ‘f4.txt’, ‘f5.txt’ nu worden geassocieerd met opslagknooppunten D, E, F, G, A. Hier zien we dat het veranderen van de hash-functie vereist dat we elk van de 5 bestanden naar een andere node moeten verplaatsen.

Als we de hash-functie elke keer moeten veranderen als we omhoog of omlaag schalen en als dit vereist dat we niet alle, maar zelfs de helft van de gegevens moeten verplaatsen, wordt het proces superduur en op de langere termijn onhaalbaar. Dus hebben we een manier nodig om de data verplaatsing die nodig is tijdens scale-ups of scale-downs te minimaliseren, en dit is waar Consistent Hashing in past en de vereiste data overdracht minimaliseert.

Consistent Hashing

Het grote pijnpunt van het bovenstaande systeem is dat het gevoelig is voor gebeurtenissen zoals scale-ups en scale-downs omdat het veel wijzigingen in associaties vereist. Deze associaties worden puur gedreven door de onderliggende Hash Functie en dus als we op een of andere manier deze hash functie onafhankelijk kunnen maken van het aantal opslag nodes in het systeem, verhelpen we dit euvel.

Consistent Hashing pakt deze situatie aan door de Hash Ruimte enorm en constant te houden, ergens in de orde van en de opslag node en objecten beide te mappen naar een van de slots in deze enorme Hash Ruimte. Anders dan in het traditionele systeem, waar het bestand werd geassocieerd met een opslagknooppunt op de index waar het werd gehasht, is in dit systeem de kans op een botsing tussen een bestand en een opslagknooppunt oneindig klein en daarom hebben we een andere manier nodig om deze associatie te definiëren.

In plaats van een op botsingen gebaseerde aanpak te gebruiken, definiëren we de associatie als – het bestand wordt geassocieerd met het opslagknooppunt dat onmiddellijk rechts van zijn gehashte locatie aanwezig is. Door de associatie op deze manier te definiëren, kunnen we

• de hashfunctie onafhankelijk houden van het aantal opslagknooppunten
• associaties relatief houden en niet gedreven door absolute botsingen

Consistent Hashing vereist gemiddeld slechts k/n eenheden van gegevens die moeten worden gemigreerd tijdens het opschalen en afschalen; waarbij k het totale aantal sleutels is en n het aantal knooppunten in het systeem.

Een zeer naïeve manier om dit te implementeren is door een array met een grootte gelijk aan de Hash-ruimte toe te wijzen en bestanden en opslagknooppunten letterlijk in de array op de gehashte locatie te zetten. Om een associatie te krijgen itereren we van de hashed locatie van het item naar rechts en vinden de eerste Storage Node. Als we het einde van de array bereiken en geen Storage Node vinden, cirkelen we terug naar index 0 en gaan verder met zoeken. De aanpak is zeer eenvoudig te implementeren maar lijdt aan de volgende beperkingen

• vereist enorm veel geheugen om zo’n grote array te bevatten
• associatie vinden door telkens naar rechts te itereren is O(hash_space)

Een betere manier om dit te implementeren is door twee arrays te gebruiken: een om de Storage Nodes in op te slaan, nodes genaamd, en een andere om de posities van de Storage Nodes in de hash-ruimte op te slaan, keys genaamd. Er is een één-op-één correspondentie tussen de twee arrays – het opslagknooppunt nodes is aanwezig op positie keys in de hash-ruimte. Beide arrays worden gesorteerd gehouden volgens de keys array.

Hash Functie in Consistent Hashing

We definiëren total_slots als de grootte van deze gehele hash ruimte, typisch van de orde 2^256 en de hash functie zou kunnen worden geïmplementeerd door SHA-256 te nemen gevolgd door een mod total_slots. Aangezien total_slots enorm is en een constante, is de volgende hashfunctie-implementatie onafhankelijk van het werkelijke aantal Opslagknooppunten in het systeem en blijft dus onaangetast door gebeurtenissen zoals scale-ups en scale-downs.

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

Een nieuwe node aan het systeem toevoegen

Wanneer er behoefte is om op te schalen en een nieuwe node aan het systeem toe te voegen, in ons geval een nieuwe Storage Node, zoeken we

• de positie van de node waar hij zich bevindt in de Hash Space
• populeren de nieuwe node met data die hij moet bedienen
• toevoegen van de node in de Hash Space

Wanneer een nieuwe node in het systeem wordt toegevoegd, heeft dit alleen invloed op de bestanden die hashen op de locatie links en geassocieerd met de node rechts, van de positie waar de nieuwe node in past. Alle andere bestanden en associaties blijven onaangetast, zodat de hoeveelheid te migreren gegevens en de mapping die moet worden gewijzigd tot een minimum wordt beperkt.

Uit bovenstaande afbeelding blijkt dat wanneer een nieuw knooppunt K wordt toegevoegd tussen de knooppunten B en E, we de associaties wijzigen van bestanden die aanwezig zijn in het segment B-K en deze toewijzen aan knooppunt K. De gegevens die bij het segment B-K horen, kunnen worden gevonden bij knooppunt E waarmee ze eerder waren geassocieerd. Dus de enige bestanden die worden beïnvloed en die moeten worden gemigreerd, bevinden zich in het segment B-K; en hun associatie verandert van knooppunt E naar knooppunt K.

Om dit op een laag niveau te implementeren met behulp van nodes en keys array, krijgen we eerst de positie van het nieuwe knooppunt in de Hash Space met behulp van de hash-functie. Vervolgens vinden we de index van de kleinste sleutel groter dan de positie in de gesorteerde keys array met behulp van binair zoeken. Deze index zal de plaats zijn waar de sleutel en de nieuwe Storage node zullen worden geplaatst in respectievelijk keys en nodes array.

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

Een nieuwe node uit het systeem verwijderen

Wanneer het nodig is om af te schalen en een bestaande node uit het systeem te verwijderen, zoeken we

• de positie van de te verwijderen node uit de Hash Space
• populeren de node naar rechts met gegevens die geassocieerd waren met de te verwijderen node
• verwijderen we de node uit de Hash Space

Wanneer een node uit het systeem wordt verwijderd, heeft dit alleen gevolgen voor de bestanden die geassocieerd zijn met de node zelf. Alle andere bestanden en koppelingen blijven onaangetast, zodat de hoeveelheid gegevens die moet worden gemigreerd en de mapping die moet worden gewijzigd tot een minimum worden beperkt.

Uit de bovenstaande illustratie blijkt dat wanneer koppeling K uit het systeem wordt verwijderd, de koppelingen van bestanden die aan koppeling K zijn gekoppeld, worden gewijzigd naar de koppeling die zich direct rechts van deze koppeling bevindt, d.w.z. koppeling E.Dus de enige bestanden die beïnvloed worden en gemigreerd moeten worden zijn diegene die geassocieerd zijn met node K.

Om dit op een laag niveau te implementeren met behulp van nodes en keys array, krijgen we de index waar node K ligt in de keys array met behulp van binair zoeken. Zodra we de index hebben, verwijderen we de sleutel uit de keys array en Storage Node uit de nodes array die op die index aanwezig is.

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

Een item aan een node koppelen

Nu we hebben gezien hoe consistent hashen helpt om datamigratie, tijdens scale-ups en scale-downs, tot een absoluut minimum te beperken; is het tijd dat we zien hoe we efficiënt de “juiste node” voor een gegeven item kunnen vinden. De operatie om de associatie te vinden moet supersnel en efficiënt zijn, omdat het iets is dat zal worden aangeroepen voor elke lees en schrijf die op het systeem gebeurt.

Om dit op laag niveau te implementeren, maken we weer gebruik van binair zoeken en voeren deze operatie uit in O(log(n)). We geven het item eerst door aan de hash-functie en halen de positie op waar het item is gehasht in de hash-ruimte. Deze positie wordt dan binair doorzocht in de keys array om de index te verkrijgen van de eerste sleutel die groter is dan de positie (verkregen van de hash-functie). Als er geen sleutels groter dan de positie zijn, in de keys array, cirkelen we terug en geven de 0e index terug. De aldus verkregen index is de index van de opslagnode in de nodes array die bij het item hoort.

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

De broncode met de implementatie van Consistent Hashing in Python is te vinden op github.com/arpitbbhayani/consistent-hashing.

Conclusie

Consistent Hashing is een van de belangrijkste algoritmen om ons te helpen bij het horizontaal schalen en beheren van elk gedistribueerd systeem. Het algoritme werkt niet alleen in sharded systemen, maar vindt ook zijn toepassing in load balancing, data partitioning, managing server-based sticky sessions, routing algoritmes, en nog veel meer. Veel databases danken hun schaal, prestaties, en vermogen om de enorme belasting aan te kunnen aan Consistent Hashing.

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

Andere artikelen die u misschien leuk vindt:

• Python Caches Integers
• Fractional Cascading – Speeding up Binary Searches
• Copy-on-Write Semantics
• Wat maakt MySQL LRU cache scan resistent
• Building Finite State Machines with Python Coroutines

Dit artikel werd oorspronkelijk gepubliceerd op mijn blog – Consistent Hashing.

Als je het leuk vond om te lezen, schrijf je dan in op mijn nieuwsbrief en ontvang de post direct in je inbox en geef me een shout-out @arpit_bhayani.