Lessons from Real Systems: CRDTs, Spanner TrueTime, CockroachDB HLC and Jepsen

Version note: The code in this post was built and run with C# 14 and .NET 10.

Guess First

Remember the cart from the seventh post: during a partition Ada added a book to the cart from her phone, removed another book from her laptop, and once the partition was over the replicas were reconciled with a union. The result: the removed book came back. Had we used "take what is on both sides" (an intersection) instead of the union, the added book would have been lost.

So is a cart possible that merges both adds and removes correctly without coordination, that is, without the replicas ever asking each other during the partition? And at the opposite end: how does a database provide transactions that respect real time (linearizable ones), knowing its clocks can be off by milliseconds?

CRDTs: Merging Without Coordination

CRDTs (Conflict-free Replicated Data Types), defined by Shapiro, Preguiça, Baquero and Zawirski in 2011, are data types where every replica accepts writes locally and replicas merge their states later. As long as the merge function has three properties, the result is independent of the order in which messages arrive and of how many times they arrive: commutative (merging a with b is the same as merging b with a), associative (grouping does not matter) and idempotent (merging the same state twice is the same as merging it once). Mathematically, the states form a join-semilattice.

These three properties neutralize three of the network's bad habits from the second post at once: messages may be reordered (commutative), duplicated (idempotent), and arrive grouped or delayed (associative). The result is the strong eventual consistency we named in the sixth post: two replicas that have received the same updates are in the same state, in whatever order they received them. The kind shown here is a state-based CRDT; there are also op-based CRDTs, which send updates as operations and make stronger assumptions about delivery order.

G-Counter and PN-Counter

The simplest CRDT is the grow-only counter (G-Counter): each replica increments only its own slot, merge takes the maximum slot by slot, and the value is the sum of the slots. It is the same as the merge rule of the vector clock in the fourth post. To allow decrements too, two G-Counters are used (PN-Counter): one counts increments, the other decrements. The third type is the OR-Set; we will get to it shortly:

using System.Collections.Immutable;

namespace Bookstore.Crdt;

// Grow-only counter: one slot per replica, merge = element-wise max
public sealed record GCounter(ImmutableSortedDictionary<string, long> Slots)
{
    public static GCounter Empty { get; } = new(ImmutableSortedDictionary<string, long>.Empty);

    public long Value => Slots.Values.Sum();

    public GCounter Increment(string replica, long by = 1) =>
        new(Slots.SetItem(replica, Slots.GetValueOrDefault(replica) + by));

    public GCounter Merge(GCounter other) =>
        new(other.Slots.Aggregate(Slots, (acc, kv) => acc.SetItem(kv.Key, Math.Max(acc.GetValueOrDefault(kv.Key), kv.Value))));
}

// Positive-negative counter: two G-Counters
public sealed record PNCounter(GCounter Plus, GCounter Minus)
{
    public static PNCounter Empty { get; } = new(GCounter.Empty, GCounter.Empty);

    public long Value => Plus.Value - Minus.Value;
    public PNCounter Increment(string replica) => this with { Plus = Plus.Increment(replica) };
    public PNCounter Decrement(string replica) => this with { Minus = Minus.Increment(replica) };
    public PNCounter Merge(PNCounter other) => new(Plus.Merge(other.Plus), Minus.Merge(other.Minus));
}

// Observed-remove set: a remove deletes only the add-tags it has seen
public sealed record ORSet(ImmutableHashSet<(string Item, Guid Tag)> Adds, ImmutableHashSet<Guid> Removed)
{
    public static ORSet Empty { get; } = new([], []);

    public IEnumerable<string> Items => Adds.Where(a => !Removed.Contains(a.Tag)).Select(a => a.Item).Distinct().Order();

    public ORSet Add(string item) => this with { Adds = Adds.Add((item, Guid.NewGuid())) };

    public ORSet Remove(string item) =>
        this with { Removed = Removed.Union(Adds.Where(a => a.Item == item).Select(a => a.Tag)) };

