SSD |（七）FTL详解（中）

📚垃圾回收

🐇垃圾回收原理

• ✋设定一个迷你SSD空间：

  • 假设迷你SSD底层有4个通道（通道0-3），每个通道上各挂了1个Die（Die0-3，它们可并行操作），假设每个Die只有6个闪存块（块0-5），所以一共有24个闪存块。每个闪存块内有9个小方块，每个小方块的大小和逻辑页大小一样。
  • 24个闪存块中，我们假设其中的 20个闪存块大小为 SSD 容量，就是主机端看到的SSD大小；另外4个闪存块是超出SSD容量的预留空间，我们称之为OP。
    

• ⭐️顺序写入：顺序写入4个逻辑页，分别写到不同通道上的Die上，这样写的目的是增加底层的并行度，提升写入性能。用户继续写入数据，固件把数据交错写入到各个Die上，直到写满整个SSD空间。
  
  

• ⭐️SSD容量写满后启用OP：假设还是从逻辑页1开始写入。由于闪存不能在原位置原地更新，这个时候SSD会把新写入的逻辑页1-4写入SSD预留空间（OP）。如下图出现了深色方块，是因为逻辑页1-4的数据已更新，原位置上的数据就变为了垃圾数据。
  

• ⭐️整个内存空间写满：继续顺序写入，深色方块越来越多（垃圾数据越来越多）。当所有内存空间都写满（如下所示）后，SSD内部就需要进行垃圾回收了。
  

• ⭐️垃圾回收（顺序写）：就是把某个闪存块上的有效数据读出来并进行重写，然后把该内存块擦除，从而得到新的可用闪存块。

  • 如下图所示，块x上面有效数据为A、B、C，块y上面有效数据为D、E、F、G，其余方块为无效数据。垃圾回收机制就是先找一个可用块z，然后把块x和块y的有效数据搬移到块z上，这样块x和块y上面就没有任何有效数据了，将它们擦除就得到两个可用的闪存块。
    
  • 我们用不到一个闪存块的代价，获得了两个可用的闪存块，这就是垃圾回收的价值。
    
  • 当我们采用的是顺序写入，如上述，垃圾集中在块0上，上面没有任何有效数据，我们把它们擦除就可以腾出新的写人空间——SSD内部可以把新的数据写入垃圾回收完成的块0上了。
  • 顺序写，即使是闪存空间写满后的写，性能也是比较好的，因为垃圾回收可以很快完成（也许只要一个擦除动作）。

• ⭐️垃圾回收（随机写）

  • 现实中，用户还是可能随机写入数据，这个时候垃圾回收是挑选垃圾比较多的闪存块来回收。因为有效数据少，要搬移的数据少，这样腾出空闪存块的速度快，付出的代价也小。
    
  • 由于我们是同时往4个通道写数据，需要每个通道都有一个空闲的闪存块，因此，我们做垃圾回收时，不是回收某个闪存块，而是所有通道上都要挑一个。一般选择每个Die上块号一样的所有闪存块做垃圾回收。
  • 如上所示，块0上的垃圾数量最多，因此我们挑选块0作为垃圾回收的闪存块。回收完毕，我们把之前块0上的有效数据重新写回这些闪存块（这里假设回收的有效数据和用户数据写在一个闪存块，但在实际实现中，它们可能是分开写的）。
    
  • 此时，有了空闲的空间，用户就可以继续写入数据了。

---

• SSD越写越慢是有科学依据的：
  • 可用闪存空间富裕时，SSD无须做垃圾回收，因为总有空闲的空间可写。
  • SSD使用早期，由于没有触发垃圾回收机制，无须额外的读写操作，所以速度很快。
  • 之后SSD变慢了，主要原因是SSD需要做垃圾回收。
• SSD的垃圾回收性能跟用户写入数据的模式也有关：
  • 如果用户是顺序写，垃圾比较集中，利于SSD做垃圾回收；
  • 如果用户是随机写，垃圾比较分散，SSD做垃圾回收相对来说就更慢，所以性能没有前者好。

🐇写放大

