TW201911058A - 資料備份方法、資料恢復方法以及儲存控制器 - Google Patents

Abstract

本發明提供適用於可複寫式非揮發性記憶體模組的一種資料備份方法、資料恢復方法與儲存控制器。所述資料備份方法包括接收修剪指令；根據所述修剪指令、用以儲存修剪資訊清單的實體位址產生修剪資訊清單，其中所述修剪資訊清單記錄對應所述修剪指令與所述實體位址的資訊；將所產生之修剪資訊清單儲存至所述實體位址。所述資料恢復方法包括重建邏輯轉實體表；從可複寫式非揮發性記憶體模組中載入最新的修剪資訊清單至記憶體中；根據記憶體中的修剪資訊清單與重建後邏輯轉實體表來更新重建後邏輯轉實體表或所述記憶體中的修剪資訊清單。

Description

資料備份方法、資料恢復方法以及儲存控制器

本發明是有關於一種資料備份方法與資料恢復方法，且特別是有關於一種適用於配置有可複寫式非揮發性記憶體模組的儲存裝置的資料備份方法、資料恢復方法與儲存控制器。

一般來說，主機系統可利用修剪命令（Trim command）通知配置可複寫式非揮發性記憶體模組的儲存裝置（如，固態硬碟，SSD）哪些實體單元（實體區塊）的資料不再被視為在使用中（即，無效資料），並且所述多個實體單元可以被抹除。儲存裝置的控制器會根據修剪命令的修剪資訊將對應修剪資訊所指示的邏輯單元位址的實體單元位址標記為無效，以使控制器可在爾後的其他操作中，藉由被標記為無效的實體單元位址辨識出儲存在所述實體單元位址中的資料為無效資料，進而增加了儲存裝置的管理效率。例如，藉由修剪指令所標記的無效資料，可增進垃圾回收操作的效率。

但是，如何即時地管理（保存）所接收到的修剪指令的修剪資訊（Trim information），以應付突然的斷電和後續資料恢復成為一個值得研究的問題。更詳細來說，控制器一般會維持邏輯轉實體表（Logical to physical table，L2P table），以監視整個邏輯單元與實體單元的映射狀態。但，邏輯轉實體表（以下稱L2P表）的缺點是，控制器需要在特定時間來更新且儲存所維護於記憶體（如，RAM）中的L2P表至儲存裝置中。否則，在下次啟動時L2P表將會消失。此外，為了支持修剪指令，L2P表也會包含儲存對應修剪指令的修剪資訊的邏輯單元位址與實體單元位址的映射關係。為了在每次開機後或是斷電後的恢復操作中來安全地恢復L2P表與最新的修剪資訊，目前傳統的作法是在接收到每個修剪指令時，將L2P表與最新的修剪指令儲存（程式化）至儲存裝置中。但是，上述的傳統作法會降低系統性能並降低實體單元的使用壽命。

基此，如何更有效率地管理修剪資訊與L2P表，進而進行更佳的資料恢復操作，進而提昇配置有可複寫式非揮發性記憶體模組的儲存裝置的性能與安全，是本領域人員研究的課題之一。

本發明提供一種資料備份與恢復方法與儲存控制器，可利用已備份至可複寫式非揮發性記憶體模組的特定資料架構的修剪資訊與L2P表，來進行對應的資料恢復操作。

本發明的一實施例提供一種資料備份方法，適用於配置有可複寫式非揮發性記憶體模組的儲存裝置，其中所述可複寫式非揮發性記憶體模組具有多個實體單元，並且所述可複寫式非揮發性記憶體模組被配置多個實體位址，其中耦接至所述儲存裝置之主機系統配置多個邏輯位址。所述方法包括從所述主機系統接收修剪指令，其中所述修剪指令指示儲存於邏輯位址區段中的無效資料；根據所述修剪指令、所述多個實體位址中的目標實體位址來產生修剪資訊，以根據所述修剪資訊更新第一修剪資訊清單為第二修剪資訊清單，其中所述修剪資訊記錄無效資料起始邏輯位址、無效資料長度值、修剪資訊頁面順序與修剪資訊時間戳記；將所述第二修剪資訊清單儲存至所述目標實體位址，其中所述第一或第二修剪資訊清單根據接收對應一或多筆修剪資訊的修剪指令的時間順序來依序記錄所述一或多筆修剪資訊；將用以儲存所述第二修剪資訊清單的所述目標實體位址記錄至第一邏輯轉實體表的修剪資訊清單實體位址，以更新所述第一邏輯轉實體表為第二邏輯轉實體表；以及當符合預設條件，儲存所述第二邏輯轉實體表至所述可複寫式非揮發性記憶體模組。

本發明的一實施例提供一種資料恢復方法，適用於配置有可複寫式非揮發性記憶體模組的儲存裝置，其中所述可複寫式非揮發性記憶體模組具有多個實體單元，並且所述可複寫式非揮發性記憶體模組被配置多個實體位址，其中耦接至所述儲存裝置之主機系統配置多個邏輯位址。所述方法包括根據儲存在所述可複寫式非揮發性記憶體模組的第一邏輯轉實體表與所述可複寫式非揮發性記憶體模組中時間戳記大於所述第一邏輯轉實體表的時間戳記的所有有效資料的實體位址與對應的邏輯位址來重建所述第一邏輯轉實體表，並且將重建後之所述第一邏輯轉實體表儲存至一記憶體為第二邏輯轉實體表；若所述可複寫式非揮發性記憶體模組儲存有一或多個第一修剪資訊清單，辨識所述一或多個第一修剪資訊清單中最新的第二修剪資訊清單，其中所述一或多個第一修剪資訊清單的每一個第一修剪資訊清單記錄一或多筆修剪資訊，其中每一筆修剪資訊記錄無效資料起始邏輯位址、無效資料長度值、修剪資訊頁面順序與修剪資訊時間戳記，其中所述一或多個第一修剪資訊清單的時間戳記皆大於所述第一邏輯轉實體表的時間戳記；以及根據所述第二修剪資訊清單的所有修剪資訊與所述第二邏輯轉實體表來更新所述第二邏輯轉實體表或更新儲存於所述記憶體中的一第三修剪資訊清單。

本發明的一實施例提供用於控制配置有可複寫式非揮發性記憶體模組的儲存裝置的一種儲存控制器。所述儲存控制器包括連接介面電路、記憶體介面控制電路與處理器。所述連接介面電路用以耦接至配置多個邏輯位址之主機系統。所述記憶體介面控制電路用以耦接至所述可複寫式非揮發性記憶體模組，其中所述可複寫式非揮發性記憶體模組具有多個實體單元，並且所述可複寫式非揮發性記憶體模組被配置多個實體位址。所述處理器耦接至所述連接介面電路及所述記憶體介面控制電路。此外，所述處理器用以從所述主機系統接收修剪指令，其中所述修剪指令指示儲存於邏輯位址區段中的無效資料，其中所述處理器更用以根據所述修剪指令、所述多個實體位址中的目標實體位址來產生一修剪資訊，以根據所述修剪資訊更新第一修剪資訊清單為第二修剪資訊清單，其中所述修剪資訊記錄無效資料起始邏輯位址、無效資料長度值、修剪資訊頁面順序與修剪資訊時間戳記。所述處理器更用以將所述第二修剪資訊清單儲存至所述目標實體位址，其中所述第一或第二修剪資訊清單根據接收對應一或多筆修剪資訊的修剪指令的時間順序來依序記錄所述一或多筆修剪資訊，其中所述處理器更用以將用以儲存所述第二修剪資訊清單的所述目標實體位址記錄至第一邏輯轉實體表的一修剪資訊清單實體位址，以更新所述第一邏輯轉實體表為第二邏輯轉實體表。當符合預設條件，所述處理器更用以儲存所述第二邏輯轉實體表至所述可複寫式非揮發性記憶體模組。

本發明的一實施例提供用於控制配置有可複寫式非揮發性記憶體模組的儲存裝置的一種儲存控制器。所述儲存控制器包括連接介面電路、記憶體介面控制與電路處理器。所述連接介面電路用以耦接至配置多個邏輯位址之主機系統。所述記憶體介面控制電路用以耦接至所述可複寫式非揮發性記憶體模組，其中所述可複寫式非揮發性記憶體模組具有多個實體單元，並且所述可複寫式非揮發性記憶體模組被配置多個實體位址。所述處理器耦接至所述連接介面電路及所述記憶體介面控制電路，其中所述處理器用以根據儲存在所述可複寫式非揮發性記憶體模組的第一邏輯轉實體表與所述可複寫式非揮發性記憶體模組中時間戳記大於所述第一邏輯轉實體表的時間戳記的所有有效資料的實體位址與對應的邏輯位址來重建所述第一邏輯轉實體表，並且將重建後之所述第一邏輯轉實體表儲存至記憶體為第二邏輯轉實體表。若所述可複寫式非揮發性記憶體模組儲存有一或多個第一修剪資訊清單，所述處理器更用以辨識所述一或多個第一修剪資訊清單中最新的第二修剪資訊清單，其中所述一或多個第一修剪資訊清單的每一個第一修剪資訊清單記錄一或多筆修剪資訊，其中每一筆修剪資訊記錄無效資料起始邏輯位址、無效資料長度值、修剪資訊頁面順序與修剪資訊時間戳記，其中所述一或多個第一修剪資訊清單的時間戳記皆大於所述第一邏輯轉實體表的時間戳記。此外，所述處理器更用以根據所述第二修剪資訊清單的所有修剪資訊與所述第二邏輯轉實體表來更新所述第二邏輯轉實體表或更新儲存於所述記憶體中的第三修剪資訊清單。

基於上述，本發明實施例所提供的資料讀取方法以及儲存控制器，可根據所接收的修剪指令來產生特定資料架構的修剪資訊，並且利用已備份至可複寫式非揮發性記憶體模組的修剪資訊清單與邏輯轉實體表，來進行對應的資料恢復操作。由於不需要因為所接收之修剪指令而備份對應的修剪資訊與邏輯轉實體表至可複寫式非揮發性記憶體模組，因此避免了大量的寫入操作，並且增進儲存裝置整體的工作效率。此外，在斷電後，可經由所備份的特定結構的修剪資訊清單與邏輯轉實體表來有效地進行資料恢復，以重建斷電前之修剪資訊清單與邏輯轉實體表。

為讓本發明的上述特徵和優點能更明顯易懂，下文特舉實施例，並配合所附圖式作詳細說明如下。

在本實施例中，儲存裝置包括可複寫式非揮發性記憶體模組(rewritable non-volatile memory module)與儲存裝置控制器(亦稱，儲存控制器或儲存控制電路)。此外，儲存裝置是與主機系統一起使用，以使主機系統可將資料寫入至儲存裝置或從儲存裝置中讀取資料。

