Efim Beshmenev
139 lines
9.4 KiB
Markdown
139 lines
9.4 KiB
Markdown
# Архитектура
|
||
|
||
## Представления
|
||
|
||
`AdaptiveSequence<T>` хранит `variant<vector<T>, TieredStorage<T>>`.
|
||
Contiguous vector выгоден для малых последовательностей и индексного чтения.
|
||
Tiered storage состоит из независимо выделенных циклических leaf-блоков
|
||
(`RingBlock`) и многоуровневого каталога весов.
|
||
|
||
У обоих backend есть единая **логическая вместимость** `capacity()`. Это не
|
||
сумма физического slack в leaf-блоках, а управляющая граница, на которой
|
||
разрешена автоматическая O(N)-перестройка.
|
||
|
||
Текущий `TieredStorage` остаётся сегментированным исследовательским вариантом, а
|
||
не полной реализацией implicit tiered vector с offsets/carry на каждом
|
||
внутреннем узле. Offsets используются внутри leaf, но split/merge может менять
|
||
массив leaf-дескрипторов и перестраивать каталог за O(number_of_leaves). Это
|
||
ограничение нужно учитывать при интерпретации результатов.
|
||
|
||
## Текущая default-policy: перестройка только с capacity
|
||
|
||
`ResizePolicy` не пытается распознать workload после каждой операции. В
|
||
auto-mode представление и геометрия пересматриваются только вместе с изменением
|
||
логической вместимости:
|
||
|
||
1. Перед вставкой, которая не помещается, capacity удваивается до достаточного
|
||
значения. Для обычного роста это одна граница `C -> 2C`.
|
||
2. После удаления при `size <= capacity / 8`, то есть при заполнении не более
|
||
12.5%, capacity уменьшается на один шаг `C -> C/2` (но не ниже `size`).
|
||
3. Внутри той же перестройки выбираются mode, leaf geometry и размер hash
|
||
table. Между такими границами они остаются неизменными.
|
||
|
||
В auto-mode целевое представление определяется размером на момент перестройки:
|
||
|
||
```text
|
||
target_size < 4096 -> vector
|
||
target_size >= 4096 -> tiered
|
||
```
|
||
|
||
`4096` — cutoff, подтверждённый текущим focused-run 7 x 100000 для
|
||
`AdaptiveSequence<uint32_t, true>` и заданного mix; это не универсальный
|
||
результат для всех типов и workload. Само пересечение `size=4096` немедленного перехода не
|
||
вызывает: mode меняется только на следующей capacity-boundary. Например, при
|
||
обычном последовательном росте контейнер остаётся vector при capacity 4096 и
|
||
переходит в tiered, когда следующая вставка меняет capacity на 8192. На shrink
|
||
boundary правило применяется заново, поэтому возможен обратный переход
|
||
`tiered -> vector`.
|
||
|
||
Явные `force_vector_mode()`, `force_tiered_mode()` и `reserve()` остаются
|
||
пользовательскими управляющими операциями и не являются автоматической
|
||
адаптацией.
|
||
|
||
## Геометрия tiered storage
|
||
|
||
При capacity-boundary размер малого массива вычисляется из фактического размера
|
||
последовательности на этой границе:
|
||
|
||
```text
|
||
leaf_capacity = max(4, ceil(sqrt(target_size)))
|
||
```
|
||
|
||
Значения fanout и допустимой глубины каталога берутся из `TieredConfig`.
|
||
`leaf_capacity` не подстраивается после каждой вставки или удаления: новое
|
||
`sqrt(N)` применяется только в общей перестройке. Поэтому rebuild одновременно
|
||
может выполнить `vector -> tiered`, `tiered -> vector` или
|
||
`tiered -> tiered` с новой геометрией.
|
||
|
||
## Flat hash index
|
||
|
||
`AdaptiveSequence<T, true>` использует open-addressed flat table
|
||
`value -> {head_id,count}`. Дубликаты связаны через компактные intrusive links в
|
||
ID metadata. `find_one` возвращает любой экземпляр, `find_all_ids` — unordered
|
||
stable IDs, а `find_all` сортирует логические позиции и может стоить
|
||
O(k log k).
|
||
|
||
Внутри цепочек используются 32-битные slot IDs. Освобождённые metadata slots
|
||
переиспользуются через free list, а публичный 64-битный stable ID кодирует
|
||
`generation + slot`. Поэтому сбалансированный insert/erase churn не наращивает
|
||
metadata без границ и старый ID не оживает после повторного использования slot.
|
||
|
||
Hash table следует той же capacity-policy, что и storage:
|
||
|
||
```text
|
||
required_buckets = ceil(logical_capacity / 0.70)
|
||
bucket_count = next_power_of_two(max(16, required_buckets))
|
||
```
|
||
|
||
Иными словами, таблица заранее рассчитана на худший случай «один уникальный
|
||
ключ на элемент» при load factor не выше 70%. При росте bucket reserve/rehash
|
||
выполняется перед перестройкой storage, при shrink — после неё. Целевое число
|
||
buckets пересчитывается только при изменении логической capacity; если оно не
|
||
изменилось, отдельного rehash нет. Обычные вставки и удаления между границами не
|
||
запускают независимое увеличение hash table.
|
||
|
||
Такой выбор сохраняет O(1) expected lookup и включает стоимость редкого rehash
|
||
в ту же измеряемую capacity-перестройку, где уже оплачивается перенос storage.
|
||
Flat hash остаётся compile-time optional: вариант `AdaptiveSequence<T, false>`
|
||
не несёт его память; тот же API поиска по значению работает линейным обходом.
|
||
|
||
## Инвалидация
|
||
|
||
- const-чтение и hash lookup ничего не инвалидируют;
|
||
- `set()` не меняет логические позиции, но ссылка на заменённое значение не
|
||
должна использоваться как ссылка на старый объект;
|
||
- вставка или удаление инвалидирует позиционные references, pointers и
|
||
iterators согласно структурному изменению; capacity-boundary дополнительно
|
||
может перестроить весь backend;
|
||
- conversion, geometry rebuild, `force_*`, `reserve`, `clear` и
|
||
`make_contiguous()` инвалидируют всё позиционное;
|
||
- stable ID переживает shifts, split и смену представления и перестаёт быть
|
||
живым только после удаления соответствующего элемента или `clear()`.
|
||
|
||
Stable ID имеет область действия конкретного состояния конкретного контейнера.
|
||
Copy/move assignment заменяет это состояние: ранее полученные ID обеих сторон
|
||
после assignment использовать нельзя (их числовое значение может совпасть с ID
|
||
элемента нового состояния). Move construction переносит состояние целиком и
|
||
сохраняет его ID в новом объекте.
|
||
|
||
Debug iterator хранит structural generation и бросает `logic_error` после
|
||
инвалидирования.
|
||
|
||
## Historical / retired: operation-window CostModelPolicy
|
||
|
||
До текущей постановки default-policy собирала `OperationSample`, оценивала
|
||
vector и набор фиксированных leaf 64/128/256/512/1024, применяла EWMA,
|
||
hysteresis и прогноз окупаемости O(N)-перехода:
|
||
|
||
```text
|
||
(current_cost - candidate_cost) * forecast
|
||
> rebuild_cost * safety_factor
|
||
```
|
||
|
||
Также исследовались deferred/eager read adaptation, minimum residency и
|
||
отдельные `vector -> tiered`, `tiered -> vector`, `tiered -> tiered` решения.
|
||
Эта схема и соответствующая benchmark-матрица **retired**: они сохранены для
|
||
воспроизводимости старых CSV и для экспериментов с явно выбранной
|
||
`CostModelPolicy`, но не описывают текущую default-policy и не используются для
|
||
нового cutoff.
|