TWI603193B - 資料儲存裝置及其資料維護方法 - Google Patents

Description

資料儲存裝置及其資料維護方法

本發明係關於一種資料儲存裝置之資料維護方法；特別係關於一種三階儲存單元的資料維護方法。

快閃記憶體為一種普遍的非揮發性資料儲存媒體，係以電性方式抹除與程式化。以非及閘型的快閃記憶體(即NAND FLASH)為例，常用作記憶卡(memory card)、通用序列匯流排閃存裝置(USB flash device)、固態硬碟(SSD)、嵌入式快閃記憶體模組(eMMC)…等之儲存媒體。

快閃記憶體(如，NAND FLASH)的儲存陣列包括複數個區塊(blocks)，其中浮置閘極電晶體可用以構成快閃記憶體。浮置閘極電晶體中之浮置閘極，可捕捉的電荷以儲存資料。然而，儲存於浮置閘極之電荷會由於快閃記憶體之操作以及各種環境參數，自浮置閘極流失，造成資料保存(Data retention)之問題。其中，三階儲存單元(Triple-Level Cell，TLC)之快閃記憶體相較於其他快閃記憶體的寫入程序更為繁複。因此，如何有效地並且穩定的進行寫入程序是重要的課題。

本發明所提供之資料儲存裝置以及資料維護方法，可穩定的提供三階備用區塊並且同時將資料寫入單階備用 區塊。

本發明提供一種資料儲存裝置。資料儲存裝置包括一快閃記憶體以及一控制器。快閃記憶體具有複數單階備用區塊、複數單階資料區塊、複數三階備用區塊以及複數三階資料區塊。控制器響應於用以將一資料寫入快閃記憶體之一寫入命令，將資料寫入單階備用區塊。當一第一既定條件滿足時，控制器自三階資料區塊中選取具有最少有效資料之複數第一三階資料區塊，將第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊，並且釋放第一三階資料區塊，以將三階備用區塊之總數增加一。

在一實施例中，第一三階資料區塊中之無效資料的資料量等於一個三階資料區塊或者一個三階備用區塊的資料量。當第一既定條件滿足時，控制器更用以在選取第一三階資料區塊之前，將資料中之一第一部分寫入單階備用儲存區塊中之一第一單階備用儲存區塊。另外，當第一既定條件滿足時，控制器更用以在釋放第一三階資料區塊後，才將所寫入之資料的至少一邏輯位址映射至所寫入之第一單階備用區塊並將映射至邏輯位址之單階備用區塊定義為單階資料區塊。在又一實施例中，控制器係在資料中之第一部分以外之其他部分被寫入單階備用儲存區塊之其他者之前，執行選取第一三階資料區塊，將第一三階資料區塊中之有效資料寫入第一三階備用區塊以及釋放第一三階資料區塊的步驟。

另外，第一既定條件為三階備用區塊之數量小於一第一既定值。當第一既定條件未被滿足時，控制器連續將資 料寫入單階備用區塊中。單階備用區塊係為不具有有效資料之單階區塊，單階資料區塊為具有有效資料之單階區塊，三階備用區塊為不具有有效資料之三階區塊，並且三階資料區塊為具有有效資料之三階區塊。

本發明亦提供一種資料儲存裝置。資料儲存裝置包括一快閃記憶體以及一控制器。快閃記憶體具有複數單階備用區塊、複數單階資料區塊、複數三階備用區塊以及複數三階資料區塊。控制器響應於用以將一資料寫入快閃記憶體之一寫入命令，將資料寫入單階備用區塊。當一第一既定條件滿足時，控制器每寫入一個單階備用區塊便整理三階資料區塊中之複數第一三階資料區塊以將三階備用區塊之總數增加一。

在一實施例中，第一三階資料區塊中之無效資料的資料量等於一個三階資料區塊或者一個三階備用區塊的資料量。為了將三階備用區塊之總數增加一，控制器自三階資料區塊中選取具有最少有效資料之複數第一三階資料區塊，將第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊，並且釋放第一三階資料區塊。當第一既定條件滿足時，控制器更用以在釋放第一三階資料區塊後，才將所寫入之資料的至少一邏輯位址映射至所寫入之第一單階備用區塊並將映射至邏輯位址之單階備用區塊定義為單階資料區塊。

本發明又提供一種資料維護方法適用於具有一快閃記憶體之資料儲存裝置，其中快閃記憶體具有複數單階備用區塊、複數單階資料區塊、複數三階備用區塊以及複數三階資料區塊。資料維護方法包括：接收用以將一資料寫入快閃記憶 體之一寫入命令；以及響應於寫入命令，將資料寫入單階備用區塊。當一第一既定條件滿足時將資料寫入單階備用區塊之步驟更包括：自三階資料區塊中選取具有最少有效資料之複數第一三階資料區塊；將第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊；以及釋放第一三階資料區塊，以將三階備用區塊之總數增加一。

在一實施例中，第一三階資料區塊中之無效資料的資料量等於一個三階資料區塊或者一個三階備用區塊的資料量。當一第一既定條件滿足時將資料寫入單階備用區塊之步驟更包括：在選取第一三階資料區塊之前，將資料中之一第一部分寫入單階備用儲存區塊中之一第一單階備用儲存區塊。當一第一既定條件滿足時將資料寫入單階備用區塊之步驟更包括：在釋放第一三階資料區塊後，才將所寫入之資料的至少一邏輯位址映射至所寫入之第一單階備用區塊並將映射至邏輯位址之單階備用區塊定義為單階資料區塊。

又一實施例中，選取第一三階資料區塊，將第一三階資料區塊中之有效資料寫入第一三階備用區塊以及釋放第一三階資料區塊的步驟係在資料中之第一部分以外之其他部分被寫入單階備用儲存區塊之其他者之前執行的。

本發明亦提供一種資料維護方法適用於具有一快閃記憶體之資料儲存裝置，其中快閃記憶體具有複數單階備用區塊、複數單階資料區塊、複數三階備用區塊以及複數三階資料區塊。資料維護方法包括：接收用以將一資料寫入快閃記憶體之一寫入命令；以及響應於寫入命令，將資料寫入單階備用 區塊。當一第一既定條件滿足時將資料寫入單階備用區塊之步驟更包括：每寫入一個單階備用區塊便整理三階資料區塊中之複數第一三階資料區塊以將三階備用區塊之總數增加一。