• 垃圾回收的存在会引入写放大问题：用户要写入一定量的数据，SSD为了腾出空间写这些数据，需要额外做一些数据搬移工作，也就是进行额外写，导致的后果往往是SSD往闪存中写入的数据量比实际用户写入SSD的数据量要大。因此，SSD中有一个重要参数——写放大系数，计算公式：

  • $写放大系数（WA）=写入闪存的数据量/用户写的数据量$
  • 对空盘来说（未触发垃圾回收），写放大系数一般为1，即用户写入数据量与SSD写入闪存的数据量相等（这里忽略了SSD内部数据的写入，如映射表的写入）。
  • 在SandForce控制器出来之前，写放大系数最小值为1。但由于SandForce控制器内部具有实时数据压缩模块，它能对用户写入的数据进行实时压缩，然后再写入闪存，因此写放大系数可以做到小于1。举个例子，用户写入8KB数据，经压缩后，数据变为4KB，如果这个时候还没有垃圾回收，那么写放大系数就只有0.5。

• WAF计算，以前面介绍的垃圾回收为例：

  • 我们挑选每个Die上的块0做垃圾回收，一共36个方块，其中有12个有效数据方块，我们做完垃圾回收后，需对这12个有效数据方块进行写回操作，后面还可以写入24个方块的用户数据。
  • 因此，为了写这24个方块的用户数据，SSD实际写了12个方块的原有效数据，再加上该24个方块的用户数据，总共写入36个方块的数据，由写放大系数的定义可知：$WAF=36/24=1.5$。

---

• 写放大系数越小越好，越小意味着对内存损耗越小，闪存寿命越长。因此，SSD设计的一个目标是让写放大系数尽量小。减小写放大系数的三条思路：压缩办法（由主控决定），顺序写（可遇不可求，取决于用户写入负载）、增大OP（这个可控）。

• ⭐️增大OP减小写放大系数：

  • $OP比例=(闪存空间-用户空间)/用户空间$
  • 以前述SSD空间为例。假设SSD容量是180个小方块，当OP是36个小方块时，整个SSD闪存空间为216个小方块，OP比例是$36/180=20$。那么180个小方块的用户数据平均分摊到 216个小方块时，每个小方块的平均有效数据为$180/216=0.83$，一个闪存块上的有效数据为$0.83x9=7.5$，也就是一个闪存块上面平均有7.5个浅色方块和1.5个深色方块。为了写1.5个用户数据方块，需要写9个方块的数据（原有7.5个有效数据方块加1.5个用户数据方块），写放大系数是$9/1.5=6$。
  • 如果整个SSD闪存空间不变，还是216个小方块，调整OP至72个小方块，那么SSD容量就变成144个小方块。144个小方块的用户数据平均分摊到 216个小方块时，每个小方块的平均有效数据为$144/216=0.67$，一个闪存块上的有效数据$为0.67x9=6$，写放大系数是$9/3=3$。
  • 上面说的都是最坏情况（垃圾数据平均分排到每个闪存块上）。现实情况是，垃圾数据更多时候并不是平均分配到每个闪存块上，有些块上的垃圾多，有些块上的垃圾少，实际进行垃圾回收时挑选闪存块，挑的是垃圾多的，因此，实际写放大系数是小于前面的计算值的。

• OP越大越好，OP越大，意味着写放大系数越小，意味着SSD写性能和耐写性越好。但OP加大，意味着需要提供更多的额外闪存空间，也就意味着SSD成本要加大。
  

  • 消费级 SSD对成本敏感，不追求稳态性能和延时（即允许一边写入一边做垃圾回收），因此它们的OP比较小，一般为7%左右。
  • 企业级 SSD追求稳态性能和延时，为有好的稳态性能，它们一般都提供比较大的 OP，一般为百分之几十。
  • 因此，一个SSD最终OP的选择，需要在成本和写放大之间做平衡。

---

