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
GetPathoperation (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