GitHub - crabbuild/prolly: Prolly is a content-addressed ordered map built on prolly trees. It gives applications immutable snapshots, cheap branching, structural sharing, efficient diffs and merges, sync primitives, and verifiable key/range proofs.

Prolly publishes the prolly Rust library crate. Users depend on the package as prolly-map, while code imports stay concise: use prolly::{Config, Prolly};. The crate provides content-addressed prolly tree storage primitives: an immutable, ordered key-value index over byte keys and byte values, with stable content-derived structure for efficient structural sharing, diff, merge, and bulk loading. At the API boundary, a Tree is a small persistent handle: root: Option<Cid> points at the content-addressed root node. config: Config records the chunking and encoding parameters used by the tree. The actual nodes live in a pluggable Store. Operations clone and rewrite only the affected path or subtrees, write new content-addressed nodes, and return a new Tree handle. All storage-backed tree work is implemented once by a runtime-neutral, async-first engine. AsyncProlly<S: AsyncStore> uses it directly; Prolly<S: Store> drives the same complete operation through an inline ready-only adapter. The synchronous path does not create a runtime, park a thread, or dispatch store calls to Tokio. Architecture The same diagram is also rendered as diagram/prolly-tree-architecture@2x.png for contexts that prefer raster images. The full end-user documentation set lives in docs/, with getting started material, guides, cookbook recipes, architecture, design spec, implementation notes, roadmap, and language-porting guidance. The canonical cookbook is docs/cookbook.md. Native approximate nearest-neighbor indexing is documented in docs/proximity-map.md. Breaking changes and release qualification are recorded in CHANGELOG.md. Interactive visualizer The browser app in 3rd/prolly-tree-visualizer executes mutations against this repository's real @crabbuild/prolly-wasm binding and renders the resulting content-addressed tree, lookup paths, structural diffs, and storage history. For application builders who want a Git-like repository layer on top of prolly trees, see the proposed prolly-vcs design. It keeps prolly-map focused on immutable ordered maps while outlining a separate crate with a general backend-neutral KvStore substrate for commits, refs, reflogs, patches, merge orchestration, sync planning, and repository-level GC. What this crate gives you Ordered byte-key lookup with lexicographic key ordering. Immutable updates: put, delete, and batch return a new Tree. Content-addressed nodes: each node CID is the SHA-256 hash of deterministic node bytes. Deterministic content-defined chunking using xxHash64 boundary checks. Structural sharing between versions because unchanged nodes keep the same CID. Efficient diff and range diff by pruning equal CIDs and disjoint child spans. Three-way merge with conflict resolver support. CRDT-style conflict-free merge strategies. Lazy range iteration and cursor-based traversal. Batch mutation paths for sorted, grouped, append-heavy, and multi-leaf writes. Parallel bulk builders for large initial trees. Pluggable storage through the Store trait, with memory, SQLite, and optional RocksDB implementations. Merkle-style missing-node planning and copy helpers for store sync. Snapshot namespace helpers for branch, tag, checkpoint, and custom roots. A transaction-safe VersionedMap facade with automatic heads, immutable content-derived versions, pinned reads, proofs, comparison and merge, backup/sync, typed codecs, subscriptions, multi-map transactions, bounded history, and scoped GC. A strict IndexedMap coordinator for runtime-defined, non-unique secondary indexes with one-root atomic publication, finite operation budgets, sparse and multi-valued terms, KeysOnly/Include/All projections, exact historical snapshots, durable pins, safe GC, structured diagnostics, and verified bounded transfer. Applications open it through the same engine.indexed_map(...) shape on Prolly or AsyncProlly; both paths use the same canonical state format and strict transactional root publication. Native async support is first class for PostgreSQL, MySQL, Redis, Turso, DynamoDB, Cosmos DB, and Spanner, with synchronous facades available when a blocking application needs them. Store-independent single-key, shared multi-key, complete range, cursor-page, and diff-page proofs for a tree root. Tree statistics for inspecting shape, fill factor, fanout, and serialized size. A hard-cut deterministic proximity map with exact lookup, filtered best-first search, localized canonical COW, overflow/external vectors, SQ8/PQ/HNSW acceleration, async/SIMD execution, typed replication/GC, and descriptor-bound proofs. Quick start use prolly::{Config, MemStore, Prolly}; let store = MemStore::new(); let prolly = Prolly::new(store, Config::default()); let tree = prolly.create(); let tree = prolly .put(&tree, b"name".to_vec(), b"Alice".to_vec()) .unwrap(); let value = prolly.get(&tree, b"name").unwrap(); assert_eq!(value, Some(b"Alice".to_vec())); let tree = prolly.delete(&tree, b"name").unwrap(); assert!(prolly.get(&tree, b"name").unwrap().is_none()); All update APIs are persistent. The old Tree handle remains valid as long as the store still contains the nodes it references. Standalone checkout This directory can be opened as its own repository. The Rust manifests under this tree declare their own package metadata, dependency versions, and lint settings. Run the core crate from the repository root: cargo check --all-targets cargo test cargo run --example basic_map Provider stores and Rust bindings live in nested packages. Check them with --manifest-path: cargo check --manifest-path stores/prolly-store-redis/Cargo.toml --all-targets cargo check --manifest-path bindings/uniffi/Cargo.toml --all-targets cargo check --manifest-path bindings/wasm/Cargo.toml --target wasm32-unknown-unknown More copyable examples live in examples/: agent_event_log.rs: append-heavy agent event logs for messages, tools, memory writes, checkpoints, and summaries. background_compaction.rs: retention-aware event-log compaction, summary index rebuild, and GC. basic_map.rs: put, get, delete, and range scan. batch_build.rs: bulk build plus tree stats. diff_merge.rs: diff and conflict-free three-way merge. resolver.rs: delete-aware merge resolvers. secondary_index.rs: declare, build, query, verify, replace, retain, export, and import strict IndexedMap indexes. indexed_map_real_world.rs: run 14 production-shaped patterns for status, customer, tenant, time, sparse, multi-valued, covering, path, geospatial, text, and historical indexes. materialized_view.rs: derive and update a materialized view from source diffs, with source/view roots in manifests. crdt_merge.rs: LWW, multi-value, delete/update, diagnostics, and base-aware custom merge examples. conversation_memory.rs: canonical memory roots, agent attempt branches, merge, and CAS publish. deterministic_rag_snapshot.rs: record exact index roots for reproducible RAG answers and rollback. document_chunk_index.rs: document/chunk key conventions, blob-backed text, and vector sidecar IDs. vector_sidecar.rs: keep embeddings in a sidecar vector engine while prolly roots preserve retrieval metadata. versioned_map.rs: use the built-in managed map facade for atomic edits, history, diff, rollback, and retention. provenance_values.rs: values that carry source, parser, embedding, model, parent chunk, and CID provenance. file_blob_store.rs: durable blob offload and blob GC. filesystem_snapshot.rs: Git-like filesystem snapshots with file blobs and named roots. Adapter-specific examples include semantic_rag.rs, a fully offline 1,536-dimensional ProximityMap that persists its corpus and named descriptor in SQLite, reopens it across process runs, and emits ranked RAG citations plus an LLM-ready context block. The standalone prolly-gluesql integration turns a complete GlueSQL database into one transactional Prolly tree, with durable branches, immutable versions, secondary indexes, logical diffs, historical reads, and an optional SQLite-backed CLI. Native Rust store adapters live under stores/. The prolly-store-turso adapter embeds the native async Turso Database engine for local storage and optionally exposes explicit Turso Cloud push/pull behind its sync Cargo feature. Key helpers Keys are raw bytes and sort lexicographically. For application-level schemas, use KeyBuilder to build segment-safe composite keys and prefix_range to scan one logical namespace: use prolly::{prefix_range, Config, KeyBuilder, MemStore, Prolly}; let prolly = Prolly::new(MemStore::new(), Config::default()); let mut tree = prolly.create(); let conversation = KeyBuilder::new() .push_str("tenant") .push_str("t1") .push_str("conversation") .push_str("c42") .finish(); let message_key = KeyBuilder::from_prefix(conversation.clone()) .push_u64(7) .finish(); tree = prolly.put(&tree, message_key, b"hello".to_vec()).unwrap(); let (start, end) = prefix_range(&conversation); let messages = prolly .range(&tree, &start, end.as_deref()) .unwrap() .collect::<Result<Vec<_>, _>>() .unwrap(); assert_eq!(messages.len(), 1); Use push_u64, push_u128, push_i64, push_i128, and push_timestamp_millis when numeric order must match byte order. Use decode_segments in tests and diagnostics, and debug_key for readable logs. Key and range proofs Proof APIs let a reader verify map content against a root CID without opening the backing store. Verification recomputes node CIDs and checks child links before returning verified data. Use the smallest proof shape that matches the exchange: prove_key: prove one value or one absence prove_keys: prove several keys while sharing proof nodes prove_range: prove every entry in [start, end) prove_prefix: prove every entry under one logical key prefix prove_range_page: prove one cursor page prove_diff_page: prove one bounded diff page against base and target roots inspect_proof_bundle: read bundle kind, bounds, roots, and counts verify_proof_bundle: verify opaque canonical bundle bytes Wrap canonical bundle bytes in an HMAC-SHA256 envelope when peers need tamper detection, application