數據儲存方法及其系統與流程

2023-06-26 00:06:01 2

本發明是關於一種數據儲存方法，且特別是可應用於硬碟的數據儲存系統的數據儲存方法。

背景技術：

近年來，非易失性儲存裝置發展蓬勃，例如固態硬碟，由於快閃記憶體的儲存能力、耗電量及記憶體的集成度相較於傳統硬碟均為較佳，使得快閃記憶體成為電子裝置中的儲存裝置的理想元件。

公知的快閃記憶體包含許多用來儲存數據的儲存區塊，每個儲存區塊由許多儲存頁組合而成。快閃記憶體的儲存數據在經多次更新後，原先儲存於儲存頁中的舊數據成為無效數據，在此情形下，必須要進行垃圾收集(garbagecollection)來將無效數據清除，以將無效數據佔據的儲存頁釋放。然而，儲存頁的寫入操作僅可將儲存區塊整個成功抹除後才能被寫入，而抹除一個儲存區塊所需的時間較寫入一個儲存頁的時間來的長，舉例來說，假設數據寫入儲存頁需耗時200微秒，而將儲存區塊抹除需耗時約2毫秒。因此，快閃記憶體的抹除操作大幅地降低其讀寫效能。

再者，在將儲存區塊進行抹除之前，必需先將儲存區塊中的有效數據搬移到快閃記憶體中的其他儲存頁，接著才可將欲儲存區塊進行抹除。由於快閃記憶體的每一儲存頁均有讀寫次數限制，將儲存數據搬移的過程中會造成額外的讀寫負擔，增加儲存頁的讀寫次數，如此便降低了快閃記憶體的可使用壽命。

技術實現要素：

有鑑於此，本發明提出一種數據儲存方法及其系統。

在一實施例中，一種數據儲存系統包含硬碟及處理單元。硬碟包含具多個實體頁面的一實體區塊，前述實體頁面儲存對應於多個邏輯地址的多個寫入數據，每一實體頁面對應於一有效位元，各實體頁面根據對應的有效位元為一第一值而區分為一有效數據頁面，或根據對應的有效位元為一第二值而區分為一無效數據頁面；處理單元系用以配置第一邏輯區塊及第二邏輯區塊，第一邏輯區塊及第二邏輯區塊映射於實體區塊，第一邏輯區塊包含連續的多個第一邏輯頁面，第二邏輯區塊包含連續的多個第二邏輯頁面，第一邏輯頁面用以儲存邏輯地址，邏輯地址包含多個映射於有效數據頁面的多個有效邏輯地址，且多個有效邏輯地址與多個有效數據頁面之間具有一對一對應的一第一映射關係，處理單元於執行垃圾收集時，根據有效位元將有效邏輯地址依據第二邏輯頁面的順序依序且連續地儲存於第二邏輯頁面，且處理單元根據第一映射關係建立第二邏輯頁面與有效數據頁面之間的一對一對應的一第二映射關係。

在一實施例中，一種數據儲存方法用以根據多個邏輯地址將多個寫入數據儲存於一硬碟的一實體區塊的多個實體頁面，每一實體頁面對應於一有效位元，各實體頁面根據對應的有效位元為一第一值而區分為一有效數據頁面，或根據對應的有效位元為一第二值而區分為一無效數據頁面，邏輯地址包含多個映射於有效數據頁面的多個有效邏輯地址，且多個有效邏輯地址與多個有效數據頁面之間具有一對一對應的一第一映射關係，前述的數據儲存方法包含：配置一第一邏輯區塊及一第二邏輯區塊，第一邏輯區塊及第二邏輯區塊映射於實體區塊，第一邏輯區塊包含連續的多個第一邏輯頁面，第一邏輯頁面用以儲存邏輯地址，第二邏輯區塊包含連續的多個第二邏輯頁面；於執行垃圾收集時，根據有效位元將有效邏輯地址依據第二邏輯頁面的順序依序且連續地儲存於第二邏輯頁面；及根據第一映射關係建立第二邏輯頁面與有效數據頁面之間的一對一對應的一第二映射關係。

