CN112463647A - 使用散列来减小前向映射表的大小 - Google Patents

Abstract

本申请公开了使用散列来减小前向映射表的大小。本文描述了用于使用散列来减小SSD或其他存储装置中的前向映射表的大小的技术。确定用于存储与逻辑块地址相关联的数据的存储介质内的存储位置的物理地址。将所述数据写入所述存储位置，并且使用散列函数根据所述物理地址的表示计算出散列值，其中所述散列值的大小小于所述物理地址的所述表示，并且所述散列值指向所述存储介质中的多个单独的存储位置。所述散列值存储在关联于与所述物理地址的所述表示相对的逻辑块地址的所述前向映射表中。

Description

使用散列来减小前向映射表的大小

发明内容

本公开涉及用于使用散列来减小SSD或其他存储装置中的前向映射表的大小的技术。根据一些实施方案，一种用于减小前向映射表的大小的方法包括：确定所述存储装置的存储介质内的存储位置的物理地址，以存储与逻辑块地址相关联的数据，并将所述数据写入所述存储位置。使用散列函数根据所述存储位置的所述物理地址的表示计算出散列值，其中所述散列值的大小小于所述物理地址的表示，并且所述散列值指向所述存储介质中的多个单独的存储位置。所述散列值存储在关联于与所述物理地址的所述表示相对的逻辑块地址的所述前向映射表中。

根据另外的实施方案，一种存储装置包括：非易失性存储器，所述非易失性存储器包括多个存储位置；前向映射表，所述前向映射表用于将逻辑块地址映射到所述多个存储位置；以及控制器，所述控制器用于将主机的用户数据存储到所述非易失性存储器。所述控制器被配置为确定所述非易失性存储器内的存储位置的物理地址，以存储与逻辑块地址相关联的数据，并将所述数据写入所述存储位置。使用散列函数根据所述存储位置的所述物理地址计算出散列值，并将所述散列值存储在与所述逻辑块地址相关联的所述前向映射表中。响应于接收到指定所述逻辑块地址的读取命令，所述控制器基于所述逻辑块地址从所述前向映射表中检索所述散列值，并使用所述散列函数的逆根据所述散列值计算出多个物理地址。然后，控制器从与所述多个物理地址中的每一个物理地址相对应的所述非易失性存储器内的存储位置读取数据，并且基于与从所述存储位置读取的数据相关联的标头信息来确定将针对所述读取命令返回的与所述逻辑块地址相关联的数据。

根据另外的实施方案，一种计算机可读介质具有在其上存储的处理器可执行指令，所述处理器可执行指令在由存储装置的控制器的CPU执行时使所述CPU确定所述存储装置的存储介质内的存储位置的物理地址，用于存储与逻辑块地址相关联的数据。所述CPU使用散列函数根据所述存储位置的所述物理地址计算出散列值，其中所述散列值的大小小于所述物理地址的表示的大小，并且所述CPU将所述散列值存储在所述控制器的前向映射表中。响应于接收到指定所述逻辑块地址的读取命令，所述CPU基于所述逻辑块地址从所述前向映射表中检索所述散列值，并使用所述散列函数的逆根据所述散列值计算出多个物理地址。然后，所述CPU能够从与所述多个物理地址中的每个物理地址相对应的所述存储介质内的存储位置读取数据，并且基于与从所述存储位置读取的数据相关联的标头信息来确定将针对所述读取命令返回的被映射到所述逻辑块地址的数据。

在阅读以下具体实施方式并查看附图时，各种实施方案的这些和其他的特征和方面将变得显而易见。

附图说明

在以下具体实施方式中，参考了构成本文的一部分的附图，并且通过例示的方式示出了具体的实施方案或实例。本文中的附图未按比例绘制。在所有的几幅附图中，相同的附图标记表示相同的元件。

图1是根据本文描述的实施方案的示出用于使用散列来减小SSD中的前向映射表的大小的一个例程的流程图。

图2是示出可以在其中实现本文描述的实施方案的例示性存储装置的部件的框图。

图3是根据本文描述的实施方案的示出NAND闪存管芯的实例性存储布局的框图。

图4是根据本文描述的实施方案的示出SSD中的前向映射表的细节的数据结构图。

图5是根据本文描述的实施方案的示出用于在前向映射表中存储物理位置地址的格式的细节的框图。

图6是根据本文描述的实施方案的示出用于对用于存储在前向映射表中的物理地址进行散列处理的一种方案的细节的框图。

图7是根据本文描述的实施方案的示出NAND闪存中的页面的一种布局的细节的数据结构图，其包括用于页面数据的元数据。

图8是根据本文描述的实施方案的示出用于运用散列的物理地址来执行从存储装置的读取以减小前向映射表大小的例程的流程图。

具体实施方式

以下详细描述针对用于使用散列来减小固态驱动器(“SSD”)或其他存储装置中的前向映射表的大小的技术。在当前的面向性能的SSD中，前向映射表将主机的逻辑块地址(“LBA”)转换为闪存介质中的物理位置，前向映射表被视为不可压缩的数据格式，因为它必须将所有可能的LBA一对一地映射到所有可能的物理位置。因此，随着由装置支持的LBA空间的大小和/或装置的物理存储容量的增加，前向映射表的大小必须成比例地缩放。例如，在支持4KB LBA块大小的32TB SSD中，前向映射表的大小可以为32GB。因为整个前向映射表可以被存储在控制器的DRAM中，所以控制器中的DRAM存储器的成本大大增加。

