Konsistent hashning är en hashteknik som fungerar riktigt bra när den används i en dynamisk miljö där det distribuerade systemet ofta ökar och minskar i omfattning. Kärnkonceptet för Consistent Hashing introducerades i artikeln Consistent Hashing and RandomTrees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, men den blev populärare efter det berömda dokumentet DynamoDB – Dynamo: Amazon’s Highly Available Key-value Store. Sedan dess har den konsekventa hashingen fått ökad spridning och har funnit massor av användningsområden när det gäller att utforma och skala distribuerade system på ett effektivt sätt. De två kända exemplen som använder denna teknik på ett uttömmande sätt är Bit Torrent för sina peer-to-peer-nätverk och Akamai för sina webbcacher. I den här artikeln dyker vi djupt ner i behovet av Consistent Hashing, dess interna egenskaper och, ännu viktigare, implementerar den på vägen med hjälp av arrays och Binary Search.

För att hoppa in i kärnan i Consistent Hashing-tekniken måste vi först reda ut några saker, varav en är Hash-funktioner. Hashfunktioner är alla funktioner som mappar värde från en godtyckligt stor domän till en annan domän av fast storlek, vanligtvis kallad Hash Space. Till exempel mappning av URL:er till 32-bitars heltal eller webbsidors HTML-innehåll till en sträng på 256 byte. De värden som genereras som ett resultat av dessa hashfunktioner används vanligtvis som nycklar för att möjliggöra effektiva sökningar av den ursprungliga enheten.

Ett exempel på en enkel hashfunktion är en funktion som mappar ett 32-bitars heltal till ett 8-bitars heltal i hashutrymmet. Funktionen skulle kunna implementeras med hjälp av den aritmetiska operatören modulo och vi kan uppnå detta genom att ta ett modulo 256 som ger tal i intervallet som tar upp 8-bitar för sin representation. En hashfunktion, som mappar nycklar till ett sådant heltalsområde, tillämpar oftast modulo N för att begränsa värdena, eller hashutrymmet, till ett område .

En bra hashfunktion har följande egenskaper

• Funktionen är beräkningseffektiv och de värden som genereras är lätta att slå upp
• Funktionen beter sig, för de flesta allmänna användningsfall, som en pseudotillfallsgenerator som sprider data jämnt utan någon märkbar korrelation

När vi nu har sett vad en hashfunktion är tar vi en titt på hur vi skulle kunna använda dem och bygga ett något skalbart distribuerat system.

Bygga ett distribuerat lagringssystem

Säg att vi bygger ett distribuerat lagringssystem där användarna kan ladda upp filer och få tillgång till dem på begäran. Tjänsten exponerar följande API:er för användarna

• upload för att ladda upp filen
• fetch för att hämta filen och returnera dess innehåll

Här bakom kulisserna har systemet lagringsnoder på vilka filerna lagras och nås. Dessa noder exponerar funktionerna put_file och fetch_file som lägger in och hämtar filinnehållet till/från disken och skickar svaret till den huvudsakliga API-servern som i sin tur skickar tillbaka det till användaren.

För att klara av den initiala belastningen har systemet 5 Stogare-noder som lagrar de uppladdade filerna på ett distribuerat sätt. Att ha flera noder säkerställer att systemet som helhet inte blir överväldigat och att lagringen fördelas nästan jämnt över.

När användaren anropar upload-funktionen med filens sökväg måste systemet först identifiera den lagringsnod som kommer att ansvara för att lagra filen och vi gör detta genom att tillämpa en hashfunktion på sökvägen och i sin tur få fram indexet för lagringsnoden. När vi har fått fram lagringsnoden läser vi innehållet i filen och lägger filen på noden genom att åberopa put_file-funktionen för noden.

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

Hashfunktionen som används här summerar helt enkelt bytena och tar modulo med 5 (eftersom det finns 5 lagringsnoder i systemet) och genererar på så sätt utdata i hashutrymmet . Detta utdatavärde representerar nu indexet för den lagringsmotor som kommer att ansvara för att hålla filen.

Säg att vi har 5 filer ”f1.txt”, ”f2.txt”, ”f3.txt”, ”f4.txt”, ”f5.Om vi tillämpar hashfunktionen på dessa finner vi att de lagras på lagringsnoderna E, A, B, C respektive D.

