利用非均匀散列函数在非均匀访问存储器中放置记录的方法和装置

摘要

一种用于在非均匀访问存储器中存储记录的方法和装置。在多种实施例中，记录的放置定位于该存储器的一个或多个区域。这可利用的散列函数的不同排序列表来实现，以优先映射记录至存储器的不同区域，以实现一个或多个性能特性或考虑潜在的存储器技术的区别。例如，散列函数的一个排序列表可定位数据用于更快速的访问。散列函数的另一列表可定位期望具有相对较短有效期的数据。定位此类数据可显著改进擦除性能和/或存储器有效期，例如，通过在一个位置集中废弃的数据元素。因此，排序散列函数的两个或多个列表可改进访问延迟、存储器有效期、和/或操作速率中的一个或多个。

权利要求

1.一种存储用于存储系统的索引的方法，所述存储系统在磁盘存储上存储数据元素，所述索引由所述存储系统使用来访问所述存储系统所需的每个数据元素；

所述索引包括存储在非均匀访问存储器中的多个索引记录，每一个记录包含记录键和到所述磁盘存储上存储相关联的数据元素的物理块地址的指针，其中所述方法包括将新的索引记录插入所述索引中，所述方法特征在于插入新的索引记录包括以下步骤：如果新的索引记录具有第一类型，则散列值生成器通过将散列函数的第一排序列表中的第一散列函数应用到相关联的记录键来将所述第一排序列表应用到相关联的记录键以产生逻辑存储段空间中的逻辑存储段的候选逻辑存储段标识符，转译组件将非均匀访问存储器的第一区域的物理存储段位置映射到所述候选逻辑存储段标识符，并且如果在第一区域的物理存储段位置中没有可用的空位，则所述散列值生成器将所述第一排序列表中的第二散列函数应用到相关联的记录键以产生不同的候选逻辑存储段标识符；以及如果新的索引记录具有第二类型，散列值生成器通过将散列函数的第二排序列表中的第一散列函数应用到相关联的记录键来将所述第二排序列表应用到相关联的记录键以产生所述逻辑存储段空间中的逻辑存储段的候选逻辑存储段标识符，转译组件将非均匀访问存储器的第二区域的物理存储段位置映射到所述候选逻辑存储段标识符，并且如果在第二区域的物理存储段位置中没有可用的空位，则将所述第二排序列表中的第二散列函数应用到相关联的记录键以产生不同的候选逻辑存储段标识符；

其中所述第一排序列表中的第一散列函数寻址所述逻辑存储段空间中的逻辑存储段的子集以使得第一区域被定位，并且第一排序列表中的第一散列函数不同于第二排序列表中的第一散列函数，其中所述第二区域不同于第一区域且不限于所述第一区域。

2.根据权利要求1的方法，包括：

其中不同散列函数的逻辑存储段范围被映射到非均匀访问存储器的具有不同访问特性的特定存储器技术。

3.根据权利要求1的方法，其中：

第一记录类型在该存储器中相比第二记录类型具有更高的预期访问需求。

4.根据权利要求1的方法，其中：

第一记录类型在该存储器中相比第二记录类型具有更低的预期有效期。

5.根据权利要求1的方法，其中：

第一记录类型相比第二记录类型具有更高的预期引用需求。

6.根据权利要求1的方法，其中：

存储器的第一区域比该存储器的第二区域具有更快的访问特性。

7.根据权利要求1的方法，其中：

存储器的第一区域比该存储器的第二区域具有更长的预期存储器有效期。

8.根据权利要求1的方法，其中该非均匀访问存储器包括：具有不同的特性的计算机请储媒体，所述特性包括读访问时间、写访问时间、一次性写入限制、数据位置或特定地址访问时间，多个步骤的写入或读取处理以及/或者导致对不同的地址的访问显示出本质上不同的访问特性的其他约束。

9.根据权利要求1的方法，其中：

存储器包含闪存设备、相变存储器设备、固态存储器设备、DRAM和硬盘存储器设备中的一个或多个。

10.根据权利要求1的方法，其中：

存储器包含闪存设备，该闪存设备包括多个擦除块，每一个擦除块包含多个页，并且每一个页包含多个存储段。

11.根据权利要求10的方法，包括：

执行请除处理以生成空擦除块。

12.根据权利要求1的方法，其中：

存储器包含物理设备层，该物理设备层通过非均匀读取和写入访问来表征。

13.根据权利要求1的方法，还包括：

擦除第一区域，包括将第一区域中的有效记录重写至存储器中的另一位置，并擦除第一区域中的一个或多个块。

14.根据权利要求1的方法，包括：

修改以下一个或多个：

散列函数的第一排序组中的散列函数的数量或类型；

散列函数的第二排序组中的散列函数的数量或类型；以及

存储器的第一区域和/或第二区域的性能特性。

15.根据权利要求1的方法，还包括：

执行逻辑存储段操作，以用于对存储该记录的物理存储段位置的读取和写入。

