[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

TW201539187A - 快閃記憶體之壓縮、讀取方法及應用其方法的裝置 - Google Patents

快閃記憶體之壓縮、讀取方法及應用其方法的裝置 Download PDF

Info

Publication number
TW201539187A
TW201539187A TW104103867A TW104103867A TW201539187A TW 201539187 A TW201539187 A TW 201539187A TW 104103867 A TW104103867 A TW 104103867A TW 104103867 A TW104103867 A TW 104103867A TW 201539187 A TW201539187 A TW 201539187A
Authority
TW
Taiwan
Prior art keywords
header
compressed
data
lba
data block
Prior art date
Application number
TW104103867A
Other languages
English (en)
Other versions
TWI648622B (zh
Inventor
Kun Meng Lee
Priyanka Thakore
Original Assignee
Tidal Systems Inc
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 Tidal Systems Inc filed Critical Tidal Systems Inc
Publication of TW201539187A publication Critical patent/TW201539187A/zh
Application granted granted Critical
Publication of TWI648622B publication Critical patent/TWI648622B/zh

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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; CALCULATING OR 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; CALCULATING OR 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; CALCULATING OR 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/0625—Power saving in storage systems
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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; CALCULATING OR 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; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10—Providing a specific technical effect
    • G06F2212/1016—Performance improvement
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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/1028—Power efficiency
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/40—Specific encoding of data in memory or cache
    • G06F2212/401—Compressed data
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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/7207—Details relating to flash memory management management of metadata or control data
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR 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/7208—Multiple device management, e.g. distributing data over multiple flash devices
    • 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)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Memory System (AREA)
  • Detection And Correction Of Errors (AREA)

Abstract

揭露用於從非揮發性儲存器如SSD裝置讀取壓縮資料的系統及方法，一邏輯區，例如：資料的頁，包含多個被壓縮的資料區塊，使得其長度不同。頁的一標頭區儲存用於該資料區塊的標頭及儲存每一資料區塊的長度。標頭區可為根據錯誤校正方式編碼標頭的碼字。為了讀出資料區塊，硬體解碼器會要求讀取頁以及傳輸標頭區至硬體解碼器，其解碼標頭以取得用於所需資料區塊的偏移量。不指示頁的讀取，偏移量被硬體解碼器使用以請求所需資料區塊的傳輸，然後將其解碼並回傳至請求裝置。

Description

快閃記憶體之壓縮、讀取方法及應用其方法的裝置
本發明涉及一種在快閃記憶體系統中存取壓縮資料的系統。
固態驅動器（Solid-state drives, SSDs），也被稱為固態硬碟，是資料儲存設備，其使用NAND快閃記憶裝置作為儲存元件。通常這樣的裝置具有一個SSD控制器接受在一端的主機命令且與其他NAND快閃記憶裝置通信。NAND快閃記憶裝置是一種非揮發性儲存裝置的類型，當斷電時仍保存資料。SSD控制器透過NAND介面存取NAND快閃記憶裝置。NAND裝置具有有限的寫入／程序週期。資料寫入操作至NAND快閃記憶裝置包括兩個階段。資料傳送階段和記憶程序階段。同樣地，資料讀出被細分為兩個階段。第一個階段為記憶讀取階段和第二個階段為資料傳送階段。記憶讀取階段為控制器引入了一個相對於資料的讀出時間非常大的延遲（〜60微秒）。
NAND快閃晶粒的物理分層被分解成面（planes）、區塊（blocks）及頁（pages）。一個NAND快閃晶粒可包含多個面，每一面分割成區塊，以及每一區塊包含N個頁。一個典型的NAND具有二個面，～4K區塊及每一區塊具有256個頁。
顯而易見，頁是讀取／寫入操作的最小記憶單元，即一個程序或讀取操作被執行在頁上。典型NAND頁的大小是～4K位元組（Byte）、～8K位元組及～16K位元組。所述頁的大小可稍大於4K位元組、8K位元組或16K位元組以適應ECC奇偶校驗數據。典型的NAND介面的資料速率可為200MBps至400MBps，對於讀取，記憶讀取時間將為～60μs，~16KB資料的資料傳出將為~40μs，8KB資料的資料傳出將為~20μs，4KB資料的資料傳出將為~10μs。
邏輯區塊位址（Logical block addressing, LBA）是用於描述儲存在計算機儲存裝置上的資料的區塊的位置的通用機制，通常用於硬碟及SSDs（請參閱：http://en.wikipedia.org/wiki/Computer_storage）。
典型的主機LBA單位為512bytes以及在SSD中為4KB。所述SSD控制器可選擇在4KBytes上操作且管理在512byte主機LBA及4KByte控制器LBA之間的映射（mapping）。在系統中每一LBA需要被映射到唯一的資料單元，此資料單元的大小定義多大的物理位址指標，因此LBA指標的大小會隨著晶粒數量、區塊數量、頁數量及資料單元的大小而變化，取決於在頁中的資料單元的大小。
舉例來說，一個配置SSD的例子如下：
系統中的晶粒數量：128晶粒=2^7。
每一晶粒的區塊數量：4K+區塊=2^13。
每一區塊的頁數量：256頁=2^8。
LBA資料單元大小：~4KB。
在16KB中4KB的LBA的數量：4。
物理裝置容量：128*4K(+)*256*16KB+=2^43。
邏輯裝置容量：128*4K*256*16KB=2^41=2TB。
在裝置中LBA位置的數量：2TB/4KB=2^29。
指向物理位置的LBA表的一個條目（Entry）的總位元=7（對於晶粒）+13（對於區塊）+8（對於頁）+2（對於4個LBA）=30Bits。
儲存物理LBA位置的LBA表的總大小=30bits*2^29條目=1.875GBytes。
所述LBA條目通常會全面的四捨五入至位元組以用於每一韌體管理機制，其結果是4位元組被用於每一LBA條目且總LBA表大小成為4B*2^29條目=2GBytes，在此情況下，4KB主機資料被編碼及映射作為4KB資料及奇偶校驗位元至NAND快閃。
文中所述的裝置和方法提供一種用於在NAND快閃SSD或其他非揮發性儲存裝置中儲存資料的裝置和方法的改善。所述裝置和方法揭露增加可被儲存在SSD的資料數量，以及減少用於存取SSD的LBA表的大小。
本發明揭露一種快閃記憶體之壓縮、讀取方法及應用其方法的裝置。
首先，本發明揭露一種壓縮方法，其步驟包括：壓縮多個資料區塊以產生多個壓縮區塊；產生多個標頭，每一標頭包含所述壓縮區塊其中之一的壓縮長度；寫入該些標頭至非揮發性記憶裝置的邏輯區；以及寫入這些壓縮區塊至邏輯區。
接著，本發明揭露一種用於讀取壓縮資料之方法，其步驟包括：透過記憶體控制器裝置接收來自主機裝置的讀取請求，此讀取請求參照儲存裝置的邏輯區及儲存在邏輯區的第一資料區塊；透過記憶體控制器裝置取回儲存在邏輯區的標頭區，此標頭區包含多個標頭，每一標頭包含儲存在邏輯區的多個壓縮資料區塊的識別及長度，這些壓縮資料區塊包含代表第一資料區塊的第一壓縮資料區塊；透過記憶體控制器裝置確定標頭區的第一壓縮資料區塊在邏輯區內的偏移量；透過記憶體控制器裝置從位於儲存裝置中的偏移量取回第一壓縮資料區塊；解壓縮第一壓縮資料區塊以取得第一資料區塊；以及回傳第一資料區塊至主機裝置。
另外，本發明揭露一種裝置，此裝置包含：主機計算機裝置、儲存裝置及記憶體控制器裝置。其中，主機計算機裝置包含一個或多個處理器；儲存裝置包含非揮發性儲存媒體；記憶體控制器裝置操作耦合至主機計算機裝置及儲存裝置，此記憶體控制器裝置被配置為：接收來自主機計算機裝置參照第一資料區塊的讀取請求；指示儲存裝置讀取儲存媒體的邏輯區至內部緩衝器；指示儲存裝置傳輸邏輯區的標頭區至記憶體控制器裝置，標頭區包含多個標頭，各標頭包含儲存在邏輯區中的多個資料區塊其中之一的識別及長度；判斷標頭區以確定第一資料區塊前的資料區塊的一部分的長度的總和；使用總和指示儲存裝置傳輸第一資料區塊；以及回傳第一資料區塊至主機計算機裝置。
以下將配合圖式及實施例來詳細說明本發明之實施方式，藉此對本發明如何應用技術手段來解決技術問題並達成技術功效的實現過程能充分理解並據以實施。
容易理解的是，本發明一般所述和圖中所示意的組件，可以佈置和設計在各種不同的配置中。因此，本發明實施例以下列更詳細的描述，如在圖中所示意，並非意在限制本發明的範圍，如申請專利範圍，而是僅為根據本發明當前構思的實施例的某些代表性的例子。目前描述的實施例將通過參閱附加圖式得到最好的理解，其中相同的部件在各處用相同的標號。
本發明已被開發以響應本領域的當前狀態，並且特別地響應於本領域中還沒有被完全由當前可用的設備和方法解決這些問題和需求。因此，本發明已經發展到提供設備和方法，用於在快閃記憶體中儲存及存取壓縮資料。
具體實施方式按照本發明可以體現為裝置、方法或計算機程式產品。因此，本發明可採取完全硬體實施例，完全軟體實施例（包括韌體，常駐軟體，微代碼等）的形式，或者一個實施例中結合軟體和硬體方面可能所有通常在此可以稱為作為一個“模組”或“系統”。此外，本發明可以採取計算機程式產品中體現在媒體中具有表達的計算機可執行程式碼的任何有形媒體的形式。
一個或多個計算機可用或計算機可讀媒體的任何組合都可以使用。例如，計算機可讀媒體可以包括一個或多個可攜式計算機軟碟、硬碟、隨機存取記憶體（RAM）裝置、唯讀記憶體（ROM）裝置、可抹除可程式化唯讀記憶體（EPROM或快閃記憶體）裝置、可攜式唯讀光碟機（CDROM）、光儲存裝置、磁儲存裝置。在選定實施例中，計算機可讀媒體可以包括任何可以包含儲存、通信、傳播、或由使用或與指令執行系統、裝置或設備結合使用的程式的非暫時性平台。
用於實施本發明執行操作的計算機程式碼可以被寫入的一個或多個程式語言的任何組合，包括物件導向程式語言，如：Java、Smalltalk、C++、或類似的程式語言，以及常規的程序型程式語言，如“C”程式語言或類似的程式語言。程式語言可以完全執行在計算機系統上作為一個獨立的軟體套件、在一個獨立的硬體設備上、部分在遠端計算機上相隔一段距離的計算機、或者完全在遠端計算機或伺服器上。在最後一種情形中，遠端計算機可以通過任何類型的網路連接到計算機，包含：局域網路（LAN）或廣域網路（WAN），或者連接可進行到外部計算機（例如：使用網際網路服務供應商來通過網際網路）。
本發明是參照根據本發明的實施例以流程圖及／或方法的方塊圖、設備（系統）和計算機程式產品說明如下。但可以理解的是，流程圖及／或方塊圖和方塊的組合中的流程圖及／或方塊圖中的每個方塊可以通過計算機程式指令或程式碼來實現。這些計算機程式指令可以提供給一般計算機、專用計算機或其他可程式化資料處理設備的處理器以產生機器，使得指令經由計算機或其他可程式化資料處理設備的處理器執行創建用於實現在流程圖及／或方塊圖方塊或多個方塊中指定的功能／行為。
這些計算機程式指令也可以被儲存在一個非臨時性計算機可讀媒體，其可以引導計算機或其他可程式化資料處理設備以特定方式起作用，使得儲存在計算機可讀媒體的指令生產製造物品，包括指令方法實現在流程圖及／或方塊圖方塊或多個方塊中指定的功能／動作。
指令也可以被加載到計算機或其他可程式化資料處理設備，以便使一系列操作步驟的計算機程式可以在計算機或其他可程式化設備上執行以產生計算機實現的過程，使得指令執行上在計算機或其他可程式化設備用於實現在流程圖及／或方塊圖方塊或多個方塊中指定的功能／動作提供處理。
第1圖係為方塊圖說明一個計算機裝置100的例子，計算機裝置100可用於執行如文中所述的各種程序，計算機裝置100可充當伺服器、客戶端、或任何其他計算實體。文中所述的計算機裝置可執行各種監控功能，以及執行一個或多個應用程式，如文中所述的應用程式。計算機裝置100可以是任何各式各樣的計算機裝置，例如：桌上型電腦、筆記型電腦、伺服器電腦、手持式電腦及其他相似物。
計算機裝置100包含一個或多個處理器102、一個或多個記憶裝置104、一個或多個介面106、一個或多個大容量儲存裝置108、一個或多個輸入／輸出（Input／Output, I／O）裝置110、以及顯示裝置130，這些全部耦合到匯流排112。處理器102包含一個或多個處理器或控制器，其執行儲存在記憶裝置104及／或大容量儲存裝置108的指令，處理器102也可包含各種類型的計算機可讀媒體，如：快取記憶體。
記憶裝置104包含各種計算機可讀媒體，例如：揮發性記憶體（如：隨機存取記憶體114）及／或非揮發性記憶體（如：唯讀記憶體116）。記憶裝置104也可以包括可複寫的唯讀記憶體，例如：快閃記憶體。
大容量儲存裝置108包含各種計算機可讀媒體，如：磁帶、磁碟、光碟、固態記憶體（例如：快閃記憶體）等等。如第1圖所示意，一個特定的大容量儲存裝置是硬碟驅動器124。各種驅動器也可以被包含在大容量儲存裝置108以便能夠自各計算機可讀媒體讀取及／或寫入各計算機可讀媒體。大容量儲存裝置108包含可移動媒體126及／或不可移動媒體。
輸入／輸出裝置110包含各種裝置，其允許資料及／或其他信息被輸入至或取自計算機裝置100。舉例來說，輸入／輸出裝置110包含游標控制裝置、鍵盤、小鍵盤、麥克風、螢幕或其他顯示裝置、揚聲器、印表機、網路介面卡、數據機、鏡頭、電荷耦合元件或其他圖像擷取裝置、以及相似物。
顯示裝置130包含能夠顯示訊息給計算機裝置100的一個或多個使用者之任意類型的裝置。例如顯示裝置130包含監視器、顯示終端、視訊投影裝置以及其相似物。
介面106包含各種介面，其允許計算機裝置100與其他系統、裝置或計算環境互動。舉例來說，介面106包含任意數量的不同網路介面120，例如：連接區域網路、廣域網路、無線網路及網際網路的介面。其他介面包含使用者介面118及外圍裝置介面122，介面106也可包含一個或多個使用者介面元件118。介面106也可包含一個或多個外圍介面，如：印表機、指向裝置（滑鼠、觸控板等等）、鍵盤及其相似物的介面。
匯流排112允許處理器102、記憶裝置104、介面106、大容量儲存裝置108及輸入／輸出裝置110相互通信，以及與耦合至匯流排112的其他裝置或組件相互通信。匯流排112表示一種或多種類型的匯流排結構，例如：系統匯流排、PCI匯流排、IEEE 1394匯流排、USB匯流排等等。
為了說明起見，程序和其他可執行程序組件在此顯示為分散方塊，儘管應當被理解為程序和組件可常駐在計算機裝置100的不同儲存組件中的不同時間，並且透過處理器執行。另外，文中所述的系統和程序可被實現於硬體或是硬體、軟體及／或韌體的組合。舉例來說，一個或多個特定應用積體電路（Application Specific Integrated Circuits, ASICs）可被程式化以執行文中所述的一個或多個系統及程序。
請參閱第2圖，在一些實施例中，系統200包含SSD 200，其可包含多個NAND快閃記憶裝置202。一個或多個NAND快閃記憶裝置202可與一個和SSD控制器206相互作用的NAND介面204連接。所述SSD控制器206可從實現在主機裝置（如：一個裝置包含計算機裝置100的一些或全部屬性）上或用於主機裝置的主機介面208接收讀寫指令。所述主機介面208可為資料匯流排、記憶體控制器、或計算機裝置的輸入／輸出系統的其他組件。
文中揭示的系統及方法可透過主機介面208和NAND介面204之間的SSD控制器206被實現。在其他具體實施中，所述NAND介面204可實現文中揭示的一些或全部的功能。同樣在一些其他具體實施中，一個額外組件可被插入在常規的NAND介面204和SSD控制器206之間，用以實現文中所揭示的全部或部分功能。
文中揭示的系統和方法有利地提供儲存在NAND快閃記憶裝置202中的資料之壓縮，同時也減少映射和存取壓縮資料所需的資料，如儲存在NAND快閃記憶體的LBA表、SSD控制器、主機計算機裝置的RAM、或一些其它記憶裝置的RAM中。
本文中所提供的例子示例
範例1：樸素(NAÏVE)資料壓縮方式
壓縮的固有優點是增加了邏輯系統總容量，以及減少讀取和寫入操作的總功耗。特別是，相較於未壓縮的資料，主機LBA相同數量可佔用更少的空間。其結果導致相同物理空間，增加可被儲存在NAND裡面的LBA的數量（即：資料）。假如最大壓縮率是50%，可在相同的容量分配多達兩倍的資料（及LBA）。如上述例子，假設所有LBA具有此壓縮率，這意味著可以在16KB物理頁中儲存8個壓縮的LBA而不是4個未壓縮的LBA。此壓縮率定義寫入所述頁的資料長度。
假如不同LBA資料具有不同的壓縮率（其為典型的壓縮演算法），這些壓縮的LBA資料的最終長度是不同的。現在間隔尺寸不是取決於4KB最小單元，而且每一個壓縮的LBA資料大小是可變的。在一些具體實施中，其可為1位元組的間隔尺寸準確偏移到編碼的碼字資料（encoded codeword data）的開始或為1KB，假如1KB被設為最小單元（在文中所述的其他情況下，這是關閉的）。這對LBA指標大小有直接影響。現在以2位元來表示位置，15位元需要被儲存以在16KB+（=2^15 Bytes）的頁中指示LBA資料的準確開始，或在1KB間隔尺寸的例子中為5位元。在SRAM空間而言，這對系統是巨大的開銷，而且對LBA表而言，任何存取超過32位元的查找需要多次讀取及重疊資料的管理。
由於每個LBA可被分配一個單獨的碼字，這需要為LBA表中的每一個LBA提供開始位置。由於壓縮的LBA長度可變化，每一個LBA的開始位置可能必須精準到1位元組或2位元組，即：對於一個16KB+頁的偏移量可以是在0~2^15的範圍內，而且位址指標在頁內指示將是15位元。假設高達25%的壓縮率，使用者資料的每一個4KB可被壓縮至1KB加上碼字位元。在極端的情況下，所有LBA為25%壓縮且每一個16KB+頁可包含16個LBA。因此，範例1的方案的數值特性如下：
邏輯裝置容量：128*4K*256*16KB=2^41=2TB。
在裝置中的LBA位置的數量：2TB/4KB=2^29條目。
考量跨越16KB+頁的可變偏移量的LBA表內的一個條目之總位元長度=7（對於晶粒）+13（對於區塊）+8（對於頁）+15（可變LBA偏移跨越16KB+頁的大小）=每一條目43位元。
儲存物理LBA位置的LBA表的總大小=43位元*2^29條目=2.6875GBytes。
當每條目四捨五入至位元組邊界時的總LBA表大小，每條目6位元組=6位元組*2^29=3GByte。
在範例1，存取LBA的壓縮資料可運行如下：
1)    韌體（如：主機裝置的韌體）讀出LBA表條目連同分配給LBA偏移的N位元（如：43）。
2)    NAND讀出整個LBA碼字。
3)    解碼碼字。
4)    獲得為了主機傳輸目的或為了類似垃圾回收（garbage collection）的內部操作的LBA使用者資料。
範例1的樸素（naïve）方法具有非常大的LBA表大小之問題，一種方式為了解決這個問題將節省用於每一LBA的指標至NAND頁本身而不是LBA表。這種方式將在稍後更詳細地作討論（範例3、4及5）。假如標頭被用來儲存指標資訊，這需要讀出標頭資訊以取得LBA開始位置或在物理頁中的LBA偏移量。此標頭資訊也需要用相同的校正能力編碼作為使用者資料。這種方法可以用兩種方式取回LBA資料來完成，第一種方式是先讀取標頭以取得指標資訊，接著再讀出LBA資料。此種方式有兩種從NAND的讀取請求（請參閱後述的範例3）。第二種方式會帶來從NAND讀出的冗餘資料，作為LBA資料的位置無法在找到指標資訊之前確定（請參閱後述的範例4）。
範例2：LBA指標儲存在NAND裝置
另一種方式是將指標資訊隨著在碼字中的使用者資料進行編碼，在此情況下，讀出指標資訊將涉及讀出包含使用者資料的整個碼字、對其解碼，然後找出指標資訊給LBA資料。在此方式，LBA表具有儲存每個LBA的碼字位置及碼字的數量，用以讀出指標資訊和LBA資料。對於高達25%的壓縮率，LBA的數量在16KB+物理頁中，其範圍將從4個LBA多達至16個LBA。在LBA表中被配置到碼字識別的位元數量將取決於編碼碼字的大小。對於2KB的碼字，在16KB物理頁中碼字的數量將為8個且在LBA表中需要3個位元。更大的碼字大小，每一碼字將包含更多LBA。由於壓縮的LBA可以跨越多個碼字，例如：4KB資料可以跨越三個2KB碼字，因此，在3位元上有多2個位元，即：需要5位元以指示在編碼碼字中的LBA內容。
請參閱第3A圖，在常規的方法中，一個頁包括多個LBA（A至D），每一個都具有相同的寬度。對於具有儲存在LBA表的指標的樸素（naïve）壓縮方法（範例1），一個頁可包含具有如第3B圖所示的可變長度的多個LBA（A至D），因為LBA（A至D）具有可變長度，多個LBA（A至D）可在相同碼字中進行編碼。舉例來說，因為LBA A是小的，壓縮的LBA A及LBA B可為了錯誤校正目的被編碼在單一碼字中，例如：LBA A及LBA B可被編碼在單一碼字CWAB中，其可被解碼以獲得LBA A及LBA B。
請參閱第3C圖，範例2可以儲存每個LBA（A至D）及其相應的標頭（HA至HD）。每個LBA（A至D）及其相應的標頭（HA至HD）可以被編碼在單一碼字（CWA至CWD）中。
對於範例2的儲存方式，特性數值如下：
邏輯裝置容量：128*4K*256*16KB=2^41=2TB。
在裝置中LBA位置的數量：2TB/4KB=2^29條目。
考量跨越16KB+頁的可變偏移量的LBA表內的一個條目之總位元長度=7（對於晶粒）+13（對於區塊）+8（對於頁）+5（2KB碼字偏移量及在2KB碼字內高達4KB資料偏移量）=每一條目33位元。
儲存物理LBA位置的LBA表的總大小=33位元*2^29條目=2.0625GBytes。
每一條目四捨五入至位元組，每一條目5位元組=5Byte*2^29=2.5GBytes。
對於範例2，存取LBA的壓縮資料可進行如下：
1)    韌體讀出LBA表條目連同分配給碼字的N位元，其中N為碼字的位元數量。
2)    NAND讀出整個碼字（~60μs NAND快閃讀取時間加~10μs資料傳輸時間）。
3)    解碼碼字。
4)    獲得指示LBA開始的指標資訊。
5)    使用在此位置的資料作為為了主機傳輸目的或為了類似垃圾回收的內部操作的LBA使用者資料。
範例2的缺點是讀出不必要的資料，即：如果一個碼字包含8個LBA，那麼讀出1個LBA連帶讀出其餘7個LBA，這耗損傳輸功率和NAND傳輸時間。還有解碼需要被運行在8個LBA+標頭資訊，從而耗損額外的解碼功率（超過必要功率7倍）。此外，解碼8個LBA而不是1個LBA需要額外的時間，從而影響效能。對於此方式（範例2），LBA表的大小增加25%且讀出LBA導致額外讀出整個碼字和標頭資訊的後處理（post processing）運算以獲得LBA偏移量。
範例3：指標在不同碼字中單獨儲存
在另一實施例中，每個LBA被編碼成一個獨立的碼字，而且指標資訊被儲存在NAND內部作為一個單獨碼字。舉例來說，請參閱第3D圖，標頭（HA至HD）對應至LBA（A至D）儲存在單獨碼字或多個碼字而不是LBA（A至D）碼字本身。舉例來說，HA和HB可被編碼在碼字CWH1而碼字CWH2則編碼標頭HC和HD。所述LBA（A至D）是分別被編碼至一個或多個碼字（CWA至CWD）。至於文中揭示的其他具體實施中，多個LBA（A至D）可以以單個碼字來表示，或者，每個LBA（A至D）可透過它自己的碼字（CWA至CWD）來表示。
對於範例3，從一個特定的LBA讀取資料可進行如下：
1)    韌體讀出LBA表條目，其不包含至特定的LBA資料的指標。
2)    發布NAND讀取及讀出標頭碼字（~60μs記憶體讀取時間+資料傳輸時間）。
3)    解碼標頭碼字。
4)    後處理解碼後的標頭碼字以取得指示LBA開始的指標資訊。
5)    重發頁讀取導致另一個~60μs NAND讀取時間+資料傳輸時間。
6)    解碼LBA資料。
7)    使用在此位置的資料作為為了主機傳輸目的或為了類似垃圾回收的內部操作的LBA使用者資料。
範例4：具有隨後的資料抽取的標頭及LBA的讀出
在另一方式中，如「第3D圖」所示儲存的資料可被存取如下：
1)    發布NAND頁讀取及讀出整個頁內容（~60μs記憶體讀取時間+資料傳輸時間）。
2)    解碼整個頁內容，包含標頭指標碼字，後處理解碼後的標頭碼字以獲得指示LBA開始的指標資訊。
3)    使用指標資訊從解碼頁內容獲得LBA資料。
4)    使用在此位置的資料作為為了主機傳輸目的或為了類似垃圾回收的內部操作的LBA使用者資料。
範例5：硬體解碼器實現分離標頭及LBA資料傳輸用於單頁讀取
如下所述的範例5之方式補救上述方式的不足之處，特別是範例5可有利於：
1)    從LBA表移除LBA偏移位元。LBA表只需要包含LBA的位置高達物理頁等級；
2)    減少需要讀出的資料和解碼要求的LBA加上標頭區，從而節省傳輸時間和傳輸功率；
3)    只需要在一個特定的LBA和標頭區進行解碼從而節省解碼功率；
4)    實現高效能無須後處理，並且由韌體拆散標頭和資料，因為這是由硬體解碼器進行；以及
5)    在垃圾回收或系統資料循環過程中無須LBA重新編碼。
請參閱第4圖，根據文中所揭示的系統及方法，所述系統可為了提供存取壓縮的資料併入SSD控制器206或NAND介面204。硬體解碼器404可被插入至讀出引擎402和主機介面412之間。讀出引擎402可用於從硬體解碼器404響應頁讀取。作為響應，從NAND快閃記憶裝置202取回請求的頁並儲存至內部緩衝器。讀出引擎402更可進一步操作以響應傳輸來自硬體解碼器的指令，透過內部緩衝器的傳輸指令讀取資料，並且提供資料至硬體解碼器。
所述硬體解碼器404可包含標頭解碼模組406、LBA偏移計算模組408以及LBA／標頭端偵測模組410。所述標頭解碼模組406是可操作以解碼標頭碼字。所述LBA偏移計算模組408可被配置以計算每一個LBA碼字的偏移量和確定硬體解碼器404在接收到來自主機介面412的讀取命令要求特定的LBA之偏移量。所述LBA／標頭端偵測模組410使用從標頭確定的偏移量以確定在請求的LBA的一個頁內的一個實際的偏移量。為了取得基本偏移量，這可包含確定所述標頭區的末端。為了取得在請求的LBA的一個頁內的偏移量，此偏移量從標頭被確定後可加至此基本偏移量。
硬體解碼器404可被配置以自動發布適當的LBA讀出用於確定請求的LBA的偏移量的LBA。在具體實施上，整個操作是透過硬體執行，不需要主機裝置的韌體對資料進行後處理。另外，硬體解碼器404解碼標頭和計算偏移量，相同的頁讀取操作被用於讀出標頭碼字和LBA資料碼字，從而不再需要第二種的頁讀取操作。在頁的標頭和資料的格式以及操作順序將在稍後作詳細描述。
請參閱第5圖，系統400可被用於執行所示相對於來自主機裝置的讀取指令之方法500，所述讀取指令參考在NAND快閃儲存裝置內的頁的LBA。讀出引擎402接收在LBA請求中的標頭資料的傳輸以及在響應時接收來自NAND快閃的頁資料502。如上所述，讀出引擎402可執行頁讀取請求，其請求來自NAND快閃的頁資料502並且儲存在內部緩衝器。所述讀出引擎402可提供標頭資料506到標頭解碼模組406。標頭資料506可被提供以響應來自硬體解碼器404的資料傳輸命令。標頭解碼模組406解碼標頭資料以獲得解碼後的標頭510，所述解碼後的標頭510被用於LBA偏移計算模組408以確定特定的LBA的偏移量514，其被參照在相對於被執行的方法500的讀取指令。偏移量514被用於LBA／標頭端偵測模組410以確定在所請求的LBA開始的頁內的偏移量。舉例來說，偏移量514可被加至一個基本位址發現儲存在頁中的資料之標頭區的末端。所述偏移量514可被用於LBA／標頭端偵測模組410以確定在請求的LBA之頁內的偏移量。請求518參照此偏移量可被提交至讀出引擎402，其後輸出LBA資料520，即：所要求的LBA之LBA碼字。
第4圖的系統及第5圖的方法可被用於讀取資料，其編碼每一個LBA作為如第3D圖所示意的獨立的碼字。這意味著根據壓縮資料的結果每一個碼字大小是可變的。在一個壓縮25%的例子中，每個碼字具有4KB的未壓縮大小，範圍可以從1KB（原始資料的25%）至4KB（原始資料的100%）。所有LBA的標頭在物理頁內部，如：32KB頁在物理頁內部被分組且如上述第3D圖所述編碼至標頭碼字。每個標頭對應一個儲存在頁中且其標頭被儲存其中的LBA，每個標頭可包含其參照的LBA的識別、其參照的LBA的長度、以及韌體資料。
響應於來自主機介面的讀取請求，隨後指示讀出引擎讀取頁至其緩衝區。硬體引擎可先讀出標頭碼字且解碼這些標頭碼字。解碼可和從NAND快閃移出其餘資料並行發生。在解碼這些碼字且獲得標頭後，LBA偏移計算模組408累積標頭內的長度以產生編碼後的LBA碼字的偏移量（即：指示開始位置）。舉例來說，LBA N的一個開始位址／偏移量將為：「Header_codeword_size*Number_of_Header codewords+Length(LBA M)」。硬體解碼器404可匹配來自韌體（如：主機介面）所請求的LBA至解碼後的標頭內容以得出 LBA偏移量，因為標頭包含每一個壓縮的LBA資料流的長度。
一旦得到LBA偏移量，硬體解碼器404可發布資料傳輸命令以讀出LBA碼字，然後將其傳送至解碼器，如：硬體解碼器。硬體解碼器在物理頁中執行識別和讀出LBA碼字，它不需要重新發出頁面讀取從而完成來自單頁讀取記憶體存取（~55us）的標頭和LBA兩者的讀取。
標頭碼字可以足夠小且採取相較於LBA碼字的讀出和解碼還要短時間的讀出及解碼。其結果對效能影響相較於基於在LBA表中簡單地讀出未壓縮的LBA碼字是非常小的。在大多數情況下，效能實際上更好，因為要處理的資料量相較於未壓縮資料減少了。舉例來說，第6圖根據範例5的方法所示意的讀取操作的時間軸600，如圖所示，首先頁讀取為約60μs的延遲602，之後是約1.5μs的延遲604以傳輸標頭資料至硬體解碼器404。標頭解碼可引入約2μs的延遲606，在此延遲606期間，頁讀取至晶粒可透過硬體解碼器404或讀出引擎402來阻擋，具體來說，延遲606可被NAND空閒週期佔據。所請求的LBA碼字可被轉移導致延遲608取決於LBA碼字的長度（1KB約為2.5μs至4KB約為10μs）。所述LBA碼字可被解碼造成約2μs的延遲610。
第7圖示意一種用於處理讀取命令的方法700，所述方法700可透過硬體解碼器404與讀出引擎402的組合被執行。在所述方法700之前可透過來自主機介面的指令回執，或一些其他的內部處理，如：垃圾回收，從NAND快閃裝置讀取特定的LBA。所述指令參照頁，該頁其中的LBA被發現具有LBA被讀取的識別。
所述方法可包含發布（步驟702）一個頁讀取至NAND快閃裝置用於來自主機介面的讀取指令所參照的頁。作為響應，讀出引擎402可從被儲存在NAND快閃裝置（例如：適當的NAND晶粒）的頁讀取頁資料，並且儲存頁資料至緩衝區。
所述方法700可包含從頁資料讀取（步驟704）一個或多個標頭碼字，並且解碼（步驟706）標頭碼字以獲得標頭。所述標頭可隨後被分析以獲得（步驟708）一些或全部的LBA的偏移資訊。舉例來說，假如LBA N被讀取指令參照，那麼LBA 0至N-1的長度可被加總以獲得LBA N的偏移量。除此之外，一個遞歸方法可被執行，從而計算出LBA N-1的偏移量，然後加上LBA N-1的長度以獲得LBA N的偏移量。基於LBA N-1的偏移量及其長度，LBA N-1的偏移量可以相同方式獲得，以及直至LBA 0的偏移量為0，或標頭區的最後一個位元。
一旦獲得偏移量，方法700可包含在偏移位址讀取（步驟710）LBA，舉例來說，其中，LBA N被請求，則相應的標頭可進行評估以確定LBA N的碼字的長度L。在步驟708確定LBA N的偏移量後，L位元可接著被傳輸。
在步驟708傳輸LBA碼字後可接著解碼（步驟712），並且LBA的使用者資料可被回傳（步驟714）至主機介面或其他請求組件或程序。解碼（步驟712）可包含解壓縮LBA或LBA可在壓縮的LBA提供至主機介面或其他請求實體之後被解碼，主機介面或其他請求實體發出讀出指令或透過一些其他中間實體或程序發出讀出指令。
範例5的方式數值特性如下：
邏輯裝置容量：128*4K*256*16KB=2^41=2TB。
裝置中LBA位置的數量：2TB/4KB=2^29條目。
考量跨越16KB+頁的可變偏移量的LBA表內的一個條目之總位元長度=7（對於晶粒）+13（對於區塊）+8（對於頁）+0（標頭包含LBA碼字偏移資訊）=每一條目28位元。
儲存物理LBA位置的LBA表的總大小=28位元*2^29條目=1.75GBytes。
當每條目四捨五入至位元組，每條目4位元組=4Byte*2^29=2GBytes。
與其他方法（範例1至4）相較之下可以看出範例5的每個條目具有更多空閒位元，甚至與未壓縮資料相較亦同。下列的表1顯示與其他三個範例相較，範例5減少的位元需求。這導致直接節省硬體記憶體需求以及降低管理LBA表條目的複雜性。具體而言，對於寫入頁的每個LBA，在LBA表中的相應條目可被建立或保持，不儲存每個LBA的長度或每個LBA在頁內的偏移量。
請參閱第8圖，其為第3D圖中所示的壓縮的LBA的儲存方式，能夠簡單且有效的垃圾回收或LBA的碎片整理（defragmentation）。舉例來說，硬體解碼器404、讀出引擎402或其他組件可執行所述方法800。例如：方法800可包含從頁讀取（步驟802）有效的LBA的碼字，並且省略讀取無效的LBA。無效的LBA可以是已經抹除不再代表被儲存的資料。方法800可包含覆寫（步驟804）頁，僅包含有效的LBA且省略無效的LBA。第3D圖的儲存方式之優點是有效的碼字之LBA可在無進行解碼及重新編碼的垃圾回收過程或在垃圾回收過程中解壓縮及壓縮其間被讀取及覆寫。
方法800還可包含更新（步驟806）頁的標頭區，這是方法800的主題。特別是，標頭對應每個有效的LBA可被編碼至一個或多個標頭碼字並且寫入至頁。標頭可包含在上述方法中指出的資訊，包含如LBA識別及長度這樣的資訊。
本文所述的系統和方法提供硬體技術用於智慧型標頭及取回，使壓縮資料能夠儲存至NAND快閃裝置。硬體自動化技術以解碼標頭，獲得在NAND頁中的LBA位置，以及執行自動讀出LBA碼字，為系統中之壓縮的現實使用情況提供一個獨特的優勢。這些方法的組合對於系統及主機操作會導致節省功率及性能提升。
本發明可以不背離其精神或本質特徵的其他特定形式體現。所述具體實施例的考量在各方面僅是說明而非限制性，特別是儘管方法提及NAND快閃SSD、其他SSD裝置或非揮發性儲存裝置，如：硬碟裝置也可使用文中所述的方法。本發明的權利範圍由所附申請專利範圍指出而不是由前面的描述，所有在權利要求的等效範圍和方式中的改變皆在本發明的權利範圍中。
100‧‧‧計算機裝置
102‧‧‧處理器
104‧‧‧記憶裝置
106‧‧‧介面
108‧‧‧大容量儲存裝置
110‧‧‧輸入／輸出裝置
112‧‧‧匯流排
114‧‧‧隨機存取記憶體
116‧‧‧唯讀記憶體
118‧‧‧使用者介面
120‧‧‧網路介面
122‧‧‧外圍裝置介面
124‧‧‧硬碟驅動器
126‧‧‧可移動媒體
130‧‧‧顯示裝置
200‧‧‧系統
202‧‧‧NAND快閃記憶裝置
204‧‧‧NAND介面
206‧‧‧SSD控制器
208‧‧‧主機介面
400‧‧‧系統
402‧‧‧讀出引擎
404‧‧‧硬體解碼器
406‧‧‧標頭解碼模組
408‧‧‧LBA偏移計算模組
410‧‧‧LBA／標頭端偵測模組
412‧‧‧主機介面
500‧‧‧方法
502‧‧‧來自NAND快閃的頁資料
506‧‧‧標頭資料
510‧‧‧解碼後的標頭
514‧‧‧偏移量
518‧‧‧請求
520‧‧‧LBA資料
600‧‧‧時間軸
602～610‧‧‧延遲
700、800‧‧‧方法
A~D‧‧‧LBA
HA~HD‧‧‧標頭
步驟702‧‧‧發布頁讀取至NAND快閃
步驟704‧‧‧讀出標頭碼字
步驟706‧‧‧解碼標頭碼字
步驟708‧‧‧獲得每一LBA的偏移量資訊
步驟710‧‧‧在偏移位置讀出感興趣的LBA
步驟712‧‧‧解碼LBA
步驟714‧‧‧回傳使用者資料
步驟802‧‧‧讀取有效LBA的碼字
步驟804‧‧‧覆寫有效LBA的碼字
步驟806‧‧‧更新標頭
第1圖係根據本發明實施例用於實現方法的計算機系統之方塊圖。 第2圖係根據習知技術的儲存系統的組件之方塊圖。 第3A至3D圖係說明資料儲存機制，包含根據本發明實施例的儲存機制之示意圖。 第4圖係根據本發明實施例的硬體解碼之方塊圖。 第5圖係根據本發明實施例的讀取壓縮資料之方法流程圖。 第6圖係根據本發明實施例的資料讀取的時間軸之示意圖。 第7圖係根據本發明實施例的讀取壓縮資料之方法流程圖。 第8圖係根據本發明實施例的垃圾回收之方法流程圖。
202‧‧‧NAND快閃記憶裝置
400‧‧‧系統
402‧‧‧讀出引擎
404‧‧‧硬體解碼器
406‧‧‧標頭解碼模組
408‧‧‧LBA偏移計算模組
410‧‧‧LBA/標頭端偵測模組
412‧‧‧主機介面

