Konsistentes Hashing ist ein Hashing-Verfahren, das in einer dynamischen Umgebung, in der das verteilte System häufig vergrößert und verkleinert wird, sehr gut funktioniert. Das Kernkonzept des konsistenten Hashings wurde in der Arbeit Consistent Hashing and RandomTrees vorgestellt: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web vorgestellt, aber es gewann an Popularität nach dem berühmten Papier zur Einführung von DynamoDB – Dynamo: Amazons hochverfügbarer Key-Value-Speicher. Seitdem hat das konsistente Hashing an Zugkraft gewonnen und eine Vielzahl von Anwendungsfällen bei der effizienten Entwicklung und Skalierung verteilter Systeme gefunden. Zwei berühmte Beispiele, die diese Technik ausgiebig nutzen, sind Bit Torrent für ihre Peer-to-Peer-Netzwerke und Akamai für ihre Web-Caches. In diesem Artikel tauchen wir tief in die Notwendigkeit von Consistent Hashing ein, in die Interna, und – was noch wichtiger ist – wir implementieren es mit Arrays und Binary Search.

Bevor wir uns in die Kerntechnik des Consistent Hashing stürzen, müssen wir zunächst einige Dinge klären, darunter Hash-Funktionen. Hash-Funktionen sind alle Funktionen, die einen Wert aus einem beliebig großen Bereich auf einen anderen Bereich fester Größe abbilden, der üblicherweise als Hash Space bezeichnet wird. So werden beispielsweise URLs auf 32-Bit-Ganzzahlen oder der HTML-Inhalt von Webseiten auf eine 256-Byte-Zeichenkette abgebildet. Die als Ausgabe dieser Hash-Funktionen erzeugten Werte werden in der Regel als Schlüssel verwendet, um eine effiziente Suche nach der ursprünglichen Entität zu ermöglichen.

Ein Beispiel für eine einfache Hash-Funktion ist eine Funktion, die eine 32-Bit-Ganzzahl in einen 8-Bit-Ganzzahl-Hash-Raum abbildet. Die Funktion könnte mit dem arithmetischen Operator modulo implementiert werden, und wir können dies erreichen, indem wir ein modulo 256 nehmen, das Zahlen im Bereich ergibt und 8-Bit für seine Darstellung benötigt. Eine Hash-Funktion, die Schlüssel auf einen solchen ganzzahligen Bereich abbildet, wendet in den meisten Fällen modulo N an, um die Werte oder den Hash-Raum auf einen Bereich zu beschränken.

Eine gute Hash-Funktion hat die folgenden Eigenschaften

• Die Funktion ist rechnerisch effizient und die erzeugten Werte sind leicht nachzuschlagen
• Die Funktion verhält sich für die meisten allgemeinen Anwendungsfälle wie ein Pseudozufallsgenerator, der die Daten gleichmäßig und ohne erkennbare Korrelation verteilt

Nachdem wir nun gesehen haben, was eine Hash-Funktion ist, schauen wir uns an, wie wir sie verwenden und ein einigermaßen skalierbares verteiltes System aufbauen können.

Aufbau eines verteilten Speichersystems

Angenommen, wir bauen ein verteiltes Speichersystem, in dem Benutzer Dateien hochladen und bei Bedarf darauf zugreifen können. Der Dienst stellt den Benutzern die folgenden APIs zur Verfügung

• upload, um die Datei hochzuladen
• fetch, um die Datei abzurufen und ihren Inhalt zurückzugeben

Hinter den Kulissen verfügt das System über Storage Nodes, auf denen die Dateien gespeichert und abgerufen werden. Diese Knoten stellen die Funktionen put_file und fetch_file zur Verfügung, die den Dateiinhalt auf die Festplatte legen bzw. von ihr abrufen und die Antwort an den Haupt-API-Server senden, der sie wiederum an den Benutzer zurücksendet.

Um die anfängliche Last aufrechtzuerhalten, verfügt das System über 5 Stogare-Knoten, die die hochgeladenen Dateien verteilt speichern. Mehrere Knoten sorgen dafür, dass das System als Ganzes nicht überlastet wird und der Speicherplatz nahezu gleichmäßig verteilt ist.

