NAND Flash

NAND Flash 相关基本知识整理。

Blocks, Pages and Program / Erases

原文链接:https://flashdba.com/2014/06/20/understanding-flash-blocks-pages-and-program-erases/

几个名词:
package, 即内存芯片。
die, 可独立执行指令及反馈状态信息的最小单位。
plane, 通常,并发操作在plane上执行(往往有一些限制条件)。
block, 最小可被擦除的单元,通常是4-8MB大小。
page, 最小可编程单元(例如写入),通常是8-16KB大小。

notion: 编程操作在page中进行,而擦除操作在block中进行;block需要擦除后方可进行再编程。

Operation Area
Read Page
Write(Program) Page
Erase Block

Program/Erase Cycles

如果想要更新刚刚写入Flash的数据该怎么做?Flash不提供撤销/退回机制,只能擦除重写。

NOTE! 擦除操作将清空block中所有page的数据!因此,如果某些page中存在active data,必须对其备份或不做擦除。但是,鉴于Flash的读写次数受限(program erase cycle, or PE cycle),若每次想要更新page内的数据时都进行擦除,Flash的寿命将大大折损。

因此,一个更好的选择是,将含有无用数据的page标记为INVALID,将更新后的数据重写入一个空page,然后将数据取用操作都指向新的page,而被标为INVALID的旧page则使用一定机制进行回收(recycle),这一回收机制就是我们后续会讲到的flash translation layer。

picture: Updating a page in NAND Flash

尽管上述机制通过将数据移入新的page,推迟了擦除操作,但当block中没有空闲的page可供写入时,就必须执行擦除操作了。这就面临一个问题:擦除操作所需时间将会比读/写操作更长,如果不能很好的加以控制,势必会影响性能。

综上,NAND Flash主要有以下几个方面的问题:

1、不对称的性能。读的性能最好;写性能次之;擦除性能最差。
2、读写基本单元是Page页,而擦除基本单元是block块。
3、Block块内部只能采用顺序方式进行写入。
4、每次page页写的时候都需要进行擦除操作。
5、块擦除有寿命限制。


The Flash Translation Layer

原文链接:https://flashdba.com/2014/09/17/understanding-flash-the-flash-translation-layer/

背景:Flash的数据修改机制采用的策略是,将修改后的数据写到新的page中,而把原本的page标记为invalid,后续对其进行回收。

功能诉求:
将更新后的信息写到新的空page上,并将所有读请求都绑定到新地址;
确保新编程的page均匀分布,以保证flash的损耗是均匀的;
建立一个invalid pages的表格以供后续回收复用。

Flash Translation Layer (FTL)的功能:

  • Logical Block Mapping

逻辑块地址 (logical block address, LBA)使底层系统对高层的服务消费者不可见。在flash中该机制主要用于在更新时,当一个page被标记为invalid后,逻辑块地址可以重新映射到新page。

  • Wear Leveling*(可以重点关注的优化点)

我们预定义了一定数量的flash blocks,每一个block都可以执行一定数量的P/E循环,直至他们寿命到头。很明显,wear leveling算法的目的是均匀分配P/E cycle,以使所有block同时到达极限。

如果系统中所有的block都是定期更新的,那么就不存在问题,因为在page被标记为invalid和进行P/E cycle时,wear leveling会自动发生;但是,如果存在一些cold blocks,例如数据从不会更新的位置,我们就需要采取措施手动对数据进行重定位,否则这些块将永远不会损耗,这就意味着我们实际上在向系统增加写入负荷,并最终增加系统损耗

综上,我们对wear leveling evenly采取得越严苛,则系统损耗越大。但若系统损耗不够均衡,则会产生 hot and cold spots。通常情况下,我们需要对此进行均衡。或者也可以寻求写入均衡。

  • Garbage Collection*(可以重点关注的优化点)

回收不再需要(比如invalid)但尚未擦除的page。我们不能简单地擦除它们,因为在flash中擦除意味着要擦除整个block。所以,我们考虑block中剩余的内容,如果有必要,就将一些active data移动到其他地方。一旦一个block中没有active data了,就可以进行擦除。

