Reclaiming 100TB of RAM via Mathematics and Rust

Cloudflare operates on a scale that often defies intuition. With a global footprint consisting of thousands of servers, millions of CPU cores, and petabytes of memory, our infrastructure is constantly pushed to its absolute limits.

Because these resources are finite—and because we require every single service to be deployed on every node—there is no room zero room for inefficiency. In an environment this massive, a mere 1% optimization is a significant victory.

In this article, we explore how minor algorithmic adjustments to a specific service allowed us to recover over 100TB of RAM globally. This follows a similar success by the DNS team, who also shed 100TB of memory last month.

The Quest for Efficiency

Maintaining a fair distribution of resources across various teams in a giant organization is a complex task. This is where the Performance team steps in.

The catalyst for this specific optimization was a ticket submitted by Ivan, who flagged an issue:

"Excessive memory usage from pingora-ketama in Pingora Backend Router."

The investigation revealed that the Pingora Backend Router (PBR)—our internal load-balancing service—was consuming far more memory than anticipated. The culprit was the pingora-ketama library, an open-source tool used for consistent hashing.

What is Consistent Hashing?

Consistent hashing is a strategy for distributing workloads across a cluster of servers. Its primary advantage is that it minimizes the need for massive re-mappings when servers are added to or removed from the pool.

Our Use Case:

• We route cacheable requests to specific servers based on the URL.
• This ensures only one copy of a file exists per data center.
• It provides a deterministic method for locating files.

How it Works

Hash functions take an input and produce a fixed-size unsigned integer (typically 32, 64, or 128 bits). While often visualized as a circular ring, it is simpler to think of this as a number line.

1. Mapping: Servers (via IP) and tasks (via cache keys) are hashed onto this line.
2. Assignment: A task is assigned to the first server encountered to its left.
3. Wrapping: The range for the final server wraps around to the start of the line (creating the "ring").

The Problem: Statistical Imbalance

While the basic concept is simple, the reality is messy. Because hashes are essentially random, the "distance" between servers on the number line varies. If Server A's range is larger than Server B's, Server A will handle a disproportionately higher volume of requests.

To quantify this, we look at the statistics of the fractional range size for $N$ servers:

Key Metrics:

• Expected Value ($\text{Exp}$): The center point of the distribution.
• Standard Deviation ($\text{SD}$): How much the actual values deviate from the center.

The formulas are as follows:

$\text{Exp} = \frac{1}{N}$ $\text{SD} = \frac{1}{N}\sqrt{\frac{N-1}{N+1}}$

Concrete Example: $N = 100$ Servers

At first glance, a $0.99\%$ deviation seems negligible. However, we must calculate the Coefficient of Variation (CV) to understand the error relative to the target size:

$\text{CV} = \frac{\text{SD}}{\text{Exp}} = \sqrt{\frac{N-1}{N+1}}$

For $N=100$, the $\text{CV} \approx 99\%$. This implies a staggering imbalance: some servers might work twice as hard as others, while some remain nearly idle.

Implementation Details

To address this, we utilize Rust for its memory safety and performance. Below is a conceptual representation of how such a hashing structure might be initialized in a pingora-ketama context:

// Conceptual snippet for Ketama-style hashing
struct ConsistentHashRing {
    nodes: Vec<Node>,
    ring: BTreeMap<u32, NodeId>,
}

impl ConsistentHashRing {
    fn add_node(&mut self, node: Node) {
        // Add multiple virtual nodes to reduce CV
        for i in 0..VIRTUAL_NODES {
            let hash = hash_function(format!("{}:{}", node.id, i));
            self.ring.insert(hash, node.id);
        }
    }
}

Optimization Checklist

• Identify memory leak/overuse in pingora-ketama.
• Analyze statistical distribution of server ranges.
• Calculate Coefficient of Variation (CV).
• Implement range balancing to reduce RAM footprint.

Now that we have a way to predict how evenly loaded servers...