綜上所述，根據本發明的數據儲存方法及其系統的一實施例藉由配置映射於同一實體區塊的兩邏輯區塊來儲存邏輯地址，在執行垃圾收集時，將儲存於第一邏輯區塊的邏輯地址搬移至第二邏輯區塊來完成垃圾收集，而不需搬移實體區塊中的寫入數據，故可減少實體頁面的讀寫次數而增加快閃記憶體的使用壽命。

附圖說明

圖1為根據本發明的數據儲存系統的一實施例的功能方塊圖。

圖2為圖1的處理單元所配置的第一邏輯區塊的一實施例的功能方塊圖。

圖3為圖1的處理單元所配置的第二邏輯區塊的一實施例的功能方塊圖。

圖4為根據本發明的數據儲存方法的一實施例的流程圖。

【符號說明】

1硬碟

11、12、13實體區塊

111～115實體頁面

2處理單元

l1第一邏輯區塊

l11～l15第一邏輯頁面

l2第二邏輯區塊

l21～l25第二邏輯頁面

v1～v5有效位元

10、20、30邏輯地址

具體實施方式

圖1為根據本發明的數據儲存系統的一實施例的功能方塊圖。圖2為圖1的處理單元2所配置的第一邏輯區塊l1的一實施例的功能方塊圖。圖3為圖1的處理單元2所配置的第二邏輯區塊l2的一實施例的功能方塊圖。

請同時參照圖1至圖3，數據儲存系統包含硬碟1及處理單元2。處理單元2電性連接於硬碟1，以控制硬碟1的讀寫動作。硬碟1包含多個實體區塊，且每一實體區塊包含多個實體頁面。圖1至圖3是以硬碟1的實體區塊包含實體區塊11、12、13且實體區塊11包含五個實體頁面111～115為例。於此，處理單元2可將寫入數據儲存於實體頁面111～115中。

實體頁面111～115分別對應於有效位元v1～v5，以表示實體頁面111～115中所儲存的寫入數據是否有效。若實體頁面111～115所儲存的寫入數據為不再使用的舊數據則表示寫入數據為無效。其中，有效位元v1對應於實體頁面111而可表示實體頁面111所儲存的寫入數據為有效或無效，有效位元v2對應於實體頁面112而可表示實體頁面112所儲存的寫入數據為有效或無效，其餘則依此類推，不再贅述。基此，根據有效位元v1～v5的第一值及第二值，實體頁面111～115可區分為有效數據頁面及無效數據頁面，舉例來說，以前述的第一值為「1」且第二值為「0」為例，在此情形下，若對應於實體頁面111的有效位元v1為「0」，則表示實體頁面111為無效數據頁面，若對應於實體頁面114的有效位元v4為「1」，則表示實體頁面114為有效數據頁面。如此一來，有效位元v1～v5可表示實體頁面111～115是否包含無效數據而是否須被釋放。

在本實施例中，每一寫入數據系對應於一邏輯地址，而每一邏輯地址系映射於實體頁面111～115中的對應頁面，使處理單元2可根據邏輯地址將寫入數據儲存於對應的實體頁面111～115。以圖2為例，四個邏輯地址分別為「10」、「20」、「30」及「10」且四個邏輯地址「10」、「20」、「30」及「10」分別映射於四個實體頁面111、112、113、114，使處理單元2可根據四個邏輯地址將對應的四筆寫入數據分別儲存於實體頁面111～114。其中，實體頁面111、114映射於相同邏輯地址「10」，若實體頁面114的寫入時間點晚於實體頁面111的寫入時間點，則實體頁面111為無效數據頁面，而其餘的實體頁面112、113、114則為有效數據頁面。基此，邏輯地址包含有效邏輯地址及無效邏輯地址，即映射於有效數據頁面的邏輯地址為有效邏輯地址，映射於無效數據頁面的邏輯地址為無效邏輯地址。並且，有效邏輯地址與有效數據頁面之間具有一對一對應的第一映射關係。如圖2所示，第一邏輯頁面l11儲存的「10」為無效邏輯地址，第一邏輯頁面l12～l14儲存的「20」、「30」及「10」為有效邏輯地址。有效邏輯地址的邏輯地址「20」一對一映射於有效數據頁面的實體頁面112，有效邏輯地址的邏輯地址「30」一對一映射於有效數據頁面的實體頁面113，且有效邏輯地址的邏輯地址「10」一對一映射於有效數據頁面的實體頁面114。在實作上，前述的邏輯地址可為來自輸出入(i/o)裝置的虛擬地址。

