BetrFS: A Right-Optimized Write-Optimized File System

0x00 引言

BetrFS是一个以TokuDB为基础的文件系统。它有以下的几个特点：1. 基于写优化的数据结构Bε-tree；2. 将文件系统的操作转化为TokuDB的Key/Value操作；3. 自身不能算是一个完整的操作系统，空闲空间管理等其实还是要利用ext4文件系统，也就是BetrFS其实是一个构建在ext4文件系统上面的文件系统，

On one microdata benchmark, BetrFS provides more than 4× the performance of ext4 or XFS. BetrFS is an ongoing prototype effort, and requires ad- ditional data-structure tuning to match current general-purpose file systems on some operations such as deletes, directory renames, and large sequential writes. Nonetheless, many applications realize significant performance improvements. For instance, an in-place rsync of the Linux kernel source realizes roughly 1.6–22× speedup over other commodity file systems.

0x01 基本思路

BetrFS的实现和一些利用Level-DB之类的Key/Value系统实现的文件系统的思路是基本一致的。

元数据和数据索引

BetrFS使用两个索引来保存文件系统的元数据和数据，

• 元数据索引，使用path → (size, owner, timestamps, etc . . .)这样的形式。与一般的文件系统不同，BetrFS使用的是完整的路径来作为Key，相关的信息作为Value保到一个基于Bε-tree的Key/Value Store中。
• 数据索引，使用(path, block-number) → data[4096]这样的形式。对于稀疏问题，BetrFS就是之间忽略这个部分的Key/Value Pair。

文件系统操作实现

由于BetrFS是以Key/Value Store为基础的，首先要做的就是讲文件系统的操作转化为Key/Value Store上面的操作，

上面这个表还是很直观的。这样做对于大部分的操作都是很简单而且是效率很高的。一个要处理的问题就是重命名文件夹的问题，重命名一个文件需要对这个文件下面的所有的文件、文件夹以及更低层次的文件文件夹都需要重新处理。在这篇Paper中，也就是BetrFS 0.1的时候，它使用的方法就是重新插入一个重命名之后的记录，然后在删除之前的记录。这种方式的缺点是很明显的。如果是一个比较大的文件夹，那么这个工作的工作量是非常大的。BetrFS后面的版本中针对这个问题做了不少的优化，发表在后面的Paper中。另外的几个设计：

• Crash一致性，使用事务的方式实现Crash一致性，和常见的一些也是基于日志的方式，

  TokuDB transactions are equivalent to full data journaling, with all data and metadata updates logged to a file in the underlying ext4 file system. Log entries are retired in-order, and no updates are applied to the tree on disk ahead of the TokuDB logging mechanism. 
  

• 压缩，使用完整路径作为Key的时候，其实有很多的数据都是系统，这个时候使用压缩能得到很好的效果，

  Both indexes use full paths as keys, which can be long and repetitive, but TokuDB’s compression mitigates these overheads. Using quicklz, the sorted path names in our experiments compress by a factor of 20, making the disk-space overhead manageable.
  

0x02 写入优化

BetrFS为了优化的几个设计：

• 在Linux中，一般的写入操作会经过Page Cache，多次对同一个位置的写入可以被合并为一个，在一段时间之后才会同步到磁盘上面，这个对提高性能很有好处。但是在BetrFS中，它是更改了Page Cahe的缓存之后，直接就是去更改磁盘上面的内容，因为Bε-tree的写入性能比较优秀。这个方法可以避免大部分情况下的Page Cahe和磁盘上面的数据不一致。但在大量小的写的情况下，性能是有下降的。

• 有些和BetrFS一样基于Key/Value Store的文件系统利用FUSE来在用户空间实现，而BetrFS则直接实现在Kernel中，这个可以避免很多额外的开销；

• BetrFS中还依赖于ext文件系统实现其它的一些如空闲空间管理的功能，

  TokuDB relies on an underlying file system to act as a block and free space manager for the disk. Conventional file systems do a good job of stor- ing blocks of large files adjacently on disk, especially when writes to the file are performed in large chunks.
  

