# Good snapshottable data structure for an in-memory index

I'm designing an in-memory object database for a very specific use case. It is single writer, but must support efficient concurrent reads. Reads must be isolated. There is no query language, the database only supports:

• get object/-s by attribute/set of attributes (there may be support for expressions, e.g. x.count < 5)
• get object's attribute

A query is an imperative script composed of an arbitrary number of the above operations. The data size will be << memory, so all the object and indices on most of the attributes should fit comfortably without swapping.

What I need is a data structure for the object's attribute index, which can be O(n) on writes, not support write concurrency, but should support ideally O(1) snapshots (maybe copy on write) and O(logN) access. Ideally it would allow high concurrency on reads with maximal structural sharing between the versions.

I was looking at CTries, Concurrent BSTs and Concurrent Splay Trees but I'm not sure if I'm really looking in the right direction here. The above structures pay a lot of attention to the complexity of inserts which I don't care about.

The question: is there a known data structure that is a good fit for my use case out of the box?

EDIT: after thinking some more it seems that a persistent BST/Splay tree would work. The writer would update the 'master' copy and the queries would get the tree as of the start of execution and throw it away after they are done. However, I'm still interested if there's a better solution.

• Do you need snapshots in memory, or do you need to save them to disk/network? A purely functional data structure automatically gives you in-memory snapshots, so if that's what you need, it's your best bet. – Gilles Jul 12 '15 at 14:18
• It's all in memory. I was wondering maybe there's an efficient mutable version with a constant-time snapshot (like CTrie, only without concurrent writes). – dm3 Jul 12 '15 at 16:56
• Your problem may be less the choice of data structure, but the kind of concurrency control. – Raphael Jul 12 '15 at 17:30
• It may well be, could you elaborate on that a little bit more? – dm3 Jul 12 '15 at 17:47

Use any kind of persistent/immutable (i.e., functional) tree-based data structure. The key is getting the locking right, as @Raphael pointed out in the comments.

The nice thing about functional/persistent tree-based data structures, is that you get "snapshots" for free. Let's suppose you use a treap (randomized binary search tree) for your data structure. Here's an example of one written in Go: https://github.com/steveyen/gtreap. The author describes it thusly:

By immutable, any updates/deletes to a treap will return a new treap which can share internal nodes with the previous treap. All nodes in this implementation are read-only after their creation. This allows concurrent readers to operate safely with concurrent writers as modifications only create new data structures and never modify existing data structures. This is a simple approach to achieving MVCC or multi-version concurrency control.

At any point in time the "current" state of the tree is represented by a pointer to the root of the tree. Insertions are non-mutating. Instead an insertion keeps the previous version of the tree completely intact, creates $O(\log n)$ new nodes for the path from the root to the correct insertion point, with pointers back to the nodes of the previous version that can be shared.

You use a lock to protect the pointer to the root. Since the data structure is immutable reads can be done concurrently, and you can save pointers to old snapshots. A read is:

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


Even though the search may take a while, you only hold the lock while copying the pointer, so the searches can happen concurrently.

A write is:

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


In this version, writes do need to hold the lock during the entire process of creating the new version of the tree. You can improve read performance (at the cost of sometimes having the write transaction fail) by changing the write to something like this:

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


You may be able to do even slightly better (make it "lock free") if your programming language has atomic variables with an atomic compare-and-swap operation. (For example by using C++11's atomic<T*>.)

• Thanks for the elaborate answer. I kind of knew that, maybe I didn't put that clearly enough in the question itself. However, the answer is still great! – dm3 Aug 1 '15 at 7:54
• Your "improved" version depends on the memory model of the system in use. It may well need verables to be declared volatile on some system and need great skill to get the coding correct. – Ian Ringrose Aug 14 '15 at 22:32

Microsoft has published details on their new in memory database, it has indexes that do not block reads while writes are being done.

For example:

Justin Levandoski, David Lomet, and Sudipta Sengupta, The Bw-Tree: A B-tree for New Hardware, in 2013 IEEE 29th International Conference on Data Engineering (ICDE), International Conference on Data Engineering, 8 April 2013.

See http://research.microsoft.com/en-us/projects/main-memory_dbs/ for a list of their publications.