在固态驱动器中利用空闲空间计数来重建两阶加电映射的方法、设备和系统

摘要

一种数据存储设备包括非易失性存储器，所述非易失性存储器包含多个块，每一个块被配置为在预定物理位置处存储多个物理页。控制器对存储在多个逻辑页中的数据进行编程和读取。易失性存储器包括逻辑到物理地址转换映射，所述映射被配置为使得能够确定存储在每一个逻辑页中的数据在一个或多个物理页中的物理位置。可以存储多个日志，每一个日志包括将一个或多个物理页与每一个逻辑页相关联的多个条目。在启动时，所述控制器可以有序读取所述多个日志中的至少一些，并且重建该映射；表明在重建映射后服务数据访问命令的预备状态；根据映射来重建表，并且基于其，在已经表明了处理所述命令的预备状态后选择块以用于垃圾收集。

说明书

背景技术

由于固态驱动器(SSD)中闪速存储器的本质，数据通常由页进行编程 并且以块擦除。在SSD中的页一般大小是8-16千字节(KB)，而块包含大 量页(例如，256或512)。因此，SSD中特定的物理位置(例如，页)不 能直接进行覆写，而不会覆写相同块中页内的数据，这在磁性硬盘驱动中 是可能的。这样，需要间接地址。传统的数据存储设备控制器管理数据存 储设备上的闪速存储器并且与主机系统交互，其使用作为闪存转换层(FTL) 的一部分的被称为逻辑块寻址(LBA)的逻辑到物理(L2P)映射系统。当 新数据代替已经写入的旧数据时，数据存储设备控制器使得新的数据写在 新位置(因为数据存储设备不能直接覆写旧数据)，并且更新逻辑映射以指 向新的物理位置。此时，旧的物理位置不再保存有效数据。这样，旧的物 理位置将最终需要在能够被再次写入之前被擦除。

通常，大的L2P映射表将逻辑条目映射到SSD上的物理地址位置。当 写入到来时，该大的L2P映射表通常被保存在小段中。例如，如果发生随 机写入，虽然系统可能不得不只更新一个条目，但是必须要保存整个表或 其部分，包括未被更新的条目，这是固有低效的。

图1示出了用于数据存储设备的传统逻辑块寻址(LBA)方案的方面。 如图所示，映射表104包括针对数据存储设备的闪速存储器106定义的每 个逻辑块102的一个条目。例如，支持512字节逻辑块的64GB数据存储 设备可以将自己呈现给主机作为具有125,000,000逻辑块。映射表104中的 一个条目包括闪速存储器106中的125,000个逻辑块中每一个的当前位置。 在常规的数据存储设备中，闪存页保存有整数个逻辑块(即，逻辑块不跨 闪存页)。在该常规示例中，8KB闪存页将保存有16个(大小为512字节 的)逻辑块。因此，逻辑到物理映射表104中的每一个条目包含识别在其 上存储有LBA的管芯的字段108，识别在其上存储有LBA的闪存块的字段 110，识别闪存块内的闪存页的另一字段112，以及识别用于识别LBA数据 开始于所识别出的闪存页中何处的闪存页内的偏移的字段114。映射表104 的大尺寸防止该表被保存于SSD控制器内。照惯例，大的映射表104被保 存在与SSD控制器连接的外部DRAM中。由于映射表104存储在易失性 DRAM中，所以其必须在SSD加电时恢复，因为表的大尺寸，这将花费很 长时间。

当写入逻辑块时，更新映射表104中的相对应的条目以反映逻辑块的 新位置。当读取逻辑块时，读取映射表104中的相对应的条目以确定在闪 速存储器中将要读取的位置。然后针对在映射表104中相对应的条目指定 的闪存页执行读取。当所读取的数据对于闪存页可用时，将在映射条目指 定的偏移处的数据从闪存设备传送到主机。当写入逻辑块时，保存有“旧” 版本数据的闪速存储器变成“垃圾”(即，数据不再有效)。需要注意的是， 当写入逻辑块时，闪速存储器将初始包含至少两个版本的逻辑块；即，有 效的、最近写入的版本(由映射表104指向)，以及其至少一个其它的旧版 本，其是陈旧的并且不再由映射表104中的任何条目所指向。这些“陈旧 的”条目被称作“垃圾”，其占据了必须被计数、收集、擦除以及供将来使 用可用的空间。这个过程被称作“垃圾收集”。

当关机或其它电力中断事件时，存储有映射表104的易失性存储器的 内容不再有效。因此必须重建映射表104。该过程的目标是1)创建逻辑到 物理关系的相干映射，以及2)允许存储器系统的正常操作。该正常操作应 该允许由准备时间(time-to-ready)约束的数据访问命令的服务，并且应该 允许存储器系统拾取最佳块以用于垃圾收集操作。拾取最佳块以用于垃圾 收集继而涉及准确地针对存储器块中的空闲空间等其它可能因素进行计 数。

重建映射表104的常规方法包括：当RAM以随机状态加电(即，没有 有效的ECC)时，首先将易失性存储器内的所有存储器位置初始化为零。 之后，L2P映射可以根据保存在非易失性存储器中的映射信息来进行重建， 同时实施空闲空间计数。这些操作涉及冗长的随机读取和随机写入，这花 费大量时间，并且最终延迟驱动器在加电时用于主机读取和写入的准备时 间。照常规，映射重建和空闲空间计数二者必须在驱动器能够向主机报告 准备好服务数据访问命令之前被完成。

附图说明

图1示出了用于SSD的常规逻辑块寻址方案的方面。

图2是根据一个实施例的数据存储设备的框图。

图3是示出了根据一个实施例的数据存储设备的物理和逻辑数据组织 的方面的图。

图4示出了根据一个实施例的逻辑到物理地址转换映射及其图示条目。

图5示出了根据一个实施例的用于更新逻辑到物理地址转换映射以及 用于创建S日志条目的方法的方面。

图6是根据一个实施例的S日志的框图。

图7示出了根据一个实施例的S日志的一个条目的示例性组织。

图8是根据一个实施例的超级块(S块)的框图。