减小前向映射表的大小的一种选择是将多个LBA组合成被称为映射单元(“MU”)的二级构造。每个MU包括逻辑上连续的LBA，使得集合始终被映射到同一位置。例如，如果将8个LBA分配给每个MU，则前向映射表必须仅跟踪每个MU的位置，并且其大小减小8倍。然而，因为必须为每个LBA更新重写整个MU，所以该方法可能导致写放大显著增加，这对SSD的性能和寿命具有不利影响。另一种选择是使用分层前向映射，其中前向映射表的主层存储在控制器的DRAM中，而第二层和第三层存储在闪存介质中。当目标LBA的物理位置当前在DRAM中不可用并且必须从闪存介质中获取时，该方法可能会增加主机读取操作的延迟，从而影响驱动器的性能。

以上两种选择均试图通过减少在任意给定时间存储在DRAM中的条目的数量来控制前向映射表的垂直大小。然而，随着SSD和其他存储装置的物理容量增加，存储在前向映射表的每个条目中的物理地址的大小也随之增加，从而增加了表的水平大小，因此需要更多的DRAM进行存储。另外，如果增加的条目大小超出了控制器的CPU的字边界，则前向映射表的大小必须加倍以使每个条目的大小更大，或者CPU必须访问前向映射表在非字对齐边界上的条目，这在计算上是昂贵的，并且可能不利地影响读取性能。

根据本文所述的实施方案，一种用于减小前向映射表的水平大小(即，表的每个条目的大小)的方法涉及对物理地址进行散列处理以减小其大小。这引起每个前向映射表条目都指向闪存介质中的一定数量X的物理位置而不是单个物理位置。因此，在处理特定LBA的读取时，必须检索并检查物理介质中的总共X个位置以返回目标数据。在一些实施方案中，可以设计散列算法，以使得可以同时访问散列的条目所指向的X个物理位置中的每个物理位置，诸如驻留在不同的逻辑单元(“LUN”)上或沿着并行的访问信道。以此方式，如分层前向映射中的情况那样，读取操作不需要额外的时间，并且如增加MU大小的情况那样，不会引致写惩罚或写放大。因此，在对装置的性能或寿命的影响最小的情况下减小了前向映射表的大小。

图1根据本文描述的实施方案例示了用于使用散列来减小SSD或其他存储装置中的前向映射表的大小的一个例程。根据一些实施方案，例程100可以由SSD或其他存储装置的控制器运用前向映射表来执行，以将主机系统的LBA转换为存储介质中的物理地址。例程100包括步骤102，在该步骤中，由控制器接收写入命令。写入命令例如可以包括要写入的数据和用于写入的目标LBA。例程100从步骤102进行至步骤104，其中控制器分派存储介质中的物理位置以存储数据。这例如可以涉及在NAND闪存的块中定位空闲页。

例程100从步骤104进行至步骤106，其中控制器对所分派的物理位置的地址进行散列处理以减小其大小。例如，物理地址可以是36位值，表示NAND闪存的被分派的页面的信道、管芯、块和页面号的复合。由控制器所运用的散列算法可以将物理地址减少为32位散列值，以存储在前向映射表中。根据实施方案，如本文将更详细地描述的，所运用的散列算法还可以确保在读取目标LBA时从散列值解码的物理位置地址可以被并行访问，诸如驻留在不同的LUN上或沿着并行的访问信道。

例程100从步骤106进行至步骤108，其中根据物理地址得出的散列值由控制器存储在前向映射表中。前向映射表可以被存储在控制器的DRAM存储器中，并且散列值可以在包括写入命令中提供的目标LBA的值的索引处被写入该表中。应当理解，控制器还可以更新DRAM中和/或将目标LBA链接到要存储数据的物理地址的存储介质上的其他映射表和元数据。例程100在步骤108后结束。

图2和以下描述旨在提供可以在其中实现本文描述的实施方案的合适环境的一般描述。特别地，图2根据本文提供的实施方案示出了例示性存储装置200，诸如SSD装置，以及用于使用散列来减小存储装置中的前向映射表的大小的硬件、软件和部件。存储装置200包括存储介质210。在一些实施方案中，存储介质210可以包括一个或多个非易失性存储器(“NVM”)元件212。NVM元件212可以包括NAND闪存管芯。在其他实施方案中，存储介质210可以包括NOR闪存、垂直NAND(“V-NAND”)或3D NAND闪存、使用基于多晶硅或氮化硅技术的电荷存储单元的闪存、相变存储器(“PCM”)、赛道内存或任何其他类型的固态存储介质。

图3示出了包括多层NAND闪存管芯的单个NVM元件212的一种实例性存储布局。NAND闪存管芯包含被组织成多个阵列的大量存储单元。每个存储单元可以存储单个数据位(例如，单级单元(“SLC”))或多个位(例如，多级单元(“MLC”))。存储单元的每个阵列构成一个块，诸如块0至块N-1 304A-304N(通常被称为块304)，其中每个阵列的行构成该块内的页面，诸如页面0至页面K-1 302A-302K(通常被称为页面302)。块304可以分布在NVM元件212的多个层上，被称为平面306。特定NVM元件212的存储容量取决于NVM元件中存储单元的类型(即，每个单元存储的位数)、每行的单元数量(页面302)、每个块304的页面数量、每个平面306的块304的数量以及平面(层)的数量。常见的页面大小包括4KB、8KB或16KB，其中每个块304具有128、256或512个页面302。因此，块大小通常在128KB至8MB之间变化。

