# Итераторы коллекций armdb
## Обзор
Упорядоченная итерация **всегда** доступна для **Tree**-коллекций (индекс SkipList):
ConstTree, VarTree, TypedTree, ZeroTree.
**Map**-коллекции могут подключить итерацию через `Config::iterable(true)` (или
`FixedConfig::iterable(true)`), что создаёт per-shard companion key index (`BTreeSet`).
Локальные вызовы для Map используют `iter_view()`; RPC-вызовы — `First`/`Last`/`Range`/`RangeKeys`.
Map-сканы предназначены для редких административных и maintenance-задач. Они **weakly consistent**:
шардовые блокировки снимаются между батчами, поэтому конкурентные записи могут быть видны
частично. Tree-сканы тоже weakly consistent и **не** являются point-in-time snapshot.
| `iter()` / `iter_view().iter()` | Все записи | полный обход |
| `range(start, end)` | Диапазон `[start, end)` | включая start, исключая end |
| `range_bounds(start, end)` | Диапазон с произвольными `Bound` | `Included`, `Excluded`, `Unbounded` |
| `prefix_iter(prefix)` | Ключи с заданным префиксом | автоматические границы |
Tree-итераторы реализуют `Iterator` + `DoubleEndedIterator`. Map-итераторы через
`iter_view()` — только `Iterator` (однонаправленный обход по шардам).
---
## Типы итераторов
| ConstTree | `ConstIter<'a, K, V>` | `(K, [u8; V])` — копия | нет |
| VarTree | `VarIter<'a, K, H>` | `(K, ByteView)` — RC | возможен (cache miss) |
| TypedTree | `TypedIter<'a, K, T>` | `(K, TypedRef<'a, T>)` — guard | нет |
| ZeroTree | `ZeroIter<'a, K, V, T>` | `(K, T)` — копия | нет |
| TypedMap | `TypedMapIterView` → `TypedMapIter` | `(K, TypedRef<'a, T>)` — guard | нет |
| ZeroMap | `ZeroMapIterView` → `iter()` | `(K, T)` — копия | нет |
| VarTypedMap | `VarTypedMapIterView` → `VarTypedMapIter` | `(K, T)` — decode | возможен (cache miss) |
Операции только по ключам (`keys()`, `keys_range()`, `keys_prefix()` и RPC `RangeKeys`)
обходят companion `BTreeSet` без материализации значений.
### Возврат значений
- **ConstTree** — `[u8; V]` копируется из inline SeqLock (`node.read_value()`)
- **VarTree** — `ByteView` читается через `read_value_cached(&disk)`, при промахе block cache — pread с диска
- **TypedTree** — `TypedRef<'a, T>` на значение в `TypedData`; каждая строка несёт
**собственный** seize guard, поэтому пережившая итератор строка остаётся валидной
(issue #123)
- **ZeroTree** — обёртка над `ConstIter`, `[u8; V]` → `T` через zerocopy (`from_value_bytes`)
- **TypedMap** — `TypedRef<'a, T>` под seize guard; `iter_view()` возвращает `None` без `iterable(true)`
- **ZeroMap** — `T` копируется из inline `[u8; V]` через zerocopy
- **VarTypedMap** — `T` декодируется из `ByteView` при каждом шаге; при промахе block cache — pread
---
## Структура итератора
Все итераторы (кроме ZeroIter) имеют одинаковую структуру:
```rust,ignore
pub struct ConstIter<'a, K: Key, const V: usize> {
list: &'a SkipList<ConstNode<K, V>>,
front: *mut ConstNode<K, V>, // указатель вперёд
back: *mut ConstNode<K, V>, // указатель назад
end: Bound<K>, // верхняя граница (forward)
start: Bound<K>, // нижняя граница (backward)
reversed: bool, // флаг обратного порядка
done: bool, // front == back — итерация завершена
_guard: seize::LocalGuard<'a>, // предотвращает reclamation нод
}
```
`ZeroIter` — тонкая обёртка:
```rust,ignore
pub struct ZeroIter<'a, K: Key, const V: usize, T> {
inner: ConstIter<'a, K, V>,
_marker: PhantomData<T>,
}
```
`VarIter` отличается тем, что хранит `tree: &'a VarTree<K, H>` вместо `list`,
чтобы читать значения через block cache.
---
## Алгоритм обхода
### next() — прямой обход
```text
loop:
converged = (front == back)
front = node.tower[0].next() // двигаем front вперёд
if converged → done = true
if node.is_marked() → skip // удалённая нода
if !check_end(node.key) → None // вышли за границу
return Some((key, value))
```
### next_back() — обратный обход
```text
loop:
converged = (front == back)
back = back_step(key) // двигаем back назад
if converged → done = true
if node.is_marked() → skip
if !check_start(node.key) → None
return Some((key, value))
```
Асимметрия: `next()` использует `tower[0].next()` (O(1)). Начальный обратный
seek заполняет read-only predecessor staircase и ожидаемо стоит O(log n); затем
обход из `m` строк ожидаемо/амортизированно стоит O(log n + m) при геометрическом
распределении башен `p = 0.25`. В топологии, где все башни имеют высоту 1,
возможен откат к прежней стоимости поиска.
### Конвергенция
Когда `front == back`, итератор устанавливает `done = true`. После этого и `next()`, и `next_back()` возвращают `None`. Это предотвращает повторную выдачу элемента.
---
## Reversed ordering
По умолчанию `Config::reversed = true` — SkipList хранит ключи в обратном порядке (компаратор `b.cmp(a)`).
| true (default) | descending | ascending |
| false | ascending | descending |
Проверка границ учитывает `reversed`:
```rust,ignore
// check_end (forward direction)
fn check_end(&self, key: &K) -> bool {
match &self.end {
Bound::Unbounded => true,
Bound::Excluded(end) => {
if self.reversed { key > end } else { key < end }
}
Bound::Included(end) => {
if self.reversed { key >= end } else { key <= end }
}
}
}
```
---
## Prefix search
`prefix_iter(prefix)` вычисляет границы через `prefix_bounds()`:
**reversed = false:**
- `search_key` = prefix + `0x00` padding → первый ключ с этим префиксом
- `end` = `prefix + 1` (инкремент последнего байта) как `Excluded` bound; если overflow (все `0xFF`) — `Unbounded`
**reversed = true:**
- `search_key` = prefix + `0xFF` padding → последний ключ с этим префиксом
- `end` = prefix + `0x00` padding как `Included` bound
```rust
// Пример: prefix = [0x01]
// reversed=true:
// search = [0x01, 0xFF, 0xFF, ...] — ищем от конца группы
// end = [0x01, 0x00, 0x00, ...] — до начала группы (Included)
// reversed=false:
// search = [0x01, 0x00, 0x00, ...] — ищем от начала группы
// end = [0x02, 0x00, 0x00, ...] — до следующей группы (Excluded)
```
---
## Scopes — типизированные префиксы и диапазоны
Для ключей с `KeyScheme::Typed` предпочтительный способ задать префикс по границе
поля — `scope::<N>()` и `range::<M>()`. Они работают на всех одиннадцати
упорядоченных семействах (Tree, Map, LsmTree) через общий `OrderedScan`-шов.
```rust,ignore
let scope = tree.scope::<2>(&SpaceActivityKey { space_id, user_id, ..zeroed() });
let rows: Vec<_> = scope
.range::<3>(lower.as_ref(), upper.as_ref())
.iter()
.collect();
// Map — только при Config::iterable(true)
let Some(scope) = map.scope::<2>(&key) else { /* not iterable */ };
let page = scope.asc().page(after.as_ref(), 50);
```
### Поле-гранулярный префикс и диапазон
- **`scope::<N>(&key)`** — все ключи, совпадающие с первыми `N` полями `key`.
Поля `[N..)` в `key` игнорируются; `scope::<0>()` — вся коллекция.
- **`range::<M>(start, end)`** — сужает scope парой `Bound` с насыщением хвоста
(см. таблицу ниже). Повторный вызов `range` на том же scope **заменяет** границы,
а не пересекает их; префикс scope не меняется.
- **`asc()` / `desc()`** — направление обхода как вход скана, а не `Iterator::rev()`.
- **`iter()` / `keys()`** — полный обход или только ключи (`keys()` не читает значения).
- **`page(after, limit)`** / **`page_by(after, limit, f)`** — cursor-пагинация;
`page_by` добирает до `limit` при отсеве строк через `Ok(None)`.
На Map `scope::<N>()` возвращает `Option<Scope>` — `None`, если коллекция открыта
без `iterable(true)`.
### Bulk range operations
`Scope` also provides synchronous bulk operations over the same typed prefix or
range:
- `delete_all()` removes every key the forward cursor observes; `delete_up_to(n)`
removes at most `n` keys and returns resumable `Progress`;
- `count()` and `is_empty()` walk keys without decoding values, so corrupt rows
and TTL-expired rows that have not yet been swept still count;
- `retain(|key, value| ...)` reads strict owned rows and compare-deletes only
rejected rows that have not changed concurrently.
These operations are weakly consistent and non-atomic. A key inserted behind a
running cursor can survive. Map `is_empty()` initializes the ordered merge and
probes every non-exhausted shard before returning its first key or `None`.
Sources with a configured change stream or unique claim target reject
non-transactional mutation before scanning with `ChangeStreamRequiresTx` or
`UniqueIndexRequiresTx`; use `db.tx().delete_scope(...)` for those sources.
Transactional range deletion is delete-only in v1: there is no transactional
`retain` or transactional `count`.
`N` и `M` проверяются целиком в `const { … }` (`N < M <= fields`, плюс ширина
ключа / `KeyScheme::Typed`): нарушение роняет сборку вызывающего крейта, а не
рантайм. Const-eval такого блока выполняется на **мономорфизации**, то есть уже
в codegen, поэтому нарушение видят `cargo build` / `cargo test` / доктест — и
только если вызов действительно инстанцирован. Голый `cargo check` codegen не
запускает и сломанный `range::<M>` **не поймает**; CI, состоящий из одного
`cargo check`, для этого контракта бесполезен.
`Scope` реализует `Clone` + `Debug`, оба безусловно. `Debug` написан вручную:
`derive` потребовал бы `S::Key: Debug`, чего трейт `Key` не обещает (ключи armdb —
обычно zerocopy-структуры без `Debug`), поэтому ключи печатаются hex-байтами.
`OrderedScan` требует `Copy` (view над `&Coll`).
`page` / `page_by` берут `&self` и билдер **не** потребляют — `page` → `iter` на
одном scope работает без клона. Потребляют `self` только `iter()` / `keys()`,
поэтому клон нужен в обратном порядке: если итерация должна идти *до* пагинации.
`iter()` / `keys()` возвращают именованные типы (`TreeRowIter`, `MapKeyIter`,
`LsmRowIter`, …), экспортированные из корня крейта, — итератор можно положить в
поле структуры или вернуть из функции без TAIT.
### Объединение отсортированных источников и chunk-пагинация
`armdb::merge_sorted(dir, sources)` лениво объединяет однородные источники:
при создании не читается ни одна строка, а затем в heap держится не больше одной
головы на источник. Каждый источник уже обязан быть отсортирован в направлении
`Dir`; равные головы выходят стабильно, по возрастанию номера источника.
`coalesce_equal` вызывает reducer только для равных по `Ord` строк: первым
аккумулятором становится строка из источника с наименьшим индексом (source 0,
если он участвует в tie), а reducer обязан сохранить поля, определяющие порядок.
Для разных конкретных типов итераторов используйте `BoxedRows` и `boxed`.
Обе предпосылки — отсортированность источника и сохранение ключа порядка
в reducer — проверяются `debug_assert`: в release-сборке их нарушение молча даёт
неверный результат, поэтому тесты этих путей обязаны идти в debug.
Курсор применяйте к **каждому исходному** scope до `merge_sorted`, а не как
фильтр уже слитого потока: это не даёт следующей странице повторно пройти все
предыдущие строки.
```rust,ignore
let rows = armdb::merge_sorted(armdb::Dir::Desc, sources)
.coalesce_equal(|acc, next| acc.flags |= next.flags);
let page = armdb::page_chunks(
rows,
armdb::PageSpec { limit: 20, chunk: 20, max_examined: Some(200) },
|row| row.cursor_key(),
|chunk| load_related_rows_once(chunk),
|row, related| project_row(row, related),
)?;
```
`chunk` разумно держать равным `limit`: меньший вызывает `prepare` чаще,
больший готовит строки, до которых страница может не дойти. `max_examined`
ограничивает строки, вычитанные из **переданного** итератора, а не из его
источников: за одной строкой coalesced-merge может стоять сколь угодно длинный
прогон равных строк, поэтому сырая работа ограничена примерно
`k × max_examined`.
`page_chunks` нормализует `chunk` и присутствующий `max_examined` до как минимум
одной строки. `limit == 0` сразу возвращает `Filled` с пустыми `items` и без
курсора, не читая итератор и не вызывая closure (`Scope::page_by_chunks` при этом
не берёт `seize` guard и не делает seek, как и `page_by`). Иначе `Filled` несёт курсор
принятой заполняющей строки, `Exhausted` — `None`, а `BudgetExhausted` — курсор
последней просмотренной строки. `prepare` вызывается один раз на непустой chunk;
его prefetch-суффикс после заполнения страницы отбрасывается и при продолжении
после курсора готовится заново. Поэтому `prepare` должен быть только читающим
либо идемпотентным; ошибки `prepare`/`project` возвращают ошибку без частичной
страницы.
`Scope::page_by_chunks` создаёт тот же exclusive cursor-bounded scan, что и
`page_by`, и делегирует ему эту механику. Его `prepare` и `project` наследуют
контракт блокировок `Scope`: у Map lock отпускается между batch, у skiplist
`seize` guard удерживается всю пагинацию. Свободный `page_chunks` ничего не
обещает о lock'ах итератора: они остаются ответственностью вызывающего.
### Насыщение хвоста (tail saturation)
`range::<M>` сравнивает границы по первым `M` полям и заполняет хвост (поля `M..`)
в направлении bound:
| `Included(k)` как start | `0x00` | ≥ первых `M` полей `k` |
| `Excluded(k)` как start | `0xFF` | > первых `M` полей `k` |
| `Included(k)` как end | `0xFF` | ≤ первых `M` полей `k` |
| `Excluded(k)` as end | `0x00` | < первых `M` полей `k` |
| `Unbounded` | — | край scope |
Поля `[0..N)` bound-ключа тоже игнорируются — scope всегда подставляет префикс.
Значимые данные в bound-ключе несут только поля `[N..M)`.
### Стоимость направления по семействам
| Map (`iterable`) | бесплатно — `Dir` передаётся в `MapIterView`, k-way merge меняет компаратор |
| `LsmTree` | бесплатно — `LsmIter` уже двунаправленный, direction override вместо флага конфига |
| SkipList Tree | первый seek в противоположном направлении: ожидаемо **O(log n)**; скан из `m` строк: ожидаемо/амортизированно **O(log n + m)** — `next_back()` возобновляет read-only predecessor staircase; singly-linked, без `prev` |
Документируйте это при выборе `asc()` на DESC Tree или `desc()` на ASC Tree.
### Key-only и LSM
`keys()` обещает не читать значения:
- **SkipList Tree** — `SkipKeyIter` обходит ноды без `read_value_cached` / pread.
Наибольший выигрыш у VarTree / VarTypedTree.
- **Map** — companion `BTreeSet` через `keys_range_bounds` (как и раньше).
- **`LsmTree`** — `fjall::Guard::key()`; для key-value-separated keyspace значение
может не загружаться, для inline — выигрыша нет. Rustdoc не обещает универсальный win.
На частично битой коллекции `keys()` и `iter()` расходятся **по построению**:
codec-типизированные семейства (`VarTypedTree`, `VarTypedMap`, `LsmTree`) молча
пропускают строку, значение которой не декодируется, а `keys()` не декодирует
вообще и такую строку отдаёт. Курсор, пройденный через `keys()`, покрывает строки,
которые `page`/`iter()` пропустят.
### `scope::<N>` vs `prefix_iter(&[u8])`
Оба идут по одному пути `prefix_to_end_bound` → `range_bounds`, но назначение разное:
| **`scope::<N>(&key)`** | префикс по **границе поля** typed-ключа (`N <= fields.len()`) |
| **`prefix_iter(&[u8])`** | **escape hatch**: sub-field byte prefix (например первые 3 байта `Fuid`), частичный `Array(n)`, ключи `KeyScheme::Bytes`, любой ручной байтовый префикс |
`prefix_iter` **не deprecated** — 123+ существующих call site и случаи, которые
field-granular API выразить не может.
---
## Weakly-consistent семантика
Итераторы **не** создают point-in-time snapshot. Они являются weakly-consistent:
- Конкурентные вставки/обновления **могут быть видны** во время итерации
- Удалённые записи (marked nodes в Tree; CAS-удаления в Map) автоматически **пропускаются**
- `seize::LocalGuard` предотвращает reclamation памяти нод на время жизни Tree-итератора
- Map-итераторы снимают shard lock между батчами — снимок коллекции не гарантируется
---
## VarTree: disk I/O при итерации
`VarIter` — единственный итератор, который может выполнять disk I/O:
```rust,ignore
fn next(&mut self) -> Option<Self::Item> {
// ... обход SkipList ...
let disk = *node.load_disk();
match self.tree.read_value_cached(&disk) {
Some(value) => return Some((node.key, value)),
None => continue, // значение недоступно (compacted), пропускаем
}
}
```
При промахе block cache выполняется `pread` с диска. Для предзагрузки кэша используйте `warmup()`.
---
## Helper-методы
| ConstIter | `collect_vec()` | `Vec<(K, [u8; V])>` |
| TypedIter | `collect_vec()` | `Vec<(K, TypedRef<T>)>` |
| TypedIter / TreeRowIter | `for_each_ref(f)` | обход с `(K, &T)` без `TypedRef` на строку |
| VarIter | `collect_keys()` | `Vec<K>` — только ключи |
| VarIter | `collect_entries()` | `Vec<(K, ByteView)>` |
### `for_each_ref` — дешёвый скан TypedTree
Строка `TypedIter` несёт собственный seize guard (issue #123), и это стоит
≈3.5 ns на строку. Если строка не должна пережить скан, guard не нужен:
`for_each_ref` отдаёт `(K, &T)` в замыкание на время вызова, под guard самого
итератора.
```rust,ignore
let mut total = 0;
tree.scope::<2>(&key).desc().iter().for_each_ref(|key, value| {
if value.done { ControlFlow::Break(()) } else { ControlFlow::Continue(()) }
});
```
Ранний выход живёт внутри замыкания: адаптеры `Iterator` (`take`, `filter`, …)
возвращают тип-обёртку, у которой этого метода уже нет. Бенч `kv_ops`:
`scan/typed_tree/iter_take_100` — 686 ns через `Iterator`, 212 ns через
`for_each_ref`.
---
## Send safety
Итераторы держат `seize::LocalGuard`, который привязан к потоку, поэтому они
**не** `Send` — прежние `unsafe impl Send` для `ConstIter` / `VarIter` /
`TypedIter` были сняты как unsound. Значения `TypedRef<'a, T>` из `TypedIter` /
`TypedMap` тоже `!Send` по той же причине: чтобы отправить значение в другой
поток, скопируйте его (`clone_value()`).
---
## Стоимость операций
| `next()` | O(1), zero I/O | O(1) + возможен pread | O(1), zero I/O | O(1), zero I/O |
| `next_back()` | first: expected O(log n); m rows: expected/amortized O(log n + m), zero I/O | first: expected O(log n); m rows: expected/amortized O(log n + m) + возможен pread | first: expected O(log n); m rows: expected/amortized O(log n + m), zero I/O | first: expected O(log n); m rows: expected/amortized O(log n + m), zero I/O |
| `prefix_iter()` setup | O(log n) | O(log n) | O(log n) | O(log n) |
| `range()` setup | O(log n) | O(log n) | O(log n) | O(log n) |
---
## Примеры использования
### Полный обход
```rust,ignore
// ConstTree
for (key, value) in tree.iter() {
// key: [u8; K], value: [u8; V]
}
// TypedTree
for (key, user) in tree.iter() {
// key: [u8; K], user: &User
}
// ZeroTree
for (key, counters) in tree.iter() {
// key: [u8; K], counters: Counters (Copy)
}
```
### Prefix search — "последние N записей"
```rust,ignore
// Составной ключ: [user_id:8][post_id:8]
// reversed=true (default) → prefix_iter возвращает от новых к старым
let latest_posts: Vec<_> = tree
.prefix_iter(&user_id)
.take(20)
.collect();
```
### Range query
```rust,ignore
// Диапазон [start, end) — start включительно, end исключительно
let start = 5u64.to_be_bytes();
let end = 10u64.to_be_bytes();
for (key, value) in tree.range(&start, &end) {
// reversed=true → ключи 9, 8, 7, 6, 5
}
```
### range_bounds — произвольные границы
`range_bounds(start: Bound<&K>, end: Bound<&K>)` — обобщение `range()`.
Каждая граница может быть `Included`, `Excluded` или `Unbounded`.
`range(start, end)` эквивалентен `range_bounds(Bound::Included(start), Bound::Excluded(end))`.
```rust,ignore
use std::ops::Bound;
// (5, 10] — исключить 5, включить 10
let entries: Vec<_> = tree.range_bounds(
Bound::Excluded(&5u64.to_be_bytes()),
Bound::Included(&10u64.to_be_bytes()),
).collect();
// reversed=true → 10, 9, 8, 7, 6
// [5, 10] — включить обе границы
let entries: Vec<_> = tree.range_bounds(
Bound::Included(&5u64.to_be_bytes()),
Bound::Included(&10u64.to_be_bytes()),
).collect();
// reversed=true → 10, 9, 8, 7, 6, 5
// (5, ..) — от 5 исключительно до конца
let entries: Vec<_> = tree.range_bounds(
Bound::Excluded(&5u64.to_be_bytes()),
Bound::Unbounded,
).collect();
// (.., 10) — от начала до 10 исключительно
let entries: Vec<_> = tree.range_bounds(
Bound::Unbounded,
Bound::Excluded(&10u64.to_be_bytes()),
).collect();
```
### DoubleEndedIterator
```rust,ignore
// .rev() — обратный порядок
let oldest: Vec<_> = tree.prefix_iter(&user_id).rev().take(10).collect();
// Смешанный обход: next() + next_back()
let mut iter = tree.iter();
let first = iter.next(); // первый в порядке итерации
let last = iter.next_back(); // последний в порядке итерации
// Итератор схлопывается к центру
```
### VarTree — предзагрузка кэша
```rust,ignore
// Предзагрузить все значения в block cache перед итерацией
tree.warmup()?;
for (key, value) in tree.iter() {
// value: ByteView — без disk I/O после warmup
}
```