Blogs›Cloudflare›Rate Limiting and Event Counting
Cloudflare is developing Pingora, an in-house proxy, and its associated libraries. The pingora-limits library provides efficient mechanisms for counting inflight events and estimating event rates over time. This is crucial for protecting infrastructure from malicious or misbehaving requests. The library utilizes Count-Min Sketch (CM sketch) for space-efficient and lock-free event counting, offering significant performance and memory advantages over traditional hash table approaches, especially at scale.
5/12/2023
Introduced pingora-limits, a library for counting inflight events and estimating event rates. Implemented Count-Min Sketch (CM sketch) as the core algorithm, providing O(1) time complexity per event and O(log(n)) space complexity, with lock-free operations. Benchmarked pingora-limits against naive and optimized hash table approaches, demonstrating significant speed and memory improvements, particularly in multi-threaded scenarios.