固态硬盘中地址转换与数据访问的并行化设计及性能评估

ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月利用固态硬盘内部Wei Xie和Yong Chen，德克萨斯理工大学Philip C.橡树岭国家实验室固态硬盘（SSD）与传统硬盘相比，具有低延迟、高带宽和低功耗等特点，改变了存储系统的格局，为数据密集型应用提供了一种极具前景的存储解决方案SSD通过内部并行性（并行访问多个内部闪存芯片）和闪存转换层（FTL）实现这些理想特性，闪存转换层（FTL）确定数据存储在这些芯片上的位置，以便它们不会过早磨损。然而，当前最先进的基于缓存的FTL（如基于需求的闪存转换层（DFTL））不允许IO缓存器充分利用内部并行性，因为它们在逻辑到物理地址转换和数据访问之间施加了紧密耦合为了解决这一限制，我们引入了一个新的FTL设计，称为Diel-DFTL，与DFTL的工作解耦地址转换操作的数据访问。Diel-DFTL将地址转换和数据访问操作分离到不同的队列中，允许SSD对这两种类型的操作使用并发闪存访问我们也提出一个平行LRU快取置换演算法，以改善位址转换作业的并发性为了比较现有的FTL方法，我们提出了一个FTL的性能模型，并将其预测与DFTL和理想的页面映射方法进行比较。我们还使用真实的器件参数在SSD模拟器中实现了Diel-DFTL方法，并使用跟踪驱动的模拟来评估Diel-DFTL我们的评估结果表明，对于我们测试的真实IO工作负载，Diel-DFTL将整体性能提高了32%，对于合成测试工作负载，Diel-DFTL将整体性能提高了两个数量级我们还发现，Diel-DFTL能够以非常小的缓存大小实现合理的性能，并且它为具有大请求大小或高写入率的工作负载提供了最佳优势CCS概念：·硬件→内存和密集存储;其他关键词和短语：闪存转换层，SSD，并行性，DFTL，地址转换本材料基于美国政府支持的工作能源部，科学办公室，高级科学计算研究办公室这项研究得到了美国国家科学基金会的资助CNS-1162488，CNS- 1338078，IIP-1362134，CCF-1409946和CCF-1718336。本手稿由UT-Battelle，LLC根据合同编号DE-AC 05 - 00 OR 22725与美国能源部美国政府保留和出版商，通过接受出版的文章，承认美国政府保留一个非排他性的，付费的，不可撤销的，世界范围内的许可，出版或复制本手稿的出版形式，或允许他人这样做，为美国政府的目的。能源部将根据能源部公共获取计划（http://energy.gov/downloads/doe-public-access-plan）向公众提供这些联邦资助研究的结果作者地址：W。Xie和Y. Chen，Texas Tech University，902 Boston Ave，Lubbock，TX 79409;电子邮件：{wei.xie，yong.chen}@ ttu.edu; P. C.罗斯，1伯特利谷路邮政信箱。Box 2008 MS-6173，Oak Ridge，TN 37831-6173，USA;电子邮件：rothpc@ornl.gov。允许制作本作品的全部或部分数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知必须尊重作者以外的其他人所拥有的本作品组件的版权。允许用信用进行提取复制，或重新发布，张贴在服务器上或重新分发到列表，需要事先特定的许可和/或费用。从permissions@acm.org请求权限。© 2018计算机协会。1553-3077/2018/12-ART32 $15.00https://doi.org/10.1145/323956432ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月三十二：2W. Xie等人ACM参考格式：Wei Xie，Yong Chen，and Philip C.罗斯2018.在固态硬盘中利用内部地址转换。ACM Trans.Storage14，4，Article 32（December 2018），30 pages. https://doi.org/10.1145/32395641介绍近年来，来自企业以及科学和工程计算领域的许多应用已经变得高度数据密集。不幸的是，这一公认的趋势与系统处理能力和满足IO需求的能力之间不断扩大的差距同时发生。这些落后的IO功能可能会对应用程序可以操作的数据集的大小施加越来越严重的已经有许多研究试图通过软件方法来提高应用程序与这些软件方法相反，存储技术的进步导致IO性能的直接例如，在过去的十年中，使用NAND闪存技术的固态驱动器（SSD）已经成为缩小IO和计算之间的性能差距的有前途的解决方案。SSD非常适合用于为数据密集型应用程序设计的存储系统，与传统硬盘驱动器（HDD）相比，它们具有低延迟、高带宽和低能耗的特点。由于成本较高，SSD通常用作加速器，而不是硬盘驱动器的替代品。许多研究人员和工程师努力在这种混合系统或纯SSD存储中实现SSD的全部性能潜力。然而，SSDSSD硬件具有高度的潜在并行性，包含多个通道，每个通道多个封装，每个封装多个芯片，每个芯片多个平面尽管硬件并行度很高，但最近的研究表明，随着内部资源（例如，沟道、管芯和平面）增加。例如，最近对Sprinkler [23]的研究表明，由于某些IO访问模式和闪存级事务局部性引起的依赖性，随着裸片数量的增加，内部资源利用率降低，闪存级空闲急剧增加SSD无法实现其性能潜力的另一个主要原因是管理它们的软件，包括闪存转换层（FTL）、缓存管理算法、块IO调度算法和文件系统，没有很好地适应SSD硬件的实际特性。最近，基于缓存的FTL [16]越来越受欢迎，因为它们可以优于传统的基于日志块的FTL（BAST [26]和FAST [28]）。这些基于高速缓存的FTL在闪存中维护一个大型表，其中包含细粒度的逻辑到物理地址转换映射。为了控制访问和更新表项的成本，它们使用SSD的板载RAM的一然而，基于缓存的FTL仍然受到地址转换开销的影响-维护此映射表缓存的开销。当高速缓存命中率由于有限的高速缓存大小或工作负载中的低时间局部性（或两者）而低时，地址转换开销可能由于高速缓存条目的回写和替换所需的大量闪存访问而非常高。理想情况下，SSD架构（如图1所示）的内部并行性可用于通过允许对地址转换表条目的并发访问来减轻地址转换开销不幸的是，涉及地址转换和后续数据访问的数据依赖性使得基于高速缓存的SSD管理方法的并发访问具有挑战性当请求到达时，FTL调度程序必须查询映射表，利用固态硬盘内部地址转换机制三十二：3ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月图1. SSD组织示例。为了实现更高的带宽，SSD通常具有多个数据通道。 每个通道可以包含多个封装（在该示例中为两个封装），并且每个封装可以具有多个闪存芯片（管芯）。数据并行性在层次结构的每个级别都是可能的这种并行性称为SSD的内部并行性标识请求中涉及的数据的物理地址。对于保持粗粒度映射信息以使其完全适合于设备的在基RAM的传统FTL，与在闪存中访问所请求的数据本身所基于缓存的FTL的情况可能非常不同。如果请求的处理导致缓存条目替换，则地址转换的时间与数据访问的时间一样长更糟糕的是，SSD可能能够同时服务数据访问，因为其内部并行性，但不能并行处理先决条件地址转换操作，因此无法实现SSD的高度并行架构的性能潜力。为了解决基于缓存的FTL中地址转换开销的关键问题，我们提出了一种使FTL能够同时处理地址转换操作的技术，从而隐藏-从而节省了大量的地址转换开销。在我们的方法中，SSD将地址转换请求与数据访问请求分开排队，允许调度程序对请求进行排序或合并，充分利用SSD的内部并行性。与往常一样，特定的数据访问请求必须在其相关联的地址转换请求完成之前才开始，但是通过将地址转换请求与数据访问请求分离，调度器具有更好的能力来调度呈现给闪存的请求，使得它们可以被并行地服务。我们的技术是对现有的基于高速缓存的FTL方法（例如DFTL [16]）的并行性感知改进，因此我们将我们的方法命名为并行化-DFTL。基于我们以前的工作[48]，本研究做出了以下主要贡献：(1) 我们提出了一种创新的IO请求处理方法，称为Diel-DFTL，它通过利用内部并行性来减少FTL地址转换开销（第3节）。它包括两个主要部分：多队列请求排队机制和并行LRU缓存替换算法;(2) 多队列机制将基于缓存的FTL中的地址转换和数据访问分离，提高了地址转换操作的并发性;(3) 缓存-LRU修改了缓存映射表（CMT）条目的回收方式，改进了并发地址转换;三十二：4W. Xie等人ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月(4) 我们提供了一个性能模型，为SSD设计（第4节），并讨论了该模型的影响;(5) 我们模拟了一个概念验证的多队列-DFTL（多队列方案和并行-LRU算法）在FlashSim SSD模拟器中的实现（第5.1节）;以及(6) 我们比较了使用跟踪驱动模拟的Diel-DFTL与最先进的DFTL方法和页面映射方法的性能（第5节）。并对评价结果进行了分析和讨论。仿真结果表明了多队列调度方案和基于队列的LRU算法的有效性微基准测试结果证实，固态硬盘的并行度增加时，具有更好的性能可扩展性的并行-DFTL2背景和动机2.1SSD架构和NAND闪存与将数据存储在旋转磁性介质上的传统硬盘驱动器不同，SSD将数据存储在非易失性存储器中。目前大多数SSD使用NAND闪存芯片进行数据存储。NAND闪存芯片包含多个块，每个块由多个页组成。在当前SSD中使用的闪存芯片中，页面大小通常为2KB至16KB，块包含64至256个页面。例如，三星840 EVO SSD中使用的128Gb 19nm三级单元芯片具有8KB页面，每块256页[39]。虽然数据可以以页面粒度写入NAND闪存芯片或从NAND闪存芯片读取，但在写入之前必须擦除页面，并且可以擦除的最小存储量是块[20]。而且，每个块可以被擦除的次数是有限的。由于NAND闪存读取/写入粒度的差异以及其有限的寿命，SSD使用复杂的技术来管理闪存存储，如第2.2节所述。图1显示了SSD架构的示例大多数固态硬盘使用多个闪存芯片，几个IO通道，内部缓存和处理核心，以获得比单芯片设计更大的容量和更高的性能[4，8，21，24，36，38]。IO总线通道将封装连接到SSD控制器，并且每个通道可以将多个封装连接到控制器。总线通道相对简单，组合总线传输和闪存访问的延迟约为100μs，因此将其各自的带宽限制在40 MB/s左右。为了实现更高的带宽，多个闪存芯片（管芯）被组织成具有多个通道、封装、管芯和平面。例如，在图1中，存在八个通道，每个通道两个闪存封装，每个封装四个管芯，以及每个管芯四个平面（图中未示出平面）。像美光和三星这样的供应商已经提出了进一步在多个级别上暴露并行性的闪存设备[14]，包括通道级条带化，管芯级交错和平面级共享。为了利用这种内部并行性，大多数SSD使用例如，如果主机写入具有逻辑地址10、25、41和92的四个页面，则SSD将尝试将它们写入闪存中的四个连续物理页面，即使它们的逻辑地址不连续。SSD通常对物理闪存页面进行编号，以便它们在封装，芯片或平面上进行条带化，以促进并发访问[4]。2.2闪存转换层SSD使用闪存转换层来管理其闪存存储，以提高性能并延长设备寿命。由于NAND闪存芯片的页面大小的读/写粒度与其块大小的擦除粒度之间的不一致，并且由于其擦除和写周期的数量有限， 大多数FTL使用与基于日志的文件系统类似的不适当的方法[20]。当利用固态硬盘内部地址转换机制三十二：5ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月当FTL接收到页面写入请求时，它必须标识要在其中存储数据的空闲页面（即，自上次写入以来已被擦除的页面）。如果没有合适的空闲页面可用，则FTL必须启动垃圾收集[42]以合并活动页面并产生空闲页面。垃圾收集的开销很高：除了从牺牲块复制活动页面并将其擦除的成本之外，垃圾收集器可能在如何选择牺牲块以及出于性能和损耗均衡原因如何对活动页面进行分组方面非常复杂，但这种复杂性是以写入开销为代价的净效应是SSD写入操作与读取操作相比可能使用这种不适当的写入方法，给定逻辑页面地址处的数据可能随着时间的推移而具有不同的物理地址，因此FTL必须将逻辑地址转换为物理地址。理想情况下，SSD将其所有地址转换信息存储在板载DRAM中，以控制地址转换的成本然而，将这种地址转换保持在页面粒度需要大量的内存。例如，一个128GB的SSD，2KB的页面和4B的每个翻译表条目将需要256MB的翻译表。尽管许多当前的SSD配备有大DRAM（大于512MB），但DRAM空间通常用于缓冲数据，也用于提高所请求数据的传输性能 一些最近的SSD甚至具有无DRAM设计（具有小SRAM，例如，32MB，用于映射），以降低产品一般来说，在内存中维护完整的页级映射要么是不可能的，要么不是使用可用内存的最佳选择。为了控制转换表的大小以使其适合板上DRAM或SRAM，块映射方法以比页映射方法粗得多的粒度保持地址转换信息。然而，使用粗粒度的转换表往往无法提供足够的性能，特别是对于随机访问工作负载。为了解决维护映射信息的这些限制，已经提出了几种基于日志块的方法，包括BAST [26]和FAST [28]，以使用闪存块的一部分作为用页面大小的映射管理的日志块尽管这些方法优于传统的块映射，但它们仍然遭受合并操作的高成本，这发生在日志块中的数据需要迁移到数据块中时。基于需求的选择性缓存闪存转换层[16]（DFTL）保留了纯页面映射方法的性能和灵活性，但需要更少的RAM。DFTL将其完整的页面映射表保存在闪存中的转换块中，并将DRAM用于CMT，即页面映射表条目的高速缓存对于许多工作负载，这种方法提供了比混合映射方法更好的读写性能，因为工作负载通常表现出访问局部性和高CMT命中率。然而，如果工作负载具有低访问局部性或高速缓存太小，则在DRAM和闪存之间传输高速缓存的映射数据会有很大的开销与没有缓存未命中的工作负载相比，这种开销可能会使整体性能降低高达57%[22]。2.3DFTL地址转换DFTL处理地址转换的方式不同，这取决于它是服务于读请求还是写请求。图2（改编自参考文献[16]，也用于我们以前的工作[47]）说明了如何使用四个步骤处理读取请求(1) 请求到达，FTL提取其逻辑页号（LPN）;(2) 如果CMT已满，则选择牺牲条目，并且如果它是脏的，则将其写回到闪存中的翻译三十二：6W. Xie等人ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月图2. DFTL中的读取请求处理映射表缓存在缓存映射表（CMT）中当发生缓存未命中时，它需要映射加载和写回操作来替换和加载缓存的映射条目。 这些地址转换操作需要访问闪存和招致显着的性能下降。(3) 如果在CMT中丢失，则将所请求的页面的页面映射条目加载到CMT中;以及(4) 从由新加载的页面映射条目指示的物理数据块读取请求数据。在处理读请求时，映射操作必须在数据访问之前完成写操作所需的步骤是不同的。(1) 请求到达，FTL根据动态页面分配方案确定物理页面号（PPN）(2) 请求数据被写入物理数据块。(3) 如果CMT已满，则选择牺牲条目，如果它是脏的，则写回到闪存中的翻译页。(4) 被请求页面的页面映射条目被更新到缓存映射表和转换页面中特别地，用于写入数据的目标地址被动态地确定而不考虑映射信息。在数据写入完成之后更新映射表以实现容错。读序列中的第2步和写序列中的第3步被称为回写操作，而读回写操作仅在高速缓存已满并且牺牲条目是脏的（即，高速缓存的映射不同于存储在闪存中的映射）。当工作负载主要由读操作控制时，利用固态硬盘内部地址转换机制三十二：7ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月但是当写入频率高时不能忽略，因为每次写入都会弄脏CMT条目。回写操作是昂贵的，因为它在闪存上引入了写操作，与RAM访问相比，写操作具有显著更高的延迟更糟糕的是，如果没有空闲块可供写入，闪存写入也可能考虑到地址转换数据的垃圾收集和块写入的成本，DFTL回写操作是其高地址转换开销的重要贡献者。映射加载对于所有写操作是必要的，并且对于当CMT未命中发生时的读操作是必要的因此，对于时间局部性较差的工作负载，与时间局部性良好的工作负载相比，对闪存的读写操作大约是其两倍（参见图2）。2.4地址转换的优化为了减轻地址转换的开销，原始DFTL设计使用延迟复制和批量更新技术来延迟写入闪存的映射更新并减少写入闪存的次数当垃圾收集选择受害者数据块时，在受害者准备好被擦除之前，任何有效数据都应该被移动到新的块由于数据移动，映射信息应在CMT（如果缓存）和翻译页面（闪存）中更新。延迟复制方案仅更新CMT中的映射信息，并且稍后批量更新方案将脏映射条目批量写入翻译页由于大量映射条目共同位于同一转换页面上，因此可以在对转换页面的单个页面写入中组合许多更新，从而显著减少闪存写入计数。即使延迟复制和批量更新方案能够减少地址转换开销，但它们仅适用于垃圾收集或写入操作，而不适用于数据读取。在这项工作中，我们扩展了懒惰复制和批量更新的使用所有写操作。如写入请求处理序列的步骤4所示，一旦写入完成，映射条目就被更新到CMT和转换页中在采用延迟复制和批量更新之后，在步骤4中仅更新CMT，并且条目被标记为脏。稍后，脏条目可以批量更新到闪存中的翻译页面2.5解耦合地址转换延迟复制和批量更新减少了翻译开销，但它们只适用于步骤4在写操作（映射加载）中。它们对读写操作的回写和读取的映射加载没有帮助。但是，我们可以通过优化地址转换来优化这些操作。在图3中，案例1和案例2比较了DFTL地址转换和数据访问的成本与理想页面映射方法的成本，在理想页面映射方法中，整个页面映射表保存在板载DRAM中。该图显示了SSD处理三个传入IO请求R1、R2和R3时的时间轴在这两种情况下，地址转换必须在数据访问之前发生，我们假设内部并行性允许并行访问数据页对于页面映射（情况1），与访问数据所需的时间相比，地址转换所需的时间非常小，因为地址转换信息保存在设备上的DRAM中。相反，对于DFTL（情况2），地址转换涉及长延迟闪存访问，其持续时间可以与数据访问本身的持续时间相在没有重新排序的先进先出（FIFO）调度的情况下，地址转换操作和数据访问不能同时进行，因为转换操作在数据访问之间交错地址转换和数据访问操作必须在未修改的DFTL方法中顺序发生三十二：8W. Xie等人ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月图3. 将地址转换操作与数据访问解耦。 如果可能的话，地址转换操作被同时处理，因此在地址转换上花费的时间被显著地减少。大多数SSD使用基于写入顺序的负载平衡，以便将写入的第i个块分配给通道号（imodD）（也称为循环动态分配），其中D是通道的总数[4，8，14]。无论工作负载如何（顺序或随机），这种方法都可以提供令人印象深刻的写入性能，因为写入请求在可用通道中均匀分布，并且可以并发地处理向不同通道发出的请求（包括读取请求）。然而，原来的DFTL的地址转换和数据访问仅限于顺序处理，失去了实现这种改进的潜力。由于这些地址缓存管理操作与其关联的数据访问请求紧密耦合，并且必须在其关联的数据访问之前或之后完成，因此为它们提供服务可能会严重降低能够同时寻址请求数据的性能优势（参见图3，案例2）。如果地址转换操作可以从其关联的数据访问操作中解耦，并表示为不同的IO操作，则IO调度程序可以调度它们，以便它们可以并发发生，从而减少服务请求所需的总时间（参见图3，情况4）。请求重新排序是解决该问题的一种方法。例如，案例3显示了请求重新排序的影响。三个回写请求被放置在三个映射加载请求之前，映射加载请求之后是三个数据访问请求。因此，重新排序将转换请求与数据访问请求分开。在情况3中，请求被重新排序，但仍然按顺序处理。相反，在情况4中，分别同时处理三个回写、映射加载和数据访问请求。这导致服务这三个请求所需的时间显著减少尽管重新排序可以很好地解决问题，但它也有潜在的问题。例如，对于调度程序来说，弄清楚如何更好地重新排序请求是很复杂的重新排序要求调度程序确定特定的顺序来处理转换和数据访问请求，以实现更好的并发性，但不得违反操作之间的依赖关系因为利用固态硬盘内部地址转换机制三十二：9ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月满足这些依赖关系所需的分析可能是昂贵的，我们的新设计在不重新排序请求的情况下实现了地址转换。3并行DFTL的设计Diel-DFTL为两种类型的地址转换操作和数据访问操作使用多个请求队列它允许IO调度程序发出请求，以便地址转换和数据访问操作可以同时发生，通过利用SSD架构的内部并行性来减少服务请求所需的总时间3.1多队列地址转换解耦通过将与地址转换相关联的这些操作（映射加载和回写）添加到不同的队列，DFTL-DFTL实现了地址转换操作的解耦因为被写回的高速缓存条目的目标物理地址是动态确定的，并且与映射加载操作的物理地址无关，所以使用不同的队列允许独立地调度操作我们称这种方法为多队列。当闪存访问请求到达（读或写）时，如果需要，则Diel-DFTL将按照第2.3节中描述的步骤这三个请求被插入到三个相应的队列中，分别命名为挂起回写队列、挂起映射加载队列和挂起数据访问队列请注意，每个队列都有一个读和一个写区域，因为这两个操作的处理方式不同。每个队列中的请求仍按FIFO顺序提供服务。这三个队列中的每一个都有一个队列深度，表示它所能容纳的最大请求数。单独队列的使用使得与相同请求数据相关联的映射加载和数据访问能够实现更简单的流水线和同步当调度器算法1：用于读取的地址转换请求调度INPUT：挂起回写队列（Pend_Write_Q）、完成回写队列（Comp_Write_Q）、挂起映射加载队列（Pend_Load_Q）、完成映射加载队列（Comp_Load_Q）1： 当SSD运行时，2：如果Pend_Write_Q中存在请求，则3：将Pend_Write_Q中的IO调度到闪存4：将已完成的请求从Pend_Write_Q移动到Comp_Write_Q5：其他6：如果新的地址转换请求R到达，则7：将R添加到Pend_Write_Q和Pend_Load_Q中8：如果结束9：如果在Comp_Write_Q和Pend_Load_Q中存在请求，则10：在Pend_Load_Q11：从Comp_Write_Q中删除映射加载完成的请求12：将已完成的请求从Pend_Write_Q移动到Comp_Write_Q13：否则14：继续15：如果结束16：如果结束第17章：结束三十二：W. Xie等人ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月图第四章IO请求的地址转换和数据访问的分离以及并行感知调度。四个请求的写回和映射加载完成，数据访问正在进行。 假设这四个请求的回写、映射加载和数据访问都只需要一次并发的闪存访问。接收到一个请求时，它会向这三个挂起队列中的每一个添加一个条目。回写和映射加载操作的生成如图4所示。当每个写回和映射加载操作生成时，它被添加到相应的挂起队列中。3.1.1读取处理。 与DFTL类似，Diel-DFTL以不同的方式处理读和写操作。当为读操作提供服务时，挂起回写队列中的请求首先被处理队列中挂起的回写请求数取决于队列深度。请注意，写回请求不包括关于应该写回哪个缓存映射条目的信息，只是必须驱逐条目在选择受害者时，Diel-DFTL优先考虑干净的条目，因为它们不需要回写。如果没有足够的干净条目，那么它会尝试合并属于同一个翻译页面的脏映射条目，这样它就可以像原始DFTL方法一样进行批量更新（请注意，批量更新不用于DFTL中的回写。）因此，Diel-DFTL的缓存替换算法将从CMT中驱逐多个条目，以创建足够的空位用于添加的映射条目。我们在3.2节中更详细地描述了缓存替换算法。在选择牺牲条目并且写回操作完成之后，Pendel-DFTL可以处理来自挂起的映射加载队列的请求与回写操作类似，映射加载请求的并行化程度取决于所请求数据的位置。一系列顺序请求可能适合单个翻译页面，这将只需要读取一个闪存页面。例如，假设有四个请求，其逻辑地址为1、2、3和4，如图4所示。我们假设这四个页面请求中的每一个都需要回写和映射加载操作，并且这四个请求的相应回写写入四个不同的翻译页面，这些页面可以同时访问（参见图4，利用固态硬盘内部地址转换机制三十二：ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月算法2：用于读取的数据访问请求调度输入：挂起数据访问队列（Pend_Data_Q）、就绪数据访问队列（Ready_Data_Q）、已完成地址转换队列（Comp_Addr_Q）、并行级别（C）1： 当SSD运行时，2：当Comp_Load_Q中存在项目时，3：当Ready_Data_Q未满时，4：将Pend_Data_Q中的对应项移动到Ready_Data_Q5：如果Ready_Data_Q中存在项目，则6：调度对闪存的数据请求7：从Ready_Data_Q中删除已完成的请求8：其他9：继续10：如果结束11：从Comp_Load_Q12：结束时13：结束时14：结束时右上角）。在完成四次回写之后，请求1、2、3和4的映射条目因为页面1、2、3和4的映射条目位于同一转换页面（假设每个转换页面包含至少四个条目），所以仅需要一次闪存读取来加载所有四个映射条目。当所述数据转换-DFTL将地址转换请求添加到所述待决队列时，其还将对应的数据访问请求添加到所述待决数据访问请求队列以等待相关联的地址转换的完成因此，在服务来自这两个队列的请求时需要同步当完成地址转换操作（包括回写和映射加载）时，将对应的数据访问请求从未决数据访问队列移动到就绪数据访问请求队列，使得它们可以被发布到闪存。例如，在图4中，当请求1、2、3和4的对应的回写和映射加载请求在完成队列中时，请求1、2、3和4的数据从待决数据访问队列移动到就绪数据访问队列，并且然后可以经由通道C1、C2、C3和C4独立地访问，因为它们的物理地址对应于四个不同的通道。算法1和算法2详细说明了如何调度地址转换和数据访问请求进行读取。我们不描述底层的IO调度算法，这是因为Diel-DFTL是一种通用方法，不依赖于特定的IO调度算法。我们的技术支持对SSD内部资源的并发访问，但这取决于底层IO调度程序来排序和合并IO请求，以利用潜在的数据并行性。3.1.2写入处理。 与传统的DFTL一样，Diel-DFTL处理写请求的方式与处理读请求的方式不同。当服务于写入请求时，出于一致性原因，在数据写入完成之后，Diel-DFTL更新映射信息。写入的目标物理地址是动态确定的，并且必须存储在映射表中（在CMT和转换页中）。与读取不同，写入不会触发映射加载，因为映射条目是动态生成的，但它仍然可能导致回写操作，因为映射条目将存储在CMT中，并且当存储新条目时，该表可能已满。请注意，并行- DFTL使用延迟复制，因此无需将映射条目写入闪存上的转换当从CMT中驱逐条目时，脏条目可以批量写回三十二：W. Xie等人ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月算法3：用于写入的数据访问请求调度输入：挂起数据访问队列（Pend_Data_Q）、就绪数据访问队列（Ready_Data_Q）、挂起回写队列（Pend_Write_Q）、并行度（C）1： 当SSD运行时，2：当Pend_Data_Q中存在项目时，3：如果可能的话，4：将写入请求添加到Ready_Data_Q5：更新CMT中的映射信息，并在Pend_Write_Q6：批量调度回写（算法4）7：结束时8：结束时算法4：用于写入的地址转换请求调度INPUT：挂起回写队列（Pend_Write_Q），已完成回写队列（Comp_Write_Q），1： 当SSD运行时，2：当Pend_Write_Q中至少存在K个项目时，3：批量安排所有回写4：将回写请求添加到Comp_Write_Q5：结束时6：结束时由于处理读和写请求的差异，我们在数据访问和写回队列中区分读和写如果CMT中缺少所请求的页，则会生成回写操作，就像处理读操作一样在遍历数据访问队列中的请求之后，确定所需的回写次数当数据访问请求完成时，相应的回写请求可以批量进行算法3给出了处理数据写入的步骤。它首先完成数据写入，然后更新CMT中的映射信息。如果更新后的映射不在CMT中，则需要插入它，如果CMT已满，则需要写回以释放空间。回写请求被插入到Pend_Write_Q中，等待批量完成算法4描述了如何处理未决的回写请求注意，同时处理地址转换和数据访问操作并不总是有益的。例如，通过并行化具有小的随机IO的工作负载来实现良好的性能是困难的，因为地址转换目标地址和数据访问地址通常是不连续的，但也不对应于独立的通道。虽然通过允许地址转换开销被其他访问隐藏，DFTL可以提高许多类型的工作负载的性能，但是它不能提高这种随机工作负载的性能3.2利用SQL-LRU提高写回并发性上一节中讨论的多队列方案将地址转换和数据访问分离但是，它不能保证或提高利用并发闪存访问的机会对于这三种类型的请求，利用固态硬盘内部地址转换机制三十二：ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月−算法5：多路复用-LRUINPUT：所需的收回（回写）次数（num_req）1：whilenum_selectnum_reqdo<2：根据LRU选择条目e3：num_select=num_select+14：查找与e相同的翻译页面的所有条目e1到ec，然后查找LRU或der5：如果num_select+cnum_req，则<6：选择ecte1至ec7：num_select=num_select+c8：继续9：其他10：选择e1 到e（num_reqnum_select）11：num_select=num_req12：休息13：如果结束14：结束时OUTPUT：num_req要逐出的映射加载和数据访问由所请求的数据给出换句话说，这些请求本身决定了它们是否可以被并发处理.然而，回写操作的目标地址由高速缓存替换算法（例如，最少使用（LRU）。当请求回写时（由于脏缓存条目的驱逐），缓存替换算法从缓存映射表中选择条目。使用多队列方案时，多个写回请求被放置在挂起的写回队列中。当一定数量的请求Ne排队时，则必须从CMT中驱逐Ne个条目使用LRU等算法，由于现代SSD中的动态分配，可以并行写回选定的受害者条目然而，该方法没有识别当若干CMT条目属于同一闪存转换页时的情况，因此这些N个条目的回写将不会充分利用SSD的并发数据访问的潜力。为了进一步减少地址转换开销，我们提出了一个并行缓存替换算法，以实现更好的写回并发。该算法使用LRU策略，但在寻找受害者时也考虑条目是否属于同一翻译页面在算法5中详细描述的算法通过根据LRU选择条目（第2行）开始为了利用回写期间的并发性，它然后以LRU到MRU的顺序扫描高速缓存，以这些附加条目以LRU优先顺序排序。接下来，根据此类条目的数量有两种可能如果驱逐这些条目是免费的，则算法通过从前面选择这些条目来结束，直到找到所请求的受害者条目的数量（第9否则，该算法通过考虑LRU顺序中的下一个条目并从其开始重复该算法（第5-8行）来继续使用此算法，牺牲选择仍然遵循一般LRU策略，但尝试尽可能多地包括可以组合到单个页面写入中最初的DFTL设计使用批量更新方法从CMT中驱逐条目。当从CMT中驱逐条目时，批量更新还写回属于驱逐条目的同一翻译页的所有脏条目然而，与其驱逐这些肮脏的三十二：W. Xie等人ACM Transactions on Storage，Vol.号144、第三十二条。出版日期：2018年12月表1.LRU与非LRU Cache写回的比较LRU无源LRU写入减少缓存状态（8个条目）驱逐条目（4条目）缓存状态（8个条目）驱逐条目（4条目）十五，十七，九，零，十六，十二，八，四十六十二八四十五，十七，九，零，十六，十二，八，四[12]、[8、9]、[4]4/3二、一、四、三、十五、十七、九、零十五十七九零二、一、四、三、十五、十七、零、十六[0、3]、[16、17]2十二，十，一，九，四，八，二，三四，八，二，三十二，十，一，九，四，八，二，十五[2、1]、[15、12]2十三，十一，八，十，十六，十二，一，九十六十二一九十三，十一，八，十，十六，十二，九，四[9、10、8]、[4]2它假设CMT大小为8，每次我们需要驱逐四个条目。每个翻译页面包含四个映射条目（例如，条目0、1、2和3属于同一翻译页面）。粗体的页码是新缓存的条目。表2.双列LRU和双列LRU的比较无源LRULemel-LRU（4）缓存状态（8个条目）驱逐条目（4条目）缓存状态（8个条目）驱逐条目（4条目）十四，十三，十二，四，三，二，一，零【三、二、一、零】十四，十三，十二，四，三，二，一，零【三、二、一、零】八、七、六、五、十四、十三、十二、四[四、五、六、七]八、七、六、五、十四、十三、十二、四[12、13、14]、[4]七，六，五，四，八，十四，十三，十二[8]，[12，13，14]七六五四八[8]LRU只允许驱逐前四个LRU条目。条目，它将它们作为干净的条目保存在CMT中，以保持缓存的有效性。相比之下，Diel-DFTL不将回写条目保持在CMT中，因为它必须释放多于一个光点（即，要加载到CMT中的条目的数量），而原始DFTL一次只需释放一个光点表1给出了一个例子来显示双列LRU和LRU之间的差异在该表中，以转换页为单位管理具有缓存-LRU的缓存中的条目。例如，对于具有条目15、 17、 9、 0、16、 12、 8、 4的LRU高速缓存，缓存-LRU选择第一条目4进行替换。然后它选择倒数第二个条目8。因为条目9与条目8属于同一翻译页，所以条目9也被逐出。这样的分组使用算法5来完成。在我们显示的四种缓存状态中，由于分组回收条目，与LRU相比，缓存-LRU提供了更少的写入次数即使没有分组，它仍然可以并行写回4个条目缓存-LRU能够对它们进行重新排序和分组，使得它们可以被一起驱逐，特别是在属于同一转换页面的若干条目在缓存中被分离的情况下（例如，表中的最后一行所描述的缓存-LRU的一个限制是它可能过早地从CMT中逐出条目例如，在表1的最后一行中，因为条目11属于LRU条目9，所以条目11被移除，但是条目11实际上是第二个最近使用的条目。驱逐最近访问的条目可能会降低缓存的有效性（降低缓存命中率），并引入更多的缓存替换操作（回写和映射加载）。为了缓解这个问题，我们引入了一种称为有限的级联-LRU（L级联-LRU）的级联-LRU的变体在该变型中，选择与当前选择的牺牲条目属于相同翻译页面的条目的步骤被稍微修改。在所选择的LRU中，即使基于LRU顺序选择这些条目，也可以选择所有条目进行替换。在LRU-LRU中，仅可以选择LRU顺序中的几个顶部条目，这防止了一些条目被过早驱逐的情况如从表2中所见，索引-LRU总是将属于相同转换页面的条目分组（例如，表2中第四行中的4、5、6、7）。相比之下，LRUel-LRU不驱逐最近访问的这些条目（即，4、5、6、7是MRU 4条目