用于数据恢复的方法以及用于数据恢复的装置

摘要

一种用于数据恢复的方法、用于数据恢复的装置以及用于快闪装置的数据恢复的方法。其中用于数据恢复的方法包括从主机获得第一数据；从存储器的多个页面选择第一页面用于储存第一数据；储存指示第一页面的物理地址的起始页面链接；将第一数据、指示下一个页面的物理地址的第一页面链接以及第一快闪转换层分段数据写入第一页面；从主机获得下一个数据；将下一个数据、指示后续页面的物理地址的下一个页面链接以及相应于下一个页面的快闪转换层分段数据写入下一个页面。本发明的效果之一在于，能够在电源突然关闭后恢复最新的FTL数据。

说明书

技术领域

本发明涉及快闪装置，尤其涉及用于数据恢复的方法、用于数据恢复的 装置以及用于快闪装置的数据恢复的方法。

背景技术

快闪装置(例如记忆卡)是一种包括用于数据储存的快闪存储器的装置。 快闪存储器是非易失(non-volatile)存储器，能够被电擦除或重程序化 (reprogrammed)。快闪装置用于为主机储存数据，主机可例如个人计算器。 当主机要将数据储存至快闪装置时，主机将数据随同数据的逻辑地址发送至 快闪装置，其中逻辑地址表示储存数据的位置。然而，快闪存储器根据物理 地址储存数据。因此快闪装置必须首先将主机发送的逻辑地址转换为物理地 址，然后指示快闪存储器将数据储存至具有逻辑地址的存储器空间中。因此， 快闪装置包括微处理器，微处理器能够将主机的逻辑地址转换为快闪存储器 的物理地址。

为了将逻辑地址转换为物理地址，快闪装置需要记录逻辑地址与物理地 址之间的映像关系(mapping relationship)。逻辑地址与物理地址之间的映像关 系称为快闪转换层(Flash Translation Layer，FTL)数据。FTL数据常储存于快 闪装置的快闪存储器中。致能快闪装置后，微处理器将来自快闪存储器的FTL 数据承载至快闪装置的动态随机存取存储器(Dynamic Random Access Memory，DRAM)，并且微处理器接着根据储存于DRAM中的FTL数据将 逻辑地址转换为物理地址。

每当一个时间周期过去后，快闪装置的微处理器必须根据储存于DRAM 中的最新(latest)FTL数据更新储存于快闪存储器中的FTL数据，这样储存于快 闪存储器中的FTL数据与储存于DRAM中的最新FTL数据保持相同。然而， 当快闪装置的电源突然关闭时，储存于快闪存储器中的FTL数据没有时间进 行更新，所以电源的突然关闭导致储存于DRAM中的最新FTL数据丢失。重 新获得快闪存储器的电源后，快闪装置的微处理器必须首先恢复最新的FTL 数据。否则，因为储存于快闪存储器中的FTL数据的版本不是最新版本，微 处理器会根据FTL数据的错误信息将逻辑地址转换为物理地址。举例来说， 当主机请求快闪装置读取数据时，快闪装置可能读取快闪存储器的旧(old)物 理地址从而得到错误的数据。当主机请求快闪装置写入数据时，快闪装置可 能误将使用过的数据区块当作空数据区块并覆盖使用过的数据区块中的数 据。因此，需要一种为快闪装置恢复最新FTL数据的方法。

发明内容

有鉴于此，本发明提供用于数据恢复的方法、用于数据恢复的装置以及 用于快闪装置的数据恢复的方法。

一种用于数据恢复的方法，其特征在于，存储器包括用于数据储存的多 个页面，随机存取存储器根据所述多个页面的逻辑地址与物理地址之间的映 像关系储存快闪转换层数据，并且所述存储器储存所述快闪转换层数据的前 一个版本，所述用于数据恢复的方法包括：从主机获得第一数据；从所述存 储器的所述多个页面选择第一页面用于储存所述第一数据；在所述存储器中 储存指示所述第一页面的物理地址的起始页面链接；将所述第一数据、指示 下一个页面的物理地址的第一页面链接以及相应于所述第一页面的第一快闪 转换层分段数据写入所述第一页面；从所述主机获得下一个数据；以及将所 述下一个数据、指示后续页面的物理地址的下一个页面链接以及相应于所述 下一个页面的快闪转换层分段数据写入所述下一个页面。

一种用于数据恢复的装置，其特征在于，所述用于数据恢复的装置包括： 存储器，包括用于数据储存的多个页面；随机存取存储器，根据所述多个页 面的逻辑地址与物理地址之间的一映像关系储存快闪转换层数据；微处理器， 用于从主机获得第一数据，从所述存储器的所述多个页面选择第一页面用于 储存所述第一数据，在所述存储器中储存指示所述第一页面的物理地址的起 始页面链接，将所述第一数据、指示下一个页面的物理地址的第一页面链接 以及相应于所述第一页面的第一快闪转换层分段数据写入所述第一页面，从 所述主机获得下一个数据以及将所述下一个数据、指示后续页面的物理地址 的下一个页面链接以及相应于所述下一个页面的快闪转换层分段数据写入所 述下一个页面。