    public ORSet Merge(ORSet other) => new(Adds.Union(other.Adds), Removed.Union(other.Removed));
}

using System.Globalization;
using Bookstore.Crdt;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

// "Wishlist" likes for a book, counted on two replicas while they cannot talk
GCounter istanbul = GCounter.Empty.Increment("ist").Increment("ist").Increment("ist");
GCounter frankfurt = GCounter.Empty.Increment("fra").Increment("fra");
GCounter ab = istanbul.Merge(frankfurt), ba = frankfurt.Merge(istanbul);
Console.WriteLine($"G-Counter  ist={istanbul.Value} fra={frankfurt.Value} merged={ab.Value} " +
                  $"commutative={ab.Value == ba.Value} idempotent={ab.Merge(ab).Value == ab.Value}");

PNCounter stockA = PNCounter.Empty.Increment("ist").Increment("ist").Decrement("ist");
PNCounter stockB = PNCounter.Empty.Decrement("fra");
Console.WriteLine($"PN-Counter ist={stockA.Value} fra={stockB.Value} merged={stockA.Merge(stockB).Value}");

G-Counter  ist=3 fra=2 merged=5 commutative=True idempotent=True
PN-Counter ist=1 fra=-1 merged=0

The Istanbul replica counted three "wishlist" entries and the Frankfurt replica two; the merge is five, and neither the merge order nor merging again changes the result. An LWW (last-write-wins) register would have picked one of the two values here and lost the other. The PN-Counter adds up correctly too: Istanbul saw two receipts and one sale, Frankfurt one sale, the result is zero.

But note what the PN-Counter cannot do. If there is a single book in stock and both replicas accept a sale each during a partition, the merge drops to minus one. A CRDT guarantees the merge, not the invariant (stock never goes below zero). Protecting an invariant requires the replicas to ask each other; that is the C side of CAP (Consistency, Availability, Partition tolerance) from the seventh post. The practical fix is to allocate the stock to replicas in advance (each replica may sell only its share and needs coordination once the share runs out), or to keep the operation that decrements stock in a single place.

The OR-Set and Fixing the Cart

A cart is a set, but a plain set reconciled by union does not recognize removes. An OR-Set (Observed-Remove Set) gives every add a unique tag. A remove deletes not the item itself but the tags the removing replica has seen at that moment. On merge, the adds and the removed tags are merged separately; an item is in the set if it has at least one tag that has not been removed:

// The cart from the CAP post, now as an OR-Set
ORSet cart = ORSet.Empty.Add("ddia").Add("clean-code");
ORSet phone = cart.Add("refactoring");      // replica C during the partition
ORSet laptop = cart.Remove("clean-code");   // replica A during the partition
Console.WriteLine($"OR-Set     merged cart = {string.Join(", ", phone.Merge(laptop).Items)}");
ORSet again = laptop.Add("clean-code");     // a fresh add after the remove survives
Console.WriteLine($"OR-Set     re-added    = {string.Join(", ", again.Merge(phone).Items)}");

OR-Set     merged cart = ddia, refactoring
OR-Set     re-added    = clean-code, ddia, refactoring

The same scenario as in the seventh post, but this time clean-code does not come back: the remove on the laptop deleted the tag the phone had seen too. refactoring is kept, because nobody removed its tag after seeing it. And a fresh add after the remove produces a new tag, so it is kept as well. When a remove meets a concurrent add, the add wins (add-wins); the right choice for a cart, but not for every domain. There is a cost too: removed tags (tombstones) accumulate; real implementations compact them with version vectors.

CRDTs are in many places today: Riak's data types, Redis Enterprise's active-active replication, Automerge by Kleppmann and colleagues, and collaborative editing libraries such as Yjs. Text editing is the hardest case: in a document where several people type into the same text concurrently, every character's position is kept with a sequence CRDT, and a good algorithm must not interleave, letter by letter, words two people typed at the same spot. crdt.tech collects the papers and implementations in this field.

Spanner: TrueTime and Commit Wait

