Abstract
This report details the design of two new concurrent data structures, a hash table, called CLHT, and a binary search tree (BST), called BST-TK. Both designs are based on asynchronized concurrency (ASCY), a paradigm consisting of four complementary programming patterns. ASCY calls for the design of concurrent search data structures to resemble that of their sequential counterparts. CLHT (cache-line hash table) uses cache-line-sized buckets and performs in-place updates. As a cache-line block is the granularity of the cache-coherence protocols, CLHT ensures that most operations are completed with at most one cache-line transfer. BST-TK reduces the number of cache-line transfers by acquiring less locks than existing BSTs.
Introduction
In the era of many-core computing, software performance is increasingly constrained by memory synchronization rather than raw processing power. Specifically, "cache-coherence traffic"—the inter-core communication required to synchronize local caches—presents a significant barrier to scalability. Traditional Concurrent Search Data Structures (CSDSs) often employ intricate locking mechanisms or heavy synchronization primitives that fail to scale across diverse hardware architectures, such as NUMA systems.
To achieve "portable scalability," we advocate for a design philosophy where concurrent structures mirror the simplicity of their sequential versions. This approach, termed Asynchronized Concurrency (ASCY), prioritizes minimizing expensive memory "stores" and ensuring that search operations remain wait-free.
The ASCY Paradigm
The core of ASCY is the separation of concerns between searching and updating. Under this paradigm, search operations are strictly read-only and never involve waiting or retries. Updates are decomposed into two distinct phases:
- Phase 1 (Parse): A read-only traversal to locate the target position.
- Phase 2 (Modify): A minimal, synchronized step to apply the update.
By keeping the concurrent logic as close to sequential logic as possible, ASCY reduces the overhead typically associated with thread safety.
CLHT: Hardware-Aware Hashing
The Cache-Line Hash Table (CLHT) is designed with "mechanical sympathy" for modern hardware. Since hardware manages memory in 64-byte cache lines, CLHT sizes its buckets to fit exactly within a single cache line.
- Efficiency: Most operations (search, insert, delete) require only a single cache-line transfer between cores, reaching the theoretical minimum for shared state updates.
- Atomic Snapshots: CLHT-LB (lock-based) enables lock-free searches by taking atomic snapshots of buckets. Because keys and values are read together and validated, searches proceed without acquiring locks, even during concurrent updates.
- Variants: The design includes both lock-based (CLHT-LB) and lock-free (CLHT-LF) implementations, the latter using atomic snapshots for consistency.
BST-TK: Optimized Tree Synchronization
The Binary Search Tree Ticket (BST-TK) optimizes tree operations by repurposing ticket locks. In BST-TK, ticket locks serve a dual purpose: mutual exclusion and versioning.
- Lock-as-Version: By modifying the lock interface, we can acquire a lock and validate a node's version in a single atomic step. This significantly reduces the synchronization overhead compared to traditional BSTs that require locking multiple nodes.
- Reduced Contention: BST-TK requires only one lock for a successful insertion and two for a removal. It employs an optimistic approach, parsing the tree without locks and validating the target node's version before modification.
Key Insights and Results
The primary insight of this work is that the most efficient concurrent structures are those that minimize deviation from sequential logic.
- Minimal Coherence Traffic: CLHT's alignment with hardware cache lines eliminates false sharing and excessive traffic.
- Wait-Free Searches: Both CLHT and BST-TK provide wait-free (or effectively wait-free) search operations, ensuring high throughput in read-heavy workloads.
- Scalability: By reducing the number of locks and memory stores, these structures achieve massive scalability on modern multi-core processors.
Limitations
While highly performant, these designs involve trade-offs. CLHT's resizing mechanism is currently single-threaded, which may impact performance for extremely large tables during expansion. BST-TK requires operations to restart from the root if version validation fails, though this keeps the design simple and ASCY-compliant. Finally, the lock-free variant of CLHT relies on specific memory management assumptions to guarantee progress.
Conclusion
By adhering to the ASCY paradigm and designing with hardware constraints in mind, CLHT and BST-TK demonstrate that concurrent data structures can be both simple and highly scalable. These designs provide a blueprint for building portably scalable software in the many-core era.
Summary updated