默克尔搜索树

此软件包实现了默克尔搜索树，如2019年论文默克尔搜索树：开放网络中高效的基于状态 CRDT中所述，作者为Alex Auvolat & François Taïani。[^引用]

与基于 CRDT 的值类型结合使用时，默克尔搜索树可以作为高效的抗熵原语，允许独立副本并发地在树中修改数据，并在所有对等方之间确定性和最终收敛。

请参阅MerkleSearchTree文档。

使用方法

use merkle_search_tree::{MerkleSearchTree, diff::diff};

// Initialise a tree using the default configuration, appropriate for most uses.
let mut node_a = MerkleSearchTree::default();

// Upsert values into the tree.
//
// For the MST construct to be a CRDT itself, the values stored into the tree
// must also be CRDTs (or at least, have deterministic conflict resolution).
// Here the MST is used as an add-only set (a trivial CRDT) by using () as the
// key values.
node_a.upsert("bananas", &());
node_a.upsert("plátanos", &());

// Another node has differing keys.
let mut node_b = MerkleSearchTree::default();
node_b.upsert("donkey", &());

// The MST root hash can be used as an efficient consistency check (comparison
// is O(1) in space and time).
//
// In this case, both trees are inconsistent w.r.t each other, which is
// indicated by their differing root hashes.
assert_ne!(node_a.root_hash(), node_b.root_hash());

// Generate compact summaries of the MST content, suitable for transmission over
// the network, and use it to compute the diff between two trees.
let diff_range = diff(
    node_b.serialise_page_ranges().unwrap().into_iter(),
    node_a.serialise_page_ranges().unwrap().into_iter(),
);

// In this case, node B can obtain the missing/differing keys in node A by
// requesting keys within the computed diff range (inclusive):
assert_matches::assert_matches!(diff_range.as_slice(), [range] => {
    assert_eq!(range.start(), &"bananas");
    assert_eq!(range.end(), &"plátanos");
});

性能

对默克尔搜索树的操作非常 快，每秒可处理数百万/数十亿个键

以下测量值反映了在 M1 MacBook Pro 上对包含不同数量键的树进行操作的单线程性能。

• 插入所有键：将行中列出的 N 个键插入空树
• 生成根：重新生成修改后树的根哈希
• 序列化：将树编码为网络通信的差分格式
• 差异（一致）：为相同的树生成差异（没有不同的范围）
• 差异（不一致）：为完全不一致的树生成差异

生成这些数字的基准测试包含在此存储库中（运行 cargo bench）。

测试

此软件包使用随机化模糊测试和属性测试进行广泛测试，以验证正确性，并确保发布版本中不会出现恐慌。

参考文献：Alex Auvolat, François Taïani. Merkle搜索树：开放网络中高效的状态CRDT。SRDS 2019 - 第38届IEEE可靠分布式系统国际研讨会，2019年10月，法国里昂。第1-10页，[10.1109/SRDS.2019.00032]。[hal-02303490]