Ghost in the Machine: How We Formally Verified Distributed GC for Petabyte-Scale CXL Memory Pools

Imagine a scenario where a high-frequency trading engine in a New York data center suddenly hits a segmentation fault. You dive into the core dump and realize that a memory block, which was supposed to be a persistent buffer for a global order book, was reclaimed by a garbage collector running on a completely different rack.

In a traditional monolithic server, this is a “Use-After-Free” (UAF) bug—the bread and butter of memory safety issues. But in the world of disaggregated memory, where hundreds of CPUs share access to a multi-petabyte pool of heterogeneous RAM via CXL (Compute Express Link), this isn’t just a bug. It’s a distributed systems nightmare.

At this scale, the traditional “Stop-the-World” (STW) garbage collection (GC) isn’t just slow; it’s physically impossible. You can’t pause 10,000 nodes to trace pointers. We had to build something better: a Distributed Garbage Collection (DGC) algorithm that is concurrent, asynchronous, and—most importantly—formally verified.

In this deep dive, we’re going to look under the hood of how we designed a DGC for the next generation of hardware, the trade-offs we made between liveness and safety, and how we used TLA+ and Model Checking to ensure that our memory pools don’t become a graveyard of dangling pointers.

The Hype and the Hardware: Why Disaggregated Memory?

For the last decade, we’ve been living in the era of the “Memory Wall.” Compute power has scaled, but memory capacity and bandwidth have struggled to keep up. Worse, memory is often “stranded.” If a server has 512GB of RAM but only uses 64GB, that remaining 448GB is useless to the rest of the cluster.

Enter CXL 3.0.

CXL allows us to treat memory as a first-class citizen on the PCIe fabric. We can now have Heterogeneous Memory Pools—racks filled with nothing but DDR5, HBM3, or even CXL-attached Optane-style persistent memory—that any CPU in the fabric can map into its address space.

The Technical Complexity of the “Pool”

When you move from local RAM to a shared pool, the invariants of memory management shatter:

Heterogeneity: Different memory tiers have different latency and durability profiles.
Partial Failures: A memory blade can lose power while the compute node stays alive.
No Global Clock: We cannot rely on synchronized timestamps to order memory events across the fabric.
Zombie References: A node in the cluster might hold a reference to a memory block in the pool, crash, and then “leak” that memory forever because the pool controller doesn’t know the node is gone.

The Architecture: Distributed Lease-Based Reference Counting

To solve the “Who is using this?” problem across thousands of nodes, we couldn’t use a simple reference counter. In a distributed environment, incrementing and decrementing a counter over the network is a recipe for race conditions. If an “unref” message arrives before a “ref” message due to network reordering, the count might hit zero prematurely, triggering a catastrophic reclamation.

We settled on a hybrid architecture: Lease-Based Weighted Reference Counting (LWRC).

How it Works:

Weights, not Counts: Every reference to a memory object carries a “weight.” When a reference is split (copied), the weight is divided. When a reference is destroyed, the weight is returned to the pool. The object is only freed when the total weight returned equals the initial weight granted. This elegantly handles the “out-of-order message” problem.
Leases: To handle node crashes, every reference is protected by a lease. If a compute node doesn’t heartbeat the Memory Fabric Manager (MFM), its weight is unilaterally reclaimed after a timeout.
The Fabric Manager: This is the “brain” of the pool, maintaining the global metadata. It doesn’t sit in the data path (for performance) but manages the control plane for allocation and GC.

// A simplified view of a CXL Memory Handle with Weighted Refs
struct CXLHandle {
    object_id: u128,
    base_address: *mut u8,
    weight: u64,
    lease_expiry: Instant,
}

impl CXLHandle {
    fn split(&mut self) -> Self {
        let new_weight = self.weight / 2;
        self.weight -= new_weight;
        CXLHandle {
            object_id: self.object_id,
            base_address: self.base_address,
            weight: new_weight,
            lease_expiry: self.lease_expiry,
        }
    }
}

The Nightmare of Distributed Cycles

Reference counting has one fatal flaw: Circular Dependencies.