0x03 评估

具体内容可以参看[1]

Optimizing Every Operation in a Write-optimized File System

0x10 引言

这篇Paper讲的是BetrFS 0.2上面的一些优化，主要讲了它使用的3种技术：late-binding journaling, zon-ing, 和 range deletion。这里的总结也只是看看这3种优化的技术

BetrFS 0.2 performs directory scans 2.2× faster, and small random writes over two orders of magnitude faster, than the fastest conventional file system. But unlike BetrFS 0.1, it renames and deletes files commensurate with conventional file systems and performs large sequential I/O at nearly disk bandwidth.

0x11 3种技术

• Avoiding Duplicate Writes，与此相关的技术就是late-binding journaling。目的就是处理之前在写入文件的时候写入日志一次，写入正式的结构中至少一次导致的写入多次的问题。BetrFS这里的基本方式就是 redirect-on-write(ROW)技术。对于如何在BetrFS中具体实现这个，Paper中有比较详细的描述；

• 查找和重命名之间的平衡，需要这个优化的原因就是提高的BetrFS中重命名文件夹可能的很高的成本。这里的基本思路就是讲索引结构分区。基本的思路如下面的图所示。这样做的一个出发点就是可以将一个zone作为一个整体移动。但是在一些情况下还是需要和之前一样的操作，

  for example, renaming “/local/bin” to “/docs/tools” requires 
  (1) deleting all the keys of the form (0, “/local/bin/p”) in the metadata index, 
  (2) reinserting them as keys of the form (1, “/tools/p”), 
  (3) deleting all keys of the form (0, “/local/bin/p”, i) from the data index, and 
  (4) reinserting them as keys of the form (1, “/tools/p”, i).
  

• 有效的区间删除；基本思路优点lazy的意思。通过在Bε-tree提交一种rangecast信息记录了删除区间的信息，在处理的时候。在处理的时候一步步传播下去。在查询的时候要特别去处理这类型的消息

0x12 评估

具体信息可以参看[2].

The Full Path to Full-Path Indexing

0x20 引言

这个是第3篇描述BetrFS中一些优化手段的Paper，这里主要讲的如果优化BetrFS的完整路径的索引，一个很重要的部分还是重命名操作的优化，

This new version, BetrFS 0.4, performs recursive greps 1.5x faster and ran- dom writes 1.2x faster than BetrFS 0.3, but renames are competitive with indirection-based file systems for a range of sizes. 

0x21 两种优化方式

• Tree Surgery主要的优化目标还是大量文件重命名时候的问题。使用的方法是重命名的时候直接去修改树的结构，而不是使用插入新的在去删除的方式。基本的步骤如下：1. 找到新旧路径的最小公共祖先结点; 2. 将需要移动的部分分离出来，如下面的图所示；3. 将分离出来的部分移植到改动之后的路径上面；4. 对改动之后的树结构进行修复。当然实际的操作的实现还是很复杂的，可以参看论文[3];

• Batched Key Updates，这里主要基于这样一个观察，由于使用完整的路径作为key，这样其实有很多的数据是多余的(相同的)。对于一段路径，找到它们相同的前缀，把这个前缀的信息保存在它们的父结点中，而它们则是需要保存剩余的部分即可，

  Consider the prefix encoding for a sequence of strings. In this compression method, if two strings share a substantial longest common prefix (lcp), then that lcp is only stored once. We apply this idea to Bε-trees. The lcp of all keys in a subtree is removed from the keys and stored in the subtree’s parent node. We call this approach key lifting or simply lifting for short.
  

0x22 评估

具体可以参看[3].

参考

1. BetrFS: A Right-Optimized Write-Optimized File System, FAST ‘15.
2. Optimizing Every Operation in a Write-Optimized File System, FAST ‘16.
3. The Full Path to Full-Path Indexing, FAST’18.