armdb 0.15.1

sharded bitcask key-value storage optimized for NVMe
Documentation
# SegMap и SegTree Q&A

Сегментированные коллекции предназначены для больших объёмов преимущественно
неизменяемых данных, когда все ключи не помещаются в RAM. Здесь собраны ответы
о текущей реализации, оставшихся этапах, удалённом хранении и глобальном индексе.

**Состояние на 2026-10-09, `main` на `ae192138`.** Реализованные возможности
отделены от предложений для будущих этапов. Вопросы про «seq коллекции» ниже
относятся к `SegMap` и `SegTree`; `SeqGen` и `WriteKey::Sequence` — другой
механизм, генерация последовательных ID.

## Что уже реализовано

| Этап | Возможности |
|---|---|
| 1. Локальное хранение | `SegMap`, журнал активного поколения, заморозка и фоновая упаковка в неизменяемые сегменты, фильтры, кеш, recovery, retention целыми сегментами, `verify`, интеграция с `Db`, RPC, Inspector и schema. |
| 2. Транзакции и проекции | Участие в `db.tx()` вместе с обычными коллекциями: `put`, `insert`, `delete`, `upsert`, `guard`; crash recovery; источник вторичных индексов, счётчиков и change streams. |
| 3a. Упорядоченная коллекция | `SegTree`: диапазоны, префиксы, прямой и обратный обход, `first`, `last`, страницы значений и ключей, префиксные фильтры. |
| 3b. Вторичные индексы | `SegTree` как индексная коллекция: транзакционное обновление, первоначальное построение, миграции, состояния pending/ready/retired, проверка и исправление в заданных бюджетах. |
| 7a. Постраничные метаданные | `resident_metadata_bytes`, постраничное чтение фильтров и индексов, кеш метаданных, поддержка старых сегментов, временные подсказки для чтения и записи. |

Исправления после 7a, включая задачи #198 и #199, вошли в `main` через #202.
Подробные контракты находятся в [руководстве по сегментированным коллекциям](segmented.md).

## Доступны ли эти коллекции в выпущенной версии

По [текущему changelog](../CHANGELOG.md) это **Unreleased 0.15.0**.
Релизная ветка `0.14.x` сегментированных коллекций не содержит. Включение
в исходниках требует фичи `segmented`, которая не входит в default features.
Указание `0.14.0` в старых спецификациях — историческая цель релиза.

## Какие крупные этапы остались

| Этап | Содержание |
|---|---|
| 4. Репликация | Поток активных записей и передача готовых сегментов. |
| 5. Сжатие и шифрование | Поддержка сжатых и зашифрованных блоков; сейчас для неё только зарезервированы поля формата. |
| 6. Удалённое хранение | S3-compatible tier, публикация объектов, локальный кеш и чтение удалённых данных. |
| 7b. Глобальный дисковый индекс | Поиск нужного сегмента по ключу без проверки всей истории, включая проверку отсутствия ключа. |

