Write Amplification Analysis in Flash-Based Solid State Drives

Write Amplification Analysis in Flash-Based Solid State Drives

• 摘要
• 第一部分
• 第二部分
• 第三部分

此文发表于2009年

摘要

写入放大是限制基于NAND闪存的存储设备中的随机写入性能和写入耐久性的关键因素。GC对WAF的影响来自于OP 水平和回收策略的选择。在本文中，提出了一种新的基于日志结构的闪存SSD写入放大的概率模型。具体来说，通过量化分析op对WAF的影响，并通过仿真假设均匀分布的随机短写入的工作量。此外，我们提出了贪婪垃圾收集回收政策的修改版本，并比较了它们的性能，最后，我们分析评估分离静态和动态数据在减少写入放大方面的好处，以及如何通过适当的磨损均衡来解决耐久性问题。最后，评估静态和动态数据在减少WAF方面的好处，以及如何通过适当的磨损均衡来解决耐久性问题

第一部分

介绍
使用闪存的这些器件提供数量级的随机I / O性能和访问延迟比旋转硬盘驱动器（HDD）更好。NAND闪存具有独特的特性，这对SSD系统设计提出了挑战，尤其是随机写入性能和写入耐久性方面。
关于NAND性能主要来自out-of-place write的原因，如果使用write-in-place，则由于必要的读取，擦除和重新编程（写入）正在更新数据的整个块，闪存将表现出高延迟。但是，out-of-place write写入需要垃圾收集过程，这会导致额外的读写操作。而在引用文献【The design and implementation of a log-structured file system】中选择块进行垃圾收集的回收策略仅基于要获得的可用空间量，引用文献【An age-threshold algorithm for garbage collection in log-structured arrays and file systems】中定义的策略还包括自上次写入的带有数据的block以来所经过的时间。通常上，进行垃圾回收的目标块是有效页最少的块，比如说，高效的垃圾回收是通过延长保持块中的数据活跃无效来提高的。GC读写来源于块中有效无效页数。
与磁盘相比，闪存块最终会磨损随着program-erase周期数的增加，直到他们不能再被写了。WL技术尽可能耗尽program-erase周期（即，周期预算），以便为最大数量的用户写入（或主机）提供服务，从而最大限度地提高耐力。它们的性能是通过垃圾收集不再返回空闲块时剩余的总消耗周期预算来衡量的。retention是另一个问题，也可以通过磨损均衡来解决。
假设独立且均匀分布的随机短写入，最佳损耗均衡技术包括尽可能均匀地磨损所有块。例如，这可以通过最小化所有块上的最大磨损和平均磨损之间的差来实现，描述在引用文献【The real story about NAND flash and solid-state drive reliability】。
实际上，主机写入不是均匀分布的。如果可以在具有静态数据的块之间进行区分（即，主机不经常重写数据的地址）和具有动态数据的块（具有频繁的重写），磨损均衡可以从不同地处理这两种类型的受益而不是整体均匀地磨损它们。因此，在这种情况下，耗损均衡性能不仅取决于未消耗的周期预算，以及通过反复移动未被修改的静态数据而浪费的周期（也就是说如果数据是不经常更新的，就不要来回move增加读写操作）。
在所有的情况下，WL都会引起额外的读写操作。因此，在闪存中，WAF相对应的额外写操作是由于GC和WL引起的。因此,用户写入的总数取决于总周期预算的总周期,WAF和最终的不再被消费周期预算因磨损不足而导致的。
最后，out-of-place更新的 管理涉及到逻辑块地址，user(host)的地址到物理快的地址的转换映射。这个映射可用于区分动态静态数据。
这篇论文提出了基于日志结构的闪存SSD中写入放大的概率分析。分析假设窗口贪婪的回收
政策，是基于年龄阈值的政策在引用文献【An age-threshold algorithm for garbage collection in log-structured arrays and file systems】中描述的变体。假设4 KB独立且均匀分布的用户写请求，导出写放大。通过仿真来证实结果。然后将分析结果扩展到案例中可以区分哪些静态和动态数据。

第二部分

引用文献【A flash-memory based file system】中的在基于闪存的日志结构文件系统垃圾收集中
当利用率很高时，对性能有重大影响。常见的GC策略是引用文献【Real-time garbage collection for flash-memory storage systems of real-time embedded systems】中的贪婪算法，一个包含无效页最多的块要被回收。然而，垃圾收集也有助于消耗周期块的预算，将它与磨损均衡结合起来通常是有益的。