图9示出了根据一个实施例的超级页(S页)的另一视图。

图10A示出了根据一个实施例的逻辑到物理地址转换映射、S日志以 及S块之间的关系。

图10B是根据一个实施例的S日志映射的框图。

图11是根据一个实施例的实施两阶加电逻辑到物理映射重建的方法的 流程图。

图12是根据一个实施例的示出了实施两阶加电逻辑到物理映射重建的 方法的另一方面的框图。

图13表示根据一个实施例的有效大小信息表。

图14是示出了根据一个实施例的实施利用空闲空间计数进行两阶加电 逻辑到物理映射重建的方法的方面的框图。

图15是示出了根据一个实施例的垃圾收集的方面的框图。

图16是示出了根据一个实施例的垃圾收集的另一方面的框图。

图17是示出了根据一个实施例的垃圾收集的又一方面的框图。

图18是示出了根据一个实施例的垃圾收集的再一方面的框图。

具体实施方式

系统概述

图2是示出了根据一个实施例的数据存储设备的物理和逻辑数据组织 的方面的框图。在一个实施例中，数据存储设备是SSD。在另一实施例中， 数据存储设备是混合驱动器，其包括闪速存储器和旋转磁性存储介质。本 公开适应于SSD和混合实现方式二种，但是为了简单，将结合基于SSD的 实现来描述各种实施例。根据一个实施例的数据存储设备控制器202可以 被配置为与如附图标记218示出的主机耦合。控制器可以包括执行以下描 述的由控制器执行的一些或全部功能的一个或多个处理器。主机218可以 利用逻辑块寻址(LBA)方案。虽然LBA大小一般是固定的，但主机可以 动态地改变LBA的大小。例如，LBA大小可以通过接口和接口模式而改变。 事实上，虽然512字节是最常见的，但4KB也变得更加普通，如作为512+ (520、528等)和4KB+(4KB+8、4KB+16等)格式。如图所示，数据存 储设备控制器202可以包括页寄存器204或与页寄存器204耦合。页寄存 器204可以被配置为使得控制器202能够从数据存储设备读取数据以及向 数据存储设备存储数据。控制器202可以被配置为响应于来自主机218的 数据访问命令对来自闪速存储器设备的阵列的数据进行编程并且来从其读 取数据。虽然本文的描述提及闪速存储器，但可以理解的是存储器设备的 阵列可以包括其它类型的非易失性存储器设备，例如，闪存集成电路、硫 属化合物RAM(C-RAM)、相变存储器(PC-RAM或PRAM)、可编程金 属化单元RAM(PMC-RAM或PMCm)、双向通用存储器(OUM)、阻抗 RAM(RRAM)、NAND存储器(例如，单层单元(SLC)存储器、多级单 元(MLC)存储器、或其任意组合)、NOR存储器、EEPROM、铁电存储 器(FeRAM)、磁阻RAM(MRAM)、其它分立的NVM(非易失性存储器) 芯片、或其任意组合。

页寄存器204可以被配置为使得控制器202从阵列读取数据以及将数 据存储到阵列。根据一个实施例，闪速存储器设备的阵列可以包括管芯(例 如，128个管芯)中的多个非易失性存储器设备，所述多个非易失性存储器 设备中的每一个包括多个块，例如图2的206所示出的。其它页寄存器204 (未示出)可以耦合到另一管芯上的块。闪存块的组合组合到一起可以被 称作超级块或S块。在一些实施例中，形成S块的个体块可以从一个或多 个管芯、平面或其它级别粒度中选择。因此，S块可以包括分布于一个或多 个管芯的、组合到一起的多个闪存块。以这种方式，S块可以形成闪存管理 系统(FMS)在其上操作的单元。在一些实施例中，形成S块的个体块可 以根据不同于管芯级别的粒度来选择，例如当存储器设备包括细分为例如 平面的结构的管芯(即，块可以取自个体平面)的情况。根据一个实施例， 可以在S块级别实施分配、擦除以及垃圾收集。在其它实施例中，FMS可 以根据例如页、块、平面、管芯等的其它逻辑分组来执行数据操作。

接下来，闪存块206中的每一个包括多个闪存页(F页)208。每一个 F页可以具有固定的大小，例如16KB。根据一个实施例，F页为给定闪存 设备的最小程序单元的大小。如图3所示，每一个F页208可以被配置为 容纳多个物理页，之后被称为E页210。术语“E页”指的是存储在闪速存 储器中的数据结构，在其上应用了误差校正码(ECC)。根据一个实施例， E页210可以形成在数据存储设备内进行物理寻址的基础，并且可以构成闪 存读取数据传送的最小单位。因此，E页210可以(但不必)具有预定的固 定大小(例如，2KB)，并且确定ECC系统的有效载荷(例如，主机数据) 的大小。根据一个实施例，每一个F页208可以被配置为在其边界内适应 预定的多个E页210。例如，给定16KB大小的F页208以及每E页210 固定大小2KB，如图3所示，八个E页210在单个F页208内适应。在任 何情况下，根据一个实施例，包括ECC的E页210的2的幂次可以被配置 为适应F页208。每一个E页210可以包括数据部分214，以及取决于E页 210所在之处，还可以包括ECC部分216。数据部分214和ECC部分216 在大小上都不需要是固定的。E页的地址唯一地识别E页在闪速存储器内 的位置。例如，E页的地址可以指定闪存信道、在识别出的闪存信道内的特 定管芯、管芯内的特定块、特定的F页，以及最后在所识别出的F页内的E 页。

