Consistent-Hashing

Consistent-Hashing-Funktionen stellen eine Flexibilisierung der bislang üblichen HASH-Funktionen dar und sind ein zentrales Konzept von NoSQL-Systemen, deren Speicherplätze sehr dynamischen Entwicklungen unterliegen. Grundidee ist, dass sich der Speicherplatz einer NoSQL-DB auf einem Servernetz mit mehreren hundert, mehreren tausend Servern verteilt wird. Dabei bestehen die Server aus einer einfacheren Hardware. Das System ist in der Lage, Serverzugänge, wie auch Serverausfälle zu kompensieren, ohne dass der laufende Betreib gestört wird. Und genau damit ergeben sich zwei Probleme, die mit den einfachen und starren HASH-Funktionen nicht gelöst werden können.

  • Die "einfachen" HASH-Funktionen transformieren die Schlüsselwerte in eine feste Anzahl an Speicheradressen der Zielmenge. Serverzugänge, wie auch Serverausfälle führen aber dazu, dass die Anzahl der Speicherplätze und damit die Größe der Zielmenge quasi ständig Änderungen unterliegt, also höchst dynamisch wird.
  • Die Server bestehen aus sehr unterschiedlichen Systemen mit sehr verschiedenen Kapazitäten und es ist wünschenswert, dass ein Server mit viel Speicherplatz auch mit mehr Datensätzen ausgelastet wird, während ein kleinerer Server nicht mit dieser Datenmenge überlastet werden darf.

Beispiel für die Probleme einer "einfachen" Hash-Funktion:

Ein Serververbund mit 3 Servern verteilt die Datensätze 3-9 mittels Modulo-3-Funktion auf die zu speichernden Serverknoten.

  • Fällt Server 3 aus, so muss nun mit Modulo 2 gearbeitet werden. Der Austausch der Funktion ist aber nur das kleinere Problem. Die neue Funktion hat die Eigenschaft, dass für alle Datensätze neue Speicherplätze berechnet werden. Der Datensatz mit dem Schlüsselwert 5 wird bei Modulo-3 auf dem Server 2 gespeichert, bei Modulo-2 auf dem Server 1. Dieser Datensatz und alle anderen werden umgespeichert, obwohl sie überhaupt nichts mit dem ausgefallenen Server 3 zu tun haben. Wünschenswert ist es, hier nur die Datensätze vom ausgefallenen Server aus die übriggebliebenen Knoten zu verteilen.
  • Kommt hingegen ein neuer Server hinzu, so muss nun mit Modulo 4 gearbeitet werden und es treten analoge Probleme auf: Austausch der Funktion, Umspeichern von allen Datensätzen, wobei es wünschenswert ist, dass z.B. nur von benachbarten Servern Daten zu den neuen Servern übertragen werden.
  • Mit der Modulo-3-Funktion werden allen Serverknoten jeweils ein Drittel der Datensätze zugewiesen. Verfügt aber der Server 2 über doppelt so viel Speicherplatz wie Server 1, so ist Server 1 entweder überlastet mit dieser Datensatzmenge oder Server 2 ist überhaupt nicht ausgelastet. Es ist wünschenswert, dass Server 2 dann auch mit der doppelten Datensatzmenge belastet wird.
Consistent Hashing im Serververbund
Consistent-Hashing-Verfahren

Funktionsweise:

  • Der Wertebereich der Zielmenge wird nicht als Liste sondern als Ring verstanden. Es werden die beiden Enden zusammengefügt.
  • Die Server 1-n werden gemäß des Hash-Wertes ihrer IDs (Servernamen, IP-Adressen, ...) auf diesem Adressring angeordnet.
  • Die Datensätze werden gemäß ihres Hash-Wertes auf dem Adressring angeordnent. Die Datensätze werden auf den Servern gespeichert, die im Uhrzeigersinn auf dem Adressring nachfolgend angeordnet sind.
  • Wird ein neuer Server zugefügt, so wird er gemäß seinem Hash-Wert auf dem Ring angeordnet. Die Datensätze, deren Adressen nun im Uhrzeigersinn vor dem neuen Server liegen, werden vom ursprünglichen Server auf den neuen umgespeichert. Alle anderen Datensätze sind nicht betroffen von dieser Erweiterung.
  • Wird ein Server herausgenommen, dann werden seine Daten auf den ihm im Uhrzeigersinn nachfolgenden Server kopiert. Alle anderen Datensätze sind nicht betroffen von dieser Veränderung.
  • Verfügt ein Server über mehr Kapazitäten (z.B. mehr Speicher, schnellere CPU,...), so können für ihn entsprechend viele virtuelle Server erzeugt werden. Diese virtuellen Server unterscheiden sich in der ID, zB. Server n1, Server n2, Server n3 und damit werden für jeden dieser virtuellen Server andere Hash-Werte ermittelt und damit auch unterschiedlich auf dem Adressring platziert. Auf den realen Server werden dann alle Daten kopiert, deren Adressen vor den zugehörigen virtuellen Servern auf dem Ring angeordnet sind.

Beispiel für Consistent-Hashing:

Ein Serververbund mit 3 Servern verteilt die Datensätze 3-9 mittels Consistent-Hashing auf die zu speichernden Serverknoten. (Abb. "Adressring mit Servern und Datensätzen")

  • Fällt Server 3 aus, so werden nur der Datensatz 3 umgespeichert auf den Server 1. (Abb. "Entfernen eines Servers")
  • Kommen nun ein neuer Server hinzu, hier Server 3, dann wird der Datensatz 9 umgespeichert. (Abb. "Einfügen eines neuen Servers")
  • Aufgrund der des doppelten Speicherplatzes bei Server 2 werden zwei virtuelle Server mit den Speicherplatzadressen 2-1 und 2-2 in den Adressraum aufgenommen und gemäß ihrem Hash-Wert auf dem Adressring angeordnet. Und damit wird der Server 2 mit der doppelten Datenmenge belastet wie die übrigen Server. (Abb. "virtuelle Server zur Lastverteilung")

Quellen:

  • DeCandia, G., Hastorun, D., Jampani, M., et al.: "Dynamo: Amazon's highly available Key-Value-Store", SIGOPS Operating Systems Rev. New York, New York, USA, 2007, Stand 20.05.2011
  • Edlich, Friedland, Hampe, Brauer: „NoSQL – Einstieg in die Welt der nichtrelationalen Web2.0- Anwendungen“, Hanser-Verlag, 2010, ISBN 978-3-446-42355-8
  • Karger, D., Lehman, E., Leighton, T., et al.: "Consistent Hashing and Random Trees: Distributed Cashing Protocols for Relieving Hot Spots on the World Wide Web", STOC'97, Proceceedings of the zwenty-nine anual ACM Symposium on Theory of Computing, El Paso, Texas, USA, 1997

Weiterführende Literatur:

  • Frey, M.: „Etablierte Datenmodelle der NoSQL-Familie und ihre spezifischen Eigenschaften im Kontext von Cloud-Datenbanken“, Bachelorarbeit, FH Köln, Institut für Informatik, 08/2010
  • Kossmann, D., Kraska T.: „Data Management in the Cloud: Promises, State- of-the-art and Open Questions“, in „Datenbanken und Cloud-Computing“, Datenbank Spektrum, Band 10 Heft 3, Springer-Verlag, 12.2010, S. 121-129

Weiterführende Links:

Kategorie: Neue DB-Entwicklungen, Grundlagen, NoSQL, C