Latch-free concurrent searching

Patent metadata

Field	Value
Publication number	US-10360206-B2
Application number	US-201415107392-A
Country	US
Kind code	B2
Filing date	Jan 16, 2014
Priority date	Jan 16, 2014
Publication date	Jul 23, 2019
Grant date	Jul 23, 2019

Abstract

Systems and methods associated with latch-free searching are disclosed. One example method includes receiving a key identifying data to be retrieved from a tree-based data structure. The method also includes performing a concurrent, latch-free search of the tree-based data structure until a leaf node is reached. The method also includes validating the leaf node. The method also includes retreading a portion of the search if the leaf node fails validation.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving a key identifying data to be retrieved from a tree-based data structure;
performing a concurrent, latch-free search of the tree-based data structure until a leaf node is reached;
validating the leaf node, wherein validating the leaf node comprises determining whether the leaf node passes validation, and determining whether the leaf node passes validation comprises determining at least one of whether the leaf node has a type that matches a type associated with the tree-based data structure or determining whether the leaf node is associated with the tree-based data structure; and
retreading a portion of the search if the leaf node fails validation.

2. The computer-implemented method of claim 1 , further comprising one or more of providing the data if a determination is made that the leaf node passes validation or modifying the data if a determination is made that the leaf node passes validation.

3. The computer-implemented method of claim 2 , further comprising acquiring a latch associated with the leaf node in a read mode, performing a binary search on the contents of the leaf node based on the key to find the data, and releasing the latch associated with the leaf node.

4. The computer-implemented method of claim 1 , where retreading the portion of the search comprises returning to a traversed node that was previously reached during the search and continuing the search from the traversed node.

5. The computer-implemented method of claim 4 , where the traversed node is a root node of the tree-based data structure and where latches are acquired in read mode when continuing the search.

6. The computer-implemented method of claim 1 , further comprising retreading a portion of the search upon detecting an intermediate node fails a validation test.

7. The computer-implemented method of claim 6 , where a test for validity of the intermediate node is more thorough than a test for validity of a parent of the intermediate node.

8. The computer-implemented method of claim 1 , where the tree-based data structure is organized according to a B-Tree data structure.

9. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer cause the computer to:
concurrently search a tree-based data structure for a leaf node based on a key, where latches are disregarded during the search;
validate the leaf node, wherein validating the leaf node comprises determining whether the leaf node passes validation, and determining whether the leaf node passes validation comprises determining at least one of whether has a type that matches a type associated with the tree-based data structure or determining whether the leaf node is associated with the tree-based data structure; and
re-perform a portion of the search when the leaf node fails validation.

10. The computer-readable medium of claim 9 , wherein the instructions, when executed by the computer, further cause the computer to perform at least one of providing the data if a determination is made that the leaf node passes validation or modifying the data if a determination is made that the leaf node passes validation.

11. The computer-readable medium of claim 9 , wherein the instructions, when executed by the computer, further cause the computer to acquire a latch associated with the leaf node in a read mode, perform a binary search on the contents of the leaf node based on the key to find the data, and release the latch associated with the leaf node.

12. The computer-readable medium of claim 9 , wherein the instructions, when executed by the computer, further cause the computer to, in response to the leaf node failing validation, return to a traversed node that was previously reached during the search and continue the search from the traversed node.

13. The computer-readable medium of claim 12 , wherein the traversed node comprises a root node of the tree-based data structure, and the instructions, when executed by the computer, further cause the computer to acquire latches in a read mode when continuing the search.

14. The computer-readable medium of claim 9 , whereing the tree-based data structure comprises a B-Tree data structure.

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Tucek Joseph
• Lillibridge Mark
• Kuno Harumi
• Graefe Goetz

Classifications

• G06F16/2343 Primary

  Locking methods, e.g. distributed locking or locking implementation details · CPC title

• G06F16/2315 Primary

  Optimistic concurrency control · CPC title

• G06F16/2455

  Query execution · CPC title

• G06F16/9027

  Trees · CPC title