为了桥接主机在数据存储设备上的物理寻址和逻辑块寻址，引入逻辑 页(L页)构造。L页在图3中由附图标记212示出，其可以包括FMS所 使用的地址变换的最小单元。根据一个实施例，每一个L页可以与L页号 相关联。因此，L页212的L页号可以被配置为使控制器202能够逻辑地 引用存储在一个或多个物理页(例如，E页210)中的主机数据。L页212 还可以用作压缩的基本单元。根据一个实施例，与F页208和E页210不 同，由于要存储的数据压缩的可变性，L页212在大小上并不是固定的而在 大小上可以改变。例如，因为数据的压缩性变化，所以可以将一种类型的 4KB的数据压缩成2KB的L页，同时可以将不同类型的4KB的数据压缩 成1KB的L页。由于这种压缩，所以L页的大小在最小压缩大小(例如， 24字节)到最大未压缩大小(例如，4KB或4KB+)所定义的范围内可以 变化。可以实现其它的大小和范围。如图3所示，L页212不需要与E页 210的边界对齐。事实上，L页212不仅可以被配置为与F页208和/或E 页210边界对齐的开始地址，而且可以被配置为与F页208或E页210的 边界不对齐。也就是说，L页开始地址可以位于与F页208的开始地址或 结束地址或者E页210的开始地址或结束地址的非零偏移处，如图3所示。 由于L页212在大小上并不固定并且可能小于固定大小的E页210，所以 多于一个的L页212可以在单个E页210内适应。类似地，由于L页212 大小可能大于E页210，所以L页212可能跨越多于一个E页，并且可能 甚至跨F页208的边界，如图3中附图标记217所示。

例如，当LBA大小为512或512+字节时，例如，假设未压缩的L页 212可以是4KB到4KB+，则最大的八个连续LBA可以被封装到4KB的L 页212中。应该注意的是，根据一个实施例，L页212的准确逻辑大小不重 要，这是因为在压缩后，物理大小可能跨越从最小尺寸的几字节到全尺寸 的几千字节。例如，对于4TB SSD设备，可以使用30位寻址来寻址可能存 在于这种SSD中的每一个L页212。

地址转换映射和相关数据结构

图4示出了根据一个实施例的逻辑到物理地址转换映射及其图示条目。 当主机数据被主机在L页212中引用并且当数据存储设备将L页212存储 在一个或多个连续E页210中时，需要逻辑到物理地址转换映射来使得控 制器202能够将L页212的L页号与一个或多个E页210相关联。这种逻 辑到物理地址转换映射在图4的302处示出，并且在一个实施例中，其是 具有每L页212一个条目的线性阵列。这种逻辑到物理地址转换映射302 可以存储在易失性存储器中，例如，DRAM或SRAM。图4还示出了用于 四个不同L页212的逻辑到物理地址转换映射中的条目，图4中的L页212 与标示为L页1、L页2、L页3和L页4的L页号相关联。根据一个实施 例，存储在数据存储设备中的每一个L页可以由逻辑到物理地址转换映射 302中的单个并且唯一的条目指向。因此，在与其发展的示例中，示出了四 个条目。如302处所示，映射302中的每一个条目可以包括L页号，其可 以包括包含被引用的L页的开始地址的物理页(例如，E页)的识别、物 理页(例如，E页)中开始地址的偏移以及L页的长度。另外，多个ECC 位可以为映射条目提供误差校正功能。例如，以及如图4所示的，并且假 设E页大小为2KB，则可以按如下在逻辑到物理地址转换映射302中引用 L页：E页1003、偏移800、长度1624，随后是预定量的ECC位(未示出)。 也就是，在物理地址方面，L页1的开始在E页300中(未对齐)，而且位 于距E页1003的开始物理位置等于800字节的偏移处。此外，压缩的L页 1延伸1,624字节，从而跨E页边界到E页1004。因此，E页1003和1004 中的每一个存储由L页号L页1所标示的L页212的一部分。类似地，由 L页号L页2所引用的压缩的L页整体存储在E页1004中，并且在其400 字节的偏移处开始，并且仅在E页1004中延伸696字节。与L页号L页3 相关联的压缩的L页在E页1004的1,120字节的偏移处开始(仅与L页2 的边界距离24字节)，并且延伸4,096字节经过E页1005进入E页1006。 因此，与L页号L页3相关联的L页跨越E页1004的一部分、E页1005 的全部以及E页1006的一部分。最后，与L页号L页4相关联的L页在E 页1006中的1,144字节的偏移处开始，并且延伸3,128字节以完全跨越E 页1007，跨F页边界进入下一F页的E页1008。

共同地，这些组成逻辑到物理地址转换映射302的每一个条目的构成 标识符字段(E页、偏移、长度和ECC)中的每一个例如大小可以是8字 节。也就是，对于示例性4TB驱动器，E页的地址大小可以是32位，偏移 大小可以是12位(对于高达4KB的E页数据部分)，长度大小可以是10 位，并且可以提供ECC字段。其它组织和位字段也是可能的。可以在每次 写入或修改L页时创建这种8字节条目，以使得控制器202能够在闪速存 储设备中跟踪在L页写入的主机数据。在逻辑到物理地址转换映射中的该8 字节条目可以由L页号或LPN进行索引。换句话说，根据一个实施例，L 页号用作对逻辑到物理地址转换映射302的索引。需要注意的是，在4KB 扇区大小的情况下，LBA与LPN相同。因此，LPN可以组成易失性存储器 中条目的地址。当控制器202从主机218接收读取命令时，可以从所提供 的LBA推导出LPN，并且将所述LPN用于对逻辑到物理地址转换映射302 进行索引以提取将在闪速存储器中读取的数据位置。当控制器202从主机 接收到写入命令时，可以根据LBA构建LPN，并且可以修改逻辑到物理地 址转换映射302。例如，可以在其中创建新的条目。取决于存储逻辑到物理 地址转换映射302的易失性存储器的大小，LPN可以存储在单个条目中， 或例如被分解为识别包含所讨论的L页的开始地址的E页(加ECC位)的 第一条目和识别偏移和长度(加ECC位)的第二条目。因此，根据一个实 施例，这两个条目可以一起对应于并且指向闪速存储器中的单个L页。在 其它实施例中，逻辑到物理地址转换映射条目的具体格式可以不同于上述 所示的示例。

