TW201931126A

TW201931126A - 資料貯存裝置的垃圾回收方法

Info

Publication number: TW201931126A
Application number: TW106146458A
Authority: TW
Inventors: 許嫣蘭; 徐博賢; 張柏堅
Original assignee: 國科美國研究實驗室
Priority date: 2017-12-29
Filing date: 2017-12-29
Publication date: 2019-08-01
Also published as: TWI644207B

Abstract

一個資料貯存裝置用一種垃圾回收方法。該資料貯存裝置包括一個NAND快閃記憶體，該NAND快閃記憶體包括若干資料區塊，每一個資料區塊包括若干資料頁。在該垃圾回收方法中，從該等資料區塊選一個目的資料區塊。把使用者資料寫入該目的資料區塊以前，為該目的資料建立若干映射表來記錄使用者資料的邏輯地址與實體地址之關係，並建立一個關聯性位元圖。該關聯性位元圖中的每一個位元對應一個映射表。然後，選擇一個待回收資料區塊。然後，依該待回收資料區塊的關聯性位元圖讀取相關映射表。然後，逐一判斷該待回收資料區塊的全部資料頁是否在相關映射表裡。若該待回收資料區塊的一資料頁在相關映射表裡，則把該資料頁設為有效資料頁。然後，把該等有效資料頁的資料寫入該目的資料區塊。

Description

資料貯存裝置的垃圾回收方法

本發明有關於資料貯存裝置，特別有關於資料貯存裝置的垃圾回收方法。

快閃記憶體轉換層(Flash Translation Layer：FTL)泛指實現於快閃記憶體的韌體演算法。快閃記憶體分為NOR和NAND快閃記憶體。以下主要討論NAND快閃記憶體的FTL(或稱NFTL)。NAND快閃記憶體的快閃記憶體，不論SLC(Single-Level Chip)或MLC(Multi-Level Chip)，有三個物理特性。第一，寫過的地址須抹除後方能再寫。第二，一次讀或寫的單位小而一次抹除的單位大。舉例而言，一次讀或寫的單位是一資料頁(Page)而一次抹除的單位是一資料區塊(Block)。通常，一資料區塊包括許多資料頁。第三，每一資料區塊的抹除次數受限。舉例而言，SLC的抹除次數之限制是約100000次，MLC的抹除次數之限制是約10000次。

如第1圖所示，一個FTL管理一個NAND快閃記憶體，並連接一個檔案系統。NAND快閃記憶體被分成若干資料區塊。

如第2圖所示，每一資料區塊有若干資料頁及若干備用部(Spare)。如上所述，對FTL而言，讀及寫的最小單位是一資料頁，抹除的最小單位是一資料區塊。資料頁貯存使用者資料。備用部，又稱作元資料(Metadata)，貯存關於對應資料頁的資訊，例如這資料頁對應的邏輯位置及ECC資訊。

FTL的主要工作是處理邏輯地址(Logic Address)與實體地址(Physical Address)的映射關係(Mapping)。所以，FTL會用一些表格記錄這些關係，方便查表及寫入。FTL在寫入後，更新表格。FTL在記憶體裡配置表格空間，並在寫滿表格後，把資料從該表格下刷到NAND快閃記憶體。NAND快閃記憶體的資料區塊簡單被分為資料區塊及表格區塊。資料區塊貯存使用者資料，表格區塊貯存表格。

第3圖到第5圖顯示寫入及回收的簡單範例。圖中的表格為實體頁碼(Physical Page Number：PPN)及資料的對應。

如第3圖所示，資料區塊1000有三筆資料x、y及z。資料區塊2000是一個空閒的(free)資料區塊，裡面沒任何資料。

如第4圖所示，更新x的資料，也就是為同一個邏輯地址(圖未示)把一筆新的資料x’寫入PPN是3的那資料頁。此時，PPN是0的那資料頁的資料就變成無效資料(invalid data)。寫滿資料區塊1000時，它包含有效資料(valid data)及無效資料。

