Gute Snapshottable-Datenstruktur für einen speicherinternen Index

Ich entwerfe eine speicherinterne Objektdatenbank für einen bestimmten Anwendungsfall. Es ist ein einzelner Writer, muss jedoch effiziente gleichzeitige Lesevorgänge unterstützen. Lesevorgänge müssen isoliert werden. Es gibt keine Abfragesprache, die Datenbank unterstützt nur:

• Objekt / -s nach Attribut / Gruppe von Attributen abrufen (möglicherweise werden Ausdrücke unterstützt, z. B. x.count < 5)
• Objektattribut abrufen

Eine Abfrage ist ein Imperativskript, das aus einer beliebigen Anzahl der oben genannten Operationen besteht. Die Datengröße ist << Speicher, sodass alle Objekte und Indizes für die meisten Attribute problemlos ohne Auslagerung passen sollten.

Was ich brauche, ist eine Datenstruktur für den Attributindex des Objekts, die O (n) bei Schreibvorgängen sein kann, Schreib-Parallelität nicht unterstützt, aber idealerweise O (1) Snapshots (möglicherweise beim Schreiben kopieren) und O (logN) -Zugriff unterstützen sollte. Idealerweise würde dies eine hohe Parallelität bei Lesevorgängen mit maximaler struktureller Aufteilung zwischen den Versionen ermöglichen.

Ich habe mir CTries , Concurrent BSTs und Concurrent Splay Trees angesehen , bin mir aber nicht sicher, ob ich hier wirklich in die richtige Richtung schaue. Die obigen Strukturen widmen der Komplexität von Inserts, die mir egal sind, viel Aufmerksamkeit.

Die Frage : Gibt es eine bekannte Datenstruktur, die sofort für meinen Anwendungsfall geeignet ist?

BEARBEITEN : Nach einigem Nachdenken scheint es, als würde ein beständiger BST / Splay-Baum funktionieren. Der Schreiber würde die 'Master'-Kopie aktualisieren und die Abfragen würden den Baum zu Beginn der Ausführung abrufen und ihn wegwerfen, nachdem sie fertig sind. Ich bin jedoch immer noch daran interessiert, ob es eine bessere Lösung gibt.

Verwenden Sie eine beliebige Art von persistenter / unveränderlicher (dh funktionaler) baumbasierter Datenstruktur. Der Schlüssel hat die richtige Schließung, wie @Raphael in den Kommentaren hervorhob.

Das Schöne an funktionalen / persistenten baumbasierten Datenstrukturen ist, dass Sie kostenlos "Schnappschüsse" erhalten. Angenommen, Sie verwenden einen Treap (randomisierten binären Suchbaum) für Ihre Datenstruktur. Hier ist ein Beispiel von einem, das in Go geschrieben wurde: https://github.com/steveyen/gtreap . Der Autor beschreibt es so:

Bei unveränderlichen Aktualisierungen / Löschungen eines Treaps wird ein neuer Treap zurückgegeben, der interne Knoten mit dem vorherigen Treap teilen kann. Alle Knoten in dieser Implementierung sind nach ihrer Erstellung schreibgeschützt. Dies ermöglicht gleichzeitigen Lesern den sicheren Betrieb mit gleichzeitigen Schreibvorgängen, da durch Änderungen nur neue Datenstrukturen erstellt und niemals vorhandene Datenstrukturen geändert werden. Dies ist ein einfacher Ansatz, um eine MVCC- oder Mehrversions-Parallelitätskontrolle zu erreichen.

$O(\log n)$

Sie verwenden eine Sperre, um den Zeiger auf die Wurzel zu schützen. Da die Datenstruktur unveränderlich ist, können Lesevorgänge gleichzeitig ausgeführt und Zeiger auf alte Snapshots gespeichert werden. Eine Lektüre ist:

lock
tmp = ptr_to_root
unlock
value = search(tmp, <value to search for>)
return value

Obwohl die Suche eine Weile dauern kann, halten Sie die Sperre nur beim Kopieren des Zeigers gedrückt, sodass die Suche gleichzeitig erfolgen kann.

Ein Schreiben ist:

lock
old_ptr_to_root = ptr_to_root
ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
unlock

In dieser Version müssen Schreibvorgänge die Sperre während des gesamten Erstellungsprozesses der neuen Version des Baums beibehalten. Sie können die Leseleistung verbessern (auf Kosten eines manchmal fehlgeschlagenen Schreibvorgangs), indem Sie den Schreibvorgang folgendermaßen ändern:

top:
  lock
  old_ptr_to_root = ptr_to_root
  unlock
  new_ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
  lock
  if (ptr_to_root == old_ptr_to_root)   # make sure no other write happened in the interim
    ptr_to_root = new_ptr_to_root
    unlock
  else                                  # transaction fails, try again
    unlock
    goto top

Möglicherweise können Sie sogar eine geringfügige Verbesserung erzielen ("lock free" machen), wenn Ihre Programmiersprache atomare Variablen mit einer atomaren Compare-and-Swap-Operation enthält. (Zum Beispiel mit C ++ 11. atomic<T*>)

Microsoft hat Details zu ihrer neuen In-Memory-Datenbank veröffentlicht. Sie verfügt über Indizes, die keine Lesevorgänge blockieren, während Schreibvorgänge ausgeführt werden.

Beispielsweise:

Justin Levandoski, David Lomet und Sudipta Sengupta, Der Bw-Baum: Ein B-Baum für neue Hardware, 2013 IEEE 29. Internationale Konferenz für Datentechnik (ICDE), Internationale Konferenz für Datentechnik, 8. April 2013.

Eine Liste der Veröffentlichungen finden Sie unter http://research.microsoft.com/en-us/projects/main-memory_dbs/ .