Diaspora

Inhaltsverzeichnis

Braucht eine Anwendung schnellen Zugriff auf gespeicherte Daten, bieten Hash-Tabellen im Gegensatz zu Bäumen oder Listen erhebliche Vorteile. Finden keine Kollisionen statt, genügt ein einziger Schlüsselvergleich, während die Suchzeit bei Bäumen bestenfalls logarithmisch und bei Listen linear mit der Zahl der Einträge wächst. Je mehr Datensätze zu verwalten sind, desto eher lohnt sich Hashing.

Allerdings gelangt man bei wachsender Datenmenge unweigerlich an den Punkt, wo die Daten nicht mehr in den Hauptspeicher passen und man sie auf Massenspeicher auslagern muss, was die Zugriffe wieder verlangsamt – und zwar erheblich. Ein extremes Beispiel ist die Datendeduplizierung, bei der man Terabytes oder sogar Petabytes in Milliarden kleiner Stücke („Chunks“) zerlegt und diese unter ihrem Hash-Wert ablegt. Selbst wenn man nur die Schlüssel und Verweise auf die Daten im RAM hält, bleiben pro Chunk etwa 20 bis 30 Byte übrig.

Verteilt rechnen, verteilt speichern

In verteilten Systemen kommt erschwerend hinzu, dass ein Rechner alle Zugriffe auf die Hash-Tabelle durchführen muss. Linderung in beiden Fällen verschaffen verteilte Hash-Tabellen (Distributed Hash Tables, kurz DHT). Deren Vorteil besteht darin, dass jeder der beteiligten Rechner nur einen Teil der Datensätze speichert (siehe iX-Link [a]). Das lässt sich durch Partitionieren des Schlüsselraums (Key Space) relativ einfach erreichen, etwa indem man die möglichen Schlüssel nach einem bestimmten Schema den einzelnen Rechnern zuweist. Nach diesem Prinzip arbeitet unter anderem der Caching-Server memcached [b].

Allerdings bietet der weder persistenten Speicher – der bei einem Cache ohnehin sinnlos wäre – noch Schutz gegen den Ausfall von Storage-Knoten. Beide Lücken füllt die „NoSQL“-Datenbank Couchbase (vormals Membase) [c], die dasselbe Netzprotokoll verwendet und sich daher mit allen memcached-Clients versteht – nicht zu verwechseln mit Apaches dokumentenorientierter Datenbank CouchDB [1]. Couchbase schreibt Änderungen am Datenbestand im Hintergrund auf die Platte. Zum Schutz gegen den Ausfall einzelner Server lassen sich die Daten im Cluster mehrfach speichern. Quasi nebenbei kann Couchbase die Aufgaben von memcached mit übernehmen.

Mit zunehmender Verbreitung von P2P-Netzen wuchs auch das akademische Interesse an DHTs, insbesondere an den zugrunde liegenden Netzstrukturen – sogenannten Overlay Networks [d] –, Routing-Protokollen (Key-based Routing, kurz KBR) und Mechanismen zum Erhöhen der Verfügbarkeit. Innerhalb kurzer Zeit entstanden vier Vorschläge: das Content Addressable Network (CAN) [e], Chord [f], Pastry [g] und Tapestry beziehungsweise dessen Nachfolger Chimera [h]. Für Chord, Pastry und Chimera ist Quellcode verfügbar, der offenbar jedoch seit einigen Jahren nicht mehr weiterentwickelt wird. Das häufig referenzierte Bamboo [i] hatte ebenfalls bereits 2006 seine letzte offizielle Release.

P2P-Netze als Motor der Entwicklung

Aktuellere Implementierungen in diversen Sprachen gibt es hingegen für Kademlia [j, k]. Jeder Rechner in einem Kademlia-Cluster ist für die Datensätze verantwortlich, deren Schlüssel seiner eigenen ID am „nächsten“ liegen. Zur Berechnung der „Entfernung“ zweier Schlüssel dient eine simple XOR-Funktion, was das Routing im baumförmigen Overlay-Netz erheblich vereinfacht. Replikation der Key-Value-Paare und ein interner Balancing-Mechanismus verhindern, dass beim Wegfall eines Knotens – was in P2P-Netzen ständig vorkommt – Daten verloren gehen.

Ebenfalls noch aktiv sind die Entwickler von Voldemort [l]. Der in Java geschriebene Key-Value-Store zielt im Gegensatz zu Kademlia weniger auf P2P-Anwendungen als auf allgemeine Datenspeicherung, bei der die Wahrscheinlichkeit eines Rechnerausfalls geringer ist. Der Einsatz einer sogenannten konsistenten Hash-Funktion [m] gewährleistet, dass der Cluster beim Ausfall eines Knotens dessen Daten mit einem Minimum an Datentransporten über die verbleibenden Knoten repliziert. Kommt ein neuer Rechner zum Cluster hinzu, läuft der Vorgang umgekehrt ab, sodass die Daten stets gleichmäßig über die Knoten verteilt sind. Als Datenbank-Backend verwendet Voldemort die Berkeley DB Java Edition, alternativ kann der Nutzer MySQL, die „Read-Only Storage Engine“ des Projekts oder einen Eigenbau einsetzen. Für Tests von Anwendungen lässt sich der zugrunde liegende Storage-Layer im RAM emulieren.

Nicht verschwiegen bleiben sollte allerdings die Tatsache, dass DHTs wie alle verteilten Speichersysteme dem CAP-Theorem unterliegen. Es besagt, dass sich von den drei Anforderungen Konsistenz (Consistency), Verfügbarkeit (Availability) und Partitionstoleranz nur maximal zwei erfüllen lassen [2].

Literatur

[1] Rudolf Jansen; NoSQL; Emporkömmlinge; NoSQL – Alternative zu relationalen Datenbanken; iX Developer 1/2011, S. 132

[2] Martin Scholl; Verteiltes Speichern; Weit entrückt; Was Cloud Storage von klassischem Storage unterscheidet; iX 3/2012, S. 46

Alle Links: www.ix.de/ix1204157 (mr)