从嘉の小站

Embedded system, Operating system & AI. Reading, Movie & Life.

Design Tradeoffs for SSD Performance

Design Tradeoffs for SSD Performance

文献:Agrawal N, Prabhakaran V, Wobber T, et al. Design Tradeoffs for SSD Performance.[C], Usenix Technical Conference. 2009. https://www.usenix.org/legacy/event/usenix08/tech/full_papers/agrawal/agrawal.pdf

一、本文工作

  • 对设计选择进行分析、分类和折衷,以达到SSD最佳性能;
  • 使用 trace-driven 手段评估优化结果;
  • Wear-leveling & Cleaning (Garbage Collection)优化。

备注:本文主要关注 flash array 的组织形式,以及管理映射机制的算法。其他影响 SSD 性能的重要因素,如 SSD 逻辑组件的设计和布局,并不在本文的考虑范畴。

二、研究背景

与 rotating disks 相比,SSD 具有更高带宽,可提升随机读写 (random I/O) 性能,节约能耗,提升系统可靠性;但同时,成本更高。

与SSD性能有关的因素:

  • 数据放置策略 (Data placement)。影响 Load-balancing & wear-leveling;
  • 并行性 (Parallelism)。提高带宽和操作速率;
  • 写顺序 (Write ordering)。解决小的、随机写问题;
  • 负载管理 (Workload management)。性能与负载高度挂钩。

三、知识点梳理

1.Flash

(1)构成

  • 一个 4GB Flash Package 由两个 2GB die 构成,每个 die 包含四个 plane,每个 plane 由2048个 block 构成,每个 block 由64个 4KB page 构成,每个 page 包含 128 byte 的元数据 (metadata: identification and error-detection information) ;
  • 两个 die 共享8-bit串行 I/O 总线及公共控制信号,而片使能与 ready/busy 信号 独立。因此,两个 die 可以交错运行 (interleaved operations);
  • 每个 die 操作包含一个或两个 plane。Two-plane 操作只能在 0&1 || 2&3 的 plane 对上执行,不能横跨其他组合。

(2)操作属性

  • 数据 读操作发生在 page 粒度。读操作的过程如下:从 media 读到 4KB 的数据寄存器(data register)中,再从寄存器转移到数据总线(25µs);然后,串行总线以大约 100µs/page 的速度传输数据;
  • 写操作过程如下:将数据交换到寄存器中 (100µs),再从寄存器中写入到 flash cell (200µs)。数据在 block 内 只能按照地位地址到高位地址的顺序写。同时,为了提高性能,提供从一个 page 到另一个 page 的拷贝操作 (copy back),以避免通过串行总线将数据传输到外部缓冲区;
  • Erase cycles limit: 100K.

(3)Bandwidth and Interleaving

  • Flash package用于接收命令和传输数据的串行接口,是SSD性能的一大瓶颈。 以读操作为例,若 transfer a 4KB page from the on-chip register to an off-chip controller (100µs) 与 move data into the register from the NAND cells (25µs) 两个过程顺序执行,一个 flash package 每秒只能读 8000 pages (32 MB/sec);而若使用交错读 (interleaving) 策略,最大读带宽可达 10000 pages/sec (40 MB/sec)。
  • 理论上,由于一个 package 中有两个独立的 die,我们可以将三种操作(从寄存器读、向寄存器写、数据总线)交错起来。

  • 当操作延迟比总线传输延迟大时,interleaving 机制的提速效果相当可观。如上图所示,尽管一个单独的写操作就需要耗费 200µs,两个 package 之间的交错数据拷贝却可以被提速到 100µs/page。
  • Interleaving 存在一些限制:同一 plane 上的操作不能被交错;
  • The difference/connection between two-plane write & interleaving //待搜

2.SSD

(1)构成

  • 主机接口逻辑 (host interface logic),用于与物理主机接口 (USB, FiberChannel, PCI Express, SATA) 连接。主机互联接口的带宽往往是整个设备性能的瓶颈,必须与 flash array 的性能相匹配;
  • Logical disk emulation,与 FTL 一样,都是为了模拟硬盘驱动 (hard disk driver) 行为;
  • 内部缓冲区管理器 (Buffer Manager) 保存在主数据路径 (the primary datapath) 上的待处理请求;
  • 多路复用器 (Flash Demux/Mux),或 Flash Controller,通过与 flash packages 连接的串行总线来发送命令与传输数据;
  • 处理器 (processor) 负责处理请求流和完成逻辑块地址到 flash 物理地址的映射;
  • Processor, buffer manager 和 multiplexer 构成了 SSD Controller。SSD Controller 常部署在 ASIC/FPGA 等独立组件上;
  • Flash package 引出控制引脚及 8-Bit 宽的串行总线接口,与 SSD 连接。一个 32GB 的 SSD 包含八个三星 Flash Package,其 flash controller 需要 136个引脚 与 flash 连接。//为什么是136?

