METHOD AND SYSTEM FOR EFFICIENTLY REPLICATING DATA IN NON-RELATIONAL DATABASES
First Claim
1. A method of replicating data for a distributed database between a plurality of instances, each instance comprising one or more server computers with memory and one or more processors, the method comprising:
- identifying a first instance of the distributed database at a first geographic location;
identifying a second instance of the distributed database at a second geographic location;
tracking changes to the distributed database at the first instance by storing deltas, each delta having a row identifier that identifies a piece of data modified, a sequence identifier that specifies an order in which the deltas are applied to the data, and an instance identifier that specifies an instance where the delta was created;
determining which deltas are to be sent to the second instance using a second egress map at the first instance, wherein the second egress map specifies which combinations of row identifier and sequence identifier have been acknowledged as received at the second instance;
building a second transmission matrix for the second instance that identifies deltas that have not yet been acknowledged as received at the second instance;
transmitting deltas identified in the second transmission matrix to the second instance;
receiving acknowledgement that transmitted deltas have been incorporated in the second instance; and
updating the second egress map to indicate acknowledged deltas.
2 Assignments
0 Petitions
Accused Products
Abstract
A method replicates data between instances of a distributed database. The method identifies at least two instances of the database at distinct geographic locations. The method tracks changes to the database by storing deltas. Each delta has a row identifier that identifies the piece of data modified, a sequence identifier that specifies the order in which the deltas are applied to the data, and an instance identifier that specifies where the delta was created. The method determines which deltas to send using an egress map that specifies which combinations of row identifier and sequence identifier have been acknowledged as received at other instances. The method builds a transmission matrix that identifies deltas that have not yet been acknowledged as received. The method then transmits deltas identified in the transmission matrix. After receiving acknowledgement that transmitted deltas have been incorporated into databases at other instances, the method updates the egress map.
-
Citations
23 Claims
-
1. A method of replicating data for a distributed database between a plurality of instances, each instance comprising one or more server computers with memory and one or more processors, the method comprising:
-
identifying a first instance of the distributed database at a first geographic location; identifying a second instance of the distributed database at a second geographic location; tracking changes to the distributed database at the first instance by storing deltas, each delta having a row identifier that identifies a piece of data modified, a sequence identifier that specifies an order in which the deltas are applied to the data, and an instance identifier that specifies an instance where the delta was created; determining which deltas are to be sent to the second instance using a second egress map at the first instance, wherein the second egress map specifies which combinations of row identifier and sequence identifier have been acknowledged as received at the second instance; building a second transmission matrix for the second instance that identifies deltas that have not yet been acknowledged as received at the second instance; transmitting deltas identified in the second transmission matrix to the second instance; receiving acknowledgement that transmitted deltas have been incorporated in the second instance; and updating the second egress map to indicate acknowledged deltas. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method of compacting a distributed database having a plurality of instances, wherein each instance stores data on one or more server computers and each server computer has memory and one or more processors, the method comprising:
-
identifying a first instance of the distributed database; selecting a set of one or more row identifiers that identify rows of data in the distributed database, wherein each row in the distributed database has a base value and a set of zero or more deltas, and wherein each delta specifies a change to the base value, includes a sequence identifier that specifies an order in which the deltas are to be applied to the base value, and specifies an instance where the delta was created; selecting a compaction horizon for the selected set of one or more row identifiers, wherein the compaction horizon is a sequence identifier; applying, in sequence, all deltas for the selected set of one or more row identifiers that have sequence identifiers less than or equal to the compaction horizon, to the base value for the corresponding row identifier; and deleting the deltas that have been applied to the base value for the corresponding row identifier. - View Dependent Claims (9, 10)
-
-
11. A method of reading a data item from a distributed database with a plurality of data items, each data item comprising a base value and zero or more deltas that specify modifications to the base value, the method performed by one or more server computers having memory and one or more processors, the method comprising:
-
receiving a request from a client for a specified data item, the request including a row identifier that identifies the data item; reading the base value for the specified data item from the distributed database and storing the base value in memory; reading the deltas for the specified data item, if any, from the distributed database, wherein each delta includes a sequence identifier that specifies an order in which the deltas are to be applied to the base value; applying the deltas to the base value in memory, in sequence, resulting in a current base value stored in memory; and returning the current base value stored in memory to the client.
-
-
12. A server system, comprising a plurality of servers, each server having:
-
one or more processors; memory; and one or more programs stored in the memory for execution by the one or more processors, the one or more programs comprising instructions for; identifying a first instance of the distributed database at a first geographic location; identifying a second instance of the distributed database at a second geographic location; tracking changes to the distributed database at the first instance by storing deltas, each delta having a row identifier that identifies a piece of data modified, a sequence identifier that specifies an order in which the deltas are applied to the data, and an instance identifier that specifies an instance where the delta was created; determining which deltas are to be sent to the second instance using a second egress map at the first instance, wherein the second egress map specifies which combinations of row identifier and sequence identifier have been acknowledged as received at the second instance; building a second transmission matrix for the second instance that identifies deltas that have not yet been acknowledged as received at the second instance; transmitting deltas identified in the second transmission matrix to the second instance; receiving acknowledgement that transmitted deltas have been incorporated in the second instance; and updating the second egress map to indicate acknowledged deltas. - View Dependent Claims (13, 14)
-
-
15. A server system, comprising a plurality of servers, each server having:
-
one or more processors; memory; and one or more programs stored in the memory for execution by the one or more processors, the one or more programs comprising instructions for; identifying a first instance of a distributed database; selecting a set of one or more row identifiers that identify rows of data in the distributed database, wherein each row in the distributed database has a base value and a set of zero or more deltas, and wherein each delta specifies a change to the base value, includes a sequence identifier that specifies an order in which the deltas are to be applied to the base value, and specifies an instance where the delta was created; selecting a compaction horizon for the selected set of one or more row identifiers, wherein the compaction horizon is a sequence identifier; applying, in sequence, all deltas for the selected set of one or more row identifiers that have sequence identifiers less than or equal to the compaction horizon, to the base value for the corresponding row identifier; and deleting the deltas that have been applied to the base value for the corresponding row identifier. - View Dependent Claims (16)
-
-
17. A server system, comprising a plurality of servers, each server having:
-
one or more processors; memory; and one or more programs stored in the memory for execution by the one or more processors, the one or more programs comprising instructions for; receiving a request from a client for a specified data item from a distributed database with a plurality of data items, each data item comprising a base value and zero or more deltas that specify modifications to the base value, wherein the request includes a row identifier that identifies the data item; reading the base value for the specified data item from the distributed database and storing the base value in memory; reading the deltas for the specified data item, if any, from the distributed database, wherein each delta includes a sequence identifier that specifies an order in which the deltas are to be applied to the base value; applying the deltas to the base value in memory, in sequence, resulting in a current base value stored in memory; and returning the current base value stored in memory to the client.
-
-
18. A computer readable storage medium storing one or more programs configured for execution by a server computer system having one or more processors and memory storing one or more programs for execution by the one or more processors, the one or more programs comprising instructions to:
-
identify a first instance of the distributed database at a first geographic location; identify a second instance of the distributed database at a second geographic location; track changes to the distributed database at the first instance by storing deltas, each delta having a row identifier that identifies a piece of data modified, a sequence identifier that specifies an order in which the deltas are applied to the data, and an instance identifier that specifies an instance where the delta was created; determine which deltas are to be sent to the second instance using a second egress map at the first instance, wherein the second egress map specifies which combinations of row identifier and sequence identifier have been acknowledged as received at the second instance; build a second transmission matrix for the second instance that identifies deltas that have not yet been acknowledged as received at the second instance; transmit deltas identified in the second transmission matrix to the second instance; receive acknowledgement that transmitted deltas have been incorporated in the second instance; and update the second egress map to indicate acknowledged deltas. - View Dependent Claims (19, 20)
-
-
21. A computer readable storage medium storing one or more programs configured for execution by a server computer system having one or more processors and memory storing one or more programs for execution by the one or more processors, the one or more programs comprising instructions to:
-
identify a first instance of a distributed database; select a set of one or more row identifiers that identify rows of data in the distributed database, wherein each row in the distributed database has a base value and a set of zero or more deltas, and wherein each delta specifies a change to the base value, includes a sequence identifier that specifies an order in which the deltas are to be applied to the base value, and specifies an instance where the delta was created; select a compaction horizon for the selected set of one or more row identifiers, wherein the compaction horizon is a sequence identifier; apply, in sequence, all deltas for the selected set of one or more row identifiers that have sequence identifiers less than or equal to the compaction horizon, to the base value for the corresponding row identifier; and delete the deltas that have been applied to the base value for the corresponding row identifier. - View Dependent Claims (22)
-
-
23. A computer readable storage medium storing one or more programs configured for execution by a server computer system having one or more processors and memory storing one or more programs for execution by the one or more processors, the one or more programs comprising instructions to:
-
receive a request from a client for a specified data item from a distributed database with a plurality of data items, each data item comprising a base value and zero or more deltas that specify modifications to the base value, wherein the request includes a row identifier that identifies the data item; read the base value for the specified data item from the distributed database and storing the base value in memory; read the deltas for the specified data item, if any, from the distributed database, wherein each delta includes a sequence identifier that specifies an order in which the deltas are to be applied to the base value; apply the deltas to the base value in memory, in sequence, resulting in a current base value stored in memory; and return the current base value stored in memory to the client.
-
Specification