[go: up one dir, main page]

TWI792534B - 以局部清理操作來進行垃圾回收的方法與相關控制器和儲存系統 - Google Patents

以局部清理操作來進行垃圾回收的方法與相關控制器和儲存系統 Download PDF

Info

Publication number
TWI792534B
TWI792534B TW110132998A TW110132998A TWI792534B TW I792534 B TWI792534 B TW I792534B TW 110132998 A TW110132998 A TW 110132998A TW 110132998 A TW110132998 A TW 110132998A TW I792534 B TWI792534 B TW I792534B
Authority
TW
Taiwan
Prior art keywords
pages
page
valid
cleaning
cleaned
Prior art date
Application number
TW110132998A
Other languages
English (en)
Other versions
TW202242664A (zh
Inventor
楊子逸
Original Assignee
慧榮科技股份有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 慧榮科技股份有限公司 filed Critical 慧榮科技股份有限公司
Publication of TW202242664A publication Critical patent/TW202242664A/zh
Application granted granted Critical
Publication of TWI792534B publication Critical patent/TWI792534B/zh

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
    • G06F13/14—Handling requests for interconnection or transfer
    • G06F13/16—Handling requests for interconnection or transfer for access to memory bus
    • G06F13/1605—Handling requests for interconnection or transfer for access to memory bus based on arbitration
    • G06F13/161—Handling requests for interconnection or transfer for access to memory bus based on arbitration with latency improvement
    • G06F13/1626—Handling requests for interconnection or transfer for access to memory bus based on arbitration with latency improvement by reordering requests
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0253—Garbage collection, i.e. reclamation of unreferenced memory
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0238—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
    • G06F12/0246—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory in block erasable memory, e.g. flash memory
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0877—Cache access modes
    • G06F12/0882—Page mode
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0891—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches using clearing, invalidating or resetting means
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
    • G06F13/14—Handling requests for interconnection or transfer
    • G06F13/16—Handling requests for interconnection or transfer for access to memory bus
    • G06F13/1668—Details of memory controller
    • G06F13/1673—Details of memory controller using buffers
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10—Providing a specific technical effect
    • G06F2212/1016—Performance improvement
    • G06F2212/1024—Latency reduction
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/72—Details relating to flash memory management
    • G06F2212/7201—Logical to physical mapping or translation of blocks or pages
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/72—Details relating to flash memory management
    • G06F2212/7204—Capacity control, e.g. partitioning, end-of-life degradation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/72—Details relating to flash memory management
    • G06F2212/7205—Cleaning, compaction, garbage collection, erase control
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/72—Details relating to flash memory management
    • G06F2212/7209—Validity control, e.g. using flags, time stamps or sequence numbers

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Memory System (AREA)
  • Memory System Of A Hierarchy Structure (AREA)

Abstract

一種對一來源區塊進行一垃圾回收操作的方法，包含：在一系列的主機寫入操作期間，進行複數個局部清理操作。每個局部清理操作包含：在該來源區塊的一分區搜尋範圍內執行一有效性檢查程序，以獲得一有效頁資訊；以及根據該有效頁資訊與一目標清理頁數量，執行一頁清理程序，以讀取該有效頁資訊所指出的一個或多個有效頁。

Description

以局部清理操作來進行垃圾回收的方法與相關控制器和儲存 系統
本發明關於快閃記憶體，尤指在快閃記憶體中執行垃圾回收操作的方法，以及相關控制器和儲存系統。
近來，基於NAND快閃記憶體的儲存設備被廣泛應用於各種範疇。與傳統硬碟相比，NAND快閃記憶體的優勢包括卓越的讀寫性能、抗震性、無噪音和更低的功耗。
由於快閃記憶體的特性，其不支援覆寫操作。當新資料需要替換已經儲存在快閃記憶體中的舊資料時，新資料將被寫入新位置，而舊位置上的資料便失效。因此，隨著對資料的重複覆寫，無效資料的數量將增加。為了確保有足夠的儲存區域可供資料儲存，需要抹除快閃記憶體中的無效資料。一般來說，快閃記憶體依靠垃圾回收(garbage collection)操作來釋放無效資料佔用的空間。
在垃圾回收操作期間，來源區塊的有效頁(即，具有有效資料的頁)被複製(其資料被讀出和寫入)到空白的目的區塊，然後將來源區塊抹除，以供重 新使用。通常，垃圾回收操作需要查詢位址轉換表(address translation table)，以確定來源區塊上哪些頁是有效的，哪些資料需要被複製到目的區塊中，這將耗費相當可觀的時間。另外，為了在快閃記憶體中保持足夠的儲存空間，垃圾回收操作還需要釋放一定量的儲存空間，來容納主機嘗試寫入的資料。由於有效頁不是連續且均勻地分佈在來源區塊上，因此垃圾回收操作可能會卡在從來源區塊中搜尋有效頁，並釋放所需的儲存空間的過程中，這可能導致顯著的系統延遲。在最壞的情況下，還這可能導致在時限到期前無法順利執行主機命令，從而嚴重降低平均系統性能。
有鑑於此，本發明的目的之一在於提供一種執行垃圾回收操作的方法和裝置。本發明實施例將垃圾回收操作劃分為多個局部清理操作，這些操作與主機寫入操作交錯地進行。在單次局部清理操作期間，僅檢查來源區塊的一部分的頁有效性，並讀取發現的有效頁資料。如果發現的有效頁數量低於預期，局部清理操作將提前結束，使得記憶體控制器不會卡在進行垃圾回收操作的過程中，而是轉而執行主機寫入操作。如此一來，本發明避免了主機寫入操作因搜尋有效頁而被延宕，導致系統性能下降的問題。
本發明的實施例提供一種對一來源區塊進行一垃圾回收操作的方法，該方法包含：在一系列的主機寫入操作期間，進行複數個局部清理操作。其中，每個局部清理操作包含：在該來源區塊的一分區搜尋範圍內執行一有效性檢查程序，以獲得一有效頁資訊；以及根據該有效頁資訊與一目標清理頁數量，執行一頁清理程序，以讀取該有效頁資訊所指出的一個或多個有效頁。
本發明的實施例提供一種用於控制一快閃記憶體並對該快閃記憶體上的一來源區塊進行一垃圾回收操作的控制器。該控制器包含：一儲存單元與一處理單元。該儲存單元用於儲存資訊。該處理單元用於執行一程序碼，並參考該快閃記憶體或該儲存單元中儲存的資訊，進行以下操作：在一系列的主機寫入操作期間，進行複數個局部清理操作。其中每個局部清理操作包含：在該來源區塊的一分區搜尋範圍內執行一有效性檢查程序，以獲得一有效頁資訊；以及根據該有效頁資訊與一目標清理頁數量，執行一頁清理程序，以讀取該有效頁資訊所指出的一個或多個有效頁。
本發明的實施例提供一種儲存系統，該儲存系統包含一快閃記憶體與一控制器。該控制器用於控制該快閃記憶體並對該快閃記憶體上的一來源區塊進行一垃圾回收操作。該控制器用於在一系列的主機寫入操作期間，進行複數個局部清理操作。其中，每個局部清理操作包含：在該來源區塊的一分區搜尋範圍內執行一有效性檢查程序，以獲得一有效頁資訊；以及根據該有效頁資訊與一目標清理頁數量，執行一頁清理程序，以讀取該有效頁資訊所指出的一個或多個有效頁。
10:電子裝置
50:主控裝置
52:處理器
54:隨機存取記憶體
100:儲存系統
120:NV記憶體
122_1~122_N:NV記憶體元件
110:記憶體控制器
112:微處理器
112M:唯讀記憶體
112C:程式碼
114:控制邏輯電路
116:隨機存取記憶體
118:傳輸介面電路
170:有效性位元映射硬體引擎
201、205、210~250:步驟
第1圖繪示本發明實施例的儲存系統的架構示意圖。
第2圖繪示在本發明實施例中如何執行垃圾回收操作。
第3圖繪示本發明實施例中單次局部頁清理操作的流程圖。
第4圖~第6圖繪示在不同的有效頁分布下，有效性檢查程序和頁清理程序之間的關聯。
第7圖繪示本發明實施例中實現有效性檢查程序的硬體架構。
第8圖繪示本發明另一實施例中單次局部頁清理操作的流程圖。
在以下內文中，描述了許多具體細節以提供閱讀者對本發明實施例的透徹理解。然而，本領域的技術人士將能理解，如何在缺少一個或多個具體細節的情況下，或者利用其他方法或元件或材料等來實現本發明。在其他情況下，眾所皆知的結構、材料或操作不會被示出或詳細描述，從而避免模糊本發明的核心概念。
說明書中提到的「一實施例」意味著該實施例所描述的特定特徵、結構或特性可能被包含於本發明的至少一個實施例中。因此，本說明書中各處出現的「在一實施例中」不一定意味著同一個實施例。此外，前述的特定特徵、結構或特性可以以任何合適的形式在一個或多個實施例中結合。
第1圖為本發明實施例之電子裝置10的架構示意圖。如圖所示，電子裝置10包含主控裝置(host device)50與儲存系統100。主控裝置50可包含：一隨機存取記憶體(random access memory,RAM)54與至少一處理器52，用來控制主控裝置50之運作。在不同實施例中，主控裝置50可以是(但不限於)：智慧型手機、平板電腦、可穿戴裝置、個人電腦、筆記型電腦、數位相機、數位錄影機、遊戲主機、車用導航系統、印表機、掃描器或者伺服器。另外，在不同實施例中，儲存系統100可以是(但不限於)：可攜式儲存裝置(如符合SD/MMC、CF、MS、XD或UFS標準之記憶卡)、固態硬碟(solid state drive,SSD)以及各種嵌入式(embedded)儲存裝置(如符合UFS或EMMC規格之嵌入式儲存裝置)。
在本發明的各種實施例中，儲存系統100可以包含如記憶體控制器110之類的控制器，並且還可以包括非揮發性(non-volatile,NV)記憶體120。NV記憶體120用於儲存資訊。NV記憶體120可以包括一個或多個NV記憶體元件，例如，多個NV記憶體元件122_1~122_N。再者，NV記憶體120可以是快閃記憶體，並且NV記憶體元件122_1~122_N可以分別是多個快閃記憶體晶片或多個快閃記憶體裸晶，但本發明不限於此。另外，NV記憶體120可以包含具有二維結構的記憶體單元(memory cells)，或者可以包含具有三維結構的記憶體單元。
如第1圖所示，記憶體控制器110可以包含如微處理器112之類的處理電路、唯讀記憶體(read-only memory,ROM)112M之類的儲存元件、控制邏輯電路114、揮發性記憶體116、傳輸介面電路118以及一選擇性的有效性位元映射引擎(validity bitmap engine)170。其中，這些元件的至少一部分(例如，一部分或全部)可以透過匯流排彼此互連。揮發性記憶體116由隨機存取記憶體(random-access memory,RAM)實現。例如，揮發性記憶體116可以是靜態RAM(static RAM,SRAM)。揮發性記憶體116可以用於向記憶體控制器110提供內部儲存空間，例如，暫時性地儲存資訊。另外，本實施例的ROM 112M用於儲存程式碼112C，而微處理器112用於執行程式碼112C，從而控制對NV記憶體120的存取。在另一個實施例中，程式碼112C可以被儲存在NV記憶體120中。
記憶體控制器110透過控制邏輯電路114控制NV記憶體120的讀取、寫入和抹除。此外，記憶體控制器110可以同時基於來自主控裝置50的主機命令，執行使用者資料的寫入，並且藉由垃圾回收操作或耗損平衡(wear-leveling)操作從NV記憶體120中蒐集有效資料，執行有效資料的寫入。控制邏輯電路114 可以進一步用於控制NV記憶體120，其包含錯誤校正(error correction code,ECC)電路(未示出)，以執行資料保護和/或校正，但是本發明不限於此。傳輸介面電路118符合特定的資料傳輸規範(例如，序列進階技術附加裝置(Serial Advanced Technology Attachment,SATA)規範、通用序列匯流排(Universal Serial Bus,USB)規範、快捷外設互聯標準((Peripheral Component Interconnect Express,PCIE)規範、嵌入式多媒體卡(Embedded Multimedia Card,eMMC)規範、或通用快閃記憶體儲存(Universal Flash Storage,UFS)規範，並可以根據特定的通信規範與主控裝置50進行通訊。
一般來說，主控裝置50可以透過向記憶體控制器110發送主機命令和相應的邏輯位址來間接存取儲存系統100。記憶體控制器110接收主機命令和邏輯位址，將主機命令轉換為記憶體操作命令，並且進一步用記憶體操作命令控制NV記憶體120，從而對NV記憶體120內具有特定物理位址的記憶體單元(memory cells)或頁(pages)，執行讀、寫或抹除操作，其中物理位址對應於邏輯位址。當記憶體控制器110對NV記憶體元件122_1~122_N內的任何NV記憶體元件122_k執行抹除操作時，NV記憶體元件122_k中的至少一個區塊(block)可以被抹除。另外，NV記憶體元件122_k的每個區塊可以包括多個頁，並且可以在一個或多個頁上執行存取操作(例如，讀取或寫入)。
在本發明中，垃圾回收(garbage collection,GC)操作可以透過由記憶體控制器110所驅動的多個局部清理(partial clean)操作來實現，並且這些局部清理操作可以分散到不同的時槽(time slot)。局部清理操作可以與基於主控裝置50發送的主機命令所導致的一系列讀取或寫入操作，交錯地進行。在單次局部清理操作期間，記憶體控制器110可以辨識一個來源區塊的一部分分頁的有效頁， 並讀出被辨識為有效頁上的資料。在執行幾次局部清理操作，並將來源區塊中所有有效頁上的資料複製到新的目的區塊後，來源區塊便可以被抹除和再次使用。此時，GC操作完成。
第2圖繪示本發明實施例如何執行GC操作。如圖所示，每個局部清理操作包含兩個子程序(sub-process)，一個是有效性檢查(validity check)程序，另一個是頁清理(page clean)程序。在有效性檢查程序中，將在來源區塊的一分區搜尋範圍ScanP內，檢查每個頁的有效性，從而建立關於分區搜尋範圍ScanP內的有效頁資訊，其中有效頁資訊指出哪些頁是有效的。在有效性檢查程序中，記憶體控制器110將查詢主機至快閃記憶體(host-to-flash,H2F)位址轉換表，以及快閃記憶體至主機(flash-to-host,F2H)位址轉換表，以確認哪一個頁是有效的。具體來說，記憶體控制器110首先將與分區搜尋範圍ScanP相關聯的一部分F2H位址轉換表載入到主控裝置50的記憶體54或記憶體控制器110自身的記憶體116。基於所載入的F2H位址轉換表的部分，記憶體控制器110可以得到待檢查的頁被映射到哪個邏輯位址。據此，記憶體控制器110再查詢H2F位址轉換表，以將待檢查的頁的邏輯位址轉換為物理位址。如果該物理位址屬於待檢查的頁，則確認待檢查的頁有效。如果不是，則表示待檢查的頁的邏輯位址還被映射到另一個頁，故待檢查的頁為無效。
透過有效性檢查程序所獲得的有效頁資訊可以被記錄到，主控裝置50的記憶體54或記憶體控制器110自身的記憶體116所保存的有效性位元映射表(validity bitmap)中，其使用一位元來指出一頁的有效性。或者，有效頁資訊可以記錄到在記憶體54或記憶體116中額外配置的先進先出(first in-first out,FIFO)緩衝器中，FIFO緩衝器的項目(entry)記錄有效頁的位址。一個來源區塊中所有頁的 有效性，可透過對該來源區塊的多個連續分區搜尋範圍ScanP，執行有效性檢查程序後來決定。例如，假設一個來源區塊由10000個頁組成，每個分區搜尋範圍ScanP劃分來源區塊中的400個連續頁。因此，經過25次有效性檢查程序後，便可確認來源區塊上所有頁的有效性。
一旦完成有效性檢查程序(即，分區搜尋範圍ScanP內所有頁的有效性已檢查)，頁清理程序開始。在頁清理程序中，將讀取有效頁資訊所指出的有效頁上的資料。記憶體控制器110將讀出在有效性檢查程序中已發現並且被確認的有效頁。根據本發明不同實施例，當有效頁的資料被讀出後，頁清理程序可以結束。又或者是，當有效頁的資料已被寫入到新的目的區塊中的頁時，頁清理程序才結束。
記憶體控制器110憑藉指標SearchPtr來追踪有效性檢查的進度。指標SearchPtr指向有效性正在被檢查的頁的位址。一旦有效性檢查程序結束，指標SearchPtr將有效性已被檢查的最後一頁的位址。稍後，將使用指標SearchPtr指向的頁，做為新的有效性檢查程序所檢查的第一個頁。此外，記憶體控制器110憑藉指標CleanPtr來追踪頁清理的進度。指標CleanPtr指向資料正在被讀取的有效頁的位址。一旦頁清理程序結束，指標CleanPtr儲存資料已被讀取的最後一個有效頁的位址。稍後，將使用指標CleanPtr指向的頁，做為新的頁清理程序所讀取的第一個頁。
為了初始化GC操作，記憶體控制器110首先需要確定主機對GC操作的寫入比例。主機對GC操作的寫入比例表示，在特定時間內，基於主控裝置50所發送的主機命令要求寫入的使用者資料的寫入量，與基於GC操作的有效資料 寫入量的比例。主機對GC操作的寫入比例反映了GC操作需要移動多少有效資料(即，需要釋放NV記憶體120中多少儲存空間)，才能平衡主機命令引發的寫入(其將佔用NV記憶體120的儲存空間)，從而在NV記憶體120中保有一定數量的空閒區塊。根據主機對GC操作的寫入比例，記憶體控制器110可以決定一目標清理頁數量C，它表示有多少有效頁需要在每次頁清理程序中被讀取或複製，以滿足主機對GC操作的寫入比例。假設一來源區塊的有效頁總數為SrcVP，且該來源區塊的頁總數為BlkP，則讀出該來源區塊中所有有效頁需要進行的局部清理操作的次數為：(SrcVP/C)。並且，每一次局部清理操作中的有效性檢查程序的分區搜尋範圍ScanP將為：BlkP/(ScrVP/C)，其中分區搜尋範圍ScanP表示在一個有效性檢查程序中，來源區塊中需要被檢查的頁數。
由於有效頁不是連續且均勻地分布在來源區塊上，因此在單一次有效性檢查程序中，記憶體控制器110可能無法找到與目標清理頁數量C所要求的一樣多的有效頁。例如，當前分區搜尋範圍ScanP內的有效頁數量低於預期，導致頁清理程序讀取不到有效頁，或者是讀取到的有效頁數量很少。如此，代表了在每個頁清理程序中實際讀取了多少頁的實際清理頁數量CleanVP，將會有很大的變動。基於有效頁在來源區塊上的分布情況，實際清理頁數量CleanVP可能小於目標清理頁數量C。在這種情況下，一旦指標CleanPtr與指標SearchPtr相同，則頁清理程序將結束。這是因為已被發現並且確認的有效頁都已被頁清理程序所讀取。因此，只能預期後續的頁清理程序可以讀取到更多有效頁。有鑑於此，接下來的頁清理程序需要讀取的有效頁數將變為(RemainVP+C)，其中“RemainVP”為剩餘清理頁數量，其代表目標清理頁數量中有多少個頁到目前為止還沒有被讀取。如果實際清理頁數量CleanVP持續低於目標清理頁數量C，則剩餘清理頁數量RemainVP將被累加。例如，如果目標清理頁數量C指出，每個 頁清理程序需要清理出30個頁，並且在一第一局部清理操作的有效性檢查程序中，僅在其對應的分區搜尋範圍ScanP內發現且確認14個有效頁，則這意味著該第一局部清理操作的頁清理程序只能讀取到14個有效頁。因此，在該第一局部清理操作結束之後，剩餘清理頁數量RemainVP便是16個頁(即，30-14=16)。有鑑於此，一第二局部清理操作中的頁清理程序便需要讀取46個有效頁(即，RemainVP(16)+C(30)=46)。但是，如果該第二局部清理操作的有效性檢查頁程序僅在其對應的分區搜尋範圍ScanP內，發現且確認13個有效頁，則這意味著該第二局部清理操作中的頁清理程序只能讀取到13個有效頁。因此，在該第二次局部清理操作結束後，剩餘清理頁數RemainVP便是63個頁(即，RemainVP(46)+C(30)-CleanVP(13)=63)。有鑑於此，一第三局部清理操作中的頁清理程序需要讀取93個有效頁(即，63+30=93)。由以上描述可知，在局部清理操作完成後，剩餘清理頁數量RemainVP將透過：(RemainVP+C)-CleanVP的計算而進行更新。另一方面，如果有效頁集中分布在當前的分區搜尋範圍ScanP內，則記憶體控制器110可能足以找到與目標清理頁數量C和剩餘清理頁數量RemainVP之總和一樣多的有效頁。在此情況下，一旦記憶體控制器110所讀取的有效頁數量達到：(RemainVP+C)，則頁清理程序將結束。
請參考第3圖，其繪示出本發明實施例的執行單一局部清理操作的流程圖。如圖所示，該流程包括以下步驟：
步驟210：基於指標SearchPtr，在一來源區塊的一分區搜尋範圍內進行一有效性檢查程序，從而得到有效頁資訊；
步驟220：基於指標CleanPtr，根據該有效頁資訊進行一頁清理程序，從而讀取該有效頁資訊所指出的有效頁。
步驟230：判斷實際清理頁數量CleanVP是否低於目標清理頁數量C 與剩餘清理頁數量RemainVP的總和。
步驟240：設定剩餘清理頁數量RemainVP為：C+RemainVP-CleanVP。
步驟250：設定剩餘清理頁數量RemainVP為0。
在步驟210中，在一來源區塊的一分區搜尋範圍ScanP內執行一有效性檢查程序，以獲得有效頁資訊。如上所述，來源區塊的分區搜尋範圍ScanP是根據來源區塊的目標清理頁數量C、有效頁總數SrcVP和頁總數BlkP來確定的。在步驟220，根據該有效性檢查程序中獲得的有效頁資訊進行一頁清理程序。如果記憶體控制器110讀取到的有效頁數，與剩餘清理頁數量RemainVP和目標清理頁數量C之總和(即，C+RemainVP)一樣多，則該頁清理程序結束。又或者，當指標CleanPtr追上指標SearchPtr時，頁清理程序也會結束，這意味著已確認的有效頁數量可能不足。在完成該頁清理程序後，流程進入步驟230。在步驟230中，檢查實際清理頁數量CleanVP(即，記憶體控制器110實際讀取的有效頁的數量)是否小於(C+RemainVP)個頁。如果是，這意味著已確認的有效頁數量不足，記憶體控制器110將在隨後的頁清理程序中，嘗試讀取更多的有效頁。之後，流程進入步驟240，將剩餘清理頁數量設定成C+RemainVP-CleanVP。若步驟230的檢查結果為否，則表示在該有效性檢查程序中所確認的有效頁足以供記憶體控制器110進行讀取，並滿足主機對GC操作的寫入比例。據此，流程進入步驟250，剩餘清理頁數量RemainVP將被設定成0。
第4圖~第6圖繪示在不同有效頁分布情況下，有效性檢查程序和頁清理程序之間的關聯。在第4圖所示的第一種情況下，有效頁主要分布在來源區塊(或者是一超級來源區塊(super source block))的末端。所以在操作之初，每一次局部清理操作中的頁清理程序都無法讀取到足夠的有效頁(即，實際清理頁 數量CleanVP持續低於目標清理頁數量C)。如此一來，在大多數情況下，指標CleanPtr與指標SearchPtr非常接近。據此，剩餘清理頁數量RemainVP將不斷增加。
在第5圖所示的第二種情況中，有效頁主要分布在來源區塊的開頭。有鑑於此，每次局部清理操作中的頁清理程序將無法完全讀取出，在分區搜尋範圍ScanP內已發現且確認的所有有效頁(即，分區搜尋範圍ScanP內找到的有效頁數量明顯高於RemainVP+C)。如此，指標CleanPtr將在一開始落後指標SearchPtr。而一旦頁清理程序朝向不包含任何有效頁，或僅包含很少有效頁的來源區塊範圍中移動時，指標CleanPtr將逐漸追上指標SearchPtr。當指標CleanPtr追上指標SearchPtr後，剩餘清理頁數量RemainVP開始增加。
在第6圖所示的第三種情況中，有效頁均勻第分佈在來源區塊上。因此，指標CleanPtr可能會落後或追上指標SearchPtr。當指標CleanPtr落後於指標SearchPtr時，剩餘清理頁數量RemainVP逐漸增加。當指標CleanPtr趕上指標SearchPtr時，剩餘清理頁數量RemainVP逐漸減少至零。
第7圖繪示了本發明實施例中，有效性檢查程序的硬體實施架構。在一個實施例中，微處理器112可以在具備多個處理器核心的多核心處理器112上實現。每個處理器核心可包含用於儲存全局或局部變量的資料記憶體、用於儲存程式碼的指令記憶體，以及處理單元。在操作期間，微處理器112可以分配一個或多個處理器核心來運作快閃記憶體轉換層(flash translation layer,FTL)相關的執行緒(thread)，以進行關於位址映射、垃圾回收和耗損平衡等操作。例如，可以在一個或多個處理器核心上，執行前述的局部清理操作。又或者是，可以 在一個處理器核心上，運作關於有效性檢查程序的執行緒，同時在另一個處理器核心上，運作關於頁清理程序的執行緒。在部分實施例中，記憶體控制器110還可能包含專用硬體，即有效性位元映射硬體引擎170，以執行有效性檢查程序。有效性位元映射硬體引擎170可透過查詢F2H和H2F位址轉換表，檢查分區搜尋範圍內的頁有效性，並且如上所述將有效頁資訊儲存在緩衝器中。
第8圖繪示了在本發明另一實施例中的進行局部清理操作的流程。如圖所示，在微處理器112的處理器核心上運作的FTL執行緒，可以發起局部清理操作。在步驟201，FTL執行緒可以將有效性檢查程序的任務，作為一個新任務(如步驟205)，指派給微處理器112內部的另一個處理器核心或者是有效性位元映射硬體引擎170，從而逐頁進行有效性檢查，以獲得有效頁資訊，供FTL執行緒進行頁清理程序。
在以上實施例中，局部清理操作和相應的有效性檢查程序以及頁清理程序被描述為應用在NV記憶體120的頁與區塊。然而，根據本發明不同各種實施例，本發明也可以針對NV記憶體120的超級頁(super page)和超級區塊(super block)進行局部清理操作，以及相應的有效性檢查程序與頁清理程序。其中，一個超級頁可以由不同NV記憶體元件122_1~122_N上的數個頁所組成，而一個超級區塊可能由不同NV記憶體元件122_1~122_N上的數個區塊所組成。此外，記憶體控制器110可以同時對不同的NV記憶體元件122_1~122_N分別進行多個局部清理操作。因此，不同NV記憶體元件122_1~122_N上的有效性檢查程序和頁清理程序可以分別具有不同的進度。
總結來說，本發明提供了一種進行垃圾回收操作的方法。本發明的 實施例以多次局部清理操作來實現垃圾回收操作。這些局部清理操作與主機寫入操作交錯地進行。在每次局部清理操作中，執行有效性檢查程序以檢查來源區塊中的部分頁的有效性，並且執行頁清理程序以讀取在有效性檢查程序中被發現且確認的有效頁的資料。另外，本發明也允許頁清理程序的進度與有效性檢查程序的進度不同。並且，當已發現且確認的有效頁數量低於預期(即，有效頁數低於(RemainVP+C))，則結束局部清理操作，使得記憶體控制器不會卡在垃圾回收操作上，而是轉而進行主機寫入操作。並期待有效性檢查程序能夠在下一個分區搜尋範圍內，發現更多的有效頁，從而彌補有效頁的匱乏。有鑑於此，本發明避免了主機寫入操作因尋找有效頁而延遲，導致系統性能下降的問題。
本發明之實施例可使用硬體、軟體、韌體以及其相關結合來完成。藉由適當之一指令執行系統，可使用儲存於一記憶體中之軟體或韌體來實作本發明的實施例。就硬體而言，則是可應用下列任一技術或其相關結合來完成：具有可根據資料信號執行邏輯功能之邏輯閘的一個別運算邏輯、具有合適的組合邏輯閘之一特定應用積體電路(application specific integrated circuit,ASIC)、可程式閘陣列(programmable gate array,PGA)或一現場可程式閘陣列(field programmable gate array,FPGA)等。
說明書內的流程圖中的流程和方塊示出了基於本發明的各種實施例的系統、方法和電腦軟體產品所能實現的架構，功能和操作。在這方面，流程圖或功能方塊圖中的每個方塊可以代表程式碼的模組，區段或者是部分，其包括用於實現指定的邏輯功能的一個或多個可執行指令。另外，功能方塊圖以及/或流程圖中的每個方塊，以及方塊的組合，基本上可以由執行指定功能或動作 的專用硬體系統來實現，或專用硬體和電腦程式指令的組合來實現。這些電腦程式指令還可以存儲在電腦可讀媒體中，該媒體可以使電腦或其他可編程數據處理裝置以特定方式工作，使得存儲在電腦可讀媒體中的指令，實現流程圖以及/或功能方塊圖中的方塊所指定的功能/動作。
以上所述僅為本發明之較佳實施例，凡依本發明申請專利範圍所做之均等變化與修飾，皆應屬本發明之涵蓋範圍。
210~250:步驟

Claims (15)

  1. 一種對一來源區塊進行一垃圾回收操作的方法，包含：在一系列的主機寫入操作期間，進行複數個局部清理操作，每個局部清理操作包含：在該來源區塊的一分區搜尋範圍內執行一有效性檢查程序，以獲得一有效頁資訊；根據該有效頁資訊與一目標清理頁數量，執行一頁清理程序，以讀取該有效頁資訊所指出的一個或多個有效頁；決定一主機對垃圾回收操作的寫入比例，其代表基於主機命令的使用者資料的一寫入量與基於該垃圾回收操作的有效資料的一寫入量之間的比例；根據該主機對垃圾回收操作的寫入比例，決定該目標清理頁數量；以及根據該目標清理頁數量、該來源區塊的一頁總數、該來源區塊的一有效頁總數，決定該分區搜尋範圍；其中，針對該來源區塊的垃圾回收操作會在多個階段中執行，每個階段中會執行一次局部清理操作；該分區搜尋範圍界定了每個階段中需要被檢查的連續頁的預定範圍，以及該目標清理頁數量為每個階段中資料被讀出的頁的預期數量。
  2. 如請求項1所述的方法，其中執行該有效性檢查程序的步驟包含：將該分區搜尋範圍內每個頁的有效性，記錄到一有效性位元映射表(validity bitmap)中。
  3. 如請求項1所述的方法，其中執行該有效性檢查程序的步驟包含：將該分區搜尋範圍內每個有效頁的位址，記錄到一先進先出(first in-first out,FIFO)緩衝器中。
  4. 如請求項1所述的方法，其中執行該頁清理程序的步驟包含：如果在該頁清理程序中所讀取到的有效頁數量，與該目標清理頁數量和一剩餘清理頁數量兩者的總和相同，則結束該頁清理程序。
  5. 如請求項4所述的方法，另包含：在該頁清理程序結束後，將該剩餘清理頁數量更新成零。
  6. 如請求項1所述的方法，其中執行該頁清理程序的步驟包含：如果在該頁清理程序中所讀取到的有效頁數量，小於該目標清理頁數量和一剩餘清理頁數量兩者的總和，並且該分區搜尋範圍內的所有有效頁皆已被讀取，則結束該頁清理程序。
  7. 如請求項6所述的方法，另包含：在該頁清理程序結束後，根據該剩餘清理頁數量、該目標清理頁數量，以及在已結束的該頁清理程序中所讀取的有效頁數，更新該剩餘清理頁數量。
  8. 一種用於控制一快閃記憶體並對該快閃記憶體上的一來源區塊進行一垃圾回收操作的控制器，包含：一儲存單元，用於儲存資訊；以及 一處理單元，用於執行一程序碼，並參考該快閃記憶體或該儲存單元中儲存的資訊，進行以下操作：在一系列的主機寫入操作期間，進行複數個局部清理操作，每個局部清理操作包含：在該來源區塊的一分區搜尋範圍內執行一有效性檢查程序，以獲得一有效頁資訊；根據該有效頁資訊與一目標清理頁數量，執行一頁清理程序，以讀取該有效頁資訊所指出的一個或多個有效頁；決定一主機對垃圾回收操作的寫入比例，其代表基於主機命令的使用者資料的一寫入量與基於該垃圾回收操作的有效資料的一寫入量之間的比例；根據該主機對垃圾回收操作的寫入比例，決定該目標清理頁數量；以及根據該目標清理頁數量、該來源區塊的一頁總數、該來源區塊的一有效頁總數，決定該分區搜尋範圍；其中，針對該來源區塊的垃圾回收操作會在多個階段中執行，每個階段中會執行一次局部清理操作；該分區搜尋範圍界定了每個階段中需要被檢查的連續頁的預定範圍，以及該目標清理頁數量為每個階段中資料被讀出的頁的預期數量。
  9. 如請求項8所述的控制器，其中該處理單元執行該程式碼以進行以下操作：將該分區搜尋範圍內每個頁的有效性，記錄到一有效性位元映射表(validity bitmap)中。
  10. 如請求項8所述的控制器，其中該處理單元執行該程式碼以進行以下操作：將該分區搜尋範圍內每個有效頁的位址，記錄到一先進先出(first in-first out,FIFO)緩衝器中。
  11. 如請求項8所述的控制器，其中該處理單元執行該程式碼以進行以下操作：如果在該頁清理程序中所讀取到的有效頁數量，與該目標清理頁數量和一剩餘清理頁數量兩者的總和相同，則結束該頁清理程序。
  12. 如請求項11所述的控制器，其中該處理單元執行該程式碼以進行以下操作：在該頁清理程序結束後，將該剩餘清理頁數量更新成零。
  13. 如請求項8所述的控制器，其中該處理單元執行該程式碼以進行以下操作：如果在該頁清理程序中所讀取到的有效頁數量，小於該目標清理頁數量和一剩餘清理頁數量兩者的總和，並且該分區搜尋範圍內的所有有效頁皆已被讀取，則結束該頁清理程序。
  14. 如請求項13所述的控制器，其中該處理單元執行該程式碼以進行以下操作：在該頁清理程序結束後，根據該剩餘清理頁數量、該目標清理頁數量，以 及在已結束的該頁清理程序中所讀取的有效頁數，更新該剩餘清理頁數量。
  15. 一種儲存系統，包含：一快閃記憶體；以及一控制器，用於控制該快閃記憶體並對該快閃記憶體上的一來源區塊進行一垃圾回收操作，該控制器用於：在一系列的主機寫入操作期間，進行複數個局部清理操作，每個局部清理操作包含：在該來源區塊的一分區搜尋範圍內執行一有效性檢查程序，以獲得一有效頁資訊；根據該有效頁資訊與一目標清理頁數量，執行一頁清理程序，以讀取該有效頁資訊所指出的一個或多個有效頁；決定一主機對垃圾回收操作的寫入比例，其代表基於主機命令的使用者資料的一寫入量與基於該垃圾回收操作的有效資料的一寫入量之間的比例；根據該主機對垃圾回收操作的寫入比例，決定該目標清理頁數量；以及根據該目標清理頁數量、該來源區塊的一頁總數、該來源區塊的一有效頁總數，決定該分區搜尋範圍；其中，針對該來源區塊的垃圾回收操作會在多個階段中執行，每個階段中會執行一次局部清理操作；該分區搜尋範圍界定了每個階段中需要被檢查的連續頁的預定範圍，以及該目標清理頁數量為每個階段中資料被讀出的頁的預期數量。
TW110132998A 2021-04-25 2021-09-06 以局部清理操作來進行垃圾回收的方法與相關控制器和儲存系統 TWI792534B (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US17/239,669 2021-04-25
US17/239,669 US11580018B2 (en) 2021-04-25 2021-04-25 Method and apparatus for page validity management and related storage system

Publications (2)

Publication Number Publication Date
TW202242664A TW202242664A (zh) 2022-11-01
TWI792534B true TWI792534B (zh) 2023-02-11

Family

ID=83668240

Family Applications (1)

Application Number Title Priority Date Filing Date
TW110132998A TWI792534B (zh) 2021-04-25 2021-09-06 以局部清理操作來進行垃圾回收的方法與相關控制器和儲存系統

Country Status (3)

Country Link
US (1) US11580018B2 (zh)
CN (1) CN115237820A (zh)
TW (1) TWI792534B (zh)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12019878B2 (en) * 2021-11-22 2024-06-25 Western Digital Technologies, Inc. Pre-validation of blocks for garbage collection
KR20230094262A (ko) * 2021-12-21 2023-06-28 삼성전자주식회사 비휘발성 메모리를 포함하는 메모리 저장 장치 및 전자 장치
CN119669103A (zh) * 2024-10-17 2025-03-21 深圳三地一芯电子股份有限公司 垃圾回收方法、装置、存储控制芯片及存储介质

Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20140101372A1 (en) * 2012-10-05 2014-04-10 Young Woo Jung Memory system and read reclaim method thereof
US8782327B1 (en) * 2010-05-11 2014-07-15 Western Digital Technologies, Inc. System and method for managing execution of internal commands and host commands in a solid-state memory
US20160092122A1 (en) * 2014-09-30 2016-03-31 Sandisk Technologies Inc. Method and apparatus for wear-levelling non-volatile memory
TWI548989B (zh) * 2014-03-19 2016-09-11 宏達國際電子股份有限公司 行動電子裝置與清理記憶區塊的方法
US9645924B2 (en) * 2013-12-16 2017-05-09 International Business Machines Corporation Garbage collection scaling
CN108139968A (zh) * 2015-10-19 2018-06-08 华为技术有限公司 确定垃圾收集器线程数量及活动管理的方法及设备
US20190196966A1 (en) * 2017-12-22 2019-06-27 Samsung Electronics Co., Ltd. Storage device performing garbage collection and garbage collection method of storage device
CN110580228A (zh) * 2018-06-11 2019-12-17 北京忆恒创源科技有限公司 去分配命令处理方法及其存储设备
US10754769B2 (en) * 2009-06-12 2020-08-25 Violin Systems Llc Memory system having persistent garbage collection
US20200379861A1 (en) * 2019-05-31 2020-12-03 SK Hynix Inc. Controller and operation method thereof

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2016135954A1 (ja) * 2015-02-27 2016-09-01 株式会社日立製作所 ストレージ装置および不揮発メモリデバイス

Patent Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10754769B2 (en) * 2009-06-12 2020-08-25 Violin Systems Llc Memory system having persistent garbage collection
US8782327B1 (en) * 2010-05-11 2014-07-15 Western Digital Technologies, Inc. System and method for managing execution of internal commands and host commands in a solid-state memory
US20140101372A1 (en) * 2012-10-05 2014-04-10 Young Woo Jung Memory system and read reclaim method thereof
US9645924B2 (en) * 2013-12-16 2017-05-09 International Business Machines Corporation Garbage collection scaling
TWI548989B (zh) * 2014-03-19 2016-09-11 宏達國際電子股份有限公司 行動電子裝置與清理記憶區塊的方法
US20160092122A1 (en) * 2014-09-30 2016-03-31 Sandisk Technologies Inc. Method and apparatus for wear-levelling non-volatile memory
CN108139968A (zh) * 2015-10-19 2018-06-08 华为技术有限公司 确定垃圾收集器线程数量及活动管理的方法及设备
US20190196966A1 (en) * 2017-12-22 2019-06-27 Samsung Electronics Co., Ltd. Storage device performing garbage collection and garbage collection method of storage device
CN110580228A (zh) * 2018-06-11 2019-12-17 北京忆恒创源科技有限公司 去分配命令处理方法及其存储设备
US20200379861A1 (en) * 2019-05-31 2020-12-03 SK Hynix Inc. Controller and operation method thereof

Also Published As

Publication number Publication date
US11580018B2 (en) 2023-02-14
CN115237820A (zh) 2022-10-25
TW202242664A (zh) 2022-11-01
US20220342811A1 (en) 2022-10-27

Similar Documents

Publication Publication Date Title
TWI409633B (zh) 快閃記憶體儲存裝置、其控制器與資料寫入方法
TWI797742B (zh) 在快閃記憶體中進行耗損平衡操作的方法和相關控制器以及儲存系統
TWI569139B (zh) 有效資料合併方法、記憶體控制器與記憶體儲存裝置
TWI479313B (zh) 資料寫入方法、記憶體控制器與記憶體儲存裝置
CN110989918B (zh) 写入控制方法以及数据存储装置及其控制器
TWI792534B (zh) 以局部清理操作來進行垃圾回收的方法與相關控制器和儲存系統
CN107608908A (zh) 用于数据储存装置的磨损平均方法
CN111444030B (zh) 数据储存装置及避免固件失效的方法
TW201706847A (zh) 映射表格更新方法、記憶體儲存裝置及記憶體控制電路單元
TWI430091B (zh) Semiconductor memory device
US11204864B2 (en) Data storage devices and data processing methods for improving the accessing performance of the data storage devices
TWI698749B (zh) 資料儲存裝置與資料處理方法
TWI709975B (zh) 寫入控制方法以及資料儲存裝置及其控制器
TWI421870B (zh) 用於快閃記憶體的資料寫入方法及其控制器與儲存系統
CN111338562A (zh) 数据存储装置与数据处理方法
JP2025041665A (ja) メモリデバイスのデフラグメンテーションのためのシステムおよび方法
CN108628760B (zh) 原子写命令的方法与装置
CN108628761B (zh) 原子命令执行方法与装置
CN112099731B (zh) 数据储存装置与数据处理方法
WO2024250268A1 (en) Memory controller, memory system managing logical-to-physical mapping table, method, and storage medium thereof
CN120196558B (zh) 映射表垃圾回收方法、回收装置、存储装置和电子设备
CN105825082A (zh) 数据储存装置以及快闪存储器控制方法
US20250123959A1 (en) Memory controllers and operation methods thereof and memory systems
CN117950573A (zh) 数据储存装置与写入缓存器管理方法