Virtual bucket multiple hash tables for efficient memory in-line deduplication application

• US 10,496,543 B2
• Filed: 05/23/2016
• Issued: 12/03/2019
• Est. Priority Date: 03/31/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
• Assistant Examiner(s): Kwong, Edmund H
• Application Number:
  US15/162,517
• Publication Number:
  US 20170286005A1
• Time in Patent Office: 1,289 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement

Abstract

A method of deduplicating memory in a memory module includes identifying a hash table array including 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 a plurality of virtual buckets each including some of the physical buckets, and each sharing at least one of the physical buckets with another of the virtual buckets, hashing a block of data according to a corresponding one of the hash functions to produce a hash value, determining whether an intended physical bucket has available space for the block of data according to the hash value, and determining whether a near-location physical bucket has available space for the block of data when the intended physical bucket does not have available space, the near-location physical bucket being in a same one of the virtual buckets as the intended physical bucket.

Claims

1. A method of deduplicating memory in a memory module having increased capacity, improved lifespan, and improved latency due to the method, the method comprising:

identifying a hash table array comprising a plurality of hash tables each corresponding to a hash function, and each comprising physical buckets, each physical bucket comprising ways, and each being configured to store data;

identifying a plurality of virtual buckets each comprising some of the physical buckets, and each sharing at least one of the physical buckets with another of the virtual buckets;

hashing a block of data according to a corresponding one of the hash functions to produce a hash value;

determining whether an intended physical bucket of the physical buckets has available space for the block of data according to the hash value;

determining whether one of near-location physical buckets of the physical buckets has available space for the block of data when the intended physical bucket does not have available space, the near-location physical buckets being in a same one of the virtual buckets as the intended physical bucket; and

storing the block of data in the intended physical bucket when the intended physical bucket has available space.

2. The method of claim 1, further comprising storing the block of data in the one of the near-location physical buckets when one of the near-location physical buckets has available space and when the intended physical bucket does not have available space.

3. The method of claim 1, further comprising hashing the block of data according to another one of the hash functions corresponding to another one of the hash tables of the hash table array when all of the physical buckets of the hash table associated with the corresponding one of the hash functions are full;

and

storing the block of data in the another one of the hash tables.

4. The method of claim 1, further comprising storing the block of data in a buffer memory when all of the physical buckets of all of the hash tables of the hash table array are full.

5. The method of claim 1, further comprising associating each of the virtual buckets with a corresponding group of the physical buckets using a physical line ID (PLID) comprising a virtual bucket index.

6. The method of claim 1, further comprising:

receiving a write request corresponding to the block of data;

discarding the write request when the block of data is stored in one of the virtual buckets having the intended physical bucket therein; and

updating a reference count line of the hash table.

7. A dynamic random-access memory (DRAM) memory module for deduplicating memory, and having increased capacity, improved lifespan, and improved latency, the DRAM memory module comprising a DRAM comprising multiple hash tables in a hash table array, each of the hash tables comprising:

physical buckets each comprising ways for storing data; and

a plurality of virtual buckets each comprising some of the physical buckets,

wherein the DRAM memory module is configured to;

interface with a memory interface to retrieve the stored data, and to deliver the retrieved data to the memory interface;

receive a write request from the memory interface to store a block of data in the hash table array;

perform a hash function on the block of data to determine an intended physical bucket of the physical buckets;

determine whether the block of data is previously stored in either the intended physical bucket, or in one of near-location physical buckets of the physical buckets located in any of the virtual buckets to which the intended physical bucket belongs; and

store the block of data in either the intended physical bucket or the one of the near-location physical buckets when the block of data is not previously stored therein, and when either the intended physical bucket or the one of the near-location physical buckets has available space.

8. The DRAM memory module of claim 7, wherein the DRAM further comprises a buffer memory for storing data when all of near-location physical buckets and the intended physical bucket are full.

9. The DRAM memory module of claim 7, wherein the DRAM memory module is further configured to:

determine whether the near-location physical buckets and the intended physical bucket are full; and

perform another hash function on the block of data to determine another intended physical bucket in a different one of the hash tables than the intended physical bucket when all of the near-location physical buckets and the intended physical bucket are full.

10. The DRAM memory module of claim 9, wherein the DRAM further comprises a buffer memory for storing data when all of the physical buckets of all of the hash tables of the hash table array are full.

11. A method of deduplicating memory in a memory module having increased capacity, improved lifespan, and improved latency due to the method, the method comprising:

receiving a write request corresponding to a block of data to store the block of data in a hash table array comprising a plurality of hash tables, each hash table comprising physical buckets, each physical bucket comprising ways, and each physical bucket being associated with a virtual bucket comprising some of the physical buckets;

hashing the block of data according to a corresponding hash function to produce a hash value;

determining an intended physical bucket of the physical buckets based on the hash value;

determining whether an identical block of data is stored in the intended physical bucket;

determining whether the identical block of data is stored in one of other physical buckets in a same one of the virtual buckets as the intended physical bucket when the identical block of data is not stored in the intended physical bucket; and

storing the block of data in the intended physical bucket when the intended physical bucket has available space.

12. The method of claim 11, the method further comprising:

determining whether the intended physical bucket is full when the identical block of data is not stored in any other physical buckets in the same one of the virtual buckets as the intended physical bucket.

13. The method of claim 12, the method further comprising:

determining whether all of the other physical buckets in the same one of the virtual buckets as the intended physical bucket are full when the intended physical bucket is full; and

storing the block of data in one of the physical buckets when one of the other physical buckets is not full.

14. The method of claim 13, the method further comprising storing the block of data in a buffer memory when all of the other physical buckets in the same one of the virtual buckets as the intended physical bucket.

15. The method of claim 13, the method further comprising:

determining whether all of the other physical buckets in a same one of the hash tables as the intended physical bucket are full when all of the other physical buckets are full;

determining whether another one of the hash tables of the hash table array has available space when all of the physical buckets in the same one of the hash tables are full;

hashing the block of data according to another hash function corresponding to the another one of the hash tables when the another one of the hash tables has available space; and

storing the block of data in the another one of the hash tables.

16. The method of claim 15, the method further comprising storing the block of data in a buffer memory when no other one of the hash tables of the hash table array has available space.

17. The method of claim 11, the method further comprising:

storing the block of data in one of the physical buckets of one of the virtual buckets including the intended physical bucket when the identical block of data is not stored therein;

generating a physical line ID (PLID) corresponding to the one of the physical buckets in which the block of data is stored; and

storing the PLID in an address lookup table.