问题在于,一个block中可能包含128或256个page,其中许多都包含了active data。我们可能需要耗费很多精力,才能回收少量的invalid pages,并且,和wear leveling类似,移动数据的操作可能反而会影响性能和endurance。所以,有必要寻找一个合适的平衡点。

下一节,我们将对garbage collection机制进行详细探讨。但需要注意一点:如果垃圾填满速度快于清楚速度,将会怎么办?若回收站空间不足,将是一个很严重的问题。我们需要确保这一情况不会发生。

  • Write Amplification

可以看到,上述的处理都会导致在flash media中的额外操作。Wear leveling会重定向inactive (cold) pages,从而确保它们和active (hot) pages损耗均衡。Page collection会将某些page移出即将要进行擦除的block。简而言之,由于主机上采取的操作,background中会产生一系列变化——我们称其为foreground。如果你要以foreground的视角看问题,比如一个数据库服务器访问flash内存,那么你不会看到在baceground中发生的操作。

在主机上使用何种操作系统监控工具是没有影响的,你只会看到foreground的I/O操作。这一特征很重要,因为flash的性能和endurance与foreground和background的操作数总和有关。

我们把这一现象称为write amplification,并且可以使用下述公式表示:$Write Amplification = \frac{Data Written To Flash}{Data Written By The Host}$

Write amplification的值越高,说明系统工作负载越大,这极有可能降低flash的性能和endurance。因此,在测试flash系统时,我们应当监测的不仅是存储系统的工作负载,也应当关注主机(host)工作负载。

FTL在哪里运行?

可以分为两种:host-based FTL(部分或全部功能在主机上运行) & array-based FTL,每种方法都各有优缺点。但是若我们在服务器上运行数据库,那么FTL与成本的相关性将变得非常小。毕竟,数据库服务器中的处理器和core-based licenses代价非常昂贵。在这种情况下,调度部分CPU cycle来管理flash是非常不明智的。

FTL是SSD固态硬盘的软件核心技术。正因为有了FTL,NAND Flash才能被当成硬盘来使用;文件系统才可以直接把SSD当成普通块设备来使用。它决定了一个 SSD 的使用寿命、性能和可靠性。

可供参考的优化点:在有限硬件资源的环境下如何实现 mapping ?如何实现 buffer 的管理?如何实现高效的 Garbage Collection ?如何实现磨损均衡 Wear-leveling ?如何实现 NAND Flash 芯片之间的数据冗余( RAID on Chip )?

其他可供参考的文献:
https://wenku.baidu.com/view/fcc35217a216147916112807.html (Intel: Understanding the Flash Translation Layer Specification)

https://www.tuicool.com/articles/ba6rmi 对mapping机制进行了初步探讨


Garbage Collection

原文链接:https://flashdba.com/2014/10/15/understanding-flash-garbage-collection-matters/

Why We Need Garbage Collection?

首先我们来考虑一下没有垃圾回收机制的flash系统会发生什么。

假设一个由6个blocks组成的非常简单的flash系统,每个block中包含10个pages。最开始,所有的page都是空的。

现在,我们向flash写入一些数据。写操作(write operation / program operation)发生在page层。现在,系统使用情况变成了下图所示。

可以看到,wear leveling算法将这些数据尽可能均匀地分布到了各个block中,但是,仍然存在一些block,其被占用的page数更多。实际上,wear leveling无需非常精确。

现在,我们来加一些数据。

现在系统达到了50%的使用率。同样的,为了wear leveling,数据都被尽可能地均匀分散。之后,flash translation会进行逻辑块(logical block)到物理块(physical block)的映射,因此,尽管数据已经被分散到不同的block中,在被应用程序调用时它们仍然表现得是连续的。

数据更新

有些时候,我们可能需要更新一些现存的数据。但是,如之前所介绍的,NAND flash不能更新page中的数据,只能擦除重用。因此我们先简单地把更新后的数据写到空page中,然后把旧page标记为invalid(stale)。逻辑块地址会重映射到新的page物理地址上。