由于逻辑到物理地址转换映射302可以存储在易失性存储器中，所以 当易失性存储器开始或任何其它丢失电力时必须被重建。因此，这要求在 非易失性存储器中存储一些机制和信息，来使得控制器202在开始之后或 电源故障之后在控制器能够“知道”L页存储在非易失性存储器何处之前对 逻辑到物理地址转换映射302进行重构。根据一个实施例，这种机制和信 息可以具体实现在可以被称作系统日志或S日志的构造中。根据一个实施 例，控制器202可以被配置为在多个非易失性存储器设备(例如，在一个 或多个管芯、信道或平面中的一个或多个块206)中维持多个定义物理到逻 辑地址对应的S日志。根据一个实施例，每一个S日志可以覆盖预定范围 的物理页(例如，E页)。根据一个实施例，每一个S日志可以包括多个日 志条目，每一个条目被配置为将一个或多个物理页(例如E页)与每一个L 页的L页号相关联。根据一个实施例，每次控制器202重启或者无论何时 必须重建逻辑到物理地址转换映射302时，控制器202读取S日志，并且 根据从S日志条目读取的信息来重建逻辑到物理地址转换映射302。

图5示出了根据一个实施例的用于更新逻辑到物理地址转换映射以及 用于创建S日志条目的方法的方面。如图所示，为了确保逻辑到物理地址 转换映射302保持最新，当如框B51所示L页被写入或更新时，逻辑到物 理地址转换映射302如B52处所示被更新。如B53处所示，S日志条目还 可以被创建，在其内存储指向更新后的L页的位置的信息。以这种方式， 当发生新写入时(例如，当主机发布写入到非易失性存储器时，当发生垃 圾收集/耗损平衡时，等)，逻辑到物理地址转换映射302和S日志都被更新。 因此，到非易失性存储器设备以维持地址转换数据的电力安全副本的写操 作可以被配置为由新创建的S日志条目(其大小可能仅几字节)被触发而 不是重新保存逻辑到物理地址转换映射的全部或部分，从而降低写入放大 率(WA)。更新S日志确保控制器202能够访问新更新的L页，以及确保 当重启或其它影响存储逻辑到物理地址转换映射的非易失性存储器的信息 擦除电力事件时可以对逻辑到物理地址转换映射302进行重构。此外，除 了重建逻辑到物理地址转换映射302的效用之外，S日志还可用于运行有效 的垃圾收集(GC)。事实上，S日志可以包含对所有L页号的最近更新，以 及还可以包含陈旧条目、不指向有效L页的条目。

根据一个实施例，S日志可以构成写入到介质中的主闪存管理数据。根 据一个实施例，S日志可以包括针对给定S块的映射信息，以及可以包括针 对给定S块的物理到逻辑(P2L)信息。图6是示出了根据一个实施例的S 日志的方面的框图。如图所示以及根据一个实施例，每一个S日志602覆 盖非易失性存储器的预定物理区域，例如，如606处显示的32E页，利用 5位来对其进行寻址。每一个S日志602可以由S日志号604来进行识别。 用于存储主机数据的P2L信息的S日志号604可以包括由S日志覆盖的第 一物理页的地址的一部分。例如，S日志602的S日志号例如可以包括由该 S日志602覆盖的第一E页的27MSb。

图7示出了根据一个实施例的S日志602的一个条目702的示例性组 织。S日志602的每一个条目702可以指向在E页物理定址的一个L页的 开始地址。每一个条目702可以包括例如包含L页的开始E页的E页的多 个LSb(例如，5个)。可以通过将这些5个LSb和头部中S日志号的27 个MSb进行级联而获得完整的E页地址。随后，条目702可以包括L页号， 其在识别出的E页中的偏移以及其大小。例如，数据带S日志602的每一 个条目702可以包括该S日志条目覆盖的第一E页的5个LSb，30位的L 页号，9位的E页偏移以及10位的L页大小，加起来总共大约7字节的大 小。在其它实施例中可以使用各种其它内部日志条目格式。

根据一个实施例，由于存储在L页的数据的压缩可变性或者主机配置， 可变量的L页可以存储在物理区域中，例如等于32个E页的物理区域中， 如图6中606处所示。由于使用压缩和L页大小的随后的变化性，S日志 602可以包括可变量的条目。例如，根据一个实施例，以最大压缩，L页的 大小可以是24字节，而S日志602可以包括多于2,500个条目，引用与L 页相同量，每S日志条目702一个L页。

如上所述，S日志602可以被配置为包括针对给定S块的映射信息，并 且可以包括针对给定S块的P2L信息。更准确地，根据一个实施例，S日 志602可以包括针对在给定S块内的预定范围的E页的映射信息。图8是 根据一个实施例的超级块(S块)的框图。如图所示，S块802可以包括每 管芯一个闪存块(F块)804(也如图2中206所示)。因此，可以将S块 802认为是F块804的集合，每管芯一个F块，其被组合到一起以形成闪存 管理系统的单元。根据一个实施例，可以在超级块级别管理分配、擦除和 GC。如图8所示，每一个F块804可以包括多个闪存页(F页)，例如256 或512个F页。根据一个实施例，F页可以是给定非易失性存储器设备的程 序的最小单元的大小。图9示出了根据一个实施例的超级页(S页)。如图 所示，S页803可以包括S块的每块一个F页，意味着S页803跨越整个S 块802。

图10A示出了根据一个实施例的逻辑到物理地址转换映射、S日志以 及S块之间的关系。附图标记902表示逻辑到物理地址转换映射。根据一 个实施例，逻辑到物理地址转换映射902可以通过L页号进行索引，因为 在逻辑到物理地址转换映射中每L页的逻辑到物理地址转换映射902中可 能存在一个条目。在闪速存储器中L页的开始的物理地址及其大小可以在 映射条目中给出；即通过E页地址、E页内的偏移和L页的大小。如前所 述，L页取决于其大小可以跨越一个或多个E页，并且可以跨越F页以及 块。

如904处所示，易失性存储器(例如，DRAM)还可以存储S日志映 射。S日志映射904中的条目存储与S日志物理位于非易失性存储器中何处 相关的信息。例如，存储L页的开始的E页物理地址的27个MSb可以构 成S日志号。易失性存储器中的S日志映射904还可以包括在非易失性存 储器中S日志的地址，在系统E页中引用。从易失性存储器中的S日志映 射904中，可以提取系统S块信息908。系统S块信息908可以由系统S 块(系统带中的S块)进行索引，并且可以包括关于S块的信息、系统S 块中任何空闲或已用空间的大小。还从S日志映射904中，可以提取非易 失性存储器910中S日志的物理位置。