返回图2，存储装置200还可以包括控制器220，该控制器控制存储装置的操作。根据各种实施方案，控制器通过一个或多个装置接口214与NVM元件212接口。在一些实施方案中，装置接口214包括开放NAND闪存接口(“ONFI”)兼容接口。在另外的实施方案中，装置接口214可以包括以下中的一个或多个：异步接口；同步接口；单数据速率(“SDR”)接口；双数据速率(“DDR”)接口；切换模式兼容的闪存接口；上述接口中的任意接口的非标准版本；自定义接口；或用于定义与NVM元素212的通信的任何其他类型的接口。

装置接口214可以被组织成一个或多个信道，其中每个NVM元件212通过一个信道连接。每个信道可以支持一定数量P的NVM元件212。例如，装置接口214可以包括16个信道，其连接到被组织成四个存储体的64个NVM元件212。根据实施方案，可以使控制器220能够同时访问连接到单独的信道的NVM元件212。在另外的实施方案中，装置接口214可以被组织在一个或多个通道组中，其中每个通道具有一个或多个NVM元件212，或者一个或多个NVM元件212的任何其他组织可以被组织在装置接口214上。

控制器220可以包括中央处理单元(“CPU”)222，以监视和控制存储装置200的操作。CPU 222可以表示本领域中已知的一个或多个单核或多核处理器。控制器220还可以包括主机接口224，该主机接口允许存储装置200与一个或多个主机装置或其他部件(未示出)通信，诸如服务器计算机、个人计算机(“PC”)、膝上型计算机、平板电脑、游戏机、机顶盒、存储区域控制器或可以通信地耦合到存储装置200以在该存储装置中存储和检索数据的任何其他电子装置。在一些实施方案中，控制器可以经由开关/结构/中间控制器(未示出)或某个其他中间装置通过主机接口224连接到主机装置。根据一些实施方案，主机接口可以与串行ATA(“SATA”)接口标准兼容。在另外的实施方案中，主机接口224可以与以下中的一个或多个兼容：IDE接口标准、SCSI接口标准、SAS接口标准、PCIe接口标准、USB接口标准、CF接口标准、MMC接口标准、SD接口标准等。

控制器220可以通过格式化关联的数据并经由读取/写入/擦除信道230从存储介质210上的物理位置传输格式化的数据和将格式化的数据传输到所述存储介质上的物理位置，从而通过装置接口214来处理主机装置的读取命令和写入命令。读取/写入/擦除信道230包括必要的模块和/或电路，以擦除、编码、写入、读取和解码存储介质210的数据。根据实施方案，读取/写入/擦除信道230包括地址转换模块231，该地址转换模块提供由主机装置运用的数据寻址(例如，逻辑块地址(“LBA”))与由装置接口214用于存储介质210的物理位置寻址(例如，信道、管芯、块304和NVM元件212中的页面302)之间的转换。

根据一些实施方案，读取/写入/擦除信道230还可以包括缓冲器管理模块232，该缓冲器管理模块对用于在各种访问(读和写)操作期间临时存储与NVM元件212相关联的用户数据和元数据的缓冲器226进行管理。例如，缓冲器226可以在数据被编程到NVM元件212中时临时存储等待验证操作的写数据。在一些实施方案中，缓冲器226可以包括控制器220上的本地存储器，诸如静态随机存取存储器(“SRAM”)或动态随机存取存储器(“DRAM”)。在另外的实施方案中，缓冲器可以包括一个或多个外部SRAM或DRAM存储器和/或一个或多个NVM元件212中的缓冲区域。

在另外的实施方案中，读取/写入/擦除信道230包括纠错码(“ECC”)模块233，该纠错码模块在从NVM元件212读取数据或向所述NVM元件写入数据时提供纠错和/或冗余功能。例如，ECC模块233可以计算和写入ECC位以及被编程到NVM元件212中的数据。当从NVM元件212读回数据时，ECC模块233可以运用ECC位来校正任何读错误。在一些实施方案中，随着NVM元件212老化，由ECC模块233运用的ECC算法可以从较弱的代码逐渐变为较强的代码。

根据另外的实施方案，读取/写入/擦除信道230还可以包括垃圾收集模块234和损耗均衡模块235。垃圾收集模块234通过擦除NVM元素212的“陈旧的”或不再使用的块304来执行垃圾收集，以使其有资格用新数据重写。垃圾收集模块234还可以被使能在NVM元件212之内或之间移动存储的数据，以使闪存的较大的连续部分可用于写入。损耗均衡模块235工作以确保在NVM元件212中的所有块304上均匀地分布编程/擦除循环，以便在一定程度上避免在其他块之前过早地损耗、潜在地影响性能和缩短存储装置200的寿命。例如，损耗均衡模块235可以跟踪NVM元件212中的每个块304的循环计数，以便允许空闲块用于新写入的均衡使用。

在另外的实施方案中，读取/写入/擦除信道230包括缺陷管理模块236。当块对于数据存储变得不可使用或不可靠时，缺陷管理模块236可以检测并处理NVM元件212中的不良块304。这可以包括将块304标记为有缺陷，以及用NVM元件212中的备用区域代替块以将数据存储在有缺陷的块中。应当理解，缺陷管理模块236、损耗均衡模块235、垃圾收集模块234、ECC模块233、缓冲器管理模块232和地址转换模块231可以包括读取/写入/擦除信道230中的硬件电路、用于在CPU 222中执行的处理器可执行指令或者控制器220中的这些部件和其他部件的任意组合。

