NUMA-aware perfect hash algorithm

1. A method comprising:

splitting a perfect hash vector (PHVEC) into a number of perfect hash vectors, wherein the number corresponds to a number of nodes having a processing core and associated local memory;

assigning each perfect hash vector of the number of perfect hash vectors to a respective local memory of a node so that each perfect hash vector accesses only the respective local memory; and

assigning fingerprints in each perfect hash vector to a respective node using a mask function.

2. The method of claim 1 wherein the PHVEC is used in a garbage collection process in a deduplication backup system implementing non-uniform memory access (NUMA) processes.

3. The method of claim 1 wherein the fingerprints are partitioned according to the number of NUMA nodes N in the system, and wherein each fingerprint is mapped to the NUMA node in accordance with an equation node=(FP mod N).

4. The method of claim 1 wherein fingerprints are assigned to a particular node using a mapping scheme based on the last two bits of an index (00, 01, 10, 11) created by walking a walk index to create the mask that is combined with the fingerprint.

5. The method of claim 1 wherein the PHVEC is internally subdivided into many smaller vectors denoted buckets, and wherein fingerprints are uniformly hashed into these buckets.

6. The method of claim 5 wherein the PHVEC is created in a single-threaded process wherein fingerprints from an index bucket are hashed into a number of perfect hash buckets based on a stride size of the PHVEC, and wherein the index bucket is read one stride at a time and all the fingerprints are sent to the PHVEC for creation.

7. The method of claim 6 wherein the stride is calculated by first calculating a total number of perfect hash buckets by a total number of fingerprints in the index divided by each perfect hash bucket size, and then dividing the total number of index buckets by the total number of perfect hash buckets.

8. The method of claim 7 wherein the PHVEC is created in a multi-threaded process comprising subdividing the index buckets in stride size units, and wherein at least one bucket is split between two threads to form partial strides, and wherein full strides are processed using the multi-threaded execution and the partial strides are processed using single-threaded execution.

9. The method of claim 1 wherein the PHVEC is used in a perfect physical garbage collection process maintaining a perfect hash live vector in a multi-field data structure including each perfect hash vector, and wherein the PHVEC is split into four perfect hash vectors.

10. The method of claim 9 further comprising combining the bucket access and header per bucket into a single cache line to reduce the four random memory accesses to three random memory accesses.

11. The method of claim 9 further comprising:

creating the PHVEC in a single-threaded process wherein fingerprints from an index bucket are hashed into a number of perfect hash buckets based on a stride size of the PHVEC, and wherein the index bucket is read one stride at a time and all the fingerprints are sent to the PHVEC for creation; and

making the perfect hash buckets NUMA-aware, so that there can be a copy of perfect hash buckets per NUMA node.

12. The method of claim 9 further comprising implementing multi-stride cache prefetching to prefetch all four memory locations to reduce the latency of lookup.

13. A system comprising:

a first component splitting a perfect hash vector (PHVEC) into a number of perfect hash vectors, wherein the number corresponds to a number of nodes having a processing core and associated local memory;

a second component assigning each perfect hash vector of the number of perfect hash vectors to a respective local memory of a node so that each perfect hash vector accesses only the respective local memory; and

a third component assigning fingerprints in each perfect hash vector to a respective node using a mask function.

14. The system of claim 13 wherein the PHVEC is used in a garbage collection process in a deduplication backup system implementing non-uniform memory access (NUMA) processes.

15. The system of claim 14 wherein the fingerprints are partitioned according to the number of NUMA nodes N in the system, and wherein each fingerprint is mapped to the NUMA node in accordance with an equation node=(FP mod N).

16. The system of claim 13 wherein fingerprints are assigned to a particular node using a mapping scheme based on the last two bits of an index (00, 01, 10, 11) created by walking a walk index to create the mask that is combined with the fingerprint.

17. The system of claim 13 wherein the PHVEC is internally subdivided into many smaller vectors denoted buckets, and wherein fingerprints are uniformly hashed into these buckets.

18. 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 method comprising:

splitting a perfect hash vector (PHVEC) into a number of perfect hash vectors, wherein the number corresponds to a number of nodes having a processing core and associated local memory;

assigning each perfect hash vector of the number of perfect hash vectors to a respective local memory of a node so that each perfect hash vector accesses only the respective local memory; and

assigning fingerprints in each perfect hash vector to a respective node using a mask function.

19. The computer program product of claim 18 wherein the PHVEC is used in a garbage collection process in a deduplication backup system implementing non-uniform memory access (NUMA) processes.

20. The computer program product of claim 19 wherein the fingerprints are partitioned according to the number of NUMA nodes N in the system, and wherein each fingerprint is mapped to the NUMA node in accordance with an equation node=(FP mod N).