根据一个实施例，系统带不包括L页数据，并且可以包括所有的文件 管理系统(FMS)元数据和信息。系统带可以被配置为仅针对可靠性和电 源故障简单化的较低页。在正常操作期间，系统带除了在垃圾收集期间否 则不需要被读取。根据一个实施例，针对全部WA优化，系统带可以与数 据带相比被提供显著高的过供应。其它带可以包括：热带，其可以包括L 页数据并且被频繁更新；以及冷带，其是存储从垃圾收集过程保留的静态 数据的存储器的物理区域，其可以不被频繁更新。根据一个实施例，系统 带、热带和冷带可以由控制器固件在S块的基础上进行分配。

如上所述，非易失性存储器的这些S日志中的每一个可以包括S日志 条目的集合，并且例如覆盖32个页数据。非易失性存储器910中这些S日 志使得控制器202能够在开机时访问非易失性存储器中的S日志条目，使 得控制器202能够在易失性存储器中不仅重建逻辑到物理地址转换映射 902，而且能重建S日志映射904、S块信息906以及系统S块信息908。

非易失性存储器中的S日志还可以包括所有的陈旧L页信息，由此使 得控制器202能够在易失性存储器中重建逻辑到物理地址转换映射902以 及S日志映射904之后进行GC。因此，可以说S日志包括对逻辑到物理地 址转换映射902随着时间的所有更新的顺序历史。

图10B是根据一个实施例的S日志映射904的另一视图的框图。S日 志映射904可以针对每一个S块引用多个S日志条目。根据一个实施例，S 块号可以是S日志号的MSb。S日志映射904的大小可以与每S块的S日 志条目数量乘以S块数量相关。因此，对S日志映射904进行索引可以通 过引用S块号(S日志号的MSb)和S块号的S日志条目来实施。控制器 202还可以被配置为建立或重建S日志的映射，以及将所得到的S日志映射 904存储在易失性存储器中。例如，当重启或在误差恢复之后的重启之后或 电源故障的另一事件发生时，控制器202可以以预定的顺序次序来读取多 个S日志，基于顺序地读取的多个S日志来建立存储在非易失性存储器设 备中的S日志的映射，并且将建立的S日志映射904存储在易失性存储器 中。特别地，重建的S日志映射904可以被配置为包括每一个S日志的最 近写入的版本的物理位置。事实上，根据一个实施例，在重建S日志映射 904中，当发现较新的S日志时，可以覆写较旧的S日志的物理位置。换句 话说，根据一个实施例中，可以通过处理器202基于被判定为有效的读取S 日志来重建S日志映射904。

两阶映射重建

根据一个实施例，在加电时，地址转换映射重建和空闲空间计数可以 分割成两个区别的阶段。在第一阶段，可以根据存储在非易失性存储器的 系统带中的S日志来重建地址转换映射。如上所述，系统带可以是包含FMS 元数据和信息的非易失性存储器的一部分。为了后加电电源故障操作的可 靠性和简单化，系统带可以被配置为仅用于较低页操作，由此避免了MLC 闪速存储器的较低页损坏的任意可能性。此外，针对全部WA优化，系统 带与数据带(其存储所有的L页数据并且包括热带和冷带)相比被提供显 著多的过供应。

根据一个实施例以及如图11中B 151处所示，为了重建逻辑到物理地 址转换映射902，可以读取所有的S日志。读取所有的S日志使得控制器 202能够从每一个S日志的每一个条目提取与每一个L页号相关联的每一 个L页的大小和准确物理位置。在一个实施例中，在所有S日志被读取以 及从其提取其存储在易失性存储器中的逻辑到物理地址转换映射902中的 物理到逻辑信息之后，控制器202将计数并且映射所有存储在整个非易失 性存储器中的L页。读取了多少S日志至少部分地取决于每一个S日志所 覆盖的物理页的范围(例如，根据一个实施例是32个E页)以及非易失性 存储器的大小。此外并且根据一个实施例，S日志构造可以用于存储与虚拟 地址范围相关的信息，并且用于将其它文件管理表存储在易失性存储器中。

根据一个实施例，由于S日志可以被配置为共同地包括所有的物理到 路基信息，并且因为多个L页可能已经被更新了多次，所以读取S日志的 次序是重要的。实际上，由于S日志可以被配置为共同地存储对L页的更 新的完整历史(至少由于存储L页的S块的最后垃圾收集)，在一个实施例 中以创建S日志的次序来读取S日志，如在框B151处所示。这在图12中 图形示出，其中，如有序读取S日志，根据时间上在前的S日志条目生成 的L2P转换映射条目1602被顺序由针对相同L页的相对稍后创建的S日志 条目中的对应的映射条目1602顺序地替代。以这种方式，如果对特定L页 应该(可能)进行了多次更新，则按照创建次序读取S日志确保了在有效 条目(即，指向L页的当前位置的S日志条目)之前读取了无效S日志条 目(即，没有指向L页的当前位置的S日志条目)。这继而确保了针对特定 L页的时间上最新的S日志条目被用作创建用于所述L页的有效映射条目 1602的基础。该种以创建次序顺序读取S日志以及确保针对L页最近读取 的的S日志条目是最当前的一个，确保了重建的逻辑到物理地址转换映射 902是相干的；也就是，准确地将逻辑页映射到非易失性存储器的正确物理 位置。根据一个实施例，当读取了存储在非易失性存储器中的S日志时，S 日志映射904(见图10B)也可以根据每一个读取的S日志的S日志号和地 址来进行重构。S日志映射904可以存储在易失性存储器中。

