Große verteilte Dateisysteme benötigten traditionell Metadaten, die angaben, wo jeder Block oder jedes Objekt lag. In Petabyte-Größenordnung wurden diese Zuordnungskarten zu Problemen bei Koordination, Wiederherstellung und Neuverteilung.
Cephs Antwort war CRUSH: eine pseudozufällige Platzierungsfunktion. Clients und Speicherknoten konnten den Ort eines Objekts aus dem Objektnamen und der Cluster-Karte berechnen, statt eine zentrale Tabelle zu fragen.
Das OSDI-Papier berichtete, dass Ceph mehr als 250.000 Metadatenoperationen pro Sekunde unterstützte, und die CRUSH-Veröffentlichung beschrieb den Algorithmus für Zehntausende oder Hunderttausende von Speichergeräten, ohne ein zentrales Verzeichnis zu benötigen.
Die Platzierung in eine Funktion verwandeln
Eine deterministische Platzierungsfunktion ermöglicht es jedem Teilnehmer, dasselbe Objekt unabhängig zu finden.
Gewichte und Regeln für Fehlerdomänen wahren reale Einschränkungen wie Racks und Gerätegrößen.
Kleine Topologieänderungen verschieben nur die Daten, die verschoben werden müssen, wodurch Wachstum und Ausfälle weniger störend wirken.
Der Wegfall von Zuordnungslisten reduziert die Aufgabe des Metadatenservers auf den Namensraum, nicht auf die Adresse jedes einzelnen Bytes.
In extremer Größenordnung kann das Beseitigen von Koordination wichtiger sein als deren Optimierung; eine gemeinsame deterministische Funktion kann ein gemeinsames veränderliches Verzeichnis ersetzen.
CRUSH wurde zu einer der prägenden Ideen von Ceph und trug dazu bei, das Projekt zu einem dauerhaften Open-Source-Speichersystem zu machen. Seine Schönheit ist architektonischer Natur: Das beste Verzeichnis in Petabyte-Größenordnung war gar kein Verzeichnis.
DEN BELEGEN FOLGEN
Die Quellen
- CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data Storage Systems Research Center, UC Santa Cruz · ssrc.us
- Ceph: A Scalable, High-Performance Distributed File System USENIX · usenix.org ·