Expand description
§segstore
Generic durable segmented store with write-ahead log and compaction.
§Overview
A consumer implements the Store trait to say how a batch of items becomes a
segment and how segments merge during compaction; segstore owns the durability
(built on durability) and the LSM-style
lifecycle. The segment representation is opaque, so the same machinery backs an
inverted index (posting-list segments), a graph index (graph-delta segments), or
any other updatable structure.
§Install
[dependencies]
segstore = "0.8"
durability = "0.9"§Example
use segstore::{DefaultStore, SegmentedStore};
use durability::MemoryDirectory;
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, DefaultStore::<u32, String>::new(), 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
s.delete(2).unwrap();
assert!(s.is_live(&1) && !s.is_live(&2));Use DefaultStore<Id, Item> when a segment is just Vec<(Id, Item)>. Implement
Store directly when a consumer needs sorted segments or a custom merge.
A re-add replaces the id’s previous value. A copy already sealed in a segment is
marked superseded rather than rewritten, so filter each segment’s items with
is_live_in(segment_id, &id) (on the writer, a View, or a SegmentCatalog);
is_live(&id) only says the id is not deleted. Custom stores get this by
implementing Store::item_ids.
§Durability
In-memory or on-disk via durability. Each add/delete is logged to a
write-ahead log before it takes effect. A checkpoint writes each new segment to
its own file, then atomically publishes a CRC-checked manifest naming the current
segments and tombstones. The filesystem backend also applies an fsync barrier.
The checkpoint starts a new WAL epoch and deletes the old log, so the WAL covers
at most one checkpoint interval. Only new segment payloads are written, but each
checkpoint also serializes the current segment IDs, tombstones, and
superseded-copy metadata.
Recovery loads the manifest’s segment files and replays only the current epoch’s
WAL. SyncPolicy::Fsync (via open_with_options) syncs every WAL record to
stable storage; the default flushes to the OS without a per-op fsync.
§Memory model
The on-disk layout is segment-per-file, but the current SegmentedStore::open
API loads every manifest segment into Arc<Segment> memory and View::segments
returns those in-memory segments. That is the right shape for fast embedded
indexes whose active segment set fits RAM, and for caching expensive per-segment
sidecars across restarts.
There is no out-of-core reader yet for corpora larger than memory; see docs/out-of-core-segment-reader.md for the proposed design.
SegmentCatalog reads the checkpoint manifest without opening segment files.
From there it can report one segment’s file offset, length, and CRC, read its
validated payload bytes, or decode it for a sidecar rebuild. It is a catalog
helper for loaders and diagnostics, not a byte-native query reader.
The catalog boundary is precise: segment bytes are the source payload as written,
and liveness is exposed separately through is_live_in. Consumers that decode or
map segment bytes must apply liveness and their own query metadata; segstore does
not convert source payloads into a live query view. Consumers that mmap or
range-read bytes from SegmentPayloadInfo should call
SegmentPayloadInfo::verify_payload before trusting those bytes.
For byte-native query paths, use consumer sidecars. segstore reserves and
garbage-collects segstore.idx.<segment-id>.<kind> next to the source segment,
but the consumer owns the sidecar format and compatibility checks. A postings
crate can store a raw postings block there; an ANN crate can store graph pages
there. SidecarEnvelope is available for the repeated magic/version/segment-id/
recipe/CRC byte envelope, but recipe meaning and payload decoding stay in the
consumer. segstore.seg.<id> remains the durable source payload.
§Compaction
compact() merges all segments into one and purges tombstones.
compact_tiers() runs size-tiered compaction (Cassandra/Lucene-style): segments
are grouped into size buckets and a full bucket is merged, smallest first, never
exceeding max_merged_len items, with larger segments frozen out so the biggest
one is never rewritten by tiering. Scheduling is the consumer’s: call
compact_tiers() when convenient (e.g. a background thread), or set
Options::auto_compact to run it inline after a flush. segment_sizes() and the
CompactionStats returned by both expose the segment-count and merge-cost signal
to watch as the corpus grows.
For bulk ingest (an index build phase), extend(items) syncs the WAL once per
batch instead of per item.
§Concurrent reads
Single writer, many readers. reader() returns a cloneable, thread-safe Reader;
reader.view() takes a consistent point-in-time View of the segments and
tombstones that a query holds (lock-free) for its whole duration, even while the
writer adds, deletes, or compacts on another thread. Visibility is commit-style:
a view reflects the state as of the last checkpoint() (which compaction also
performs), so writes since then become visible after the next checkpoint. This is
the Lucene SearcherManager / Tantivy Searcher model, made light by segstore’s
in-memory segments (a View is Arc clones; an old segment’s memory frees when
the last view holding it drops). Publishing only at the checkpoint keeps the
snapshot off the ingest hot path; republishing per write would make bulk ingest
quadratic. View::segment_ids() plus try_index_name(id, kind) lets readers load
consumer sidecars without holding the writer.
§Examples
cargo run --release --example inverted_indexindexed 4 docs; df(rust)=3
after delete(1): df(rust)=2
[PASS] segstore backs an updatable inverted index: build, delete, compact, recoverexamples/README.md covers the other examples (vector search, sidecars) with captured output.
§Status
0.x; the API and on-disk format may change between minor versions.
§License
Dual-licensed under MIT or Apache-2.0. Generic durable segmented store.
segstore provides the LSM-style lifecycle shared by updatable indexes,
immutable segments plus tombstone deletes plus a write-ahead log plus
checkpoint and compaction, on top of durability. It is generic over the
segment payload: a consumer implements Store to say how a batch of items
becomes a segment and how segments merge during compaction, and segstore
owns the durability and the orchestration.
The split mirrors the rest of the retrieval stack: a storage substrate
(postings, a graph index) keeps its own representation while delegating the
mutable-and-persistent machinery here, the same way it already delegates the
raw WAL/checkpoint primitives to durability.
§What it owns vs what the consumer owns
segstoreowns: the append-only WAL of operations, the in-memory buffer of not-yet-flushed adds, the ordered list of immutable segments, the tombstone set, checkpoint snapshots, and crash recovery (replay the WAL past the last checkpoint).- The consumer owns: the segment representation (an opaque
Serializetype), how a batch of live items becomes one segment (Store::build_segment), how segments merge while dropping tombstoned ids (Store::merge_segments), and querying (iterateSegmentedStore::segments+SegmentedStore::buffer, filtering each segment’s copies withSegmentedStore::is_live_in).
§Example
use segstore::{DefaultStore, SegmentedStore};
use durability::MemoryDirectory;
let dir = MemoryDirectory::arc();
let mut s = SegmentedStore::open(dir, DefaultStore::<u32, String>::new(), 2).unwrap();
s.add(1, "a".into()).unwrap();
s.add(2, "b".into()).unwrap();
s.delete(2).unwrap();
assert!(s.is_live(&1) && !s.is_live(&2));For custom segment layouts, implement Store directly.
§Durability
A checkpoint is the commit point. It persists each new segment to its own
segstore.seg.<id> file (written once, never rewritten), then atomically
writes a small manifest (segstore.manifest, CRC-checked) naming the current
segment files + tombstones, then rotates the WAL: a fresh generation
(segstore.wal.<epoch>) is started and the old one deleted, so the log never
grows past one checkpoint interval. Because only new segments are written, a
checkpoint is O(new data), not O(total): the Lucene segments_N / RocksDB
MANIFEST model. The manifest records the epoch it covers; recovery loads the
named segment files and replays only that epoch’s WAL.
The write order makes every crash window safe: new segment files are durable
before the manifest names them, and superseded segment files are GC’d only
after the new manifest is durable. A crash before the manifest leaves orphan
segment files the next open never reads and garbage-collects; a crash after it
leaves the old files as the orphans, GC’d the same way. The WAL, not the
segment files, is the durability backbone: an add/delete is durable once
its WAL record is, so a partial checkpoint never loses an acknowledged write
(recovery replays the WAL onto the last good manifest). On a filesystem backend
each segment file and the manifest pass a power-loss barrier (fsync of the file
and parent dir); in-memory backends publish atomically without one.
SyncPolicy chooses the WAL write durability: the default SyncPolicy::Flush
is a visibility boundary (userspace -> OS), while SyncPolicy::Fsync syncs
every record to stable storage (filesystem backend only).
Recovery is point-in-time: the WAL is read best-effort, so a torn final record
(the expected damage from a crash mid-write) is truncated and the consistent
prefix recovered. This is the same default as RocksDB’s kPointInTimeRecovery.
It does NOT detect corruption beyond the torn tail (a bit-flip of an
already-committed interior record): each record is CRC-checked, so such a record
is never decoded as garbage, but best-effort read stops at it and drops the rest.
Media-rot detection (a strict “fail on any corruption” mode) is out of scope for
this crash-consistency WAL; a consumer needing it should use checksummed storage.
A CRC-corrupt manifest or segment file is a hard error on open, never misread.
On-disk format note: 0.3 replaced 0.2’s single monolithic segstore.ckpt
checkpoint blob with the manifest + per-segment-file layout above. A 0.1
unsuffixed segstore.wal and a 0.2 segstore.ckpt (with no manifest) are each
detected and rejected with a clear error rather than misread. The manifest
now ends with a versioned extension listing superseded copies (see
SegmentedStore::add); a manifest without it is read as having none, and
an older segstore that does not know the extension ignores it.
§Memory model
The on-disk layout is segment-per-file, but the current read API is still an
in-memory segment model: SegmentedStore::open deserializes every manifest
segment into Arc<Store::Segment>, and View::segments exposes those loaded
segments. This is not yet an out-of-core reader for corpora larger than RAM.
Such consumers need a future reader shape that exposes stable segment ids and
segment file handles (or mmap-backed consumer readers) while preserving the
same manifest, checkpoint, and garbage-collection invariants.
Modules§
- sidecar
- Derived per-segment sidecars with a consumer-owned format.
Structs§
- Compaction
Stats - What a compaction did, for the consumer to track merge cost vs corpus size (the signal that a multi-segment store is outgrowing the search-all-segments model).
- Default
Store - Default vec-backed segment model for append-only source batches.
- Options
- Options for opening a
SegmentedStore. - Reader
- A cloneable, thread-safe handle for concurrent snapshot reads while the writer
mutates. Obtain via
SegmentedStore::reader; clone freely across threads. - Segment
Catalog - Checkpointed segment metadata without deserializing segment payloads.
- Segment
Payload Info - Location and integrity metadata for the serialized payload inside a segment file.
- Segmented
Store - A generic, durable, segmented mutable store.
- Sidecar
Envelope - Consumer-owned sidecar envelope with checked shared mechanics.
- Sidecar
Payload Info - Payload range described by a sidecar envelope header.
- Tier
Config - Size-tiered compaction tuning. Defaults follow Cassandra’s SizeTieredCompactionStrategy
(
min_threshold = 4,max_threshold = 32, bucket band0.5x .. 1.5x) and Lucene’sTieredMergePolicy(a max merged-segment cap, above half of which a segment is frozen out of further tier merges). - View
- A consistent, point-in-time read view of the store, independent of the writer.
Enums§
- Sync
Policy - How durable each WAL write is before
SegmentedStore::add/SegmentedStore::deletereturns.
Traits§
- Store
- The consumer-defined payload model: how items batch into a segment and how segments merge during compaction.
Functions§
- index_
name - Infallible convenience wrapper around
try_index_name. - try_
index_ name - The reserved sidecar file name for a consumer’s per-segment built index.