1. A good day to trie-hard: saving compute 1% at a time (blog.cloudflare.com)
摘要:
本文介绍了Cloudflare如何通过优化一个简单的Rust函数来减少其CDN服务的CPU使用量。该服务(pingora-origin)每秒处理高达3500万个请求,其中一个名为clear_internal_headers的函数用于在请求离开Cloudflare前移除内部头部信息,此函数消耗了约1.7%的总CPU时间,相当于680个持续工作的CPU核心。
优化过程:
- 初步优化 - 反转查找逻辑:原代码遍历一个庞大的内部头列表并逐一检查请求头。优化后改为遍历请求头并检查其是否存在于内部头集合中。由于平均请求头数量远少于内部头数量,此变更将函数平均执行时间从3.65微秒降至1.53微秒,速度提升2.39倍,但预计仅节省约1%的CPU。
- 数据结构探索:为寻找更优的查找结构,团队评估了多种方案:
- 哈希表(HashMap):已采用,但其查找时间复杂度与键长(O(L))相关。
- 排序集合(如FST):比哈希表略慢。
- 状态机(如正则表达式):在识别不匹配(miss)时非常快,符合此场景(绝大多数请求头非内部头),但基准测试中仍比哈希表方案慢一倍。
- 最终方案 - Trie(字典树):Trie结构在查找不匹配字符串时非常高效(O(log(L))),但现有开源实现未针对超高性能路径优化。因此,团队开发并开源了名为**
trie-hard**的Rust库。 trie-hard的优化:该库通过将节点关系存储在无符号整数的位中,并将整个树保存在连续内存块中来实现极致速度。基准测试显示,使用trie-hard后,函数平均耗时降至0.93微秒。
成果:
- 经生产环境验证,使用
trie-hard后,clear_internal_headers函数的CPU使用率从1.71%降至0.34%,节省了1.28%的总CPU计算资源。 - 所有基准测试预测与生产环境通过堆栈跟踪采样获得的实际性能数据高度吻合。
核心结论:
作者强调,精确的性能监测和定位慢代码比具体的优化技巧更为重要。即使是对微秒级函数的优化,在海量请求下也能产生显著的整体效益。文章凸显了可观测性工具(如火焰图、性能剖析)在驱动系统级优化中的关键作用。trie-hard库已作为开源项目发布。