Latchless, non-blocking dynamically resizable segmented hash index

Patent metadata

Field	Value
Publication number	US-10346315-B2
Application number	US-201715606327-A
Country	US
Kind code	B2
Filing date	May 26, 2017
Priority date	May 26, 2017
Publication date	Jul 9, 2019
Grant date	Jul 9, 2019

Abstract

A hashing scheme includes a cache-friendly, latchless, non-blocking dynamically resizable hash index with constant-time lookup operations that is also amenable to fast lookups via remote memory access. Specifically, the hashing scheme provides each of the following features: latchless reads, fine grained lightweight locks for writers, non-blocking dynamic resizability, cache-friendly access, constant-time lookup operations, amenable to remote memory access via RDMA protocol through one sided read operations, as well as non-RDMA access.

First claim

What is claimed is:

1. A method comprising:
organizing a hash table into a plurality of segments, wherein each segment of the plurality of segments includes a set of buckets;
inserting hash records into the hash table based on a first number of bucket-identifying bits;
dynamically resizing the hash table without blocking access to the hash table, wherein dynamically resizing the hash table includes:
selecting a particular segment of the plurality of segments for resizing;
adding to the hash table one or more companion segments of the particular segment;
redistributing hash records from buckets in the particular segment between the particular segment and the one or more companion segments based on a second number of bucket-identifying bits that is different than the first number of bucket-identifying bits;
determining the second number of bucket-identifying bits for a particular hash record by prepending, to the first number of bucket-identifying bits for the particular hash record, one or more bits from a tag value stored in the particular hash record;

while dynamically resizing the hash table, allowing one or more requesting entities to continue to perform lookups using the hash table;
wherein the method is performed by one or more computing devices.

2. The method of claim 1 further comprising:
using a resize index to track progress of the dynamic resizing of the hash table;
during dynamic resizing of the hash table, determining that a new hash record for a particular key is to be inserted into the hash table;
determining, based on the resize index and first number of bucket-identifying bits produced by hashing the particular key, whether to:
select a target bucket based on the first number of bucket-identifying bits produced by hashing the particular key; or
select the target bucket based on the second number of bucket-identifying bits produced by hashing the particular key;

storing the new hash record in the hash table based on the particular key mapping to the target bucket.

3. The method of claim 1 further comprising:
using a resize index to track progress of the dynamic resizing of the hash table;
during dynamic resizing of the hash table, a requesting entity performing a lookup based on a particular key by:
determining, based on the resize index and the first number of bucket-identifying bits produced by hashing the particular key, whether to:
select a target bucket based on the first number of bucket-identifying bits produced by hashing the particular key; or
select the target bucket based on the second number of bucket-identifying bits produced by hashing the particular key;

performing the lookup based on the particular key mapping to the target bucket.

4. A method comprising:
organizing a hash table into a plurality of segments, wherein each segment of the plurality of segments includes a set of buckets;
inserting hash records into the hash table based on a first number of bucket-identifying bits;
dynamically resizing the hash table without blocking access to the hash table, wherein dynamically resizing the hash table includes:
selecting a particular segment of the plurality of segments for resizing;
adding to the hash table one or more companion segments of the particular segment;
redistributing hash records from buckets in the particular segment between the particular segment and the one or more companion segments based on a second number of bucket-identifying bits that is different than the first number of bucket-identifying bits;

while dynamically resizing the hash table, allowing one or more requesting entities to continue to perform lookups using the hash table;
wherein the one or more companion segments include companion buckets for the buckets in the particular segment;
wherein redistributing hash records includes, for each particular bucket in the set of buckets in the particular segment, splitting the bucket by performing the steps of:
identifying a set of candidate hash records that qualify as redistribution candidates for the particular bucket, wherein the set of candidate hash records that qualify as redistribution candidates for the particular bucket are hash records that correspond to key values that hash to the particular bucket using the first number of bucket-identifying bits;
for each candidate hash record, determining a target bucket based on the second number of bucket-identifying bits; and
for those candidate hash records whose target bucket is not the particular bucket, moving the hash records to a bucket in one of the one or more companion segments;

wherein identifying the set of candidate hash records that qualify as redistribution candidates for the particular bucket includes:
inspecting overflow-indicating bits maintained for the particular bucket to identify hash records for which the particular bucket is a primary bucket; and
inspecting overflow-indicating bits maintained for a next bucket that immediately follows the particular bucket to identify hash records for which the next bucket is a secondary bucket.

5. A method comprising:
organizing a hash table into a plurality of segments, wherein each segment of the plurality of segments includes a set of buckets;
inserting hash records into the hash table based on a first number of bucket-identifying bits;
dynamically resizing the hash table without blocking access to the hash table, wherein dynamically resizing the hash table includes:
selecting a particular segment of the plurality of segments for resizing;
adding to the hash table one or more companion segments of the particular segment;
redistributing hash records from buckets in the particular segment between the particular segment and the one or more companion segments based on a second number of bucket-identifying bits that is different than the first number of bucket-identifying bits;

while dynamically resizing the hash table, allowing one or more requesting entities to continue to perform lookups using the hash table;
after some but not all of the plurality of segments have been resized, halting the resizing of the hash table in response to determining that a load factor of the hash table satisfies certain conditions; and
resuming the resizing of the hash table responsive to detecting that that the load factor of the hash table ceases to satisfy certain conditions.

6. A method comprising:
organizing a hash table into a plurality of segments, wherein each segment of the plurality of segments includes a set of buckets;
inserting hash records into the hash table based on a first number of bucket-identifying bits;
dynamically resizing the hash table without blocking access to the hash table, wherein dynamically resizing the hash table includes:
selecting a particular segment of the plurality of segments for resizing;
adding to the hash table one or more companion segments of the particular segment;
redistributing hash records from buckets in the particular segment between the particular segment and the one or more companion segments based on a second number of bucket-identifying bits that is different than the first number of bucket-identifying bits;

while dynamically resizing the hash table, allowing one or more requesting entities to continue to perform lookups using the hash table;

when a hash record is to be inserted into the hash table, performing the steps of:
determining a target bucket based on a hash value produced by hashing a key value that corresponds to the hash record;
determining that the target bucket does not have room for the hash record;
responsive to determining that the target bucket does not have room for the hash record, inspecting N buckets that immediately follow the target bucket to find room for the hash record; and
responsive t

Assignees

• Oracle Int Corp

Inventors

• Teotia Siddharth
• Kunchithapadam Krishna
• Lahiri Tirthankar
• Kamp Jesse
• Gleeson Michael J
• Loaiza Juan R
• Swart Garret F
• Macnaughton Neil J S
• Shergill Kam

Classifications

• G06F2212/621

  Coherency control relating to peripheral accessing, e.g. from DMA or I/O device · CPC title

• G06F2212/313

  In storage device · CPC title

• G06F12/128

  adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel · CPC title

• G06F12/126

  with special data handling, e.g. priority of data or instructions, handling errors or pinning · CPC title

• G06F12/0868

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title