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)针对多核数据库和分布式数据库，提出了一种高效的并行索引数据结构。项目的所有三个部分都将原型化并部署在硬件/软件测试平台中。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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

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

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

Mainlining databases: supporting fast transactional workloads on universal columnar data file formats

主线数据库：支持通用列式数据文件格式的快速事务工作负载

• DOI: 10.14778/3436905.3436913
• 发表时间: 2020
• 期刊: Proceedings of the VLDB Endowment
• 影响因子: 2.5
• 作者: Li, Tianyu;Butrovich, Matthew;Ngom, Amadou;Lim, Wan Shen;McKinney, Wes;Pavlo, Andrew
• 通讯作者: Pavlo, Andrew