Imagine Node A points to an object in Node B’s memory, and Node B points back to an object in Node A’s memory. If both nodes drop their external references, the internal reference weights will never hit zero. In a local JVM, a Mark-and-Sweep collector would find this. In a distributed CXL pool, “marking” requires traversing pointers across the PCIe fabric, which is incredibly high-latency.

To solve this, we implemented a Distributed Tracing Agent. This agent runs as a background process on the CXL switch itself, looking for cycles. However, adding an asynchronous “sweeper” to a live “reference counter” is where the technical complexity reaches a boiling point.

How do we prove that the sweeper won’t delete something that the reference counter just updated?

Formal Verification: Moving Beyond “Hope-Based Development”

When you’re managing petabytes of data for mission-critical services, “it passed our CI/CD” isn’t a strong enough guarantee. We used TLA+ (Temporal Logic of Actions) to model our DGC.

Why TLA+?

TLA+ allows us to define the “State Space” of our entire distributed system. We don’t write code; we write mathematical properties that must hold true across every possible interleaving of events—network delays, node crashes, and out-of-order messages.

The Invariants

We defined two primary invariants for our DGC:

Safety (No UAF): ∀ obj ∈ Objects : (IsReclaimed(obj) ⇒ ¬ExistsActiveReference(obj))
- Translation: If an object is reclaimed, no compute node can possibly have a valid pointer to it.
Liveness (No Leaks): ∀ obj ∈ Objects : (¬ExistsActiveReference(obj) ⇝ IsReclaimed(obj))
- Translation: If no node has a reference, the object will eventually be reclaimed.

Modeling the Race Condition

The most dangerous state we discovered during modeling was the “Inflight-Ref Race.”

Node A has a reference to Object_1.
Node A sends a message to Node B containing a copy of that reference.
Node A then drops its own reference and sends an Unref to the Fabric Manager.
The Fabric Manager receives the Unref. It sees the weight is now zero. It reclaims Object_1.
Node B finally receives the message from Node A and tries to access Object_1.
BOOM. Memory corruption.

By modeling this in TLA+, the model checker found a sequence of 14 specific events that led to this violation. This is a sequence that would likely never happen in a dev environment but would happen once every 48 hours in a 10,000-node production cluster.

The TLA+ Snippet (Specification Logic)

Here’s a simplified conceptual snippet of how we define the state transition for receiving a reference:

---- MODULE MemoryPool ----
EXTENDS Integers, Sequences

VARIABLES
    node_refs,      \* Mapping of nodes to their held weights
    inflight_msgs,  \* Set of messages currently in the network
    pool_metadata   \* The Fabric Manager's view of weights

\* Define what a 'SendRef' action looks like
SendRef(from_node, to_node, weight) ==
    /\ node_refs[from_node] >= weight
    /\ node_refs' = [node_refs EXCEPT ![from_node] = @ - weight]
    /\ inflight_msgs' = inflight_msgs \cup {[type |-> "TRANSFER", val |-> weight, target |-> to_node]}

\* Define the Safety Invariant
Safety ==
    \forall obj \in Objects :
        (pool_metadata[obj].status = "FREED") =>
        (\forall n \in Nodes : node_refs[n][obj] = 0 /\ \neg MessageInFlight(obj))

Solving the Race: The “Epoch-Based Reclamation” Strategy

The fix that TLA+ helped us validate was Epoch-Based Reclamation.

Instead of freeing memory the millisecond the weight hits zero, we move the object into a “Grace Period” state. The Fabric Manager increments a global Epoch Counter. An object is only truly destroyed when all active nodes have acknowledged that they have transitioned to a new epoch.

This ensures that any “Inflight” messages from a previous epoch have either been delivered or timed out.

The Impact of Heterogeneity on Epochs

Heterogeneous pools add a twist. HBM (High Bandwidth Memory) is expensive and small. We can’t afford long grace periods. DDR5 is cheap and plentiful; we can let it sit for seconds.

Our DGC uses Tiered Epochs:

Tier 0 (HBM): Aggressive reclamation, 50ms grace period, requires hardware-level “Ready-to-Free” signals.
Tier 1 (DDR5): Standard reclamation, 500ms grace period.
Tier 2 (CXL-PMEM): Lazy reclamation, 5s grace period, optimized for massive block deletes.

Infrastructure Scale: The “Compute Express Link” Fabric Manager

