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§

chunking: Built-in persisted chunking policies.
resolver: Ready-made standard merge resolvers.

Structs§

ActiveIndexControl
ActiveIndexHealth: Bounded startup-health details for one active index generation.
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.
BoundaryDetector: Resettable boundary state for one ordered tree level.
BuildParallelism: Runtime-only worker limit for independent construction work.
BytesKeyCodec: Identity codec for byte-vector keys.
CanonicalSpliceStats: Observable logical and physical work performed by canonical_splice.
CanonicalWriteStats: Store-neutral work performed by a canonical write.
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.
ChunkingSpec: Persisted content-defined chunking configuration.
Cid: Content identifier - a 32-byte SHA-256 hash
Config: Tree configuration
ConfigBuilder: Builder for Config
Conflict: Merge conflict information
ContentGcPlan: Global typed-content GC plan over an explicit candidate set.
ContentGcSweep: Applied typed-content GC result.
ContentGraphCopy: Descendant-first replication result.
ContentGraphLimits: Hard limits for untrusted typed graph traversal.
ContentGraphWalk: Deterministic descendant-first traversal report.
ContentRootManifest: Immutable typed-root publication payload.
ContentRootPublication
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.
DecodedPhysicalIndexKey
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.
HierarchyConfig: Deterministic hierarchy promotion configuration.
HnswBuildStats: Logical work reported by a deterministic graph build.
HnswConfig: Deterministic HNSW shape and serving limits.
HnswIndex: Persisted HNSW serving graph bound to one proximity descriptor CID.
IndexBuildResult: Outcome of one idempotent dynamic index registration attempt.
IndexCheckpoint: Exact hidden-index version selected for one source version.
IndexControl: Small deterministic root that fences all raw source-map mutations.
IndexVerification: Full semantic comparison of one rebuilt index and its selected checkpoint.
IndexedHeadRecord: Canonical current selection of one source version and all active index checkpoints.
IndexedMap: Strict coordinator for one source map and its active secondary indexes.
IndexedMapEditor: Last-write-wins mutation collector for IndexedMap::edit.
IndexedMapHealth: Structurally validated current state of an IndexedMap.
IndexedMapMetricsSnapshot: Cumulative logical work counters for one IndexedMap handle.
IndexedRetentionResult: Deterministic root-name pruning result for one indexed source namespace.
IndexedSnapshot: Immutable catalog-selected source and index view.
IndexedSnapshotBundle: Self-contained, canonical transport for one current coordinated snapshot.
IndexedSnapshotBundleIndex: One descriptor/checkpoint/tree selection carried by an indexed bundle.
IndexedSnapshotBundleSummary: Compact validated metadata for an indexed snapshot bundle.
IndexedSnapshotBundleVerification: Complete reachability result for a verified indexed snapshot bundle.
IndexedSnapshotId: Reproducible identity of one catalog-selected indexed snapshot.
IndexedVersion: Complete coordinated publication selected by one catalog version.
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.
MapBackupVersion: One version and its self-contained node bundle in a map catalog backup.
MapCatalogVerification: Successful integrity audit of one complete managed-map catalog.
MapChangeEvent: One observed managed-map head transition.
MapChangeSubscription: Resumable in-process change subscription driven by explicit polling.
MapComparison: A version-pinned comparison between two snapshots of the same managed map.
MapMerge: A three-way merge pinned to a base, current head, and candidate version.
MapReverseIter: Lazy descending iterator backed by bounded reverse pages.
MapSnapshot: An immutable, version-pinned view over one managed map snapshot.
MapVersion: One durable snapshot in a versioned map.
MapVersionId: Content-derived identifier for one index snapshot.
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.
Neighbor: One resolved nearest-neighbor result.
Node: A node in the Prolly Tree
NodeBuilder: Builder pattern for Node construction
OverflowConfig: Canonical physical-node paging configuration.
OwnedProllyTransaction: A strict optimistic transaction that owns a cloned store handle.
OwnedTransactionOverlayStore: Owned store overlay used by OwnedProllyTransaction.
ParallelConfig: Configuration for parallel rebalancing operations.
ProductQuantizationBuildStats: Canonical logical work performed by one PQ build.
ProductQuantizationConfig: Deterministic offline product-quantization training and serving policy.
ProductQuantizationQuality: Reconstruction measurements committed into a PQ manifest.
ProductQuantizer: Source-bound persisted product-quantization sidecar.
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.
ProofAuthentication: Metadata attached when authenticating a snapshot proof bundle.
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.
ProximityBuildStats: Canonical logical work reported independently of worker count.
ProximityConfig: Shape-affecting configuration for a proximity map.
ProximityMap: Immutable exact-key directory plus deterministic ANN hierarchy.
ProximityMembershipProof: Store-independent exact presence or absence proof bound to one PRXI CID.
ProximityMembershipVerification: Verified logical outcome of a descriptor-bound membership proof.
ProximityMutation: One immutable-map mutation. None deletes the key.
ProximityMutationStats: Observable copy-on-write work for one mutation batch.
ProximityRecord: One logical record supplied to a bulk build.
ProximitySearchProof: Self-contained proof for native, PQ, or HNSW search replay.
ProximitySearchRequest: Owned deterministic search request committed by a proof.
ProximitySearchStats: Observable resource use for one search.
ProximitySearchVerification: Verified result and appropriately scoped claim.
ProximityStructuralProof: Complete typed PRXI closure sufficient for store-independent verification.
ProximityStructuralVerification: Authenticated structural summary recomputed from proof objects.
ProximityTree: Persisted handle for the exact directory and derived proximity hierarchy.
ProximityVerification: Full structural verification summary.
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.
RuntimeConfig: Runtime-only tuning that never participates in persisted tree identity.
Savepoint: An overlay checkpoint valid until the next successful flush.
ScalarQuantizationConfig: Node-local symmetric signed-int8 routing configuration.
SearchBudget: Deterministic logical search resource limits.
SearchRequest: One deterministic native proximity search.
SearchResult
SecondaryIndex: One immutable runtime index definition.
SecondaryIndexBuilder: Builder for a general projection-aware runtime definition.
SecondaryIndexCursor: Snapshot- and query-bound cursor for resumable secondary-index scans.
SecondaryIndexDescriptor: Canonical persisted semantic definition for one index generation.
SecondaryIndexEntry: One logical index emission from one source record.
SecondaryIndexError: Error returned by an application index extractor.
SecondaryIndexLimits: Resource bounds applied before index-derived buffers are published.
SecondaryIndexMatch: One decoded physical secondary-index match.
SecondaryIndexPage: One bounded secondary-index query page.
SecondaryIndexRegistry: Deterministically ordered runtime definitions supplied when opening an indexed map.
SecondaryIndexSnapshot: Query handle for one exact hidden-index checkpoint.
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
StringKeyCodec: UTF-8 codec for string keys. Ordering follows UTF-8 byte order.
StructuralDiffCursor: Stable checkpoint token for structural diff traversal.
StructuralDiffPage: A bounded page from the structural diff iterator.
StructuralPatch
TermBounds
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.
TreeFormat: Persisted settings that determine tree shape and content IDs.
TreeStats: Statistics about a Prolly tree structure
TypedContentObject: One authenticated object returned in descendant-first order.
TypedContentRoot: Typed content-addressed root plus decode context required by PRXN objects.
TypedMigrationResult: Result of rewriting every typed value through a schema migration.
TypedVersionedMap: Typed facade over a byte-oriented VersionedMap.
VectorStorageConfig: Canonical inline versus external representative-vector policy.
VersionPruneResult: Result of pruning immutable version roots from a managed map.
VersionedCborCodec: Versioned CBOR codec with schema/version validation on decode.
VersionedJsonCodec: Versioned JSON codec with schema/version validation on decode.
VersionedMap: Built-in versioned map facade over a Prolly engine.
VersionedMapBackup: Portable backup of one complete managed-map catalog.
VersionedMapBatchResult: Managed-map publication plus engine batch execution statistics.
VersionedMapEditor: Mutation collector used by VersionedMap::edit.
VersionedMapsTransaction: One strict transaction spanning any number of managed maps.
VersionedValue: Deterministic schema/version envelope for an application value.
WriteSession: Bounded mutable view over an immutable base tree.