Saker och ting blir intressanta när systemet får lite dragkraft och det behöver skalas upp till 7 noder, vilket innebär att hashfunktionen nu ska göra mod 7 i stället för mod 5. Att ändra hashfunktionen innebär att man ändrar mappningen och associeringen av filer med lagringsnoder. Vi måste först administrera de nya associationerna och se vilka filer som måste flyttas från en nod till en annan.

Med den nya hashfunktionen kommer samma 5 filer ”f1.txt”, ”f2.txt”, ”f3.txt”, ”f4.txt”, ”f5.txt” nu att associeras med lagringsnoderna D, E, F, G, A. Här ser vi att om vi ändrar hashfunktionen måste vi flytta varenda en av de fem filerna till en annan nod.

Om vi måste ändra hashfunktionen varje gång vi skalar upp eller ner, och om detta kräver att vi flyttar inte alla, utan till och med hälften av datamängderna, blir processen superdyr och i det långa loppet omöjlig att genomföra. Så vi behöver ett sätt att minimera den dataförflyttning som krävs vid uppskalning eller nedskalning, och det är här som Consistent Hashing passar in och minimerar den nödvändiga dataöverföringen.

Consistent Hashing

Den stora smärtpunkten med ovanstående system är att det är känsligt för händelser som uppskalning och nedskalning, eftersom det kräver en hel del ändringar i associationer. Dessa associationer styrs enbart av den underliggande hashfunktionen och om vi därför på något sätt kan göra denna hashfunktion oberoende av antalet lagringsnoder i systemet, åtgärdar vi denna brist.

Consistent Hashing åtgärdar denna situation genom att hålla hashutrymmet enormt och konstant, någonstans i storleksordningen , och lagringsnoden och objekten mappas båda till en av platserna i detta enorma hashutrymme. Till skillnad från det traditionella systemet där filen var associerad med lagringsnoden vid indexet där den hashades till, är chansen för en kollision mellan en fil och en lagringsnod i detta system oändligt liten och därför behöver vi ett annat sätt att definiera denna association.

Istället för att använda ett kollisionsbaserat tillvägagångssätt definierar vi associationen som – filen kommer att associeras med den lagringsnod som finns till omedelbar höger om dess hashade plats. Att definiera associationen på detta sätt hjälper oss

• att hålla hashfunktionen oberoende av antalet lagringsnoder
• att hålla associationerna relativa och inte drivna av absoluta kollisioner

Consistent Hashing kräver i genomsnitt att endast k/n enheter av data migreras vid upp- och nedskalning; där k är det totala antalet nycklar och n är antalet noder i systemet.

Ett mycket naivt sätt att genomföra detta är att allokera en matris av samma storlek som Hash Space och placera filer och lagringsnoder bokstavligen i matrisen på den hashade platsen. För att få association itererar vi från objektets hashed location mot höger och hittar den första Storage Node. Om vi når slutet av matrisen och inte hittar någon lagringsnod cirkulerar vi tillbaka till index 0 och fortsätter sökningen. Metoden är mycket enkel att genomföra men lider av följande begränsningar

• kräver stort minne för att hålla en så stor matris

att hitta associationen genom att iterera varje gång till höger är O(hash_space)

Ett bättre sätt att genomföra detta är att använda två matriser: en för att hålla lagringskoderna, kallad nodes, och en annan för att hålla lagringskodernas positioner i hashutrymmet, kallad keys. Det finns en en-till-en-korrespondens mellan de två matriserna – lagringsnoden nodes finns på position keys i hashutrymmet. Båda matriserna hålls sorterade enligt matrisen keys.

Hashfunktion i konsistent hashning

Vi definierar total_slots som storleken på hela detta hashutrymme, vanligen i storleksordningen 2^256, och hashfunktionen skulle kunna implementeras genom att ta SHA-256 följt av en mod total_slots. Eftersom total_slots är enormt stort och en konstant är följande hashfunktionsimplementering oberoende av det faktiska antalet lagringsnoder som finns i systemet och förblir därmed opåverkad av händelser som uppskalningar och nedskalningar.

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

Lägga till en ny nod i systemet

När det finns ett behov av att skala upp och lägga till en ny nod i systemet, i vårt fall en ny lagringsnod, Vi

