Overlay mechanism for key-value embedded databases

x 8d220f215b feat: Add persistent tree caches to database overlays 3 weeks ago
benches 8d220f215b feat: Add persistent tree caches to database overlays 3 weeks ago
src 8d220f215b feat: Add persistent tree caches to database overlays 3 weeks ago
tests 8d220f215b feat: Add persistent tree caches to database overlays 3 weeks ago
.gitignore 7fdf312f9c Initial commit 3 months ago
Cargo.toml d719f1a20b perf: Index retained managed tree overlay history 3 weeks ago
LICENSE.md 7fdf312f9c Initial commit 3 months ago
README.md 8d220f215b feat: Add persistent tree caches to database overlays 3 weeks ago

README.md

kvdb-overlay

This Rust library serves as a minimal overlay mechanism for various key-value embedded databases.

This mechanism enables us to simulate changes in a database/tree so that keys and values can be dynamically mutated, while avoiding having to change the underlying database. With this, we can perform changes to the trees and access the latest changes in-memory, and then only when we're satisfied with the results, we can actually atomically write it into the actual database.

This functionality can also serve as a rollback-like mechanism for the database.

Currently supported databases:

Usage examples are offered in the repository as test units, and docs can be found on docs.rs/kvdb-overlay.

Overlay Types

TreeOverlay provides data operations, batch aggregation, and data checkpoints. ManagedTreeOverlay adds standalone history, diff capture, replay, cleanup, and key references; construct it from a tree or an existing plain overlay with empty bookkeeping. DatabaseOverlay owns database history and key/tree references over plain live/dropped data components. Ownership checks use each owner's history indexes; reference_count() and the database's tree_reference_count() scan retained history only when explicitly queried. On a managed tree, use inner() to borrow the data overlay for persistence and set_tree(&Tree) to bind a phantom without changing data, history, references, or checkpoints.

For plain data-only persistence:

use kvdb_overlay::{Database, TreeOverlay};

let (db, _directory) = Database::open_temp()?;
let tree = db.open_tree_default("records")?;
let mut overlay = TreeOverlay::new(&tree);
overlay.insert(b"key", b"accepted")?;
overlay.checkpoint();
overlay.insert(b"key", b"speculative")?;
overlay.revert_to_checkpoint();
db.write_tree_overlays_changes(&[&overlay])?;

Batch persistence leaves the plain overlay's cached data intact.

Both bookkeeping owners retain an oldest-first queue of captured diffs:

  • Direct edits and add_diff(packet) mutate data only.
  • diff() previews the next local delta without changing bookkeeping.
  • capture() retains that delta and acquires its references, including a queue entry for an empty step. Multiple packets can form one local capture.
  • history() borrows retained diffs oldest first; explicitly clone an archive when it must outlive confirmation.
  • confirm() retires one oldest step after caller persistence. With no history, it leaves current data unchanged, including uncaptured edits. It returns () on managed trees and Result<Option<Arc<DatabaseOverlayStateDiff>>> on databases, where rebinding can fail. Database confirmation returns the retired payload; None means there was no captured step.
  • reset() clears the complete queue and references while preserving current data, bindings, and checkpoint. The next capture uses the backend baseline.

Use DatabaseOverlayStateDiff::new_delta(&overlay.state) to inspect all current database changes against the backend regardless of retained history. For a managed tree, use:

let inner = managed.inner();
let delta = TreeOverlayStateDiff::new_delta(&inner.tree, &inner.state)?;

Successful full database apply() persists current changes, including uncaptured edits, then clears pending data, history, and references only after backend work succeeds. Pass frequently used tree names as persistent_tree_caches to new() to keep their live caches open through confirm(), apply_front(), and apply(). Pass &[] for normal cache eviction:

let mut overlay = DatabaseOverlay::new(&db, &["records"])?;
overlay.open_tree_default("records")?;
overlay.insert("records", b"key", b"value")?;
overlay.apply()?;
assert_eq!(overlay.get("records", b"key")?.unwrap().as_ref(), b"value");

