Konsistent hashing er en hashing-teknik, der fungerer rigtig godt, når den anvendes i et dynamisk miljø, hvor det distribuerede system skaleres op og ned hyppigt. Det centrale koncept for konsistent hashning blev introduceret i artiklen Consistent Hashing and RandomTrees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, men den blev mere populær efter den berømte artikel, der introducerede DynamoDB – Dynamo: Amazon’s Highly Available Key-value Store. Siden da har konsistent hashing vundet indpas og fundet et væld af anvendelsesmuligheder i forbindelse med effektivt design og skalering af distribuerede systemer. De to berømte eksempler på udtømmende brug af denne teknik er Bit Torrent til deres peer-to-peer-netværk og Akamai til deres webcaches. I denne artikel dykker vi dybt ned i behovet for Consistent Hashing, det interne i det, og vigtigere undervejs implementerer vi det ved hjælp af arrays og Binary Search.

Hvor vi hopper ind i den centrale Consistent Hashing-teknik får vi først afklaret et par ting, hvoraf en af dem er Hash-funktioner. Hash-funktioner er alle funktioner, der kortlægger værdi fra et vilkårligt stort domæne til et andet domæne af en fast størrelse, som normalt kaldes Hash Space. F.eks. mapping af URL’er til 32-bit-integriteter eller websiders HTML-indhold til en 256-byte-streng. De værdier, der genereres som output af disse hash-funktioner, bruges typisk som nøgler for at muliggøre effektive opslag i den oprindelige enhed.

Et eksempel på en simpel hash-funktion er en funktion, der kortlægger et 32-bit heltal til et 8-bit heltal i et hash-rum. Funktionen kunne implementeres ved hjælp af den aritmetiske operator modulo, og vi kan opnå dette ved at tage en modulo 256, som giver tal i intervallet , der optager 8-bits til sin repræsentation. En hashfunktion, der kortlægger nøgler til et sådant heltalsområde, anvender oftest modulo N for at begrænse værdierne, eller hashrummet, til et område .

En god hashfunktion har følgende egenskaber

• Funktionen er beregningseffektiv, og de genererede værdier er nemme at slå op
• Funktionen opfører sig, for de fleste generelle anvendelsestilfælde, som en pseudorandumgenerator, der spreder data jævnt uden nogen mærkbar korrelation

Nu har vi set, hvad en hashfunktion er, tager vi et kig på, hvordan vi kan bruge dem og bygge et nogenlunde skalerbart distribueret system.

Opbygning af et distribueret lagringssystem

Sæt, at vi er ved at opbygge et distribueret lagringssystem, hvor brugerne kan uploade filer og få adgang til dem efter behov. Tjenesten udsætter følgende API’er for brugerne

• upload for at uploade filen
• fetch for at hente filen og returnere dens indhold

Hinter kulisserne har systemet Storage Nodes, hvorpå filerne lagres og tilgås. Disse knuder eksponerer funktionerne put_file og fetch_file, der sætter og henter filindholdet til/fra disken og sender svaret til den primære API-server, som igen sender det tilbage til brugeren.

For at opretholde den indledende belastning har systemet 5 Stogare Nodes, som gemmer de uploadede filer på en distribueret måde. Ved at have flere knuder sikres det, at systemet som helhed ikke bliver overbelastet, og at lageret er fordelt næsten jævnt på tværs.

Når brugeren påkalder upload-funktionen med filens sti, skal systemet først identificere den lagerknude, der vil være ansvarlig for at opbevare filen, og det gør vi ved at anvende en hashfunktion på stien og til gengæld få lagerknudeindekset. Når vi har fået lagerknuden, læser vi indholdet af filen og lægger filen på knuden ved at påkalde put_file-funktionen for knuden.

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

Den hashfunktion, der anvendes her, summerer simpelthen bytes og tager modulo med 5 (da der er 5 lagerknuder i systemet) og genererer således output i hashrummet . Denne outputværdi repræsenterer nu indekset for den lagringsmaskine, som vil være ansvarlig for at opbevare filen.

Sig vi har 5 filer “f1.txt”, “f2.txt”, “f3.txt”, “f4.txt”, “f5.txt’, hvis vi anvender hashfunktionen på disse, finder vi ud af, at de er gemt på henholdsvis lagerknudepunkterne E, A, B, C og D.