在一實施例中，第一三階資料區塊中之無效資料的資料量等於一個三階資料區塊或者一個三階備用區塊的資料量。為了將三階備用區塊之總數增加一，當第一既定條件滿足時將資料寫入單階備用區塊之步驟更包括：自三階資料區塊中選取具有最少有效資料之複數第一三階資料區塊；將第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊；以及釋放第一三階資料區塊。當第一既定條件滿足時將資料寫入單階備用區塊之步驟更包括：在釋放第一三階資料區塊後，才將所寫入之資料的至少一邏輯位址映射至所寫入之第一單階備用區塊並將映射至邏輯位址之單階備用區塊定義為單階資料區塊。

100‧‧‧電子系統

120‧‧‧主機

140‧‧‧資料儲存裝置

160‧‧‧控制器

162‧‧‧運算單元

164‧‧‧永久記憶體

166‧‧‧隨機存取記憶體

180‧‧‧快閃記憶體

SLC_SP_POOL‧‧‧單階備用池

TLC_SP_POOL‧‧‧三階備用池

SLC_DA_POOL‧‧‧單階資料池

TLC_DA_POOL‧‧‧三階資料池

SLC_SP_1~SLC_SP_N‧‧‧單階備用區塊

SLC_DA_1~SLC_DA_P‧‧‧單階資料區塊

TLC_SP_1~TLC_SP_M‧‧‧三階備用區塊

TLC_DA_1~TLC_DA_Q‧‧‧三階資料區塊

S300~S332、S400~S432‧‧‧步驟

第1圖係本發明之一種實施例之電子系統之方塊圖。

第2圖係本發明之一種實施例之快閃記憶體之示意圖。

第3A~3B圖係本發明之一種實施例之資料維護方法之流程圖。

第4A~4B圖係本發明之另一種實施例之資料維護方法之流程圖。

以下將詳細討論本發明各種實施例之裝置及使用 方法。然而值得注意的是，本發明所提供之許多可行的發明概念可實施在各種特定範圍中。這些特定實施例僅用於舉例說明本發明之裝置及使用方法，但非用於限定本發明之範圍。

第1圖為本發明所提供之一電子系統之一種實施例的方塊圖。電子系統100包括一主機120以及一資料儲存裝置140。資料儲存裝置140包括一快閃記憶體180以及一控制器160，且可根據主機110所下達的命令操作。控制器160包括一運算單元162、一永久記憶體(如，唯讀記憶體ROM)164以及隨機存取記憶體(RAM)166。永久記憶體164與所載之程式碼、資料組成韌體(firmware)，由運算單元162執行，使控制器160基於該韌體控制該快閃記憶體180。隨機存取記憶體(RAM)166用以載入程式碼與參數以提供控制器160根據所載入的程式碼與參數動作。快閃記憶體180具有複數區塊，其中每一區塊具有複數頁面，其中快閃記憶體180係以頁面為最小單位進行寫入，並且以區塊為最小單位進行抹除。值得注意的是，在一實施例中，快閃記憶體180為固態硬碟(SSD)。

第2圖係本發明之一種實施例之快閃記憶體之示意圖。如第2圖所示，快閃記憶體180具有一單階備用池SLC_SP_POOL、一三階備用池TLC_SP_POOL、一單階資料池SLC_DA_POOL以及一三階資料池TLC_DA_POOL。單階備用池SLC_SP_POOL包括複數單階備用區塊(Single-Level Cell，SLC)SLC_SP_1~SLC_SP_N，其中N為單階備用池SLC_SP_POOL中單階備用區塊的數量，並且每一單階備用區塊SLC_SP_1~SLC_SP_N的大小等同於一個區塊的大小，但本發 明不限於此。換言之，單階備用區塊SLC_SP_1~SLC_SP_N係為不具有有效資料之單階區塊，並且單階備用區塊SLC_SP_1~SLC_SP_N係用以以單階儲存模式寫入資料的區塊。值得注意的是，單階備用池SLC_SP_POOL中之單階備用區塊SLC_SP_1~SLC_SP_N被寫入有效資料後，則會被定義為單階資料區塊並且被分配到推到(PUSH)單階資料池SLC_DA_POOL中。單階資料池SLC_DA_POOL包括複數單階資料區塊(Single-Level Cell，SLC)SLC_DA_1~SLC_DA_P，其中P為單階資料池SLC_DA_POOL中之單階資料區塊的數量，並且每一單階資料區塊SLC_DA_1~SLC_DA_P的大小等同於一個區塊的大小，但本發明不限於此。換言之，單階資料區塊SLC_DA_1~SLC_DA_P係為具有有效資料之單階區塊，並且單階資料區塊SLC_DA_1~SLC_DA_P中之有效資料係用以以三階儲存模式寫入三階備用區塊資料的區塊。值得注意的是，單階資料池SLC_DA_POOL中之單階資料區塊SLC_DA_1~SLC_DA_P中之有效資料被整理至三階備用區塊後，則會被定義為單階備用區塊並且被分配到推到(PUSH)單階備用池SLC_SO_POOL中。三階備用池TLC_SP_POOL包括複數三階備用區塊(Triple-Level Cell，TLC)TLC_SP_0~TLC_SP_M，其中M為三階備用池TLC_SP_POOL中三階備用區塊TLC_SP_0~TLC_SP_M的數量，並且每一三階備用區塊TLC_SP_0~TLC_SP_M的大小等同於一個區塊的大小。換言之，三階備用區塊TLC_SP_0~TLC_SP_M是不具有有效資料之三階區塊，並且三階備用區塊TLC_SP_0~TLC_SP_M係用 以以三階儲存模式寫入資料的區塊。詳細而言，三階備用區塊TLC_SP_0~TLC_SP_M被寫入的資料為原本儲存於單階資料區塊的資料。值得注意的是，已被寫入有效資料之三階備用區塊TLC_SP_0~TLC_SP_M會被定義為三階資料區塊並且被推至三階資料池TLC_DA_POOL中。三階資料池TLC_DA_POOL包括複數三階資料區塊(Triple-Level Cell，SLC)TLC_DA_1~TLC_DA_Q，其中Q為三階資料池TLC_DA_POOL中之三階資料區塊的數量，並且每一三階資料區塊TLC_DA_1~TLC_DA_P的大小等同於一個區塊的大小，但本發明不限於此。換言之，三階資料區塊TLC_DA_1~TLC_DA_Q係為具有有效資料之三階區塊，並且三階資料區塊TLC_DA_1~TLC_DA_Q。值得注意的是，三階資料池TLC_DA_POOL中之三階資料區塊TLC_DA_1~TLC_DA_Q被中之有效資料被無效後，則會被定義為三階備用區塊並且被分配到推到(PUSH)三階備用池TLC_SP_POOL中。

