Cross-ACL multi-master replication

• US 9,715,518 B2
• Filed: 09/28/2015
• Issued: 07/25/2017
• Est. Priority Date: 01/23/2012
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Ducott, III, Richard Allen, Brainard, Katherine, Garrod, John Kenneth, Carrino, John Antonio
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US14/868,310
• Publication Number:
  US 20160019252A1
• Time in Patent Office: 666 Days
• Field of Search: 707617
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2329 using versioning
• 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
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/2141 Access rights, e.g. capability lists, access control lists, access tables, access matrices
• CPC Class Codes: G06F 2221/2151 Time stamp

Abstract

Techniques for cross-ACL multi-master replication are provided. The techniques allow a replication site in a multi-master replication system implementing an asynchronous replication protocol and an access control policy to appropriately apply received data change updates to data maintained at the site even where a data change update is missing information because of the implemented access control policy.

Claims

1. A method comprising:

at one or more computing device comprising one or more processors and memory storing one or more programs executed by the one or more processors to perform the method, performing operations comprising;

receiving a first update to a data object;

updating the data object in a first database based on the first update;

receiving a second update to the data object;

responsive to receiving the second update, detecting a concurrency conflict between a first value for a first property of the data object in the first database and a second value for the first property in the second update;

updating the data object in the first database based on the second update only after the concurrency conflict is deconflicted;

wherein the second update comprises one or more values for one or more other properties of the data object; and

wherein the operation of updating the data object in the first database based on the second update only after the concurrency conflict is deconflicted comprises the operation of updating the data object in the first database based on the one or more values for the one or more other properties of the data object only after the concurrency conflict is deconflicted.

2. The method of claim 1, wherein the operation of detecting the concurrency conflict comprises the operation of:

comparing a first version vector associated with first value to a second version vector associated with the second value; and

determining the concurrency conflict exists based on a result of the comparing.

3. The method of claim 1, wherein the operations further comprise the operation of automatically deconflicting the concurrency conflict.

4. The method of claim 1, wherein:

the operations further comprise the operation of obtaining a deconflicted value for the first property as a result of the concurrency conflict being deconflicted; and

the deconflicted value for the first property is one of the first value or the second value.

5. The method of claim 1, wherein the operations further comprise the operations of:

obtaining a deconflicted value for the first property as a result of the concurrency conflict being deconflicted; and

wherein the deconflicted value for the first property is neither the first value nor the second value.

6. The method of claim 1, A method comprising:

at one or more computing device comprising one or more processors and memory storing one or more programs executed by the one or more processors to perform the method, performing operations comprising;

receiving a first update to a data object;

updating the data object in a first database based on the first update;

receiving a second update to the data object;

responsive to receiving the second update, detecting a concurrency conflict between a first value for a first property of the data object in the first database and a second value for the first property in the second update;

updating the data object in the first database based on the second update only after the concurrency conflict is deconflicted;

wherein the first update comprises a plurality of values for a first set of a plurality of properties of the data object;

wherein the second update comprises a plurality of values for a second set of a plurality of properties of the data object;

wherein the first set of properties comprises a property that is not in the second set of properties; and

wherein the second set of properties comprises a property that is not in the first set of properties.

7. One or more non-transitory computer-readable media storing instructions which, when executed by one or more processors, cause the one or more processors to perform operations comprising:

receiving a first update to a data object;

updating the data object in a first database based on the first update;

receiving a second update to the data object;

responsive to receiving the second update, detecting a concurrency conflict between a first value for a first property of the data object in the first database and a second value for the first property in the second update;

updating the data object in the first database based on the second update only after the concurrency conflict is deconflicted;

wherein the second update comprises one or more values for one or more other properties of the data object; and

wherein the operation of updating the data object in the first database based on the second update only after the concurrency conflict is deconflicted comprises the operation of updating the data object in the first database based on the one or more values for the one or more other properties of the data object only after the concurrency conflict is deconflicted.