Wenn der Benutzer die Funktion upload mit dem Dateipfad aufruft, muss das System zunächst den Speicherknoten identifizieren, der für die Speicherung der Datei zuständig sein wird, und wir tun dies, indem wir eine Hash-Funktion auf den Pfad anwenden und so den Index des Speicherknotens erhalten. Sobald wir den Speicherknoten erhalten haben, lesen wir den Inhalt der Datei und legen diese Datei auf dem Knoten ab, indem wir die put_file-Funktion des Knotens aufrufen.

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

Die hier verwendete Hash-Funktion summiert einfach die Bytes und nimmt das Modulo durch 5 (da es 5 Speicherknoten im System gibt) und erzeugt so die Ausgabe im Hash-Raum . Dieser Ausgabewert stellt nun den Index des Speichers dar, der für die Datei zuständig ist.

Angenommen wir haben 5 Dateien ‚f1.txt‘, ‚f2.txt‘, ‚f3.txt‘, ‚f4.txt‘, ‚f5.txt‘. Wenn wir die Hash-Funktion auf diese Dateien anwenden, finden wir heraus, dass sie auf den Speicherknoten E, A, B, C und D gespeichert sind.

Die Dinge werden interessant, wenn das System an Zugkraft gewinnt und es auf 7 Knoten skaliert werden muss, was bedeutet, dass die Hash-Funktion jetzt mod 7 statt mod 5 machen sollte. Die Änderung der Hash-Funktion bedeutet eine Änderung der Zuordnung von Dateien zu Speicherknoten. Zunächst müssen wir die neuen Zuordnungen verwalten und sehen, welche Dateien von einem Knoten zu einem anderen verschoben werden müssen.

Mit der neuen Hash-Funktion werden die gleichen 5 Dateien ‚f1.txt‘, ‚f2.txt‘, ‚f3.txt‘, ‚f4.txt‘, ‚f5.txt‘ nun den Speicherknoten D, E, F, G, A zugeordnet. Hier sehen wir, dass wir bei einer Änderung der Hash-Funktion jede einzelne der 5 Dateien auf einen anderen Knoten verschieben müssen.

Wenn wir die Hash-Funktion bei jeder Vergrößerung oder Verkleinerung ändern müssen und dies erfordert, dass wir nicht alle, sondern nur die Hälfte der Daten verschieben müssen, wird der Prozess sehr teuer und auf lange Sicht nicht durchführbar. Wir brauchen also einen Weg, um die Datenbewegungen zu minimieren, die bei einer Vergrößerung oder Verkleinerung erforderlich sind, und hier kommt das konsistente Hashing ins Spiel, das den erforderlichen Datentransfer minimiert.

Konsistentes Hashing

Der Hauptkritikpunkt des obigen Systems ist, dass es anfällig für Ereignisse wie Vergrößerungen und Verkleinerungen ist, da es eine Menge Änderungen in den Assoziationen erfordert. Diese Assoziationen werden ausschließlich durch die zugrundeliegende Hash-Funktion gesteuert, und wenn wir diese Hash-Funktion irgendwie unabhängig von der Anzahl der Speicherknoten im System machen könnten, würden wir diesen Fehler beheben.

Consistent Hashing löst diese Situation, indem es den Hash-Space groß und konstant hält, irgendwo in der Größenordnung von , und sowohl der Speicherknoten als auch die Objekte auf einen der Slots in diesem riesigen Hash-Space abbildet. Im Gegensatz zum traditionellen System, bei dem die Datei mit dem Speicherknoten an dem Index assoziiert wurde, an dem sie gehasht wurde, ist in diesem System die Wahrscheinlichkeit einer Kollision zwischen einer Datei und einem Speicherknoten verschwindend gering, und daher brauchen wir einen anderen Weg, um diese Assoziation zu definieren.

Anstatt einen kollisionsbasierten Ansatz zu verwenden, definieren wir die Assoziation als – die Datei wird mit dem Speicherknoten assoziiert, der sich unmittelbar rechts von ihrer Hash-Position befindet. Diese Definition der Assoziation hilft uns