(2)逻辑块映射

由于对每个单独的逻辑磁盘块地址 (logical-disk block address, LBA) 的写操作对应于对不同 flash page,因此,需要对逻辑块地址与 flash 物理位置进行映射。

使用 分配池 (allocation pool) 来描述 SSD 如何分配 flash block,以响应写请求。当处理一个写请求时,每个目标逻辑页 (4KB) 将从一个预定义的 flash 存储池中被分配。分配池的性能与以下几个参数有关:

  • 静态映射。每个 LBA 中有一部分会固定映射到特定的分配池;
  • 动态映射。LBA 中的非静态部分是池内映射的查找键值;
  • 逻辑页尺寸。映射项的引用尺寸从 flash block (256KB) 到四分之一页 (1KB) 不等;
  • 页范围。逻辑页可能横跨 不同 flash packages 上的 page,由此,并行访问部分页是可行的。

    Attention: 注意逻辑页与物理页的区别!逻辑页大小可能大于 block。

这些参数受以下三个条件约束:

  • 负载均衡。
  • 并行访问。LBA 在物理地址上的分配应尽可能少地相互影响,从而保证可以并行获取他们。比如,如果 LBA0…LBAn 往往是同时访问的,就不应当将他们存储到需要顺序访问的组件中;
  • 块擦除。只有块擦除后才能进行页重写。

Tradeoffs:

  • 如果 LBA 的大部分空间是静态映射的,那么负载平衡的余地就很小;
  • 如果连续的 LBA 被映射到相同的物理 die,则对大块 (large chunk) 的顺序访问性能将受到影响;
  • 若使用较小的逻辑页面大小,将需要更多工作来移除待擦除块中的有效页面;
  • 若逻辑页面大小(单位跨度)等于块大小,则虽然擦除工作被简化了,但是所有小于逻辑页面大小的写入都会导致读取-修改-写入操作,哪怕目标逻辑页面中的某些部分并没有被修改。

Solution:

这里,我们使用细粒度的 striping 方法来在多个 flash dies 或 packages 中分配逻辑页面(4K)。这样既可以 分配负载,也可以将连续的页面放在可以 并行访问的不同 packages 上。

(3)Cleaning (Garbage Collection)

以 block 作为分配池中的基本分配单元。在任意时间,池中存在一个或多个可以接收数据写入的 active block。使用垃圾回收策略回收之前使用过的块,以供后续写入。若逻辑页粒度小于 flash block size,那么待擦除页面上可能存在 unsuperseded pages,必须在擦除前进行 cleaning/GC,将 unsuperseded pages 写到其他地方。

在最坏情况下,若 superseded pages 均匀分布在所有块上,则每写入一个新数据,需要进行 N-1 个 GC 操作。当然,大多数工作负载的写操作是聚集的,所以,在数据重写时,每个块中有多个 superseded pages。

使用 cleaning efficiency 来量化 GC 期间被取代页面数占总页面数的比例。大多数选择待擦除块的算法,都是以最大化 cleaning efficiency 为目标。

值得注意的是,使用 striping 来增强顺序地址的并行访问会减少 superseded pages 的聚集。

此处假设使用贪心法进行垃圾回收,以最大化 cleaning efficiency。

此外,必须存在块冗余,以支持坏块替换。SSD 通过 overprovision 来减少 foreground GC (The Write Cliff 一文中有详细阐述)。

延迟 GC 可以在 non-random workloads 上更好地聚集 superseded pages。

(4)Parallelism and Interconnect Density

假设 SSD 与 flash 全连接。Flash packages 并行处理 I/O 请求的方式有如下几种:

  • 并行请求。在全连接的 flash array 中,每个元素彼此独立,可以单独接收请求流。但是这带来了维护的复杂性;
  • 联合 (ganging)。可以同步使用一组 flash packages 来优化多页请求问题。这样可以并行使用多个 package,并且不会带来多个队列的复杂性,但是,如果只有一个请求队列,若请求不涵括的所有元素,那么他们将一直处于 idle 状态;
  • 交错 (Interleaving)。交错可用于改善带宽和隐藏高延迟操作;
  • 背景 GC。见 The Write Cliff。此外,使用不需要通过串行接口传输数据的操作(例如内部 copy back)可以帮助隐藏 GC 成本。

