Efficient concurrent tree

Question

I'm looking for an efficient way to implement a concurrent tree structure. If that helps, assume that I have a lot more read accesses than changes to the structure.

The tree should support these operations:

• Adding and removing nodes
• Sort branches every time a new node is inserted
• Iterate over all the nodes (without ConcurrentModificationException)
• Look up an element by path

Answer 1

Take a look at: Concurrent-Trees on Google code for a way to modify tree-like structures without locking.

The project provides Concurrent Radix and Suffix trees for Java. They supports concurrent reads and writes, and reads are lock-free. It works by applying patches to the tree atomically. While these types of tree might not be exactly what you want, the approach using "patching" as described in TreeDesign is useful for any kind of tree-like structure.

The trees are intended for high concurrency read-mostly use cases, where (say) a background thread might be inserting or deleting entries from the tree while many foreground threads would continue to traverse it unimpeded by the modifications.

Answer 2

The Java structure that is the closest to what you may need is a ConcurrentSkipListSet (or maybe ConcurrentSkipListMap).

---

If you need a more custom approach, you can implement a custom tree structure if you have a hierarchic read-write lock. Here is an answerto a similar question about how to implement a reentrant read-write lock: https://stackoverflow.com/a/6154873/272388

Answer 3

You could use a reader-writer lock in your structure, in a way that multiple threads can read cuncurrently but only one thread at a time can modify it. If some thread tries to modify the structure it cannot do it until all of the readers have done their reads. If a thread wants to read it can only if a writer isn't already working, or it is on shedule of doing some modifications. Maybe a look at this could help:

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

Answer 4

Basic idea with Read/Write lock

For all write methods use following idiom:

someWriteMethod(){
  writeLock.lock();
  // logic
  writeLock.unlock();
}

For all read methods use similar code:

someReadMethod(){
  readLock.lock();
  // logic
  readLock.unlock();
}

• If at least one method performs writing, no one can obtain read or write lock.
• If at least one method performs reading, any numbers of thread can obtain readlock.
• If at least one method performs reading, no one can obtain write lock.

Note, if your code (replace logic comment above) can throw exception make sure you release locks before exit from method in finally section.