圖1是根據本發明的一實施例所繪示的主機系統及儲存裝置的方塊示意圖。

請參照圖1，主機系統(Host System)10包括處理器(Processor)110、主機記憶體(Host Memory)120及資料傳輸介面電路(Data Transfer Interface Circuit)130。在本實施例中，資料傳輸介面電路130耦接(亦稱，電性連接)至處理器110與主機記憶體120。在另一實施例中，處理器110、主機記憶體120與資料傳輸介面電路130之間利用系統匯流排(System Bus)彼此耦接。

儲存裝置20包括儲存控制器(Storage Controller)210、可複寫式非揮發性記憶體模組(Rewritable Non-Volatile Memory Module)220及連接介面電路(Connection Interface Circuit)230。其中，儲存控制器210包括處理器211、資料管理電路(Data Transfer Management Circuit)212與記憶體介面控制電路(Memory Interface Control Circuit)213。

在本實施例中，主機系統10是透過資料傳輸介面電路130與儲存裝置20的連接介面電路230耦接至儲存裝置20來進行資料的存取操作。例如，主機系統10可經由資料傳輸介面電路130將資料儲存至儲存裝置20或從儲存裝置20中讀取資料。

在本實施例中，處理器110、主機記憶體120及資料傳輸介面電路130可設置在主機系統10的主機板上。資料傳輸介面電路130的數目可以是一或多個。透過資料傳輸介面電路130，主機板可以經由有線或無線方式耦接至儲存裝置20。儲存裝置20可例如是隨身碟、記憶卡、固態硬碟(Solid State Drive，SSD)或無線記憶體儲存裝置。無線記憶體儲存裝置可例如是近距離無線通訊(Near Field Communication，NFC)記憶體儲存裝置、無線傳真(WiFi)記憶體儲存裝置、藍牙(Bluetooth)記憶體儲存裝置或低功耗藍牙記憶體儲存裝置(例如，iBeacon)等以各式無線通訊技術為基礎的記憶體儲存裝置。此外，主機板也可以透過系統匯流排耦接至全球定位系統(Global Positioning System，GPS)模組、網路介面卡、無線傳輸裝置、鍵盤、螢幕、滑鼠、喇叭等各式I/O裝置。

在本實施例中，資料傳輸介面電路130與連接介面電路230是相容於高速周邊零件連接介面(Peripheral Component Interconnect Express, PCI Express)標準的介面電路。並且，資料傳輸介面電路130與連接介面電路230之間是利用快速非揮發性記憶體介面標準(Non-Volatile Memory express，NVMe)通訊協定來進行資料的傳輸。

然而，必須瞭解的是，本發明不限於此，資料傳輸介面電路130與連接介面電路230亦可以是符合並列先進附件(Parallel Advanced Technology Attachment，PATA)標準、電氣和電子工程師協會(Institute of Electrical and Electronic Engineers，IEEE)1394標準、序列先進附件(Serial Advanced Technology Attachment，SATA)標準、通用序列匯流排(Universal Serial Bus，USB)標準、SD介面標準、超高速一代(Ultra High Speed-I，UHS-I)介面標準、超高速二代(Ultra High Speed-II，UHS-II)介面標準、記憶棒(Memory Stick, MS)介面標準、多晶片封裝(Multi-Chip Package)介面標準、多媒體儲存卡(Multi Media Card，MMC)介面標準、eMMC介面標準、通用快閃記憶體(Universal Flash Storage，UFS)介面標準、eMCP介面標準、CF介面標準、整合式驅動電子介面(Integrated Device Electronics，IDE)標準或其他適合的標準。此外，在另一實施例中，連接介面電路230可與儲存控制器210封裝在一個晶片中，或者連接介面電路230是佈設於一包含儲存控制器210之晶片外。

在本實施例中，主機記憶體120用以暫存處理器110所執行的指令或資料。例如，在本範例實施例中，主機記憶體120可以是動態隨機存取記憶體（Dynamic Random Access Memory，DRAM）、靜態隨機存取記憶體(Static Random Access Memory，SRAM)等。然而，必須瞭解的是，本發明不限於此，主機記憶體120也可以是其他適合的記憶體。

儲存控制器210用以執行以硬體型式或韌體型式實作的多個邏輯閘或控制指令並且根據主機系統10的指令在可複寫式非揮發性記憶體模組220中進行資料的寫入、讀取與抹除等運作。

更詳細來說，儲存控制器210中的處理器211為具備運算能力的硬體，其用以控制儲存控制器210的整體運作。具體來說，處理器211具有多個控制指令，並且在儲存裝置20運作時，此些控制指令會被執行以進行資料的寫入、讀取與抹除等運作。

值得一提的是，在本實施例中，處理器110與處理器211例如是中央處理單元(Central Processing Unit，CPU)、微處理器(micro-processor)、或是其他可程式化之處理單元(Microprocessor)、數位訊號處理器(Digital Signal Processor，DSP)、可程式化控制器、特殊應用積體電路(Application Specific Integrated Circuits，ASIC)、可程式化邏輯裝置(Programmable Logic Device，PLD)或其他類似電路元件，本發明並不限於此。

在一實施例中，儲存控制器210還具有唯讀記憶體(未繪示)及隨機存取記憶體(未繪示)。特別是，此唯讀記憶體具有開機碼(boot code)，並且當儲存控制器210被致能時，處理器211會先執行此開機碼來將儲存於可複寫式非揮發性記憶體模組220中之控制指令載入至儲存控制器210的隨機存取記憶體中。之後，處理器211會運轉此些控制指令以進行資料的寫入、讀取與抹除等運作。在另一實施例中，處理器211的控制指令亦可以程式碼型式儲存於可複寫式非揮發性記憶體模組220的特定區域，例如，可複寫式非揮發性記憶體模組220中專用於存放系統資料的實體儲存單元中。

在本實施例中，如上所述，儲存控制器210還包括資料管理電路212與記憶體介面控制電路213。應注意的是，儲存控制器220各部件所執行的操作亦可視為儲存控制器220所執行的操作。

其中，資料管理電路212耦接至處理器211、記憶體介面控制電路213與連接介面電路230。資料管理電路212用以接受處理器211的指示來進行資料的傳輸。例如，經由連接介面電路230從主機系統10(如，主機記憶體120)讀取資料，並且將所讀取的資料經由記憶體介面控制電路213寫入至可複寫式非揮發性記憶體模組220中（如，根據來自主機系統10的寫入指令來進行寫入操作）。又例如，經由記憶體介面控制電路213從可複寫式非揮發性記憶體模組220的一或多個實體單元中讀取資料，並且將所讀取的資料經由連接介面電路230寫入至主機系統10(如，主機記憶體120)中（如，根據來自主機系統10的讀取指令來進行讀取操作）。在另一實施例中，資料管理電路212亦可整合至處理器211中。以下會再配合多個圖式與實施例來詳細說明本發明中資料管理電路212的功能。

記憶體介面控制電路213用以接受處理器211的指示，配合資料管理電路212來進行對於可複寫式非揮發性記憶體模組220的寫入(亦稱，程式化，Programming)操作、讀取操作或抹除操作。

舉例來說，處理器211可執行寫入指令序列，以指示記憶體介面控制電路213將資料寫入至可複寫式非揮發性記憶體模組220的實體單元（亦稱，目標實體單元）中；處理器211可執行讀取指令序列，以指示記憶體介面控制電路213從可複寫式非揮發性記憶體模組220的對應讀取指令的一或多個實體單元中讀取資料；處理器211可執行抹除指令序列，以指示記憶體介面控制電路213對可複寫式非揮發性記憶體模組220進行抹除操作。寫入指令序列、讀取指令序列及抹除指令序列可各別包括一或多個程式碼或指令碼並且用以指示對可複寫式非揮發性記憶體模組220執行相對應的寫入、讀取及抹除等操作。在一實施例中，處理器211還可以下達其他類型的指令序列給記憶體介面控制電路213，以對可複寫式非揮發性記憶體模組220執行相對應的操作。

此外，欲寫入至可複寫式非揮發性記憶體模組220的資料會經由記憶體介面控制電路213轉換為可複寫式非揮發性記憶體模組220所能接受的格式。具體來說，若處理器211要存取可複寫式非揮發性記憶體模組220，處理器211會傳送對應的指令序列給記憶體介面控制電路213以指示記憶體介面控制電路213執行對應的操作。例如，這些指令序列可包括指示寫入資料的寫入指令序列、指示讀取資料的讀取指令序列、指示抹除資料的抹除指令序列、以及用以指示各種記憶體操作(例如，改變讀取電壓組準位或執行垃圾回收程序等等)的相對應的指令序列。這些指令序列可包括一或多個訊號，或是在匯流排上的資料。這些訊號或資料可包括指令碼或程式碼。例如，在讀取指令序列中，會包括讀取的辨識碼、記憶體位址等資訊。

可複寫式非揮發性記憶體模組220是耦接至儲存控制器210（記憶體介面控制電路213）並且用以儲存主機系統10所寫入之資料。可複寫式非揮發性記憶體模組220可以是單階記憶胞(Single Level Cell，SLC)NAND型快閃記憶體模組(即，一個記憶胞中可儲存1個位元的快閃記憶體模組)、多階記憶胞(Multi Level Cell，MLC)NAND型快閃記憶體模組(即，一個記憶胞中可儲存2個位元的快閃記憶體模組)、三階記憶胞(Triple Level Cell，TLC)NAND型快閃記憶體模組(即，一個記憶胞中可儲存3個位元的快閃記憶體模組)、三維NAND型快閃記憶體模組（3D NAND flash memory module）或垂直NAND型快閃記憶體模組（Vertical NAND flash memory module）等其他快閃記憶體模組或其他具有相同特性的記憶體模組。可複寫式非揮發性記憶體模組220中的記憶胞是以陣列的方式設置。

在本實施例中，可複寫式非揮發性記憶體模組220的記憶胞會構成多個實體程式化單元（亦稱，實體子單元），並且此些實體程式化單元會構成多個實體區塊(亦稱，實體抹除單元或實體單元)。具體來說，同一條字元線(或同一個字元線層)上的記憶胞會組成一或多個實體程式化單元。

在本實施例中，是以實體子單元作為寫入(程式化)資料的最小單位。實體單元為抹除之最小單位，即，每一實體單元含有最小數目之一併被抹除之記憶胞。每一實體單元會具有多個實體子單元。實體子單元可為實體頁面(page)或是實體扇(sector)。在本實施例中，實體子單元包括資料位元區與冗餘(redundancy)位元區。資料位元區用以儲存使用者資料，而冗餘位元區用以儲存系統資料。系統資料例如為錯誤更正碼、錯誤檢查碼或元資料（Meta Data）。