Ganging flash packages 有如下两种方法:

  • Controller 动态选择每个命令的目标,packages 通过串行总线互连;
  • 每个 package 有独立的数据路径,而控制总线共享。

方案一共享 D/C bus,使能信号对每一命令做片选。该方案可以在不增加引脚的情况下增加容量,但不会增加带宽。

在方案二中,跨越多 package 的操作可并行执行。Enable 信号可以不要,但如果去掉 enable signal,所有的操作都必须作用在整个 gang 上(即没有 package 可以处于 idle 状态)。

交错机制也可以在 gang 内使用。可以在一个组件上执行诸如 GC 之类的耗时操作,而在其他组件上执行读写操作。唯一的问题就是对共享 D/C bus 的竞争,在页循环 (page recycling) 过程中,这一点非常重要,因为块擦除比其他操作的时间开销高出一个数量级。此外,可以使用 intra-plane copy-back 机制来实现后台 GC。

若 page 在两个 chip 之间以最大速度流式传输,GC 耗时可以减少,但这是以占用两组控制器引脚为代价的。

然而,随着 SSD 容量的增大,实现 controller 与 Flash package 之间的全连接是困难的。因此应当根据工作负载特性选择并行策略。例如:

  • 高度顺序的负载更适用于 ganging;
  • 固有并行机制的负载适宜使用深度并行的请求队列结构 (request queuing structure);
  • Cleaning efficiency 较差的负载则更依赖与前景负载兼容 (foreground load) 的 GC 策略。

(5)Persistence

Flash 是持久存储单元,然而,为了恢复 SSD 状态,重建逻辑块映射及所有相关的数据结构至关重要。这种恢复还必须重建坏块信息,以防他们被重新使用。

解决上述问题有几种方法,多数使用了 flash page 中的 128 bytes 的元数据 (metadata),可用于存储映射到给定 flash page 的逻辑块地址。

[2]通过保存每个块而不是每页的映射信息,避免了在启动时访问每个页面。但是,在这种算法中,内容已被取代 (superseded) 但尚未被删除的页面将在恢复期间多次出现。在这些情况下,稳定存储表示必须让恢复算法确定分配池中逻辑页的最新实例。通常,flash 不提供错误检测和纠正,这些功能必须由应用程序固件提供。页面元数据还可以包含 EDC,以确定有效页和无错误块;以及 ECC,以从 NAND flash 的单比特错误 (single-bit errors) 中恢复。通过使用更稳健的纠错策略,可以延长块寿命。

此外,通过在 Phase-Change RAM [14] 或 Magnetoresistiv eRAM [9] 中保存逻辑块映射,可以完全绕过恢复 SSD 状态的问题。这些非易失性存储器可以以字节粒度写入,并且没有 NAND flash 的块擦除约束。

(6)Wear-leveling

上面我们假设使用贪心法进行 GC/cleaning,但这带来了一个问题:相同的块可能会被反复利用。这样会降低总体寿命。

我们采取的策略是尽可能确保所有块的剩余寿命大致相等。比如,每个块的剩余寿命都低于平均剩余寿命的 ageVariance (如20%)。若块寿命超过阈值,则可以使用贪心法选择目标块。为此我们需要在 persistent storage(如 metadata)中维护块擦除数。有两种策略:

  • 仅当目标块的寿命超出阈值时,才允许回收。但这样可能会导致部分块回收更频繁,从而降低 cleaning efficiency。例如,若 25% 的块上储存的是 cold data,而 75% 的块上储存的是均匀访问的 hot data,那么在一定数量的写操作后,回收将会集中在 25% 的块上,这些块的重用速度将提高四倍,每次擦除所产生的 page 也会相应减少。因此,我们应当避免大量的块不会被回收的情况。对这一问题的解决方案是 速率限制 (rate-limit) 它们的使用。同时,使用 随机化方法 来减缓速率限制策略对 worn-out block 的影响,当块的剩余寿命从平均值的80%下降到0%时,回收概率从1到0线性下降。
  • 将 cold data 迁移到 worn-out block 中。迁移数据时,像往常一样执行 cleaning,但不是将循环后的块加到分配池队列,而是使用之前存储 cold data 的块。这一操作在块的剩余寿命低于 retirementAge (如平均剩余寿命的85%)时被触发。RetirementAge 应小于 ageVariance,以便在 rate-limiting 前将冷数据迁移到 worn-out block 中。

那么,如何鉴定 cold data?一种方法是查找自上次擦除以来剩余寿命和距上次擦除的时间超过某特定参数的块。可以通过查询块的 metadata 最后一次被写入的时间来得到这些信息。在这种情况下,temperature metadata 应始终与块内容一同移到新的物理块;而块迁移则不会改变其 temperature metadata。GC 过程可能将具有不同 temperature 的页聚集到同一个 block 中。//temperature metadata 是什么?与其他 metadata 的区别?感觉这里的温度应该有别的内涵。metadata 的构成?

