Resizable cache sensitive hash table

• US 20030204698A1
• Filed: 04/23/2003
• Published: 10/30/2003
• Est. Priority Date: 04/29/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Huras, Matthew A., Sachedina, Aamer, Romanufa, Keriley K.
• Granted Patent: US 7,085,911 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

A hash table for a collection of data items includes a set of hash buckets, each hash bucket being associated with a subset of the collection of data items, and a set of properties entries in each of the hash buckets. Each properties entry includes a pointer to an associated data item in the subset associated with the bucket and a set of representative values identifying the associated data item. A hash table can also include bucket groups defining a second level hash table to permit resizing of the hash table.

Claims

1. A method for providing a hash table for a collection of data items, the method comprising:

(a) providing a set of hash buckets in the hash table, each hash bucket being associated with a subset of the collection of data items; and

(b) providing a set of properties entries in each of the hash buckets, wherein each properties entry includes a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.

2. The method of claim 1 further comprising defining the hash buckets to be storable in alignment with cache line boundaries in a specified data cache.

3. The method of claim 1 further comprising maintaining the set of properties entries in each hash bucket in a linked list.

4. The method of claim 3 further comprising maintaining a set of unused entries in each hash bucket in a linked list.

5. The method of claim 2 further comprising maintaining the set of properties entries in each hash bucket in a linked list.

6. The method of claim 1 wherein said hash table includes a set of bucket groups, each bucket group including:

a latch for the bucket group;

a set of inline hash buckets; and

a group header comprising a pointer definable to point to an array of overflow hash buckets.

7. The method of claim 6 further comprising defining each bucket group to be storable in alignment with cache line boundaries in a specified data cache.

8. The method of claim 6 further comprising carrying out a resizing of the hash table including:

obtaining the latch for a selected bucket group in exclusive mode;

allocating a memory location for an array of overflow buckets;

updating the overflow pointer in the group header for the selected bucket group to point to the memory location; and

redistributing buckets in the inline hash buckets and the array of overflow buckets.

9. The method of claim 8 in which resizing the hash table includes:

launching an asynchronous thread to carry out the resizing, wherein the asynchronous thread determines the load factor for a selected bucket group; and

resizing the selected bucket group if the load factor is higher or lower than predefined thresholds.

10. The method claim 9 wherein the thread acquires the latch for the selected bucket group in exclusive mode to carry out an updating operation on the bucket group.

11. The method of claim 6 wherein the number of bucket groups in the hash table is based on the number of threads in the computer system, and on a limit defined such that a specified load factor for the hash table is no larger than the product of the number of bucket groups and the number of inline buckets in each hash bucket.

29. The system of claim 1 wherein the set of properties entries in each hash bucket is maintained in a linked list.

30. The system of claim 29 wherein a set of unused entries in each hash bucket is maintained in a linked list.

12. A method for generating a hash table for a collection of data items, the method comprising:

(a) defining a set of hash buckets;

(b) generating, for each data item, a properties entry associated with the data item, the properties entry including representative values for the data item and a pointer to the data item; and

(c) storing each properties entry in a selected one of the hash buckets in a linked list of properties entries, the selected one of the hash buckets being determined by a hash value of the data item associated with the properties entry.

13. A computer readable medium including program instructions to be implemented by a computer for generating and maintaining a hash table for a collection of data items, the hash table comprising a set of bucket groups and hash buckets, each bucket group comprising:

a latch for the bucket group;

a set of inline hash buckets; and

a group header comprising a pointer definable to point to an array of overflow hash buckets.

14. The computer readable medium of claim 13 wherein each hash bucket is associated with a subset of the collection of data items, and wherein each hash bucket comprises a set of properties entries, each properties entry comprising a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.

15. The computer readable medium of claim 13 wherein each bucket group is defined to be storable in alignment with cache line boundaries in a specified data cache.

16. The computer readable medium of claim 13 further comprising program instructions for resizing the hash table, implementing steps comprising:

obtaining the latch for a selected bucket group in exclusive mode;

allocating a memory location for an array of overflow buckets;

updating the overflow pointer in the group header for the selected bucket group to point to the memory location; and

redistributing buckets in the inline hash buckets and the array of overflow buckets.

17. The computer readable medium of claim 16 wherein resizing the hash table includes launching an asynchronous thread to carry out the resizing, the asynchronous thread determining the load factor for a selected bucket group and carrying out the resizing for the selected bucket group if the load factor is higher or lower than predefined thresholds.

18. The computer readable medium of claim 16 wherein the resizing of the hash table further provides a thread determining the load factor for a selected bucket group and carrying out the resizing for the selected bucket group if the load factor is higher or lower than predefined thresholds, the thread acquiring the latch for the selected bucket group in exclusive mode to carry out an updating operation on the bucket group.

19. The computer readable medium of claim 13 wherein the number of bucket groups in the hash table is based on the number of threads in the computer, and on a limit defined such that a specified load factor for the hash table is no larger than the product of the number of bucket groups and the number of inline buckets in each hash bucket.

20. A method for generating a hash table for a collection of data items, the hash table comprising a set of bucket groups and hash buckets, the method comprising:

(a) defining each of the bucket groups to include a latch for the bucket group, a set of inline hash buckets, and a group header comprising a pointer definable to point to an array of overflow hash buckets; and

(b) defining each hash bucket to comprise a set of properties entries, each properties entry comprising a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.

21. The method of claim 20, further comprising the steps of:

obtaining the latch for a selected bucket group in exclusive mode,

allocating a memory location for an array of overflow buckets,

updating the overflow pointer in the group header for the selected bucket group to point to the memory location, and

redistributing buckets in the buckets in the bucket group and the array of overflow buckets.

22. A method for generating and maintaining a collection of data items, the method comprising:

(a) providing a hash table; and

(b) defining hash buckets in the hash table, the hash buckets storable in alignment with cache line boundaries in a specified data cache.

23. The method of claim 22 wherein each hash bucket is associated with a subset of the collection of data items, and wherein each hash table includes:

a set of property entries, each property entry including a pointer to an associated data item in the subset associated with the hash bucket; and

a set of representative values for the associated data item, the set of representative values being selected for the identification of the data item.

24. The method of claim 22 further comprising maintaining the set of property entries in each hash bucket in a linked list.

25. The method of claim 24 further comprising maintaining a set of unused entries in each hash bucket in a linked list.

26. The method of claim 23 further comprising maintaining the set of property entries in each hash bucket in a linked list.

27. A system for providing a hash table for a collection of data items, the system comprising:

means for providing a set of hash buckets in the hash table, each hash bucket being associated with a subset of the collection of data items; and

means for providing a set of properties entries in each of the hash buckets, wherein each properties entry includes a pointer to an associated data item in the subset associated with the hash bucket, and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.

28. The system of claim 27 wherein the hash buckets are storable in alignment with cache line boundaries in a specified data cache.

31. The system of claim 27 wherein said hash table includes a set of bucket groups, each bucket group including:

a latch for the bucket group;

a set of inline hash buckets; and

a group header comprising a pointer definable to point to an array of overflow hash buckets.

32. The system of claim 31 further comprising defining each bucket group to be storable in alignment with cache line boundaries in a specified data cache.

33. The system of claim 31 further comprising means for carrying out a resizing of the hash table, including:

means for obtaining the latch for a selected bucket group in exclusive mode;

means for allocating a memory location for an array of overflow buckets;

means for updating the overflow pointer in the group header for the selected bucket group to point to the memory location; and

means for redistributing buckets in the inline hash buckets and the array of overflow buckets.

34. The system of claim 33 in which resizing the hash table includes:

means for launching an asynchronous thread to carry out the resizing, wherein the asynchronous thread determines the load factor for a selected bucket group; and

means for resizing the selected bucket group if the load factor is higher or lower than predefined thresholds.

35. The system claim 34 wherein the thread acquires the latch for the selected bucket group in exclusive mode to carry out an updating operation on the bucket group.

36. The system of claim 31 wherein the number of bucket groups in the hash table is based on the number of threads in the computer system, and on a limit defined such that a specified load factor for the hash table is no larger than the product of the number of bucket groups and the number of inline buckets in each hash bucket.

37. A computer readable medium including program-instructions to be implemented by a computer for providing a hash table for a collection of data items, the program instructions performing steps comprising:

(a) providing a set of hash buckets in the hash table, each hash bucket being associated with a subset of the collection of data items; and

(b) providing a set of properties entries in each of the hash buckets, wherein each properties entry includes a pointer to an associated data item in the subset associated with the hash bucket and a set of representative values for the associated data item, wherein the set of representative values identifies the data item.

38. The computer readable medium of claim 37 wherein the steps further comprise defining the hash buckets to be storable in alignment with cache line boundaries in a specified data cache.

39. The computer readable medium of claim 37 wherein the steps further comprise maintaining the set of properties entries in each hash bucket in a linked list.

40. The computer readable medium of claim 39 wherein the steps further comprise maintaining a set of unused entries in each hash bucket in a linked list.

41. The computer readable medium of claim 37 wherein said hash table includes a set of bucket groups, each bucket group including:

a latch for the bucket group;

a set of inline hash buckets; and

a group header comprising a pointer definable to point to an array of overflow hash buckets.

42. The computer readable medium of claim 41 further comprising defining each bucket group to be storable in alignment with cache line boundaries in a specified data cache.

43. The computer readable medium of claim 41 wherein the steps further comprise carrying out a resizing of the hash table including:

obtaining the latch for a selected bucket group in exclusive mode;

allocating a memory location for an array of overflow buckets;

updating the overflow pointer in the group header for the selected bucket group to point to the memory location; and

redistributing buckets in the inline hash buckets and the array of overflow buckets.

44. The computer readable medium of claim 43 in which resizing the hash table includes:

launching an asynchronous thread to carry out the resizing, wherein the asynchronous thread determines the load factor for a selected bucket group; and

resizing the selected bucket group if the load factor is higher or lower than predefined thresholds.

45. The computer readable medium of claim 44 wherein the thread acquires the latch for the selected bucket group in exclusive mode to carry out an updating operation on the bucket group.