Hybrid hash tables

• US 8,806,175 B2
• Filed: 02/06/2013
• Issued: 08/12/2014
• Est. Priority Date: 02/23/2009
• Status: Expired due to Fees

• Current Assignee: Autonomy Incorporated (HP Inc.)
• Original Assignee: Longsand Limited (Open Text Corporation)
• Inventors: Beaman, Peter D., Newson, Robert S., Tran, Tuyen M.
• Primary Examiner(s): CHOE, YONG J
• Application Number:
  US13/760,115
• Publication Number:
  US 20130151810A1
• Time in Patent Office: 552 Days
• Field of Search: 711/216, 711/208, 711/E12.018
• US Class Current: 711/216
• CPC Class Codes: G06F 16/2255 Hash tables

Abstract

A hash table system having a first hash table and a second hash table is provided. The first hash table may be in-memory and the second hash table may be on-disk. Inserting an entry to the hash table system comprises inserting the entry into the first hash table, and, when the first hash table reaches a threshold load factor, flushing entries into the second hash table. Flushing the first hash table into the second hash table may comprise sequentially flushing the first hash table segments into corresponding second hash table segments. When looking up a key/value pair corresponding to a selected key in the hash table system, the system checks both the first and second hash tables for values corresponding to the selected key. The first and second hash tables may be divided into hash table segments and collision policies may be implemented within the hash table segments.

Claims

1. A computer-implemented method for identifying a set of values associated with a selected key, the method comprising:

providing, in a computer system having a processor, an in-memory hash table and a second hash table in a persistent storage;

computing, by the computer system, a first index for the selected key;

selecting first candidate elements from the in-memory hash table using the first index, the first candidate elements having associated first candidate keys;

computing, by the computer system, a second index for the selected key;

selecting second candidate elements from the second hash table using the second index, the second candidate elements having associated second candidate keys;

examining, by the computer system, the first candidate elements to determine whether a first candidate key matches the selected key, and, when the first candidate key matches the selected key, identifying, as a member of the set of values, a first value associated with a first candidate element that is associated with the first candidate key; and

examining, by the computer system, the second candidate elements to determine whether a second candidate key matches the selected key, and, when the second candidate key matches the selected key, identifying, as a member of the set of values, a second value associated with a second candidate element that is associated with the second candidate key.

2. The method of claim 1,

wherein selecting the first candidate elements comprises selecting an element corresponding to the first index in the in-memory hash table, and when a next in-memory element in the in-memory hash table has a previously inserted entry, selecting the next in-memory element;

and

wherein selecting the second candidate elements comprises selecting an element corresponding to the second index in the second hash table, and when a next in persistent storage element in the second hash table has a previously stored entry, selecting the next in persistent storage element.

3. The method of claim 2,

wherein the in-memory hash table is divided into a plurality of in-memory hash table segments,

wherein the next in-memory element is found within a first of the in-memory hash table segments,

wherein the second hash table is divided into a plurality of second hash table segments, and

wherein the next in persistent storage element is found within a first of the second hash table segments.

4. The method of claim 1,

wherein the selected key is associated with a selected discriminator value,

wherein selecting the first candidate elements comprises rejecting elements in the in-memory hash table containing an entry having a first discriminator value that is different than the selected discriminator value, and

wherein selecting the second candidate elements comprises rejecting elements in the second hash table containing an entry having a second discriminator value that is different than the selected discriminator value.

5. The method of claim 1, wherein the second hash table is an on-disk hash table.

6. A data storage system comprising:

a hash table system comprising an in-memory hash table and a second hash table in a persistent storage; and

an identification module for identifying a set of values associated with a selected key, wherein identifying comprises;

computing a first index for the selected key;

selecting first candidate elements from the in-memory hash table using the first index, the first candidate elements having associated first candidate keys;

computing a second index for the selected key;

selecting second candidate elements from the second hash table using the second index, the second candidate elements having associated second candidate keys;

examining the first candidate elements to determine whether a first candidate key matches the selected key, and when the first candidate key matches the selected key, identifying, as a first member of the set of values, a first value associated with a first candidate element that is associated with the first candidate key; and

examining the second candidate elements to determine whether a second candidate key matches the selected key, and when the second candidate key matches the selected key, identifying, as a second member of the set of values, a second value associated with a second candidate element that is associated with the second candidate key.

7. The data storage system of claim 6,

wherein selecting the first candidate elements comprises selecting an element corresponding to the first index in the in-memory hash table, and when a next in-memory element in the in-memory hash table has a previously inserted entry, selecting the next in-memory element;

and

wherein selecting the second candidate elements comprises selecting an element corresponding to the second index in the second hash table, and when a next in-persistent storage element in the second hash table has a previously stored entry, selecting the next in persistent storage element.

8. The data storage system of claim 7,

