Heal on read, heal on a schedule — read repair and Merkle-tree anti-entropy

1def read_repair(key, replicas):
2    responses = [r.read(key) for r in replicas]
3    winner = max(responses, key=lambda x: x.ts)
4    # only the keys actually read get healed
5    for resp in responses:
6        if resp.ts < winner.ts:
7            send_async(resp.replica,
8                Write(key, winner.value, winner.ts))
9    return winner.value

1def merkle_repair(a, b, range):
2    tree_a = a.build_merkle(range)
3    tree_b = b.build_merkle(range)
4    diffs = diff_subtree(tree_a.root, tree_b.root)
5    # diffs is the set of mismatched leaf ranges
6    for leaf_range in diffs:
7        rows_a = a.fetch(leaf_range)
8        rows_b = b.fetch(leaf_range)
9        merged = lww_merge(rows_a, rows_b)
10        a.bulk_write(merged)
11        b.bulk_write(merged)

1def diff_subtree(node_a, node_b):
2    if node_a.hash == node_b.hash:
3        return []          # entire subtree matches; skip
4    if node_a.is_leaf:
5        return [node_a.range]
6    out = []
7    out += diff_subtree(node_a.left, node_b.left)
8    out += diff_subtree(node_a.right, node_b.right)
9    return out