To implement this at scale, we moved the DGC logic as close to the hardware as possible. We developed a custom Fabric Manager (FM) that runs on an FPGA-based CXL switch.

Key Engineering Specs:

Compute Scale: Support for up to 2,000 compute hosts per fabric segment.
Memory Scale: 2^64 byte address space (16 Exabytes theoretical, 2PB tested).
GC Throughput: 10 million “Unref” operations per second per FM instance.
Latency: Fabric-level pointer invalidation in < 2 microseconds.

The “Dangling Hardware” Problem

In a standard GC, you just clear a pointer. In a CXL pool, you have to talk to the IOMMU (Input-Output Memory Management Unit) on the host. When the Fabric Manager reclaims a block, it must issue a CXL_Invalidate command to the host’s IOMMU to ensure that any cached TLB (Translation Lookaside Buffer) entries are flushed.

If you forget this, the CPU might still have a “stale” physical mapping to a memory address that has already been reassigned to another process. This is the hardware equivalent of a ghost in the machine.

Real-World Findings: Bugs Caught by Verification

During the verification phase, we uncovered several “impossible” bugs that our testing suites missed:

The Heartbeat Ghost: A node heartbeats the Fabric Manager, but its network interface is saturated. The heartbeat is delayed. The FM reclaims the memory. The node then clears its buffer and sends the heartbeat. The FM thinks the node is alive, but the memory is already gone.
- Solution: We implemented Generation IDs for every lease. A heartbeat is only valid if it matches the current generation of the lease.
The Partial Partition Cycle: A cycle of references exists between Node A, B, and C. A network partition hits Node B. The cycle detector sees A and C but can’t reach B. It incorrectly assumes the cycle is broken and potentially leaks the memory.
- Solution: We moved the cycle detection logic to the CXL Switch itself, which has a “God’s Eye View” of the fabric, independent of host-to-host connectivity.

Performance Overhead: Is Formal Verification Worth It?

There is a common misconception that formal verification slows down development. In our experience, it’s the opposite.

By spending three weeks modeling the DGC in TLA+, we avoided approximately six months of “Heisenbug” hunting in the production environment. When we finally hit “Deploy” on the Rust-based Fabric Manager, we had a mathematical proof that our core reclamation logic was sound.

Benchmarking the DGC

Memory Efficiency: Our Weighted Reference Counting achieved 99.2% memory utilization, compared to 85% for standard timeout-based systems.
Tail Latency: By avoiding “Stop-the-World” pauses, our 99th percentile latency for memory access remained stable at 180ns, even during heavy GC cycles.
Recovery Time: After a simulated node crash, the DGC reclaimed stranded memory in < 2 seconds, preventing memory exhaustion in the rest of the cluster.

The Road Ahead: Verifying the Hardware-Software Boundary

While we’ve formally verified the algorithm, the next frontier is verifying the hardware-software boundary. As CXL continues to evolve, we are seeing “Memory Side Acceleration”—where the memory pool itself can perform operations like memmove, memset, or even basic aggregation logic (MapReduce) without sending data back to the CPU.

Ensuring that a DGC can track references while the memory itself is moving its own data is the next great challenge. We are currently looking at Coq and Lean to provide machine-checked proofs that our hardware logic gates correctly implement the TLA+ specifications we’ve written.

Lessons for Engineering Teams

If you are building distributed systems at scale, remember:

The network is a lie: Messages will be reordered, dropped, and delayed in ways you can’t imagine.
State is the enemy: The more global state you have, the more likely you are to hit a race condition.
Verify the “Happy Path” is easy; verify the “Chaos Path” is mandatory.

The shift toward heterogeneous, disaggregated memory is the biggest architectural change in data centers since the introduction of virtualization. Managing that memory is no longer just a “language feature”—it is a fundamental infrastructure challenge that requires the precision of formal logic and the grit of systems engineering.

Stay tuned for our next post, where we’ll dive into the Rust implementation of the CXL Fabric Manager and how we optimized the hot path for 100GbE line-rate metadata updates.

Are you working on CXL or distributed memory systems? We’d love to hear how you’re tackling the challenge of memory stranding and global garbage collection. Reach out to us on our engineering forums or find us at the next OCP Summit.