At the other end of the spectrum is Google Spanner. The paper, published at OSDI (Operating Systems Design and Implementation) in 2012, provides external consistency in a globally distributed database, that is, the strict serializability from the sixth post: every transaction that starts after another has committed gets a larger timestamp. For that it has to rely on physical time, and the third post showed why clocks are unreliable.

Spanner's solution is not to hide the clock's uncertainty but to measure it. Every data center has time masters equipped with GPS (Global Positioning System) receivers and atomic clocks; the TrueTime API (Application Programming Interface) on the machines returns not a single instant but an interval guaranteed to contain real time: TT.now() = [earliest, latest]. According to the paper, the interval's half-width ε typically varies like a sawtooth between about 1 and 7 milliseconds and is about 4 milliseconds most of the time.

When a transaction commits, its timestamp is chosen as s = TT.now().latest. Then comes commit wait: it waits until TT.now().earliest passes s, that is, until s is certainly in the past on every machine, and only then releases its locks. The average wait is about 2ε. Let us simulate the same logic with Stopwatch's monotonic clock:

using System.Diagnostics;

namespace Bookstore.Crdt;

public readonly record struct TTInterval(double Earliest, double Latest);

// TrueTime-like API: now() returns an interval that contains real time
public sealed class TrueTime(double epsilonMs)
{
    private readonly Stopwatch _clock = Stopwatch.StartNew();

    public TTInterval Now()
    {
        double t = _clock.Elapsed.TotalMilliseconds;
        return new(t - epsilonMs, t + epsilonMs);
    }

    // Commit wait: pick s = now().latest, then wait until s is surely in the past
    public async Task<(double Timestamp, double WaitedMs)> CommitAsync()
    {
        double s = Now().Latest;
        long start = Stopwatch.GetTimestamp();
        while (Now().Earliest <= s)
        {
            await Task.Delay(1);
        }
        return (s, Stopwatch.GetElapsedTime(start).TotalMilliseconds);
    }
}

// Commit wait with epsilon = 4 ms (Spanner's typical value)
TrueTime tt = new(epsilonMs: 4);
for (int i = 0; i < 3; i++)
{
    (double ts, double waited) = await tt.CommitAsync();
    Console.WriteLine($"commit wait: timestamp={ts:F1} ms, waited {waited:F1} ms before acknowledging");
}

commit wait: timestamp=4.2 ms, waited 8.7 ms before acknowledging
commit wait: timestamp=13.3 ms, waited 9.1 ms before acknowledging
commit wait: timestamp=22.4 ms, waited 9.1 ms before acknowledging

The theoretical wait is 2ε = 8 milliseconds; the measured one is between 8.7 and 9.1 milliseconds, because the resolution of Task.Delay(1) is a little coarser than a millisecond. Spanner's design decision is clear: better clock hardware shrinks ε, and a small ε shortens the wait on every write. The uncertainty does not go away, but it becomes bounded and known, and the system pays for it as write latency. It is a deliberate EC (Else: Consistency) choice in the E branch of PACELC (if Partition: Availability or Consistency, Else: Latency or Consistency) from the seventh post.

CockroachDB: NTP, HLC and the Uncertainty Interval

What do you do without atomic clocks? Cockroach Labs' post "Living Without Atomic Clocks" describes CockroachDB's answer. Nodes are synchronized with ordinary NTP (Network Time Protocol), and timestamps come from the hybrid logical clock (HLC) of the fourth post, so an event that comes later causally always gets a larger timestamp. An upper bound on clock difference is configured (the default maximum offset is 500 milliseconds), and nodes constantly measure each other's clocks; a node that is off from at least half of the other nodes by more than 80 percent of that bound shuts itself down.