控制器220还可以包括用于存储处理器可执行指令、数据结构和其他信息的计算机可读存储介质或“存储器”240。存储器240可以包括非易失性存储器，诸如只读存储器(“ROM”)和/或闪存，以及随机存取存储器(“RAM”)，诸如SRAM或DRAM。存储器240还可以包括存储装置200的非易失性存储介质210的一部分。例如，存储器240可以存储固件，该固件包括执行存储装置200的操作所需的命令和数据。根据一些实施方案，存储器240可以存储处理器可执行指令，所述处理器可执行指令在由CPU222执行时执行例程100和800，以使用散列来减小SSD或其他存储装置中的前向映射表的大小，如本文所描述的。

存储器240还可以存储读取/写入/擦除信道230所运用的支持数据。根据一些实施方案，存储器240包含前向映射表242，地址转换模块231运用该前向映射表来查找被映射到在读取命令和写入命令中指定的LBA的物理地址。在一些实施方案中，前向映射表242可以存储在控制器220上的DRAM中用于高速地址查找，以改善存储装置200中的读取延迟。在另外的实施方案中，存储器240可以存储由控制器的模块所运用的其他信息，诸如由地址转换模块231和垃圾收集模块234所运用的附加映射表，由损耗均衡模块235所运用的擦除/循环计数表，和由缺陷管理模块236所运用的缺陷块列表，以及其他信息。

除了存储器240之外，环境还可以包括用于存储程序模块、数据结构和本文描述的其他数据的其他计算机可读介质，以用于使用散列来减小SSD或其他存储装置中的前向映射表的大小。本领域技术人员将理解，计算机可读介质可以是可由控制器220或其他计算系统访问以用于信息的非暂时性存储的任何可用介质。计算机可读介质包括以任何方法或技术来实现的易失性和非易失性、可移除和不可移除的记录介质，包括但不限于：RAM、ROM、闪存或其他固态存储技术；光盘ROM(“CD-ROM”)、数字通用盘(“DVD”)或其他光学存储装置；磁带盒、磁带、磁盘存储装置或其他磁性存储装置等。

应当理解，存储装置200的结构可以与图2所示和本文所描述的结构不同。例如，CPU 222、读取/写入/擦除信道230、存储器240以及存储装置200的其他部件和电路可以集成在通用集成电路封装内，诸如片上系统(“SoC”)，或者也可以将它们分布在多个集成电路封装中。类似地，提供例示的连接路径是为了进行例示而不是限制，并且为了清楚起见，可以省略一些部件和/或互连。还应当理解，存储装置200可以不包括图2所示的所有部件，可以包括图2未明确示出的其他部件，或者可以运用与图2所示的架构完全不同的架构。

图4根据本文描述的实施方案示出了SSD中的前向映射表242的实例结构。根据实施方案，前向映射表242包括由LBA索引的一定数量M的前向映射表条目的有序列表，诸如前向映射表条目402A-402M(在本文中被统称为前向映射表条目402)的有序列表，其中M表示基于LBA大小和存储装置的存储容量表示给主机系统的LBA数量。例如，在LBA大小为4KB的32TB SSD中，前向映射表242可以包括大约85.90亿条目。在每个条目为四个字节时，这可以引起前向映射表大小为32GB。

图5根据一些实施方案示出了用于在前向映射表条目402中在用于SSD的存储介质210中存储物理位置地址的例示性格式500。从图中可以看出，前向映射表条目402可以针对对应的LBA的存储数据的物理位置，对信道指定502、管芯编号504、块编号506和页面编号508进行编码。根据本文描述的实施方案，运用示出的格式500，用于SSD(包括16个信道，每个信道4个管芯(NVM元件212)，其中每个管芯具有128K的块304，每个块包括512个页面302)的存储介质210的唯一物理地址可以由32位值表示，以用于存储在前向映射表条目402中。

应当理解，如果增加了SSD的任何指定以支持增加的装置容量，则用于唯一物理地址的信道指定502、管芯编号504、块编号506和页面编号508的组合可以引起比图5所示的值更大的值。例如，如图6所示，SSD包括每16个信道，每个信道16个管芯(NVM元件212)，其中每个管芯具有包括1024个页面302的256K的块304，所述SSD可能需要36位物理地址值602来对用于存储介质210中的唯一物理位置的信道指定502、管芯编号504、块编号506和页面编号508进行编码。36位物理地址值602可以引起前向映射表242的大小显著增加，从而需要控制器220中的更多DRAM用于表的存储，因而增加了存储装置200的成本。另外，不能在现代CPU的字边界内高效地存储36位值，从而要求将每个前向映射表条目402的大小增加到48位或64位，进一步增加了前向映射表242的大小，或者要求实现CPU在非字对齐边界上访问前向映射表条目402的方案，这可能在计算上是昂贵的并且会对存储装置200中的读取延迟产生不利影响。

如图6还示出的，可以运用散列算法604将36位物理地址值602散列处理为更适合于存储在前向映射表242中的较小散列值606。根据实施方案，取决于获得的尺寸减小的位数，所得的散列值606可以指向存储介质210中的一定数量X的物理位置。散列算法还可以被设计为确保可以同时访问X个物理位置中的每个物理位置，以便减轻由于实施散列算法604而增加的读取时间。可以在散列算法604中组合不同类型的散列，以实现期望的大小减小，同时实现允许散列值606所指向的X个物理位置被同时访问的目标。