一种用于快闪装置的数据恢复的方法，其特征在于，所述快闪装置的存 储器包括用于数据储存的多个页面，随机存取存储器根据所述多个页面的逻 辑地址与物理地址之间的映像关系储存快闪转换层数据，并且所述快闪存储 器储存所述快闪转换层数据的前一个版本，所述用于快闪装置的数据恢复的 方法包括：从主机获得第一数据；从所述快闪存储器的所述多个页面选择第 一页面用于储存所述第一数据；将所述第一数据、指示所述快闪转换层数据 的前一个版本的第一页面链接以及相应于所述第一页面的第一快闪转换层分 段数据写入所述第一页面；从所述主机获得下一个数据；以及将所述下一个 数据、指示所述第一页面的前一个页面链接以及相应于下一个页面的快闪转 换层分段数据写入所述下一个页面。

一种用于快闪装置的数据恢复的方法，其特征在于，所述快闪装置的快 闪存储器包括多个区块，并且所述多个区块中的每个包括用于数据储存的多 个页面，所述用于快闪装置的数据恢复的方法包括：当将数据写入从所述多 个区块选择的目标区块的目标页面时，在所述目标页面中记录所述目标区块 的区块类型与物理区块号；恢复所述快闪装置的电源后，根据储存于所述目 标区块的多个页面中的区块类型与物理区块号决定所述目标区块是否是废料 收集区块；以及根据所述目标区块是否是废料收集区块重建快闪转换层数据， 其中所述快闪转换层数据记录逻辑区块号与物理区块号之间的映射关系。

一种用于数据恢复的装置，其特征在于，包括：存储器，包括多个区块， 其中所述多个区块中的每个包括用于数据储存的多个页面；以及微处理器， 当将数据写入目标页面时，在所述目标页面中记录目标区块的区块类型与物 理区块号，恢复所述装置的电源后，根据储存于所述目标区块的多个页面中 的区块类型与物理区块号决定所述目标区块是否是废料收集区块，并且根据 决定结果重建快闪转换层数据，其中所述快闪转换层数据记录逻辑区块号与 物理区块号之间的映射关系。

本发明的效果之一在于，能够在电源突然关闭后恢复最新的FTL数据。

以下为根据多个图式对本发明的较佳实施例进行详细描述，所属技术领 域技术人员阅读后应可明确了解本发明的目的。

附图说明

图1为根据本发明的装置的方块示意图。

图2A为根据本发明的实施例的用于将FTL恢复信息写入快闪存储器的 页面的方法的示意图。

图2B为根据本发明的用于恢复最新FTL数据的方法的流程示意图。

图3A为根据本发明另一实施例的将FTL恢复信息写入快闪存储器的页 面的方法的示意图。

图3B为根据本发明的用于恢复最新FTL数据的方法的流程示意图。

图4为根据本发明另一实施例的用于将FTL恢复信息写入快闪存储器的 页面的方法的示意图。

图5为根据本发明另一实施例的用于将FTL恢复信息写入快闪存储器的 页面的方法的示意图。

图6为相应于逻辑区块号的多个区块的实施例的示意图。

图7为决定目标区块是否为废料收集区块的方法的流程示意图。

图8为从相应于逻辑区块号的多个区块决定最新的区块的方法的流程示 意图。

图9为有效区块转变为数据区块的实施例的示意图。

图10为相应于逻辑区块号的多个区块的实施例的示意图。

图11为决定目标区块是否为废料收集区块的方法的流程示意图。

图12为从相应于逻辑区块号的多个区块决定最新的区块的方法的流程 示意图。

图13为有效区块转变为数据区块的实施例的示意图。

图14为相应于逻辑区块号的多个区块的另一个实施例的示意图。

图15为根据本发明一个实施例的多个区块的示意图。

具体实施方式

下面的实施例仅用来例举本发明的实施态样，以及阐释本发明的技术特 征，并非用来限制本发明的范畴。所属技术领域技术人员可依据本发明的精 神轻易完成的改变或均等性的安排均属于本发明所主张的范围，本发明的权 利范围应以权利范围为准。

图1为根据本发明一实施例的装置100的方块示意图。装置100包括微处理 器102、RAM(例如DRAM 104)、存储器控制器106、存储器108以及主机界面 107。举例来说，装置100可为快闪装置，存储器108可为快闪存储器。装置100 用于为主机(图未示)储存数据。主机界面107用于主机与微处理器102之间的 数据通信。DRAM 104用于为微处理器102储存数据。存储器控制器106控制 快闪存储器108的操作。快闪存储器108包括多个区块，并且每个区块包括多 个用于数据储存的页面(page)。快闪存储器108储存FTL数据109(图中显示为 FTL)，其中FTL数据109记录主机使用的逻辑地址与快闪存储器108使用的物 理地址之间的映像关系。致能装置100后，微处理器102将FTL数据承载至 DRAM 104，并且根据储存于DRAM 104中的FTL数据105(图中显示为最新 FTL)将从主机接收的逻辑地址转换为物理地址。微处理器102在储存于 DRAM 104中的FTL数据105中记录逻辑地址与物理地址之间的新映像关系。 因此，储存于DRAM 104中的FTL数据105包括地址映像关系的最新版本。

