[go: up one dir, main page]

TWI670596B - 記憶體系統及控制非揮發性記憶體之控制方法 - Google Patents

記憶體系統及控制非揮發性記憶體之控制方法 Download PDF

Info

Publication number
TWI670596B
TWI670596B TW106146403A TW106146403A TWI670596B TW I670596 B TWI670596 B TW I670596B TW 106146403 A TW106146403 A TW 106146403A TW 106146403 A TW106146403 A TW 106146403A TW I670596 B TWI670596 B TW I670596B
Authority
TW
Taiwan
Prior art keywords
data
reference count
block
written
management table
Prior art date
Application number
TW106146403A
Other languages
English (en)
Other versions
TW201915742A (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 TW201915742A publication Critical patent/TW201915742A/zh
Application granted granted Critical
Publication of TWI670596B publication Critical patent/TWI670596B/zh

Links

Classifications

    • 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
    • G06F12/0261—Garbage collection, i.e. reclamation of unreferenced memory using reference counting
    • 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/10—Address translation
    • G06F12/1009—Address translation using page tables, e.g. page table structures
    • G06F12/1018—Address translation using page tables, e.g. page table structures involving hashing techniques, e.g. inverted page tables
    • 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
    • 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
    • G06F3/0641—De-duplication techniques
    • 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
    • G06F3/0679—Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
    • 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/0683—Plurality of storage devices
    • G06F3/0688—Non-volatile semiconductor memory arrays
    • 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/20—Employing a main memory using a specific memory technology
    • G06F2212/202—Non-volatile memory
    • G06F2212/2022—Flash memory
    • 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
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management

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)
  • Memory System (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本發明實現一種既能實現重複資料刪除，又能節約對用於進行重複資料刪除所需的管理資料進行儲存所需之記憶體資源的記憶體系統。
實施形態之記憶體系統係管理非揮發性記憶體內之與複數個第1區塊對應之複數個管理表。各管理表包含與對應的第1區塊內之複數個資料對應之複數個參照計數。記憶體系統將包含於垃圾回收之複製源區塊內且與屬於第1參照計數範圍之參照計數各自對應之資料集合複製至第1複製目標區塊，將包含於上述複製源區塊內且與屬於第2參照計數範圍之參照計數各自對應之資料集合複製至第2複製目標區塊，上述第2參照計數範圍具有較上述第1參照計數範圍之上限更大之下限。

Description

記憶體系統及控制非揮發性記憶體之控制方法
本發明之實施形態係關於一種記憶體系統及控制非揮發性記憶體之控制方法。
近年來，具備非揮發性記憶體之記憶體系統正廣泛地普及。
作為此種記憶體系統之一，已知有具備NAND(Not And，與非)型快閃記憶體之固態硬碟(SSD)。SSD被用作各種計算裝置之主儲存器。
但是，最近開始要求將大量資料高效地保持至儲存器中。
作為用以改善儲存效率之技術，已知有重複資料刪除(De-duplication)。
但是，進行重複資料刪除需要用到管理資料，儲存此種管理資料需要用到記憶體資源，而於先前之重複資料刪除技術中，並未考慮到節約此種記憶體資源之技術。
本發明提供一種既能實現重複資料刪除，又能節約對重複資料刪除用管理資料進行儲存時所需之記憶體資源的記憶體系統及控制非揮發性記憶體之控制方法。
根據實施形態，可連接主機之記憶體系統具備非揮發性記憶體及控制器，上述控制器電性連接於上述非揮發性記憶體，控制上述非揮發性記憶體。上述控制器係管理上述非揮發性記憶體內之與複數個第1區塊對應 之複數個管理表。各管理表包含與對應的第1區塊內之複數個資料對應之複數個參照計數，各參照計數表示參照對應的資料之邏輯位址之數量。當上述非揮發性記憶體中不存在與自主機接收之寫入資料一致之重複資料時，上述控制器更新管理各邏輯位址與各中間位址之對應關係之第1轉換表，將未使用之第1中間位址與上述寫入資料之邏輯位址建立關聯，將上述寫入資料寫入上述非揮發性記憶體，且更新管理上述各中間位址與各實體位址之對應關係之第2轉換表，將表示已被寫入上述寫入資料之上述非揮發性記憶體內之位置之實體位址與上述第1中間位址建立關聯，將與上述寫入資料對應之參照計數設定為1。當上述非揮發性記憶體中已存在與上述寫入資料一致之上述重複資料時，上述控制器不將上述寫入資料寫入上述非揮發性記憶體，而更新上述第1轉換表，將第2中間位址與上述寫入資料之上述邏輯位址建立關聯，將與上述重複資料對應之參照計數增加1；上述第2中間位址係指示保持有與上述重複資料對應之實體位址之上述第2轉換表內之條目(entry)。當上述寫入資料為已被寫入上述非揮發性記憶體之資料之更新資料時，上述控制器將與上述已被寫入之資料對應之參照計數減去1。當選擇上述複數個第1區塊中之一個作為垃圾回收之複製源區塊時，上述控制器基於與上述複製源區塊對應之上述複數個管理表內之第1管理表，將包含於上述複製源區塊內且與屬於第1參照計數範圍之參照計數各自對應之資料集合複製至第1複製目標區塊，將包含於上述複製源區塊內且與屬於第2參照計數範圍之參照計數各自對應之資料集合複製至第2複製目標區塊；上述第2參照計數範圍具有較上述第1參照計數範圍之上限更大之下限。
1‧‧‧資訊處理系統
2‧‧‧主機
3‧‧‧SSD
4‧‧‧控制器
5‧‧‧NAND型快閃記憶體
6‧‧‧DRAM
7‧‧‧用戶資料區域
8‧‧‧管理區域
10‧‧‧匯流排
11‧‧‧主機介面
12‧‧‧CPU
13‧‧‧NAND介面
14‧‧‧DRAM介面
21‧‧‧重複資料刪除處理部
22‧‧‧GC動作控制部
23‧‧‧資料分離動作控制部
31‧‧‧寫入緩衝器
32‧‧‧LUT
32-0‧‧‧LUT
32-1‧‧‧LUT
33‧‧‧雜湊LUT
34‧‧‧iLUT
36‧‧‧非揮發性LUT
37‧‧‧非揮發性LUT
38‧‧‧查找表快取
50‧‧‧網路
51‧‧‧儲存區塊池
52‧‧‧空閒區塊池
53‧‧‧複製目標SB
54‧‧‧寫入目標SB
90‧‧‧終端用戶終端
100-0、100-1、…100-i‧‧‧SB
101‧‧‧處理器
102‧‧‧主記憶體
103‧‧‧BIOS-ROM
105‧‧‧網路控制器
106‧‧‧周邊I/F控制器
107‧‧‧控制器
107A‧‧‧連接器
108‧‧‧嵌入式控制器
200-0、200-1、…200-i‧‧‧SB管理表
201‧‧‧殼體
201A‧‧‧前表面
202‧‧‧系統板(母板)
210‧‧‧SB
211‧‧‧SB
212‧‧‧SB
221‧‧‧複製目標SB
221A‧‧‧SB管理表
222‧‧‧複製目標SB
222A‧‧‧SB管理表
BLK0~BLKm-1‧‧‧實體區塊
Ch‧‧‧通道
Ch.1~Ch.16‧‧‧通道
d1~d28‧‧‧資料
iLBA0~iLBAm‧‧‧中間位址
LBA0~LBAj‧‧‧邏輯位址
P0~Pn-1‧‧‧頁
PBA0~PBAn‧‧‧實體位址
圖1係表示實施形態之記憶體系統之構成例之方塊圖。
圖2係表示該實施形態之記憶體系統中設定之非揮發性記憶體之構成例之方塊圖。
圖3係表示該實施形態之記憶體系統中使用之複數個通道與複數個NAND型快閃記憶體晶片之關係之方塊圖。
圖4係表示該實施形態之記憶體系統中使用之某超級區塊之構成例之圖。
圖5係表示由該實施形態之記憶體系統管理之查找表與中間查找表之關係之方塊圖。
圖6係表示由該實施形態之記憶體系統管理之2個查找表與中間查找表之關係之方塊圖。
圖7係用以說明該實施形態之記憶體系統中之位址參照結構之方塊圖。
圖8係表示由該實施形態之記憶體系統管理之超級區塊管理表之構成例之方塊圖。
圖9係表示由該實施形態之記憶體系統管理之中間查找表(iLUT)之構成例之方塊圖。
圖10係表示由該實施形態之記憶體系統管理之查找表(LUT)之構成例之方塊圖。
圖11係表示由該實施形態之記憶體系統管理之雜湊查找表(HASH LUT)之構成例之方塊圖。
圖12係用以說明由該實施形態之記憶體系統執行之位址轉換動作之方塊圖。
圖13係用以說明由該實施形態之記憶體系統執行之資料讀出動作之圖。
圖14係表示由該實施形態之記憶體系統執行之用戶資料管理用結構之方塊圖。
圖15係表示由該實施形態之記憶體系統執行之垃圾回收動作之一部分之圖。
圖16係表示由該實施形態之記憶體系統執行之垃圾回收動作之剩餘部之圖。
圖17係表示由該實施形態之記憶體系統執行之資料寫入動作之順序之流程圖。
圖18係表示由該實施形態之記憶體系統執行之垃圾回收動作之順序之流程圖。
圖19係表示由該實施形態之記憶體系統執行之資料讀出動作之順序之流程圖。
圖20係表示由該實施形態之記憶體系統管理之各超級區塊管理表內之參照計數記憶區域部之構成例之圖。
圖21係表示由該實施形態之記憶體系統執行之將對應於較大參照計數之資料與對應於較小參照計數對應之資料分離之垃圾回收動作之概要之圖。
圖22係表示由該實施形態之記憶體系統執行之垃圾回收動作中包含之資料複製動作及參照計數複製動作之圖。
圖23係表示與某資料對應之參照計數溢出之情形時由該實施形態之記憶體系統執行之資料複製動作之一部分之圖。
圖24係表示與某資料對應之參照計數溢出之情形時由該實施形態之記憶體系統執行之資料複製動作之剩餘部分之圖。
圖25係表示與某資料對應之參照計數溢出之情形時由該實施形態之記憶體系統執行之參照計數記憶區域擴張動作之圖。
圖26係用以說明該實施形態之記憶體系統中應用之垃圾回收對象區塊(複製源區塊)候補之選擇條件之圖。
圖27係表示由該實施形態之記憶體系統執行之複製源區塊候補選擇動作之圖。
圖28係表示由該實施形態之記憶體系統執行之複製源區塊候補選擇動作之順序之流程圖。
圖29係表示由該實施形態之記憶體系統寫入至超級區塊內各頁中之用戶資料與中間位址(iLBA)之關係之圖。
圖30係表示與某資料對應之參照計數溢出之情形時由該實施形態之記憶體系統執行之資料寫入動作之圖。
圖31係表示垃圾回收動作中由該實施形態之記憶體系統執行之重複資料刪除動作之一部分之圖。
圖32係表示垃圾回收動作中由該實施形態之記憶體系統執行之重複資料刪除動作之剩餘一部分之圖。
圖33係表示垃圾回收動作中之重複資料刪除動作中由該實施形態之記憶體系統執行之參照計數複製動作之圖。
圖34係表示垃圾回收動作中之重複資料刪除動作中由該實施形態之記憶體系統執行之中間查找表(iLUT)更新動作之圖。
圖35係表示用以將具有較大參照計數之資料與具有較小參照計數之 資料分離之GC(Garbage Collection，垃圾回收)動作之順序之流程圖。
圖36係表示與某資料對應之參照計數溢出時執行之重複資料複製處理之順序之流程圖。
圖37係表示與某資料對應之參照計數溢出時執行之參照計數記憶區域擴張處理之順序之流程圖。
圖38係表示與某資料對應之參照計數溢出時執行之資料寫入處理之順序之流程圖。
圖39係用以說明自邏輯位址直接參照實體位址之位址參照路徑、及經由中間位址而自邏輯位址參照實體位址之位址參照路徑混合存在之位址參照結構之圖。
圖40係用以說明對於所有資料都經由中間位址而自邏輯位址參照實體位址之位址參照結構之圖。
圖41係表示圖40之位址參照結構中使用之查找表之構成例之圖。
圖42係表示主機之構成例之方塊圖。
圖43係表示包含主機及該實施形態之記憶體系統之電腦之構成例之圖。
以下，參照圖式，對實施形態進行說明。
首先，參照圖1，對包含實施形態之記憶體系統之資訊處理系統1之構成進行說明。
該記憶體系統係以向非揮發性記憶體寫入資料、自非揮發性記憶體讀入資料之方式構成之半導體儲存裝置。該記憶體系統例如係以具備NAND型快閃記憶體之固態硬碟(SSD)3之形式實現。
資訊處理系統1包含主機(主機裝置)2、及SSD3。主機2係伺服器、個人電腦等資訊處理裝置(計算裝置)。於以伺服器之形式實現主機2之案例中，該主機(伺服器)2亦可經由網路50而連接於複數個終端用戶終端(用戶端)90。主機2能對該等終端用戶終端90提供各種服務。
主機(伺服器)2所能提供之服務中亦可包含對複數個終端用戶終端(用戶端)90提供虛擬桌面環境之服務。於此種情形時，主機(伺服器)2亦可作為以使用虛擬桌面基礎架構(VDI)提供虛擬桌面環境之方式構成之VDI伺服器發揮功能。於作為VDI伺服器發揮功能之主機(伺服器)2中，亦可運行與複數個終端用戶終端(用戶端)90分別對應之複數個虛擬機。該等虛擬機各自包含OS(Operating System，操作系統)(虛擬桌面OS)、及於OS(虛擬桌面OS)上運行之應用程式。與該等虛擬機對應之複數個OS/應用程式會被儲存於SSD3中。
SSD3可被用作作為主機2發揮功能之資訊處理裝置之主儲存器。SSD3既可內置於該資訊處理裝置，亦可經由纜線或網路而連接於該資訊處理裝置。
作為用以將主機2與SSD3相互連接之介面，可使用SCSI(Small Computer System Interface，小型電腦系統介面)、串列連接SCSI(Serial Attached SCSI，SAS)、ATA(Advanced Technology Attachment，高級技術附件)、串列ATA(Serial ATA，SATA)、外圍組件互連高速(Peripheral Component Interconnect Express，PCI Express，PCIe)、以太網(Ethernet，註冊商標)、光纖通道(Fibre channel)、非揮發性記憶體高速(Non-Volatile Memory Express，NVM Express，NVMe，註冊商標)等。
SSD3具備控制器4、及非揮發性記憶體(NAND型快閃記憶體)5。 SSD3亦可進而具備隨機存取記憶體，例如DRAM(Dynamic Random Access Memory，動態隨機存取記憶體)6。
NAND型快閃記憶體5包含具備呈矩陣狀配置之複數個記憶單元之記憶單元陣列。NAND型快閃記憶體5既可為2維結構之NAND型快閃記憶體，亦可為3維結構之NAND型快閃記憶體。NAND型快閃記憶體5內之區域(記憶區域)包含用戶資料區域7及管理區域8。用戶資料區域7係用以儲存來自主機2之資料(用戶資料)之區域。管理區域8係用以儲存管理SSD3之動作所用之管理資訊之區域。
NAND型快閃記憶體5之記憶單元陣列如圖2所示，包含複數個實體區塊BLK~BLKm-1。實體區塊BLK0~BLKm-1各自由複數個頁(於此，為頁P0~Pn-1)組成。實體區塊BLK0~BLKm-1係作為能指定位址之最小刪除單位發揮功能。實體區塊有時亦會被稱為「刪除區塊」、「實體刪除區塊」，或簡稱為「區塊」。頁P0~Pn-1各自包含連接於同一字元線之複數個記憶單元。頁P0~Pn-1係資料寫入動作及資料讀入動作之單位。
實體區塊B0~Bm-1具有有限之刪除次數。刪除次數亦可藉由編程/刪除週期(Program/Erase cycles)數而表達。某實體區塊之一個編程/刪除週期(Program/Erase cycles)包含用以使該實體區塊內之所有記憶單元成為刪除狀態之刪除動作、及向該實體區塊之各頁中寫入資料之寫入動作(編程動作)。由於實體區塊B0~Bm-1具有有限之刪除次數(有限之編程/刪除週期)，所以較佳為將實體區塊B0~Bm-1之編程/刪除週期儘量均勻化。
於本實施形態中，圖1之控制器4管理各自包含1個以上實體區塊之複 數個第1區塊，並以第1區塊為單位執行刪除動作。因此，第1區塊實際上作為刪除單位發揮功能。以下，將第1區塊作為超級區塊加以參照。再者，超級區塊有時亦會被稱為邏輯區塊。
控制器4經由Toggle、開放式NAND型快閃記憶體介面(Open NAND Flash Interface，ONFI)等NAND介面13而電性連接於作為非揮發性記憶體之NAND型快閃記憶體5。控制器4係控制NAND型快閃記憶體5之記憶體控制器(控制電路)。該控制器4亦能以系統晶片(system on a chip，SoC)等單晶片LSI(Large Scale Integration，大規模積體電路)之形式實現。
NAND型快閃記憶體5如圖3所示，包含複數個NAND型快閃記憶體晶片(NAND型快閃記憶體晶片區塊)。各個NAND型快閃記憶體晶片能獨立地動作。因此，NAND型快閃記憶體晶片作為能並行動作之單位發揮功能。於圖3中，例示了NAND介面13連接有16個通道Ch.1~Ch.16，16個通道Ch.1~Ch.16各自連接有2個NAND型快閃記憶體晶片之情形。於此種情形時，連接於通道Ch.1~Ch.16之16個NAND型快閃記憶體晶片#1~#16亦可組成為記憶體組(bank)#0，又連接於通道Ch.1~Ch.16之剩餘16個NAND型快閃記憶體晶片#17~#32亦可組成為記憶體組#1。記憶體組作為用以使複數個記憶體模組藉由記憶體組交錯而並行動作之單位發揮功能。於圖3之構成例中，藉由16個通道、及使用2個記憶體組之記憶體組交錯，能使最多32個NAND型快閃記憶體晶片並行動作。
一個超級區塊並不限定於包含該等，亦可包含自NAND型快閃記憶體晶片#1~#32中逐一選擇出之共計32個實體區塊。再者，NAND型快閃記憶體晶片#1~#32各自亦可具有多平面構成。例如，於NAND型快閃記 憶體晶片#1~#32各自具有包含2個平面之多平面構成之情形時，一個超級區塊亦可包含自與NAND型快閃記憶體晶片#1~#32對應之64個平面逐一選擇出之共計64個實體區塊。
圖4中例示了包含32個實體區塊(於此，為NAND型快閃記憶體晶片#1內之實體區塊BLK2、NAND型快閃記憶體晶片#2內之實體區塊BLK3、NAND型快閃記憶體晶片#3內之實體區塊BLK7、NAND型快閃記憶體晶片#4內之實體區塊BLK4、NAND型快閃記憶體晶片#5內之實體區塊BLK6、…NAND型快閃記憶體晶片#32內之實體區塊BLK3)之一個超級區塊(SB)。
再者，一個超級區塊亦可利用僅包含一個實體區塊之構成，於此種情形時，一個超級區塊與一個實體區塊等同。
如上所述，控制器4係以超級區塊為單位執行刪除動作。因此，同一超級區塊中包含之該32個實體區塊之刪除動作係並行執行。
又，於向該超級區塊寫入資料時，控制器4亦可依NAND型快閃記憶體晶片#1內之實體區塊BLK2之頁0、NAND型快閃記憶體晶片#2內之實體區塊BLK3之頁0、NAND型快閃記憶體晶片#3內之實體區塊BLK7之頁0、NAND型快閃記憶體晶片#4內之實體區塊BLK4之頁0、NAND型快閃記憶體晶片#5內之實體區塊BLK6之頁0、…NAND型快閃記憶體晶片#32內之實體區塊BLK3之頁0之順序寫入資料。藉此，能並行執行最多向32個頁中之資料寫入。又，於自該超級區塊讀出資料時，亦能並行執行最多自32個頁中之資料讀出。
其次，對圖1之控制器4之構成進行說明。
控制器4經由複數個通道(例如16個通道)而電性連接於複數個NAND 型快閃記憶體晶片。控制器4控制NAND型快閃記憶體5(複數個NAND型快閃記憶體晶片)。
控制器4亦可作為以執行NAND型快閃記憶體5之資料管理及區塊管理之方式構成之快閃轉換層(FTL)發揮功能。由該FTL執行之資料管理中包含如下等：(1)管理表示各邏輯位址與NAND型快閃記憶體5之各實體位址之間之對應關係之映射資訊；(2)進行用以將以頁為單位之讀出/寫入及以區塊為單位(以超級區塊為單位)之刪除動作隱蔽之處理。邏輯位址係為了對SSD3進行位址指定而供主機使用之位址。作為該邏輯位址，可使用LBA(logical block address(addressing)，邏輯區塊位址(尋址))。
於普通SSD中，各邏輯位址與各實體位址之間之對應關係(映射)之管理僅使用作為邏輯-實體位址轉換表發揮功能之查找表而執行。對應於某邏輯位址之實體位址表示寫入有該邏輯位址之資料之NAND型快閃記憶體內之最新位置(最新實體記憶位置)。
於本實施形態中，為了既能維持垃圾回收之效率又能於SSD3內部執行用以實現重複資料刪除(De-duplication)之動作，而利用新位址參照路徑。
該新位址參照路徑並非自邏輯位址直接參照實體位址，而係經由中間位址自邏輯位址參照實體位址。各邏輯位址與各中間位址之對應關係由作為邏輯-中間位址轉換表(第1轉換表)發揮功能之查找表(LUT)32管理。各中間位址與各實體位址之對應關係由作為中間-實體位址轉換表(第2轉換表)發揮功能之中間查找表(iLUT)34管理。
本實施形態中，於與自主機2新接收之寫入資料(用戶資料)一致之資料(作為「重複資料」加以參照)已儲存於NAND型快閃記憶體5中之情形 時，控制器4不將該寫入資料寫入至NAND型快閃記憶體5中。取而代之，控制器4更新邏輯-中間位址轉換表(LUT)32，將已與重複資料建立有關聯之中間位址、即指示保持有與重複資料對應之實體位址之中間-實體位址轉換表(iLUT)34內之條目之特定中間位址與該寫入資料之邏輯位址建立關聯。
藉此，能自包含重複資料之邏輯位址及寫入資料之邏輯位址之2個邏輯位址參照同一中間位址，且能自該同一中間位址參照儲存有重複資料之實體記憶位置之實體位址。其結果，能自重複資料之邏輯位址及寫入資料之邏輯位址兩者參照該重複資料，從而能提高儲存效率。
如自上述說明所理解般，於本實施形態中，使用邏輯-中間位址轉換表(LUT)32及中間-實體位址轉換表(iLUT)34而執行2級位址轉換。於邏輯-中間位址轉換表(LUT)32中，與已存在之某資料一致之寫入資料之邏輯位址關聯於與已存在之資料之中間位址相同之中間位址。因此，於中間-實體位址轉換表(iLUT)34中，無論參照某資料之邏輯位址之數量為何，各實體位址僅與一個中間位址建立有關聯。
藉此，於被複數個邏輯位址參照之資料(重複資料)藉由垃圾回收而被複製至其他超級區塊之案例中，控制器4可保證：只進行僅將與該一個中間位址對應之中間-實體位址轉換表(iLUT)34內之一個條目更新為複製目標實體位址之動作，便能自該複數個邏輯位址正確參照該複製目標實體位址。
進而，控制器4管理與用戶資料區域7內之複數個超級區塊(SB)100-0、100-1、…100-i分別對應之複數個超級區塊(SB)管理表200-0、200-1、…200-i。
該等SB管理表200-0、200-1、…200-i各自為用以管理對應超級區塊中所保持之複數個資料之區塊管理資訊。
各SB管理表包含與對應超級區塊內之複數個資料對應之複數個參照計數。於各SB管理表中，該等參照計數係依與對應超級區塊之實體位址之排列順序相同之順序配置。各參照計數表示參照對應資料(即超級區塊內之對應位置(實體記憶位置)之邏輯位址之數量。
例如，若某資料僅被1個邏輯位址參照，即，若與儲存有該資料之實體記憶位置之實體位址建立有關聯之中間位址僅被1個邏輯位址獨佔性地使用，則對應於該資料之參照計數為1。
若某資料被2個邏輯位址參照，即，若與儲存有該資料之實體記憶位置之實體位址建立有關聯之中間位址被2個邏輯位址共用，則對應於該資料之參照計數為2。
若某資料被3個邏輯位址參照，即，若與儲存有該資料之實體記憶位置之實體位址建立有關聯之中間位址被3個邏輯位址共用，則對應於該資料之參照計數為3。
控制器4使用SB管理表200-0、200-1、…200-i各者，而管理與各超級區塊內之複數個資料對應之複數個參照計數。該等SB管理表200-0、200-1、…200-i亦可於SSD3接通電源時自NAND型快閃記憶體5內之管理區域8載入至DRAM6中。
於NAND型快閃記憶體5內之管理區域8中，亦儲存有其他各種管理資訊，例如，邏輯-中間位址轉換表(LUT)32、雜湊LUT33、及中間-實體位址轉換表(iLUT)34。該等邏輯-中間位址轉換表(LUT)32、雜湊LUT33、及中間-實體位址轉換表(iLUT)34同樣地亦可於SSD3接通電源時 自NAND型快閃記憶體5內之管理區域8載入至DRAM6中。
通常，於NAND型快閃記憶體5中，向頁中之資料寫入每1刪除週期僅能進行1次。
因此，控制器4將對應於某邏輯位址之更新資料寫入至NAND型快閃記憶體5內之其他位置，而非儲存有對應於該邏輯位址之先前資料之NAND型快閃記憶體5內之位置(實體記憶位置)。然後，控制器4更新中間-實體位址轉換表(iLUT)34，將該其他實體記憶位置之實體位址與對應於該邏輯位址之中間位址建立關聯。
區塊管理中包含壞區塊之管理、耗損平均、垃圾回收等。耗損平均係用以將實體區塊各自之消耗均勻化之動作。垃圾回收係為了增加能寫入資料之空閒區塊(空閒超級區塊)之個數，將有效資料與無效資料混合存在之若干複製源區塊(複製源超級區塊)內之有效資料複製至複製目標區塊(複製目標超級區塊)。於此，所謂有效資料係指被邏輯位址作為最新資料而關聯之資料、即後面有可能會被主機2讀出之某資料。所謂無效資料係指已無可能被主機2讀出之資料。
於本實施形態中，超級區塊(SB)100-0、100-1、…100-i各者中包含之所有用戶資料之參照計數儲存於對應於各超級區塊之SB管理表中。換而言之，控制器4使用對應於各超級區塊之SB管理表，而管理與各超級區塊內之複數個資料對應之複數個參照計數。因此，控制器4能僅基於與用於垃圾回收之複製源區塊對應之SB管理表內之參照計數群，便執行用於垃圾回收之資料複製動作。即，控制器4不複製與零參照計數對應之資料，而僅將與非零參照計數對應之資料自垃圾回收對象超級區塊(垃圾回收之複製源區塊)複製至複製目標區塊。垃圾回收對象超級區塊(垃圾回收 之複製源區塊)亦被作為GC源超級區塊加以參照。又，複製目標區塊亦被作為GC宿超級區塊加以參照。即，由於與零參照計數對應之資料未被任何邏輯位址參照，所以被當作無效資料看待。由於與非零參照計數對應之資料被1個以上邏輯位址參照，所以被當作有效資料看待。藉由將與非零參照計數對應之資料移動至複製目標區塊而已不再存在與非零參照計數對應之資料之複製源區塊被解放成為空閒區塊(空閒超級區塊)。藉此，該空閒超級區塊能於執行該刪除動作後再次利用。
於垃圾回收中，控制器4進而將對應於複製源區塊之SB管理表內之各非零參照計數複製至對應於複製目標區塊之SB管理表。藉此，於資料自複製源區塊複製至複製目標區塊後，亦能正確管理與所複製之各資料對應之參照計數值。
又，各SB管理表之內容於執行過與該SB管理表對應之超級區塊之刪除動作後便不再有用。因此，某超級區塊內之各資料不再有用之時序與對應於該超級區塊之SB管理表內之各參照計數不再有用之時序同時發生，所以能降低用以管理與各超級區塊內之各資料對應之各參照計數之成本。
控制器4亦可包含主機介面11、CPU(Central Processing Unit，中央處理器)12、NAND介面13、DRAM介面14等。該等CPU12、NAND介面13、DRAM介面14亦可經由匯流排10而相互連接。
主機介面11自主機2接收各種指令(例如，寫入指令、讀出指令、映射取消(UNMAP)/禁用刪除(Trim)指令等)。
CPU12係以控制主機介面11、NAND介面13、及DRAM介面14之方式構成之處理器。CPU12響應SSD3之電源接通，將儲存於NAND型快閃記憶體5或未圖示之ROM(Read Only Memory，只讀記憶體)中之控制程 式(韌體)載入至DRAM6上，藉由執行該韌體而進行各種處理。該CPU12例如除了上述FTL之處理以外，還能執行用以對來自主機2之各種指令進行處理之指令處理等。CPU12之動作由藉由CPU12加以執行之上述韌體控制。再者，FTL處理及指令處理之一部分或全部亦可由控制器4內之專用硬體執行。
CPU12能作為重複資料刪除處理部21、垃圾回收(GC)動作控制部22、資料分離動作控制部23發揮功能。
<重複資料刪除處理部21>
重複資料刪除處理部21於SSD3內執行用以實現重複資料刪除之資料寫入動作。
當重複資料刪除處理部21自主機2接收寫入資料(應寫入之用戶資料)時，重複資料刪除處理部21會執行以下資料寫入動作。
(1)於NAND型快閃記憶體5中不存在與寫入資料一致之資料(重複資料)之情形時，重複資料刪除處理部21更新管理各邏輯位址與各中間位址之對應關係之LUT32，將未使用之第1中間位址與寫入資料之邏輯位址建立關聯。重複資料刪除處理部21將寫入資料寫入至複數個超級區塊中之一個(寫入目標超級區塊)。重複資料刪除處理部21更新管理各中間位址與各實體位址之對應關係之iLUT34，將表示寫入有寫入資料之NAND型快閃記憶體5內之位置(實體記憶位置)之實體位址與第1中間位址建立關聯。然後，重複資料刪除處理部21將與該寫入資料對應之參照計數設定為1。
(2)於NAND型快閃記憶體5中已存在與寫入資料一致之重複資料之情形時，重複資料刪除處理部21不將寫入資料寫入至複數個超級區塊中之一個(寫入目標超級區塊)，而更新LUT32，將第2中間位址與寫入資料之邏 輯位址建立關聯，其中上述第2中間位址指示保持有與該重複資料對應之實體位址之iLUT34內之條目。然後，重複資料刪除處理部21將與重複資料對應之參照計數增加1。
(3)於寫入資料係之前已寫入至NAND型快閃記憶體5中之資料之更新資料之情形時，重複資料刪除處理部21將與之前已寫入之該資料對應之參照計數減去1。
重複資料刪除處理部21亦管理雜湊LUT33。該雜湊LUT33係管理各雜湊值與各中間位址之對應關係之轉換表。於用以將某中間位址與寫入資料之邏輯位址建立關聯之處理中，重複資料刪除處理部21亦可執行以下動作。
(1)重複資料刪除處理部21獲得寫入資料之雜湊值。
(2)於雜湊LUT33中不存在與所獲得之雜湊值對應之中間位址之情形時，重複資料刪除處理部21判定NAND型快閃記憶體5中不存在與寫入資料一致之重複資料。然後，重複資料刪除處理部21將未使用之中間位址賦予給所獲得之雜湊值，並將所獲得之雜湊值與賦予給所獲得之雜湊值之中間位址之對應關係儲存至雜湊LUT33中。如此，於NAND型快閃記憶體5中不存在與寫入資料一致之重複資料之情形時，賦予給所獲得之雜湊值之中間位址作為上述第1中間位址而與寫入資料之邏輯位址建立關聯。
(3)於雜湊LUT33中已存在與所獲得之雜湊值對應之中間位址之情形時，重複資料刪除處理部21參照iLUT34，取得與對應於上述所獲雜湊值之中間位址建立有關聯之實體位址。重複資料刪除處理部21將寫入資料與由所取得之實體位址指定之NAND型快閃記憶體5內之位置上儲存之資料加以比較。於該等資料相互一致之情形時，重複資料刪除處理部21判定 NAND型快閃記憶體5中已存在與寫入資料一致之重複資料。如此，於NAND型快閃記憶體5中已存在與寫入資料一致之重複資料之情形時，重複資料刪除處理部21將與所獲得之雜湊值對應且已存在於雜湊LUT33中之上述中間位址作為上述第2中間位址而與寫入資料之邏輯位址建立關聯。
<GC動作控制部22>
GC動作控制部22基於與複製源區塊(複製源超級區塊)對應之SB管理表內之各參照計數，而執行以下GC動作。
(1)於選擇複數個超級區塊100-1、100-2、…100-i中之一個作為垃圾回收之複製源區塊(複製源超級區塊)之情形時，GC動作控制部22基於與複製源區塊對應之SB管理表，而僅將與各非零參照計數對應之資料自複製源區塊複製至複製目標區塊(複製目標超級區塊)。
(2)GC動作控制部22更新iLUT34，將表示複製有與各非零參照計數對應之資料之複製目標區塊內之各位置之實體位址與對應於所複製資料之各中間位址建立關聯。
(3)GC動作控制部22將與複製源區塊對應之SB管理表內之各非零參照計數複製至與複製目標區塊對應之SB管理表中。
如此，於iLUT34中，各中間位址與各實體位址相互一對一地映射。因此，於被複數個邏輯位址參照之資料(重複資料)藉由垃圾回收(GC)而自複製源區塊複製至複製目標區塊之案例中，控制器4只需更新iLUT34，便能將該資料之舊實體位址(複製源實體位址)正確變更為新實體位址(複製目標實體位址)。
又，控制器4對於與儲存於某超級區塊中之複數個資料分別對應之複 數個參照計數全部，係使用與該超級區塊對應之SB管理表加以管理。而且，於某超級區塊被選作用於GC之複製源區塊之情形時，基於與該超級區塊對應之SB管理表之內容，而執行僅將與非零參照計數對應之資料自複製源區塊複製至複製目標區塊之處理、及將各非零參照計數自與複製源區塊對應之SB管理表複製至與複製目標區塊對應之SB管理表之處理。因此，能僅基於與複製源區塊對應之SB管理表之內容而執行GC動作，從而既能實現重複資料刪除，又能改善GC動作之效率。
<資料分離動作控制部23>
資料分離動作控制部23執行用以將具有較大參照計數之資料群與具有較小參照計數之資料群相互分離，將具有較大參照計數之資料群與具有較小參照計數之資料群儲存於互不相同之超級區塊中之動作。換而言之，資料分離動作控制部23為了將屬於相同參照計數範圍之資料群集中於相同之超級區塊，而執行以下動作。
資料分離動作控制部23執行以下動作：將與屬於第1參照計數範圍之各參照計數對應之第1資料集合集中於一個以上超級區塊，將與屬於第2參照計數範圍之各參照計數對應之第2資料集合集中於一個以上其他超級區塊，其中上述第2參照計數範圍具有較第1參照計數範圍之上限大之下限。藉此，能將屬於相同參照計數範圍之資料群集中於相同之超級區塊。將第1資料集合集中於一個以上超級區塊、將第2資料集合集中於一個以上其他超級區塊之動作亦可藉由垃圾回收而實現。
即，於選擇超級區塊100-0、100-1、…100-i中之一個作為垃圾回收之複製源區塊之情形時，為了將第1資料集合集中於一個以上超級區塊，資料分離動作控制部23基於與複製源區塊對應之SB管理表，將包含於複 製源區塊內且與屬於第1參照計數範圍之各參照計數對應之資料集合複製至第1複製目標區塊。進而，為了將第2資料集合集中於一個以上其他超級區塊，資料分離動作控制部23將包含於複製源區塊內且與屬於第2參照計數範圍之各參照計數對應之資料集合複製至第2複製目標區塊，其中上述第2參照計數範圍具有較第1參照計數範圍之上限大之下限。
各SB管理表具有能儲存各自具有某設定位元長度之複數個參照計數之參照計數記憶區域。雖然可為各參照計數之位元長度越長則所能計數之參照計數之最大值越大，但是必須確保之參照計數記憶區域之尺寸亦會增大。若一個超級區塊中混合存在具有較大參照計數之資料群與具有較小參照計數之資料群，則必須確保較大尺寸之參照計數記憶區域，其中上述參照計數記憶區域需能儲存可表現較大參照計數且各自具有較長位元長度之複數個參照計數。但是，該超級區塊中亦包含具有較小參照計數之資料群。因此，該較大尺寸之參照計數記憶區域內之很多記憶體資源可能會被無端消耗。
於本實施形態中，可將屬於相同參照計數範圍之資料群集中於相同之超級區塊。因此，能將需設定於各SB管理表內之參照計數記憶區域之尺寸優化，其結果能削減參照計數各自之管理所需之記憶體資源量。
又，具有較大參照計數之資料群可謂之為被覆寫之概率較低之資料，即，具有較長生命週期之資料。其原因在於，只要與參照具有較大參照計數之資料之大量邏輯位址分別對應之資料未被全部更新，與該資料對應之參照計數便不會為零。例如，於將SSD3用作上述VDI伺服器之儲存器之案例中，若執行向複數個終端用戶提供之複數個虛擬桌面OS各自之更新，則有可能會自主機2(VDI伺服器)向SSD3發送複數個寫入請求，而 該等寫入請求係用以寫入具有彼此相同之內容之資料。其結果，於NAND型快閃記憶體5中，會存在分別具有較大參照計數之複數個資料。該等具有較大參照計數之資料群有較大可能會一直有效地維持至虛擬桌面OS各自之下次更新為止。
另一方面，具有較小參照計數之資料群係被覆寫之概率相對較高之資料，即，具有較短生命週期之資料。
若為具有較大參照計數之資料群及具有較小參照計數之資料群混合存在於相同超級區塊之環境，則有可能寫入放大會增加。
其原因在於，於具有較大參照計數之資料群及具有較小參照計數之資料群混合存在之超級區塊中，只有具有較小參照計數之資料群會於較早之時序無效化，另一方面，該超級區塊內之剩餘資料群(具有較大參照計數之資料群)有可能會長時間地維持為有效狀態。
寫入放大(WA)係以如下方式定義。
WA=「寫入至SSD中之資料之總量」/「自主機寫入至SSD中之資料之總量」
「寫入至SSD中之資料之總量」相當於，自主機寫入至SSD中之資料之總量與藉由垃圾回收等內部性地寫入至SSD中之資料之總量之和。
寫入放大(WA)之增加會引起SSD3內之超級區塊/實體區塊各自之覆寫次數(編程/擦除次數)之增加。即，寫入放大(WA)越大，則實體區塊之編程/擦除次數越容易快速地達到其編程/擦除次數之上限值。其結果，會引起SSD3之耐用性及壽命之劣化。
於本實施形態中，由於屬於相同參照計數範圍之資料群會被集中於相同之超級區塊，所以能使相同超級區塊中包含之資料各自之生命週期保 持為相同程度。具有相同程度之生命週期之資料群表示有較大可能藉由抹除或更新而於大致同一時期無效化之資料組。對於所有資料都已無效化之超級區塊，不執行GC，便能使該超級區塊成為空閒區塊。其結果，能使相同超級區塊中包含之資料各自之參照計數保持為相同程度此點能抑制GC之頻率，藉此能降低寫入放大。
進而，資料分離動作控制部23於集中有具有較大參照計數之資料群之超級區塊群、與集中有具有較小參照計數之資料群之超級區塊群之間，執行變更用以選擇GC源超級區塊(即，複製源區塊候補)之條件之處理。即，由於與資料對應之參照計數越大，則該資料被覆寫之概率越低，因此資料分離動作控制部23將集中有具有較大參照計數之資料群之超級區塊群優先於集中有具有較小參照計數之資料群之超級區塊群地選作GC候補。
更詳細而言，資料分離動作控制部23執行以下動作。
(1)資料分離動作控制部23將超級區塊100-1、100-2、…100-i分為集中有屬於第1參照計數範圍之資料集合之第1區塊群、及集中有屬於第2參照計數範圍之資料集合之第2區塊群。
(2)對於第1區塊群，資料分離動作控制部23選擇滿足無效資料量大於第1閾值之條件之區塊(超級區塊)作為用於垃圾回收之複製源區塊候補。
(3)對於第2區塊群，資料分離動作控制部23選擇滿足無效資料量大於第2閾值之條件之區塊(超級區塊)作為用於垃圾回收之複製源區塊候補，其中上述第2閾值小於第1閾值。
於集中有屬於第2參照計數範圍之資料集合之第2區塊、即集中有具有較大參照計數之資料群之超級區塊中，儲存有無效資料之無效資料記憶 區域於較長時間內都不會被用於新資料之儲存。該無效資料記憶區域無端地消耗SSD3之超額配置(Over-provisioning)容量。於本實施形態中，能將集中有具有較大參照計數之資料群之超級區塊群優先於集中有具有較小參照計數之資料群之超級區塊群地選作GC候補，因此能容易將集中有具有較大參照計數之資料群之超級區塊群內之無效資料記憶區域用作用以儲存新資料之記憶體資源。此能增加SSD3之實質超額配置容量，藉此能降低寫入放大。
圖1之DRAM介面14係以對DRAM6進行存取控制之方式構成之DRAM控制器。DRAM6之記憶區域之一部分用以儲存寫入緩衝器(WB)31。DRAM6之記憶區域之另一部分用以將上述LUT32、雜湊LUT33、iLUT34儲存為查找表快取。可為僅將LUT32、雜湊LUT33、iLUT34各自之一部分儲存於查找表快取中，亦可為將LUT32、雜湊LUT33、iLUT34各自之全部儲存於查找表快取中。DRAM6之記憶區域之進而另一部分用以儲存上述SB管理表200-0、200-1、…200-i。
圖5表示LUT32與iLUT34之關係。
如上所述，LUT32作為邏輯-中間位址轉換表發揮功能，管理各邏輯位址(LBA)與各中間位址之對應關係。以下，將中間位址稱為iLBA。
又，如上所述，iLUT34係作為中間-實體位址轉換表發揮功能之中間查找表，管理各iLBA與NAND型快閃記憶體5之各實體位址之對應關係。以下，將實體位址亦稱為PBA。
在已存在於NAND型快閃記憶體5中之某資料被複數個LBA參照之情形時，LUT32中，該等LBA關聯於同一iLBA。iLUT34中，該iLBA關聯於表示儲存有該資料之NAND型快閃記憶體5內之位置之PBA。因此，能 自該等LBA參照同一iLBA，能自該同一iLBA參照表示儲存有該資料之NAND型快閃記憶體5內之位置之PBA。
於iLUT34中，各iLBA與各PBA相互一對一地映射。因此，於被複數個邏輯位址參照之資料(重複資料)藉由垃圾回收(GC)而自複製源區塊複製至複製目標區塊之案例中，控制器4只需更新iLUT34，便能將該資料之舊PBA正確變更為新PBA。
亦可使用自複數個LBA直接參照同一PBA之位址轉換結構。但此種情形時，於LUT32中，若某資料被1000個LBA參照，則需對與此1000個LBA對應之1000個條目分別記憶相同之PBA。因此，於被1000個LBA參照之資料(重複資料)藉由垃圾回收(GC)而自複製源區塊複製至複製目標區塊之案例中，控制器4需分別更新此1000個條目內之PBA。
於本實施形態中，即便某資料被1000個LBA參照，該等LBA亦只參照一個iLBA，該資料之PBA僅與此一個iLBA建立關聯。因此，控制器4只要更新儲存有該PBA之iLUT34內之一個條目之PBA即可。
如圖6所示，亦可自複數個LUT32參照iLUT34。於圖6中，例示了自2個LUT32-0、LUT32-1參照iLUT34之案例。LUT32-0亦可為管理與某命名空間對應之各LBA與各iLBA之對應關係之LUT，LUT32-1亦可為管理與另一命名空間對應之各LBA與各iLBA之對應關係之LUT。對各命名空間分配自LBA0開始之LBA範圍。來自主機2之寫入指令/讀出指令亦可包含指定特定命名空間之標識符(命名空間ID)。主機2亦可按照來自某終端用戶之I/O請求，將包含指定分配給該終端用戶之特定命名空間之命名空間ID之寫入指令/讀出指令發送給SSD3。又，主機2亦可按照來自另一終端用戶之I/O請求，將包含指定分配給該另一終端用戶之另一特定命名空 間之命名空間ID之寫入指令/讀出指令發送給SSD3。
圖7表示位址參照結構。
SSD3之控制器4自主機2接收寫入資料及與該寫入資料對應之LBA。與一個LBA對應之寫入資料之尺寸例如亦可為4K位元組(4KB)。
控制器4獲得自主機2接收之寫入資料之雜湊值。對用於雜湊計算之演算法並不限定，可利用任意演算法。藉由雜湊計算獲得之雜湊值之位元寬度只要為小於寫入資料之尺寸、例如4KB(=32768位元)之位元寬度即可。藉由雜湊計算獲得之雜湊值之位元寬度亦可為256位元。控制器4對所獲得之雜湊值賦予某iLBA，並將所獲得之雜湊值及賦予給該雜湊值之iLBA儲存至雜湊LUT33中。
對所獲得之雜湊值賦予iLBA之動作亦可按照以下方式進行。
若雜湊LUT33中不存在與所獲得之雜湊值對應之iLBA，則控制器4判定NAND型快閃記憶體5中不存在與寫入資料一致之資料(重複資料)，從而將未使用之任意iLBA賦予給該雜湊值。然後，控制器4將所獲得之雜湊值及賦予給該雜湊值之iLBA儲存至雜湊LUT33中。該被賦予之iLBA會被通知給LUT32。於LUT32中，該被通知之iLBA與對應於自主機2接收之寫入資料之LBA建立關聯。控制器4將寫入資料寫入至複數個超級區塊100-0、100-1、100-2、…中之一個(寫入目標超級區塊)。然後，控制器4更新iLUT34，將表示寫入有寫入資料之NAND型快閃記憶體5內之位置(實體記憶位置)之實體位址(PBA)與該被賦予之iLBA建立關聯。控制器4更新與寫入目標超級區塊對應之SB管理表，將與該寫入資料對應之參照計數設定為1。
若雜湊LUT33中已存在與所獲得之雜湊值對應之iLBA，則控制器4 判定NAND型快閃記憶體5中有可能已存在與該寫入資料一致之資料(重複資料)。
於此種情形時，控制器4首先自雜湊LUT33取得與所獲得之雜湊值對應之iLBA。控制器4自iLUT34取得與該iLBA對應之PBA，讀出由所取得之PBA指定之NAND型快閃記憶體5內之位置上儲存之資料。然後，控制器4將寫入資料與讀出資料加以比較。若寫入資料與讀出資料一致，則控制器4判定NAND型快閃記憶體5中已存在與寫入資料一致之資料(重複資料)。於此種情形時，寫入資料不會被寫入至複數個超級區塊100-0、100-1、100-2、…中之一個(寫入目標超級區塊)。控制器4將與所獲得之雜湊值對應之該iLBA、即指示iLUT34內之條目之iLBA通知給LUT32，該iLUT34保持有表示儲存有重複資料之NAND型快閃記憶體5內之位置之PBA。於LUT32中，該被通知之iLBA與對應於自主機2接收之寫入資料之LBA建立關聯。然後，控制器4更新與儲存有重複資料之超級區塊對應之SB管理表，將對應於該重複資料之參照計數增加1。
圖8表示超級區塊管理表之構成例。
於圖8中，為了簡化圖式，例示出超級區塊(SB)100-0具有各自能儲存4個4KB資料之頁0~k之案例。又，對儲存有各4KB資料之實體記憶位置分配有實體位址(PBA)。
於頁0中，對應於PBA0之實體記憶位置上儲存有資料A，對應於PBA1之實體記憶位置上儲存有資料B，對應於PBA2之實體記憶位置上儲存有資料C，對應於PBA3之實體記憶位置上儲存有資料D。
又，於頁1中，對應於PBA4之實體記憶位置上儲存有資料E，對應於PBA5之實體記憶位置上儲存有資料F，對應於PBA6之實體記憶位置上儲 存有資料G，對應於PBA7之實體記憶位置上儲存有資料H。
同樣地，於頁k中，對應於PBAn-3之實體記憶位置上儲存有資料W，對應於PBAn-2之實體記憶位置上儲存有資料X，對應於PBAn-1之實體記憶位置上儲存有資料Y，對應於PBAn之實體記憶位置上儲存有資料Z。
超級區塊(SB)100-1、100-2、…亦具有與超級區塊(SB)100-0相同之構成。
SB管理表200-0、200-1、200-2、…分別對應於超級區塊(SB)100-0、100-1、100-2、…而設。於各SB管理表中，記憶與儲存於對應的超級區塊(SB)中之複數個資料對應之複數個參照計數(Refcount)。該等參照計數(Refcount)係依對應的超級區塊(SB)之實體位址(PBA)之排列順序配置。
作為一例，在對應於超級區塊(SB)100-0之SB管理表200-0中，與超級區塊(SB)100-0內之各資料對應之參照計數係按照如下方式加以管理。
於SB管理表200-0中，管理與超級區塊(SB)100-0之PBA0~n對應之n+1個參照計數(Refcount)。此n+1個參照計數(Refcount)依PBA0~n之排列順序配置於SB管理表200-0內。
與PBA0對應之SB管理表200-0內之開頭記憶位置上儲存之參照計數「3」係與對應於PBA0之實體記憶位置上儲存之資料A對應之參照計數，表示參照資料A之邏輯位址(LBA)數為3。
於不具有重複資料刪除結構之一般SSD中，將對應於此等3個LBA之3個用戶資料寫入NAND型快閃記憶體。若對應於一個LBA之用戶資料尺寸為4K位元組，則因為寫入3個4K位元組資料，所以會消耗12K位元組 之記憶體資源。
於本實施形態中，與此3個LBA對應之3個用戶資料中僅一個會被寫入至NAND型快閃記憶體5中。因此，能將所消耗之記憶體資源縮減至4K位元組。如此，SSD3便能藉由重複資料刪除功能壓縮應寫入至SSD3中之用戶資料。
與PBA1對應之SB管理表200-0內之第2號記憶位置上儲存之參照計數「4」係與對應於PBA1之實體記憶位置上儲存之資料B對應之參照計數，表示參照資料B之邏輯位址(LBA)數為4。同樣地，與PBAn對應之SB管理表200-0內之第n+1號記憶位置上儲存之參照計數「0」係與對應於PBAn之實體記憶位置上儲存之資料Z對應之參照計數，表示參照資料Z之邏輯位址(LBA)數為零。
同樣地，於SB管理表200-1、200-2、…各者中，與對應超級區塊(SB)100-1、100-2、…內之複數個資料對應之複數個參照計數係依對應超級區塊(SB)內之PBA之排列順序而配置。
圖9表示中間查找表(iLUT)34之構成例。
iLUT34管理各中間位址(iLBA)與NAND型快閃記憶體5之各實體位址(PBA)之對應關係。
iLUT34亦可具有與iLBA0~m對應之m+1個條目。例如，與iLBA0對應之條目用以儲存表示儲存有與被賦予了iLBA0之1個以上LBA對應之資料之NAND型快閃記憶體5內之位置(實體記憶位置)之PBA(於此，為PBA0)。與iLBA1對應之條目用以儲存表示儲存有與被賦予了iLBA1之1個以上LBA對應之資料之NAND型快閃記憶體5內之位置(實體記憶位置)之PBA(於此，為PBA1)。
圖10表示查找表(LUT)32之構成例。
LUT32管理各邏輯位址(LBA)與各中間位址(iLBA)之對應關係。
LUT32亦可具有與LBA0~j對應之j+1個條目。
例如，與LBA0對應之條目用以儲存賦予給LBA0之iLBA(於此，為iLBA0)。與LBA1對應之條目用以儲存賦予給LBA1之iLBA(此處iLBA1)。與LBA2對應之條目用以儲存賦予給LBA2之iLBA(於此，為iLBA7)。同樣地，與LBA10對應之條目用以儲存賦予給LBA10之iLBA(於此，為iLBA0)，與LBAj對應之條目用以儲存賦予給LBAj之iLBA(於此，為iLBA0)。
圖11表示雜湊查找表(雜湊LUT)33之構成例。
雜湊LUT33管理各雜湊值(Hash(Data))與各中間位址(iLBA)之對應關係。
雜湊查找表(雜湊LUT)33具有複數個條目，各條目記憶某雜湊值(Hash(Data))、及賦予給該雜湊值(Hash(Data))之中間位址(iLBA)。基本上，對不同之雜湊值賦予不同之iLBA。SSD3獲取來自主機2之寫入資料之雜湊值，若雜湊LUT33中不存在所獲得之雜湊值，則將未使用之任意iLBA賦予給所獲得之雜湊值，並將所獲得之雜湊值與被賦予之iLBA之對應關係儲存於雜湊LUT33中。
於圖11中，例示了如下情形：對資料A之雜湊值(Hash(DataA))賦予iLBA0，對資料B之雜湊值(Hash(DataB))賦予iLBA1，對資料C之雜湊值(Hash(DataC))賦予iLBA7，對資料D之雜湊值(Hash(DataD))賦予iLBA5，對資料E之雜湊值(Hash(DataE))賦予iLBA10，對資料F之雜湊值(Hash(DataF))賦予iLBA2，對資料G之雜湊值(Hash(DataG))賦予 iLBA4，對資料H之雜湊值(Hash(DataH))賦予iLBA6。
其次，利用圖12，對本實施形態中所執行之位址轉換動作進行說明。
於此，假設為如下情形：SSD3自主機2接收了各自具有4KB尺寸之4個新寫入資料、即資料A、資料B、資料C、資料D、資料E。又，假設為如下情形：資料A、資料B、資料C、資料D係包含互不相同之內容、即互不相同之位元行之資料，且資料E係與資料A一致之資料。
計算資料A、資料B、資料C、資料D各自之雜湊值(Hash(DataA)、Hash(DataB)、Hash(DataC)、Hash(DataD)，對該等雜湊值分別賦予未使用之中間位址(iLBA)。
於圖12中，例示了對Hash(DataA)賦予iLBA0，對Hash(DataB)賦予iLBA1，對Hash(DataC)賦予iLBA2，對Hash(DataD)賦予iLBA3之情形。於雜湊LUT33中，記憶4個雜湊值與4個iLBA之對應關係，即，Hash(DataA)與iLBA0對、Hash(DataB)與iLBA1對、Hash(DataC)與iLBA2對、Hash(DataD)與iLBA3對。又，更新LUT32，藉此使iLBA0與對應於資料A之LBA0建立關聯，使iLBA1與對應於資料B之LBA1建立關聯，使iLBA2與對應於資料C之LBA2建立關聯，使iLBA3與對應於資料D之LBA3建立關聯。
將資料A、資料B、資料C及資料D寫入至複數個超級區塊中之一個(於圖12中，為超級區塊(SB)100-0)。該超級區塊(SB)100-0係被分配為當前寫入目標區塊(當前寫入目標超級區塊)之超級區塊。然後，更新iLUT34，藉此使表示寫入有資料A之寫入目標超級區塊(SB)100-0內之實體記憶位置之PBA0與iLBA0建立關聯，使表示寫入有資料B之寫入目標 超級區塊(SB)100-0內之實體記憶位置之PBA1與iLBA1建立關聯，使表示寫入有資料C之寫入目標超級區塊(SB)100-0內之實體記憶位置之PBA2與iLBA2建立關聯，使表示寫入有資料D之寫入目標超級區塊(SB)100-0內之實體記憶位置之PBA3與iLBA3建立關聯。再者，亦可於向超級區塊(SB)100-0中寫入資料A、資料B、資料C及資料D前執行iLUT34之更新。
資料E之雜湊值(Hash(DataE))與Hash(DataA)一致。因此，與Hash(DataE)(=Hash(DataA))對應之iLBA(於此，為iLBA0)已存在於雜湊LUT33中。於此種情形時，將由與iLBA0對應之PBA0指定之實體記憶位置上儲存之資料(於此，為資料A)與資料E加以比較，而判定資料E是否與資料A一致。
若資料E與資料A一致，則不將資料E寫入至超級區塊(SB)100-0中(重複資料刪除)。然後，更新LUT32，將與Hash(DataE)對應且已存在於雜湊LUT33中之iLBA(於此，為iLBA0)與對應於資料E之LBA4建立關聯。
其次，利用圖13，對本實施形態中所執行之資料讀出動作進行說明。
於SSD3之控制器4自主機2接收包含LBA4之讀出指令之情形時，控制器4參照LUT32。由於與LBA4對應之中間位址係iLBA0，所以控制器4基於iLBA0而參照iLUT34。與iLBA0對應之實體位址係PBA0。因此，控制器4從由PBA0指定之SB100-0內之實體記憶位置讀出資料A，並將資料A回傳給主機2。
圖14表示用於用戶資料管理之結構。
於圖14中，查找表快取38用於將分別儲存於NAND型快閃記憶體5之 管理區域8之LUT32整體及iLUT34整體各自之一部分保持於DRAM6上。又，於圖14中，非揮發性LUT36表示儲存於NAND型快閃記憶體5之管理區域8之LUT32整體之內容，非揮發性iLUT37表示儲存於NAND型快閃記憶體5之管理區域8之iLUT33整體之內容。
當查找表快取38中不存在目標位址轉換資訊(LBA-iLBA轉換資訊、或iLBA-PBA轉換資訊)時(快取缺失)，會自NAND型快閃記憶體5(非揮發性LUT36、或非揮發性iLUT37)中讀出目標位址轉換資訊，並將查找表快取38內之某替換對象快取列之內容替換成上述被讀出之位址轉換資訊。當上述替換對象快取列中保持之位址轉換資訊已被更新時，便將該替換對象源快取列中保持之位址轉換資訊之內容重寫至NAND型快閃記憶體5(非揮發性LUT36、或非揮發性iLUT37)中(Updatate cache lines，更新後之快取列)中。
用戶資料區域7內之各超級區塊(SB)之狀態大致分為記憶有有效資料之工作區塊(工作超級區塊)、及未儲存有效資料之空閒區塊(空閒超級區塊)。於本實施形態中，與非零參照計數對應之資料被當作有效資料看待，與零參照計數對應之資料被當作無效資料看待。
作為工作區塊之各超級區塊(SB)由被稱為儲存區塊池(工作區塊池)51之列表管理。另一方面，作為空閒區塊之各超級區塊(SB)由被稱為空閒區塊池52之列表管理。
於本實施形態中，控制器4分配選自空閒區塊池52之一個超級區塊(空閒超級區塊)作為應寫入自主機2接收之寫入資料之寫入目標區塊(寫入目標超級區塊)。於此種情形時，控制器4首先對所選擇之超級區塊(空閒超級區塊)內之各實體區塊執行刪除動作，藉此使該超級區塊內之各實體 區塊成為能寫入之刪除狀態。若當前寫入目標超級區塊整體被來自主機2之寫入資料寫滿，控制器4便會將當前寫入目標超級區塊54移動至儲存區塊池51，自空閒區塊池52中分配一個新超級區塊(空閒超級區塊)作為新寫入目標超級區塊。
當儲存區塊池51內之某超級區塊內，所有資料各自之參照計數因資料更新、取消映射、垃圾回收(GC)等而歸零時，控制器4便會將該超級區塊移動至空閒區塊池52。
於GC動作中，控制器4分配選自空閒區塊池52之一個超級區塊(空閒超級區塊)作為用於GC之複製目標區塊(複製目標超級區塊)53。於此種情形時，控制器4首先對所選擇之超級區塊(空閒超級區塊)內之各實體區塊執行刪除動作，藉此使該超級區塊內之各實體區塊成為能寫入之刪除狀態。控制器4選擇儲存區塊池51內之一個以上超級區塊作為複製源區塊(複製源超級區塊)。若當前複製目標區塊53整體被自複製源區塊(複製源超級區塊)複製之資料寫滿，控制器4便會將當前複製目標區塊53移動至儲存區塊池51。又，控制器4將因GC而不再存在與非零參照計數對應之資料之複製源區塊移動至空閒區塊池52。
以下，對寫入動作、讀出動作、GC動作分別進行說明。
<寫入動作>
若SSD3自主機2接收包含寫入資料及LBA之寫入指令，寫入資料會被暫時儲存至寫入緩衝器(WB)31中。
若NAND型快閃記憶體5中不存在與寫入資料一致之重複資料，則將未使用之iLBA賦予給寫入資料之LBA。然後，控制器4更新LUT32，將被賦予之iLBA與寫入資料之LBA建立關聯。於此種情形時，控制器4亦可把 用以將被賦予之iLBA與寫入資料之LBA建立關聯之查找表快取更新請求(Update request)發送給查找表快取38。藉此，查找表快取38(LUT32)得以更新，被賦予之iLBA與寫入資料之LBA建立關聯。然後，將該寫入資料寫入至寫入目標超級區塊(SB)54中。若寫入資料被寫入至寫入目標超級區塊(SB)54中，控制器4便更新iLUT34，將表示寫入有寫入資料之實體記憶位置之PBA與上述被賦予之iLBA建立關聯。於此種情形時，控制器4亦可把用以將表示寫入有寫入資料之實體記憶位置之PBA與上述被賦予之iLBA建立關聯之查找表快取更新請求(Update request)發送給查找表快取38。藉此，查找表快取38(iLUT34)得以更新，該PBA與上述被賦予之iLBA建立關聯。
若NAND型快閃記憶體5中已存在與寫入資料一致之重複資料，則將賦予給重複資料之iLBA賦予給寫入資料之LBA。然後，控制器4更新LUT32，將賦予給重複資料之iLBA與寫入資料之LBA建立關聯。於此種情形時，控制器4亦可把用以將賦予給重複資料之iLBA與寫入資料之LBA建立關聯之查找表快取更新請求(Update request)發送給查找表快取38。藉此，查找表快取38(LUT32)得以更新，被賦予之iLBA與寫入資料之LBA建立關聯。由於該寫入資料與重複資料一致，所以控制器4並不執行用以將該寫入資料寫入至寫入目標超級區塊(SB)54中之寫入動作。藉此，能執行重複資料刪除。
<讀出動作>
若自主機2接收包含LBA之讀出指令，控制器4便會參照查找表快取38(LUT32)，取得與由該讀出指令指定之LBA對應之iLBA。於此種情形時，控制器4亦可將用以取得與所指定之LBA對應之iLBA之查找表快取 (LUT)參照請求(Lookup request)發送給查找表快取38。
繼而，控制器4基於所取得之iLBA，參照查找表快取38(iLUT34)，取得PBA。於此種情形時，控制器4亦可將用以取得與所取得之iLBA對應之PBA之查找表快取(iLUT)參照請求(Lookup request)發送給查找表快取38。
然後，控制器4從由所取得之PBA指定之實體記憶位置讀出資料，並將所讀出之資料回傳給主機2。於此，有與讀出指令中包含之LBA對應之PBA對應於儲存區塊池(工作區塊池)51內之任一工作區塊或寫入目標超級區塊內之實體記憶位置之情形。又，亦有對應於寫入緩衝器31內之實體記憶位置之情形。
<GC動作>
控制器4分配選自空閒區塊池52之一個超級區塊(空閒超級區塊)作為複製目標區塊(複製目標超級區塊)53。
又，控制器4自儲存區塊池(工作區塊池)51內之工作區塊(工作超級區塊)中選擇被判斷出需要GC動作之一個工作區塊(工作超級區塊)作為GC對象超級區塊(複製源超級區塊)。此時，亦可以在儲存於工作區塊(工作超級區塊)中之無效資料量多於某閾值時，判斷該工作區塊(工作超級區塊)需要GC動作。
控制器4基於與複製源區塊對應之SB管理表，僅將與各非零參照計數對應之資料自複製源區塊複製至複製目標區塊53。然後，控制器4更新iLUT34，將分別表示複製有資料之複製目標區塊53內之實體記憶位置之PBA與對應於該等複製資料之各iLBA建立關聯。於此種情形時，控制器4亦可把用以將表示寫入有寫入資料之實體記憶位置之PBA與上述被賦予之 iLBA建立關聯之查找表快取更新請求(Update request)發送給查找表快取38。藉此，查找表快取38(iLUT34)得以更新，該PBA與對應於上述複製資料之各iLBA建立關聯。
若複製目標區塊53被非零參照計數之資料寫滿，該複製目標區塊53便會被移動至儲存區塊池(工作區塊池)51，作為工作區塊(工作超級區塊)進行管理。
利用圖15及圖16，對本實施形態中所執行之垃圾回收動作進行說明。於此，為了簡化圖式，假設為超級區塊(SB)100-0、100-1、100-2各自具有頁0~3，且於各頁中儲存4個4KB資料之情形。
圖15中表示了藉由垃圾回收動作將包含於超級區塊(SB)100-0內且與各非零參照計數對應之資料複製至超級區塊(SB)100-2之情形。
於超級區塊(SB)100-0中，由PBA0~15分別指定之實體記憶位置上分別儲存有資料A0~P0，其中，資料A0、資料B0、資料G0、資料H0、資料I0、資料K0、資料N0、資料P0係與非零參照計數(Refcount)對應之資料。另一方面，資料C0、資料D0、資料E0、資料F0、資料J0、資料L0、資料M0、資料O0係與零參照計數(Refcount)對應之資料。儲存於超級區塊(SB)100-0中之該等資料各自之參照計數(Refcount)按照PBA0~15之排列順序配置於SB管理表200-0內。
於圖15中，表示出了如下情況：由PBA0指定之實體記憶位置上儲存之資料A0之參照計數(Refcount)為「1」，由PBA1指定之實體記憶位置上儲存之資料B0之參照計數(Refcount)為「2」，由PBA2指定之實體記憶位置上儲存之資料C0之參照計數(Refcount)為「0」，由PBA3指定之實體記憶位置上儲存之資料D0之參照計數(Refcount)為「0」，…由PBA15指定之 實體記憶位置上儲存之P0之參照計數(Refcount)為「2」。
現在，若選擇超級區塊(SB)100-0作為GC對象超級區塊(複製源區塊)，則控制器4基於與超級區塊(SB)100-0對應之SB管理表(於此，為SB管理表200-0)，僅將包含於超級區塊(SB)100-0內且與非零參照計數(Refcount)對應之資料複製至複製目標超級區塊(於此，為超級區塊(SB)100-2)。於圖15中，資料A0、資料B0、資料G0、資料H0、資料I0、資料K0、資料N0、資料P0分別被複製至複製目標超級區塊(於此，為超級區塊(SB)100-2)之由PBA100~107指定之各自之實體記憶位置。
繼而，控制器4將各非零參照計數自與GC對象超級區塊(複製源區塊)對應之SB管理表(於此，為SB管理表200-0)複製至與複製目標超級區塊(SB)對應之SB管理表(於此，為SB管理表200-2)。具體而言，將之前於與複製源超級區塊(超級區塊(SB)100-0)對應之SB管理表200-0中加以管理之與資料A0、資料B0、資料G0、資料H0、資料I0、資料K0、資料N0、資料P0分別對應之參照計數(於此，為1、2、2、3、2、1、1、2)複製至與複製目標超級區塊(超級區塊(SB)100-2)對應之SB管理表200-2。零參照計數(Refcount)不被複製。複製非零參照計數(Refcount)之其結果，如圖15所示，於SB管理表200-2中，與資料A0、資料B0、資料G0、資料H0、資料I0、資料K0、資料N0、資料P0分別對應之參照計數(1、2、2、3、2、1、1、2)依PBA100~107之排列順序配置。
又，iLUT34得以更新，分別表示複製有資料之複製目標超級區塊內之實體記憶位置之PBA與對應於該等複製資料之各iLBA建立關聯。於圖15中，指定資料A0之複製目標超級區塊之實體記憶位置之PBA100與對應於資料A0之iLBA0建立關聯，指定資料B0之複製目標超級區塊之實體記 憶位置之PBA101與對應於資料B0之iLBA1建立關聯，指定資料G0之複製目標超級區塊之實體記憶位置之PBA102與對應於資料G0之iLBA4建立關聯，指定資料H0之複製目標超級區塊之實體記憶位置之PBA103與對應於資料H0之iLBA6建立關聯，指定資料I0之複製目標超級區塊之實體記憶位置之PBA104與對應於資料I0之iLBA12建立關聯，指定資料K0之複製目標超級區塊之實體記憶位置之PBA105與對應於資料K0之iLBA9建立關聯，指定資料N0之複製目標超級區塊之實體記憶位置之PBA106與對應於資料N0之iLBA13建立關聯，指定資料P0之複製目標超級區塊之實體記憶位置之PBA107與對應於資料P0之iLBA17建立關聯。於各超級區塊中，亦可為按每個用戶資料逐一記憶4KB之用戶資料與對應於該用戶資料之iLBA對。於此種情形時，控制器4藉由參照複製源區塊，能容易地識別出與資料A0對應之iLBA0、與資料B0對應之iLBA1、與資料G0對應之iLBA4、與資料H0對應之iLBA6、與資料I0對應之iLBA12、與資料K0對應之iLBA9、與資料N0對應之iLBA13、與資料P0對應之iLBA17，藉此能容易地更新iLUT34。
圖16中表示了於對超級區塊(SB)100-0執行垃圾回收動作後，對超級區塊(SB)100-1執行垃圾回收動作，藉此將包含於超級區塊(SB)100-1內且與各非零參照計數對應之資料複製至超級區塊(SB)100-2之情形。
於超級區塊(SB)100-1之由PBA50~65分別指定之實體記憶位置，分別儲存有資料A1~P1，其中，資料C1、資料D1、資料E1、資料F1、資料I1、資料L1、資料N1、資料O1係參照計數(Refcount)不為零之資料。另一方面，資料A1、資料B1、資料G1、資料H1、資料J1、資料K1、資料M1、資料P1係參照計數(Refcount)為零之資料。儲存於超級區塊 (SB)100-1中之各資料之參照計數(Refcount)依PBA50~65之排列順序配置於SB管理表200-1內。
於圖16中，表示出了：由PBA50指定之實體記憶位置上儲存之資料A1之參照計數(Refcount)為「0」，由PBA51指定之實體記憶位置上儲存之資料B1之參照計數(Refcount)為「0」，由PBA52指定之實體記憶位置上儲存之資料C1之參照計數(Refcount)為「2」，由PBA53指定之實體記憶位置上儲存之資料D1之參照計數(Refcount)為「1」，…由PBA65指定之實體記憶位置上儲存之資料P1之參照計數(Refcount)為「0」。
現在，若選擇超級區塊(SB)100-1作為GC對象超級區塊(複製源區塊)，則控制器4基於與GC對象超級區塊(複製源區塊)對應之SB管理表(於此，為SB管理表200-1)，而僅將包含於超級區塊(SB)100-1中且與非零參照計數(Refcount)對應之資料複製至複製目標超級區塊(於此，為超級區塊(SB)100-2)。於圖16中，資料C1、資料D1、資料E1、資料F1、資料I1、資料L0、資料N1、資料O1分別被複製至複製目標超級區塊(於此，為超級區塊(SB)100-2)之由PBA108~115指定之實體記憶位置。
繼而，控制器4將各非零參照計數自與GC對象超級區塊(複製源區塊)對應之SB管理表(於此，為SB管理表200-1)複製至與複製目標超級區塊(SB)對應之SB管理表(於此，為SB管理表200-2)。具體而言，將之前於與複製源超級區塊(超級區塊(SB)100-1)對應之SB管理表200-1中加以管理之資料C1、資料D1、資料E1、資料F1、資料I1、資料L0、資料N1、資料O1之參照計數(Refcount)複製至與複製目標超級區塊(超級區塊(SB)100-2)對應之SB管理表200-2。複製參照計數(Refcount)之其結果，於圖16中，SB管理表200-2上依PBA108~115之排列順序配置有資料C1、資料 D1、資料E1、資料F1、資料I1、資料L0、資料N1、資料O1各自之參照計數(Refcount)。
又，iLUT34得以更新，分別表示複製有資料之複製目標超級區塊內之實體記憶位置之PBA與對應於所複製資料之各iLBA建立關聯。於圖16中，指定資料C1之複製目標超級區塊之實體記憶位置之PBA108與對應於資料C1之iLBA23建立關聯，指定資料D1之複製目標超級區塊之實體記憶位置之PBA109與對應於資料D1之iLBA32建立關聯，指定資料E1之複製目標超級區塊之實體記憶位置之PBA110與對應於資料E1之iLBA25建立關聯，指定資料F1之複製目標超級區塊之實體記憶位置之PBA111與對應於資料F1之iLBA30建立關聯，指定資料I1之複製目標超級區塊之實體記憶位置之PBA112與對應於資料I1之iLBA21建立關聯，指定資料L1之複製目標超級區塊之實體記憶位置之PBA113與對應於資料L1之iLBA35建立關聯，指定資料N1之複製目標超級區塊之實體記憶位置之PBA114與對應於資料N1之iLBA22建立關聯，指定資料O1之複製目標超級區塊之實體記憶位置之PBA115與對應於資料O1之iLBA31建立關聯。
如上所述，能不變更於LUT32中加以管理之LBA與iLBA之關係，只需使用與複製源區塊對應之SB管理表內之參照計數資訊便能執行垃圾回收動作。
圖17之流程圖表示本實施形態中之資料寫入動作之順序。
圖17之左下方表示出了SB管理表200-0、超級區塊(SB)100-0、LUT32、雜湊LUT33、iLUT34之資料結構。SB管理表200-0上配置有與儲存於超級區塊(SB)100-0中之各資料對應之參照計數(Refcount)。超級區塊(SB)100-0中儲存有資料及與該資料對應之iLBA或LBA。LUT32儲存 有各LBA與各iLBA之對應關係。再者，於NAND型快閃記憶體5內不存在與某寫入資料一致之重複資料之情形時，該寫入資料之LBA亦可直接關聯於PBA而非iLBA。於此種情形時，超級區塊(SB)100-0中亦可儲存有該寫入資料與對應於該寫入資料之LBA對，而非該寫入資料與iLBA對。雜湊LUT33管理各雜湊值(資料之Hash(Data))與各iLBA之對應關係。iLUT34管理各iLBA與各PBA之對應關係。
繼而，對寫入動作進行說明。
控制器4首先對LUT32中是否存在與自主機2接收之寫入指令中包含之LBA對應之iLBA進行判定(步驟S101)。若LUT32中不存在與寫入指令中包含之LBA對應之iLBA(步驟S101中為否)，則控制器4對LUT32中是否存在與寫入指令中包含之LBA對應之PBA進行判定(步驟S102)。若LUT32中不存在與寫入指令中包含之LBA對應之iLBA/PBA(步驟S102中為否)，則表示寫入指令中包含之寫入資料係第一次被寫入之資料，而非已寫入至NAND型快閃記憶體5內之資料之更新資料(首次LBA之寫入)。於此種情形時，進入下述步驟S104。
若LUT32中存在與寫入指令中包含之LBA對應之iLBA(步驟S101中為是)，則控制器4判定寫入資料係已寫入至NAND型快閃記憶體5內之資料之更新資料。即，該寫入資料之寫入並非第一次之寫入，而係第二次及第二次以上之寫入(第二次及第二次以上之LBA寫入)。於此種情形時，更新SB管理表200-0(步驟S103)。於此，控制器4將與已寫入之資料對應之參照計數減去1。其原因在於，該寫入資料(更新資料)與已寫入之資料(更新前資料)不同，該更新前資料不再會被該寫入資料之LBA參照。此時，控制器4自iLUT34取得與對應於寫入指令中包含之LBA之iLBA對應之 PBA，於SB管理表200-0中，將與所取得之PBA對應之資料之參照計數(Refcount)減去「1」。
其次，控制器4計算寫入資料之雜湊值(步驟S104)。然後，控制器4對雜湊LUT33中是否存在與藉由計算而獲得之雜湊值對應之iLBA進行判定(步驟S105)。若雜湊LUT33中已存在與所獲得之雜湊值對應之iLBA(步驟S105中為是)，則控制器4參照iLUT34，取得與對應於所獲雜湊值之iLBA對應之PBA之資料，並將所取得之資料與接收之寫入資料(輸入資料)加以比較，對兩資料是否一致進行判定(步驟S106)。若兩資料一致(步驟S106中為是)，則NAND型快閃記憶體5內會存在與寫入資料一致之重複資料。於此種情形時，不將寫入資料寫入至寫入目標超級區塊(超級區塊(SB)100-0)，而更新管理與賦予給所獲雜湊值之iLBA對應之PBA之參照計數(Refcount)之SB管理表200-0，將與該PBA對應之參照計數(Refcount)增加「1」(步驟S114)。又，更新LUT32，將與所獲得之雜湊值對應之iLBA與寫入指令中包含之LBA建立關聯(步驟S115)。
另一方面，若兩資料不一致(步驟S106中為否)，則NAND型快閃記憶體5內不會存在重複資料。又，於雜湊LUT33中不存在與所獲得之雜湊值對應之iLBA之情形時(步驟S105中為否)，亦不會存在重複資料。
於步驟S106中為否、或步驟S105中為否之情形時，控制器4對與供寫入資料寫入之寫入目標超級區塊(超級區塊(SB)100-0)對應之於SB管理表200-0中加以管理之參照計數(Refcount)中之最大參照計數(Refcount)是否為「1」進行判定(步驟S107)。若最大參照計數(Refcount)為「1」(步驟S107中為是)，則亦可不使用iLBA，而使LBA與PBA直接建立關聯。當然，亦可始終使用iLBA。
若最大參照計數(Refcount)不為「1」(步驟S107中為否)，則更新雜湊LUT33(步驟S110)。此時，對於步驟S104中獲得之雜湊值賦予新iLBA(未使用之iLBA)。而且，所獲得之雜湊值與被賦予之iLBA之對應關係儲存於雜湊LUT33中。再者，於步驟S105中為否之情形時，在與於步驟S104中獲得之雜湊值對應之雜湊LUT33內之條目已存在iLBA，因此亦可對該條目追加新iLBA(未使用之iLBA)。
又，更新iLUT34，將表示供寫入資料寫入之預定之NAND型快閃記憶體5內之實體記憶位置之PBA與被賦予之iLBA建立關聯(步驟S111)。
進而，更新寫入目標超級區塊(超級區塊(SB)100-0)(步驟S112)。此時，寫入資料與被賦予之iLBA一併被寫入至寫入目標超級區塊(超級區塊(SB)100-0)之與供寫入資料寫入之預定之PBA(新PBA)對應之實體記憶位置。
進而，更新與寫入目標超級區塊(超級區塊(SB)100-0)對應之SB管理表200-0(步驟S113)。此時，將與寫入資料對應之參照計數(Refcount)、即與寫入有該寫入資料之實體記憶位置之PBA對應之參照計數(Refcount)設定為「1」。
又，更新LUT32，將被賦予之iLBA與寫入指令中包含之LBA建立關聯(步驟S115)。
若最大參照計數(Refcount)為「1」(步驟S107中為是)，則寫入目標超級區塊(超級區塊(SB)100-0)中不會存在被2個以上LBA參照之資料。於此種情形時，能判斷出寫入至寫入目標超級區塊(超級區塊(SB)100-0)之寫入資料可不使用iLBA而利用PBA直接管理。再者，於該狀況下亦可還使用iLBA進行管理。
繼而，更新寫入目標超級區塊(超級區塊(SB)100-0)(步驟S108)。此時，寫入資料與寫入指令中包含之LBA一併被寫入至寫入目標超級區塊(超級區塊(SB)100-0)之與供寫入資料寫入之預定之PBA(新PBA)對應之實體記憶位置。
然後，更新與寫入目標超級區塊(超級區塊(SB)100-0)對應之SB管理表200-0(步驟S109)。此時，將與寫入資料對應之參照計數(Refcount)、即與寫入有該寫入資料之實體記憶位置之PBA對應之參照計數(Refcount)設定為「1」。
又，更新LUT32，將寫入有寫入資料之實體記憶位置之PBA與寫入指令中包含之LBA建立關聯(步驟S116)。
又，於LUT32中存在與寫入指令中包含之LBA對應之PBA之情形時(步驟S102中為是)，寫入資料之寫入即為第二次及第二次以上之寫入(第二次及第二次以上之LBA寫入)。又，由於不存在與寫入指令中包含之LBA對應之iLBA所以不存在重複資料，因此處於以不使用iLBA之方法便能進行資料管理之狀況下。
然後，將寫入資料寫入至寫入目標超級區塊(超級區塊(SB)100-0)中，更新LUT32，將指定寫入有寫入資料之實體記憶位置之新PBA與寫入指令中包含之LBA建立關聯(步驟S116)。
圖18之流程圖表示垃圾回收動作之順序。
控制器4選擇應進行GC之超級區塊作為GC對象超級區塊(複製源區塊)(步驟S201)。其次，控制器4參照SB管理表，特定與非零參照計數(Refcount)對應之PBA(步驟S202)。
繼而，控制器4將與所特定之PBA對應之實體記憶位置上儲存之資 料，即，將與非零參照計數對應之資料複製至複製目標區塊(步驟S203)。其後，控制器4更新iLUT34，將表示儲存有複製資料之複製目標區塊內之實體記憶位置之PBA與對應於該複製資料之iLBA建立關聯(步驟S204)。於步驟S204中，控制器4進而向與複製目標區塊對應之SB管理表複製與該複製資料對應之參照計數(Refcount)。
其次，控制器4對GC對象超級區塊(複製源區塊)內是否存在與非零參照計數(Refcount)對應之資料進行判定(步驟S205)。
若GC對象超級區塊(複製源區塊)內存在與非零參照計數(Refcount)對應之資料(步驟S205中為否)，則進入步驟S202之處理。再者，反覆進行步驟S202~S204之處理，直至GC對象超級區塊(複製源區塊)內不再存在與非零參照計數(Refcount)對應之資料為止。
若GC對象超級區塊(複製源區塊)內不再存在與非零參照計數(Refcount)對應之資料(步驟S205中為是)，則垃圾回收動作完成。
圖19之流程圖表示本實施形態中之資料讀出動作之順序。
若自主機2接收讀出指令(步驟S301中為是)，則控制器4參照LUT32，取得與讀出指令中包含之LBA對應之iLBA(步驟S302)。其次，控制器4參照iLUT34，取得與所取得之iLBA對應之PBA(步驟S303)。然後，控制器4讀出與所取得之PBA對應之實體記憶位置上儲存之資料(步驟S304)。
圖20表示各超級區塊管理表內之參照計數記憶區域部之構成例。
SB管理表係針對每個超級區塊(SB)逐一而設。SB管理表保持對應超級區塊(SB)之各種相關管理資訊(元資料)。管理資訊(元資料)之例可包括對應超級區塊(SB)之編程/擦除週期數、對應超級區塊(SB)之無效資料量 (或有效資料量)。
進而，SB管理表具有參照計數記憶區域，該參照計數記憶區域用以儲存對應超級區塊(SB)中所能儲存之全部資料各自之參照計數。各SB管理表內之一個參照計數指針指示出一定尺寸(例如，1024位元)之一個參照計數記憶區域部之位置。各SB管理表包含複數個參照計數指針。藉此，各SB管理表與複數個參照計數記憶區域部建立關聯。上述複數個參照計數記憶區域部被用作對應SB管理表用之參照計數記憶區域。
例如，於一個超級區塊之尺寸為4GB之情形時，1M個4KB資料儲存於一個超級區塊中。此種情形時，一個SB管理表需要有能保持1M個參照計數之參照計數記憶區域。
若一個參照計數位元長度為2位元，則「00」用以表示對應資料未被任何邏輯位址參照，「01」用以表示對應資料被一個邏輯位址參照，「10」用以表示對應資料被2個邏輯位址參照，「11」用以表示對應資料被3個邏輯位址參照。因此，所能管理之最大參照計數值為3。
若一個參照計數位元長度為3位元，則所能管理之最大參照計數值為7。若一個參照計數位元長度為4位元，則所能管理之最大參照計數值為15。若一個參照計數位元長度為8位元，則所能管理之最大參照計數值為255。
雖然如上所述，參照計數位元長度越長，則所能管理之最大參照計數值越為增加，但是被參照計數記憶區域消耗之記憶體資源量亦會增加。
通常，每個資料之參照計數值都不相同之情形較多。因此，相同超級區塊中會混合存在參照計數互不相同之資料。參照計數不同之資料混合存在於相同超級區塊此種狀況成為使被確保用作參照計數記憶區域之記憶 體資源遭到浪費之原因。
於本實施形態中，藉由GC，具有較大參照計數之資料群與具有較小參照計數之資料群得以相互分離。藉此，能將屬於相同參照計數範圍之資料彼此儲存至相同超級區塊中。其結果，能對集中了具有較大參照計數之資料群之超級區塊，確保包含能儲存各自具有較長位元長度之複數個參照計數之大尺寸參照計數記憶區域之SB管理表，能對集中了具有較小參照計數之資料群之超級區塊，確保包含能儲存各自具有較短位元長度之複數個參照計數之小尺寸參照計數記憶區域之SB管理表。
因此，各SB管理表構成為能改變參照計數記憶區域之尺寸。各SB管理表亦可預先含有數量與構成最大尺寸之參照計數記憶區域所需之參照計數記憶區域部數相同之參照計數指針。
於圖20中，例示了包含不同尺寸之參照計數記憶區域之3種SB管理表。
SB管理表200-0被設定成包含能儲存各為1位元之複數個參照計數之最小尺寸之參照計數記憶區域之SB管理表。
於SB管理表200-0中，僅利用SB管理表200-0中包含之所有參照計數指針中之1000個參照計數指針。一個參照計數指針表示具有1024位元長度之一個參照計數記憶區域部之位置。各參照計數之位元長度為1位元。因此，參照計數記憶區域部包含與1024個4KB資料分別對應之1024個點陣圖旗標(BM)。參照計數(點陣圖旗標)=「0」表示參照對應4KB資料之邏輯位址之數量為零。參照計數(點陣圖旗標)=「1」表示參照對應4KB資料之邏輯位址之數量為1。
SB管理表200-1被設定成包含能儲存各為2位元之複數個參照計數之 參照計數記憶區域之SB管理表。
於SB管理表200-1中，利用SB管理表200-1中包含之所有參照計數指針中之2000個參照計數指針。一個參照計數指針表示具有1024位元長度之一個參照計數記憶區域部之位置。各參照計數之位元長度為2位元。一個參照計數記憶區域部包含512個參照計數。因此，為了儲存與1024個4KB資料分別對應之1024個參照計數，要利用2個參照計數記憶區域部。
SB管理表200-2被設定成包含能儲存各為4位元之複數個參照計數之參照計數記憶區域之SB管理表。
於SB管理表200-2中，利用SB管理表200-2中包含之所有參照計數指針中之4000個參照計數指針。一個參照計數指針表示具有1024位元長度之一個參照計數記憶區域部之位置。各參照計數之位元長度為4位元。一個參照計數記憶區域部包含256個參照計數。因此，為了儲存與1024個4KB資料分別對應之1024個參照計數，要利用4個參照計數記憶區域部。
與SB管理表200-0建立有關聯之超級區塊(SB)100-0被用作用以儲存參照計數(Refcount)=0~1之資料之超級區塊(SB)。與SB管理表200-1建立有關聯之超級區塊(SB)100-1主要被用作用以儲存參照計數(Refcount)=2~3之資料之超級區塊(SB)。
與SB管理表200-2建立有關聯之超級區塊(SB)100-2主要被用作用以儲存參照計數(Refcount)=4~15之資料之超級區塊(SB)。
圖21表示將對應於較大參照計數(Refcount)之資料與對應於較小參照計數(Refcount)之資料分離之垃圾回收動作之概要。
於此，分配有複製目標超級區塊(SB)221、222。又，SB管理表221A、222A分別與複製目標超級區塊(SB)221、222建立有關聯。又， SB管理表221A具有能儲存各為4位元長度之複數個參照計數(Refcount)之參照計數記憶區域，SB管理表222A具有能儲存各為2位元長度之複數個參照計數(Refcount)之參照計數記憶區域。
超級區塊(SB)210中儲存有具有較大參照計數(Refcount=4~15)之資料d1、資料d2、資料d4、資料d5、具有較小參照計數(Refcount=1~3)之資料d6、資料d8、具有零參照計數(Refcount)之資料d3、d7等。
超級區塊(SB)211中儲存有具有較大參照計數(Refcount=4~15)之資料d17、具有較小參照計數(Refcount=1~3)之資料d11、資料d13、資料d14、資料d18、具有零參照計數之資料d12、資料d15、資料d16等。
超級區塊(SB)212中儲存有具有較大參照計數(Refcount=4~15)之資料d22、資料d23、資料d24、具有較小參照計數(Refcount=1~3)之資料d27、資料d28、具有零參照計數之資料d21、資料d25、資料d26等。
於選擇超級區塊(SB)210作為GC對象超級區塊(複製源區塊)之情形時，控制器4基於與超級區塊(SB)210對應之SB管理表，將包含於超級區塊(SB)210中且具有屬於第1參照計數範圍(於此，為1~3)之參照計數之資料集合複製至複製目標超級區塊(SB)222，並將包含於超級區塊(SB)210中且具有屬於第2參照計數範圍(於此，為4~15)之參照計數之資料集合複製至複製目標超級區塊(SB)221，其中上述第2參照計數範圍具有較第1參照計數範圍之上限(於此，為3)大之下限。
具體而言，將具有較大參照計數(Refcount=4~15)之資料d1、資料d2、資料d4、資料d5複製至複製目標超級區塊(SB)221，並將具有較小參照計數(Refcount=1~3)之資料d6、資料d8複製至複製目標超級區塊(SB)222。
其次，於選擇超級區塊(SB)211作為GC對象超級區塊(複製源區塊)之情形時，控制器4基於與超級區塊(SB)211對應之SB管理表，將包含於超級區塊(SB)211中且具有屬於第1參照計數範圍(於此，為1~3)之參照計數之資料集合複製至複製目標超級區塊(SB)222，並將包含於超級區塊(SB)211中且具有屬於第2參照計數範圍(於此，為4~15)之參照計數之資料集合複製至複製目標超級區塊(SB)221，其中上述第2參照計數範圍具有較第1參照計數範圍之上限(於此，為3)大之下限。
具體而言，將具有較大參照計數(Refcount=4~15)之資料d17複製至複製目標超級區塊(SB)221，並將具有較小參照計數(Refcount=1~3)之資料d11、資料d13、資料d14、資料d18複製至複製目標超級區塊(SB)222。
其次，於選擇超級區塊(SB)212作為GC對象超級區塊(複製源區塊)之情形時，控制器4基於與超級區塊(SB)212對應之SB管理表內，將包含於超級區塊(SB)212中且具有屬於第1參照計數範圍(於此，為1~3)之參照計數之資料集合複製至複製目標超級區塊(SB)222，將包含於超級區塊(SB)212中且具有屬於第2參照計數範圍(於此，為4~15)之參照計數之資料集合複製至複製目標超級區塊(SB)221；上述第2參照計數範圍具有較第1參照計數範圍之上限(此處為3)更大之下限。
具體而言，將具有較大參照計數(Refcount=4~15)之資料d22、資料d23、資料d24複製至複製目標超級區塊(SB)221，將具有較小參照計數(Refcount=1~3)之資料d27、資料d28複製至複製目標超級區塊(SB)222。
如此，於GC動作中，應被複製資料之複製目標區塊會隨著該資料之 參照計數(Refcount)之值而變更。其結果，能將屬於相同參照計數範圍之資料集中於相同之超級區塊。藉此，能僅將具有較大參照計數之資料群集中於已與能儲存各自具有較長位元長度之複數個參照計數之SB管理表建立關聯之超級區塊，且，能僅將具有較小參照計數之資料群集中於已與能儲存各自具有較短位元長度之複數個參照計數之SB管理表建立關聯之超級區塊。藉此，與參照計數不同之資料混合存在於相同超級區塊之狀況相比，能大幅降低參照計數記憶區域用之記憶體資源之消耗量。
又，屬於相同參照計數範圍之資料群係具有類似生命週期之資料群。因此，能提高使相同超級區塊中包含之各資料於同一時期無效化之概率，藉此能抑制GC之頻率。此能降低寫入放大，其結果，能將SSD3之壽命延長至最大限度。
圖22表示垃圾回收動作中包含之資料複製動作及參照計數複製動作。
於此，選擇超級區塊(SB)100-0作為GC對象超級區塊(GC之複製源區塊)，將超級區塊(SB)100-2及超級區塊100-3分配作為複製目標超級區塊。
又，SB管理表200-0、200-2、200-3分別與超級區塊(SB)100-0、100-2、100-3建立關聯。又，SB管理表200-2具有能儲存各為2位元長度之複數個參照計數(Refcount)之參照計數記憶區域，SB管理表200-3具有能儲存各為3位元長度之複數個參照計數(Refcount)之參照計數記憶區域。
於作為GC對象超級區塊(GC之複製源區塊)之超級區塊(SB)100-0中，儲存有與非零參照計數對應之資料A0、資料B0、資料G0、資料H0、 資料I0、資料K0、資料N0、資料P0、與零參照計數對應之資料C0、資料D0、資料E0、資料F0、資料J0、資料L0、資料M0、資料O0。
又，與參照計數(Refcount)=4~7對應之資料即資料I0、資料K0、資料N0、資料P0分別儲存於超級區塊(SB)100-0內之由PBA8、PBA10、PBA13、PBA15指定之實體記憶位置。與參照計數(Refcount)=1~3對應之資料即資料A0、資料B0、資料G0、資料H0分別儲存於超級區塊(SB)100-0內之由PBA0、PBA1、PBA6、PBA7指定之實體記憶位置。參照計數為零之資料C0、資料D0、資料E0、資料F0、資料J0、資料L0、資料M0、資料O0分別儲存於超級區塊(SB)100-0內之與PBA2、PBA3、PBA4、PBA5、PBA9、PBA11、PBA12、PBA14對應之實體記憶位置。
於與超級區塊(SB)100-0對應之SB管理表200-0中，儲存有儲存於超級區塊(SB)100-0內之資料各自之參照計數(Refcount)。
若對超級區塊(SB)100-0開始GC動作，則超級區塊(SB)100-0內之資料A0、資料B0、資料G0、資料H0分別被複製至作為複製目標超級區塊之超級區塊(SB)100-2內之由PBA100、PBA101、PBA102、PBA103指定之實體記憶位置。隨之，與於SB管理表200-0中加以管理之資料A0、資料B0、資料G0、資料H0分別對應之參照計數(「1」、「2」、「2」、「3」)被複製至與作為複製目標超級區塊之超級區塊(SB)100-2對應之SB管理表200-2。此時，於SB管理表200-2中，與資料A0、資料B0、資料G0、資料H0分別對應之參照計數(「1」、「2」、「2」、「3」)依此順序連續地配置。
又，超級區塊(SB)100-0內之資料I0、資料K0、資料N0、資料P0分別被複製至作為複製目標超級區塊之超級區塊(SB)100-3內之由PBA150、PBA151、PBA152、PBA153指定之各自之實體記憶位置。隨 之，與於SB管理表200-0中加以管理之資料I0、資料K0、資料N0、資料P0分別對應之參照計數(「4」、「5」、「4」、「6」)被複製至與作為複製目標超級區塊之超級區塊(SB)100-3對應之SB管理表200-3。此時，於SB管理表200-2中，與資料I0、資料K0、資料N0、資料P0分別對應之參照計數(「4」、「5」、「4」、「6」)依此順序連續地配置。
利用圖23及圖24，對與某資料對應之參照計數(Refcount)溢出之情形時執行之資料複製動作進行說明。於此，與超級區塊(SB)100-0建立有關聯之SB管理表200-0具有能儲存各為2位元長度之複數個參照計數(Refcount)之參照計數記憶區域，與超級區塊(SB)100-1建立有關聯之SB管理表200-1具有能儲存各為3位元長度之複數個參照計數(Refcount)之參照計數記憶區域。
於超級區塊(SB)100-0中，與參照計數(Refcount)=1~3對應之資料即資料A0、資料C0、資料D0、資料E0、資料F0、資料G0、資料H0、資料I0、資料J0、資料K0、資料L0、資料M0、資料N0、資料O0、資料P0分別儲存於由PBA0、PBA2、PBA3、PBA4、PBA5、PBA6、PBA7、PBA8、PBA9、PBA10、PBA11、PBA12、PBA13、PBA14、PBA15指定之實體記憶位置，與參照計數(Refcount)=0對應之資料即資料B0儲存於由PBA1指定之實體記憶位置。
於超級區塊(SB)100-1中，與參照計數=4~7對應之資料即資料A1、資料B1、資料C1、資料D1、資料E1、資料F1、資料G1、資料H1、資料I1、資料J1、資料K1分別儲存於由PBA50、PBA51、PBA52、PBA53、PBA54、PBA55、PBA56、PBA57、PBA58、PBA59、PBA60指定之實體記憶位置。於由PBA61~PBA65指定之實體記憶位置未儲存 資料，而對應於刪除狀態之實體記憶位置(能利用之實體記憶位置)。
與儲存於超級區塊(SB)100-0中之資料H0對應之參照計數值為「3」。因此，與資料H0對應之參照計數值因來自主機2之與資料H0一致之寫入資料之接收，而超過以能儲存於SB管理表200-0參照計數記憶區域之各參照計數之位元長度(於此，為2位元)所能表現之最大值(於此，為3)(溢出)。
於此種情形時，控制器4如圖24所示，將資料H0複製至與SB管理表200-1建立有關聯之超級區塊(SB)100-1，上述SB管理表200-1包含能儲存各自具有較SB管理表200-0長之位元長度之複數個參照計數之參照計數記憶區域。資料H0會被複製至超級區塊(SB)100-1內之下個可利用實體記憶位置(於此，為由PBA61指定之實體記憶位置)。隨之，將表示複製源超級區塊(超級區塊(SB)100-0)內之原來儲存有資料H0之實體記憶位置之PBA7之參照計數(Refcount)由3更新為0。其目的在於將由PBA7指定之實體記憶位置上儲存之資料無效化。又，資料H0之參照計數(於此，為「4」)會被複製至與PBA61對應之SB管理表200-1內之位置。
利用圖25，對與某資料對應之參照計數(Refcount)溢出之情形時執行之參照計數記憶區域擴張動作進行說明。於此，與超級區塊(SB)100-0建立有關聯之SB管理表200-0具有能儲存各為2位元長度之複數個參照計數之參照計數記憶區域。
現在，於超級區塊(SB)100-0中，與參照計數(Refcount)=1~3對應之資料即資料A0、資料C0、資料D0、資料E0、資料F0、資料G0、資料H0、資料I0、資料J0、資料K0、資料L0、資料M0、資料N0、資料O0、資料P0分別儲存於由PBA0、PBA2、PBA3、PBA4、PBA5、PBA6、PBA7、PBA8、PBA9、PBA10、PBA11、PBA12、PBA13、PBA14、 PBA15指定之實體記憶位置，與參照計數(Refcount)=0對應之資料即資料B0儲存於由PBA1指定之實體記憶位置。
控制器4於與超級區塊(SB)100-0內之資料H0對應之參照計數值因來自主機2之包含與資料H0一致之寫入資料之寫入指令之接收，而超過以能儲存於SB管理表200-0參照計數記憶區域之各參照計數之位元長度所能表現之最大值之情形時，藉由將SB管理表200-0之參照計數記憶區域之尺寸擴張，而加長能儲存於SB管理表200-0參照計數記憶區域之各參照計數之位元長度。
具體而言，於自主機2接收包含與資料H0一致之寫入資料之寫入指令後，資料H0之參照計數(Refcount)自3增加至4。於此種情形時，資料H0之參照計數(Refcount)超過能儲存於與超級區塊(SB)100-0對應之SB管理表200-0參照計數記憶區域之參照計數最大值(溢出)。此時，如圖25之右側所示，例如以使各參照計數之位元長度自2位元變更為4位元之方式，擴張SB管理表200-0參照計數記憶區域之尺寸。於此種情形時，控制器4亦可將先前之參照計數記憶區域開放，而且，亦可取而代之，重新確保較大尺寸之參照計數記憶區域。
然後，控制器4將與資料H0對應之參照計數增加1，藉此將與資料H0對應之參照計數自「3」變更為「4」。
其次，利用圖26，對垃圾回收對象區塊(複製源區塊)候補之選擇條件進行說明。
控制器4基於超級區塊(SB)各自之無效資料量(或有效資料量)，而自該等超級區塊(SB)中選擇GC對象區塊(複製源區塊)候補。於此種情形時，控制器4將集中有具有較大參照計數之資料之超級區塊(SB)優先於集 中有具有較小參照計數之資料之超級區塊(SB)地選作GC之複製源區塊候補。即，參照計數越大之資料，該資料被覆寫之概率越低，因此即使集中有具有較大參照計數之資料之超級區塊(SB)相較於集中有具有較小參照計數之資料之超級區塊(SB)而言有效資料量更多，控制器4亦將其選作GC之複製源區塊候補。
複數個超級區塊(SB)分為集中有屬於第1參照計數範圍之資料集合之超級區塊(SB)群、及集中有屬於第2參照計數範圍之資料集合之超級區塊(SB)群。
於圖26中，超級區塊(SB)100-0歸為集中有屬於某參照計數範圍(第1參照計數範圍)之資料之超級區塊(SB)群、即集中有具有較小參照計數之資料之超級區塊(SB)群，超級區塊(SB)100-1歸為集中有屬於具有較第1參照計數範圍之上限大之下限之參照計數範圍(第2參照計數範圍)之資料之超級區塊(SB)群、即集中有具有較大參照計數之資料之超級區塊(SB)群。
此時，控制器4對於超級區塊(SB)100-0，於滿足無效資料量大於某閾值Xa之條件之情形時，將其選作用於GC之複製源區塊候補。另一方面，控制器4對於超級區塊(SB)100-1，於滿足無效資料量大於閾值Xb之條件之情形時，將其選作用於GC之複製源區塊候補，其中上述閾值Xb係小於閾值Xa之值。
如上所述，參照計數越大之資料，該資料被覆寫之概率越低。因此，通常，集中有具有較大參照計數之資料之超級區塊(SB)內之各資料會於較長時間內被持續利用，該超級區塊(SB)再用於其他資料之記憶之概率變低。因此，SSD3之超額配置會以集中有具有較大參照計數之資料之超級區塊(SB)內所存在之無效資料(具有零參照計數之資料)之量而減少。於 本實施形態中，如上所述，集中有具有較大參照計數之資料之超級區塊(SB)即使相較於集中有具有較小參照計數之資料之超級區塊(SB)而言有效資料量更多，亦會被選作GC之複製源區塊候補。因此，能降低SSD3之超額配置之減少，能降低寫入放大。
圖27表示選擇用於GC之複製源區塊候補之動作。
超級區塊(SB)100-0集中有與參照計數=1~3對應之資料。於超級區塊(SB)100-0中，資料A0~資料P0分別儲存於由PBA0~15指定之實體記憶位置。由SB管理表200-0可知，儲存於超級區塊(SB)100-0中之資料之中參照計數為零之資料係由PBA1指定之資料B0、由PBA4指定之資料E0、由PBA11指定之資料L0、由PBA12指定之資料M0。控制器4於超級區塊(SB)100-0之無效資料量大於閾值X1之條件下，選擇超級區塊(SB)100-0作為GC對象區塊候補、即用於GC之複製源區塊候補。無效資料量亦可藉由具有零參照計數之資料數而表達。於此種情形時，超級區塊(SB)100-0之當前無效資料量為4。若將閾值X1設定為4，則超級區塊(SB)100-0不滿足上述條件，因此不會被選作用於GC之複製源區塊候補。
於超級區塊(SB)100-1中，集中有與參照計數=4~7對應之資料。於超級區塊(SB)100-1中，資料A1~資料P1分別儲存於由PBA50~65指定之實體記憶位置。由SB管理表200-1可知，儲存於超級區塊(SB)100-1中之資料之中參照計數為零之資料係由PBA53指定之資料D1、由PBA55指定之資料F1、由PBA60指定之資料K1、由PBA62指定之資料M1。控制器4於超級區塊(SB)100-1之無效資料量大於閾值X2之條件下，選擇超級區塊(SB)100-1作為GC對象區塊候補、即用於GC之複製源區塊候補。超級區塊(SB)100-1之當前無效資料量與超級區塊(SB)100-0之無效資料量相同為 4。閾值X2小於閾值X1。若將閾值X1設定為4，則閾值X2會被設定為3以下之值。因此，超級區塊(SB)100-1滿足上述條件，所以會被選作用於GC之複製源區塊候補。
圖28之流程圖表示選擇複製源區塊候補之動作之順序。於此，為了簡化說明，假設為如下情形：將NAND型快閃記憶體5之所有超級區塊(SB)分為集中有屬於參照計數為1~3之範圍之資料之超級區塊(SB)群、集中有屬於參照計數為4~7之範圍之資料之超級區塊(SB)群、及集中有屬於參照計數為8~15之範圍之資料之超級區塊(SB)群。
首先，控制器4選擇某一個超級區塊(SB)(步驟S401)。然後，控制器4參照與所選擇之超級區塊(SB)建立有關聯之SB管理表(步驟S402)，基於儲存於所選超級區塊(SB)中之所有資料之參照計數(Refcount)，而自其等中特定最大之參照計數(Refcount)(步驟S403)。
若所特定之最大參照計數(Refcount)未達4(步驟S404中為是)，則控制器4判定所選超級區塊(SB)屬於集中有屬於參照計數為1~3之範圍之資料之超級區塊(SB)群。然後，控制器4對所選超級區塊(SB)之無效資料量是否多於閾值X1進行判定(步驟S405)。
若無效資料量多於閾值X1(步驟S405中為是)，則控制器4將所選擇之超級區塊(SB)選作GC對象超級區塊(複製源區塊)候補(步驟S406)。若無效資料量為閾值X1以下(步驟S405中為否)，則控制器4不將所選擇之超級區塊(SB)選作GC對象超級區塊(複製源區塊)候補(步驟S407)。
若所特定之最大參照計數(Refcount)為4以上且未達8(步驟S404中為否，且步驟S408中為是)，則控制器4判定所選超級區塊(SB)屬於集中有屬於參照計數為4~7之範圍之資料之超級區塊(SB)群。然後，控制器4對所 選超級區塊(SB)之無效資料量是否多於閾值X2(<X1)進行判定(步驟S409)。
若無效資料量多於閾值X2(步驟S409中為是)，則控制器4將所選擇之超級區塊(SB)選作GC對象超級區塊(複製源區塊)候補(步驟S410)。若無效資料量為閾值X2以下(步驟S409中為否)，則控制器4不將所選擇之超級區塊(SB)選作GC對象超級區塊(複製源區塊)候補(步驟S411)。
若所特定之最大參照計數(Refcount)為8以上(步驟S408中為否)，則控制器4判定所選超級區塊(SB)屬於集中有屬於參照計數為8~15之範圍之資料之超級區塊(SB)群。然後，控制器4對所選超級區塊(SB)之無效資料量是否多於閾值X3(<X2)進行判定(步驟S412)。
若無效資料量多於閾值X3(步驟S412中為是)，則控制器4將所選擇之超級區塊(SB)選作GC對象超級區塊(複製源區塊)候補(步驟S413)。若無效資料量為閾值X3以下(步驟S412中為否)，則控制器4不將所選擇之超級區塊(SB)選作GC對象超級區塊(複製源區塊)候補(步驟S414)。
圖29表示寫入至超級區塊(SB)內各頁中之用戶資料與中間位址(iLBA)之關係。
控制器4將用戶資料與iLBA對寫入至超級區塊(SB)內之頁中。於此種情形時，控制器4亦可首先基於iLBA與用戶資料之組合而生成錯誤檢測碼(EDC)。然後，控制器4將iLBA-用戶資料-EDC組寫入至超級區塊(SB)內之頁中。控制器4於自超級區塊(SB)讀出用戶資料時，會藉由對基於所讀出之iLBA及所讀出之用戶資料計算出之值與所讀出之EDC是否一致進行檢查，而判定是否正確讀出了用戶資料。其次，利用圖30~34，對於垃圾回收(GC)動作中執行之重複資料刪除動作進行說明。
圖30表示與某資料對應之參照計數(Refcount)溢出之情形時執行之資料寫入動作。
於此，超級區塊(SB)100-0係用以儲存與參照計數(Refcount)=0~3對應之資料之超級區塊。即，與超級區塊(SB)100-0建立有關聯之SB管理表200-0具有能儲存各為2位元長度之複數個參照計數(Refcount)之參照計數記憶區域。
設定為自主機2接收之寫入資料(資料X)與已儲存於超級區塊(SB)100-0中之資料A0一致。若該資料A0之當前參照計數為3，則需將與資料A0對應之參照計數值自3變更為4。但是，管理資料A0之參照計數(Refcount)之SB管理表200-0無法儲存大於3之參照計數(Refcount)，因此無法將資料A0之參照計數(Refcount)自3變更為4(溢出)。
因此，控制器4將資料X寫入至寫入目標超級區塊(於此，為超級區塊(SB)100-1)中。此時，LUT32得到更新，未使用之iLBA(於此，為iLBAx)與對應於資料X之LBAj建立關聯。又，iLUT34得到更新，表示寫入有資料X之NAND型快閃記憶體5內之實體記憶位置之PBA61與iLBAx建立關聯。進而，於管理寫入目標超級區塊(超級區塊(SB)100-1)之參照計數(Refcount)之SB管理表200-1中，與資料X對應之參照計數(Refcount)被設定為1。
其次，對於GC時執行之重複資料刪除動作進行說明。
於圖31中，例示了如下情形：選擇寫入有資料X之寫入目標超級區塊(超級區塊(SB)100-1)整體於被來自主機2之寫入資料寫滿後作為GC對象超級區塊(用於GC之複製源區塊)，且與資料X一致之資料A0之參照計數(Refcount)由3減少至2。於此種情形時，如圖32所示，控制器4僅將資料X 以外之與非零參照計數對應之資料(資料A1、資料D1、資料F1、資料G1、資料I1、資料M1、資料O1)自複製源區塊(超級區塊(SB)100-1)複製至複製目標區塊(超級區塊(SB)100-2)。
然後，如圖33所示，控制器4將非零參照計數(Refcount)之中資料X(對應於PBA61)以外資料之參照計數(Refcount)自SB管理表200-1複製至SB管理表200-2。即，將資料A1(對應於PBA50)、資料D1(對應於PBA53)、資料F1(對應於PBA55)、資料G1(對應於PBA56)、資料I1(對應於PBA58)、資料M1(對應於PBA62)、資料O1(對應於PBA64)各自之參照計數(Refcount)自與複製源區塊(超級區塊(SB)100-1)對應之SB管理表200-1複製至與複製目標超級區塊(超級區塊(SB)100-2)對應之SB管理表200-2。
又，控制器4將資料A0(對應於PBA0)之參照計數(Refcount)增加1。藉此，在對應於儲存有與資料X一致之資料A0之超級區塊(SB)100-0之SB管理表200-0中，資料A0(對應於PBA0)之參照計數(Refcount)例如由2變更為3。
進而，如圖34所示，控制器4更新LUT32，將指示保持有與資料A0對應之PBA0之iLUT34內之條目之iLBA(於此，為iLBA0)與資料X之LBA(於此，為LBAj)建立關聯。藉此，於接收包含LBAj之讀出指令時，能基於與LBAj對應之iLBA0，而參照與iLBA0建立有關聯之PBA0。因此，能讀出與資料X一致之資料A0。
圖35之流程圖表示用以將具有較大參照計數之資料與具有較小參照計數之資料分離之GC動作之順序。
控制器4自具有非零參照計數之資料與具有零參照計數之資料混合存 在之超級區塊群中選擇GC對象超級區塊(複製源區塊)(步驟S501)。
控制器4基於與複製源區塊對應之SB管理表，將包含於複製源區塊內且與屬於第1參照計數範圍之各參照計數對應之資料集合複製至第1複製目標區塊(步驟S502)。第1複製目標區塊係與包含能儲存各自具有第1位元長度之複數個參照計數之參照計數記憶區域之SB管理表建立有關聯之超級區塊。
繼而，控制器4基於與複製源區塊對應之SB管理表，將包含於複製源區塊內且與屬於第2參照計數範圍之各參照計數對應之資料集合複製至第2複製目標區塊，其中上述第2參照計數範圍具有較第1參照計數範圍之上限大之下限(步驟S503)。第2複製目標區塊係與包含能儲存各自具有第2位元長度之複數個參照計數之參照計數記憶區域之SB管理表建立有關聯之超級區塊，其中上述第2位元長度長於第1位元長度。
藉由以上之處理，具有屬於第1參照計數範圍之參照計數之資料與具有屬於第2參照計數範圍之參照計數之資料會被移動至互不相同之超級區塊，因此能將屬於相同參照計數範圍之資料群集中於相同之超級區塊。因此，能提高各SB管理表之參照計數記憶區域之利用效率，其結果能削減參照計數各自之管理所需之記憶體資源量。
圖36之流程圖表示與某資料對應之參照計數溢出時執行之重複資料複製處理之順序。
控制器4對已儲存之某資料(第1資料)之參照計數是否因來自主機2之新寫入資料之接收而溢出進行判定(步驟S601)。於步驟S601中，控制器4對與第1資料對應之參照計數值因來自主機2之與第1資料一致之寫入資料之接收，是否超過了以能儲存於SB管理表參照計數記憶區域之各參照計 數之位元長度所能表現之最大值進行判定，其中上述SB管理表係與儲存有第1資料之第1超級區塊對應之SB管理表。
若與第1資料對應之參照計數值超過以能儲存於與第1超級區塊對應之SB管理表參照計數記憶區域內之各參照計數之位元長度所能表現之最大值(步驟S601中為是)，則控制器4將第1資料複製至與包含如下參照計數記憶區域之管理表建立有關聯之其他超級區塊，上述參照計數記憶區域為能儲存各自具有較與儲存有第1資料之第1超級區塊對應之SB管理表內之各參照計數長之位元長度之複數個參照計數(步驟S602)。又，於步驟S602中，控制器4如圖24中所說明般，更新與複製有第1資料之超級區塊對應之SB管理表，將與第1資料對應之參照計數增加1。進而，控制器4更新iLUT34，將表示複製有第1資料之實體記憶位置之PBA與對應於第1資料之iLBA建立關聯。
圖37之流程圖表示與某資料對應之參照計數溢出時執行之參照計數記憶區域擴張處理之順序。
控制器4對已儲存之某資料(第1資料)之參照計數是否因來自主機2之新寫入資料之接收而溢出進行判定(步驟S701)。於步驟S701中，控制器4對與第1資料對應之參照計數值因來自主機2之與第1資料一致之寫入資料之接收，是否超過了以能儲存於SB管理表參照計數記憶區域之各參照計數之位元長度所能表現之最大值進行判定，其中上述SB管理表係與儲存有第1資料之第1超級區塊對應之SB管理表。
若與第1資料對應之參照計數值超過以能儲存於與第1超級區塊對應之SB管理表參照計數記憶區域內之各參照計數之位元長度所能表現之最大值(步驟S701中為是)，則控制器4藉由將與第1超級區塊對應之SB管理 表參照計數記憶區域之尺寸擴張，而加長能儲存於與第1超級區塊對應之SB管理表參照計數記憶區域之各參照計數之位元長度(步驟S702)。於步驟S702中，如圖20中所說明般，控制器4亦可將先前之參照計數記憶區域開放，而且，亦可重新確保較大尺寸之參照計數記憶區域。
圖38之流程圖表示與某資料對應之參照計數溢出時執行之資料寫入處理之順序。
控制器4對已儲存之某資料(第1資料)之參照計數是否因來自主機2之新寫入資料之接收而溢出進行判定(步驟S801)。於步驟S801中，控制器4對與第1資料對應之參照計數值因來自主機2之與第1資料一致之寫入資料之接收，是否超過了以能儲存於SB管理表參照計數記憶區域之各參照計數之位元長度所能表現之最大值進行判定，其中上述SB管理表係與儲存有第1資料之第1超級區塊對應之SB管理表。
若與第1資料對應之參照計數值超過以能儲存於與第1超級區塊對應之SB管理表參照計數記憶區域內之各參照計數之位元長度所能表現之最大值(步驟S801中為是)，則控制器4執行以下處理，而代替將已賦予給第1資料之iLBA與寫入資料之LBA建立關聯。
控制器4更新LUT32，將未使用之iLBA(例如iLBAx)與寫入資料之LBA建立關聯(步驟S802)。繼而，控制器4將寫入資料寫入至某超級區塊(例如，當前寫入目標超級區塊)中(步驟S803)。控制器4更新iLUT34，將表示寫入有寫入資料之NAND型快閃記憶體5內之位置(實體記憶位置)之PBA與關聯於寫入資料之LBA之上述iLBA(iLBAx)建立關聯(步驟S804)。然後，控制器4更新與寫入有寫入資料之超級區塊對應之SB管理表，將與寫入資料對應之參照計數設定為1(步驟S805)。
其結果，即便於與寫入資料一致之現有資料(第1資料)之當前參照計數值達到以能利用之參照計數之最大位元長度所能表現之最大值之情形時，亦能將該寫入資料寫入至NAND型快閃記憶體5中。
圖39表示自LBA直接參照PBA之位址參照路徑、及經由iLBA而自LBA參照PBA之位址參照路徑混合存在之位址參照結構。
於圖39中，LBA32係以某一個LBA關聯於iLBA或PBA中之任一者之方式構成。
於某LBA關聯於iLBA之情形時，並非自該LBA直接參照PBA，而係經由iLBA自該LBA參照PBA。於此種情形時，如上所述，利用包含LBA32及iLUT34此2個位址轉換表執行位址轉換。
另一方面，於某LBA關聯於PBA之情形時，與普通SSD同樣地，能自LBA直接參照PBA，藉此，能改善例如資料讀出動作之性能。
本實施形態中，於NAND型快閃記憶體5中不存在與自主機2接收之寫入資料一致之資料(重複資料)之情形時，執行以下任一項。
(1)控制器4更新雜湊LUT33，而對寫入資料之雜湊值賦予未使用之iLBA，然後更新LUT32，而對寫入資料之LBA關聯該iLBA。
(2)控制器4更新LUT32，而對寫入資料之LBA直接關聯PBA。
於(2)之案例中，該寫入資料亦可寫入至獨佔類型之超級區塊中。於圖39中，超級區塊(SB)100-100、100-101、100-102…表示獨佔類型之超級區塊(SB)。所謂獨佔類型之超級區塊(SB)係指用以儲存僅被單獨LBA參照之資料之超級區塊(SB)。獨佔類型之超級區塊(SB)與包含能儲存各為1位元長度之複數個參照計數(Refcount)之參照計數記憶區域之SB管理表建立有關聯。1位元長度之參照計數=0表示對應資料未被任何LBA參照， 即對應資料為無效資料。1位元長度之參照計數=1表示對應資料僅被一個LBA參照，即對應資料為有效資料。於將寫入資料寫入至獨佔類型之超級區塊之案例中，由LUT32通知寫入目標超級區塊為獨佔類型之超級區塊，藉此，亦可對寫入資料之LBA關聯PBA。
於(1)之案例中，該寫入資料亦可寫入至共用類型之超級區塊中。於圖39中，超級區塊(SB)100-0、100-1、100-2、…、100-50、100-51、100-52、…表示共用類型之超級區塊(SB)。所謂共用類型之超級區塊(SB)係指用以儲存有可能被複數個LBA參照之資料之超級區塊(SB)。共用類型之超級區塊(SB)與包含能儲存各為2位元以上之複數個參照計數(Refcount)之參照計數記憶區域之SB管理表建立有關聯。於圖39中，例示了如下情形：與超級區塊(SB)100-50、100-51、100-52、…各者建立有關聯之SB管理表具有能儲存各為2位元長度(或8位元長度)之複數個參照計數之參照計數記憶區域，與超級區塊(SB)100-0、100-1、100-2、…各者建立有關聯之SB管理表具有能儲存各為4位元長度(或16位元長度)之複數個參照計數之參照計數記憶區域。於將寫入資料寫入至共用類型之超級區塊之案例中，由LUT32通知寫入目標超級區塊為共用類型之超級區塊，藉此，亦可對寫入資料之LBA關聯iLBA。
於共用類型之各超級區塊(SB)中，當發生與所儲存之某資料對應之參照計數之溢出時，亦可擴張對應SB管理表之參照計數記憶區域之尺寸。例如，在需將與儲存於超級區塊(SB)100-50中之某資料對應之參照計數自3變更為4時(或需自255變更為256時)，亦可藉由擴張與超級區塊(SB)100-50對應之SB管理表參照計數記憶區域之尺寸，而將該SB管理表之各參照計數之位元長度自2位元變更為4位元(或自8位元變更為16位 元)。
於NAND型快閃記憶體5中不存在與自主機2接收之寫入資料一致之資料(重複資料)之情形時，控制器4亦可將iLBA/PBA中之某一個與該寫入資料之LBA建立關聯。於此種情形時，控制器4亦可基於自主機2接收之提示資訊，而決定將iLBA/PBA中之哪一個與該寫入資料之LBA建立關聯。例如，於將表示有可能被其他LBA參照之LBA群之提示資訊通知給SSD3之案例中，控制器4於NAND型快閃記憶體5中不存在與寫入資料一致之資料(重複資料)，且該寫入資料之LBA不屬於藉由該提示資訊而通知之LBA群之情形時，亦可將PBA與該寫入資料之LBA建立關聯，將該寫入資料寫入至獨佔類型之超級區塊中。
圖40表示對於所有資料都經由iLBA而自LBA參照PBA之位址參照結構。
於NAND型快閃記憶體5中不存在與自主機2接收之寫入資料一致之資料(重複資料)之情形時，控制器4對寫入資料之雜湊值賦予未使用之iLBA，對寫入資料之LBA關聯該iLBA。然後，控制器4將該寫入資料寫入至獨佔類型之超級區塊中。
於某獨佔類型之超級區塊(SB)中，當發生與所儲存之某資料對應之參照計數之溢出時，亦可擴張對應SB管理表之參照計數記憶區域之尺寸。
例如，在需將與儲存於超級區塊(SB)100-10中之某資料對應之參照計數自1變更為2時，亦可藉由擴張與超級區塊(SB)100-100對應之SB管理表參照計數記憶區域之尺寸，而將該SB管理表之各參照計數之位元長度自1位元變更為2位元(或自1位元變更為8位元)。
又，於共用類型之超級區塊(SB)中同樣地，當發生與所儲存之某資料對應之參照計數之溢出時，亦可擴張對應SB管理表之參照計數記憶區域之尺寸。
例如，在需將與儲存於超級區塊(SB)100-50中之某資料對應之參照計數自3變更為4時(或自255變更為256時)，亦可藉由擴張與超級區塊(SB)100-50對應之SB管理表參照計數記憶區域之尺寸，而將該SB管理表之各參照計數之位元長度自2位元變更為4位元(或自8位元變更為16位元)。
再者，於NAND型快閃記憶體5中不存在與自主機2接收之寫入資料一致之資料(重複資料)之情形時，控制器4亦可基於自主機2接收之提示資訊，而決定應被寫入該寫入資料之超級區塊(SB)之類型。例如，於將表示有較大可能被其他LBA分別參照之LBA群之提示資訊通知給SSD3之案例中，控制器4於NAND型快閃記憶體5中不存在與寫入資料一致之資料(重複資料)，且該寫入資料之LBA不屬於藉由該提示資訊而通知之LBA群之情形時，亦可將該寫入資料寫入至共用類型之超級區塊中。
圖41表示圖39之位址參照結構中使用之查找表(LUT)32之構成例。
LUT32包含與複數個LBA對應之複數個條目。各條目包含標誌欄位、及iLBA/PBA欄位。標誌欄位保持表示對應iLBA/PBA欄位之內容為iLBA或PBA中之哪一個之標誌。例如，「1」之標誌表示對應iLBA/PBA欄位之內容為iLBA，「0」之標誌表示對應iLBA/PBA欄位之內容為PBA。
當自主機2接收讀出指令時，控制器4參照LUT32，自與讀出指令中包含之LBA對應之條目中取得標誌及位址(iLBA/PBA)。
若自LUT32取得之標誌為「1」，則控制器4使用自LUT32取得之位址(iLBA)，參照iLUT34，自iLUT34取得PBA。然後，控制器4從由自iLUT34取得之PBA指定之NAND型快閃記憶體5內之實體記憶位置讀出資料。
另一方面，若所取得之標誌為「0」，則控制器4不參照iLUT34，從由自LUT32取得之位址(PBA)指定之NAND型快閃記憶體5內之實體記憶位置讀出資料。
圖42表示作為主機2發揮功能之資訊處理裝置(計算裝置)之硬體構成例。
該資訊處理裝置係以伺服器等計算裝置之形式實現。該資訊處理裝置包含處理器(CPU)101、主記憶體102、BIOS(Basic Input/Output System，基本輸入輸出系統)-ROM103、網路控制器105、周邊介面控制器106、控制器107、及嵌入式控制器(EC)108等。
處理器101係以控制該資訊處理裝置各組件之動作之方式構成之CPU。該處理器101執行自複數個SSD3中之任一個載入至主記憶體102之各種程式。主記憶體102包含DRAM等隨機存取記憶體。
又，處理器101亦運行儲存於作為非揮發性記憶體之BIOS-ROM103中之基本輸入輸出系統(BIOS)。BIOS係用於硬體控制之系統程式。
網路控制器105係有線LAN(Local Area Network，局域網)控制器、無線LAN控制器等通信設備。周邊介面控制器106係以執行與USB設備等周邊設備之通信之方式構成。
控制器107係以執行與分別連接於複數個連接器107A之設備之通信之方式構成。複數個SSD3亦可分別連接於複數個連接器107A。控制器 107為SAS擴展器(SAS expander)、PCIe交換器(PCIe Switch)、PCIe擴展器(PCIe expander)、快閃陣列控制器、或RAID(Redundant Arrays of Independent Disks，獨立冗餘磁碟陣列)控制器等。
EC108作為以執行資訊處理裝置之電力管理之方式構成之系統控制器發揮功能。EC108根據用戶對電源開關之操作而將資訊處理裝置接通電源及切斷電源。
圖43表示包含複數個SSD3及主機2之資訊處理裝置(計算裝置)之構成例。
該資訊處理裝置具備能收容於機架之薄的箱形殼體201。複數個SSD3亦可配置於殼體201內。於此種情形時，各SSD3亦可能夠插拔地插入設定於殼體201前表面201A之插槽中。
系統板(母板)202配置於殼體201內。於系統板(母板)202上，安裝有包括CPU101、主記憶體102、網路控制器105、控制器107之各種電子零件。該等電子零件作為主機2發揮功能。
如以上所說明般，根據本實施形態，使用LUT32及iLUT34而執行2級位址轉換。於LUT32中，與已存在之某資料一致之寫入資料之邏輯位址(LBA)關聯於與已存在之資料之中間位址(iLBA)相同之中間位址(iLBA)。因此，於iLUT34中，無論參照某資料之邏輯位址之數量為何，各實體位址僅與一個中間位址(iLBA)建立關聯。
藉此，於被複數個邏輯位址參照之資料(重複資料)藉由垃圾回收而被複製至其他區塊之案例中，控制器4亦可保證：只進行僅將與此一個中間位址對應之iLUT34內之一個條目更新為複製目標實體位址之動作，便能自此複數個邏輯位址正確參照該複製目標實體位址。
進而，與儲存於某第1區塊(超級區塊)中之複數個資料分別對應之複數個參照計數全部由與該第1區塊對應之管理表(SB管理表)管理。而且，於某第1區塊被選作用於GC之複製源區塊之情形時，執行以下動作：基於與該第1區塊對應之管理表之內容，並基於與複製源區塊對應之管理表，將包含於複製源區塊內且與屬於第1參照計數範圍之各參照計數對應之資料集合複製至第1複製目標區塊，並將包含於複製源區塊內且與屬於第2參照計數範圍之各參照計數對應之資料集合複製至第2複製目標區塊，其中上述第2參照計數範圍具有較上述第1參照計數範圍之上限大之下限。藉此，能將與屬於相同參照計數範圍之各參照計數對應之資料集合集中於相同之區塊。藉此，與參照計數不同之資料混合存在於相同超級區塊之狀況相比，能大幅降低參照計數記憶區域用記憶體資源之消耗量。其結果，能節約對重複資料刪除用管理資料進行記憶時所需之記憶體資源。
又，屬於相同參照計數範圍之資料群係具有類似生命週期之資料群。因此，藉由將與屬於相同參照計數範圍之各參照計數對應之資料集合集中於相同之區塊，能提高使相同區塊中包含之各資料於同一時期無效化之概率，藉此能抑制GC之頻率。此能降低寫入放大，其結果能將SSD3之壽命最大化。
再者，於本實施形態中，對以包含複數個實體區塊之超級區塊為單位進行寫入目標區塊/複製目標區塊之分配、刪除動作、寫入動作、及讀出動作之情形進行了說明，但亦能以實體區塊為單位進行寫入目標區塊/複製目標區塊之分配、刪除動作、寫入動作、及讀出動作。換而言之，第1區塊中包含之實體區塊數只要為1以上即可。
再者，於本實施形態中，作為非揮發性記憶體例示了NAND型快閃 記憶體。但，本實施形態之功能亦能應用於例如MRAM(Magnetoresistive Random Access Memory，磁阻式隨機存取記憶體)、PRAM(Phase change Random Access Memory，相變隨機存取記憶體)、ReRAM(Resistive Random Access Memory，電阻式隨機存取記憶體)、或FeRAM(Ferroelectric Random Access Memory，鐵電隨機存取記憶體)等其他各種非揮發性記憶體。
對本發明之若干實施形態進行了說明，但該等實施形態僅作為一例而提出，並非意圖限定發明之範圍。該等新穎之實施形態能藉由其他各種形態加以實施，能於不脫離發明主旨之範圍內，進行各種省略、替換、變更。該等實施形態及其變化包含於發明之範圍及主旨中，並且包含於申請專利範圍所記載之發明及其同等之範圍內。
[相關申請]
本申請享有以日本專利申請2017-181686號(申請日：2017年9月21日)為基礎申請之優先權。本申請藉由參照該基礎申請而包含基礎申請之全部內容。

Claims (16)

  1. 一種記憶體系統，其具備：非揮發性記憶體；及控制器，其電性連接於上述非揮發性記憶體，控制上述非揮發性記憶體；且上述控制器構成為執行以下動作：管理上述非揮發性記憶體內之與複數個第1區塊對應之複數個管理表，各管理表包含與對應的第1區塊內之複數個資料對應之複數個參照計數，各參照計數表示參照對應的資料之邏輯位址之數量，當上述非揮發性記憶體中不存在與自主機接收之寫入資料一致之重複資料時，更新管理各邏輯位址與各中間位址之對應關係之第1轉換表，將未使用之第1中間位址與上述寫入資料之邏輯位址建立關聯，將上述寫入資料寫入上述非揮發性記憶體，且更新管理上述各中間位址與各實體位址之對應關係之第2轉換表，將表示已被寫入上述寫入資料之上述非揮發性記憶體內之位置之實體位址與上述第1中間位址建立關聯，將與上述寫入資料對應之參照計數設定為1，當上述非揮發性記憶體中已存在與上述寫入資料一致之上述重複資料時，不將上述寫入資料寫入上述非揮發性記憶體，而更新上述第1轉換表，將第2中間位址與上述寫入資料之上述邏輯位址建立關聯，將與上述重複資料對應之參照計數增加1，上述第2中間位址係指示保持有與上述重複資料對應之實體位址之上述第2轉換表內之條目，當上述寫入資料為已被寫入上述非揮發性記憶體之資料之更新資料時，將與上述已被寫入之資料對應之參照計數減去1，當選擇上述複數個第1區塊中之一個作為垃圾回收之複製源區塊時，基於與上述複製源區塊對應之上述複數個管理表內之第1管理表，將包含於上述複製源區塊內且與屬於第1參照計數範圍之參照計數各自對應之資料集合複製至第1複製目標區塊，將包含於上述複製源區塊內且與屬於第2參照計數範圍之參照計數各自對應之資料集合複製至第2複製目標區塊，上述第2參照計數範圍具有較上述第1參照計數範圍之上限更大之下限。
  2. 如請求項1之記憶體系統，其中上述第1複製目標區塊係與包含能儲存各自具有第1位元長度之複數個參照計數之參照計數記憶區域之管理表建立關聯，且上述第2複製目標區塊係與包含能儲存各自具有第2位元長度之複數個參照計數之參照計數記憶區域之管理表建立有關聯，上述第2位元長度較上述第1位元長度更長。
  3. 如請求項1之記憶體系統，其中上述控制器構成為：將上述複數個第1區塊分類為第1區塊群及第2區塊群，上述第1區塊群集中有屬於上述第1參照計數範圍之資料集合，上述第2區塊群集中有屬於上述第2參照計數範圍之資料集合；對於上述第1區塊群，選擇滿足無效資料量大於第1閾值之條件之區塊作為用於垃圾回收之複製源區塊候補，對於上述第2區塊群，選擇滿足無效資料量大於第2閾值之條件之區塊作為用於垃圾回收之複製源區塊候補，上述第2閾值小於上述第1閾值。
  4. 如請求項1之記憶體系統，其中上述控制器構成為，當與上述複數個第1區塊中之一個第1區塊內之第1資料對應之參照計數值，因接收來自上述主機之與上述第1資料一致之第1寫入資料，而超過以能儲存於與上述一個第1區塊對應之管理表參照計數記憶區域之各參照計數之位元長度所能表現之最大值時，將上述第1資料複製至與包含如下參照計數記憶區域之管理表建立關聯之另一個第1區塊，上述參照計數記憶區域為能儲存各自具有較與上述一個第1區塊對應之上述管理表內之各參照計數更長之位元長度之複數個參照計數。
  5. 如請求項1之記憶體系統，其中上述控制器構成為，當與上述複數個第1區塊中之一個第1區塊內之第1資料對應之參照計數值，因接收來自上述主機之與上述第1資料一致之第1寫入資料，而超過以能儲存於與上述一個第1區塊對應之管理表參照計數記憶區域之各參照計數之位元長度所能表現之最大值時，藉由將與上述一個第1區塊對應之上述管理表之上述參照計數記憶區域之尺寸擴張，而加長能儲存於與上述一個第1區塊對應之上述管理表上述參照計數記憶區域之各參照計數之位元長度。
  6. 如請求項1之記憶體系統，其中上述控制器構成為，當與上述複數個第1區塊中之一個第1區塊內之第1資料對應之參照計數值，因接收來自上述主機之與上述第1資料一致之第1寫入資料，而超過以能儲存於與上述一個第1區塊對應之管理表參照計數記憶區域之各參照計數之位元長度所能表現之最大值時，更新上述第1轉換表，將未使用之中間位址與上述第1寫入資料之邏輯位址建立關聯，將上述第1寫入資料寫入上述複數個第1區塊中之一個，更新上述第2轉換表，將表示已被寫入上述第1寫入資料之上述非揮發性記憶體內之位置之實體位址與已與上述第1寫入資料之邏輯位址建立關聯之上述中間位址建立關聯，將與上述第1寫入資料對應之參照計數設定為1。
  7. 如請求項6之記憶體系統，其中構成為當選擇已被寫入上述第1寫入資料之上述複數個第1區塊中之上述一個作為於資料寫滿後用以進行垃圾回收之複製源區塊，且與上述第1資料對應之參照計數值減少至小於上述最大值之值時，僅將上述第1寫入資料以外之與非零之參照計數對應之資料自上述複製源區塊複製至複製目標區塊，更新上述第1轉換表，將中間位址與上述第1寫入資料之上述邏輯位址建立關聯，將上述第1資料之參照計數增加1，上述中間位址係指示保持有與上述第1資料對應之實體位址之上述第2轉換表內之條目。
  8. 一種控制非揮發性記憶體之控制方法，其包括：管理上述非揮發性記憶體內之與複數個第1區塊對應之複數個管理表，各管理表包含與對應的第1區塊內之複數個資料對應之複數個參照計數，各參照計數表示參照對應的資料之邏輯位址之數量，當上述非揮發性記憶體中不存在與自主機接收之寫入資料一致之重複資料時，執行以下動作：更新管理各邏輯位址與各中間位址之對應關係之第1轉換表，將未使用之第1中間位址與上述寫入資料之邏輯位址建立關聯；將上述寫入資料寫入上述非揮發性記憶體；更新管理上述各中間位址與各實體位址之對應關係之第2轉換表，將表示已被寫入上述寫入資料之上述非揮發性記憶體內之位置之實體位址與上述第1中間位址建立關聯；將與上述寫入資料對應之參照計數設定為1；當上述非揮發性記憶體中已存在與上述寫入資料一致之上述重複資料時，執行以下動作：不將上述寫入資料寫入上述非揮發性記憶體，而更新上述第1轉換表，將第2中間位址與上述寫入資料之上述邏輯位址建立關聯，上述第2中間位址係指示保持有與上述重複資料對應之實體位址之上述第2轉換表內之條目；將與上述重複資料對應之參照計數增加1；當上述寫入資料為已被寫入上述非揮發性記憶體之資料之更新資料時，將與上述已被寫入之資料對應之參照計數減去1；當選擇上述複數個第1區塊中之一個作為垃圾回收之複製源區塊時，執行以下動作：基於與上述複製源區塊對應之上述複數個管理表內之第1管理表，將包含於上述複製源區塊內且與屬於第1參照計數範圍之參照計數各自對應之資料集合複製至第1複製目標區塊，將包含於上述複製源區塊內且與屬於第2參照計數範圍之參照計數各自對應之資料集合複製至第2複製目標區塊，上述第2參照計數範圍具有較上述第1參照計數範圍之上限更大之下限。
  9. 如請求項8之控制非揮發性記憶體之控制方法，其中上述第1複製目標區塊係與包含能儲存各自具有第1位元長度之複數個參照計數之參照計數記憶區域之管理表建立關聯，且上述第2複製目標區塊係與包含能儲存各自具有第2位元長度之複數個參照計數之參照計數記憶區域之管理表建立有關聯，上述第2位元長度較上述第1位元長度更長。
  10. 如請求項8之控制非揮發性記憶體之控制方法，其中進而包括：將上述複數個第1區塊分類為第1區塊群及第2區塊群，上述第1區塊群集中有屬於上述第1參照計數範圍之資料集合，上述第2區塊群集中有屬於上述第2參照計數範圍之資料集合；對於上述第1區塊群，選擇滿足無效資料量大於第1閾值之條件之區塊作為用於垃圾回收之複製源區塊候補，對於上述第2區塊群，選擇滿足無效資料量大於第2閾值之條件之區塊作為用於垃圾回收之複製源區塊候補，上述第2閾值小於上述第1閾值。
  11. 如請求項8之控制非揮發性記憶體之控制方法，其中進而包括：當與上述複數個第1區塊中之一個第1區塊內之第1資料對應之參照計數值，因接收來自上述主機之與上述第1資料一致之第1寫入資料，而超過以能儲存於與上述一個第1區塊對應之管理表參照計數記憶區域之各參照計數之位元長度所能表現之最大值時，將上述第1資料複製至與包含如下參照計數記憶區域之管理表建立關聯之另一個第1區塊，上述參照計數記憶區域為能儲存各自具有較與上述一個第1區塊對應之上述管理表內之各參照計數更長之位元長度之複數個參照計數。
  12. 如請求項8之控制非揮發性記憶體之控制方法，其中進而包括：當與上述複數個第1區塊中之一個第1區塊內之第1資料對應之參照計數值，因接收來自上述主機之與上述第1資料一致之第1寫入資料，而超過以能儲存於與上述一個第1區塊對應之管理表參照計數記憶區域之各參照計數之位元長度所能表現之最大值時，藉由將與上述一個第1區塊對應之上述管理表之上述參照計數記憶區域之尺寸擴張，而加長能儲存於與上述一個第1區塊對應之上述管理表上述參照計數記憶區域之各參照計數之位元長度。
  13. 如請求項8之控制非揮發性記憶體之控制方法，其中進而包括：當與上述複數個第1區塊中之一個第1區塊內之第1資料對應之參照計數值，因接收來自上述主機之與上述第1資料一致之第1寫入資料，而超過以能儲存於與上述一個第1區塊對應之管理表參照計數記憶區域之各參照計數之位元長度所能表現之最大值時，執行以下動作：更新上述第1轉換表，將未使用之中間位址與上述第1寫入資料之邏輯位址建立關聯；將上述第1寫入資料寫入上述複數個第1區塊中之一個；更新上述第2轉換表，將表示已被寫入上述第1寫入資料之上述非揮發性記憶體內之位置之實體位址與已與上述第1寫入資料之邏輯位址建立關聯之上述中間位址建立關聯；將與上述第1寫入資料對應之參照計數設定為1。
  14. 如請求項13之控制非揮發性記憶體之控制方法，其中進而包括：當選擇已被寫入上述第1寫入資料之上述複數個第1區塊中之上述一個作為於資料寫滿後用以進行垃圾回收之複製源區塊，且與上述第1資料對應之參照計數值減少至小於上述最大值之值時，執行以下動作：僅將上述第1寫入資料以外之與非零之參照計數對應之資料自上述複製源區塊複製至複製目標區塊；更新上述第1轉換表，將中間位址與上述第1寫入資料之上述邏輯位址建立關聯，上述中間位址係指示保持有與上述第1資料對應之實體位址之上述第2轉換表內之條目；將上述第1資料之參照計數增加1。
  15. 一種記憶體系統，其具備：非揮發性記憶體；及控制器，其電性連接於上述非揮發性記憶體，控制上述非揮發性記憶體；且上述控制器構成為執行以下動作：管理上述非揮發性記憶體內之與複數個第1區塊對應之複數個管理表，各管理表包含與對應的第1區塊內之複數個資料對應之複數個參照計數，各參照計數表示參照對應的資料之邏輯位址之數量，當上述非揮發性記憶體中不存在與自主機接收之寫入資料一致之重複資料時，將上述寫入資料寫入上述非揮發性記憶體，且更新管理各中間位址與上述非揮發性記憶體之各實體位址之對應關係之中間-實體位址轉換表，將表示已被寫入上述寫入資料之上述非揮發性記憶體內之位置之實體位址、與對上述寫入資料之邏輯位址賦予之第1中間位址建立關聯，將與上述寫入資料對應之參照計數設定為1，當上述非揮發性記憶體中已存在與上述寫入資料一致之上述重複資料時，不將上述寫入資料寫入上述非揮發性記憶體，而將對上述重複資料賦予之第2中間位址、與上述寫入資料之上述邏輯位址建立關聯，將與上述重複資料對應之參照計數增加1，當上述寫入資料為已被寫入上述非揮發性記憶體之資料之更新資料時，將與上述已被寫入之資料對應之參照計數減去1，將與屬於第1參照計數範圍之各參照計數對應之第1資料集合集中於上述複數個第1區塊中之一個以上第1區塊，將與屬於第2參照計數範圍之各參照計數對應之第2資料集合集中於上述複數個第1區塊中之一個以上之其他第1區塊，上述第2參照計數範圍具有較上述第1參照計數範圍之上限更大之下限。
  16. 如請求項15之記憶體系統，其中當選擇上述複數個第1區塊中之一個作為垃圾回收之複製源區塊時，上述控制器基於與上述複製源區塊對應之上述複數個管理表內之第1管理表，將包含於上述複製源區塊內且與屬於上述第1參照計數範圍之各參照計數對應之資料集合複製至第1複製目標區塊，將上述第1資料集合集中於上述一個以上第1區塊，將包含於上述複製源區塊內且與屬於上述第2參照計數範圍之各參照計數對應之資料集合複製至第2複製目標區塊，將上述第2資料集合集中於上述一個以上之其他第1區塊。
TW106146403A 2017-09-21 2017-12-29 記憶體系統及控制非揮發性記憶體之控制方法 TWI670596B (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2017-181686 2017-09-21
JP2017181686A JP2019057172A (ja) 2017-09-21 2017-09-21 メモリシステムおよび制御方法

Publications (2)

Publication Number Publication Date
TW201915742A TW201915742A (zh) 2019-04-16
TWI670596B true TWI670596B (zh) 2019-09-01

Family

ID=65720376

Family Applications (1)

Application Number Title Priority Date Filing Date
TW106146403A TWI670596B (zh) 2017-09-21 2017-12-29 記憶體系統及控制非揮發性記憶體之控制方法

Country Status (4)

Country Link
US (3) US10545864B2 (zh)
JP (1) JP2019057172A (zh)
CN (1) CN109542332B (zh)
TW (1) TWI670596B (zh)

Families Citing this family (61)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10635339B2 (en) 2017-05-02 2020-04-28 Smart Ipos, Inc. Devices, systems, and methods for reducing storage utilization with data deduplication
US11354247B2 (en) 2017-11-10 2022-06-07 Smart IOPS, Inc. Devices, systems, and methods for configuring a storage device with cache
US10496548B2 (en) 2018-02-07 2019-12-03 Alibaba Group Holding Limited Method and system for user-space storage I/O stack with user-space flash translation layer
US11379155B2 (en) 2018-05-24 2022-07-05 Alibaba Group Holding Limited System and method for flash storage management using multiple open page stripes
US10921992B2 (en) 2018-06-25 2021-02-16 Alibaba Group Holding Limited Method and system for data placement in a hard disk drive based on access frequency for improved IOPS and utilization efficiency
WO2020000136A1 (en) 2018-06-25 2020-01-02 Alibaba Group Holding Limited System and method for managing resources of a storage device and quantifying the cost of i/o requests
US10996886B2 (en) 2018-08-02 2021-05-04 Alibaba Group Holding Limited Method and system for facilitating atomicity and latency assurance on variable sized I/O
US11327929B2 (en) 2018-09-17 2022-05-10 Alibaba Group Holding Limited Method and system for reduced data movement compression using in-storage computing and a customized file system
US10977122B2 (en) 2018-12-31 2021-04-13 Alibaba Group Holding Limited System and method for facilitating differentiated error correction in high-density flash devices
US11061735B2 (en) 2019-01-02 2021-07-13 Alibaba Group Holding Limited System and method for offloading computation to storage nodes in distributed system
US11132291B2 (en) 2019-01-04 2021-09-28 Alibaba Group Holding Limited System and method of FPGA-executed flash translation layer in multiple solid state drives
US11200337B2 (en) 2019-02-11 2021-12-14 Alibaba Group Holding Limited System and method for user data isolation
KR102837223B1 (ko) * 2019-04-18 2025-07-22 에스케이하이닉스 주식회사 메모리 시스템 내에서 서로 다른 종류의 데이터를 처리하기 위한 장치 및 방법
TWI717751B (zh) * 2019-06-10 2021-02-01 群聯電子股份有限公司 資料寫入方法、記憶體控制電路單元及記憶體儲存裝置
CN112181276B (zh) * 2019-07-03 2023-06-20 北京忆恒创源科技股份有限公司 提升存储设备服务质量的大块构造、分配方法及其存储设备
US12135888B2 (en) * 2019-07-10 2024-11-05 Pure Storage, Inc. Intelligent grouping of data based on expected lifespan
US10860223B1 (en) 2019-07-18 2020-12-08 Alibaba Group Holding Limited Method and system for enhancing a distributed storage system by decoupling computation and network tasks
US11907114B2 (en) 2019-08-18 2024-02-20 Smart IOPS, Inc. Devices, systems, and methods for dynamically remapping memory addresses
US11580030B2 (en) * 2019-08-18 2023-02-14 Smart IOPS, Inc. Devices, systems, and methods of logical-to-physical address mapping
US11126561B2 (en) 2019-10-01 2021-09-21 Alibaba Group Holding Limited Method and system for organizing NAND blocks and placing data to facilitate high-throughput for random writes in a solid state drive
US11617282B2 (en) 2019-10-01 2023-03-28 Alibaba Group Holding Limited System and method for reshaping power budget of cabinet to facilitate improved deployment density of servers
CN112764663B (zh) * 2019-10-21 2024-04-12 阿里巴巴集团控股有限公司 云存储空间的空间管理方法、装置和系统、电子设备以及计算机可读存储介质
CN110908972B (zh) * 2019-11-19 2022-09-02 加和（北京）信息科技有限公司 一种日志数据预处理方法、装置、电子设备和存储介质
KR102869321B1 (ko) * 2019-11-21 2025-10-14 에스케이하이닉스 주식회사 메모리 컨트롤러 및 그 동작 방법
KR102867694B1 (ko) * 2019-11-25 2025-10-13 에스케이하이닉스 주식회사 메모리 시스템의 동작 방법 및 장치
US11449455B2 (en) 2020-01-15 2022-09-20 Alibaba Group Holding Limited Method and system for facilitating a high-capacity object storage system with configuration agility and mixed deployment flexibility
US11379447B2 (en) 2020-02-06 2022-07-05 Alibaba Group Holding Limited Method and system for enhancing IOPS of a hard disk drive system based on storing metadata in host volatile memory and data in non-volatile memory using a shared controller
US11372547B2 (en) * 2020-02-13 2022-06-28 International Business Machines Corporation Compression of aging data during compaction
US11200114B2 (en) 2020-03-17 2021-12-14 Alibaba Group Holding Limited System and method for facilitating elastic error correction code in memory
US11449386B2 (en) 2020-03-20 2022-09-20 Alibaba Group Holding Limited Method and system for optimizing persistent memory on data retention, endurance, and performance for host memory
US11301173B2 (en) 2020-04-20 2022-04-12 Alibaba Group Holding Limited Method and system for facilitating evaluation of data access frequency and allocation of storage device resources
US11385833B2 (en) 2020-04-20 2022-07-12 Alibaba Group Holding Limited Method and system for facilitating a light-weight garbage collection with a reduced utilization of resources
US11281575B2 (en) 2020-05-11 2022-03-22 Alibaba Group Holding Limited Method and system for facilitating data placement and control of physical addresses with multi-queue I/O blocks
US11461262B2 (en) 2020-05-13 2022-10-04 Alibaba Group Holding Limited Method and system for facilitating a converged computation and storage node in a distributed storage system
US11494115B2 (en) 2020-05-13 2022-11-08 Alibaba Group Holding Limited System method for facilitating memory media as file storage device based on real-time hashing by performing integrity check with a cyclical redundancy check (CRC)
US11218165B2 (en) 2020-05-15 2022-01-04 Alibaba Group Holding Limited Memory-mapped two-dimensional error correction code for multi-bit error tolerance in DRAM
US11507499B2 (en) 2020-05-19 2022-11-22 Alibaba Group Holding Limited System and method for facilitating mitigation of read/write amplification in data compression
US11556277B2 (en) 2020-05-19 2023-01-17 Alibaba Group Holding Limited System and method for facilitating improved performance in ordering key-value storage with input/output stack simplification
US11263132B2 (en) 2020-06-11 2022-03-01 Alibaba Group Holding Limited Method and system for facilitating log-structure data organization
US11354200B2 (en) 2020-06-17 2022-06-07 Alibaba Group Holding Limited Method and system for facilitating data recovery and version rollback in a storage device
US11422931B2 (en) 2020-06-17 2022-08-23 Alibaba Group Holding Limited Method and system for facilitating a physically isolated storage unit for multi-tenancy virtualization
US11354233B2 (en) 2020-07-27 2022-06-07 Alibaba Group Holding Limited Method and system for facilitating fast crash recovery in a storage device
US11372774B2 (en) 2020-08-24 2022-06-28 Alibaba Group Holding Limited Method and system for a solid state drive with on-chip memory integration
JP7559429B2 (ja) 2020-08-25 2024-10-02 日本電気株式会社 記録媒体管理装置、記録媒体管理方法、およびプログラム
CN112162692B (zh) * 2020-09-02 2023-03-21 Oppo（重庆）智能科技有限公司 一种数据处理方法及终端、存储介质
US11487465B2 (en) 2020-12-11 2022-11-01 Alibaba Group Holding Limited Method and system for a local storage engine collaborating with a solid state drive controller
US11734115B2 (en) 2020-12-28 2023-08-22 Alibaba Group Holding Limited Method and system for facilitating write latency reduction in a queue depth of one scenario
US11416365B2 (en) 2020-12-30 2022-08-16 Alibaba Group Holding Limited Method and system for open NAND block detection and correction in an open-channel SSD
US11360888B1 (en) * 2021-02-16 2022-06-14 Micron Technology, Inc. Host system notification based on entry miss
US11494299B2 (en) * 2021-02-18 2022-11-08 Silicon Motion, Inc. Garbage collection operation management with early garbage collection starting point
TWI821152B (zh) * 2021-02-23 2023-11-01 慧榮科技股份有限公司 儲存裝置、快閃記憶體控制器及其控制方法
TWI808384B (zh) * 2021-02-23 2023-07-11 慧榮科技股份有限公司 儲存裝置、快閃記憶體控制器及其控制方法
TWI771926B (zh) * 2021-02-25 2022-07-21 慧榮科技股份有限公司 資料儲存裝置以及非揮發式記憶體控制方法
US12153820B2 (en) 2021-03-19 2024-11-26 Silicon Motion, Inc. Method of performing wear-leveling operation in flash memory and related controller and storage system
US11726699B2 (en) 2021-03-30 2023-08-15 Alibaba Singapore Holding Private Limited Method and system for facilitating multi-stream sequential read performance improvement with reduced read amplification
US11461173B1 (en) 2021-04-21 2022-10-04 Alibaba Singapore Holding Private Limited Method and system for facilitating efficient data compression based on error correction code and reorganization of data placement
US11476874B1 (en) 2021-05-14 2022-10-18 Alibaba Singapore Holding Private Limited Method and system for facilitating a storage server with hybrid memory for journaling and data storage
CN114185486B (zh) * 2021-11-17 2024-07-30 深圳市德明利技术股份有限公司 一种dram存储器的数据写入方法和dram控制系统
KR102467372B1 (ko) 2022-01-06 2022-11-14 삼성전자주식회사 스토리지 장치 및 이의 동작 방법
US12164372B2 (en) * 2022-08-24 2024-12-10 Western Digital Technologies, Inc. Data retention (DR) warning system
US12277322B2 (en) * 2022-09-30 2025-04-15 Samsung Electronics Co., Ltd. Method of optimizing quality of service (QOS) in solid-state drives (SSDS) and an SSD thereof

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20140115258A1 (en) * 2012-10-18 2014-04-24 Oracle International Corporation System and method for managing a deduplication table
US20140143213A1 (en) * 2012-11-22 2014-05-22 Kaminario Technologies Ltd. Deduplication in a storage system
US20150019507A1 (en) * 2013-07-15 2015-01-15 International Business Machines Corporation Optimizing hash table structure for digest matching in a data deduplication system
TW201626230A (zh) * 2015-01-06 2016-07-16 國立臺灣科技大學 利用快閃記憶體的壞頁來存取資料的方法

Family Cites Families (32)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6687325B1 (en) * 1999-06-23 2004-02-03 Intel Corporation Counter with non-uniform digit base
US6792065B2 (en) * 2003-01-21 2004-09-14 Atmel Corporation Method for counting beyond endurance limitations of non-volatile memories
CN100476979C (zh) * 2003-07-17 2009-04-08 皇家飞利浦电子股份有限公司 利用缺陷管理信息重新组织记录信息的设备和方法
US7877540B2 (en) * 2005-12-13 2011-01-25 Sandisk Corporation Logically-addressed file storage methods
JP4464378B2 (ja) * 2006-09-05 2010-05-19 株式会社日立製作所 同一データを纏める事で格納領域を節約する計算機システム、ストレージシステム及びそれらの制御方法
JP4675985B2 (ja) * 2008-03-01 2011-04-27 株式会社東芝 メモリシステム
JP5198245B2 (ja) * 2008-12-27 2013-05-15 株式会社東芝 メモリシステム
US8918619B2 (en) * 2009-10-04 2014-12-23 Infinidat Ltd. Virtualized storage system and method of operating thereof
JP2011145838A (ja) * 2010-01-13 2011-07-28 Toshiba Corp 記憶装置管理装置および記憶装置の管理方法
JP5609683B2 (ja) * 2011-01-31 2014-10-22 ソニー株式会社 メモリ装置およびメモリシステム
US9251087B2 (en) * 2011-02-11 2016-02-02 SanDisk Technologies, Inc. Apparatus, system, and method for virtual memory management
US9563555B2 (en) * 2011-03-18 2017-02-07 Sandisk Technologies Llc Systems and methods for storage allocation
US9223511B2 (en) 2011-04-08 2015-12-29 Micron Technology, Inc. Data deduplication
JP6019940B2 (ja) * 2012-08-30 2016-11-02 富士通株式会社 情報処理装置、コピー制御プログラム、およびコピー制御方法
CN104583929A (zh) * 2012-10-12 2015-04-29 株式会社日立制作所 存储装置和数据管理方法
US9454474B2 (en) * 2013-03-05 2016-09-27 Western Digital Technologies, Inc. Methods, devices and systems for two stage power-on map rebuild with free space accounting in a solid state drive
US8751763B1 (en) 2013-03-13 2014-06-10 Nimbus Data Systems, Inc. Low-overhead deduplication within a block-based data storage
JP2015001908A (ja) * 2013-06-17 2015-01-05 富士通株式会社 情報処理装置、制御回路、制御プログラム、および制御方法
US9852066B2 (en) * 2013-12-20 2017-12-26 Sandisk Technologies Llc Systems and methods of address-aware garbage collection
JP5858081B2 (ja) * 2014-03-27 2016-02-10 Tdk株式会社 メモリコントローラ、メモリシステム及びメモリ制御方法
US9652153B2 (en) * 2014-09-02 2017-05-16 Sandisk Technologies Llc Process and apparatus to reduce declared capacity of a storage device by reducing a count of logical addresses
JP2016126632A (ja) 2015-01-07 2016-07-11 富士通株式会社 ストレージ装置、ストレージシステム、データ読み出し方法、及びストレージプログラム
US20170337212A1 (en) * 2015-01-13 2017-11-23 Hitachi Data Systems Engineering UK Limited Computer program product, method, apparatus and data storage system for managing defragmentation in file systems
WO2016181481A1 (ja) * 2015-05-12 2016-11-17 株式会社日立製作所 ストレージシステムおよび記憶制御方法
JP2017049806A (ja) 2015-09-02 2017-03-09 富士通株式会社 ストレージ制御装置およびストレージ制御プログラム
US20170147499A1 (en) * 2015-11-25 2017-05-25 Sandisk Technologies Llc Multi-Level Logical to Physical Address Mapping Using Distributed Processors in Non-Volatile Storage Device
JP6414853B2 (ja) * 2015-12-14 2018-10-31 東芝メモリ株式会社 メモリシステムおよび制御方法
JP6414852B2 (ja) * 2015-12-14 2018-10-31 東芝メモリ株式会社 メモリシステムおよび制御方法
US10114743B2 (en) * 2016-04-06 2018-10-30 Sandisk Technologies Inc. Memory erase management
JP6553566B2 (ja) * 2016-09-23 2019-07-31 東芝メモリ株式会社 メモリシステムおよび制御方法
JP2019057178A (ja) * 2017-09-21 2019-04-11 東芝メモリ株式会社 メモリシステムおよび制御方法
JP6840113B2 (ja) * 2018-09-20 2021-03-10 株式会社日立製作所 ストレージコントローラ及びストレージ制御方法

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20140115258A1 (en) * 2012-10-18 2014-04-24 Oracle International Corporation System and method for managing a deduplication table
US20140143213A1 (en) * 2012-11-22 2014-05-22 Kaminario Technologies Ltd. Deduplication in a storage system
US20150019507A1 (en) * 2013-07-15 2015-01-15 International Business Machines Corporation Optimizing hash table structure for digest matching in a data deduplication system
TW201626230A (zh) * 2015-01-06 2016-07-16 國立臺灣科技大學 利用快閃記憶體的壞頁來存取資料的方法

Also Published As

Publication number Publication date
CN109542332A (zh) 2019-03-29
US11132295B2 (en) 2021-09-28
US11693770B2 (en) 2023-07-04
US20220083466A1 (en) 2022-03-17
US20190087328A1 (en) 2019-03-21
US10545864B2 (en) 2020-01-28
CN109542332B (zh) 2022-04-12
US20200110698A1 (en) 2020-04-09
TW201915742A (zh) 2019-04-16
JP2019057172A (ja) 2019-04-11

Similar Documents

Publication Publication Date Title
TWI670596B (zh) 記憶體系統及控制非揮發性記憶體之控制方法
TWI644211B (zh) Memory system and control method for controlling non-volatile memory
US12019872B2 (en) Storage device that writes data from a host during garbage collection
US11669444B2 (en) Computing system and method for controlling storage device
US12038834B2 (en) Memory system and method for controlling nonvolatile memory during command processing without replacing defective blocks
US10789162B2 (en) Memory system and method for controlling nonvolatile memory
CN109240938B (zh) 存储系统以及控制非易失性存储器的控制方法
US10282288B2 (en) Memory system and method for controlling nonvolatile memory
JP6785204B2 (ja) メモリシステムおよび制御方法
CN111949206A (zh) 存储器系统、控制器以及控制器的操作方法
JP2019016386A (ja) メモリシステムおよび制御方法
JP6721765B2 (ja) メモリシステムおよび制御方法
JP2022036263A (ja) 制御方法