根据一个实施例，在下文示出和描述的两阶过程的一个实施例的第一 阶段中，控制器202可以被配置为在启动时按如B151处所示的创建次序来 读取多个S日志的每一个，并且根据读取出的多个日志来在易失性存储器 中重建逻辑到物理地址转换映射902。也就是，控制器202可以根据读取的 S日志条目，以每一个L页的物理位置信息(例如，在非易失性存储器的E 页中的长度和开始地址)来填充逻辑到物理地址转换映射902，如图4的 302所示。以这种方式，存储在数据存储设备的每一个L页可以通过逻辑到 物理地址转换映射902中的单个并且唯一的条目指向。根据一个实施例， 控制器202可以针对每一个读取的S日志中的每一个条目来执行到易失性 存储器的写入操作(例如，8字节写入)。然而，可以理解的是，实施例不 限于本文所示和描述的示例性的8字节大小，其它实现方式也是可能的。

根据一个实施例，在已经读取了所有S日志之后并且如逻辑到物理地 址转换映射902，在易失性存储器中已经重建了S日志映射904以及任意所 需表，数据存储设备可以报告其预备状态以处理到主机218的数据访问命 令，如在B152处所示。注意，在完成该第一阶段时，数据存储设备尚未执 行任意空闲空间计数操作，并且因此可能尚未准备好最佳地执行垃圾收集 操作。事实上，在垃圾收集的最佳块选择至少部分地取决于个体S块中的 空闲空间的实施例中，控制器202在第一阶段的结束时尚不知道哪个是用 于垃圾收集的最佳S块，因为还未执行空闲空间计数。在选择用于垃圾收 集活动的S块时的一个考虑可以包括确定每一个S块中可用的空闲空间量。 例如，控制器202可以将具有最大量的空闲空间的S块选择作为实施垃圾 收集活动的下一S块。注意，根据一个实施例，控制器202还识别用于垃 圾收集的下一最佳S块，以及之后的下一最佳S块，等等。

根据一个实施例，在至少已经重建了逻辑到物理地址转换映射902之 后，以及在数据存储设备已经报告了其预备状态以处理数据访问命令之后， 可以实施当前的两阶加电过程的第二阶段。根据一个实施例，在至少已经 重建了逻辑到物理地址转换映射902之后，以及在数据存储设备已经报告 了其预备状态以处理数据访问命令之后，根据重建的逻辑到物理地址转换 映射902，可以重建一个或多个表，以及基于这种重建的表，可以选择多个 S块中的一个或多个用于垃圾收集，如图11中B153所示。为此，在已经 重建了逻辑到物理地址转换映射902之后，控制器202可以重建包含多个S 块的每一个中空闲空间的量的空闲空间表，以及其它可能的动作。为了重 建这种空闲空间表，可以计算多个块的每一个中的空闲空间的量。取代控 制器202跟踪每一个S块中的空闲空间的量，根据一个实施例，控制器202 可以跟踪每一个S块中有效数据的量。用于每一个S块的这种信息可以容 易地在逻辑到物理地址转换映射902中可用，所述信息可以被配置为包含 在非易失性存储器中的每一个L页的大小的记录。根据每一个S块中有效 数据的量以及通过确认S块的大小，控制器202可以通过从S块的预定大 小减去每一个S块中有效数据的大小(从读取逻辑到物理地址转换映射902 获得的)来计算每一个S块中的空闲空间的量。在S块中存储的有效数据 的量与其大小之间的差可以等于或相关于每一个S块中空闲空间的量。因 此，根据逻辑到物理地址转换映射902的单个顺序读取，或通过在重建逻 辑到物理地址转换映射902时更新在每一个S块中的有效数据的量，可以 通过控制器202来计算在每一个S块中的空闲空间的量。每一个S块中所 累积的(即，跨逻辑到物理地址转换映射902中的条目相加)有效空间的 量可以存储在例如在易失性存储器中维护的表中。例如，系统块信息表908 (例如，参见图10A)可以用于所述目的。可选地，控制器202可以创建 单独的有效大小信息表，并且以每一个S块的有效数据的累积大小来填充 该表。如图13的表1702所示，在该示例中，S块1具有存储于其中的总共 450MB的有效数据，并且S块2具有存储在其中的总共1.5TB的有效数据。 由于S块的大小是已知先验的，所以每一个S块中的空闲空间的量可以是 容易计算出的。在另一实施例中，通过基于来自逻辑到物理地址转换映射 902的信息来直接相加空闲空间的量，从而执行计算空闲空间的量。

根据一个实施例，数据存储设备报告：其准备好在已经完成重建逻辑 到物理地址转换映射902(以及可选地其它内务处理活动，例如填充易失性 存储器中的S日志映射904以及其它表)之后立即处理主机命令。在这种 实施例中，数据存储设备被配置为实施空闲空间计数操作(例如，包括重 建空闲空间)同时和/或在处理主机(即，数据访问)命令之后。这种输入 主机命令可以改变S块的空闲空间计数，同时执行第二阶段。一个实施例 解释在每一个S块中呈现的有效数据的量中的这种改变。

例如，在重建逻辑到物理地址转换映射902之后，可以从开始到结束 顺序读取映射902。控制器202可以被配置为在读取现在相干的逻辑到物理 地址转换映射902期间跟踪指针，如图14中1902处所示。根据一个实施 例，在处理主机命令同时实施这种空闲空间计数时，控制器202可以被配 置为取决于由于写入命令而修改的L页是与已经由控制器202处理用于空 闲空间计数的L页号相关联还是与当顺序读取逻辑到物理地址转换映射 902时尚未被控制器202所读取的L页号相关联而不同地动作。根据一个实 施例，如果由于写入命令而修改的L页与已经由控制器202处理用于空闲 空间的L页号相关联，如图14中附图标记1904处的“新写入1”所示，则 控制器202可以以上述方式来实施空闲空间计数。在该情况下的空闲空间 计数是必要的，因为控制器202已经处理了与当前更新的用于空闲空间的L 页相对应的条目，并且已经将其长度增加到存储更新后的L页的S块的有 效数据的运行计数。更新的长度与L页的先前长度可能是相同的，在该情 况下，如果L页被写入到相同S块，则有效数据的运行计数将不变。然而， 如果执行写入导致L页长度的改变或者如果被写入到不同的S块，则S块 中数据的累积大小将实际改变。为了在每一个块中维护空闲空间的准确计 数，因此，需要控制器202返回并且适当地对由于更新L页而可用的空闲 空间进行计数。