因为储存于DRAM 104中的最新FTL数据105与储存于快闪存储器108中 的FTL数据109有些不同，因此微处理器102需要保持FTL数据109与最新FTL 数据105相同。每当一个预设时间周期过去后，微处理器102就根据储存于 DRAM 104中的最新FTL数据105更新储存于快闪存储器108中的FTL数据 109。然而，当装置100的电源突然关闭时，微处理器102没有时间更新储存于 快闪存储器108中的FTL数据109，并且电源的突然关闭导致储存于DRAM 104中的最新FTL数据105丢失。装置100重新获得电源后，微处理器102需要 恢复最新FTL数据105以用于地址转换。为了参考最新FTL数据105，每当将 数据写入新页面时，微处理器102将一些信息随着数据写入新页面。

请参考图2A。图2A为根据本发明的实施例的用于将FTL恢复信息写入快 闪存储器108的页面的方法的示意图。微处理器102首先根据储存于DRAM 104中的最新FTL数据105更新储存于快闪存储器108中的FTL数据109，其中 FTL数据109与最新FTL数据105相同。假设主机要将一系列数据写入装置 100，并且主机界面107从主机顺序地接收数据序列。微处理器102首先决定快 闪存储器108的第一页面111以用于储存数据序列的第一数据。微处理器102 接着记录起始页面链接110(图中显示为S)，起始页面链接110用于指示快闪存 储器108中的第一页面111的物理地址。微处理器102接着指导存储器控制器 106将第一数据写入第一页面111。将第一数据写入第一页面111后，微处理器 102同样指导存储器控制器106将下一个页面链接N₁(即下一个页面链接N₁能 视为第一页面链接)以及FTL片段数据T₁(即FTL片段数据T₁能视为第一FTL片 段数据)写入第一页面111，其中下一个页面链接N₁指示第二页面112的物理地 址(即第二页面112能视为第一页面111的下一个页面)，并且FTL片段数据T₁是相应于写入第一页面111的数据的最新FTL数据105的更新数据。

微处理器102接着指导存储器控制器106将数据序列的第二数据写入第二 页面112。将第二数据写入第二页面112后，微处理器102同样指导存储器控制 器106将下一个页面链接N₂以及FTL片段数据T₂写入第二页面112，其中下一 个页面链接N₂指示第三页面的物理地址，并且FTL片段数据T₂是相应于写入 第二页面112的数据的最新FTL数据105的更新数据。微处理器102接着以与第 一页面111以及第二页面112相同的方式将数据写入后续页面(例如，11K页面 是11(K-1)页面的后续页面)。换句话说，每当微处理器102将数据写入新页面， 微处理器102同样写入指示后续页面的物理地址的下一个页面链接以及相应 于写入新页面的数据的FTL分段数据。换句话说，重复执行写入下一个数据、 下一个页面链接以及下一个页面的快闪转换层分段数据的步骤直到主机不再 发送新数据。最后，微处理器102将数据序列的最终数据、下一个页面链接 N_K以及FTL分段数据T_K写入最终页面11K，其中下一个页面链接N_K指向空值 (NULL)。当传统快闪装置的电源突然关闭后，储存于DRAM 104中的最新FTL 数据会丢失，并且微处理器102无法恢复储存于多个区块(区块用于储存最近 的数据)中的数据。因为图2A所示的每个页面储存FTL分段数据以及指向下一 个页面的下一个页面链接，因此，当装置100的电源突然关闭时，微处理器102 能够根据下一个页面链接重新获得页面111～11K并且根据FTL分段数据恢复 最新FTL数据，没有数据丢失。因此根据本发明的装置100比传统快闪装置具 有更好的性能。

假设装置100的电源突然关闭，储存于DRAM 104中的最新FTL数据105 丢失了。装置100重新获得电源后，微处理器102需要恢复最新FTL数据105。 请参考图2B，图2B为根据本发明的用于恢复最新FTL数据的方法200的流程 示意图。首先，微处理器102根据储存于快闪存储器108中的起始页面链接110 决定用于储存数据的第一页面111(步骤202)。微处理器102接着指导存储器控 制器106读取第一页面111以获得相应于第一页面的FTL分段数据T₁(步骤 204)，其中FTL片段数据T₁能视为第一FTL片段数据。因为第一页面111的下 一个页面链接N₁已经储存了下一个页面112的物理地址，因此微处理器102接 着根据第一页面111的下一个页面链接N₁决定下一个页面112(步骤206)。微处 理器102接着指导存储器控制器106读取下一个页面112以获得相应于下一个 页面112的FTL分段数据(步骤208)。

因为前一个页面总是储存指示下一个页面的物理地址的下一个页面链 接，根据当前的下一个页面的下一个页面链接决定新的下一个页面(步骤 212)，微处理器102继续读取下一个页面以收集相应于下一个页面的FTL分段 数据(步骤208)。最后，微处理器102决定最终页面11K是否已经储存指向 NULL的下一个页面链接(步骤210)。微处理器102读取最终页面11K以获得相 应于最终页面11K的FTL分段数据之后，微处理器102整合所有页面111～11K 的FTL分段数据以获得FTL补丁(patch)数据，其中FTL补丁数据包括相应于写 入所有页面111～11K的数据的FTL更新数据(步骤214)。举例来说，页面 111～11K的FTL分段数据T₁～T_K可包括关于区块的逻辑区块号以及区块类型 的信息以支持重建(rebuild)最新FTL数据，其中区块包含页面111～11K。因此 微处理器102可结合页面111～11K的FTL分段数据T₁～T_K以获得FTL补丁数据， 其中补丁数据是储存于快闪存储器108中的原始FTL数据109的丢失信息。最 后，微处理器102将储存于快闪存储器108中的FTL数据109与FTL补丁数据结 合以恢复在电源被切断之前的最新FTL数据105(步骤216)。也就是说，将储存 于快闪存储器108中的FTL数据的前一个版本与FTL补丁数据结合以获得FTL 数据的最新版本。最新FTL数据恢复后，微处理器102接着可根据最新FTL数 据105中包含的地址映像关系将从主机接收的逻辑地址转换为物理地址并接 着根据物理地址存取储存于快闪存储器108中的数据。