• ⭐️影响写放大系数的因素主要有：OP大小、用户写入的数据模式（随机写与顺序写）、垃圾回收策略（在挑选源闪存块的时候，如果不是挑选有效数据最少的块作为源闪存块就会增加写放大系数）、垃圾回收的时机（理论上，越晚做垃圾回收写放大系数越小，因为闪存块上的一些数据可能被后续用户重写，从而变成垃圾数据，越到后面垃圾数据越多，需要搬移的有效数据越少，写放大系数越小）、磨损均衡（为均衡每个闪存块的擦除次数，需要搬移数据）、数据刷新（数据搬移会增加写放大系数）、主控（带压缩和不带压缩）。

🐇垃圾回收实现

• ⭐️Step1：挑选源闪存块
  • 挑选源闪存块，常见算法是挑选有效数据最少的块（贪婪算法，绝大多数SSD采用的策略），这样需要重写的有效数据最少，写放大系数自然最小，回收一个块付出的代价最小。
  • 迅速找到有效数据最少的那个块，需要固件在写用户数据时做一些额外的工作，即记录和维护每个用户闪存块的有效数据量。
    • 用户每往一个新的块上写入一笔用户数据，该闪存块上的有效数据计数就加1；
    • 同时还需要找到这笔数据之前所在的块（如果之前该笔数据曾写入过），由于该笔数据写入到新的块，那么在原闪存块上数据就变为无效状态了，因此原闪存块上的有效数据技术应该减1。

  • 除贪婪算法外，还有其他的选源算法。比如，有些SSD在挑选源闪存块时，还把闪存块的擦写次数考虑其中，这其实就暗藏了磨损均衡算法（后面会详细介绍）。
  • 好处：可以把损均衡算法做到垃圾回收中来，不需要额外提供磨损均衡算法；
  • 缺点：这不是一种只看有效数据策略的垃圾回收，由于挑选的闪存块可能有效数据很多，因此写放大系数更大，垃圾回收性能更差。

• ⭐️Step2：把数据从源闪存块读出来

  • 【法①：位图表】前面提到，固件在往一个闪存块上写入逻辑页时，会更新和维护闪存块的有效数据量，因此可以快速挑中源闪存块。再进一步，固件不仅更新和维护闪存块的有效数据量，还给闪存块一个位图表，用于标识哪个物理页式有效的。在做垃圾回收的时候，固件只需根据位图表的信息把有效数据读出来，然后重写即可。

    • 固件把一笔逻辑页写入某个内存块时，该内存块上对应位置的比特位就置1。
    • 一个闪存块上新增一笔有效数据，就意味着这笔数据所在的前一个闪存块上的数据变为无效，因此需要把前一个闪存块对应位置的“比特位”置0。
    • 如用户空间写满后继续写入4个逻辑页，对应的位图表如下：
      
      

  • 由于有了闪存块上有效数据的位图，在进行垃圾回收的时候，固件就能准确定位并读取有效数据。位图存在的好处就是使垃圾回收更高效，但固件需要付出额外的代价去维护每个闪存块的位图。

    • 在上述例子中，每个闪存块只有36个逻辑页，但在实际中，每个闪存块有可能存在一两千个闪存页，每个闪存页可以容纳若干个逻辑页，因此，每个闪存块的位图需要占用不小的存储空间，这对带 DRAM的SSD来说可能不是问题。
    • 对使用DRAM-less的SSD来说，由于SRAM 受限，只能加载部分闪存块的位图到SRAM中，因此还需要进行位图的换入换出操作，这会给固件带来不小的开销，实现起来没有想象中那么简单。

  • 【法②：读取所有数据】如果没有每个闪存块的有效数据位图，SSD固件做垃圾回收的时候，可以选择读取所有数据，这时需要明确哪些数据需要重写。SSD 在将用户数据写入闪存的时候，会额外打包一些数据，我们称其为元数据（MetaData），它记录着该笔用户数据的相关信息。

    • 垃圾回收的时候，SSD固件把数据读取出来，获得与该笔数据对应的LBA（逻辑地址）。
    • 要判断数据是否无效，需要查找映射表，获得与该LBA对应的PPA（物理地址），如果该地址与该数据在该闪存块上的地址一致，就说明是有效的，否则该数据就是无效的。
      
    • 以上图为例，我们在某个源闪存块位置PPA x上读取数据，获得元数据，从而得到存在该位置的逻辑地址为LBA x，然后我们用LBA x查找逻辑地址到物理地址的映射表，得知最新数据存储在PPA y上。
    • 然后检查PPA x和PPA y是否一致，如果一致，说明存储在PPA x位置上的是与LBA x对应的最新数据，即为有效数据；否则为无效数据，垃圾回收时无需搬移。

  • 把源闪存块里的数据全部读出来的方式的缺点是显而易见：垃圾回收做得慢。

    • 不管数据是否有效都需要读出来，然后还需要查找映射表来决定该笔数据是否有效。
    • 这对带DRAM的SSD来说问题不大，因为其所有映射表都在DRAM中；但对 DRAM-less SSD来说，很多时候都需要从闪存里面把映射关系读出来，这是灾难性的。

  • 这种方式的好处就是SSD固件实现起来简单，不需要维护闪存块有效数据位图等额外内容，也不需要额外的 RAM 资源和固件开销。

  • 【法③：P2L表】还有一个折中的办法，就是在L2P（Logical to Physical）映射表外，再维护一张P2L（Physical to Logical）表。

    • 该表记录了每个闪存块写入的 LBA，该 P2L数据写在该闪存块某个位置（或单独存储）。
    • 当回收该闪存块时，首先把该P2L表加载上来，然后根据上面的LBA，依次查找映射表以决定该数据是否有效。有效数据会被读上来，然后重新写入。
    • 采用该方法不需要把该闪存块上的所有数据一股脑儿地读上来，但还是需要查找映射表以决定数据是否有效。因此，该方法在性能上介于前面两种方法之间，在资源和固件开销上也是处于中间的。
