HASH INDEX

• US 20180011893A1
• Filed: 01/29/2015
• Published: 01/11/2018
• Est. Priority Date: 01/29/2015
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Kimura, Hideaki
• Granted Patent: US 11,023,453 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/202 Non-volatile memory

Abstract

Example implementations disclosed herein can be used to build, maintain, and use a hash table distributed across the plurality multiple nodes in a multi-node computing system. The hash table can include data pages associated by corresponding pointers according to a tree data structure. The data pages include leaf data pages. Each leaf data page can be associated with a corresponding hash value and include a tag bitmap. When a transaction associated with a key is executed, a hash value and a tag value are generated based on the key. The leaf data pages can be searched using the hash value. A probability that a leaf data page includes the key can be determined based on a comparison tag value with the tag bitmap.

Claims

1. A system comprising:

a plurality of processors;

a plurality of volatile random access memories (VRAMs) coupled to one or more of the plurality of processors;

a plurality of non-volatile random access memories (NVRAMs) coupled to one or more of the plurality of processors, wherein at least one of the plurality of NVRAMs comprises instructions, that when executed by one or more processors in the plurality of processors, cause the processors to;

access a hash table distributed across the plurality of VRAMs and the plurality of NVRAMs comprising;

a plurality of data pages associated with one another by a plurality of corresponding pointers according to a tree data structure, wherein the plurality of data pages comprise;

a root data page associated with a plurality of hash values;

a plurality of intermediate data pages associated with the root data page through corresponding subsets of the plurality of pointers and associated with corresponding subsets of the plurality of hash values; and

a plurality of leaf data pages, each associated with one intermediate data page in the plurality of intermediate data pages through a corresponding pointer in the plurality of pointers, and comprising a corresponding hash value included in the subset of the plurality of hash values included in the one intermediate data page.

2. The system of claim 1, wherein each data page in the plurality of data pages is a fixed sized data pages.

3. The system of claim 1, wherein the instructions further cause the processors to:

receive an input key;

generate a search hash value based on the input key;

search the hash table to find a matching leaf data page in the plurality of leaf data pages that includes the search hash value.

4. The system of claim 1, wherein each leaf data page in the plurality of leaf data pages comprise a probability tag map that includes a probability that a particular key exists in a particular leaf data page.

5. The system of claim 4, wherein the instructions further cause the processors to:

generate a tag value based on the input key;

search the hash table to find a matching leaf data page in the plurality of leaf data pages that includes a search hash value associated with the input key;

determine a probability the matching leaf data page contains the input key based on the probability tag map and the tag value;

if the probability is zero, then abort a transactions associated with the input key, otherwise, search for a data record in the matching leaf data page associated with the input key.

6. The system of claim 1, wherein copies of the root data page and a subset of the plurality of intermediate data pages are maintained in the plurality of VRAMs and the plurality of NVRAMs.

7. The system of claim 1, wherein the plurality of VRAMs and the plurality of NVRAMs are distributed among a plurality of system-on-chips (SOCs).

8. A method comprising:

generating, by a processor, a tag and a hash value based on an input key associated with a transaction;

searching, by the processor, a plurality of data pages comprising corresponding hash values and tag bitmaps for a data page in the plurality of data pages based on the hash value; and

comparing, by the processor, the tag to a tag bitmap in the data page to determine a probability that the data page contains a data record associated with the input key.

9. The method of claim 8 further comprising:

if the probability is greater than zero, then searching, by the processor, the data page for the data record associate with the input key; and

if the probability is less or equal to zero, then aborting the transaction.

10. The method of claim 9, wherein searching for the data page comprises:

executing the transaction using the data record when the data page is found; and

aborting the transaction when the data page is not found.

11. The method of claim 8 wherein the plurality of data pages comprise:

a root data page associated with a plurality of hash values;

a plurality of intermediate data pages associated with the root data page through corresponding subsets of the plurality of pointers and associated with corresponding subsets of the plurality of hash values; and

a plurality of leaf data pages, each associated with one intermediate data page in the plurality of intermediate data pages through a corresponding pointer in the plurality of pointers, and comprising a corresponding hash value included in the subset of the plurality of hash values included in the one intermediate data page.

12. The method of claim 11, wherein copies of the root data page and a subset of the plurality of intermediate data pages are maintained in an array comprising a volatile random access memory and a nonvolatile random access memory.

13. The method of claim 12, wherein the array is distributed among a plurality of system-on-chips (SOCs).

14. A non-transitory computer readable storage medium comprising instructions, that when executed by a processor, cause the processor to:

generate a tag and a hash value based on an input key associated with a transaction;

search a plurality of data pages comprising corresponding hash values and tag bitmaps for a data base in the plurality of data pages based on the hash value; and

compare the tag to a tag bitmap in the data page to determine a probability that the data page contains a data record associated with the input key.

15. The non-transitory computer readable storage medium of claim 14, wherein the instructions further cause the processor to:

search the data page for the data record associated with the input key if the probability is greater than zero; and

abort the transaction if the probability is less or equal to zero.