應注意的是，在本實施例中，用以記錄一實體單元的資訊的系統資料可利用該實體單元中的一或多個實體子單元來記錄，或是利用一個系統區中用以記錄所有系統資料的特定實體單元的一或多個實體子單元來記錄。在本實施例中，所述對應一實體單元的系統資料包括該實體單元的時間戳記（Timestamp）（亦稱，全域時間戳記）等資訊。所述時間戳記的大小（數值差異）可用來表示對應的實體單元最早被使用的時間的先後。本發明並不限定所述時間戳記的詳細格式。舉例來說，每當處理器211對選擇分配於閒置區的一實體單元以進行資料寫入操作時，所述實體單元會被分配至資料區（如，所述實體單元會成為開放實體單元），並且所述實體單元的時間戳記會記錄當前的儲存裝置時間或是系統時間。也就是說，若一實體單元的時間戳記大於（晚於）另一實體單元的時間戳記，此情況表示該實體單元比該另一實體單元還要早被分配至資料區（或更早被處理器211選擇來使用）。

此外，在本實施例中，當完成寫入邏輯轉實體表或實體轉邏輯表至可複寫式非揮發性記憶體模組220後，處理器211也會附加時間戳記至所寫入的邏輯轉實體表或實體轉邏輯表，以記錄此邏輯轉實體表或實體轉邏輯表被寫入至可複寫式非揮發性記憶體模組220的時間。

所述資料寫入操作例如是根據對應一邏輯位址的資料寫入資作來程式化對應的資料至所述實體單元的一或多個實體頁面（亦稱，實體子單元），或例如是程式化資料至所述實體單元的其他型態的實體位址（如，實體扇區）。在本實施例中，當完成對於一個邏輯頁面（邏輯位址）的資料寫入操作（如，對應的資料已被程式化至一實體頁面）時，處理器211會對應地更新邏輯轉實體表，以記錄該邏輯位址所對應的實體頁面的位址（實體位址）。此外，處理器211會將對應的元資料記錄至對應所述實體頁面的冗餘位元區中。在本實施例中，所述元資料可記錄所述實體頁面所映射之邏輯位址。在另一實施例中，所述元資料亦可記錄對應所述寫入操作的時間戳記，即，當所述實體頁面的資料寫入操作完成時，處理器211可記錄一個時間戳記來記錄完成所述實體頁面的資料寫入操作的當前時間。

主機系統10是透過儲存控制器210配置多個邏輯單元給可複寫式非揮發性記憶體模組220。所配置的邏輯單元用以存取儲存在可複寫式非揮發性記憶體模組220的多個實體單元中的使用者資料。在此，每一個邏輯單元可以是由一或多個邏輯位址組成。例如，邏輯單元可以是邏輯區塊(Logical Block)、邏輯頁面(Logical Page)或是邏輯扇區(Logical Sector)。一個邏輯單元可以是映射至一或多個實體單元，其中實體單元可以是一或多個實體位址、一或多個實體扇、一或多個實體程式化單元或者一或多個實體抹除單元。

在以下實施例中，為了方便說明，邏輯單元為邏輯區塊，邏輯子單元指邏輯頁面，並且邏輯位址指對應的邏輯頁面或其位址。每一邏輯單元具有多個邏輯頁面（邏輯位址）；實體單元指實體區塊，實體子單元指實體頁面，並且實體位址指對應的實體頁面或其位址。然而，在另一實施例中，一個實體單元/實體子單元亦可以分別是指任意數目的記憶胞組成，視實務上的需求而定，並且實體位址可指實體區括或實體頁面的位址。

此外，儲存控制器210會建立邏輯轉實體表(Logical To Physical table)與實體轉邏輯表(Physical To Logical table)，以記錄配置給可複寫式非揮發性記憶體模組220的邏輯單元(如，邏輯區塊、邏輯頁面、邏輯位址或邏輯扇區)與實體單元(如，實體抹除單元、實體程式化單元、實體位址或實體扇區)之間的映射關係。換言之，儲存控制器210可藉由邏輯轉實體表來查找一邏輯單元所映射的實體單元，並且儲存控制器210可藉由實體轉邏輯表來查找一實體單元所映射的邏輯單元。然而，上述有關邏輯單元與實體單元映射的技術概念為本領域技術人員之慣用技術手段，不再贅述於此。

在一實施例中，儲存控制器210還包括緩衝記憶體與電源管理電路。緩衝記憶體是耦接至處理器211並且用以暫存來自於主機系統10的資料與指令、來自於可複寫式非揮發性記憶體模組220的資料或其他用以管理儲存裝置20的系統資料（如，邏輯轉實體表與實體轉邏輯表、修剪資訊清單等），以讓處理器211可快速地從緩衝記憶體中存取所述資料、指令或系統資料。電源管理電路是耦接至處理器211並且用以控制儲存裝置20的電源。

以下配合圖1、圖2、圖5A～5C與第一實施例來說明本發明所提供的資料備份方法的細節。

[第一實施例]

圖5A為根據本發明的第一實施例所繪示的邏輯轉實體表的示意圖。圖5B～5C為根據本發明的第一實施例所繪示的資料備份方法的示意圖。請參照圖5A，舉例來說，在本實施例中，為了方便說明，假設主機系統配置用以儲存資料的128個邏輯位址（邏輯頁面）LBA(0)~LBA(127)，可複寫式非揮發性記憶體模組220被配置多個實體單元。每一實體單元具有8個實體頁面。例如，實體單元51具有8個實體頁面51(1)~51(8)。所述實體單元51的時間戳記為“X1”。

處理器211會維護邏輯轉實體表501於記憶體（緩衝記憶體）中。在本實施例中，初始的邏輯轉實體表501是讀取之前備份（儲存）於可複寫式非揮發性記憶體模組220的邏輯轉實體表備份資料，其時間戳記為“X0”。所述邏輯轉實體表501記錄了128個邏輯位址LBA(0)~LBA(127)以及所對應的實體位址PBA(0)~PBA(127)。此外，邏輯轉實體表也可記錄延伸邏輯位址（Extended Logical Address，例如，邏輯轉實體表501記錄延伸邏輯位址exLBA(0)以及對應的實體位址exPBA(0)。所述延伸邏輯位址並不被主機系統10（的作業系統）所管理或是知悉，並且本發明並不限定延伸邏輯位址的大小，即，延伸邏輯位址的總空間可大於或是小於主機系統的作業系統所配置的全部邏輯位址的大小。

假設，讀取自可複寫式非揮發性記憶體模組220的邏輯轉實體表501的多個邏輯位址皆未記錄任何值。在時間T0，假設實體單元51的第1、2、3、4個實體頁面（實體位址）（即，實體頁面51(1)~51(4)）被寫入了資料D511、D512、D513、D514，其中上述資料D511、D512、D513、D514儲存於邏輯位址LBA(0)、LBA(1)、LBA(2)、LBA(3)。對應地，當前的維護於記憶體中的邏輯轉實體表501所記錄的邏輯位址LBA(0)、LBA(1)、LBA(2)、LBA(3)所分別對應的實體位址PBA(0)、PBA(1)、PBA(2)、PBA(3)會記錄了“51_1”、“51_2”、“51_3”、“51_4”。此例子表示在實體單元51中的第1、2、3、4個實體頁面（實體位址）儲存了有效資料（如圖5A所繪示之實體單元51的灰底區塊），如，有效資料D511、D512、D513、D514。此外，如圖5A所繪示，實體頁面51(5)~51(8)沒有儲存任何資料（即，無資料，如圖5A所繪示之實體單元51的空白區塊）。值得一提的是，經由時間戳記的比對，可知道實體單元51最早被使用的時間會晚於初始的邏輯轉實體表501被儲存至可複寫式非揮發性記憶體模組220的時間。即，在寫入有效資料D511、D512、D513、D514至實體單元51之前，初始的邏輯轉實體表501已被備份至可複寫式非揮發性記憶體模組220。應注意的是，若邏輯轉實體表的一邏輯位址並沒有儲存任何資料，此邏輯位址所對應的實體位址所記錄的資訊可為空（即，不儲存任何資訊）。例如，假設邏輯位址LBA(127)沒有儲存資料，邏輯轉實體表501中對應的（所映射的）實體位址PBA(127)不記錄任何資訊（如圖5A所繪示，對應LBA(127)的實體位址PBA(127)不記錄任何資訊）。在另一實施例中，若一邏輯位址所對應的實體位址並未存在有效資料，該邏輯位址會從邏輯轉實體表中被刪除。

圖2是根據本發明的一實施例所繪示的資料備份方法的流程圖。請同時參照圖1與圖2，在步驟S21中，處理器211從主機系統10接收修剪指令。所述修剪指令指示儲存於邏輯位址區段中的無效資料。具體來說，如上所述，安裝於主機系統10上的作業系統刪除某筆資料時，作業系統可經由傳送修剪指令(TRIM command)至儲存裝置20（處理器211），以讓儲存裝置20獲知（處理器211）所述被刪除的某筆資料位於哪個邏輯位址區段（即，哪些邏輯位址上的資料已被作業系統所刪除）。換句話說，儲存裝置20的處理器211可經由所接收的修剪指令來知道儲存於一邏輯位址區段中的資料是無效的（Invalid）（無效資料，Invalid Data）。

舉例來說，請參照圖5B，假設在時間T1，處理器211從主機系統10接收修剪指令TC1，所述修剪指令TC1指示了兩個邏輯位址區段LS1、LS2中的資料已被刪除（已成為無效的）。其中修剪指令TC1是利用兩種資訊來記錄邏輯位址區段LS1、LS2，如，起始邏輯位址用以表示（記錄）邏輯位址區段的第一個邏輯位址（邏輯頁面），並且區段長度用以表示（記錄）邏輯位址區段的總長度，即，對應的邏輯位址區段所包含的所有邏輯位址（邏輯頁面）的總數目。舉例來說，經由修剪指令TC1所指示邏輯位址區段LS1的起始邏輯位址“LBA(0)”與區段長度“2”，可知道目前儲存在邏輯位址LBA(0)與邏輯位址LBA(1)共“2”個邏輯位址的資料成為無效資料。應注意的是，時間T1表示晚於時間T0的一個時間點。此外，本發明並不限定上述邏輯轉實體表的結構。例如，在另一實施例中，邏輯轉實體表會僅利用一行資料欄來固定依序地記錄所有邏輯位址所映射的實體位址。