Enums§

AdaptiveQuality: Deterministic approximate-search quality policy.
BatchOp: Batch operation for atomic writes
BoundaryInput: Entry bytes supplied to the boundary hash.
BoundaryRule: Rule used to select a content-defined boundary.
ChunkMeasure: Quantity used to enforce a chunk’s soft size bounds.
ContentManifestUpdate
ContentObjectKind: Authenticated content codec used for one graph object.
CrdtResolution: Conflict-free custom resolution.
DeletePolicy: Policy for delete vs update conflicts.
Diff: Difference between two trees
DistanceMetric: Distance function committed into a proximity-map descriptor.
Encoding: Encoding type for values
Error: Prolly tree errors
FileBlobStoreError: Error type for FileBlobStore.
FileNodeStoreError: Error type for FileNodeStore.
HashAlgorithm: Stable hash algorithms available to persisted chunking policies.
IndexProjection: Bytes stored beside a matching primary key in the physical index tree.
IndexValue: Canonical physical value stored in a secondary-index tree.
IndexedMapUpdate: Conditional indexed-map write outcome.
KeyDecodeError: Error returned by decode_segments.
LogicalPatch
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.
NodeLayoutSpec: Physical encoding used for nodes in a tree.
PendingValue: Pending value in a write-session overlay.
ProofBundleKind: Canonical proof bundle family.
ProximityFilter: Canonical structural restriction applied before leaf scoring.
ProximityProofFilter: Owned, replayable form of every public proximity filter.
ProximitySearchClaim: Scope of the claim established by replay.
ProximitySearchEvent: Deterministic, tamper-evident replay transcript summary.
QueryKernel: Runtime-only deterministic query distance implementation.
Resolution: Resolution for a standard three-way merge conflict.
RootWrite: A named-root write staged by a transaction.
SearchBackend: Search execution backend.
SearchCompletion: Honest completion state for a search result.
SearchPolicy: Logical search termination policy.
SecondaryIndexDirection: Direction captured by a resumable secondary-index cursor.
SnapshotNamespace: Namespace used to derive stable named-root keys for snapshots.
StructuralDiffMarker: Public marker for one suspended structural diff frame.
StructuralEdit
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.
VersionedMapUpdate: Outcome of a compare-and-update operation.

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
DEFAULT_VERSIONED_MAP_RETRIES: Maximum optimistic attempts made by the convenience mutation methods.
INDEXED_SNAPSHOT_BUNDLE_FORMAT_VERSION
INDEX_PHYSICAL_LAYOUT_VERSION
INIT_LEVEL: Initial (leaf) level from which the prolly tree is built
SECONDARY_INDEX_FORMAT_VERSION
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.
VERSIONED_MAP_ROOT_PREFIX: Root namespace reserved for built-in versioned maps.

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.
KeyCodec: Codec for converting typed application keys to and from ordered map bytes.
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.
SecondaryIndexExtractor: Deterministic runtime callback that derives zero or more index emissions.
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.
canonical_splice: Apply logical mutations through the canonical localized writer.
catalog_checkpoint_key
catalog_checkpoints_prefix: Prefix containing every source-version checkpoint record.
catalog_current_key
catalog_descriptor_key
catalog_format_key
catalog_map_id
catalog_retired_key
compare_and_swap_named_content_root
compare_and_swap_named_content_root_with_limits
content_references: Load one authenticated object and return its exact, deterministic typed reference list without recursively walking descendants.
control_record_key
control_root_name
copy_and_publish_content_graph: Replicate a closed graph, then publish its immutable typed-root manifest by name.
copy_content_graph
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_physical_index_key
decode_segments: Decode a composite key built from escaped segments.
descriptor_fingerprint: Hash the canonical semantic descriptor envelope (excluding its fingerprint field).
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.
encode_segment_prefix: Escape a partial segment without appending its terminator.
i64_key: Encode an i64 so lexicographic byte ordering matches numeric ordering.
i128_key: Encode an i128 so lexicographic byte ordering matches numeric ordering.
index_map_id
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.
load_named_content_root
load_named_content_root_with_limits
physical_index_key
plan_content_gc
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.
put_named_content_root
put_named_content_root_with_limits
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.
sweep_content_gc
sweep_content_gc_with_invalidator: Sweep unreachable candidates and invalidate process-local consumers after each successful deletion. Per-object notification keeps caches correct even when a later store deletion fails.
term_bounds_exact
term_bounds_prefix
term_bounds_range
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.
walk_content_graph

Type Aliases§

CustomMergeFn: Custom merge function type.
ExactProximityRecord: Vector and application value returned by an exact-key lookup.
IndexedSourceRecord: One primary key and full source value resolved from the pinned snapshot.
KeyValue: An owned key-value entry returned by ordered tree lookups.
MergePolicyFn: Shared merge policy function used by MergePolicyRegistry.
ProjectedIndexEntry: One primary key and its optional projected bytes.
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