圖3為圖1的處理單元2所配置的第二邏輯區塊l2的一實施例的功能方塊圖。請同時參照圖2及圖3，處理單元2用以配置第一邏輯區塊l1及第二邏輯區塊l2，第一邏輯區塊l1包含連續的多個第一邏輯頁面，第二邏輯區塊l2包含連續的多個第二邏輯頁面，且第一邏輯區塊l1及第二邏輯區塊l2映射於硬碟1的同一實體區塊。如圖2及圖3所示，第一邏輯區塊l1及第二邏輯區塊l2均映射於實體區塊11，第一邏輯區塊l1包含連續的第一邏輯頁面l11～l15，第二邏輯區塊l2包含連續的第二邏輯頁面l21～l25。在本實施例中，圖2及圖3是以處理單元2配置兩邏輯區塊l1、l2映射於實體區塊11為例，然本發明不以此為限，處理單元2可配置多個邏輯區塊來映射於硬碟1的同一實體區塊，且處理單元2可配置多個邏輯區塊來映射於硬碟1的每一實體區塊。舉例來說，處理單元2可配置四個邏輯區塊映射於硬碟1的實體區塊12，並配置三個邏輯區塊映射於硬碟1的實體區塊13，使多個邏輯區塊映射於硬碟1的每一實體區塊。

第一邏輯區塊l1系用以儲存邏輯地址，處理單元2於執行寫入動作時，處理單元2將對應於每一寫入數據的邏輯地址依次地儲存於第一邏輯區塊l1。如圖2所示，第一邏輯頁面l11～l14分別包含前述的第一邏輯地址「10」、「20」、「30」及「10」，處理單元2根據第一邏輯頁面l11～l14所儲存的邏輯地址將四筆寫入數據分別寫入對應的實體頁面111～114。於硬碟1的實體區塊11儲存多筆寫入數據之後，若硬碟1的可儲存空間低於臨界值，此時處理單元2開始執行垃圾收集，以釋放包含無效數據的無效數據頁面。首先，處理單元2根據有效位元v1～v5將有效邏輯地址依據第二邏輯頁面l21～l24的順序依序且連續地儲存於第二邏輯頁面l21～l24。詳言之，如圖2所示，處理單元2根據有效位元v1～v5判斷出第一邏輯頁面l12～l14中的邏輯地址為有效邏輯地址；接著，如圖3所示，處理單元2將第一邏輯頁面l12中的有效邏輯地址「20」儲存於第二邏輯頁面l21，且處理單元2將第一邏輯頁面l13中的有效邏輯地址「30」儲存於與第二邏輯頁面l21互為連續的第二邏輯頁面l22，最後，處理單元2將第一邏輯頁面l14中的有效邏輯地址「10」儲存於與第二邏輯頁面l22互為連續的第二邏輯頁面l23，如此便完成垃圾收集。於是，相較於第一邏輯區塊l1，第二邏輯區塊l2中並未包含任何對應於無效數據頁面的邏輯地址，使邏輯區塊l2中的空白頁面(即，第二邏輯頁面l24、l25)的數量大於第一邏輯區塊l1中的空白頁面(即，第一邏輯頁面l15)的數量。因此，相對於先前技術，處理單元2不需搬移實體區塊11中的寫入數據即可完成垃圾收集，故可減少硬碟1的讀寫次數而增加硬碟1的使用壽命。

在本實施例中，於處理單元2將有效邏輯地址「20」、「30」、「10」自第一邏輯區塊l1搬移至第二邏輯區塊l2之後，處理單元2根據前述的第一映射關係來建立第二邏輯頁面l21～23與有效數據頁面(即，實體頁面112、113、114)之間的一對一對應的一第二映射關係，使第二邏輯頁面l21、l22、l23分別一對一映射於實體頁面112、113、114，以使有效邏輯地址「20」、「30」、「10」可映射於原先存有對應的寫入數據的實體頁面112、113、114。

