Systems and Methods for Constructing Composable Persistent Data Structures

• US 20160314044A1
• Filed: 01/05/2016
• Published: 10/27/2016
• Est. Priority Date: 04/21/2015
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Izraelevitz, Joseph H., Marathe, Virendra J.
• Granted Patent: US 10,007,581 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/0766 Error or fault reporting or storing
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

A technique referred to as “data structure chronicles” is described that may be used to build strictly failure resilient persistent concurrent data structures. A “chronicle” maintains a persistent history of operations invoked on a persistent data structure that can be replayed to recover the current consistent state of the data structure after a failure. The chronicle technique may also enable composability of data structure operations with the enclosing application. In addition, the chronicle technique is non-blocking, a desirable progress condition for concurrent data structures. A lock free, non-blocking chronicle stack algorithm is described that may outperform a lock-based implementation in the presence of high contention. In addition, a lock free, non-blocking chronicle queue algorithm is described.

Claims

1. A method, comprising:

performing by one or more computing nodes in a system that supports multithreading;

beginning execution of a multithreaded application that comprises a plurality of operations targeting a concurrent data structure implemented in persistent memory, wherein the concurrent data structure is accessible by a plurality of threads of the multithreaded application;

performing, on behalf of one or more threads of the application, one or more operations that target the concurrent data structure, wherein, for at least some of the one or more operations, said performing comprises;

creating an entry in a signal log, wherein the entry represents an invocation of the operation and a state of its response;

persisting the entry in the signal log;

persisting the operation on the concurrent data structure in the persistent memory; and

returning an indication of the state of its response to the thread on whose behalf the operation was performed;

performing, in response to a failure of a computing node on which the multithreaded application is executing, the persistent memory, or a connection between a computing node on which the multithreaded application is executing and the persistent memory, a recovery operation that returns a respective response for each of at least one other operation that targets the concurrent data structure and for which an entry was created in the signal log;

wherein the returned responses of each of the one or more operations and the returned respective responses for each of the at least one other operation collectively represent a consistent state of the data structure.

2. The method of claim 1,

wherein said beginning execution comprises creating a state object for a chronicle list that represents a state of the concurrent data structure;

wherein the method further comprises updating the state object for the chronicle list to reflect one or more changes to the state of the concurrent data structure.

3. The method of claim 2, wherein, for at least some of the one or more operations, said performing further comprises updating, in response to a change in the state of its response, the entry in the signal log to reflect the change in the state of its response.

4. The method of claim 3, wherein said performing one or more operations and said updating the state object are performed substantially in parallel.

5. The method of claim 3, wherein, for at least some of the one or more operations, said performing further comprises flushing the chronicle list from a current state object prior to said persisting the operation, wherein said flushing the chronicle list flushes effects of prior operations before persisting the operation.

6. The method of claim 3, further comprising:

maintaining, in a memory location accessible by at least one of the one or more threads of the application, an indication of a last state object that the at least one thread has seen;

wherein, for at least some of the one or more operations, said performing further comprises;

checking the memory location to determine if a current state object for the operation is the state object as indicated in the memory location;

if the current state object is the state object as indicated in the memory location, performing and persisting the operation without flushing the chronicle list; and

if the current state object is not the state object as indicated in the memory location, flushing the chronicle list from the current state object prior to said performing and persisting the operation.

7. The method of claim 1, wherein said performing a recovery operation comprises, for each operation of the at least one other operation:

determining whether or not the operation was persisted prior to the failure and whether or not its response was returned to the thread on whose behalf the operation was to be performed prior to the failure; and

in response to determining that the operation was not persisted prior to the failure or that its response was not returned to the thread on whose behalf the operation was to be performed prior to the failure, performing one or more of;

persisting the operation on the concurrent data structure in the persistent memory, or returning its response to the thread on whose behalf the operation was to be performed.

8. The method of claim 1, wherein the concurrent data structure is implemented as a stack data structure, and wherein the operation targeting the concurrent data structure is one of a push operation to add an element to the stack or a pop operation to remove an element from the stack.

9. The method of claim 1, wherein the concurrent data structure is implemented as a queue data structure, and wherein the operation targeting the concurrent data structure is one of an enqueue operation to add an element to the queue or a dequeue operation to remove an element from the queue.

10. The method of claim 1, wherein the returned response for each of the one or more operations includes an indication that the operation succeeded and was persisted to the concurrent data structure, and wherein the returned response for each of the least one other operation includes an indication that the operation failed and was not persisted to the concurrent data structure.

