# Review: VarTree / VarNode — GLM 5.1

**Дата:** 2025-05-15
**Файлы:** `src/var_tree.rs`, `src/skiplist/node.rs`, `src/skiplist/mod.rs`, `docs/design.md`

---

## Обзор: дизайн VarTree / VarNode

Дизайн в целом очень грамотный и продуманный. Архитектура «in-memory SkipList + on-disk append-only + block cache» — классический LSM-подход, адаптированный под конкретные требования (O_DIRECT, seize-based reclamation, ByteView). Разделение на ConstTree/VarTree/TypedTree — правильное решение, избегающее overhead универсального контейнера.

### Что сделано хорошо

1. **RCU для DiskLoc** — `AtomicPtr<DiskLoc>` swap + seize retire — lock-free reads, shard lock только для writes. Это правильный паттерн.
2. **ByteView** — inline ≤20 байт, ref-counted heap для больших. Дешёвый clone, нет аллокаций на hot path для коротких значений.
3. **Block cache вместо value cache** — пространственная локальность, один miss кеширует данные для соседних записей.
4. **WriteHook как generic parameter** — zero overhead при NoHook, чисто compile-time.
5. **VarShard для atomic multi-key** — элегантный API, shard lock уже захвачен.

---

## Явные и потенциальные ошибки / проблемные места

### 🔴 1. `insert_locked` — TOCTOU race (key exists check → insert)

```rust
fn insert_locked(...) -> DbResult<()> {
    if self.index.get(key.as_bytes(), guard).is_some() {
        return Err(DbError::KeyExists);
    }
    // ^-- между этой проверкой и insert() другой поток может вставить тот же ключ
    //     (через другой шард, если shard_prefix_bits == 0, или через replication)

    let (disk_loc, _gsn) = inner.append_entry(...)?;
    let node_ptr = VarNode::alloc(*key, disk_loc, height);
    self.index.insert(node_ptr, guard);  // InsertResult игнорируется!
    Ok(())
}
```

**Проблемы:**
- `index.insert()` возвращает `InsertResult::Exists`, но результат **игнорируется**. Если между `get()` и `insert()` конкурентный `put` вставил тот же ключ — `insert_locked` вернёт `Ok(())`, хотя ключ уже существовал. Это нарушает семантику «insert only if not exists».
- Дополнительно: если `InsertResult::Exists` — выделенный `node_ptr` и записанный на диск entry **утекают** (node не освобождён, dead bytes не учтены).

**Сравни с `put_locked`** — там `InsertResult::Exists` обрабатывается корректно (swap disk + dealloc node). `insert_locked` должен делать то же самое, но возвращать `KeyExists`.

### 🔴 2. `read_value_locked` — не обрабатывает spanning values

```rust
fn read_value_locked(&self, disk: &DiskLoc, inner: &ShardInner) -> Option<ByteView> {
    // ...
    // 2. Block cache (lock-free)
    if start + len <= 4096 {
        // OK — value внутри одного блока
        if let Some(block) = self.cache.get(&cache_key) {
            return Some(ByteView::new(&block[start..start + len]));
        }
    }
    // ^-- если start + len > 4096, block cache ПОЛНОСТЬЮ ПРОПУСКАЕТСЯ
    //     даже если оба блока в кэше!

    // 3. Disk read — тоже не обрабатывает spanning
    let bytes = direct::pread_value(file, disk.offset as u64, len).ok()?;
    Some(ByteView::new(&bytes))
}
```

**Проблема:** Если значение пересекает границу 4096-байтного блока, `read_value_locked`:
1. Пропускает block cache (условие `start + len <= 4096` не выполняется)
2. Падает на disk read через `pread_value` — это работает, но **теряет преимущество кэша**

Это особенно болезненно для `cas()` и `update()` — они держат shard lock и при cache miss делают I/O под lock. Если у тебя есть spanning values, CAS/update всегда будут идти на диск, минуя кэш.

**Сравни с `read_value_cached`** — там `extract_from_block` корректно обрабатывает spanning через `next_block()`.

### 🟡 3. `read_value_cached` — write buffer check после cache miss не retry-ит cache

