Struct ConstTree 

pub struct ConstTree<K: Key, const V: usize, H: WriteHook<K> = NoHook, D: Durability = Bitcask> { /* private fields */ }

A tree with fixed-size keys and values. All values are stored inline in SkipList nodes. Reads never touch disk — zero I/O reads.

Generic over D: Durability (default: Bitcask). Use Fixed backend for frequent updates without compaction (FixedTree is a type alias for ConstTree<K, V, Fixed>).

Batch operations

get_many does one sorted finger-walk over the index for a list of keys; update_many applies a per-key closure grouped by shard (per-shard isolation, no global atomicity). See docs/superpowers/specs/26-06-24-armdb-batch-tree-ops.md.

Each ConstTree owns its storage engine — one tree = one database directory.

Write hooks

Uses WriteHook<K>. on_write fires on put/insert/delete/cas/compare_delete/update/fetch_update, and on each mutation inside atomic() (replayed after the lock is released, in application order). on_init fires once per live entry during migrate() or replay_init(). Old value is always provided in on_write — NEEDS_OLD_VALUE is ignored (value is inline, zero cost).

Usage

let tree = ConstTree::<16, 64>::open("data/users", Config::balanced().build())?;
tree.put(&key, &value)?;
tree.close()?;

Iteration

iter(), range(), and prefix_iter() all return ConstIter which implements Iterator + DoubleEndedIterator with Item = (K, [u8; V]). Lock-free, zero disk I/O.

for (key, value) in tree.iter() { }
let latest = tree.prefix_iter(&user_id).take(20).collect::<Vec<_>>();
let oldest = tree.iter().rev().take(5);  // DoubleEndedIterator

Implementations

impl<K: Key, const V: usize> ConstTree<K, V, NoHook, Bitcask>

pub fn open(path: impl AsRef<Path>, config: Config) -> DbResult<Self>

Open or create a ConstTree at the given path. Recovers the index from existing data files on disk.

Exclusive access

Takes an exclusive lease on the directory (db.lock) and holds it for as long as the returned handle — or anything that outlives it, such as a replication server or client — is alive. A second open of the same directory returns DbError::Locked, whether it comes from another process or from another live handle in this one: two engines over one shard set would run independent in-memory indexes and silently drop each other’s writes.

The kernel releases the lease when the handle is dropped, including on SIGKILL, panic or OOM, so there is no stale lock file to clean up. To reopen in the same process, drop every handle first — shadowing a binding (let tree = ...) does not drop it.

On NFS flock is emulated with POSIX locks: cross-process exclusion still works, but the same-process rejection is lost.

impl<K: Key, const V: usize, H: WriteHook<K>> ConstTree<K, V, H, Bitcask>

pub fn open_hooked( path: impl AsRef<Path>, config: Config, hook: H, ) -> DbResult<Self>

Open or create a ConstTree with a write hook for secondary index maintenance.

Exclusive access

Takes an exclusive lease on the directory (db.lock) and holds it for as long as the returned handle — or anything that outlives it, such as a replication server or client — is alive. A second open of the same directory returns DbError::Locked, whether it comes from another process or from another live handle in this one: two engines over one shard set would run independent in-memory indexes and silently drop each other’s writes.

The kernel releases the lease when the handle is dropped, including on SIGKILL, panic or OOM, so there is no stale lock file to clean up. To reopen in the same process, drop every handle first — shadowing a binding (let tree = ...) does not drop it.

On NFS flock is emulated with POSIX locks: cross-process exclusion still works, but the same-process rejection is lost.

pub fn clean_shutdown(&self) -> DbResult<()>

Full clean shutdown: flush buffers, write hint files (if enabled), fsync.

pub fn close(self) -> DbResult<()>

Graceful shutdown: write hint files (if enabled), flush write buffers + fsync.

pub fn flush_buffers(&self) -> DbResult<()>

Flush all shard write buffers to disk (without fsync).

pub fn config(&self) -> &Config

Get the database configuration.

pub fn compact(&self) -> DbResult<usize>

Trigger a background compaction pass across all shards.

pub fn sync_hints(&self) -> DbResult<()>

Write hint files for all active shard files. Call during graceful shutdown.

impl<K: Key, const V: usize> ConstTree<K, V, NoHook, Fixed>

pub fn open(path: impl AsRef<Path>, config: FixedConfig) -> DbResult<Self>

Open or create a ConstTree with Fixed (fixed-slot) backend. Recovers the index from existing data files on disk.

Exclusive access

Takes an exclusive lease on the directory (db.lock) and holds it for as long as the returned handle — or anything that outlives it, such as a replication server or client — is alive. A second open of the same directory returns DbError::Locked, whether it comes from another process or from another live handle in this one: two engines over one shard set would run independent in-memory indexes and silently drop each other’s writes.

