Why NornicDB Uses Its Own Monotonic Counter for MVCC Ordering

[orneryd]

TL;DR

NornicDB's MVCC layer assigns each committed write a (CommitTimestamp, CommitSequence) pair, where CommitTimestamp comes from time.Now().UnixNano() and CommitSequence comes from a process-wide atomic uint64 counter. Snapshot-isolation conflict detection orders versions by sequence first, not timestamp. We did this because:

1. Wall-clock nanoseconds are not monotonic. Linux clock_gettime(CLOCK_REALTIME) can step backward under NTP correction, and even between adjacent reads on different goroutines.
2. Our parser is faster than the wall clock's resolution. A simple Cypher MATCH (n) RETURN n parses+validates in 39 ns with zero allocations. Multiple commits routinely land inside the same UnixNano() bucket.
3. Go's built-in monotonic clock is per-time.Time, not global. It is stripped by UnixNano() and is undefined across time.Time values produced by independent time.Now() calls.

A uint64 counter incremented atomically per commit gives us a total order that nothing in the operating system can perturb. At one billion commits per second sustained, it overflows in ~584 years.

---

The Bug We Were Hunting

The regression that drove this work was an intermittent CI failure in TestExecuteCypher_SetInvalidatesManagedEmbeddings:

conflict: node 0x7f3a... changed after transaction start

The failure was a phantom conflict. No second writer existed. The transaction reading the node had been opened after the commit it was racing against — there should have been nothing to conflict with. But the snapshot-isolation check disagreed.

The check is, at its core, a comparison between two MVCCVersion records: the version at which a transaction began its read, and the version at which a row was last committed. If committedVersion > readVersion, the SI machinery flags the row as having been written after the transaction started.

MVCCVersion.Compare() ordered by timestamp first:

// pkg/storage/types.go
func (a MVCCVersion) Compare(b MVCCVersion) int {
    if a.CommitTimestamp != b.CommitTimestamp {
        if a.CommitTimestamp < b.CommitTimestamp {
            return -1
        }
        return 1
    }
    if a.CommitSequence < b.CommitSequence { return -1 }
    if a.CommitSequence > b.CommitSequence { return 1 }
    return 0
}

That ordering is only sound if CommitTimestamp is monotonic across the entire process. It isn't.

---

Why time.Now().UnixNano() Cannot Be Used as a Global Order

Wall-Clock Drift, Concretely

time.Now() on Linux ultimately calls clock_gettime(CLOCK_REALTIME). CLOCK_REALTIME is the wall clock and is subject to:

• NTP slewing (adjtime): the kernel slows or speeds the clock by up to 500 ppm to converge on the reference time.
• NTP stepping (settimeofday): if the offset exceeds the panic threshold (~128 ms by default), the clock jumps — possibly backward.
• PTP corrections in containerized hosts where the hypervisor's clock is the reference.
• VM live-migration, where the guest's CLOCK_REALTIME snaps to the destination host's clock on resume.
• Per-CPU rdtsc skew: clock_gettime reads a per-CPU TSC and converts it. If two goroutines are scheduled on different cores, their reads can disagree by tens to hundreds of nanoseconds — and the disagreement is not guaranteed to be in any particular direction.

A concrete sequence that breaks timestamp ordering:

t = T₀                  goroutine A: commit row R, stamp = 1_700_000_000_000_000_100
t = T₀ + 5µs            kernel applies NTP step, clock jumps -500ns
t = T₀ + 6µs            goroutine B: BeginTransaction, samples 1_700_000_000_000_000_050
goroutine B reads R
SI check: committed (100) > readVersion (50) → CONFLICT

There was no concurrent writer. The reader simply sampled a clock that had moved backward in the interim.

The Parser Is Faster Than the Clock Tick

time.Now() claims nanosecond resolution, but the underlying TSC tick is the actual quantum, and the kernel's vDSO + syscall path has its own latency floor. On a typical x86_64 Linux host, two back-to-back time.Now() calls return identical UnixNano() values an appreciable fraction of the time — anywhere from one in a few to one in a few hundred, depending on hardware.

