在闪存存储系统中延迟持久化索引元数据的方法

摘要

本发明提出一种在闪存存储系统中延迟持久化索引元数据的方法，包括以下步骤：S1：闪存存储系统在写数据时生成数据的数据类型和反向索引，并将反向索引一同写入闪存；S2：根据数据、数据类型和反向索引建立内存正向索引，并使用待持久化索引列表标记未写入内存正向索引的数据；S3：通过更新窗口跟踪尚未建立正向索引的数据；以及S4：当闪存存储系统发生故障时，根据更新窗口的数据类型和反向索引重构正向索引以恢复闪存存储系统的故障。根据本发明实施例的方法，通过反向索引延迟了正向索引的持久化，减少了数据写操作的延迟，避免了用于被索引数据与索引元数据的事务操作开销，同时降低了更新窗口元数据持久化带来的竞争延迟。

说明书

技术领域

本发明涉及闪存存储技术领域，特别涉及一种在闪存存储系统中延迟持久化索引元 数据的方法。

背景技术

闪存是一种电子可擦除可编程的非易失性存储器件。闪存以页为单位进行读写，以 块为单位进行擦除。随着编程擦除（Program/Erase，P/E）次数的增加，闪存单元贮存 电子的能力减弱，降低造成数据存储的可靠性。闪存的编程擦除次数有限，该问题也被 称为闪存的寿命问题。

在存储系统中，数据写操作通常包括数据更新以及元数据更新，后者用于记录数据 更新的位置或者记录数据修改的状态。例如，文件系统创建文件的操作在写入索引节点 （inode）之后需要在目录项（directory entries）中更新该创建文件的目录项。用于 索引的元数据需要及时持久化，否则被索引的数据在系统故障后不能被查找到，从而造 成数据丢失。索引元数据的更新既增加了写操作的延迟，也带来了闪存寿命和操作原子 性的问题。首先，数据写操作等待索引元数据持久化完成后返回，元数据持久化的延迟 增加了写操作的延迟。其次，索引元数据持久化操作加速了闪存存储系统中P/E的频率， 降低了闪存存储系统的寿命。由于闪存以页为单位进行读写，索引元数据持久化引入至 少一个闪存页的更新。频繁的元数据更新持久化也造成大量的额外闪存页的写。最后， 索引元数据的持久化也使得数据写操作的原子性保证更为复杂。文件系统等软件模块引 入事务等机制维护写操作的原子性，进一步加剧了闪存存储系统的性能及寿命问题。

发明内容

本发明的目的旨在至少解决上述的技术缺陷之一。

为此，本发明的目的在于提出一种在闪存存储系统中延迟持久化索引元数据的方 法。

为达到上述目的，本发明的实施例提出一种在闪存存储系统中延迟持久化索引元数 据的方法，包括以下步骤：S1：闪存存储系统在写数据时生成所述数据的数据类型和反 向索引，并将所述反向索引一同写入闪存；S2：根据所述数据、所述数据类型和反向索 引建立内存正向索引，并使用待持久化索引列表标记未写入所述内存正向索引的数据； S3：通过更新窗口跟踪尚未建立所述正向索引的数据；以及S4：当所述闪存存储系统发 生故障时，根据所述更新窗口的数据类型和反向索引重构正向索引以恢复所述闪存存储 系统的故障。

本发明的一个实施例中，还包括：当所述更新窗口的利用率超过阈值时，为所述更 新窗口分配新的更新窗口，并将所述更新窗口中已满的闪存块从所述更新窗口中移除。

本发明的一个实施例中，所述更新窗口中已满的闪存块从所述更新窗口中移除进一 步包括：当所述更新窗口中存在已满的闪存块时，更新所述已满的闪存块的正向索引， 并将所述已满的闪存块从所述更新窗口中移除。

本发明的一个实施例中，所述步骤S2具体包括：根据更新窗口元数据中闪存块的 地址确定所述更新窗口；获得所述更新窗口中页元数据中的所述数据类型，并根据不同 数据类型读取存储于不同位置的所述反向索引，以生成所述内存正向索引；以及使用待 持久化索引列表标记未写入所述内存正向索引的数据。

