crabbuild/prolly 来源：https://github.com/crabbuild/prolly

Prolly

Prolly 发布 prolly Rust 库 crate。用户依赖该包时使用 prolly-map，而代码导入保持简洁：use prolly::{Config, Prolly};。该 crate 提供了基于内容的 proly 树存储原语：一个基于字节键和字节值的不可变、有序键值索引，具有稳定的派生结构，支持高效的结构共享、差异对比、合并和批量加载。在 API 边界，Tree 是一个小型持久句柄：

• root: Option 指向内容寻址的根节点。
• config: Config 记录树使用的分块和编码参数。 实际的节点存储在一个可插拔的 Store 中。操作仅克隆并重写受影响的路径或子树，写入新的内容寻址节点，并返回新的 Tree 句柄。所有基于存储的树操作由一个运行时无关、异步优先的引擎统一实现。AsyncProlly 直接使用该引擎；Prolly 通过内联的 ready-only 适配器驱动相同完整的操作。同步路径不会创建运行时、挂起线程或将存储调用分派给 Tokio。

架构

Prolly 树架构 该图同样渲染为 diagram/[email protected]，适用于需要光栅图像的场景。 完整的最终用户文档集位于 docs/，包含入门材料、指南、实用代码示例、架构、设计规范、实现说明、路线图和语言移植指南。标准示例集在 docs/cookbook.md。原生近似最近邻索引文档在 docs/proximity-map.md。破坏性变更和版本发布记录在 CHANGELOG.md。

交互式可视化工具

3rd/prolly-tree-visualizer 中的浏览器应用程序对本仓库的真实 @crabbuild/prolly-wasm 绑定执行变更，并渲染生成的内容寻址树、查找路径、结构差异和存储历史。对于希望在 prolly 树之上构建类似 Git 仓库层的应用构建者，请参阅提议的 prolly-vcs 设计。它保持 prolly-map 专注于不可变有序映射，同时概述了一个单独的 crate，该 crate 具有通用后端无关的 KvStore 基底，用于提交、引用、引用日志、补丁、合并协调、同步规划和仓库级别的垃圾回收（GC）。

此 crate 提供的功能

• 有序字节键查找，按键的字典序排序。
• 不可变更新：put、delete 和 batch 返回一个新 Tree。
• 内容寻址节点：每个节点 CID 是确定性节点字节的 SHA-256 哈希。
• 使用 xxHash64 边界检查的确定性内容定义分块。
• 版本间的结构共享，因为未更改的节点保持相同的 CID。
• 通过修剪相等的 CID 和不相交的子范围实现高效的差异对比和范围差异对比。
• 支持冲突解决器的三向合并。
• CRDT 风格的无冲突合并策略。
• 惰性范围迭代和基于游标的遍历。
• 针对排序、分组、追加密集型和多叶写入的批量变更路径。
• 用于大型初始树的并行批量构建器。
• 通过 Store trait 实现的可插拔存储，包含内存、SQLite 以及可选的 RocksDB 实现。
• Merkle 风格的缺失节点规划和用于存储同步的复制助手。
• 用于分支、标签、检查点和自定义根的快照命名空间助手。
• 事务安全的 VersionedMap 外观，提供自动头部、不可变的内容派生版本、固定读取、证明、比较与合并、备份/同步、类型化编解码器、订阅、多映射事务、有界历史和范围垃圾回收。
• 一个严格的 IndexedMap 协调器，用于运行时定义的、非唯一的二级索引，支持单根原子发布、有限操作预算、稀疏和多值项、KeysOnly/Include/All 投影、精确历史快照、持久固定、安全垃圾回收、结构化诊断和经验证的有界传输。应用程序通过 Prolly 或 AsyncProlly 上的相同 engine.indexed_map(...) 形式打开它；两条路径都使用相同的规范状态格式和严格的事务性根发布。原生异步支持是 PostgreSQL、MySQL、Redis、Turso、DynamoDB、Cosmos DB 和 Spanner 的一等公民，当阻塞式应用程序需要时也提供同步外观。
• 与存储无关的树根单键、共享多键、完整范围、游标页和差异页证明。
• 用于检查形状、填充因子、扇出数和序列化大小的树统计信息。
• 具有精确查找、过滤最佳优先搜索、局部化规范写时复制（COW）、溢出/外部向量、SQ8/PQ/HNSW 加速、异步/SIMD 执行、类型化复制/垃圾回收和描述符绑定证明的硬切割确定性邻近映射。

快速开始

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());

所有更新 API 都是持久化的。只要存储仍然包含旧 Tree 句柄引用的节点，该句柄就保持有效。

独立检出

此目录可以作为自己的仓库打开。此树下的 Rust 清单声明了自己的包元数据、依赖版本和 lint 设置。从仓库根目录运行核心 crate：

cargo check --all-targets
cargo test
cargo run --example basic_map

