[go: up one dir, main page]

TW201805811A - 記憶體模組及其控制可程式化去重複率的方法 - Google Patents

記憶體模組及其控制可程式化去重複率的方法 Download PDF

Info

Publication number
TW201805811A
TW201805811A TW106120759A TW106120759A TW201805811A TW 201805811 A TW201805811 A TW 201805811A TW 106120759 A TW106120759 A TW 106120759A TW 106120759 A TW106120759 A TW 106120759A TW 201805811 A TW201805811 A TW 201805811A
Authority
TW
Taiwan
Prior art keywords
deduplication
memory
memory module
rate
hash
Prior art date
Application number
TW106120759A
Other languages
English (en)
Other versions
TWI710902B (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 TW201805811A publication Critical patent/TW201805811A/zh
Application granted granted Critical
Publication of TWI710902B publication Critical patent/TWI710902B/zh

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/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/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0604—Improving or facilitating administration, e.g. storage management
    • 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
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
    • G06F12/0811—Multiuser, multiprocessor or multiprocessing cache systems with multilevel cache hierarchies
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0864—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches using pseudo-associative means, e.g. set-associative or hashing
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0866—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches for peripheral storage systems, e.g. disk cache
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0866—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches for peripheral storage systems, e.g. disk cache
    • G06F12/0873—Mapping of cache memory to specific storage devices or parts thereof
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/10—Address translation
    • G06F12/1009—Address translation using page tables, e.g. page table structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
    • G06F13/38—Information transfer, e.g. on bus
    • G06F13/42—Bus transfer protocol, e.g. handshake; Synchronisation
    • G06F13/4282—Bus transfer protocol, e.g. handshake; Synchronisation on a serial bus, e.g. I2C bus, SPI bus
    • 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/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0614—Improving the reliability of storage systems
    • G06F3/0619—Improving the reliability of storage systems in relation to data integrity, e.g. data losses, bit errors
    • 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/065—Replication mechanisms
    • 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
    • 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
    • G06F2213/00—Indexing scheme relating to interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
    • G06F2213/0026—PCI express

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

Abstract

一種具有包括程式化暫存器、去重複率控制邏輯以及去重複引擎的邏輯的記憶體模組。程式化暫存器儲存記憶體模組的最大去重複率。控制邏輯用以根據最大去重複率控制記憶體模組的去重複率。去重複率由可藉由主機電腦來程式化。

Description

記憶體系統之控制可程式化重複資料刪除率的系統和方法
本揭露是有關於一種記憶體系統，且特別是有關於一種用於記憶體系統之控制可程式化去重複率的系統和方法。
在記憶體系統領域中，去重複（deduplication）指的是藉由消除冗餘資料以達成減少儲存量的技術。在諸如固態硬碟（solid-state drive；SSD）及硬碟（hard disk drive；HDD）等儲存媒體中，僅會一筆資料實際保留其唯一單例（unique instance）。冗餘資料則由所述資料的唯一單例所對應的指標（pointer）來取代。
用於去重複化記憶體（deduplicated memory）的線內記憶體去重複策略（In-line memory deduplication schemes）可提供容量上的優勢，同時能較非去重複化記憶體更減少每單位位元成本（cost-per-bit）。傳統的記憶體去重複策略採用以中央處理器（central processing unit；CPU）為中心的方法，其中去重複引擎與主機電腦的中央處理器及/或記憶體控制器（memory controller；MC）作整合。這些記憶體去重複策略常使用簡易多路雜湊陣列（simple multiple-way hash array）以實施去重複演算法（deduplication algorithm）。隨著雜湊陣列的填入，資料可能被放置到非去重複化溢位區（non-deduplicated overflow region）中，因而降低了去重複化的程度。另外，擁有高去重複率亦可望能減輕去重複化系統中記憶體元件的消耗。
根據一實施例，一種記憶體模組包括邏輯，其包括程式化暫存器、去重複率控制邏輯以及去重複引擎。程式化暫存器儲存記憶體模組的最大去重複率。去重複率控制邏輯用以根據最大去重複率來控制記憶體模組的去重複率。去重複率由可藉由主機電腦來程式化。
根據另一實施例，一種方法包括：於記憶體模組中實施邏輯，該邏輯包括程式化暫存器、去重複率控制邏輯以及去重複引擎；將該記憶體模組的最大去重複率儲存於該程式化暫存器中；藉由主機電腦程式化去重複率；以及根據該最大去重複率控制該記憶體模組的該去重複率。
以下將參照附圖對上述及其他優選特徵，包括各種實施的新穎細節和事件組合，特別作出說明並於申請專利範圍中指出。應理解，本文中所述特定系統及特定方法僅為例示性的呈現而非作為限制。本領域技術人員應可理解，在不脫離本揭露範疇下，本文中所述原理及特徵可為各種實施例以及眾多實施例所採用。
可單獨地利用本文中揭露的各個特徵及教示或與其他特徵及教示結合，藉以提供記憶體系統之控制可程式化去重複率的系統和方法。參照隨附圖式，多個代表性實例將單獨地並以組合形式利用這些額外特徵及教示作進一步詳細描述。此詳細描述僅旨在提供本領域技術人員對實踐本教示各態樣方面的進一步細節，而非旨在限定申請專利範圍的範疇。因此，詳細描述中揭露特徵之組合以最廣泛意義來說並非實踐所述教示所必需，而僅為教學以說明本教示中特定代表性實例。
在以下描述中，特定命名法僅出於解釋的目的而闡述，藉以提供對本揭露的透徹理解。然而，顯而易見的是，本領域技術人員毋須這些具體細節即可實踐本揭露的教示。
一些本文中詳細描述的部分是在對電腦記憶體內資料位元在操作中演算法以及符號表達方面的呈現。這些演算用描述及表達為資料處理領域技術人員所用，以將其工作內容有效地傳達給該領域其他技術人員。此處，大體上來說，演算法是一種自我一致序列（self-consistent sequence），其設想為引導至期望結果所需的步驟。這些步驟為需要對實體數量進行實體操縱的步驟。通常，雖非必要，這些數量是以可被儲存、傳送、組合、比較並以其他方式操縱的電信號或磁信號形式來呈現。已經多次證實，原則上，將信號稱為位元、數值、元素、符號、字元、術語、數字或其類似者有利於普及使用。
然而，應謹記的是，這些術語及類似術語皆需與適當的實體數量相關聯，且僅用於方便標記所述數量。應瞭解，貫穿全文，除非顯然另有特地陳述，否則以下論述中，利用諸如「處理」、「計算」、「運算」、「判定」、「顯示」或其類似者等術語的論述是指電腦系統或類似的電子計算裝置的動作及處理程序，其可將電腦系統的暫存器及記憶體內以實體（電子）數量表示的資料操縱且變換成電腦系統記憶體或暫存器或其他此類資訊儲存裝置、傳輸裝置或顯示裝置內以類似實體數量所表示的其他資料。
本文中呈現的演算法非與任何特定電腦或其他設備有本質上的相關。各種一般用途的系統、電腦伺服器或個人電腦可與符合文中教示的程式並用，或構建較專業化設備亦證實可能方便執行所需的方法步驟。以下描述將呈現用於這些系統所需的結構。當可瞭解的是，文中所述之本揭露的教示可以各種程式化語言來實施。
此外，代表性實例及附屬申請專利範圍的各種特徵可以並非確切及非明確列舉的方式來組合以便提供本發明教示的額外適用實施例。另外值得特別注意的是，實體群組的所有數值範圍或表示揭露了各個可能的中間值或中間實體，其目的在作為原始揭露的內容以及限制所主張的標的物。另外值得特別注意的是，諸圖中所示組件的尺寸及形狀經設計以幫助理解如何實踐本發明教示，但並不意欲限制實例中所示的尺寸及形狀。
圖1繪示習知技術中一種去重複系統的方塊圖。關於細密化（fine-grained）記憶體內去重複的實施細節，可參考約翰·彼得·史蒂文生（John Peter Stevenson）所著作的博士論文中之討論（“Fine-Grain In-Memory Deduplication for Large-Scale Workloads,” Stanford University, December 2013)。
去重複系統100包括主機電腦160以及多個DDR記憶體模組1500 ～150n-1 。主機電腦160具有：具有多核心1100 ～110n-1 的CPU、包括資料快取（L1D）112及指令快取（L1I）113的1級快取（L1）111、2級快取（L2）114、直譯緩衝器(direct translation buffer；DTB）110、去重複化快取（deduplicated cache；DDC）120以及記憶體控制器130。去重複系統100可實施在包括具多核心CPU的系統中。
DDC 120代表著去重複化記憶體的一種快取版本。DDC 120擺與一般最後級快取（last level cache；LLC）相同的介面，但可明確地快取轉譯線段（translation line）、資料線段以及引用計數（reference count）。DDC 120可減少對DDR記憶體模組1500 ～150n-1 進行記憶體存取的次數。當最後級快取（LLC）所快取的特定資料以及寫入記憶體模組的數值已經過時，讀取請求可由最近一次執行過寫入的CPU核心其所屬的L1或L2快取來提供。
圖2繪示圖1的去重複系統中所用範例雜湊表。雜湊表200包括：包括有m 個雜湊桶（hash buckets）的雜湊陣列。每一個雜湊桶包含n 個途徑（ways）或槽（slots）。此處的用語「途徑」及「槽」可互換使用。雜湊函數h 可產生(logm )-位元雜湊以將實體線段ID （physical line ID；PLID）索引（index）至雜湊桶中。要將線段C 插入到雜湊陣列中，先計算h (C )的值，並檢查雜湊表中h (C)的列T 看看是否有途徑可供線段C 的插入。雜湊表200的總容量為m 個雜湊桶乘以n 個資料線段，如圖2所示。
簽章（signature）線段及引用計數線段可各自佔據雜湊桶的一個途徑。整體來看，m 個雜湊桶的簽章線段及引用計數線段可各自佔據雜湊陣列的一整行（column）。簽章線段及引用計數線段可能小到能將幾個數量裝進每一個線段。舉例而言，雜湊陣列包括64條途徑，而簽章則為8位元（bits）以便裝進8位元的線段中。在這種情況下，雜湊陣列的線段為64位元組（bytes；64x8 bits）。
在另一個例子中，簽章為X位元，引用計數為Y位元，且雜湊陣列的實體線段為64位元組。如果途徑的數量為n ，每n個途徑雜湊桶的簽章計數需要總數為n / (64x8/X)的實體線段。類似地，每n-way雜湊桶的引用計數需要總數為n / (64x8/Y)的實體線段。總計起來，雜湊陣列會具有n (1 + 1/(64x8/X) + 1/(64x8/Y))條途徑。只要簽章線段及引用計數線段都能夠被裝進雜湊桶的一個線段，這些途徑會對應至雜湊表中的多個行。
在習知的去重複記憶體中，中央處理器無法直接存取實體記憶體。取而代之的是，可由主機電腦的記憶體控制器來管理實體記憶體（在本範例中，為具有64-bytes記憶體線段的陣列）。每一個實體線段可藉由其實體線段ID（PLID）來辨識。PLID分成三個區域：轉譯陣列（translation array）、雜湊陣列（hash array）以及溢出（overflow）。PLID可使用雜湊函數h 索引至雜湊陣列中。舉例而言，PLID可實施如下： PLID = overflow flag（溢出旗標） | hash bits（雜湊位元） | way bits （途徑位元） 雜湊位元使雜湊桶能索引至雜湊陣列中。途徑位元被賦予途徑索引（way index）。若指向的資料在雜湊表200中，則溢出旗標設為0。若溢出旗標設為1，則PLID中的剩餘位元會用於索引至溢出陣列（overflow array）。
PLID的寬度是由雜湊表200的大小所決定。對圖2中的雜湊表200而言，雜湊位元及途徑位元需要log2 m +log2 n 個位元。加上用於溢出旗標的額外位元，則PLID的寬度計算如下： |PLID| = 1 +log2 m +log2 n
本揭露提出用於提供可程式化去重複率控制機制給去重複記憶體系統的系統和方法。去重複率控制機制採用了以記憶體為中心（memory-centric）的作法而非用於傳統去重複記憶體系統的以CPU為中心的作法，藉由可配置的去重複演算法的使用以最大化去重複記憶體系統的記憶體容量。去重複率控制機制可以替各種去重複記憶體產品（例如，庫存管理單元（stock keeping units；SKUs））挑選最大去重複率並根據經程式化去重複率配置去重複記憶體產品。取決於為去重複記憶體系統所擬定的目標應用程式（例如，資料庫），相同的產品可經程式化而有不同的去重複率。
圖3是根據一實施例所繪示的一種範例去重複記憶體系統的結構。去重複記憶體系統300包括主機電腦360及去重複記憶體310。去重複記憶體310包括系統單晶片（system-on-chip；SOC）邏輯320，其包括去重複率暫存器321、去重複率控制邏輯322以及整合式去重複引擎325。去重複率暫存器321可藉由主機電腦（未繪示）程式化，且可儲存去重複記憶體310的最大去重複率。去重複率暫存器321可用任何程式化方式來程式化，所述程式化方式包括（但不限於此）永久性硬體程式化（例如設置熔絲）以及對電子抹除式可複寫唯讀記憶體（electrically erasable programmable read-only memory；EEPROM）進行讀寫及寫入。去重複率暫存器321可根據系統管理需求在去重複記憶體310的生產期間，或者在後期製作（post-production）期間進行程式化，例如在系統開機時間。
去重複率控制邏輯322可根據儲存於去重複率暫存器321中經程式化的最大去重複率控制位址查詢表（address lookup table；LUT）的表格大小以限制記憶體模組310的虛擬容量。去重複率控制邏輯322可將經程式化的最大去重複率及/或去重複記憶體310的虛擬容量提供至外部的請求者以及內部的去重複引擎325。在一實施例中，最大去重複率是將去重複記憶體310的實體容量乘以去重複率來計算。去重複引擎325可基於去重複記憶體310的最大虛擬容量管理對去重複記憶體310的讀寫請求。
根據一實施例，去重複記憶體310包括雜湊表記憶體350。雜湊表記憶體350包括位址查詢表記憶體（address LUT memory；ALUTM）351、雜湊表記憶體（hash table memory；HTM）352以及緩衝記憶體（buffer memory；BM）353。位址查詢表記憶體（ALUTM）351儲存裝置位址與查詢位址之間的映射資訊。雜湊表記憶體（HTM）352儲存雜湊表中的數值。緩衝記憶體（BM）353是一個保留的記憶體區域，其作為SOC記憶體緩衝/快取以及虛擬密度超量（virtual density over-provision）管理（HTM overflow）。
圖4是根據一實施例所繪示的一種範例去重複記憶體系統。去重複記憶體系統400可提供以記憶體為中心的資料去重複，藉由使用可配置的去重複演算法以最大化記憶體容量。在本實例中，去重複記憶體系統400包括主機電腦410、DRAM雙線記憶體模組（DRAM DIMM）420以及去重複記憶體模組430。主機電腦410包括處理器413，其用以運行操作系統411（例如，Linux）以及使用核心（kernel）模組412的使用者應用程式。另外，主機電腦410包括一或多個記憶體及介面控制器（統稱為記憶體/介面控制器414）以提供多個記憶體介接至DRAM DIMM 420及去重複記憶體模組430的支援。本實例繪示有一個DRAM DIMM 420及一個去重複記憶體模組430。然而，應可理解，在不偏離本揭露範疇下，去重複記憶體系統400可包括任何數量的DRAM DIMM及/或去重複記憶體模組。
DRAM DIMM 420及去重複記憶體模組430各自經由一特定介面而耦接至主機電腦410。舉例而言，DRAM DIMM 420是經由雙倍資料速率（DDR）（例如，DDR4）記憶體介面而耦接至主機電腦410。去重複記憶體模組430可經由DDR4記憶體介面或者諸如快速週邊組件互連（peripheral component interconnect express；PCIe）介面、高速非揮發性記憶體（non-volatile memory express；NVMe）以及跨網路非揮發性記憶體（NVM-over-fabrics；NVMf）等任何其他非記憶體介面而耦接至主機電腦410。在一實施例中，去重複記憶體模組430可為非揮發性雙線記憶體模組NVDIMM，其包括一或多個非揮發記憶體裝置（例如，快閃記憶體）或者至少一非揮發記憶體裝置、以及一或多個DRAM裝置。
根據一實施例，主機電腦410可經由所述特定介面（例如，DDR4、PCIe）而具有對去重複記憶體模組430的進行快取線路存取（cache line access）的能力。SOC可提供去重複記憶體模組430的超量記憶體容量（即，虛擬記憶體容量）至主機電腦。由於去重複化資料儲存在去重複記憶體模組430中，去重複記憶體模組430的虛擬記憶體容量可大於其實體記憶體容量。去重複記憶體模組430的SOC 431可提供主機電腦410如資料去重複（data deduplication）、可尋址資料（addressable data）、安全性、記憶體內處理（processing-in-memory；PIM）及光柵化處理（rasterization processing；RAS）等智能功能。另外，SOC 431可提供虛擬密度管理與有效資料置放（virtual density management and efficient data placement）以及DRAM介面（例如，DDR4）。去重複記憶體模組430可具有包括有，但不限於，DIMM、2.5吋硬碟、全高半長（full height, half length；FHHL）、半高半長（half height, half length；HHHL）以及全高全長（full height, full length；FHFL）等各種形式因素。
圖5是根據一實施例所繪示的一種範例雜湊表。雜湊表記憶體（HTM）500包括3D資料，其包括m 個雜湊桶、n 個雜湊函數以及用於各個雜湊函數的d 個途徑。虛擬桶（virtual bucket；VB）容許資料置放在鄰近位置的雜湊桶中，例如，具有VB高度h 的雜湊桶內。針對每一個雜湊桶，都有一個關聯的雜湊函數h(x)雜湊表，用以產生log2(m)-位元雜湊來索引至雜湊桶中。舉例而言，若雜湊表具有8個雜湊桶，則雜湊表的雜湊函數會產生3-位元雜湊。也就是說，雜湊函數h(x)使相對大量的輸入資料（例如，欲儲存到記憶體的輸入資料檔案）能被輸入雜湊函數h(x)，而實質上不同的較小量輸出資料（例如，雜湊值）則由雜湊函數h(x)產生並輸出以儲存到雜湊表中。這樣一來，即便不同的資料組可能偶爾被雜湊成相同的雜湊值，雜湊函數h(x)也能實現壓縮。
圖6是根據一實施例所繪示的一種用於範例去重複寫入處理的流程圖。去重複記憶體的去重複引擎可判斷是否要採用非適應性去重複演算法或適應性去重複演算法（601）。針對非適應性去重複演算法，主機電腦上運行的軟體可定義去重複演算法。針對適應性去重複演算法，去重複記憶體的去重複引擎可基於各種參數（例如，應用程式歷史（application history）及選擇規則）來定義去重複演算法。
當非適應性去重複演算法被選定時，載入到主機操作系統的核心中用於去重複記憶體的驅動程式設定去重複線段大小、雜湊表的數量、雜湊桶的數量、途徑的數量以及虛擬桶高度（611）。SOC建立如圖3所示的雜湊表記憶體、位址查詢表記憶體以及緩衝記憶體的區域（612）。驅動程式選擇預處理演算法（613）並選擇雜湊演算法（614）。去重複記憶體的SOC建立去重複寫入演算法（615）。
當適應性去重複演算法被選定時，去重複記憶體的SOC選擇線上的適應性去重複演算法（622）。在選擇適應性去重複演算法時，SOC參考各種參數，例如應用程式態樣歷史池（application pattern history pool）、去重複演算法池及去重複選擇規則（621）。SOC可應用不同的去重複寫入演算法631A～631X。SOC可在開機時間為不同的記憶體區域選擇不同的演算法。所選擇的演算法可在下次開機時間更換。
圖7是根據一實施例所繪示的一種用於去重複記憶體系統寫入處理的範例流程圖。寫入請求經由特定介面（例如，DDR4及PCIe）抵達去重複記憶體（711）。舉例而言，寫入請求用以資料0x3456789A寫入裝置位址0x2。實施於去重複記憶體的SOC中的去重複引擎雜湊寫入請求所欲寫入的資料。在此實例中，經雜湊資料具有查詢(LU)位址0x5以及金鑰0x3。去重複引擎將經雜湊的LU位址0x5以及金鑰0x3與儲存於雜湊表記憶體722中的金鑰與數值進行比對（712）。若有在雜湊表記憶體722中發現符合的數值，去重複引擎會將符合項目（matching entry）的頻率計數（frequency count）從1增加至2。頻率計數是一種參考計數，用以指示位址查詢轉譯陣列中有多少PLID指向特定線段。去重複引擎取得原始LU位址（例如，0x5）並更新位址查詢表記憶體723中的LU位址（713）。去重複引擎更新雜湊表記憶體722中原始LU位址（例如，0x5）的頻率計數（714）。若未在雜湊表記憶體722中發現符合的數值，去重複引擎將一筆具有頻率值1的新項目增加到雜湊表記憶體722以及位址查詢表記憶體723兩者之中。去重複引擎向主機記憶體控制器報告寫入請求完成（751）。
圖8是根據一實施例所繪示的一種用於去重複記憶體系統讀取處理的範例流程圖。讀取請求經由特定介面（例如，DDR4及PCIe）抵達去重複記憶體（811）。舉例而言，讀取請求對向裝置位址0x2。裝置位址指的是欲讀取的資料的位址，而LU位址指的是資料儲存在雜湊表記憶體823中的實際位置。去重複引擎從讀取的位址查詢表記憶體822取得LU位址（812）。去重複引擎從所讀取的雜湊表記憶體823取得對應LU位址0x4的數值（0x12345678）（813）。去重複引擎傳送所讀取的資料到主機記憶體控制器以完成讀取請求（851）。
根據一實施例，一種記憶體模組包括邏輯，其包括程式化暫存器、去重複率控制邏輯以及去重複引擎。程式化暫存器儲存記憶體模組的最大去重複率。去重複率控制邏輯用以根據最大去重複率來控制記憶體模組的去重複率。去重複率由可藉由主機電腦來程式化。
去重複率控制邏輯可進一步用以將去重複率經由主機介面傳達至主機電腦。
記憶體模組的去重複率可於生產記憶體模組時程式化。
記憶體模組的去重複率可於系統開機時間程式化。
記憶體模組可更包括雜湊表記憶體。雜湊表記憶體可包括位址查詢表（LUT）、雜湊表以及緩衝記憶體。
去重複率控制邏輯可用以根據儲存於去重複率暫存器中經程式化的去重複率來控制位址查詢表的表格大小以限制去重複記憶體模組的虛擬容量。
主機介面可為雙倍資料速率（DDR）介面。
主機介面可為快速週邊組件互連（PCIe）介面。
根據另一實施例，一種方法包括：於記憶體模組中實施邏輯，該邏輯包括程式化暫存器、去重複率控制邏輯以及去重複引擎；將該記憶體模組的最大去重複率儲存於該程式化暫存器中；藉由主機電腦程式化去重複率；以及根據該最大去重複率控制該記憶體模組的該去重複率。
所述方法可更包括：將記憶體模組的去重複率經由主機介面傳達至主機電腦。
記憶體模組的去重複率可於生產記憶體模組時程式化。
記憶體模組的去重複率可於系統開機時間程式化。
所述方法可更包括：提供雜湊表記憶體，其包括位址查詢表（LUT）、雜湊表以及緩衝記憶體。
所述方法可更包括：根據儲存於該程式化暫存器中經程式化的所述去重複率來控制該位址查詢表的表格大小以限制該記憶體模組的虛擬容量。
主機介面可為雙倍資料速率（DDR）介面。
主機介面可為快速週邊組件互連（PCIe）介面。
上述範例實施例已說明如上，並藉由各種實施例來說明如何實施並提供可程式化去重複率控制機制給去重複記憶體系統的系統和方法。任何所屬技術領域中具有通常知識者，在不脫離本揭露的精神和範圍內，當可作些許的更動與潤飾，故本揭露的保護範圍當視後附的申請專利範圍所界定者為準。
100、200‧‧‧去重複系統
110‧‧‧直譯緩衝器
1100～110n-1‧‧‧核心
111‧‧‧1級快取
112‧‧‧資料快取
113‧‧‧指令快取
114‧‧‧2級快取
120‧‧‧去重複化快取
130‧‧‧記憶體控制器
1500～150n-1‧‧‧DDR記憶體模組
160、360、410‧‧‧主機電腦
300、400‧‧‧去重複記憶體系統
310‧‧‧去重複記憶體
320‧‧‧系統單晶片（system-on-chip；SOC）邏輯
321‧‧‧去重複率暫存器
322‧‧‧去重複率控制邏輯
325‧‧‧去重複引擎
350、352、500、552、722、823‧‧‧雜湊表記憶體
351、723、822‧‧‧位址查詢表記憶體
353、553‧‧‧緩衝記憶體
411‧‧‧操作系統
412‧‧‧核心模組
413‧‧‧處理器
414‧‧‧記憶體/介面控制器
420‧‧‧DRAM雙線記憶體模組
430‧‧‧去重複記憶體模組
431‧‧‧系統單晶片
601～622、631A~631X、711～714、751、811～813、851‧‧‧步驟
作為本說明書一部份而包含的附圖繪示有目前優選的實施例，並且與上文給出的一般說明及下文給出的詳細說明一同用作解釋並教示本文中所述原理。
圖1繪示習知技術中一種細密化（fine-grained）去重複系統的方塊圖。 圖2繪示圖1的去重複系統中所用範例雜湊表。 圖3是根據一實施例所繪示的一種範例去重複記憶體系統的結構。 圖4是根據一實施例所繪示的一種範例去重複記憶體系統。 圖5是根據一實施例所繪示的一種範例去重複系統中所用雜湊表。 圖6是根據一實施例所繪示的一種用於範例去重複寫入處理的流程圖。 圖7是根據一實施例所繪示的一種用於去重複記憶體系統寫入處理的範例流程圖。 圖8是根據一實施例所繪示的一種用於去重複記憶體系統讀取處理的範例流程圖。
貫穿諸圖，出於說明性目的，諸圖未必按比例繪製且具有類似結構或功能的元件通常由相同的參考編號表示。諸圖僅旨在方便描述本文中所述各種實施例。諸圖未描述本文中所揭露教示的每一態樣且不限定申請專利範圍的範疇。

Claims (16)

  1. 一種記憶體模組，包括： 邏輯，其包括程式化暫存器、去重複率控制邏輯以及去重複引擎；以及 主機介面，對向主機電腦的 其中所述程式化暫存器儲存該記憶體模組的最大去重複率， 其中所述去重複率控制邏輯用以根據所述最大去重複率控制所述記憶體模組的去重複率，以及 其中所述去重複率由可藉由所述主機電腦程式化。
  2. 如申請專利範圍第1項所述的記憶體模組，其中所述去重複率控制邏輯更用以將所述去重複率經由所述主機介面傳達至所述主機電腦。
  3. 如申請專利範圍第1項所述的記憶體模組，其中所述記憶體模組的所述去重複率於生產所述記憶體模組時程式化。
  4. 如申請專利範圍第1項所述的記憶體模組，其中所述記憶體模組的所述去重複率於系統開機時間程式化。
  5. 如申請專利範圍第1項所述的記憶體模組，更包括雜湊表記憶體，其中所述雜湊表記憶體包括位址查詢表（LUT）、雜湊表以及緩衝記憶體。
  6. 如申請專利範圍第5項所述的記憶體模組，其中所述去重複率控制邏輯用以根據儲存於所述程式化暫存器中經程式化的所述去重複率控制所述位址查詢表的表格大小以限制所述記憶體模組的虛擬容量。
  7. 如申請專利範圍第1項所述的記憶體模組，其中所述主機介面為雙倍資料速率（DDR）介面。
  8. 如申請專利範圍第1項所述的記憶體模組，其中所述主機介面為快速週邊組件互連（PCIe）介面。
  9. 一種方法，包括： 於記憶體模組中實施邏輯，所述邏輯包括程式化暫存器、去重複率控制邏輯以及去重複引擎； 將所述記憶體模組的最大去重複率儲存於所述程式化暫存器中； 藉由主機電腦程式化去重複率；以及 根據所述最大去重複率來控制所述記憶體模組的所述去重複率。
  10. 如申請專利範圍第9項所述的方法，更包括將所述記憶體模組的所述去重複率經由主機介面傳達至所述主機電腦。
  11. 如申請專利範圍第9項所述的方法，其中所述記憶體模組的所述去重複率於生產所述記憶體模組時程式化。
  12. 如申請專利範圍第9項所述的方法，其中所述記憶體模組的所述去重複率於系統開機時間程式化。
  13. 如申請專利範圍第9項所述的方法，更包括提供雜湊表記憶體，其包括位址查詢表（LUT）、雜湊表以及緩衝記憶體。
  14. 如申請專利範圍第13項所述的方法，更包括根據儲存於所述程式化暫存器中經程式化的所述去重複率控制所述位址查詢表的表格大小以限制所述記憶體模組的虛擬容量。
  15. 如申請專利範圍第11項所述的方法，其中所述主機介面為雙倍資料速率（DDR）介面。
  16. 如申請專利範圍第11項所述的方法，其中所述主機介面為雙倍資料速率（DDR）介面。
TW106120759A 2016-08-03 2017-06-21 記憶體模組及其控制可程式化去重複率的方法 TWI710902B (zh)

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
US201662370655P 2016-08-03 2016-08-03
US62/370,655 2016-08-03
US15/285,437 US10162554B2 (en) 2016-08-03 2016-10-04 System and method for controlling a programmable deduplication ratio for a memory system
US15/285,437 2016-10-04

Publications (2)

Publication Number Publication Date
TW201805811A true TW201805811A (zh) 2018-02-16
TWI710902B TWI710902B (zh) 2020-11-21

Family

ID=61069415

Family Applications (1)

Application Number Title Priority Date Filing Date
TW106120759A TWI710902B (zh) 2016-08-03 2017-06-21 記憶體模組及其控制可程式化去重複率的方法

Country Status (5)

Country Link
US (1) US10162554B2 (zh)
JP (1) JP6757299B2 (zh)
KR (1) KR102216116B1 (zh)
CN (1) CN107688436B (zh)
TW (1) TWI710902B (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI688859B (zh) * 2018-12-19 2020-03-21 財團法人工業技術研究院 記憶體控制器與記憶體頁面管理方法

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP3750991A4 (en) 2018-02-09 2021-12-01 Amano Enzyme Inc. RANDOM INTERESTERIFICATION LIPASE
KR102144185B1 (ko) * 2018-10-24 2020-08-12 전자부품연구원 상용 메모리 버스를 이용하는 프로세싱 인 메모리 장치
CN112313630A (zh) * 2018-11-16 2021-02-02 英特尔公司 用于增加有效存储器容量的动态存储器去重
KR102689645B1 (ko) 2019-01-29 2024-07-30 삼성전자주식회사 해시 솔루션을 위한 반도체 메모리 장치 및 이의 구동방법
US11436165B2 (en) * 2019-05-01 2022-09-06 Samsung Electronics Co., Ltd. High bandwidth memory system
US20210286523A1 (en) * 2020-03-10 2021-09-16 EMC IP Holding Company LLC Deduplication analysis
US12045173B2 (en) * 2020-04-18 2024-07-23 International Business Machines Corporation Stale data recovery using virtual storage metadata
CN114157611B (zh) * 2021-12-15 2023-12-08 苏州盛科通信股份有限公司 一种报文去重方法、装置及存储介质

Family Cites Families (32)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6438560B1 (en) 1999-09-16 2002-08-20 International Business Machines Corporation Reuse of immutable objects during object creation
KR100816155B1 (ko) * 2006-12-28 2008-03-21 주식회사 하이닉스반도체 불휘발성 메모리 장치 및 불휘발성 메모리 장치의 멀티레벨 셀 프로그램 방법
US8504791B2 (en) 2007-01-26 2013-08-06 Hicamp Systems, Inc. Hierarchical immutable content-addressable memory coprocessor
CN101652758B (zh) 2007-01-26 2013-10-16 海坎普系统股份有限公司 分级式不可变内容可寻址存储器处理器
JP5026213B2 (ja) * 2007-09-28 2012-09-12 株式会社日立製作所 ストレージ装置及びデータ重複排除方法
US8825617B2 (en) 2008-03-14 2014-09-02 International Business Machines Corporation Limiting deduplication based on predetermined criteria
CN103080910B (zh) 2010-09-09 2016-06-01 日本电气株式会社 存储系统
US8533407B2 (en) 2010-12-01 2013-09-10 International Business Machines Corporation Capacity management in deduplication storage systems
KR20120082218A (ko) * 2011-01-13 2012-07-23 (주)인디링스 파티션 정보를 기초로 호스트의 요청에 대한 처리 기법을 적응적으로 결정하는 스토리지 장치 및 상기 스토리지 장치의 동작 방법
US9122639B2 (en) 2011-01-25 2015-09-01 Sepaton, Inc. Detection and deduplication of backup sets exhibiting poor locality
US9223511B2 (en) * 2011-04-08 2015-12-29 Micron Technology, Inc. Data deduplication
CN103620563B (zh) * 2011-04-26 2015-04-29 Lsi公司 用于非易失性存储器的可变超量配置
US9501421B1 (en) 2011-07-05 2016-11-22 Intel Corporation Memory sharing and page deduplication using indirect lines
US8521705B2 (en) 2011-07-11 2013-08-27 Dell Products L.P. Accelerated deduplication
KR20130081526A (ko) * 2012-01-09 2013-07-17 삼성전자주식회사 저장 장치, 그것을 포함하는 전자 장치, 및 그것의 데이터 관리 방법들
US9026503B2 (en) 2012-02-29 2015-05-05 Netapp, Inc. Fragmentation control for performing deduplication operations
US20130275699A1 (en) 2012-03-23 2013-10-17 Hicamp Systems, Inc. Special memory access path with segment-offset addressing
US9075710B2 (en) 2012-04-17 2015-07-07 SanDisk Technologies, Inc. Non-volatile key-value store
US8930612B2 (en) 2012-05-31 2015-01-06 Seagate Technology Llc Background deduplication of data sets in a memory
JP5842768B2 (ja) 2012-08-22 2016-01-13 富士通株式会社 重複除去装置、重複除去方法及び重複除去プログラム
US9158468B2 (en) * 2013-01-02 2015-10-13 International Business Machines Corporation High read block clustering at deduplication layer
US10275397B2 (en) 2013-02-22 2019-04-30 Veritas Technologies Llc Deduplication storage system with efficient reference updating and space reclamation
KR101505263B1 (ko) * 2013-03-07 2015-03-24 포항공과대학교 산학협력단 데이터 중복 제거 방법 및 장치
KR20140114515A (ko) 2013-03-15 2014-09-29 삼성전자주식회사 불휘발성 메모리 장치 및 그것의 중복 데이터 제거 방법
US10133502B2 (en) 2013-07-15 2018-11-20 International Business Machines Corporation Compatibility and inclusion of similarity element resolutions
US10073853B2 (en) 2013-07-17 2018-09-11 International Business Machines Corporation Adaptive similarity search resolution in a data deduplication system
US9898410B2 (en) 2013-09-10 2018-02-20 Intel Corporation Hybrid main memory using a fine-grain level of remapping
US9465735B2 (en) * 2013-10-03 2016-10-11 Qualcomm Incorporated System and method for uniform interleaving of data across a multiple-channel memory architecture with asymmetric storage capacity
US9384205B1 (en) * 2013-12-18 2016-07-05 Veritas Technologies Llc Auto adaptive deduplication to cloud based storage
US9792063B2 (en) 2014-01-15 2017-10-17 Intel Corporation Deduplication-based data security
US9966152B2 (en) * 2016-03-31 2018-05-08 Samsung Electronics Co., Ltd. Dedupe DRAM system algorithm architecture
US10101935B2 (en) * 2016-06-03 2018-10-16 Samsung Electronics Co., Ltd. System and method for providing expandable and contractible memory overprovisioning

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
TWI688859B (zh) * 2018-12-19 2020-03-21 財團法人工業技術研究院 記憶體控制器與記憶體頁面管理方法
US11372779B2 (en) 2018-12-19 2022-06-28 Industrial Technology Research Institute Memory controller and memory page management method

Also Published As

Publication number Publication date
CN107688436B (zh) 2022-04-01
US20180039443A1 (en) 2018-02-08
CN107688436A (zh) 2018-02-13
KR20180015565A (ko) 2018-02-13
KR102216116B1 (ko) 2021-02-16
US10162554B2 (en) 2018-12-25
TWI710902B (zh) 2020-11-21
JP2018022487A (ja) 2018-02-08
JP6757299B2 (ja) 2020-09-16

Similar Documents

Publication Publication Date Title
TWI710902B (zh) 記憶體模組及其控制可程式化去重複率的方法
US10540100B2 (en) Mapping-based wear leveling for non-volatile memory
US10866797B2 (en) Data storage device and method for reducing firmware update time and data processing system including the device
US12141480B2 (en) Storage device and operating method thereof including a plurality of zones and operating method thereof
CN106354745B (zh) 用于提供计算机装置的接口的方法和计算机装置
KR102149817B1 (ko) 메모리 어드레싱
US9811456B2 (en) Reliable wear-leveling for non-volatile memory and method therefor
US10061710B2 (en) Storage device
US9645924B2 (en) Garbage collection scaling
TWI683217B (zh) 使用去重複dram系統演算法架構的去重複記憶體模組及其方法
TW201335937A (zh) 用於複合式非揮發性儲存裝置之資料遷移
US20170357462A1 (en) Method and apparatus for improving performance of sequential logging in a storage device
CN103890856A (zh) 支持内存储数据结构的可移位存储器
US10861580B2 (en) Memory system for controlling nonvolatile memory
US12260122B2 (en) Storage controller providing status information of zone region, method of operating the same, and method of operating electronic device having the same
CN119003383A (zh) 用于逻辑到物理表的异常列表压缩
CN114746848B (zh) 用于存储装置的高速缓存架构
US20250298528A1 (en) Read operations for mixed data
US9880930B2 (en) Method for operating controller and method for operating device including the same
US11126624B2 (en) Trie search engine
US10133785B2 (en) Data storage device including internal hardware filter and data processing system
US11068175B2 (en) Technology to manage capacity loss in storage drives
KR20220066402A (ko) 자가-적응형 웨어 레벨링 방법 및 알고리즘