如第5圖所示，資料區塊1000被回收以前，資料區塊1000的有效資料頁會被寫入資料區塊2000。然後，資料區塊1000就被抹除，變回空閒資料區塊。

當NAND快閃記憶體的可用的空間降到一個水位，FTL就會執行垃圾回收(Garbage Collection：GC)。垃圾回收有幾個步驟。首先，從一個資料區塊區域(Data Block Area：DBA)挑選一個待回收資料區塊(victim block)，例如圖4所示的資料區塊1000。其次，挑選一個目的資料區塊(destination block)，例如圖4所示的資料區塊2000。接著，搬該待回收資料區塊中有效資料頁到該目的資料區塊。最後，抹除並釋放該待回收資料區塊。這流程會一直被執行，直到空閒資料區塊數目回到另一個水位之上為止。

要判斷待回收資料區塊裡的某一資料頁是有效資料頁或無效資料頁，做法是檢查該資料頁的實體地址是否在一張映射表(Mapping Table)裡。若是，則表示該資料頁是有效資料頁。

當控制器用小尺寸的RAM，FTL不能把全部映射表貯存在RAM裡，以致它只能把一定數量的映射表暫存(CACHE)於RAM裡。有兩種方法可比較實體地址與映射表。

第一種做法是FTL把全部映射表逐一從NAND快閃記憶體寫入RAM，並把它的內容與實體地址相比。舉例而言，若在NAND快閃記憶體裡有M張映射表，則FTL須花映射表載入時間的M倍。這時間很長。

第二種做法是FTL從待回收資料區塊的每一資料頁的元資料讀取邏輯地址，並由這些邏輯地址得知應從NAND快閃記憶體讀取那些映射表。舉例而言，若一個資料區塊有K資料頁，且須從NAND快閃記憶體讀取L張映射表，則FTL須花元資料讀取時間的K倍加映射表載入時間L倍。L小於或等於K。這時間不短。

有鑑於上述習知技術之問題與缺失，本發明之目的在於為一個資料貯存裝置提供一種只需要很少資源的垃圾回收方法。

為達成上述目的，該資料貯存裝置包括一個NAND快閃記憶體，該NAND快閃記憶體包括若干資料區塊，每一個資料區塊包括若干資料頁。在該垃圾回收方法中，從該等資料區塊選一個目的資料區塊。把使用者資料寫入該目的資料區塊以前，為該目的資料建立若干映射表來記錄使用者資料的邏輯地址與實體地址之關係，並建立一個關聯性位元圖。該關聯性位元圖中的每一個位元對應一個映射表。然後，選擇一個待回收資料區塊。然後，依該待回收資料區塊的關聯性位元圖讀取相關映射表。然後，逐一判斷該待回收資料區塊的全部資料頁是否在相關映射表裡。若該待回收資料區塊的一資料頁在相關映射表裡，則把該資料頁設為有效資料頁。然後，把該等有效資料頁的資料寫入另一個資料區塊。

10‧‧‧主機

12‧‧‧SSD控制器

14‧‧‧SSD記憶體

16‧‧‧NAND快閃記憶體

18‧‧‧處理器

20‧‧‧有效資料頁位元圖

22‧‧‧映射表

24‧‧‧關聯性位元圖

26‧‧‧資料緩衝區

28‧‧‧表格索引一維陣列

30‧‧‧資料區塊

32‧‧‧表格區塊

34‧‧‧表格索引區塊

第1圖是典型的資料貯存系統的方塊圖；第2圖是第1圖所示的資料貯存系統的NAND快閃記憶體的簡化的方塊圖；第3圖到第5圖是第2圖所示的NAND快閃記憶體的兩個資料區塊在不同狀態的方塊圖；第6圖是本發明的較佳實施例的資料貯存系統在書寫子程序裡的方塊圖；第7圖是第6圖所示的資料貯存系統在回收子程序裡的方塊圖；第8圖是第6圖所示的資料貯存系統所執行的書寫子程序的流程圖；第9圖是第7圖所示的資料貯存系統所執行的回收子程序的流程圖；及第10圖是第9圖所示的回收子程序的部分的流程圖。