请参考图3A。图3A为根据本发明另一实施例的将FTL恢复信息写入快闪 存储器108的页面的方法的示意图。微处理器102首先根据储存于DRAM 104 中的最新FTL数据105更新储存于快闪存储器108中的FTL数据109，其中FTL 数据109与最新FTL数据105相同。假设主机要将一系列数据写入装置100，并 且主机界面107从主机顺序地接收数据序列。微处理器102首先决定快闪存储器 108的第一页面121以用于储存数据序列的第一数据。微处理器102接着指导 存储器控制器106将第一数据写入第一页面121。将第一数据写入第一页面121 后，微处理器102同样指导存储器控制器106将前一个页面链接P₁以及FTL片 段数据T₁写入第一页面121，其中前一个页面链接P₁指示储存于快闪存储器 108中的FTL数据109的物理地址，并且FTL片段数据T₁是相应于写入第一页面 121的数据的最新FTL数据105的更新数据。

微处理器102接着决定第二页面122用于储存数据序列的第二数据并且指 导存储器控制器106将数据序列的第二数据写入第二页面122。将第二数据写 入第二页面122后，微处理器102同样指导存储器控制器106将前一个页面链接 P₂以及FTL片段数据T₂(FTL片段数据T₂能视为第二FTL片段数据)写入第二页 面122，其中前一个页面链接P₂指示第一页面121的物理地址，并且FTL片段 数据T₂是相应于写入第二页面122的数据的最新FTL数据105的更新数据。微 处理器102接着以与第一页面121以及第二页面122相同的方式将数据写入后 续页面。换句话说，每当微处理器102将数据写入新页面，微处理器102同样 写入指示先前页面的物理地址的前一个页面链接以及相应于写入新页面的数 据的FTL分段数据。最后，微处理器102将数据序列的最终数据、前一个页面 链接P_K以及FTL分段数据T_K写入最终页面12K，其中前一个页面链接P_K指示 先前页面12(K-1)的物理地址。

假设装置100的电源突然关闭，储存于DRAM104中的最新FTL数据105 会丢失。装置100重新获得电源后，微处理器102需要恢复最新FTL数据105。 请参考图3B。图3B为根据本发明的用于恢复最新FTL数据的方法的流程示意 图。首先，微处理器102搜索快闪存储器108的页面以找到最后的页面12K(步 骤302)。微处理器102接着指导存储器控制器106读取最后的页面12K以获得 相应于最后的页面12K的FTL分段数据T_K(步骤304)。因为最后的页面12K的 前一个页面链接P_K已经储存了前一个页面12(K-1)的物理地址，因此微处理器 102接着根据最后的页面12K的前一个页面链接P_K决定前一个页面12(K-1) (步骤306)。微处理器102接着指导存储器控制器106读取前一个页面12(K-1) 以获得相应于前一个页面12(K-1)的FTL分段数据(步骤308)。

因为后续页面总是储存指示前一个页面的物理地址的前一个页面链接， 根据当前的前一个页面的前一个页面链接决定新的前一个页面(步骤312)，微 处理器102继续读取前一个页面以收集相应于前一个页面的FTL分段数据(步 骤308)。微处理器102决定前一个页面的前一个页面链接是否指向储存于快闪 存储器中的FTL数据(步骤310)。也就是说，微处理器102决定第一页面121是 否已经储存指向储存于快闪存储器108中的FTL数据109的前一个页面链接。 微处理器102读取第一页面121以获得相应于第一页面121的FTL分段数据之 后，微处理器102整合所有页面121～12K的FTL分段数据以获得FTL补丁数据， 其中FTL补丁数据包括相应于写入所有页面121～12K的数据的FTL更新数据 (步骤314)。最后，微处理器102将储存于快闪存储器108中的FTL数据109与 FTL补丁数据结合以获得最新FTL数据105(步骤316)。最新FTL数据恢复后， 微处理器102接着可根据最新FTL数据105中包含的地址映像关系将从主机接 收的逻辑地址转换为物理地址并接着根据物理地址存取储存于快闪存储器 108中的数据。