两者结合的算法很多。引用文献【Real-time garbage collection for flash-memory storage systems of real-time embedded systems】中提到，避免垃圾收集中不必要的回收，并将其与执行任务形式的磨损均衡相结合线性搜索具有少量擦除计数的块，以识别要回收的块。引用文献【Design tradeoffs for SSD performance】中提到另一种结合的算法叫做更改贪婪算法策略，该算法通常选择具有最多无效页面的块用于垃圾收集，同时避免所有块中的剩余周期预算中的大量扩展并限制静态数据的频繁移动。静态WL在引用文献【True FFS wear-leveling mechanism】中提到的与不重新定位静态数据的策略相比，耐久性提高了4倍（假设动态的75％和静态数据的25％）。文献【Competitive analysis of flash-memory algorithms】中进行了最坏情况的竞争分析，重点是基于耐力的随机算法。为了达到近乎理想的耐久性，他们建议将垃圾收集与磨损均衡分开。

最初，Rosenblum等人已经研究了WAF。 文献【The design and implementation of a log-structured file system】中日志结构文件系统作为磁盘利用率的函数。Sprite LSF分析区分热数据和冷数据（包括读取和写入），而我们则区分静态和动态数据，因为只有写入会导致写入放大。此外，Sprite LSF写入成本比较包括搜索时间，旋转延迟和清洁成本。 因此，我们的结果只能与Sprite LSF的结果进行定性比较。

虽然有些闪存研究论文简要提到了垃圾收集和磨损均衡对性能的影响，但我们没有找到基于闪存的存储系统中写入放大的详细分析，例如文献中的备用关系。

第三部分

Architecture of a Log-structured SSD

日志结构SSD的通用体系结构由具有一些DRAM的控制器和一组闪存芯片组成。当一个闪存页面被写入后，在擦除其块之前，它不可用于写入。控制器保持一个LBA-PBA的映射，当更新LBA寻址的页面时，将分配一个空闲闪存页面来存储新数据。LBA-PBA映射中的相应LBA条目将相应地进行修改：LBA映射到新PBA，旧PBA标记为无效数据页。 请注意，可以保留LBA-PBA映射在

DRAM或闪存。然而，后者引起额外的读和写操作，因此导致WAF。由于这是特定于实现的，因此这里不考虑这些附加操作。 此外，高效LBA-PBA映射的实现超出了本文的范围。

如果写入工作负载是严格顺序的意味着所有数据将按照LBA的连续顺序更新，则不需要复杂的GC，因为当写入请求继续时，闪存块逐块无效。可以简单地擦除不包含有效数据的块，从而避免重新定位有效数据页的负担。
在随机写入工作负载的情况下，并且在处理大量页面写入之后，闪存中的空闲页面的数量变低。GC然后回收被分散在块上的无效页面阻止的空间。一旦被回收的块被选中，块中所有的有效页都要被重定位到新块中的空闲页。这时选中的块要被擦除掉，在那个块上所有页这里设页数为np都变成空闲的再次被分配给新的写入请求。GC的效率由WAF来决定。

写入放大因子Af = V/I (GC write与Host write之比)，非零写入放大因子意味着每个用户页面
写入会导致额外写入重定位页面，平均导致总共（1 + Af）页面写入。写入放大不仅会恶化用户随机写入性能，还会降低耐用性。 对于严格顺序的写入工作负载，写入放大因子为零，即，没有写入放大。

回收策略应该尝试最小化减少写放大，这里考虑流行的贪婪算法等到几乎所有的空闲页被耗尽开始选择有效页最少的块来回收。这个策略的原理是，回收过程可以延迟的时间越长，所选块中的有效页面就越少，从而使写入放大最小化。贪婪算法略通过独立，随机，均匀分布的写入对写入放大的贡献最小。

OP是一个影响GC性能的重要因素，OP理论是让用户只使用总容量的一部分，因此，增加OP就导致无效页数量增加，提高了GC的整体效率。

为了衡量op的影响，这里介绍两个术语，即op因素和备用因素。
Of=t / u (t: SSD的原始容量block数 u:用户是使用的一部分blocks数 Of: op factor)
Sf=(t-u)/t (Sf: spare factor)
Sf = 1 – 1/ Of