Optimized hopscotch multiple hash tables for efficient memory in-line deduplication application

• US 10,318,434 B2
• Filed: 02/26/2018
• Issued: 06/11/2019
• Est. Priority Date: 03/29/2016
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Sala, Frederic, Hu, Chaohong, Zheng, Hongzhong, Niu, Dimin, Chang, Mu-Tien
• Primary Examiner(s): Bertram, Ryan
• Application Number:
  US15/905,746
• Publication Number:
  US 20180181495A1
• Time in Patent Office: 470 Days
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 15/7821 Tightly coupled to memory, e.g. computational memory, smart memory, processor in memory
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G11C 29/74 using duplex memories, i.e. using dual copies
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method of memory deduplication includes identifying hash tables each corresponding to a hash function, and each including physical buckets, each physical bucket including ways and being configured to store data, identifying virtual buckets each including some physical buckets, and each sharing a physical bucket with another virtual bucket, identifying each of the physical buckets having data stored thereon as being assigned to a single virtual bucket, hashing a data line according to a hash function to produce a hash value, determining whether a corresponding virtual bucket has available space for a block of data according to the hash value, sequentially moving data from the corresponding virtual bucket to an adjacent virtual bucket when the corresponding virtual bucket does not have available space until the corresponding virtual bucket has space for the block of data, and storing the block of data in the corresponding virtual bucket.

Claims

1. A deduplication dynamic random-access memory (DRAM) memory module for deduplicating memory by performing deduplication on-chip and reducing duplicate blocks of data in memory to increase a logical capacity of the deduplication DRAM memory module, to reduce use of host processor resources, and to reduce a number of memory accesses to the deduplication DRAM memory module, the deduplication DRAM memory module comprising:

a hash table memory for storing only deduplicated blocks of data;

an address lookup table memory (ALUTM) for storing addresses corresponding to the deduplicated blocks of data; and

a processor for receiving read requests to enable the deduplication DRAM memory module to retrieve the blocks of data from the hash table memory and to export the blocks of data, and for receiving write requests to enable the deduplication DRAM memory module to store the blocks of data in the hash table memory.

2. The deduplication DRAM memory module of claim 1, wherein the hash table memory is stored on a volatile memory, and comprises a three-dimensional array of hash tables stored therein, each of the hash tables comprising physical hash buckets, each physical hash bucket comprising ways and being configured to store the deduplicated blocks of data.

3. The deduplication DRAM memory module of claim 2, wherein each of the hash tables further comprises a plurality of virtual buckets each comprising two or more of the physical hash buckets.

4. The deduplication DRAM memory module of claim 3, wherein the deduplication DRAM memory module is configured to move the deduplicated blocks of data between adjacent ones of the virtual buckets within a corresponding one of the hash tables.

5. The deduplication DRAM memory module of claim 2, wherein the deduplication DRAM memory module is able to perform data deduplication without externally supplied commands.

6. The deduplication DRAM memory module of claim 2, wherein the deduplication DRAM memory module further comprises a buffer memory for storing data when the hash table memory is full.