图3A的另一个实施例并不包括储存最后的页面12K的结束页面链接。因 此，当FTL数据恢复过程300开始后(即方法300开始后)，微处理器102需要搜 索快闪存储器108的页面以找到最后的页面12K。搜索最后的页面12K的操作 需要很长的时间周期。请参考图4。图4为根据本发明另一实施例的用于将FTL 恢复信息写入快闪存储器108的页面的方法的示意图。图4所示实施例与图3A 所示实施例相似，区别主要在于，图4中包括储存装置130，储存装置130储存 结束页面链接120(图中显示为E)。储存装置130可为快闪存储器108或额外的 电可除程序化只读存储器(Electrically Erasable Programmable Read Only  Memory，EEPROM)。在电源和装置100之间耦接电容器以延长消逝喘息周期 (dying gasp period)，其中在消逝喘息周期中电源突然关闭后，电源仍然供电。 在短暂的消逝喘息周期中，微处理器102在储存装置130中储存结束页面链接 120，结束页面链接120指示最后的页面12K。因此，当微处理器102执行方法 300以重建最新FTL数据105时，微处理器102可以直接根据储存于储存装置 130中的结束页面链接120找到最后的页面12K。

请参考图5。图5为根据本发明另一实施例的用于将FTL恢复信息写入快 闪存储器108的页面的方法的示意图。图5所示实施例与图2A所示实施例相 似。图2A中所示页面储存FTL分段数据T₁～T_K，FTL分段数据T₁～T_K分别相应 于写入页面111～11K的数据。其中，FTL分段数据T₁～T_K是未被压缩的。图5 中当微处理器102将数据写入页面131～13K时，微处理器102将压缩的FTL分 段数据C₁～C_K写入页面131～13K。举例来说，当将第一数据写入第一页面131 时，最新FTL数据105必须相应地改变以记录第一页面131的物理地址与第一 数据的逻辑地址之间的映像关系。接着压缩表明最新FTL数据105与原始FTL 数据109之间的差异的更新数据以获得已压缩FTL分段数据C₁，并且微处理器 102将已压缩FTL分段数据C₁写入第一页面131。类似地，将相应于页面 132～13K的已压缩FTL分段数据C₂～C_K写入页面132～13K。这样，最新FTL数 据105与原始FTL数据109之间的差异数据就储存于已压缩FTL分段数据 C₂～C_K中而没有进一步逻辑处理。重新获得装置100的电源后，微处理器102 可将已压缩FTL分段数据C₁～C_K解压缩以获得FTL补丁数据，其中FTL补丁数 据表明最新FTL数据105与原始FTL数据109之间的差异。微处理器102可接着 根据FTL补丁数据更新储存于快闪存储器108中的FTL数据109以获得最新 FTL数据105。

另一方面，图2A中所示页面111～11K的分段FTL数据T₁～T_K是由逻辑处理 产生的逻辑数据，并且最新FTL数据105与原始FTL数据109之间的差异数据 必须经由微处理器102的逻辑处理从分段FTL数据T₁～T_K得到。因此，根据已 压缩分段数据C₂～C_K恢复最新FTL数据105比根据分段FTL数据T₁～T_K恢复最 新FTL数据105需要更短的时间周期

耦接于装置100的主机可频繁地更新具有相同逻辑区块号(逻辑区块号也 称为逻辑区块地址)的数据，因此装置100在具有不同物理区块号(Physical  Block Number，PBN)的多个区块中储存相应于特定逻辑区块号的数据。举例 来说，相应于逻辑区块号的数据区块首先储存数据。当主机要将更新数据写 入相同逻辑区块号时，装置100可将更新数据储存于相应于相同逻辑区块号的 有效(active)区块中。另外，装置100的微处理器102可整合数据区块与有效区 块的数据以获得相应于相同逻辑区块号的废料收集(garbage collection)区块。 因此，可提高存取具有连续逻辑地址和间歇物理地址的数据的性能。当装置 100的电源突然关闭，储存于DRAM 104中的最新FTL数据105丢失，微处理 器102不易决定相应于相同逻辑区块号的多个区块是否储存数据的最新版本。 因此，需要一种用于从相应于相同逻辑区块号的多个区块决定最新的区块的 方法。逻辑区块号可同时相应于储存原始数据的数据区块、储存更新数据的 有效区块以及储存数据区块的原始数据和有效区块的更新数据的废料收集区 块。微处理器102接着决定相应于逻辑区块号的区块中的哪一个是最新的区 块，并且将最新的区块的逻辑区块号与物理区块号之间的映像关系储存于重 建的最新FTL数据中。

因为废料收集区块是通过将数据区块和有效区块结合而获得，因此和有 效区块以及数据区块相比，通常废料收集区块是最新的区块。因此，要从相 应于逻辑区块号的多个区块中决定最新的区块，微处理器102必须首先决定区 块是否为废料收集区块，并接着从废料收集区块选择最新的区块。为了更好 的从多个区块中决定最新的区块和废料收集区块，当将数据写入目标区块的 页面时，微处理器102指导存储器控制器106将目标区块的区块类型和目标区 块的物理区块号写入目标区块的页面。这样，当装置100的电源关闭时，区块 的每页包括原始区块的区块类型以及原始区块的物理区块号(物理区块号也 称为物理区块地址)的信息。当装置100重新获得电源后，微处理器102可接着 根据储存于区块的页面中的区块类型信息以及物理区块号信息从相应于逻辑 区块号的多个区块决定最新的区块。

