Cross-ACL multi-master replication

• US 10,089,345 B2
• Filed: 06/20/2017
• Issued: 10/02/2018
• 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
• Application Number:
  US15/628,342
• Publication Number:
  US 20170351724A1
• Time in Patent Office: 469 Days
• Field of Search: 707617, 707634
• 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 computing system comprising:

one or more processors;

storage media; and

one or more programs stored in the storage media and configured for execution by the one or more processors, the one or more programs comprising instructions configured for;

storing a data object at a first replication site of a plurality of replication sites arranged in a multi-master replication topology;

wherein the data object stored at the first replication site comprises;

a first access controlled data object data unit, and

a second access controlled data object data unit;

wherein first access controls are associated at the first replication site with the first access controlled data object data unit of the data object at the first replication site;

wherein second access controls are associated at the first replication site with the second access controlled data object data unit of the data object at the first replication site;

wherein the first access controls specify that the first access controlled data object data unit, of the data object at the first replication site, is permitted to be shared from the first replication site with a first set of zero or more other replication sites of the plurality of replication sites;

wherein the second access controls specify that the second access controlled data object data unit, of the data object at the first replication site, is permitted to be shared from the first replication site with a second set of zero or more other replication sites of the plurality of replication sites;

wherein the first set of zero or more other replication sites, of the plurality of replication sites, is different than the second set of zero or more other replication sites, of the plurality of replication sites;

receiving a data object change update for the data object from a second replication site of the plurality of replication sites;

wherein the data object change update comprises a first data object data unit update for the first access controlled data object data unit of the data object at the first replication site;

wherein the data object change update does not include a second data object data unit update for the second access control data object data unit of the data object at the first replication site;

wherein the data object change update further comprises a third data object data unit update for the data object at the first replication site;

detecting a concurrency conflict between the first data object data unit update, of the data object change update, and the first access controlled data object data unit, of the data object at the first replication site;

applying the third data object data unit update, of the data object change update, to the data object stored at the first replication site only after the concurrency conflict is deconflicted, the data object change update comprising one or more values for one or more other properties of the data object, and wherein the applying comprises updating the data object in the first replication site 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 computing system of claim 1, the one or more programs comprising instructions configured for detecting the concurrency conflict by comparing a first version vector associated with a first value among the one or more values to a second version vector associated with a second value among the one or more values;

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

3. The computing system of claim 2, the one or more programs comprising instructions configured for obtaining a deconflicted value for a first property of the data object as a result of the concurrency conflict being deconflicted, the deconflicted value for the first property being one of the first value or the second value.

4. The computing system of claim 2, the one or more programs comprising instructions configured for obtaining a deconflicted value for a first property of the data object as a result of the concurrency conflict being deconflicted, the deconflicted value for the first property being neither the first value nor the second value.

5. The computing system of claim 2, the one or more programs comprising instructions configured for determining that the third data object data unit update conflicts with the first access controlled data object data unit by comparing the first version vector to the second version vector;

and detecting, based on the comparing, that the data object change update happened concurrently with an update to the first access controlled data object data unit represented by the first version vector.

6. The computing system of claim 2, the one or more programs comprising instructions configured for determining that the third data object data unit update conflicts with the first access controlled data object data unit by detecting that the first version vector and the second version vector are neither ordered before nor ordered after one another.

7. The computing system of claim 2, the one or more programs comprising instructions configured for, if the second data object data unit update happened concurrently with the first data object data unit update, applying results of a deconfliction between the third data object data unit update and the first access controlled data object data unit to the first access controlled data object data unit and incrementing a version vector generated by merging the second version vector associated with the third data object data unit update and the first version vector associated with the first access controlled data object data unit.

8. The computing system of claim 2, wherein the first version vector maintained for the first access controlled data object unit at the first replication site is associated at the first replication site with the data object.

9. The computing system of claim 2, wherein the first version vector maintained for the first access controlled data object unit at the first replication site is associated at the first replication site with the first access controlled data object unit.

10. The computing system of claim 1, the one or more programs comprising instructions configured for automatically deconflicting the concurrency conflict.

11. The computing system of claim 1, wherein the first access controlled data object data unit is a property, attribute, or field of the data object.

12. The computing system of claim 1, wherein the first access controlled data object data unit is a portion of a file or a portion of a document.

13. The computing system of claim 1, wherein the first access controlled data object data unit is associated with an access control list;

wherein the third data object data unit update includes an access control list update; and

the one or more programs comprising instructions configured for applying the data object change update to the data object only after the conflict has been deconflicted by applying the access control list update to the access control list only after the conflict has been deconflicted.

14. The computing system of claim 1, wherein the third data object data unit update includes an identifier of the first access controlled data object data unit.

15. The computing system of claim 1, the one or more programs comprising instructions configured for not applying the third data object data unit update to the data object maintained at the first replication site if the third data object data unit update happened before the first access controlled data object data unit.

16. The computing system of claim 1, wherein because of an access control filter at the second replication site, the data object change update received from the second replication site does not include a data object data unit update for an update to an access controlled data object data unit of the data object made at a replication site of the plurality of replication sites.