CockroachDB & YugabyteDB Internals: Hybrid Logical Clocks (HLC), Multi-Raft Consensus & Distributed MVCC

In modern cloud-native database engineering (CockroachDB, YugabyteDB, TiDB), applications require full PostgreSQL compatibility alongside elastic horizontal scaling.

While Google Spanner demonstrated global linearizability, it relies on proprietary GPS receivers and Rubidium atomic clock hardware (TrueTime) to bound physical clock uncertainty.

To deliver Spanner-grade distributed transactions on commodity cloud VMs (AWS EC2, GCP, Azure), open-source Distributed SQL engines deploy Hybrid Logical Clocks (HLC).

By pairing HLC time tracking with Multi-Raft Range Partitioning and Distributed MVCC Write Intents, these databases execute multi-shard transactions with strict serializability on standard hardware.

This article details Hybrid Logical Clock math, Multi-Raft $64\text{ MB}$ range splits, Distributed Multi-Version Concurrency Control (MVCC), and Write Intent transaction records.

Distributed SQL Architecture & HLC Multi-Raft Mechanics

How CockroachDB and YugabyteDB combine Hybrid Logical Clocks and Multi-Raft consensus to execute distributed ACID transactions:

Core Open-Source Distributed SQL Mechanics

1. Hybrid Logical Clocks (HLC):
   • Standard physical clocks ($pt$) drift due to NTP network latency. Pure logical clocks (Lamport clocks) lack correlation with real-world time.
   • HLC Tuple Format: Represented as a pair $(l, c)$, where $l$ represents the highest physical timestamp observed and $c$ is a logical sequence counter.
   • HLC Update Rules:
     • When local event occurs: $l' = \max(l, \text{pt})$. If $l' == l$, $c = c + 1$; else $c = 0$.
     • When receiving message with $(l_m, c_m)$: $l' = \max(l, \text{pt}, l_m)$. If $l'$ equals both $l$ and $l_m$, $c = \max(c, c_m) + 1$; else if $l' == l$, $c = c + 1$; else $c = 0$.
   • Max Offset Guardrail: If physical clock drift $|l - \text{pt}| > \text{max_offset}$ (e.g. $500\text{ms}$), the node self-terminates to prevent causality violations!
2. Multi-Raft Range Partitioning:
   • Instead of running a single global Raft consensus group (which creates a CPU bottleneck), tables are split into contiguous $64\text{ MB}$ Ranges.
   • Each $64\text{ MB}$ Range is managed by its own independent Multi-Raft Group consisting of 3 or 5 replica nodes across the cluster.
   • Automatic Range Splitting: When a Range exceeds $64\text{ MB}$, it automatically splits into two new Ranges, spawning a new Multi-Raft consensus group in milliseconds.
3. Distributed MVCC & Write Intents:
   • Writes in CockroachDB/YugabyteDB do not modify data in-place. They append Multi-Version Concurrency Control (MVCC) keys tagged with the transaction's HLC timestamp (key@HLC).
   • Write Intents: When a transaction modifies multiple rows, it writes Write Intents containing a pointer to a central Transaction Record (/sys/txn/txn_id).
   • Atomic One-Bit Commit: When the transaction completes, updating the Transaction Record status from PENDING to COMMITTED atomically converts all distributed Write Intents into permanent readable MVCC values instantaneously!

Python Implementation: Hybrid Logical Clock & Multi-Raft Simulator

Here is a production-grade Python implementation of a Hybrid Logical Clock (HLC) and Multi-Raft Range Partitioning Engine Simulator:

import time
from typing import Dict, List, Optional, Tuple
from pydantic import BaseModel

class HLCTimestamp(BaseModel):
    l_physical: int # Physical time in ms
    c_logical: int  # Logical counter

    def __gt__(self, other: 'HLCTimestamp') -> bool:
        if self.l_physical != other.l_physical:
            return self.l_physical > other.l_physical
        return self.c_logical > other.c_logical

