System and method for incremental replication

• US 10,762,102 B2
• Filed: 09/14/2017
• Issued: 09/01/2020
• Est. Priority Date: 06/20/2013
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Landau, Alexander, Wilson, Tim, Ducott, III, Richard Allen
• Primary Examiner(s): Ortiz Ditren, Belix M
• Application Number:
  US15/704,529
• Publication Number:
  US 20180004832A1
• Time in Patent Office: 1,083 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation

Abstract

A method of incrementally replicating investigative analysis data is disclosed along with a system for performing the same. The method and system provide the ability to break a data replication job into multiple “replication chunks” which can be exported and imported separately. By doing so, the method and system can efficiently replicate large numbers of data object changes over an unreliable data network.

Claims

1. A method performed by a computing system comprising one or more processors and storage media storing one or more programs, the one or more programs comprising instructions executed by the one or more processors to perform the method, the method comprising:

receiving, at an importing system, from an exporting system, a plurality of replication chunks of an incremental replication job, wherein a replication chunk of the plurality of replication chunks contains a respective chunk identifier and respective change data;

performing, at the importing system, causality detection between the respective change data in the replication chunk received at the importing system and existing change data at the importing system; and

based at least in part on results of the causality detection, importing the replication chunk of the plurality of replication chunks into the importing system by;

(a) superseding the existing change data already at the importing system with the respective change data in the replication chunk, (b) not superseding the existing change data already at the importing system with the respective change data in the replication chunk, or (c) determining that a concurrency conflict exists between the respective change data in the replication chunk and the existing change data at the importing system.

2. The method of claim 1, wherein the respective chunk identifier for the replication chunk is used by the importing system to determine an order of the replication chunk in a sequence of the plurality of replication chunks that the exporting system has broken the incremental replication job into.

3. The method of claim 1, wherein the performing the causality detection is based, at least in part, on using version vectors for versioning the respective change data in the replication chunk and the existing change data at the importing system, wherein the version vectors are used to determine whether the respective change data in the replication chunk happened after, happened before or neither happened after nor happened before the existing change data at the importing system.

4. The method of claim 3, wherein,

in response to determining that the change data in the replication chunk happened after the existing change data at the importing system, superseding the existing change data at the importing system with the respective change data in the replication chunk;

in response to determining that the change data in the replication chunk happened before the existing change data at the importing system, not superseding the existing change data at the importing system with the respective change data in the replication chunk; and

in response to determining that change data in the replication chunk neither happened before nor happened after the existing change data at the importing system, determining that a concurrently conflict exists between the respective change data in the replication chunk and the existing change data at the importing system.

5. The method of claim 4, wherein in response to resolution of the concurrency conflict, superseding the existing change data at the importing system with results of the resolution of the concurrency conflict.

6. The method of claim 5, wherein resolution of the concurrency conflict is based at least in part on user input provided by a user, the user input selecting one of:

(a) the respective change data in the replication chunk, or (b) the existing change data at the importing system.

19. The method of claim 1, further comprising:

receiving the plurality of replication chunks at the importing system in a first order;

wherein each replication chunk of the plurality of replication chunks has a respective chunk identifier and respective chunk data;

determining a second order of the plurality of replication chunks based on the respective chunk identifiers of the plurality of replication chunks;

wherein the first order is different than the second order; and

performing causality detection at the importing system for each replication chunk of the plurality of replication chunks in the second order of the plurality of replication chunks.

7. One or more non-transitory computer-readable media storing instructions which, when executed by one or more processors, causes:

receiving, at an importing system, from an exporting system, a plurality of replication chunks of an incremental replication job, wherein a replication chunk of the plurality of replication chunks contains a respective chunk identifier and respective change data;

performing, at the importing system, causality detection between the respective change data in the replication chunk received at the importing system and existing change data at the importing system; and

based at least in part on results of the causality detection, importing the replication chunk of the plurality of replication chunks into the importing system by;

(a) superseding, at the importing system, the existing change data already stored at the importing system with the respective change data in the replication chunk, (b) not superseding, at the importing system, the existing change data already stored at the importing system with the respective change data in the replication chunk, or (c) determining that a concurrency conflict exists between the respective change data in the replication chunk and the existing change data already stored at the importing system.

8. The one or more non-transitory computer-readable media of claim 7, wherein the respective chunk identifier for the replication chunk is used by the importing system to determine an order of the replication chunk in a sequence of plurality of replication chunks that the exporting system has broken the incremental replication job into.

