Function merkle_search_tree::diff::diff

pub fn diff<'p, 'a: 'p, T, U, K>(local: T, peer: U) -> Vec<DiffRange<'p, K>>where
    T: IntoIterator<Item = PageRange<'a, K>>,
    U: IntoIterator<Item = PageRange<'p, K>>,
    K: PartialOrd + Ord + Debug + 'p + 'a,

Compute the difference between local and peer, returning the set of DiffRange covering the inconsistent key ranges found in peer.

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

// Initialise a "peer" tree.
let mut node_a = MerkleSearchTree::default();
node_a.upsert("bananas", &42);
node_a.upsert("plátanos", &42);

// Initialise the "local" tree with differing keys
let mut node_b = MerkleSearchTree::default();
node_b.upsert("donkey", &42);

// Generate the tree hashes before serialising the page ranges
node_a.root_hash();
node_b.root_hash();

// Generate the tree page bounds & hashes, and feed into the diff function
let diff_range = diff(
    node_b.serialise_page_ranges().unwrap().into_iter(),
    node_a.serialise_page_ranges().unwrap().into_iter(),
);

// The diff_range contains all the inclusive key intervals the "local" tree
// should fetch from the "peer" tree to converge.
assert_matches::assert_matches!(diff_range.as_slice(), [range] => {
    assert_eq!(range.start(), &"bananas");
    assert_eq!(range.end(), &"plátanos");
});

State Convergence

To converge the state of the two trees, the key ranges in the returned DiffRange instances should be requested from peer and used to update the state of local.

If local is a superset of peer (contains all the keys in peer and the values are consistent), or the two trees are identical, no DiffRange intervals are returned.

Optimistic Page Bounds Fetching

When a page exists in peer has a key range that is a strict superset of the key range of the same page in local, it is guaranteed to be inconsistent. When this occurs, only the difference / missing keys are returned in that page’s DiffRange.

This optimistically assumes the intersection of keys between the two pages are consistent, minimising the number of keys fetched when this assumption holds true. If false, the page will be marked fully inconsistent (inclusive of the newly fetched keys) in the next diff() call.

This optimises for monotonic keys, recommended to minimise tree page inconsistencies / keys fetched when new keys are inserted into the tree.

Termination

A single invocation to diff() always terminates, and completes in O(n) time and space. Inconsistent page ranges (if any) are minimised in O(n_consistent * n_inconsistent) time and O(n) space.

In the absence of further external updates to either tree, this algorithm terminates (leaving local and peer fully converged) and no diff is returned within a finite number of sync rounds between the two trees.

If a one-way sync is performed (pulling inconsistent keys from peer and updating local, but never syncing the other way around) this algorithm MAY NOT terminate.