本发明的一个实施例中，所述反向索引根据所述数据类型而不同。

本发明的一个实施例中，所述数据类型包括数据和索引节点。

根据本发明实施例的方法，通过正向索引减少在被延迟持久化的闪存写次数和数据 写操作的延迟，避免了用于被索引数据与索引元数据的事务操作开销，同时使得闪存空 间分配不会受到检查点操作的阻塞，在更新窗口元数据持久化的同时可进行数据写操 作，很大程度上降低了更新窗口元数据持久化带来的竞争延迟。另外，反向索引可提供 系统意外故障后的正向索引重构，提高了系统鲁棒性。

本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得 明显，或通过本发明的实践了解到。

附图说明

本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明 显和容易理解，其中：

图1为根据本发明一个实施例的在闪存存储系统中延迟持久化索引元数据的方法的 流程图；

图2为根据本发明一个实施例的闪存页页元数据字段的示意图；

图3为根据本发明一个实施例的数据类型和反向索引的生成流程图；

图4为根据本发明一个实施例的更新窗口的实施例示意图；

图5为根据本发明一个实施例的内存更新窗口元数据与存储设备更新窗口元数据的 状态转换过程示意图；

图6为根据本发明一个实施例的更新窗口的检查点操作的流程图；以及

图7为根据本发明一个实施例的闪存存储系统的故障恢复的流程图。

具体实施方式

下面详细描述本发明的实施例，实施例的示例在附图中示出，其中自始至终相同或 类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描 述的实施例是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

图1为根据本发明一个实施例的在闪存存储系统中延迟持久化索引元数据的方法的 流程图。如图1所示，根据本发明实施例的在闪存存储系统中延迟持久化索引元数据的 方法，包括以下步骤：

步骤101，闪存存储系统在写数据时生成数据的数据类型和反向索引，并将反向索 引一同写入闪存。

步骤102，根据数据、数据类型和反向索引建立内存正向索引，并使用待持久化索 引列表标记未写入内存正向索引的数据。

具体地，在读写功能单元中，读操作与原先读操作一样。写操作与原先写操作不同， 需要在被索引数据写入时一同写入反向索引。写操作首先判断写操作中被索引数据的数 据类型，根据不同的数据类型生成不同的反向索引，并记录于不同的位置。其中，反向 索引根据数据类型而不同。

在本发明的一个实施例中，根据更新窗口元数据中闪存块的地址确定更新窗口。然 后获得更新窗口中页元数据中的数据类型，并根据不同数据类型读取存储于不同位置的 反向索引，以生成内存正向索引，之后使用待持久化索引列表标记未写入内存正向索引 的数据。

在本发明的一个实施例中，被索引数据的数据类型分为数据（DATA）和索引节点 （INODE）两种。数据类型记录于页元数据中数据类型字段。图2为根据本发明一个实 施例的闪存页页元数据字段的示意图。如图2所示，反向索引根据数据类型不同而不同。 数据的反向索引格式为<i_num,l_off,version>，其中，字段分别记录了该数据所属 文件索引节点的索引号，在该文件中的逻辑偏移，以及该数据更新的版本。索引节点反 向索引格式为<parent_i_num,name,version>，其中，字段分别记录了该索引节点所 在目录的索引节点的索引号，该索引节点所表示文件的文件名，已经该索引节点的更新 版本。反向索引记录的位置也因数据类型的不同而不同。数据的反向索引记录于页元数 据中，而不影响数据内容。索引节点的方向索引因name字段为变长字段，因而记录于 索引节点的起始位置。

图3为根据本发明一个实施例的数据类型和反向索引的生成流程图。如图3所示， 数据类型和反向索引的生成包括以下步骤：

步骤（1）记录数据类型，生成反向索引。

