Skip to main content

Crate segstore

Crate segstore 

Source
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_index
indexed 4 docs; df(rust)=3
after delete(1): df(rust)=2
  [PASS] segstore backs an updatable inverted index: build, delete, compact, recover

examples/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

  • segstore owns: 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 Serialize type), how a batch of live items becomes one segment (Store::build_segment), how segments merge while dropping tombstoned ids (Store::merge_segments), and querying (iterate SegmentedStore::segments + SegmentedStore::buffer, filtering each segment’s copies with SegmentedStore::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§

CompactionStats
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).
DefaultStore
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.
SegmentCatalog
Checkpointed segment metadata without deserializing segment payloads.
SegmentPayloadInfo
Location and integrity metadata for the serialized payload inside a segment file.
SegmentedStore
A generic, durable, segmented mutable store.
SidecarEnvelope
Consumer-owned sidecar envelope with checked shared mechanics.
SidecarPayloadInfo
Payload range described by a sidecar envelope header.
TierConfig
Size-tiered compaction tuning. Defaults follow Cassandra’s SizeTieredCompactionStrategy (min_threshold = 4, max_threshold = 32, bucket band 0.5x .. 1.5x) and Lucene’s TieredMergePolicy (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§

SyncPolicy
How durable each WAL write is before SegmentedStore::add / SegmentedStore::delete returns.

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.