Границы этапов зафиксированы в [дорожной карте исходной спецификации](../../docs/superpowers/specs/26-09-29-segmented-append-only-collection.md#scope-one-part-of-seven).

## Какие ограничения есть у текущей реализации

- `len()` — верхняя граница числа видимых записей, учитывающая физическую
  историю. Точный подсчёт требует обхода.
- Отдельные старые версии и tombstones не собираются: компакции сегментов
  нет. Место освобождается при удалении целого сегмента.
- Источники индексных и счётчиковых проекций, а также индексные `SegTree`
  не допускают retention. При частых изменениях их физическая история растёт.
- Транзакции дают crash-атомарность, но не единый атомарный снимок для
  конкурентных читателей. Обходы с конкурентными изменениями слабо согласованы.
- Нет per-row TTL, watches, unique-source claims, публичного `Scope`,
  транзакционного удаления диапазона и facade-методов `update`, `cas`, `atomic`.
  Транзакционные `upsert` и `guard` поддерживаются.
- Потоковая проверка индексов, превышающих бюджеты schema validation, отложена.
  Такие цели получают `IndexUnchecked`, а `repair` их пропускает.
- В руководстве отдельно отмечен цикл владения для источника change stream:
  закрытие и удаление `Db` не гарантируют освобождение всех связанных handles
  и workers для повторного открытия в том же процессе.

Эти ограничения не означают, что все перечисленные возможности включены в
ближайший план. Контракты: [транзакции](segmented.md#transactions-and-projections),
[индексные коллекции](segmented.md#segtree-as-an-index-target),
[SegTree](segmented.md#byte-ordered-segtree).

## Какой масштаб действительно проверен

Есть настоящий прогон `SegMap` на **2 334 000 000 физических записей в 389
сегментах** для режима с метаданными в RAM, включая холодные чтения и проверки
восстановления. Это отдельный [полномасштабный отчёт](benches/26-10-02-segmented-full-window.md).

Для 7a измерены три корпуса по **20 млн записей**: два варианта `SegMap` и
`SegTree` с префиксным фильтром. Критерий чтения выбранного холодного сегмента
за ≤5 мс на NVMe при действительно холодном OS page cache остаётся
**UNVERIFIED / MANUAL**. Сброс кеша движка не заменяет сброс кеша ОС.

Оценка 7a для **10 млрд записей** — расчёт, а не измеренный корпус.
Она не подтверждает пиковую память при seal/recovery/migration, время запуска
или достаточность лимитов файловых дескрипторов на таком масштабе.
См. [отчёт 7a](benches/26-10-05-segmented-paged-metadata.md) и
[границы оценки памяти](segmented.md#sizing).

## Все ли методы коллекций сейчас синхронные

Да. Публичные методы `SegMap` и `SegTree` синхронные: чтение, запись, страницы,
итераторы, flush и ожидание seal. Например, `try_get` возвращает
`DbResult<Option<T>>`, а `page` — `DbResult<Page<K, T>>`.

Наличие фонового worker для seal не делает вызываемые методы асинхронными.
Сигнатуры: [SegMap](../src/seg/map.rs), [SegTree](../src/seg/tree.rs).

## Требует ли S3 перевести все методы на async

Нет. Это зависит от роли удалённого хранилища и поведения при промахе локального
кеша.

| Роль S3 | Последствия для API |
|---|---|
| Архивная копия при сохранении необходимых данных локально | Методы могут остаться sync, загрузка объектов идёт в фоне. |
| Холодные данные удаляются локально, sync-чтение скачивает их по запросу | API можно сохранить, но вызывающий поток блокируется на сети. |
| Холодные данные читаются без блокировки вызывающего потока | Нужен async-путь для операций, способных обратиться к S3. |

Для полноценного удалённого слоя возможное направление — сохранить локальный
sync API и добавить async-фасад. Это **предложение для будущего дизайна**,
а не утверждённый контракт или существующая реализация.

- `try_get`, `contains`, `page`, `first` и `last` потенциально ждут сеть.
  Попадание в кеш может завершать ту же async-операцию немедленно.
- Для обхода подходят async-страницы или `Stream`: обычный `Iterator::next()`
  не умеет приостанавливаться через `.await`.
- `len`, `stats` и чтение конфигурации могут оставаться sync.
- Записи в локальный журнал могут оставаться sync, если их подтверждение
  не требует загрузки в S3. Но `insert` и операции с чтением старого значения
  потенциально обращаются к удалённой истории.

Сама обёртка `async fn` вокруг блокирующего вызова не устраняет блокировку.
Внутри нужны асинхронный I/O либо выполнение блокирующей работы в ограниченном
пуле потоков.

## Почему S3 затрагивает транзакции

Сейчас `insert`, `upsert`, `guard` и вычисление проекций могут читать старые
значения из сегментов под блокировками участников транзакции. С S3 это может
стать ожиданием сети с удержанием блокировок других коллекций.

`.await` освобождает поток исполнения, но не удерживаемые блокировки.
Простая замена сигнатур на `async fn` этот вопрос не решает.

Один возможный дизайн — загрузить и закрепить необходимые данные до захвата
блокировок, затем под блокировками проверить актуальность подготовленного
состояния. Если состояние изменилось, повторить подготовку до записи commit
в лог. Это требует отдельного протокола проверки; просто отпустить блокировки
между чтением и записью нельзя. Такой повтор не разрешает повторять транзакцию
после `TxFailedAfterLog`.

Текущий контракт чтений под блокировками описан в
[руководстве по транзакциям сегментированных коллекций](segmented.md#transactions-and-projections).

## Что ещё нужно для S3 кроме async

Удалённый слой требует собственного протокола:

- загрузить объект, проверить доступность и целостность, durably опубликовать
  манифест и только затем разрешить удаление локальной копии;
- объединять одинаковые запросы, поддерживать prefetch, ограничивать кеши,
  параллелизм, таймауты и повторные попытки;
- различать отсутствие ключа и недоступность хранилища;
- согласовать физическое удаление объектов с читателями, recovery и репликами;
- явно определить подтверждение записи: локальный WAL, реплики и загрузка
  в S3 дают разные гарантии. Текущая `.durable()` означает локальный fsync,
  а не сохранение в S3.

Общая копия данных в S3 сама по себе не обеспечивает репликацию активных
изменений, выбор лидера или защиту от двух писателей. Эти требования описаны
в [исходном исследовании](../../docs/research/26-09-14-segmented-append-only-collection.md).

## Чем отличаются 7a и 7b

| | 7a | 7b |
|---|---|---|
| Основная задача | Ограничить RAM для метаданных | Сократить число проверяемых сегментов при поиске ключа |
| Структура | Постраничные фильтры и индексы каждого сегмента | Глобальный дисковый routing index, концептуально `ключ → сегмент` |
| Промах без временной подсказки | Проверка всех подходящих слоёв; стоимость растёт с числом холодных сегментов | Цель — избежать полного обхода истории |
| Состояние | Реализовано | Нужна отдельная спецификация |

7a оставляет небольшой resident skeleton, дескрипторы и запись манифеста на
каждый сегмент. Поэтому суммарная память всё ещё зависит от числа сегментов,
хотя полные фильтры и индексы больше не обязаны помещаться в RAM.

Граница сформулирована в [Goal и Scope спецификации 7a](../../docs/superpowers/specs/26-10-05-segmented-paged-metadata.md#goal).

## Почему 7b вынесли отдельно

Решение D1 в 7a явно выбирает постраничные метаданные первым этапом и отдельную
спецификацию для 7b. Первой задачей было снять ограничение по памяти, особенно
для проецирующих источников и индексных коллекций, где retention запрещён.

7a сохраняет семантику поиска и существующие файлы: новые сегменты получают
необязательную секцию `PAGE_INDEX`, для старых метаданные подготавливаются без
перезаписи файлов. Это самостоятельный результат без глобального изменяемого
индекса и нового протокола его публикации.

Для работы с недавними данными добавлены `Tx::written_since` и
`insert_hinted`. Они позволяют пропускать старые слои, если приложение может
обосновать временную границу. Это доверенное утверждение: неверная подсказка
может скрыть существующий ключ, оставить старые индексные записи, исказить
счётчик или решение `guard`.

Следовательно, подсказки помогают определённым сценариям, но не заменяют 7b
для произвольных запросов по всей истории. Спецификация принимает линейную
стоимость поиска без подсказки явно. См. [решения D1 и D11](../../docs/superpowers/specs/26-10-05-segmented-paged-metadata.md#decisions)
и [архитектурное ревью](../../docs/superpowers/reviews/26-10-05-segmented-paged-metadata-gpt-6-codex-review.md#alternative-e--add-routing-or-compaction-when-whole-history-probes-matter).

## В чём сложность глобального индекса 7b

**Последняя версия и tombstones.** Пусть старый сегмент содержит `K → value`,
а новый — tombstone для `K`. Указатель на старый сегмент воскресит удалённую
запись. Ещё более свежая версия может находиться в активном или замороженном
поколении. Сейчас правильность обеспечивает обход слоёв от новых к старым,
с остановкой на первой записи, включая tombstone. Глобальный индекс должен
сохранить этот результат.

**Публикация и recovery.** К файлам сегмента и манифесту добавляется состояние
индекса. После сбоя нельзя считать ответ неполного индекса «ключа нет»
достоверным. Нужно выбрать протокол согласования, способ восстановления и
поведение до его завершения. Восстанавливаемый производный индекс возможен,
но его неполноту тогда надо обнаруживать и безопасно обрабатывать.

**Retention и очистка.** После удаления сегмента остаются ссылки на него.
При очистке нельзя удалить уже обновлённый указатель того же ключа на новый
сегмент. Обработка ключей, перестроение или другой механизм удаления
устаревших записей добавляют работу и амплификацию записи.

**Размер и обслуживание структуры.** Для миллиардов ключей надо выбрать
формат, обработку коллизий, кеширование, первоначальное построение, обновления
и восстановление. Исходный research оценивал компактный вариант примерно
в 16 байт на ключ: около 160 GB для 10 млрд ключей до накладных расходов
конкретной реализации. Это предварительная оценка, а не согласованный формат
или обещание стоимости lookup. Готовый дисковый KV-движок может предоставить
саму структуру, но согласование с жизненным циклом сегментов всё равно нужно.

Согласованность новых версий, tombstones, публикации и recovery прямо названа
причиной отдельного дизайна в [ревью 7a](../../docs/superpowers/reviews/26-10-05-segmented-paged-metadata-gpt-6-codex-review.md#alternative-e--add-routing-or-compaction-when-whole-history-probes-matter).
Оценка размера и проблема очистки — из [исходного исследования](../../docs/research/26-09-14-segmented-append-only-collection.md).

## Когда 7b особенно нужен и решит ли он все медленные запросы

7b особенно важен для частых поисков произвольного хэша за всю историю,
промахов и проверок существования без временной подсказки. Проверка отсутствия
нужна также успешной вставке нового ключа; при чтении старых значений внутри
транзакции полный обход может задерживать другие записи.

Для работы преимущественно с недавним окном 7a и корректные временные подсказки
уже дают самостоятельную пользу. Выбор приоритета 7b зависит от доли запросов
без подсказки и требуемых задержек на реальной нагрузке.

Hash-index для точечных запросов не ускоряет автоматически префиксные и
диапазонные обходы `SegTree`. Для них потребуется отдельное решение, сужающее
набор подходящих сегментов. Компакция также может уменьшать число кандидатов
и объём старых версий, но замена сегментов, время жизни читателей и дисковые
бюджеты требуют собственной спецификации.