Crate prolly

Expand description

§Prolly Trees

A Rust implementation of Prolly Trees - content-addressable ordered search indexes that combine the efficiency of B+ trees with deterministic merging capabilities.

§Features

Ordered key-value storage: Keys are sorted lexicographically (byte comparison)
Content-addressable nodes: Each node has a unique CID (Content Identifier) derived from its content
Deterministic structure: Same content always produces the same tree structure
Efficient diff/merge: Compare trees by comparing root hashes, skip identical subtrees
Pluggable storage: Implement the Store trait for custom backends

§Quick Start

use prolly::{Prolly, MemStore, Config};

// Create a store and tree manager
let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());

// Create an empty tree
let tree = prolly.create();

// Insert key-value pairs (returns a new tree - immutable)
let tree = prolly.put(&tree, b"name".to_vec(), b"Alice".to_vec()).unwrap();
let tree = prolly.put(&tree, b"age".to_vec(), b"30".to_vec()).unwrap();

// Retrieve values
let name = prolly.get(&tree, b"name").unwrap();
assert_eq!(name, Some(b"Alice".to_vec()));

// Delete keys
let tree = prolly.delete(&tree, b"age").unwrap();
assert!(prolly.get(&tree, b"age").unwrap().is_none());

§Range Iteration

use prolly::{Prolly, MemStore, Config};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let mut tree = prolly.create();

// Insert some data
tree = prolly.put(&tree, b"a".to_vec(), b"1".to_vec()).unwrap();
tree = prolly.put(&tree, b"b".to_vec(), b"2".to_vec()).unwrap();
tree = prolly.put(&tree, b"c".to_vec(), b"3".to_vec()).unwrap();

// Iterate over all keys
for result in prolly.range(&tree, &[], None).unwrap() {
    let (key, val) = result.unwrap();
    println!("{:?} -> {:?}", String::from_utf8_lossy(&key), String::from_utf8_lossy(&val));
}

// Iterate over a specific range [b, c)
for result in prolly.range(&tree, b"b", Some(b"c")).unwrap() {
    let (key, val) = result.unwrap();
    // Only yields "b" -> "2"
}

§Diff and Merge

use prolly::{Prolly, MemStore, Config, Diff};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());

// Create base tree
let base = prolly.create();
let base = prolly.put(&base, b"a".to_vec(), b"1".to_vec()).unwrap();

// Create two divergent branches
let left = prolly.put(&base, b"b".to_vec(), b"2".to_vec()).unwrap();
let right = prolly.put(&base, b"c".to_vec(), b"3".to_vec()).unwrap();

// Compute diff
let diffs = prolly.diff(&base, &left).unwrap();
// diffs contains: Added { key: b"b", val: b"2" }

// Three-way merge (no conflicts since changes are disjoint)
let merged = prolly.merge(&base, &left, &right, None).unwrap();

// Merged tree has all keys: a, b, c
assert!(prolly.get(&merged, b"a").unwrap().is_some());
assert!(prolly.get(&merged, b"b").unwrap().is_some());
assert!(prolly.get(&merged, b"c").unwrap().is_some());

§Batch Building

For bulk loading data, use BatchBuilder for parallel tree construction:

use prolly::{BatchBuilder, MemStore, Config, Prolly};
use std::sync::Arc;

let store = Arc::new(MemStore::new());
let config = Config::default();

// Build tree from many entries in parallel
let mut builder = BatchBuilder::new(store.clone(), config.clone());
for i in 0..1000 {
    builder.add(format!("key{:04}", i).into_bytes(), format!("val{}", i).into_bytes());
}
let tree = builder.build().unwrap();

// Use the tree with Prolly
let prolly = Prolly::new(store, config);
let val = prolly.get(&tree, b"key0042").unwrap();
assert!(val.is_some());

§Named Roots

Use named-root helpers when an application needs durable names for immutable tree snapshots:

A named root is a mutable pointer, not a live view. put, delete, batch, and merge return new immutable Tree handles and do not automatically advance any name. Publish the replacement tree explicitly, preferably with compare_and_swap_named_root when another writer could update the same name.

use prolly::{Config, MemStore, Prolly};
use std::sync::Arc;

let store = Arc::new(MemStore::new());
let prolly = Prolly::new(store.clone(), Config::default());
let tree = prolly.create();
let tree = prolly.put(&tree, b"name".to_vec(), b"Trail".to_vec()).unwrap();

