Concurrent reads and inserts into a data structure without latching or waiting by readers

Patent metadata

Field	Value
Publication number	US-10108653-B2
Application number	US-201514671664-A
Country	US
Kind code	B2
Filing date	Mar 27, 2015
Priority date	Mar 27, 2015
Publication date	Oct 23, 2018
Grant date	Oct 23, 2018

Abstract

A method includes performing, by a data structure processor, concurrent read and write operations into a hierarchical data structure. Writers acquire latches on the hierarchical data structure elements that the latches modify. The hierarchical data structure elements are directly accessed by readers without acquiring latches. A modify operation is executed by a writer for one or more levels of the hierarchical data structure. When removed portions of the hierarchical data structure are no longer referenced, tracking is performed by use of a combination of a global state value and a copied local state value. The global state value transitions through a non-repeating sequence of values. No longer referenced portions of the hierarchical data structure are tagged with the current global state value.

First claim

What is claimed is:

1. A method comprising:
performing, by a data structure processor, concurrent read and write operations into a hierarchical data structure;
acquiring latches, by writers, on the hierarchical data structure elements that the writers modify;
directly accessing the hierarchical data structure elements by readers without acquiring latches;
executing a modify operation by a writer for one or more levels of the hierarchical data structure, wherein the modify operation comprises performing a lookup into a parent node for determining a child node to modify, the child node including a linked list, and the modify inserts new entries to the linked list by atomically modifying linked list next pointers; and
tracking when removed portions of the hierarchical data structure are no longer referenced by use of a combination of a global state value and a local copy of the global state value;
wherein:
the global state value transitions through a non-repeating sequence of values;
no longer referenced portions of the hierarchical data structure are tagged with the global state value captured after last reference removed; and
the hierarchical data structure comprises a mutable tier including extendible hashing, a hash table, and an immutable tier including a concise hash table (CHT) bitmap.

2. The method of claim 1 , wherein the modify operation comprises instructions for:
forming a new child node of the parent node if there is insufficient space for modifying a full child node; and
inserting the new child node in the node chain for the child node.

3. The method of claim 2 , wherein inserting of the first new child node comprises atomically adding the new child node to the node chain when the node chain is unchanged since starting the lookup, and directly performing a modify on the first new child node using a reader-wait-free protocol.

4. The method of claim 3 , further comprising:
exiting execution for the modify operation for an on-going merge on the partition on another modify operation or if merging on the partition is unnecessary;
creating a second new child node sized for holding data from a set of child nodes;
merging the set of child nodes into the second new child node; and
updating the node chain by replacing merged nodes with the second new child node.

5. The method of claim 1 , further comprising:
maintaining the global state value by periodic update using timer signals or driven during read and modify actions comprising incrementing a counter or capture of a system time value.

6. The method of claim 1 , further comprising:
maintaining the local state value that is periodically updated by copying the global state value before any forming any references to entries within the hierarchical data structure and clearing the local state value when no operation is in progress locally; wherein the hierarchical data structure further comprises CHT leaf page.

7. The method of claim 6 , further comprising:
reclaiming space by freeing the no longer referenced portions of the hierarchical data structure after all operations have a local state value that occurs later in the sequence than the tagged value for the portion to be reclaimed.

8. The method of claim 1 , wherein:
modify operations that are restricted to a single hierarchical data structure element are performed directly; and
modify operations that split an original hierarchical data structure element into two or more hierarchical data structure elements are performed by forming separate split hierarchical data structure elements, and leaving the original hierarchical data structure element unchanged for access by any concurrent readers.

9. A computer program product for concurrent read and write operations for hierarchical data structure elements, the computer program product comprising a non-transitory computer readable storage medium having program code embodied therewith, the program code executable by a processor to:
perform, by the processor, concurrent read and write operations into a hierarchical data structure;
acquire, by writers, latches on the hierarchical data structure elements that the writers modify;
directly access, by the processor, the hierarchical data structure elements by readers without acquiring latches;
execute, by the processor, a modify operation by a writer for one or more levels of the hierarchical data structure, wherein the modify operation comprises performing a lookup into a parent node for determining a child node to modify, the child node including a linked list, and the modify inserts new entries to the linked list by atomically modifying linked list next pointers,
track, by the processor, when removed portions of the hierarchical data structure are no longer referenced by use of a combination of a global state value and a copied local state value;
wherein:
the global state value transitions through a non-repeating sequence of values;
no longer referenced portions of the hierarchical data structure are tagged with the current global state value; and
the hierarchical data structure comprises a mutable tier including extendible hashing, a hash table, and an immutable tier including a concise hash table (CHT) bitmap.

10. The computer program product of claim 9 , wherein the modify operation comprises program code executable by the processor to:
determining a partition to modify;
form a first new child node of the parent node if there is insufficient space for modifying a full child node; and
insert the first new child node before the full child node in a node chain.

11. The computer program product of claim 10 , wherein inserting of the first new child node comprises atomically adding the first new child node first to the node chain when the node chain is unchanged since starting the lookup, and directly performing a modify on the first new child node using a reader-wait-free protocol.

12. The computer program product of claim 11 , further comprising program code executable by the processor to:
exit execution for the modify operation for an on-going merge on the partition on another modify operation or if merging on the partition is unnecessary;
create a second new child node sized for holding data from a set of child nodes;
merge the set of child nodes into the second new child node; and
update the node chain by replacing merged nodes with the second new child node.

13. The computer program product of claim 9 , further comprising program code executable by the processor to:
maintain the global state value by periodic update using timer signals comprising incrementing a counter or capture of a system time value.

14. The computer program product of claim 9 , further comprising program code executable by the processor to:
maintain the local state value that is periodically updated by copying the global state value before any caching of pointers to entries within the hierarchical data structure and clearing the local state value when no operation is in progress locally, wherein the hierarchical data structure further comprises a CHT leaf page.

15. The computer program product of claim 14 , further comprising program code executable by the processor to:
reclaim space by freeing the no longer referenced portions of the hierarchical data structure after all operations have a local state value that exceeds the value of the recorded global state value for the portion to be reclaimed.

16. The computer program product of claim 9 , wherein:
writer operations that are restricted to a single hierarchical data structure element are performed directly; and
wri

Assignees

• IBM

Inventors

• Barber Ronald J
• Leis Viktor
• Lohman Guy M
• Raman Vijayshankar
• Sidle Richard S

Classifications

• G06F17/30097

  Physics · mapped topic

• G06F17/30194

  Physics · mapped topic

• G06F17/30359 Primary

  Physics · mapped topic

• G06F16/2315

  Optimistic concurrency control · CPC title

• G06F16/137

  Hash-based (content-based indexing of textual data G06F16/31) · CPC title