值得注意的是，當沒有任何資料被寫入快閃記憶體180時，三階資料池TLC_DA_POOL以及單階資料池SLC_DA_POOL中不具有任何三階資料區塊以及單階資料區塊。

另外，三階區塊(三階資料區塊TLC_DA_1~TLC_DA_Q以及三階備用區塊TLC_SP_1~TLC_SP_M)可儲存之資料量是單階區塊(單階資料區塊SLC_DA_1~SLC_DA_P以及單階備用區塊SLC_SP_1~SLC_SP_N)的三倍。詳細而言，三階區塊以及單階 區塊皆是快閃記憶體180中之區塊，其物理構造是相同的。然而，三階區塊是藉由電壓對區塊進行多次整理(Program)來寫入資料，而單階區塊是藉由電壓對區塊進行一次整理(Program)來寫入資料。在一實施例中，三階區塊是藉由電壓對區塊進行三次整理(Program)來寫入資料。換言之，三個具有有效資料之單階資料區塊可整理為一個三階資料區塊。

由於單階區塊相較於三階區塊較為穩定，因此在本發明之實施例中，單階區塊(SLC)是用來作為預取空間(Cache)，並且在單階區塊快被使用完時，才開始將單階資料區塊的資料整理至三階區塊中。一次將大量之單階資料區塊的資料轉移到三階區塊，雖然可確保清出大量的單階備用區塊可使用。然而，控制器160卻會因為一次性大量的整理工作無法對寫入資料繼續進行處理，而造成寫入效能不穩定。

因此，在本發明之一實施例中，控制器160可基於單階區塊以及三階區塊的特性，交替地執行寫入以及清除操作，以確保快閃記憶體180可穩定地提供可用的單階備用區塊也可以穩定地進行寫入工作。

詳細而言，當控制器160自主機120接收到用以將一資料寫入快閃記憶體180之一寫入命令時，控制器則響應於寫入命令將資料寫入單階備用區塊。另外，每當對等單階備用區塊中之一者進行寫入前，控制器160判斷單階備用區塊SLC_SP_1~SLC_SP_N之數量是否小於一第二既定值，以判斷一第二既定條件是否被滿足。當單階備用區塊SLC_SP_1~SLC_SP_N之數量小於第二既定值時，既定條件被 滿足。當第二既定條件被滿足時，控制器160則開始進行清除單階資料區塊SLC_DA_1~SLC_DA_P。換言之，當第二既定條件被滿足時，控制器160每寫入三個單階備用區塊便將單階資料區塊SLC_DA_1~SLC_DA_P中存在最久之三者整理至三階備用區塊TLC_SP_1~TLC_SP_M中之一者。值得注意的是，在一實施例中，資料儲存裝置140具有一區塊維護表，用以紀錄在單階資料池SLC_DA_POOL中之每一單階資料區塊SLC_DA_1~SLC_DA_P中之有效資料存在的時間，但本發明不限於此。在其他實施例中，資料儲存裝置140可藉由其他方式記錄每一單階資料區塊SLC_DA_1~SLC_DA_P中之有效資料存在的時間。另外，當第二既定條件未滿足時，控制器160則接著連續將資料寫入單階備用區塊中，並且在對每個單階備用區塊進行寫入前判斷是否滿足第二既定條件。在其他實施例中，第二既定條件可包括任何需要清理單階資料區塊之事件。

在一實施例中，控制器160係在將單階資料區塊中存在最久之三者整理至三階備用區塊TLC_SP_1~TLC_SP_M中之一者後，才將所寫入之資料的至少一邏輯位址映射至所寫入之單階備用區塊並將映射至邏輯位址之單階備用區塊定義為單階資料區塊。在突發的斷電事件或者其他中斷事件發生時，資料雖然已被寫入三階備用區塊中，但資料的鏈結還是保存在原本的單階資料區塊。因此，資料可保存在較穩定的單階區塊中。

舉例而言，當第二既定條件滿足時，控制器160先將資料中之一第一部分寫入單階備用儲存區塊 SLC_SP_1~SLC_SP_N中之三個第一單階備用儲存區塊。接著，在將資料中之其他部分寫入單階備用儲存區塊SLC_SP_1~SLC_SP_N之其他者之前，控制器160自單階資料區塊SLC_DA_1~SLC_DA_P中選擇所具有之有效資料存在最久之三個第一單階資料區塊，並且將第一單階資料區塊中之資料整理至三階備用區塊中之一者以釋放第一單階資料區塊，其中被釋放的第一單階資料區塊已失去與原資料的位址映射關係，並且被定義為單階備用區塊。接著，在第一單階資料區塊被釋放後，控制器160將第一部分之至少一邏輯位址映射至第一單階備用區塊，並將第一單階備用區塊定義為單階資料區塊中之三者。

在第一單階備用區塊被定義為單階資料區塊中之三者後，控制器160接著先將資料中之一第二部分寫入單階備用儲存區塊中之三個第二單階備用儲存區塊。在將資料中之其他部分寫入單階備用儲存區塊之其他者之前，控制器160自單階資料區塊中選擇所具有之有效資料存在最久之三個第二單階資料區塊，將第二單階資料區塊中之資料整理至三階備用區塊中之一者以釋放第二單階資料區塊，其中被釋放的第二單階資料區塊已失去與原資料的位址映射關係，並且被定義為單階備用區塊。接著，在第二單階資料區塊被釋放後，控制器160將第二部分之至少一邏輯位址映射至第二單階備用區塊，並將第二單階備用區塊定義為單階資料區塊中之三者。接著，控制器160重複上述步驟直到資料之所有部分皆被寫入單階備用區塊中。另外，上述資料之第一部分以及第二部分的資料量，分 別等於三個單階區塊的資料量。

