III: Small: Rethinking the Data Organization and Lifecycle in LSM Storage Systems

III：小：重新思考 LSM 存储系统中的数据组织和生命周期

基本信息

批准号：
2227669
负责人：
Evangelos Christidis
金额：
$ 60万
依托单位：
University of California-Riverside
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2023
资助国家：
美国
起止时间：
2023-01-01 至 2025-12-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2227669&HistoricalAwards=false
关键词：
III Small Rethinking Data Organization

项目摘要

To support the efficient storing of large amounts of data, many modern database systems use the Log Structured Merge tree (LSM) technology. This technology allows grouping many data updates together, before applying them to the database. This project has identified several limitations of LSM storage, which cause reduced rates of reads and writes to the database system. Specifically, current LSM systems do not consider the hotness of a data record when deciding how to store it, and may also suffer from periodic stalls, where the system may become unresponsive while large maintenance operations, called merges, are performed. Further, LSM systems are inefficient at exploiting larger computer memories. The developed techniques create novel data organization and flow patterns in the LSM storage, which leverage modern hardware capabilities to boost the read and write capabilities of the storage system. Improving the performance of database systems will allow storing larger data at lower costs, thus making storage systems more accessible to scientists and general users. This project will also strengthen and extend the ongoing undergraduate research and high school outreach activities of the investigators. The project has several research aims. First, algorithms will be developed to store frequently accessed records in more accessible locations for faster retrieval. This will facilitate a bi-directional LSM tree architecture, where records flow both top-down and bottom-up. This will allow naturally maintaining hot records together, for faster querying and more effective caching. Second, new algorithms will be created to improve the speed of data merges. Periodic merges are used to maintain the stored data organized and consistent. This aim will study how to universally partition LSM runs to facilitate splitting a large merge into multiple disjoint sub-merges, thus reducing stall periods. The third aim will create algorithms to better utilize large memory sizes and multithreading parallelism, and develop a mixed memory-disk LSM tree. The key idea is that, instead of directly enlarging the MemTable, where recent writes are buffered, some components can be pinned in memory, with a more efficient organization, and enable parallel execution on queries. The project includes theoretical analysis, experimental study and software development. The developed algorithms are tested on real-world data and integrated in real database systems. This integration may increase the impact of the project.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.

为了支持大量数据的高效存储，许多现代数据库系统使用日志结构化合并树（LSM）技术。该技术允许在将许多数据更新应用到数据库之前将它们分组在一起。该项目发现了 LSM 存储的几个限制，这些限制导致数据库系统的读写速率降低。具体来说，当前的 LSM 系统在决定如何存储数据记录时不考虑数据记录的热度，并且还可能遭受周期性停顿，其中系统可能在执行称为合并的大型维护操作时变得无响应。此外，LSM 系统在利用更大的计算机内存方面效率低下。所开发的技术在 LSM 存储中创建了新颖的数据组织和流动模式，利用现代硬件功能来增强存储系统的读写能力。提高数据库系统的性能将允许以更低的成本存储更大的数据，从而使存储系统更容易被科学家和普通用户使用。该项目还将加强和扩展研究人员正在进行的本科研究和高中外展活动。该项目有几个研究目标。首先，将开发算法将经常访问的记录存储在更容易访问的位置，以便更快地检索。这将促进双向 LSM 树架构，其中记录自上而下和自下而上流动。这将允许自然地将热记录维护在一起，以实现更快的查询和更有效的缓存。其次，将创建新的算法来提高数据合并的速度。定期合并用于维护存储的数据的组织和一致性。该目标将研究如何普遍分区 LSM 运行，以便于将大型合并拆分为多个不相交的子合并，从而减少停顿期。第三个目标是创建算法以更好地利用大内存大小和多线程并行性，并开发混合内存磁盘 LSM 树。关键思想是，不是直接扩大 MemTable（缓冲最近的写入），而是可以将一些组件固定在内存中，以更有效的组织，并启用查询的并行执行。该项目包括理论分析、实验研究和软件开发。开发的算法在真实世界的数据上进行测试，并集成到真实的数据库系统中。这种整合可能会增加该项目的影响。该奖项反映了 NSF 的法定使命，并且通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。