Distributed Hash Table #

Ist ähnlich einer normalen HashMap, die jedoch verteilt auf mehrere Nodes ist. Man könnte damit versuchen einen verteilten Cloud-Storage zu bauen. Ein Produkt dafür ist DynamoDB. Wenn ein neuer Node dazu kommt, sollte nur ein kleiner Teil der Daten verschoben werden und nicht alle. Stichwort dazu ist consistent hashing. Man könnte aber auch einen verteilten Cache bauen. Ein Produkt dafür heisst Memcached.

Das ganze System baut auf einem gemeinsamen Adressraum auf. Alle Objekte und alle Nodes benutzen den gleichen Addressraum und werden logisch in einem Ring angeordnet. Der Node mit dem kleinsten Key k, der grösser oder gleich dem Key des Objektes ist, ist für das Objekt verantwortlich. Das wird auch (consistent hashing) genannt. Im untenstehenden Diagramm wäre der Knoten 4 für alle Objekte von 2 bis inklusive 4 verantwortlich.

Die Tabelle neben dem Ring ist die Finger-Tabelle, die eine logarithmische Zugriffszeit auf alle Nodes sicherstellt.

Diese Hash Tabelle hat aber einige Probleme. Wenn die Nodes, also in der Regel Computer, den Key selber wählen können, kann ein böser User Objekte aus der Hash Tabelle löschen. Es muss nur einen Key gewählt werden, der den bösen User zum Verantwortlichen für diese Objekte macht, wodurch der alte Verantwortliche seine Daten auf den neuen Node überträgt. Ein anderer Angriff führt zur Störung eines Nodes, indem sich der böse User direkt davor platziert, sodass der alte Verantwortliche für keine Objekte mehr zuständig ist. In beiden Fällen können falsche Informationen zurückgeliefert werden.

Die Daten des “successor” und des “predecessor” müssen immer aktuell sein. Ob der “successor” noch aktuell ist, kann mit einem Trick herausgefunden werden. Dabei fragt der Node nach dem “predecessor” des “successor” und wenn dieser grösser als der Node selber aber kleiner als der jetzige “successor” ist, kann der Node ihn als “successor” übernehmen.

Der “predecessor” kann den “successor” über regelmässige Notifikationen aktuell halten. Der “successor” übernimmt ihn, sofern er grösser als der jetzige “predecessor” aber kleiner als der Node selber ist.

Wenn Nodes ungeplant verschwinden, stimmt vielleicht der “successor” nicht mehr. Der betroffene Node muss dann einfach zum nächsten “successor” wechseln indem der betroffene Node nach dem zuständigen Node für das Objekt mit “Node-Key + 1” sucht.