Datenbanken Online Lexikon TH Köln, Campus Gummersbach
Aktuelle Änderungen - Suchen:

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