请参考图6。图6为相应于逻辑区块号的多个区块601～605的实施例的示 意图。区块601具有区块类型“数据区块”以及物理区块号X，并且区块601包 括三个页面，页面601a～601c。页面601a～601c都储存区块类型信息“数据区块” 以及物理区块号“X”。区块602具有区块类型“有效区块”以及物理区块号Y， 并且区块602包括三个页面，页面602a～602c。页面602a～602c都储存区块类型 信息“有效区块”以及物理区块号“Y”以及相应数据区块的物理区块号“X”。区 块603具有区块类型“有效区块”以及物理区块号Z，并且区块603包括五个页 面，页面603a～603e。页面603a 储存区块类型信息“有效区块”以及物理区块号 “Y”。页面603b～603c储存区块类型信息“数据区块”以及物理区块号“X”。页 面603d～603e储存区块类型信息“数据区块”以及物理区块号“Z”。区块604具有 区块类型“有效区块”以及物理区块号Q，并且区块604包括三个页面，页面 604a～604c。区块605具有区块类型“数据区块”以及物理区块号P，并且区块605 包括五个页面，页面605a～605e。

首先，微处理器102决定区块601～605是否为废料收集区块。请参考图7。 图7为决定目标区块是否为废料收集区块的方法700的流程示意图。首先，微 处理器102获得目标区块(步骤702)。微处理器102接着决定目标区块是否包括 储存与目标区块的物理区块号不同的物理区块号的页面(步骤704)。若是，则 微处理器102决定目标区块为废料收集区块(步骤708)。微处理器102接着决定 目标区块是否包括储存不同区块类型(信息)的至少两个页面(步骤706)。若是， 则微处理器102决定目标区块为废料收集区块(步骤708)。若目标区块的所有 页面储存与目标区块的物理区块号相同的物理区块号，并且目标区块没有包 括储存不同区块类型信息的两个页面，则微处理器102决定目标区块不是废料 收集区块(步骤710)。

举例来说，区块601的所有页面601a～601c储存物理区块号X，其中物理 区块号X是区块601的物理区块号，并且区块601的所有页面601a～601c储存相 同的区块类型信息“数据区块”。因此区块601不是废料收集区块。类似地，区 块602的所有页面602a～602c储存物理区块号Y，其中物理区块号Y是区块602 的物理区块号，并且区块602的所有页面602a～602c储存相同的区块类型信息 “有效区块”。因此区块602不是废料收集区块。类似地，决定区块604也不是 废料收集区块。然而，区块603包括储存物理区块号Y的页面603a，物理区块 号Y与区块603的物理区块号Z不同，并且区块603包括页面603b与603c，页面 603b与603c储存物理区块号X，其中页面603b与603c储存的物理区块号X与区 块603的物理区块号Z不同。另外，区块603包括页面603a，页面603a储存区块 类型信息“有效区块”，页面603a储存的区块类型信息“有效区块”与页面 603b～603e储存的区块类型信息“数据区块”不同。因此，微处理器102决定区 块603是废料收集区块。类似地，决定区块605也是废料收集区块。

因此微处理器102决定区块603与区块605是废料收集区块。请参考图8。 图8为从相应于逻辑区块号的多个区块决定最新的区块的方法800的流程示意 图。首先，微处理器102获得相应于相同逻辑区块号的多个区块601～605(步骤 802)。微处理器102接着决定多个区块601～605是否为废料收集区块(步骤 804)。根据图7所示方法700，仅决定区块603与区块605是废料收集区块。决 定是否仅有一个区块是废料收集区块(步骤806)，若决定仅有一个区块是废料 收集区块，则微处理器102决定废料收集区块是最新的区块(步骤808)。举例 来说，若仅有三个区块601～603相应于一个逻辑区块号，区块603是唯一的废 料收集区块，则决定区块603是最新的区块。

决定是否不止一个区块是废料收集区块(步骤812)，若不止一个区块是废 料收集区块，则微处理器102在多个废料收集区块中搜索目标废料收集区块， 其中目标废料收集区块包括储存其他废料收集区块的物理区块号的页面(步 骤814)，并且决定目标废料收集区块是最新的区块(步骤816)。举例来说，若 决定区块603与区块605是废料收集区块，因为区块605包括储存物理区块号Z 的页面605e，其中物理区块号Z是另一个废料收集区块603的物理区块号，因 此微处理器102决定区块605是最新的区块。否则，若决定没有区块是废料收 集区块，则微处理器102根据多个区块的区块类型决定最新的区块(步骤818)。 举例来说，若仅有两个区块，区块601与区块602相应于逻辑区块号，因为区 块602是有效区块并且区块601是数据区块，所以微处理器102决定有效区块 602是最新的区块。最后，决定最新区块后，微处理器102记录最新的区块的 物理区块号与储存于DRAM 104中的最新FTL数据105中的逻辑区块号之间 的映射关系，以重建最新FTL数据105。

请参考图9。图9为有效区块902转变为数据区块902’的实施例的示意图。 数据区块901相应于逻辑区块号。接着更新储存于数据区块901中的数据。建 立有效区块902以储存数据区块901的更新数据。微处理器102接着将有效区块 902转变为数据区块902’。因为区块902’的区块类型从“有效区块”改变为“数据 区块”，因此区块902’的新页面902o与新页面902p储存区块类型信息“数据区 块”。接着更新储存于数据区块902’中的数据。微处理器102接着建立有效区 块903以储存数据区块902’中的更新数据。当微处理器102将更新数据储存至 有效区块903的页面903a与页面903b时，微处理器102也将区块类型信息“有效 D”写入页面903a与页面903b，以指示区块903是从有效区块转变过来的数据 区块902’的有效区块。