• finner positionen för noden där den befinner sig i Hash Space
• påfyller den nya noden med data som den ska betjäna
• lägger till noden i Hash Space

När en ny nod läggs till i systemet påverkar det bara de filer som hashasar på platsen till vänster och som är associerade med noden till höger om positionen som den nya noden kommer att passa in. Alla andra filer och associationer förblir opåverkade, vilket minimerar mängden data som måste migreras och mappning som måste ändras.

Från illustrationen ovan ser vi att när en ny nod K läggs till mellan noderna B och E, ändrar vi associationerna för de filer som finns i segmentet B-K och tilldelar dem noden K. De data som tillhör segmentet B-K skulle kunna återfinnas i noden E som de tidigare var associerade med. De enda filer som påverkas och som behöver migreras finns alltså i segmentet B-K, och deras koppling ändras från nod E till nod K.

För att genomföra detta på låg nivå med hjälp av nodes och keys array, får vi först fram positionen för den nya noden i Hash Space med hjälp av hash-funktionen. Därefter hittar vi indexet för den minsta nyckeln som är större än positionen i den sorterade keys arrayen med hjälp av binär sökning. Detta index kommer att vara den plats där nyckeln och den nya lagringsnoden kommer att placeras i keys respektive 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

Ta bort en ny nod från systemet

När det finns ett behov av att skala ner och ta bort en befintlig nod från systemet, Vi

• söker positionen för den nod som ska tas bort från Hash Space
• påfyller noden till höger med data som var associerad med den nod som ska tas bort
• tar bort noden från Hash Space

När en nod tas bort från systemet påverkas endast de filer som är associerade med själva noden. Alla andra filer och associationer förblir opåverkade, vilket minimerar mängden data som ska migreras och mappning som måste ändras.

Från illustrationen ovan ser vi att när noden K tas bort från systemet ändrar vi associationerna av filer som är associerade med noden K till den nod som ligger omedelbart till höger om noden i.De enda filer som påverkas och behöver migreras är de som är associerade med nod K.

För att genomföra detta på en låg nivå med hjälp av nodes och keys array, får vi indexet där nod K ligger i keys array med hjälp av binär sökning. När vi har indexet tar vi bort nyckeln från keys arrayen och Storage Node från nodes arrayen som finns på det indexet.

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

Associera ett objekt till en nod

Nu när vi har sett hur konsekvent hashing hjälper till att hålla datamigrering, under uppskalning och nedskalning, till ett minimum; det är dags att vi ser hur effektivt vi kan hitta ”noden till höger” för ett givet objekt. Operationen för att hitta associationen måste vara supersnabb och effektiv eftersom det är något som kommer att anropas för varje enskild läsning och skrivning som sker i systemet.

För att implementera detta på låg nivå tar vi återigen hjälp av binär sökning och utför denna operation i O(log(n)). Vi skickar först objektet till hashfunktionen och hämtar positionen där objektet är hashat i hashutrymmet. Denna position genomgår sedan en binär sökning i arrayen keys för att erhålla indexet för den första nyckeln som är större än positionen (som erhålls från hashfunktionen). om det inte finns några nycklar som är större än positionen, i arrayen keys, går vi tillbaka och returnerar det 0:e indexet. Indexet som erhålls på detta sätt blir indexet för den lagringsnod i arrayen nodes som är associerad med posten.

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

Källkoden med implementeringen av Consistent Hashing i Python kan hittas på github.com/arpitbbhayani/consistent-hashing.

Slutsats

Consistent Hashing är en av de viktigaste algoritmerna för att hjälpa oss att horisontellt skala och hantera alla distribuerade system. Algoritmen fungerar inte bara i sharded-system utan finner också sin tillämpning i lastbalansering, datapartitionering, hantering av serverbaserade klibbiga sessioner, routningsalgoritmer och många fler. Många databaser har sin skala, prestanda och förmåga att hantera den enorma belastningen att tacka Consistent Hashing för.

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

Andra artiklar som du kanske gillar:

• 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

Den här artikeln publicerades ursprungligen på min blogg – Consistent Hashing.

Om du gillade vad du läste, prenumerera på mitt nyhetsbrev och få inlägget levererat direkt till din inkorg och ge mig ett utropstecken @arpit_bhayani.

.