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

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

• 批准号: 1755615
• 负责人: Michael Bender
• 金额: $ 5.08万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1755615&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）设计。 为此，团队将为使用WRO数据结构的Linux构建一个通用文件系统。该性质的工作有可能消除磁盘和小写入性能的数据位置之间的当前权衡。 该项目观察到，WRO数据结构（例如B^epsilon树和分形树索引）可以为查询和批量更新提供可比的渐近行为，并支持较小的更新，并且具有近距离记录的性能。 初步工作表明，这些渐近益处转化为实际的绩效改进 - 比传统的B -Tree快两个数量级。 现代操作系统对文件系统的设计方式有一定的假设，例如在更新操作期间引起额外的查找（称为Cryptoreads）。 Cryptoreads会导致更新操作阻止查找，从而限制WRO数据结构提供的更快更新。该项目将调查对WRO数据结构的OS支持，并重新设计WRO数据结构，以支持功能齐全的文件系统的操作。最终目标是技术传输和实际采用。这项工作将推动文件系统和操作系统设计中的当前状态。 计算机是我们社会的基本组成部分，台式机和笔记本电脑渗透到学校和工作场所，携带至少一个移动设备的个人以及使用超级计算机进行新发现的科学家。文件系统是这些计算平台的骨干，提高通用文件系统的效率可以提高我们国家网络基础架构的效率，并将灵活性重新引入储存堆栈，以适应快速发展的设备。