可以看到,系统即将到达存储极限。在上图中,最左边的block中有两个stale pages (invalid pages),四个used pages。为了释放掉这些stale pages,我们需要将used pages拷贝到其他地方,然后擦除block。如果不这么做,继续写入数据,系统free pages将会越来越少,存储空间消耗殆尽,我们没有充足的空间来释放stale pages,这就意味着我们只能将存储系统 (flash system)转换为一个只读系统。但是,如下图所示,其实只有75%的空间存着真正有用的数据。这是否意味着我们永远不能利用100%的系统存储呢?

冗余机制

为了确保系统中始终有足够的空间来进行garbage collection,以及允许bad blocks, wear leveling等,许多flash system使用了冗余机制。

也就是说,设备内存的实际容量往往更大。这个冗余量并不固定,它不是一组专用的block或page,只是强制性的空间,用于防止上述意外的发生。

如何确定冗余量呢?对于读取密集型的工作负载,冗余量没必要太大;相反,对于某些特定工作负载而言,在SSD设备上进行硬限制并不是一个好的策略。可以根据工作负载来确定需要多少冗余。

接下来,我们将讨论更多垃圾收集的细节,特别是背景与前景垃圾收集的概念 (background versus foreground garbage collection),以及写入悬崖(write cliff)。


The Write Cliff

原文链接:https://flashdba.com/2014/11/24/understanding-flash-the-write-cliff/

可预测行为

系统行为的可预测性是非常重要的。如果知道一个系统任何时间的行为,我们就可以计划对应的操作。

当flash设备即将占满时,包含有用数据的page将要重定位,以进行block擦除操作。但是这里需要考虑两个问题:

  • 每个flash die一次只能执行一个操作(有些flash是每个plane上一次只能执行一个操作),这就意味着,如果你正在擦除block A,那么对block Z的读取操作将必须排队(queue),尽管这是die中与block A完全无关的另一个block。
  • 擦除操作实在太了。对于MLC flash,擦除操作可能需要3 milliseconds,而读取操作只需要~50microseconds。编程操作(写入操作)耗时介于读取操作与擦除操作之间。

因此,基于上述信息,若一个用户只是简单地以可预测的速率读取数据,将可能突然发现,延迟峰值会比预期的50us高出大约60倍(如果读取操作被排到擦除操作之后的话)。

Background vs Active / Foreground Garbage Collection

现在我们考虑,当用户操作(例如,主机读/写)排在背景操作(例如,flash translation layer所做的系列工作)之后时,所带来的性能问题。我们应当使所有的背景操作在不影响用户的情况下进行。

如果垃圾收集工作以不影响用户的active I/O操作的方式进行,我们就称其为背景垃圾收集 (background garbage collection, BGC)。BGC隐藏了擦除操作的影响,并且带来了更稳定、可预测的主机I/O时间。

反之,若某一时间段内,改变的数据量大于BGC可以维系的擦除量,那么系统可供写入的的free space将被耗尽。这种情况我们称其为前景垃圾收集 (foreground garbage collection, or active garbage collection, AGC)。在AGC中,用户I/O操作将不可避免地排在背景操作之后,若这些I/O请求不能及时执行,将会被操作系统kill掉。冗余机制能一定程度上缓解这一问题,但治标不治本,我们仍有可能会用完所有空余空间。

The Infamous Write Cliff

对write cliff的讨论一直很多,主要观点集中于如下几个方面:

Flash设备都会提供一定的冗余来作为缓冲区,如果我们更新的数据量大于BGC算法能处理的数据量,系统就将使用缓冲区,直至达到AGC。此时,若我们继续向系统写入数据,就将发现,系统延迟急剧增加,而IOPS (Input/Output Operations Per Second)将下降。

有两种可能的场景,flash设备不会发生write cliff:

  • Flash设备(大多是SLC)处理垃圾收集的速度足够快,且拥有足够大的冗余空间;
  • Flash有写入限额,也就是说,它们将永远无法达到耗尽冗余空间的地步。”A chain is no stronger than its weakest link”。