Claims (20)

  1. 一種壓縮方法，其步驟包括： 壓縮多個資料區塊以產生多個壓縮區塊； 產生多個標頭，每一標頭包含所述壓縮區塊其中之一的一壓縮長度； 寫入該些標頭至一非揮發性記憶裝置的一邏輯區；以及 寫入該些壓縮區塊至該邏輯區。
  2. 根據申請專利範圍第1項之壓縮方法，其中更包含更新關於所述資料區塊的邏輯識別的一資料表至該些壓縮區塊的一物理位置，該資料表只參考在該非揮發性記憶裝置的該邏輯區的一物理位址，不儲存該些壓縮區塊的一長度或從該邏輯區的該物理位置的一偏移量。
  3. 根據申請專利範圍第1項之壓縮方法，其中寫入該些標頭至該非揮發性記憶裝置的該邏輯區包含： 產生該些標頭的多個標頭的一標頭碼字，該標頭碼字包含一個或多個錯誤校正位元。
  4. 根據申請專利範圍第1項之壓縮方法，其中寫至該邏輯區中的該些壓縮區塊的所有壓縮區塊的標頭是在該邏輯區的一單一連續區。
  5. 根據申請專利範圍第1項之壓縮方法，其中該單一連續區比起該些壓縮區塊更靠近該邏輯區的一起始位址。
  6. 根據申請專利範圍第1項之壓縮方法，其中寫入該些壓縮區塊至該非揮發性記憶裝置包含產生代表該些壓縮區塊中多個壓縮區塊的至少一碼字，所述碼字包含一個或多個錯誤校正位元。
  7. 根據申請專利範圍第1項之壓縮方法，其中該些標頭各包含該些壓縮區塊中其中之一壓縮區塊的一識別。
  8. 根據申請專利範圍第1項之壓縮方法，其中寫入該些標頭及所述壓縮區塊至該邏輯區包含執行關於該非揮發性記憶裝置的一快閃記憶體程式操作，該非揮發性記憶裝置為一快閃記憶裝置。
  9. 一種用於讀取壓縮資料之方法，其步驟包括： 透過一記憶體控制器裝置接收來自一主機裝置的一讀取請求，該讀取請求參照一儲存裝置的一邏輯區及儲存在該邏輯區的一第一資料區塊； 透過該記憶體控制器裝置取回儲存在該邏輯區的一標頭區，該標頭區包含多個標頭，每一標頭包含儲存在該邏輯區的多個壓縮資料區塊的一識別及一長度，該些壓縮資料區塊包含代表該第一資料區塊的一第一壓縮資料區塊； 透過該記憶體控制器裝置確定該標頭區的該第一壓縮資料區塊在該邏輯區內的一偏移量； 透過該記憶體控制器裝置從位於該儲存裝置中的該偏移量取回該第一壓縮資料區塊； 解壓縮該第一壓縮資料區塊以取得該第一資料區塊；以及 回傳該第一資料區塊至該主機裝置。
  10. 根據申請專利範圍第9項之用於讀取壓縮資料之方法，其中確定該偏移量包含對應該第一壓縮資料區塊的一標頭之前加總包含在該些標頭的該長度。
  11. 根據申請專利範圍第9項之用於讀取壓縮資料之方法，其中確定該偏移量更包含： 確定該些標頭的一末端位置；以及 在對應該第一壓縮資料區塊的該標頭之前，加入包含在該些標頭的該長度的一總和。
  12. 根據申請專利範圍第9項之用於讀取壓縮資料之方法，其中透過該記憶體控制器裝置取回該標頭區包含： 由該記憶體控制器裝置發布讀取至該儲存裝置的一頁，該儲存裝置為一快閃NAND記憶裝置； 由該儲存裝置讀取該邏輯區至一緩衝器； 由該記憶體控制器裝置發布用於該標頭區的一第一傳輸請求至該儲存裝置；以及 由該記憶體控制器裝置接收該標頭區。
  13. 根據申請專利範圍第12項之用於讀取壓縮資料之方法，其中透過該記憶體控制器裝置取回該第一壓縮資料區塊包含： 由該記憶體控制器裝置發布用於該第一壓縮資料區塊的一第二傳輸請求，該第二傳輸請求被隨後傳輸以發布讀取至該儲存裝置的該頁而不執行由該儲存裝置讀取的任何中間頁。
  14. 一種裝置，該裝置包含： 一主機計算機裝置，包含一個或多個處理器； 一儲存裝置，包含一非揮發性儲存媒體；以及 一記憶體控制器裝置，操作耦合至該主機計算機裝置及該儲存裝置，該記憶體控制器裝置被配置為： 接收來自該主機計算機裝置參照一第一資料區塊的一讀取請求； 指示該儲存裝置讀取該儲存媒體的一邏輯區至一內部緩衝器； 指示該儲存裝置傳輸該邏輯區的一標頭區至該記憶體控制器裝置，該標頭區包含多個標頭，各標頭包含儲存在該邏輯區中的多個資料區塊其中之一的一識別及一長度； 判斷該標頭區以確定該第一資料區塊前的該些資料區塊的一部分的長度的一總和； 使用該總和指示該儲存裝置傳輸該第一資料區塊；以及 回傳該第一資料區塊至該主機計算機裝置。
  15. 根據申請專利範圍第14項之裝置，其中該記憶體控制器裝置被配置用以評估該標頭區，透過： 解碼該標頭區以提取該些標頭； 確定該標頭區的一末端；以及 加入該標頭區的該末端的該總和以確定對應該第一資料區塊的一偏移量。
  16. 根據申請專利範圍第14項之裝置，其中該記憶體控制器裝置被配置為在指示該儲存裝置讀取該儲存媒體的該邏輯區至該內部緩衝器之後，以及在使用該總和指示該儲存裝置傳輸該第一資料區塊之前，防止該邏輯區執行後續讀取至該內部緩衝器。
  17. 根據申請專利範圍第14項之裝置，其中該記憶體控制器裝置被配置為在回傳該第一資料區塊至該主機計算機裝置之前解碼該第一資料區塊。
  18. 根據申請專利範圍第17項之裝置，其中該記憶體控制器裝置被配置為在回傳該第一資料區塊至該主機計算機裝置之前解壓縮該第一資料區塊。
  19. 根據申請專利範圍第17項之裝置，其中該記憶體控制器裝置被配置為： 從該儲存裝置讀取該些資料區塊的有效資料區塊，不解碼或解壓縮該有效資料區塊且不讀取該些資料區塊的無效資料區塊； 產生用於該些有效資料區塊的一更新標頭區；以及 寫入該標頭區及該些有效資料區塊至該邏輯區。
  20. 根據申請專利範圍第14項之裝置，其中該儲存裝置為NAND快閃裝置。
TW104103867A 2014-02-05 2015-02-05 快閃記憶體之壓縮、讀取方法及應用其方法的裝置 TWI648622B (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US14/173,586 US9927998B2 (en) 2014-02-05 2014-02-05 Flash memory compression
US14/173,586 2014-02-05

Publications (2)

Publication Number Publication Date
TW201539187A true TW201539187A (zh) 2015-10-16
TWI648622B TWI648622B (zh) 2019-01-21

Family

ID=53754855

Family Applications (1)

Application Number Title Priority Date Filing Date
TW104103867A TWI648622B (zh) 2014-02-05 2015-02-05 快閃記憶體之壓縮、讀取方法及應用其方法的裝置

Country Status (7)

Country Link
US (1) US9927998B2 (zh)
EP (1) EP3103009B1 (zh)
JP (1) JP6316974B2 (zh)
KR (1) KR101824612B1 (zh)
CN (1) CN106537327B (zh)
TW (1) TWI648622B (zh)
WO (1) WO2015119974A1 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI682278B (zh) * 2017-10-30 2020-01-11 日商東芝記憶體股份有限公司 記憶體系統及控制方法

Families Citing this family (26)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9965191B2 (en) * 2014-10-28 2018-05-08 Samsung Electronics Co., Ltd. Electronic system with message mechanism and method of operation thereof
US9710199B2 (en) 2014-11-07 2017-07-18 International Business Machines Corporation Non-volatile memory data storage with low read amplification
US10162700B2 (en) * 2014-12-23 2018-12-25 International Business Machines Corporation Workload-adaptive data packing algorithm
US10613756B2 (en) * 2015-09-03 2020-04-07 Qualcomm Incorporated Hardware-accelerated storage compression
US20170068458A1 (en) * 2015-09-03 2017-03-09 Qualcomm Incorporated Hardware-accelerated storage compression
US9712190B2 (en) 2015-09-24 2017-07-18 International Business Machines Corporation Data packing for compression-enabled storage systems
US9870285B2 (en) 2015-11-18 2018-01-16 International Business Machines Corporation Selectively de-straddling data pages in non-volatile memory
KR102680390B1 (ko) 2016-10-12 2024-07-03 삼성전자주식회사 저장 장치 및 그것의 동작 방법
US10027984B2 (en) 2016-11-30 2018-07-17 Hewlett Packard Enterprise Development Lp Methods and systems for efficiently reading a data block from a data seglet with compressed data blocks
US10282127B2 (en) 2017-04-20 2019-05-07 Western Digital Technologies, Inc. Managing data in a storage system
US10705970B1 (en) 2017-05-12 2020-07-07 Seagate Technology Llc Enhanced address compaction
US10140215B1 (en) 2017-05-26 2018-11-27 Seagate Technology Llc Low overhead mapping for highly sequential data
US10809928B2 (en) 2017-06-02 2020-10-20 Western Digital Technologies, Inc. Efficient data deduplication leveraging sequential chunks or auxiliary databases
US10496335B2 (en) * 2017-06-30 2019-12-03 Intel Corporation Method and apparatus for performing multi-object transformations on a storage device
US10503608B2 (en) 2017-07-24 2019-12-10 Western Digital Technologies, Inc. Efficient management of reference blocks used in data deduplication
US20190065088A1 (en) * 2017-08-30 2019-02-28 Micron Technology, Inc. Random access memory power savings
JP2019053415A (ja) * 2017-09-13 2019-04-04 東芝メモリ株式会社 メモリシステム、その制御方法及びプログラム
CN110785734A (zh) * 2018-04-25 2020-02-11 深圳市大疆创新科技有限公司 数据处理方法和装置
US10635599B2 (en) 2018-07-26 2020-04-28 Sandisk Technologies Llc Memory controller assisted address mapping
GB2579399B (en) * 2018-11-30 2020-12-16 Imagination Tech Ltd Data compression and storage
US11221776B2 (en) * 2019-12-30 2022-01-11 Micron Technology, Inc. Metadata indication for a memory device
GB2603459B (en) * 2021-01-22 2023-05-10 Advanced Risc Mach Ltd Data processing systems
US11861195B2 (en) * 2021-03-15 2024-01-02 Western Digital Technologies, Inc. TLC data programming with hybrid parity
US11934706B2 (en) 2021-12-22 2024-03-19 Western Digital Technologies, Inc. Smart relocation scan optimization
CN116009790A (zh) * 2023-02-03 2023-04-25 合肥兆芯电子有限公司 有效节点管理方法、存储装置及存储器控制电路单元
KR102557557B1 (ko) 2023-04-19 2023-07-24 메티스엑스 주식회사 전자 장치 및 이를 포함하는 컴퓨팅 시스템

Family Cites Families (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5757295A (en) * 1995-12-28 1998-05-26 Philips Electronics North America Corporation Variable length decoder with enhanced throughput due to parallel processing of contiguous code words of identical type
US6243081B1 (en) 1998-07-31 2001-06-05 Hewlett-Packard Company Data structure for efficient retrieval of compressed texture data from a memory system
US7113432B2 (en) * 2000-09-14 2006-09-26 Sandisk Corporation Compressed event counting technique and application to a flash memory system
US7139864B2 (en) * 2003-12-30 2006-11-21 Sandisk Corporation Non-volatile memory and method with block management system
WO2008072452A1 (ja) * 2006-12-11 2008-06-19 Panasonic Corporation 動画像復号化装置、半導体装置、映像機器および動画像復号化方法
US8364929B2 (en) 2009-10-23 2013-01-29 Seagate Technology Llc Enabling spanning for a storage device
US8533564B2 (en) * 2009-12-23 2013-09-10 Sandisk Technologies Inc. System and method of error correction of control data at a memory device
US9582431B2 (en) 2010-03-22 2017-02-28 Seagate Technology Llc Storage address space to NVM address, span, and length mapping/converting
US8694703B2 (en) * 2010-06-09 2014-04-08 Brocade Communications Systems, Inc. Hardware-accelerated lossless data compression
US8995534B2 (en) * 2010-09-20 2015-03-31 Bevara Technologies, Llc Systems and methods for encoding and decoding
KR101636785B1 (ko) 2010-12-01 2016-07-06 엘에스아이 코포레이션 독립 실리콘 소자들을 갖는 동적 상위 레벨 리던던시 모드 관리
US8626989B2 (en) * 2011-02-02 2014-01-07 Micron Technology, Inc. Control arrangements and methods for accessing block oriented nonvolatile memory
JP2014150593A (ja) 2011-06-06 2014-08-21 Panasonic Corp 車両用電源システム
TWI467590B (zh) * 2011-07-11 2015-01-01 Phison Electronics Corp 資料處理方法、記憶體控制器及記憶體儲存裝置
JP5687639B2 (ja) 2012-02-08 2015-03-18 株式会社東芝 コントローラ、データ記憶装置及びプログラム
US20130343131A1 (en) * 2012-06-26 2013-12-26 Lsi Corporation Fast tracking for flash channels
US8898376B2 (en) 2012-06-04 2014-11-25 Fusion-Io, Inc. Apparatus, system, and method for grouping data stored on an array of solid-state storage elements
US9148172B2 (en) * 2012-06-22 2015-09-29 Micron Technology, Inc. Data compression and management
US9495288B2 (en) * 2013-01-22 2016-11-15 Seagate Technology Llc Variable-size flash translation layer
WO2014141411A1 (ja) * 2013-03-13 2014-09-18 株式会社日立製作所 ストレージシステムおよびストレージシステム制御方法
JP5978259B2 (ja) 2013-08-16 2016-08-24 エルエスアイ コーポレーション 順次読み出し最適化可変サイズフラッシュトランスレーションレイヤ
US9514057B2 (en) * 2013-12-04 2016-12-06 Sandisk Technologies Llc Storage module and method for managing logical-to-physical address mapping

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI682278B (zh) * 2017-10-30 2020-01-11 日商東芝記憶體股份有限公司 記憶體系統及控制方法

Also Published As

Publication number Publication date
EP3103009A4 (en) 2017-10-04
JP6316974B2 (ja) 2018-04-25
WO2015119974A1 (en) 2015-08-13
TWI648622B (zh) 2019-01-21
CN106537327A (zh) 2017-03-22
CN106537327B (zh) 2019-06-04
US9927998B2 (en) 2018-03-27
KR101824612B1 (ko) 2018-02-07
JP2017511521A (ja) 2017-04-20
EP3103009B1 (en) 2019-09-11
KR20170002369A (ko) 2017-01-06
US20150220277A1 (en) 2015-08-06
EP3103009A1 (en) 2016-12-14

Similar Documents

Publication Publication Date Title
TWI648622B (zh) 快閃記憶體之壓縮、讀取方法及應用其方法的裝置
KR102155191B1 (ko) 비휘발성 메모리에 대한 기록들의 관리 및 그 기록들의 영역 선택
US9875153B2 (en) Validation bits and offsets to represent logical pages split between data containers
US9514057B2 (en) Storage module and method for managing logical-to-physical address mapping
WO2016107272A1 (zh) 固态硬盘存储设备和固态硬盘存储设备的数据存取方法
US9891833B2 (en) Eliminating garbage collection in nand flash devices
CN106326140B (zh) 数据拷贝方法、直接内存访问控制器及计算机系统
JP2014142931A (ja) 記憶アドレス空間と不揮発性メモリのアドレス、範囲、および長さとの間のマッピング／変換
TW201626382A (zh) 用於快取壓縮資料之設備、系統及方法
TW201314452A (zh) 緩衝資料的系統及方法
CN107548491B (zh) 用于管理存储器的设备和方法以及存储介质
WO2016048599A1 (en) Caching technologies employing data compression
EP3196767A1 (en) Method for writing data into flash memory device, flash memory device and storage system
US20180225298A1 (en) Adaptive rate compression hash processing device
CN107135662B (zh) 一种差异数据备份方法、存储系统和差异数据备份装置
CN115756312A (zh) 数据访问系统、数据访问方法和存储介质
KR20190052366A (ko) 컨트롤러 및 컨트롤러의 동작방법
US9547550B1 (en) System and method for improved data maintenance in a flash drive
KR20190048453A (ko) 저장 장치 및 메모리 시스템
US9524236B1 (en) Systems and methods for performing memory management based on data access properties
US11698871B2 (en) Method for PRP/SGL handling for out-of-order NVME controllers
US11232024B2 (en) Predictive caching in device for media seek in playback or scrolling