```rust
fn read_value_cached(&self, disk: &DiskLoc) -> Option<ByteView> {
    // 1. Block Cache — miss
    // 2. Write buffer — miss (данные уже flushed)
    // 3. Disk read + cache
    let block = self.get_or_read_block(...)?;
    // ^-- get_or_read_block сначала проверяет cache!
    //    Но мы уже проверили на шаге 1 и не нашли.
    //    Между шагом 1 и 3 другой поток мог заполнить кэш — это OK (двойной read не вреден)
}
```

Это не баг, но стоит отметить: между шагом 1 (cache miss) и шагом 3 другой поток мог заполнить кэш через `get_or_read_block`. Это не ошибка — просто дублирующий read. Но есть тонкость: **шаг 2 (write buffer) берёт shard lock**. Если данные уже на диске, lock берётся зря. Можно оптимизировать — проверять `file_id` против active file_id без lock (через AtomicU32 для active file_id).

### 🟡 4. `migrate` — unsafe traversal без защиты от concurrent remove

```rust
pub fn migrate(&self, f: impl Fn(&K, &[u8]) -> MigrateAction<ByteView>) -> DbResult<usize> {
    let _guard = self.index.collector().enter();
    let mut current = strip_mark(unsafe {
        (*self.index.head_ptr())
            .tower(0)
            .load(Ordering::Acquire)
    });
    while !current.is_null() {
        let node = unsafe { &*current };
        current = strip_mark(
            node.tower(0).load(Ordering::Acquire),
        );
        if node.is_marked() { continue; }
        let disk = *node.load_disk();
        let value = match self.read_value_cached(&disk) {
            Some(v) => v,
            None => continue,  // ← I/O error — skip entry silently
        };
        // ...
    }
}
```

**Проблемы:**
- `read_value_cached` возвращает `None` при I/O ошибке — entry молча пропускается. Для migrate это может быть проблемой: если блок повреждён, данные теряются без уведомления.
- Concurrent `put` может обновить `disk` между `load_disk()` и `read_value_cached()` — прочитается stale значение. Для weakly-consistent migrate это OK, но стоит задокументировать.
- `MigrateAction::Keep` вызывает `self.hook.on_write(&node.key, None, Some(&value))` — передаёт `None` как old_value, даже если hook'у нужен old_value (`NEEDS_OLD_VALUE = true`). Это может быть некорректно для hooks, которым нужно знать старое значение.

### 🟡 5. `VarIter::next_back` — O(log N) per call, но `find_last_lt` может быть неточным

```rust
fn next_back(&mut self) -> Option<Self::Item> {
    // ...
    self.back = Some(self.tree.index().find_last_lt(key.as_bytes()));
    // ^-- find_last_lt ищет последний узел СТРОГО МЕНЬШИЙ чем key
    //     Но при reversed=true "меньше" в list order = "больше" в natural order
    //     Это корректно, но есть нюанс:
}
```

При `reversed=true` `find_last_lt(key)` ищет узел с ключом **больше** key (в natural order). Это правильно для backward iteration. Но если между `next()` и `next_back()` конкурентный insert добавил узел между front и back — итератор может вернуть дубликат или пропустить запись. Это expected для weakly-consistent, но стоит явно задокументировать.

### 🟡 6. `prefix_to_end_bound` — overflow для prefix из 0xFF байт

```rust
fn prefix_to_end_bound<K: Key>(prefix: &[u8]) -> Bound<K> {
    let mut incremented = prefix.to_vec();
    let mut carry = true;
    for byte in incremented.iter_mut().rev() {
        if carry {
            if *byte == 0xFF {
                *byte = 0x00;  // carry continues
            } else {
                *byte += 1;
                carry = false;
                break;
            }
        }
    }
    if carry { Bound::Unbounded }  // ← если prefix = [0xFF, 0xFF, ...]
    else { ... }
}
```

Если prefix состоит полностью из `0xFF` байт — `carry` остаётся true и возвращается `Bound::Unbounded`. Это означает, что `prefix_iter(&[0xFF, 0xFF])` вернёт **все** записи с ключами >= `[0xFF, 0xFF]` без верхней границы. Это корректно математически, но может быть неожиданным для пользователя — prefix iter вернёт больше записей, чем ожидается.

### 🟡 7. `shard_for` — `K::zeroed()` аллокация на каждый вызов при `extra_bits > 0`

```rust
let mut buf = K::zeroed();
buf.as_bytes_mut()[..full_bytes + 1].copy_from_slice(&key.as_bytes()[..full_bytes + 1]);
```