16.根据权利要求1的方法，其中所述存储器包括闪存，并且所述方法包括：识别在存储器中相比第二记录类型具有更低的预期有效期的第一记录类型的记录；

将散列函数的第一排序列表应用到第一记录类型的记录键以将第一记录类型的记录优先映射到所述闪存的所定位的区域以降低在所述第一区域的擦除块清除期间的写入时间。

17.根据权利要求16的方法，还包括：

执行清除处理以在所述第一区域中生成空擦除块。

18.一种存储用于存储系统的索引的设备，包含用于执行根据权利要求1-17中任一项的方法的步骤的装置。

19.一种计算机系统，包括服务器，该服务器具有一个或多个处理器和存储用于由该一个或多个处理器执行的一个或多个程序的存储器，以用于执行根据权利要求1-17中任一项的方法。

20.一种计算机系统，包含处理器和程序代码，当被所述处理器执行时，所述程序代码将索引记录置于存储在非均匀访问存储器中的索引中，所述索引被存储系统使用来访问存储在磁盘存储上的每个数据元素，所述存储系统在所述磁盘存储上存储数据元素，其中每一个记录包含记录键和到所述磁盘存储上存储数据元素的物理块地址的指针，所述计算机系统包括：非均匀访问存储器，包含存储于该非均匀访问存储器的物理存储段位置中的索引记录；

散列值生成器；以及

转译组件；

其中该散列值生成器通过以下操作将新的索引记录插入所述索引中：如果新的索引记录具有第一类型，则通过将散列函数的第一排序列表中的第一散列函数应用到相关联的记录键来将所述第一排序列表应用到相关联的记录键以产生逻辑存储段空间中的逻辑存储段的候选逻辑存储段标识符，转译组件将非均匀访问存储器的第一区域的物理存储段位置映射到所述候选逻辑存储段标识符，并且如果在第一区域的物理存储段位置中没有可用的空位，则将所述第一排序列表中的第二散列函数应用到相关联的记录键以产生不同的候选逻辑存储段标识符；以及如果新的索引记录具有第二类型，则通过将散列函数的第二排序列表中的第一散列函数应用到相关联的记录键来将所述第二排序列表应用到相关联的记录键以产生所述逻辑存储段空间中的逻辑存储段的候选逻辑存储段标识符，转译组件将非均匀访问存储器的第二区域的物理存储段位置映射到所述候选逻辑存储段标识符，并且如果在第二区域的物理存储段位置中没有可用的空位，则将所述第二排序列表中的第二散列函数应用到相关联的记录键以产生不同的候选逻辑存储段标识符；

其中所述第一排序列表中的第一散列函数寻址所述逻辑存储段空间中的逻辑存储段的子集以使得第一区域被定位，并且第一排序列表中的第一散列函数不同于第二排序列表中的第一散列函数，其中所述第二区域不同于第一区域且不限于所述第一区域。

说明书

利用非均匀散列函数在非均匀访问存储器中放置记录的方法

和装置

技术领域

[0001] 本发明涉及计算机数据字典(dictionary)以及用于在非均匀访问存储器中放置记录的方法和装置。

背景技术

[0002] 索引(也称数据字典或关联阵列)是用于将被称为键的标识值映射至相关值的相关算法和数据结构，也称卫星数据。键及它的卫星数据的联结(concatenation)包含记录数据条目的一个实施例。

[0003] 在一个示例，索引被划分为存储段，每个存储段具有足够的空间用于N条记录数据条目，例如30条。存储段具有大小域，例如512字节，指示多少个记录可容纳于该存储段。记录数据条目能够以排序的顺序、时间顺序(其到达顺序)存储于存储段，或间接表可用于以任意顺序存储记录数据条目。多种算法已用于分配记录数据条目至存储段，典型地以均匀分发跨全部存储段的记录数据条目为目标。在某些示例，如果初始存储段被填充，多个等级的存储段被提供以处理溢出。

[0004] 多个应用需要具有大量条目的索引，因此需要千兆字节的存储器存储相关数据结构，并且需要很高的操作速率，例如，每秒成千上万的操作。某些存储器技术(如DRAM)可以提供必要的性能，但不是足够密集以经济地存储该大量记录。其他存储器技术(如磁盘技术)可具有该密度，但没有所需要的性能。因此，正需要一种存储器技术，该存储器技术能够同时满足存储大小和操作速率需求，用于生成和保持大量的记录。

发明内容

[0005] 根据本发明，一种新的方法和装置被提供用于在非均匀访问存储器中放置记录数据条目(例如，用于索引)。在多种实施例，记录数据条目(记录)的放置定位于存储器的一个或多个区域，其中不同区域可以包含不同类型的存储器。这可以利用散列函数的不同排序列表实现，以优先映射记录至存储器不同的区域，从而实现一个或多个性能特性或考虑潜在的存储器技术的区别。例如，一个散列函数的排序列表可定位用于更快速的访问的记录。另一散列函数的排序列表可定位期望具有相对较短有效期的记录。定位该记录可显著改进性能和/或存储器有效期，例如，通过在一个位置集中废弃记录。因此，两个(或多个)排序散列函数的列表可改进访问延迟、存储器有效期、和/或操作速率中的一个或多个。

