US 10,649,976 B1Granted

Using a global sequence number for replicating mutating data

AssigneeAmazon Technologies, Inc.

InventorsAlazel Acheson, Christopher Andrew Stephens, Seth William Markle, Subhakanta Kar

Life of this patent

Estimating the term…

Loading patent…

Abstract

Routing data is copied from a primary data store to a local data store of a computing device. As the routing data is being copied by the computing device, changes to the data continue to occur. After copying all or a portion of the data, the computing device uses a value of a global sequence number (GSN) to determine if mutations have been made to the primary data. The routing data in the local data store is not consistent with the routing data stored in the primary data store when the value of the GSN is larger after the copying of the routing data as compared to the initial value of the GSN when the copying started. When changes have been made to the data, the computing device integrates the changes into the local data store before beginning routing operations.

Claims20

Dependent claims

A computer-implemented method, comprising:

accessing, from a first computing device within a network, a data store of a second computing device within the network, the data store including routing data that includes routing instructions indicating how to route data within the network;
determining, from a global sequence number (GSN), a first value that identifies a number of mutations to the routing data, wherein the GSN is updated for individual changes to the routing data;
obtaining, from the data store of the second computing device during a first time period, a first portion of the routing data, the first portion of the routing data including a first number of records;
storing the first portion of the routing data within a local data store of the first computing device;
determining a second value of the GSN that identifies a current number of mutations to the routing data after obtaining the first portion of the routing data;
determining that the first value is not equal to the second value;
obtaining changes made to the routing data;
applying the changes to the first portion of the routing data stored within the local data store of the first computing device;
determining a third value of the GSN;
determining that the second value is equal to the third value;
determining that the first portion of the routing data stored within the local data store of the first computing device is consistent with the routing data stored within the data store of the second computing device;
and
at least in response to determining that the first portion of the routing data stored within the local data store of the first computing device is consistent with the routing data stored within the data store of the second computing device, utilizing the first computing device in addition to the second computing device to perform routing operations using the routing data stored within the local data store of the first computing device and the routing data stored within the data store of the second computing device.

10 more elements

A system, comprising:

a first computing device executing within a network, the first computing device performing operations to store data in a first data store, the data including records utilized by a plurality of computing devices within the network to perform a service, wherein the plurality of computing devices includes the first computing device;
and
a second computing device executing within the network, the second computing device performing operations to:
determine, at a first time, a first value associated with a number of mutations to the data within the first data store,
obtain, from the first data store during a first time period, a first portion of the data, the first portion of the data including a first number of records,
store the first portion of the data within a second data store that is local to the second computing device,
determine a second value associated with a number of the mutations to the data within the first data store at a second time,
compare the first value to the second value,
obtain changes made to the first data store during the first time period based, at least in part, on the comparison,
apply the changes to the first portion of the data stored within the second data store, and
utilize the second computing device in addition to the first computing device to perform computer operations associated with the service using at least a portion of the data stored within the first data store and the first portion of the data stored within the second data store.

8 more elements

A non-transitory computer-readable storage medium having computer-executable instructions stored thereupon which, when executed by a computer, cause the computer to:

determine a first value associated with a number of mutations to data stored within a first data store at a first time, the first data store external to the computer and wherein the data includes records utilized by a plurality of computing devices within a service provider network to perform a service;
obtain, from the first data store during a first time period, a first portion of the data, the first portion of the data including a first number of records;
store the first portion of the data within a second data store local to the computer;
determine a second value associated with a number of the mutations to the data within the first data store at a second time;
compare the first value to the second value;
obtain changes made to the first data store at least during the first time period based, at least in part, on the comparison;
apply the changes to the first portion of the data stored within the second data store;
and
utilize the first portion of the data stored within the second data store in addition to the data stored within the first data store to perform one or more computer operations associated with the service.

6 more elements

Dependencies are inferred from the claim text.