CasualDB, an eventually consistent distributed system

CasualDB is a small key-value store I wrote to understand what eventual consistency really demands of a system once the marketing language is stripped away. It is not production software. It is a place to be wrong cheaply.

The premise is ordinary: several nodes, no coordinator, writes accepted anywhere, and a promise that replicas converge. The interesting part is what "converge" quietly obliges you to build.

Why causal, not just eventual

Plain eventual consistency lets a replica show you an effect before its cause. You reply to a message that, from another node's point of view, has not been sent yet. Technically correct, completely unusable.

Causal consistency is the weakest model that avoids this. If write B happened after the client observed write A, every replica that shows B must already show A. Concurrent writes with no such relationship can land in any order.

Vector clocks, and their bill

Each node keeps a counter per node. A write carries the writer's whole vector. Comparing two vectors gives you one of three answers: A precedes B, B precedes A, or the two are concurrent.

type Clock = Record<NodeId, number>;
 
function compare(a: Clock, b: Clock): "before" | "after" | "concurrent" {
  let aSmaller = false;
  let bSmaller = false;
 
  for (const node of new Set([...Object.keys(a), ...Object.keys(b)])) {
    const left = a[node] ?? 0;
    const right = b[node] ?? 0;
    if (left < right) aSmaller = true;
    if (right < left) bSmaller = true;
  }
 
  if (aSmaller && bSmaller) return "concurrent";
  return aSmaller ? "before" : "after";
}

The bill arrives immediately. Every value carries metadata proportional to the number of nodes that have ever written it, and nothing garbage-collects that on its own.

Somebody has to decide

Concurrent writes are not a bug to be prevented, they are a case to be handled. CasualDB keeps both versions as siblings and hands them to the caller on read. That is the honest option, and it is also the one nobody wants.

The alternative is to constrain the data type until conflicts cannot happen: counters that only increment, sets that only grow, registers with a defined merge. You give up generality and get determinism back.

Anti-entropy is most of the work

Replication over the happy path is easy. The system spends far more of its code on the boring repair loop that runs when the happy path did not happen: periodic digest exchange, Merkle trees over key ranges, and a repair pass for the ranges whose hashes disagree.

:::

What I would keep

The parts worth carrying into real systems are unglamorous:

• Make the ordering relationship explicit in the data, not implied by arrival time.
• Treat conflict as a first-class read result, not an error.
• Budget for repair traffic from day one; it is not an edge case, it is steady state.
• Assume metadata grows. Decide when it is pruned before you need to.