Det bliver interessant, når systemet får lidt mere fart på, og det skal skaleres til 7 knudepunkter, hvilket betyder, at hashfunktionen nu skal lave mod 7 i stedet for en mod 5. Ændring af hashfunktionen indebærer ændring af mapping og tilknytning af filer med lagerknuder. Vi skal først administrere de nye associationer og se, hvilke filer der skal flyttes fra en knude til en anden.

Med den nye hashfunktion vil de samme 5 filer “f1.txt”, “f2.txt”, “f3.txt”, “f4.txt”, “f4.txt”, “f5.txt” nu være associeret med lagerknudepunkterne D, E, F, G, A. Her kan vi se, at en ændring af hashfunktionen kræver, at vi flytter hver enkelt af de 5 filer til en anden knude.

Hvis vi skal ændre hashfunktionen, hver gang vi skalerer op eller ned, og hvis dette kræver, at vi ikke flytter alle, men blot halvdelen af dataene, bliver processen superdyr og i det lange løb uigennemførlig. Så vi har brug for en måde at minimere den nødvendige databevægelse under op- og nedskaleringer, og det er her, Consistent Hashing passer ind og minimerer den nødvendige dataoverførsel.

Consistent Hashing

Det store smertepunkt ved ovenstående system er, at det er tilbøjeligt til at være udsat for begivenheder som op- og nedskaleringer, da det kræver en masse ændringer i associationerne. Disse foreninger er udelukkende drevet af den underliggende hashfunktion, og hvis vi derfor på en eller anden måde kunne gøre denne hashfunktion uafhængig af antallet af lagringsnoder i systemet, løser vi denne fejl.

Consistent Hashing løser denne situation ved at holde hashrummet enormt og konstant, et sted i størrelsesordenen , og lagringsnoder og objekter både kortlægger til en af pladserne i dette enorme hashrum. I modsætning til det traditionelle system, hvor filen var forbundet med lagerknuden ved det indeks, hvor den blev hashet til, er chancerne for en kollision mellem en fil og en lagerknude i dette system uendeligt små, og derfor har vi brug for en anden måde at definere denne tilknytning på.

I stedet for at bruge en kollisionsbaseret tilgang definerer vi tilknytningen som – filen vil blive forbundet med den lagerknude, der er til stede til umiddelbar højre for dens hashet placering. At definere association på denne måde hjælper os

• at holde hashfunktionen uafhængig af antallet af lagerknuder

at holde associationerne relative og ikke drevet af absolutte kollisioner

Konsistent hashning kræver i gennemsnit kun k/n enheder af data, der skal migreres under op- og nedskalering; hvor k er det samlede antal nøgler, og n er antallet af knuder i systemet.

En meget naiv måde at gennemføre dette på er ved at allokere et array af størrelse svarende til Hash Space og sætte filer og lagerknude bogstaveligt talt i arrayet på den hashede placering. For at få association vi iterere fra elementets hashed placering mod højre og finde den første Storage Node. Hvis vi når til enden af arrayet og ikke finder nogen Storage Node, går vi tilbage til indeks 0 og fortsætter søgningen. Denne fremgangsmåde er meget nem at gennemføre, men lider under følgende begrænsninger

• kræver enorm hukommelse til at rumme et så stort array

at finde association ved at iterere hver gang til højre er O(hash_space)

En bedre måde at gennemføre dette på er ved at bruge to arrays: et til at rumme Storage Nodes, kaldet nodes, og et andet til at rumme Storage Nodes’ positioner i hash-rummet, kaldet keys. Der er en en-til-en-korrespondance mellem de to arrays – lagerknuden nodes er til stede på position keys i hashrummet. Begge arrays holdes sorteret i henhold til arrayet keys.

Hashfunktion i konsistent hashning

Vi definerer total_slots som størrelsen af hele dette hashrum, typisk af størrelsesordenen 2^256, og hashfunktionen kan implementeres ved at tage SHA-256 efterfulgt af en mod total_slots. Da total_slots er enormt stort og en konstant, er den følgende hashfunktionsimplementering uafhængig af det faktiske antal lagringsknuder, der er til stede i systemet, og forbliver derfor upåvirket af begivenheder som op- og nedskaleringer.

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

Tilføjelse af en ny knude i systemet

Når der er behov for at skalere op og tilføje en ny knude i systemet, i vores tilfælde en ny lagringsnode, vi

• finder nodens position, hvor den befinder sig i Hash Space

opfylder den nye node med data, som den skal betjene tilføjer noden i Hash Space