另外，當三階區塊塊被使用完時，控制器160會開始整理三階區塊中之資料以釋出可用之三階區塊(Garbage collection)。在一實施例中，控制器160是根據固定之一預設整合比例(clean ratio/move write ratio)對三階資料區塊進行整合，其中預設整合比例是基於最差的狀況所決定的。舉例而言，若快閃記憶體180中具有100個三階區塊，可用之容量有99個三階區塊。最差的狀況是每個三階區塊具有99%之有效資料以及1%之無效資料。在最差的情況中，快閃記憶體180需要從100個三階區塊中蒐集無效資料才可釋出一個可用之三階區塊(三階備用區塊)。換言之，控制器160則需要在下一個單階備用區塊被寫滿前，對三階資料區塊中之資料進行99次的整理，才可釋出一可用之三階備用區塊。因此，基於上述的最差狀況，快閃記憶體180固定的預設整合比例即為100。換言之，每當三階備用區塊的數量低於一第一既定值時，控制器160則會在下一個單階備用區塊被寫滿前，對三階資料區塊中之資料進行99次的整理，以釋放出至少一個可用之三階備用區塊。詳細而言，控制器160每次需要對三階資料區塊進行整理時，皆是自三階資料區塊中選取100個三階資料區塊以進行99次的資料整理，以釋放出至少一個可用之三階備用區塊。因此，控制器160也會因為一次性大量的整理工作無法對寫入資料繼續進行處理，而造成寫入效能不穩定。

因此，在本發明之另一實施例中，控制器160可根據目前三階資料區塊TLC_DA1~TLC_DAQ中無效資料的數 量，動態地決定每一次整合之整合比例，以在下一個單階備用區塊被寫滿前固定釋出一個可用之三階備用區塊。值得注意的是，在一實施例中，資料儲存裝置140具有一資料維護表，用以紀錄在三階資料池TLC_DA_POOL中之每一三階資料區塊TLC_DA_1~TLC_DA_Q中所具有之有效資料的資料量，但本發明不限於此。在其他實施例中，資料儲存裝置140可藉由其他方式記錄每一三階資料區塊TLC_DA_1~TLC_DA_Q中所具有之有效資料的資料量。

詳細而言，在接收到用以將一資料寫入快閃記憶體180之一寫入命令後，控制器160響應於所接收之寫入命令，將資料寫入單階備用區塊SLC_SP1~SLC_SP_N。另外，每當對等單階備用區塊中之一者進行寫入前，控制器160判斷三階備用區塊TLC_SP_1~TLC_SP_M之數量是否小於一第一既定值，以判斷一第一既定條件是否被滿足。當三階備用區塊TLC_SP_1~TLC_SP_M之數量小於第一既定值時，第一既定條件被滿足。當第一既定條件被滿足時，控制器160則開始進行整合三階資料區塊TLC_DA_1~TLC_DA_Q。換言之，當第一既定條件滿足時，控制器160每寫入一個單階備用區塊便整理三階資料區塊TLC_DA1~TLC_DA_Q中之複數第一三階資料區塊，以將三階備用區塊之總數增加一。值得注意的是，為了將三階備用區塊之總數增加一，第一三階資料區塊中之無效資料的資料量需要大於等於一個三階資料區塊或者一個三階備用區塊的資料量。換言之，為了將三階備用區塊之總數增加一，控制器160係自三階資料區塊TLC_DA1~TLC_DA_Q中選取具 有最少有效資料並且所具有之無效資料量大於等於一個三階區塊之資料量的複數個第一三階資料區塊，將第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊，並且釋放第一三階資料區塊。另外，當第一既定條件未被滿足時，控制器160則連續地將資料寫入單階備用區塊SLC_SP1~SLC_SP_N中。在其他實施例中，既定條件可包括任何需要整合三階資料區塊TLC_DA1~TLC_DA_Q之事件。

另外，在一實施例中，控制器160系在釋放第一三階資料區塊後，才將所寫入之資料的至少一邏輯位址映射至所寫入之第一單階備用區塊並將映射至邏輯位址之單階備用區塊定義為單階資料區塊。在突發的斷電事件或者其他中斷事件發生時，資料雖然已被寫入第一單階備用區塊中，但資料的鏈結還沒映射至所寫入的單階備用區塊。換言之，在突發的斷電事件或者其他中斷事件發生時，資料雖然已被寫入第一單階備用區塊中，但對於主機120以及控制器160而言資料還不算被寫入快閃記憶體180中。因此，在斷電事件或者其他中斷事件後，控制器160會重新寫入資料，以確保資料的完整性。

舉例而言，在對一單階備用區塊進行寫入前，控制器160判斷第一既定條件是否滿足。當第一既定條件滿足時，控制器160先將資料中之一第一部分寫入單階備用儲存區塊中之一第一單階備用儲存區塊。接著，在資料中之第一部分以外之其他部分被寫入單階備用儲存區塊之其他者之前，控制器160自三階資料區塊TLC_DA1~TLC_DA_Q中選取具有最少有效資料並且所具有之無效資料量大於等於一個三階區塊之 資料量的複數個第一三階資料區塊，將第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊，並且釋放第一三階資料區塊，以將三階備用區塊之總數增加一，其中原第一三階資料區塊中之有效資料的邏輯位址會映射至所寫入之第一三階備用區塊，具有資料鏈結之第一三階備用區塊會被定義為三階資料區塊，原第一三階資料區塊會喪失與有效資料的邏輯位址的連結，並且失去資料鏈結之第一三階資料區塊會被定義為新的三階備用區塊。最後，在釋放第一三階資料區塊後，控制器160才將所寫入之資料的至少一邏輯位址映射至所寫入之第一單階備用區塊並將映射至邏輯位址之單階備用區塊定義為單階資料區塊。若第一既定條件沒有滿足時，控制器160則直接將資料中之第一部分寫入第一單階備用儲存區塊，並且將所寫入之資料的至少一邏輯位址映射至所寫入之第一單階備用區塊並將映射至邏輯位址之單階備用區塊定義為單階資料區塊。接著，控制器160重複上述動作，直到所有資料皆被寫入快閃記憶體180中。