在實作上，處理單元2可以微處理器、微控制器、中央處理單元來實現，並可藉由軟體或固件來控制處理單元2；或者處理單元亦可為特殊應用ic(application-specificic；asic)；處理單元2可在高速緩衝存儲器、或ram中配置第一邏輯區塊l1及第二邏輯區塊l2，以儲存邏輯地址。

在一實施例中，處理單元2系將邏輯地址根據第一邏輯頁面l11～l15的順序依序地儲存於第一邏輯區塊l1中的連續頁面，以圖2為例，處理單元2先將邏輯地址「10」儲存於第一邏輯頁面l11，接著，處理單元2將邏輯地址「20」儲存於與第一邏輯頁面l11互為連續的第一邏輯頁面l12，並且，處理單元2將邏輯地址「30」儲存於與第一邏輯頁面l12互為連續的第一邏輯頁面l13，最後，處理單元2將邏輯地址「10」儲存於與第一邏輯頁面l13互為連續的第一邏輯頁面l14。基此，在硬碟1的實體區塊11儲存前述的四筆寫入數據之後，第一邏輯區塊l1依其第一邏輯頁面l11～l14的順序依序包含四個邏輯地址，且四個邏輯地址分別映射於有效數據頁面及無效數據頁面。再者，第一邏輯頁面l11～l15與實體頁面111～115之間具有一對一對應的第三映射關係，使儲存於第一邏輯頁面l11～l15的有效邏輯地址與有效數據頁面之間根據第三映射關係而具有前述的第一映射關係。舉例來說，如圖2所示，第一邏輯頁面l11、l12、l13、l14、l15分別映射於實體頁面111、112、113、114、115，在邏輯地址「10」、「20」、「30」及「10」儲存於第一邏輯頁面l11、l12、l13、l14之後，有效邏輯地址「20」、「30」及「10」即一對一映射於有效邏輯頁面112、113、114而具有前述的第一映射關係。

在一實施例中，於處理單元2將邏輯地址自第一邏輯區塊l1搬移至第二邏輯區塊l2之後，處理單元2建立第二邏輯區塊l2中的多個空白頁面與實體區塊11的無效數據頁面之間的一對一對應的一第四映射關係。以圖3為例，第二邏輯區塊l2中的多個空白頁面為第二邏輯頁面l24、l25，處理單元2建立第二邏輯頁面l24、l25分別映射於無效數據頁面的實體頁面111、115的第四映射關係。於是，處理單元2在垃圾收集之後可將另一寫入數據例如第五筆及第六筆寫入數據對應的邏輯地址分別填入第二邏輯頁面l24、l25，使兩寫入數據根據前述的第四映射關係而儲存於對應的實體頁面111、115。基此，不論實體區塊11中的無效數據頁面為連續或不連續，在處理單元2執行垃圾收集後皆可用來儲存新的寫入數據而覆蓋原數據。

在一實施例中，在處理單元2未執行任何寫入動作之前，第一邏輯區塊l1與實體區塊11的第三映射關係可預先儲存於硬碟1或其他任何具儲存能力的電路中，使處理單元2可根據預存的第三映射關係將寫入數據根據邏輯地址於第一邏輯區塊l1中的頁面位置而儲存於對應的任一實體頁面111～115；在處理單元2對第一邏輯區塊l1進行垃圾收集之後，處理單元2儲存第二邏輯區塊l2與實體區塊11之間的第四映射關係來覆蓋已儲存的第三映射關係，使前述的另一寫入數據例如第五筆及第六筆寫入數據可根據其對應的邏輯地址於第二邏輯區塊l2中的頁面位置而儲存於對應的實體頁面111、115。基此，處理單元2在對第一邏輯區塊l1進行垃圾收集之後即不再使用第一邏輯區塊l1，而是藉由第二邏輯區塊l2使邏輯地址映射於實體區塊11。

