本文提出GPU并发索引数据结构，实现单卡每秒超20亿的并发请求处理，服务质量提升7X。
万事平台基础系统软件研究团队一篇论文被PPOPP'23会议接收🧑🏻🔧，该论文针对新型异构硬件架构千/万级线程并发处理过程中同步开销大、服务质量差的问题🦗，提出一种高效🌑、扩展强的并发控制算法，相比传统算法（当前最经典算法，UC Davis大学发表于PPoPP 2019的算法)，性能和服务质量都获得超过7X的提升🏌🏽，并发吞吐率达到每秒24亿。
据了解，PPoPP是CCF的A类会议👩🏭，并行领域最顶级的国际会议之一🕵🏼，包括理论基础、技术🌤、语言、编译器👯♂️、运行时系统、工具和实践经验。第28届“ACM并行程序设计原理与实践会议”（PPoPP: ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming）将于2023年2月25日-3月1日在加拿大蒙特利尔召开。本次PPoPP 会议共收到131篇投稿🙍🏿♀️🌯，接受31篇, 接受率为23.6%。在本次会议中，并行处理研究所(PPI)的一篇论文被录用🤦🏽♂️。这是该研究所继2017、2019年后，实验室在并发索引结构领域第3次在PPoPP上发表论文👨🏼🦰。论文信息如下😏：
Weihua Zhang, Chuanlei Zhao, Lu Peng, Yuzhe Lin, Fengzhe Zhang, Yunping Lu. Boosting Performance and QoS for Concurrent GPU B+trees by Combining-based Synchronization.The 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP’23), Montreal, Canada. 2023.
并发B+树是基础的数据结构，是数据库、文件系统等存储系统最核心的索引结构之一，例如XFS, PostgreSQL。随着数据请求的规模呈指数级增长🤿，系统正面临着巨大的性能压力💅✡️。GPU在加速并发B+树性能方面展现了它的潜力🧔🏼♂️。当大规模并发请求被处理时，请求之间的潜在的冲突需要被检测和解决。先前的方法通过基于锁或基于软件事务存储器（STM）的方法来保证并发GPU B+树的正确性🧖🏻。然而♍️，这些方法使请求处理逻辑复杂化，增加了内存访问量并引发执行路径分叉（如图1所示），从而导致了性能下降和响应时间波动的增加(如图2而所示)。此外，可线性化是保证并发请求处理正确定和公平性的重要原则，然而此前的方法并不提供并发请求之间的线性化☞。
论文提出了一个为GPU B+树设计的Combining-based并发控制框架，简称Eirene👩🏽🦳🕛，以减少冲突检测和解决的开销并保证并发请求可线性化。Eirene 框架使用 Combining-based 同步方法(如图3所示)来组合和执行请求，以消除键冲突并保证线性化🫳🏼。该方法结合具有相同键的请求🫀，构建它们的依赖关系以决定后续执行的请求，并确定其返回值。每个相同键的请求只有一个会被执行，从而完全消除键冲突。此后，Eirene采用乐观的STM策略（如图4所示）来减少结构冲突。查询和更新请求被分发到不同的GPU内核。对于更新内核🥡，只在请求重试次数达到阈值时才会触发STM保护。最后，Eirene执行局部性感知的Warp重组优化方法（如图5所示），以改善GPU内存行为，并通过利用请求之间的局部性来进一步减少冲突👨🏽🎓。实验评估表明🎴🧑🏻🦽➡️，Eirene 能达到每秒24亿的并发读写吞吐量🕵️♀️，并能保证并发请求之间的可线性化。与最先进的并发GPU B+树(发表于PPoPP’19)相比，Eirene实现了7倍的吞吐量提升🙇，并将响应时间波动从36%降低到5%。