值得注意的是，第一既定值以及第二既定值可由開發者，依照不同快閃記憶體180之需求自行決定，其中第一既定值以及第二既定值皆是大於零之正整數。

舉例而言，假設第一既定值為5，並且第二既定值為10。控制器160響應於寫入命令將資料寫入單階備用池SLC_SP_POOL中之單階備用區塊中，直到單階備用池SLC_SP_POOL僅剩餘9個單階備用區塊SLC_SP_1~SLC_SP_9。控制器160開始每寫三個單階備用區 塊，便將三個單階資料區塊中之資料整理至三階備用池TLC_SP_POOL中之一個三階備用區塊，以將單階備用池SLC_SP_POOL中之單階備用區塊的數量維持在9個。被寫入有效資料之三階備用區塊依序被推入三階資料池TLC_SP_POOL中成為三階資料區塊，直到三階備用池TLC_SP_POOL中僅剩下4個三階備用區塊TLC_SP_1~TLC_SP_4。控制器160則在將資料中之一部分寫入一個單階備用區塊後，整合三階資料池TLC_DA_POOL中之三階資料區塊，以將三階備用區塊之總數加一。接著，三階備用池TLC_SP_POOL中之三階備用區塊增加至5個。接著，控制器160繼續每寫三個單階備用區塊，便將三個單階資料區塊中之資料整理至三階備用池TLC_SP_POOL中之一個三階備用區塊。依此類推，直到所有資料都寫入快閃記憶體180中為止。

舉例而言，三階備用池TLC_SP_POOL中僅剩下4個三階備用區塊TLC_SP_1~TLC_SP_4，三階資料池TLC_DA_POOL包括具有1/3無效資料之八個三階資料區塊TLC_DA_1~TLC_DA_8、具有1/6無效資料之十六個三階資料區塊TLC_DA_9~TLC_DA_24、具有1/10無效資料之十個三階資料區塊TLC_DA_25~TLC_DA_34。在本實施例中，控制器160會在將資料中之一部分寫入一個單階備用區塊後，自三階資料池TLC_DA_POOL中選擇3個具有1/3無效資料之三階資料區塊，例如三階資料區塊TLC_DA_1~TLC_DA_3。接著，控制器160會選擇兩個三階備用區塊TLC_SP_1~TLC_SP_2，以將三階資料區塊TLC_DA_1~TLC_DA_3中6/3的有效資料寫入三 階備用區塊TLC_SP_1~TLC_SP_2中。因此，三階備用區塊TLC_SP_1~TLC_SP_2被推至三階資料池TLC_DA_POOL並且被定義為三階資料區塊，原本之三階資料區塊TLC_DA_1~TLC_DA_3則被推至三階備用池TLC_SP_POOL並且被定義為三階備用區塊。三階備用池TLC_SP_POOL增加了三個區塊並且減少了兩個區塊，故三階備用池TLC_SP_POOL中三階備用區塊的總數增加一。

又舉例而言，三階備用池TLC_SP_POOL中僅剩下4個三階備用區塊TLC_SP_1~TLC_SP_4，三階資料池TLC_DA_POOL包括具有1/2無效資料之八個三階資料區塊TLC_DA_1~TLC_DA_8、具有1/3無效資料之十六個三階資料區塊TLC_DA_9~TLC_DA_24、具有1/7無效資料之十個三階資料區塊TLC_DA_25~TLC_DA_34。在本實施例中，控制器160會在將資料中之一部分寫入一個單階備用區塊後，自三階資料池TLC_DA_POOL中選擇2個具有1/2無效資料之三階資料區塊，例如三階資料區塊TLC_DA_1~TLC_DA_2。接著，控制器160會選擇一個三階備用區塊TLC_SP_1，以將三階資料區塊TLC_DA_1~TLC_DA_2中2/2的有效資料寫入三階備用區塊TLC_SP_1中。因此，三階備用區塊TLC_SP_1被推至三階資料池TLC_DA_POOL並且被定義為三階資料區塊，原本之三階資料區塊TLC_DA_1~TLC_DA_2則被推至三階備用池TLC_SP_POOL並且被定義為三階備用區塊。三階備用池TLC_SP_POOL增加了兩個區塊並且減少了一個區塊，故三階備用池TLC_SP_POOL中三階備用區塊的總數增加一。

值得注意的是，在三階資料區塊TLC_DA_Z~TLC_DA_Q中之無效資料是由控制器160對資料的重複寫入或者刪除所造成的。舉例而言，當控制器160對同一個特定邏輯位址重複進行寫入時，控制器160會將資料寫入新的區塊並且特定邏輯位址與原區塊中之頁面的鏈結斷開以連結至新的區塊中的葉面。因此，原本被映射至特定邏輯位址之舊區塊中的至少一頁面則成了無效資料。

第3A~3B圖係本發明之一種實施例之資料維護方法之流程圖。資料維護方法適用於第1圖所示之資料儲存裝置140。流程開始於步驟S300。

在步驟S300中，控制器160自主機120接收到用以將一資料寫入快閃記憶體180之一寫入命令。在本實施例中，資料大於三個單階區塊的資料量，但本發明不限於此。在本實施例中，控制器160可根據目前三階資料區塊TLC_DA1~TLC_DAQ中無效資料的數量，動態地決定每一次整合之整合比例，以在下一個單階備用區塊被寫滿前固定釋出一個可用之三階備用區塊。

