近日，SIGCOMM 2023论文录取结果公布，由华为云计算与网络创新lab与北京大学杨仝老师团队共同发表的论文《P4LRU: Towards An LRU Cache Entirely in Programmable Data Plane》被大会主会正式录用。

SIGCOMM(Special Interest Group on Data Communication)是美国计算机协会ACM组织的旗舰型会议，也是计算机网络系统领域历史最为悠久、最为权威的学术会议，这也充分说明华为云在高性能可编程网络领域的探索得到了业界专家的一致认可。

网络测量通过监控、采集网络相关数据，对网络运行状态进行分析建模、控制调整，是网络调优、运维，规划的基础，一直是华为云网络重点探索的领域。随着华为云规模快速增长，高速网络下的全流级精细化面临挑战，高性能可编程交换机高效的数据处理能力与灵活的编程能力为高速网络数据流测量提供了支撑。

然而高性能处理能力也伴随着极其苛刻的数据面缓存资源（约100Mb）限制，如何基于可编程数据面有限的资源实现高性能测量，则需要极致的性能优化和技术探索，这篇论文所讨论的面向可编程数据面的LRU缓存替换机制设计与实现便是在可编程数据面的一次极致探索。

问题背景

数据面缓存是网络设备，如可编程交换机、智能网卡、DPU等的重要功能。LRU(Least Recently Used)机制是一种较优的缓存替换策略，但是传统LRU实现需要至少两次访存，在pipeline架构需要通过端口环回方式实现，浪费资源和性能。

因此，本论文分析了为何多种典型的LRU实现无法在当前的可编程数据面部署，并提出了P4LRU，一种专门为pipeline模型设计的精简高效的LRU实现方案。

核心创新点1

key和value分离，通过状态机维护逻辑映射关系。传统方案的两次访存就是因为key与value是一起的，第一次查找key确定更新对象；第二次访存去调整队列顺序。

但是实际上，key的顺序我们在比较的查找过程中就可以进行调整，比如最新到达的数据一定是最热的数据，可以直接放在队列头部，然后依次与队列里所有key比较，如果比匹配，则key依次后移，此操作在pipeline里是天然支持的。此时，难点就还剩value的位置如何调整和key匹配，如果调整，就会涉及到二次访存或者说stage回退。

最直接的思路就是，value的物理内存不变，只改变逻辑位置映射状态，即本论文第一个创新点，以 LRU 的机制维护 key 列表，不改变value的物理存储位置，通过一个 cache state 寄存器维护 key 和 value 的映射关系，每一次key的调整，对应更新逻辑映射，就可以保证任何时候通过key都可以正确的找到value位置。

核心创新点2

状态转换操作编码为整数运算。在key和value采用逻辑映射后，修改逻辑映射就变成了关键的技术点。论文中通过详细数学推导论证这种逻辑状态转换可以抽象为置换群算法，但是在可编程数据面实现如此复杂的数据结构和计算几乎是不可能。

因此，提出了本论文的另一个创新点：化繁为简，通过将有限状态编码为整数，然后将状态转换总结为整数的逻辑运算，从而可以在数据面实现高效的映射状态维护。

此外，论文还设计了基于P4LRU的几个典型的应用系统，例如快路径查表系统LruTable、数据库缓存加速系统LruIndex和高性能测量系统LruMon。这些系统利用P4LRU实现了更高效的数据平面缓存，并通过大量实验验证了P4LRU缓存在性能和可扩展性方面的优势。

小结与展望

论文所述工作已经在华为云FlowScope高性能测量平台中落地，单tofino设备测量吞吐提升超50%。FlowScope是华为云网络高性能可编程测量平台，提供业务级流量精准画像，统计精度超99%，支撑网络分层买卖精准账单、流量精细化调度、异常流识别等场景，持续提升华为云广域网在成本、性能和可靠性方面竞争力。此外，我们在华为云搭建了网流测量实验平台，该平台将作为网络测量技术创新黑土地，吸引更多优秀的合作伙伴，产出优秀的创新成果。

关于华为云计算与网络创新lab：https://www.huaweicloud.com/lab/cnl/home.html

关注@华为云，了解更多资讯