Scaleable hash table for shared-memory multiprocessor system

• US 6,578,131 B1
• Filed: 04/27/1999
• Issued: 06/10/2003
• Est. Priority Date: 04/27/1999
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Larson, Per-Ake, Reilly, George V., Krishnan, Murali R.
• Primary Examiner(s): Ellis, Kevin L.
• Application Number:
  US09/300,715
• Time in Patent Office: 1,505 Days
• Field of Search: 707/100, 711/216, 711/170
• US Class Current: 711/216
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A scaleable hash table for shared memory multi-processor (SMP) that supports very high rates of concurrent operations (e.g., insert, delete, and lookup), while simultaneously reducing cache misses. The SMP system has a memory subsystem and a processor subsystem interconnected via a bus structure. The hash table is stored in the memory subsystem to facilitate access to data items. The hash table is segmented into multiple buckets, with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to a common value. Individual bucket nodes contain multiple signature-pointer pairs that reference corresponding data items. Each signature-pointer pair has a hash signature computed from a key of the data item and a pointer to the data item. The first bucket node in the linked list for each of the buckets is stored in the hash table. To enable multithread access, while serializing operation of the table, the SMP system utilizes two levels of locks: a table lock and multiple bucket locks. The table lock allows access by a single processing thread to the table while blocking access for other processing threads. The table lock is held just long enough for the thread to acquire the bucket lock of a particular bucket node. Once the table lock is released, another thread can access the hash table and any one of the other buckets.

Claims

1. A system, comprising:

a memory subsystem to store data items;

a hash table stored in the memory subsystem to facilitate access to the data, the hash table comprising multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket, individual bucket nodes containing multiple signature-pointer pairs with each signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item; and

a processing subsystem coupled to the memory subsystem to access the data via the hash table, the processing subsystem comparing a hash signature of a search key for a target data item with the hash signatures of the signature-pointer pairs from the bucket nodes when searching a hash chain for the target data item.

2. A system as recited in claim 1, wherein the processing subsystem comprises multiple processors.

3. A system as recited in claim 1, wherein the hash table stores first bucket nodes of the linked lists referenced by the buckets.

4. A system as recited in claim 1, wherein the processing subsystem supports multiple processing threads that utilize the hash table to access particular data items in the memory subsystem, further comprising:

a table lock to selectively allow access by a single processing thread to the hash table while blocking access for other processing threads; and

multiple bucket locks for corresponding buckets, each bucket lock selectively allowing access by a single processing thread to the corresponding bucket while blocking access for other processing threads.

5. A system as recited in claim 1, wherein the hash table is partitioned into multiple subtables, with each subtable having multiple buckets.

6. A system as recited in claim 1, wherein said individual bucket nodes contain three signature-pointer pairs.

7. A system as recited in claim 1, wherein said individual bucket nodes contain seven signature-pointer pairs.

8. A shared-memory multiprocessor system, comprising:

a memory subsystem to store data items;

a hash table stored in the memory subsystem to facilitate access to the data, the hash table being partitioned into multiple subtables, each subtable comprising multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket, individual bucket nodes containing multiple signature-pointer pairs, each signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item;

the hash table being configured to store first bucket nodes of the linked lists referenced by the buckets;

multiple processors coupled to the memory subsystem, each processor supporting at least one processing thread that uses the hash table to access particular data items in the memory subsystem;

multiple subtable locks for corresponding ones of the subtables, each subtable lock selectively allowing access by a single processing thread to the corresponding subtable while blocking access for other processing threads; and

multiple bucket locks for corresponding buckets, each bucket lock selectively allowing access by a single processing thread to the corresponding bucket while blocking access for other processing threads.

9. A shared-memory multiprocessor system as recited in claim 8, wherein said each processor hashes a key of a target data item and compares the hashed key with the hash signatures of the signature-pointer pairs from the bucket nodes in an effort to locate the target data item.

10. A shared-memory multiprocessor system as recited in claim 8, wherein said each processor has a cache memory and one of said processors loads the multiple signature-pointer pairs from one of the bucket nodes into the cache memory.

11. A shared-memory multiprocessor system as recited in claim 10, wherein the cache memory has at least two cache lines and the signature-pointer pairs are arranged in the cache memory so that the hash signatures are placed in a first of the cache lines and the pointers are placed in a second of the cache lines.

12. A shared-memory multiprocessor system as recited in claim 10, wherein said one processor sets a lock on the cache memory.

13. A system, comprising:

a memory subsystem to store data items;

a hash table stored in the memory subsystem to facilitate access to the data, the hash table comprising multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket;

individual bucket nodes containing multiple signature-pointer pairs, each signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item;

a processing subsystem coupled to the memory subsystem, the processing subsystem supporting multiple processing threads that utilize the hash table to access particular data items in the memory subsystem;

a table lock to selectively allow access by a single processing thread to the hash table while blocking access for other processing threads; and

multiple bucket locks for corresponding buckets, each bucket lock selectively allowing access by a single processing thread to the corresponding bucket while blocking access for other processing threads.

14. A system as recited in claim 13, wherein the processing subsystem comprises multiple processors.

15. A system as recited in claim 13, wherein the hash table stores first bucket nodes of the linked lists referenced by the buckets.

16. A system as recited in claim 13, wherein the hash table is partitioned into multiple subtables;

with each subtable having multiple buckets.

17. A system as recited in claim 13, wherein the processing subsystem has a cache memory and loads the multiple signature-pointer pairs from one of the bucket nodes into the cache memory.

18. A system as recited in claim 17, wherein the cache memory has at least two cache lines and the signature-pointer pairs are arranged such that the hash signatures are placed in the first of the cache lines and the pointers are placed in the second cache lines.

19. A system as recited in claim 17, wherein the processing subsystem sets a spin lock on the cache memory.

20. A system, comprising:

a memory subsystem to store data items;

a hash table stored in the memory subsystem to facilitate access to the data, the hash table comprising multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket, individual bucket nodes containing a signature-pointer pair having a hash signature computed from a key of a data item and a pointer to the data item;

the hash table being configured to store first bucket nodes of the linked lists referenced by the buckets; and

a processing subsystem coupled to the memory subsystem to access the data via the hash table, the processing subsystem comparing a hash signature of a search key of a target data item with the hash signatures of the signature-pointer pairs from the bucket nodes in an effort to locate the target data item.

21. A system as recited in claim 20, wherein the individual bucket nodes contain multiple signature-pointer pairs.

22. A system as recited in claim 20, wherein the processing subsystem comprises multiple processors.

23. A system as recited in claim 20, wherein the processing subsystem supports multiple processing threads that utilize the hash table to access particular data items in the memory subsystem, further comprising:

a table lock to selectively allow access by a single processing thread to the hash table while blocking access for other processing threads; and

multiple bucket locks for corresponding buckets, each bucket lock selectively allowing access by a single processing thread to the corresponding bucket while blocking access for other processing threads.

24. A system as recited in claim 20, wherein the hash table is partitioned into multiple subtables, with each subtable having multiple buckets.

25. A system as recited in claim 20, wherein the processing subsystem has a cache memory and loads the signature-pointer pair from a first bucket node in the hash table into the cache memory.

65. The system as recited in claim 20, wherein the reference to a linked list of bucket nodes comprises a pointer that points to the location of bucket nodes stored outside the hash table.

66. The system as recited in claim 20, wherein the first bucket nodes stored in the hash table are configured to make reference to other bucket nodes stored outside the table.

67. The system as recited in claim 20, wherein the hash table is configured to automatically store only the first bucket nodes in the hash table.

26. A system, comprising:

a memory subsystem to store data items;

a hash table stored in the memory subsystem to facilitate access to the data, the hash table comprising multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket, individual bucket nodes containing multiple pointers to associated data items;

the hash table being configured to store first bucket nodes of the linked lists referenced by the buckets; and

a processing subsystem coupled to the memory subsystem to access target data items by traversing the bucket nodes referenced in the hash table.

27. A system as recited in claim 26, further including multiple hash signatures respectively associated with the multiple pointers, to form multiple signature-pointer pairs.

28. A system as recited in claim 26, wherein the processing subsystem comprises multiple processors.

29. A system as recited in claim 26, wherein the processing subsystem supports multiple processing threads that utilize the hash table to access particular data items in the memory subsystem, further comprising:

a table lock to selectively allow access by a single processing thread to the hash table while blocking access for other processing threads; and

multiple bucket locks for corresponding buckets, each bucket lock selectively allowing access by a single processing thread to the corresponding bucket while blocking access for other processing threads.

30. A system as recited in claim 26, wherein the hash table is partitioned into multiple subtables, with each subtable having multiple buckets.

31. A system as recited in claim 27, wherein the processing subsystem has a cache memory and loads the multiple signature-pointer pairs from one of the bucket nodes into the cache memory.

