concread Documentation

Concurrently readable data structures (often called Copy-On-Write or Multi-Version-Concurrency-Control) allow multiple readers to proceed with transactions while a single writer operates.

Key Characteristics

• Non-blocking Readers: Readers are guaranteed that content remains consistent for the duration of the read. Readers do not block writers, and writers do not block readers.
• Serialized Writers: Writers are serialized, behaving similarly to a Mutex.
• Transactional Behavior: Unlike Lock-Free structures that rely on atomics and may show immediate/partial updates, Concread provides consistent state from the start to the end of an operation.
• Space-Time Trade-off: This approach uses more memory (to hold copies of data during updates) to achieve higher parallel throughput by reducing thread stalls.

When to use Concread

• Replace RwLock: Use Concread when you want to improve parallel throughput in scenarios where readers hold locks for non-trivial amounts of time. If a reader holds an RwLock for a long time, it stalls writers; if a writer holds it, it stalls readers. Concread avoids this.
• Avoid for trivial operations: If you are using an RwLock where the lock is taken, data is changed/read, and dropped immediately, Concread likely won't provide benefits.
• Map/Cache usage: Use the provided BTreeMap, HashMap, or Adaptive Replacement Cache (ARC) when you have at least 512 bytes of data in your Cell, as these structures only copy the required portions for an update.

A concurrently readable B+Tree uses a Copy-on-Write (CoW) mechanism to allow multiple readers to access stable snapshots of the tree while a writer performs updates.

The Mechanism

When an update occurs, the system does not modify nodes in place. Instead, it copies only the affected node and the nodes on the path to the leaf (the path from the root to the modified node).

Key Advantages

• Stable Snapshots: By preserving previous tree roots, readers can maintain a consistent, whole-tree view of a specific transaction generation even as new roots are being created by writers.
• Minimal Overhead: For a tree with $N$ nodes, an update only requires copying a small subset of nodes (e.g., in a tree where each node has 7 descendants, an update might only require copying 6 nodes).
• Cache Efficiency: Because nodes are cloned rather than modified in place, existing nodes remain in a Shared state, minimizing CPU cache invalidations across different cores.

The Concurrent Adaptive Replacement Cache (ARC) is designed for high-concurrency environments where readers are the majority. It uses a Copy-on-Write (CoW) approach to ensure readers and writers have consistent "point in time" views without blocking each other with heavy locks.

Core Abstractions

• Arc: The primary structure containing the core ARC state (frequency lists, recency lists, ghost lists) protected by a Mutex. It also holds the cache_set, max_capacity, and the communication channels (tx_channel).
• ArcRead: The reader interface. It maintains a cache_set_ro (read-only view), a thread_local_set for temporary inclusions, and a tx_channel to communicate events to the writer.
• ArcWrite: The writer interface. It manages a cache_set_rw, a thread_local_set for dirty/new items, and a hit_array to track access patterns.
• Haunted Set: A specialized linked list used to track keys that have been evicted. It stores the transaction ID of when a key was last observed to prevent outdated inclusions from corrupting the cache state.

Communication Model

To avoid the performance penalty of a global read lock (which would prevent readers from updating ARC metadata like hit counts), the system uses an MPSC (multiple producer - single consumer) queue.

• Readers send Hit(timestamp, K) or Inc(K, V, transaction_id, timestamp) messages to the queue.
• Writers consume these messages during the Commit Phase to update the global ARC state asynchronously.

Adaptive Replacement Cache (ARC) is a caching strategy that improves upon Least Recently Used (LRU) by using four Double Linked Lists (DLLs) to track different types of data access. This allows the cache to adapt to varying workloads and resist common cache poisoning patterns like scans or repeated single-item hits.

Core Components

• Four DLLs:
  1. Recent: Items accessed recently.

2. Frequent: Items accessed multiple times.
3. Ghost Recent: Metadata for items recently evicted from the 'Recent' set.
4. Ghost Frequent: Metadata for items recently evicted from the 'Frequent' set.

• Weight Factor p: A parameter representing "demand on the recent set".

How p Adapts

• Increasing p: If a cache miss occurs but the key is found in the Ghost Recent set, it indicates demand for more recent items. p is increased.
• Decreasing p: If a cache miss occurs but the key is found in the Ghost Frequent set, it indicates demand for more frequent items. p is decreased.

Benefits