然而，如果由于写入命令而修改的L页与尚未由控制器202处理用于 空闲空间的L页号相关联，则一个实施例允许控制器202避免实施空闲空 间计数活动，并且继续其顺序读取逻辑到物理地址转换映射902。事实上， 如果执行的写入命令导致更新L页号尚未被控制器202读取的L页，例如 附图标记1906处“新写入2”的情况，则不需要执行用于空闲空间计数的 单独处理，因为当指针1902达到现在新更新的L页的L页号时，控制器 202将正确地累积表1702中的有效数据的大小。

根据一个实施例，非易失性存储器的块206可以包括多级单元(MLC)， 其存储例如每单元2位。对于MLC设备，至少存在可能不是连续的较低页 和较高页。MLC的较低页通常在其较高页之前被编程。因为在MLC设备 中单元电压的分布，如果在对较高页进行编程时或期间电力被中断则可能 损坏MLC的较低页。事实上，在编程期间，MLC所存储的电荷以逐步的 方式逐渐增加直到到达表示所期望的逻辑状态的期望电压。根据一个实施 例，这就是存储S日志的系统带可以被配置为仅使用块中较低页以用于增 加可靠性的原因。

为了进一步减轻较低页讹误错误，一个实施例利用非易失性缓冲器来 暂时存储更新后的L页至少直到每一个MLC的较低页和较高页二者被编 程。当较低页和较高页不连续时，非易失性存储设备可以被配置为足够大 以便存储MLC的较低页和较高页。也就是，非易失性缓冲器可以被配置为 至少足够大以使得能够在数据存储设备丢失电力之后从较低页讹误中恢 复。这种非易失性缓冲器在图2以附图标记211示出。非易失性缓冲器211 可以被配置为环形缓冲器。根据一个实施例，控制器202可以被配置为在 非易失性缓冲器211中累积将写入到非易失性存储器的数据。为此，控制 器202可以分配缓冲器211中的空间，并且将累积的数据写入到在缓冲器 211中分配的空间。累积数据的至少一部分随后可以存储在非易失性存储器 的较低页中以及在缓冲器211中的分配空间中。在稍后的时间，与先前编 程的较低页相对应的较高页本身可以被编程，此时在非易失性缓冲器211 中先前分配的空间可以被解除分配，以针对进一步输入的数据留出空间。 有利地，提供这种非易失性缓冲器211和在其中暂时存储的新更新的L页 使得控制器202在累积数据写入到非易失性缓冲器211中的分配空间之后 生成写入确认并且将该写入确认发送到主机218。因此，该确认可以比在数 据在非易失性存储器中编程之后发送的确认的情况早些发送，同时避免使 用例如超级电容器或电池备份的NAND之类的这种备份电源机制。例如， 非易失性缓冲器211可以包括磁性随机存取存储器(MRAM)，其在以非易 失性方式存储数据的同时以与DRAM可比较的速度操作。利用这种非易失 性缓冲器211，在丢失电力之后恢复对数据存储设备的电力后，使得控制器 能够从非易失性缓冲器211读取数据，并且将读取的数据的一部分存储在 非易失性存储器中。如图2的209处所示，数据可以在非易失性缓冲器211 中以S页为单元进行累积、写入和存储。

根据一个实施例，非易失性缓冲器211使得控制器202能够读取存储在 非易失性缓冲器211中的L页，并且利用从中读取的逻辑页来重建逻辑到 物理地址转换映射902。在启动期间，当重建逻辑到物理地址转换映射902 时，控制器202可以被配置为读取与冷带中存储的L页相对应的系统带中 的S日志。冷带可以是控制器202分配的专用于存储最近垃圾收集的L页 的非易失性存储器的一部分。然而，冷带可能在对应的较高页尚未被编程 的较低页处存储“不安全的”L页数据。当控制器执行写入命令时，这导致 了相对应的较高页的编程，这种较低页数据可能冒较低页讹误的风险。因 此，该较低页讹误能够影响逻辑到物理地址转换映射902的相干性，导致 可能对数据存储设备致命的错误。

根据非易失性存储器包括MLC的一个实施例，当重建逻辑到物理地址 转换映射902时，控制器202可以被配置为读取与冷带相对应的S日志， 而不超过存储在与相对应的较高页已经被编程的较低页中的安全页相对应 的其条目。这确保后续执行的写入命令不能导致用于重建逻辑到物理地址 转换映射902的数据的较低页讹误。还根据一个实施例，对于与冷带相对 应的S日志的条目，其中所述S日志的条目与相对应的较高页未被编程的 较低页处存储的不安全的L页相对应，控制器202还可以被配置为停止处 理包含与这种不安全的L页相对应的条目的S日志，并且代替从非易失性 存储器211中读取不安全的L页，并将其写入到非易失性存储器中。这继 而生成对逻辑到物理地址转换映射902和相对应的S日志条目和/或新的S 日志的更新。该过程可以针对由包含这种条目(例如，与冷带相对应的包 括存储在相对应的较高页未被编程的较低页中的不安全的L页的S日志的 条目)的S日志所引用的一个或多个最近写入的S块来实施。然后，可以 对这种一个或多个S块进行垃圾收集。以这种方式，非易失性缓冲器211 可以用于在重构逻辑到物理地址转换映射902(图11的映射重建的阶段1) 期间恢复可能不安全的L页，以及正确地安排垃圾收集(图11的映射重建 的阶段2)。在其它实施例中，针对其它类型的数据(代替冷带数据)来执 行与不安全的页相关的额外处理。

