Method and apparatus for enabling larger memory capacity than physical memory size

• US 10,678,704 B2
• Filed: 03/31/2017
• Issued: 06/09/2020
• Est. Priority Date: 03/29/2016
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jiang, Dongyan, Lin, Changhui, Malladi, Krishna, Gim, Jongmin, Zheng, Hongzhong
• Primary Examiner(s): Krofcheck, Michael
• Application Number:
  US15/476,757
• Publication Number:
  US 20170286313A1
• Time in Patent Office: 1,166 Days
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 2212/60 Details of cache memory
• CPC Class Codes: G06F 2212/68 Details of translation look-aside buffer [TLB]
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method of retrieving data stored in a memory associated with a dedupe module is provided. The method includes: identifying a logical address of the data; identifying a physical line ID of the data in accordance with the logical address by looking up at least a portion of the logical address in a translation table; locating a respective physical line, the respective physical line corresponding to the PLID; and retrieving the data from the respective physical line, the retrieving including copying a respective hash cylinder to the read cache, the respective hash cylinder including: a respective hash bucket, the respective hash bucket including the respective physical line; and a respective reference counter bucket, the respective reference counter bucket including a respective reference counter associated with the respective physical line.

Claims

1. A method of retrieving data stored in a memory associated with a dedupe module, the method comprising:

identifying a logical address of the data;

identifying a physical line ID (PLID) of the data in accordance with the logical address by looking up at least a portion of the logical address in a translation table, wherein the PLID comprises a first identifier indicating whether the data is stored in a hash table or in an overflow memory region;

determining that the data is stored in the hash table or the overflow memory region using the first identifier;

locating a physical line corresponding to the PLID; and

retrieving the data from the physical line, the retrieving comprising copying a hash cylinder to a read cache, the hash cylinder comprising;

a hash bucket comprising the respective physical line; and

a reference counter bucket comprising a reference counter associated with the physical line.

2. The method of claim 1,

wherein the PLID is generated utilizing a first hash function applied to the data, and

wherein the PLID further comprises an address pointing to a location in the hash table.

3. The method of claim 2, wherein the PLID further comprises:

a second identifier indicating a row in which the data is stored; and

a third identifier indicating a column in which the data is stored.

4. The method of claim 1,

wherein the reference counter bucket is part of a reference counter table,

wherein the hash table and reference counter table are part of a combined data structure,

wherein the combined data structure further comprises a signature table comprising a plurality of signature buckets, each signature bucket comprising a plurality of signatures, and

wherein the hash cylinder further comprises a respective signature bucket of the plurality of signature buckets, the respective signature bucket comprising a signature associated with the physical line.

5. The method of claim 4,

wherein the PLID is generated utilizing a first hash function applied to the data,

wherein the PLID comprises an address pointing to a location in the hash table, and

wherein the plurality of signatures are generated utilizing a second hash function smaller than the first hash function.

6. The method of claim 1, wherein the reference counter tracks a number of dedupes for corresponding data stored in the hash table.

7. A method of storing data in memory associated with a dedupe engine, the method comprising:

identifying the data to be stored;

determining a first hash value corresponding to a physical line where the data should be stored in a hash table in the memory utilizing a first hash function;

storing the data at a location in the hash table corresponding to the first hash value when the physical line is available and a location corresponding to an overflow memory region when the physical line is not available;

setting a physical line ID (PLID) of the data according to the location, wherein the PLID comprises a first identifier indicating whether the data is stored in the hash table or in the overflow memory region;

determining a second hash value also corresponding to where the data should be stored utilizing a second hash function smaller than the first hash function;

storing the first hash value in a translation table in the memory; and

storing the second hash value in a signature table in the memory.

8. The method of claim 7, further comprising incrementing a reference counter, which corresponds to the data, in a reference counter table.

9. The method of claim 7, wherein the memory comprises:

the hash table storing a plurality of data;

the translation table storing a plurality of PLIDs generated utilizing the first hash function;

the signature table storing a plurality of signatures generated utilizing the second hash function;

a reference counter table storing a plurality of reference counters, each reference counter tracking a number of dedupes for corresponding data stored in the hash table; and

the overflow memory region.

10. The method of claim 9, wherein each of the PLIDs further comprise:

a second identifier indicating a row in which the data is stored; and

a third identifier indicating a column in which the data is stored.

11. The method of claim 9, wherein the hash table, the signature table, and the reference counter table are integrated into a combined data structure, and

wherein the combined data structure comprises a plurality of hash cylinders, each hash cylinder comprising:

a hash bucket comprising a plurality of physical lines;

