Geordneter Schlüssel-Wert-Speicher

Ein geordneter Key-Value-Speicher (OKVS) ist ein Datenspeicherparadigma, das Multi-Modell-Datenbanken unterstützt . Ein OKVS bildet Bytes geordnet auf Bytes ab. Die Schlüssel-Wert-Paare werden in einem OKVS gemäß der lexikografischen Reihenfolge der Schlüssel gespeichert. OKVS-Systeme bieten unterschiedliche Funktionen und Leistungskompromisse. Die meisten werden als Bibliothek ohne Netzwerkschnittstelle bereitgestellt, um in andere Prozesse eingebettet werden zu können. Die meisten OKVS erfüllen die ACID-Garantien . Einige OKVS sind verteilte Datenbanken . Geordnete Key-Value-Speicher finden in vielen modernen Datenbanksystemen, einschließlich NewSQL -Datenbanksystemen, Anwendung.

Die Ursprünge des geordneten Key-Value-Speichers liegen in Ken Thompsons Arbeit an dbm im Jahr 1979. 1991 erschien Berkeley DB mit einem B-Baum -Backend, das die Sortierung der Schlüssel ermöglichte. Berkeley DB galt als sehr schnell und fand Eingang in diverse kommerzielle Produkte. Bis Version 2.7 war es Bestandteil der Python-Standardbibliothek. ^{[ 1 ]} 2009 wurde Tokyo Cabinet veröffentlicht, das später von Kyoto Cabinet abgelöst wurde , welches sowohl Transaktionen als auch geordnete Schlüssel unterstützte. 2011 wurde LMDB als Nachfolger von Berkeley DB in OpenLDAP entwickelt . Googles LevelDB wurde 2012 von Facebook als RocksDB abgespalten . 2014 wurde WiredTiger , der Nachfolger von Berkeley DB, von MongoDB übernommen und ist seit 2019 das primäre Backend der MongoDB-Datenbank.

Weitere bemerkenswerte Implementierungen des OKVS-Paradigmas sind Sophia ^{[ 2 ]} und die SQLite3-LSM-Erweiterung. Ein weiteres wichtiges Anwendungsgebiet des OKVS-Paradigmas ist das auf RocksDB basierende Multi-Modell-Datenbanksystem ArangoDB ^{[ 3 ]} .

Einige NewSQL- Datenbanken unterstützen geordnete Schlüsselwertspeicher. JanusGraph , eine Eigenschaftsgraphdatenbank, verfügt sowohl über ein Berkeley-DB- als auch über ein FoundationDB- Backend.

Es gibt Algorithmen, die grundlegende Datentypen (Boolesche Werte, Zeichenketten, Zahlen) und deren Kompositionen in sortierten Containern (Tupel, Listen, Vektoren) kodieren und dabei deren natürliche Reihenfolge beibehalten. So kann man mit einem sortierten Schlüssel-Wert-Speicher arbeiten, ohne direkt mit Bytes arbeiten zu müssen. In FoundationDB wird dies als Tupelschicht bezeichnet. ^{[ 4 ]}

Innerhalb eines OKVS sind die Schlüssel geordnet, wodurch Bereichsabfragen möglich sind. Eine Bereichsabfrage ruft alle Schlüssel zwischen zwei angegebenen Schlüsseln ab und stellt sicher, dass die abgerufenen Schlüssel in sortierter Reihenfolge zurückgegeben werden.

Man kann Schlüsselräume konstruieren, um Abstraktionen höherer Ebene zu erstellen. Die Idee besteht darin, Schlüssel zu konstruieren, die die geordnete Struktur des übergeordneten Schlüsselraums ausnutzen. Durch die Ausnutzung dieser Ordnung lassen sich Schlüsselbereiche mit einem bestimmten Muster abfragen.

Denormalisierung, also die Wiederholung derselben Daten in mehreren Unterräumen, ist gängige Praxis. Sie ermöglicht die Erstellung sekundärer Repräsentationen, sogenannter Indizes, die die Abfragegeschwindigkeit erhöhen.

Die folgenden Abstraktionen bzw. Datenbanken wurden auf der Grundlage von Top-Order-Key-Value-Speichern erstellt:

• Zeitreihendatenbank,
• Datensatzdatenbanken, ^{[ 5 ]} auch als Zeilenspeicherdatenbanken bekannt, verhalten sich ähnlich wie das, was als RDBMS bezeichnet wird .
• Tuple Stores, auch bekannt als Triple Store oder Quad Store, aber auch als generischer Tuple Store, ^{[ 6 ] [ 7 ]}
• Dokumentendatenbank, ^{[ 8 ]} die die MongoDB-API nachbildet,
• Volltextsuche ^{[ 9 ]}
• Geographische Informationssysteme ^{[ 10 ]}
• Eigenschaftsgraph ^{[ 11 ]}
• Versionierte Daten ^{[ 12 ]}
• Vektorraumdatenbank für Approximative Nächste-Nachbarn ^{[ 13 ]}

Alle diese Abstraktionen können mit derselben OKVS-Datenbank koexistieren, und wenn ACID unterstützt wird, erfolgen die Operationen mit den Garantien, die das Transaktionssystem bietet.

OKVS eignen sich für zwei Strategien: die Optimierung kleiner Funktionen, z. B. zur Verbesserung der Lese- oder Schreiblatenz um 10 %; die Nutzung der verteilten Architektur von FoundationDB und TiKV, für die es in Bezug auf Ausfallsicherheit bei sehr großem Umfang keine vergleichbare Lösung gibt. Beide Anwendergruppen müssen die benötigten Abstraktionen höherer Ebene selbst implementieren, da keine portablen, sofort einsatzbereiten Bibliotheken für diese Abstraktionen existieren. Die komplexe Balance zwischen Komplexität, Wartbarkeit, Feinabstimmung und verfügbaren Funktionen macht die Wahl von OKVS weiterhin zu einer Angelegenheit für Experten. Manchmal sind spezialisiertere Datenstrukturen schneller als eine Abstraktion höherer Ebene auf Basis eines OKVS.

Ein weiterer Vorteil des OKVS-Paradigmas liegt in seiner einfachen und vielseitigen Schnittstelle, die es zu einem interessanten Ziel für experimentelle Speicheralgorithmen und Datenstrukturen macht.

• Schlüssel-Wert-Datenbank
• Breitsäulenladen
• Multi-Modell-Datenbank