8. The one or more non-transitory computer-readable media of claim 7, wherein the operation of detecting the concurrency conflict comprises the operation of:

comparing a first version vector associated with first value to a second version vector associated with the second value; and

determining the concurrency conflict exists based on a result of the comparing.

9. The one or more non-transitory computer-readable media of claim 7, wherein the operations further comprise the operation of automatically deconflicting the concurrency conflict.

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

the operations further comprise the operation of obtaining a deconflicted value for the first property as a result of the concurrency conflict being deconflicted; and

the deconflicted value for the first property is one of the first value or the second value.

11. The one or more non-transitory computer-readable media of claim 7, wherein the operations further comprise the operations of:

obtaining a deconflicted value for the first property as a result of the concurrency conflict being deconflicted; and

wherein the deconflicted value for the first property is neither the first value nor the second value.

12. One or more non-transitory computer-readable media storing instructions which, when executed by one or more processors, cause the one or more processors to perform operations comprising:

receiving a first update to a data object;

updating the data object in a first database based on the first update;

receiving a second update to the data object;

responsive to receiving the second update, detecting a concurrency conflict between a first value for a first property of the data object in the first database and a second value for the first property in the second update;

updating the data object in the first database based on the second update only after the concurrency conflict is deconflicted;

wherein the first update comprises a plurality of values for a first set of a plurality of properties of the data object;

wherein the second update comprises a plurality of values for a second set of a plurality of properties of the data object;

wherein the first set of properties comprises a property that is not in the second set of properties; and

wherein the second set of properties comprises a property that is not in the first set of properties.

13. A system comprising:

one or more processors;

one or more storage media storing one or more computer programs for execution by the one or more processors, the one or more computer programs comprising instructions for configured for;

receiving a first update to a data object;

updating the data object in a first database based on the first update;

receiving a second update to the data object;

responsive to receiving the second update, detecting a concurrency conflict between a first value for a first property of the data object in the first database and a second value for the first property in the second update;

updating the data object in the first database based on the second update only after the concurrency conflict is deconflicted;

wherein the second update comprises one or more values for one or more other properties of the data object; and

wherein the instructions configured for updating the data object in the first database based on the second update only after the concurrency conflict is deconflicted comprise instructions configured for updating the data object in the first database based on the one or more values for the one or more other properties of the data object only after the concurrency conflict is deconflicted.

14. The system of claim 13, wherein the instructions configured for detecting the concurrency conflict comprise instructions configured for:

comparing a first version vector associated with first value to a second version vector associated with the second value; and

determining the concurrency conflict exists based on a result of the comparing.

15. The system of claim 13, wherein the instructions are further configured for automatically deconflicting the concurrency conflict.

16. The system of claim 13, wherein:

the instructions are further configured for obtaining a deconflicted value for the first property as a result of the concurrency conflict being deconflicted; and

the deconflicted value for the first property is one of the first value or the second value.

17. The system of claim 13, wherein the instructions are further configured for:

obtaining a deconflicted value for the first property as a result of the concurrency conflict being deconflicted; and

wherein the deconflicted value for the first property is neither the first value nor the second value.

18. A system comprising:

one or more processors;

one or more storage media storing one or more computer programs for execution by the one or more processors, the one or more computer programs comprising instructions for configured for;

receiving a first update to a data object;

updating the data object in a first database based on the first update;

receiving a second update to the data object;

responsive to receiving the second update, detecting a concurrency conflict between a first value for a first property of the data object in the first database and a second value for the first property in the second update;

updating the data object in the first database based on the second update only after the concurrency conflict is deconflicted;

wherein the first update comprises a plurality of values for a first set of a plurality of properties of the data object;

wherein the second update comprises a plurality of values for a second set of a plurality of properties of the data object;

wherein the first set of properties comprises a property that is not in the second set of properties; and

wherein the second set of properties comprises a property that is not in the first set of properties.