The Cloudflare Blog
·
Pingora 如何进行计数
💡
原文英文，约1800词，阅读约需7分钟。
📝
内容提要
Pingora-limits是一个采用CM Sketch算法的高效计数事件的库，可以快速计数且不使用锁。与哈希表相比，Pingora-limits在空间利用率和性能方面都有所提升。该库在pingora的连接限制功能中得到了应用，可以有效地保护服务器和基础设施免受过载的影响。Pingora将继续开源其组件和库，分享代码背后的思想。
🎯
关键要点
- Pingora-limits是一个高效计数事件的库，采用CM Sketch算法，快速计数且不使用锁。
- 与哈希表相比，Pingora-limits在空间利用率和性能方面有所提升。
- 该库用于pingora的连接限制功能，有效保护服务器免受过载影响。
- Pingora-limits能够计数流入事件并估计事件的发生率，保护基础设施和服务。
- CM Sketch算法在每个事件的时间复杂度为O(1)，空间复杂度为O(log(n))。
- CM Sketch通过独立的哈希函数和计数器矩阵来估计事件计数。
- Pingora-limits在单线程和多线程情况下的性能优于传统哈希表方法。
- 在内存消耗方面，Pingora-limits显著低于传统哈希表实现。
- Pingora-limits可以作为第一阶段过滤器，帮助准确计数高频事件。
- 在生产环境中，Pingora-limits用于连接限制功能，防止服务器过载。
- Pingora-limits库现已在GitHub上开源，继续分享代码和背后的思想。
🏷️
标签
➡️