图6所示的实施例中，当将数据写入目标区块的页面时，微处理器102仅 将关于目标区块的区块类型以及目标区块的物理区块号的信息写入页面。另 一个实施例中，当微处理器102将更新数据写入有效区块的页面时，微处理器 102除了写入关于有效区块的区块类型以及有效区块的物理区块号的信息，微 处理器102还将关于相应于有效区块的数据区块的物理区块号的信息写入有 效区块的页面，其中有效区块为相应的数据区块储存更新的数据。关于相应 于有效区块的数据区块的物理区块号的写入的信息可称为“数据-源物理区块 号”，简写为PBNds。将PBNds信息写入有效区块的页面后，储存于有效区块 的页面中的PBNds信息有助于从相应于相同逻辑区块号的多个废料收集区块 中决定最新的区块。

请参考图10。图10为相应于逻辑区块号的多个区块1001～1005的实施例 的示意图。区块1001具有区块类型“数据区块”与物理区块号X，并且区块1001 包括三个页面，页面1001a～1001c。页面1001a～1001c都储存区块类型信息“数 据区块”与物理区块号“X”。区块1002具有区块类型“有效区块”与物理区块号 Y，并且区块1002包括三个页面，页面1002a～1002c。页面1002a～1002c都储 存区块类型信息“有效区块”与物理区块号“Y”。另外，因为有效区块1002为数 据区块1001储存更新数据，页面1002a～1002c也储存相应于数据区块1001的数 据-源物理区块号“X”。区块1003具有区块类型“数据区块”与物理区块号Z，并 且区块1003包括五个页面，页面1003a～1003e。实际上，区块1003是包含数据 区块1001与有效区块1002的已整合数据的废料收集区块。因此，从页面1002c 得到的页面1003a储存相应数据区块1001的区块类型信息“有效区块”、物理区 块号“Y”以及数据-源物理区块号“X”。从页面1001b～1001c得到的页面 1003b～1003c储存区块类型信息“数据区块”以及物理区块号“X”。页面 1003d～1003e储存区块类型信息“数据区块”以及物理区块号“Z”。

区块1004具有区块类型“有效区块”与物理区块号Q，并且区块1004是为 数据区块1003储存更新数据的有效区块。有效区块1004包括三个页面，页面 1004a～1004c。类似地，页面1004a～1004c储存有效区块1004的区块类型信息 “有效区块”、有效区块1004的物理区块号“Z”以及相应数据区块1003的数据- 源物理区块号“Z”。区块1005具有区块类型“数据区块”以及物理区块号P。实 际上，区块1005是包含数据区块1003与有效区块1004的已整合数据的废料收 集区块。因此，从页面1003a得到的页面1005a储存区块类型信息“有效区块”、 物理区块号“Y”以及数据-源物理区块号“X”。从页面1003b～1003c得到的页面 1005b～1005c储存区块类型信息“数据区块”以及物理区块号“X”。从有效区块 1004的更新页面1004c得到的页面1005d储存相应数据区块1003的区块类型信 息“有效区块”、物理区块号“Q”以及数据-源物理区块号“Z”。从页面1003e得 到的页面1005e储存区块类型信息“数据区块”以及物理区块号“Z”。页面1005f 储存区块1005的区块类型信息“数据区块”以及物理区块号“P”。

图11为决定目标区块是否为废料收集区块的方法的流程示意图。如图11 所示，微处理器102可首先根据方法1100决定区块1001～1005是否为废料收集 区块。图11所示方法1100的步骤与图7所示方法700的步骤相似。举例来说， 数据区块1001的所有页面1001a～1001c储存物理区块号X，其中物理区块号X 是区块1001的物理区块号，并且数据区块1001的所有页面1001a～1001c储存相 同的区块类型信息“数据区块”。因此区块1001不是废料收集区块。类似地， 区块1002的所有页面1002a～1002c储存物理区块号Y，其中物理区块号Y是区 块1002的物理区块号，并且区块1002的所有页面1002a～1002c储存相同的区块 类型信息“有效区块”。因此区块1002不是废料收集区块。类似地，决定区块 1004也不是废料收集区块。然而，区块1003包括储存物理区块号Y的页面 1003a，物理区块号Y与区块1003的物理区块号Z不同，并且区块1003包括页 面1003b与1003c，页面1003b与1003c储存物理区块号X，其中页面1003b与 1003c储存的物理区块号X与区块1003的物理区块号Z不同。另外，区块1003 包括页面1003a，页面1003a储存区块类型信息“有效区块”，页面1003a储存的 区块类型信息“有效区块”与页面1003b～1003e储存的区块类型信息“数据区 块”不同。因此，微处理器102决定区块1003是废料收集区块。类似地，决定 区块1005也是废料收集区块。

因此微处理器102决定图10所示区块1003与区块1005是废料收集区块。请 参考图12。图12为从相应于逻辑区块号的多个区块决定最新的区块的方法 1200的流程示意图。首先，微处理器102获得相应于相同的逻辑区块号的多个 区块1001～1005(步骤1202)。微处理器102接着决定多个区块1001～1005中是否 存在废料收集区块(步骤1204)。根据图11所示方法1100，仅决定区块1003与 区块1005是废料收集区块。微处理器102进一步决定在区块1001～1005中是否 有不止一个废料收集区块(步骤1206)。若决定仅有一个区块是废料收集区块， 则微处理器102决定废料收集区块是最新的区块(即决策步骤1206之后的“否” 路径)。举例来说，举例来说，若仅有三个区块1001～1003相应于一个逻辑区 块号，区块1203是唯一的废料收集区块，则决定区块1003是最新的区块。

