Atomically moving data elements between or within linked data structures

• US 9,910,907 B2
• Filed: 01/29/2015
• Issued: 03/06/2018
• Est. Priority Date: 01/29/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Glasser, Dara J
• Application Number:
  US14/608,469
• Publication Number:
  US 20160224608A1
• Time in Patent Office: 1,132 Days
• CPC Class Codes: G06F 16/2336 Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

A data element of a linked data structure is atomically moved without delaying lockless readers. A status-indicating entity is allocated, associated with the data element, and indicates validity of the data element with respect to the first linked data structure. A copy element, or a pointer thereto, is created from the data element. The status-indicating entity is associated with the copy element and indicates no validity of the copy element with respect to a second linked data structure. The copy element is linked to the second linked data structure. The status-indicating entity is atomically updated to indicate no validity of the data element with respect to the first linked data structure and validity of the copy element with respect to the second linked data structure. The data element is deleted and the status-indicating entity is disassociated from the copy element. Both structures may be deallocated in a deferred reader-friendly manner.

Claims

1. A system, comprising:

one or more processors;

a memory coupled to said one or more processors, said memory including a computer usable medium storing at least one program of instructions executable by said processor to perform operations for atomically moving a data element of a linked data structure without delaying lockless readers that reference said data element without using locks, said operations comprising;

allocating a status-indicating entity if one does not already exist and associating it with said data element in a manner that allows said status-indicating entity to be referenced from said data element by said lockless readers, said data element being linked to a first linked data structure that said lockless readers can traverse in order to reference said data element;

copying said data element, or a pointer thereto, to create a copy element that is to be linked to a second linked data structure;

associating said status-indicating entity with said copy element in a manner that allows said status-indicating entity to be referenced from said copy element by said lockless readers;

linking said copy element to said second linked data structure that said lockless readers can traverse in order to reference said copy element;

said status-indicating entity initially indicating to said lockless readers that said data element has validity with respect to said first linked data structure and said copy element has no validity with respect to said second linked data structure;

atomically updating said status-indicating entity to indicate to said lockless readers that said data element has no validity with respect to said first linked data structure and said copy element has validity with respect to said second linked data structure;

deleting said data element from said first linked data structure and deallocating it in a deferred manner that guarantees none of said lockless readers will be referencing said data element at the time of deallocation; and

disassociating said status-indicating entity from said copy element, and if no longer needed, deallocating it in a deferred manner that guarantees none of said lockless readers will be referencing said status-indicating entity at the time of deallocation.

2. The system of claim 1, wherein said first linked data structure and said second linked data structure are different linked data structures or they are the same linked data structure, and wherein:

if said first linked data structure and said second linked data structure are different, said operations are performed without modifying said copy element such that the effect of said operations is to atomically move said data element between different linked data structures; and

if said first linked data structure and said second linked data structure are the same, said operations includes modifying said copy element such that the effect of said operations is to atomically update said data element within the same linked data structure.

3. The system of claim 1, wherein said status-indicating entity comprises either (1) an existence group structure that indicates whether a data element exists in a linked data structure, or (2) an allegiance structure that indicates whether a data element has allegiance to a linked data structure.

4. The system of claim 3, wherein:

said status-indicating entity comprises said existence group structure, said existence group structure having an outgoing existence structure referenced by said data element and an incoming existence structure referenced by said copy element;

said outgoing existence structure initially indicating existence and said incoming existence structure initially indicating non-existence; and

said atomic updating of said status-indicating entity comprises switching said existence group structure so that said outgoing existence structure indicates non-existence and said incoming existence structure indicates existence.

5. The system of claim 4, wherein switching said existence group structure comprises atomically updating an existence switch, and wherein:

said existence switch is referenced by said outgoing existence structure and said incoming existence structure;

said existence switch selectively references one of two or more existence arrays, said existence arrays comprising array elements that each store an existence indicator that indicates existence or non-existence;

said outgoing existence structure and said incoming existence structure each store an array offset value identifying an offset position in said existence arrays;

said existence switch is atomically updated to change its reference from a first one of said existence arrays to a second one of said existence arrays; and

said first and second existence arrays store different existence indicators at their array offset positions, such that atomically updating said existence switch to change its reference between said first and second existence arrays results in a change in existence status of said data element and said copy element according to said array offset values stored in their respective outgoing existence structure and incoming existence structure.

6. The system of claim 3, wherein:

said status-indicating entity comprises said allegiance structure, said allegiance structure embodying an allegiance switch that selectively establishes allegiance to said first linked data structure and said second linked data structure;

said atomic updating of said status-indicating entity comprises atomically updating said allegiance switch to change its allegiance from said first linked data structure to said second linked data structure; and

said allegiance switch being either directly or indirectly referenced by said data element and said copy element.

7. The system of claim 6, wherein:

said allegiance switch is indirectly referenced by said data element and said copy element via respective allegiance/offset structures that each store a pointer to said allegiance switch and store an array offset value;

said allegiance switch establishes allegiance to said first linked data structure and said second linked data structure by selectively referencing either (1) two or more allegiance status arrays or (2) two or more existence arrays;

said allegiance switch is atomically updated to either (1) change its reference from a first one of said allegiance status arrays to a second one of said allegiance status arrays or (2) change its reference from a first one of said existence arrays to a second one of said existence arrays;