[0006] 根据本发明的一个实施例，提供在非均匀访问存储器中存储索引记录的方法，每一个记录包含记录键，并且其中多个散列函数用于将记录映射至用于转译到所述非均匀访问存储器中的物理位置的逻辑存储段，该方法包含：

[0007] 将散列函数的第一排序列表应用到第一类型的记录的记录键，以优先将第一记录类型映射至该存储器的第一区域；以及

[0008] 将散列函数的第二排序列表应用到第二类型的记录的记录键，以优先将第二记录类型映射至该存储器的不限于第一区域的第二区域。

[0009] 根据一个实施例，保持存储段转译表以用于将逻辑存储段标识符映射至该存储器的物理存储段位置，其中该逻辑存储段标识符通过应用步骤生成，并且该表包含逻辑存储段标识符到物理存储段位置的映射，其中在该物理存储段位置处，相关联的记录存储于该存储器中。

[0010] 根据一个实施例，第一记录类型在该存储器中相比第二记录类型具有更高的预期访问需求。

[0011] 根据一个实施例，第一记录类型在该存储器中相比第二记录类型具有更低的预期有效期。

[0012] 根据一个实施例，第一记录类型相比第二记录类型具有更高的预期引用需求。

[0013] 根据一个实施例，存储器的第一区域比该存储器的第二区域具有更快的访问特性。

[0014] 根据一个实施例，存储器的第一区域比该存储器的第二区域具有更长的预期存储器有效期。

[0015] 根据一个实施例，非均匀访问存储器包含具有不同的特性的计算机存储媒体，所述特性包括读访问时间、写访问时间、一次性写入限制、数据位置或特定地址访问时间，多个步骤的写入或读取处理以及/或者导致对不同的地址的访问显示出本质上不同的访问特性的其他约束。

[0016] 根据一个实施例，存储器包含闪存设备、相变存储器设备、固态存储器设备、DRAM和硬盘存储器设备中的一个或多个。

[0017] 根据一个实施例，存储器包含闪存设备，该闪存设备包括多个擦除块，每一个擦除块包含多个页，并且每一个页包含多个存储段。

[0018] 根据一个实施例，该方法包括执行清除处理，以生成空擦除块。

[0019] 根据一个实施例，该存储器包含物理设备层，该物理设备层通过非均匀读取和写入访问来表征。

[0020] 根据一个实施例，存储器包括擦除第一区域，包括将第一区域中的有效记录重写至存储器中的另一位置，并擦除第一区域中的一个或多个块。

[0021] 根据一个实施例，该方法包括修改以下一个或多个：

[0022] 散列函数的第一排序组中的散列函数的数量或类型；

[0023] 散列函数的第二排序组中的散列函数的数量或类型；以及

[0024] 存储器第一区域和/或第二区域的性能特性。

[0025] 根据一个实施例，该方法包括执行逻辑存储段操作，以用于对存储该记录的物理存储段位置的读取和写入。

[0026] 根据一个实施例，提供一种计算机程序产品，包含程序代码，该程序代码当由处理器执行时，执行所描述的方法步骤。

[0027] 根据本发明的一个实施例，提供一种计算机系统，包括服务器，该服务器具有一个或多个处理器和存储用于由该一个或多个处理器执行的一个或多个程序的存储器，以用于执行所描述的方法步骤。

[0028] 根据另一本发明的实施例，提供一种计算机系统，包含：非均匀访问存储器，包含存储于该存储器的物理存储段位置中的索引记录，每个记录包含记录键，该系统包括：

[0029] 散列值生成器，用于使记录键散乱，以生成逻辑存储段标识符；

[0030] 转译组件，用于将逻辑存储段标识符映射至关联于所述记录键的记录被存储的存储器的物理存储段位置；以及

[0031] 其中该散列值生成器：

[0032] 将散列函数的第一排序列表应用到第一类型的记录的记录键，以优先将第一记录类型映射至该存储器的第一区域；以及

[0033] 将散列函数的第二排序列表应用到第二类型的记录的记录键，以优先将第二记录类型映射至存储器的不限于第一区域的第二区域。

附图说明

[0034] 应当理解，本发明包括两个或多个散列函数的排序列表，以用于优先映射记录以选择存储器的区域。

[0035] 图1为本发明的一个实施例的示意性高级系统体系结构，说明通过应用散列函数的排序列表至记录键而在非均匀访问存储器中存储索引记录；

[0036] 图2为根据本发明的一个实施例的用于在存储器插入记录的处理的流程图；

[0037] 图3为根据本发明的另一实施例的用于查找记录处理的流程图；

[0038] 图4为根据本发明的另一实施例的用于删除记录的处理的流程图；

[0039] 图5为说明根据本发明的一个实施例的多种索引操作的示意性框图；

