Optimized hopscotch multiple hash tables for efficient memory in-line deduplication application
First Claim
1. A method of memory deduplication, the method comprising:
- identifying a plurality of hash tables each corresponding to a hash function, and each comprising physical hash buckets, each physical hash bucket comprising ways and being configured to store data;
identifying a plurality of virtual buckets each comprising some of the physical hash buckets, and each sharing at least one of the physical hash buckets with another of the virtual buckets;
identifying each of the physical hash buckets having data stored thereon as being assigned to a single corresponding one of the virtual buckets;
hashing a data line according to a corresponding one of the hash functions to produce a hash value;
determining whether a corresponding one of the virtual buckets of a corresponding hash table has available space for a block of data according to the hash value;
sequentially moving data from the corresponding one of the virtual buckets to an adjacent one of the virtual buckets when the corresponding one of the virtual buckets does not have available space until the corresponding one of the virtual buckets has space for the block of data; and
storing the block of data in the corresponding one of the virtual buckets.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
19 Claims
-
1. A method of memory deduplication, the method comprising:
-
identifying a plurality of hash tables each corresponding to a hash function, and each comprising physical hash buckets, each physical hash bucket comprising ways and being configured to store data; identifying a plurality of virtual buckets each comprising some of the physical hash buckets, and each sharing at least one of the physical hash buckets with another of the virtual buckets; identifying each of the physical hash buckets having data stored thereon as being assigned to a single corresponding one of the virtual buckets; hashing a data line according to a corresponding one of the hash functions to produce a hash value; determining whether a corresponding one of the virtual buckets of a corresponding hash table has available space for a block of data according to the hash value; sequentially moving data from the corresponding one of the virtual buckets to an adjacent one of the virtual buckets when the corresponding one of the virtual buckets does not have available space until the corresponding one of the virtual buckets has space for the block of data; and storing the block of data in the corresponding one of the virtual buckets. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A deduplication dynamic random-access memory (DRAM) memory module for deduplicating memory by reducing duplicate blocks of data in memory, the deduplication DRAM memory module comprising:
-
a hash table memory for storing only deduplicated blocks of data, and comprising 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; 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. - View Dependent Claims (14, 15, 16, 17)
-
-
18. A deduplication DRAM memory module for reducing duplicate blocks of data in memory, the deduplication DRAM memory module comprising:
-
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 blocks of data; a processor; and memory, wherein the memory has stored thereon instructions that, when executed by the processor, causes the deduplication DRAM memory module to move a previously stored deduplicated block of data between adjacent virtual buckets of one of the hash tables, each of the virtual buckets comprising two or more of the physical hash buckets. - View Dependent Claims (19)
-
Specification