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

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

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.