×

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

  • US 9,983,821 B2
  • Filed: 05/20/2016
  • Issued: 05/29/2018
  • Est. Priority Date: 03/29/2016
  • Status: Active Grant
First Claim
Patent Images

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 all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×