vector-clock-merkle

Answer

The package vclock provides a state reconciliation engine for eventually-consistent distributed key-value stores. It has four core components:

1. Vector Clock (VectorClock)

A map from replica/node ID to logical counter that captures causal history. The Compare method classifies relationships as Equal, Less, Greater, or Concurrent (incomparable).

type VectorClock map[string]uint64

func (vc VectorClock) Compare(other VectorClock) Order {
    // Collect all node IDs from both clocks
    all := make(map[string]struct{})
    for k := range vc { all[k] = struct{}{} }
    for k := range other { all[k] = struct{}{} }

    leq, geq := true, true  // vc <= other, vc >= other
    for k := range all {
        a, b := vc[k], other[k]
        if a > b { leq = false }
        if a < b { geq = false }
    }
    switch {
    case leq && geq:  return Equal
    case leq:         return Less
    case geq:         return Greater
    default:          return Concurrent
    }
}

2. Merkle Tree — Trie-based Diff Detection

Entries are stored in a byte-wise trie. Each node's hash = SHA256("internal" | child_hashes…), leaf hashes = SHA256("entry" | key | val | clock). Comparing root hashes detects divergence in O(1); when different, the algorithm descends recursively to find exactly which keys differ.

func (mt *MerkleTree) Diff(other *MerkleTree) []string {
    mt.ensureHashes(); other.ensureHashes()
    diffSet := make(map[string]bool)
    mt.diffDescend(mt.root, other.root, diffSet)
    // sort and return
}

func (mt *MerkleTree) diffDescend(a, b *node, out map[string]bool) {
    if a.hash == b.hash { return }        // subtree identical
    if a.entry != nil || b.entry != nil { // leaf difference
        // collect differing keys
        return
    }
    // recurse into differing children
    for k := range allKeys {
        ca, cb := a.children[k], b.children[k]
        switch {
        case ca == nil: mt.collectAll(cb, out)
        case cb == nil: mt.collectAll(ca, out)
        default:        mt.diffDescend(ca, cb, out)
        }
    }
}

3. Conflict Key Extraction (ExtractConflicts)

A key is in conflict when both replicas modified it (or created it) and the resulting vector clocks are concurrent — neither causally dominates the other:

func ExtractConflicts(ancestor, replica1, replica2 map[string]*Entry) []string {
    // For each key present in any replica:
    //   a = ancestor[key], b = replica1[key], c = replica2[key]
    //   if b == nil || c == nil → skip (only one side has it)
    //   changedB = a == nil || a.Clock.Compare(b.Clock) != Equal
    //   changedC = a == nil || a.Clock.Compare(c.Clock) != Equal
    //   if changedB && changedC && b.Clock.Compare(c.Clock) == Concurrent
    //     → conflict
}

4. Three-Way Merge (ThreeWayMerge)

For each key across all three states, the merge applies these rules: