[go: up one dir, main page]

TW201835922A - 資料儲存裝置以及其操作方法 - Google Patents

資料儲存裝置以及其操作方法 Download PDF

Info

Publication number
TW201835922A
TW201835922A TW106110108A TW106110108A TW201835922A TW 201835922 A TW201835922 A TW 201835922A TW 106110108 A TW106110108 A TW 106110108A TW 106110108 A TW106110108 A TW 106110108A TW 201835922 A TW201835922 A TW 201835922A
Authority
TW
Taiwan
Prior art keywords
block
data
physical
physical block
storage device
Prior art date
Application number
TW106110108A
Other languages
English (en)
Other versions
TWI613652B (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 慧榮科技股份有限公司
Priority to TW106110108A priority Critical patent/TWI613652B/zh
Priority to US15/802,130 priority patent/US20180275887A1/en
Priority to CN201810039463.7A priority patent/CN108664418A/zh
Application granted granted Critical
Publication of TWI613652B publication Critical patent/TWI613652B/zh
Publication of TW201835922A publication Critical patent/TW201835922A/zh

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0608—Saving storage space on storage systems
    • 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/10—Address translation
    • G06F12/1009—Address translation using page tables, e.g. page table structures
    • 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/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
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0638—Organizing or formatting or addressing of data
    • G06F3/064—Management of blocks
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0646—Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
    • G06F3/0652—Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0673—Single storage device
    • 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/1041—Resource optimization
    • G06F2212/1044—Space efficiency improvement
    • 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/7205—Cleaning, compaction, garbage collection, erase control

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Techniques For Improving Reliability Of Storages (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

一種高可靠度的資料儲存裝置。重建一映射表時，所述技術根據一第一物理區塊內的一有效性列表區分該第一物理區塊的一第一資料以及一第二物理區塊的一第二資料何者為較新版本。該第一物理區塊前身為垃圾回收的目的區塊。該第二物理區塊前身為供主機寫入資料的主動區塊。該有效性列表標示該第一物理區塊各儲存單元有效與否。上述第一資料以及第二資料皆關於同一邏輯位址。

Description

資料儲存裝置以及其操作方法
本發明係有關於資料儲存裝置，特別有關於資料儲存裝置之映射表重建技術。
資料儲存裝置所採用的非揮發性記憶體有多種形式一例如，快閃記憶體(flash memory)、磁阻式隨機存取記憶體(Magnetoresistive RAM)、鐵電隨機存取記憶體(Ferroelectric RAM)、電阻式隨機存取記憶體(Resistive RAM)、自旋轉移力矩隨機存取記憶體(Spin Transfer Torque-RAM，STT-RAM)…等，用於長時間資料保存。
非揮發式記憶體之使用狀況需要以映射表管理。映射表顯示主機端邏輯位址以及非揮發式記憶體端物理空間的映射關係。如何維護映射表為本技術領域一項重要課題。特別是，因應映射表毀壞甚至掉失的狀況，本領域需要一種準確重建映射表的技術。
根據本案一種實施方式提供的一資料儲存裝置包括一非揮發式記憶體以及一微控制器。該非揮發式記憶體包括複數個物理區塊。該微控制器在掃瞄該非揮發式記憶體以重建一主機至該非揮發式記憶體的一映射表時，根據一第一物理區 塊內的一有效性列表區分該第一物理區塊的一第一資料以及一第二物理區塊的一第二資料何者為較新版本。該第一物理區塊前身為垃圾回收的目的區塊。該第二物理區塊前身為供該主機寫入資料的主動區塊。該有效性列表標示該第一物理區塊各儲存單元有效與否。上述第一資料以及第二資料皆關於同一邏輯位址。
根據本案一種實施方式提供的一資料儲存裝置操作方法包括：令一資料儲存裝置的一非揮發式記憶體的空間劃分為複數個物理區塊；且在掃瞄該非揮發式記憶體以重建一主機至該非揮發式記憶體的一映射表時，根據一第一物理區塊內的一有效性列表區分該第一物理區塊的一第一資料以及一第二物理區塊的一第二資料何者為較新版本。該第一物理區塊前身為垃圾回收的目的區塊。該第二物理區塊前身為供該主機寫入資料的主動區塊。該有效性列表標示該第一物理區塊各儲存單元有效與否。上述第一資料以及第二資料皆關於同一邏輯位址。
以上技術正確地完成映射表重建。
更有一種實施方式揭露一種垃圾回收方法，可用於一資料儲存裝置。所述垃圾回收方法包括：選取一來源區塊；選取一目的區塊；將該來源區塊的複數資料複製至該目的區塊；以及當該些有效資料複製完成後，儲存一關閉資訊EOB至該目的區塊，並將該該目的區塊記錄至一時序列表LinkList。該關閉資訊EOB更包括一有效性列表bitMap，該有效性列表bitMap記錄該目的區塊所儲存的每一資料的有效性。
根據本案另一種實施方式所揭露的一種重建映射表H2F方法用於一資料儲存裝置，且包括：依據一時序列表LinkList依序選取該資料儲存裝置之複數物理區塊；讀取該些物理區塊所儲存的複數關閉資訊EOB；取得該些關閉資訊EOB的複數有效性列表bitMap，並依據該些有效性列表bitMap來判斷該些物理區塊所儲的複數資料的有效性；以及記錄該些資料中複數有效資料的複數映射資訊至該映射表H2F。
下文特舉實施例，並配合所附圖示，詳細說明本發明內容。
100‧‧‧快閃記憶體
102‧‧‧資料區域
104‧‧‧閒置區域
300‧‧‧資料儲存裝置
302‧‧‧控制單元
304‧‧‧主機
306‧‧‧動態隨機存取記憶體
310‧‧‧在系統編程區塊池
312‧‧‧系統資訊區塊池
314‧‧‧閒置區塊池
316‧‧‧資料區塊池
320‧‧‧微控制器
322‧‧‧隨機存取記憶空間
324‧‧‧唯讀記憶體
A1、A2‧‧‧資料
Active_Blk‧‧‧主動區塊
bitMap‧‧‧列表
BLK#1、BLK#2、BLK#Z‧‧‧物理區塊
BLK#X、BLK#Y、BLK#V、BLK#W‧‧‧當資料區塊的物理區塊
EOB‧‧‧關閉資訊
GC_D、GC_S‧‧‧目的區塊、來源區塊
H2F‧‧‧映射表
ID‧‧‧欄位，填寫區塊識別碼
LinkList‧‧‧時序列表
Map‧‧‧映射資訊
S602…S616、S802…S814‧‧‧步驟
U#1…U#N‧‧‧儲存單元
第1A圖以及第1B圖根據本案一種實施方式圖解一快閃記憶體100的物理空間規劃；第2圖圖解垃圾回收的概念；第3圖以方塊圖圖解根據本案一種實施方式實現的一資料儲存裝置300；第4圖示意重建映射表H2F之時序列表LinkList掃描所可能遭遇之意外狀況；第5圖對應第4圖之狀況，圖解本案一種實施方式的解決方案；第6圖為流程圖，根據本案一種實施方式圖解如何掃描資料區塊以重建映射表H2F，係對應第5圖實施例；第7圖對應第4圖之狀況，圖解本案另一種實施方式的解決方案；且 第8圖為流程圖，根據本案一種實施方式圖解如何掃描資料區塊以重建映射表H2F，係對應第7圖實施例。
以下敘述列舉本發明的多種實施例。以下敘述介紹本發明的基本概念，且並非意圖限制本發明內容。實際發明範圍應依照申請專利範圍界定之。
非揮發性記憶體可以是快閃記憶體(flash memory)、磁阻式隨機存取記憶體(Magnetoresistive RAM)、鐵電隨機存取記憶體(Ferroelectric RAM)、電阻式記憶體(Resistive RAM，RRAM)、自旋轉移力矩隨機存取記憶體(Spin Transfer Torque-RAM，STT-RAM)等具有長時間資料保存之記憶體裝置。以下特別以快閃記憶體(flash memory)為例進行討論。
現今資料儲存裝置常以快閃記憶體為儲存媒體，常用來實現記憶卡(memory card)、通用序列匯流排閃存裝置(USB flash device)、固態硬碟(SSD)...等產品。有一種應用是採多晶片封裝、將快閃記憶體與其控制器包裝在一起-稱為嵌入式快閃記憶體模組(如eMMC)。以快閃記憶體為儲存媒體的資料儲存裝置可應用於多種電子裝置中。所述電子裝置包括智慧型手機、穿戴裝置、平板電腦、虛擬實境設備…等。電子裝置的中央處理單元(CPU)可視為操作所述資料儲存裝置的一主機。
第1A圖以及第1B圖根據本案一種實施方式圖解一快閃記憶體100的物理空間規劃。
如第1A圖所示，快閃記憶體100的儲存空間劃分為 複數個區塊(或稱物理區塊，physical blocks)BLK#1、BLK#2…BLK#Z等，Z為正整數。各物理區塊包括複數物理頁(physical pages)，例如：256個物理頁。
第1B圖詳解物理頁內容。每一物理頁包括一資料區域(data area)102、以及一備用區域(spare area)104。資料區域102可劃分為複數個儲存單元U#1…U#N，經配置後，對應主機端邏輯位址儲存資料。主機端邏輯位址有多種形式，例如，以邏輯區塊位址(Logical Block Address，簡稱LBA)、或全域主機頁(Global Host Page，簡稱GHP)編號。一種實施方式中，資料區域102尺寸為16KB，劃分為4KB的4個儲存單元。各4KB儲存單元對應8個邏輯區塊位址(如LBA#0~LBA#7之類)、或一個全域主機頁。備用區域104是用來儲存元資料(metadata)，包括映射資訊Map。映射資訊Map顯示儲存單元U#1…U#N所儲存的內容所對應的主機端邏輯位址。例如，映射資訊Map紀錄4段LBA(各段包括8個LBA編號)或4個GHP編號。以下以GPH為例進行說明，但不以此為限。此外，在特定物理頁上，閒置區域104可更記錄所屬物理區塊的區塊識別碼ID，其詳細內容將於後續說明。
一般運作下，快閃記憶體100之映射資訊需動態整理成映射表(如H2F、F2H)隨時調整。映射表H2F可以全域主機頁GHP為索引，記錄各全域主機頁GHP的資料是被儲存至快閃記憶體100何物理位址，即哪一物理區塊之哪一資料頁或哪一儲存單元。映射表F2H則可記錄所描述的物理區塊中，資料頁或儲存單元所儲存的內容所對應的全域主機頁GHP為何。映射 表是主機操控快閃記憶體100的重要依據，即需重建的管理資訊。
特別是，快閃記憶體100有一種特殊的物理特性：其中資料之更新並非對同樣儲存空間作複寫，而是將更新資料儲存在閒置空間，且原儲存空間的儲存內容將轉為無效。頻繁的寫入操作容易致使快閃記憶體100充斥無效的內容，垃圾回收(Garbage Collection)機制因應發展而出。
第2圖圖解垃圾回收的概念。斜線標示無效資料。來源區塊(source blocks)的有效資料將被複製至目的區塊(destination block)。當複製完成後，來源區塊可被抹除(erase)並將變更為閒置區塊(spare block)，其空間釋出。另一種實施方式則是將抹除動作延後至已無有效資料之物理區塊再次被配置使用時才進行。如此垃圾回收機制使得前述映射表維護難度提高。本案即提出相應的解決方案。
第3圖以方塊圖圖解根據本案一種實施方式實現的一資料儲存裝置300，其中包括快閃記憶體100以及一控制單元302。控制單元302耦接於一主機304與該快閃記憶體100之間，包括根據主機304所下達的指令操作該快閃記憶體100。資料儲存裝置300更可選擇性地設置一個動態隨機存取記憶體(DRAM)306，作為資料緩衝器。
控制單元302包括一微控制器320、一隨機存取記憶空間322以及一唯讀記憶體324。隨機存取記憶空間322較佳可由靜態隨機存取記憶體(SRAM)或動態隨機存取記憶體(DRAM)實現。隨機存取記憶空間322較佳與微控制器320置於 同一個晶粒(die)，而動態隨機存取記憶體306則可不與微控制器320置於同一個晶粒。唯讀記憶體324存有唯讀程式碼(如，ROM code)。微控制器320執行該唯讀記憶體324所載之唯讀程式碼或/以及該快閃記憶體100該在系統編程(in-system programming，簡稱ISP)區塊池310所載之在系統編程(ISP)程式，以進行運作。微控制器320可以該隨機存取記憶空間322(或該動態隨機存取記憶體306)動態整理主機304端邏輯位址(LBA或GHP)以及快閃記憶體100之間的映射資訊，包括映射表H2F與主動區塊Active_Blk以及目的區塊GC_D各自的映射表F2H，再載入該快閃記憶體100做非揮發性儲存。映射表H2F可存於系統資訊區塊池312。映射表F2H可儲存於對應區塊的關閉資訊(End of Block，EOB)中，較佳係儲存於對應區塊的最末物理頁。
第3圖更顯示快閃記憶體100之物理區塊被邏輯地配置成包括：在系統編程(ISP)區塊池310、系統資訊區塊池312、閒置區塊池314、資料區塊池316、主動區塊Active_Blk以及因應垃圾回收而產生的目的區塊GC_D。在系統編程(ISP)區塊池310之區塊儲存在系統編程(ISP)的程式。系統資訊區塊池312之區塊儲存系統資訊，除用作前述映射表H2F之非揮發式存儲外，更儲存一時序列表LinkList。主動區塊Active_Blk係由閒置區塊池314供應，負責接收來自於主機304的資料，待完成資料儲存後即推入資料區塊池316(即重新定義為資料區塊)。垃圾回收程序之目的區塊GC_D也可以由閒置區塊池314供應。資料區塊池316的區塊可以被選作來源區塊(標號GC_S)，在執行 垃圾回收程序時，來源區塊GC_S的有效內容將複製至該目的區塊GC_D，在完成複製有效內容後，來源區塊GC_S即推入閒置區塊池314(即重新定義為閒置區塊)。該目的區塊GC_D可於寫滿時推入該資料區塊池316(重新定義為資料區塊)。資料區塊被推入該資料區塊池316的先後順序則是以上述時序列表LinkList記載。無論主動區塊Active_Blk或目的區塊GC_D，在推入資料區塊池316之前，皆會儲存關閉資訊(End of Block，EOB)，之後，記載至時序列表LinkList，成為時序列表LinkList的最新(最末或最晚)一筆記錄。較早做EOB儲存的資料區塊會較早記載至該時序列表LinkList，較晚的做EOB儲存的資料區塊會較晚記載至該時序列表LinkList。當兩資料區塊儲存的內容對應到相同GHP時，較早做EOB儲存的資料區塊的內容會被視為無效，即無效資料。
如果發生不正常斷電並造成映射表H2F遺失，資料儲存裝置300會重建映射表H2F。映射表H2F之重建包括根據各資料區塊登錄至時序列表LinkList的順序掃描各資料區塊取得映射資訊。所取得的映射資訊可為各物理頁之備用區域104儲存的映射資訊Map或各資料區塊之關閉資訊EOB所儲存的映射表F2H。前述掃描意在得知不同邏輯位址(LBA或GHP)對應的物理空間。如果多個區塊所儲存內容皆對應至相同邏輯位址時，則資料有效性的判斷原則為較末掃描的內容為有效。當然，相較前述掃描順序，映射表H2F之重建可採反向的掃描順序；資料有效性的判斷是以較早掃描到的內容為有效。
然而，在第4圖所示特殊狀況下，前述掃描方式可 能無法反應實際資料更新狀況。為方便理解，第4圖將較晚登錄時序列表LinkList的資料區塊繪製於較右側。曾經登錄在時序列表LinkList的區塊BLK#X經垃圾回收後徒留無效資料。垃圾回收之目的區塊GC_D(區塊BLK#V)做關閉資訊EOB儲存、且登錄至時序列表LinkList後，區塊BLK#X自時序列表LinkList移除。所述垃圾回收將資料A1自區塊BLK#X搬移到區塊BLK#V。至於區塊BLK#Y，其原本是做主動區塊Active_Blk使用，早於區塊BLK#V儲存關閉資訊EOB，故早於區塊BLK#V登錄至時序列表LinkList。區塊BLK#Y上的資料A2係資料A1的更新版本，是在區塊BLK#Y做主動區塊Active_Blk使用時寫入。關於第4圖所示狀況，若非預期斷電發生，復電之映射表H2F重建依照時序列表LinkList掃描資料區塊後，會誤將區塊BLK#V上的資料A1視為最新版本，而將區塊BLK#Y上的資料A2視為較舊版本一資料管理發生錯誤。
為了清楚區別出區塊BLK#Y上的資料A2較區塊BLK#V上的資料A1新，本案提出相應解決方案。回到第3圖，根據所示實施方式，目的區塊GC_D進行關閉資訊EOB儲存時，更逐4KB儲存單元經掃描，建立一有效性列表bitMap，標註目的區塊GC_D各4KB儲存單元儲存的是有效還是無效內容。以圖示例子而言，有效性列表bitMap會顯示該目的區塊GC_D上的資料A1係無效資料(最新版本為資料A2)。如此一來，即使主動區塊Active_Blk早於該目的區塊GC_D推入該資料區塊池316，在時序列表LinkList排序較前面，藉由有效性列表bitMap，目的區塊GC_D較舊的資料A1不會被錯誤解讀為有效 資料，資料A2會被正確辨識為有效。關於非預期斷電事件，本案微控制器320於復電後進行包括有效性列表bitMap檢索的映射表H2F重建。
第3圖實施例包括以各區塊中一物理頁之備用區域(104)之區塊識別碼ID來區別一資料區塊推入資料區塊池316之前是主動區塊(Active_Blk)還是目的區塊(GC_D)。有效性列表bitMap檢索可以是針對目的區塊(GC_D)設計。區塊識別碼ID顯示映射表H2F重建所掃描之資料區塊之前為目的區塊GC_D時，判定該有效性列表bitMap存在，並將之應用於該資料區塊之資料有效性確認。更有其他實施方式不規劃欄位填寫區塊識別碼ID，而是無論主動區塊(Active_Blk)還是目的區塊(GC_D)，都於儲存其關閉資訊(EOB)時建立相應之有效性列表bitMap，供復電重建映射表H2F時使用。
第5圖對應第4圖之狀況，圖解本案一種實施方式的解決方案。各資料區塊的首物理頁之備用區域(104)標有區塊識別碼ID。一種實施例中，為0之區塊識別碼ID表示此資料區塊之前是主動區塊Active_Blk，為1之區塊識別碼ID表示此資料區塊之前是目的區塊GC_D。區塊BLK#Y之區塊識別碼ID註明區塊BLK#Y原本是主動區塊Active_Blk。區塊BLK#V之區塊識別碼ID註明區塊BLK#V原本是目的區塊GC_D。映射表H2F重建時，所述技術根據時序列表LinkList進行各資料區塊各物理頁的閒置區域(104)掃描，從閒置區域(104)取出各物理頁中各儲存單元所對應的邏輯資訊Map(LBA或GHP)。如圖所示，掃描進行到區塊BLK#Y時，是視一邏輯位址(以下標號GHP_A)映 射至區塊BLK#Y之資料A2。掃描進行到區塊BLK#V時，由於區塊識別碼ID註明區塊BLK#V前身是目的區塊GC_D，掃描動作將更考量有效性列表bitMap內容。由於有效性列表bitMap顯示區塊BLK#V上的資料A1為無效，故不會改動邏輯位址GHP_A之映射。邏輯位址GHP_A維持指到區塊BLK#Y之資料A2。區塊BLK#Y之資料A2正確地被辨識出乃最新版本。
第6圖為流程圖，根據本案一種實施方式圖解如何掃描資料區塊以重建映射表H2F；對應第5圖實施例。步驟S602初始化掃描點。例如，設定掃描點指向時序列表LinkList所指之最早資料區塊的第一物理頁的閒置區域104，其中包括設定一索引i(對應該資料區塊上之4KB儲存單元的編號)為0。步驟S604檢查區塊識別碼ID。若所掃描之資料區塊前身是目的區塊GC_D，流程進入步驟S606核對有效性列表bitMap[i]。若有效性列表bitMap[i]顯示儲存單元i的數據有效，流程進行步驟S608，以掃描所得的映射資訊覆蓋舊有映射資訊。例如，令相關的邏輯位址改指向該資料區塊之儲存單元i。若有效性列表bitMap[i]顯示儲存單元i的的數據無效，流程略過步驟S608。步驟S610則遞增索引i。步驟S612檢查是否要切換資料區塊。若否，流程回到步驟S606，進行下一個儲存單元之有效性列表bitMap[i]檢索。若是，流程進行步驟S614查詢時序列表LinkList。若已無其他資料區塊在時序列表LinkList，則流程結束。若尚有資料區塊待掃描，根據時序列表LinkList，步驟S616指引掃描點到下一個資料區塊的第一個物理頁的閒置空間104，索引i對應該資料區塊的第一個儲存單元設定為0。接著， 流程再次進行步驟S604。
倘若步驟S604所辨識欄位ID顯示掃描的資料區塊前身為主動區塊Active_Blk，流程跳過步驟S606進行步驟S608，無須核對有效性列表bitMap[i]即更新映射資訊。整理之，本案對於前身為目的區塊GC_D的資料區塊更提供一種覆核機制，以免目的區塊GC_D中早已無效的內容被誤認為有效。第6圖流程設計使得映射表H2F得以正確重建。
第7圖對應第4圖之狀況，圖解本案另一種實施方式的解決方案。此實施方式沒有規劃區塊識別碼ID，但每做關閉資訊EOB儲存即建立有效性列表bitMap。區塊BLK#Y之關閉資訊EOB中的有效性列表bitMap顯示區塊BLK#Y之資料A2有效。區塊BLK#V之關閉資訊EOB中的有效性列表bitMap顯示區塊BLK#V之資料A1無效。映射表H2F重建時，所述技術根據時序列表LinkList進行各資料區塊各物理頁的閒置區域(104)掃描，從閒置區域(104)取出各物理頁中各儲存單元所對應的邏輯資訊Map(LBA或GHP)。如圖所示，掃描進行到區塊BLK#Y時，更檢索其有效性列表bitMap，確定邏輯位址GHP_A映射至區塊BLK#Y之資料A2。掃描進行到區塊BLK#V時，由於其有效性列表bitMap顯示區塊BLK#V上的資料A1為無效，故不會改動邏輯位址GHP_A之映射。邏輯位址GHP_A維持指到區塊BLK#Y之資料A2。區塊BLK#Y之資料A2正確地被辨識出乃最新版本。
第8圖為流程圖，根據本案一種實施方式圖解如何掃描資料區塊以重建映射表H2F；對應第7圖實施例。步驟S802初始化掃描點。例如，設定掃描點指向時序列表LinkList所指 之最早資料區塊的第一物理頁的閒置區域104，其中包括設定一索引i(對應該資料區塊上之4KB儲存單元的編號)為0。步驟S804核對有效性列表bitMap[i]。若有效性列表bitMap[i]顯示儲存單元i的數據有效，流程進行步驟S806，以掃描所得的映射資訊覆蓋舊有映射資訊。例如，令相關的邏輯位址改指向該資料區塊之儲存單元i。若有效性列表bitMap[i]顯示儲存單元i的的數據無效，流程略過步驟S806。步驟S808則遞增索引i。步驟S810檢查是否要切換資料區塊。若否，流程回到步驟S804，進行下一個儲存單元之有效性列表bitMap[i]檢索。若是，流程進行步驟S812查詢時序列表LinkList。若已無其他資料區塊在時序列表LinkList，則流程結束。若尚有資料區塊待掃描，根據時序列表LinkList，步驟S814指引掃描點到下一個資料區塊的第一個物理頁的閒置空間104，索引i對應該資料區塊的第一個儲存單元設定為0。接著，流程再次進行步驟S804。
其他採用上述概念重建資料儲存裝置映射表H2F的技術都屬於本案所欲保護的範圍。基於以上技術內容，本案更涉及資料儲存裝置操作方法。
雖然本發明已以較佳實施例揭露如上，然其並非用以限定本發明，任何熟悉此項技藝者，在不脫離本發明之精神和範圍內，當可做些許更動與潤飾，因此本發明之保護範圍當視後附之申請專利範圍所界定者為準。

Claims (22)

  1. 一種資料儲存裝置，包括：一非揮發式記憶體，包括複數個物理區塊；以及一微控制器，在掃瞄該非揮發式記憶體以重建一主機至該非揮發式記憶體的一映射表時，根據一第一物理區塊內的一列表區分該第一物理區塊的一第一資料以及一第二物理區塊的一第二資料何者為較新版本；其中：該第一物理區塊前身為垃圾回收的目的區塊；該第二物理區塊前身為供該主機寫入資料的主動區塊；該有效性列表標示該第一物理區塊各儲存單元有效與否；且上述第一資料以及第二資料皆關於同一邏輯位址。
  2. 如申請專利範圍第1項所述之資料儲存裝置，其中：該微控制器是在儲存該第一物理區塊之關閉資訊時建立該有效性列表。
  3. 如申請專利範圍第2項所述之資料儲存裝置，其中：該微控制器是在該第一物理區塊的最末物理頁儲存該有效性列表。
  4. 如申請專利範圍第2項所述之資料儲存裝置，其中：該微控制器更以一時序列表紀錄上述物理區塊儲存關閉資訊的先後順序；且該微控制器更將該時序列表非揮式儲存於該非揮發式記憶體。
  5. 如申請專利範圍第4項所述之資料儲存裝置，其中： 該微控制器更在各物理區塊至少一處紀載一欄位，標示所屬物理區塊接收資料時是做目的區塊或主動區塊使用。
  6. 如申請專利範圍第5項所述之資料儲存裝置，其中：該微控制器掃瞄該非揮發式記憶體重建該映射表時，是根據該時序列表掃描上述物理區塊，並自上述欄位辨識出前身為目的區塊的上述第一物理區塊以及前身為主動區塊的上述第二物理區塊。
  7. 如申請專利範圍第6項所述之資料儲存裝置，其中：該第二物理區塊早於該第一物理區塊儲存關閉資訊時，該微控制器令該第二物理區塊早於該第一物理區塊登錄於該時序列表。
  8. 如申請專利範圍第7項所述之資料儲存裝置，其中：關於晚於該第二物理區塊儲存關閉資訊的該第一物理區塊，該微控制器於儲存該第一物理區塊之關閉資訊時令該有效性列表標示該第一物理區塊的該第一資料為無效。
  9. 如申請專利範圍第8項所述之資料儲存裝置，其中：該微控制器在該時序列表早於該第一區塊尋得該第二區塊時，是早於該第一區塊先掃描該第二區塊，並在掃瞄該第二資料之映射資訊時令所重建的該映射表將該邏輯位址指向該第二資料所在。
  10. 如申請專利範圍第9項所述之資料儲存裝置，其中：該微控制器在該時序列表晚於該第二區塊尋得該第一區塊時，是晚於該第二區塊掃描該第一區塊，並在掃瞄該第一資料之映射資訊時自該有效性列表得知該第一資料無效， 據以不變動所重建的該映射表中該邏輯位址所指向的物理空間。
  11. 一種資料儲存裝置操作方法，包括：令一資料儲存裝置的一非揮發式記憶體的空間劃分為複數個物理區塊；且在掃瞄該非揮發式記憶體以重建一主機至該非揮發式記憶體的一映射表時，根據一第一物理區塊內的一有效性列表區分該第一物理區塊的一第一資料以及一第二物理區塊的一第二資料何者為較新版本；其中：該第一物理區塊前身為垃圾回收的目的區塊；該第二物理區塊前身為供該主機寫人資料的主動區塊；該有效性列表標示該第一物理區塊各儲存單元有效與否；且上述第一資料以及第二資料皆關於同一邏輯位址。
  12. 如申請專利範圍第11項所述之資料儲存操作方法，更包括：在儲存該第一物理區塊之關閉資訊時建立該有效性列表。
  13. 如申請專利範圍第12項所述之資料儲存裝置操作方法，更包括：在該第一物理區塊的最末物理頁儲存該有效性列表。
  14. 如申請專利範圍第12項所述之資料儲存裝置操作方法，更包括：以一時序列表紀錄上述物理區塊儲存關閉資訊的先後順序；以及 將該時序列表非揮式儲存於該非揮發式記憶體。
  15. 如申請專利範圍第14項所述之資料儲存裝置操作方法，更包括：在各物理區塊至少一處紀載一欄位，標示所屬物理區塊接收資料時是做目的區塊或主動區塊使用。
  16. 如申請專利範圍第15項所述之資料儲存裝置操作方法，更包括：在掃瞄該非揮發式記憶體重建該映射表時，根據該時序列表掃描上述物理區塊，並自上述欄位辨識出前身為目的區塊的上述第一物理區塊以及前身為主動區塊的上述第二物理區塊。
  17. 如申請專利範圍第16項所述之資料儲存裝置操作方法，更包括：在該第二物理區塊早於該第一物理區塊儲存關閉資訊時，令該第二物理區塊早於該第一物理區塊登錄於該時序列表。
  18. 如申請專利範圍第17項所述之資料儲存裝置操作方法，其中：關於晚於該第二物理區塊儲存關閉資訊的該第一物理區塊，該有效性列表是在該第一物理區塊之關閉資訊儲存時標示該第一物理區塊的該第一資料無效。
  19. 如申請專利範圍第18項所述之資料儲存裝置操作方法，其中： 該第二區塊早於該第一區塊自該時序列表尋得時，該第二區塊早於該第一區塊被掃描，且掃描到的該第二資料之映射資訊使得該映射表中該邏輯位址指向該第二資料所在。
  20. 如申請專利範圍第19項所述之資料儲存裝置操作方法，其中：該第一區塊晚於該第二區塊自該時序列表尋得時，該第一區塊晚於該第二區塊被掃描，且該有效性列表顯示該第一資料無效的狀況使得該映射表中該邏輯位址所指向的物理空間不變動。
  21. 一種垃圾回收方法，可用於一資料儲存裝置，包括：選取一來源區塊；選取一目的區塊；將該來源區塊的複數資料複製至該目的區塊；以及當該些有效資料複製完成後，儲存一關閉資訊EOB至該目的區塊，並將該該目的區塊記錄至一時序列表LinkList，其中，該關閉資訊EOB更包括一有效性列表bitMap，該有效性列表bitMap記錄該目的區塊所儲存的每一資料的有效性。
  22. 一種重建映射表H2F方法，可用於一資料儲存裝置，包括：依據一時序列表LinkList依序選取該資料儲存裝置之複數物理區塊；讀取該些物理區塊所儲存的複數關閉資訊EOB； 取得該些關閉資訊EOB的複數有效性列表bitMap，並依據該些有效性列表bitMap來判斷該些物理區塊所儲的複數資料的有效性；以及記錄該些資料中複數有效資料的複數映射資訊至該映射表H2F。
TW106110108A 2017-03-27 2017-03-27 資料儲存裝置以及其操作方法 TWI613652B (zh)

Priority Applications (3)

Application Number Priority Date Filing Date Title
TW106110108A TWI613652B (zh) 2017-03-27 2017-03-27 資料儲存裝置以及其操作方法
US15/802,130 US20180275887A1 (en) 2017-03-27 2017-11-02 Data Storage Device and Operating Method of Data Storage Device
CN201810039463.7A CN108664418A (zh) 2017-03-27 2018-01-16 数据储存装置以及其操作方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
TW106110108A TWI613652B (zh) 2017-03-27 2017-03-27 資料儲存裝置以及其操作方法

Publications (2)

Publication Number Publication Date
TWI613652B TWI613652B (zh) 2018-02-01
TW201835922A true TW201835922A (zh) 2018-10-01

Family

ID=62014501

Family Applications (1)

Application Number Title Priority Date Filing Date
TW106110108A TWI613652B (zh) 2017-03-27 2017-03-27 資料儲存裝置以及其操作方法

Country Status (3)

Country Link
US (1) US20180275887A1 (zh)
CN (1) CN108664418A (zh)
TW (1) TWI613652B (zh)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111338562A (zh) * 2018-12-18 2020-06-26 慧荣科技股份有限公司 数据存储装置与数据处理方法
TWI831623B (zh) * 2022-03-10 2024-02-01 慧榮科技股份有限公司 借助序號分配時序控制來進行記憶體裝置之存取管理的方法、記憶體裝置、電子裝置以及記憶體裝置的控制器
TWI911682B (zh) 2024-03-19 2026-01-11 神達數位股份有限公司 快閃記憶體的資料管理方法

Families Citing this family (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI714830B (zh) * 2018-02-13 2021-01-01 緯穎科技服務股份有限公司 目錄資料的管理方法與記憶體裝置
US10936046B2 (en) * 2018-06-11 2021-03-02 Silicon Motion, Inc. Method for performing power saving control in a memory device, associated memory device and memory controller thereof, and associated electronic device
TWI671631B (zh) * 2018-08-01 2019-09-11 大陸商深圳大心電子科技有限公司 記憶體管理方法以及儲存控制器
CN110825310B (zh) * 2018-08-09 2023-09-05 深圳大心电子科技有限公司 存储器管理方法以及存储控制器
KR20200020464A (ko) * 2018-08-17 2020-02-26 에스케이하이닉스 주식회사 데이터 저장 장치 및 그 동작 방법
CN110888591B (zh) 2018-09-07 2023-05-30 慧荣科技股份有限公司 数据储存装置以及非挥发式存储器控制方法
CN110888593B (zh) 2018-09-07 2024-01-26 慧荣科技股份有限公司 数据储存装置以及非挥发式存储器控制方法
TWI696916B (zh) * 2018-09-07 2020-06-21 慧榮科技股份有限公司 資料儲存裝置以及非揮發式記憶體控制方法
CN110888820B (zh) 2018-09-07 2022-01-25 慧荣科技股份有限公司 数据储存装置以及非挥发式存储器控制方法
CN112100087B (zh) 2019-06-17 2024-04-02 慧荣科技股份有限公司 数据储存装置以及非挥发式存储器控制方法
CN112099985B (zh) 2019-06-17 2023-09-12 慧荣科技股份有限公司 数据储存装置以及非挥发式存储器控制方法
CN112130749B (zh) * 2019-06-25 2023-12-22 慧荣科技股份有限公司 数据储存装置以及非挥发式存储器控制方法
CN112130750B (zh) 2019-06-25 2023-11-07 慧荣科技股份有限公司 数据储存装置以及非挥发式存储器控制方法
KR20210137679A (ko) * 2020-05-11 2021-11-18 에스케이하이닉스 주식회사 메모리 컨트롤러
KR20220049230A (ko) * 2020-10-14 2022-04-21 에스케이하이닉스 주식회사 메모리 시스템에서 비휘발성 메모리 장치 내 오류를 확인하는 장치 및 방법
CN114442903B (zh) * 2020-10-30 2024-07-05 伊姆西Ip控股有限责任公司 管理存储系统的方法、电子设备和计算机程序产品
CN112379830B (zh) * 2020-11-03 2022-07-26 成都佰维存储科技有限公司 有效数据位图的创建方法、装置、存储介质及电子设备
US12197766B2 (en) * 2020-11-10 2025-01-14 Micron Technology, Inc. Error injection methods using soft post-package repair (sPPR) techniques and memory devices and memory systems employing the same
US12399822B2 (en) * 2023-08-22 2025-08-26 Silicon Motion, Inc. Method and apparatus for performing data access management of memory device in predetermined communications architecture with aid of multi-table checking

Family Cites Families (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5341330A (en) * 1992-10-30 1994-08-23 Intel Corporation Method for writing to a flash memory array during erase suspend intervals
US20090172269A1 (en) * 2005-02-04 2009-07-02 Samsung Electronics Co., Ltd. Nonvolatile memory device and associated data merge method
US8397014B2 (en) * 2008-02-04 2013-03-12 Apple Inc. Memory mapping restore and garbage collection operations
KR100954039B1 (ko) * 2008-08-11 2010-04-20 (주)인디링스 플래시 메모리 제어 방법 및 제어 장치
US8914567B2 (en) * 2008-09-15 2014-12-16 Vmware, Inc. Storage management system for virtual machines
TWI431627B (zh) * 2009-07-31 2014-03-21 Silicon Motion Inc 快閃記憶體裝置及快閃記憶體裝置之運作方法
US8381018B2 (en) * 2010-05-21 2013-02-19 Mediatek Inc. Method for data recovery for flash devices
WO2012051600A2 (en) * 2010-10-15 2012-04-19 Kyquang Son File system-aware solid-state storage management system
US9213594B2 (en) * 2011-01-19 2015-12-15 Intelligent Intellectual Property Holdings 2 Llc Apparatus, system, and method for managing out-of-service conditions
US9075708B1 (en) * 2011-06-30 2015-07-07 Western Digital Technologies, Inc. System and method for improving data integrity and power-on performance in storage devices
US8788788B2 (en) * 2011-08-11 2014-07-22 Pure Storage, Inc. Logical sector mapping in a flash storage array
CN103106143B (zh) * 2011-11-11 2016-01-13 光宝科技股份有限公司 固态储存装置及其逻辑至实体对应表建立方法
KR101907059B1 (ko) * 2011-12-21 2018-10-12 삼성전자 주식회사 비휘발성 메모리 장치의 블록 관리 방법 및 블록 관리 시스템
US9384254B2 (en) * 2012-06-18 2016-07-05 Actifio, Inc. System and method for providing intra-process communication for an application programming interface
TWI514140B (zh) * 2013-02-05 2015-12-21 Via Tech Inc 非揮發性記憶裝置及其操作方法
US20140281842A1 (en) * 2013-03-14 2014-09-18 Fusion-Io, Inc. Non-Volatile Cells Having a Non-Power-of-Two Number of States
US9152495B2 (en) * 2013-07-03 2015-10-06 SanDisk Technologies, Inc. Managing non-volatile media using multiple error correcting codes
CN105612503B (zh) * 2013-08-09 2018-10-23 桑迪士克科技有限责任公司 持久性数据结构
TWI546666B (zh) * 2014-11-03 2016-08-21 慧榮科技股份有限公司 資料儲存裝置以及快閃記憶體控制方法
US10180805B2 (en) * 2015-03-25 2019-01-15 SK Hynix Inc. Memory system and operating method thereof
CN105573681B (zh) * 2015-12-31 2017-03-22 湖南国科微电子股份有限公司 一种ssd盘片内部raid组建方法及系统
CN106055279B (zh) * 2016-06-12 2019-05-10 浪潮(北京)电子信息产业有限公司 管理固态硬盘的地址映射表的方法、装置及固态硬盘

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111338562A (zh) * 2018-12-18 2020-06-26 慧荣科技股份有限公司 数据存储装置与数据处理方法
TWI749279B (zh) * 2018-12-18 2021-12-11 慧榮科技股份有限公司 資料儲存裝置與資料處理方法
CN111338562B (zh) * 2018-12-18 2023-06-09 慧荣科技股份有限公司 数据存储装置与数据处理方法
TWI831623B (zh) * 2022-03-10 2024-02-01 慧榮科技股份有限公司 借助序號分配時序控制來進行記憶體裝置之存取管理的方法、記憶體裝置、電子裝置以及記憶體裝置的控制器
US11899977B2 (en) 2022-03-10 2024-02-13 Silicon Motion, Inc. Method and apparatus for performing access management of memory device with aid of serial number assignment timing control
TWI911682B (zh) 2024-03-19 2026-01-11 神達數位股份有限公司 快閃記憶體的資料管理方法

Also Published As

Publication number Publication date
TWI613652B (zh) 2018-02-01
US20180275887A1 (en) 2018-09-27
CN108664418A (zh) 2018-10-16

Similar Documents

Publication Publication Date Title
TWI613652B (zh) 資料儲存裝置以及其操作方法
CN108733510B (zh) 数据储存装置及映射表重建方法
TWI645404B (zh) 資料儲存裝置以及非揮發式記憶體操作方法
CN101673226B (zh) Nand错误管理
US10176190B2 (en) Data integrity and loss resistance in high performance and high capacity storage deduplication
US10642729B2 (en) Data storage device and operating method thereof wherein update to physical-to-logical mapping of destination block is restarted when closing active block
TWI646535B (zh) 資料儲存裝置以及非揮發式記憶體操作方法
US10223208B2 (en) Annotated atomic write
WO2019174205A1 (zh) 一种垃圾回收的方法、装置及存储设备
US9507523B1 (en) Methods, devices and systems for variable size logical page management in a solid state drive
CN112099985B (zh) 数据储存装置以及非挥发式存储器控制方法
CN109976664B (zh) 固态存储设备的日志数据组织
CN110389906A (zh) 存储器元件中重新编排数据的方法、及其控制器与系统
US20170010810A1 (en) Method and Apparatus for Providing Wear Leveling to Non-Volatile Memory with Limited Program Cycles Using Flash Translation Layer
US20170017405A1 (en) Systems and methods for improving flash-oriented file system garbage collection
TWI718709B (zh) 資料儲存裝置以及非揮發式記憶體控制方法
US20170017406A1 (en) Systems and methods for improving flash-oriented file system garbage collection
CN108334275A (zh) 数据储存方法及其装置
CN108509295B (zh) 存储器系统的操作方法
TWI897545B (zh) 非揮發式記憶體控制器、控制方法、以及電腦程式產品
CN110597454B (zh) 数据储存装置以及非挥发式存储器控制方法
CN114860500A (zh) Nvm的故障注入方法及其存储设备
CN118939174A (zh) 设备克隆方法、存储设备及存储介质