接著，在步驟S302中，控制器160判斷一第一既定條件是否滿足。在一實施例中，控制器160判斷三階備用區塊TLC_SP_1~TLC_SP_M之數量是否小於一第一既定值，以判斷一第一既定條件是否被滿足。當三階備用區塊TLC_SP_1~TLC_SP_M之數量小於第一既定值時，第一既定條件被滿足。詳細而言，當第一既定條件被滿足時，流程進行至步驟S304以開始進行整合三階單階資料區塊 TLC_DA_1~TLC_DA_Q的操作。當既定條件未被滿足時，流程進行至步驟S314。在其他實施例中，既定條件可包括任何需要整合三階資料區塊之事件。

在步驟S304中，控制器160擷取資料中尚未被寫入單階備用區塊之一部分。詳細而言，控制器160接續著前一次所擷取的資料的部分，擷取資料中尚未被寫入單階備用區塊並且等同於一個單階區塊之資料量的一部分。當所剩餘之資料小於一個單階區塊時，控制器160則擷取所有剩餘之資料。

接著，在步驟S306中，控制器160將所擷取之資料的部分寫入單階備用儲存區塊SLC_SP_1~SLC_SP_N中之一個單階備用儲存區塊。換言之，控制器160將在步驟S304中所擷取之資料的部分寫入單階備用儲存區塊SLC_SP_1~SLC_SP_N中之一者。

接著，在步驟S308中，控制器160自三階資料區塊TLC_DA1~TLC_DA_Q中選取具有最少有效資料並且所具有之無效資料量大於等於一個三階區塊之資料量的複數個三階資料區塊。

接著，在步驟S310中，控制器160將所選取之三階資料區塊中之資料整理至至少一三階備用區塊，並且釋放所選取之三階資料區塊，以將三階備用區塊之總數增加一，其中原三階資料區塊中之有效資料的邏輯位址會映射至所寫入之三階備用區塊，具有資料鏈結之三階備用區塊會被定義為三階資料區塊，原三階資料區塊會喪失與有效資料的邏輯位址的連結，並且失去資料鏈結之三階資料區塊會被定義為新的三階備 用區塊。

接著，在步驟S312中，控制器160將所寫入之資料的至少一邏輯位址映射至所寫入之單階備用區塊並將映射至邏輯位址之單階備用區塊定義為單階資料區塊。換言之，控制器160將在步驟S304中所擷取之資料之部分的邏輯位址映射至在步驟S306被寫入之單階備用區塊，並將被寫入單階備用區塊定義為單階資料區塊中之一者。

在步驟S314中，控制器160擷取資料中尚未被寫入單階備用區塊之一部分。詳細而言，控制器160接續著前一次所擷取的資料的部分，擷取資料中尚未被寫入單階備用區塊並且等同於一個單階區塊之資料量的一部分。當所剩餘之資料小於一個單階區塊時，控制器160則擷取所有剩餘之資料。

在步驟S316中，控制器160將所擷取之資料的部分寫入單階備用儲存區塊SLC_SP_1~SLC_SP_N中之一者。換言之，控制器160將在步驟S314中所擷取之資料的部分寫入單階備用儲存區塊SLC_SP_1~SLC_SP_N中之一者。

接著，在步驟S318中，控制器160將所擷取之資料之部分的邏輯位址映射至被寫入之單階備用區塊，並將被寫入單階備用區塊定義為單階資料區塊中之一者。換言之，控制器160將在步驟S314中所擷取之資料之部分的邏輯位址映射至在步驟S316被寫入之單階備用區塊，並將被寫入單階備用區塊定義為單階資料區塊中之一者。

在步驟S332中，控制器160判斷資料是否是全部寫入單階區塊中。當資料未全部寫入單階區塊時，流程回到步驟 S302以繼續判斷是否滿足第一既定條件。當資料已全部寫入單階區塊時，流程結束於步驟S320。

第4A~4B圖係本發明之一種實施例之資料維護方法之流程圖。資料維護方法適用於第1圖所示之資料儲存裝置140。流程開始於步驟S400。第4A~4B圖所示之資料維護方法相似於第3A~3B圖之資料維護方法。第4A~4B圖所示之資料維護方法更可基於單階區塊以及三階區塊的特性，交替地執行寫入以及清除操作，以確保快閃記憶體180可穩定地提供可用的單階備用區塊也可以穩定地進行寫入工作。步驟S400~S412以及S432相似於第3A~3B圖之步驟S300~S312以及S332，請參考第3A~3B圖之說明，在此不在贅述。

接著，在步驟S414中，控制器160判斷一第二既定條件是否滿足。在一實施例中，控制器160判斷單階備用區塊SLC_SP_1~SLC_SP_N之數量是否小於一第二既定值，以判斷第二既定條件是否被滿足。當單階備用區塊SLC_SP_1~SLC_SP_N之數量小於既定值時，第二既定條件被滿足。詳細而言，當第二既定條件被滿足時，流程進行至步驟S416以開始進行清除單階資料區塊SLC_DA_1~SLC_DA_P的操作。當第二既定條件未被滿足時，流程進行至步驟S426。在其他實施例中，第二既定條件可包括任何需要清理單階資料區塊之事件。

在步驟S416中，控制器160擷取資料中尚未被寫入單階備用區塊之一部分。詳細而言，控制器160接續著前一次所擷取的資料的部分，擷取資料中尚未被寫入單階備用區塊並 且等同於三個單階區塊之資料量的一部分。當所剩餘之資料小於三個單階區塊時，控制器160則擷取所有剩餘之資料。

接著，在步驟S418中，控制器160將所擷取之資料的部分寫入單階備用儲存區塊SLC_SP_1~SLC_SP_N中之三個第一單階備用儲存區塊。換言之，控制器160將在步驟S304中所擷取之資料的部分寫入單階備用儲存區塊SLC_SP_1~SLC_SP_N中之三個單階備用儲存區塊。

接著，在步驟S420中，控制器160自單階資料區塊SLC_DA_1~SLC_DA_P中選擇所具有之有效資料存在最久之三個單階資料區塊。換言之，控制器160自單階資料區塊SLC_DA_1~SLC_DA_P中選取三個具有冷資料(Cold Data)的三個單階資料區塊。

接著，在步驟S422中，控制器160將所選擇之三個單階資料區塊中之資料整理至三階備用區塊中之一者以釋放所選擇之三個單階資料區塊，其中被釋放的三個單階資料區塊已失去與原資料的位址映射關係，並且被定義為單階備用區塊。