32. A system as recited in claim 31, wherein the cache memory has at least two cache lines and the signature-pointer pairs are arranged in the cache memory so that the hash signatures are placed in a first of the cache lines and the pointers are placed in a second of the cache lines.

33. A system as recited in claim 31, wherein the processing subsystem sets a spin lock on the cache memory.

68. The system as recited in claim 26, wherein the reference to a linked list of bucket nodes comprises a pointer that points to the location of bucket nodes stored outside the hash table.

69. The system as recited in claim 26, wherein the first bucket nodes stored in the hash table are configured to make reference to other bucket nodes stored outside the table.

70. The system as recited in claim 26, wherein the hash table is configured to automatically store only the first bucket nodes in the hash table.

34. A system, comprising:

a memory subsystem to store data items;

a hash table stored in the memory subsystem to facilitate access to the data, the hash table comprising multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket;

individual bucket nodes containing multiple signature-pointer pairs, each signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item;

the hash table being configured to store first bucket nodes of the linked lists referenced by the buckets; and

a processing subsystem coupled to the memory subsystem to access a target data item by comparing a hash of a key for the target data item with the hash signatures in the bucket nodes.

35. A system as recited in claim 34, wherein the hash table is partitioned into multiple subtables, with each subtable having multiple buckets.

36. A system as recited in claim 34, wherein the processing subsystem has a cache memory and loads the multiple signature-pointer pairs from one of the bucket nodes into the cache memory.

37. A system as recited in claim 36, wherein the cache memory has at least two cache lines and the signature-pointer pairs are arranged in the cache memory so that the hash signatures are placed in a first of the cache lines and the pointers are placed in a second of the cache lines.

38. A system as recited in claim 36, wherein the processing subsystem sets a spin lock that resides in the cache.

39. A system, comprising:

a memory subsystem to store data items;

a hash table stored in the memory subsystem to facilitate access to the data, the hash table comprising multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket, individual bucket nodes containing a signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item;

a processing subsystem coupled to the memory subsystem, the processing subsystem supporting multiple processing threads that utilize the hash table to access particular data items in the memory subsystem;

wherein the hash table is partitioned into multiple subtables, and each subtable includes a subtable lock to selectively allow access by a single processing thread to the corresponding subtable while blocking access for other processing threads; and

multiple bucket locks for corresponding buckets, each bucket lock selectively allowing access by a single processing thread to the corresponding bucket while blocking access for other processing threads.

40. A system as recited in claim 39, wherein the processing subsystem has a cache memory and loads the signature-pointer pair from one of the bucket nodes into the cache memory.

41. A system as recited in claim 40, wherein the individual bucket nodes contain multiple signature-pointer pairs, further wherein the cache memory has at least two cache lines and the signature-pointer pairs are arranged in the cache memory so that the hash signatures are placed in a first of the cache lines and the pointers are placed in a second of the cache lines.

42. A system as recited in claim 40, wherein the processing subsystem sets a spin lock that resides in the cache memory.

43. A system, comprising:

a memory subsystem to store data items;

a hash table stored in the memory subsystem to facilitate access to the data, the hash table being partitioned into multiple subtables, each subtable comprising multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket;

a processing subsystem coupled to the memory subsystem, the processing subsystem supporting multiple processing threads that utilize the hash table to access particular data items in the memory subsystem;

multiple subtable locks for corresponding ones of the subtables, each subtable lock selectively allowing access by a single processing thread to the corresponding subtable while blocking access for other processing threads; and

multiple bucket locks for corresponding buckets, each bucket lock selectively allowing access by a single processing thread to the corresponding bucket while blocking access for other processing threads.

44. A system as recited in claim 43, wherein the hash table stores first bucket nodes of the linked lists referenced by the buckets.

45. A system as recited in claim 43, wherein the processing subsystem has a cache memory to temporarily hold bucket nodes for processing, the processing subsystem setting a spin lock on the cache memory.

46. A system, comprising:

a memory subsystem to store data items;

a hash table stored in the memory subsystem to facilitate access to the data, the hash table being partitioned into multiple subtables, each subtable comprising multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket;

individual bucket nodes containing at least one signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item; and

a processing subsystem coupled to the memory subsystem to access the data via the hash table.

47. A system as recited in claim 46, wherein the processing subsystem has a cache memory to temporarily hold bucket nodes for processing, the processing subsystem setting a spin lock on the cache memory.