Når en ny node tilføjes i systemet, påvirker det kun de filer, der hasher på placeringen til venstre og er tilknyttet noden til højre for den position, som den nye node skal passe ind i. Alle andre filer og associationer forbliver upåvirket, hvilket minimerer mængden af data, der skal migreres, og den mapping, der skal ændres.

Fra illustrationen ovenfor ser vi, at når en ny knude K tilføjes mellem knudepunkterne B og E, ændrer vi associationerne af de filer, der findes i segmentet B-K, og tildeler dem knudepunkt K. De data, der hører til segmentet B-K, kunne findes på knudepunkt E, som de tidligere var associeret med. Således er de eneste filer, der er berørt, og som skal migreres, i segmentet B-K; og deres tilknytning ændres fra knude E til knude K.

For at gennemføre dette på et lavt niveau ved hjælp af nodes og keys array, får vi først positionen for den nye knude i Hash Space ved hjælp af hash-funktionen. Derefter finder vi indekset for den mindste nøgle, der er større end positionen i det sorterede keys-array ved hjælp af binær søgning. Dette indeks vil være det sted, hvor nøglen og den nye lagerknude vil blive placeret i henholdsvis keys– og 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

Fjernelse af en ny knude fra systemet

Når der er behov for at nedskalere og fjerne en eksisterende knude fra systemet, vi

• finder positionen for den node, der skal fjernes fra Hash Space

opfylder noden til højre med data, der var tilknyttet den node, der skal fjernes

• fjerner noden fra Hash Space

Når en node fjernes fra systemet, påvirker det kun de filer, der er knyttet til selve noden. Alle andre filer og associationer forbliver upåvirket, hvilket minimerer mængden af data, der skal migreres, og den mapping, der skal ændres.

Fra illustrationen ovenfor ser vi, at når node K fjernes fra systemet, ændrer vi associationerne af de filer, der er associeret med node K, til den node, der ligger umiddelbart til højre for den i.Dvs. node E. Således er de eneste filer, der påvirkes og skal migreres, de filer, der er tilknyttet node K.

For at implementere dette på et lavt niveau ved hjælp af nodes og keys array, får vi indekset, hvor node K ligger i keys arrayet ved hjælp af binær søgning. Når vi har indekset, fjerner vi nøglen fra keys arrayet og Storage Node fra nodes arrayet, der er til stede på dette indeks.

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

Tilknyt et element til en node

Nu har vi set, hvordan konsistent hashing hjælper med at holde datamigration, under op- og nedskaleringer, til et absolut minimum; det er på tide, at vi ser, hvordan vi effektivt kan finde den “node til højre” for et givet element. Operationen til at finde forbindelsen skal være super hurtig og effektiv, da det er noget, der vil blive påberåbt for hver eneste læsning og skrivning, der sker på systemet.

For at implementere dette på lavt niveau udnytter vi igen binær søgning og udfører denne operation i O(log(n)). Vi sender først elementet til hash-funktionen og henter den position, hvor elementet er hashet i hash-rummet. Denne position søges derefter binært i arrayet keys for at få indekset for den første nøgle, der er større end positionen (hentet fra hash-funktionen). hvis der ikke er nogen nøgler, der er større end positionen, i arrayet keys, vender vi tilbage og returnerer det 0. indeks. Det således opnåede indeks vil være indekset for lagerknuden i nodes arrayet, der er forbundet 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

Kildekoden med implementeringen af Consistent Hashing i Python kunne findes på github.com/arpitbbhayani/consistent-hashing.

Konklusion

Consistent Hashing er en af de vigtigste algoritmer, der hjælper os med at skalere og administrere ethvert distribueret system horisontalt. Algoritmen fungerer ikke kun i sharded-systemer, men finder også anvendelse i load balancing, datapartitionering, forvaltning af serverbaserede sticky-sessioner, routing-algoritmer og mange flere. Mange databaser skylder deres skala, ydeevne og evne til at håndtere den enorme belastning til Consistent Hashing.

• Hash-funktioner – Wikipedia
• Consistent Hashing – Wikipedia
• Consistent Hashing – Stanford
• Consistent Hashing and RandomTrees

Dynamo: Amazon’s Highly Available Key-value Store

Andre artikler, du måske vil kunne lide:

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

Denne artikel blev oprindeligt offentliggjort på min blog – Consistent Hashing.

Hvis du kunne lide det, du læste, så tilmeld dig mit nyhedsbrev og få indlægget leveret direkte til din indbakke og giv mig et shout-out @arpit_bhayani.