請參考圖2，接著，在步驟S23中，處理器211根據所述修剪指令、多個實體位址中的目標實體位址來產生修剪資訊，以根據所述修剪資訊更新第一修剪資訊清單為第二修剪資訊清單，其中所述修剪資訊記錄無效資料起始邏輯位址、無效資料長度值、修剪資訊頁面順序與修剪資訊時間戳記。所述第一修剪資訊清單指舊的修剪資訊清單，所述第二修剪資訊清單指根據當前所接收的修剪指令而產生的新的修剪資訊清單。

請參考圖5B，舉例來說，接續上方的例子，接收到修剪指令TC1後，處理器211會根據修剪指令TC1的資訊產生（更新）修剪資訊清單TIL1（如箭頭A502所示）。所述修剪資訊清單TIL1會被維護於緩衝記憶體（以下亦稱，記憶體）中。對應修剪指令TC1的所兩筆邏輯位址區段LS1、LS2，所產生之修剪資訊清單TIL1也會記錄兩筆修剪資訊。為了產生修剪資訊清單的兩筆修剪資訊，處理器211根據所接收之修剪指令，記錄邏輯位址區段的起始邏輯位址為修剪資訊之無效資料起始邏輯位址，並且記錄邏輯位址區段的區段長度為修剪資訊之無效資料長度值。例如，針對邏輯位址區段LS1，對應邏輯位址區段LS1所產生的修剪資訊TI1的無效資料起始邏輯位址為“LBA(0)”，其相同於邏輯位址區段LS1的起始邏輯位址“LBA(0)”；修剪資訊TI1的無效資料長度值為“2”，其相同於邏輯位址區段LS1的區段長度“2”。

接著，處理器211會從可複寫式非揮發性記憶體模組220的多個實體單元中辨識可用的實體單元為目標實體單元，並且從所述目標實體單元的多個實體頁面中辨識可用的目標實體頁面。舉例來說，當前已使用且未寫滿的實體單元51可被辨識為可用的實體單元（被辨識為目標實體單元），並且空的實體頁面51(5)~51(8)為可用的實體頁面。在此例子中，如箭頭A503所示，處理器211選擇了排序在實體頁面51(5)~51(8)中的第一個實體頁面51(5)為目標實體頁面，以儲存修剪資訊清單TIL1。此外，處理器211會辨識目標實體單元51的時間戳記（即，“X1”），並且辨識目標實體頁面51(5)於目標實體單元51的所有實體頁面51(4)~51(8)中的順序（亦稱，頁面順序）。接著，處理器211根據目標實體位址，記錄對應目標實體頁面的頁面順序為修剪資訊之修剪資訊頁面順序以及記錄目標實體單元的時間戳記為修剪資訊之修剪資訊時間戳記。即，根據欲儲存修剪資訊清單TIL1的目標實體頁面位於目標實體單元51的順序（第5個實體頁面），修剪資訊TI1的修剪資訊頁面順序被記錄為“5”；根據目標實體單元51的時間戳記，修剪資訊TI1的修剪資訊時間戳記被記錄為“X1”。當一修剪資訊的所有種類的資訊都已被記錄，便完成了所述修剪資訊的產生。所產生之修剪資訊會被記錄（附加至）維護於記憶體的修剪資訊清單中。

相似於上述方式，處理器211會根據邏輯位址區段LS2來產生修剪資訊TI2，並且附加修剪資訊TI2至修剪資訊清單TIL1中。如上所述，在本實施例中，所述修剪資訊TI2會被附加至之前所產生的修剪資訊清單TIL1的修剪資訊TI1之後。此外，對應所接受的每個修剪指令，當前維護於記憶體中的修剪資訊清單都會被產生（或被更新）。即，若記憶體中沒有任何修剪資訊清單，處理器211會根據當前接收的修剪指令來新增一個修剪資訊清單（如，第二修剪資訊清單）至記憶體中，並且根據當前接收的修剪指令來產生對應的修剪資訊至修剪資訊清單中；若記憶體中已存在一個修剪資訊清單（如，第一修剪資訊清單），處理器211會根據當前接收的修剪指令來產生且附加對應的修剪資訊至已存在的修剪資訊清單的其他修剪資訊之後，以產生一個不同於舊的第一修剪資訊清單的新的第二修剪資訊清單。

在完成修剪資訊清單的產生（或更新）後，在步驟S25中，處理器211將所述第二修剪資訊清單儲存至所述目標實體位址。即，對應每次接收的修剪指令所產生的新的修剪資訊清單，處理器211會將所產生的新的修剪資訊清單（包含舊的修剪資訊清單的所有修剪資訊與對應本次修剪指令所產生的修剪資訊）寫入至可複寫式非揮發性記憶體模組220的目標實體頁面51(5)。應注意的是，本發明並不限定目標實體頁面的個數。

另一方面，處理器211會根據修剪指令TC1所指示的邏輯位址區段LS1、LS2來更新邏輯轉實體表501為邏輯轉實體表502（如箭頭A501所示）。更詳細來說，處理器211根據邏輯位址區段LS1清空了邏輯轉實體表的邏輯位址LBA(0)、LBA(1)所分別對應的實體位址PBA(0)、PBA(1)（如，將實體位址PBA(0)所記錄的資訊“51_1”修改為“0”，將實體位址PBA(1)所記錄的資訊“51_2”修改為“0”）。相似地，根據邏輯位址區段LS2，邏輯位址LBA(3)所對應的實體位址PBA(3)所記錄的資訊也被清空。換言之，實體單元51的實體頁面51(1)、51(2)、51(4)已被處理器211視為無效資料（如菱形格線所示）。

接著，在步驟S27中，處理器211將用以儲存所述第二修剪資訊清單的所述目標實體位址記錄至第一邏輯轉實體表的修剪資訊清單實體位址，以更新所述第一邏輯轉實體表為第二邏輯轉實體表。例如，用以儲存所述第二修剪資訊清單的目標實體頁面51(5)，其目標實體位址為“51_5”，並且此資訊（即，“51_5”）會被記錄至邏輯轉實體表501的對應延伸邏輯位址exLBA(0)的修剪資訊清單實體位址exPBA(0)，以更新邏輯轉實體表501（亦稱，第一邏輯轉實體表）為邏輯轉實體表502（亦稱，第二邏輯轉實體表）。

此外，在步驟S29中，當符合預設條件，處理器211可儲存所述第二邏輯轉實體表至所述可複寫式非揮發性記憶體模組。具體來說，上述步驟S21～S27所更新的邏輯轉實體表502會在符合預設條件的時候，被儲存至可複寫式非揮發性記憶體模組220中。所述預設條件例如為經過一固定閒置時間、所述修剪資訊清單的大小已超過預設大小、當前時間與邏輯轉實體表的時間戳記之間的時間間隔以超過一預設時間門檻值、所接收的修剪指令所指示的無效資料已超過另一預設大小等條件或其組合。

應注意的是，如上所述，處理器211會對應資料寫入操作來更新邏輯轉實體表。請參照圖5C，舉例來說，假設在晚於時間T1的時間T2，處理器211接收寫入指令WC1。所述寫入指令WC1包括起始邏輯位址、區段長度以及寫入資料。更詳細來說，寫入指令指示處理器211將寫入資料WD寫入至邏輯位址LBA(0)、LBA(1)，共兩個邏輯位址（邏輯頁面）中。即，用以儲存寫入資料WD的邏輯區段包含“2”個邏輯頁面，並且第一個邏輯頁面的邏輯位址為LBA(0)。處理器211根據寫入指令WC1，依序將寫入資料WD儲存至當前的可用的實體單元51的實體頁面51(6)、51(7)中（如箭頭A504所示）。即，儲存在實體頁面51(6)、51(7)中的資料D516、D517可組成上述的寫入資料WD。值得一提的是，儲存在實體頁面51(5)的資料TIL1即為前述所寫入之修剪資訊清單TIL1。

以下會配合圖3、圖4以及圖5D～5F來說明第一實施利索提供的資料恢復方法，其利用了前述的資料備份方法所產生且儲存的修剪資訊清單。

圖3是根據本發明的一實施例所繪示的資料恢復方法的流程圖。圖5D～5F為根據本發明的第一實施例所繪示的資料恢復方法的示意圖。請先參照圖3，在步驟S31中，處理器211根據儲存在所述可複寫式非揮發性記憶體模組的第一邏輯轉實體表與所述可複寫式非揮發性記憶體模組中時間戳記大於所述第一邏輯轉實體表的時間戳記的所有有效資料的實體位址與對應的邏輯位址來重建所述第一邏輯轉實體表，並且將重建後之所述第一邏輯轉實體表儲存至一記憶體為第二邏輯轉實體表。

舉例來說，請參照圖5D，接續之前圖5A～5C的例子，假設在晚於時間T2的時間T3發生了突然斷電事件。由於原本（如，時間T2的）儲存在記憶體中的修剪資訊清單TIL1與邏輯轉實體表503會因為突然斷電而丟失，因此，儲存裝置20開電後，處理器211會偵測到突然斷電事件的發生，並且對應地執行資料恢復操作。在所述資料恢復操作中，在晚於時間T3的時間T4，處理器211會先重建邏輯轉實體表。詳細來說，處理器211會先從可複寫式非揮發性記憶體模組220讀取最新儲存的邏輯轉實體表501至記憶體，並且讀取對應所有被寫入任何資料的實體頁面的元資料，以找出時間戳記大於邏輯轉實體表501的時間戳記的實體頁面的位址與對應的有效資料（即，處理器211會找尋寫入時間晚於邏輯轉實體表501的備份時間的所有實體頁面）。接著，處理器211會根據此些實體頁面的元資料所記錄的對應的邏輯位址來更新邏輯轉實體表501。

例如，處理器211已辨識目前實體單元51的實體頁面51(1)~51(7)所分別儲存的資料D511、D512、D513、D514、TIL1、D516、D517所屬的實體單元51的時間戳記“X1”大於邏輯轉實體表501的時間戳記“X0”。即，寫入資料D511、D512、D513、D514、TIL1、D516、D517皆晚於（初始的）邏輯轉實體表501備份至可複寫式非揮發性記憶體模組220的時間。基此，處理器211會根據資料D511、D512、D513、D514、TIL1、D516、D517來進行資料恢復操作。處理器211會以資料D511、D512、D513、D514、TIL1、D516、D517的時間戳記與對應的實體頁面（實體位址）的順序（即，寫入資料D511、D512、D513、D514、TIL1、D516、D517至可複寫式非揮發性記憶體模組220的時間）的先後來判斷其所對應的邏輯位址的映射關係的準確程度。換言之，若兩個不同的實體位址所對應的邏輯位址相同，處理器211會以時間戳記較大的實體位址為準，即，將所述邏輯位址應設置時間戳記較大的實體位址。在本實施例中，處理器211會針對使用者資料（如，經由資料寫入操作的資料D511、D512、D513、D514、D516、D517）來重建（更新）邏輯轉實體表（如箭頭A505所示）。