在一些实施方案中，散列算法604可以包括信道散列。例如，如果存储装置200包含16个信道，则物理地址值602的信道指定502部分将需要四位来唯一地标识信道。然而，如果移除了4位值的两个最低有效位，则剩余的两位将指示LBA的数据驻留在四个信道中的一个信道上。因为可以同时访问每个信道上的管芯(NVM元件212)，所以可以同时在四个信道上读取目标物理位置。因此，用于存储在前向映射表242中的散列值606的大小可以减小两位，而任何连接的主机装置在读取延迟方面几乎没有或完全没有增加。在其他实施方案中，可以从物理地址值602的信道指定502部分中丢弃一个、三个或任意数量的其他位，以实现前向映射表条目402的期望的大小减小。

在另外的实施方案中，散列算法604可以包括块散列。许多现代NAND闪存管芯允许向与管芯具有的平面306一样多的块304同时发出读取命令。因此，在实现具有四个平面306的NVM元件212的存储装置200中，控制器220可以同时从四个平面中的每个平面读取相同的块指定。在这种情况下，指示唯一平面306的位可以从物理地址值602的块号506部分中被移除。例如，如图6所示，块编号506的2个最高有效位可以指定该块驻留在四个平面中的哪个平面上。可以通过散列算法604从物理地址值602中移除这2个位，其中当检索到LBA数据时，同时从目标管芯的所有四个平面访问相同的块。因此，可以将存储在前向映射表242中的散列值606进一步减小另外两位的大小，而不会增加读取延迟。

通过将信道散列和块散列组合到散列算法604中，可以将36位物理地址值602散列处理为较小的32位散列值606，用于存储在对应的LBA的前向映射表242中。普通技术人员在阅读本公开时可以想到，可以将其他散列合并到散列算法604中以进一步减小前向映射表条目402的大小。例如，如果提供了用于同时访问存储介质的块304中的页面302的组或分区的存储装置200，则页面散列可以被包括在散列算法中以用于额外的尺寸减小。旨在将所有这样的散列包括在本公开的范围内。

在另外的实施方案中，各种散列方法可以与本文描述的其他方法相结合以同时在两个维度上减小存储装置200中的前向映射表242的大小。例如，一种方法可以是为包括存储装置和附接主机装置的系统选择与最低平均写入粒度相等的MU大小。在许多系统中，这将是每个MU 8个LBA，从而将前向映射表242的垂直大小减小了8倍。因为从性能的角度来看，跨平面同时访问块在本质上是“自由的”，所以添加块散列会将每个前向映射表条目402的大小减小基于每个管芯(NVM元件212)的平面数的位数，通常为两位(一位)或四位(两位)。然后，可以根据需要运用信道散列将前向映射表条目402的大小减小到32位以适合CPU222的字边界，然后可以运用分层前向映射来确保前向映射表242的分段(层)可以适合控制器220可用的DRAM。

根据实施方案，当存储装置200的控制器220从主机装置接收到读取命令时，可以从前向映射表条目402中检索由读取命令指定的LBA的散列值606，并且可以基于检索到的散列值和散列算法604的逆来确定目标数据的X个可能的物理位置地址。例如，如果指定信道2、管芯5、块2356和页面9的物理地址值602被上述散列算法604散列处理以生成图6所示的散列值606，那么针对读取命令的LBA从前向映射表242读取的该值将指示X＝16个目标物理位置，或者更具体地，在信道0-3上的管芯5的平面0-3上的块2356的页面9。然后，控制器220可以同时发起对信道0、1、2和3上的管芯5上的块2356的页面9的平面读取(即，同时读取所有四个平面306)，其中NVM元件212异步地将页面数据返回到控制器220。

为了确定所读取的哪个物理位置包含与所请求的LBA相对应的目标数据，控制器220可以检查与所返回的页面数据相关联的元数据，以确定哪个数据要返回到主机装置。根据一些实施方案，图7提供了NAND闪存中的页面302的例示性布局700。页面数据可以包括描述剩余页面数据的内容的元数据702。例如，如图所示，存储介质210中的8KB页面302可以包含与两个4KB LBA—LBA 2394280 704A和LBA 2394281 704B有关的数据。如还示出的，元数据702还可以为页面302中的每个LBA指定数据的位置(偏移)。当从16个同时读取返回页面数据时，控制器220可以检查与每个页面数据相关联的元数据702，以定位在读取命令中指定的匹配LBA，并选择目标数据以返回到主机装置。

如本领域技术人员将理解的，可能出现非常罕见的情况，其中对散列值606解码引起存储介质210中的多个单独的页面302的物理地址值602，其包含映射到同一LBA的数据。例如，用于LBA的新数据可能已在装置处被接收并在新的物理位置处被写入存储介质210，剩下旧的位置包含尚未通过垃圾收集过程释放的“陈旧”数据。根据一些实施方案，如果响应于同时读取而将来自映射到LBA的多个物理位置的页面数据返回到控制器220，则控制器可以检查与页面302相关联的垃圾收集单元的时间戳以确定哪个页面数据包含映射到LBA的最新数据以返回到主机。在其他实施方案中，时间戳或序列号可以存在于与页面302相关联的元数据702中，其可以指示要返回的最新数据。