综上,若选定块的剩余寿命低于 retirementAge,则将 cold data 从迁移候选队列迁移到该块中,并回收队列 head 块,同时使用超过剩余寿命阈值的块来填充队列,或通过跟踪内容 temperature 来选择迁移候选者;否则,若选定块的剩余寿命低于 ageVariance,则限制块的回收,其回收概率随着剩余寿命降至0而线性增加。

四、实验手段

From our discussion of industry trends, it is clear that current SSDs can get very good performance numbers from ideal workloads. For example, under sequential workloads these devices verge on saturating any interconnect, RAID controller [24], or host peripheral chipset [1][1]. However, it’s unclear whether this is true of a single sequential stream, or multiple streams. And if multiple, how many streams are optimal? Does the stated write performance account for cleaning overhead? What is the random write performance and what are the assumptions about distribution of superseded pages during cleaning?//说实话没太看懂这段,与之前提到的工业界发展趋势有何关系?提出这些问题的中心疑惑点在哪儿?需要再悟一悟。

本文使用 trace-driven simulation environment 来深入了解 SSD 在不同工作负载下的表现。

1.实验对象

Flash: Samsung’s K9XXG08UXM series NAND-flash, 4GB, SLC

2.Benchmark (需要后续再深入了解)

TPC-C benchmark, Exchange server workload, standard file system benchmarks (IOzone and Postmark).

此处对每个 benchmark 的细节配置暂时略去。

3.Simulator

使用 CMU Parallel Data Lab 的 DiskSim Simulator 的修改版本。DiskSim 模拟了存储组件的层次结构,例如总线和控制器(如RAID阵列)以及磁盘。

本文从通用 rotating disk 模块派生 SSD 模块。

  • 由于这个模块没有原始地支持多个请求队列,我们​​添加了一个辅助并行元素,每个元素都有一个封闭的队列,以表示 flash elements 或 gangs;
  • 添加了序列化完成来自这些并行元素的请求的逻辑;
  • 对于每个元素,使用数据结构来表示 SSD 逻辑块映射,cleaning state 和 wear-leveling 状态;
  • 在处理每个请求时,根据下表中的规范引入延迟,来模拟实时延迟;
  • 若模拟器需要进行 GC 和recycling,则引入额外的延迟来解释,并相应地更新状态;
  • 使用配置参数来实现 background cleaning, gang-size, gang organization (e.g. switched or shared control),interleaving, and overprovisioning 等特征。

使用 DiskSim 生成的综合工作负载作为表征顺序和随机访问请求流的​​ baseline。

4.Wear-leveling

鉴于 IOzone 具有更高的清洁率,使用 IOzone 来分析 wear-leveling 算法的效果。实验中,将一个 flash block 的生命周期设置为50,RetirementAge = 85%,ageVariance = 20%。

五、实验结果

1.Simulation Results

(1) Baseline (Microbenchmarks)

Configuration: 32GB SSD, 8 fully connected flash packages, size(allocation pools) = 4GB, size(logical page) = size(strip size) = 4KB, each SSD is overprovisioned by 15%, cleaning when 5% free blocks remain.

TPC-C 需要六块 SSD,Exchange 需要十块。

实验结果如下图所示。

分析: 在全连接 SSD 中,顺序读写与随机读写具有相同延迟(包含传输页数据和 128 byte 元数据的时间)。而当引入 GC/cleaning 后,写入操作的延迟会导致额外开销。不过,顺序写可以提高 cleaning efficiency,从而减小 GC 开销。

(2) Page Size, Striping, and Interleaving

逻辑页尺寸的选择对整体性能有很大的影响。

当以单位深度(例如,同一 die 上的所有逻辑页)运行块大小的逻辑页(256KB)时,TPC-C 的平均 I/O 延迟超过20毫秒,比 4KB 逻辑页的延迟超出两个数量级。同时,由于 SSD 固有的并行性,使用 256KB 的逻辑页大小,几乎不能达到 300 IOPS/SSD 的平均 trace rate。

当减小页尺寸时,性能表现有所提升。

page size = 4KB 时,TPC-C 的延迟为 200µs,即 40,000 IOPS.

此外,交错机制也可以提升 SSD 性能。有两种可供选择的交错方案:package / die 内交错。下图是交错机制的实验结果。

可以看到,交错机制对 TPC-C 和 Exchange 没有影响,而 IOzone 和 Postmark 的吞吐量则有明显提升。下面对这一现象进行分析。

