Concurrent data structure design

Question

I am trying to come up with the best data structure for use in a high throughput C++ server. The data structure will be used to store anything from a few to several million objects, and no sorting is required (though a unique sort key can be provided very cheaply).

The requirements are that it can support efficient insert, ideally O(1), moderately efficient removal, and efficient traversal. It doesn't need to support a find operation (other than might be needed for removal).

The twist is that it must be thread safe with respect to modifications while other threads are enumerating the data structure. This means that a simple red-black tree doesn't work, since one thread can't insert an element (and perform the necessary tree rotations) without messing up any cursors held by other threads.

It is not acceptable to use a read/write lock and defer the write operations until all readers have finished, since read operations may be long lived. It doesn't matter if inserts that happen while there is a reader are visible to that reader or not.

Memory footprint is also very important, and small is obviously better!

What suggestions are there?

Response to comments:

Thanks for the answers.

No, inserts cannot invalidate existing iterators. Iterators may or may not see the new insert, but they must see everything that they would have seen if the insert hadn't occurred.

Deletion is required, however due to higher level rules I can guarantee that a iterator will never be stopped on an item that is available for deletion.

Locking per node for a cursor would have too great an impact on performance. There may be a number of threads reading at once, and any kind of memory hot spot that multiple threads are using in a lock kills memory bandwidth (as we discovered the hard way!). Even a simple count of readers with multiple threads calling InterlockedIncrement fails to scale cleanly.

I agree a linked list is likely the best approach. Deletes are rare, so paying the memory penalty for the back pointers to support O(1) delete is costly and we may compute those separately on demand and since deletes tend to be batch operations.

Fortunately insertion into a linked list doesn't require any locking for readers, as long as the pointers are updated in the inserted node before the head pointer is changed.

The lock-copy-unlock idea is interesting. The amount of data involved is too large for this to work as the default for readers, but it could be used for writers when they collide with readers. A read/write lock would protect the whole structure, and the write would clone the data structure if it collides with a reader. Writes are much rarer than reads.

Answer 1

I think linked list should answer your requirements. Note that you can lock only the nodes that are being changed (i.e. deleted/appended) so readers most of the time will be able to work in full parallelism with the writers. This approach requires a lock per linked list node, however it's not a must. You can have limited amount of locks and then several nodes will be mapped to the same lock. I.e., having array of N locks and nodes numbered 0..M you can use lock (NodeId % N) for locking this node. Those can be read-write locks, and by controlling amount of locks you can control amount of parallelism.

Answer 2

Well, to be thread-safe you're going to have to lock something at some point. One key thing is to make sure that the objects in your repository can be locked separately from the repository structure itself: i.e. don't have a _next link or anything of the sort inside the data you are storing. This way read operations can lock the contents of the objects without locking the structure of the repository.

Efficient insert is easy: linked list, unsorted arrays, hashtables all work ok. Efficient deletion is harder since that involves finding the deleted thing in the repository. Howerver, for raw simplicity and speed, a linked list is a good choice. Can deletions be postponed for non-busy times and items just marked as "inactive"? Then the cost of finding/deleting is not so limiting.

You're still going to have problems with traversal though. About all you can do is to lock and take a snapshot of what needs to be traversed, then check for any changes after the snapshot is looked at. Tough problem...

Answer 3

If you don't need a sort order, don't use a red/black tree or anything else that inherently sorts.

Your question is not well specified enough w.r.t to interaction between reads and writes. Would it be ok if a "read" is implemented by a lock+copy+unlock and then use the new copy?

You may want to read about seqlocks in http://en.wikipedia.org/wiki/Seqlock, and on "lock free" processes in general -- though, you may want to relax your requirements as much as possible -- a lock-free hash table implementation is a major undertaking.

Answer 4