图8根据一些实施方案的例示了用于运用前向映射表大小中的散列的物理地址从存储装置执行读取的一个例程800。根据实施方案，例程800可以至少部分地由SSD或其他存储装置200的控制器220中的地址转换模块231执行。在另外的实施方案中，例程800可以由存储装置的控制器、由外部处理器或在存储装置中执行存储处理的计算系统、或者由模块、处理器和装置的某种其他组合来执行。

例程800开始于步骤802，其中存储装置200的控制器220从主机装置接收读取请求，该读取请求指定了所请求的数据的LBA。例程800从步骤802进行到步骤804，其中地址转换模块231从前向映射表242查找指定LBA的物理地址散列值606。如本文所述，如果前向映射表242由于其减小的大小而被完全包含在控制器220的DRAM内，则地址转换模块231可以简单地通过LBA编号的索引从前向映射表中检索前向映射表条目402以获取散列值606。

接下来，在步骤806，地址转换模块231对散列值606进行解码以确定目标数据的X个可能的物理位置地址。这是通过反转用于生成存储在前向映射表242中的散列值606的散列算法604来实现的。例如，如果散列算法604对指定信道2、管芯5、块2356和页面9的物理地址值602进行了散列处理以生成散列值606，如上面关于图6所描述的，则反转散列算法将产生X＝16个目标物理位置，包括在信道0-3上的管芯5的平面0-3中的每个平面上的块2356的页面9。

例程800从步骤806进行到步骤808A-808X，其中控制器发出对从散列值606解码的所有X个物理位置地址的同时读取。在以上给出的实例中，控制器将同时对信道0、1、2和3上的管芯5上的块2356的页面9发起平面读取(即，同时读取所有四个平面306)。因为跨每个管芯(NVM元件212)的平面306的读取和对不同信道的读取都同时发生，所以存储装置将基本上仅引起一次tRead来执行所有读取操作808A-808X，其中“tRead”表示从将物理地址应用于NVM元件直到有效数据出现在NVM元件的输出上所经过的时间。

接下来，在步骤810，控制器220检查从每个读取操作808A-808X返回的页面数据，以查看其是否包含用于指定的LBA的目标数据。根据一些实施方案，这可以包括检查与页面302相关联的元数据702，以确定该页面是否包含映射到LBA的数据。如果从读取操作808A-808X中的一个读取操作返回的页面数据不包含映射到LBA的数据，则例程100从步骤810进行到步骤812，其中返回的页面数据被丢弃。如果页面数据被映射到LBA，则例程从步骤810进行到步骤814，其中控制器220确定是否返回了来自多个读取操作的被映射到LBA的页面数据。例如，这种情况可以是当LBA的新数据随后在新页面302中被写入存储装置200时，留下旧页面包含尚未通过垃圾收集过程释放的“陈旧”数据。

如果未返回来自多个读取操作的被映射到LBA的页面数据，则例程800从步骤814进行到步骤816，其中将映射到LBA的返回页面数据返回给主机装置。如果多个读取操作返回了映射到LBA的页面数据，则例程800从步骤814进行到818，其中控制器220检索与包含映射到LBA的数据的每个页面302相关联的时间戳。可以从与每个页面302相关联的元数据702、与该页面相关联的垃圾收集单元或者被保留在存储器240中或存储介质210上的一些其他元数据中检索时间戳。例程800从步骤818进行到步骤820，其中控制器返回映射到与最新时间戳值相关联的LBA的页面数据。例程800在步骤820后结束。

基于前述内容，应当理解，本文提出了用于使用散列来减小SSD或其他存储装置中的前向映射表的大小的技术。尽管本文中关于实现闪存的SSD总体上描述了实施方案，但是应当理解，本公开中描述的实施方案可以运用于实现以高性能读取操作为目标的任何存储技术的任何存储装置中。这可以包括SSD、混合磁和固态驱动器、磁硬盘驱动器、USB闪存驱动器、存储卡和盒带、用于闪存装置阵列的存储控制器、用于高速磁盘驱动器阵列的存储控制器等。上述实施方案仅是可能的实现实例，仅是为了清楚地理解本公开的原理而被提出。

本领域技术人员将理解，图4、图6和图7中示出的以及本文描述的数据结构仅出于例示目的而被提供，并且可以表示数据文件、数据库表、存储在计算机存储器中的对象、程序结构或本领域中公知的任何其他数据容器。数据结构中包括的每个数据元素可以表示数据文件中的一个或多个字段、数据库表的一个或多个列、对象的一个或多个属性、程序结构的一个或多个成员变量或本领域中公知的数据结构的任何其他数据单元。该实现是选择问题，并且可以取决于实现数据结构的存储装置200的存储器240、CPU 222、控制器220或其他元件的技术、性能和其他要求。还将理解，数据结构可以包含除了本文描述的附图中所示的那些数据元素之外的其他数据元素。

本文中作为方法、过程或例程的一部分描述的逻辑操作、功能或步骤可以实现为(1)在处理器或计算系统上运行的一系列处理器实现的动作、软件模块或代码部分，和/或(2)控制器或计算系统内的互连机器逻辑电路或电路模块。该实现是选择问题，取决于系统的性能和其他要求。如本公开领域技术人员将理解的，包括替代性实施方式，其中可以完全不包括或不执行操作、功能或步骤，其可以不按所示出或所讨论的顺序执行，包括基本上同时地或相反的顺序，具体取决于所涉及的功能。