[0040] 图6A至6D说明了可用于本发明的数据结构和系统组件的多种实施例，图6A示出了存储段转译表，图6B示出存储段有效表，图6C示出了闪存中存储段的内容，而图6D示出了NAND闪存设备的组织；

[0041] 图7A为说明清除处理的一个实施例的示意性框图；

[0042] 图7B为说明清除处理的一个实施例的示意性框图；

[0043] 图8为在一个本发明的实施例使用的记录条目的示意性图示；

[0044] 图9为说明根据本发明的一个实施例的物理闪存芯片的一个示例的示意性框图，该物理闪存芯片具有多个裸片、擦除块、页和存储段；以及

[0045] 图10说明了用于处理和存储数据的总体系统配置的一个实施例。

具体实施方式

[0046] 现参考附图描述本发明的多种实施例。在如下描述中，出于解释的目的，多个特定细节被提出以提供本发明一个或多个实现方式的全面理解。然而，显而易见的是：本发明可在没有这些特定细节的情况下实施。在其他实例中，公知结构和设备在框图形式中显示，以便于描述本发明。

[0047] 如本申请所使用，术语“组件”和“系统”意图指代计算机相关的实体，为硬件、硬件和软件组合、软件，或执行中的软件。例如，组件可以是但不限于运行在处理器上的处理、处理器、对象、可执行程序、执行线程、程序、和/或计算机。以说明的形式，运行于服务器的应用和服务器可均为组件。一个或多个组件可驻留于执行的处理和/或线程，而组件可定位于一个计算机上和/或分布在两个或多个计算机之间。

[0048] 本发明还可说明为本发明处理的流程图。为简化说明，尽管以流程图形式显示的一个或多个方法被描述为一系列动作，但应当理解和领会，本发明不受动作的顺序限制，某些动作可根据本发明以不同的顺序发生和/或与所示出的和本文描述的其他动作同时发生。例如，本领域技术人员将理解和领会，该方法能够另选地被表示为一系列相互关联的状态或事件，例如在状态图中。此外，并非全部说明的动作都是实现根据本发明的方法所需要的。

[0049] 在本文公开的多种本发明的实施例中，术语“数据”和“数据元素”互换使用。如本文所使用的，数据是指不透明的数据集合，例如，任何顺序的符号(典型地标示为“0”和“1”)，其可被输入到计算机并在那里被存储和处理，或被传输至另一计算机。如本文所使用的，数据包括元数据、其他数据的描述。写入本文描述的存储系统的数据可为相同大小的数据元素、或可变大小的数据元素。数据的某些示例包括信息、程序代码、程序状态、程序数据、其他数据等。

[0050] 如本文所使用的“存储系统”可为任何系统或应用，以用于存储数据至存储器，例如可以是文件系统、块存储设备、或其他系统。存储系统可使用标识符或名称，来引用存储器中的每一个数据元素。在一个示例，名称为全局唯一标识符(GUID)，如数据内容的散列，优选为数据内容的密码散列或抗碰撞散列。其他命名约定也是可能的，只要每个数据元素在存储系统中具有许可重组存储至用户的数据的名称。在一个实施例，中央服务器生成名称。数据名称通常为固定长度二进制串，其意在由程序使用，而不是由人使用。全部数据的索引(有时称为字典或目录)可被存储系统需要，以便访问(定位)每一个数据元素。索引中的每一个记录可包含数据元素名称、其逻辑和/或物理位置(地址)、以及关于各个数据元素的其他信息。在一个实施例，每一个索引条目包括指针，该指针指向存储有数据对象的磁盘上的物理块地址。在一个实施例，固定算法可用于定位存储有数据对象的磁盘上的物理位置。

[0051] 根据本发明的一个实施例，提供数据放置方法和装置，以与在磁盘存储中存储数据的存储系统一起使用。该存储系统可包含例如文件系统、块存储设备、或用于存储数据的其他存储系统。写入该存储系统的数据典型地包含多个小的(例如，4KB)数据片段，本文互换地称为数据或数据元素，其数据可为相同或可变大小。

[0052] 如本文所使用的，非均匀访问存储器指具有不同的特性的计算机存储媒体，包括读访问时间、写访问时间、一次性写入限制、数据位置或特定地址访问时间、多个步骤写入或读取处理和/或导致对显示出本质上不同的访问特性的不同的地址访问的其他约束。非均匀访问存储器包括(如一个示例)异构存储器，即，视为单个逻辑和/或连续存储器的不同的计算机存储媒体的组合。

[0053] 如本文所使用的，计算机存储媒体包括易失性和非易失性媒体、可移除和非可移除媒体，以用于存储信息，如计算机可读指令、数据结构、程序模块、或其他数据。计算机存储媒体包括RAM、ROM、EEPROM、闪存或其他存储器技术、CD-ROM、数字多用盘(DVD)或其他光盘存储、盒式磁带、磁带、磁盘存储器或其他磁存储设备、或可用于存储所需信息并可由计算机访问的任何其他介质。

