How do I organize multithreaded access to a graph?

Question

I'm elaborating over a problem which seems hard to me and I'm not expecting a simple solution, but maybe there are proven practices or further reading that might make this easier. I'm pretty sure that the general problem pops up in many applications (for example garbage collection or transactional databases).

My application has a graph (a DAG if it matters) which is being traversed by multiple threads simultaneously. Some of these are just trying to find certain nodes or retrieve a subgraph, others may change the graph's structure.

The policy I want to implement is that a reading thread will perform its entire operation on a "snapshot" of the graph, i. e. see the structure as it was at a certain point in time.

My current plan is to set up something similar to row versioning in transactional DBs, i. e. a reading thread first obtains a current version number and then only visits graph nodes and edges that have this version number or earlier. Writing threads would then put an incremented version number on new elements (changed elements would be cloned first), making them invisible for running readers. A writing thread can then "commit" its new version when it has successfully finished, and readers would "release" their version number, making deleted elements eligible for removal.

This strategy is still sketchy and has a number of unsolved issues such as concurrent write access, but generally it seems like a viable road to go.

Answer 1

an alternative would be using Persistent Data Structures. They are data structure which always preserves the previous version of itself when it is modified.

They are like a log file, the modified version is always appendend last making them immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. Programming languages like Clojure lately polularized this approach (at least to me).

Answer 2

Your approach seems sound to me ...

What you might have problems with however is ensuring causality between writes on separate subgraphs.

If a writer alters subgraph A and another writer alters distinct subgraph B, but other read/write operations happen on subgraph C where A and B are in C then you need to ensure that the version of subgraph C aligns correctly with the versions of B and A.

I would suggest a locking scheme in the DAG that incorporates subgraph locking for multiple read/single write from a given root. You will need to grep the graph for cyclic dependencies however to ensure that you don't get into a starvation/deadlock state within the graph.

If your graph is distributed or your concurrent access has latency then your transaction system will be harder to implement and will likely require additional safeguards.

Your versioning approach sounds fine providing your locking provisions ensure, in all cases that a set of revisions for nodes at any time T represent an integral state of the graph. The set of nodes and revisions at T = {n0, n1, n2, n3} and a concurrent revision bumping of subgraphs will pose the headache in keeping the entire set of revisions and nodes at T integral.

As dfa suggests above, the set of nodes and revisions at some point represents a changeset of the entire structure. Providing it has integrity, this represents the entire structure at some point in time.

Remember: Time, Integrity, Causality and Concurrency

Good Luck!

Answer 3

Well, I thought I'd be clever and google several keywords, to find some literature. The first result... was this question.

So there isn't too much on this topic! Interesting. Just thought I'd share.

Aiden Bell and DFA have both given very thorough answers, so I won't try to top them. :) But I will make one observation, concerning the DAG quality of the graph and concurrent write access. This may have already occurred to you, but hey. :)

You can allow concurrent threads without having to worry about one overwriting another's changes by simply assuming that, at all times, the node inhabited by a writing thread, and all of the children of that node, are "locked" by that particular writing thread. I find it easiest to visualize this with a tree (which is a DAG as well, obviously). Any writing thread has basically locked a particular sub-tree, but likewise we can now say that any sibling trees, or any ancestor nodes, are happily writable.

A more complex DAG (where a node can have multiple parents, in particular) will have, in effect, a lot of overlapping sub-trees, and so there may not be so much freedom, but the rule still applies: any node that is not inhabited by, or the child of a node inhabited by a write-thread, can be considered write-enabled.

Obviously, there could be a lot of factors why the above idea is not helpful, but if multiple write threads often head off in "different" directions, it may ease some of the requirements needed to make it thread-safe.

Hope this helps!

-Agor