Stellen Sie sich folgendes Szenario vor: Sie betreiben eine Webapplikation, die noch relativ jung ist, aber die Userzahlen explodieren und vor allem die Datenbank hinter der Anwendung ächzt schon unter der Last – vor allem der vieler Lesezugriffe. Die Lösung für dieses Problem ist allgemein bekannt: Caching.
Doch damit die Caching-Architektur horizontal skalieren kann, müssen gleich mehrere Server die Last übernehmen. Damit besteht ein neues Problem darin, wie man am besten die Daten speichert, so dass sie sich auf beide Nodes gleichmäßig verteilt speichern lassen. Eine clevere Lösung möchte ich Ihnen hier mit auf den Weg geben.
Ein naiver Ansatz
Die einfachste, aber auch sehr naive Lösung für das Problem lautet wie folgt:
HASH(key) % N
Das heißt, wir wenden auf jeden Key eines zu speichernden Datensatzes eine Hash-Funktion an, die möglichst gleichmäßig verteilte Hashes generiert und verteilen diese dann mittels Modulo über die Anzahl der verfügbaren Server auf die Nodes. Als Hash-Funktion bieten sich dabei schnelle Algorithmen wie MD5 oder CRC32 an, da der wichtigste Aspekt in diesem Schritt nicht Sicherheit sondern gleichmäßige Verteilung ist; Hashkollisionen spielen dabei keine Rolle.
Experimentiert man damit ein bisschen, funktioniert das schnell sehr gut und die Daten werden gleich auf die verfügbaren Server verteilt. Doch was passiert, wenn ein Server ausfällt oder ein neuer Server hinzugefügt werden muss, weil beispielsweise die Kapazität der verfügbaren nicht mehr ausreicht? Bis zu 90 Prozent der gespeicherten Keys müssten neu aufgeteilt werden, d.h. nicht nur auf die des ausgefallenen Servers sondern auch auf noch im Betrieb befindlichen Server!
Die Lösung: Consistent Hashing
Hier kommt der Consistent-Hashing-Algorithmus ins Spiel, denn er verringert diese Neuverteilung auf ein Mindestmaß. So bleibt das Caching performant, auch bei Ausfall eines oder mehrerer Server.
Dabei funktioniert das Prinzip ganz simpel und lässt sich einfach grafisch veranschaulichen. Zuerst einmal erstellen wir einen leeren Ring (natürlich virtuell), der später sowohl die Daten als auch die Nodes enthalten wird.
Im zweiten Schritt fügen wir initial sämtliche verfügbaren Nodes hinzu, im Beispiel sind das die Server A, B und C. Die Anordnung kommt dabei durch das Hashing zustande. Server C bekommt einen kleineren Hash und liegt damit auf dem Ring vor B.
In der Praxis werden für jeden Server weitere virtuelle Punkte auf dem Ring erstellt, um die Daten noch gleichmäßiger verteilen zu können. Ein guter Richtwert ist es, drei virtuelle Punkte je Node zu verwenden.
Nun werden nach dem selben Prinzip die Daten gehashed (hier die ersten 7 Stellen eines SHA1) und auf dem Ring angeordnet.
Was noch fehlt, ist die eigentliche Zuordnung der Daten zu den Nodes. Für diesen Schritt wurden die Daten eigentlich auf dem Ring angeordnet, denn jetzt ist es sehr einfach, sie gegen den Uhrzeigersinn dem zuständigen Node zuzuordnen.
Auch redundante Writes lassen sich sehr leicht realisieren, in dem man den Ring weiter in die selbe Richtung verfolgt und nicht nur den nächsten, sondern auch den übernächsten Node zum Schreiben sucht. Fällt nun der erste Node aus, so wird automatisch ein Fallback auf den nächsten Node im Ring versucht.
Anwendungsgebiete
Das wichtigste Anwendungsgebiet des Consistent-Hashing-Algorithmus ist sicherlich das Distributed Caching. Beispielsweise gibt es eine Implementierung für Memcache von Last.fm (libketama) und auch Amazons Dynamo verwendet intern diesen Algorithmus.
Implementierungen
Es gibt von mir eine Implementierung in Ruby als Gem (consistent-hashing), die alle Nodes intern in einem AVL Tree speichert und so auch bei einer hohen Anzahl von virtuellen Nodes performant bleibt.
Auch für PHP gibt es einige nennenswerte Implementierungen, z.B. chash, eine in C geschriebene Extension. Daneben existiert auch noch eine Userland-Implementierung namens flexihash, für die auch ein Symfony2 Bundle geschrieben wurde, die den Algorithmus als Service innerhalb einer SF2-Anwendung zur Verfügung stellt.
Schreibe einen Kommentar