[0054] A.利用非均匀散列函数的记录放置

[0055] 图1为根据本发明的一个实施例的处理的高级示意性说明，该实施例利用非均匀多个N散列函数在非均匀访问存储器中放置记录。利用散列函数来使记录键K散乱，在这种情况下为三个，即，H0，H1和H2，每一个均产生逻辑存储段标识符。散列函数之一的H0不寻址逻辑存储段空间14中的全部存储段；这里H0寻址存储段0到n的子集，该子集少于全部存储段0到m。因此，图1示出了：对于键值(x)的散列函数：

[0056] H0(x)＝{0..n}

[0057] H1(x)＝{0..m}

[0058] H2(x)＝{n+1..m}

[0059] 并且对于任何键(x)

[0060] H0(x)〈〉H1(x)〈〉H2(x)

[0061] 当键K利用3个散列函数被散乱时，3个候选存储段标识符被生成。来自散列函数H0的第一存储段标识符可仅把第一少许存储段0..n作为目标。另一散列函数H1可把任何存储段作为目标，而H2可将不在可由H0生成的存储段地址范围内的存储段作为目标。这在图1由横跨用于散列函数H0的存储段0到n的第一条线30示意性地说明，第二条线31跨越用于散列函数H1的存储段0到m，而第三条线32跨越用于散列函数H的存储段n+1到m2。通过利用这样的非均匀散列函数的排序集合，至少一个散列函数覆盖了少于全部(子集)的存储段，一种方法被提供用于优选地映射记录键以在各种存储器技术中选择(定位)存储器区域，同时有效地利用存储器。逻辑存储段范围H0，H1和112可映射至具体的强调的存储器技术，例如具有不同的访问特性。它们还可映射至相同的存储器技术，但将特定存储段集中至有限的定义的存储器区域，由此增强性能和/或存储器耐久性。

[0062] 如在图1底部所示，一个或多个转译表16映射逻辑存储段空间14至非均匀访问存储器中的物理位置。在一个示例，存储器18包含不同的闪存技术，如MLC和SLC。SLC为一种NAND闪存类型，它包括单级单元(SLC)设备，其中每一个单元仅存储一个信息位。较新的NAND闪存技术利用多级单元(MLC)设备，它能够在每个单元存储一个以上的位。不同的闪存技术具有不同的性能特性。

[0063] 在第二示例中，均匀技术存储器20可以当在存储器20的一个区域集中特定数据(如由H0寻址的存储段的子集)的同时被使用，仍用于性能或其他原因(例如，有效期)。

[0064] 如进一步的示例，存储器技术22可包含多个闪存芯片，而由H0覆盖的逻辑存储段的子集可定位在闪存芯片中被分成条状的区域中的数据。条的大小可为多个擦除块大小，用于改进擦除性能。条可以在多个闪存芯片中上下移动。

[0065] 这仅仅是用于利用非均匀散列函数放置数据记录以选择该存储器的区域的三个不同非均匀存储器技术和不同方法的示例。

[0066] B.记录操作

[0067] 图2-4说明了根据本发明的一个实施例的三个类型的记录操作，分别用于插入、查找、和删除记录。

[0068] 图2说明了插入记录的方法40的一个实施例。从步骤41开始，记录被提供，该记录在该示例中包括记录键和相关数据。如先前描述，该类型的一种记录为索引记录，其中键被映射至位置。在其他示例，键被映射至访问许可。在另一示例，键被映射至表示数据被修改的最后时间的值。在另一示例，键被映射至数据的特性。数据本身存储于存储设备(未示出)，并且数据可被散乱以生成记录键。相关数据可以是对存储有数据的存储系统的物理块地址的指针。这仅仅是一个示例，本领域技术人员将理解存在此类记录的多种其他示例。

[0069] 在下一步骤42，基于记录类型而做出选择，在该示例中该记录类型为是否期望该记录为短期并且频繁访问，或另选地是否期望为长期(例如，永久的)并且偶尔访问。假设记录为第一类型，方法在图2左列向下进行至步骤43，其中散列函数的排序列表{H0，H2，H1}分配至该记录。接着用于在排序散列函数的列表中排列的处理44，在步骤45第一散列函数H0应用于键，这在46产生逻辑存储段数量0..n。接下来，逻辑存储段数量(其包含逻辑存储段标识符的一种形式)在步骤47被转译成非均匀访问存储器的物理存储段位置。接下来，在步骤48，物理存储段位置的内容被读取，以确定在该物理存储段位置中是否有可用的空位用于记录(步骤49)。如果存在，处理进入步骤50，添加记录至非均匀访问存储器中的物理存储段位置。接下来，在步骤51，存储段被重写，并且到物理存储段表(以下描述)的逻辑根据该变化而更新，处理完成。返回步骤49，如果物理存储段位置中没有可用空位，处理返回步骤44以将散列函数H2的排序列表的下一(不同于第一个)散列函数应用至该键。该第二散列函数H2为散列函数的排序列表的第二个，用于优先映射记录至非均匀访问存储器的第一区域。第二散列函数覆盖没有被第一散列函数H0覆盖的逻辑存储段空间中的存储段，即存储段n+1..m，并且在步骤56中，记录根据散列函数H2被分配至该空间的存储段之一。接下来，逻辑存储段标识符在步骤47中被转译成非均匀访问存储器中的物理存储段位置。在步骤
48，该物理存储段位置的内容被读取，并且在步骤49中确定该物理存储段位置是否存在可用空位。如果空位可用，处理进行到步骤50并添加记录至该存储段，在步骤51重写存储段并更新逻辑至物理存储段表，并且处理完成。另选地，在步骤49如果没有可用空位，则处理从步骤44以第三散列函数重复，否则，如果在57全部散列函数已被应用，则在步骤58表(索引)为满。