还应理解，条件语言，诸如“可以(can)”、“可以(could)”、“可能(might)”或“可以(may)”等，除非另有明确说明，或者在所使用的上下文中以另外的方式理解，否则通常旨在表明某些实施方案包括而某些实施方案不包括某些特征、元素和/或步骤。因此，这样的条件语言通常不旨在暗示特征、元素和/或步骤以任何方式对于一个或多个特定实施方案是必需的，或者一个或多个特定实施方案必须包括用于在有或没有用户输入或提示的情况下确定这些特征、元素和/或步骤是否被包括在任何特定的实施方案中或要在任何特定的实施方案中被执行的逻辑。

可以在实质上不脱离本公开的精神和原理的情况下对上述实施方案做出各种变化和修改。此外，本公开的范围旨在覆盖以上讨论的所有元件、特征和方面的任何以及所有组合和子组合。所有这些修改和变型在本文中旨在被包括在本公开的范围内，并且对各个方面或者元素或步骤的各个组合的所有可能的权利要求旨在由本公开支持。

进一步的示例

示例1.一种在存储装置的控制器中实现的方法，所述方法包括以下步骤：确定所述存储装置的存储介质内的存储位置的物理地址，以存储与逻辑块地址相关联的数据；将所述数据写入所述存储位置；使用散列函数根据所述物理地址的表示计算出散列值，所述散列值的大小小于所述物理地址的所述表示，并且所述散列值指向所述存储介质中的多个单独的存储位置；以及将所述散列值存储在所述控制器的映射表中对应于与所述数据相关联的所述逻辑块地址的位置。

示例2.如示例1所述的方法，其中所述散列函数被配置为使得所述控制器能够在所述存储介质中同时访问所述多个单独的存储位置。

示例3.如示例1所述的方法，其中所述散列函数包括：散列处理所述物理地址的所述表示的信道指定部分。

示例4.如示例1所述的方法，其中所述散列函数包括：散列处理所述物理地址的所述表示的块编号部分。

示例5.如示例1所述的方法，其中所述映射表被存储在所述控制器的RAM中。

示例6.如示例1所述的方法，其中所述物理地址的所述表示的大小不允许将所述物理地址的所述表示存储在所述控制器的CPU的字边界内，并且其中所述散列值被存储在所述CPU的所述字边界内。

示例7.如示例1所述的方法，还包括以下步骤：响应于接收到指定所述逻辑块地址的读取命令，基于所述逻辑块地址从所述映射表中检索所述散列值；使用所述散列函数的逆根据所述散列值计算出所述多个单独的存储位置中的每个存储位置的物理地址；基于计算出的物理地址从所述多个单独的存储位置读取数据；以及基于与从所述多个单独的存储位置读取的数据相关联的标头信息，确定将针对所述读取命令返回的与所述逻辑块地址相关联的数据。

示例8.如示例7所述的方法，还包括以下步骤：确定从所述多个单独的存储位置中的两个存储位置读取的数据与所述逻辑块地址相关联；从所述两个存储位置检索与每个所述数据相关联的时间戳；以及基于与每个所述数据相关联的所述时间戳的较晚值，确定将针对所述读取命令返回的与所述逻辑块地址相关联的数据。

示例9.如示例1所述的方法，其中所述存储介质包括NAND闪存，并且所述存储装置包括固态磁盘(“SSD”)装置。

示例10.一种存储装置，包括：非易失性存储器，所述非易失性存储器包括多个存储位置；前向映射表，所述前向映射表用于将逻辑块地址映射到所述多个存储位置；和控制器，所述控制器用于将主机的用户数据存储到所述非易失性存储器，所述控制器被配置为确定所述非易失性存储器内的存储位置的物理地址以存储与逻辑块地址相关联的数据，将所述数据写入所述存储位置，使用散列函数根据所述存储位置的所述物理地址计算出散列值，将所述散列值存储在与所述逻辑块地址相关联的所述前向映射表中，响应于接收到指定所述逻辑块地址的读取命令，基于所述逻辑块地址从所述前向映射表中检索所述散列值，使用所述散列函数的逆根据所述散列值计算出多个物理地址，从所述非易失性存储器内与所述多个物理地址中的每个物理地址相对应的存储位置中读取数据，以及基于与从所述存储位置读取的所述数据相关联的标头信息，确定将针对所述读取命令返回的与所述逻辑块地址相关联的数据。

示例11.如示例10所述的存储装置，其中所述散列函数被配置为使得与所述多个物理地址相对应的所述存储位置能够由所述控制器在所述非易失性存储器中同时访问。

示例12.如示例10所述的存储装置，其中所述前向映射表被存储在所述控制器的RAM中。

示例13.如示例12所述的存储装置，其中所述散列值的大小小于所述物理地址的表示的大小。

示例14.如示例12所述的存储装置，其中所述物理地址的表示的大小不允许将所述物理地址的所述表示存储在所述控制器的CPU的字边界内，并且其中所述散列值被存储在所述CPU的所述字边界内。

示例15.如示例10所述的存储装置，其中所述散列函数包括：散列处理所述物理地址的信道指定部分。

示例16.如示例10所述的存储装置，其中所述散列函数包括：散列处理所述物理地址的块编号部分。