如图(b)所示,TPC-C 和 Exchange 每个 flash package 的平均排队请求数约为零,自然无需交错机制。而 IOzone 和 Postmark 则是顺序 I/O,当受限于 strip size,将顺序请求分发给多个 package 时,排队就产生了,此时则需要引入交错机制,以提升性能。

One might think that TPC-C would benefit from striping its 8KB requests at 8KB increments thereby allowing every request to interleave at the package or die level. However, splitting up each request into parallel 4KB requests is in this case superior. //????? 对 strip 机制还是没吃透,需要再看看。

(3) Gang Performance

Ganging 可以扩展存储容量,而无需扩展引脚数和引入复杂逻辑固件。有两种 ganging 方式:共享数据总线和共享控制信号。

上表显示了在 8-wide (32KB) 和16-wide (64KB) 共享总线下,Exchange 可变大小 I/O 请求的平均延迟。实际上,该负载只需要大约 900 IOPS,因此即使必须串行访问 ganged components,16-gang 也足够快。当使用简单的 page level striping 时,没有明显的负载均衡问题。

Shared-control ganging 有两种方式,1.每个 package 有独立的 allocation&cleaning 机制,即异步共享控制,这为并行执行提供了可能;2.同步共享控制,通过使用大小等于 ganging size 的 logical page,同步管理 gang 中的所有 packages,例如,8-gang 中的 logical page size = 32KB。

使用 intra-plane copy-back 来实现同步 ganging 中少于一页的写操作的 read-modify-write 过程。

下图是实验结果。由于同步 ganging 的逻辑页大于相应的异步 ganging,因此它限制了可以在 gang unit 中同时执行的操作数,因此与异步 ganging 相比,同步 ganging 表现总体不佳。

(4) Copy-back vs. Inter-plane Transfer

在 GC 中,要转移待擦除块中的 valid page。若转移的目标块与待擦除块在同一 plane 中,则可以使用 copy-back 机制,从而避免了数据通过串行引脚(在 plane 间)传输。

上表展示了每个 package 中的平均需要 GC 的块数、GC 的平均时间,以及平均 cleaning efficiency。

通过使用 copy-back 机制,TPC-C 的 GC 开销减少了40%。然而,尽管 IOzone 和 Postmark 有大量块需要进行 GC,使用 copy-back 却没有带来明显的优化,这是因为这两种 benchmark 的 cleaning efficiency 为100%,在 GC 时无需移动 page。

(5) Cleaning Thresholds

需设置一个触发 GC 的最小阈值,以保证 SSD 能正常运行,并能够应对写入尖峰。然而,提升阈值会导致更频繁的 GC,从而增加开销。

图(a)显示了 cleaning 阈值对访问延迟的影响。TPC-C 的访问延迟随着阈值的增大而明显增加,而其他 workload 则没有明显变化。通过分析各负载在 GC 期间移动的页数与阈值的关系可以对上述现象进行解释。

因此,阈值变化对 SSD 性能的影响与工作负载需移动的页数有关。

(6) Summary

2.Wear-leveling

表7展示了三种算法的运行结果:greedy, greedy + rate-limiting, greedy + rate-limiting + migration。尽管三种算法并没有对平均寿命有大的改变,但 greedy + rate-limiting + migration 对寿命方法有较大改善,此外,运用该算法时,没有块 expired。而 greedy + rate-limiting 则比单纯的贪心算法的 expired 块数目更少。

表8展示了块寿命的分布情况。可以看到,greedy + rate-limiting + migration 算法的块寿命分布更为均衡和集中。

与文件系统相关的部分暂未吃透。

六、结论

  • SSD的性能和寿命与工作负载高度挂钩 (workload-sensitive)
  • 从硬件角度来看,SSD interface (SATA, IDE, PCI-Express) 和 package 组织方式限制了 SSD 的最大 I/O 性能;
  • 从软件角度来看,可通过 allocation pool, load balancing, data placement, and block management (wear-leveling and cleaning) 与工作负载特性结合的方式来优化 SSD 性能。此外,plane interleaving 和 overprovisioning 也可以提升性能。

七、相关研究

1.SSD

2.File System

3.算法及数据结构

八、本文参考文献

[1] host peripheral chipset

[2] NAND Flash 写特性及提升写性能

[4] DiskSim simulator

[8] Random Early Discard

[9] Magnetoresistive RAM

[14] Phase-Change RAM

[15] IOzone

[16] Postmark

[24] RAID Controller

[26] RAID系统

[28] Log-Structured File System

[29] Samsung’s K9XXG08UXM series NAND-flash

admin

评论已关闭。