舉例來說，，處理器211根據對應不同實體頁面的元資料辨識對應實體頁面51(1)的邏輯位址為LBA(0)；對應實體頁面51(2)的邏輯位址為LBA(1)；對應實體頁面51(3)的邏輯位址為LBA(2)；對應實體頁面51(4)的邏輯位址為LBA(3)；對應實體頁面51(5)的邏輯位址為LBA(0)；以及對應實體頁面51(6)的邏輯位址為LBA(1)。對於邏輯位址重疊的資料D511、D512、D516、D517，處理器211會根據對應的實體頁面51(1)、51(2)、51(6)、51(7)的順序判定資料D516、D517為分別對應邏輯單元LBA(0)、LBA(1)的有效資料，並且資料D511、D512為分別對應邏輯單元LBA(0)、LBA(1)的無效資料。處理器211將此辨識的結果反映至邏輯轉實體表501中（如箭頭A506所示），以完成重建邏輯轉實體表501為邏輯轉實體表504。換言之，根據重建後的邏輯轉實體表504，處理器211可知道當前儲存在實體頁面51(1)～51(2)的資料D511、D512為無效資料（如，圖5E的菱形格線所示）。

此外，處理器211亦會將時間戳記大於邏輯轉實體表501的時間戳記的修剪資訊清單TIL1的實體位址（即，“51_5”）記錄至邏輯轉實體表501的邏輯位址exLBA(0)所對應的實體位址exPBA(0)。

完成邏輯轉實體表的重建後，在步驟S33中，若所述可複寫式非揮發性記憶體模組儲存有一或多個第一修剪資訊清單，處理器211辨識所述一或多個第一修剪資訊清單中最新的第二修剪資訊清單，其中所述一或多個第一修剪資訊清單的每一個第一修剪資訊清單記錄一或多筆修剪資訊，其中每一筆修剪資訊記錄無效資料起始邏輯位址、無效資料長度值、修剪資訊頁面順序與修剪資訊時間戳記，其中所述一或多個第一修剪資訊清單的時間戳記皆大於所述第一邏輯轉實體表的時間戳記。具體來說，如上述，處理器211會利用比較時間戳記的方式，從可複寫式非揮發性記憶體模組所儲存的所有修剪資訊清單中較邏輯轉實體表501新的（即，比邏輯轉實體表501更晚被儲存至可複寫式非揮發性記憶體模組220）一或多個修剪資訊清單（亦稱，第一修剪資訊清單）中辨識其中的最新者。例如，所述第一修剪資訊清單中具有最多修剪資訊（因為修剪資訊清單會隨著時間持續被附加/更新修剪資訊）的修剪資訊清單（亦稱，第二修剪資訊清單）被判定為最新的修剪資訊清單。所述修剪資訊清單/修剪資訊的資料結構已說明如上，不贅述於此。如圖5D的例子，處理器211會辨識第二修剪資訊清單TIL1，並且將第二修剪資訊清單TIL1讀取至記憶體中（如箭頭A507所示）。

接著，在步驟S35中，處理器211根據所述第二修剪資訊清單的所有修剪資訊與所述第二邏輯轉實體表來更新所述第二邏輯轉實體表或更新儲存於所述記憶體中的第三修剪資訊清單。以下配合圖4來詳細說明步驟S35的詳細流程。

圖4為根據本發明的一實施例所繪示的圖3的步驟S35的流程圖。請參照圖4，在步驟S351中，處理器211依據第二修剪資訊清單所記錄的多個第一修剪資訊的記錄順序來選擇所述多個第一修剪資訊中的第二修剪資訊，以對所選擇的所述第二修剪資訊執行解析操作，其中所述第二修剪資訊為所述多個第一修剪資訊內尚未被解析之多個修剪資訊中記錄順序最前者。舉例來說，接續圖5D的例子，請參照圖5E，處理器211根據記憶體中的修剪資訊清單TIL1來對其中的修剪資訊TI1、TI2（亦稱，第一修剪資訊）進行解析操作。首先，在時間T5，處理器211會從尚未被選擇以進行解析操作的修剪資訊TI1、TI2中的排列在最前面的修剪資訊TI1（亦稱，第二修剪資訊）來進行解析操作（如箭頭A508所示）。

接著，處理器211開始對所選擇之修剪資訊TI1進行解析操作，在步驟S352中，根據所選擇的所述第二修剪資訊所記錄的第一無效資料起始邏輯位址與第一無效資料長度來辨識第一邏輯位址區段，根據第二邏輯轉實體表辨識儲存於所述第一邏輯位址區段內多個第一邏輯位址的多個第一有效資料，並且選擇所述多個第一有效資料中尚未被選擇的第二有效資料。

舉例來說，根據修剪資訊TI1的無效資料起始邏輯位址（亦稱，第一無效資料起始邏輯位址）與無效資料長度（亦稱，第一無效資料長度）來辨識出儲存無效資料的第一邏輯位址區段。由於第一無效資料起始邏輯位址為“LBA(0)”，並且第一無效資料長度為“2”，因此，第一邏輯位址區段包含邏輯位址LBA(0)、LBA(1)。接著，處理器211根據當前位於記憶體中的邏輯轉實體表504（參照圖5D）辨識對應第一邏輯位址區段的邏輯位址LBA(0)、LBA(1)所對應的實體位址分別為“51_6”與“51_7”以及對應的有效資料D516、D517。由於有效資料D516、D517皆未被選擇過，處理器211會先選擇有效資料D516。

接著，在步驟S353中，處理器211會比較所述第二修剪資訊所記錄的第一修剪資訊時間戳記與所述第二有效資料的有效資料時間戳記。所述有效資料時間戳記為儲存第二有效資料的實體單元的時間戳記。接續上述的例子，處理器211會比較修剪資訊TI1的修剪資訊時間戳記“X1”與有效資料D516的有效資料時間戳記（即，儲存有效資料D516的實體單元51的時間戳記“X1”）。

在本實施例中，若第一修剪資訊時間戳記大於第二有效資料的有效資料時間戳記，執行步驟S354；若第一修剪資訊時間戳記小於第二有效資料的有效資料時間戳記，執行步驟S355；若第一修剪資訊時間戳記等於第二有效資料的有效資料時間戳記，執行步驟S356。

在上述的例子中，由於修剪資訊TI1的修剪資訊時間戳記“X1”等於有效資料D516的有效資料時間戳記“X1”，接續至步驟S356，處理器211判斷第二修剪資訊所記錄的第一修剪資訊頁面順序大於或小於所述第二有效資料的有效資料頁面順序。所述有效資料頁面順序為儲存第二有效資料的實體頁面於其所屬之實體單元的所有實體頁面中的順序。在本實施例中，若判定第一修剪資訊頁面順序大於第二有效資料的有效資料頁面順序，處理器211執行步驟S354；若第一修剪資訊頁面順序小於有效資料頁面順序，執行步驟S355。

舉例來說，接續上述的例子，處理器211會接著判斷修剪資訊TI1的修剪資訊頁面順序“5”大於或小於有效資料D516的有效資料頁面順序。由於有效資料D516儲存於實體頁面51(6)，其排序為實體單元51中所有實體頁面的第6個。因此，有效資料D516的有效資料頁面順序為“6”。基此，處理器211會判定修剪資訊TI1的修剪資訊頁面順序小於有效資料D516的有效資料頁面順序（即，5小於6），並且接續至步驟S355。

在步驟S355中，處理器211根據所述第一邏輯位址修改所述第二修剪資訊，以使所述第一邏輯位址區段中不包含所述第一邏輯位址。具體來說，因為修剪資訊TI1的修剪資訊頁面順序小於有效資料D516的有效資料頁面順序，處理器211會判定寫入有效資料D516的時間晚於寫入修剪資訊TI1的時間，並且處理器211會以有效資料D516以及對應的邏輯位址LBA(0)為準，不會因為有效資料D516所對應的邏輯位址LBA(0)被包含於修剪資訊TI1所指示的儲存無效資料的邏輯位址區段而認為邏輯位址LBA(0)儲存的資料為無效資料。換言之，處理器211不會更改（清空）邏輯轉實體表504的邏輯位址LBA(0)所對應的實體位址PBA(0)所記錄的資訊 “51_6”。此外，處理器211可更新修剪資訊清單TIL1的修剪資訊TI1的邏輯位址區段，以讓此邏輯位址區段不包含邏輯位址LBA(0)。例如，處理器211可修改修剪資訊TI1的無效資料起始邏輯位址為邏輯位址LBA(1)，並且修改修剪資訊TI1的無效資料長度值為邏輯位址LBA(1)，以更新修剪資訊TI1。至此，對於有效資料D516的解析已完成。

接著，在步驟S357中，處理器211判斷所述第一邏輯位址區段中所有的所述多個第一有效資料是否皆已被選擇。若是，則執行步驟S358；若否，則執行步驟S352，以選擇位於該邏輯位址區段的其他尚未被選擇的有效資料來進行解析。

接續上述的例子，解析完有效資料D516後，在步驟S357中，處理器211會判定有效資料D516、D517並非皆已被選擇（即，有效資料D517尚未被選擇），處理器211再度執行步驟S352，對有效資料D517進行解析。相似於上述對於有效資料D516的解析，處理器211會以有效資料D517所對應的邏輯位址LBA(1)為準，不會更改（清空）邏輯轉實體表504的邏輯位址LBA(1)所對應的實體位址PBA(0)所記錄的資訊 “51_7”。此外，處理器211可更新修剪資訊清單TIL1的修剪資訊TI1的邏輯位址區段，以讓此邏輯位址區段不包含邏輯位址LBA(0)。例如，處理器211可刪除/清空修剪資訊TI1的所有資訊（因為處理器211判定修剪資訊TI1所指示的邏輯位址區段內的資料皆為有效資料）。

接著，在步驟S357中，處理器211判定所有有效資料D516、D517皆已被選擇（已被解析），並且判定對於修剪資訊TI1的解析操作已完成。接續至步驟S358，處理器211判斷所述多個第一修剪資訊是否皆被解析。即，當完成一個修剪資訊的解析操作，處理器211會接著判斷目前在記憶體中的修剪資訊清單是否還有未執行解析操作的修剪資訊。

