Efficient usage of one-sided RDMA for linear probing

Patent metadata

Field	Value
Publication number	US-11720522-B2
Application number	US-202117176856-A
Country	US
Kind code	B2
Filing date	Feb 16, 2021
Priority date	Jun 12, 2020
Publication date	Aug 8, 2023
Grant date	Aug 8, 2023

Abstract

Systems and methods for reducing latency of probing operations of remotely located linear hash tables are described herein. In an embodiment, a system receives a request to perform a probing operation on a remotely located linear hash table based on a key value. Prior to performing the probing operation, the system dynamically predicts a number of slots for a single read of the linear hash table to minimize total cost for an average probing operation. The system determines a hash value based on the key value and determines a slot of the linear hash table to which the hash value corresponds. After predicting the number of slots, the system issues an RDMA request to perform a read of the predicted number of slots from the linear hash table starting at the slot to which the hash value corresponds.

First claim

What is claimed is:

1. A system comprising:
one or more processors;
a memory storing instructions which, when executed by the one or more processors, causes performance of:
receiving a request to perform a probing operation on a remotely located linear hash table based on a key value;
prior to performing the probing operation, dynamically predicting a first number of slots for a single read of the linear hash table that minimizes total cost for an average probing operation;
determining a hash value based on the key value;
determining a slot of the linear hash table to which the hash value corresponds; and
after predicting the first number of slots, issuing a first remote direct memory access (RDMA) request to perform a read of the predicted first number of slots from the linear hash table starting at the slot to which the hash value corresponds.

2. The system of claim 1 , wherein dynamically predicting the first number of slots for a single read of the linear hash table to minimize total cost for the average probing operation comprises:
generating a first value comprising a cost of performing a single read operation from the linear hash table as a function of a number of slots per read;
generating a second value comprising an expected number of reads to reach a first empty slot as a function of the number of slots per read;
computing the predicted first number of slots as a minimization over the number of slots per read of a function comprising the cost of performing the single read operation and the expected number of reads to reach the first empty slot.

3. The system of claim 2 , wherein computing the expected number of reads to reach the first empty slot comprises computing a summation of a plurality of weighted probabilities, each of the plurality of weighted probabilities computed as a product of a number of reads and a probability that the first empty slot would be found after the number of reads but not after a smaller number of reads.

4. The system of claim 3 , wherein each of the plurality of weighted probabilities is computed based, at least in part, on a number of slots in the linear hash table and a number of empty slots in the linear hash table.

5. The system of claim 1 , wherein the instructions, when executed by the one or more processors, further cause performing:
receiving a second request to perform a second probing operation on the remotely located linear hash table based on a second key value;
prior to performing the second probing operation, dynamically predicting a second number of slots for a single read of the linear hash table to minimize total cost for the average probing operation;
determining that the second number of slots is greater than a stored threshold number of slots;
determining a second hash value based on the second key value;
determining a second slot of the linear hash table to which the second hash value corresponds;
in response to determining that the second number of slots is greater than the stored threshold number of slots, issuing a second RDMA request to perform a second read with the threshold number of slots from the linear hash table starting at the slot to which the hash value corresponds.

6. The system of claim 1 , wherein the instructions, when executed by the one or more processors, further cause performing:
after issuing the RDMA request to read the predicted first number of slots from the linear hash table starting at the slot to which the hash value corresponds, identifying, based on one or more results of the RDMA request, a location in the linear hash table of a plurality of occupied slots;
receiving a second request to perform a second probing operation on the remotely located linear hash table based on a second key value;
determining a second hash value based on the second key value;
determining a second slot of the linear hash table to which the second hash value corresponds;
prior to performing the second probing operation, dynamically predicting a second number of slots for a single read of the linear hash table to minimize total cost for the average probing operation, wherein predicting the second number of slots for a single read of the linear hash table to minimize total cost for the average probing operation comprises setting a probability of encountering an empty slot to zero for each of the plurality of occupied slots; and
issuing a second RDMA request to perform a read with the predicted second number of slots from the linear hash table starting at the second slot to which the second hash value corresponds.

7. The system of claim 1 , wherein the instructions, when executed by the one or more processors, further cause performing:
predicting a second number of slots for a second read of the linear hash table to minimize cost for an average probing operation;
receiving results of the RDMA read request;
determining that the results do not include an empty slot or data corresponding to the key value and, in response, issuing a second RDMA request to perform a read of the predicted second number of slots from the linear hash table.

8. The system of claim 7 , wherein the second number of slots is predicted prior to issuing the first RDMA request.

9. A method comprising:
receiving a request to perform a probing operation on a remotely located linear hash table based on a key value;
prior to performing the probing operation, dynamically predicting a first number of slots for a single read of the linear hash table that minimizes total cost for an average probing operation;
determining a hash value based on the key value;
determining a slot of the linear hash table to which the hash value corresponds; and
after predicting the first number of slots, issuing a first remote direct memory access (RDMA) request to perform a read of the predicted first number of slots from the linear hash table starting at the slot to which the hash value corresponds.

10. The method of claim 9 , wherein dynamically predicting the first number of slots for a single read of the linear hash table to minimize total cost for the average probing operation comprises:
generating a first value comprising a cost of performing a single read operation from the linear hash table as a function of a number of slots per read;
generating a second value comprising an expected number of reads to reach a first empty slot as a function of the number of slots per read;
computing the predicted first number of slots as a minimization over the number of slots per read of a function comprising the cost of performing the single read operation and the expected number of reads to reach the first empty slot.

11. The method of claim 10 , wherein computing the expected number of reads to reach the first empty slot comprises computing a summation of a plurality of weighted probabilities, each of the plurality of weighted probabilities computed as a product of a number of reads and a probability that the first empty slot would be found after the number of reads but not after a smaller number of reads.

12. The method of claim 11 , wherein each of the plurality of weighted probabilities is computed based, at least in part, on a number of slots in the linear hash table and a number of empty slots in the linear hash table.

13. The method of claim 9 , further comprising:
receiving a second request to perform a second probing operation on the remotely located linear hash table based on a second key value;
prior to performing the second probing operation, dynamically predicting a second number of slots for a single read of the linear hash table to minimize total cost for the average probing operation;
determining th

Assignees

• Oracle Int Corp

Inventors

• Wang Tinggang
• Yang Shuo
• Kimura Hideaki
• Swart Garret F
• Blanas Spyros

Classifications

• G06F16/2455

  Query execution · CPC title

• G06F15/17331 Primary

  Distributed shared memory [DSM], e.g. remote direct memory access [RDMA] · CPC title

• G06F16/245

  Query processing · CPC title