• ⭐️Step3：重写有效数据，即把读出来的有效数据写入目标闪存块。

🐇垃圾回收时机

• 当用户写入数据时，如果可用的闪存块小于一定阈值，这个时候就需要做垃圾回收，以腾出空间供用户写。这个时候做的垃圾回收为前台垃圾回收(Foreground GC)。这是被动方式的，是由于没有足够多可用的闪存块才做的垃圾回收。
• 与之相对应的是后台垃圾回收（BackgroundGC），它是在SSD空闲的时候，SSD主动做的垃圾回收，这样在用户写入的时候就有充裕的可用闪存块，不需要临时抱佛脚，从而改善用户写入性能。
• 但是，出于功耗考虑，有些SSD可能不支持后台垃圾回收，当SSD空闲后，直接进入省电模式，或者做少量的垃圾回收，然后进入省电模式。

---

• 上述两种垃圾回收是由SSD自已控制的。2015年8月15日，OCZ发布了一款采用SATA接口的企业级SSD——Saber1000HMS，它是首款具有主机管理SSD（Host Managed SSD，HMS）功能的SSD。所谓 HMS，就是主机通过应用软件获取 SSD的运行状态，然后控制SSD的一些行为。
  • 在 SSD内部运行着一些后台任务，比如垃圾回收、记录SSD运行日志等。这些后台任务的执行会影响SSD的性能，并且使SSD的延时不可预测。
  • HMS技术使主机能控制SSD的后台任务，比如控制后台任务执行或者不执行，什么时候执行，什么时候不执行。
  • 企业级的SSD相比消费级SSD，对稳定的性能和延时更加关注。后台任务的存在，使得 SSD性能和延时很难保持一致。HMS技术的出现，使得整个系统具有更稳定的性能和可预测的延时。
    

📚解除映射关系

• 对一个文件File A来说，用户看到的是文件，操作系统会为文件分配逻辑块，最终文件会写入SSD的闪存空间。当用户删除文件File A时，其实只是切断用户与操作系统的联系，即用户访问不到这些地址空间；而在SSD内部，逻辑页与物理页的映射关系还在，文件数据在闪存当中还是有效的。
  