The kernel releases the lease when the handle is dropped, including on SIGKILL, panic or OOM, so there is no stale lock file to clean up. To reopen in the same process, drop every handle first — shadowing a binding (let tree = ...) does not drop it.

On NFS flock is emulated with POSIX locks: cross-process exclusion still works, but the same-process rejection is lost.

impl<K: Key, const V: usize, H: WriteHook<K>> ConstTree<K, V, H, Fixed>

pub fn open_with_hook( path: impl AsRef<Path>, config: FixedConfig, hook: H, ) -> DbResult<Self>

Open or create a ConstTree with a write hook, using Fixed (fixed-slot) backend.

Exclusive access

Takes an exclusive lease on the directory (db.lock) and holds it for as long as the returned handle — or anything that outlives it, such as a replication server or client — is alive. A second open of the same directory returns DbError::Locked, whether it comes from another process or from another live handle in this one: two engines over one shard set would run independent in-memory indexes and silently drop each other’s writes.

The kernel releases the lease when the handle is dropped, including on SIGKILL, panic or OOM, so there is no stale lock file to clean up. To reopen in the same process, drop every handle first — shadowing a binding (let tree = ...) does not drop it.

On NFS flock is emulated with POSIX locks: cross-process exclusion still works, but the same-process rejection is lost.

pub fn clean_shutdown(&self) -> DbResult<()>

Full clean shutdown: per-shard sidecar + clean-shutdown flag.

pub fn close(self) -> DbResult<()>

Perform a clean shutdown (Fixed backend).

impl<K: Key, const V: usize, H: WriteHook<K>> ConstTree<K, V, H, Fixed>

pub fn fixed_engine_access(&self) -> Arc<dyn FixedEngineAccess>

Return an Arc<dyn FixedEngineAccess> for this tree’s engine. Used by integration tests to construct a FixedReplicationServer.

impl<K: Key, const V: usize, H: WriteHook<K>, D: Durability> ConstTree<K, V, H, D>

pub fn sweep_expired( &self, now_ms: u64, budget: usize, ) -> DbResult<SweepOutcome>

pub fn set_ttl_sweep(&self, enabled: bool) -> DbResult<()>

pub fn mark_replication_follower(&self)

pub fn rebuild_ttl_index(&self) -> DbResult<()>

pub fn get(&self, key: &K) -> Option<[u8; V]>

Get a value by key. Lock-free, zero disk I/O.

O(log n) — SkipList point lookup.

pub fn get_or_err(&self, key: &K) -> DbResult<[u8; V]>

Get a value by key, returning Err(KeyNotFound) if absent.

pub fn put(&self, key: &K, value: &[u8; V]) -> DbResult<Option<[u8; V]>>

Insert or update a key-value pair. Returns the old value if the key existed.

pub fn insert(&self, key: &K, value: &[u8; V]) -> DbResult<()>

Insert a key-value pair only if the key does not exist. Returns Err(KeyExists) if the key is already present.

pub fn delete(&self, key: &K) -> DbResult<Option<[u8; V]>>

Delete a key. Returns the old value if the key existed.