以下，參考相關圖式，進一步說明本發明的資料貯存裝置的垃圾回收方法的實施例，相同元件係採相同符號。

如第6圖及第7圖所示，一個資料貯存系統包括一個主機10、一個SSD控制器12、一個SSD記憶體14及一個NAND快閃記憶體16。該資料貯存系統可用本發明的較佳實施例的垃圾回收方法。該垃圾回收方法包括一道書寫子程序及一道回收子程序。

第6圖顯示該資料貯存系統在該書寫子程序中的狀態。首先，主機10提供書寫指令。一個書寫指令包括將被貯存於NAND快閃記憶體16的使用者資料。

SSD控制器12有一個處理器18。處理器18執行FTL。SSD記憶體14貯存映射表22、一張關聯性位元圖(Relevance Bit Map)24、一個資料緩衝區(Data Buffer)26及一個表格索引一維陣列(Map Index Array)28。NAND快閃記憶體16包括若干資料區塊30、若干表格區塊32及一個表格索引區塊34。該等資料區塊30本質上相同，但因在本發明的垃圾回收方法中某階段扮演不同角色而冠上不同形容詞。空閒(free)資料區塊30是不含任何使用者資料的資料區塊30。目的資料區塊30是使用者資料要進入的資料區塊30。待回收資料區塊30是即將被抹除並回收的資料區塊30。

映射表22貯存邏輯地址與實體地址對應關係。映射表22的大小及數目取決於SSD記憶體14的大小。

關聯性位元圖24貯存一個對應的資料區塊30與多張映射表22的關聯。關聯性位元圖24的每一個位元代表一張映射表22。若目前系統有N張映射表22，則關聯性位元圖24至少會有N個位元。關聯性位元圖24被初始化時，其全部位元被設為「0」。若此對應的資料區塊30與第M張映射表22有關聯，則關聯性位元圖24的第M個位元會被設為「1」。

資料緩衝區26暫時貯存將從主機10被寫入NAND快閃記憶體16的使用者資料。一旦地址轉換(Address Translation)完成而確定這些使用者資料的實體地址，這些使用者資料會由資料緩衝區26被搬入NAND快閃記憶體16的一個資料區塊30。

表格索引一維陣列28是一張表，並紀錄映射表22及關聯性位元圖24的實體地址的一維陣列。若目前系統有N張映射表22及K張關聯性位元圖24，則這個一維陣列的大小為N+K列。表格索引一維陣列28貯存各張表在NAND快閃記憶體16裡的實體地址。

寫滿一張映射表22時，把它的內容下刷到NAND快閃記憶體16的表格區塊32，並在表格索引一維陣列28裡更新這張映射表22在NAND快閃記憶體16裡的實體地址。

寫滿一資料區塊30時，就把它的關聯性位元圖24的內容下刷到NAND快閃記憶體16的表格區塊32，且在表格索引一維陣列28裡更新這張關聯性位元圖24在NAND快閃記憶體16裡的實體地址。

每隔一段固定時間，會把表格索引一維陣列28下刷到NAND快閃記憶體16的特定地址。

資料區塊30貯存從主機10而來的使用者資料。表格區塊32貯存各種表，主要是映射表22及關聯性位元圖24。表格索引區塊34貯存各種表的實體地址，位在NAND快閃記憶體16的特定地址。

第7圖顯示該資料貯存系統在該回收子程序中的狀態。第7圖所示的狀態與第6圖所示的狀態相似，但有幾項差異。第一項差異是資料流向為雙向。第二項差異是資料緩衝區26貯存從待回收資料區塊30回收的資料，且把這些資料寫入目標資料區塊30。第三項差異是增加一個有效資料頁位元圖20。