11. A system, comprising:

one or more processor cores;

a volatile memory coupled to the one or more processor cores; and

a byte-addressable persistent memory coupled to the one or more processor cores;

wherein the persistent memory stores a concurrent data structure;

wherein the volatile memory stores;

program instructions that when executed on the one or more processor cores cause the one or more processor cores to implement a multithreaded application that invokes a plurality of operations targeting the concurrent data structure; and

program instructions that when executed on the one or more processor cores cause the one or more processor cores to implement a persistent data structure support module;

wherein in response to invocation by a thread of the multithreaded application of an operation targeting the concurrent data structure, the persistent data structure support module is configured to attempt to perform and persist the operation targeting the concurrent data structure and to return a response for the operation to the thread; and

wherein in response to failing to successfully perform and persist the operation targeting the concurrent data structure and to return the response for the operation prior to a failure in the system, the persistent data structure support module is configured to perform a recovery operation that returns a consistent state of the concurrent data structure to the thread.

12. The system of claim 11,

wherein the concurrent data structure comprises a stack, a queue, a linked-list, or a priority queue;

and

wherein the operation targeting the concurrent data structure comprises an operation to add an element to the data structure, to remove an element from the data structure, or to modify an element of the data structure.

13. The system of claim 11, wherein the volatile memory stores program instructions that when executed on the one or more processor cores cause the one or more processor cores to:

implement a state object for a chronicle list that represents a state of the concurrent data structure;

update the state object for the chronicle list to reflect one or more changes to the state of the concurrent data structure; and

flush the chronicle list from a current state object prior to said persisting the operation, wherein said flushing the chronicle list flushes effects of prior operations before persisting the operation.

14. The system of claim 11, wherein the volatile memory stores program instructions that when executed on the one or more processor cores cause the one or more processor cores to:

implement a state object for a chronicle list that represents a state of the concurrent data structure;

update the state object for the chronicle list to reflect one or more changes to the state of the concurrent data structure;

store, in a memory location accessible by at least one thread of the application, an indication of a last state object that the at least one thread has seen;

check the memory location to determine if a current state object for the operation is the state object as indicated in the memory location;

if the current state object is the state object as indicated in the memory location, flush the chronicle list from the current state object prior to said performing and persisting the operation; and

if the current state object is not the state object as indicated in the memory location, perform and persist the operation without flushing the chronicle list.

15. The system of claim 11, wherein, to perform the recovery operation, the persistent data structure support module is configured to:

determine whether or not the operation was persisted prior to the failure and whether or not its response was returned to the thread on whose behalf the operation was to be performed prior to the failure; and

in response to determining that the operation was not persisted prior to the failure or that its response was not returned to the thread on whose behalf the operation was to be performed prior to the failure, perform one or more of;

persist the operation on the concurrent data structure in the persistent memory, or return its response to the thread on whose behalf the operation was to be performed.

16. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

beginning execution of a multithreaded application that comprises a plurality of operations targeting a concurrent data structure implemented in persistent memory, wherein the concurrent data structure is accessible by a plurality of threads of the multithreaded application;

initiating, by a given thread of the application, an operation targeting the concurrent data structure, wherein said initiating comprises storing, in the concurrent data structure, an entry comprising a thread identifier, an operation identifier, and a return field; and

receiving, by the given thread, a response for the operation that represents a consistent view of the concurrent data structure.

17. The non-transitory, computer-readable storage medium of claim 16, wherein the response comprises:

an indication that the operation targeting the concurrent data structure failed and was not persisted to the concurrent data structure;

or

an indication that the operation targeting the concurrent data structure succeeded and was persisted to the concurrent data structure.

18. The non-transitory, computer-readable storage medium of claim 16, wherein the program instructions, when executed on one or more computers, further cause the one or more computers to perform:

implementing a state object for a chronicle list that represents a state of the concurrent data structure;

updating the state object for the chronicle list to reflect changes to the state of the concurrent data structure; and

flushing the chronicle list from a current state object prior to storing the entry in the concurrent data structure, wherein said flushing the chronicle list flushes effects of prior operations before persisting the operation to the concurrent data structure.

19. The non-transitory, computer-readable storage medium of claim 16, wherein the concurrent data structure is implemented as a stack data structure.

20. The non-transitory, computer-readable storage medium of claim 16, wherein the concurrent data structure is implemented as a queue data structure.