[0070] 返回在步骤42做出的选择，如果该记录类型为第二类型(例如，长期并且偶尔访问)则处理如前进行，但散列函数被应用的被分配的顺序(52)为{H2，H1，H0}，以优先映射该记录至存储器的第二区域。

[0071] 图3说明了根据本发明的一个实施例用于记录查找的处理70。从步骤71开始，键被提供用于查找处理。散列函数H0在72应用于该键，而在73，在0..n范围中的逻辑存储段标识符由散列函数H0引起。接下来，逻辑存储段标识符在74被转译成物理存储段位置，物理存储段位置的内容在75被读取，并且物理存储段的查找在76被针对该键的值而做出。如果在77中具有键值的记录在物理存储段中被找到，则在步骤90，处理返回该记录、即键和相关数据，并且处理完成。如果否，则处理在78继续(沿图3中部)以应用第二散列函数H2至该键，从而在79生成逻辑存储段标识符，用于在跨越剩余逻辑存储段空间的存储段n+1..m之一放置该记录。在80，逻辑存储段标识符被转译成非均匀访问存储器中的物理存储段位置，物理存储段的内容在81被读取，在83，物理存储段的查找被针对该键的值而做出，并且如果记录在83被找到，则在90记录被返回且处理完成。如果在83没有发现记录，则第三散列函数H1在84应用于该键，在85，产生的存储段标识符在存储段0..m之一放置记录，逻辑存储段标识符在
86被转译成物理存储段位置，物理存储段的内容在87被读取，在88在该存储段中查找该键的值，并且如果在89记录被找到，则在90记录被返回，处理完成。如果在89没有记录被找到，则处理在步骤91结束。

[0072] 图4示出了用于记录删除操作的处理92的一个实施例。从步骤93开始，键被提供用于查找处理，例如，根据图3所示的方法。如果记录在步骤94被找到，(例如，图3的步骤77，83和89之一)则处理继续到在95从物理存储段移除记录并按需重组该存储段。接下来，该存储段被重写并且逻辑在96被更新到物理存储段表(以下描述)，处理完成。如果没有记录在步骤94被找到，处理完成。

[0073] 本领域技术人员将会理解，对图2-4提出的方法以及其他方法的修改可用于记录操作，同时利用本发明的主题。因此，上述示例并非限定性的而仅仅是意图说明本发明的特定实施例。

[0074] 如先前描述的分类或选择步骤42可通过利用接收自其他处理的信息实现，以确定应用哪个散列函数，在该步骤42中记录可被分类以便应用不同的散列函数的排序列表至不同的类型的记录的目的。例如，文件系统写入某几种数据，如文件数据、元数据、位图(bitmap)、和目录。来自文件系统的每一个数据类型如此标示，以使本发明的处理能够使用这些数据类型以优先分配相关记录来选择存储器的存储位置。如一个示例，文件数据可分类为相对长期和偶尔访问，而文件系统元数据可分类为短期和频繁访问。类似地，存储系统本身将具有关于存储器中不同的区域的性能特性的信息，以用于选择步骤，该选择步骤基于记录的特性和存储器区域特性中的一个或多个来分配存储器中的存储位置。

[0075] 在一个实施例，本发明在降低闪存存储器设备的清除开支方面具有特殊优点。闪存典型地以512字节扇区读取，以8KB页写入，并且以1MB擦除块擦除。写入比读取慢，并且擦除比写入更慢。管理闪存的单元为512字节的存储段，并且存储段被随机读取、写入和更新。更新需要读取、修改和写入。闪存在不擦除的情况下无法重写，因此存储段中的任何有效数据必须在其它地方被写入以生成空存储段。

[0076] 清除为擦除块被检查并且好的数据被读取自擦除块并被放置在其它地方并空出擦除块的处理。这导致对系统的额外读取/写入，有时称为“写放大”问题。如果没有合适地管理，清除开支在设备带宽使用中变得比初始的写入流量更贵(例如，2-3倍或更高)。根据本发明，该问题通过定位记录来解决，该定位记录在闪存的被定位的区域中被更频繁地修改。通过将频繁修改(短期)数据映射至更窄的闪存区域，更少的数据需要在擦除块清除期间重写，因此减少了写放大问题。

