Proactive state change acceptability verification in journal-based storage systems

Patent metadata

Field	Value
Publication number	US-10324905-B1
Application number	US-201514833009-A
Country	US
Kind code	B1
Filing date	Aug 21, 2015
Priority date	Aug 21, 2015
Publication date	Jun 18, 2019
Grant date	Jun 18, 2019

Abstract

A particular node of a journal-based multi-node distributed storage system requests the addition of an acceptability verification request entry to the journal, indicating a proposed state change of the system. The particular node examines contents of entries added to the journal after the acceptability verification request entry. After determining that a targeted set of acceptability verification response entries have been added to the journal, indicating that the potential state change meets acceptance criteria at respective other nodes of the system, the particular node requests an addition of a committed transaction entry to the journal, indicating an approval of the proposed state change.

First claim

What is claimed is:

1. A method, comprising:
appending, to a journal of a multi-data-store database by a journal manager implemented at one or more computing devices, a first acceptability verification request entry, wherein the first acceptability verification request entry indicates one or more potential state changes of the multi-data-store database submitted to the journal manager by a client-side component, wherein the journal includes one or more committed transaction entries indicating respective approved state changes of the multi-data-store database, and wherein the multi-data-store database comprises a plurality of data stores, including a first data store with a first data store manager implemented at one or more computing devices;
determining, by the first data store manager, based at least in part on examining contents of the first acceptability verification request obtained from the journal, and without applying the one or more potential state changes at the first data store, that the one or more potential state changes meet an acceptance criterion associated with processing state changes at the first data store;
appending, by the journal manager to the journal, a first acceptability verification response entry indicating a positive response to the first acceptability verification request, wherein the positive response is received from the first data store manager;
confirming, by the client-side component, that the journal includes a targeted set of acceptability verification response entries with respective positive responses to the first acceptability verification request;
transmitting, by the client-side component to the journal manager after said confirming, a transaction request to commit the one or more potential state changes;
appending, by the journal manager based at least in part on a result of a commit analysis of the transaction request, a new committed transaction entry indicating that the one or more potential state changes have been approved; and
applying, by the first data store manager, one or more writes indicated in the new committed transaction entry.

2. The method as recited in claim 1 , wherein the one or more proposed state changes correspond to a new proposed version of a journal schema of the multi-data-store database, wherein the journal schema includes an indication of one or more of (a) a data-store-independent transaction language, or (b) a set of attributes of a data object which is materialized at least in part at the first data store.

3. The method as recited in claim 2 , wherein said determining that the one or more proposed state changes meet the acceptance criterion comprises verifying that the new proposed version of the journal schema is compatible with a concrete schema of the first data store.

4. The method as recited in claim 1 , further comprising:
appending, by the journal manager on behalf of the client-side component, a second acceptability verification request entry into the journal, wherein the second acceptability verification request entry indicates another potential state change, and wherein the second acceptability verification request indicates a validity period; and
detecting, by the client-side component that a second acceptability verification response entry corresponding to the second acceptability verification request has not been added to the journal on behalf of the first data store manager prior to an expiration of the validity period; and
determining, by the client-side component in response to said detecting, that a transaction request indicating the other proposed state change is not to be submitted to the journal manager.

5. The method as recited in claim 1 , wherein individual ones of entries of the journal comprise a sequence number indicative of an order in which the entries were added to the journal, wherein the first acceptability verification request entry has a particular sequence number, further comprising performing, by the first data store manager:
updating, during a sequential traversal of the journal entries in sequence number order, a processing progress marker to indicate the highest sequence number for which processing of the corresponding journal entry has been completed; and
determining, in response to encountering the first acceptability verification request entry during the sequential traversal, the particular sequence number of the first acceptability verification request entry; and
prior to determining whether the one or more potential state changes meet the acceptance criterion, setting the processing progress marker to the particular sequence number.

6. A distributed system comprising:
a plurality of nodes implemented at respective sets of one or more computing devices comprising one or more processors and memory, wherein the plurality of nodes include:
a first node configured to:
initiate an addition of an acceptability verification request entry to a journal of the distributed system, wherein the acceptability verification request entry indicates one or more proposed rules for representing state change requests associated with a state machine of the distributed system; and
after determining that a targeted set of acceptability verification response entries indicating that the one or more proposed rules meet respective acceptance criteria for processing state change requests at respective nodes of the plurality of nodes have been added to the journal, initiate an addition of a committed transaction entry indicating the one or more proposed rules to the journal; and

a second node configured to:
initiate an addition of an acceptability verification response entry to the journal indicating whether the one or more proposed rules meet an acceptance criterion for processing state change requests at the second node; and
in response to examining the committed transaction entry, perform one or more write operations indicated in the committed transaction entry.

7. The distributed system as recited in claim 6 , wherein the first node comprises a client-side component of a multi-data-store storage system, wherein the second node comprises a data store manager of a particular member data store of the multi-data-store storage system.

8. The distributed system as recited in claim 7 , wherein the one or more proposed rules correspond to a new proposed version of a journal schema of the multi-data-store storage system, wherein the journal schema includes an indication of one or more of (a) a data-store-independent transaction language, or (b) a set of attributes of a data object which is materialized at least in part at the particular member data store.

9. The distributed system as recited in claim 8 , wherein to determine whether the one or more proposed rules meet an acceptance criterion for processing state change requests at the second node, the data store manager is configured to check whether the new proposed version of the journal schema is compatible with a concrete schema of the particular member data store.

10. The distributed system as recited in claim 6 , wherein the targeted set of acceptability verification response entries includes a respective acceptability verification response entry from each node of a selected set of nodes of the distributed system, wherein the selected set includes the second node.

11. The distributed system as recited in claim 10 , wherein at least a respective portion of a database whose state changes are managed using the journal is materialized at individual ones of the selected set of nodes.

12. The distributed system as recited in claim 6 , wherein the plurality of nodes includes a third node, wherein the acceptability verification reques

Assignees

• Amazon Tech Inc

Inventors

• Ross Andrew Wayne
• Danilov Artem
• Cole Timothy Daniel
• Certain Tate Andrew
• Jacques De Kadt Christopher Richard
• Morkel John Michael
• Vermeulen Allan Henry

Classifications

• G06F16/1805 Primary

  Append-only file systems, e.g. using logs or journals to store data · CPC title

• G06F16/1865

  Transactional file systems · CPC title

• G06F16/23

  Updating · CPC title

• G06F16/284

  Relational databases · CPC title

• G06F16/283

  Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP · CPC title