写入非易失性存储器的技术

1.一种用于存储数据的方法，包括：
执行多次写操作以在不同的物理存储位置内存储数据，每一个所述物理存储位置均与在所述物理存储位置之间共同共享的一逻辑地址相关联；
在所述物理存储位置内存储顺序信息以指示所述写操作的哪一次最后出现；
储存与被存储在每个物理存储位置处的内容的消耗状态有关的信息；以及响应于掉电，使用所述顺序信息来重建有关所储存内容的消耗状态的信息。
2.如权利要求1所述的方法，其特征在于，所述顺序信息包括全局序号、本地序号和时间戳之一。
3.如权利要求1所述的方法，其特征在于，所储存内容的消耗状态包括用过、有效或空白之一。
4.如权利要求1所述的方法，其特征在于，还包括：
在所述物理存储位置内存储所述逻辑地址以指示所述写操作的哪一次最后出现。
5.如权利要求1所述的方法，其特征在于，每个所述物理存储位置均存储有关所述逻辑地址的数据的不同版本。
6.如权利要求1所述的方法，其特征在于，还包括：
在每个所述物理存储位置内均存储所述逻辑地址的指示。
7.如权利要求1所述的方法，其特征在于，所述物理存储位置是非易失性存储器的一部分，所述方法还包括：
响应于每一次所述写操作，更新易失性存储器中的状态信息以指示所述物理存储位置的哪一个存储有效数据。
8.如权利要求1所述的方法，其特征在于，所述物理存储位置是非易失性存储器的一部分，所述方法还包括：
响应于每一次所述写操作，更新逻辑-物理地址转换表，所述逻辑-物理地址转换表指示所述逻辑地址和所述物理存储位置之一之间的映射。
9.如权利要求7所述的方法，其特征在于，还包括：
在块擦除操作中擦除所述被指示的物理存储位置。
10.如权利要求1所述的方法，其特征在于，还包括：
响应于掉电，使用所述顺序信息来重构指示所述逻辑地址和所述物理存储位置之一之间映射的逻辑-物理转换表。
11.如权利要求1所述的方法，其特征在于，还包括：
响应于掉电，使用所述顺序信息来判定所述物理存储位置的哪些没有存储有关所述逻辑地址的有效数据。
12.如权利要求1所述的方法，其特征在于，还包括：
响应于掉电，使用所述顺序信息判定所述物理存储位置的哪些处于空白状态以及所述物理存储位置的哪些是用过的。
13.一种用于存储数据的装置，包括：
用于执行多次写操作以在非易失性存储器的不同的物理存储位置内存储数据的装置，每一个所述物理存储位置均与在所述物理存储位置之间共同共享的一逻辑地址相关联；
用于在所述物理存储位置内存储顺序信息以指示所述写操作的哪一次最后出现的装置；
用于储存与被存储在每个物理存储位置处的内容的消耗状态有关的信息的装置；以及用于响应于掉电，使用所述顺序信息来重建有关所储存内容的消耗状态的信息的装置。
14.如权利要求13所述的装置，其特征在于，所述顺序信息包括全局序号、本地序号和时间戳之一。
15.如权利要求13所述的装置，其特征在于，所储存内容的消耗状态包括用过、有效或空白之一。
16.如权利要求13所述的装置，其特征在于，还包括用于在所述物理存储位置内存储所述逻辑地址的装置。
17.如权利要求13所述的装置，其特征在于，每个所述物理存储位置均存储有关所述逻辑地址的数据的不同版本。
18.如权利要求13所述的装置，其特征在于，还包括用于在每个所述物理存储位置内均存储所述逻辑地址的指示的装置。
19.如权利要求18所述的装置，其特征在于，还包括：
用于响应于每一次所述写操作，更新易失性存储器中的状态信息以指示所述物理存储位置的哪一个存储有效数据的装置。
20.如权利要求18所述的装置，其特征在于，还包括：
用于响应于每一次所述写操作，更新指示所述逻辑地址和所述物理存储位置之一之间映射的逻辑-物理地址转换表的装置。
21.如权利要求13所述的装置，其特征在于，还包括用于响应于掉电，使用所述顺序信息来重构指示所述逻辑地址和所述物理存储位置之一之间映射的逻辑-物理转换表的装置。
22.一种用于存储数据的装置，包括：
用于使用存储在动态随机存取存储器内的逻辑-物理地址转换表来执行多次写操作以在非易失性存储器的不同的物理存储位置内存储数据的装置，每一个所述物理存储位置均与在所述物理存储位置之间共同共享的一逻辑地址相关联，
用于在所述物理存储位置内存储顺序信息以指示所述写操作的哪一次最后出现的装置，
用于储存与被存储在每个物理存储位置处的内容的消耗状态有关的信息的装置；以及用于响应于掉电，使用所述顺序信息来重建有关所储存内容的消耗状态的信息的装置。
23.如权利要求22所述的装置，其特征在于，所储存内容的消耗状态包括用过、有效或空白之一。
24.如权利要求22所述的装置，其特征在于，还包括用于响应于掉电，使用所述顺序信息来重构所述逻辑-物理地址转换表的装置。
25.如权利要求22所述的装置，其特征在于，还包括响应于掉电，使用所述顺序信息来判定所述物理存储位置的哪些没有存储有关所述逻辑地址的有效数据的装置。
26.一种用于存储数据的设备，包括：
用于执行多次写操作以在不同的物理存储位置内存储数据的装置，每一个所述物理存储位置均与在所述物理存储位置之间共同共享的一逻辑地址相关联；
用于在所述物理存储位置内存储顺序信息以指示所述写操作的哪一次最后出现的装置；
用于储存与被存储在每个物理存储位置处的内容的消耗状态有关的信息的装置；以及用于响应于掉电，使用所述顺序信息来重建有关所储存内容的消耗状态的信息的装置。
27.如权利要求26所述的设备，其特征在于，所储存内容的消耗状态包括用过、有效或空白之一。
28.如权利要求26所述的设备，其特征在于，还包括用于在每个所述物理存储位置内均存储所述逻辑地址的指示的装置。
29.如权利要求26所述的设备，其特征在于，还包括用于响应于每一次所述写操作，更新易失性存储器中的状态信息以指示所述物理存储位置的哪一个当前正与所述逻辑地址相关联的装置。
30.如权利要求26所述的设备，其特征在于，所述物理存储位置是非易失性存储器的一部分，所述设备还包括用于响应于每一次所述写操作，更新指示所述逻辑地址和所述物理存储位置之一之间映射的逻辑-物理地址转换表的装置。
31.如权利要求26所述的设备，其特征在于，还包括用于响应于掉电，使用所述顺序信息来重构指示所述逻辑地址和所述物理存储位置之一之间映射的逻辑-物理转换表的装置。
32.如权利要求26所述的设备，其特征在于，还包括用于响应于掉电，使用所述顺序信息来判定所述物理存储位置的哪些没有存储有关所述逻辑地址的有效数据的装置。
33.如权利要求26所述的设备，其特征在于，还包括用于响应于掉电，使用所述顺序信息来判定所述物理存储位置的哪些被擦除的装置。

