Vector Clocks and Eventual Consistency

The CAP Theorem

• When a network partition splits a distributed system into two groups that cannot communicate, it must make a choice between:
  • Consistency: every node sees the same data, even if that means refusing some requests until connectivity is restored
  • Availability: every node continues to respond, even if that means different nodes return different values
• Most distributed databases choose availability and provide eventual consistency
  • Replicas diverge during a partition and converge when they reconnect
• This lesson models the convergence mechanism: vector clocks

Vector Clocks

• A vector clock is a map from node IDs to event counts
• When node n performs an operation, it increments its own counter
• When two nodes synchronize, they merge their clocks by taking the element-wise maximum
• The representation is a Dict(String, Int):

pub fn merge_clocks(
  a: dict.Dict(String, Int),
  b: dict.Dict(String, Int),
) -> dict.Dict(String, Int) {
  dict.combine(a, b, fn(va, vb) { int.max(va, vb) })
}

• dict.combine merges two dicts
  • For keys present in both, the merge function is applied
  • Keys present in only one dict pass through unchanged
• int.max(va, vb) keeps the larger counter for each shared key

Dominance

• Clock a dominates clock b if a has seen everything b has seen and possibly more:

pub fn dominates(
  a: dict.Dict(String, Int),
  b: dict.Dict(String, Int),
) -> Bool {
  let a_entries = dict.to_list(a)
  list.all(a_entries, fn(entry) {
    let #(node, count_a) = entry
    let count_b = dict.get(b, node) |> result.unwrap(0)
    count_a >= count_b
  })
}

• For every node in a, a's counter must be >= b's counter
• result.unwrap(dict.get(b, node), 0) treats a missing counter as zero
  • If b has not recorded any events from that node, a's value is automatically >=
• dominates(a, b) means a happened after b (causally)
• If both dominates(a, b) and dominates(b, a) are false, the writes are concurrent

Simulating Two Replicas

• Replica A has only seen events from node n1:

{"n1": 1}

• Replica B has seen more events from n1 and also events from n2:

{"n1": 2, "n2": 1}

• dominates(a, b) is false: a's n1 counter (1) is less than b's (2)
• After merging, the combined clock is:

{"n1": 2, "n2": 1}

• The merged clock dominates both originals
• This is the mathematical property that guarantees eventual convergence
  • Any two replicas that exchange clocks and merge will reach the same state

Versioned Values

• To track which version of a value is current, pair the value with its clock:

pub type Versioned(v) {
  Versioned(value: v, clock: dict.Dict(String, Int))
}

pub fn resolve(
  local: Versioned(String),
  remote: Versioned(String),
) -> Versioned(String) {
  let merged_clock = merge_clocks(local.clock, remote.clock)
  case dominates(local.clock, remote.clock) {
    True -> Versioned(local.value, merged_clock)
    False ->
      case dominates(remote.clock, local.clock) {
        True -> Versioned(remote.value, merged_clock)
        False ->
          case string.compare(local.value, remote.value) {
            order.Lt | order.Eq -> Versioned(local.value, merged_clock)
            order.Gt -> Versioned(remote.value, merged_clock)
          }
      }
  }
}

• Versioned(v) is a generic type: any v can be versioned
• resolve picks the newer value when one clock dominates the other
• For concurrent writes, it falls back to a deterministic tie-break
  • Here: string.compare picks the lexicographically smaller value
• The merged clock always advances: no information is lost

Testing

pub fn merge_takes_max_test() {
  let a = dict.from_list([#("n1", 3), #("n2", 1)])
  let b = dict.from_list([#("n1", 1), #("n2", 4)])
  let merged = merge_clocks(a, b)
  dict.get(merged, "n1")
  |> should.equal(Ok(3))
  dict.get(merged, "n2")
  |> should.equal(Ok(4))
}

pub fn dominates_true_test() {
  let a = dict.from_list([#("n1", 2)])
  let b = dict.from_list([#("n1", 1)])
  dominates(a, b)
  |> should.be_true()
}

pub fn dominates_false_test() {
  let a = dict.from_list([#("n1", 1)])
  let b = dict.from_list([#("n1", 2)])
  dominates(a, b)
  |> should.be_false()
}

pub fn concurrent_test() {
  let a = dict.from_list([#("n1", 2), #("n2", 1)])
  let b = dict.from_list([#("n1", 1), #("n2", 3)])
  dominates(a, b)
  |> should.be_false()
  dominates(b, a)
  |> should.be_false()
}

pub fn merged_dominates_both_test() {
  let a = dict.from_list([#("n1", 2)])
  let b = dict.from_list([#("n1", 1), #("n2", 3)])
  let merged = merge_clocks(a, b)
  dominates(merged, a)
  |> should.be_true()
  dominates(merged, b)
  |> should.be_true()
}

• merge_takes_max_test checks that the merged clock holds the maximum counter per node
• dominates_true_test and dominates_false_test cover both directions of the relation
• concurrent_test confirms that neither clock dominates when counters have crossed
• merged_dominates_both_test verifies the convergence guarantee

Check Understanding

Exercises