步骤（1.1）首先判断当前写操作的数据类型，若为数据写，转步骤（1.2），若为 索引节点写，转步骤（1.3），否则转步骤（1.4）。

步骤（1.2）若为数据写，则按照闪存页大小切分为闪存页写，为每个闪存页生成 反向索引，并与数据类型一同记录于页元数据。

步骤（1.2.1）切分数据写为闪存页写，并循环以下步骤至数据写完成。

步骤（1.2.2）在闪存页写的页元数据中设置数据类型字段为DATA，表示该闪存页 的内容为数据。

步骤（1.2.3）为该闪存页生成反向索引<i_num,l_off,version>，并记录在页元 数据中，其中i_num表示该页所属文件索引节点的索引号，l_off表示该闪存页在该页 所属文件中的逻辑页偏移，version表示版本号。

步骤（1.2.4）写入该页的页数据及页元数据。

步骤（1.3）若为索引节点写，生成该索引节点的反向索引，记录于索引节点的起 始位置，即记录在该索引节点第一个闪存页的页数据中，同时将数据类型记录于页元数 据中。

步骤（1.3.1）为该索引节点生成反向索引<parent_i_num,name,version>，记录 于索引节点的起始位置，其中，parent_i_num为该索引节点表示文件所在目录的索引节 点的索引号，name为该索引节点表示文件的文件名，version为版本号。

步骤（1.3.2）按闪存页大小对索引节点内容切分为闪存页写，在第一个闪存页的 页元数据中设置数据类型字段为INODE，表示该闪存页为索引节点的第一个闪存页，然 后写入该页的页数据及页元数据。

步骤（1.3.3）继续写入该索引节点的其它闪存页。

步骤（1.4）直接写入该页的页数据及页元数据。

步骤（2）更新内存正向索引，将正向索引内存结构链接到待持久化正向索引链表 中。

步骤（2.1）区分不同类型的数据，确定对正向索引结构的持久化。

步骤（2.2）若数据类型为DATA，则需要在其索引节点的映射中更新映射关系。

步骤（2.2.1）在其索引节点的映射关系内存数据结构中更新映射关系。

步骤（2.2.2）若索引节点中除映射关系、时间等字段发生修改外，其它字段未发 生修改，可不立即持久化，将索引节点的内存结构链接到待持久化正向索引链表中。

步骤（2.2.3）否则，立即进行该索引节点的持久化。

步骤（2.3）若数据类型为INODE，则需要在其目录的目录项中增加相应目录项。

步骤（2.3.1）在其目录的目录项的内存结构中增加相应目录项。

步骤（2.3.2）将目录项的内存结构链接到待持久化正向索引链表中。

步骤（2.4）对于其它数据类型的更新，按原有方式更新其索引元数据。

在本发明的一个实施例中，闪存存储系统包括闪存存储子系统以及基于闪存存储子 系统的文件系统等软件模块。为延迟持久化索引元数据，闪存存储系统引入三个功能单 元：支持索引元数据延迟持久化的读写功能单元、更新窗口与检查点功能单元和故障恢 复功能单元。这三个功能单元可实施于直接管理闪存的文件系统等软件模块内部，也可 实施于管理闪存的固件闪存转换层中。实施例一示出了在闪存介质上直接构建文件系统 的方式，不引入闪存转换层。在这种方式下，支持索引元数据延迟持久化的三个功能单 元实施于文件系统中。

