The Death of the Wait State: Engineering Global Multi-Writer Databases via Deterministic Scheduling

Imagine you’re building a payment ledger for a global fintech app. A user in Singapore sends $100 to a friend in London. At the exact same millisecond, an automated subscription service in New York tries to debited the sender’s account. In the world of traditional distributed databases, this is where things get ugly.

For decades, we’ve been told that linearizability at scale requires a heavy tax: the dreaded Two-Phase Commit (2PC). We’ve accepted that if we want high consistency across the globe, we have to endure the “speed of light problem”—waiting for multiple round-trips across the Atlantic just to release a row lock. We’ve lived with the fear of “zombie transactions” and coordinator failures that can freeze a database solid.

But what if I told you that the most sophisticated databases being built today—the ones powering the next generation of global infrastructure—are moving beyond 2PC?

By marrying Hybrid Logical Clocks (HLC) with State Machine Replication (SMR) and a Deterministic Scheduler, we can achieve multi-writer, globally distributed transactions that don’t just scale; they defy the traditional trade-offs of distributed systems. We’re moving from a world of negotiated consensus to ordered execution.

Let’s tear down the old architecture and look under the hood of the new one.

The Ghost in the Machine: Why 2PC is Killing Your Tail Latency

Before we look at the solution, we have to acknowledge the elephant in the room: Two-Phase Commit is fundamentally incompatible with modern global scale.

In a standard 2PC setup (used by many traditional RDBMS clusters), the process is a synchronous conversation:

1. The Prepare Phase: The coordinator asks all participating shards, “Can you commit this?”
2. The Commit Phase: If everyone says yes, the coordinator sends the “Do it!” command.

In a local data center, this is fast. Over the public internet between Tokyo and Dublin? It’s a disaster. If one node is slightly slow (a “straggler”), the entire transaction—and every other transaction waiting for those same locks—stalls. This creates a convoys effect, where throughput collapses as latency spikes.

Furthermore, 2PC is non-deterministic. The order in which transactions are processed depends on exactly when their packets hit the network. If two nodes receive the same two transactions in a different order, they have to use locks to resolve the conflict. Locking is the enemy of concurrency.

The Spanner Hype and the “TrueTime” Barrier

Google’s Spanner changed the game by introducing TrueTime, using atomic clocks and GPS receivers to provide tightly bound clock uncertainty. This allowed Spanner to achieve external consistency without the usual 2PC overhead. But unless you have Google’s CAPEX budget to install specialized hardware in every rack, TrueTime is out of reach for the rest of us.

This is where the engineering community started looking for a “Software-Defined Spanner”—a way to get those same guarantees using standard commodity hardware.

The Architecture of Certainty: Deterministic Scheduling

The core shift in thinking is this: Stop trying to resolve conflicts at the time of execution. Instead, agree on the order of transactions before you run them.

This is Deterministic Scheduling. If two nodes start with the same state and execute the same sequence of inputs in the exact same order, they will arrive at the exact same output state. No locks, no negotiation, no “Prepare” phase.

The Three-Layer Stack

To implement this globally, we need a three-layered architecture:

1. The Sequencing Layer (SMR): A distributed log (usually Raft or Paxos) that puts transactions in a global order.
2. The Timestamping Layer (HLC): A mechanism to give every transaction a causal, human-readable time without hardware clocks.
3. The Execution Layer: A deterministic scheduler that processes the log across many cores without hitting lock contention.

Deep Dive: Hybrid Logical Clocks (HLC)

If we are going to order transactions globally, we need a clock. But NTP (Network Time Protocol) is too jittery, and pure Logical Clocks (Lamport Clocks) don’t correspond to real-world time, making “point-in-time” queries impossible for humans.

Hybrid Logical Clocks (HLC) give us the best of both worlds. An HLC timestamp consists of two parts: (wall_time, logical_counter).

How HLC Works in the Wild

Every node maintains an HLC. When an event happens:

• If the local physical clock is ahead of the highest timestamp the node has seen, it updates the wall_time and resets the logical_counter to 0.
• If the local physical clock is behind, it keeps the highest wall_time it knows and increments the logical_counter.

// A simplified look at HLC Update Logic
struct HLC {
    wall_time: u64,
    counter: u32,
}