let update = prolly
    .compare_and_swap_named_root(b"main", None, Some(&tree))
    .unwrap();
assert!(update.is_applied());

let loaded = prolly.load_named_root(b"main").unwrap().unwrap();
assert_eq!(prolly.get(&loaded, b"name").unwrap(), Some(b"Trail".to_vec()));

§Custom Storage Backend

Implement the Store trait for custom storage:

use prolly::{Store, BatchOp};

struct MyStore {
    // Your storage implementation
}

impl Store for MyStore {
    type Error = std::io::Error;

    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>, Self::Error> {
        // Implement get
        Ok(None)
    }

    fn put(&self, key: &[u8], value: &[u8]) -> Result<(), Self::Error> {
        // Implement put
        Ok(())
    }

    fn delete(&self, key: &[u8]) -> Result<(), Self::Error> {
        // Implement delete
        Ok(())
    }

    fn batch(&self, ops: &[BatchOp]) -> Result<(), Self::Error> {
        // Implement batch operations
        Ok(())
    }
}

§Configuration

Customize tree behavior with Config:

use prolly::{Config, Encoding};

let config = Config::builder()
    .min_chunk_size(4)        // Min entries before considering split
    .max_chunk_size(1024)     // Max entries per node
    .chunking_factor(128)     // Controls average node size
    .hash_seed(42)            // Seed for boundary detection
    .encoding(Encoding::Raw)  // Value encoding type
    .node_cache_max_nodes(50_000) // Optional decoded-node cache cap
    .node_cache_max_bytes(256 * 1024 * 1024) // Optional serialized-byte cap
    .build();

§Advanced Extensibility

The library provides extensible traits for advanced use cases:

§Streaming Diff

Use StreamingDiffer for memory-efficient diff operations on large trees:

use prolly::{Prolly, MemStore, Config, Diff};
use std::sync::Arc;

let store = Arc::new(MemStore::new());
let prolly = Prolly::new(store.clone(), Config::default());

let base = prolly.create();
let other = prolly.put(&base, b"key".to_vec(), b"val".to_vec()).unwrap();

// Stream differences lazily (memory-efficient for large trees)
for diff_result in prolly.stream_diff(&base, &other).unwrap() {
    match diff_result {
        Ok(diff) => println!("{:?}", diff),
        Err(e) => eprintln!("Error: {}", e),
    }
}

§CRDT Merge

Use ConflictFreeMerger for automatic conflict resolution:

use prolly::{CrdtConfig, CrdtResolution, MergeStrategy, DeletePolicy, TimestampedValue};

// Last-Writer-Wins strategy
let lww_config = CrdtConfig::lww();

// Multi-Value strategy (preserves all concurrent values)
let mv_config = CrdtConfig::multi_value();

// Custom merge function
let custom_config = CrdtConfig::custom(|conflict| {
    match &conflict.left {
        Some(value) => CrdtResolution::value(value.clone()),
        None => CrdtResolution::delete(),
    }
});

§Parallel Processing

Use ParallelRebalancer for multi-threaded batch operations:

use prolly::{ParallelConfig, DefaultParallelRebalancer};

// Configure parallel processing
let config = ParallelConfig {
    max_threads: 4,           // Use 4 threads (0 = auto)
    parallelism_threshold: 50, // Parallelize when > 50 items
};

let rebalancer = DefaultParallelRebalancer::new();

Modules§

resolver: Ready-made standard merge resolvers.

Structs§

