De-indirection for Flash-based SSDs with Nameless Writes
De-indirection for Flash-basedSSDs with Nameless Writes
0、摘要
Abstract
Wepresent Nameless Writes, a new device interface that removes the need forindirection in modern solid-state storage devices (SSDs). Doing so allows the device to control block allocation decisions, thus enabling it toexecute critical tasks such as garbage collection and wear leveling, while removingthe need for large and costly indirection tables. We demonstrate the effectiveness of namelesswrites by porting the Linux ext3 file system to use an emulated nameless-writingdevice and show that doing so both reduces space and time overheads, thusmaking for simpler, less costly, and higher-performance SSD-based storage.
本文提出一个新的设备接口——NamelessWrites，它移除了SSD设备中的间接层。Nameless Writes执行写操作时，在设备端为写操作分配具体的位置，然后设备将此地址反馈给文件系统。这样，由设备来控制块的分配策略，则设备可以执行垃圾回收、磨损均衡等工作，同时移除了不必要的间接表。通过将Linux ext3文件系统移植到一个模拟的nameless-writing设备，证明了namelesswrites减少了时间和空间的开销，提高了系统的性能。
1、现有背景下的问题
Indirection是计算机系统中的核心技术。磁盘驱动中使用到，在固态盘SSD设备中也使用到（FTL提供逻辑地址到物理地址的转换：间接转换）。但是，FTL中的Indirection带来的空间和性能代价也很高。页映射中，1TB的SSD需要2GB的Indirection空间（page:2KB；pointer:32bit）；块映射中，1TB的SSD需要32MB的映射表空间（block：64page）。如今，大多FTL使用混合映射，但代价依旧明显。
Excess indirection四个典型应用：（1）OSvirtual memory running atop a hypervisor；（2）单一disk上的文件系统；（3）RAID阵列上的文件系统；（4）flash上的文件系统（FTL是Excessindirection）。
2、提出的解决方案
本文提出de-indirection[2]的一个特殊实例。在大多数写操作中，将（data，name[3]）传给设备，但本文提出nameless writes，即只将data传给下层设备，设备分配一个底层物理页，向物理页中写入data；同时，设备将此物理页的name（页的物理地址）反馈给上层client（文件系统），client根据这个name，执行后续的读操作。另一方面，由于设备可以控制写操作的地址，故namelesswrites可以方便的进行磨损均衡。
Namelesswrites不同于传统写：第一，namelesswrite不指定地址，这就允许设备选择一个合适的地址，不需要上层主机的控制。第二，设备写完数据之后，返回物理地址和状态给主机，主机保存这个地址用于将来的读操作。
2.1 解决方案详述（section 3）
A. Nameless writes接口
Namelesswrites的接口见Table 1：
Table 1:The Nameless-Writing Device Interfaces The
tablepresents the nameless-writing device interfaces.
| Virtual Read | |
| down | virtual address, length |
| up | status, data |
| Virtual Write | |
| down | virtual address, data, length |
| up | status |
| Nameless (new) Write 代替传统的写操作 | |
| Down (输入参数) | data, length, metadata |
| Up (返回参数) | status, resulting physical address(es) |
| Nameless Overwrite | |
| Down (输入参数) | old physical address(es), data, length, metadata |
| Up (返回参数) | status, resulting physical address(es) |
| Physical Read与传统的读操作相似 | |
| down | physical address, length, metadata |
| up | status, data |
| Free/Trim | |
| down | virtual/physical addr, length, metadata, flag |
| up | status |
| Migration [Callback] | |
| down | old physical addr, new physical addr, metadata |
| up | old physical addr, new physical addr, metadata |
Nameless writes代替传统的写操作，但不输入物理地址，而是将物理地址返回给文件系统。
Nameless overwrites：输入旧的物理地址到设备，并free其数据（与传统free操作相似），然后执行一个NamelessWrite操作。
Physical Read：与传统的读操作相似，但是输入参数增加了一个：metadata。
因为一个namelesswirtes是一个分配操作，nameless-writing设备也需要被通知回收。大多数ssd称此接口为free或trim命令。一旦一个块被释放，该设备是free的可重用。
Migrationcallback：flash执行磨损均衡的时候需要迁移数据，nameless-writingdevice向文件系统返回新的物理地址，文件系统更新相关的metadata指针。
要在典型的文件系统（比如ext3）中实现namelesswrites接口，为了说明，我们检查操作，增加一个新块到现有的文件。首先，文件系统发出一个新增加数据块的nameless write到Nameless-writing Device。写操作完成后，文件系统根据返回的地址，更新内存中的相应节点，故这个指的是块的物理地址。节点更新后，文件系统需要刷回节点到设备中；节点必须使用另一个namelesswrite写到设备。再次，文件系统等待节点的写操作完成，然后更新一些结构（结构包含到节点的引用）。若namelesswrite是设备写操作的唯一接口，则执行上述循环，直到达到rootstructure。
B. 分段地址空间
为了完成上述递归，引进一个分段地址空间（segmentedaddress space），见下图1，分段地址空间分为：虚拟地址空间和物理地址空间。虚拟段共V个块，设备虚拟化这段空间，故它保存一个较小的间接表来映射到虚拟地址空间的访问，以纠正底层的物理位置。对虚拟地址空间的访问与对传统设备的访问一样。用户发送地址和数据到设备，设备返回状态信息给用户。
Namelesssegment是一个物理地址空间，大小为P块。大多数物理块都能在此空间中找到，允许典型的标准的name读；所有到物理地址空间的写都是nameless的，故防止用户到某物理地址的直接写。
使用一个虚拟/物理标记来表明段和合适的接口。若设备中还有空闲空间则其它段的分配可同时执行。设备空间使用计数器主要用于这个。
分段地址空间的原因是使文件系统在很大程度上降低递归更新的级数（只有namelesswrites时的递归次数）。如ext2和ext3文件系统可以设计，故inode和其他元数据被放置在虚拟地址空间。这样的文件系统可以简单的发出一个写操作到inode，并完成更新而不需要修改引用inode的目录结构。因此，分段地址空间允许完成更新，而不需要传播整个目录层次结构。
V和P的大小不固定，只要两个段中有空闲空间，就可以用于执行请求。
虚拟段接口：virtualread，virtualwrite，free
Nameless段接口：physicalread，namelesswrite，overwrite，free
C. 迁移回调
几种基于闪存的固态硬盘等设备因磨损均衡而需要迁移数据。我们提出迁移回调接口支持这样的需要。
一个典型的基于闪存的固态硬盘通过间接表执行磨损均衡：它只是移动物理块并更新映射表。在namelesswrites，段中的物理块不能移动，若不通知文件系统。为了允许nameless-writing设备移动数据，nameless-writing设备使用迁移回调通知文件系统块的物理地址的变化。然后文件系统更新指向这个迁移块的一些元数据。
D. 关联元数据
nameless-writing设备的最后接口是用于启用客户端快速定位指向数据块的元数据结构。关联元数据的完整规范支持客户端和设备之间的元数据通信。具体地说，nameless writes命令扩展到包括第三个参数：少量的元数据，这是持续记录一个per-blockheader中，与数据相邻。读取和迁移回调也扩展到包括元数据这个参数。关联元数据同时与每个块缓存一起保存在页面缓存中。
这种元数据使客户端文件系统很容易识别指向一个数据块的元数据结构(s)。例如，在ext3我们可以通过inode号、inode代号、inode中的块偏移，找到指向一个数据块的元数据结构。文件系统已经明确记录逆向引用，如btrfs和nof[]，逆向引用可以被重用于我们的目的。
Metadata使得文件系统更容易找出由metadata结构指向的数据块。（1）在pagecache中查询数据块时，我们获得元数据信息，并将其与数据页中数据块的关联元数据对比；（2）migrationcallback中，当一个数据块被迁移，使用关联元数据寻找需要更新的metadata；（3）associatedmetadata用于故障恢复。
最后一个值得注意的问题是关联元数据与地址映射表之间的差异。不同于地址映射表，相关元数据不用于定位物理数据，而是只在迁移回调和系统崩溃恢复时被设备使用。因此，它可以存储在与设备上的数据相邻的位置。只有少量的相关元数据提取到缓存设备，在迁移回调或短时间内恢复时。因此，关联元数据的空间成本远小于地址映射表。
E. 实现问题
一系列问题围绕虚拟段。最重要的是,这样的一段应该多大?不幸的是,它的大小在很大程度上依赖于客户端如何使用它,我们将看到当我们在Linuxext3使用namelesswrite。在第6节我们的研究结果表明,小型虚拟段通常是足够了。
虚拟空间,根据定义,需要一个内存中的间接表。幸运的是,这个表是非常小的,就像为虚拟段中的每个页包括了简单的页级映射。然而,虚拟地址空间可以大于表的大小；在这种情况下，设备会换入换出部分页表，减缓到虚拟段的访问（动态换入换出间接表，向DFTL一样）。因此，虽然把很多数据结构放置到虚拟空间是可行的，理想情况下，用户应该对虚拟段吝啬，为了避免超过支持物理资源。
另一个问题是额外级别的信息通过将物理地址暴露给用户。虽然物理地址已经被别人赞扬[]，但设备制造商可能会觉得这些信息揭示了他们太多的“秘密武器”，因此采用这种接口非常警惕。我们相信，如果这样的问题存在，设备就可以分发修改形式的真正的物理地址，从而试图对客户隐藏确切地址。这样做可能的额外性能和空间开销,也许从客户隐藏的成本信息。
2.2 构建nameless write设备（section 4）
在本节中，我们描述我们的实现一个模拟nameless-writingSSD。与namelesswrites，nameless-writingSSD可以有一个简单的FTL，有权力实现分配和磨损均衡。我们首先讨论如何实现nameless-writing接口，然后提出一种新的垃圾收集方法，避免了文件系统交互。
A. Nameless-Writing InterfaceSupport
我们实现了一个模拟nameless-writingSSD，它以日志结构方式，执行数据分配，通过维护有效块（块被顺序写）。当收到一个无名写时，设备分配下一个空闲的物理地址，写数据，并返回物理地址给文件系统。
为了支持虚拟块空间，nameless-writing设备维护逻辑地址和物理地址之间的映射表，在设备缓存。当缓存已满，映射表换出到SSD的闪存。在6.1节,我们的结果显示典型的文件系统的映射表印象很小，因此，这样的交换在实践中很少发生。
nameless-writing设备处理trims的方式类似于传统SSD，它将trim命令发送的物理地址置为无效。垃圾回收期间，无效页面被回收。该设备也将overwrites的旧物理地址置为无效。
Nameless writes需要为Namelesswrite保存确定的关联元数据。将每个数据页的关联元数据存储在其OOB区，associatedmetadata随着数据页的迁移而迁移。
B. In-place Garbage Collection
在Nameless-writingdevice中，使用in-placegarbage collection。FTL使用策略选择出一个候选块，并读出此块中的活动页及其元数据，暂时存储在一个超级电容或者备用电池缓存中，擦除此块中数据后，FTL将活动页写回到原地址块中，并尽量填满块的剩余空间（执行等待队列中的写操作）。因为flash块的写是顺序写，故若此块未写满且没有写操作来写剩余的空间使，剩余空间标记为不可用，即wastedspace。就地垃圾收集期间，有效数据的物理地址没有改变。因此,不需要任何文件系统的参与。
选择候选块的策略：
一个自然的问题是如何选择块的垃圾收集。一个简单的方法是选择块最少活跃页面，则读写的成本最小化。然而，选择这样的块可能会导致过多的浪费空间。为了就地垃圾收集期间选择一个好的候选块，我们的目标是最小化有效数据的重写成本，并在垃圾收集时减少空间浪费。我们提出一种算法，试图最大化效益和减少就地垃圾收集的成本。我们定义了垃圾回收一个块的成本cost为：cost= T_erase +（T_(page-read)+ T_(page-write) ）*N_valid
同时，定义benefit为可能会写入块中的新页的数量：
：等待队列中写操作的个数；：块中剩余的空闲页数目；预计的写操作个数（基于到来的写操作速度）。在写有效页和等待写请求期间，设备队列中将到达新的写请求，使用
计算新到达的请求开销，则FTL计算最大的块，即为候选块。
3、方案的实施（section5）
本章讨论在Linuxext3文件系统中，实现namelesswrites。Ext3系统中有三种日志模式：datamode，ordered mode和journal mode。ext3的命令日志模式是一种常用的模式，在事务提交元数据前，将元数据写入日志，将数据写到磁盘。它提供了命令，namelesswrites可以使用，因为nameless-writing接口需要元数据，来reflect数据写操作返回的物理地址。当在命令模式下提交元数据，数据块的物理地址对文件系统是已知的，因为数据块先被写入。因此，我们实现了无名写在ext3的命令模式下，其他模式留给未来的工作。
3.1 分段地址空间Segmented Address Space
我们首先讨论物理和虚拟地址空间分离和在ext3文件系统中修改配置。我们使用物理地址空间存储所有数据块，虚拟地址空间来存储所有的元数据结构,包括超级块、inode、数据和inode位图、间接块、目录块和日志块。我们使用一块的类型来确定是在虚拟或物理地址空间和接口类型。
Nameless-writing的文件系统不执行物理地址空间的分配，只在虚拟地址空间分配元数据。故不需要为了nameless块分配，获取或更新groupbitmap。对这些数据块，文件系统需要执行的唯一统计任务是跟踪整个设备空间的使用情况。具体来说，文件系统检查设备总空闲空间，并当一个数据块分配和回收时更新空闲空间计数器。在虚拟物理地址空间的元数据块以同样的方式分配（与ext3文件系统一样的方式），因此利用现有的位图。
3.2 关联元数据
关联元数据包含（1）指向数据块的间接块的节点号或者逻辑地址；（2）节点或者间接块的偏移；（3）inodegeneration number；（4）数据块的timesramp。前三项用于识别指向数据块的元数据结构；第四项在迁移回调进程更新元数据结构时使用。
所有的Associated metadata都存储在每个flash页的OOB区，并小于48bytes。
3.3 写操作：
执行nameless writes时，文件系统将数据和关联元数据发送给设备，设备执行无名写操作，并返回一个物理地址。文件系统根据这个物理地址更新inode节点或者指向此节点的间接块。同时用新地址更新块缓存。在命令模式下，metadatablocks总是在数据块提交后被更新，因此,磁盘上的元数据总是与它的数据一致。文件系统用类似方法执行覆盖。唯一的区别是，覆盖有现有的物理地址，发送到设备，该设备使用这些信息置旧的数据无效。
3.4 读操作
物理地址空间修改数据块读操作的两部分：读页缓存、读设备。为了搜索页缓存中的数据块，我们将块的元数据索引(比如i节点号、i节点代号和块偏移量)与缓存页的元数据对比。如果页缓存没有，文件系统使用它的物理地址从设备获取它。数据块的关联元数据也发送给读操作，使设备在磨损均衡期间搜索重新映射条目。
3.5 Free操作：
Linux ext3文件系统中，不支持trim操作，故这里使用类似ext4的方法处理trim操作。文件系统每删除一个块，就产生一个tirm entr。一个tirm entry包含named块的逻辑地址或nameless块的物理地址、块长度、关联元数据、地址空间标记。文件系统将这些条目加到当前事务处理日志中。在事务提交的最后，属于此事务的所有trimentries被发送至设备中。设备根据条目信息，定位数据块，并置为无效。
当一个元数据块被删除，原来ext3执行回收进程。当一个数据块被删除,不执行de-allocation（即位图没有被更新），只更新空闲空间计数器。
3.6 Wear Leveling withCallbacks：
nameless-writing设备执行磨损平衡时，它迁移实时数据以实现设备的均匀磨损。当这样的迁移在物理地址空间与数据块一起发生，文件系统需要了解他们物理地址的变化。在本节中,我们描述nameless-writing设备如何处理数据块迁移和它如何与文件系统执行迁移回调。
当有效的nameless数据块(和它们的关联元数据都在OOB地区)在磨损均衡期间迁移，nameless-writing设备创建一个映射（从数据块的旧物理地址到新的物理地址），并将其与关联元数据一起存储在设备缓存的migration remapping tabl中。migration remapping table用于定位数据块迁移的物理地址（读操作和覆盖操作）,这个新的物理地址与旧的物理地址一起发送到设备。添加了映射后，旧的物理地址被回收，是未来可以使用。
磨损均衡操作的最后，设备发送一个迁移回调（migrationcallback）到文件系统，其中包含所有迁移的物理地址和它们的关联元数据。然后文件系统使用相关的元数据来定位指向数据块的元数据，并使用新的物理地址更新它，在一个后台进程。接下来，文件系统将改变的元数据写入设备。当一个元数据写完，文件系统删除所有属于此元数据块的回调条目，并将响应发送给设备,告知他们迁移回调处理。最后，当设备收到迁移回调的响应后，删除重新映射条目。
对于迁移的元数据块，文件系统不需要知道物理地址的改变，因为它保存在虚拟地址空间。因此，设备不为元数据块保存重新映射条目或发送迁移回调。
在迁移回调过程中，我们允许对迁移数据块的读操作和覆盖写操作。当在回调期间收到一个读或覆盖写，设备首先在migrationremapping table中查找当前数据块的物理地址，然后执行该请求。
因为文件系统完成迁移回调前，所有重新映射条目存储在设备上的RAM中，如果文件系统不响应回调或者反应太慢，我们可能会耗尽RAM空间。在这种情况下，我们只是禁止未来的磨损均衡迁移，直到文件系统响应，并只通过垃圾收集防止块磨损。
3.7 ReliabilityDiscussion：
有三个主要的可靠性问题。1，我们保持在设备上的RAM映射表为虚拟地址空间。这个表在每一次设备启动时需要重建(正常关机后或崩溃)。2，内存中的元数据与nameless块的物理地址不一致的，因为系统崩溃在写一个数据块后和前更新其元数据块前，或者损耗均衡回调间系统崩溃。3，崩溃可以发生在就地垃圾收集期间，具体来说，在读实时数据后且在写之前，这可能会导致数据丢失。
我们解决前两个问题通过使用保存在设备OOB区域的元数据信息。我们在虚拟地址空间存储逻辑地址与数据页，以便重构逻辑地址到物理地址映射表。我们存储关联元数据，和所有nameless数据。我们存储所有flash的有效性在OOB区域。我们维护一个不变量，即OOB区的元数据总是符合flash中的数据页，通过原子写写OOB区和flash。
我们解决就地垃圾收集的可靠性问题，要求使用一个小内存由电池或超级电容器。注意，我们在垃圾收集操作时需要保持的实时数据的数量，不超过SSD块的大小，通常256KB，因此只添加一个小的货币成本对整个设备。
恢复过程如下工作。在启动设备时，我们执行整个设备扫描和阅读OOB区域所有有效的flash页面重建虚拟地址空间的映射表。如果检测到崩溃，我们执行以下步骤。设备发送OOB地区相关联的元数据和闪存的物理地址页面的物理地址空间到文件系统。然后文件系统找到适当的元数据结构。如果物理地址在一个元数据结构不一致,文件系统更新的新物理地址并添加元数据写入一个专门事务。毕竟元数据处理、文件系统提交事务,此时恢复过程完成。
4、测试结果及分析
SSDEmulator：伪块设备[[1]]，有垃圾回收和磨损均衡[[2]]，执行三种类型的FTL：（1）页级映射；（2）混合映射[[3]]；（3）在PSU最上层的nameless-writing[[4]]。配置如下：
系统配置：Linux2.6.33 kernel，64位，2.5GHz Intel Quad Core CPU with 8 GB memory。下图为三种FTL设备（页映射、混合映射、namelesswrites）在不同文件系统映像下的映射表大小。
如下图2，显示了三种FTL设备（页映射、混合映射、namelesswrites）在三种环境（Varmail、FileServer、WebServer）下的吞吐率。其中，Varmail、FileServer、Webserver分别包含90.8%、70.6%、3.8%的随机写操作。Varmail、FileServer环境下，页映射和namelesswriting的吞吐率相当，高于混合映射。在WebServer环境下，三种FTL设备吞吐率相当。
如下图3，测试了三种FTL设备（页映射、混合映射、nameless writes）在执行顺序写和连续4 KB的随机写操作的吞吐率。得出以下结论：（1）三种设备执行顺序写操作的吞吐率相近；（2）执行随机写操作时，页映射和nameless writes设备的吞吐率相近，混合映射的吞吐率则小很多，并且，混合映射日志块越大（日志块占设备总大小比例：5%、10%、20%），吞吐率越大。故由图3可得，相比于页映射设备，nameless writes设备在执行顺序写和随机写时，开销更小。
如下图4-6，表示了在不同的workingset下，三种设备在执行随机写操作时的吞吐率、数据迁移次数、平均相应时间。可得：workingset对于随机写性能的影响很大：随着workingset的增大，页映射设备和namelesswrites设备的吞吐率明显减小，原因是这期间垃圾回收期间的数据迁移明显增大。
将设备利用率分为：regularwrites, block erases, writes during merging, readsduring merging, device idle time。如图7-9，显示了在不同的workingset下，三种设备在执行随机写操作时各种开销所占的比例。可得以下结论：（1）当工作集很小时，页映射和nameless writes设备的主要开销来自于regularwrites，随着工作集的增大，mergewrites和erases逐渐成为主要因素。（2）混合映射的主要开销来自于migratinglive data和idletime。
由以上可得：页映射与namelesswriting设备的随机写性能相当，比混合映射设备好很多，主要因为混合映射的合并开销。另一方面，当workingset较小时，页映射与namelesswriting设备的随机写性能较为客观。
5、存在的问题
本文：Zhang,Yiying, et al. "De-indirection for flash-based SSDs with namelesswrites." FAST. 2012.（A类会议）
[1] excess indirection：计算机系统中为了解决问题，而增加的间接层
[2] de-indirection：移除计算机系统中的excess indirection；
[3] name：本文中的name一般指逻辑地址或者物理地址
[[1]]N. Agrawal, L. Arulraj, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau.Emulating Goliath Storage Systems with David. In Proceedings of the 9th USENIXSymposium on File and Storage Technologies (FAST ’11), San Jose, California,February 2011.
[[2]]N. Agarwal, V. Prabhakaran, T. Wobber, J. D. Davis, M. Manasse, and R.Panigrahy. Design Tradeoffs for SSD Performance. In Proceedings of the USENIXAnnual Technical Conference (USENIX’08), Boston, Massachusetts, June 2008.