提供者存储和 Rust 绑定位于嵌套包中。使用 --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

更多可复制的示例位于 examples/：

• agent_event_log.rs：用于消息、工具、内存写入、检查点和摘要的追加密集型代理事件日志。
• background_compaction.rs：具有保留感知的事件日志压缩、摘要索引重建和垃圾回收。
• basic_map.rs：put、get、delete 和范围扫描。
• batch_build.rs：批量构建加树统计。
• diff_merge.rs：差异对比和无冲突三向合并。
• resolver.rs：删除感知的合并解析器。
• secondary_index.rs：声明、构建、查询、验证、替换、保留、导出和导入严格的 IndexedMap 索引。
• indexed_map_real_world.rs：运行 14 种生产级模式，涵盖状态、客户、租户、时间、稀疏、多值、覆盖、路径、地理空间、文本和历史索引。
• materialized_view.rs：从源差异派生和更新物化视图，源/视图根记录在清单中。
• crdt_merge.rs：最后写入获胜（LWW）、多值、删除/更新、诊断和基于基础的自定义合并示例。
• conversation_memory.rs：规范内存根、代理尝试分支、合并和 CAS 发布。
• deterministic_rag_snapshot.rs：记录精确索引根以实现可复现的 RAG 答案和回滚。
• document_chunk_index.rs：文档/分块键约定、基于 blob 的文本和向量辅助 ID。
• vector_sidecar.rs：将嵌入保留在辅助向量引擎中，同时 prolly 根保留检索元数据。
• versioned_map.rs：使用内置的托管映射外观进行原子编辑、历史、差异对比、回滚和保留。
• provenance_values.rs：携带来源、解析器、嵌入、模型、父分块和 CID 来源的值。
• file_blob_store.rs：持久化 blob 卸载和 blob 垃圾回收。
• filesystem_snapshot.rs：类似 Git 的文件系统快照，具有文件 blob 和命名根。 特定于适配器的示例包括 semantic_rag.rs，一个完全离线的 1,536 维 ProximityMap，它将其语料库和命名描述符持久化到 SQLite 中，可在进程运行之间重新打开，并生成排名 RAG 引文以及一个可直接提供给 LLM 的上下文块。独立的 prolly-gluesql 集成将一个完整的 GlueSQL 数据库转换为一个事务性 Prolly 树，具有持久分支、不可变版本、二级索引、逻辑差异对比、历史读取，以及一个可选的基于 SQLite 的 CLI。原生 Rust 存储适配器位于 stores/ 下。prolly-store-turso 适配器嵌入了原生异步 Turso 数据库引擎用于本地存储，并可选地在其 sync Cargo 特性之后暴露显式的 Turso Cloud 推送/拉取。

键辅助工具

键是原始字节，按字典序排序。对于应用层模式，请使用 KeyBuilder 构建段安全的复合键，并使用 prefix_range 扫描一个逻辑命名空间：

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);

当数值顺序必须匹配字节顺序时，请使用 push_u64、push_u128、push_i64、push_i128 和 push_timestamp_millis。在测试和诊断中使用 decode_segments，在可读日志中使用 debug_key。

键和范围证明

证明 API 允许读取器验证映射内容与根 CID 的一致性，而无需打开后备存储。验证会重新计算节点 CID，并在返回已验证数据之前检查子链接。使用与交换匹配的最小证明形式：

• prove_key：证明一个值或一个不存在性
• prove_keys：证明多个键，同时共享证明节点
• prove_range：证明 [start, end) 中的每个条目
• prove_prefix：证明一个逻辑键前缀下的每个条目
• prove_range_page：证明一个游标页
• prove_diff_page：针对基础和目标根证明一个有界差异页
• inspect_proof_bundle：读取包类型、边界、根和计数
• verify_proof_bundle：验证不透明的规范包字节 当对等方需要防篡改检测、应用上下文、密钥 ID、nonce 或签发/到期时间时，将规范包字节包装在 HMAC-SHA256 信封中。使用 verify_authenticated_proof_bundle 在一次调用中认证信封并验证其中包含的证明包。从一个小树开始：

use prolly::{
    inspect_proof_bundle, sign_proof_bundle_hmac_sha256, verify_authenticated_proof_bundle,
    verify_authenticated_proof_envelope, verify_proof_bundle, Config, Diff, DiffPageProof,
    KeyProof, MemStore, Prolly, RangeCursor, RangePageProof, RangeProof,
};
let prolly = Prolly::new(MemStore::new(), Config::default());
let tree = prolly
    .put(&prolly.create(), b"name".to_vec(), b"Alice".to_vec())
    .unwrap();

证明一个键并在不从存储读取的情况下验证结果：

let proof = prolly.prove_key(&tree, b"name").unwrap();
let verified = proof.verify();
assert!(verified.exists());
assert_eq!(verified.value, Some(b"Alice".to_vec()));