48. In a system having a memory subsystem and a processing subsystem that accesses the memory subsystem using a hash table, wherein the hash table comprises multiple buckets with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket, a method comprising:

grouping multiple signature-pointer pairs into a single bucket node, each signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item;

loading a single bucket node of said multiple signature-pointer pairs into a cache memory;

hashing a key of a target data item; and

comparing the hashed key with the hash signatures of the signature-pointer pairs in the cache memory.

49. A method as recited in claim 48, wherein the grouping comprises grouping three signature-pointer pairs into the bucket node.

50. A method as recited in claim 48, wherein the grouping comprises grouping seven signature-pointer pairs into the bucket node.

51. A method as recited in claim 48, further comprising storing, in the hash table, a first bucket node from each of the linked lists of bucket nodes.

52. A method as recited in claim 48, further comprising:

selectively setting a table lock to govern access to the hash table; and

selectively setting one of multiple bucket locks to govern access to corresponding buckets.

53. A method as recited in claim 48, further comprising partitioning the hash table into multiple subtables.

54. A method as recited in claim 48, wherein the cache memory has at least two cache lines, and further comprising arranging the signature-pointer pairs in the cache memory so that the hash signatures are placed in a first of the cache lines and the pointers are placed in a second of the cache lines.

55. A method as recited in claim 54, further comprising setting a spin lock on the cache memory.

56. In a system having a memory subsystem and a processing subsystem that accesses the memory subsystem using a hash table, wherein the hash table comprises multiple buckets with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket, a method comprising:

grouping multiple signature-pointer pairs in a single bucket node, each signature-pointer pair comprising- a hash signature computed from a key of a data item and a pointer to the data item;

storing, in the hash table, a first bucket node from each of the linked lists of bucket nodes;

establishing a table lock to selectively allow access to the hash table; and

establishing multiple bucket locks for corresponding ones of the buckets to selectively allow access to the corresponding buckets.

57. A method as recited in claim 56, wherein the grouping comprises grouping three signature-pointer pairs into the bucket node.

58. A method as recited in claim 56, wherein the grouping comprises grouping seven signature-pointer pairs into the bucket node.

59. In a system having a memory subsystem and a processing subsystem that accesses the memory subsystem using a hash table, wherein the hash table comprises multiple buckets with each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to said each bucket, a method comprising:

grouping multiple signature-pointer pairs into a single bucket node, each signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item;

storing a first bucket node from each of the linked lists of bucket nodes in the hash table;

partitioning the hash table into multiple subtables;

establishing subtable locks to selectively allow access of one processing thread at a time to the corresponding subtables;

establishing multiple bucket locks for corresponding ones of the buckets to selectively allow access of one processing thread at a time to the corresponding buckets;

creating a processing thread to access a target data item with an associated key;

hashing the key of the target data item;

selecting one of the subtables using the hashed key;

acquiring a subtable lock for the selected subtable;

choosing a bucket within the subtable using the hashed key;

acquiring a bucket lock associated with the chosen bucket;

releasing the subtable lock after said setting the bucket lock;

loading a single bucket node from the chosen bucket into a cache memory; and

comparing the hashed key with the hash signatures of the multiple signature-pointer pairs contained in the bucket node loaded in the cache memory.

60. A computer-readable medium having computer executable instructions for directing a processor to:

hash a key of a target data item that is stored in memory;

use the hashed key to access a bucket in a hash table, the bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to the bucket;

load a first bucket node from the hash table into a cache, the first bucket node comprising multiple signature-pointer pairs, each signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item;

hash a key of a target data item; and

compare the hashed key with the hash signatures of the signature-pointer pairs in the cache memory.

61. A computer-readable medium as recited in claim 60, further comprising instructions to direct the processor to set a spin lock on the cache memory.

62. A hash table embodied as a data structure stored on a computer-readable medium, the hash table comprising:

multiple buckets, each bucket containing a reference to a linked list of bucket nodes that hold references to data items with keys that hash to a common bucket;

first bucket nodes from each of the linked lists of bucket nodes stored in corresponding ones of the buckets; and

wherein individual first bucket nodes contain multiple signature-pointer pairs, each signature-pointer pair comprising a hash signature computed from a key of a data item and a pointer to the data item.

63. A hash table as recited in claim 62, further comprising:

a table lock that can be set to govern access to the table; and

multiple bucket locks for corresponding ones of the buckets, each bucket lock being selectively set to govern access to the corresponding bucket.

64. A hash table as recited in claim 62, further comprising multiple subtables, each subtable having multiple buckets.