• Scan Resistance: Unlike LRU, a large scan of new data will only affect the 'Recent' and 'Ghost Recent' sets, leaving the 'Frequent' set intact.
• Workload Adaptation: The cache automatically balances between recency and frequency based on real-time demand.

The commit phase is the critical stage where a writer's local changes and the accumulated reader events are applied to the global ARC state. This ensures temporal consistency and proper ARC semantics.

Commit Steps

1. Timestamping: The commit captures the current monotonic timestamp and the writer's transaction ID.
2. Drain Writer Local State: The writer's thread_local_set is merged into the main cache. Each item's transaction ID is updated to the writer's ID.
3. Drain MPSC Channel: The commit processes messages from the reader channel.
   • To prevent infinite loops on busy caches, it only drains messages up to the timestamp captured at the start of the commit.
   • Temporal Consistency Check: An item from the channel is only treated as an inclusion if its transaction ID is $\ge$ the existing item's transaction ID. If the transaction ID is lower, it is treated as a hit instead. This prevents old reader views from overwriting newer data.
4. Drain Writer Hit Set: The writer's hit_array is drained into the cache to give weight to recently written items.
5. Eviction: The cache performs evictions based on updated $p$ (weight) factors. All evicted items are moved to the haunted set along with their current transaction ID to protect against future stale inclusions.

Concurrently readable data structures (often referred to as Copy-On-Write, Multi-Version-Concurrency-Control, or Software Transactional Memory) allow multiple readers to proceed with transactions while a single writer operates.

Key Characteristics:

• Non-blocking Readers: Readers are guaranteed that the content of their transaction remains consistent for the duration of the read, and they do not block writers.
• Serialized Writers: Writers are serialized, behaving similarly to a Mutex.
• Performance Profile: These structures are most effective when replacing a RwLock where the read lock is held for a non-trivial amount of time. If you are using a RwLock where the lock is acquired, data is accessed, and the lock is dropped immediately, Concread may not provide significant benefits.

Use Concread to improve parallel throughput in applications where readers frequently hold locks for extended periods, which would otherwise cause writers to stall or readers to block.

An Async CowCell is a concurrently readable cell that uses a copy-on-write (clone-on-write) strategy to allow parallel reads and writes to occur simultaneously without blocking each other.

Key Behaviors:

• Parallelism: Readers and writers do not block one another. Multiple readers can access different generations of data in parallel.
• Serialization: Writers are serialized; only one write transaction can be active at a time.
• Consistency: Readers are guaranteed that the content remains consistent for the entire duration of their read transaction, even if a writer commits new data during that time.
• Isolation: Changes made during a write transaction are only visible to the writer until commit() is called.
• Rollback: If a CowCellWriteTxn is dropped without calling commit(), the changes are discarded (rolled back), and the cell remains in its previous state.

// Conceptual usage pattern
let cc = CowCell::new(initial_data);

// Readers don't block writers
let reader = cc.read().await;

// Writers don't block readers
let mut writer = cc.write().await;
*writer = new_data;
writer.commit().await;

A CowCell<T> is a concurrently readable cell that can be used as a replacement for RwLock<T>. It uses a "copy-on-write" (or clone-on-write) mechanism to allow readers and writers to operate simultaneously without blocking each other.

Key Behaviors:

• Non-blocking Reads/Writes: Readers do not block writers, and writers do not block readers.
• Consistent Reads: Readers are guaranteed that the data will remain consistent and will not change for the entire lifetime of the read transaction, even if a writer commits a new version during the read.
• Serialized Writes: While readers and writers don't block each other, writers are serialized (only one writer can be active at a time).
• Implementation: This specific implementation uses Arc, which provides better behavior for very long-running read operations and more accurate memory reclamation compared to EbrCell implementations, though it is slightly slower.

To use CowCell, the type T must implement Clone.

use concread::cowcell::CowCell;

let data: i64 = 0;
let cowcell = CowCell::new(data);

// Begin a read transaction
let read_txn = cowcell.read();
assert_eq!(*read_txn, 0);
{
    // Now create a write, and commit it.
    let mut write_txn = cowcell.write();
    *write_txn = 1;
    // Commit the change
    write_txn.commit();
}
// Show the previous generation still reads '0'
assert_eq!(*read_txn, 0);
let new_read_txn = cowcell.read();
// And a new read transaction has '1'
assert_eq!(*new_read_txn, 1);