Names are copied, not opened automatically; persisted data is cleaned up normally. Successful direct/replayed drops remove names; recreation does not restore retention. Checkpoint rollback restores the set. Clones own independent sets; reset() preserves them. Full apply() checkpoints the clean retained caches and current set.

For a managed tree, persist the front packet through the caller, then confirm it. Bind a phantom to a real tree before writing:

use kvdb_overlay::{Database, ManagedTreeOverlay};

let (db, _directory) = Database::open_temp()?;
let tree = db.open_tree_default("records")?;
let mut managed = ManagedTreeOverlay::new(&tree);
managed.insert(b"key", b"value")?;
managed.capture()?;
if let Some(diff) = managed.history().next() {
    db.write_tree_overlays_diff(&managed.inner().tree, diff, false)?;
}
managed.confirm();

For incremental database persistence, apply_front() writes and confirms only the oldest captured step. Later steps and uncaptured edits remain pending. With no history it returns None; an empty captured step is still consumed and returned as Some. Like database confirm(), it returns the popped Arc without copying the payload. Keeping it does not retain logical references in the overlay.

use kvdb_overlay::{Database, DatabaseOverlay};

let (db, _directory) = Database::open_temp()?;
let mut overlay = DatabaseOverlay::new(&db, &[])?;
overlay.open_tree_default("records")?;
for value in [b"D0", b"D1", b"D2"] {
    overlay.insert("records", b"key", value)?;
    overlay.capture()?;
}
overlay.insert("records", b"key", b"uncaptured")?;
let d0 = overlay.apply_front()?.unwrap();
// Database: D0; history: [D1, D2]; current value: uncaptured.
// The returned d0 remains available for archiving or inverse replay.

For caller-controlled persistence, borrow history().next(), create/drop its trees, write its aggregated batches, then call confirm() after successful persistence.

Key/value batches use native cross-tree atomic writes. Physical tree creation/drop are nontransactional; persistence ordering, coordination between overlays, flushing, and recovery belong to the caller. Database confirmation prepares fallible rebinding before releasing data, references, or the queue entry.

Clones independently copy current data, reference ownership, retained-history queues, indexes, and the data checkpoint while sharing backend handles and immutable captured diff payloads; confirming or dropping one leaves the other owner's bookkeeping intact.

Checkpoints preserve history while snapshotting current data. Database snapshots also retain tree catalogs, bindings, and persistent cache names. The speculative flow is checkpoint(); /* data changes */; revert_to_checkpoint(), with no diff preview, capture, confirmation, or registration in between. Rollback preserves existing references and retained history. Rolling a database overlay back past a confirmed step panics in debug builds; take a new checkpoint after confirming.

Reading Without an Extra Copy

Tree::get, TreeOverlay::get, ManagedTreeOverlay::get, and DatabaseOverlay::get return a Value handle without copying the bytes into a Vec<u8>:

if let Some(value) = overlay.get("my_tree", b"key")? {
    let bytes: &[u8] = value.as_ref();
    // Pass bytes to a slice deserializer, or use Cursor::new(value)
    // with a deserializer that accepts std::io::Read.
}

Cached values borrow the overlay; backend values retain an owned backend handle. Keep the value alive while borrowing its bytes. An overlay cannot be mutated while its returned value is still in use. Tree::get returns an owned handle that can outlive the tree.

To obtain an independent buffer, consume the handle with into_vec():

let owned: Option<Vec<u8>> = overlay.get("my_tree", b"key")?.map(|value| value.into_vec());

This explicitly copies the bytes, allowing the vector to outlive overlay mutation or destruction. clone() and to_owned() clone the handle, not the bytes; they do not detach cached values from the overlay. This is a breaking change from the previous vector-returning get; the separate get_value method has been removed. Other APIs such as insert, remove, and iterators still return owned vectors.

Reading through the handle avoids an extra value-buffer allocation and copy. It does not stream from disk or avoid loading the entire value into memory; backend reads and deserialization may still allocate. Wrapping the value in a synchronous or async cursor does not change that.

License

GNU AGPLv3.