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

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

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.