`K::zeroed()` — это `MaybeUninit::zeroed().assume_init()` или аналогичное. Для ключа 16 байт — 16 байт на стеке, не проблема. Но если K большой (например 256 байт) — это лишний zero-fill. Можно просто хешировать `key.as_bytes()[..full_bytes + 1]` с маской, без создания `K::zeroed()`.

### 🟡 8. `first()` — guard дропается до `read_value_cached`

```rust
pub fn first(&self) -> Option<(K, ByteView)> {
    let guard = self.index.collector().enter();
    let mut ptr = strip_mark(unsafe {
        (*self.index.head_ptr()).tower(0).load(Ordering::Acquire)
    });
    while !ptr.is_null() {
        let node = unsafe { &*ptr };
        if !node.is_marked() {
            let disk = *node.load_disk();
            let _ = guard;  // ← guard "used" но не дропается явно
            return self.read_value_cached(&disk).map(|v| (node.key, v));
        }
        // ...
    }
    None
}
```

`let _ = guard;` — это идиома чтобы подавить warning о неиспользуемой переменной, но guard **не дропается** в этой точке (он жив до конца функции). Это OK — guard защищает node от reclamation пока мы читаем `disk`. Но после `return self.read_value_cached(...)` guard дропается, а `node.key` уже скопирован (K: Copy), так что это безопасно.

Однако есть тонкость: `node` — это `&VarNode<K>`, полученный через `unsafe { &*ptr }`. Если конкурентный `remove` + `retire` происходит **после** `load_disk()` но **до** возврата из `first()` — guard предотвращает reclamation. Это корректно.

### 🟢 9. `resolve_front_asc` и `resolve_front_rev` — идентичная реализация

```rust
fn resolve_front_asc(&self, bound: &Bound<&K>, guard: &seize::LocalGuard<'_>) -> *mut VarNode<K> {
    match bound {
        Bound::Included(k) => self.index.find_first_ge(k.as_bytes(), guard),
        Bound::Excluded(k) => {
            let ge = self.index.find_first_ge(k.as_bytes(), guard);
            if !ge.is_null() && !unsafe { &*ge }.is_marked() && unsafe { &*ge }.key_bytes() == k.as_bytes() {
                strip_mark(unsafe { (*ge).tower(0).load(Ordering::Acquire) })
            } else {
                ge
            }
        }
        Bound::Unbounded => strip_mark(unsafe {
            (*self.index.head_ptr()).tower(0).load(Ordering::Acquire)
        }),
    }
}

fn resolve_front_rev(&self, ...) -> *mut VarNode<K> {
    // ПОЛНОСТЬЮ ИДЕНТИЧНО resolve_front_asc
}
```

Это не баг, но дублирование. При `reversed=true` `find_first_ge` уже учитывает reversed comparator, так что логика одинакова. Можно оставить одну функцию или задокументировать, почему они разделены (если планируется diverge).

### 🟢 10. `VarNode::dealloc_node` — `disk.get_mut()` без синхронизации

```rust
unsafe fn dealloc_node(ptr: *mut Self) {
    let disk = *(*ptr).disk.get_mut();  // ← UnsafeCell::get_mut
    if !disk.is_null() {
        drop(Box::from_raw(disk));
    }
    // ...
}
```

Это вызывается только из `reclaim` (seize callback) или `Drop` — в обоих случаях гарантировано единоличное владение. Корректно.

---

## Резюме по приоритету

| Приоритет | Проблема | Влияние |
|-----------|----------|---------|
| 🔴 Критический | `insert_locked` игнорирует `InsertResult::Exists` — нарушает семантику insert-if-absent, утечка памяти | Некорректное поведение, memory leak |
| 🔴 Критический | `read_value_locked` не обрабатывает spanning values — CAS/update всегда идут на диск для больших значений | Performance degradation, latency под lock |
| 🟡 Средний | `migrate` молча пропускает I/O ошибки и передаёт `None` как old_value в hook | Потеря данных при migrate, некорректные hook notifications |
| 🟡 Средний | `prefix_to_end_bound` для all-0xFF prefix возвращает Unbounded | Неожиданно широкий результат prefix_iter |
| 🟡 Низкий | `resolve_front_asc` / `resolve_front_rev` дублирование | Code smell |
| 🟡 Низкий | `shard_for` лишняя аллокация `K::zeroed()` | Микро-overhead |
