Method and apparatus for implementing a fully dynamic lock-free hash table

• US 7,287,131 B1
• Filed: 09/29/2003
• Issued: 10/23/2007
• Est. Priority Date: 03/21/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Martin, Paul A., Luchangco, Victor, Maessen, Jan-Willem
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): RUTZ, JARED IAN
• Application Number:
  US10/674,942
• Time in Patent Office: 1,485 Days
• Field of Search: 711/154, 707/101, 707/103
• US Class Current: 711/154
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

One embodiment of the present invention provides a system that implements a hash table that is fully dynamic and lock-free. During a lookup in the hash table the system first uses a hash key to lookup a bucket pointer in a bucket array. Next, the system follows the bucket pointer to a data node within a linked list that contains all of the data nodes in the hash table, wherein the linked list contains only data nodes and at most a constant number of dummy nodes. The system then searches from the data node through the linked list to locate a node that matches the hash key, if one exists.

Claims

1. A method for using a hash table that is fully dynamic and lock-free, comprising:

performing a lookup into the hash table, wherein the lookup involves,

using a hash key to lookup a bucket pointer in a bucket array,

following the bucket pointer to a data node within a linked list containing all of the data nodes in the hash table, and

searching from the data node through the linked list to locate a node that matches the hash key if one exists;

wherein the linked list contains only data nodes and at most a constant number of dummy nodes; and

when the average number of data nodes in each bucket exceeds a maximum value;

increasing the number of buckets in the bucket array to form a larger bucket array, and

using more bits from the hash key to perform lookups in the larger bucket array,

wherein the data nodes are stored in the linked list in bit-inverted hash key order, and

wherein increasing the number of buckets in the bucket array involves copying the existing bucket array into the top half of the larger bucket array through a single pointer operation.

2. The method of claim 1, wherein the data node pointed to by the bucket pointer precedes the nodes in the bucket.

3. The method of claim 2, wherein deleting the data node from the linked list involves using garbage collection or a solution to the repeat offender problem to reclaim the data node if possible.

4. The method of claim 2, wherein if the average number of data nodes in each bucket falls below a minimum value, the method further comprises:

reducing the number of buckets in the bucket array to form a smaller bucket array; and

using fewer bits from the hash key to perform lookups in the smaller bucket array.

5. The method of claim 1, wherein deleting the data node from the linked list involves:

using an atomic operation to mark the data node as dead; and

atomically updating the next pointer of the predecessor of the data node to point around the data node to the successor of the data node in the linked list.

6. The method of claim 5, wherein deleting the data node from the linked list additionally involves redirecting the next pointer of the data node to become a back pointer that points to the predecessor of the data node.

7. The method of claim 6, wherein if a search through a chain of nodes from the back pointer does not lead to a live node, the method further comprises:

obtaining a parent bucket pointer;

searching through the linked list from a node pointed to by the parent bucket pointer to locate a starting node for the bucket pointer; and

updating the bucket pointer to point to the starting node.

8. The method of claim 1, further comprising generating the hash key by performing a pre-hashing operation to achieve a uniform distribution of hash keys over possible hash key values.

9. The method of claim 1, wherein buckets in the larger bucket array are initialized on-the-fly as they are referenced.

10. The method of claim 1, wherein initializing a bucket pointer involves:

obtaining a parent bucket pointer for the bucket pointer;

searching through the linked list from a node pointed to by the parent bucket pointer to locate a starting node for the bucket pointer; and

updating the bucket pointer to point to the starting node.

11. The method of claim 1, wherein if there exists an old hash table, initializing a bucket pointer involves looking for a corresponding entry in the old hash table first, and if this fails:

obtaining a parent bucket pointer for the bucket pointer;

searching through the linked list from a node pointed to by the parent bucket pointer to locate a starting node for the bucket pointer; and

updating the bucket pointer to point to the starting node.

12. The method of claim 1,

wherein the data nodes are stored in the linked list in hash key order;

and

wherein increasing the number of buckets in the bucket array involves interleaving the bucket array into the larger bucket array.

13. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for using a hash table that is fully dynamic and lock-free, wherein the computer-readable storage medium does not include computer instruction signals embodied in a transmission medium, and wherein the method comprising:

performing a lookup into the hash table, wherein the lookup involves,

using a hash key to lookup a bucket pointer in a bucket array,

following the bucket pointer to a data node within a linked list containing all of the data nodes in the hash table, and

searching from the data node through the linked list to locate a node that matches the hash key if one exists;

wherein the linked list contains only data nodes and at most a constant number of dummy nodes; and

when the average number of data nodes in each bucket exceeds a maximum value;

increasing the number of buckets in the bucket array to form a larger bucket array, and

using more bits from the hash key to perform lookups in the larger bucket array,

wherein the data nodes are stored in the linked list in bit-inverted hash key order, and

wherein increasing the number of buckets in the bucket array involves copying the existing bucket array into the top half of the larger bucket array through a single pointer operation.

14. The computer-readable storage medium of claim 13, wherein the data node pointed to by the bucket pointer precedes the nodes in the bucket.

15. The computer-readable storage medium of claim 14, wherein deleting the data node from the linked list involves using garbage collection or a solution to the repeat offender problem to reclaim the data node if possible.

16. The computer-readable storage medium of claim 13, wherein deleting the data node from the linked list involves:

using an atomic operation to mark the data node as dead; and

atomically updating the next pointer of the predecessor of the data node to point around the data node to the successor of the data node in the linked list.