在本发明的一个实施例中，索引元数据是指用于索引数据存放物理地址的映射关 系。索引节点作为数据页的索引元数据时，在直接管理闪存的文件系统中，异地更新要 求每次数据页的更改都需要修改映射关系。将这种映射关系直接记录于索引节点中。索 引节点除了记录该文件逻辑偏移至物理地址的映射关系外，还记录文件大小、访问时间、 访问控制列表等元数据信息。但其中映射关系被认为是索引元数据。目录项作为索引节 点的索引元数据。目录项中记录了该目录中文件的名字及索引节点号。文件系统通过索 引节点号查找索引节点的位置。在直接管理闪存介质的闪存存储系统中，目录项中记录 的索引节点号与其所表示的索引节点物理地址的映射关系因闪存异地更新特性而频繁 修改，因而写操作直接在目录项中同时记录了索引节点的物理地址。目录项被认为是索 引节点的索引元数据。这些索引元数据是用于正向查找数据页或索引节点的物理地址， 所以也被称为正向索引。反之，记录于数据页或者索引节点中的用于扫描重构正向索引 的索引，被称为反向索引。为延迟持久化索引元数据，正向索引在其内存结构中更新到 最新状态，然后通过加入待持久化正向索引链表的方式延后持久化。待持久化正向索引 链表记录了尚未持久化的正向索引的内存结构。

步骤103，通过更新窗口跟踪尚未建立正向索引的数据。

具体地，更新窗口用于跟踪尚未建立正向索引的数据所在的闪存块。由于更新窗口 需要在系统故障之后能被确认，因而更新窗口元数据需要及时持久化，以避免系统意外 故障导致的内存状态丢失。为减少更新窗口元数据的持久化，检查点操作预先分配预设 数量的空闲闪存块至更新窗口，直至更新窗口中页面使用率超过预设阈值时才启动检查 点操作持久化更新窗口元数据。

检查点操作是需要持久化待持久化正向索引，并修改存储设备更新窗口元数据。为 避免更新窗口元数据修改过程中闪存空间分配被阻塞，闪存空间分配的闪存块为前后两 个更新窗口中闪存块的交集。也就是，不管存储设备更新窗口元数据修改成功与否，从 新旧两个存储设备更新窗口元数据均能查找到该修改过程中用于闪存空间分配的闪存 块。从而在检查点操作过程中继续提供闪存空间分配服务，而不被阻塞。

图4为根据本发明一个实施例的更新窗口的实施例示意图。如图4所示，当前更新 窗口包含闪存块16,33,18,19,68,69,70,71,128,129,130,62,79,80,81, 82，其中闪存块16,33,18,19,68,69,70,71已写满，而闪存块128,129,130,62, 79,80,81,82未写满。根据预设阈值，当前更新窗口需要移动，因而分配闪存块144, 145,146,147,148,96,97,98至更新窗口，新更新窗口包含闪存块128,129,130, 62,79,80,81,82,144,145,146,147,148,96,97,98。

图5为根据本发明一个实施例的内存更新窗口元数据与存储设备更新窗口元数据的 状态转换过程示意图。在图4所示的情况下的内存更新窗口元数据以及存储设备更新窗 口元数据在检查点操作中的状态转换的时间序列。如图5所示，在检查点操作的起始时 刻T(i)，内存及存储设备更新窗口元数据一致，均包含闪存块16,33,18,19,68,69, 70,71,128,129,130,62,79,80,81,82。检查点操作首先从更新窗口中移除已 写满的闪存块，修改内存更新窗口元数据，其包含闪存块128,129,130,62,79,80, 81,82，如时刻T(i+1)所示，而此时存储设备更新窗口元数据不变。直至时刻T(i+3)， 检查点操作持久化待持久化正向索引完成，并分配新闪存块至更新窗口。此时，检查点 操作先修改存储设备更新窗口元数据，其包含闪存块128,129,130,62,79,80,81, 82,144,145,146,147,148,96,97,98。等待存储设备更新窗口元数据持久化完 毕，内存更新窗口元数据才修改为最新状态，包含闪存块128,129,130,62,79,80, 81,82,144,145,146,147,148,96,97,98。在检查点持久化待持久化正向索引 的过程中，闪存空间分配仍可从闪存块128,129,130,62,79,80,81,82中分配。

图6为根据本发明一个实施例的更新窗口的检查点操作的流程图。如图6所示，更 新窗口的数据处理包括如下步骤：

步骤（1）区分当前更新窗口已写满和未写满闪存块，设置当前内存更新窗口元数 据为未写满闪存块及未使用闪存块的物理地址，将闪存空间分配限制在该范围内。

