# Usage Guide: fst_incremental
Everything needed to build, query, persist and tune an `IncrementalFstSet`.
## Table of Contents
* [Core Concepts](#core-concepts)
* [Quick Start](#quick-start)
* [Creating a Set](#creating-a-set)
* [Inserting and Removing Keys](#inserting-and-removing-keys)
* [Loading Many Keys at Once](#loading-many-keys-at-once)
* [Testing Membership](#testing-membership)
* [Streaming Every Key](#streaming-every-key)
* [Searching with an Automaton](#searching-with-an-automaton)
* [Saving and Loading a Set](#saving-and-loading-a-set)
* [Saving](#saving)
* [Loading](#loading)
* [Skipping Writes That Are Not Needed](#skipping-writes-that-are-not-needed)
* [Controlling When Rebuilds Happen](#controlling-when-rebuilds-happen)
* [The Add Threshold](#the-add-threshold)
* [The Delete Ratio](#the-delete-ratio)
* [The Minimum Interval](#the-minimum-interval)
* [Reading Rebuild Metrics](#reading-rebuild-metrics)
* [Sharing a Set Between Threads](#sharing-a-set-between-threads)
* [Why the Design Is Shaped This Way](#why-the-design-is-shaped-this-way)
* [Error Handling](#error-handling)
## Core Concepts
* **Finite state set** — a trie compressed into a directed acyclic graph, so shared prefixes and shared suffixes are stored once. Compact and fast to query, but built in one pass and immutable afterwards.
* **Persisted component** — the immutable `fst::Set` holding the bulk of the keys. Either a byte vector in memory or a memory-mapped file.
* **Mutation buffer** — the sorted in-memory structure holding every change made since the last rebuild. One buffer covers both insertions and deletions.
* **Tombstone** — a buffer entry marking a key as deleted. Removing a key that lives in the persisted component cannot erase it, so the key is tombstoned and resolved at the next rebuild.
* **Live key** — a key the set logically contains: present in the persisted component without a tombstone, or present in the buffer as an insertion.
* **Rebuild** — merging the persisted component with the mutation buffer into a fresh FST, dropping tombstoned keys. Clears the buffer.
* **Amortized rebuild** — the policy of letting the buffer absorb many cheap changes and paying for the merge once, rather than per change.
* **Rebuild threshold** — the buffer size, or tombstone-to-key ratio, at which a mutation triggers a rebuild.
* **Minimum rebuild interval** — an optional floor on the gap between rebuilds. A rebuild that comes due inside the window is deferred to the next call past it.
* **Deferred rebuild** — a rebuild that was due but held back by the minimum interval. It runs at the next opportunity; the set stays correct meanwhile.
* **Change type** — what a mutation actually did, reported on every mutating call: the FST was rebuilt, only the buffer moved, or nothing changed.
* **Caller-managed persistence** — this crate performs no file I/O for you. It hands you bytes and takes bytes back; where they live is your decision.
* **Automaton** — a matcher from the `fst` crate (prefix, range, regex, Levenshtein) that can be run over a set without scanning it.
## Quick Start
```rust
use fst_incremental::{FstChangeType, IncrementalFstSet};
use fst_incremental::fst::Streamer;
fn main() -> fst_incremental::Result<()> {
let set = IncrementalFstSet::new(None)?;
set.insert(b"apple".to_vec())?;
set.insert(b"apricot".to_vec())?;
set.insert(b"banana".to_vec())?;
assert!(set.contains(b"apple")?);
assert_eq!(set.len()?, 3);
set.remove(b"apple")?;
assert!(!set.contains(b"apple")?);
let mut stream = set.stream()?;
while let Some(key) = stream.next() {
println!("{}", String::from_utf8_lossy(&key));
}
drop(stream);
assert_eq!(set.force_rebuild()?.change_type, FstChangeType::FstRebuilt);
Ok(())
}
```
## Creating a Set
Three constructors, all taking the same optional configuration. Start empty:
```rust
use fst_incremental::IncrementalFstSet;
let set = IncrementalFstSet::new(None).unwrap();
```
From FST bytes you already hold in memory:
```rust,no_run
use fst_incremental::IncrementalFstSet;
let bytes: Vec<u8> = std::fs::read("words.fst").unwrap();
let set = IncrementalFstSet::from_data(Some(bytes), None).unwrap();
```
From a file, mapped rather than read. Prefer this for a large set: startup does not scale with the file size and the pages are shared with the page cache.
```rust,no_run
use fst_incremental::IncrementalFstSet;
use std::path::Path;
let set = IncrementalFstSet::from_persisted_mmap(Path::new("words.fst"), None).unwrap();
```
The mapped file must not be modified while the set is alive.
## Inserting and Removing Keys
Both take bytes, not strings. Both return an `FstMutationResult` saying what happened.
```rust
use fst_incremental::{FstChangeType, IncrementalFstSet};
let set = IncrementalFstSet::new(None).unwrap();
let result = set.insert(b"apple".to_vec()).unwrap();
assert_eq!(result.change_type, FstChangeType::BuffersModified);
let again = set.insert(b"apple".to_vec()).unwrap();
assert_eq!(again.change_type, FstChangeType::NoChange);
set.remove(b"apple").unwrap();
assert!(!set.contains(b"apple").unwrap());
```
Removing a key that lives only in the persisted component writes a tombstone rather than erasing it. The key stops being visible immediately; the space is reclaimed at the next rebuild.
Re-inserting a tombstoned key resurrects it, without a second copy of the bytes:
```rust
use fst_incremental::IncrementalFstSet;
let set = IncrementalFstSet::new(None).unwrap();
set.insert(b"apple".to_vec()).unwrap();
set.force_rebuild().unwrap();
set.remove(b"apple").unwrap();
assert!(!set.contains(b"apple").unwrap());
set.insert(b"apple".to_vec()).unwrap();
assert!(set.contains(b"apple").unwrap());
```
## Loading Many Keys at Once
`insert` takes the write lock and checks the rebuild thresholds on every call. For a batch, use `bulk_insert`: it takes the lock once and never rebuilds mid-batch.
```rust
use fst_incremental::IncrementalFstSet;
let set = IncrementalFstSet::new(None).unwrap();
let keys: Vec<Vec<u8>> = vec![b"apple".to_vec(), b"apricot".to_vec(), b"banana".to_vec()];
set.bulk_insert(keys).unwrap();
set.finish_bulk_operations_and_rebuild_if_needed().unwrap();
```
Call `finish_bulk_operations_and_rebuild_if_needed` when the batch is done. Without it the keys stay in the buffer, correct but unconsolidated, until some later mutation trips a threshold.
## Testing Membership
```rust
use fst_incremental::IncrementalFstSet;
let set = IncrementalFstSet::new(None).unwrap();
set.insert(b"apple".to_vec()).unwrap();
assert!(set.contains(b"apple").unwrap());
assert!(!set.contains(b"cherry").unwrap());
assert!(!set.is_empty().unwrap());
assert_eq!(set.len().unwrap(), 1);
```
`contains` is a buffer probe followed by an FST lookup. `len` and `is_empty` walk the merged stream instead, because the live count is not stored anywhere; `is_empty` stops at the first key, but `len` is O(n).
## Streaming Every Key
`stream` yields live keys in lexicographic order, merging the persisted component with the buffer and skipping tombstones as it goes. Nothing is rebuilt and nothing is collected.
```rust
use fst_incremental::IncrementalFstSet;
use fst_incremental::fst::Streamer;
let set = IncrementalFstSet::new(None).unwrap();
set.bulk_insert(vec![b"banana".to_vec(), b"apple".to_vec()]).unwrap();
let mut stream = set.stream().unwrap();
while let Some(key) = stream.next() {
println!("{}", String::from_utf8_lossy(&key));
}
```
`next` comes from `fst::Streamer`, which is re-exported as `fst_incremental::fst::Streamer`. The stream is not an `Iterator`: it hands out a value borrowed from itself, which `Iterator` cannot express.
A live stream holds a read lock on the set. Drop it before mutating, or the next write will block:
```rust
use fst_incremental::IncrementalFstSet;
use fst_incremental::fst::Streamer;
let set = IncrementalFstSet::new(None).unwrap();
set.insert(b"apple".to_vec()).unwrap();
let mut keys = Vec::new();
let mut stream = set.stream().unwrap();
while let Some(key) = stream.next() {
keys.push(key);
}
drop(stream);
set.insert(b"cherry".to_vec()).unwrap();
```
## Searching with an Automaton
`search` runs any `fst::Automaton` over the set and returns the matches sorted and deduplicated.
```rust
use fst_incremental::IncrementalFstSet;
use fst_incremental::fst::Automaton;
use fst_incremental::fst::automaton::Str;
let set = IncrementalFstSet::new(None).unwrap();
set.bulk_insert(vec![b"apple".to_vec(), b"apricot".to_vec(), b"banana".to_vec()]).unwrap();
let matches = set.search(Str::new("ap").starts_with()).unwrap();
assert_eq!(matches.len(), 2);
```
Matches are returned as a `Vec`, not a stream, because hits from the persisted component and hits from the buffer have to be merged before they can be ordered.
## Saving and Loading a Set
A set's state is two pieces: the FST bytes and the pending mutations. Save both or neither. Where they go is your decision; the crate opens no files of its own.
### Saving
```rust
use fst_incremental::IncrementalFstSet;
use std::fs;
use std::path::Path;
fn save(set: &IncrementalFstSet, fst_path: &Path, buffer_path: &Path) -> std::io::Result<()> {
fs::write(fst_path, set.persisted_fst_as_bytes())?;
let snapshot = set.buffers_snapshot();
let encoded = rmp_serde::to_vec_named(&snapshot).expect("buffer snapshot is serializable");
fs::write(buffer_path, encoded)
}
```
Calling `force_rebuild` first folds the buffer into the FST, so the buffer file comes out empty and loading is a single mapped file. That trades a rebuild at save time for a cheaper load.
### Loading
```rust
use fst_incremental::{FstConfigOptions, IncrementalFstSet, SerializableFstBuffers};
use std::fs;
use std::path::Path;
fn load(fst_path: &Path, buffer_path: &Path) -> fst_incremental::Result<IncrementalFstSet> {
let mut options = FstConfigOptions::new();
if buffer_path.exists() {
let encoded = fs::read(buffer_path)?;
let buffers: SerializableFstBuffers =
rmp_serde::from_slice(&encoded).expect("buffer file is well formed");
options = options.with_initial_buffer(buffers.into_mutation_buffer());
}
IncrementalFstSet::from_persisted_mmap(fst_path, Some(options))
}
```
Any serde format works. The examples use `rmp-serde` because the buffer is mostly raw bytes and MessagePack does not expand them.
### Skipping Writes That Are Not Needed
Every mutating call reports what changed, so the FST file can be left alone when only the buffer moved:
```rust
use fst_incremental::{FstChangeType, IncrementalFstSet};
let set = IncrementalFstSet::new(None).unwrap();
let result = set.insert(b"apple".to_vec()).unwrap();
match result.change_type {
FstChangeType::FstRebuilt => { /* write both files */ }
FstChangeType::BuffersModified => { /* write only the buffer file */ }
FstChangeType::NoChange => { /* write nothing */ }
_ => {}
}
```
`FstChangeType` is `#[non_exhaustive]`, so a match on it needs a wildcard arm.
## Controlling When Rebuilds Happen
`FstConfigOptions` decides when a mutation triggers a merge. Every constructor takes it.
```rust
use fst_incremental::{FstConfigOptions, IncrementalFstSet};
let options = FstConfigOptions::new()
.with_rebuild_adds_count(50_000)
.with_rebuild_dels_ratio(0.25)
.with_min_rebuild_interval_ms(10_000);
let set = IncrementalFstSet::new(Some(options)).unwrap();
```
### The Add Threshold
Rebuild once the buffer holds this many live keys. Default 10,000.
```rust
use fst_incremental::{FstChangeType, FstConfigOptions, IncrementalFstSet};
let options = FstConfigOptions::new().with_rebuild_adds_count(2);
let set = IncrementalFstSet::new(Some(options)).unwrap();
set.insert(b"a".to_vec()).unwrap();
let result = set.insert(b"b".to_vec()).unwrap();
assert_eq!(result.change_type, FstChangeType::FstRebuilt);
```
Raise it to make writes cheaper and reads slightly dearer; lower it to keep the buffer small. Reads stay correct either way.
### The Delete Ratio
Rebuild once tombstones reach this fraction of the persisted key count. Default 0.3. Tombstones are what keeps deleted keys occupying space, so this is the knob that reclaims it.
```rust
use fst_incremental::{FstConfigOptions, IncrementalFstSet};
let options = FstConfigOptions::new().with_rebuild_dels_ratio(0.1);
let set = IncrementalFstSet::new(Some(options)).unwrap();
```
### The Minimum Interval
A floor on the gap between rebuilds, off by default. A rebuild that comes due inside the window is deferred and reported as `BuffersModified`; it runs on the first call past the window. Use it to stop a burst of writes from rebuilding repeatedly.
```rust
use fst_incremental::{FstConfigOptions, IncrementalFstSet};
let options = FstConfigOptions::new()
.with_rebuild_adds_count(1)
.with_min_rebuild_interval_ms(60_000);
let set = IncrementalFstSet::new(Some(options)).unwrap();
```
`force_rebuild` respects this too. There is no way to rebuild inside the window.
## Reading Rebuild Metrics
Every field is a running total over the life of the set, not a rate. Divide by `num_rebuilds` for a per-rebuild average.
```rust
use fst_incremental::IncrementalFstSet;
let set = IncrementalFstSet::new(None).unwrap();
set.insert(b"apple".to_vec()).unwrap();
set.force_rebuild().unwrap();
let metrics = set.get_metrics().unwrap();
assert_eq!(metrics.num_rebuilds, 1);
if metrics.num_rebuilds > 0 {
let avg_micros = metrics.rebuild_duration_micros_sum / metrics.num_rebuilds as u64;
println!("average rebuild: {avg_micros}us");
}
```
Rising `rebuild_duration_micros_sum` against a flat `num_rebuilds` means each merge is getting more expensive, which is the signal to raise the add threshold.
## Sharing a Set Between Threads
Every method takes `&self` and locks internally, so an `Arc` is all that is needed. Readers run concurrently; a rebuild takes the write lock and excludes them for its duration.
```rust
use fst_incremental::IncrementalFstSet;
use std::sync::Arc;
use std::thread;
let set = Arc::new(IncrementalFstSet::new(None).unwrap());
let mut handles = Vec::new();
for n in 0..4u8 {
let set = Arc::clone(&set);
handles.push(thread::spawn(move || {
set.insert(vec![b'k', n]).unwrap();
}));
}
for handle in handles {
handle.join().unwrap();
}
assert_eq!(set.len().unwrap(), 4);
```
A `stream` holds a read lock for as long as it is alive, so a thread that keeps one open blocks every writer. Collect what you need and drop it.
## Why the Design Is Shaped This Way
**One buffer, not two.** An earlier shape kept insertions in a `BTreeSet` and deletions in a `HashSet`. A single sorted arena replaced both: it stores keys as spans into one contiguous byte vector rather than as individual `Vec<u8>` allocations, it answers "inserted, deleted, or absent" in one binary search rather than two lookups, and it can be walked in sorted order, which is what both the merge and the stream need. Insertion and deletion of the same key also collapse naturally, since a tombstone flag on an existing entry costs nothing.
**Rebuilds stream through a temporary file.** A merge writes to an anonymous temp file through an 8KB buffered writer and memory-maps the result, rather than building a `Vec<u8>` on the heap. Peak memory during a rebuild is therefore independent of the set size.
**Persistence is the caller's.** Sets get stored in wildly different places, so the crate hands over bytes and takes bytes back instead of guessing at a file layout. The `FstChangeType` on every mutation exists to make that cheap: without it a caller would have to rewrite the FST on every change, which is the cost the buffer exists to avoid.
## Error Handling
`IncrementalFstError` has two variants, both wrapping the layer beneath. It is `#[non_exhaustive]`, so a match needs a wildcard arm.
```rust
use fst_incremental::{IncrementalFstError, IncrementalFstSet};
use std::path::Path;
match IncrementalFstSet::from_persisted_mmap(Path::new("missing.fst"), None) {
Ok(set) => println!("{} keys", set.len().unwrap()),
Err(IncrementalFstError::Io(e)) => eprintln!("could not open or map the file: {e}"),
Err(IncrementalFstError::Fst(e)) => eprintln!("the bytes are not a valid FST: {e}"),
Err(e) => eprintln!("{e}"),
}
```
`Io` covers opening and mapping the FST file and writing the temporary file a rebuild streams into. `Fst` covers bytes that do not parse as an FST and failures from the builder during a merge. Both implement `From`, so `?` works in a function returning `fst_incremental::Result<T>`.