舉例來說，接續上述的例子，由於修剪資訊TI2尚未被解析且排列在最前，因此，請參照圖5F，在時間T6，處理器211開始對修剪資訊TI2執行解析操作（如箭頭A509所示）。如上述的方法，處理器211會辨識修剪資訊TI2所指示的邏輯位址區段內的有效資料D514以及對應的邏輯位址LBA(3)，並且判定修剪資訊TI2的修剪資訊頁面順序大於有效資料D514的有效資料頁面順序。基此，處理器211會知道，對於邏輯位址LBA(3)所儲存的資料是否為無效資料，修剪資訊TI2所給出的對應資訊（修剪資訊TI2認為該資料為無效資料）會較邏輯轉實體表給的對應資訊（邏輯轉實體表認為該資料為有效資料）還準確。接著，處理器211執行步驟S354。在步驟S354中，處理器211會將所述第二有效資料判定為無效，將所述第二邏輯轉實體表所記錄的對應所述第一邏輯位址的第一實體位址清空。即，處理器211將有效資料D514判定為無效（即，儲存於實體頁面51(4)中的資料D514為無效資料），並且將邏輯轉實體表的邏輯位址LBA(3)所對應的實體位址PBA(3)所記錄的資訊清空（即，將“51_4”修改為“0”），以更新邏輯轉實體表504為邏輯轉實體表507。

相似地，處理器211接續執行步驟S357。處理器211會判定對應修剪資訊TI2的邏輯位址區段的所有有效資料皆被解析，接續執行步驟S358，並且判定修剪資訊清單TIL1中的所有修剪資訊皆完成解析操作。至此，處理器211才完成更新邏輯轉實體表504與更新修剪資訊清單TI1的操作。此時，更新後的邏輯轉實體表507所記錄的資訊會相同於在斷電之前（如，時間T2）的邏輯轉實體表503所記錄的資訊。處理器211也完成了對應突然斷電事件的所述資料恢復操作。

[第二實施例]

第二實施例接續第一實施例的例子。其中，硬體元件與資料備份方法、資料恢復方法的流程相同於第一實施例，不再贅述於此。以下會藉由第二實施例、圖5G～5L來闡述包含了垃圾回收操作的資料備份方法與資料恢復方法的實施方式，以進一步說明本發明的效用。

圖5G～5H為根據本發明的第二實施例所繪示的資料備份方法的示意圖。圖5I～5L為根據本發明的第二實施例所繪示的資料恢復方法的示意圖。請參照圖5G，接續圖5C的例子，在時間T2後的時間T7，處理器211接收修剪指令TC2。根據修剪指令TC2，處理器211更新邏輯轉實體表503為邏輯轉實體表508（如箭頭A510所示），即，根據修剪指令TC2所指示的邏輯位址LBA(2)將邏輯轉實體表503的邏輯位址LBA(2)所對應的實體位址PBA(2)所記錄的資訊“51_3”修改為“0”。此外，處理器211更新記憶體中的修剪資訊清單TIL1為修剪資訊清單TIL2（如箭頭A511所示），即，附加對應修剪指令TC2的修剪資訊TI3至修剪資訊清單TIL1已使之成為修剪資訊清單TIL2。在此實施例中，更新後之修剪資訊清單TIL2被寫入至實體頁面51(8)（如箭頭A512所示），並且延伸邏輯位址所對應的實體位址exPBA(0)所記錄的資訊為實體頁面51(8)的位址“51_8”。修剪資訊TI3的產生方式已詳述於上，不再贅述於此。

請參照圖5H，在時間T7後的時間T8，處理器211接收垃圾回收指令GC1。所述垃圾回收指令GC1記錄了要執行垃圾回收的實體單元的資訊（如，“51”）。根據垃圾回收指令GC1與邏輯轉實體表508，處理器211選擇可用的實體單元52，將實體單元51中所有有效資料（即，邏輯轉實體表508所記錄的儲存於實體單元51的資料D516、D517、TIL2）複製至實體單元52（如箭頭A513所示），並且對應地更新邏輯轉實體表508為邏輯轉實體表509。所述實體單元52的時間戳記為“X2”（X2大於X1，X1大於X0）。應注意的是，原本在實體單元51中具有兩筆修剪資訊清單TIL1、TIL2，處理器211可根據邏輯轉實體表508中記錄已被寫入的最新修剪資訊清單的實體位址exPBA(0)所記錄的值“51_8”，判定修剪資訊清單TIL2為最新的（有效的）修剪資訊清單，並且會在針對實體單元51的垃圾回收操作中，複製修剪資訊清單TIL2，並且對應地於邏輯轉實體表509中更新修剪資訊清單TIL2於實體單元52的實體位址（即，“52_3”）。也就是說，處理器211根據用以儲存有效資料D516、D517、TIL2的實體頁面52(1)、52(2)、52(3)的實體位址“52_1”、“52_2”、“52_3”，邏輯位址LBA(0)、LBA(1)及對應最新的已儲存之修剪資訊清單的邏輯位址exLBA(0)來更新邏輯轉實體表508為邏輯轉實體表509。

請參照圖5I，假設在晚於時間T8的時間T9發生了突然斷電事件。應注意的是，實體單元51尚未被抹除。儲存裝置20開電後，處理器211會偵測到突然斷電事件的發生，並且對應地執行資料恢復操作。在所述資料恢復操作中，相似於第一實施例所述的資料恢復方法，在晚於時間T9的時間T10，處理器211會先重建邏輯轉實體表（如箭頭A514、A515所示），以獲得且儲存邏輯轉實體表510於記憶體中。應注意的是，根據重建後的邏輯轉實體表510，處理器211目前認為邏輯位址LBA(2)儲存了有效資料D513於實體位址“51_3”；以及邏輯位址LBA(3)儲存了有效資料D514於實體位址“51_4”。此外，處理器211於實體單元52中辨識到最新的修剪資訊清單TIL2，並且儲存修剪資訊清單TIL2至記憶體中（如箭頭A516所示）。值得一提的是，若多個修剪資訊清單所屬之實體單元的時間戳記相等，處理器211可根據頁面順序（頁面順序越後者越新）或是所包含的修剪資訊的數量（數量越多者越新）來判斷所述多個修剪資訊清單的新舊。

請參照圖5J，處理器211開始解析修剪資訊清單TIL2的修剪資訊TI1。依據前述的資料恢復方法，（因為修剪資訊TI1的修剪資訊時間戳記“X1”小於有效資料D516、D517的有效資料時間戳記“X2”）處理器211判定修剪資訊TI1所指示的邏輯位址區段（邏輯位址LBA(0)~LBA(1)）儲存了有效資料，並且不修改邏輯轉實體表510的邏輯位址LBA(0)、LBA(1)所對應的實體位址所記錄的資訊（如箭頭A517所示）。

請參照圖5K，解析完修剪資訊TI1後，處理器211開始解析修剪資訊清單TIL2的修剪資訊TI2。修剪資訊TI3指示邏輯位址LBA(3)（對應實體位址“51_4”）儲存無效資料。依據前述的資料恢復方法，因為修剪資訊TI2的修剪資訊時間戳記“X1”等於（對應實體位址“51_4”的）資料D514的有效資料時間戳記“X1”且修剪資訊TI2的修剪資訊頁面順序“5”大於有效資料D514的有效資料頁面順序“4”（修剪資訊TI2的修剪資訊頁面順序“5”大於邏輯轉實體表的所記錄的實體位址“51_4”所對應的實體頁面的頁面順序“4”），處理器211會判定修剪資訊TI2所指示的邏輯位址區段（邏輯位址LBA(3)）儲存了無效資料，並且修改邏輯轉實體表510的邏輯位址LBA(3)所對應的實體位址所記錄的資訊（如箭頭A518所示，邏輯轉實體表511的邏輯位址LBA(3)所對應的實體位址所記錄的資訊從“51_4”被修改為“0”），以獲得更新後邏輯轉實體表511。

請參照圖5L，解析完修剪資訊TI2後，處理器211開始解析修剪資訊清單TIL2的修剪資訊TI3。修剪資訊TI3指示邏輯位址LBA(2)（對應實體位址“51_3”）儲存無效資料。因為修剪資訊TI3的修剪資訊時間戳記“X1”等於（對應實體位址“51_3”的）資料D513的有效資料時間戳記“X1”且修剪資訊TI3的修剪資訊頁面順序“8”大於資料D513的有效資料頁面順序“3”（修剪資訊TI2的修剪資訊頁面順序“8”大於邏輯轉實體表的所記錄的實體位址“51_3”所對應的實體頁面的頁面順序“3”），處理器211判定修剪資訊TI3所指示的邏輯位址區段（邏輯位址LBA(2)）儲存了無效資料，並且修改邏輯轉實體表511的邏輯位址LBA(2)所對應的實體位址所記錄的資訊（如箭頭A519所示，邏輯轉實體表512的邏輯位址LBA(2)所對應的實體位址所記錄的資訊從“51_3”被修改為“0”），以獲得更新後邏輯轉實體表512。此時，修剪資訊清單TIL2的所有的修剪資訊已被解析，完成了資料恢復操作。應注意的是，完成資料恢復操作後的邏輯轉實體表512所記錄的邏輯位址與實體位址的映射關係即可被恢復至相同於突然斷電事件發生之前（時間T8）的邏輯轉實體表509所記錄的映射關係。

綜上所述，本發明實施例所提供的資料讀取方法以及儲存控制器，可根據所接收的修剪指令來產生特定資料架構的修剪資訊，並且利用已備份至可複寫式非揮發性記憶體模組的修剪資訊清單與邏輯轉實體表，來進行對應的資料恢復操作。由於不需要因為所接收之修剪指令而備份對應的修剪資訊與邏輯轉實體表至可複寫式非揮發性記憶體模組，因此避免了大量的寫入操作，並且增進儲存裝置整體的工作效率。此外，在斷電後，可經由所備份的特定結構（記錄時間戳記及頁面順序）的修剪資訊清單與邏輯轉實體表及對應的時間戳記或/及頁面順序來識別上述資料的準確性，以有效地進行資料恢復，進而重建斷電前之修剪資訊清單與邏輯轉實體表。

雖然本發明已以實施例揭露如上，然其並非用以限定本發明，任何所屬技術領域中具有通常知識者，在不脫離本發明的精神和範圍內，當可作些許的更動與潤飾，故本發明的保護範圍當視後附的申請專利範圍所界定者為準。

10‧‧‧主機系統

20‧‧‧儲存裝置

110、211‧‧‧處理器

120‧‧‧主機記憶體

130‧‧‧資料傳輸介面電路

210‧‧‧儲存控制器

212‧‧‧資料傳輸管理電路

213‧‧‧記憶體介面控制電路

220‧‧‧可複寫式非揮發性記憶體模組

230‧‧‧連接介面電路

S21、S23、S25、S27、S29‧‧‧資料備份方法的流程步驟

S31、S33、S35‧‧‧資料恢復方法的流程步驟

S351、S352、S353、S354、S355、S356、S357、S358‧‧‧步驟S35的流程步驟