步骤（1.1）在当前更新窗口中，判断每个闪存块的最新分配页面号，若为最后该 闪存块的最后一页，则该闪存块已写满，否则未写满。

步骤（1.2）将已写满闪存块的物理地址从内存更新窗口元数据中移除，则当前内 存更新窗口元数据记录了当前更新窗口中的未写满闪存块及未使用闪存块的物理地址， 如图5中T(i+1)时间所示。

步骤（2）持久化内存中待持久化正向索引链表。

步骤（2.1）扫描待持久化正向索引链表，将其中节点写入闪存存储设备中，并将 其从链表中移除。

步骤（2.2）检查该链表是否为空，若不为空，则转步骤（2.1）。

步骤（3）分配空闲闪存块至更新窗口，修改存储设备更新窗口元数据

步骤（3.1）判断当前内存更新窗口元数据中闪存块的个数，并由预设更新窗口大 小减去该值，计算出需要新分配闪存块个数。

步骤（3.2）从空闲块列表中分配相应个数的闪存块至更新窗口，并生成临时数据 结构记录该闪存块的物理地址。

步骤（3.3）由当前内存更新窗口元数据与临时数据结构合并成新的内存更新窗口 元数据，并持久化到存储设备，修改存储设备更新窗口元数据，如图5中T(i+2)时间所 示。

步骤（3）最后，修改内存更新窗口元数据至最新状态，以提供新的闪存空间分配， 如图5中T(i+3)时间所示。

步骤104，当闪存存储系统发生故障时，根据更新窗口的数据类型和反向索引重构 正向索引以恢复闪存存储系统的故障。

具体地，系统意外故障重启后，故障恢复功能单元确认更新窗口找出尚未建立正向 索引的数据所在闪存块，然后读取页元数据中的数据类型，并根据不同的数据类型读取 反向索引重构正向索引，以恢复索引元数据。

在本发明的一个实施例中，当更新窗口的利用率超过阈值时，为更新窗口分配新的 更新窗口，并将更新窗口中已满的闪存块从更新窗口中移除，其中，当更新窗口中存在 已满的闪存块时，首先更新已满的闪存块的正向索引，然后将已满的闪存块从更新窗口 中移除。

图7为根据本发明一个实施例的闪存存储系统的故障恢复的流程图。如图7所示， 闪存存储系统的故障恢复包括如下步骤：

步骤（1）读取更新窗口元数据，确定更新窗口。

步骤（2）扫描更新窗口中每个已使用闪存页的页元数据，根据不同数据类型读取 反向索引，重构正向索引。

步骤（2.1）循环读取更新窗口中每个已使用的闪存页的页元数据，确定数据类型； 若更新窗口扫描完成，则转步骤（3）；若为数据页，转步骤（2.2），若为索引节点， 转步骤（2.3），其它则转步骤（2.1）继续读取下一个已使用闪存页的页元数据。

步骤（2.2）从页元数据中读取数据页的反向索引<i_num,l_offversion>。

步骤（2.2.1）检查索引号为i_num的索引节点的在文件逻辑偏移为l_off处的映 射关系，若映射关系中物理页号与当前闪存页的物理页号一致，则转步骤（2.1）。

步骤（2.2.2）若映射关系中物理页号与当前闪存页的物理页号不一致，则将映射 关系中修改为当前物理页号，并将该页的内存结构链接到待持久化正向索引链表中，转 步骤（2.1）。

步骤（2.3）从页数据中读取索引节点的反向索引<parent_i_inum,name,version>。

步骤（2.3.1）检查索引号为parent_i_num的索引节点所表示的目录的目录项中是 否有名字为name的目录项，若存在，则转步骤（2.1）。

步骤（2.3.2）若不存在名字为name的目录项，则用name以及当前索引节点的索 引号i_num生成目录项，添加到目录的目录项中，然后将该页的内存结构链接到待持久 化正向索引链表中，转步骤（2.1）以完成对闪存存储系统的故障恢复。

