SPX: Collaborative Research: Distributed Database Management with Logical Leases and Hardware Transactional Memory

SPX：协作研究：具有逻辑租赁和硬件事务内存的分布式数据库管理

• 批准号: 1822933
• 负责人: Andrew Pavlo
• 金额: $ 50万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1822933&HistoricalAwards=false
• 关键词: SPX; Collaborative; Research; Distributed; Database

Database systems are the foundation of critical applications that maintain large amounts of data. Since single-processor performance plateaued a decade ago, increasing the number of processors or servers has become the only viable way of improving performance in distributed database management systems. Scalability is a daunting challenge in these systems due to the complex coordination among the large number of parallel tasks---a problem that this project seeks to solve. Most existing database systems determine the order among parallel tasks using conventional physical time. These systems require managing distributed locks, which leads to blocking and computation overhead. Other systems use logical time, which can be thought of as position in an order, to eliminate locking, but require centralized generation of the ordering, which is a serious scalability bottleneck as core count increases. This project breaks the abstraction of physical time and replaces it with a new definition of time that incorporates both logical and physical aspects. "Physiological" time, termed physiological time for ease of pronunciation, uses logical timestamps to order events and then breaks ties using physical time. This enables novel dependency-avoiding approaches to improving system performance and scalability. This project applies physiological time to three components in a distributed database system. (1) At hardware level, a new hardware transaction memory (HTM) mechanism will be built, which allows more effective data movement in multi-core processors' caches. (2) A new distributed concurrency control protocol will be designed and implemented to coordinate large numbers of parallel tasks in a distributed database. (3) An efficient parallel indexing data structure will be proposed for both multi-core and distributed databases. All three parts of the project will be prototyped and deployed in hardware/software testbeds.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

数据库系统是维护大量数据的关键应用程序的基础。由于单个处理器的性能在十年前稳定下来，因此增加处理器或服务器的数量已成为改善分布式数据库管理系统中性能的唯一可行方法。由于大量平行任务之间的复杂协调，该系统的协调性是该项目寻求解决的问题，因此可伸缩性是一个艰巨的挑战。大多数现有的数据库系统使用常规物理时间确定并行任务之间的顺序。这些系统需要管理分布式锁，这会导致阻塞和计算开销。其他系统使用逻辑时间，可以将其视为订单中的位置，以消除锁定，但需要集中的订单生成，这是一个严重的可扩展性瓶颈，因为核心计数的增加。该项目打破了物理时间的抽象，并用包含逻辑和物理方面的时间的新定义取代了它。 “生理”时间称为生理时间，以便于发音，使用逻辑时间戳来订购事件，然后使用物理时间打破联系。这使新的避免依赖性的方法可以改善系统性能和可伸缩性。该项目将生理时间应用于分布式数据库系统中的三个组件。 （1）在硬件级别上，将建立一种新的硬件交易存储器（HTM）机制，从而可以在多核处理器的库中更有效的数据移动。 （2）将设计和实施一个新的分布式并发控制协议，以协调分布式数据库中的大量并行任务。 （3）将为多核和分布式数据库提出有效的并行索引数据结构。该项目的所有三个部分将进行原型化和部署在硬件/软件测试床上。该奖项反映了NSF的法定任务，并使用基金会的知识分子优点和更广泛的影响审查标准，被认为值得通过评估来获得支持。

项目成果

Filter Representation in Vectorized Query Execution

• DOI: 10.1145/3465998.3466009
• 发表时间: 2021-06
• 期刊: Proceedings of the 17th International Workshop on Data Management on New Hardware
• 作者: Amadou Latyr Ngom;Prashanth Menon;Matthew Butrovich;Lin Ma;Wan Shen Lim;T. Mowry;Andrew Pavlo

Everything is a Transaction: Unifying Logical Concurrency Control and Physical Data Structure Maintenance in Database Management Systems

• 发表时间: 2021
• 作者: Ling Zhang;Matthew Butrovich;Tianyu Li;Yash Nannapanei;Andrew Pavlo;J. Rollinson;Huanchen Zhang;Ambarish Balakumar;Daniel Biales;Ziqi Dong;Emmanuel Eppinger;Jordi Gonzàlez;Wan Shen Lim;Jianqiao Liu;Prashanth Menon;Soumil Mukherjee;Tanuj Nayak;Amadou Latyr Ngom;Jeff Niu;D. Patra;P. Raj;Stephanie Wang;Wuwen Wang;Yao-Tin Yu;William Zhang

Make Your Database System Dream of Electric Sheep: Towards Self-Driving Operation

• DOI: 10.14778/3476311.3476411
• 发表时间: 2021-07
• 期刊: Proc. VLDB Endow.
• 作者: Andrew Pavlo;Matthew Butrovich;Lin Ma;Prashanth Menon;Wan Shen Lim;Dana Van Aken;William Zhang

On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes

• DOI: 10.14778/3364324.3364334
• 发表时间: 2019-10
• 期刊: Proc. VLDB Endow.
• 作者: Yihan Sun;G. Blelloch;Wan Shen Lim;Andrew Pavlo

Litmus: Towards a Practical Database Management System with Verifiable ACID Properties and Transaction Correctness

• DOI: 10.1145/3514221.3517851
• 发表时间: 2022-06
• 期刊: Proceedings of the 2022 International Conference on Management of Data
• 作者: Yu Xia;Xiangyao Yu;Matthew Butrovich;Andrew Pavlo;S. Devadas