impl HLC {
    fn update(&mut self, remote_ts: HLC) {
        let now = get_physical_time();
        let max_wall = cmp::max(self.wall_time, cmp::max(remote_ts.wall_time, now));

        if max_wall == self.wall_time && max_wall == remote_ts.wall_time {
            self.counter = cmp::max(self.counter, remote_ts.counter) + 1;
        } else if max_wall == self.wall_time {
            self.counter += 1;
        } else if max_wall == remote_ts.wall_time {
            self.counter = remote_ts.counter + 1;
        } else {
            self.counter = 0;
        }
        self.wall_time = max_wall;
    }
}

By using HLC, we ensure that if Transaction A happened before Transaction B (causally), A will always have a lower timestamp than B. This provides causal consistency, which is the “holy grail” for distributed debugging and data integrity.

The Sequencer: State Machine Replication (SMR)

Now that we have timestamps, we need a way to ensure every node in the world sees the same list of transactions in the same order. This is where State Machine Replication comes in.

In a globally distributed multi-writer database, we don’t have one single leader (that would be a bottleneck). Instead, we shard the data. Each shard is a Raft group. When a write comes in, it’s proposed to the Raft group.

The “Calvin” Approach

Named after the seminal paper by Alexander Thomson, the Calvin-style approach takes the SMR log and batches transactions. Instead of committing one by one, we collect transactions into 10ms or 50ms epochs.

All nodes across the globe agree on the contents of “Epoch 1001.” Once the epoch is closed, the deterministic scheduler takes over. Since every node has the exact same list of transactions for Epoch 1001, they can all execute them locally without ever talking to each other again during that epoch.

This is the “magic” moment. We’ve moved the consensus overhead to the input stage, rather than the execution stage. The network round-trip happens once per batch, rather than once per lock.

The Engineering Heart: The Deterministic Scheduler

This is where the rubber meets the road. How do you execute a batch of transactions across 64 CPU cores as fast as possible while ensuring the result is 100% deterministic?

If you just run them in a loop, you’re wasting the power of modern hardware. If you run them in parallel with standard mutexes, the order of lock acquisition might change, leading to different results on different nodes (non-determinism).

Lock-Free Pre-Analysis

The scheduler performs a static analysis of the batch before a single transaction is executed. It looks at the “Read Set” and “Write Set” of every transaction in the epoch.

1. Dependency Graph Construction: The scheduler builds a directed acyclic graph (DAG). If Transaction A writes to Key X and Transaction B reads Key X, a dependency edge is drawn from A to B.
2. Lock-Free Execution: The scheduler hands off transactions with zero dependencies to a pool of worker threads.
3. Completion Triggers: As soon as Transaction A finishes, it “unlocks” Transaction B in the graph, which is then immediately scheduled.

Because the execution order for conflicting keys is baked into the batch sequence, we don’t need real heavy-weight locks. We use virtual locks—counters that track how many previous transactions in the batch must finish before a specific key is “safe” to touch.

Code Snippet: The Scheduler’s Core Loop

func (s *Scheduler) ExecuteEpoch(batch []Transaction) {
    // 1. Analyze dependencies
    for _, tx := range batch {
        s.virtualLockManager.Acquire(tx.ReadSet, tx.WriteSet, tx.ID)
    }

    // 2. Dispatch ready transactions
    for _, tx := range batch {
        if s.virtualLockManager.IsReady(tx.ID) {
            go s.workerPool.Run(tx)
        }
    }
}

// When a worker finishes
func (w *Worker) OnComplete(txID int64) {
    readyTxs := s.virtualLockManager.Release(txID)
    for _, nextID := range readyTxs {
        go s.workerPool.Run(s.txMap[nextID])
    }
}

Solving the “Global” in Globally Distributed

When we move this architecture to a global scale, we encounter a unique challenge: The Batching Latency.

If a node in New York has to wait for a node in London to agree on a batch, the minimum latency for any write is the cross-Atlantic RTT (~70ms). For many applications, 70ms is fine. For high-frequency trading or real-time gaming, it’s an eternity.

Geographic Partitioning and “Partial Order”

To solve this, modern multi-writer databases use Geographic Sharding.

• Transactions that only affect data in the “US-East” region are sequenced by a local Raft group.
• Only “Global Transactions” (those touching data in both US and EU) require the global sequencer.

By using HLCs, the system can interleave local logs and global logs into a single, causally consistent stream. If a local transaction has an HLC timestamp of (100, 5) and a global one has (101, 0), the scheduler knows exactly how to order them without needing to block the local transaction for a global consensus.

Infrastructure Scale: The Compute Behind the Curtain