501、502、503、504、507、508、509、510、511、512‧‧‧邏輯轉實體表

51(1)~51(8)、52(1)~52(8)‧‧‧實體頁面

51、52‧‧‧實體單元

D511、D512、D513、D514、D516、D517‧‧‧資料

TC1、TC2‧‧‧修剪指令

WC1‧‧‧寫入指令

GC1‧‧‧垃圾回收指令

TIL1、TIL2‧‧‧修剪資訊清單

TI1、TI2、TI3‧‧‧修剪資訊

LBA(0)~LBA(127)‧‧‧邏輯位址

PBA(0)~PBA(127)、exPBA(0)‧‧‧實體位址

exLBA(0)‧‧‧延伸邏輯位址

LS1、LS2‧‧‧邏輯位址區段

A501、A502、A503、A504、A505、A506、A507、A508、A509、A510、A511、A512、A513、A514、A515、A516、A517、A518、A519‧‧‧箭頭

圖1是根據本發明的一實施例所繪示的主機系統及儲存裝置的方塊示意圖。 圖2是根據本發明的一實施例所繪示的資料備份方法的流程圖。 圖3是根據本發明的一實施例所繪示的資料恢復方法的流程圖。 圖4為根據本發明的一實施例所繪示的圖3的步驟S35的流程圖。 圖5A為根據本發明的第一實施例所繪示的邏輯轉實體表的示意圖。 圖5B～5C為根據本發明的第一實施例所繪示的資料備份方法的示意圖。 圖5D～5F為根據本發明的第一實施例所繪示的資料恢復方法的示意圖。 圖5G～5H為根據本發明的第二實施例所繪示的資料備份方法的示意圖。 圖5I～5L為根據本發明的第二實施例所繪示的資料恢復方法的示意圖。

Claims (18)

