How Pingora keeps count

Replacing hash tables with probability

Cloudflare has published the first in a planned series of code libraries from Pingora, the in-house proxy that replaced NGINX. The initial release is pingora-limits, a crate for counting inflight events and estimating event rates over time — functions typically used to shield infrastructure from malicious or misbehaving traffic.

One motivating case: when an origin server slows down or becomes unresponsive, requests pile up on Cloudflare's servers and the customer's. The library identifies which origins are troubled so action can be taken without disturbing other traffic.

The underlying problem is simple. A stream of different event types arrives continuously, and at any moment the system must report how often a given type has appeared. The obvious solution is a hash table mapping each key to a counter, giving O(1) time per event but O(n) space where n is the number of event types. That approach has two practical drawbacks at Cloudflare's scale:

• Traffic is observed to millions of distinct servers, but only a few misbehave at any time. Holding counters for all keys wastes memory.
• Concurrent updates, especially when adding new keys, require a lock. Under heavy contention this serializes event processing and becomes a bottleneck.

These inefficiencies matter: the algorithm runs on tens of thousands of machines and handles more than twenty million requests per second.

Count–min sketch

pingora-limits instead uses a count–min sketch (CM sketch), a probabilistic structure related to Bloom filters. It estimates counts in O(1) time per event with only polylogarithmic space. Because the algorithm is fundamentally simple, it can be implemented without locks, giving substantial speed and memory advantages over hash tables.

A CM sketch has two parameters: H, the number of hashes (rows), and N, the number of counters per row (columns), forming an H×N matrix. Each row has its own independent hash function.

When an event such as "red" arrives, each row hashes the event to a column with its own function and increments that counter, without worrying about collisions. Retrieval asks each row for the value in the column to which the key maps and returns the minimum across all rows.

Collisions are acceptable. Consider a "blue" event that collides with "red" in row 2, with both hashing to the third slot. Over subsequent events, estimated counts drift higher in some rows. But because the min() operation picks the cells with the fewest collisions, any row without a collision for a given key preserves an accurate count.

The estimator can overestimate when two or more keys collide on every row. With two keys, the probability of a total collision is 1 / N^H. Crucially, it never underestimates, because no event is ever dropped.

Practical implementation

The algorithm needs only hashing, array indexing, and counter increment, so the Rust implementation is compact and lock-free:

pub struct Estimator {
    estimator: Box<[(Box<[AtomicIsize]>, RandomState)]>,
}
 
impl Estimator {
    /// Increment `key` by the value given. Return the new estimated value as a result.
    pub fn incr<T: Hash>(&self, key: T, value: isize) -> isize {
        let mut min = isize::MAX;
        for (slot, hasher) in self.estimator.iter() {
            let hash = hash(&key, hasher) as usize;
            let counter = &slot[hash % slot.len()];
            let current = counter.fetch_add(value, Ordering::Relaxed);
            min = std::cmp::min(min, current + value);
        }
        min
    }
}

Performance comparison

Pingora's team benchmarked the sketch against two hash-table designs: 1. Naive: a Mutex<HashMap<u32, usize>>, locking on every operation. 2. Optimized: a DashMap<u32, AtomicUsize>, which shards keys across multiple internal hash tables to cut contention and uses atomic counters so reading existing keys needs no write lock.

Both test cases used one million keys generating 100 million events, uniformly distributed, running on a Debian VM on an M1 MacBook Pro.

In the single-threaded case, where there is no lock contention, the CM sketch is 5x faster than the naive hash table and 4x faster than the optimized one. With multiple threads and high contention, the sketch and the optimized hash table both run 7x faster than the naive version — in both fast designs the hot path is just an atomic counter update.

Peak memory use was about 1/2000 that of the naive hash table and 1/1300 that of the optimized version in single-threaded tests. The sketch is efficient on both CPU and memory.

This is a biased estimator: it can overreport event counts. Where exact counting is mandatory, the sketch still works well as a front-end filter, sending only events above a threshold to a hash table for precise tallies. Most low-frequency event types are filtered out, so the hash table stays small without sacrificing accuracy.

Production use: connection limits

Cloudflare uses the library in production, most commonly for connection limits. When servers attempt too many simultaneous connections to a single origin, the feature rejects new requests with 503 errors to protect both the origin and Cloudflare's own infrastructure.

On every incoming request the feature increments a counter shared by all requests with the same customer ID, server IP, and server hostname. The counter is decremented when the request terminates. If the count crosses a threshold, new requests get a 503 response. The library's parameters are chosen in production so the theoretical collision chance between two unrelated customers is about 1 / 2^52. The rejection threshold is also set well above what healthy customer traffic would reach, so even collided counters are unlikely to trigger a false positive.

The pingora-limits crate is now available on GitHub, along with its core functionality and the benchmark used here.