Our parser benchmarks make this concrete:

BenchmarkParserValidationIsolation/Nornic/simple_match-16     30,066,961    39.09 ns/op    0 B/op    0 allocs/op
BenchmarkParserValidationIsolation/Nornic/match_with_label-16 21,996,284    53.20 ns/op    0 B/op    0 allocs/op
BenchmarkParserValidationIsolation/Nornic/create_node-16      17,062,600    70.40 ns/op    0 B/op    0 allocs/op
BenchmarkParserValidationIsolation/Nornic/merge_node-16       17,167,636    71.85 ns/op    0 B/op    0 allocs/op

A MATCH (n) RETURN n parses and validates in 39 nanoseconds. That is ~25.6 million queries per second on a single goroutine, with zero heap allocations. Throughput across query shapes is 450–550 MB/s of source text.

Compare to ANTLR on the same machine, same queries:

BenchmarkParserValidationIsolation/ANTLR/simple_match-16        494,116    4,725 ns/op    5,708 B/op    53 allocs/op
BenchmarkParserValidationIsolation/ANTLR/create_node-16         425,192    5,649 ns/op    6,700 B/op    62 allocs/op
BenchmarkParserValidationIsolation/ANTLR/match_where_in-16      152,034   15,616 ns/op   17,748 B/op   149 allocs/op

ANTLR is ~120× slower and allocates per parse. The fact that our parser is fast is not incidental — it is the entire reason UnixNano() cannot order our writes. Slow parsers naturally space commits apart by microseconds, and microsecond gaps swamp clock skew. We don't have that luxury.

Same-Tick Math

Suppose clock_gettime has an effective resolution of R nanoseconds (typical: R ∈ [1, 40]) and we are sustaining Q commits per second. The probability that two commits land in the same tick is approximately:

P(collision) ≈ 1 - e^(-Q·R / 1e9)

At Q = 1,000,000 commits/sec and R = 20 ns, P ≈ 1 - e^(-0.02) ≈ 1.98%. Roughly one collision every fifty commits. Over a 10-second ingestion burst, that's hundreds of unordered pairs — and we still need a total order to reason about snapshot isolation correctly.

Why time.Now()'s Monotonic Reading Doesn't Help

Go's time.Now() does include a monotonic reading from CLOCK_MONOTONIC. It is real, and it is genuinely monotonic. But:

• The monotonic component is stripped by UnixNano(). Per the Go docs: "Because the monotonic clock reading has no meaning outside the current process, serializing a t.UnixNano() value and parsing it back loses the monotonic reading."
• It is only meaningful between two time.Time values that share a wall+monotonic pair, used by Sub, After, Before, Equal. We persist a single int64 to disk.
• It is per-time.Time, not a process-global counter. Two independent time.Now() calls produce two independent monotonic samples that are not guaranteed to be totally ordered with respect to each other once you reduce them to scalars.

There is no public Go API that returns a single int64 of monotonic nanoseconds suitable for storage and cross-goroutine comparison. You can hack one with runtime.nanotime via //go:linkname, but it has the same per-process scope as time.Now()'s monotonic reading and ties us to runtime internals.

---

The Fix: A Process-Global Atomic Counter

pkg/storage/badger.go carries two atomic fields on the engine:

mvccSeq             atomic.Uint64  // strictly-increasing commit sequence
mvccHighWaterNanos  atomic.Int64   // max committed CommitTimestamp ever observed

Every commit calls allocateMVCCVersion(), which:

1. Atomically increments mvccSeq and reads the new value.
2. Reads time.Now().UnixNano().
3. Atomically advances mvccHighWaterNanos to max(highWater, now).
4. Returns MVCCVersion{CommitTimestamp: now, CommitSequence: seq}.

BeginTransaction() calls currentMVCCReadVersion(), which clamps now upward to mvccHighWaterNanos. A backward NTP step cannot make a new transaction observe a read timestamp earlier than something already committed.

Snapshot-isolation conflict detection in pkg/storage/badger_transaction.go then compares by sequence first:

func snapshotIsolationConflict(read, committed MVCCVersion) bool {
    if read.CommitSequence != maxMVCCCommitSequence &&
       committed.CommitSequence != maxMVCCCommitSequence {
        return committed.CommitSequence > read.CommitSequence
    }
    // Saturation fallback only — see below.
    return committed.CommitTimestamp > read.CommitTimestamp
}

Because mvccSeq is a single atomic that no commit can skip, the sequence is a true total order. The wall-clock timestamp is retained for two reasons: (a) it's human-readable in dumps and admin UIs, and (b) it's a fallback total order if and only if the sequence saturates.

Tests We Wrote

• TestCurrentMVCCReadVersion_ClampsToHighWater — read timestamp never precedes the high-water mark.
• TestAllocateMVCCVersion_AdvancesHighWater — high-water is monotonic even when wall-clock samples drift backward.
• TestBeginTransaction_DoesNotConflictAfterClockSkew — the original regression: bump high-water two seconds ahead, then commit; must not raise a phantom conflict.
• TestSnapshotIsolationConflict_UsesTimestampWhenSequenceSaturated — sequence-first ordering, with timestamp fallback only at saturation.
• TestAllocateMVCCVersion_FallsBackToTimestampOrderingWhenSequenceExhausted — when mvccSeq == ^uint64(0), advance the high-water timestamp by 1 ns rather than wrapping the counter to zero.

---

Time Until Overflow

mvccSeq is a uint64. Its maximum value is:

2^64 − 1 = 18,446,744,073,709,551,615

At a sustained commit rate of Q commits/sec, time-to-saturation is:

T = (2^64 − 1) / Q   seconds

Sustained commit rate	Time to overflow
1,000 commits/sec (heavy OLTP)	~584,942,417 years
1,000,000 commits/sec (extreme ingest)	~584,942 years
1,000,000,000 commits/sec (1B/sec, hypothetical)	~584.94 years
1,000,000,000,000 commits/sec (1T/sec, impossible)	~213 days

For reference, the Earth's projected remaining time before the Sun renders the surface uninhabitable is on the order of 10⁹ years. At 1 billion commits/sec — three orders of magnitude beyond what any single-machine database currently sustains — mvccSeq would still outlast a human civilization several times over. The saturation fallback exists for completeness, not because we expect anyone to hit it.

For a more defensible upper-bound argument: even if every Cypher query in our parser benchmark were a single committing write at peak parser throughput (~25.6 M qps for simple_match), T ≈ 22,800 years.

---

Why Not Other Techniques

A few alternatives we considered and rejected:

Hybrid Logical Clocks (HLC). HLC pairs a wall-clock with a logical counter and bumps the logical part on causality violations. It works well for distributed systems where you need wall-clock-aligned timestamps that also respect causality. For a single-node MVCC ordering, an atomic counter does the job with one-third the code and no max-skew tuning knob.

TrueTime / interval clocks. Spanner's TrueTime exposes [earliest, latest] bounds and waits out the uncertainty. This requires a hardware time source we don't have and introduces commit latency proportional to clock uncertainty. Overkill for single-node ordering.

runtime.nanotime via //go:linkname. Gives us a process-monotonic int64 of nanoseconds. Functionally close to what we want, but: (a) ties us to runtime internals that have changed in past Go releases, (b) is still per-process — useless for the eventual cross-node case where we'll want a counter that can be partitioned and merged.

time.Now() with a "monotonic clamp" only, no counter. This is what the high-water-mark mechanism does on its own. It prevents backward sampling, but it does not solve same-nanosecond ties. Two commits that legitimately land in the same UnixNano() bucket are unordered, and SI requires a total order.

The atomic counter is the smallest mechanism that provides the guarantee we need.

---

Closing Note

A useful heuristic: any time you find yourself reasoning about wall-clock ordering in code that runs faster than the wall clock can resolve, you have a logic bug waiting for an NTP correction to expose it. The fact that our Cypher parser executes in 39 ns isn't just a performance number — it's a correctness constraint on every other system in the database that wants to observe its output in order.