示例17.一种包含处理器可执行指令的非暂时性计算机可读存储介质，所述处理器可执行指令在由存储装置的控制器的CPU执行时致使所述CPU：确定所述存储装置的存储介质内的存储位置的物理地址，以存储与逻辑块地址相关联的数据；使用散列函数根据所述存储位置的所述物理地址计算出散列值，所述散列值的大小小于所述物理地址的表示的大小；将所述散列值存储在所述控制器的前向映射表中，所述散列值存储在所述前向映射表内与所述逻辑块地址相关联的位置中；响应于接收到指定所述逻辑块地址的读取命令，基于所述逻辑块地址从所述前向映射表中检索所述散列值；使用所述散列函数的逆根据所述散列值计算出多个物理地址；从所述存储介质内与所述多个物理地址中的每个物理地址相对应的存储位置中读取数据；以及基于与从所述存储位置读取的所述数据相关联的标头信息，确定将针对所述读取命令返回的被映射到所述逻辑块地址的数据。

示例18.如示例17所述的非暂时性计算机可读存储介质，其中所述散列函数被配置为使得与所述多个物理地址相对应的所述存储位置能够由所述控制器在存储介质中同时访问。

示例19.如示例17所述的非暂时性计算机可读存储介质，其中所述散列函数包括以下项中的一项或多项：散列处理所述物理地址的信道指定部分，以及散列处理所述物理地址的块编号部分。

示例20.如示例17所述的非暂时性计算机可读存储介质，其中所述前向映射表存储在所述控制器的RAM中。

Claims (10)

1.一种在存储装置的控制器中实现的方法，所述方法包括以下步骤：

确定所述存储装置的存储介质内的存储位置的物理地址，以存储与逻辑块地址相关联的数据；

将所述数据写入所述存储位置；

使用散列函数根据所述物理地址的表示计算出散列值，所述散列值的大小小于所述物理地址的所述表示，并且所述散列值指向所述存储介质中的多个单独的存储位置；以及

将所述散列值存储在所述控制器的映射表中对应于与所述数据相关联的所述逻辑块地址的位置。

2.如权利要求1所述的方法，其中所述散列函数被配置为使得所述控制器能够在所述存储介质中同时访问所述多个单独的存储位置。

3.如权利要求1所述的方法，其中所述散列函数包括：散列处理所述物理地址的所述表示的信道指定部分。

4.如权利要求1所述的方法，其中所述散列函数包括：散列处理所述物理地址的所述表示的块编号部分。

5.如权利要求1所述的方法，其中所述映射表被存储在所述控制器的RAM中。

6.如权利要求1所述的方法，其中所述物理地址的所述表示的大小不允许将所述物理地址的所述表示存储在所述控制器的CPU的字边界内，并且其中所述散列值被存储在所述CPU的所述字边界内。

7.如权利要求1所述的方法，还包括以下步骤：

响应于接收到指定所述逻辑块地址的读取命令，基于所述逻辑块地址从所述映射表中检索所述散列值；

使用所述散列函数的逆根据所述散列值计算出所述多个单独的存储位置中的每个存储位置的物理地址；

基于计算出的物理地址从所述多个单独的存储位置读取数据；以及

基于与从所述多个单独的存储位置读取的数据相关联的标头信息，确定将针对所述读取命令返回的与所述逻辑块地址相关联的数据。

8.如权利要求7所述的方法，还包括以下步骤：

确定从所述多个单独的存储位置中的两个存储位置读取的数据与所述逻辑块地址相关联；

从所述两个存储位置检索与每个所述数据相关联的时间戳；以及

基于与每个所述数据相关联的所述时间戳的较晚值，确定将针对所述读取命令返回的与所述逻辑块地址相关联的数据。

9.一种存储装置，包括：

非易失性存储器，所述非易失性存储器包括多个存储位置；

前向映射表，所述前向映射表用于将逻辑块地址映射到所述多个存储位置；和

控制器，所述控制器用于将主机的用户数据存储到所述非易失性存储器，所述控制器被配置为

确定所述非易失性存储器内的存储位置的物理地址以存储与逻辑块地址相关联的数据，

将所述数据写入所述存储位置，

使用散列函数根据所述存储位置的所述物理地址计算出散列值，

将所述散列值存储在与所述逻辑块地址相关联的所述前向映射表中，

响应于接收到指定所述逻辑块地址的读取命令，基于所述逻辑块地址从所述前向映射表中检索所述散列值，

使用所述散列函数的逆根据所述散列值计算出多个物理地址，

从所述非易失性存储器内与所述多个物理地址中的每个物理地址相对应的存储位置中读取数据，以及

基于与从所述存储位置读取的所述数据相关联的标头信息，确定将针对所述读取命令返回的与所述逻辑块地址相关联的数据。

10.一种包含处理器可执行指令的非暂时性计算机可读存储介质，所述处理器可执行指令在由存储装置的控制器的CPU执行时致使所述CPU：

确定所述存储装置的存储介质内的存储位置的物理地址，以存储与逻辑块地址相关联的数据；

使用散列函数根据所述存储位置的所述物理地址计算出散列值，所述散列值的大小小于所述物理地址的表示的大小；

将所述散列值存储在所述控制器的前向映射表中，所述散列值存储在所述前向映射表内与所述逻辑块地址相关联的位置中；

响应于接收到指定所述逻辑块地址的读取命令，基于所述逻辑块地址从所述前向映射表中检索所述散列值；

使用所述散列函数的逆根据所述散列值计算出多个物理地址；

从所述存储介质内与所述多个物理地址中的每个物理地址相对应的存储位置中读取数据；以及

基于与从所述存储位置读取的所述数据相关联的标头信息，确定将针对所述读取命令返回的被映射到所述逻辑块地址的数据。

Images