When a transaction reading data sees a value written within the interval between its own timestamp and timestamp + maximum offset (the uncertainty interval), it cannot tell whether that value was actually written before or after it. In that case it restarts with a timestamp just above that value (an uncertainty restart). Spanner waits on every write; CockroachDB waits only when the uncertainty actually hits a value, on the read side. The cost is in the guarantee: CockroachDB provides serializable isolation and linearizability on a single key, but for causally related transactions that touch different keys it does not give the strict serializability Spanner gives. And the bound itself is an assumption: if the clock difference exceeds the configured value, the guarantee breaks too, which is why nodes shutting themselves down is a safety mechanism.

Jepsen: Documentation Is Not Behavior

Every guarantee in this series was tied to a system model. Kyle Kingsbury's Jepsen project tests whether databases provide these guarantees under real failures: it records client operations, injects network partitions, process crashes and clock jumps, and then checks the history against the promised model with a checker like the one in the sixth post. Over the years, differences between promise and behavior were found in a large share of the systems tested, and most of the findings were fixed.

Two examples connect directly to this series. The 2020 analysis of PostgreSQL 12.3 found G2-item anomalies (an anti-dependency cycle in which transactions proceed without seeing each other's writes) under serializable isolation on a single healthy node, without injecting any failures; the cause was a bug in the conflict detection of serializable snapshot isolation, present in every version tested from 9.5 to 13; when the report was published, the fix had been committed and was scheduled for the August 2020 minor releases. The same report noted that what PostgreSQL calls "repeatable read" is actually snapshot isolation and that the documentation should say so explicitly. The 2020 analysis of etcd 3.4.3 observed strict serializability for key-value operations, but showed that etcd's locks are fundamentally unsafe, that two processes could hold the same lock at the same time even in a healthy cluster, and recommended the fix from the tenth post: use the lock key's revision as a fencing token.

The lesson: read a guarantee not from the documentation but from what failures it was tested under. If the database you use has a Jepsen report, read it; if not, test the critical guarantees in your own environment with your own failure scenarios.

Series Summary: Which Guarantee, at What Cost?

Every mechanism we saw in eleven posts provides a guarantee and charges a price. In an architecture decision, what you are looking for is not "the strongest guarantee" but the mechanism that provides the guarantee the operation needs at the lowest cost:

Common Pitfalls

Treating CRDTs as the answer to everything. A CRDT guarantees the merge, not the business rules. Invariants such as "stock cannot be negative" or "a coupon is used once" need coordination.

Assuming add-wins is right for every domain. In a cart it is reasonable for the add to win; in an access control list, an add winning over a concurrent remove can be a security hole. Remove-wins variants exist too; choose the semantics deliberately.

Expecting Spanner-style guarantees without the clock infrastructure. TrueTime's value comes from a bounded, measured ε. A system running on ordinary NTP gets the same guarantee either with a much longer wait or, like CockroachDB, with a weaker guarantee.

Raising the maximum clock offset without monitoring. In CockroachDB-style systems this value is both a performance setting (restarts) and a correctness assumption; raising it without monitoring clock synchronization quietly weakens the guarantee.

Saying "our database guarantees this". Which version, which settings, under which failure? Jepsen's findings show that the answer to that question is often not in the documentation.

A Small Experiment

★☆☆ Start the PN-Counter with a stock of 1 (one receipt in Istanbul), then make one sale on each replica and merge. What is the result? What would it take to prevent this at the moment of the sale?

★★☆ Add a remove-wins variant to ORSet: when a concurrent add and remove meet, the remove wins. Run the cart scenario with both variants; which is right for which domain?

★★★ Add a model to TrueTime in which ε grows like a sawtooth from 1 to 7 milliseconds every 30 seconds, and measure the average commit wait over 1000 commits. Then make ε a fixed 250 milliseconds (think of a machine synchronized with ordinary NTP over the internet). Is the commit wait approach still reasonable with these numbers?

The series ends here. We started with partial failure, saw why clocks and ordering are hard, how replicas do and do not agree, what CAP and PACELC really say, consensus, two-phase commit (2PC) and locks, and finally how real systems live with these limits. From now on, when you see "consistent", "exactly-once" or "highly available" in the documentation of a database, a cache or a broker, let your first question be: which model, under which failures, and at what cost?