class HybridLogicalClockEngine:
    """
    Simulates Hybrid Logical Clock (HLC) Math (Kulkarni et al.).
    Provides strict causality without atomic clocks!
    """
    def __init__(self, max_offset_ms: int = 500):
        self.l = 0
        self.c = 0
        self.max_offset_ms = max_offset_ms

    def get_physical_now(self) -> int:
        return int(time.time() * 1000)

    def now(self) -> HLCTimestamp:
        """Generates HLC timestamp for local event."""
        pt = self.get_physical_now()
        l_old = self.l
        self.l = max(l_old, pt)

        if self.l == l_old:
            self.c += 1
        else:
            self.c = 0

        if abs(self.l - pt) > self.max_offset_ms:
            raise RuntimeError(f" 🔴 [HLC FATAL DRIFT] Clock offset ({abs(self.l - pt)}ms) exceeded max_offset ({self.max_offset_ms}ms)!")

        return HLCTimestamp(l_physical=self.l, c_logical=self.c)

    def update_on_receive(self, remote_hlc: HLCTimestamp) -> HLCTimestamp:
        """Updates HLC upon receiving remote message tuple (l_m, c_m)."""
        pt = self.get_physical_now()
        l_old = self.l
        self.l = max(l_old, pt, remote_hlc.l_physical)

        if self.l == l_old and self.l == remote_hlc.l_physical:
            self.c = max(self.c, remote_hlc.c_logical) + 1
        elif self.l == l_old:
            self.c += 1
        elif self.l == remote_hlc.l_physical:
            self.c = remote_hlc.c_logical + 1
        else:
            self.c = 0

        return HLCTimestamp(l_physical=self.l, c_logical=self.c)

class MultiRaftRangeEngine:
    """
    Simulates CockroachDB Multi-Raft Range Partitioning & Write Intents.
    """
    def __init__(self):
        self.hlc = HybridLogicalClockEngine()
        # Range partitions: { (start_key, end_key) -> { mvcc_key -> val } }
        self.kv_store: Dict[str, Tuple[HLCTimestamp, str, str]] = {} # key@HLC -> (hlc, val, status)

    def write_intent(self, key: str, value: str, txn_id: str) -> HLCTimestamp:
        ts = self.hlc.now()
        mvcc_key = f"{key}@{ts.l_physical}:{ts.c_logical}"
        self.kv_store[mvcc_key] = (ts, value, f"INTENT:{txn_id}")
        print(f" 📥 [Write Intent Pushed] Key: '{key}' -> Value: '{value}' (HLC: {ts.l_physical}:{ts.c_logical}, TxnID: '{txn_id}')")
        return ts

    def commit_transaction_intent(self, key: str, ts: HLCTimestamp, txn_id: str):
        mvcc_key = f"{key}@{ts.l_physical}:{ts.c_logical}"
        if mvcc_key in self.kv_store:
            _, val, _ = self.kv_store[mvcc_key]
            self.kv_store[mvcc_key] = (ts, val, "COMMITTED")
            print(f" 🔒 [Transaction Committed] Intent on '{key}' marked COMMITTED at HLC ({ts.l_physical}:{ts.c_logical})")

# Demonstration Execution
if __name__ == "__main__":
    multi_raft = MultiRaftRangeEngine()

    print("🚀 Demonstrating CockroachDB & YugabyteDB Internals (HLC & Multi-Raft)...")
    print("=" * 75)

    # 1. Generate Local HLC Timestamps
    t1 = multi_raft.hlc.now()
    print(f" ⏱️ Local HLC T1: ({t1.l_physical}ms, counter={t1.c_logical})")

    # 2. Push Write Intent for Distributed Transaction
    txn_id = "txn_alpha_99"
    ts_intent = multi_raft.write_intent(key="user_balance_101", value="$500.00", txn_id=txn_id)

    # 3. Commit Transaction Record (Atomic Intent Resolution)
    multi_raft.commit_transaction_intent(key="user_balance_101", ts=ts_intent, txn_id=txn_id)

Distributed SQL Gotchas & Best Practices

When deploying open-source Distributed SQL clusters:

Real-World Enterprise Impact

Distributed SQL internals (in CockroachDB, YugabyteDB, and TiDB) report:

• Spanner-Grade Reliability on Commodity Cloud Hardware: Delivers multi-region ACID transactions without requiring atomic clock GPS hardware.
• Elastic Horizontal Auto-Scaling: $64\text{ MB}$ Multi-Raft range splits allow clusters to scale linearly across hundreds of nodes.