在SSD記憶體14裡，會初始化一張新關聯性位元圖24，該關聯性位元圖24將標示該待回收資料區塊30的有效資料頁。舉例而言，若一資料區塊30有M資料頁，則它的關聯性位元圖24至少有M個位元。若確認該待回收資料區塊30的第K資料頁是有效的，則把它的關聯性位元圖24的第K位元設為「1」。在初始時，關聯性位元圖24的全部位元被設為「0」。垃圾回收結束時，被關聯性位元圖24佔用的空間將被釋放。

第8圖是該書寫子程序的流程圖。在S10，主機10提供一個書寫指令。該書寫指令包括一筆使用者資料。

把一筆使用者資料寫入NAND快閃記憶體16以前，在S12，判斷是否把這筆使用者資料寫入一空閒資料區塊30，亦即判斷目的資料區塊30是否一空閒資料區塊30。若要把這書使用者資料寫入一空閒資料區塊30，則走到S14，否則走到S16。要把一筆使用者資料寫入空閒資料區塊30，有兩個原因。第一，這個NAND快閃記憶體16從來沒被寫過，這筆使用者資料是第一筆資料。第二，前一目的資料區塊30已滿。不論那個原因，在S14，都須在SSD記憶體14裡初始化一張新的映射表22及一張關聯性位元圖24。若目標資料區塊非一空閒資料區塊30，則不必初始化新表。

在S16，把使用者資料寫入資料緩衝區26，並在FTL完成轉換且確定要寫入的實體地址以後，把使用者資料從資料緩衝區26下刷到NAND快閃記憶體16的目的資料區塊30。

在S18，更新在SSD記憶體14裡的映射表22及關聯性位元圖24。

在S20，判斷目的資料區塊30是否已滿。若此目的資料區塊30已滿，則走到在S22，否則走到S24。

在S22，把關聯性位元圖24下刷到NAND快閃記憶體16。

在S24，判斷此映射表22是否已滿。若此映射表22已滿，則走到S26，否則走到S28。

在S26，把此映射表22下刷到NAND快閃記憶體16，且FTL把此映射表22的實體地址寫入表格索引一維陣列28。

在S28，書寫子程序結束。

參考第9圖，在S30，偵測到空閒資料區塊30的數目降到一定的水位時，執行該回收子程序。

在S32，挑選含最少有效資料頁的資料區塊30當待回收資料區塊30。

在S34，查詢表格索引一維陣列28而找到待回收資料區塊30對應的關聯性位元圖24的實體地址，並把此關聯性位元圖24的資料從對應的表格區塊32載入SSD記憶體14。

在S36，掃瞄關聯性位元圖24，可以得知待回收資料區塊30與哪些映射表22有關聯，逐一查找這些映射表22的實體地址，並把它們從NAND快閃記憶體16載入SSD記憶體14。從映射表22的資料，可以得知待回收資料區塊30的那些資料頁還是有效的。

在S38，建立有一張有效資料頁位元圖20。把與有效資料頁對應的有效資料頁位元圖20的位元設為「1」。稍後，將參考第10圖，詳細描述如何建立有效資料頁位元圖20。

在S52，判斷是否已運載並掃描全部有關聯的映射表22。若已運載並掃描全部有關聯的映射表22，則走到S54，否則回到S36。

在S54，已建立有效資料頁位元圖20，從此有效資料頁位元圖20得知那些資料頁的實體地址是有效的，並把使用者資料從NAND快閃記憶體16的待回收資料區塊30載入SSD記憶體14的資料緩衝區26。稍後，把這些使用者資料下刷到該目的資料區塊30。

在S56，已回收待回收資料區塊30的全部有效資料頁，這個垃圾回收作業完成。

參考第10圖，詳細描述如何建立有效資料頁位元圖20。在S40，掃描映射表22。

在S42，讀取在映射表22的各個條目(entry)的值，此值為實體地址。

在S44，判斷該實體地址是否在待回收資料區塊30之內。若該實體地址在待回收資料區塊30之內，則走到S46，否則走到S48。