[0077] C.系统体系结构、示例

[0078] 图5-9说明了系统和方法的一个实施例，用于访问存储于非均匀访问存储器的索引记录。该系统和方法的进一步细节描述于公开于2010年12月30日、标题为“可缩放索引”的、Bowden等的共同未决和共同所有的美国公开号2010/0332864，其在此通过引用整体并入本文。

[0079] 图5为用于实现利用存储段转译表517和缓存523的某些索引操作的系统体系结构的概览。在图5顶部，三个索引操作512-514示出针对查找函数515和转译函数516的可选的输入。第一索引操作512为“查找键”，用于从该键的记录条目返回卫星数据。第二索引操作513为“更新键的卫星数据”，用于更新(修改)键的记录条目。第三索引操作514为“插入新的键”，用于插入新的记录条目。

[0080] 所有三个索引操作首先执行查找函数515，其中某些散列函数应用于键f(key)以生成索引，这里是支持(例如，加速)散列表查找的逻辑存储段标识符。逻辑存储段标识符(索引)输入至转译函数516，其中逻辑存储段标识符的某些函数f(index)生成闪存526中的物理存储段位置。该转译函数由存储段转译表517实现，其为逻辑存储段标识符(如由索引算法提供)到目标闪存位置(闪存中的物理存储段位置)的映射。存储于闪存526的字典(索引)可包含将查找键(例如，对象名)映射至卫星数据(例如，对存储于磁盘的数据的位置指针)的记录。

[0081] 接下来，根据三个索引操作中的哪一个正在被执行(查找、更新或插入)，图5下半部示出的步骤中的一个或多个被执行。

[0082] 对于查找操作518，由转译函数识别的存储段条目从闪存中的目标存储段522通过缓存后备被读取530，(例如，如果目标存储段存储于缓存，则它可读取自缓存523而不是闪存526)。

[0083] 对于更新操作519，转译函数识别的存储段条目(原始存储段条目)从闪存(或缓存)的擦除块521a中的目标存储段522中被读取530，存储段被更新并移动532至缓存，并在后续的顺序写入524中，多个缓存存储段条目顺序地读取至闪存中的连续部分页集合、多个页和/或擦除块(例如新的擦除块521b)。处理然后将闪存中全部被移动的存储段的状态更新533为无效数据(例如，空出的或可用于裁剪操作)。

[0084] 对于插入操作520，目标存储段再次被读取自闪存并且被修改的存储段条目被移动534至缓存，再次用于后续的顺序写入524至闪存的新的位置。

[0085] 图5示意性地示出了缓存523，该缓存523用于在执行缓存存储段条目集合的顺序写入524到连续闪存存储段之前，收集多个存储段条目。在一个实施例，清除操作525用于创建空擦除块；该处理包括在清除处理期间在缓存中存储任何有效存储段(从擦除块)并且将闪存擦除块重新分配为空出。

[0086] 图6说明了本实施例中有用的数据结构的多种示例。该数据结构意图说明而不是限制。

[0087] 图6A示出了存储段转译表(BTT)300的一个实施例，该存储段转译表(BTT)300用于将逻辑存储段标识符(由索引算法生成)转译为物理闪存存储段地址。BTT表条目被示出为具有三个域：有效301；闪存物理存储段地址302；和扩展存储段状态303。存储段地址粒度(granularity)可以是闪存设备的最小写入大小，即，部分页写入(例如，用于SLCNAND)或页写入(例如，用于MLCNAND)。BTT为逻辑至物理存储段条目的1∶1映射。该表使得闪存存储段分配的重组能够进行，以实现更高随机性能(利用索引算法的随机读取和随机写入)。附加的状态信息可在第三域添加至BTT以使算法能够加速。

[0088] 图6B示出了存储段有效表(BVT)305的一个实施例。该表跟踪闪存中哪个物理存储段是有效的，以便管理将存储段清除为用于裁剪的块。如一个示例，标为有效的域306可为紧密位阵列(1位/存储段)。BVT大小为闪存存储段条目总数，只有其子集由BTT使用。

[0089] 图6C示出了闪存存储段309的一个实施例，该闪存存储段309具有包括于存储段中的多个记录310，311，312..，以及反向BTT指针313(到存储段转译表517的自索引)。因此，每一个存储段包含一个或多个记录和反向指针的集合，以用于当闪存存储段(例如，页)被插入、移动或删除时更新BTT。该存储段的每一个元素(记录或指针)可具有添加的冗余内容，如附加的ECC位，以改进数据结构的独立可靠性并显著增加存储设备的使用寿命。例如，可选的序列数域可添加至闪存存储段309，以用于在掉电事件期间执行数据一致性检查；还可提供其他优化标志。

[0090] 因为记录的大小相对于存储段的大小较小，本文提供了一个机会(可选)来实现在单个记录基础上附加的误差恢复信息。该可选的特征将通过增加可被校正的位误差和错误的数量改进解决方案的总体可靠性，因此增加潜在的存储技术的有效操作的有效期。