接著，在步驟S424中，控制器160將所擷取之資料之部分的至少一邏輯位址映射至被寫入之單階備用區塊，並將被寫入單階備用區塊定義為單階資料區塊中之三者。換言之，控制器160將在步驟S304中所擷取之資料之部分的邏輯位址映射至在步驟S306被寫入之單階備用區塊，並將被寫入單階備用區塊定義為單階資料區塊中之三者。

在步驟S426中，控制器160擷取資料中尚未被寫入 單階備用區塊之一部分。詳細而言，控制器160接續著前一次所擷取的資料的部分，擷取資料中尚未被寫入單階備用區塊並且等同於一個單階區塊之資料量的一部分。當所剩餘之資料小於一個單階區塊時，控制器160則擷取所有剩餘之資料。

在步驟S428中，控制器160將所擷取之資料的部分寫入單階備用儲存區塊SLC_SP_1~SLC_SP_N中之一者。換言之，控制器160將在步驟S314中所擷取之資料的部分寫入單階備用儲存區塊SLC_SP_1~SLC_SP_N中之一者。

接著，在步驟S430中，控制器160將所擷取之資料之部分的邏輯位址映射至被寫入之單階備用區塊，並將被寫入單階備用區塊定義為單階資料區塊中之一者。換言之，控制器160將在步驟S314中所擷取之資料之部分的邏輯位址映射至在步驟S316被寫入之單階備用區塊，並將被寫入單階備用區塊定義為單階資料區塊中之一者。

本發明所提供之資料儲存裝置以及資料維護方法，可穩定的提供三階備用區塊並且同時將資料寫入單階備用區塊。

本發明之方法，或特定型態或其部份，可以以程式碼的型態存在。程式碼可儲存於實體媒體，如軟碟、光碟片、硬碟、或是任何其他機器可讀取(如電腦可讀取)儲存媒體，亦或不限於外在形式之電腦程式產品，其中，當程式碼被機器，如電腦載入且執行時，此機器變成用以參與本發明之裝置。程式碼也可透過一些傳送媒體，如電線或電纜、光纖、或是任何傳輸型態進行傳送，其中，當程式碼被機器，如電腦接收、載 入且執行時，此機器變成用以參與本發明之裝置。當在一般用途處理單元實作時，程式碼結合處理單元提供一操作類似於應用特定邏輯電路之獨特裝置。

惟以上所述者，僅為本發明之較佳實施例而已，當不能以此限定本發明實施之範圍，即大凡依本發明申請專利範圍及發明說明內容所作之簡單的等效變化與修飾，皆仍屬本發明專利涵蓋之範圍內。另外本發明的任一實施例或申請專利範圍不須達成本發明所揭露之全部目的或優點或特點。此外，摘要部分和標題僅是用來輔助專利文件搜尋之用，並非用來限制本發明之權利範圍。

100‧‧‧電子系統

120‧‧‧主機

140‧‧‧資料儲存裝置

160‧‧‧控制器

162‧‧‧運算單元

164‧‧‧永久記憶體

166‧‧‧隨機存取記憶體

180‧‧‧快閃記憶體

Claims (30)

