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

• US 10,108,653 B2
• Filed: 03/27/2015
• Issued: 10/23/2018
• Est. Priority Date: 03/27/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Barber, Ronald J., Leis, Viktor, Lohman, Guy M., Raman, Vijayshankar, Sidle, Richard S.
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US14/671,664
• Publication Number:
  US 20160283540A1
• Time in Patent Office: 1,306 Days
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/2336 Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps

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.

Claims

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

writer 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.

17. A system comprising:

a data structure processor configured for performing concurrent read and write operations into a hierarchical data structure, and track 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 writers acquire latches on the hierarchical data structure elements that the writers modify, and the hierarchical data structure elements are directly accessed by readers without acquiring latches; and

a thread processor configured for 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,

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.

18. The system of claim 17, wherein the modify operation comprises instructions executed by the thread processor for:

determining a partition to modify;

forming a first new child node of the parent node if there is insufficient space for modifying a full child node; and

inserting the first new child node before the full child node in a node chain by 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.

19. The system of claim 18, wherein:

the thread processor is further configured for 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; and

the data structure processor is further configured for 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.

20. The system of claim 19, further comprising:

an epoch processor that is configured for maintaining the global state value by periodic update using timer signals comprising incrementing a counter or capture of a system time value, maintaining 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 thread processor is configured for reclaiming 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, and the hierarchical data structure further comprises a CHT leaf page.