Method and system for efficiently replicating data in non-relational databases

A distributed database system having a plurality of instances, wherein each instance comprises a plurality of servers and each server has:

• 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 from the plurality of instances;
• and
• at the first instance:
• selecting a set of one or more row identifiers that identify rows in the distributed database, wherein each respective row in the distributed database has a respective base value and a respective set of zero or more respective deltas, and wherein each respective delta:
• specifies a change to the respective base value;
• includes a respective sequence identifier that specifies an order in which the respective delta is applied to the respective base value to compute a current value for the respective row;
• and
• specifies a respective instance where the respective delta was created;
• identifying a plurality of other instances of the distributed database, wherein the plurality of other instances are selected from the plurality of instances and each of the other instances is distinct from the first instance;
• selecting a compaction horizon for the selected set of one or more row identifiers, wherein the compaction horizon is a sequence identifier, and wherein the compaction horizon satisfies:
• all deltas that
• (i) were created at the first instance,
• (ii) are for rows corresponding to row identifiers in the selected set of one or more row identifiers, and
• (iii) have sequence identifiers less than or equal to the compaction horizon,
• have been transmitted to and acknowledged by all of the other instances that maintain data for the corresponding row identifiers;
• and
• all deltas that
• (i) were created at instances in the plurality of other instances,
• (ii) are for rows corresponding to row identifiers in the selected set of one or more row identifiers, and
• (iii) have sequence identifiers less than or equal to the compaction horizon,
• have been received at the first instance;
• and
• for each respective row identifier in at least a subset of the selected one or more row identifiers:
• identifying a non-empty set of deltas for the respective row identifier, wherein each of the deltas in the identified non-empty set has a sequence identifier less than or equal to the compaction horizon;
• applying, in sequence, each of the deltas in the identified non-empty set, to the respective base value for the respective row identifier, thereby updating the respective base value with the changes specified by the deltas in the identified set;
• and
• deleting the deltas in the identified non-empty set.

A computer readable storage medium storing one or more programs configured for execution by a distributed database system having a plurality of instances, wherein each instance comprises one or more server computers and each server computer has one or more processors and memory, the one or more programs including instructions to:

• identify a first instance of a distributed database from the plurality of instances;
• select a set of one or more row identifiers that identify rows in the distributed database, wherein each respective row in the distributed database has a respective base value and a respective set of zero or more respective deltas, and wherein each respective delta:
• specifies a change to the respective base value;
• includes a respective sequence identifier that specifies an order in which the respective delta is applied to the respective base value to compute a current value for the respective row;
• and
• specifies a respective instance where the respective delta was created;
• identify a plurality of other instances of the distributed database, wherein the plurality of other instances are selected from the plurality of instances and each of the other instances is distinct from the first instance;
• select a compaction horizon for the selected set of one or more row identifiers, wherein the compaction horizon is a sequence identifier, and wherein the compaction horizon satisfies:
• all deltas that
• (i) were created at the first instance,
• (ii) are for rows corresponding to row identifiers in the selected set of one or more row identifiers, and
• (iii) have sequence identifiers less than or equal to the compaction horizon,
• have been transmitted to and acknowledged by all of the other instances that maintain data for the corresponding row identifiers;
• and
• all deltas that
• (i) were created at instances in the plurality of other instances,
• (ii) are for rows corresponding to row identifiers in the selected set of one or more row identifiers, and
• (iii) have sequence identifiers less than or equal to the compaction horizon,
• have been received at the first instance;
• and
• for each respective row identifier in at least a subset of the selected one or more row identifiers:
• identify a non-empty set of deltas for the respective row identifier, wherein each of the deltas in the identified non-empty set has a sequence identifier less than or equal to the compaction horizon;
• apply, in sequence, each of the deltas in the identified non-empty set, to the respective base value for the respective row identifier, thereby updating the respective base value with the changes specified by the deltas in the identified set;
• and
• delete the deltas in the identified non-empty set.