AuthenticatedProofBundleVerification: Verification result for serialized authenticated proof envelope bytes.
AuthenticatedProofEnvelope: HMAC-authenticated envelope for any proof bundle.
AuthenticatedProofEnvelopeVerification: Verification result for an AuthenticatedProofEnvelope.
BatchApplyResult: Result of applying a batch with execution stats.
BatchApplyStats: Store-neutral execution stats for a batch mutation.
BatchBuilder: Batch builder for parallel tree construction.
BatchWriter: Batch writer with configurable settings.
BatchWriterConfig: Configuration for batch write operations.
BlobGcPlan: Dry-run garbage-collection plan for offloaded blobs.
BlobGcReachability: Live blob set discovered from one or more retained tree roots.
BlobGcSweep: Result of sweeping a blob garbage-collection plan.
BlobRef: Content-addressed reference to an offloaded blob.
CborCodec: CBOR codec for serde-backed application values.
ChangedSpan: Half-open key range that was recently changed.
ChangedSpanHint: Recently changed key spans for a specific root transition.
Cid: Content identifier - a 32-byte SHA-256 hash
Config: Tree configuration
ConfigBuilder: Builder for Config
Conflict: Merge conflict information
CrdtConfig: Configuration for conflict-free merging.
Cursor: A cursor pointing to a specific position in a prolly tree.
CursorIterator: Iterator wrapper for cursor-based traversal.
CursorWindow: Bounded result for a stateless cursor seek.
DefaultConflictFreeMerger: Default conflict-free merger implementation.
DefaultParallelRebalancer: Default implementation of ParallelRebalancer using rayon.
DefaultStreamingDiffer: Default streaming differ using dual cursor traversal.
DiffCursor: Streaming diff iterator using dual cursor traversal.
DiffPage: A bounded page of diff results.
DiffPageProof: Proof for a resumable diff page.
DiffPageProofVerification: Store-independent verification result for a DiffPageProof.
DiffTraversalStats: Counters collected while traversing two trees for diff.
FileBlobStore: Durable filesystem-backed blob store.
FileNodeStore: Durable filesystem node store using content-addressed object layout.
GcPlan: Dry-run garbage-collection plan for an explicit candidate set.
GcReachability: Live node set discovered from one or more retained tree roots.
GcSweep: Result of sweeping a garbage-collection plan.
JsonCodec: JSON codec for serde-backed application values.
KeyBuilder: Builder for segment-safe composite keys.
KeyProof: Root-to-leaf proof for one key.
KeyProofVerification: Store-independent verification result for a KeyProof.
LargeValueConfig: Large-value offload policy.
MemBlobStore: In-memory blob store for tests and lightweight applications.
MemBlobStoreError: Error type for MemBlobStore.
MemStore: In-memory store for testing and simple use cases
MemStoreError: Error type for MemStore operations
MergeExplanation: Result and trace from Prolly::merge_explain and its async counterpart when the async-store feature is enabled.
MergePolicyRegistry: Domain-level conflict resolver selected by key.
MergePolicyRule: One registered merge policy rule.
MergeTrace: Structured diagnostic events for a merge operation.
MissingNodeCopy: Result of copying missing nodes from one store to another.
MissingNodePlan: Dry-run plan for making a destination store able to read one source tree.
MultiKeyProof: Shared root proof for multiple keys.
MultiKeyProofVerification: Store-independent verification result for a MultiKeyProof.
MultiValueSet: A set of concurrent values for MV-Register semantics.
MutationBuffer: Write buffer for batching mutations with size limits.
NamedRoot: A named root loaded through a crate::Prolly manager.
NamedRootManifest: A named root manifest returned by manifest-store scans.
NamedRootSelection: Result of loading roots for a retention policy.
Node: A node in the Prolly Tree
NodeBuilder: Builder pattern for Node construction
OwnedProllyTransaction: A strict optimistic transaction that owns a cloned store handle.
OwnedTransactionOverlayStore: Owned store overlay used by OwnedProllyTransaction.
ParallelConfig: Configuration for parallel rebalancing operations.
Prolly: Prolly tree manager
ProllyMetricsSnapshot: Cumulative cache and node I/O metrics for a prolly manager.
ProllyTransaction: A strict optimistic transaction over a Prolly manager.
ProofBundleSummary: Lightweight metadata decoded from canonical proof bundle bytes.
ProofBundleVerification: Store-independent verification result for opaque canonical proof bundle bytes.
ProvedDiffPage: A bounded diff page paired with a store-independent proof for that page.
ProvedRangePage: A bounded range page paired with a store-independent proof for that page.
RangeCursor: Stable cursor token for resumable range scans.
RangeIter: Iterator over key-value pairs in a range.
RangePage: A bounded page of range-scan results.
RangePageProof: Proof for a resumable range page.
RangePageProofVerification: Store-independent verification result for a RangePageProof.
RangeProof: Complete proof for all entries in a key range.
RangeProofVerification: Store-independent verification result for a RangeProof.
ReverseCursor: Stable cursor token for resumable reverse scans.
ReversePage: A bounded page of reverse-scan results.
RootCondition: A named-root value that must still match at transaction commit time.
RootManifest: Durable named-root payload.
SnapshotBundle: Self-contained transport bundle for one tree and its reachable node bytes.
SnapshotBundleNode: One content-addressed node included in a portable tree snapshot bundle.
SnapshotBundleSummary: Compact metadata for a validated snapshot bundle.
SnapshotBundleVerification: Result of verifying a snapshot bundle as a self-contained tree.
SnapshotManager: Convenience API for branch, tag, checkpoint, or custom snapshot roots.
SnapshotRoot: A snapshot root with namespace-local id and manifest metadata.
SnapshotSelection: Result of loading several snapshots by namespace-local id.
SortedBatchBuilder: Streaming bulk builder for entries that are already sorted by key.
StatsComparison: Combined statistics comparison between two tree snapshots.
StatsDiff: Difference between two statistics objects
StatsPercentageChange: Percentage change between two statistics objects
StructuralDiffCursor: Stable checkpoint token for structural diff traversal.
StructuralDiffPage: A bounded page from the structural diff iterator.
TimestampedValue: A value with an embedded timestamp for LWW ordering.
Tombstone: Logical deletion value with causal metadata.
TransactionConflict: Details for a failed transaction validation.
TransactionOverlayError
Tree: A Prolly Tree handle
TreeDebugComparedNode: A compared node annotated with its sharing status.
TreeDebugComparison: Structural sharing comparison between two tree roots.
TreeDebugComparisonLevel: Per-level structural sharing summary.
TreeDebugLevel: Debug metadata for all nodes at one tree level.
TreeDebugNode: Inspectable node metadata for debug tooling.
TreeDebugView: Debug view of a tree grouped by level.
TreeStats: Statistics about a Prolly tree structure
VersionedCborCodec: Versioned CBOR codec with schema/version validation on decode.
VersionedJsonCodec: Versioned JSON codec with schema/version validation on decode.
VersionedValue: Deterministic schema/version envelope for an application value.

