Предложение: гибридная архитектура на базе журналирования (WAL) + персистентного индексного дерева (COW-B-tree или persistent B-tree) + пер-ключевых цепочек версий (version chains / value-log). Это даёт дешёвые записи (аппенд), быстрые point- и range-исторические чтения и управляемый GC/компакцию.
1) основные структуры данных
- Журнал (WAL / append-only log): последовательность изменений (дописываемых записей) с монотонным монетизированным идентификатором версии/LSN $t$. Каждая запись: $(key,delta\_type,value,LSN=t)$.
- Value-log / per-key version chain: для каждого ключа хранится связный список версий (или оффсет в value-log), каждая версия содержит $(LSN,value,prev\_offset)$. Для ускорения поиска добавляются skip-поинты через каждые $2^k$ версий (уровни как в skip-list) или блоковые индексы.
- Персистентное индексное дерево (copy-on-write B-tree / ART / LSM+immutable SST): снабжает корневые указатели (snapshot roots) для конкретных LSN. При фиксировании контрольной точки (checkpoint/commit) сохраняется root pointer с LSN.
- Sparse checkpointing (snapshot): полная или инкрементальная снимок состояния в корневом указателе дерева для ряда LSN $t_0<t_1<\dots$.
- Метаданные: таблица active snapshots (LSN), мапа key -> latest_version_offset (для быстрой актуализации).
2) операции записи (алгоритм)
- Присвоить commit LSN $t$ (монотонно возрастающий).
- Записать в WAL запись $(key,value,LSN=t)$ (append-only) — $O(1)$.
- Создать новую запись в value-log: записать $(LSN=t,value,prev=old\_offset)$, обновить index key->new\_offset — атомарно.
- Обновить индексное дерево: если используется COW-B-tree, изменить соответствующие узлы по пути к ключу копированием узлов (copy-on-write) и записать новый root; если LSM-подход — поместить запись в memtable, позже сливаете в immutable SST.
- Возвращаем успех. Амортизированная сложность записи: append $O(1)$ + индексное обновление $O(\log n)$ (при COW-B-tree/LSM).
3) point historical read для времени $t_q$ Вариант A — per-key version chain (лучше для точечных запросов):
- Найти latest offset для ключа.
- По цепочке версий идти по prev указателям, используя skip-поинты / блоковый индекс, чтобы найти версию с наибольшим LSN $\le t_q$. Это бинароподобный поиск по уровням.
- Сложность: $O(\log v)$, где $v$ — число версий ключа; при skip-поинтах — $O(\log v)$.
Вариант B — snapshot + apply deltas:
- Найти ближайший checkpoint с LSN $t_s\le t_q$.
- Взять значение из tree-root для $t_s$.
- Применить дельты из журнала или инкрементальных файлов между $t_s$ и $t_q$ только для интересующих ключей.
- Сложность: $O(\log n+d)$, где $d$ — число дельт применяемых к ключу.
4) range/time-travel read (восстановление состояния множества ключей на $t_q$)
Вариант A — персистентное дерево:
- Если сохранён root для LSN $t_q$ (или ближайший root $t_s\le t_q$ и применимо инкрементально), читать дерево как обычное B-tree: каждый поиск/итерация — $O({\log }_{B}n)$ (B — фактор ветвления).
- Для полного сканирования состояния на $t_q$ читать дерево/файлы, игнорируя версии с LSN $>t_q$ (версионирование на узлах или ключах).
Вариант B — LSM-стиль / SSTables с versioned keys:
- Встроенные immutable файлы содержат ключи с версиями $key@LSN$; при range-скане делаем k-way merge по файлам, выбирая для каждого ключа максимальный LSN $\le t_q$.
- Сложность: амортизированная — $O((r+\log n)\cdot \text{merge\_cost})$, где $r$ — количество возвращаемых записей.
5) создание снимков и оптимизация чтения
- Частые полные снапшоты дают быстрые исторические чтения: чтение на $t_q$ — просто загрузить root для ближайшего $t_s$ и применять малое количество дельт. Параметризация: делать snapshot каждые $T$ времени/каждые $K$ изменённых страниц.
- Альтернатива — хранить последовательность immutable roots (каждый коммит в COW-B-tree сохраняет root) и доступ по LSN: точечное чтение на $t_q$ выполняется через корень соответствующего LSN без дельт.
6) уборка историй (GC / retention)
- Хранить минимальный LSN, необходимый активными snapshot’ами (min_retained_LSN). Можно проводить:
- Обратную ссылочную очистку: считать ссылки на версии из каждой snapshot root; пометить недостижимые версии и удалять value-log записи.
- Compaction (LSM): слияние SSTables, отбрасывание версий с LSN < retention_threshold.
- GC сложность зависит от объёма удаляемых данных; делается бэкграундом и аккуратно, чтобы не блокировать точечные чтения.
7) согласованность и транзакции
- Присваивайте каждой транзакции commit LSN и обеспечьте snapshot-isolation: чтения на LSN $t_q$ видят все версии с LSN $\le t_q$.
- Механизм блокировок не обязателен при append-only подходе; для индексов — оптимистическая синхронизация или COW.
8) характеристики и сложности (оценочные)
- Запись (append + index update): амортизированно $O(1)+O(\log n)$ → записать как $O(\log n)$.
- Point historical read (per-key chain): $O(\log v)$.
- Point historical read (snapshot + deltas): $O(\log n+d)$.
- Range historical read (persistent tree): $O({\log }_{B}n)$ для поиска, сканирование — $O(r)$.
Записать как KaTeX:
- запись: $O(\log n)$ - point read (chain): $O(\log v)$ - range read (tree): $O({\log }_{B}n+r)$
9) рекомендации по выбору
- Большинство точечных исторических запросов и очень частых записей: per-key version chains + skip-поинты + периодические чекпойнты.
- Частые исторические range-запросы (полные снимки): COW-persistent B-tree с сохранением корней по LSN.
- Высокая нагрузка на запись + batch-компакция: LSM-подход с versioned SSTables и периодическим compaction/GC.
- Всегда поддерживайте метаданные active-snapshots, retention-policy и background compaction/GC.
Краткая итоговая архитектура (рекомендуемая практическая):
- WAL + value-log (per-key chains) для дешёвых записей.
- COW-B-tree или snapshotable root для периодических снимков (быстрые полные исторические чтения).
- Background compaction/GC и skip-поинты для ускорения поиска в цепочках версий.
- Согласованность через монотонный LSN и snapshot-isolation.
Если нужно — могу дать детализированную структуру записей в value-log и конкретный алгоритм поиска в skip-поинтах или пример COW-B-tree интерфейса.