Memory efficient perfect hashing for large records
Embodiments for a memory efficient perfect hashing for large records. A container ID set is divided into multiple fixed range sizes. These ranges are then mapped into perfect hash buckets until each bucket is filled to uniformly distribute the container IDs across different perfect hash buckets so that the number of CIDs in every perfect hash bucket is the same or nearly the same. Individual perfect hash functions are created for each perfect hash bucket. With container IDs as keys, the process maps n keys to n positions to reduce any extra memory overhead. The perfect hash function is implemented using a compress, hash, displace (CHD) algorithm using two levels of hash functions. The level 1 hash functions divides the keys into multiple internal buckets with a defined average number of keys per bucket. The CHD algorithm iteratively tries different level 2 hash variables to achieve collision-free mapping.
1. A computer-implemented memory efficient perfect hashing method for use with large records in a deduplication backup system, comprising:
dividing a container identifier (CID) set into multiple fixed range sizes of a plurality of ranges;
mapping the ranges into a first set of perfect hash buckets until each bucket is filled to uniformly distribute the container identifiers (CIDs) across a second set of perfect hash buckets so that the number of CIDs in each perfect hash bucket is the same;
creating an individual perfect hash function for each perfect hash bucket, and implemented using a compress, hash, displace (CHD) algorithm using two levels of hash functions;
mapping, for CIDs as keys, n keys to n positions to reduce extra memory usage;
dividing, using level 1 hash functions, the keys into multiple internal buckets with a defined average number of keys per bucket;
iteratively trying different level 2 hash variables until collision-free mapping is achieved, wherein the level 2 hash is expressed as: ((h1+h2)*d0+d1)% phf_range, and further wherein the phf_range comprises a function that maps m positions for n keys based on a number of storage bits and an average number of keys per bucket, and a load factor;
computing a range index of the CIDs;
using the range index value to derive the index of the mapping table to lookup, wherein the range index value in the mapping table comprises the perfect hash bucket index;
using the perfect hash bucket index to obtain an offset of the perfect hash function and the bitmap for the bucket;
reading a function at the offset specified in the bucket descriptor and applying the function to the key to get a position from the perfect hash function;
counting the number of bits set until that position; and
returning the count of the number of set bits to the caller as an index of the value array.
2. The method of claim 1 wherein 10-bits are used to store a (d0+d1*phf_range) value and the average number of keys per bucket is 7 so that the phf_range comprises the value m=1.43n and the load factor is 0.7.
3. The method of claim 2 further comprising:
storing the final variable values achieving the collision-free mapping in a bucket descriptor; and
storing the d0 and d1 values are stored in compressed form as the value: d0+d1*phf_range.
4. The method of claim 1 wherein the caller maintains the value as an array, and wherein the method further comprises providing the index in the array associated with the key.
5. The method of claim 4 wherein the position is relative to the keys present in the current bucket, the method further comprising adding the bit offset, which specifies the start-bit for the bucket to get an actual position in the bitmap.
6. The method of claim 5 wherein the range index is computed as Range_Index=(CID−min_CID)/Range_Size.
7. A system implementing memory efficient perfect hashing method for use with large records in a deduplication backup system, comprising:
a first processing component dividing a container identifier (CID) set into multiple fixed range sizes of a plurality of ranges, and mapping the ranges into a first set of perfect hash buckets until each bucket is filled to uniformly distribute the container identifiers (CIDs) across a second set of perfect hash buckets so that the number of CIDs in each perfect hash bucket is the same;
a second processing component creating an individual perfect hash function for each perfect hash bucket and implemented using a compress, hash, displace (CHD) algorithm using two levels of hash functions, and mapping, for container IDs as keys, n keys to n positions to reduce extra memory usage;
a third processing component dividing, using level 1 hash functions, the keys into multiple internal buckets with a defined average number of keys per bucket, and iteratively trying different level 2 hash variables until collision-free mapping is achieved, wherein the level 2 hash is expressed as: ((h1+h2)*d0+d1)% phf_range, and further wherein the phf_range comprises a function that maps m positions for n keys based on a number of storage bits and an average number of keys per bucket, and a load factor;
a fourth processing component looking up a specific container identifier by:
computing a range index of the CIDs;
using the range index value to derive the index of the mapping table to lookup, wherein the range index value in the mapping table comprises the perfect hash bucket index;
using the perfect hash bucket index to obtain an offset of the perfect hash function and the bitmap for the bucket;
reading a function at the offset specified in the bucket descriptor and applying the function to the key to get a position from the perfect hash function;
counting the number of bits set until that position; and
returning the count of the number of set bits to the caller as an index of the value array.
8. The system of claim 7 wherein 10-bits are used to store a (d0+d1*phf_range) value and the average number of keys per bucket is 7 so that the phf_range comprises the value m=1.43n and the load factor is 0.7.
9. The system of claim 8 further comprising a fifth processing component storing the final variable values achieving the collision-free mapping in a bucket descriptor; and storing the d0 and d1 values are stored in compressed form as the value: d0+d1*phf_range.
10. The system of claim 7 wherein the caller maintains the value as an array, and wherein the method further comprises providing the index in the array associated with the key.
11. The system of claim 10 wherein the position is relative to the keys present in the current bucket, the method further comprising adding the bit offset, which specifies the start-bit for the bucket to get an actual position in the bitmap.
12. The system of claim 11 wherein the range index is computed as Range_Index=(CID−min_CID)/Range_Size.
13. A computer program product, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein, the computer-readable program code adapted to be executed by one or more processors to implement a memory efficient perfect hashing method for use with large records in a deduplication backup system, by:
dividing a container identifier (CID) set into multiple fixed range sizes of a plurality of ranges;
mapping the ranges into a first set of perfect hash buckets until each bucket is filled to uniformly distribute the container identifiers (CIDs) across a second set of perfect hash buckets so that the number of CIDs in each perfect hash bucket is the same;
creating an individual perfect hash function for each perfect hash bucket, and implemented using a compress, hash, displace (CHD) algorithm using two levels of hash functions;
mapping, for CIDs as keys, n keys to n positions to reduce extra memory usage; and
dividing, using level 1 hash functions, the keys into multiple internal buckets with a defined average number of keys per bucket;
iteratively trying different level 2 hash variables until collision-free mapping is achieved, wherein the level 2 hash is expressed as: ((h1+h2)*d0+d1)% phf_range, and wherein the phf_range comprises a function that maps m positions for n keys based on a number of storage bits and an average number of keys per bucket, and a load factor;
computing a range index of the CIDs;
using the range index value to derive the index of the mapping table to lookup, wherein the range index value in the mapping table comprises the perfect hash bucket index;
using the perfect hash bucket index to obtain an offset of the perfect hash function and the bitmap for the bucket;
reading a function at the offset specified in the bucket descriptor and applying the function to the key to get a position from the perfect hash function;
counting the number of bits set until that position; and
returning the count of the number of set bits to the caller as an index of the value array.
14. The computer program product of claim 13 wherein 10-bits are used to store a (d0+d1*phf_range) value and the average number of keys per bucket is 7 so that the phf_range comprises the value m=1.43n and the load factor is 0.7.