例如，考虑3.2TB数据存储设备。可以要求传统的数据存储设备来读 取将存储映射表104(图1)的易失性存储器。因为尚未设置易失性存储器 中的ECC，这继而要求初始化过程。假设易失性存储器大小是16GB的级 别，则这将需要例如2秒的级别。之后，传统数据存储设备必须执行16GB 的写入交错16GB的随机读取，以重建映射表104以及更新空闲空间信息。 仅在此之后，常规数据存储设备才可以报告其准备好接受和服务主机命令。 相反地，为了实施当前的两阶加电过程，一个实施例不需要预先读取易失 性存储器，并且因此不需要读取易失性存储器直到已经写入所有条目。事 实上，根据一个实施例，在离开制造工厂之前，数据存储设备可以是TRIMed (经受TRIM命令或相同功能等价物的所有物理页)，由此以有效条目来预 填充逻辑到物理地址转换映射902。之后，可以执行到易失性存储器的16GB 随机写入，以处理来自非易失性存储器的所有S日志到现在重建的和相干 的逻辑到物理地址转换映射902。在该早期阶段并且在实施空闲空间计数活 动之前，控制器202可以报告其准备好服务主机数据访问命令。之后，在 已经报告了其准备好执行数据访问命令之后，控制器202可以实施6.4GB 的顺序易失性存储器读取以更新有效数据表1702(图13)作为其空闲空间 计数活动的一部分。之后，当实施数据访问命令时或之后，数据存储设备 可以选择最佳的S块进行垃圾收集。根据一个实施例，控制器202可以被 配置为至少部分地基于其中可用的空闲空间量来选择这种S块以用于垃圾 收集。根据一个实施例，控制器202可以选择具有最多空闲空间的S块以 进行垃圾收集。有利地，根据一个实施例，这种空闲空间计数和块捡取可 以在硬件中实施并且在接受和执行数据访问命令的驱动器上实施。

垃圾收集

图15-18是示出了根据一个实施例的垃圾收集方面的框图。可以扫描用 户S块信息表906(图10A)来选择“最佳”S块用于垃圾收集。存在可以 被评估以选择哪个S块进行垃圾收集的大量标准。例如，用于垃圾收集的 最佳S块可以是具有最大量的空闲空间和最低程序擦除(PE)计数的S块。 可选地，这些和/或其它标准可以被加权以选择S块进行垃圾收集。出于示 例的目的，在图15-18中所选的用于垃圾收集的S块是S块15，在1502处 示出。应该注意的是，用户S块信息表906(图10A)可以包括每一个被跟 踪的S块所经历的PE周期量的运行计数等其它项目的信息，其可以被评估 以决定哪个S块用于垃圾收集。如1502所示，S块15具有有效数据(散列 块)和无效数据(非散列块)的混合。

既然S块15已经被选择用于GC，则可以查阅(例如由S块号进行索 引)S日志映射(参见图10B中的904)，以发现用于那个S块的对应的S 日志在非易失性存储器中的位置。然后，由S日志映射904指向的S日志 利用S日志号的头部(例如27LSB)来定位，并且被读取到缓冲器1009 中，如图15所示。也就是，由S日志映射904(图10B)所指向的系统S 块1804中的E页可以被访问，并且可以将在所述位置处开始存储的S日志 读取到缓冲器1009。之后，在缓冲器1009的S日志中的每一个物理到逻辑 条目随后可以与在逻辑到物理地址转换映射1802中的相对应的条目进行比 较。也就是说，S日志中的L页的地址可以与逻辑到物理地址转换映射1802 中的L页的地址进行比较。对于缓冲器1009中的S日志的每一个条目，可 以判定所述条目的L页的地址是否匹配在逻辑到物理地址转换映射1802中 相对应的条目的L页的地址。如果两者匹配，则所述条目有效。相反地， 如果在S日志中的L页的地址与在逻辑到物理地址转换映射1802中L页的 条目不匹配，则在S日志中的所述条目无效。根据一个实施例，当在条目 被解析和比较的S日志中发现有效条目时，可以将其写入到缓冲器1009， 如图16所示。在处理了用于S块15的每一个S日志之后，也如图16在附 图标记1502处所示的，S块15现在仅包括无效数据。当系统S块1804中 的S日志中的条目指向这种有效数据时，系统S块1804中的S日志被示出 为散列的，表示其现在是陈旧的。逻辑到物理地址转换映射1802随后可以 被更新，生成用于读取到缓冲器1009的有效数据的新的E页开始地址。需 要注意，在更新逻辑到物理地址转换映射期间，可以针对有效条目重新检 查映射1802，并且在映射更新过程期间锁定映射1802以保证原子性。然后 可以将有效数据写出到冷S块1801(热块用于最近写入主机数据，不是垃 圾收集的数据)，如图17所示。接着，如图18中1302处所示，这生成用 于冷S块1801的新的S日志。在后续时间(例如，在已经填充了足够量的 条目之后)，可以将S日志1302写出到系统带中的系统S块1804。S块15 现在已经进行了垃圾收集，并且其空间现在已经可能被添加到数据S块信 息908中用于S块15的空闲空间计数。现在，系统S块信息908表示整个 S块15都是空闲空间，其在之后可能被擦除，其PE计数被更新并且对于 主机数据可用。注意，在S块15中仍存在无效S日志。在系统带内被无效 S日志占据的闪速存储器中的空间可能将在后续时间进行垃圾收集、擦除并 且重新使用。

虽然已经描述了本公开的某些实施例，但这些实施例仅通过示例方式 表示，并且不是要限制本公开的范围。事实上，本文所描述的新颖的方法、 设备和系统可以以多种其它形式具体体现。此外，在不偏离本公开的精神 的情况下，可以做出对本文描述的方法和系统形式的各种省略、替代和改 变。随附权利要求及其等价物是要覆盖落入本公开的范围和精神内的这种 形式或修改。例如，本领域中的技术人员将理解在各个实施例中，实际的 物理和逻辑结构可以不同于图中所示出的。取决于实施例，以上在示例中 描述的某些步骤可以被移除，而可以添加其它步骤。另外，以上公开的具 体实施例的特征和属性可以以不同方式组合以形成额外的实施例，所有这 些都落入本公开的范围内。虽然本公开提供了某些优选的实施例和应用， 但是对于本领域的技术人员而言显而易见的是，包括未提供本文阐述的所 有特征和优点的实施例的其它实施例也落入本公开的范围内。因此，本公 开的范围是要仅通过随附权利要求来进行限定。