根據前述的第二映射關係、第三映射關係及第四映射關係可以得知，第一邏輯頁面l11～l15系一對一映射於實體頁面111～115，且第二邏輯頁面l21～l25系一對一映射於實體頁面111～115，表示第一邏輯頁面l11～l15的數量與實體頁面111～115的數量相同，且第二邏輯頁面l21～l25的數量與實體頁面111～115的數量相同。於此，當處理單元2配置與硬碟1的每一實體區塊皆一對一對應的邏輯區塊時，由於每一邏輯區塊中的邏輯頁面的數量與每一實體區塊中的實體頁面的數量相同，因此，處理單元2可根據第一邏輯區塊l1中空白頁面的數量來判斷硬碟1的可儲存空間是否達到前述的臨界值，以決定是否對第一邏輯區塊l1執行垃圾收集。同理，處理單元2亦可根據第二邏輯區塊l2中空白頁面的數量來判斷硬碟1的可儲存空間是否達到前述的臨界值，以決定是否對第二邏輯區塊l2執行垃圾收集。

在一實施例中，為避免具數據儲存系統的電子裝置斷電而使邏輯地址無法映射至實體區塊11，在處理單元2執行垃圾收集之前，處理單元2可將第一映射關係及第三映射關係儲存於硬碟1中，使得前述的電腦裝置在復電後可自硬碟1讀取第一映射關係及第三映射關係，使處理單元2可將寫入數據根據第一映射關係及第三映射關係而儲存於硬碟1；再者，於執行垃圾收集之後，處理單元2可將第二映射關係及第四映射關係儲存於硬碟1中，以避免前述電子裝置斷電後造成邏輯地址無法映射至實體區塊11的問題。

圖4為根據本發明的一實施例的數據儲存方法的流程圖。請同時參照圖1至圖4，處理單元2配置第一邏輯區塊l1及第二邏輯區塊l2(步驟s01)，以圖2及圖3為例，第一邏輯區塊l1包含第一邏輯頁面l11～l15，第二邏輯區塊l2包含第二邏輯頁面l21～l25，第一邏輯頁面l11～l15及第二邏輯頁面l21～l25用以儲存對應於寫入數據的邏輯地址。接著，處理單元2判斷硬碟1是否需要進行垃圾收集(步驟s02)，當硬碟1的可儲存空間小於或等於臨界值而需要進行垃圾收集時，處理單元2根據有效位元v1～v5將有效邏輯地址依據第二邏輯頁面l21～l25的順序依序且連續地儲存於第二邏輯頁面l21～l25(步驟s03)，以完成垃圾收集。最後，處理單元2根據有效邏輯地址與有效數據頁面之間的第一映射關係來建立第二邏輯頁面l21～l25中包含有效邏輯地址的邏輯頁面與有效數據頁面之間的一對一對應的第二映射關係(步驟s04)。

在一實施例中，在處理單元未進行任何寫入動作之前，數據儲存方法更包含建立第一邏輯頁面l11～l15與實體頁面111～115之間的一對一對應的第三映射關係；接著，在處理單元2執行寫入動作時，處理單元2將邏輯地址依據第一邏輯頁面l11～l15的頁面順序依序且連續地儲存於第一邏輯頁面l11～l15，使有效邏輯地址(即，第一邏輯頁面l12～14所儲存的邏輯地址)與有效數據頁面(即前述的實體頁面112～114)之間依據第三映射關係而具有第一映射關係。

在一實施例中，於執行步驟s04之後，處理單元2建立第二邏輯頁面l21～l25中的空白頁面(即，第二邏輯頁面l24、l25)與無效數據頁面(實體頁面111、115)之間的一對一對應的一第四映射關係，使前述的第五筆寫入數據與第六筆寫入數據可根據第二邏輯頁面l24、l25中的邏輯地址而儲存於實體頁面111、115。

在一實施例中，於執行步驟s03之前，處理單元2將第一映射關係及第三映射關係儲存於硬碟1中，以避免邏輯地址因數據儲存系統斷電而無法映射至實體頁面111～115的問題。同理，於執行步驟s03之後，處理單元2將第二映射關係及第四映射關係儲存於硬碟1中，以避免邏輯地址因數據儲存系統斷電而無法映射至實體頁面111～115的問題。

綜上所述，根據本發明的數據儲存方法及其系統的一實施例系藉由配置映射於同一實體區塊的兩邏輯區塊來儲存邏輯地址，在執行垃圾收集時，將儲存於第一邏輯區塊的邏輯地址搬移至第二邏輯區塊來完成垃圾收集，而不需搬移實體區塊中的寫入數據，故可減少實體頁面的讀寫次數而增加快閃記憶體的使用壽命。

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