A simple and practical concurrent non-blocking unbounded graph with linearizable reachability qeries

Bapi Chatterjee, Sathya Peri, Muktikanta Sa, Nandini Singhal

TL;DR

This paper introduces a novel, non-blocking concurrent directed graph that allows multiple threads to modify vertices and edges simultaneously without using locks. Its standout feature is a "linearizable" reachability query—determining if a path exists between two nodes—that remains efficient and correct even while the graph's structure is actively changing.

What Problem Does This Paper Address?

Graphs are fundamental to everything from social networks to circuit design. In modern multi-core systems, we need these graphs to be "concurrent," meaning many threads can read and write to them at once.

The traditional way to handle concurrency is through locks. However, locks are notorious for causing bottlenecks: if one thread locks the entire graph to perform a complex reachability query (like a Breadth-First Search), every other thread must wait. This leads to issues like deadlocks, priority inversion, and poor scalability.

While "non-blocking" data structures (which don't use locks) exist for simpler shapes like stacks or linked lists, building one for a dynamic, unbounded graph is incredibly difficult. The primary challenge is ensuring linearizability: the guarantee that every operation appears to take effect instantaneously at some point between its invocation and its response, even when other threads are mid-update.

Methods

The authors represent the graph using a composite adjacency list: a sorted linked list of "vertex-nodes" (VNodes), where each VNode points to its own sorted linked list of "edge-nodes" (ENodes).

Key technical components include:

  • Lock-Free Modifications: Adding or removing vertices and edges uses atomic Compare-And-Swap (CAS) operations. To remove a node, the algorithm first "logically" marks it as deleted before "physically" unlinking it, ensuring other threads don't get lost.
  • Obstruction-Free Reachability: The GetPath operation (reachability) is "obstruction-free." This means if a thread performing a search is left alone for a short time, it is guaranteed to finish.
  • The "Double Collect" Strategy: To ensure a reachability query is linearizable, the algorithm performs a BFS and then "validates" the result. It uses a clever optimization: an atomic counter (ecnt) in each vertex that increments whenever its edges change. By checking these counters, the algorithm can quickly tell if the graph changed during its search without re-scanning everything.
  • Wait-Free Lookups: For graphs of a finite size, simple "contains" checks are wait-free, meaning they are guaranteed to finish in a set number of steps regardless of what other threads are doing.

Datasets

The authors evaluated their implementation using a series of synthetic micro-benchmarks written in C/C++.

  • Initial Setup: A graph with 1,000 vertices and approximately 125,000 randomly added edges.
  • Workloads: They tested three main scenarios:
  • Lookup Intensive: 90% lookups, 10% updates.
  • Equal Lookup/Updates: 50% lookups, 50% updates.
  • Update Intensive: 10% lookups, 90% updates.
  • Baseline: They compared their non-blocking algorithm against a sequential version and a concurrent version using a single coarse-grained lock.

Key Insights and Ideas

  • Composition without Penalty: Usually, combining two lock-free structures (like two linked lists) doesn't automatically result in a lock-free system. The authors proved that their specific nesting of vertex and edge lists maintains progress guarantees.
  • The Power of ecnt: The use of an atomic edge counter is the "aha moment" for performance. It allows the reachability query to detect structural changes instantly, avoiding the massive overhead of comparing entire graph snapshots.
  • Practical Progress Guarantees: The authors chose "obstruction-freedom" for the reachability query. While weaker than "lock-freedom," it is much simpler to implement and, as their results show, performs exceptionally well in practice because total thread interference is relatively rare.

Key Results

  • Massive Speedup: The non-blocking algorithm provided a 5x to 7x performance improvement over the coarse-grained locking approach.
  • Excellent Scalability: While the lock-based version's performance actually decreased as more threads were added (due to lock contention), the non-blocking version scaled linearly until it saturated the hardware's 56 physical cores.
  • Low Query Overhead: Adding reachability queries to the workload only marginally decreased the overall throughput, proving the "double collect" validation is efficient.

Limitations and Future Work

  • Obstruction-Freedom Risks: In a system with extremely high, constant update contention, an obstruction-free operation could theoretically be delayed indefinitely (a "livelock"), though the authors did not observe this in their benchmarks.
  • Memory Reclamation: The paper assumes the existence of a lock-free memory reclamation scheme (to handle deleted nodes) but does not focus on implementing one, which is a non-trivial requirement for production systems.
  • Query Variety: The research focuses specifically on reachability. Future work could extend these non-blocking techniques to other complex graph algorithms, such as finding strongly connected components or calculating shortest paths.

Summary updated

Abstract

Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications - addition and removal of vertices and/or edges - in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking.
BibTeX
@inproceedings{chatterjee2019simple,
  author = {Bapi Chatterjee and Sathya Peri and Muktikanta Sa and Nandini Singhal},
  title = {{A simple and practical concurrent non-blocking unbounded graph with linearizable reachability qeries}},
  booktitle = {ICDCN},
  year = {2019},
  url = {https://openreview.net/forum?id=e56LCROw5b},
}
Figure