# Concurrency & Synchronization
Zipora provides sophisticated concurrency primitives designed for high-performance multi-threaded applications.
## Five-Level Concurrency Management System
Zipora implements a 5-level concurrency management system that provides graduated concurrency control options for different performance and threading requirements. The system automatically selects the optimal level based on CPU core count, allocation patterns, and workload characteristics.
### The 5 Levels of Concurrency Control
1. **Level 1: No Locking** - Pure single-threaded operation with zero synchronization overhead
2. **Level 2: Mutex-based Locking** - Fine-grained locking with separate mutexes per size class
3. **Level 3: Lock-free Programming** - Atomic compare-and-swap operations for small allocations
4. **Level 4: Thread-local Caching** - Per-thread local memory pools to minimize cross-thread contention
5. **Level 5: Fixed Capacity Variant** - Bounded memory allocation with no expansion
### Key Benefits
- **API Compatibility**: All levels share consistent interfaces
- **Graduated Complexity**: Each level builds sophistication while maintaining simpler fallbacks
- **Hardware Awareness**: Cache alignment, atomic operations, prefetching
- **Adaptive Selection**: Choose appropriate level based on thread count, allocation patterns, and performance requirements
- **Composability**: Different components can use different concurrency levels
### Usage Examples
```rust
use zipora::memory::{
AdaptiveFiveLevelPool, ConcurrencyLevel, FiveLevelPoolConfig,
NoLockingPool, MutexBasedPool, LockFreePool, ThreadLocalPool, FixedCapacityPool,
};
// Automatic adaptive selection (recommended)
let config = FiveLevelPoolConfig::performance_optimized();
let mut pool = AdaptiveFiveLevelPool::new(config).unwrap();
let offset = pool.alloc(1024).unwrap();
println!("Selected level: {:?}", pool.current_level());
// Explicit level selection for specific requirements
let pool = AdaptiveFiveLevelPool::with_level(config, ConcurrencyLevel::ThreadLocal).unwrap();
// Direct use of specific levels
let mut single_thread_pool = NoLockingPool::new(config.clone()).unwrap();
let mutex_pool = MutexBasedPool::new(config.clone()).unwrap();
let lockfree_pool = LockFreePool::new(config.clone()).unwrap();
let threadlocal_pool = ThreadLocalPool::new(config.clone()).unwrap();
let mut fixed_pool = FixedCapacityPool::new(config).unwrap();
// Configuration presets for different use cases
let performance_config = FiveLevelPoolConfig::performance_optimized(); // High throughput
let memory_config = FiveLevelPoolConfig::memory_optimized(); // Low memory usage
let realtime_config = FiveLevelPoolConfig::realtime(); // Predictable latency
```
### Adaptive Selection Logic
The system intelligently selects the optimal concurrency level:
- **Single-threaded**: Level 1 (No Locking) for maximum performance
- **2-4 cores**: Level 2 (Mutex) or Level 3 (Lock-free) based on allocation size
- **5-16 cores**: Level 3 (Lock-free) or Level 4 (Thread-local) based on arena size
- **16+ cores**: Level 4 (Thread-local) for maximum scalability
- **Fixed capacity**: Level 5 for real-time and constrained environments
### Performance Characteristics
| **Level 1** | Single-thread | **Minimal** | Single-threaded applications |
| **Level 2** | Good (2-8 threads) | Low | General multi-threaded use |
| **Level 3** | Excellent (8+ threads) | **Minimal** | High-contention scenarios |
| **Level 4** | **Outstanding** | Low | Very high concurrency |
| **Level 5** | Variable | **Minimal** | Real-time/embedded systems |
## Version-Based Synchronization for FSA and Tries
Zipora includes advanced token and version sequence management for safe concurrent access to Finite State Automata and Trie data structures.
### Key Features
- **Graduated Concurrency Control**: Five levels from read-only to full multi-writer scenarios
- **Token-Based Access Control**: Type-safe reader/writer tokens with automatic RAII lifecycle
- **Version Sequence Management**: Atomic version counters with consistency validation
- **Thread-Local Token Caching**: High-performance token reuse with zero allocation overhead
- **Memory Safety**: Zero unsafe operations in public APIs
### Usage Examples
```rust
use zipora::fsa::{ZiporaTrie, ZiporaTrieConfig, CompressedSparseTrie, ConcurrencyLevel};
// All trie variants use ZiporaTrie with strategy-based config.
// CompressedSparseTrie is a compatibility wrapper for concurrent access patterns.
let trie = CompressedSparseTrie::new(ConcurrencyLevel::OneWriteMultiRead).unwrap();
// Or use ZiporaTrie directly with sparse_optimized config:
let mut trie = ZiporaTrie::with_config(ZiporaTrieConfig::sparse_optimized());
trie.insert(b"hello").unwrap();
assert!(trie.contains(b"hello"));
// Advanced operations with explicit token control
Ok(())
}).unwrap();
// Direct token management for fine-grained control
let token_manager = TokenManager::new(ConcurrencyLevel::MultiWriteMultiRead);
with_reader_token(&token_manager, |token| {
assert!(token.is_valid());
Ok(())
}).unwrap();
with_writer_token(&token_manager, |token| {
assert!(token.is_valid());
Ok(())
}).unwrap();
```
### Concurrency Levels
| **Level 0** | `NoWriteReadOnly` | Static data, no writers | **Zero overhead** |
| **Level 1** | `SingleThreadStrict` | Single-threaded apps | **Zero overhead** |
| **Level 2** | `SingleThreadShared` | Single-threaded with token validation | **Minimal overhead** |
| **Level 3** | `OneWriteMultiRead` | Read-heavy workloads | **Excellent reader scaling** |
| **Level 4** | `MultiWriteMultiRead` | High-contention scenarios | **Full concurrency** |
### ConcurrentCsppTrie (Multi-Writer CSPP Trie)
The `ConcurrentCsppTrie` provides true multi-writer/multi-reader concurrent access to a Compressed Sparse Parallel Patricia trie, using epoch-based reclamation (crossbeam-epoch) and optimistic per-node locking.
```rust
use zipora::fsa::cspp_trie_concurrent::ConcurrentCsppTrie;
use crossbeam_epoch as epoch;
use std::sync::Arc;
let trie = Arc::new(ConcurrentCsppTrie::with_capacity(0, 10_000_000));
// Multi-threaded insert (each thread gets its own epoch guard for batching)
let trie_clone = Arc::clone(&trie);
for i in 0..10_000 {
let key = format!("key_{:06}", i);
trie_clone.insert_with_guard(key.as_bytes(), &guard);
}
});
// Concurrent reads are lock-free
assert!(trie.contains(b"key_000000"));
```
**Performance**: 6.9M single-thread insert/sec, 8.0M lookup/sec, 10+ M keys/sec at 16 threads with batched guards.
### Performance Characteristics
- **Single-threaded overhead**: < 5% compared to no synchronization
- **Multi-reader scaling**: Linear up to 8+ cores
- **Writer throughput**: 90%+ of single-threaded for OneWriteMultiRead
- **ConcurrentCsppTrie**: 10+ M keys/sec multi-writer (16 threads, batched guards)
- **Token cache hit rate**: 80%+ for repeated operations
- **Memory overhead**: < 10% additional memory usage
## Low-Level Synchronization Primitives
### Linux Futex Integration
```rust
use zipora::sync::{Futex, FutexWaiter};
let futex = Futex::new(0);
// Wait for condition
futex.wait(0, None).unwrap();
// Wake up waiters
futex.wake(1).unwrap();
```
### Thread-Local Storage
```rust
use zipora::sync::ThreadLocalStorage;
thread_local! {
static CACHE: ThreadLocalStorage<Vec<u8>> = ThreadLocalStorage::new();
}
});
```
### Atomic Operations Framework
```rust
use zipora::sync::{AtomicCounter, AtomicFlag};
let counter = AtomicCounter::new(0);
counter.fetch_add(1);
let flag = AtomicFlag::new();
flag.set();
assert!(flag.is_set());
```