# Segmented collections
A segmented collection (`SegMap<K, T, C, H = NoHook>`) is for large, mostly immutable data whose
keys do not all fit in RAM: an index of blockchain transactions, an event
archive. It trades features for memory. Read "What it does not do" before
choosing it.
See the [SegMap and SegTree Q&A](segmented-qa.md) (Russian) for implementation
status, the remaining roadmap, S3 and async API considerations, and the split
between paged metadata (7a) and a global routing index (7b).
Feature flag: `segmented`. Managed open takes a hook, including `NoHook`:
```rust,ignore
let rows = db.open_seg_map::<Row, RapiraCodec, _>(SegConfig::balanced(), NoHook, &[])?;
```
Standalone `SegMap::open(path, meta, config, codec)` remains available only with `NoHook`.
## The model
Writes go to the **active generation**: a journal on disk and an index of its
own keys in RAM. When the generation is full or old it is **frozen**, and a
background worker **seals** it into a **segment**: two immutable files, sorted
data blocks (`.sdat`) and a sidecar with a sparse block index and a filter
(`.sidx`). The generation's index leaves RAM. **Retention** drops whole
segments, oldest first.
A read looks at the active generation, then at frozen ones, then at segments
from the newest to the oldest, and stops at the first layer that knows the
key. A segment is consulted through its filter, so a segment that does not
hold the key costs no metadata read while hot. Cold segments read filter
pages on demand; unhinted misses and existence checks therefore grow with
the number of cold segments. With all metadata hot, the earlier 389-segment
measurement averaged 1.5 data-block reads for a missing key.
| Earlier measured SegMap RAM per key | 68.5 bytes at 6M keys, 102.8 at 1M | all-hot metadata: 11.12 bits (200-byte values), 13.59 bits (500-byte values) |
| Mutable | yes | no |
| Disk reads per lookup | 0 or 1 | hot: 1 data read on a hit; cold: metadata plus data |
## Semantics you must know
- **`put` and `delete` are blind.** They do not look at older layers. `put`
shadows any older version; `delete` always writes a tombstone.
- **`insert` looks.** It refuses with `KeyExists` when the newest visible
version is live. A newer tombstone makes the key absent, so insertion
succeeds. It costs a probe of the sealed layers. RPC insert-if-absent
(`write` with `Some(false)`) is this `insert`.
- **The facade has no read-modify-write.** No `update`, `cas` or `atomic`;
managed transactions support `upsert` and `guard`.
- **`len()` is an upper bound.** A shadowed or deleted version is counted
while its segment lives. `is_empty() == true` proves that nothing is
visible; `false` proves nothing. The exact count reads the whole collection.
The same bound, with no mark that it is one, is what `Db::collection_len`,
the Inspector's `CountMode::Current` and collection list, and RPC
`count(false)` and `ListCollections` report. RPC `count(true)` and
`CountMode::Exact` are exact and read the whole collection.
- **A snapshot is bounded in size, not in work.** `snapshot_unordered` reads
until it has one row more than its cap. Among many shadowed or deleted
versions even a cap of 1 can read the whole collection.
- **An old version is never reclaimed on its own.** Its space comes back when
its segment is dropped. A collection whose rows are rewritten often belongs
in a Bitcask family.
- **`try_get_hinted(key, written_since_ms)`** trusts your claim that the key,
if it exists, was last written at or after that time, and skips layers
frozen before it. If the claim is false the result may be `None` for a key
that exists. It prunes by layer, not by the time of a write: a version
older than the hint is returned when its layer was frozen later.
- **Write hints are trusted.** `tx.written_since(&collection, ms)` claims
that every operation key in that collection, including guard-only keys,
if it exists, was last written at or after `ms`. It covers old-value reads
for projections, counters, streams and `on_write`, insert probes, upserts
and guards. Repeated calls keep the smaller timestamp. `insert_hinted`
makes the same claim for one facade key. The active generation is always
consulted; older frozen layers are skipped by freeze time. A false claim
can allow insertion over an existing key, leave old index rows
(`IndexOrphan`), double-count a counter (`CounterMismatch`), emit an insert
stream event instead of an update, or give a guard the wrong value.
`schema::validate` reports index/counter drift; explicit `repair` can fix
supported checked targets, subject to its limits. It cannot undo a wrong
guard decision or emitted stream event. Hints are not logged; replay uses
existing unhinted old-value reads. Blind facade put/delete need no hint.
Claims are compared with layer freeze times from the node's wall clock:
take the timestamp from that clock before the write's commit began. A clock
stepped back after the write can freeze its layer earlier than that
timestamp, which makes such a claim false.
- **Retention is coarse.** A sealed segment becomes eligible for
oldest-first removal when `retention` has passed since it was frozen.
Maintenance scheduling, seal backlog or failures, and time offline can
delay removal indefinitely; retention sets no strict maximum row lifetime.
- **Iteration order is unspecified.**
## What it does not do
| Unique-source claims, watches, initialization scans, expiration hooks | rejected at open or registry construction |
| `SegMap` index target; counter, queue or replication target | no target trait implementation (`SegTree` index targets are supported below) |
| Transaction ranges (`delete_scope`) | unavailable |
| Replication | compile error |
| Encryption, compression | there is no setting |
| Per-row TTL | `DbError::Config` at open |
| Format migrations, including the proof-only `FormatMigration::unchanged` (use a typed migration instead) | `DbError::FormatMigrationUnsupported` |
| Range scans, `first`, `last` | `DbError::NotImplemented` |
| RPC update-if-present and `take` | `DbError::NotImplemented` |
Nothing in this list is ever silently ignored.
## Configuration
| `seal_max_keys` | 6 million | freeze when the index holds this many keys; bounds the index RAM |
| `seal_max_bytes` | 16 GiB | freeze when the journal holds this many bytes |
| `seal_max_age` | 24 h | freeze when the generation is this old and not empty |
| `retention` | `None` | eligible for oldest-first removal this long after it was frozen |
| `block_size` | 16 KiB | target size of a data block |
| `block_cache_bytes` | 256 MiB | shared cache payload budget for data blocks and cold metadata pages |
| `resident_metadata_bytes` | `None` in every preset | `None`: all metadata hot; `Some(bytes)`: newest-first hot prefix while costs fit; `Some(0)`: all cold |
| `max_frozen_generations` | 1 | generations that may wait for a seal |
| `seal_wait_timeout` | 30 s | how long a write waits for room |
| `maintenance_interval` | 60 s | how often age and retention are checked |
| `shard_count` and the journal fields | as in `Config` | apply to generations created from then on |
## Sizing
The **hot window** is the newest-first prefix of sealed segments whose full
metadata cost fits `resident_metadata_bytes`. Selection stops at the first
segment that does not fit; older smaller segments are not selected. The cost
is stable across paging and includes filter/index structures and parsed
containers; use the actual selected-prefix sum, not the configured budget.
Cooling is published with sealing. No cold survivor warms during retention;
changing the budget takes effect at reopen. `None` preserves eager all-hot
behavior and its memory growth with retained physical entries, including
shadows and tombstones. Paging leaves a skeleton and fixed overhead for every
segment, so those terms still grow with segment count.
```text
heap ≈ fixed empty DB/J + 2G + additional freeze J/containers
+ Σ_selected_prefix cost + Σ_all_segments skeleton
+ per-segment wrappers/manifest/Arc/path overhead
+ actual cache payload + cache bookkeeping
+ transient builds, carried iterator groups, held reader views
skeleton = Σ_pageable (32 + 4 × intersected_4KiB_pages)
+ Σ_filters (8 + 32 × partitions) + parsed tables
+ 8 × ceil(blocks / 128) # SegMap samples
| Σ_groups (6 + sample separator bytes) # SegTree samples
+ properties + key range + native container allowance
```
Wire terms expand into native parsed containers; prefix filters and their
identities must also be included. The [dated measurement and raw
JSONL](benches/26-10-05-segmented-paged-metadata.md) count those terms from
original files. Three actual 20M-entry corpora at a 1M-key generation cap gave:
| SegMap, 200-byte values | 2,744 | 6,948,240 | 213,919,261 | 335.36 |
| SegMap, 500-byte values | 4,408 | 8,494,720 | 213,919,261 | 352.71 |
| SegTree, 200-byte values, prefix8 | 7,532.25 | 7,863,426 | 341,144,553 | 503.42 |
Skeleton formulas match exactly; the maximum idle heap-model error is
0.0867%. One actual full frozen and one actual full active generation were
held simultaneously. The first full generation predicts the held-out second;
full idle-plus-live errors were 0.0081%, 0.0082%, and 0.0056%. The freeze
buffer/container increment was measured separately, rather than independently
predicted. Cache bookkeeping is a fitted allocator residual; observed cache
payloads span about 10–36 MiB. Allocator fragmentation and OS page cache are
outside requested-live heap accounting.
The 10B figures are **steady-state projections** at the measured 1M cap:
10,000 segments, fixed measured hot prefix, scaled skeletons and fitted
per-segment residual, populated two-generation increment, 64 MiB cache
payload and fitted bookkeeping. Bookkeeping at 64 MiB occupancy was not
measured or bounded. Roughly 20,000 sealed FDs exceed the measured 1024 default
and 8192 benchmark soft limits, so these projections do not validate deployment
at 10B. Larger generation caps, transient seal/recovery/migration peaks and
startup feasibility remain unmeasured here. The earlier all-hot
[full-window report](benches/26-10-02-segmented-full-window.md) remains relevant
for `None`; its 6M-cap numbers must not be substituted for this 1M-cap model.
The resident budget is soft while readers hold old views: cooled full metadata
can remain alive until the last reader releases it. Long scans also retain
carried data blocks, parsed offsets and index groups per overlapping segment.
Foreground legacy skeleton builds (at most two per collection), the worker's
build and generation indexes/buffers add transient memory outside the budget.
## Operation
- **Backpressure.** When the active generation is full and the seal queue has
no free slot, a write waits up to `seal_wait_timeout` and then fails with
`DbError::SealBackpressure`. That error means the failed operation was
**not** applied; repeat it. An RPC `apply_batch` applies its items one by
one, so the items before the failed one stay applied; the operations are
blind, so repeating the whole batch is safe. A typed migration's own writes
are not bounded by `seal_wait_timeout`: they wait while the seal worker
makes progress and fail only when a seal fails, the collection is fenced or
shut down.
- **Shutdown is final for the handle.** `clean_shutdown`, of the `SegMap` or
of the `Db`, stops the seal worker until the collection is reopened. A
write is still taken while the active generation has room; after that
every write fails at once with `SealBackpressure`, and repeating it is
pointless. Freezing by age and retention stop too.
- **Disk headroom.** While a generation is sealed, its journal and the new
segment exist together. Keep free space for one more generation. A typed
migration that rewrites rows needs up to the size of what it rewrites.
With 32-byte keys and 200-byte values a sealed entry takes 250 bytes on
disk: 583 GB for 2.33 billion entries.
- **The clock.** Retention uses the node's wall clock. A clock that jumps
forward makes segments look old. At most one segment is dropped per
maintenance tick, and every drop is logged at `warn`.
- **Cold lookup cost.** Unhinted misses and write existence checks probe every
candidate cold segment; a rare-prefix ordered query can do the same.
True time hints prune layers before metadata I/O. For one selected ready
cold segment with an empty cache, reference hits measured 3 positioned
requests for SegMap (200/500-byte values) and 5 for SegTree, including the
data block. Collection-wide probes, variable filter-window sizes and
oversized index groups can cost more; pending legacy skeleton builds are
additional whole-sidecar work. Warm OS-cache p99 for the selected hinted
reference hits was 29.044 / 29.245 / 35.236 µs. The physical-cold local-NVMe
≤5 ms gate is **UNVERIFIED / MANUAL**; metadata-cache resets do not drop the
OS cache. RAM-disk repetition was unavailable (R43).
- **Opening and deferred validation.** `None` opens and validates full
sidecars eagerly. Cold opens validate headers/footer/section structure,
properties and tree key ranges; with `PAGE_INDEX`, they also validate that
skeleton. A cold open trusts the filter tables and prefix lengths that
`PAGE_INDEX` records and does not compare them with the sections they
describe: seal reopens every new segment through the full parser, which
does, and `verify` reports a disagreement written elsewhere. Filter/index
pages are CRC-checked when read; their corruption need not fail open. `verify(VerifyScope::All)` reads originals and checks
whole-file checksums and page-index consistency. A `PAGE_INDEX` of a
version this build does not know is skipped, as a sidecar without one.
Cold legacy sidecars without `PAGE_INDEX` remain skeleton-pending; the
worker derives them newest-first at every startup without rewriting
files. It builds them one at a time, back to back, in passes of at most
250 ms with seals between them, and does not sleep while some remain; a
failed build waits for its backoff. A first read can build in the
foreground or wait for an ongoing build. A build reads and parses the
whole sidecar, so its time follows sidecar bytes: warm, twenty legacy
sidecars of 1M entries (about 1.5–2 MB each) were all derived 10–18 ms
after the open returned
([report](benches/26-10-05-segmented-paged-metadata.md#legacy-background-pacing-after-198)).
Legacy prefix wrappers additionally require counted 8-byte reads at open.
Generation recovery may repair journal tails/hints; later failures can
follow resumable repairs or unreferenced-garbage cleanup.
- **Descriptors.** Budget one data FD per never-cold segment and two FDs
(data and sidecar) for a segment used cold, even if full metadata remains
pinned by a reader. Bounded parallel open preparation adds at most eight
transient sidecar handles. Journal and other database descriptors are
additional; retention waits for last references before deleting files.
- **A fenced collection.** If the outcome of a manifest publication is
unknown (the rename happened, the directory sync failed), the collection
refuses every change with `DbError::CollectionFenced` until it is
reopened. Reads keep working. Reopen it.
- **Schema changes.** A typed migration reads the whole collection and
writes the rows it changes again, so their retention starts over. One row
that does not decode fails the migration, and the open fails with the
decode error on every attempt. Repair or delete that row with the old
binary, then upgrade.
- **Checking.** `verify(VerifyScope::All)` reads every block and compares it
with the manifest. It reads at about 1.1 GB/s: 529 s for a 583 GB window.
If a segment's original sidecar cannot be parsed or names another
segment, a hot segment's data is still walked with its resident metadata;
a cold one, with no index in memory, only has its whole data file compared
with the manifest checksum. `seal_status()` shows the seal queue and the last error.
`stats()` shows what segment reads cost. `block_reads` counts every block
read from disk, by point reads and by scans alike; `verify` is not
counted. `false_positives` counts filter hits for a key the segment does
not hold. Segment read counters cover the current view: when retention
drops a segment, its counters disappear and totals can decrease. Cache
counters cover point and user ordered reads over the lifetime of the open
handle; internal scans bypass the data cache. With
`block_cache_bytes = 0`, cache counters stay 0.
`SegStats` additionally exposes `hot_segments`, `cold_segments`,
`hot_metadata_bytes`, `skeleton_bytes`, `hot_since_ms`, `skeletons_pending`,
`skeleton_builds_foreground`, `skeleton_build_failures`, `meta_cache_hits`,
`meta_cache_misses`, `meta_requests` and `meta_bytes_read`. `resident_bytes`
is hot metadata plus skeletons, not total heap or pinned-view memory.
The worker publishes these fields as `armdb.seg.<field>` gauges with the
`collection` label. Build failure/foreground and metadata I/O counters cover
the open handle's lifetime; pending skeletons describe the current view.
Failed build attempts include both returned errors and builder panics.
MetaIo counts positioned non-header `.sidx` requests/bytes including startup,
properties, ranges, page-index reads, legacy wrappers and whole-sidecar
reads; initial header reads are the explicit exception. These requests may
be served by the OS cache and do not prove physical device I/O. Take deltas
after open to isolate query cost; pending work and failures remain visible.
## Files
```
<db>/<name>/
db.meta backend = Segmented
MANIFEST the only source of truth about the composition
gen/<id>/ one Bitcask directory per generation
seg/<id>-<version>.sdat
seg/<id>-<version>.sidx
```
A segment's `value_version` and `typ_hash`, in the manifest and the
sidecar, name the build that sealed it, not the schema its rows were
written with. Do not read them as the format of the rows.
Never open a `Db`-managed collection directory with standalone `SegMap::open`.
Its seal worker starts at once, before any transaction replay: it can seal a
generation that still owes a logged write, and the next managed open then
treats that write as already applied and drops it.
Opening removes files and directories the manifest does not mention after
referenced-object validation and generation recovery. Cleanup can remove
some garbage before a later error makes the open fail. Never add, remove or
rename anything here by hand.
## Transactions and projections
Managed `SegMap` participates in `db.tx()` alongside native collections from
that same `Db`. It supports `put`, `insert`, `delete`, `upsert`, and `guard`.
Repeated operations use pending values, including delete followed by insert.
Blind `NoHook` puts/deletes skip old-value reads; inserts, guards, upserts and
active hooks may read older generations or sealed blocks under index locks.
There is no atomic visibility to concurrent readers: a reader can see part of
a transaction before another participating collection is applied.
An active hook requires transaction writes: facade `put`, `insert` and `delete`
return `SegHookRequiresTx` before encoding. Activation includes write callbacks,
index/counter projection halves (even empty target sets), and stream emission.
A custom hook with no active capabilities behaves like `NoHook`. Hook limits
are clamped to 4096 rows and 1 MiB (or a smaller hook limit) for each projection
call/snapshot independently: old and new snapshots, and each source row, have
separate budgets. Counter snapshots have the same per-call scope; stream
emission has a fresh budget for each source-row transition. These are not
transaction-wide allocation budgets. The complete resolved transaction, including
derived writes, is bounded separately by `TxConfig.max_ops` (1024 by default)
and `TxConfig.max_bytes` (8 MiB for the encoded record by default). Indexes,
counters and change streams can use this collection as a source, but unique
claims, watches, expiration and initialization-scan hooks are unsupported.
`SegMap` cannot be an index target; `SegTree` can declare the index role below.
Neither family can be a counter, queue or replication target.
Projection source changes, absolute index/counter writes, stream appends and an
application cursor belong in one transaction. Ordinary `on_write` callbacks
run after unlocking and are best effort; they are not a durable event channel.
The callback's old value is the one evaluation read under the locks; if it
cannot be read, the event is skipped and the write still commits. Open-time
replay fires `on_write` for a replayed operation, like the native families,
with the transition a reader sees: a replayed version shadowed by a newer
layer fires nothing.
Use a transactional change stream for durable emission. Stream source teardown
currently has a known ownership cycle (source → queue → transaction runtime →
collections), also present for native typed sources: closing and dropping the
Db in the same process does not guarantee those handles/workers are released.
Do not depend on drop followed by same-process reopen for a stream source;
recovery is validated in a fresh process. This limitation is not a new storage
format or recovery guarantee.
Projecting sources cannot have retention or call `drop_segments_before`:
dropping whole segments cannot retract their derived rows. A stream-only source
may retain/drop history. Aggregates, block totals and ingestion cursors remain
application data in native collections; there is no aggregate projection API.
**Keep native derived data small.** A native index or counter target is a collection
that lives in RAM, and its repair holds the whole expected set in memory: index
reconciliation after a migration, `schema::validate`/`repair` and
`db.recount_counters` build a map of every derived row the source projects plus
every row of the target. Their memory is proportional to the derived rows, not
to one generation. Project a narrow subset (failed transactions only) or one
aggregate per address or block. An index row per source row over billions of
rows does not fit, and a migration of such a source would fail its open on every
attempt while `projections_dirty` stays set. For large, segment-shaped indexes, see [SegTree as an index target](#segtree-as-an-index-target).
Participants lock in `(rank, collection_id)` order, then ascending physical
shard order. Reading old segmented payloads keeps earlier participants locked,
including native cursors. Slow disk reads can therefore delay facade writers
on both collections. [Measured p95/p99](benches/26-10-01-segmented-transactions.md)
include a blind baseline and coordinated concurrent writers; no latency
acceptance threshold or optimistic-read guarantee follows from those samples.
Seal backpressure is waited for before the commit locks any participant: a
transaction whose segmented participant has a full active generation waits up
to `seal_wait_timeout` holding nothing. Under the locks the check repeats
without waiting: if concurrent transactions filled the generation in between
and the seal queue has no free slot, the commit fails at once with
`SealBackpressure` (not applied; repeat it) rather than stall the writers of
earlier participants.
Admission pins one generation before logging. `TxConfig.max_ops` and
`max_bytes` bound each admitted transaction, not the number admitted. Threshold
overshoot is bounded by the **sum** of the writes/encoded bytes of every
concurrently admitted transaction on that generation, rather than one maximum
transaction. Bound producer concurrency as well as transaction size when
planning peak journal/index memory.
Replay routes a logged GSN to its generation; an already sealed or dropped
layer is considered applied, so retention cannot resurrect rows. A post-log
apply failure fences the whole segmented collection until reopen/replay,
including later generations. Managed open completes replay before starting
sealing. See [transactions](transactions.md) for failure handling.
Normal crash recovery replays absolute projection writes and does not recount
counters. Typed source/target migrations reconcile native indexes by full scans
across retained layers; segmented targets instead use bounded ordered batches
whose target durability barriers precede source writes. Counter recounts record
durable counter evidence before migration work (including a zero-row or partially
failed migration). Schema validation and explicit `db.recount_counters(Row::NAME)`
also scan retained layers.
A lower-layer read/decode error aborts reconciliation; do not treat it as absence
or delete derived rows based on a partial expected set. Physical format
migrations remain unsupported for this family.
## SegTree as an index target
Enable `segmented` and `schema`. A managed `SegTree` declared
`SegTreeMeta::INDEX_TARGET = true`, opened with `NoHook`, can be the
secondary-index target of a managed `SegMap` or `SegTree` source.
Declare its projection before opening the source, through
`SchemaRegistry::secondary_index` and `IndexTargets`. Open targets first.
Native sources are refused with `DbError::Config` at managed opens and at the
six typed families' direct hooked openers listed below (future support:
[issue #192](https://github.com/libfunc/armour/issues/192)). Lower-level raw byte
openers and direct LSM opens remain unsupported routes, without this refusal
contract. Native TTL, write and physical-migration paths do not have the
segmented maintenance protocol.
Every rule fails explicitly. None is silently ignored.
| A segmented target is declared `INDEX_TARGET` and opened with `Db::open_seg_tree` | `reject_index_decl` (registry declaration, panics like the other topology checks); the source's open for a hand-assembled carrier. A standalone `SegTree::open` handle is an ordinary tree whatever its type declares | panic / `DbError::Config` |
| The source of a segmented target is a `SegMap` or `SegTree` | the managed open of every native family, and the six typed families' direct hooked openers, for any hook whose `IndexTargets` holds a segmented target | `DbError::Config` |
| Derived keys end with the source key (D10) | the projection of every derived row of a segmented target | `DbError::IndexKeyNotOwned` |
| An `INDEX_TARGET` collection has no retention | its own `open_seg_tree`, before the worker starts | `DbError::Config` |
| `drop_segments_before` on an `INDEX_TARGET` collection | the facade, always | `DbError::Config` |
| An `INDEX_TARGET` collection's own typed migration returns only `Keep` | the migration step; the first `Update` or `Delete` fails it | `DbError::Config` |
| An `INDEX_TARGET` collection takes no direct writes | the facade (`put`, `insert`, `delete`), and with it Access and RPC writes; `ProjectableIndex::put_bytes`/`delete_bytes` without the [internal maintenance grant](#internal-maintenance-grants); the transaction planner for an explicit operation, by the type flag, whether or not a source has opened | `DbError::Config`, not applied |
| A collection with persisted index state keeps its role | its own open: stored owner, pending or retired evidence while `INDEX_TARGET` is now `false` | `DbError::Config` |
| An existing non-empty collection does not become an index target | its own open, when the stored info holds no index state | `DbError::Config` |
| A segmented target has exactly one source | the atomic owner claim at the source's open | `DbError::Config` |
| A source opens only with all its owned targets declared or retired | the source's open, before replay, migration and backfill | `DbError::Config` |
| A retired target cannot be declared again | the source's open | `DbError::Config` |
| No counters or unique names on a segmented target | no `CounterCollection` or unique-namespace implementation | compile error |
| A target with a hook | `ProjectableIndex` implemented only for `NoHook` | compile error |
| Every target opens before its source | the identity check of every declared target, native ones in the same carrier included, before the owner claim | existing error |
### Internal maintenance grants
Backfill, ordered source migration and schema repair use private, thread-local
one-shot grants for a named target. Only the current innermost grant can
authorize its matching mutation. The target consumes it before key conversion,
metrics, allocation or core callbacks; the spent marker stays until scope exit,
so callback reentry cannot reuse it or fall through to an older grant. Nested
engine scopes get their own grants. Errors and unwinding release their scopes.
Durability barriers need no grant and run without one. There is no public token
or maintenance API; public trait writes from application callbacks are refused.
The D10 suffix is the source key's exact encoded bytes, even when the
projection is unchanged. Query components and discriminators precede it.
This excludes aggregate/latest-row ownership transfer. Violations return
`DbError::IndexKeyNotOwned` before applying the write.
### IndexState and lifecycle
`index_state() -> Option<IndexState>` returns `None` for an ordinary tree;
index targets return `Some(Pending)`, `Some(Ready)` or `Some(Retired)`.
New targets are pending; successful source replay, migrations and backfill
publish ready state. During source migration a target is pending and can be
ahead of the unpublished source. Check ready state before serving queries.
Owner, pending, migrating and retired evidence is persisted in `db.info`.
An existing nonempty ordinary collection cannot be promoted to an index, and
persisted role evidence cannot be removed by changing `INDEX_TARGET` to false.
Exactly one source owns a target. Source admission reserves its declaration
through staging and publication, preventing retirement while any staging or
open source declares that target. Failed opens release in-memory staging
reservations; a persisted owner claim remains. The hook declarations are fixed
before source open; changing them requires a new open. A source must declare every owned live target
before opening; an omitted target must already be retired. Retired targets
cannot be declared again, including through an old carrier. These checks
prevent an older binary or a `NoHook` opener from silently abandoning an index.
### Write cost and backpressure
Each derived row is a blind put into the target's active generation; removed
keys write tombstones. Derived operations share the transaction's `max_ops`
and `max_bytes` limits. Target admission joins source admission: a saturated
seal queue can make the source wait up to `seal_wait_timeout`, then return
`SealBackpressure` without applying the transaction. Target sealing throughput
therefore limits source throughput. Concurrent admission can overshoot the
generation threshold, multiplied by projection fan-out.
### Backfill at open
A pending target is filled by a full source scan, blocking source open; an
empty source completes immediately. Projection calls and target buffers bound
memory rather than collecting the entire expected index. Failed/crashed builds
restart from the beginning on the next open; earlier puts become shadowed
versions. At large scale the scan can take hours. A controlled interrupted
benchmark is distinct from the process-crash matrix testing recovery.
### Typed migrations and physical growth
Variant A computes each changed source row's index difference, writes the index
first, durably flushes affected targets, then writes source actions. Batches
are bounded by 65,536 entries and 16 MiB of charged encoded allocations by
default; an oversized entry is admitted alone under the projection-call limit.
Migration callbacks must be deterministic and idempotent. A crash retries the
step; D10 confines each difference to its source row so the retry converges.
Pending targets receive migration differences too. Native targets retain their
existing reconciliation/recount rules; segmented targets avoid whole-index
migration reconciliation. A target's own migration may return only `Keep`.
A target stays pending until the source opens with a `VERSION` that reaches
the unfinished migration. Going back to an older binary after an interrupted
migration therefore leaves it pending, and the open logs a warning. One of
that migration's batches may have written index rows for values the source
never received, and no older binary can tell which. Opening the newer binary
again finishes the migration and makes the index exact. Writes the older
binary makes to the rows of that batch meanwhile can leave index rows the
finished migration does not remove: run `schema::validate` before serving
from such an index again.
Tombstones, rewritten rows and interrupted backfill copies consume physical
entries and sidecar memory. Index targets have no retention or segment drops:
physical history can grow indefinitely under churn, even when live rows stay
constant. Plan capacity from physical history, not `len()`.
### Changing the projection and retirement
Use a new collection `NAME` and value type for a changed projection. A target
`VERSION` bump with a `Keep` migration does not rebuild this index.
For the upgrade release that removes an old version:
1. Open the old target, keeping its type for this release; its projection closure is unnecessary.
2. Call `db.retire_index_target(old_name)`. Its own replay must be done and no staging or open source may declare it.
3. Open the new target.
4. Open the source with a hook declaring only the new target. Source replay settles participants in records naming both source and old target; backfill fills the new target.
5. Checkpoint as usual, and close successfully to complete the log cleanup.
`pending_transactions()` includes already applied but uncut records; its immediate
emptiness is not a settlement test. A later release can remove the old type once
records have been settled and checkpointed/closed. A recovered record still
naming the retired target stays pending until that target is opened again;
source open logs a warning. Retirement keeps old files. A future
`Db::drop_collection` must retire transaction participants durably before deletion
([issue #191](https://github.com/libfunc/armour/issues/191)).
### validate and repair budgets
`SchemaRegistry::segmented_check_limits(SegmentedCheckLimits { rows, bytes })`
defaults to 10,000,000 rows per target and 1 GiB across all retained segmented
expected and actual maps. Physical target entries (including tombstones) are
checked before collecting. Expected rows are bounded too, even for an empty
target. Encoded keys/values, owner strings and container overhead are charged;
a target exceeding a limit releases its partial maps and becomes unchecked.
`validate` emits warning `IndexUnchecked` with `TargetTooLarge`,
`ExpectedRowsExceeded` or `BytesExceeded`. `repair` decides this before writing,
writes nothing to unchecked targets, and lists `RepairReport::unchecked_targets`.
For checked targets, missing/mismatched rows can be repaired; orphan deletion
requires `complete_index` and `RepairOptions::delete_orphans` and adds tombstones.
Invalid D10 ownership is an error `IndexKeyNotOwned`; diagnostics keep one
representative invalid key per segmented target to bound memory. Native target
checks keep their existing rules without these limits. Streaming verification
of oversized targets remains deferred.
### Mostly immutable history and blockchain indexing
This layout fits append-heavy history, such as blockchain transactions indexed
by `(address, block_sequence, transaction_key)`, with an empty value. Encode
numeric query fields big endian, retain the source key as the suffix, and page
an address prefix newest first. Fetch source values separately from the suffix.
See the executable [Blockchain index by address](segmented-tree-examples.md#blockchain-index-by-address).
Heavy rewriting/deletion retains historical versions and is a poor fit.
The [reference measurements](benches/26-10-04-segmented-index.md) use an actual
10-million-row source and 30-million-row index (20 segments each), plus a
668-segment latency fixture with smaller generations. The projected 8 GB envelope
is 66,751,215 logical source rows under explicit five-copy physical-history and
healthy runtime reserves (333,756,075 physical source / 1,001,268,225 physical
index entries). Billion-entry index capacity is a projection, not a measured
corpus. The measured heap model error is 2.856%; target generation capacity is
1.5 million keys and two generation indexes allocate 783,508,096 bytes.
Reported write throughput uses the real default `durable_by_default = false`;
64 MiB automatic checkpointing is a disk threshold, not a strict heap cap.
Migration measured 49 target flushes, 15.45 MB retained owned batches and 1.434%
unchanged-projection overhead; controlled half-pass/retry backfill measured about
173,000 source rows/s. Historical warm latency uses the nineteenth of twenty
ordered samples (the lower statistic); nearest-rank warm p99 was not measured.
Consult the report for measured code SHAs, workload assumptions and cold/warm
methodology before using these numbers as an operating envelope.
## Byte-ordered SegTree
`SegTree<K, T, C, H = NoHook>` shares the segmented persistence, transaction,
projection, schema, RPC, Inspector and typed-migration contracts above. Its
active generation keeps a hash index for points plus an ordered companion;
sealed segments hold a sparse separator index. `SegMap` keeps its existing
hash order and format. Both use format version 1; an order mismatch refuses
open before repair or cleanup.
Use `Db::open_seg_tree::<T, C, H>(config, hook, migrations)` with a value type
implementing `SegTreeMeta`. Hook-free standalone opening is
`SegTree::open(path, meta, prefix_filters, config, codec)`; its handle is
never an index target. This family has no
TTL, value-format migrations, watches, init/expiry/claim hooks, public Scope,
range deletion, facade update/CAS/atomic, counter/queue targets, encryption or
replication. Index/counter projection sources cannot use retention or manual segment
drops. A stream-only source may retain/drop history under the existing
stream-open guards. Active hooks require `db.tx()` for writes.
Order is encoded **key-byte order**. Numeric range/page components must use
big-endian `KeyType::U64`; native-endian bytes do not sort numerically.
[Executable sessions and deltas examples](segmented-tree-examples.md) encode
24-byte `(user, session, sequence)` and 16-byte `(document, version)` keys.
`SegTreeMeta::PREFIX_FILTERS` defaults to `&[]`. Declare distinct, nonzero prefix lengths shorter than the key. Typed keys
require valid component boundaries; raw byte schemes accept any interior byte
position. Declaration order does not affect validity. Declarations affect future seals:
old segments with missing filters remain readable and unpruned, so reopening
with a different declaration cannot create false negatives. Each filter is
built from distinct prefix hashes, independently of the full-key filter.
`SegRange::all`, `prefix` and `range` own their query bounds. `rev()` reverses
traversal while preserving newest-layer precedence. `written_since(ms)`
prunes whole immutable layers frozen before the hint. The caller must justify
that every desired row's newest write belongs to a retained layer at/after
that time; this is not a row timestamp predicate. `page` and `keys_page` return
an exclusive continuation for the last consumed key. Out-of-query cursors
intersect the original bounds; empty or inverted queries terminate.
Ordered user reads use the block cache; internal full scans bypass it. Both
keep each overlapping segment's current block between refills: its payload,
parsed row offsets and, for a cold segment, its index group. A refill that
resumes in that block or group reads no metadata, and a full scan reads every
block about once. A live iterator, idle ones included, therefore holds up to
one block per overlapping segment (`S × block_size`, 18 MB at 1128 segments of
16 KiB blocks) plus offsets and a group of about 5 KiB at 24-byte keys; a
carried payload shared with the block cache outlives its eviction. `first`,
`last`, `page` and `keys_page` read only as many rows as they return.
Iterators return owned batches, bounded to 256 visible rows or 1 MiB encoded
values; an oversized value is returned alone. After 4096 invisible consumed
keys a refill releases its view and refreshes it. An idle iterator retains
neither generations nor segment files. Concurrent writes can change later
refills, so scans are weakly consistent; transactions do not provide an
atomic cross-collection read snapshot. A read, checksum or corruption error
ends the iterator and propagates through RPC, Inspector and schema
reconciliation; a row that does not decode ends the typed iterators and pages
too. Whole-collection scans for schema validation, repair and the Access layer
behave as for `SegMap`: a row that does not decode is reported
(`UndecodableRows`) and the scan continues, while a storage error stops it
(`ScanAborted`). A valid prefix before an error is not a successful short
scan.
`len()` counts physical layer entries and remains an upper bound.
### Ordered memory envelope and first-page cost
`SegConfig::tree_balanced()` uses 3,600,000 keys per generation, with the same
16 KiB blocks, 256 MiB cache and journal defaults as `balanced()`. The
[initial index comparison](benches/26-10-02-segmented-tree.md) remains a separate
measurement. [The final execution-dated report](benches/26-10-03-segmented-tree.md)
measures actual default generations, 20 or more segments, clean-hint recovery,
typed migration, warm/cold seals and pages at the projected segment count.
For physical retained entries N, including shadowed copies and tombstones:
```text
heap(N) = 2G + N*f/8 + sum_p(N*d_p*f_p/8)
+ (N/e)*(12+mean_separator_bytes)
+ ceil(N/seal_max_keys)*64 KiB
+ block_cache_bytes + cache_metadata_fixed + 2J + max_transient_T
```
G is a steady full-generation index measurement; J is an empty journal/core
measurement. Allocated capacities count. f and f_p include measured filter
metadata, d_p is distinct prefix density, and e is measured entries/block.
The cache budget weighs payload bytes; `cache_metadata_fixed` separately
charges measured cache table, ghost and Arc allocations. T includes real
sorted-hash/fuse/sidecar, hint-generation, recovery and typed
migration scratch. The population peak is reported separately. RSS includes
allocator bookkeeping and fragmentation and is independent of allocated
heap; the 8 GB ceiling is 8,000,000,000 decimal heap bytes.
The report distinguishes finite measured heap from the maximum N projected
by the formula. Matching a sealed/empty-active observation requires one J,
actual resident metadata and actual cache occupancy; adding hypothetical two
full indexes and a cache budget does not turn those allocations into an
observed process heap.
A hot prefix present in every segment must seek/read the first block in every
eligible segment before merging; the cost grows with segment count. A valid
whole-layer hint can reduce that count. Prefix filters prune absent prefixes,
and later refills seek from the consumed cursor. The report gives first-page
50-row gates in both directions, common-prefix version ranges, point hit/miss
budgets and both reference workloads' projected maximum N.
The envelope's maximum N is a heap projection, not an observed full-window
corpus or an RSS ceiling. Budget file descriptors too: a retained segment keeps
an open data-file handle, with additional journal/directory leases. Multiple
collections add their descriptor use. The benchmark's simultaneous Tree/Map
comparison uses a scoped soft limit of 4096 (`ulimit -Sn 4096`); the measured
inherited 1024 limit cannot hold both S=521 corpora. See the report for exact
limits and the preserved/resumed `EMFILE` diagnostic.
For the measured reference declarations, the conservative projected maxima are
1,852,425,972 physical session-message rows (S515) and4,057,297,544 document-delta
rows (S1128) within8,000,000,000 allocated bytes. The actual corpora measured72M
rows/20 default segments each; the larger maxima are formula projections.