1. 一種資料儲存裝置，包括：一快閃記憶體，具有複數單階備用區塊、複數單階資料區塊、複數三階備用區塊以及複數三階資料區塊；以及一控制器，響應於用以將一資料寫入該快閃記憶體之一寫入命令，將該資料寫入該等單階備用區塊，其中當一第一既定條件滿足時，該控制器自該等三階資料區塊中選取具有最少有效資料之複數第一三階資料區塊，將該等第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊，並且釋放該等第一三階資料區塊，以將該等三階備用區塊之總數增加一。
2. 根據申請專利範圍第1項之資料儲存裝置，其中該等第一三階資料區塊中之無效資料的資料量等於一個該三階資料區塊或者一個該三階備用區塊的資料量。
3. 根據申請專利範圍第1項之資料儲存裝置，其中當該第一既定條件滿足時，該控制器更用以在選取該等第一三階資料區塊之前，將該資料中之一第一部分寫入該等單階備用儲存區塊中之一第一單階備用儲存區塊。
4. 根據申請專利範圍第3項之資料儲存裝置，其中當該第一既定條件滿足時，該控制器更用以在釋放該等第一三階資料區塊後，才將所寫入之該資料的至少一邏輯位址映射至所寫入之該第一單階備用區塊並將映射至該邏輯位址之該等單階備用區塊定義為該等單階資料區塊。
5. 根據申請專利範圍第1項之資料儲存裝置，其中該控制器係 在該資料中之一第一部分以外之其他部分被寫入該等單階備用儲存區塊之其他者之前，執行選取該等第一三階資料區塊，將該等第一三階資料區塊中之有效資料寫入該第一三階備用區塊以及釋放該等第一三階資料區塊的步驟。
6. 根據申請專利範圍第1項之資料儲存裝置，其中該第一既定條件為該等三階備用區塊之數量小於一第一既定值。
7. 根據申請專利範圍第1項之資料儲存裝置，其中當該第一既定條件未被滿足時，該控制器連續將該資料寫入該等單階備用區塊中。
8. 根據申請專利範圍第1項之資料儲存裝置，其中該等單階備用區塊係為不具有有效資料之單階區塊，該等單階資料區塊為具有有效資料之單階區塊，該等三階備用區塊為不具有有效資料之三階區塊，並且該等三階資料區塊為具有有效資料之三階區塊。
9. 一種資料儲存裝置，包括：一快閃記憶體，具有複數單階備用區塊、複數單階資料區塊、複數三階備用區塊以及複數三階資料區塊；以及一控制器，響應於用以將一資料寫入該快閃記憶體之一寫入命令，將該資料寫入該等單階備用區塊，其中當一第一既定條件滿足時，該控制器每寫入一個該等單階備用區塊便整理該等三階資料區塊中之複數第一三階資料區塊以將該等三階備用區塊之總數增加一。
10. 根據申請專利範圍第9項之資料儲存裝置，其中該等第一三階資料區塊中之無效資料的資料量等於一個該三階資料區 塊或者一個該三階備用區塊的資料量。
11. 根據申請專利範圍第9項之資料儲存裝置，其中為了將該等三階備用區塊之總數增加一，該控制器自該等三階資料區塊中選取具有最少有效資料之複數第一三階資料區塊，將該等第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊，並且釋放該等第一三階資料區塊。
12. 根據申請專利範圍第11項之資料儲存裝置，其中當該第一既定條件滿足時，該控制器更用以在釋放該等第一三階資料區塊後，才將所寫入之該資料的至少一邏輯位址映射至所寫入之該第一單階備用區塊並將映射至該邏輯位址之該等單階備用區塊定義為該等單階資料區塊。
13. 根據申請專利範圍第9項之資料儲存裝置，其中該第一既定條件為該等三階備用區塊之數量小於一第一既定值。
14. 根據申請專利範圍第9項之資料儲存裝置，其中當該第一既定條件未被滿足時，該控制器連續將該資料寫入該等單階備用區塊中。
15. 根據申請專利範圍第9項之資料儲存裝置，其中該等單階備用區塊係為不具有有效資料之單階區塊，該等單階資料區塊為具有有效資料之單階區塊，該等三階備用區塊為不具有有效資料之三階區塊，並且該等三階資料區塊為具有有效資料之三階區塊。
16. 一種資料維護方法，適用於具有一快閃記憶體之資料儲存裝置，其中該快閃記憶體具有複數單階備用區塊、複數單階資料區塊、複數三階備用區塊以及複數三階資料區塊， 該資料維護方法包括：接收用以將一資料寫入該快閃記憶體之一寫入命令；以及響應於該寫入命令，將該資料寫入該等單階備用區塊，其中當一第一既定條件滿足時將該資料寫入該等單階備用區塊之步驟更包括：自該等三階資料區塊中選取具有最少有效資料之複數第一三階資料區塊；將該等第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊；以及釋放該等第一三階資料區塊，以將該等三階備用區塊之總數增加一。
17. 根據申請專利範圍第16項之資料維護方法，其中該等第一三階資料區塊中之無效資料的資料量等於一個該三階資料區塊或者一個該三階備用區塊的資料量。
18. 根據申請專利範圍第16項之資料維護方法，其中當一第一既定條件滿足時將該資料寫入該等單階備用區塊之步驟更包括：在選取該等第一三階資料區塊之前，將該資料中之一第一部分寫入該等單階備用儲存區塊中之一第一單階備用儲存區塊。
19. 根據申請專利範圍第18項之資料維護方法，其中當一第一既定條件滿足時將該資料寫入該等單階備用區塊之步驟更包括： 在釋放該等第一三階資料區塊後，才將所寫入之該資料的至少一邏輯位址映射至所寫入之該第一單階備用區塊並將映射至該邏輯位址之該等單階備用區塊定義為該等單階資料區塊。
20. 根據申請專利範圍第16項之資料維護方法，其中選取該等第一三階資料區塊，將該等第一三階資料區塊中之有效資料寫入該第一三階備用區塊以及釋放該等第一三階資料區塊的步驟係在該資料中之一第一部分以外之其他部分被寫入該等單階備用儲存區塊之其他者之前執行的。
21. 根據申請專利範圍第16項之資料維護方法，其中該第一既定條件為該等三階備用區塊之數量小於一第一既定值。
22. 根據申請專利範圍第16項之資料維護方法，其中當該第一既定條件未被滿足時將該資料寫入該等單階備用區塊之步驟更包括：該控制器連續將該資料寫入該等單階備用區塊中。
23. 根據申請專利範圍第16項之資料維護方法，其中該等單階備用區塊係為不具有有效資料之單階區塊，該等單階資料區塊為具有有效資料之單階區塊，該等三階備用區塊為不具有有效資料之三階區塊，並且該等三階資料區塊為具有有效資料之三階區塊。
24. 一種資料維護方法，適用於具有一快閃記憶體之資料儲存裝置，其中該快閃記憶體具有複數單階備用區塊、複數單階資料區塊、複數三階備用區塊以及複數三階資料區塊，該資料維護方法包括： 接收用以將一資料寫入該快閃記憶體之一寫入命令；以及響應於該寫入命令，將該資料寫入該等單階備用區塊，其中當一第一既定條件滿足時將該資料寫入該等單階備用區塊之步驟更包括：每寫入一個該等單階備用區塊便整理該等三階資料區塊中之複數第一三階資料區塊以將該等三階備用區塊之總數增加一。
25. 根據申請專利範圍第24項之資料維護方法，其中該等第一三階資料區塊中之無效資料的資料量等於一個該三階資料區塊或者一個該三階備用區塊的資料量。
26. 根據申請專利範圍第24項之資料維護方法，其中為了將該等三階備用區塊之總數增加一，當該第一既定條件滿足時將該資料寫入該等單階備用區塊之步驟更包括：自該等三階資料區塊中選取具有最少有效資料之複數第一三階資料區塊；將該等第一三階資料區塊中之有效資料寫入至少一第一三階備用區塊；以及釋放該等第一三階資料區塊。
27. 根據申請專利範圍第26項之資料維護方法，其中當該第一既定條件滿足時將該資料寫入該等單階備用區塊之步驟更包括：在釋放該等第一三階資料區塊後，才將所寫入之該資料的至少一邏輯位址映射至所寫入之該第一單階備用區塊並將 映射至該邏輯位址之該等單階備用區塊定義為該等單階資料區塊。
28. 根據申請專利範圍第24項之資料維護方法，其中該第一既定條件為該等三階備用區塊之數量小於一第一既定值。
29. 根據申請專利範圍第24項之資料維護方法，其中當該第一既定條件未被滿足時，將該資料寫入該等單階備用區塊之步驟更包括：連續將該資料寫入該等單階備用區塊中。
30. 根據申請專利範圍第24項之資料維護方法，其中該等單階備用區塊係為不具有有效資料之單階區塊，該等單階資料區塊為具有有效資料之單階區塊，該等三階備用區塊為不具有有效資料之三階區塊，並且該等三階資料區塊為具有有效資料之三階區塊。