在本发明的一个实施例中，文件系统等软件模块通过闪存转换层管理闪存介质的方 式下，文件系统中文件逻辑偏移或目录项索引号至物理地址存在两层映射关系。首先， 文件系统中文件逻辑偏移与目录项索引号映射到存储设备导出的线性地址上。然后该线 性地址通过闪存转换层的映射关系映射到闪存物理地址。因而这种方式下的索引元数据 既包括了文件系统索引元数据，也包括了闪存转换层索引元数据。前者为用于索引线性 地址的文件逻辑偏移或索引节点号。后者为用于索引物理地址的线性地址。

在本发明的一个实施例中，数据页的反向索引为<i_num,l_off,LPN,version>， 其中i_num表示该数据所在文件的索引节点索引号，l_off表示该数据在文件中的逻辑 偏移，LPN记录该数据所在的线性地址，version为该数据的更新版本。在正向索引重 构过程中，首先检查文件系统中索引号为i_num的索引节点中映射关系是否存在l_off 至LPN的映射关系。若该关系不存在且当前反向索引中版本号更高，则在索引节点中更 新l_off至LPN的映射关系。然后检查闪存转换层中LPN是当前闪存页物理页号PPN的 映射关系，若不存在且当前反向索引中版本号更高，则更新闪存转换层中的映射关系。 索引节点的反向索引为<parent_i_num,name,LPN,version>，其中parent_i_num表 示该索引节点所在目录的索引节点索引号，name表示该索引节点所代表文件的文件名， LPN表示该索引节点所在的线性地址，version表示该索引节点的更新版本。正向索引 重构分为两个步骤。首先，检查索引节点索引号为parent_i_num的目录项中是否存在 名字为name的目录项，若不存在且反向索引中版本号更高，则更新该目录项。然后检 查闪存转换层中是否存在LPN至当前闪存页物理页号PPN的映射关系，若不存在且反向 索引中版本号更高，则更新闪存转换层中该映射关系。

在本发明的一个实施例中，文件系统等软件模块通过闪存转换层管理闪存介质的方 式下，若文件系统中索引节点号、逻辑偏移不能传递到闪存转换层中，则索引元数据的 延迟持久化仅作用于闪存转换层映射关系的延迟持久化。

在本发明的一个实施例中，闪存转换层无法感知文件系统的语义，无法判别写操作 的数据类型，因而只作用于闪存转换层中的索引元数据。反向索引为<LPN,version>， 其中LPN为该闪存页的线性地址，version为该闪存页的更新版本。重构正向索引时， 查找闪存转换层映射关系中LPN所对应的映射关系，若与当前闪存页物理页号不匹配且 当前反向索引更新版本号更高，则将LPN所对应的映射关系更新为当前闪存页页号。

在本发明的一个实施例中，为跟踪存储设备上尚未建立正向索引的数据，支持索引 元数据延迟持久化的闪存存储系统引入更新窗口。更新窗口记录上一次检查点之后尚未 建立正向索引的闪存块的物理地址。检查点操作用于持久化闪存存储系统中待持久化的 正向索引，被新分配相应数据的空闲闪存块至更新窗口，并修改更新窗口元数据。更新 窗口元数据是记录更新窗口中闪存块物理地址的元数据，包括内存更新窗口元数据和存 储设备更新窗口元数据。其中，内存更新窗口元数据为存储设备更新窗口元数据在内存 中的数据结构。

根据本发明实施例的方法，通过正向索引减少在被延迟持久化的闪存写次数和数据 写操作的延迟，避免了用于被索引数据与索引元数据的事务操作开销，同时使得闪存空 间分配不会受到检查点操作的阻塞，在更新窗口元数据持久化的同时可进行数据写操 作，很大程度上降低了更新窗口元数据持久化带来的竞争延迟。另外，反向索引可提供 系统意外故障后的正向索引重构，提高了系统鲁棒性。

尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性 的，不能理解为对本发明的限制，本领域的普通技术人员在不脱离本发明的原理和宗旨 的情况下在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。