said first and second allegiance status arrays store pointers at their array offset positions that respectively reference said first linked data structure and said second linked data structure, such that atomically updating said allegiance switch to change its reference between said first and second allegiance status arrays results in a change in allegiance of said data element and said copy element according to the array offset values stored in their respective allegiance/offset structures; and

said first and second existence arrays store existence indicators at their array offset positions, such that atomically updating said allegiance switch to change its reference between said first and second existence arrays results in a change in allegiance of said data element and said copy element according to said array offset values stored in their respective allegiance/offset structures.

8. A computer program product, comprising:

one or more computer-readable storage media;

program instructions stored on said one or more storage media for programming a data processing platform having one or more processors operatively coupled to a memory to perform operations for atomically moving a data element of a linked data structure without delaying lockless readers that reference said data element without using locks, said operations comprising;

allocating a status-indicating entity if one does not already exist and associating it with said data element in a manner that allows said status-indicating entity to be referenced from said data element by said lockless readers, said data element being linked to a first linked data structure that said lockless readers can traverse in order to reference said data element;

copying said data element, or a pointer thereto, to create a copy element that is to be linked to a second linked data structure;

associating said status-indicating entity with said copy element in a manner that allows said status-indicating entity to be referenced from said copy element by said lockless readers;

linking said copy element to said second linked data structure that said lockless readers can traverse in order to reference said copy element;

said status-indicating entity initially indicating to said lockless readers that said data element has validity with respect to said first linked data structure and said copy element has no validity with respect to said second linked data structure;

atomically updating said status-indicating entity to indicate to said lockless readers that said data element has no validity with respect to said first linked data structure and said copy element has validity with respect to said second linked data structure;

deleting said data element from said first linked data structure and deallocating it in a deferred manner that guarantees none of said lockless readers will be referencing said data element at the time of deallocation; and

disassociating said status-indicating entity from said copy element, and if no longer needed, deallocating it in a deferred manner that guarantees none of said lockless readers will be referencing said status-indicating entity at the time of deallocation.

9. The computer program product of claim 8, wherein said first linked data structure and said second linked data structure are different linked data structures or they are the same linked data structure, and wherein:

if said first linked data structure and said second linked data structure are different, said operations are performed without modifying said copy element such that the effect of said operations is to atomically move said data element between different linked data structures; and

if said first linked data structure and said second linked data structure are the same, said operations includes modifying said copy element such that the effect of said operations is to atomically update said data element within the same linked data structure.

10. The computer program product of claim 8, wherein:

said status-indicating entity comprises an existence group structure that indicates whether a data element exists in a linked data structure;

said existence group structure having an outgoing existence structure referenced by said data element and an incoming existence structure referenced by said copy element;

said outgoing existence structure initially indicating existence and said incoming existence structure initially indicating non-existence; and

said atomic updating of said status-indicating entity comprises switching said existence group structure so that said outgoing existence structure indicates non-existence and said incoming existence structure indicates existence.

11. The computer program product of claim 10, wherein switching said existence group structure comprises atomically updating an existence switch, and wherein:

said existence switch is referenced by said outgoing existence structure and said incoming existence structure;

said existence switch selectively references one of two or more existence arrays, said existence arrays comprising array elements that each store an existence indicator that indicates existence or non-existence;

said outgoing existence structure and said incoming existence structure each store an array offset value identifying an offset position in said existence arrays;

said existence switch is atomically updated to change its reference from a first one of said existence arrays to a second one of said existence arrays; and

said first and second existence arrays store different existence indicators at their array offset positions, such that atomically updating said existence switch to change its reference between said first and second existence arrays results in a change in existence status of said data element and said copy element according to said array offset values stored in their respective outgoing existence structure and incoming existence structure.

12. The computer program product of claim 8, wherein:

said status-indicating entity comprises an allegiance structure that indicates whether a data element has allegiance to a linked data structure;

said allegiance structure embodying an allegiance switch that selectively establishes allegiance to said first linked data structure and said second linked data structure;

said atomic updating of said status-indicating entity comprises atomically updating said allegiance switch to change its allegiance from said first linked data structure to said second linked data structure; and

said allegiance switch being either directly or indirectly referenced by said data element and said copy element.

13. The computer program product of claim 12, wherein:

said allegiance switch is indirectly referenced by said data element and said copy element via respective allegiance/offset structures that each store a pointer to said allegiance switch and store an array offset value;

said allegiance switch establishes allegiance to said first linked data structure and said second linked data structure by selectively referencing either (1) two or more allegiance status arrays or (2) two or more existence arrays;

said allegiance switch is atomically updated to either (1) change its reference from a first one of said allegiance status arrays to a second one of said allegiance status arrays or (2) change its reference from a first one of said existence arrays to a second one of said existence arrays;

said first and second allegiance status arrays store pointers at their array offset positions that reference said allegiance/offset structures of said first linked data structure and said second linked data structure, such that atomically updating said allegiance switch to change its reference between said first and second allegiance status arrays results in a change in allegiance of said data element and said copy element according to the array offset values stored in their respective allegiance/offset structures; and

said first and second existence arrays store existence indicators at their array offset positions, such that atomically updating said allegiance switch to change its reference between said first and second existence arrays results in a change in allegiance of said data element and said copy element according to said array offset values stored in their respective allegiance/offset structures.