# Crate merkle_search_tree

source ·## Expand description

## Merkle Search Tree

This crate implements a Merkle Search Tree as described in the 2019 paper
Merkle Search Trees: Efficient State-Based CRDTs in Open Networks by
Alex Auvolat & François Taïani.^{1}

When paired with CRDT-based value types, a Merkle Search Tree can act as an efficient anti-entropy primitive, allowing independent replicas to concurrently modify data within the tree with deterministic and eventual convergence across all peers.

See `MerkleSearchTree`

documentation.

### Use It

```
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");
});
```

### Performance

Operations against a Merkle Search Tree are *fast*, executing against
millions/billions of keys per second:

Key Count | Insert All Keys | Generate Root | Serialise | Diff (consistent) | Diff (inconsistent) |
---|---|---|---|---|---|

100 keys | 7µs | 3µs | 98ns | 152ns | 261ns |

1,000 keys | 92µs | 39µs | 847ns | 577ns | 4µs |

10,000 keys | 1356µs | 398µs | 10µs | 4µs | 36µs |

100,000 keys | 17ms | 3ms | 112µs | 26µs | 287µs |

The above measurements capture the single-threaded performance of operations against a tree containing varying numbers of keys on a M1 MacBook Pro.

*Insert All Keys*: insert the N keys listed for the row into an empty tree*Generate Root*: regenerate the root hash of a modified tree*Serialise*: encode the tree into a diff format for network communication*Diff (consistent)*: diff generation for identical trees (no differing ranges)*Diff (inconsistent)*: diff generation for a fully inconsistent tree

The benchmarks to generate these numbers are included in this repo (run `cargo bench`

).

### Testing

This crate is extensively tested using randomised fuzzing & property testing to validate correctness, and ensure no panics occur in release builds.

Alex Auvolat, François Taïani. Merkle Search Trees: Efficient State-Based CRDTs in Open Networks. SRDS 2019 - 38th IEEE International Symposium on Reliable Distributed Systems, Oct 2019, Lyon, France. pp.1-10, ⟨10.1109/SRDS.2019.00032⟩. ⟨hal-02303490⟩ ↩

## Modules

- Tree difference calculation algorithm & associated types.
- Hash function abstraction & digest types.
- Trait & implementations for tree structure inspection.

## Structs

- An implementation of the Merkle Search Tree as described in Merkle Search Trees: Efficient State-Based CRDTs in Open Networks.
- Storage of a single key/value pair.
- A group of
`Node`

instances at the same location within the tree.