wherein the in-memory hash table is divided into a plurality of in-memory hash table segments,

wherein the next in-memory element is found within a first of the in-memory hash table segments,

wherein the second hash table is divided into a plurality of second hash table segments, and

wherein the next in persistent storage element is found within a first of the second hash table segments.

9. The data storage system of claim 6,

wherein the selected key is associated with a selected discriminator value,

wherein selecting the first candidate elements comprises rejecting elements in the in-memory hash table containing an entry having a first discriminator value that is different than the selected discriminator value, and

wherein selecting the second candidate elements comprises rejecting elements in the second hash table containing an entry having a second discriminator value that is different than the selected discriminator value.

10. The data storage system of claim 6, wherein the second hash table is an on-disk hash table.

11. A computer program product comprising a non-transitory computer usable medium having computer-executable instructions that control a computer to perform identifying of a set of values associated with a selected key, the instructions upon execution causing the computer to:

provide an in-memory hash table and a second hash table in a persistent storage;

compute a first index for the selected key;

select first candidate elements from the in-memory hash table using the first index, the first candidate elements having associated first candidate keys;

compute a second index for the selected key;

select second candidate elements from the second hash table using the second index, the second candidate elements having associated second candidate keys;

examine the first candidate elements to determine whether a first candidate key matches the selected key, and, when the first candidate key matches the selected key, identifying, as a member of the set of values, a first value associated with a first candidate element that is associated with the first candidate key; and

examine the second candidate elements to determine whether a second candidate key matches the selected key, and, when the second candidate key matches the selected key, identifying, as a member of the set of values, a second value associated with a second candidate element that is associated with the second candidate key.

12. The computer program product of claim 11,

wherein selecting the first candidate elements comprises selecting an element corresponding to the first index in the in-memory hash table, and when a next in-memory element in the in-memory hash table has a previously inserted entry, selecting the next in-memory element;

and

wherein selecting the second candidate elements comprises selecting an element corresponding to the second index in the second hash table, and when a next in persistent storage element in the second hash table has a previously stored entry, selecting the next in persistent storage element.

13. The computer program product of claim 12,

wherein the in-memory hash table is divided into a plurality of in-memory hash table segments,

wherein the next in-memory element is found within a first of the in-memory hash table segments,

wherein the second hash table is divided into a plurality of second hash table segments, and

wherein the next in persistent storage element is found within a first of the second hash table segments.

14. The computer program product of claim 13,

wherein the selected key is associated with a selected discriminator value,

wherein selecting the first candidate elements comprises rejecting elements in the in-memory hash table containing an entry having a first discriminator value that is different than the selected discriminator value, and

wherein selecting the second candidate elements comprises rejecting elements in the second hash table containing an entry having a second discriminator value that is different than the selected discriminator value.

15. The computer program product of claim 11, wherein the second hash table is an on-disk hash table.

16. A computer-implemented method for identifying a value associated with a selected key, the method comprising:

providing, in a computer system having a processor, an in-memory hash table and a second hash table in a persistent storage;

computing, by the computer system, an index for the selected key;

checking, by the computer system, the in-memory hash table for an entry corresponding to the selected key, wherein the checking comprises;

selecting candidate elements from the in-memory hash table using the index, the candidate elements having associated candidate keys;

for each of the candidate keys,

determining whether the candidate key matches the selected key;

in response to determining that the candidate key matches the selected key, identifying a value associated with the candidate key as a member of a set of values associated with the selected key; and

in response to the candidate key not matching the selected key, rejecting a candidate element associated with the candidate key; and

in response to determining that the entry corresponding to the selected key is not found in the in-memory hash table, checking, by the computer system, the second hash table for the entry corresponding to the selected key.

17. The method of claim 16,

wherein the computer system comprises a data storage system,

wherein the selected key is a unique identifier of a data object stored in the data storage system, and

wherein the value indicates a location in the data storage system where the data object is stored.

18. The method of claim 16, wherein the second hash table is an on-disk hash table.

19. A data storage system comprising:

a hash table system comprising an in-memory hash table and a second hash table in a persistent storage; and

an identification module for identifying a value associated with a selected key, wherein the identifying comprises;

checking the in-memory hash table for an entry corresponding to the selected key, wherein the checking comprises;

selecting candidate elements from the in-memory hash table using the index, the candidate elements having associated candidate keys;

for each of the candidate keys,

determining whether the candidate key matches the selected key;

in response to determining that the candidate key matches the selected key, identifying a value associated with the candidate key as a member of a set of values associated with the selected key; and

in response to the candidate key not matching the selected key, rejecting a candidate element associated with the candidate key; and

in response to determining that the entry corresponding to the selected key is not found in the in-memory hash table, checking the second hash table for the entry corresponding to the selected key.

20. The data storage system of claim 19, wherein the second hash table is an on-disk hash table.