Introduction
The Order-Maintenance (OM) problem is a fundamental challenge in data structure design, requiring the maintenance of a list of items while supporting three primary operations: inserting an item after another, deleting an item, and determining the relative order of any two items (Order(x, y)). While sequential algorithms achieve optimal $O(1)$ time complexity, parallelizing these structures has historically been difficult due to the "relabeling" bottleneck. When an insertion exhausts the available label space between two items, a segment of the list must be relabeled, causing significant contention in multi-core environments.
This paper introduces a novel parallel OM data structure that overcomes these limitations through a combination of lock-free comparison mechanisms and fine-grained locking for updates. This approach is particularly effective for applications like $k$-core maintenance, where comparisons significantly outnumber structural updates.
System Architecture and Methods
The proposed structure utilizes a two-level list hierarchy consisting of a top-list and a bottom-list. The top-list nodes ($g_i$) act as group headers for segments of the bottom-list nodes ($v_i$). This hierarchy localizes the impact of relabeling operations.
1. Lock-Free Comparisons
The core innovation is the implementation of a lock-free Order(x, y) operation. By utilizing a versioning system—where each label includes an 8-bit counter—the structure allows concurrent readers to perform comparisons without acquiring locks. If a comparison is interrupted by a relabeling update, a version check detects the inconsistency and triggers a "redo," ensuring that the result is always based on a consistent "Order Snapshot."
2. Fine-Grained Locking for Updates
Unlike traditional approaches that might use global locks, this structure employs localized locks on items and their immediate neighbors during Insert and Delete operations. This allows multiple updates to proceed simultaneously in different regions of the list, significantly reducing synchronization overhead.
3. Snapshot Preservation
The relabeling algorithm uses a specific stack-based sequence (AssignLabel) to update labels. This ensures that the relative numeric order of items remains valid for concurrent lock-free readers even while labels are being modified, preventing the "ABA problem" where readers might see inconsistent states.
Workload Analysis
To justify the focus on optimizing the Order operation, the authors analyzed several real-world graph datasets. The analysis revealed a massive disparity between the frequency of comparisons and updates in practical applications like $k$-core maintenance.
As shown in the workload analysis, Order operations can outnumber updates by a factor of up to 297x (e.g., in the livej and wiki-links-en datasets). By making the most frequent operation lock-free, the authors unlocked scalability that was previously unattainable.
Performance Evaluation
The data structure was tested on a 64-core machine (128 hyperthreads), demonstrating impressive scalability across various benchmarks:
- Comparisons: Achieved a speedup of up to 34.4x. The lock-free nature of the operation allows it to scale almost linearly until reaching hardware memory bandwidth limits.
- Insertions and Deletions: Achieved speedups of up to 7x and 5.6x, respectively. While these operations are limited by atomic CAS (Compare-and-Swap) operations and memory bus contention, they represent a substantial improvement over sequential implementations.
- Stability: The structure remained stable even under "Max Relabel" scenarios, which represent worst-case contention where all insertions target a single point in the list.
Conclusion and Future Work
By prioritizing the performance of the dominant Order operation through a lock-free design, this new parallel OM data structure provides a scalable solution for complex graph algorithms. Future research will explore batching updates to further reduce memory bus traffic and applying this structure to other problems such as truss maintenance and incremental topological ordering.
Summary updated