CSR: Medium: Collaborative Research: FTFS: A Read/Write-Optimized Fractal Tree File System

现代的通用文件系统在微数据操作(如文件创建和销毁、对大文件的小写操作以及元数据更新)上性能较差，但这些操作在当今的计算机系统上非常普遍。这个问题的根本原因是用于在磁盘上组织数据的数据结构的基本限制。这个项目将探索最近发现的一类数据结构的实际效果，称为写-读优化(WRO)数据结构，这种结构有可能在不牺牲其他类型操作的良好性能的情况下显著提高微数据性能。该项目将汇集来自理论和系统的专家团队，他们可以将尖端的算法进步带入操作系统(OS)设计中。为此，该团队将为Linux构建一个通用文件系统，称为FTFS，它使用WRO数据结构。这种性质的工作可能会消除当前磁盘数据局部性和小写性能之间的权衡。该项目观察到，WRO数据结构，如B^epsilon树和分形树索引，可以为查询和批量更新提供与B树类似的渐近行为，并支持性能接近日志记录的小更新。初步工作表明，这些渐近的好处转化为真正的性能改进--对于某些操作，比传统的B-树快两个数量级。现代操作系统对如何设计文件系统有一定的假设，例如在更新操作期间引入额外的查找(称为加密读取)。加密读取会导致更新操作在查找时阻塞，从而抑制WRO数据结构提供的更快更新。该项目将调查操作系统对WRO数据结构的支持，以及重新设计WRO数据结构以支持功能齐全的文件系统的操作。最终目标是技术转让和实际采用。这一努力将推动文件系统和操作系统设计的最新水平。计算机是我们社会的基本组成部分，台式机和笔记本电脑渗透到学校和工作场所，个人携带至少一台移动设备，科学家们用超级计算机推动新的发现。文件系统是这些计算平台的主干，提高通用文件系统的效率可以提高我们国家网络基础设施的效率，并重新为适应快速发展的设备所需的存储堆栈带来灵活性。

Modern, general-purpose file systems offer poor performance on microdata operations, such as file creation and destruction, small writes to large files, and metadata updates, yet these operations are pervasive on today's computer systems. Underlying this problem are fundamental limitations of the data structures used to organize data on disk. This project will explore the practical efficacy of a recently-discovered category of data structures, called write-read-optimized (WRO) data structures, which have the potential to improve microdata performance dramatically without sacrificing good performance on other types of operations. This project will bring together a team of experts from theory and systems who can bring cutting-edge algorithmic advances into operating system (OS) designs. To this end, the team will build a general-purpose file system for Linux, called FTFS, that uses WRO data structures.Work of this nature has the potential to eliminate the current trade-off between data locality on disk and small-write performance. This project observes that WRO data structures, such as B^epsilon trees and fractal tree indexes, can give comparable asymptotic behavior to a B-tree for queries and bulk updates, as well as support small updates with performance close to logging. Preliminary work demonstrates that these asymptotic benefits translate to real performance improvements - up to two orders of magnitude faster than a traditional B-tree for some operations. Modern operating systems have certain assumptions about how file systems are designed, such as inducing extra lookups during update operations (called cryptoreads). Cryptoreads cause update operations to block on lookups, thus throttling the faster updates that WRO data structures provide. The project will investigate OS support for WRO data structures, as well as redesigning WRO data structures to support the operations of a fully-featured file system.The ultimate goal is technology transfer and practical adoption. The effort will advance the current state of the art in file system and operating system design. Computers are a fundamental part of our society, with desktops and laptops permeating schools and workplaces, individuals carrying at least one mobile device, and scientists driving new discovery with supercomputers. File systems are the backbone of these computing platforms, and improvements to the efficiency of a general-purpose file system can improve the efficiency of our national cyber-infrastructure, as well as reintroduce flexibility into the storage stack needed to adapt to rapidly evolving devices.