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

现代的通用文件系统在微数据操作（例如文件创建和销毁、对大文件的小写入以及元数据更新）上提供较差的性能，然而这些操作在当今的计算机系统上是普遍存在的。 这个问题的根本原因是用于在磁盘上组织数据的数据结构的基本限制。 该项目将探索最近发现的一类数据结构的实际功效，称为写-读-优化（WRO）数据结构，它有可能显着提高微数据性能，而不会牺牲其他类型操作的良好性能。 该项目将汇集来自理论和系统的专家团队，他们可以将尖端的算法进步带入操作系统（OS）设计。 为此，该团队将构建一个用于Linux的通用文件系统，称为FTFS，它使用WRO数据结构。这种性质的工作有可能消除当前在磁盘上的数据局部性和小写入性能之间的权衡。 该项目观察到，WRO数据结构，如B^树和分形树索引，可以为查询和批量更新提供与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.