新闻

实验室一篇论文被PPoPP’23接收,提出GPU并发索引数据结构,实现单卡每秒超过二十亿的并发请求处理,服务质量提升7X

发布时间:2022-11-11浏览次数:42

28ACM并行程序设计原理与实践会议”(PPoPP: ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming)将于2023225-31日在加拿大蒙特利尔召开。PPoPPCCFA类会议,并行领域最顶级的国际会议之一,包括理论基础、技术、语言、编译器、运行时系统、工具和实践经验。

本次PPoPP 会议共收到131篇投稿,接受31接受率为23.6%。在本次会议中,并行处理研究所(PPI)的一篇论文被录用。这是继20172019年后,实验室在并发索引结构领域第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并发控制框架(如图3所示),简称Eirene,以减少冲突检测和解决的开销并保证并发请求可线性化。Eirene 框架使用 Combining-based 同步方法来组合和执行请求,以消除键冲突并保证线性化。该方法结合具有相同键的请求,构建它们的依赖关系以决定后续执行的请求,并确定其返回值。每个相同键的请求只有一个会被执行,从而完全消除键冲突。此后,Eirene采用乐观的STM策略来减少结构冲突。查询和更新请求被分发到不同的GPU内核。对于更新内核,只在请求重试次数达到阈值时才会触发STM保护。最后,Eirene执行局部性感知的Warp重组优化方法,以改善GPU内存行为,并通过利用请求之间的局部性来进一步减少冲突。实验评估表明,Eirene 能达到每秒24亿的并发读写吞吐量,并能保证并发请求之间的可线性化。与最先进的并发GPU B+(发表于PPoPP’19)相比,Eirene实现了7倍的吞吐量提升,并将响应时间波动从36%降低到5%


该工作是PPI  Eunomia[PPoPP17] Harmonia[PPoPP19] 之后,在并发索引结构加速方向的又一领先性成果。