1. 一種資料備份方法，適用於配置有一可複寫式非揮發性記憶體模組的一儲存裝置，其中該可複寫式非揮發性記憶體模組具有多個實體單元，並且該可複寫式非揮發性記憶體模組被配置多個實體位址，其中耦接至該儲存裝置之一主機系統配置多個邏輯位址，所述方法包括： 從該主機系統接收一修剪指令，其中該修剪指令指示儲存於一邏輯位址區段中的無效資料； 根據該修剪指令、該些實體位址中的一目標實體位址來產生一修剪資訊，以根據該修剪資訊更新一第一修剪資訊清單為一第二修剪資訊清單，其中該修剪資訊記錄一無效資料起始邏輯位址、一無效資料長度值、一修剪資訊頁面順序與一修剪資訊時間戳記； 將該第二修剪資訊清單儲存至該目標實體位址，其中該第一或第二修剪資訊清單根據接收對應一或多筆修剪資訊的修剪指令的時間順序來依序記錄所述一或多筆修剪資訊； 將用以儲存該第二修剪資訊清單的該目標實體位址記錄至一第一邏輯轉實體表的一修剪資訊清單實體位址，以更新該第一邏輯轉實體表為一第二邏輯轉實體表；以及 當符合一預設條件，儲存該第二邏輯轉實體表至該可複寫式非揮發性記憶體模組。
2. 如申請專利範圍第1項所述的資料備份方法，所述方法更包括： 從該些實體單元中辨識可用的一實體單元為一目標實體單元，並且從該目標實體單元的多個實體頁面中辨識可用的一目標實體頁面，其中該目標實體頁面用以儲存該第二修剪資訊清單，並且該目標實體位址為該目標實體單元的該目標實體頁面的位址；以及 辨識該目標實體單元的一時間戳記，並且辨識該目標實體頁面於該目標實體單元的所有實體頁面中的順序為一頁面順序， 其中該目標實體單元的該時間戳記用以表示該目標實體單元最早被使用的時間。
3. 如申請專利範圍第2項所述的資料備份方法，其中該修剪指令包括該邏輯位址區段的起始邏輯位址與該邏輯位址區段的區段長度，其中該起始邏輯位址表示該邏輯位址區段的第一個邏輯位址，並且該區段長度表示該邏輯位址區段所包含的所有邏輯位址的總數目，其中上述根據該修剪指令、該些實體位址中的該目標實體位址來產生該修剪資訊，以根據該修剪資訊更新該第一修剪資訊清單為該第二修剪資訊清單的步驟包括： 根據所接收之該修剪指令，記錄該邏輯位址區段的該起始邏輯位址為該修剪資訊之無效資料起始邏輯位址，並且記錄該邏輯位址區段的該區段長度為該修剪資訊之無效資料長度值；以及 根據該目標實體位址，記錄對應該目標實體頁面的該頁面順序為該修剪資訊之修剪資訊頁面順序以及記錄該目標實體單元的該時間戳記為該修剪資訊之修剪資訊時間戳記，以產生該修剪資訊， 其中上述根據該修剪資訊更新該第一修剪資訊清單為該第二修剪資訊清單的步驟包括將所產生的該修剪資訊附加至被維護於一記憶體中的該第一修剪資訊清單的其他修剪資訊之後，以更新該第一修剪資訊清單為該第二修剪資訊清單。
4. 如申請專利範圍第3項所述的資料備份方法，其中上述當符合該預設條件，儲存該第二邏輯轉實體表至該可複寫式非揮發性記憶體模組的步驟包括： 當符合該預設條件，根據該第二修剪資訊清單的所有修剪資訊來更新該第二邏輯轉實體表，將該第二邏輯轉實體表的該修剪資訊清單實體位址清空，並且將該第二邏輯轉實體表儲存至該可複寫式非揮發性記憶體模組；以及 反應於完成將更新後之該第二邏輯轉實體表儲存至該可複寫式非揮發性記憶體模組，清空維護於該記憶體中的該第二修剪資訊清單所記錄的所有修剪資訊。
5. 一種資料恢復方法，適用於配置有一可複寫式非揮發性記憶體模組的一儲存裝置，其中該可複寫式非揮發性記憶體模組具有多個實體單元，並且該可複寫式非揮發性記憶體模組被配置多個實體位址，其中耦接至該儲存裝置之一主機系統配置多個邏輯位址，所述方法包括： 根據儲存在該可複寫式非揮發性記憶體模組的一第一邏輯轉實體表與該可複寫式非揮發性記憶體模組中時間戳記大於該第一邏輯轉實體表的時間戳記的所有有效資料的實體位址與對應的邏輯位址來重建該第一邏輯轉實體表，並且將重建後之該第一邏輯轉實體表儲存至一記憶體為一第二邏輯轉實體表； 若該可複寫式非揮發性記憶體模組儲存有一或多個第一修剪資訊清單，辨識所述一或多個第一修剪資訊清單中最新的一第二修剪資訊清單，其中所述一或多個第一修剪資訊清單的每一個第一修剪資訊清單記錄一或多筆修剪資訊，其中每一筆修剪資訊記錄一無效資料起始邏輯位址、一無效資料長度值、一修剪資訊頁面順序與一修剪資訊時間戳記，其中所述一或多個第一修剪資訊清單的時間戳記皆大於該第一邏輯轉實體表的時間戳記；以及 根據該第二修剪資訊清單的所有修剪資訊與該第二邏輯轉實體表來更新該第二邏輯轉實體表或更新儲存於該記憶體中的一第三修剪資訊清單。
6. 如申請專利範圍第5項所述的資料恢復方法，更包括： 反應完成更新該第三修剪資訊清單，將更新後之該第三修剪資訊清單儲存至該可複寫式非揮發性記憶體模組的一目標實體位址；以及 將該目標實體位址記錄至該第二邏輯轉實體表的一修剪資訊清單實體位址。
7. 如申請專利範圍第5項所述的資料恢復方法，其中上述根據該第二修剪資訊清單的所有修剪資訊與該第二邏輯轉實體表來更新該第二邏輯轉實體表或更新儲存於該記憶體中的該第三修剪資訊清單的步驟包括： 依據該第二修剪資訊清單所記錄的多個第一修剪資訊的記錄順序來選擇該些第一修剪資訊中的一第二修剪資訊，以對所選擇的該第二修剪資訊執行一解析操作，並且根據所執行的該解析操作的結果來更新該第二邏輯轉實體表或更新該第三修剪資訊清單， 其中該第二修剪資訊為該些第一修剪資訊內尚未被解析之多個修剪資訊中記錄順序最前者。
8. 如申請專利範圍第7項所述的資料恢復方法，其中上述對所選擇的該第二修剪資訊執行該解析操作，並且根據所執行的該解析操作的該結果來更新該第二邏輯轉實體表或更新該第三修剪資訊清單的步驟包括： (1) 根據所選擇的該第二修剪資訊所記錄的一第一無效資料起始邏輯位址與一第一無效資料長度來辨識一第一邏輯位址區段，根據該第二邏輯轉實體表辨識儲存於該第一邏輯位址區段內多個第一邏輯位址的多個第一有效資料，並且選擇該些第一有效資料中尚未被選擇的一第二有效資料以執行步驟(2)，其中該第二修剪資訊指示儲存於該第一邏輯位址區段中的資料為無效的； (2) 比較該第二修剪資訊所記錄的一第一修剪資訊時間戳記與該第二有效資料的一有效資料時間戳記，其中若該第一修剪資訊時間戳記大於該第二有效資料的一有效資料時間戳記，執行步驟(5)，其中該有效資料時間戳記為儲存該第二有效資料的一第一實體單元的時間戳記， 其中若該第二修剪資訊所記錄的該第一修剪資訊時間戳記小於該第二有效資料的該有效資料時間戳記，執行步驟(6)， 其中若該第一修剪資訊時間戳記等於該有效資料時間戳記，執行步驟(3)； (3) 判斷該第二修剪資訊所記錄的一第一修剪資訊頁面順序大於或小於該第二有效資料的一有效資料頁面順序，其中若該第一修剪資訊頁面順序大於該第二有效資料的該有效資料頁面順序，執行步驟(5)，其中該有效資料頁面順序為儲存該第二有效資料的一第一實體頁面於該第一實體單元的所有實體頁面中的順序， 其中若該第一修剪資訊頁面順序小於該有效資料頁面順序，執行步驟(6)； (5) 將該第二有效資料判定為無效，將該第二邏輯轉實體表所記錄的對應該第一邏輯位址的一第一實體位址清空，並且執行步驟(7)； (6) 根據該第一邏輯位址修改該第二修剪資訊，以使該第一邏輯位址區段中不包含該第一邏輯位址，並且執行步驟(7)；以及 (7) 判斷該第一邏輯位址區段中所有的該些第一有效資料是否皆已被選擇以執行步驟(2)， 其中若該些第一有效資料皆已被選擇，完成對所選擇的該第二修剪資訊的該解析操作， 其中若該些第一有效資料並非皆已被選擇，執行步驟(1)。
9. 如申請專利範圍第7項所述的資料恢復方法，其中上述根據該第二修剪資訊清單的所有修剪資訊與該第二邏輯轉實體表來更新該第二邏輯轉實體表或更新儲存於該記憶體中的該第三修剪資訊清單的步驟更包括： 若該第二修剪資訊清單所記錄的該些第一修剪資訊皆完成該解析操作，判定該第二邏輯轉實體表與該第三修剪資訊清單已更新完成。
10. 一種儲存控制器，用於控制配置有一可複寫式非揮發性記憶體模組的一儲存裝置，該儲存控制器包括： 一連接介面電路，用以耦接至配置多個邏輯位址之一主機系統； 一記憶體介面控制電路，用以耦接至該可複寫式非揮發性記憶體模組，其中該可複寫式非揮發性記憶體模組具有多個實體單元，並且該可複寫式非揮發性記憶體模組被配置多個實體位址；以及 一處理器，耦接至該連接介面電路及該記憶體介面控制電路， 其中該處理器用以從該主機系統接收一修剪指令，其中該修剪指令指示儲存於一邏輯位址區段中的無效資料， 其中該處理器更用以根據該修剪指令、該些實體位址中的一目標實體位址來產生一修剪資訊，以根據該修剪資訊更新一第一修剪資訊清單為一第二修剪資訊清單，其中該修剪資訊記錄一無效資料起始邏輯位址、一無效資料長度值、一修剪資訊頁面順序與一修剪資訊時間戳記， 其中該處理器更用以將該第二修剪資訊清單儲存至該目標實體位址，其中該第一或第二修剪資訊清單根據接收對應一或多筆修剪資訊的修剪指令的時間順序來依序記錄所述一或多筆修剪資訊， 其中該處理器更用以將用以儲存該第二修剪資訊清單的該目標實體位址記錄至一第一邏輯轉實體表的一修剪資訊清單實體位址，以更新該第一邏輯轉實體表為一第二邏輯轉實體表， 其中當符合一預設條件，該處理器更用以儲存該第二邏輯轉實體表至該可複寫式非揮發性記憶體模組。
11. 如申請專利範圍第10項所述的儲存控制器， 其中該處理器從該些實體單元中辨識可用的一實體單元為一目標實體單元，並且從該目標實體單元的多個實體頁面中辨識可用的一目標實體頁面，其中該目標實體頁面用以儲存該第二修剪資訊清單，並且該目標實體位址為該目標實體單元的該目標實體頁面的位址， 其中該處理器辨識該目標實體單元的一時間戳記，並且辨識該目標實體頁面於該目標實體單元的所有實體頁面中的順序為一頁面順序， 其中該目標實體單元的該時間戳記用以表示該目標實體單元最早被使用的時間。
12. 如申請專利範圍第11項所述的儲存控制器，其中該修剪指令包括該邏輯位址區段的起始邏輯位址與該邏輯位址區段的區段長度，其中該起始邏輯位址表示該邏輯位址區段的第一個邏輯位址，並且該區段長度表示該邏輯位址區段所包含的所有邏輯位址的總數目，其中在上述該處理器更用以根據該修剪指令、該些實體位址中的該目標實體位址來產生該修剪資訊，以根據該修剪資訊更新該第一修剪資訊清單為該第二修剪資訊清單的運作中， 該處理器根據所接收之該修剪指令，記錄該邏輯位址區段的該起始邏輯位址為該修剪資訊之無效資料起始邏輯位址，並且記錄該邏輯位址區段的該區段長度為該修剪資訊之無效資料長度值， 其中該處理器根據該目標實體位址，記錄對應該目標實體頁面的該頁面順序為該修剪資訊之修剪資訊頁面順序以及記錄該目標實體單元的該時間戳記為該修剪資訊之修剪資訊時間戳記，以產生該修剪資訊， 其中上述根據該修剪資訊更新該第一修剪資訊清單為該第二修剪資訊清單的步驟包括將所產生的該修剪資訊附加至被維護於一記憶體中的該第一修剪資訊清單的其他修剪資訊之後，以更新該第一修剪資訊清單為該第二修剪資訊清單。
13. 如申請專利範圍第12項所述的儲存控制器，其中在上述當符合該預設條件，該處理器更用以儲存該第二邏輯轉實體表至該可複寫式非揮發性記憶體模組的運作中， 當符合該預設條件，該處理器根據該第二修剪資訊清單的所有修剪資訊來更新該第二邏輯轉實體表，將該第二邏輯轉實體表的該修剪資訊清單實體位址清空，並且將該第二邏輯轉實體表儲存至該可複寫式非揮發性記憶體模組， 反應於完成將更新後之該第二邏輯轉實體表儲存至該可複寫式非揮發性記憶體模組，該處理器清空維護於該記憶體中的該第二修剪資訊清單所記錄的所有修剪資訊。
14. 一種儲存控制器，用於控制配置有一可複寫式非揮發性記憶體模組的一儲存裝置，該儲存控制器包括： 一連接介面電路，用以耦接至配置多個邏輯位址之一主機系統； 一記憶體介面控制電路，用以耦接至該可複寫式非揮發性記憶體模組，其中該可複寫式非揮發性記憶體模組具有多個實體單元，並且該可複寫式非揮發性記憶體模組被配置多個實體位址；以及 一處理器，耦接至該連接介面電路及該記憶體介面控制電路， 其中該處理器用以根據儲存在該可複寫式非揮發性記憶體模組的一第一邏輯轉實體表與該可複寫式非揮發性記憶體模組中時間戳記大於該第一邏輯轉實體表的時間戳記的所有有效資料的實體位址與對應的邏輯位址來重建該第一邏輯轉實體表，並且將重建後之該第一邏輯轉實體表儲存至一記憶體為一第二邏輯轉實體表， 其中若該可複寫式非揮發性記憶體模組儲存有一或多個第一修剪資訊清單，該處理器更用以辨識所述一或多個第一修剪資訊清單中最新的一第二修剪資訊清單，其中所述一或多個第一修剪資訊清單的每一個第一修剪資訊清單記錄一或多筆修剪資訊，其中每一筆修剪資訊記錄一無效資料起始邏輯位址、一無效資料長度值、一修剪資訊頁面順序與一修剪資訊時間戳記，其中所述一或多個第一修剪資訊清單的時間戳記皆大於該第一邏輯轉實體表的時間戳記， 其中該處理器更用以根據該第二修剪資訊清單的所有修剪資訊與該第二邏輯轉實體表來更新該第二邏輯轉實體表或更新儲存於該記憶體中的一第三修剪資訊清單。
15. 如申請專利範圍第14項所述的儲存控制器， 其中反應完成更新該第三修剪資訊清單，該處理器將更新後之該第三修剪資訊清單儲存至該可複寫式非揮發性記憶體模組的一目標實體位址， 其中該處理器將該目標實體位址記錄至該第二邏輯轉實體表的一修剪資訊清單實體位址。
16. 如申請專利範圍第14項所述的儲存控制器，其中在上述該處理器更用以根據該第二修剪資訊清單的所有修剪資訊與該第二邏輯轉實體表來更新該第二邏輯轉實體表或更新儲存於該記憶體中的該第三修剪資訊清單的運作中， 該處理器依據該第二修剪資訊清單所記錄的多個第一修剪資訊的記錄順序來選擇該些第一修剪資訊中的一第二修剪資訊，以對所選擇的該第二修剪資訊執行一解析操作，並且根據所執行的該解析操作的結果來更新該第二邏輯轉實體表或更新該第三修剪資訊清單， 其中該第二修剪資訊為該些第一修剪資訊內尚未被解析之多個修剪資訊中記錄順序最前者。
17. 如申請專利範圍第16項所述的儲存控制器，其中上述對所選擇的該第二修剪資訊執行該解析操作，並且根據所執行的該解析操作的該結果來更新該第二邏輯轉實體表或更新該第三修剪資訊清單的運作包括： (1) 該處理器根據所選擇的該第二修剪資訊所記錄的一第一無效資料起始邏輯位址與一第一無效資料長度來辨識一第一邏輯位址區段，根據該第二邏輯轉實體表辨識儲存於該第一邏輯位址區段內多個第一邏輯位址的多個第一有效資料，並且選擇該些第一有效資料中尚未被選擇的一第二有效資料以執行步驟(2)，其中該第二修剪資訊指示儲存於該第一邏輯位址區段中的資料為無效的； (2) 該處理器比較該第二修剪資訊所記錄的一第一修剪資訊時間戳記與該第二有效資料的一有效資料時間戳記，其中若該第一修剪資訊時間戳記大於該第二有效資料的一有效資料時間戳記，執行步驟(5)，其中該有效資料時間戳記為儲存該第二有效資料的一第一實體單元的時間戳記， 其中若該第二修剪資訊所記錄的該第一修剪資訊時間戳記小於該第二有效資料的該有效資料時間戳記，執行步驟(6)， 其中若該第一修剪資訊時間戳記等於該有效資料時間戳記，執行步驟(3)； (3) 該處理器判斷該第二修剪資訊所記錄的一第一修剪資訊頁面順序大於或小於該第二有效資料的一有效資料頁面順序，其中若該第一修剪資訊頁面順序大於該第二有效資料的該有效資料頁面順序，執行步驟(5)，其中該有效資料頁面順序為儲存該第二有效資料的一第一實體頁面於該第一實體單元的所有實體頁面中的順序， 其中若該第一修剪資訊頁面順序小於該有效資料頁面順序，執行步驟(6)； (5) 該處理器將該第二有效資料判定為無效，將該第二邏輯轉實體表所記錄的對應該第一邏輯位址的一第一實體位址清空，並且執行步驟(7)； (6) 該處理器根據該第一邏輯位址修改該第二修剪資訊，以使該第一邏輯位址區段中不包含該第一邏輯位址，並且執行步驟(7)；以及 (7) 該處理器判斷該第一邏輯位址區段中所有的該些第一有效資料是否皆已被選擇以執行步驟(2)， 其中若該些第一有效資料皆已被選擇，完成對所選擇的該第二修剪資訊的該解析操作， 其中若該些第一有效資料並非皆已被選擇，執行步驟(1)。
18. 如申請專利範圍第16項所述的儲存控制器，其中在上述該處理器更用以根據該第二修剪資訊清單的所有修剪資訊與該第二邏輯轉實體表來更新該第二邏輯轉實體表或更新儲存於該記憶體中的該第三修剪資訊清單的運作中， 若該第二修剪資訊清單所記錄的該些第一修剪資訊皆完成該解析操作，該處理器判定該第二邏輯轉實體表與該第三修剪資訊清單已更新完成。