Method and apparatus for enabling larger memory capacity than physical memory size
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
21 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
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.
-
Specification