• die Hash-Funktion unabhängig von der Anzahl der Speicherknoten zu halten
• die Assoziationen relativ zu halten und nicht von absoluten Kollisionen abhängig zu machen

Das konsistente Hashing erfordert im Durchschnitt nur k/n Dateneinheiten, die während des Skalierens nach oben und unten migriert werden; wobei k die Gesamtzahl der Schlüssel und n die Anzahl der Knoten im System ist.

Eine sehr naive Art und Weise, dies zu implementieren, ist die Zuweisung eines Arrays mit der Größe des Hash-Spaces und die buchstäbliche Platzierung von Dateien und Speicherknoten im Array an der Hash-Position. Um eine Zuordnung zu erhalten, iterieren wir von der Hash-Position des Elements nach rechts und suchen den ersten Storage Node. Wenn wir das Ende des Arrays erreichen und keinen Storage Node finden, kehren wir zum Index 0 zurück und setzen die Suche fort. Der Ansatz ist sehr einfach zu implementieren, leidet aber unter den folgenden Einschränkungen

• erfordert riesigen Speicher, um ein so großes Array zu halten
• Die Assoziation zu finden, indem man jedes Mal nach rechts iteriert, ist O(hash_space)

Eine bessere Möglichkeit, dies zu implementieren, ist die Verwendung von zwei Arrays: eines für die Speicherknoten, genannt nodes, und ein weiteres für die Positionen der Speicherknoten im Hashspace, genannt keys. Es besteht eine Eins-zu-Eins-Entsprechung zwischen den beiden Arrays – der Speicherknoten nodes befindet sich an der Position keys im Hash Space. Beide Arrays werden gemäß dem Array keys sortiert gehalten.

Hash-Funktion im Consistent Hashing

Wir definieren total_slots als die Größe dieses gesamten Hash-Spaces, typischerweise in der Größenordnung 2^256, und die Hash-Funktion könnte durch SHA-256, gefolgt von einem mod total_slots, implementiert werden. Da total_slots sehr groß und eine Konstante ist, ist die folgende Implementierung der Hash-Funktion unabhängig von der tatsächlichen Anzahl der im System vorhandenen Speicherknoten und bleibt daher von Ereignissen wie Scale-ups und Scale-downs unbeeinflusst.

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

Hinzufügen eines neuen Knotens im System

Wenn es notwendig ist, das System zu vergrößern und einen neuen Knoten hinzuzufügen, in unserem Fall einen neuen Speicherknoten, finden wir

• die Position des Knotens, an der er sich im Hash Space befindet
• den neuen Knoten mit Daten füllen, die er bedienen soll
• den Knoten in den Hash Space einfügen

Wenn ein neuer Knoten im System hinzugefügt wird, wirkt sich das nur auf die Dateien aus, die sich an der Stelle links vom Hash Space befinden und mit dem Knoten rechts von der Position verbunden sind, in die der neue Knoten passen wird. Alle anderen Dateien und Verknüpfungen bleiben unberührt, wodurch die Menge der zu migrierenden Daten und der zu ändernden Zuordnungen minimiert wird.

Aus der obigen Abbildung geht hervor, dass wir beim Hinzufügen eines neuen Knotens K zwischen den Knoten B und E die Zuordnungen der im Segment B-K vorhandenen Dateien ändern und sie dem Knoten K zuordnen. Die einzigen betroffenen Dateien, die migriert werden müssen, befinden sich also im Segment B-K, und ihre Zuordnung ändert sich von Knoten E zu Knoten K.

Um dies auf niedriger Ebene mit Hilfe des Arrays nodes und keys zu implementieren, ermitteln wir zunächst die Position des neuen Knotens im Hash Space mithilfe der Hash-Funktion. Dann wird der Index des kleinsten Schlüssels, der größer ist als die Position im sortierten Array keys, mit Hilfe der binären Suche ermittelt. Dieser Index ist der Ort, an dem der Schlüssel und der neue Speicherknoten im Array keys bzw. nodes platziert werden.

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