Linked lists are definitely the answer here. Insertion and deletion in O(1), iteration from one node to the next in O(1) and stability across operations. std::list guarantees all of these, including that all iterators are valid unless the element is removed from the list (this include pointers and references to elements). For locking, you could just wrap the list in a locking class, or you could write your own list class (you wouldn't be able to use std::list in this case that supports node-based locking - e.g. you can lock down certain areas of the list for use while other threads perform operations on different areas. Which you use is largely dependent on the type of concurrent access you expect - if multiple operations on different parts of the list will be really common, write your own, but remember you will be putting a mutex object in each node, which isn't space-efficient.

Answer 5

Personally, I'm quite fond of persistent immutable data structures in highly-concurrent situations. I don't know of any specifically for C++, but Rich Hickey has created some excellent (and blisteringly fast) immutable data structures in Java for Clojure. Specifically: vector, hashtable and hashset. They aren't too hard to port, so you may want to consider one of those.

To elaborate a bit more, persistent immutable data structures really solve a lot of problems associated with concurrency. Because the data structure itself is immutable, there isn't a problem with multiple threads reading/iterating concurrently (so long as it is a const iterator). "Writing" can also be asynchronous because it's not really writing to the existing structure but rather creating a new version of that structure which includes the new element. This operation is made efficient (O(1) in all of Hickey's structures) by the fact that you aren't actually copying everything. Each new version shares most of its structure with the old version. This makes things more memory efficient, as well as dramatically improving performance over the simple copy-on-write technique.

With immutable data structures, the only time where you actually need to synchronize is in actually writing to a reference cell. Since memory access is atomic, even this can usually be lock-free. The only caveat here is you might lose data between threads (race conditions). The data structure will never be corrupted due to concurrency, but that doesn't mean that inconsistent results are impossible in situations where two threads create a new version of the structure based on a single old and attempt to write their results (one of them will "win" and the other's changes will be lost). To solve this problem, you either need to have a lock for "writing operations", or use some sort of STM. I like the second approach for ease-of-use and throughput in low-collision systems (writes are ideally non-blocking and reads never block), but either one will work.

You've asked a tough question, one for which there isn't really a good answer. Concurrency-safe data structures are hard to write, particularly when they need to be mutable. Completely lock-free architectures are provably impossible in the presence of shared state, so you may want to give up on that requirement. The best you can do is minimize the locking required, hence the immutable data structures.

Answer 6

Apologies for the double-answer...

Since writes are fairly rare, you really should consider using STM instead of locking. STM is a form of optimistic locking, which means that it is heavily biased in performance toward collision-free systems (a.k.a. fewer writes). By contrast, pessimistic locking (lock-write-unlock) is optimized for collision-heavy systems (a.k.a. lots of writes). The only catch with STM is it almost demands that you make use of immutable data structures within the TVar cells, otherwise the whole system breaks down. Personally, I don't think this is a problem since a decent immutable data structure is going to be just as fast as a mutable one (see my other answer), but it's worth considering.

Answer 7

You have 3 types of tasks:

1. iteration (slow)
2. insertion (fast)
3. deletion (fast)

If near consistency is good enough then keep track of the # of active iteration tasks.

If iterations tasks are active and a new insert or deletion tasks comes in queue those tasks for later processing (but you can return the to caller right away)

As soon as the last iteration if finished process queued inserts and deletes.

If an iteration request comes in while inserts or deletes are pending then queue it up.

If an iteration request comes in while there are just iterations running just have it go and iterate.

You should still write the iteration to be as fast as possible by making a copy of the data you are iterating over and then process that data in the client if the actual data processing takes a lot more time than the iteration itself.

I would implement the main collection with a hashtable or stl:map might even be fast enough. Insert/Delete requests could be queued in a list.

Answer 8

The only way I think this is achievable is through something similar to multiversion concurrency protocol used in databases such as oracle/postgresql etc. This guarantees that readers doesn't block readers, writers doesn't block readers, but writers block only those writers which update the same piece of data. This property of writers blocking the writer(s) which update the same piece of data is important in concurrent programming world, otherwise data/system inconsistencies are possible. For each and every write operation to the data structure you take a snapshot of the data structure or atleast the portion of the data-structure nodes affected by the write operation to a different location in the memory before doing the write. So when the write is in progress, a reader thread requests to read a portion of data from the writer portion, you always refer to the latest snapshot & iterate over that snapshot, there by providing consistent view of data to all the readers. Snapshot's are costly since they consume more memory, but yes for your given requirement, this technique is the right one to go for. And yes use locks (mutex/semaphore/spinlock) to protect the write operation from other writer threads/processes needing to update the same piece of data.

Answer 9

FWIW, this is trivial to solve if you have a garbage collector. In F#, for example, you can just use a mutable reference to a linked list or purely functional map (balanced binary tree) without any locks. This works because the data structures are immutable and writing a reference (to update after a write) is atomic so concurrent readers are guaranteed to see either the old or new data structure but never corruption. If you have multiple writers then you can serialize them.

However, this is much harder to solve in C++...

Answer 10

I'm not sure if anybody has mentioned this, but I would take inspiration from Java's ConcurrentHashMap. It offers traversal, retrieval and insertion without locking or waiting. The only lock occurs once you've found a bucket of data corresponding to the hash key and you're traversing that bucket (i.e. you ONLY lock the bucket not the actual hash map). "Instead of a single collection lock, ConcurrentHashMap uses a fixed pool of locks that form a partition over the collection of buckets."

You can find more details on the actual implementation here. I believe that all of the things shown in the implementation can be just as easily done with C++.

So let's go through your list of requirements:

1. High throughput. CHECK
2. Thread safe. CHECK
3. Efficient inserts happen in O(1). CHECK
4. Efficient removal (with no data races or locks). CHECK
5. VERY efficient traversal. CHECK
6. Does not lock or wait. CHECK
7. Easy on the memory. CHECK
8. It is scalable (just increase the lock pool). CHECK

Here is an example of a map Entry:

protected static class Entry implements Map.Entry {
    protected final Object key;
    protected volatile Object value;
    protected final int hash;
    protected final Entry next;
    ...
}

Note that the value is volatile, so when we're removing an Entry we set the value to NULL which is automatically visible to and any other thread that attempts to read the value.