Skip to content

About

A thread-safe, updatable Finite State Set (FST) providing dynamic insertions, deletions, and efficient queries by managing a persisted FST with add/delete buffers and amortized rebuilds.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

FST Incremental - High Performance Updatable FST

Crates.io Docs.rs License: MPL-2.0

An updatable finite state set and map for Rust.

fst::Set and fst::Map are compact and fast to query, but you can't change them once they're built. IncrementalFstSet and IncrementalFstMap put a sorted in-memory buffer in front of one, so inserts and removes are cheap and reads still see the current state. When the buffer grows past a configured threshold it gets folded back into a fresh FST.

  • The map stores a u64 value on every key.
  • The crate opens no files. You decide when and where to save.
  • Every mutation reports whether the FST changed or only the buffer did, so you can skip the expensive write when the FST is unchanged.

The task guide is README.USAGE.md and the call surface is API_REFERENCE.md.

Example

use fst_incremental::{FstChangeType, IncrementalFstSet};

let set = IncrementalFstSet::new(None).unwrap();
set.insert(b"apple".to_vec()).unwrap();
set.insert(b"apricot".to_vec()).unwrap();
assert!(set.contains(b"apple").unwrap());

set.remove(b"apple").unwrap();
assert!(!set.contains(b"apple").unwrap());

assert_eq!(set.force_rebuild().unwrap().change_type, FstChangeType::FstRebuilt);

Install

[dependencies]
fst_incremental = "1"

The fst crate is re-exported as fst_incremental::fst, so you do not need your own dependency on it to name an Automaton or bring Streamer into scope.

Feature Default Effect
serde yes Derives Serialize/Deserialize on SerializableFstBuffers, CompactArenaSet, SerializableFstMapBuffers and CompactArenaMap, so the mutation buffer can be persisted in a format of your choosing.

Common tasks

To do this Use
Build a set in memory IncrementalFstSet::new
Map keys to u64 values IncrementalFstMap, with insert(key, value) and get
Load one from FST bytes you already hold IncrementalFstSet::from_data
Load a large one without reading it in IncrementalFstSet::from_persisted_mmap
Add or remove a single key insert, remove
Load many keys at once bulk_insert, then finish_bulk_operations_and_rebuild_if_needed
Test membership contains
Walk every key in order stream
Run an automaton (prefix, fuzzy, regex) over the set search
Decide what needs writing to disk the FstChangeType on every mutation result
Save the set or map persisted_fst_as_bytes plus buffers_snapshot
Control when rebuilds happen FstConfigOptions
See what rebuilds are costing get_metrics
Know what each operation costs docs/benches

About

A thread-safe, updatable Finite State Set (FST) providing dynamic insertions, deletions, and efficient queries by managing a persisted FST with add/delete buffers and amortized rebuilds.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages