Asynchronous consistent snapshots in a distributed system
AssigneeAmazon Technologies, Inc.
InventorEric Andrew Rubin-Smith
Life of this patent
Estimating the term…
Abstract
Disclosed are various embodiments for asynchronously generating consistent snapshots in a distributed system. In one embodiment, a snapshotting agent receives a respective local snapshot for individual processes in a distributed system. The respective local snapshot for a corresponding process includes a corresponding vector clock that comprises respective values indicating respective state changes in the corresponding process and other processes. The snapshotting agent determines whether a collection of the respective local snapshots for the individual processes represents a global consistent snapshot for the distributed system based at least in part on a comparison of the respective values of the corresponding vector clocks.
Claims20
A system, comprising:
- a cloud provider network including a plurality of regions;
- a distributed system having a plurality of processes that are implemented across at least two of the plurality of regions;
- and
- at least one computing device in the cloud provider network configured to at least:
- receive, by a first process of the plurality of processes, a corresponding vector clock from a second process of the plurality of processes, each corresponding vector clock comprising respective values indicating respective state changes in a corresponding process of the plurality of processes and other processes of the plurality of processes, the first process being implemented in a first region of the plurality of regions and the second process being implemented in a second region of the plurality of regions;
- update, by the first process, the corresponding vector clock of the first process using a pairwise maximum of values from the corresponding vector clock received from the second process;
- receive, by a snapshotting agent, a respective local snapshot for individual ones of the plurality of processes, the respective local snapshot for the corresponding process including the corresponding vector clock for the corresponding process, the respective local snapshot being generated by the corresponding process at least partially asynchronously with respect to the snapshotting agent;
- and
- determine, by the snapshotting agent, whether a collection of the respective local snapshots for the individual ones of the plurality of processes represents a global consistent snapshot for the distributed system based at least in part on a comparison of the respective values of the corresponding vector clocks.
A computer-implemented method, comprising:
- receiving, by a snapshotting agent, a respective local snapshot for individual ones of a plurality of processes in a distributed system, the respective local snapshot for a corresponding process of the individual ones of the plurality of processes including a corresponding vector clock that comprises respective values indicating respective state changes in the corresponding process and other processes of the plurality of processes, the respective local snapshot being generated by the corresponding process at least partially asynchronously with respect to the snapshotting agent;
- and
- determining, by the snapshotting agent, whether a collection of the respective local snapshots for the individual ones of the plurality of processes represents a global consistent snapshot for the distributed system based at least in part on a comparison of the respective values of the corresponding vector clocks.
A computer-implemented method, comprising:
- generating a graph representing a collection of most recent local snapshots respectively generated by individual ones of a plurality of processes in a distributed system, the graph including a set of nodes that individually represent a respective local snapshot and a vector clock for a corresponding process, and a set of arcs that individually represent a first local snapshot for a first process happening before a second local snapshot for a second process;
- identifying a first node to remove from the graph when a first node's vector clock has no entry greater than a second node's vector clock, and at least one entry of the first node's vector clock is less than the corresponding entry of the second node's vector clock;
- replacing the first node with a second node that represents a prior local snapshot for a respective process of the first node;
- and
- determining whether the collection of most recent local snapshots corresponding to the graph represents a global consistent snapshot.
Dependencies are inferred from the claim text.