Entfernen eines neuen Knotens aus dem System

Wenn ein vorhandener Knoten verkleinert und aus dem System entfernt werden muss, Wir

• finden die Position des Knotens, der aus dem Hash Space entfernt werden soll
• füllen den Knoten auf der rechten Seite mit Daten, die mit dem zu entfernenden Knoten verbunden waren
• entfernen den Knoten aus dem Hash Space

Wenn ein Knoten aus dem System entfernt wird, sind nur die mit dem Knoten selbst verbundenen Dateien betroffen. Alle anderen Dateien und Assoziationen bleiben unberührt, wodurch die zu migrierende Datenmenge und die zu ändernde Zuordnung minimiert werden.

Aus der obigen Abbildung geht hervor, dass wir, wenn der Knoten K aus dem System entfernt wird, die Assoziationen der Dateien, die mit dem Knoten K assoziiert sind, auf den Knoten ändern, der unmittelbar rechts von ihm liegt, d. h. den Knoten E.Die einzigen Dateien, die davon betroffen sind und migriert werden müssen, sind diejenigen, die mit dem Knoten K verbunden sind.

Um dies auf einer niedrigen Ebene mit dem nodes– und keys-Array zu implementieren, ermitteln wir den Index, in dem der Knoten K im keys-Array liegt, mithilfe der binären Suche. Sobald wir den Index haben, entfernen wir den Schlüssel aus dem keys-Array und den Speicherknoten aus dem nodes-Array, der auf diesem Index vorhanden ist.

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

Assoziieren eines Elements mit einem Knoten

Nachdem wir nun gesehen haben, wie konsistentes Hashing dazu beiträgt, die Datenmigration bei Scale-ups und Scale-downs auf ein Minimum zu beschränken, ist es an der Zeit zu sehen, wie wir effizient den „richtigen Knoten“ für ein bestimmtes Element finden können. Die Operation zum Auffinden der Assoziation muss superschnell und effizient sein, da sie bei jedem einzelnen Lese- und Schreibvorgang im System aufgerufen wird.

Um dies auf niedriger Ebene zu implementieren, nutzen wir wieder die binäre Suche und führen diese Operation in O(log(n)) aus. Zuerst übergeben wir das Element an die Hash-Funktion und holen die Position, an der das Element im Hash-Raum gehasht ist. Diese Position wird dann im Array keys binär durchsucht, um den Index des ersten Schlüssels zu erhalten, der größer ist als die Position (erhalten von der Hash-Funktion). Wenn es im Array keys keine Schlüssel gibt, die größer sind als die Position, gehen wir zurück und geben den 0. Der so erhaltene Index ist der Index des Speicherknotens im nodes Array, der mit dem Element verknüpft ist.

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

Der Quellcode mit der Implementierung von Consistent Hashing in Python kann unter github.com/arpitbbhayani/consistent-hashing gefunden werden.

Fazit

Consistent Hashing ist einer der wichtigsten Algorithmen, der uns bei der horizontalen Skalierung und Verwaltung jedes verteilten Systems hilft. Der Algorithmus funktioniert nicht nur in Sharded-Systemen, sondern findet auch Anwendung im Load Balancing, der Datenpartitionierung, der Verwaltung von serverbasierten Sticky Sessions, Routing-Algorithmen und vielem mehr. Viele Datenbanken verdanken ihre Skalierbarkeit, Leistung und Fähigkeit, die enorme Last zu bewältigen, dem Consistent Hashing.

• Hash-Funktionen – Wikipedia
• Consistent Hashing – Wikipedia
• Consistent Hashing – Stanford
• Consistent Hashing and RandomTrees
• Dynamo: Amazons hochverfügbarer Key-Value-Speicher

Weitere Artikel, die Ihnen gefallen könnten:

• 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

Dieser Artikel wurde ursprünglich auf meinem Blog – Consistent Hashing veröffentlicht.

Wenn Ihnen gefallen hat, was Sie gelesen haben, abonnieren Sie meinen Newsletter und erhalten Sie den Beitrag direkt in Ihren Posteingang und geben Sie mir ein Shout-out @arpit_bhayani.