Cloudflare Saves 100TB of RAM by Optimizing Consistent Hashing in Pingora

Cloudflare's Performance team resolved excessive memory usage issues in the pingora-ketama library used by the Pingora Backend Router (PBR), recovering over 100TB of RAM across its global infrastructure. This demonstrates the massive impact that algorithmic fine-tuning can have on large-scale distributed systems.

Memory Inefficiency in Consistent Hashing

PBR uses consistent hashing to route cacheable requests based on URL. The previous approach generated multiple hashes per server to reduce distribution imbalance, but this caused significant memory overhead. In particular, when servers had feature-specific limits, hashes could not be added to the existing ring, creating a structural limitation that required generating new hash rings for each feature combination.

Rust-Based Structural Optimization and Hash Count Reduction

To eliminate padding caused by Rust's memory alignment rules, the team adopted an approach using raw byte arrays and getters instead of #[repr(packed)], reducing hashing memory usage by 25%.

Additionally, by analyzing the Birthday Paradox collision probability for 32-bit hashes and simulation results, they decided to reduce the number of hashes per server by 90%. Testing at a scale of 2,048 servers with hash counts ranging from 10,000 to 100,000 confirmed that reducing the number of hashes did not lead to unpredictable errors in request distribution.

Safe Migration and Introduction of v2 Ring

To prevent global cache invalidation, a migration strategy was established to maintain both the old (Ketama) and new (compact) rings simultaneously in PBR memory. Through a framework allowing ring version selection per request, a gradual rollout was conducted at the data center level, eventually removing the old ring.

The pingora-ketama v2 developed through this process applies a compressed storage format and a fast sorting algorithm, and is currently provided as an unadvertised cargo feature. Running v1 and v2 rings simultaneously ensures stability while achieving performance improvements.