9. The one or more non-transitory computer-readable media of claim 7, wherein the performing the causality detection is based, at least in part, on using version vectors for versioning the respective change data in the replication chunk and the existing change data at the importing system, wherein the version vectors are used to determine whether the respective change data in the replication chunk happened after, happened before or neither happened after nor happened before the existing change data at the importing system.

10. The one or more non-transitory computer-readable media of claim 9, wherein,

in response to determining that the change data in the replication chunk happened after the existing change data at the importing system, superseding the existing change data at the importing system with the respective change data in the replication chunk;

in response to determining that the change data in the replication chunk happened before the existing change data at the importing system, not superseding the existing change data at the importing system with the respective change data in the replication chunk; and

in response to determining that change data in the replication chunk neither happened before nor happened after the existing change data at the importing system, determining that a concurrently conflict exists between the respective change data in the replication chunk and the existing change data at the importing system.

11. The one or more non-transitory computer-readable media of claim 10, wherein in response to resolution of the concurrency conflict, superseding the existing change data at the importing system with results of the concurrency conflict resolution.

12. The one or more non-transitory computer-readable media of claim 11, wherein resolution of the concurrency conflict is based at least in part on user input provided by a user, the user input selecting one of:

(a) the respective change data in the replication chunk, or (b) the existing change data at the importing system.

20. The one or more non-transitory computer-readable media of claim 7, further comprising instructions which, when executed by one or more processors, causes:

receiving the plurality of replication chunks at the importing system in a first order;

wherein each replication chunk of the plurality of replication chunks has a respective chunk identifier and respective chunk data;

determining a second order of the plurality of replication chunks based on the respective chunk identifiers of the plurality of replication chunks;

wherein the first order is different than the second order; and

performing causality detection at the importing system for each replication chunk of the plurality of replication chunks in the second order of the plurality of replication chunks.

13. A system comprising:

a database;

an importing system comprising one or more computer-readable media and one or more processors, the one or more computer-readable media storing instructions which, when executed by the one or more processors, causes;

receiving, at the importing system, from an exporting system, a plurality of replication chunks of an incremental replication job, wherein the replication chunk contains a respective chunk identifier and respective change data;

performing, at the importing system, causality detection between the respective change data in the replication chunk received at the importing system and existing change data at the importing system; and

based at least in part on results of the causality detection, importing the replication chunk into the importing system by;

(a) superseding, at the importing system, the existing change data already stored at the importing system with the respective change data in the replication chunk, (b) not superseding, at the importing system, the existing change data already stored at the importing system with the respective change data in the replication chunk, or (c) determining that a concurrency conflict exists between the respective change data in the replication chunk and the existing change data already stored at the importing system.

14. The system of claim 13, wherein the respective chunk identifier is used by the importing system to determine an order of the replication chunk in a sequence of plurality of replication chunks that the exporting system has broken the incremental replication job into.

15. The system of claim 14, wherein the performing the causality detection is based, at least in part, on using version vectors for versioning the change data in the replication chunk and the existing change data at the importing system, wherein the version vectors are used to determine whether the respective change data in the replication chunk happened after, happened before or neither happened after nor happened before the existing change data at the importing system.

16. The system of claim 15, wherein,

in response to determining that the change data in the replication chunk happened after the existing change data at the importing system, superseding the existing change data at the importing system with the respective change data in the replication chunk;

in response to determining that the change data in the replication chunk happened before the existing change data at the importing system, not superseding the existing change data at the importing system with the respective change data in the replication chunk; and

in response to determining that change data in the replication chunk neither happened before nor happened after the existing change data at the importing system, determining that a concurrently conflict exists between the respective change data in the replication chunk and the existing change data at the importing system.

17. The system of claim 16, wherein in response to resolution of the concurrency conflict, superseding the existing change data at the importing system with results of the concurrency conflict resolution.

18. The system of claim 17, wherein resolution of the concurrency conflict is based at least in part on user input provided by a user, the user input selecting one of:

(a) the respective change data in the replication chunk, or (b) the existing change data at the importing system.

21. The system of claim 15, wherein the one or more computer-readable media of the importing system further comprise instructions which, when executed by the one or more processors, causes:

receiving the plurality of replication chunks at the importing system in a first order;

wherein each replication chunk of the plurality of replication chunks has a respective chunk identifier and respective chunk data;

determining a second order of the plurality of replication chunks based on the respective chunk identifiers of the plurality of replication chunks;

wherein the first order is different than the second order; and

performing causality detection at the importing system for each replication chunk of the plurality of replication chunks in the second order of the plurality of replication chunks.