- Key-Value-Datenstrukturen sind ein zentraler Bestandteil datengetriebener Systeme; je nach Workload und Hardwarebedingungen können sich große Leistungsunterschiede ergeben
- Die physische Struktur gliedert sich in Datenlayout, Metadaten für die Suche sowie Algorithmen zum Speichern und Abrufen; sie wird auch als Access Methods, Datencontainer oder Suchstruktur bezeichnet
- Workloads lassen sich als Kombination aus Point Queries, Range Queries, Einfügen, Löschen und Ändern ausdrücken; auch Kapazität und Kosten von Arbeitsspeicher und persistentem Speicher werden zu Designanforderungen
- B+-trees sind stark bei Lesezugriffen und Range Queries, doch bei mehr Einfügungen und Änderungen wird die Reorganisation von Leaf Nodes zur Belastung; LSM-trees verarbeiten viele Einfügungen durch Buffering und Merging
- In Umgebungen, in denen Datenbewegung zum Engpass wird, müssen passend zu neuen Anwendungen, Hardwareveränderungen und wachsendem Datenvolumen bestehende Strukturen ausgewählt oder neue entworfen werden
Welche Probleme Key-Value-Datenstrukturen lösen
- Key-Value-Datenstrukturen werden in datenintensiven Anwendungen breit eingesetzt und bilden wegen der Vielseitigkeit des Key-Value-Modells die Grundlage vieler Systeme
- Ein Schlüssel wird auf genau einen Wert abgebildet, derselbe Wert kann jedoch mit mehreren Schlüsseln verknüpft sein
- Die Bedeutung eines Werts hängt von der Anwendung ab
- Er kann ein Datensatz in einer relationalen Datenbank sein
- Er kann ein Pandas DataFrame sein
- Er kann eine Menge von Feldern sein, die eine Anwendung in einem NoSQL-System parst und verwendet
- In Systemen für Social-Network-Daten kann er Verweise auf große Objekte wie Bilder oder Videos enthalten
Physischer Aufbau und Anwendungsbereich
- Physisch besteht eine Key-Value-Datenstruktur aus drei Elementen
- Daten, die in einem bestimmten Layout gespeichert sind
- optionale Metadaten, die beim Durchsuchen der Daten helfen
- Algorithmen, die Speicher- und Suchoperationen unterstützen
- Datenstrukturen werden in Datensystemen, Betriebssystemen, Dateisystemen, Compilern und Netzwerksystemen in vielfältigen Formen eingesetzt
- Die Beispiele des Buchs konzentrieren sich vor allem auf großvolumige Datensysteme und sekundäre Speichermedien, doch die Analyse- und Designmethoden gelten auch für In-Memory-Systeme
- Diese Analyse ist auf Umgebungen mit mindestens zwei Ebenen in der Speicher- und Storage-Hierarchie ausgerichtet
Workload und Kosten bestimmen das Design
- Eine Anwendung oder ein Workload lässt sich als Kombination von Key-Value-Operationen darstellen
-
Point Query
-
Range Query
- Einfügen
- Löschen
- Ändern
- Auch benötigte Kapazität und Kosten von Arbeitsspeicher und persistentem Speicher gehören zu den Anforderungen einer Anwendung
- Je nach Systemtyp unterscheiden sich die Datenstrukturen, die optimiert werden müssen
- Dateisysteme verwalten Dateimetadaten und Inhalte mit Datenstrukturen, die für häufige Updates optimiert sind
- Compiler verwalten Variablen während ihrer Lebensdauer in einer Hash Map und stellen die Gesamtform eines Programms als Abstract Syntax Tree dar
- Netzwerkgeräte benötigen spezialisierte Datenstrukturen, um Routingtabellen effizient zu speichern und darauf zuzugreifen
-
Die gegensätzlichen Entscheidungen bei B+-tree und LSM-tree
- B+-trees werden häufig verwendet, um bei Workloads mit wenigen Einfügungen und Updates, aber vielen Point und Range Queries Lese- und Schreibkosten auszubalancieren
- Ein hoher Node-Fanout reduziert die Zahl der Zugriffe auf sekundären Speicher beim Weg von der Root bis zum Leaf; höhere Ebenen werden in schnelleren Speicherschichten gecacht
- Sie halten alle Schlüssel sortiert in Leaf Nodes und verbinden die Leaf Nodes als Linked List, um Range Queries zu unterstützen
- Wenn Einfügungen und Updates zunehmen, werden Reorganisation oder Splits von Leaf Nodes nötig, was zum Performance-Engpass werden kann
- LSM-trees verwenden für Workloads mit vielen Einfügungen einen anderen Ansatz
- Alle Updates werden in einen gemeinsamen Speicherpuffer geschrieben
- Wenn der Puffer voll ist, wird er auf die Disk geflusht
- Wenn sich Puffer ansammeln, werden sie zu größeren sortierten Datensammlungen zusammengeführt
- Änderungen werden mit einer Out-of-Place-Policy verarbeitet; Key-Value-Paare mit demselben Schlüssel können innerhalb der Struktur mehrfach vorhanden sein
- Den aktuellen Wert eines bestimmten Schlüssels enthält das zuletzt eingefügte Key-Value-Paar
Adaptive Datenstrukturen
- Neben dem Ansatz, Datenstrukturen auf Basis eines vorab erwarteten Workloads zu entwerfen, werden auch Datenstrukturen behandelt, die sich während der Ausführung schrittweise einer idealen Form annähern
- B+-trees und LSM-trees im ursprünglichen Design erzwingen eine Sortierreihenfolge in diskresidenten Nodes, um alle Point oder Range Queries beantworten zu können
- Adaptive Datenstrukturen können mit einem oder mehreren unsortierten Nodes beginnen und diese bei Gelegenheit schrittweise sortieren
- Database Cracking nutzt Zugriffsmuster eingehender Queries, um die zugrunde liegenden Daten kontinuierlich und inkrementell physisch zu reorganisieren
- Ziel ist es, die Performance künftiger Queries zu verbessern
Hardwarehierarchie und Memory Wall
- Hardwarefortschritt schafft neue Herausforderungen und Chancen für das Design von Datenstrukturen
- In der Speicherhierarchie bieten niedrigere Ebenen mehr Speicherplatz zu geringeren Preisen, haben aber höhere Zugriffslatenzen; höhere Ebenen näher am Prozessor sind schneller, aber kleiner und pro Byte teurer
- Welche Ebene für eine bestimmte Anwendung den Engpass bildet, hängt von der Größe der Anwendungsdaten und der Speicherkapazität der einzelnen Ebenen ab
- B+-trees sollten ursprünglich durch maximierten Fanout Disk-Zugriffe reduzieren, doch mit größerem Arbeitsspeicher und Daten, die in RAM oder nichtflüchtigen Sekundärspeicher passen, verschieben sich die Trade-offs deutlich
- In-Memory-B+-trees erreichen bei kleinem Fanout die beste Performance
- Die Memory Wall bezeichnet den Trend einer wachsenden Lücke zwischen Prozessorgeschwindigkeit und der Geschwindigkeit von Off-Chip-Speicher
- Seit den frühen 2000er-Jahren wurden Betriebssysteme und Datenmanagementsysteme neu entworfen, um die Nutzung von Cache-Speicher zu optimieren
Designraum und Leitlinien
- Es wird der Raum möglicher Designentscheidungen für Datenstrukturen strukturiert und erläutert, wie man eine Struktur passend zu Anwendungszielen und Workload auswählt
- Da sich Hardware und Dateneigenschaften ständig verändern, ist auch beim Design von Datenstrukturen kontinuierliche Innovation nötig
- Der strukturierte Designraum und die Leitlinien dienen dazu, unter bestehenden Datenstrukturen die passendste auszuwählen oder eine neue Datenstruktur für einen bestimmten Workload zu entwerfen
1 Kommentare
Hacker-News-Kommentare
Ich habe es bisher nur überflogen, aber das ist eine hervorragende Recherchearbeit, die ein riesiges Feld abdeckt
Sie beschränkt sich nicht darauf, einfach Datenstrukturen aufzulisten, sondern hilft dabei, die Faktoren systematisch im Kopf zu ordnen, die man berücksichtigen muss, wenn man Datenstrukturen in Anwendungen entwirft oder verwendet
Einer der Autoren dieses Buchs leitet ein Forschungslabor in diesem Bereich
Es gibt auch ein großartiges Tool, das bei der optimalen Gestaltung von Datenstrukturen hilft: http://daslab.seas.harvard.edu/datacalculator/
Mich würden weitere Empfehlungen zu diesem Thema interessieren
Die Arbeit ist großartig, und ich kenne auch Martin Klepmanns Designing Data-Intensive Applications, aber dieses Buch ist eher datenbanknah als auf Datenstrukturen fokussiert
Wenn man eine Struktur für bestimmte Arten analytischer Daten entwirft, fehlt hier der sehr wichtige Gegensatz von Array of Structs und Struct of Arrays
Es wird also durchaus besprochen, nur nicht mit den Begriffen Array of Structs/Struct of Arrays erklärt
Ich würde gern ein Exemplar kaufen, aber bei Amazon kostet es 100 Dollar
Es ist ein kaputtes System, bei dem sowohl Autoren als auch Leser verlieren
Ich brauche ein Inhaltsverzeichnis
Selbst mit der Anweisung, Kopf- und Fußzeilen der Seiten zu ignorieren, war es nicht besser, und ich dachte, der aktuelle Stand wäre inzwischen deutlich weiter