Hash index

Patent metadata

Field	Value
Publication number	US-11023453-B2
Application number	US-201515545491-A
Country	US
Kind code	B2
Filing date	Jan 29, 2015
Priority date	Jan 29, 2015
Publication date	Jun 1, 2021
Grant date	Jun 1, 2021

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.

First claim

What is claimed is:

1. A multi-core computing system comprising:
a plurality of system-on-chips (SOCs); and
a plurality of interconnected nodes having inter-node communication connections between each of the plurality of nodes such that data is relayed from one node to another node in the plurality of nodes, wherein each of the plurality of interconnected nodes comprises:
a SOC from the plurality of SOCs;
a plurality of core processors on the SOC;
a plurality of volatile random access memories (VRAMs) coupled to one or more of the plurality of core 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 distributed across the plurality of VRAMS and NVRAMS that are associated with one another by a plurality of corresponding pointers according to a tree data structure, wherein the plurality of data pages contain data records that are maintained in both VRAM and NVRAM creating a duality of data records contained in the plurality of data pages distributed across the plurality of VRAMS and NVRAMS, and further 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, wherein the duality of data records contained in the plurality of data pages distributed across the plurality of VRAMS and NVRAMS enables the plurality of SOCs distributed among the plurality of interconnected nodes to execute transactions on the data records concurrently, and wherein the plurality of pointers track the corresponding data records such that an optimistic concurrency control (OCC) blocks contentious data accesses resulting from the concurrent transactions being executed on the same data records.

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

3. The multi-core computing 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 multi-core computing system of claim 1 , wherein each leaf data page in the plurality of leaf data pages comprise a probability tag map that indicates a probability that a particular key exists in a particular leaf data page.

5. The multi-core computing 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 transaction associated with the input key, otherwise, search for a data record in the matching leaf data page associated with the input key.

6. The multi-core computing 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 multi-core computing system of claim 1 , wherein the plurality of VRAMs and the plurality of NVRAMs are distributed among the plurality of SOCs.

8. A method comprising:
generating, by at least one core processor on a System-on-Chip (SoC), a tag and a hash value based on an input key associated with a transaction, wherein the at least one core processor is in a multi-core computing system having a plurality of core processors distributed across a plurality of SoCs;
searching, by the at least one core processor on the SOC, 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, wherein the tag bitmaps include a probability score, wherein the plurality of data pages are distributed across a plurality of volatile random access memories (VRAM) coupled to the at least one core processor in the multi-core system and a plurality of volatile random access memories (NVRAM) coupled to the at least one core processor in the multi-core computer system; and
comparing, by the at least one core processor on the SOC, 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, wherein the determined probability is based on the probability score included in the tag bitmap corresponding to the data page, wherein the plurality of data pages contain data records that are maintained in both a VRAM and a NVRAM creating a duality of data records contained in the plurality of data pages distributed across the plurality of VRAMS and NVRAMS and the duality of data records enables the plurality of SOCs in the multi-core computing system to execute transactions on the data records concurrently, and wherein the tag bitmaps track the corresponding data records such that an optimistic concurrency control (OCC) blocks contentious data accesses resulting from the concurrent transactions being executed on the same data records.

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 the plurality SOCs.

14. A non-transitory computer readable storage medium comprising instructions, that when executed by a processor, c

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Kimura Hideaki

Classifications

• G06F16/9014 Primary

  hash tables · CPC title

• G06F2212/202

  Non-volatile memory · CPC title

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F16/283

  Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP · CPC title

• G06F16/9027

  Trees · CPC title