I have a use case where I have a Bi-Partite Graph. Call one type of nodes "Type A" and the other "Type B." Now when a Type A node gets added, it forms some edges based on a criterion with Type B nodes (usually how many existing edges does the Type B node have?). Type A nodes are being added consistently (say with every HTTP request). The criteria used is very simplistic since the latency of the HTTP request cannot be large.

After some time interval X, a process runs in the background that takes a snapshot of the Graph and "reshuffles" the edges based on a more optimal criteria, which takes much longer to run. Now after it is done reshuffling it needs to update the processes that are serving HTTP requests to the new state of the graph.

Now this happens in a distributed environment. Several boxes are serving HTTP requests.

  1. How can I store the distributed graph?

One option is to store the edges and nodes in Redis. Then when a request comes in with a Type A node you first fetch all the Type B nodes (won't be too many), form all the edges and save the edges in the Redis again. Problem is that the constraint is the number of edges Type B nodes can have. So if a Type B node had 4 edges and the limit is 5 and two concurrent requests try to add an edge one has to fail. The only way I can see doing this is either

(1) Grabbing locks in Redis or

(2) Sharding the graph so that a subset of Type B nodes are always fetched by one box (which is suboptimal).

  1. How do I update the distributed graph after the optimal cycle?

The optimal cycle takes a snapshot of the Graph and optimizes the edges (reshuffles them). Now this make take some time. So during that time the HTTP requests are also adding nodes to their snapshot in Redis. What's the best way to "merge" these two graphs.

One option is after the optimal cycle runs, it

(1) sets a flag to say temporarily stop adding new nodes in HTTP requests (the requests will most likely block or send Async Message to the caller later via Kafka/RabbitMQ)

(2) adds any new nodes that were added while it was running (if it took 30 seconds to run and there was a new node added every second, then it needs to account for 30 more nodes that weren't in its snapshot).

(3) Replaces the Graph edges in Redis.

(4) Unsets the flag to start processing HTTP requests again.

However, this process causes the latency of HTTP requests to become too high when the are blocked from processing, which is not good.


Don't grab locks. Your graph must always be available, for reading and for updates.

To perform your offline reshuffling (30-seconds) you will need a way of instantly splitting the graph into two copies. That is, a web GET arrives, then you split, then a 2nd GET arrives and it won't notice an unusual delay. A typical technique to accomplish this is COW, copy-on-write.

Now you have two graphs that will diverge, one being mutated by online web requests and one being reshuffled. Web requests are additionally being logged on the side.

Once reshuffling completes, replay all logged web requests against the reshuffled graph. More requests will arrive during this, so keep at it until the queue is drained.

At this point you can safely delete the online graph, and switch the offline reshuffled graph into use for online requests.

As far as a limit of K edges per node goes, just relax it to K + 3 or 2K or something during reshuffling, and prune edges beyond K as a final step before pressing the graph into online service.

  • Thanks for the reply. So yeah we can keep "merging" the new nodes after reshuffling is done. However, if merging the new nodes into the reshuffled graph is slower than the rate at which new nodes arrive we would never stop! – dg428 Nov 25 '17 at 6:03
  • You're suggesting that queue draining could be starved by insufficient server resources. Yes, certainly. But you have that issue already, right now, you need to supply enough CPU cycles to keep up with offered load. Alternatively, you would need a mechanism (perhaps a web 302 to a fail whale page) that throttles excessive offered load. – J_H Nov 25 '17 at 6:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.