17. The computer-readable storage medium of claim 16, wherein deleting the data node from the linked list additionally involves redirecting the next pointer of the data node to become a back pointer that points to the predecessor of the data node.

18. The computer-readable storage medium of claim 17, wherein if a search through a chain of nodes from the back pointer does not lead to a live node, the method further comprises:

obtaining a parent bucket pointer;

searching through the linked list from a node pointed to by the parent bucket pointer to locate a starting node for the bucket pointer; and

updating the bucket pointer to point to the starting node.

19. The computer-readable storage medium of claim 13, wherein the method further comprises generating the hash key by performing a pre-hashing operation to achieve a uniform distribution of hash keys over possible hash key values.

20. The computer-readable storage medium of claim 13, wherein buckets in the larger bucket array are initialized on-the-fly as they are referenced.

21. The computer-readable storage medium of claim 13, wherein initializing a bucket pointer involves:

obtaining a parent bucket pointer for the bucket pointer;

searching through the linked list from a node pointed to by the parent bucket pointer to locate a starting node for the bucket pointer; and

updating the bucket pointer to point to the starting node.

22. The computer-readable storage medium of claim 13, wherein if there exists an old hash table, initializing a bucket pointer involves looking for a corresponding entry in the old hash table first, and if this fails:

obtaining a parent bucket pointer for the bucket pointer;

searching through the linked list from a node pointed to by the parent bucket pointer to locate a starting node for the bucket pointer; and

updating the bucket pointer to point to the starting node.

23. The computer-readable storage medium of claim 13,

wherein the data nodes are stored in the linked list in hash key order;

and

wherein increasing the number of buckets in the bucket array involves interleaving the bucket array into the larger bucket array.

24. The computer-readable storage medium of claim 13, wherein if the average number of data nodes in each bucket falls below a minimum value, the method further comprises:

reducing the number of buckets in the bucket array to form a smaller bucket array; and

using less bits from the hash key to perform lookups in the smaller bucket array.

25. An apparatus that implements a hash table that is fully dynamic and lock-free, comprising:

a lookup mechanism, wherein the lookup mechanism is configured to,

use a hash key to lookup a bucket pointer in a bucket array,

follow the bucket pointer to a data node within a linked list containing all of the data nodes in the hash table, and to

search from the data node through the linked list to locate a node that matches the hash key if one exists;

wherein the linked list contains only data nodes and at most a constant number of dummy nodes; and

a bucket array expansion mechanism, wherein when the average number of data nodes in each bucket exceeds a maximum value, the bucket array expansion mechanism is configured to;

increase the number of buckets in the bucket array to form a larger bucket array, and to

use additional bits from the hash key to perform lookups in the larger bucket array,

wherein the data nodes are stored in the linked list in bit-inverted hash key order, and

wherein the bucket array expansion mechanism is configured to copy the existing bucket array into the top half of the larger bucket array through a single pointer operation.

26. The apparatus of claim 25, wherein the data node pointed to by the bucket pointer precedes the nodes in the bucket.

27. The apparatus of claim 26, wherein the node deletion mechanism is additionally configured to use garbage collection or a solution to the repeat offender problem to reclaim the data node if possible.

28. The apparatus of claim 26, further comprising a bucket array contraction mechanism, wherein if the average number of data nodes in each bucket falls below a minimum value, the bucket array contraction mechanism is configured to:

reduce the number of buckets in the bucket array to form a smaller bucket array; and

to

use less bits from the hash key to perform lookups in the smaller bucket array.

29. The apparatus of claim 25, further comprising a node deletion mechanism configured to:

use an atomic operation to mark the data node as dead; and

to

atomically update the next pointer of the predecessor of the data node to point around the data node to the successor of the data node in the linked list.

30. The apparatus of claim 29, wherein the node deletion mechanism is additionally configured to redirect the next pointer of the data node to become a back pointer that points to the predecessor of the data node.

31. The apparatus of claim 30, further comprising a bucket pointer updating mechanism, wherein if a search through a chain of nodes from the back pointer does not lead to a live node, the bucket pointer updating mechanism is configured to:

obtain a parent bucket pointer;

search through the linked list from a node pointed to by the parent bucket pointer to locate a starting node for the bucket pointer; and

to

update the bucket pointer to point to the starting node.

32. The apparatus of claim 25, further comprising a pre-hashing mechanism configured to generate the hash key by performing a pre-hashing operation to achieve a uniform distribution of hash keys over possible hash key values.

33. The apparatus of claim 25, further comprising a bucket initialization mechanism configured to initialize buckets in the larger bucket array on-the-fly as they are referenced.

34. The apparatus of claim 25, wherein the bucket initialization mechanism is configured to:

obtain a parent bucket pointer for the bucket pointer;

search through the linked list from a node pointed to by the parent bucket pointer to locate a starting node for the bucket pointer; and

to

update the bucket pointer to point to the starting node.

35. The apparatus of claim 25, wherein if there exists an old hash table, the bucket initialization mechanism is configured to look for a corresponding entry in the old hash table first, and if this fails to:

obtain a parent bucket pointer for the bucket pointer;

search through the linked list from a node pointed to by the parent bucket pointer to locate a starting node for the bucket pointer; and

to

update the bucket pointer to point to the starting node.

36. The apparatus of claim 25,

wherein the data nodes are stored in the linked list in hash key order;

and

wherein the bucket array expansion mechanism is configured to interleave the bucket array into the larger bucket array.