# Lock-Free чтение для Map коллекций
## Проблема
Tree коллекции (ConstTree, VarTree, TypedTree, ZeroTree) используют общий SkipList с lock-free чтением через `seize::Guard`. Map коллекции (ConstMap, VarMap, TypedMap, ZeroMap) используют `Vec<Mutex<HashMap<K, Entry>>>` — даже `get()` берёт shard mutex.
`HashMap` не thread-safe для concurrent read+write — чтение при параллельной записи (resize, rehash) — UB. Поэтому мьютекс обязателен.
```rust
// const_map.rs — текущая реализация
pub fn get(&self, key: &K) -> Option<[u8; V]> {
let index = sync::lock(&self.indexes[self.shard_for(key)]);
index.get(key).map(|e| e.value)
}
```
Вопрос: можно ли сделать Map с lock-free чтением без потери производительности записи?
---
## Варианты
### 1. Concurrent HashMap на `seize` (chained buckets) — рекомендуется
Повторяет паттерн SkipList — atomic linked lists + epoch-based reclamation:
```rust
struct ConcurrentMap<K, V> {
buckets: Box<[Atomic<*mut Node<K, V>>]>, // fixed-size array
collector: seize::Collector,
len: AtomicUsize,
}
struct Node<K, V> {
key: K,
value: V, // ConstMap: [u8; V] + DiskLoc
// VarMap: DiskLoc
next: Atomic<*mut Node<K, V>>,
}
```
**Read path** — lock-free, O(1) amortized:
1. `guard = collector.enter()`
2. `bucket = buckets[hash(key) % len].load(Acquire)`
3. Traverse chain, compare keys
4. Return value (защищено guard)
**Write path** — shard mutex уже есть для disk write:
1. Insert: allocate Node, CAS на head bucket
2. Update: allocate новый Node, swap `AtomicPtr`, retire старый через `seize`
3. Delete: unlink из chain, retire через `seize`
**Плюсы:**
- Lock-free чтения, O(1)
- Единая система reclamation (seize) — консистентно с SkipList
- Write performance не деградирует — shard mutex уже берётся для disk append
- Memory overhead: ~40 bytes per entry (Node + next ptr) vs ~50 bytes текущего HashMap bucket
**Минусы:**
- Resize: при переполнении (load factor > 0.75) нужно увеличивать массив buckets
- Resize под global write lock (приемлемо — writes уже сериализованы)
- Sizing при `open()` через `estimated_items` в Config (уже есть в API)
- Длинные цепочки при плохом distribution — но `xxh3` этого не допустит
### 2. Open-addressing с atomic slots
```rust
struct OpenMap<K, V> {
slots: Box<[AtomicPtr<Entry<K, V>>]>,
collector: seize::Collector,
}
```
Read: linear/quadratic probing по атомарным слотам. Без аллокаций на цепочки.
**Плюс:** cache-friendly (линейный обход памяти).
**Минус:** delete через tombstone-маркеры, resize сложнее, Robin Hood / Swiss Table алгоритмы трудно сделать lock-free.
### 3. RwLock вместо Mutex
```rust
indexes: Vec<RwLock<HashMap<K, Entry>>>
```
**Плюс:** минимальные изменения, параллельные чтения.
**Минус:** не lock-free — `RwLock::read()` это атомарный инкремент reader count. При uncontended Mutex быстрее RwLock (~20ns vs ~25ns). Выигрыш только при высокой read contention.
### 4. Epoch-based snapshot (RCU на целый HashMap)
```rust
index: AtomicPtr<HashMap<K, Entry>> // whole HashMap behind atomic pointer
```
Read: load pointer под guard, читай свободно.
Write: clone HashMap → modify → swap pointer → retire old.
**Минус:** clone O(n) на каждую запись — катастрофа для write performance. Не подходит.
---
## Сравнение
| | Текущий Map | Concurrent Map на seize | RwLock | Open-addressing | RCU snapshot |
|---|---|---|---|---|---|
| Read lock | Shard Mutex (~20ns) | Lock-free (~5ns) | RwLock (~25ns) | Lock-free (~5ns) | Lock-free (~5ns) |
| Read complexity | O(1) | O(1) amortized | O(1) | O(1) | O(1) |
| Write lock | Shard Mutex | Shard Mutex | RwLock (exclusive) | Shard Mutex | Shard Mutex |
| Write overhead | HashMap insert | CAS + alloc node | HashMap insert | CAS + tombstone mgmt | clone O(n) |
| Memory per entry | ~50 bytes | ~40 bytes | ~50 bytes | ~24 bytes | ~50 bytes × 2 |
| Reclamation | HashMap owns | seize | HashMap owns | seize | seize |
| Resize | Автоматический | При open или write lock | Автоматический | Сложный (lock-free) | Автоматический |
| Сложность реализации | Есть | Средняя | Тривиальная | Высокая | Тривиальная |
---
## Когда lock-free Map оправдан
- **Read-heavy, высокая конкурентность** — десятки потоков читают один шард. Mutex ~20ns uncontended, но под contention — спинлок, context switch, tail latency растёт. Lock-free читатели не блокируют друг друга и не блокируют писателей.
- **Жёсткие требования к tail latency** — p99/p999. Mutex может дать spike при совпадении read+write на одном шарде. Lock-free — предсказуемые ~5ns всегда.
- **Единообразие архитектуры** — один паттерн (seize + atomic) для Tree и Map. Проще поддерживать, один набор примитивов.
## Когда лучше остаться на HashMap per shard
- **Мало потоков / низкая contention** — при 8+ шардах и равномерном распределении вероятность столкновения на одном шарде мала. Uncontended `parking_lot::Mutex` = ~20ns, экономия ~15ns на read не оправдывает сложность.
- **Cache locality важнее** — Rust `HashMap` (hashbrown / Swiss Table) хранит данные компактно в одном массиве. Chained buckets — pointer chasing, каждый node — отдельная аллокация, промахи L1/L2 кэша. Для маленьких map'ов HashMap быстрее даже с мьютексом.
- **Write-heavy нагрузка** — если writes сопоставимы с reads, мьютекс всё равно берётся для disk append. Экономия на read path теряется на фоне write overhead. А concurrent map добавляет alloc Node + CAS на каждый write.
- **Память** — seize откладывает освобождение (deferred reclamation). Под нагрузкой живые guard'ы задерживают retire — кратковременный рост потребления памяти. HashMap освобождает сразу при remove/resize.
- **Простота и корректность** — `Mutex<HashMap>` — 5 строк, проверено годами. Concurrent hash map на raw pointers + seize — сотни строк unsafe, тонкие баги с ordering, ABA, resize. Каждый баг в concurrent структуре данных — потенциальный use-after-free.
---
## Оценка для armdb
| Фактор | Вес | Направление |
|---|---|---|
| Map выбирают ради O(1) point lookups, не ради concurrency | Высокий | Против lock-free |
| Шардов `num_cpus * 2` — contention и так низкая | Высокий | Против |
| VarMap read = mutex + возможный disk I/O — 15ns на фоне микросекунд pread | Средний | Против |
| ConstMap read = mutex + memcpy inline value — 15ns это ~50% overhead | Средний | За |
| Проект уже использует seize, паттерны знакомы | Низкий | За |
| Больше unsafe кода для поддержки | Высокий | Против |
---
## Вывод
Для текущих use cases (point lookups, достаточно шардов) HashMap per shard скорее всего достаточен.
Lock-free Map имеет смысл если появится кейс с десятками потоков-читателей на ConstMap и жёсткими требованиями к p99 latency. Без такого кейса — premature optimization.
Если решим реализовывать — **Вариант 1 (Concurrent HashMap на seize с chained buckets)**. Архитектурно это зеркало того, что SkipList делает для Tree — только вместо tower с уровнями используется flat bucket array с цепочками. Паттерны RCU-swap для update и retire через seize идентичны. Если load factor заранее известен (через `estimated_items` в Config), resize может не понадобиться вовсе — allocate buckets при `open()` с запасом 2x.