若决定不止一个区块是废料收集区块(即决策步骤1206之后的“是”路 径)，当储存于废料收集区块的页面中的物理区块号或数据-源物理区块号与 废料收集区块的物理区块号不相等，微处理器102决定具有储存于废料收集区 块的页面的物理区块号字段或数据-源物理区块号字段中的物理区块号的区 块是旧区块(步骤1208)。举例来说，因为废料收集区块1003的页面1003a和页 面1003b分别储存物理区块号Y与物理区块号X，其中物理区块号Y与物理区 块号X分别是区块1002和区块1001的物理区块号，并且决定区块1001和区块 1002是旧区块。另外，微处理器102决定具有储存于另一个废料收集区块的页 面的物理区块号字段或数据-源物理区块号字段中的物理区块号的废料收集 区块是旧区块(步骤1210)。举例来说，因为废料收集区块1005的页面1005d储 存数据-源物理区块号Z，其中数据-源物理区块号Z是另一个废料收集区块 1003的物理区块号，并且页面1005e储存物理区块号Z，其中物理区块号Z是 另一个废料收集区块1003的物理区块号，微处理器102决定区块1003是旧区 块。因为从区块1001～1005决定了旧区块，因此微处理器102可接着根据区块 的区块类型决定最新的区块(步骤1212)，例如从区块1001～1005决定最新的区 块1005，并且根据储存于最新的区块1005中的数据重建FTL(步骤1214)。

请参考图13。图13为有效区块1302转变为数据区块1302’的实施例的示意 图。数据区块1301相应于逻辑区块号X。接着更新储存于数据区块1301中的 数据。建立有效区块1302以储存数据区块1301的更新数据。因此页面 1302a～1302d储存数据区块1301的数据-源物理区块号X。微处理器102接着将 有效区块1302转变为数据区块1302’。因为区块1302’的区块类型从“有效区 块”改变为“数据区块”，因此区块1302’的新页面1302o与新页面1302p储存区 块类型信息“数据区块”。接着更新储存于数据区块1302’中的数据。微处理器 102接着建立有效区块1303以储存数据区块1302’中的更新数据。当微处理 器102将更新数据储存至有效区块1303的页面1303a与页面1303b时，微处理器 102也将数据区块1302’的数据-源物理区块号Y写入有效区块1303的页面 1303a与页面1303b。因为页面1303a与页面1303b储存数据区块1302’的数据- 源物理区块号Y，因此微处理器102可根据图12所示方法1200决定有效区块 1303比数据区块1302’更新。

请参考图14。图14为相应于逻辑区块号的多个区块1401～1405的另一个 实施例的示意图。区块1401、区块1403以及区块1405为数据区块，并且区块 1402与区块1404为有效区块。区块1401～1405分别具有物理区块号X、Y、Z、 Q以及P。因此微处理器102可根据图12所示方法1200从区块1401～1405决定旧 区块。区块1403的页面1403a储存区块1402的物理区块号Y以及区块1401的数 据-源物理区块号X。因此，根据方法1200的步骤1208，区块1401与区块1402 相对于区块1403是旧区块。类似地，因为页面1404a～1404d储存区块1403的数 据-源物理区块号Z，根据方法1200的步骤1208，区块1403相对于区块1404是 旧区块。另外，区块1400的页面1405d与页面1405e储存区块1404的物理区块 号Q与区块1403的数据-源物理区块号Z。微处理器102因此根据方法1200的步 骤1210决定区块1403与区块1404相对于区块1405是旧区块。因为区块 1401～1404都是旧区块，微处理器102可决定区块1405是最新的区块并且根据 储存于最新的区块1405中的数据重建FTL数据。

上述实施例中仅有两种区块类型，两种区块类型包括数据区块类型与有 效区块类型。若存在第三种区块类型，废料收集区块类型用于指示废料收集 区块，并且将区块类型信息写入废料收集区块的页面，则微处理器102可根据 储存于页面中的区块类型直接决定废料收集区块的类型。请参考图15。图15 为根据本发明一个实施例的区块1501～1505的示意图。区块1501是数据区块。 区块1502与区块1504是有效区块。区块1503与区块1505是废料收集区块。页 面1503a、页面1503b以及页面1503c因此储存废料收集区块类型的区块类型信 息，并且微处理器102可因此无须根据图11所示方法1100而决定区块1503是废 料收集区块。类似地，页面1505a、页面1505b、页面1505c、页面1505以及页 面1505e储存废料收集区块类型的区块类型信息，并且微处理器102可因此无 须根据图11所示方法1100而决定区块1505是废料收集区块。

上述的实施例仅用来例举本发明的实施态样，以及阐释本发明的技术特 征，并非用来限制本发明的范畴。任何所属技术领域技术人员可依据本发明 的精神轻易完成的改变或均等性的安排均属于本发明所主张的范围，本发明 的权利范围应以权利要求为准。