当对等方希望重建相同的证明形状时，导出紧凑的证明节点：

let portable_path = proof.path_node_bytes();
let rebuilt = KeyProof::from_node_bytes(proof.root.clone(), proof.key.clone(), portable_path)
    .unwrap();
assert!(rebuilt.verify().valid);

当接收者只需要不透明的证明负载时，使用规范包字节：

let proof_bundle = proof.to_bundle_bytes().unwrap();
let bundle_summary = inspect_proof_bundle(&proof_bundle).unwrap();
assert_eq!(bundle_summary.kind_name(), "key");
assert_eq!(bundle_summary.key_count, 1);
let bundle_verified = verify_proof_bundle(&proof_bundle).unwrap();
assert!(bundle_verified.valid);
assert_eq!(bundle_verified.exists_count, 1);
let bundled = KeyProof::from_bundle_bytes(&proof_bundle).unwrap();
assert!(bundled.verify().exists());

当一个请求涵盖多个条目时，使用多键、范围和前缀证明：

let batch_proof = prolly
    .prove_keys(&tree, &[b"name".as_slice(), b"missing".as_slice()])
    .unwrap();
let batch_verified = batch_proof.verify();
assert!(batch_verified.valid);
assert!(batch_verified.results[0].exists());
assert!(batch_verified.results[1].is_absence());
let range_proof = prolly.prove_range(&tree, b"name", None).unwrap();
let range_verified = range_proof.verify();
assert!(range_verified.valid);
assert_eq!(
    range_verified.entries,
    vec![(b"name".to_vec(), b"Alice".to_vec())]
);
let range_bundle = range_proof.to_bundle_bytes().unwrap();
let range_bundled = RangeProof::from_bundle_bytes(&range_bundle).unwrap();
assert_eq!(range_bundled.verify().entries.len(), 1);
let prefix_proof = prolly.prove_prefix(&tree, b"na").unwrap();
assert_eq!(prefix_proof.verify().entries.len(), 1);

使用页证明进行基于游标的范围扫描：

let page_tree = prolly
    .build_from_sorted_entries(vec![
        (b"a".to_vec(), b"A".to_vec()),
        (b"b".to_vec(), b"B".to_vec()),
    ])
    .unwrap();
let proved_page = prolly
    .prove_range_page(&page_tree, &RangeCursor::start(), None, 1)
    .unwrap();
assert_eq!(proved_page.page.entries, vec![(b"a".to_vec(), b"A".to_vec())]);
assert_eq!(proved_page.proof.verify().entries, proved_page.page.entries);
let page_bundle = proved_page.proof.to_bundle_bytes().unwrap();
let page_bundled = RangePageProof::from_bundle_bytes(&page_bundle).unwrap();
assert_eq!(page_bundled.verify().entries.len(), 1);

当对等方需要验证一页更改时，使用差异页证明：

let diff_tree = prolly.delete(&page_tree, b"a").unwrap();
let diff_tree = prolly
    .put(&diff_tree, b"b".to_vec(), b"B2".to_vec())
    .unwrap();
let proved_diff = prolly
    .prove_diff_page(&page_tree, &diff_tree, &RangeCursor::start(), None, 1)
    .unwrap();
assert_eq!(
    proved_diff.page.diffs,
    vec![Diff::Removed {
        key: b"a".to_vec(),
        val: b"A".to_vec()
    }]
);
assert_eq!(proved_diff.proof.verify().diffs, proved_diff.page.diffs);
let diff_bundle = proved_diff.proof.to_bundle_bytes().unwrap();
let diff_summary = inspect_proof_bundle(&diff_bundle).unwrap();
assert_eq!(diff_summary.kind_name(), "diff_page");
assert_eq!(diff_summary.limit, Some(1));
assert!(diff_summary.has_lookahead);
let diff_bundle_verified = verify_proof_bundle(&diff_bundle).unwrap();
assert!(diff_bundle_verified.valid);
assert_eq!(diff_bundle_verified.diff_count, 1);
let diff_bundled = DiffPageProof::from_bundle_bytes(&diff_bundle).unwrap();
assert!(diff_bundled.verify().lookahead_valid);

当接收者还需要信封认证时，对包字节进行签名：

let signed = sign_proof_bundle_hmac_sha256(
    proof_bundle.clone(),
    b"proof-key-v1".to_vec(),
    b"shared secret",
    b"tenant=t1".to_vec(),
    Some(1_700_000_000_000),
    Some(1_700_000_100_000),
    b"nonce-1".to_vec(),
)
.unwrap();
let envelope = signed.to_bytes().unwrap();
let decoded = prolly::AuthenticatedProofEnvelope::from_bytes(&envelope).unwrap();
let authenticated = verify_authenticated_proof_envelope(&decoded).unwrap();
assert!(authenticated.valid);
let bundled_proof = authenticated.proof;
assert!(bundled_proof.verify().valid);