在S46，把在有效資料頁位元圖20中，與該實體地址對應的位元設為「1」。

在S48，判斷目前的條目是否最後一個條目。若目前的條目是最後一個條目，則走到S50，否則走回S42。

在S50，掃瞄結束。此時，已掃描目前的映射表22的全部條目，並已完成有效資料頁位元圖20。

本發明的垃圾回收方法特別適用於SSD記憶體有限的資料貯存裝置。建立關聯性位元圖24來減少掃瞄的映射表22的數量，並因此快速找到有效的資料頁。另外，建立有效資料頁位元圖20來標示有效資料頁，並因此快速把有效資料頁從待回收資料區塊30寫入一個新的資料區塊30。

以上所述說明，僅為本發明的較佳實施方式而已，意在明確本發明的特徵，非用以限定本發明實施例的範圍，本技術領域內的一般技術人員根據本發明所作的均等變化，及本領域內技術人員熟知的改變，仍應屬本發明涵蓋的範圍。

Claims

一種資料貯存裝置的垃圾回收方法，其包括以下步驟：(a)提供一種資料貯存裝置，該資料貯存裝置包括一個NAND快閃記憶體(16)，該NAND快閃記憶體(16)包括若干資料區塊(30)，每一個資料區塊(30)包括若干資料頁；(b)從該等資料區塊(30)選一個目的資料區塊(30)；(c)把使用者資料寫入該目的資料區塊(30)以前，為該目的資料建立若干映射表(22)來記錄使用者資料的邏輯地址與實體地址之關係，並建立一個關聯性位元圖(24)，該關聯性位元圖(24)中的每一個位元對應一個映射表(22)；(d)從該等資料區塊(30)選一個待回收資料區塊(30)；(e)依該待回收資料區塊(30)的關聯性位元圖(24)讀取相關映射表(22)；(f)逐一判斷該待回收資料區塊(30)的全部資料頁是否在相關映射表(22)裡；(g)若該待回收資料區塊(30)的一資料頁在相關映射表(22)裡，則把該資料頁設為有效資料頁；及(h)把該等有效資料頁的資料寫入另一個資料區塊(30)。
如第1請求項所述之資料貯存裝置的垃圾回收方法，其中步驟(g)包括以下步驟：(g1)建立一個有效資料頁位元圖(24)，該有效資料頁位元圖(24)中每一個位元對應該待回收資料區塊(30)的一資料頁。
如第2請求項所述之資料貯存裝置的垃圾回收方法，其中該步驟(g1)包括以下步驟：(g1A)把該有效資料頁位元圖(24)中對應有效資料頁的位元設為「1」；及(g1B)把該有效資料頁位元圖(24)中其他位元設為「0」。
如第1請求項所述之資料貯存裝置的垃圾回收方法，其中步驟(c)依序包括以下步驟：(c1)判斷該目的資料區塊(30)是否新資料區塊(30)；(c2)若該目的資料區塊(30)是新資料區塊(30)，則初始化一張新的關聯性位元圖(24)及一張新的映射圖(22)；(c3)把使用者資料寫入該目的資料區塊(30)；及(c4)更新該關聯性位元圖(24)及該映射圖(22)。
如第4請求項所述之資料貯存裝置的垃圾回收方法，其中步驟(c)依序包括以下步驟：(c5)判斷該目的資料區塊(30)是否已滿；(c6)若該目的資料區塊(30)已滿，則把該關聯性位元圖(24)寫入該NAND快閃記憶體(16)；(c7)判斷該映射表(22)是否已滿；(c8)若該映射表(22)已滿，則把該映射表(22)寫入該NAND快閃記憶體(16)；及(c9)結束書寫。
如第1請求項所述之資料貯存裝置的垃圾回收方法，其中步驟(c)包括以下步驟：(c10)把該關聯性位元圖(24)中對應該等映射表(22)的位元設為「1」；及(c11)把該關聯性位元圖(24)中其他位元設為「0」。