• 用户删除文件的时候，如果主机不告诉SSD，SSD就不知道那些被删除的数据页是无效的，必须等到主机要求在相同的地方写入数据时才知道那些数据是无效的，才可以放心地删除。
• 由于SSD不知道这些删除的数据已经无效，在做垃圾回收的时候，仍把它当作有效数据进行数据的搬移，这不仅影响垃圾回收的性能，还影响SSD的寿命（写放大系数增大）。
• 用户删除文件时，系统需要发出一些特殊命令来及时告诉SSD哪些数据已经不需要了。在 SSD主机协议中有相应的命令来支持该功能，比如ATA中的Data Set Management（Trim命令）、SCSI里面的UNMAP命令等。一旦SSD知道哪些数据是用户不需要的，在做垃圾回收的时候就不会搬移主机删除的数据。
• ⭐️举个例子。

  • 主机通过 Trim命令告诉 SSD：逻辑页0-7数据删除了，你可以把它们当垃圾处理了。收到 Trim命令之前，逻辑页0-7有以下映射，它们分别写在物理地址PBA a~h上。
    

  • 一般FTL都有3张表：

    • FTL映射表记录与每个LBA 对应的物理页位置；
    • Valid Page Bit Map(VPBM)表记录每个物理块上哪个页上的数据是有效数据；
    • Valid Page Count(VPC)表则记录每个物理块上的有效页个数。

  • SSD 收到Trim命令后，为了实现数据删除，固件要按顺序执行如下所示步骤1~4。
    

  • Trim的基本实现逻辑就是这样，不同的SSD在实现时可能略有不同，比如如果没有有效数据位图，就没有步骤2。需要说明的是，上图所示步骤5~7是处理Trim命令后完成垃圾回收的操作，它们不是Trim命令处理的部分。Trim命令是不会触发垃圾回收的。

📚磨损均衡

• 磨损均衡，就是让SSD中的每一个闪存块的磨损（擦除）都保持平衡。
• ⭐️为什么需要做磨损均衡？
  • 闪存都是有寿命的，即闪存块有擦写次数限制。一个闪存块，如果擦写次数超过一定的值，那么该块就变得不可靠了，甚至变成坏块。
  • 如果不做磨损均衡，则有可能出现某些闪存块被频繁擦写，这些闪存块很容易寿终正寝。随着数据不断写人，越来越多的坏块出现，最后导致SSD在保质期前就挂掉了。
  • 相反，如果让所有闪存块一起来承担用户数据的写入，则能经受更多的用户数据写入。
• ⭐️一个闪存块寿命有多长呢？
  • 从SLC 的十几万擦写次数，到MLC的几千擦写次数，然后到TIC的一两千甚至几百次擦写，随着闪存工艺不断向前推，闪存的寿命是越来越短——SSD对磨损均衡处理算法的要求越来越高。

---

• 冷数据：用户不经常更新的数据，比如用户写入SSD的操作系统数据、只读文件数据、视频文件等。
• 热数据：用户更新频繁的数据。频繁更新会在SSD内部产生很多垃圾数据（新数据写入导致老数据失效）。
• 年老的块：擦写次数比较多的闪存块。
• 年轻的块：擦写次数比较少的闪存块。

---

• ⭐️动态磨损均衡：

  • 基本思想：将热数据（频繁更新的数据）写入年轻的闪存块，以避免频繁写入年老的闪存块，从而保持闪存块擦写次数的均衡。

• ⭐️静态磨损均衡：

  • 需求原因：冷数据（不经常更新的数据）一旦写入某个闪存块，由于有效数据多，很少被选作垃圾回收，导致这些块的擦写次数增加缓慢。而其他块由于经常写入用户数据，擦写次数增加迅速，造成擦写不均衡。
  • 基本思想：将冷数据移动到擦写次数较多的年老闪存块上，让这些年老的块得到休息，同时让年轻的块承担更多的写入操作。
  • 实现方法：固件通常使用垃圾回收机制来实现静态磨损均衡，选择冷数据所在的闪存块作为源块，并将有效数据读取后写入擦写次数较多的目标块。
  • 复制方式：也可以采用复制的方式，将冷数据从年轻块复制到年老块，不论数据有效性，都原封不动地搬移。这种方法实现简单，不需要更新映射关系，但可能会移动一些无效的垃圾数据。对于冷数据块来说，这种代价是可以接受的，因为这些块中的垃圾数据通常不多。

---

• 参考书籍：《深入浅出SSD：固态存储核心技术、原理与实战》（第2版）