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

CSR：媒介：协作研究：FTFS：读/写优化的分形树文件系统

• 批准号: 1408782
• 负责人: Martin Farach-Colton
• 金额: $ 24万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-10-01 至 2017-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1408782&HistoricalAwards=false
• 关键词: CSR; Medium; Collaborative; Research; FTFS

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.

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