Enums§

BatchOp: Batch operation for atomic writes
CrdtResolution: Conflict-free custom resolution.
DeletePolicy: Policy for delete vs update conflicts.
Diff: Difference between two trees
Encoding: Encoding type for values
Error: Prolly tree errors
FileBlobStoreError: Error type for FileBlobStore.
FileNodeStoreError: Error type for FileNodeStore.
KeyDecodeError: Error returned by decode_segments.
ManifestUpdate: Result of a named-root compare-and-swap update.
MergeFallbackReason: Why merge left a fast path and continued through a broader path.
MergeFastPath: Root-level fast path used by a merge.
MergePolicyRuleLabel: Human-readable label for a merge policy rule.
MergeResolutionKind: Compact form of a resolver result for trace events.
MergeReuseReason: Why a subtree CID could be reused by the structural merge path.
MergeStrategy: Merge strategy for conflict-free merging.
MergeTraceEvent: A single event emitted while explaining a merge.
MergeTraceStage: Where in the merge algorithm a trace event occurred.
Mutation: A mutation to apply to the tree
NamedRootRetention: Policy for selecting named roots to retain during garbage collection.
NamedRootUpdate: Result of a named-root compare-and-swap through a crate::Prolly manager.
ProofBundleKind: Canonical proof bundle family.
Resolution: Resolution for a standard three-way merge conflict.
RootWrite: A named-root write staged by a transaction.
SnapshotNamespace: Namespace used to derive stable named-root keys for snapshots.
StructuralDiffMarker: Public marker for one suspended structural diff frame.
TransactionNodeWrite: A content-addressed node write staged by a transaction.
TransactionUpdate: Result of committing a transaction.
TreeDebugNodeStatus: Whether a compared subtree is shared or unique to one side.
ValueRef: Value stored in a leaf by the large-value helper layer.

Constants§

