Replicated state management using journal-based registers

Patent metadata

Field	Value
Publication number	US-9971822-B1
Application number	US-201514983237-A
Country	US
Kind code	B1
Filing date	Dec 29, 2015
Priority date	Dec 29, 2015
Publication date	May 15, 2018
Grant date	May 15, 2018

Abstract

A transaction request is received at a journal-based state management system. The transaction request includes a register processing section indicating an operation to be performed at a journal register allocated to the transaction submitter to store state information of an application. Based on the results of a conflict detection operation performed with respect to the transaction request and on the result of the operation on the journal register, the transaction request is accepted for commit. The value of the journal register is stored at a node of the state management system and provided to the transaction submitter.

First claim

What is claimed is:

1. A journal-based state management system comprising a plurality of nodes, wherein individual ones of the plurality of nodes are implemented at one or more computing devices;
wherein the plurality of nodes are configured to:
allocate a plurality of journal registers to a group of one or more transaction submitters, wherein a first journal register of the plurality of journal registers comprises a data object represented in a replicated state machine of an application associated with the group, and wherein the first journal register is materialized at one or more nodes of the plurality of nodes;
receive a transaction request from a particular transaction submitter of the group, wherein the transaction request indicates (a) a read set of a proposed transaction, (b) a write set of the proposed transaction and (c) a register processing section, wherein the register processing section includes an update operation directed to the first journal register;
determine, based at least in part on one or more of: (a) a result of a conflict detection operation with respect to the read set and one or more committed transaction entries stored previously at one or more nodes of the plurality of nodes, or (b) a result of the update operation, that the transaction request is accepted for commit;
store, at one or more nodes of the plurality of nodes, a value assigned to the first journal register by the update operation;
store, at one or more nodes of the plurality of nodes, a new committed transaction entry corresponding to the first transaction request, wherein the new committed transaction entry includes an indication of the write set; and
provide, to the particular transaction submitter, the value assigned to the first journal register by the update operation.

2. The journal-based state management system as recited in claim 1 , wherein the register processing section is formatted in a register manipulation language, wherein the register manipulation language does not support one or more of: (a) loop instructions or (b) function calls.

3. The journal-based state management system as recited in claim 1 , wherein the plurality of nodes are configured to:
prior to providing the value assigned to the first journal register to the transaction submitter, verify that the new committed transaction entry has been replicated at a selected plurality of replication nodes of a directed acyclic graph of replication nodes.

4. The journal-based state management system as recited in claim 1 , wherein the plurality of nodes are configured to:
receive a second transaction request indicating (a) a second read set of a second proposed transaction and (b) a second register processing section;
determine, using the second read set and a second set of one or more committed transaction entries stored previously, that the second proposed transaction does not have a read-write conflict with respect to previously-committed transactions; and
abort the second proposed transaction based at least in part on a result of a particular operation indicated in the second register processing section.

5. The journal-based state management system as recited in claim 1 , wherein a particular node of the plurality of nodes comprises an execution engine, wherein the register processing section comprises an executable version of one or more register commands, wherein the executable version is obtained at the particular transaction submitter using a compiler, and wherein the particular node is configured to:
execute at least a portion of the register processing section using the execution engine to obtain the result of the update command.

6. A method, comprising:
performing, by one or more nodes of a journal-based state management system, wherein individual ones of the one or more nodes are implemented at one or more computing devices:
receiving a transaction request from a particular transaction submitter of the journal-based state management system, wherein the transaction request indicates a register processing section, wherein the register processing section includes an operation directed to a first journal register allocated to at least the particular transaction submitter, wherein the first journal register comprises a data object represented in a replicated state machine of an application associated with the particular transaction submitter;
determining, based at least in part on one or more of: (a) a result of a conflict detection operation performed with respect to the transaction request, or (b) a result of the operation directed to the first journal register, that the transaction request is accepted for commit;
storing, at a particular node of the one or more nodes, a value of the first journal register obtained after the operation directed to the first journal register has been completed; and
providing, to the particular transaction submitter, the value of the first journal register.

7. The method as recited in claim 6 , wherein the register processing section is formatted in a register manipulation language defined by the journal-based state management system, wherein the register manipulation language does not support one or more of: (a) loop instructions or (b) function calls.

8. The method as recited in claim 6 , wherein the register processing section is formatted in a context-free language corresponding to a particular pushdown automaton.

9. The method as recited in claim 6 , wherein the operation directed to the first journal register is represented using byte code in the register processing section, wherein the register processing section includes an intrinsic function, further comprising:
obtaining, at a particular computing device of the one or more computing devices, a result of the intrinsic function using one or more instructions of a native instruction set, wherein said determining that the transaction request is accepted for commit is based at least in part on the result of the intrinsic function.

10. The method as recited in claim 6 , wherein the transaction request includes a read set, and wherein the conflict detection operation comprises determining whether a write set of a committed transaction for which a committed transaction entry has been stored at the journal-based state management system conflicts with the read set.

11. The method as recited in claim 6 , wherein the transaction request includes a particular required transaction signature, and wherein said determining that the transaction request is accepted for commit is based at least in part on verifying that a committed transaction entry with the particular required transaction signature has been stored at the journal-based state management system.

12. The method as recited in claim 6 , wherein the transaction request includes a particular forbidden transaction signature, and wherein said determining that the that the transaction request is accepted for commit is based at least in part on verifying that a committed transaction entry with the particular forbidden transaction signature has not been stored at the journal-based state management system.

13. The method as recited in claim 6 , further comprising performing, by the one or more nodes:
assigning, to a group of one or more transaction submitters including the particular transaction submitter, a particular logical partition of a replicated journal to store committed transaction entries of the group, wherein the particular logical partition has an associated register namespace which includes an identifier of the first journal register.

14. The method as recited in claim 6 , wherein said providing the value of the first j

Assignees

• Amazon Tech Inc

Inventors

• Deardeuff Michael Benjamin
• Cole Timothy Daniel
• Freshwater Aaron Gifford
• Vermeulen Allan Henry

Classifications

• G06F17/30191

  Physics · mapped topic

• G06F17/30575 Primary

  Physics · mapped topic

• G06F9/467

  Transactional memory (G06F9/528 takes precedence) · CPC title

• G06F9/466

  Transaction processing · CPC title

• G06F16/1815 Primary

  Journaling file systems · CPC title