a signature bucket comprising respective signatures corresponding to the plurality of physical lines; and

a reference counter bucket comprising respective reference counters corresponding to the plurality of physical lines.

12. The method of claim 11,

wherein the storing the data at a location in the hash table corresponding to the first hash value comprises storing the data in the hash bucket corresponding to the first hash value, and

wherein the storing the second hash value in the signature table comprises storing the second hash value in the signature bucket corresponding to the hash bucket where the data is stored.

13. A dedupe module comprising:

a read cache;

a dedupe engine to receive a data retrieval request from a host system; and

memory, the memory comprising;

a translation table; and

a combined data structure comprising;

a hash table comprising a plurality of hash buckets, each hash bucket comprising a plurality of physical lines, each physical line storing data;

a reference counter table comprising a plurality of reference counter buckets, each reference counter bucket comprising a plurality of reference counters; and

a plurality of hash cylinders, each hash cylinder comprising one of the hash buckets and one of the reference counter buckets,

wherein the data retrieval request causes the dedupe engine to;

identify a logical address of the data;

identify a physical line ID (PLID) of the data in accordance with the logical address by looking up at least a portion of the logical address in the translation table, wherein the PLID comprises a first identifier indicating whether the data is stored in the hash table or in an overflow memory region;

determining that the data is stored in the hash table or overflow memory region using the first identifier;

locate a respective physical line of the plurality of physical lines, the respective physical line corresponding to the PLID; and

retrieve the data from the respective physical line in the hash table or overflow memory region, the retrieving of the data comprising copying a respective hash cylinder of the plurality of hash cylinders to the read cache, the respective hash cylinder comprising;

 

a respective hash bucket of the plurality of hash buckets, the respective hash bucket comprising the respective physical line; and

 

a respective reference counter bucket of the plurality of reference counter buckets, the respective reference counter bucket comprising a respective reference counter associated with the respective physical line.

14. The dedupe module of claim 13, wherein the data retrieval request further causes the dedupe engine to determine, based on the PLID, that the data is stored in the hash table.

15. The dedupe module of claim 13,

wherein the PLID is generated utilizing a first hash function applied to the data, and

wherein the PLID comprises an address pointing to a location in the hash table.

16. The dedupe module of claim 15, wherein the PLID further comprises:

a second identifier indicating a row in which the data is stored; and

a third identifier indicating a column in which the data is stored.

17. The dedupe module of claim 13,

wherein the combined data structure further comprises a signature table comprising a plurality of signature buckets, each signature bucket comprising a plurality of signatures, and

wherein the respective hash cylinder further comprises a respective signature bucket of the plurality of signature buckets, the respective signature bucket comprising a respective signature associated with the respective physical line.

18. The dedupe module of claim 17,

wherein the PLID is generated utilizing a first hash function applied to the data,

wherein the PLID comprises an address pointing to a location in the hash table, and

wherein the plurality of signatures are generated utilizing a second hash function smaller than the first hash function.

19. The dedupe module of claim 13, wherein each reference counter tracks a number of dedupes for corresponding data stored in the hash table.

20. A dedupe module comprising:

a host interface;

a transfer manager to receive data transfer requests from a host system via the host interface; and

a plurality of partitions, each partition comprising;

a dedupe engine to receive partition data requests from the transfer manager and a data retrieval request from a host system;

a plurality of memory controllers;

a memory manager between the dedupe engine and the memory controller; and

a plurality of memory modules, each memory module being coupled to one of the memory controllers,

wherein the data retrieval request causes the dedupe engine to;

identify a logical address of the data in the memory modules;

identify a physical line ID (PLID) of the data in accordance with the logical address by looking up at least a portion of the logical address in a translation table, wherein the PLID comprises a first identifier indicating whether the data is stored in a hash table or in an overflow memory region;

locate a physical line; and

retrieve the data from a physical line in the hash table or overflow memory region corresponding to the PLID.

21. A dedupe module comprising:

a read cache;

memory, the memory comprising;

a translation table; and

a hash table comprising a plurality of hash buckets, each hash bucket comprising a plurality of physical lines, each physical line storing data; and

a reference counter table comprising a plurality of reference counter buckets, each reference counter bucket comprising a plurality of reference counters; and

a dedupe engine to identify V virtual buckets for a first hash bucket of the plurality of hash buckets, the virtual buckets being others of the plurality of hash buckets that are nearby the first hash bucket, the virtual buckets to store some of the first hash bucket'"'"'s data when the first hash bucket is full, V being an integer that is dynamically set based on how full the first hash bucket'"'"'s virtual buckets are.