写入非易失性存储器的技术\n[0001] 背景\n[0002] 本发明一般地涉及写入非易失性存储器的技术。\n[0003] 诸如闪存之类的非易失性半导体存储器对需要在正常系统关机/休眠或掉电的情况下保持数据的应用很有吸引力。于是，由闪存设备构成的存储器就可用于在磁盘高速缓存或固态磁盘中存储数据。虽然典型的闪存具有远快于磁性存储设备的存取时间，但是不同于磁性存储设备，闪存的各单元通常在首先没有被擦除的情况下无法被重写。\n[0004] 作为一个更具体的实例，在将一位数据存储在常规闪存单元内之前，首先擦除该单元。在此擦除状态下，该单元指示一特定的逻辑状态，诸如逻辑“1”状态。在对该闪存单元的后续写操作中，如果要在该单元内存储逻辑1，则该单元的状态保持不变。然而，如果要在该单元内存储逻辑0，则编程该单元以将该单元改变为0逻辑状态。于是，对闪存单元的典型写入通常涉及两个存储器操作：擦除存储单元的第一操作；以及编程该存储单元逻辑状态的第二操作。这多个操作又造成用于写入闪存的总时间。\n[0005] 于是，存在一种持续的需要，希望以更好的方式降低写入诸如闪存的非易失性半导体存储器的总时间。\n[0006] 附图简述\n[0007] 图1是根据本发明的实施例用于非易失性半导体存储器的动态寻址方案的图示。\n[0008] 图2是根据本发明实施例的存储器系统的框图。\n[0009] 图3和图8是根据本发明实施例来描述在对非易失性半导体存储器写操作方面所使用的技术的流程图。\n[0010] 图4是根据本发明实施例存储在非易失性存储器的存储位置内的数据的图示。\n[0011] 图5是根据本发明实施例的逻辑-物理转换表的图示。\n[0012] 图6是根据本发明实施例的空白池表的图示。\n[0013] 图7是根据本发明实施例的易失性元数据的图示。\n[0014] 图9是根据本发明实施例来描述一种用于在掉电后重构该逻辑-物理转换表的中间表的图示。\n[0015] 图10是根据本发明实施例来描述一种用于在掉电后重构该逻辑-物理转换表的技术的流程图。\n[0016] 图11是根据本发明实施例的计算机系统的框图。\n[0017] 详细描述\n[0018] 根据在此描述的本发明的各实施例，为了在非易失性半导体存储器(在此被称为“非易失性存储器”)方面最小化存储器的写入等待时间而使用动态寻址。更具体地，根据在此描述的本发明的各实施例，从软件的观点看，非易失性存储器是使用逻辑地址来寻址的。\n从对存储器执行的物理读取和写入操作的观点看，动态寻址将逻辑地址转换成或映射至存储器的物理地址。动态寻址不断地改变逻辑和物理地址之间的映射以确保每个逻辑写操作都能够让数据存储在该非易失性存储器先前被擦除的位置(即，在不同的物理地址处)内。\n于是，通过动态寻址，每个逻辑写操作均生成单个操作。这将与对非易失性存储器使用两次存取(一次是擦除/无效旧的物理位置，而另一次则是在新的预擦除物理位置上写入该数据)的动态寻址相比较。\n[0019] 更具体地，参见图1，根据本发明的某些实施例，动态寻址方案10将非易失性存储器的物理地址分组成空白池20、有效池30和用过池40。空白池20表示未分配的物理地址，其相关联的存储单元被擦除，正准备被编程并由此准备被分配逻辑地址。有效池30表示与存储有效数据并被分配逻辑地址的存储单元相关联的那些物理地址。用过池40表示不再存储有效数据，不再与逻辑地址相关联并且要被擦除的那些物理地址。在使用块擦除操作来擦除物理地址的邻接块(例如，页)时，用过池40的物理地址又被重新分组为空白池20。注意到块擦除要比响应于每次逻辑写操作一次擦除一个物理地址更为有效，并且作为补充，非易失性存储器(诸如，NAND闪存)可只允许块擦除。\n[0020] 作为一个更为具体的示例，非易失性存储器的示例性物理地址14(与一组存储单元或存储位置相关联)可以按如下的方式在空白池20、有效池30和用过池40之间转换。\n最初，诸如在结合非易失性半导体存储器的系统启动时或在被擦除之后，物理地址14属于空白池20。换句话说，由于位于空白池20中，使得物理地址14可用于分配一特定的逻辑地址。于是，当数据被写入一特定逻辑地址时，物理地址14就被分配给该逻辑地址，使得该数据被存储在物理地址14处；并且物理地址14随后变为有效池30的一部分。然而对物理地址14的另一写入在与物理地址14相关联的存储单元未被擦除的情况下不能出现。因此，当出现对同一逻辑地址的下一写入时，将另一物理地址分配给该逻辑地址，并且与该物理地址14相关联的存储内容就随着物理地址14变为用过池40的一部分而变为无效或“用过”。\n[0021] 与物理地址14相关联的存储单元没有必要一变为“用过”就被立刻擦除，而宁可在块擦除操作中擦除这些存储单元。此刻，物理地址14再次变为空白池20的一部分，并且可以被分配给另一逻辑地址。\n[0022] 参见图2，根据本发明的某些实施例，存储器系统50使用上述动态寻址方案10并可以在有关诸如NAND闪存之类的非易失性半导体大容量存储存储器54(在此称为“非易失性存储器54”)方面使用。非易失性存储器54含有使用物理地址寻址的物理存储单元\n55的阵列。根据本发明的某些实施例，存储器系统50的控制器52通过在逻辑地址和物理地址空间之间的变换来执行动态寻址。更具体地，根据本发明的某些实施例，控制器52耦合至诸如动态随机存取存储器(DRAM)之类的易失性存储器60。易失性存储器60存储逻辑-物理转换表(在此被称为“L2P表62”)，而该表由控制器52用于将逻辑地址映射至存储器54的物理地址。该映射不断改变，由此使得控制器52不断更新L2P表62以跟踪每个逻辑地址到不同物理地址的再映射。\n[0023] 同样如图2所描述，根据本发明的某些实施例，易失性存储器60存储空白池表66，该表指示存储器54的哪些物理地址被包括在空白池20内(见图1)。于是，当控制器52要对逻辑地址执行写操作时，控制器52通常会从空白池表66中选择一可用物理地址，更新L2P表62用以将该逻辑地址再映射至所选的物理地址，并且在所选的物理地址处对非易失性存储器54执行相应的写操作。\n[0024] 在可被存储在易失性存储器60中的其他数据中，根据本发明的某些实施例，易失性存储器60可以存储元数据68，元数据68含有(连同其他可能的信息)与那些被存储在每个物理地址处的存储器内容的消耗状态有关的信息。根据本发明的某些实施例，对于非易失性存储器54的每个可寻址位置而言，元数据68指示存储在该位置中的数据内容是用过、有效还是空白。除了空白池表66、L2P表62和元数据68之外，易失性存储器60还存储程序指令70，这些指令在被执行时会使得控制器52执行在此公开的物理写入、地址转换和掉电恢复技术中的一种或多种。\n[0025] 于是作为概括，控制器52使用易失性存储器60来存储指示逻辑-物理地址映射的信息以及指示非易失性存储器54的可寻址存储位置的状态的信息。相比于非易失性存储器(诸如存储器54)，在易失性存储器60中存储这些信息是有利的，这是由于易失性存储器60有着相对快的存取时间，从而给出较高的访问次数来维持这些信息。易失性信息可以在例如关机、休眠、挂起或低功耗检测等关键事件处被存储在非易失性存储器内，并在随后的重新启动/重新开始的过程中从非易失性存储器内恢复。然而，一般而言，关于这一技术的潜在挑战是存储在易失性存储器60内的信息在存储器系统50掉电的情况下会丢失。虽然可以对易失性存储器60的内容做出周期性地备份，但是这些备份本身对恢复丢失信息而言是不够的。因此，一旦从掉电中恢复，如果没有如下公开的本发明的各特征，控制器52将会无从知晓逻辑-物理映射以及非易失性存储器54的各可寻址存储位置的消耗状态，于是就不能重构存储在易失性存储器60中的信息。\n[0026] 允许控制器52重构或恢复在掉电之前存储在易失性存储器60内的信息的一种可能的技术是一种在其中控制器52将所有需要的状态信息保持在诸如非易失性存储器54之类的非易失性存储器内的技术。作为一个更具体的示例，为了实现该技术，控制器52可以对每次逻辑写操作执行对非易失性存储器54的两次写操作。更具体地，使用该技术，非易失性存储器54可用于存储当前元数据状态信息，以指示某一特定物理单元当前是有效还是用过的。因此，对于每次逻辑写操作而言，控制器52可以写入新分配的物理地址并写入先前分配的物理地址以将该物理地址标记为用过。然而，这一安排的潜在困难是需要为每一单次逻辑写操作进行两次对非易失性存储器54的写操作，从而会增加存储器54的写等待时间。\n[0027] 根据在此描述地本发明的实施例，控制器为每次逻辑写操作对非易失性存储器54执行单次(例如，而非两次)写操作。为了允许在掉电之后恢复存储在易失性存储器60内的信息(诸如，存储在L2P表62和空白池表66中的那些信息)，控制器52在每次物理写操作中都在非易失性存储器54内存储诸如时间戳或序号之类的顺序信息。更具体地，根据本发明的某些实施例，控制器52为对非易失性存储器54的每次写操作生成一个全局序号。\n控制器52为每次写操作递增该全局序号，以使得该序号对写操作具有(例如)不断增加的值。正如以下要描述的，这些序号可由控制器52在掉电之后用于重构在前写操作(发生在掉电之前)的时间线，从而确定非易失性存储器54的哪些可寻址位置存储了有效数据(并还藉此确定了哪些位置存储了用过的数据)。\n[0028] 参见图3，作为概括，根据本发明的某些实施例，控制器52一般在逻辑写操作方面执行方法74。依照该方法74，控制器52为不同的写操作向一逻辑地址分配不同的物理存储位置(框76)。于是，对于向某一特定逻辑地址的第一次写操作而言，控制器52写入非易失性存储器54的第一物理地址；而对这一逻辑地址的下一次写操作而言，控制器52写入非易失性存储器54的第二物理地址。依照该方法74，控制器52在该物理存储位置内存储序号和逻辑地址(框78)，它们共同地指示被分配给该逻辑地址的最后物理存储位置。如上所述，序号允许控制器52在掉电出现之后重建易失性存储器60内的信息。\n[0029] 图4描绘了根据本发明某些实施例可存储在非易失性存储器54的每个可寻址存储位置内的示例性数据80。数据80包括作为相应逻辑写操作的对象数据的内容数据82。\n数据80还包括元数据84，元数据84则包括与内容数据82状态有关的各种信息。数据字段\n86和87是元数据84的一部分，它们分别指示与用于存储内容数据82的写操作相关联的序号和逻辑地址。对于其中非易失性存储器54用作磁盘高速缓存的应用而言，元数据84可包括与相关联的高速缓存线的状态有关的数据。于是，元数据84可存储除了在此描述的示例性数据之外的其他和/或不同的数据。\n[0030] 此外，元数据84可以指示内容数据82的消耗状态，正如内容数据82是用过的还是有效的。然而，所指示的消耗状态可能不是当前的，因为控制器52不为每次逻辑写操作而在先前被映射至该逻辑地址的物理地址处将该内容标记为用过。因此，非易失性存储器\n54的若干位置可含有指示同一逻辑地址并指示该关联内容数据82有效的元数据84。易失性存储器60内所包含的该信息可由控制器52用于在正常操作期间从用过的数据中挑拣出有效数据；并且在掉电的情况下，控制器52可以通过从非易失性存储器54中读取序号来从用过的数据中挑拣出有效数据并重构先前存储在易失性存储器60内的信息，以使得存储器系统50从掉电中恢复。\n[0031] 如上所述，序号是全局的，在本发明的某些实施例中，在这一点上不管逻辑地址如何，对于向非易失性存储器54的每次写入，序号都是不同的。然而，根据本发明的其他实施例，序号对于每个逻辑地址而言可以是唯一的，藉此控制器52可以在非易失性存储器54内存储这些序号(在此称为“本地序号”)，这些序号各自都在相同的范围上延伸，但可通过关联的逻辑地址相互区别。于是可能的情况是例如非易失性存储器54为逻辑地址A存储了逻辑序号“5”，并为逻辑地址D也存储了逻辑序号“5”。使用本地序号的一个潜在缺点是需要有多个计数器而非单个计数器(对于全局序号而言)用于生成有关各逻辑地址的序号。\n然而，使用本地序号的潜在优势则在于元数据84内相对应的数据字段尺寸较小。\n[0032] 图5描绘了根据本发明某些实施例的L2P表62。L2P表62包括含有N个条目\n94(作为示例描绘的条目941，942...94N)的固定阵列93，其中每个条目都与一特定逻辑地址相关联并且存储用于该逻辑地址的物理地址的指示。于是，为了检索用于某一逻辑地址的当前物理地址，就通过逻辑地址指针91来索引固定阵列93的各条目94。\n[0033] 如上所述，在数据被存储在某一物理地址之后，存储在相应存储位置内的数据就变为用过的，于是相应的物理地址对该逻辑地址而言就变为“无效”。于是，根据本发明的某些实施例，条目94可以存储预先确定的值(例如，全“1”的值)以指示无效的物理地址。代替地，根据本发明的某些实施例，易失性元数据68可以指示哪些物理地址是有效的而哪些是用过的；并且作为又一代替，在本发明的某些实施例中，L2P表62可包括与各条目94相关联的一位，用以指示相应的物理地址是无效还是有效。于是，许多变化都是可能的并且在所附权利要求的范围内。\n[0034] 图6描绘了根据本发明某些实施例的空白池表66。空白池表66包括P个条目\n100(作为示例描绘的条目1001，1002...100P)，其中每个条目含有作为空白池20(见图1)的一部分的存储位置的物理地址。空白池表66的条目数P随着各物理地址不断地由于新的写操作而从空白池表66中取出并在块擦除操作之后被添加至空白池表66而不断变化。根据本发明的某些实施例，空白池表66可以包括先进先出(FIFO)缓冲器99或队列(作为一个示例)，其中在FIFO缓冲器99的一端添加条目100，并且条目在该缓冲器另一端将条目分配给逻辑地址。其他的安排也是可能的并且在所附权利要求的范围之内。\n[0035] 图7描绘了根据本发明某些实施例的易失性元数据68。可将易失性元数据68安排成包括Q个条目110(描绘作为示例的条目1101，1102...110Q-1，110Q)的固定阵列109的形式，其中每个条目都与非易失性存储器54的物理地址之一相关联。于是，可利用物理地址指针111来索引各条目110。如图7所描绘，每个条目110可指示该相关联的物理地址含有用过的还是有效的数据。此外，根据本发明的某些实施例，每个条目110可以指示该相关联物理地址是与一擦除还是空白存储位置相关联。于是，许多变化都是可能的并且在所附权利要求的范围内。\n[0036] 参见图8，控制器52(参见图2)通常可以响应于逻辑写操作执行方法150。逻辑写操作以逻辑地址为目标并且指示要被存储在该逻辑地址处的数据。依据方法150，控制器\n52如框152所述，诸如通过用逻辑地址从L2P表62(参见图2)中查找特定物理地址，来为该逻辑地址获取一物理地址。控制器52随后判定(菱形框154)该物理地址是否有效。这在正常操作中是很常见的情况，虽然一特定物理地址也可以在存储器系统50(参见图2)最初上电之后与空白池相关联。\n[0037] 如果控制器52判定(菱形框154)当前物理地址有效，则控制器52就在L2P表62内将当前物理地址标记为无效(框158)。于是，如果当前物理地址正存储着有效数据，那么依据在此讨论的动态寻址方案，则使用另一物理地址(如下进一步描述的)来存储作为该当前逻辑写操作的对象的数据。接下来，控制器52更新易失性元数据68以指示在当前物理地址处的内容数据82(参见图2和图4)。\n[0038] 在框162之后或是在判定(菱形框154)当前物理地址无效之后，控制器52判定(菱形框160)是否是时候补充空白池20。例如，在本发明的某些实施例中，控制器52可以监视组成空白池20的物理地址的数量。一旦判定该数量已下降到预定阈值之下，控制器52就可采取行动以补充空白池20。例如，这些动作可以包括把用过的单元重新定位(框164)至一邻接块内。于是，这一重新定位可涉及把带有关联更新的、有效的和用过的非易失性存储器54的可寻址存储位置移至易失性数据60。一旦该邻接块被建立，控制器52就如框160所述擦除该块。随后，控制器52更新(框170)空白池表66。\n[0039] 无论控制器52是否补充空白池20，控制器52随后都依据方法150，从空白池20中检索(框174)下一个物理地址(来代替当前物理地址)并递增(框178)顺序计数器。\n在结合图8讨论的实施例中假设使用全局顺序计数器。然而，如上所述，根据本发明的其他实施例，可将一个单独的本地顺序计数器用于每一个逻辑地址。\n[0040] 控制器52随后将内容和元数据(包括序号和逻辑地址)写入(框180)这一新物理地址。随后，控制器52更新(框182)L2P表62，用以将这一新物理地址映射至或分配给该逻辑地址。\n[0041] 为了在掉电后重构L2P表62，控制器52使用临时表190，在图9中描述了该临时表190的一个示例性实施例。表190包括N个二元组条目192(作为示例描绘的条目1921，\n1922...192N)，每一条目都与一特定逻辑地址相关联。于是，控制器52可出于查找一特定条目192的目的来使用逻辑地址指针197。根据本发明的某些实施例，每个条目192包括为该逻辑地址指示一物理地址的字段194以及指示迄今为止已被找出的最后(和最大)序号的字段196。因此，控制器52在其(在掉电之后)扫描通过非易失性存储器54时更新条目192，从而在该扫描结束时，每个条目192都为各自的逻辑地址指示最近用过的物理地址(即，该物理地址具有最高的序号)。\n[0042] 作为表190使用的一个更为具体的示例，根据本发明的某些实施例，控制器52一般执行如图10所示的方法200。依照方法200，控制器52初始化(202)表190。例如，这一初始化可以包括在与物理地址或最后序号不相对应的(表190的)每个条目192中存储值(诸如，“-1”)，以指示条目192的初始化状态。控制器52随后从非易失性存储器54的下一物理地址中读取(框204)元数据。如果该元数据指示存储内容无效，控制器52于是就判定(菱形框208)是否有另一物理地址要被处理，如果是，则返回框204。根据本发明的某些实施例，空白池和用过池的重构也可以在同一遍中完成。\n[0043] 如果控制器52判定(菱形框206)内容数据有效，控制器52于是就为与该物理地址相关联的特定逻辑地址从表190中检索(框210)最后序号条目。于是，该逻辑地址的指示就被存储在非易失性存储器54的存储位置内。如果控制器52判定(菱形框214)序号有效(即，控制器52判定序号不是初始化的值)，控制器52于是就判定(菱形框216)当前序号是否是该逻辑地址迄今为止最大的序号。如果不是，则控制返回至菱形框208。否则，用于该逻辑地址的最后物理地址(诸如迄今为止在扫描中指示的那样)已被定位，并且控制器52在先前物理地址处写入元数据(框220)以指示相应的内容数据是“用过的”。随后，控制器52为该相对应的逻辑地址更新(框222)表190的字段194和196(参见图9)。\n控制随后行进至菱形框208，在其中控制器52判定是否要处理另一物理地址。如果不是，则控制器52就已完成该扫描，并且表190已被构造。注意到表190的缺少的条目196(参见图9)组成了重构的L2P表62。于是，根据本发明的某些实施例，控制器52可以在重构L2P表62的扫描完结时提取数据194。\n[0044] 存储器系统50(参见图2)可以在各种不同的应用中使用，于是本发明的许多不同实施例都是可能的并且在所附权利要求的范围内。例如，根据本发明的某些实施例，存储器系统50可以是固态磁盘，而在本发明的其他实施例中，存储器系统50可以是磁盘高速缓存或用于多个磁盘或RAID卷的高速缓存。图11描绘了结合有存储器系统50的计算机体系结构250的一个示例性实施例。计算机体系结构250例如可用于台式或膝上型计算机。\n[0045] 计算机系统250包括耦合至系统总线256的处理器252(例如，一个或多个微处理器)。计算机系统250还可包括北桥或存储器集线器260，其耦合至系统总线256以建立处理器252与诸如动态随机存取存储器(DRAM)60之类的系统存储器之间的通信。根据本发明的某些实施例，DRAM 60是易失性存储器60的一个实施例，虽然在本发明的其他实施例中也可以使用其他的易失性存储器。DRAM 60可以经由存储器总线262耦合至存储器集线器260。在本发明的某些实施例中，存储器集线器260可以包括控制器52，虽然在本发明的其他实施例中，控制器52可以与存储器集线器260分开。\n[0046] 如图11所示，根据本发明的某些实施例，非易失性存储器可以是NAND闪存，虽然根据本发明的其他实施例也可在此处使用其他类型的非易失性存储器。例如，在本发明的其他实施例中，可以使用铁电聚合体存储器(ferro-electric polymermemory)来代替NAND闪存。\n[0047] 在本发明的某些实施例中，存储器集线器260可将诸如可以是外围元件互连(PCI)总线272和加速图形端口(AGP)总线270之类的其他总线接口至系统总线256。PCI规范可以从俄勒冈97214波特兰的PCI特殊利益集团(PCI SpecialInterest Group)获取。AGP在由加利福尼亚州圣克拉拉市的英特尔(Intel)公司于1996年7月31日出版的加速图形端口接口规范，版本1.0(Accelerated Graphics PortInterface Specification，Revision 1.0)中有详细描述。PCI总线272例如可将网络接口卡(NIC)273耦合至PCI总线272；而AGP总线270则例如可将驱动显示器277的显示器驱动器275耦合至系统总线\n256。\n[0048] 如图11所示，根据本发明的某些实施例，存储器集线器260可以耦合至南桥或输入/输出(I/O)集线器280。I/O集线器280例如可以提供对CD-ROM驱动器290和硬盘驱动器292的接口。此外，I/O集线器280可以提供对I/O扩展总线282的接口。I/O控制器\n284可以耦合至I/O扩展总线282并可接收来自鼠标286和键盘290的输入数据。\n[0049] 注意到在图11中所示的体系结构仅仅是出于示例的目的，因为其他的变化也是可能的并且在所附权利要求的范围内。\n[0050] 虽然已经就有限数量的实施例公开了本发明，但是从本公开中获益的本领域普通技术人员将会从中认识到各种修改和变化。所附权利要求旨在涵盖落入本发明真正精神和范围内的所有这些修改和变化。