[0091] 图6D示出了包含多个擦除块316(1到m)的SLC NAND闪存存储器设备315的一个示例。每一个擦除块包括多个页317(1到N)。在该示例中，每个页为4KB，每个页包括多个存储段318(1到B)，每一个存储段为1KB。在该示例中，设备支持部分页写入。

[0092] 典型的闪存子系统包括多个闪存设备。NAND闪存设备在擦除操作之间顺序地一次写入给定块中的每个页(或部分页)，多个块可用于同时写入和读取。

[0093] 存储段表示闪存设备的最小写入大小。典型地，存储段可为页。如果允许部分页写入，则每个闪存页的一个或多个存储段可被提供，如四个部分页SLC NAND设备支持每页四个存储段。针对每个擦除块提供多个闪存页。每个闪存设备有多个擦除块，每一个块被独立擦除。

[0094] 图7A和7B说明了用于生成空擦除块的清除处理的一个实施例。该清除处理实现为更低级设备管理层的一部分。在该处理中，闪存擦除块中物理存储段的组(某些或全部)直接读取自闪存并且存储段有效表527用于确定擦除块中的哪个存储段有效。

[0095] 如图7A所说明，在第一步骤220，清除处理525读取完整的擦除块521a。在第二步骤222，清除处理使用存储段有效表527来标识有效的读取的全部存储段。在第三步骤224，对于每一个有效存储段，存储段中的反向BTT指针313用作到存储段转译表517的自索引，以将逻辑存储段标识符返回至清除处理。在第四步骤226，有效存储段存储于缓存523，其中每一个由其逻辑存储段标识符来索引。

[0096] 图7B示意性地说明了其中清除处理525首先读取所包含的物理存储段[94，97]的处理。在第二步骤，处理确定95和96处的存储段有效。在第三步骤，存储段95和96的逻辑存储段标识符、即标签23和49分别从存储段转译表517返回。在第四步骤，两个存储段95和96以及其各自的索引标签23，49移动至缓存523。

[0097] 图8示出了记录格式的一个示例。记录140总共32字节，包括用于存储指纹(键)的第一20字节域141。指纹可以是数据内容的密码散列摘要(cryptographic hash digest)，例如SHA-1散列算法。记录的域还包括两个字节的引用计数域142、五个字节的物理块地址域143、一个字节的标志域144、以及四个字节的杂项域(miscellaneous field)145。PBA域143包含对磁盘上存储的数据的物理块地址的指针，以用于指定的指纹141。引用计数跟踪对存储于磁盘的数据的引用次数。

[0098] 图9是一个实施例的闪存设备164的示意性说明，示出了存储段、页和擦除块的相对(表示性的)大小。这里物理闪存存储器设备为2GB大小的芯片(包)165。在该芯片上，有两14
个裸片(硅晶圆)166a、167b。在每一个裸片上，可存在2 个擦除块，每个擦除块167典型地为
64KB。页168是可被写入的最小大小，这里为4KB，并且确定存储段169的大小，也是4KB。

[0099] 先前描述的方法可实现于合适的计算和存储环境，例如，可运行于一个或多个计算机上的计算机可执行指令的环境。(例如)在分布式计算环境中，特定任务由远程处理设备执行，该远程处理设备通过通信网络链接，并且程序模块可位于本地和远程存储器存储设备。通信网络可包括全局区域网，例如，因特网、局域网、广域网或其他计算机网络。应当理解，本文描述的网络连接是示例性的，在计算机之间建立通信的其他方式也可使用。

[0100] 计算机可包括一个或多个处理器和存储器。计算机可还包括磁盘驱动和至外部组件的接口。多种计算机可读媒体可由计算机访问，包括易失性和非易失性媒体、可移除和不可移除媒体。计算机可包括多种用户界面设备，包括显示屏、触摸屏、键盘或鼠标。

[0101] 现参见图10，说明了用于计算机和多个磁盘存储设备之间的通信的通用系统配置700的一个示例。磁盘存储可为多种存储设备中的任一个，其中数据通过多种电子、磁、光或机械方法被数字地记录在一个或多个旋转磁盘(包括硬盘驱动、软盘驱动和光盘驱动)的表面上。CPU 702被示出为附接至系统存储器704，而系统总线706将CPU连接至芯片组708。芯片组经由IO总线710和多个IO插槽712连接至多种输入/输出设备的任一个，例如用于连接多个磁盘驱动716的驱动控制器。芯片组还可连接于其他存储设备718。该芯片组可包括视频端口720、网络端口722、鼠标端口724、键盘端口726等的一个或多个。

[0102] 以上的描述包括本发明的示例。当然，不可能描述出于描述本发明的目的的组件或方法的每个能够想到的组合，但本领域普通技术人员将会理解，本发明进一步的组合和置换是可能的。因此，本发明意图包含属于本公开和/或权利要求的全部改变、修改和变型。