Implementing this isn’t just about smart algorithms; it’s about handling massive compute throughput.

In a non-deterministic database, a huge chunk of your CPU is wasted on Lock Contention (context switching, spinning on mutexes). In a deterministic system, the bottleneck shifts to the Sequencer throughput and Dependency analysis.

To handle this at scale (think 1 million+ transactions per second), we look at several engineering optimizations:

1. The LMAX Disruptor Pattern

For the sequencing layer, we often use a circular buffer (Disruptor) pattern to pass transactions between the network stack and the dependency analyzer. This keeps the CPU caches hot and avoids the overhead of Go channels or locked queues.

2. User-Level Threading (Fibers)

Since we are managing thousands of mini-tasks (individual transactions in a batch), the overhead of OS-level threads is too high. We use Coroutines or Fibers. In Rust, this means leveraging async/await with a custom executor optimized for the dependency graph.

3. Shared-Nothing Memory Architecture

To avoid NUMA (Non-Uniform Memory Access) bottlenecks on large multi-socket servers, we partition the data so that specific CPU cores “own” specific shards of the virtual lock manager. This minimizes cross-socket bus traffic—a detail often overlooked until you hit the million-TPS mark.

Resilience: What Happens When a Region Goes Dark?

One of the biggest criticisms of deterministic systems is their perceived fragility. If everything is “pre-ordered,” what happens if a node fails mid-batch?

In 2PC, a failed node might hold locks indefinitely. In a Deterministic SMR system, the failure is handled at the Replication layer, not the Execution layer.

1. Raft/Paxos handles the failover. If the leader of a shard dies, a new leader is elected.
2. The Log is the Truth. Because the sequence of transactions is already committed to the distributed log, the new leader simply plays back the log.
3. Deterministic Recovery. Since the execution is deterministic, the new leader is guaranteed to reach the exact same state as the old leader was in before it crashed. There is no need for complex “undo/redo” log reconciliation for the state machine itself.

The Actual Substance Behind the Hype

We see a lot of marketing buzz around “Global Databases.” But when you strip away the fluff, the industry is converging on this specific stack: HLC + SMR + Determinism.

• FaunaDB uses a variation of the Calvin protocol to provide global ACID transactions.
• FoundationDB (the backbone of Snowflake and many Apple services) uses a sophisticated sequencing proxy to achieve similar deterministic properties.
• CockroachDB utilizes HLCs extensively to provide serializable isolation without atomic clocks.

The reason this matters is predictability. In a 2PC system, your latency graph looks like a “hockey stick” as load increases—it stays low, then explodes as lock contention hits. In a deterministic system, your latency is constant. It is bound by the batch interval and the network RTT. For an engineer, a steady, predictable 50ms is infinitely better than a “usually 5ms but sometimes 5s” performance profile.

Engineering Curiosities: The “Aborted” Transaction Problem

You might be wondering: “If we decide the order before we execute, what happens if a transaction has to fail?” (e.g., a bank account has insufficient funds).

In a non-deterministic system, you just roll back the transaction and release the locks. In a deterministic system, you can’t just “stop.” Every node must reach the same conclusion.

The solution is Deterministic Aborts. The logic for the abort must be part of the state machine. If the code says if balance < 100 { abort }, every node running that code will see the same balance and decide to abort at the same point in the sequence. The transaction is still “processed” (it consumes a slot in the batch), but its side effects are not applied.

The Future: Moving to the Edge

As we push database logic to the “Edge” (Cloudflare Workers, Fastly Compute@Edge), the “Beyond 2PC” movement becomes even more critical. In an Edge environment, you have thousands of small points of presence. You cannot run a global 2PC across 300 cities.

Deterministic scheduling allows these edge nodes to act as “read replicas” that are logically consistent with the “writer nodes.” By streaming the ordered log to the edge, we allow local users to read data that is guaranteed to be causally consistent with their own previous writes, solving the “Read-Your-Writes” problem that plagues most eventually-consistent edge caches.

The Takeaway for Architects

If you are designing systems that require:

1. Global footprint with multi-writer capabilities.
2. Strict Serializability (the highest level of safety).
3. Predictable Tail Latency under high contention.

Then it’s time to look past the legacy of Two-Phase Commit. The combination of Hybrid Logical Clocks for causal ordering and Deterministic Scheduling for lock-free execution is no longer a theoretical research paper topic—it is the blueprint for the next decade of distributed data.

The speed of light isn’t getting any faster. It’s time our databases stopped waiting for it.