我在做 DPDK 开发时很第一次写forwarding程序时总有一种错觉“逻辑已经很简单了性能应该不会差。”收包查 flow转发整个流程看起来非常直接。但我曾经遇到过一个非常诡异的问题程序不开 flow table只做 L2 forwarding性能35 Mpps然而一旦开启session lookup性能瞬间掉到12 Mpps第一次遇到时我怀疑过hash 算法lock 竞争NUMAfalse sharingPCIe最后才发现真正的问题竟然是cache locality。而这个问题也让我真正理解了现代 CPU 中“数据在哪里”往往比“代码怎么写”更重要。一、问题现场程序结构RX收包。flow lookup查 session。TX发包。flow table使用rte_hash实现。理论上查表复杂度O(1)看起来应该非常快。二、为什么现实完全不同开启 lookup 后性能直接下降60%而且随着 flow 数增加性能还在继续下降。三、第一反应是不是 hash 冲突因为lookup本质hash table。于是检查bucket collisionhash qualityload factor结果都正常。四、第二反应是不是锁竞争因为flow table 是共享的。于是检查spinlockCAS retryatomic contention结果依然不明显。五、真正关键的一步perf top后来执行perf top发现大量时间消耗在memory access以及LLC miss这里终于意识到问题不是“计算”。而是cache miss。六、什么是 cache locality即数据是否“局部连续”。CPU最喜欢连续访问最讨厌随机访问七、为什么随机访问这么昂贵因为CPU cache 按cache line加载。通常64 bytes如果访问连续数据。一次 cache load后续很多数据都能命中。八、但 flow lookup 完全不同flow table本质大量随机 key。例如5 tuplehash 后entry可能位于内存任意位置。九、于是发生什么每次 packet都可能跳到完全不同的 memory address导致cache line missLLC missDRAM accessCPU开始疯狂等待内存。十、为什么 CPU usage 不高因为CPU并不是“忙”。而是stall。即等待内存返回。十一、真正的问题working set 超过 cache后来发现LLC30MBflow table几 GB于是cache根本装不下。lookup几乎全部变成DRAM random access十二、为什么 DRAM random access 极其致命现代 CPU运算可能1ns而DRAM access可能100ns差距上百倍。十三、DPDK 为什么特别怕这个问题因为DPDKPPS 极高。例如20 Mpps意味着每秒2000 万次 lookup如果每次都 miss cache。系统会瞬间memory-bound。十四、为什么小 flow table 很快因为小表能装进LLC cache。lookup大部分cache hit。十五、flow 数增加后为什么性能断崖下降因为working set逐渐超出cache capacity。cache hit rate骤降。于是memory latency被彻底暴露。十六、真正经典的问题pointer chasing很多 flow table不仅hash lookup。还会next next-next即链表。这会进一步恶化cache locality。十七、为什么链表在现代 CPU 上很慢因为链表本质随机 memory jump。CPU无法prefetchpipeline optimizesequential access十八、为什么 array 通常更快因为连续内存更符合CPU cache 设计。这也是为什么DPDK 大量使用arrayringfixed objectcontiguous memory十九、真正有效的优化hot/cold split后来重构 flow entry。原来200 bytes里面大量字段根本不常用。于是拆分hot fields频繁访问。cold fields按需访问。二十、优化后发生什么热点数据终于能放进 cache。于是lookup latency大幅下降。二十一、另一个关键优化prefetch后来增加rte_prefetch0()例如rte_prefetch0(flow_entry);提前加载cache line。二十二、为什么 prefetch 很关键因为memory latency无法消除。但可以隐藏。CPU在处理当前 packet 时。提前加载下一个 packet 的 flow entry。二十三、优化效果非常明显优化前指标数值PPS12 MppsLLC miss极高优化后指标数值PPS26 MppsLLC miss大幅下降二十四、为什么“算法复杂度”已经不够了很多人仍然停留在O(1) O(logN)这些概念。但现代 CPU真正重要的是memory behavior。因为O(1)如果每次都 DRAM miss。依然会非常慢。二十五、进一步理解现代 CPU现代 CPU真正昂贵的往往不是addmulbranch而是random memory access。二十六、DPDK 为什么极度强调 cache-friendly现在你会发现DPDK 官方设计几乎都在强调contiguous memorycache alignedprefetchper-core object本质都是提高 cache locality。二十七、工程经验总结做高 PPS 系统一定要关注working setLLC sizememory layoutpointer chasingcache hit rate不要只关注算法复杂度二十八、这次排查真正学到什么以前我以为高性能网络开发核心是locklessSIMDbatch后来才意识到真正限制系统性能的很多时候是cache locality。因为CPU 再快也快不过等待内存。二十九、总结为什么 DPDK 程序一开 flow table 就性能腰斩很多时候不是hash 算法问题锁竞争问题NUMA 问题而是cache locality。通过这次问题我们真正理解了核心概念cache localityLLC missworking setpointer chasingprefetchmemory-bound system这也是高性能网络开发真正进入“CPU cache 时代”的开始真正决定性能的。很多时候不是算法。而是数据布局。
为什么我的 DPDK 程序一开 flow table 就性能腰斩？一次排查让我彻底理解 cache locality
我在做 DPDK 开发时很第一次写forwarding程序时总有一种错觉“逻辑已经很简单了性能应该不会差。”收包查 flow转发整个流程看起来非常直接。但我曾经遇到过一个非常诡异的问题程序不开 flow table只做 L2 forwarding性能35 Mpps然而一旦开启session lookup性能瞬间掉到12 Mpps第一次遇到时我怀疑过hash 算法lock 竞争NUMAfalse sharingPCIe最后才发现真正的问题竟然是cache locality。而这个问题也让我真正理解了现代 CPU 中“数据在哪里”往往比“代码怎么写”更重要。一、问题现场程序结构RX收包。flow lookup查 session。TX发包。flow table使用rte_hash实现。理论上查表复杂度O(1)看起来应该非常快。二、为什么现实完全不同开启 lookup 后性能直接下降60%而且随着 flow 数增加性能还在继续下降。三、第一反应是不是 hash 冲突因为lookup本质hash table。于是检查bucket collisionhash qualityload factor结果都正常。四、第二反应是不是锁竞争因为flow table 是共享的。于是检查spinlockCAS retryatomic contention结果依然不明显。五、真正关键的一步perf top后来执行perf top发现大量时间消耗在memory access以及LLC miss这里终于意识到问题不是“计算”。而是cache miss。六、什么是 cache locality即数据是否“局部连续”。CPU最喜欢连续访问最讨厌随机访问七、为什么随机访问这么昂贵因为CPU cache 按cache line加载。通常64 bytes如果访问连续数据。一次 cache load后续很多数据都能命中。八、但 flow lookup 完全不同flow table本质大量随机 key。例如5 tuplehash 后entry可能位于内存任意位置。九、于是发生什么每次 packet都可能跳到完全不同的 memory address导致cache line missLLC missDRAM accessCPU开始疯狂等待内存。十、为什么 CPU usage 不高因为CPU并不是“忙”。而是stall。即等待内存返回。十一、真正的问题working set 超过 cache后来发现LLC30MBflow table几 GB于是cache根本装不下。lookup几乎全部变成DRAM random access十二、为什么 DRAM random access 极其致命现代 CPU运算可能1ns而DRAM access可能100ns差距上百倍。十三、DPDK 为什么特别怕这个问题因为DPDKPPS 极高。例如20 Mpps意味着每秒2000 万次 lookup如果每次都 miss cache。系统会瞬间memory-bound。十四、为什么小 flow table 很快因为小表能装进LLC cache。lookup大部分cache hit。十五、flow 数增加后为什么性能断崖下降因为working set逐渐超出cache capacity。cache hit rate骤降。于是memory latency被彻底暴露。十六、真正经典的问题pointer chasing很多 flow table不仅hash lookup。还会next next-next即链表。这会进一步恶化cache locality。十七、为什么链表在现代 CPU 上很慢因为链表本质随机 memory jump。CPU无法prefetchpipeline optimizesequential access十八、为什么 array 通常更快因为连续内存更符合CPU cache 设计。这也是为什么DPDK 大量使用arrayringfixed objectcontiguous memory十九、真正有效的优化hot/cold split后来重构 flow entry。原来200 bytes里面大量字段根本不常用。于是拆分hot fields频繁访问。cold fields按需访问。二十、优化后发生什么热点数据终于能放进 cache。于是lookup latency大幅下降。二十一、另一个关键优化prefetch后来增加rte_prefetch0()例如rte_prefetch0(flow_entry);提前加载cache line。二十二、为什么 prefetch 很关键因为memory latency无法消除。但可以隐藏。CPU在处理当前 packet 时。提前加载下一个 packet 的 flow entry。二十三、优化效果非常明显优化前指标数值PPS12 MppsLLC miss极高优化后指标数值PPS26 MppsLLC miss大幅下降二十四、为什么“算法复杂度”已经不够了很多人仍然停留在O(1) O(logN)这些概念。但现代 CPU真正重要的是memory behavior。因为O(1)如果每次都 DRAM miss。依然会非常慢。二十五、进一步理解现代 CPU现代 CPU真正昂贵的往往不是addmulbranch而是random memory access。二十六、DPDK 为什么极度强调 cache-friendly现在你会发现DPDK 官方设计几乎都在强调contiguous memorycache alignedprefetchper-core object本质都是提高 cache locality。二十七、工程经验总结做高 PPS 系统一定要关注working setLLC sizememory layoutpointer chasingcache hit rate不要只关注算法复杂度二十八、这次排查真正学到什么以前我以为高性能网络开发核心是locklessSIMDbatch后来才意识到真正限制系统性能的很多时候是cache locality。因为CPU 再快也快不过等待内存。二十九、总结为什么 DPDK 程序一开 flow table 就性能腰斩很多时候不是hash 算法问题锁竞争问题NUMA 问题而是cache locality。通过这次问题我们真正理解了核心概念cache localityLLC missworking setpointer chasingprefetchmemory-bound system这也是高性能网络开发真正进入“CPU cache 时代”的开始真正决定性能的。很多时候不是算法。而是数据布局。