DEFAULT_CHUNKING_FACTOR: Default chunking factor: 128 = ~0.78% boundary probability
DEFAULT_HASH_SEED: Default seed for the hash function
DEFAULT_INLINE_VALUE_THRESHOLD: Default maximum value size stored directly in leaf nodes by large-value helpers.
DEFAULT_MAX_CHUNK_SIZE: Default maximum number of key-value pairs in a node
DEFAULT_MIN_CHUNK_SIZE: Default minimum entries before considering chunk boundary
INIT_LEVEL: Initial (leaf) level from which the prolly tree is built
SNAPSHOT_BRANCH_PREFIX: Root-name prefix used for branch snapshots.
SNAPSHOT_BUNDLE_FORMAT_VERSION: Current in-memory format version for portable tree snapshot bundles.
SNAPSHOT_CHECKPOINT_PREFIX: Root-name prefix used for checkpoint snapshots.
SNAPSHOT_TAG_PREFIX: Root-name prefix used for immutable release/tag snapshots.

Traits§

BlobStore: Content-addressed blob storage used by large-value helpers.
BlobStoreScan: Blob stores that can enumerate known blob references.
ConflictFreeMerger: Trait for conflict-free merge operations using CRDT semantics.
ManifestStore: Storage for named root manifests.
ManifestStoreScan: Manifest stores that can enumerate durable named roots.
NodeStoreScan: Storage backends that can enumerate content-addressed node CIDs.
ParallelRebalancer: Trait for parallel rebalancing operations.
Store: Storage backend trait for Prolly Trees
StreamingDiffer: Trait for streaming diff operations.
TransactionalStore: Store support for strict atomic transaction commits.
ValueCodec: Codec for converting typed application values to and from stored bytes.

Functions§

append_batch: Apply mutations optimized for append-only workloads.
debug_key: Format arbitrary key bytes with printable ASCII and \xNN escapes.
decode_cbor: Deserialize typed CBOR value bytes.
decode_json: Deserialize typed JSON value bytes.
decode_segments: Decode a composite key built from escaped segments.
encode_cbor: Serialize a typed value as compact CBOR bytes.
encode_json: Serialize a typed value as compact JSON bytes.
encode_segment: Encode one segment for use in a composite key.
i64_key: Encode an i64 so lexicographic byte ordering matches numeric ordering.
i128_key: Encode an i128 so lexicographic byte ordering matches numeric ordering.
inspect_proof_bundle: Decode lightweight metadata from canonical proof bundle bytes.
is_boundary: Check if entry at index creates a chunk boundary in a node.
is_boundary_config: Check if entry creates a chunk boundary using Config.
is_tombstone_value: Return true if bytes start with the tombstone magic prefix.
prefix_end: Return the smallest exclusive upper bound for all keys with prefix.
prefix_range: Return the half-open byte range covering all keys with prefix.
sign_proof_bundle_hmac_sha256: Build an HMAC-SHA256 authenticated envelope for canonical proof bundle bytes.
snapshot_id_from_name: Return the snapshot id if name belongs to namespace.
snapshot_root_name: Build the durable named-root key for id in namespace.
timestamp_millis_key: Encode a Unix timestamp in milliseconds using unsigned lexicographic order.
tombstone_compaction: Return a physical delete mutation when stored_value is a tombstone.
tombstone_upsert: Build an upsert mutation that stores tombstone at key.
u64_key: Encode a u64 so lexicographic byte ordering matches numeric ordering.
u128_key: Encode a u128 so lexicographic byte ordering matches numeric ordering.
verify_authenticated_proof_bundle: Decode, authenticate, and verify serialized proof envelope bytes.
verify_authenticated_proof_envelope: Verify an authenticated proof envelope with the shared secret.
verify_diff_page_proof: Verify a diff-page proof without consulting a store.
verify_key_proof: Verify a key proof without consulting a store.
verify_multi_key_proof: Verify a shared multi-key proof without consulting a store.
verify_proof_bundle: Decode and verify opaque canonical proof bundle bytes.
verify_range_page_proof: Verify a resumable range-page proof without consulting a store.
verify_range_proof: Verify a range proof without consulting a store.

Type Aliases§

CustomMergeFn: Custom merge function type.
MergePolicyFn: Shared merge policy function used by MergePolicyRegistry.
Resolver: Conflict resolution strategy
TimestampExtractor: Timestamp extractor function type.

Crate prolly

Crate prolly Copy item path

§Prolly Trees

§Features

§Quick Start

§Range Iteration

§Diff and Merge

§Batch Building

§Named Roots

§Custom Storage Backend

§Configuration

§Advanced Extensibility

§Streaming Diff

§CRDT Merge

§Parallel Processing

Modules§

Structs§

Enums§

Constants§

Traits§

Functions§

Type Aliases§

Crate prolly