pub fn atomic<R>( &self, shard_key: &K, f: impl FnOnce(&mut ConstShard<'_, K, V, H, D>) -> DbResult<R>, ) -> DbResult<R>

Atomically execute multiple operations on a single shard. All keys must route to the same shard as shard_key. The closure must be short — shard lock is held for its duration.

pub fn upsert<U: IntoUpsert<[u8; V]>>( &self, key: &K, f: impl FnOnce(Option<&[u8; V]>) -> U, ) -> DbResult<U::Out>

Decide-and-write: insert, update, keep, or delete based on the closure’s Upsert decision. The closure must be short — the shard lock is held across it, so it must not panic and must not call back into this collection (the shard mutex is not reentrant).

pub fn cas( &self, key: &K, expected: &[u8; V], new_value: &[u8; V], ) -> DbResult<()>

Compare-and-swap: if current value == expected, replace with new_value. Returns Ok(()) on success, Err(CasMismatch) if current != expected, Err(KeyNotFound) if key doesn’t exist. Zero I/O — values are inline in SkipList nodes.

pub fn compare_delete(&self, key: &K, expected: &[u8; V]) -> DbResult<()>

Compare-and-delete: if the current value == expected, delete the key. Returns Ok(()) on success, Err(CasMismatch) if current != expected, Err(KeyNotFound) if the key doesn’t exist. Zero I/O on the comparison — values are inline in SkipList nodes. Works on both Bitcask and FixedStore backends.

pub fn update( &self, key: &K, f: impl FnOnce(&[u8; V]) -> [u8; V], ) -> DbResult<Option<[u8; V]>>

Atomically read-modify-write. Returns Some(new_value) if key existed, None otherwise. Zero I/O — values are inline in SkipList nodes. The closure must not be heavy (shard lock is held).

pub fn fetch_update( &self, key: &K, f: impl FnOnce(&[u8; V]) -> [u8; V], ) -> DbResult<Option<[u8; V]>>

Like update(), but returns Some(old_value) instead of the new one.

pub fn contains(&self, key: &K) -> bool

Check if a key exists.

pub fn first(&self) -> Option<(K, [u8; V])>

Return the first entry in index order, or None if empty. With reversed=true (default): the entry with the largest key. O(1) — follows head’s level-0 pointer, skipping marked nodes.

pub fn last(&self) -> Option<(K, [u8; V])>

Return the last entry in index order, or None if empty. With reversed=true (default): the entry with the smallest key.

pub fn prefix_iter(&self, prefix: &[u8]) -> ConstIter<'_, K, V, D::Loc>

Iterate entries whose keys start with prefix.

reversed=true (default): yields matching keys in DESC order. next() is O(1). The first reverse seek is expected O(log n); an m-row reverse walk is expected/amortized O(log n + m).

pub fn iter(&self) -> ConstIter<'_, K, V, D::Loc>

Iterate all entries in index order.

reversed=true (default): DESC. reversed=false: ASC. next() is O(1). The first reverse seek is expected O(log n); an m-row reverse walk is expected/amortized O(log n + m).

pub fn range(&self, start: &K, end: &K) -> ConstIter<'_, K, V, D::Loc>

Iterate entries in [start, end) — start inclusive, end exclusive.

reversed=true (default): DESC within range. reversed=false: ASC. next() is O(1). The first reverse seek is expected O(log n); an m-row reverse walk is expected/amortized O(log n + m).

pub fn range_bounds( &self, start: Bound<&K>, end: Bound<&K>, ) -> ConstIter<'_, K, V, D::Loc>

Iterate entries in range defined by start and end bounds.

Unlike range(), allows Included, Excluded, or Unbounded for each bound independently.

reversed=true (default): DESC within range. reversed=false: ASC. next() is O(1). The first reverse seek is expected O(log n); an m-row reverse walk is expected/amortized O(log n + m).

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn scope<const N: usize>(&self, key: &K) -> Scope<'_, TreeScan<&Self>, N>

Field-granular prefix / range / page builder over this tree’s key space.

pub fn migrate( &self, f: impl Fn(&K, &[u8; V]) -> MigrateAction<[u8; V]>, ) -> DbResult<usize>

Iterate all entries and optionally mutate them. Call once at startup.

The callback receives each (key, value) and returns MigrateAction:

• Keep — no change (fires on_init if NEEDS_INIT)
• Update(new_value) — replace value (fires on_init, hook-free write)
• Delete — remove entry (hook-free delete, no on_init)

on_write is never fired during migration. Returns the number of mutated entries.

pub fn shard_for(&self, key: &K) -> usize

pub fn flush(&self) -> DbResult<()>

Flush the durability backend.

pub fn get_many(&self, keys: &[K]) -> Vec<Option<[u8; V]>>

Batch point-read by a list of keys (tier-3 finger-walk). Lock-free, zero disk I/O. Result is aligned to keys: position i is Some(value) if keys[i] exists, else None. Not snapshot — a concurrent writer may be observed mid-walk. Without concurrent writers, duplicate keys yield the same value at each position.

pub fn update_many<P>( &self, items: Vec<(K, P)>, f: impl Fn(&K, Option<&[u8; V]>, &P) -> Upsert<[u8; V]>, ) -> DbResult<Vec<(K, Applied<[u8; V]>)>>

Batch read-modify-write (tier-2, shard-grouped). The closure decides per key from Option<&value> (None = absent). Keys are grouped by shard and each shard is processed under its own lock, one at a time. Within a shard, items are applied in input order, so a later duplicate of a key sees the prior in-batch result (natural fold). Per-shard isolation only — no rollback, no crash-atomicity. On a real I/O Err the batch stops; the applied prefix is committed and its hooks fire. Result is aligned to items.

impl<K: Key, const V: usize, H: WriteHook<K>> ConstTree<K, V, H, Bitcask>

pub fn start_replication_server( &self, bind_addr: SocketAddr, signal: ShutdownSignal, ) -> DbResult<ReplicationServer>

Install SPSC replication producers into every shard and start a ReplicationServer bound to bind_addr.

Single-call contract

Each call installs fresh SPSC producers, replacing any previously installed ones. Call this at most once per ConstTree instance — a second call will orphan the in-flight producer of any active streaming connection on the first server, which will then observe an empty ring buffer and silently stop forwarding entries.

pub fn start_replication_client( &self, leader_addr: SocketAddr, registry: Arc<ReplicationRegistry>, signal: ShutdownSignal, ) -> DbResult<ReplicationClient>

Start a ReplicationClient that streams entries from leader_addr into registry. Symmetric to Self::start_replication_server.

key_len is derived from size_of::<K>() (the V const-generic is the value byte length, not part of the key).

impl<K, const V: usize, H> ConstTree<K, V, H, Bitcask>

where K: Key + Send + Sync + 'static, H: WriteHook<K> + Send + Sync + 'static,

pub fn as_replication_target(self: &Arc<Self>) -> Box<dyn ReplicationTarget>

Wrap a shared handle to this tree as a Box<dyn ReplicationTarget>.

The returned box holds an Arc clone — the caller retains full read access to the original tree through the Arc while the registry owns the box. This is the intended pattern for follower-side wiring:

let follower = Arc::new(ConstTree::<[u8; 8], 8>::open(path, cfg)?);
let registry = ReplicationRegistry::new(follower.as_replication_target());
// `follower` remains usable for .get() etc.

Trait Implementations

impl<K: Key, const V: usize, H: WriteHook<K>> CompactionIndex<K> for ConstTree<K, V, H, Bitcask>

fn update_if_match(&self, key: &K, old_loc: DiskLoc, new_loc: DiskLoc) -> bool

If the current index points to old_loc, it is updated to new_loc and returns true.

fn contains_key(&self, key: &K) -> bool

Returns true if the key currently exists in the index (i.e. has a live Put).

fn is_live(&self, _shard_id: u8, key: &K, loc: DiskLoc) -> bool

Returns true iff the index currently maps key to exactly loc — i.e. the entry at loc is the live (latest) version of key.

fn invalidate_blocks(&self, _shard_id: u8, _file_id: u32, _total_bytes: u64)

Invalidate cached blocks for a file after compaction replaces its contents.

impl<K, const V: usize, H> FixedReplicationTarget for ConstTree<K, V, H, Fixed>

where K: Key + 'static, H: WriteHook<K> + 'static,

fn shard_count(&self) -> usize

fn key_len(&self) -> usize

fn value_len(&self) -> usize

fn shard_prefix_bits(&self) -> u8

fn shard_occupied_count(&self, shard_id: u8) -> u32

Current number of OCCUPIED slots for shard_id. Used by the client to decide whether to set FLAG_EMPTY_STATE in SyncRequest.

fn shard_dir(&self, shard_id: u8) -> PathBuf

Directory for per-shard cursor files.

fn grow_shard_to(&self, shard_id: u8, min_slot_count: u32) -> DbResult<()>

Grow the shard to at least min_slot_count slots. No-op when follower already has more slots.

fn apply_occupied( &self, shard_id: u8, slot_id: u32, meta: u32, key: &[u8], value: &[u8], ) -> DbResult<ApplyOutcome>

Apply an OCCUPIED slot event. Handles modular version compare, stale-cleanup of old key (rare path), slot pwrite, and index upsert.

fn apply_deleted( &self, shard_id: u8, slot_id: u32, meta: u32, key: &[u8], ) -> DbResult<ApplyOutcome>

Apply a DELETED slot event. Conditional index.remove — only if the index still points to this slot_id.

fn apply_reset( &self, shard_id: u8, slot_id: u32, meta: u32, ) -> DbResult<ApplyOutcome>

fn sync_applied_batch(&self, shard_id: u8) -> DbResult<()>

fn mark_replication_follower(&self)

Disable TTL sweep and require rebuild before re-enabling after follower duty.

impl<K: Key, const V: usize, H: WriteHook<K>> ReplicationTarget for ConstTree<K, V, H, Bitcask>

Available on crate feature replication only.

fn apply_entry( &self, _shard_inner: &mut ShardInner, _shard_id: u8, file_id: u32, entry_offset: u64, header: &EntryHeader, key: &[u8], value: &[u8], ) -> DbResult<ApplyOutcome>

Apply entry with known key/value split (streaming mode, O(1) routing). Returns the outcome so the registry can account dead bytes.

fn try_apply_entry( &self, shard_inner: &mut ShardInner, shard_id: u8, file_id: u32, entry_offset: u64, header: &EntryHeader, raw_after_header: &[u8], ) -> DbResult<ApplyOutcome>

Try to apply entry with CRC matching (catch-up mode). Returns ApplyOutcome::NotMatched if CRC fails (key belongs to a different target).

fn key_len(&self) -> usize

The key length (K) for this tree type.

fn mark_replication_follower(&self)

Disable TTL sweep and require rebuild before re-enabling after follower duty.