Cross-ACL multi-master replication

• US 8,527,461 B2
• Filed: 11/27/2012
• Issued: 09/03/2013
• Est. Priority Date: 01/23/2012
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Ducott, Richard Allen III, Brainard, Katherine, Garrod, John Kenneth, Carrino, John Antonio
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US13/686,750
• Publication Number:
  US 20130191338A1
• Time in Patent Office: 280 Days
• Field of Search: 707/640, 707/635, 707/638, 709/203, 709/223
• US Class Current: 707/638
• 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 computer-implemented method, comprising:

at a first replication site of a plurality of replication sites;

storing a data object in computer memory, the data object having at least one access controlled data object data unit;

storing in computer memory a first version vector for the access controlled data object data unit;

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

storing the data object change update in computer memory, the data object change update having at least one data object data unit update and a second version vector for the data object data unit update;

determining, based at least in part on the first version vector and the second version vector, that the data object data unit update conflicts with the access controlled data object data unit;

in response to determining that the data object data unit update conflicts with the access controlled data object data unit, applying the data object change update to the data object only after the conflict has been deconflicted;

wherein applying the data object change update to the data object only after the conflict has been deconflicted includes;

obtaining results of a deconfliction between the data object data unit update and the access controlled data object data unit;

applying the results of the deconfliction to the access controlled data object data unit to produce a new version of the access controlled data object data unit;

merging the first version vector and the second version vector to produce a merged version vector;

incrementing a logical clock value in the merged version vector to produce a merged and incremented version vector, the logical clock value corresponding to the first replication site; and

associating the merged and incremented version vector with the new version of the access controlled data object data unit;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein the access controlled data object data unit is a property, attribute, or field of the data object.

3. The method of claim 1, wherein the access controlled data object data unit is a portion of a file or a portion of a document.

4. The method of claim 1, wherein determining that the data object data unit update conflicts with the access controlled data object data unit includes:

comparing the first version vector to the second version vector; and

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

5. The method of claim 1, wherein the conflict is manually deconflicted.

6. The method of claim 1, wherein the logical clock value is incremented by one.

7. The method of claim 1, wherein determining that the data object data unit update conflicts with the access controlled data object data unit includes detecting that the first version vector and the second version vector are neither ordered before nor ordered after one another.

8. The method of claim 1, wherein the access controlled data object data unit is associated with an access control list;

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

wherein applying the data object change update to the data object only after the conflict has been deconflicted includes applying the access control list update to the access control list only after the conflict has been deconflicted.

9. The method of claim 1, wherein the data object change update includes an identifier of the data object and a plurality of data object data unit updates, one of which is the data object data unit update;

and wherein the data object data unit update includes an identifier of the access controlled data object data unit.

10. One or more non-transitory computer-readable media storing one or more programs, the one or more programs comprising instructions which, when executed by one or more computing devices, cause the one or more computing devices to perform a method comprising:

at a first replication site of a plurality of replication sites;

storing a data object in computer memory, the data object having at least one access controlled data object data unit;

storing in computer memory a first version vector for the access controlled data object data unit;

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

storing the data object change update in computer memory, the data object change update having at least one data object data unit update and a second version vector for the data object data unit update;

determining, based at least in part on the first version vector and the second version vector, that the data object data unit update conflicts with the access controlled data object data unit;

in response to determining that the data object data unit update conflicts with the access controlled data object data unit, applying the data object change update to the data object only after the conflict has been deconflicted;

wherein applying the data object change update to the data object only after the conflict has been deconflicted includes;

obtaining results of a deconfliction between the data object data unit update and the access controlled data object data unit;

applying the results of the deconfliction to the access controlled data object data unit to produce a new version of the access controlled data object data unit;

merging the first version vector and the second version vector to produce a merged version vector;

incrementing a logical clock value in the merged version vector to produce a merged and incremented version vector, the logical clock value corresponding to the first replication site; and

associating the merged and incremented version vector with the new version of the access controlled data object data unit.

11. The one or more non-transitory computer-readable media of claim 10, wherein the access controlled data object data unit is a property, attribute, or field of the data object.

12. The one or more non-transitory computer-readable media of claim 10, wherein the access controlled data object data unit is a portion of a file or a portion of a document.

13. The one or more non-transitory computer-readable media of claim 10, wherein determining that the data object data unit update conflicts with the access controlled data object data unit includes:

comparing the first version vector to the second version vector; and

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

14. The one or more non-transitory computer-readable media of claim 10, wherein the conflict is manually deconflicted.

15. The one or more non-transitory computer-readable media of claim 10, wherein the logical clock value is incremented by one.

16. The one or more non-transitory computer-readable media of claim 10, wherein determining that the data object data unit update conflicts with the access controlled data object data unit includes detecting that the first version vector and the second version vector are neither ordered before nor ordered after one another.

17. The one or more non-transitory computer-readable media of claim 10, wherein the access controlled data object data unit is associated with an access control list;

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

wherein applying the data object change update to the data object only after the conflict has been deconflicted includes applying the access control list update to the access control list only after the conflict has been deconflicted.

18. The one or more non-transitory computer-readable media of claim 10, wherein the data object change update includes an identifier of the data object and a plurality of data object data unit updates, one of which is the data object data unit update;

and wherein the data object data unit update includes an identifier of the access controlled data object data unit.

19. An apparatus, comprising:

computer memory storing instructions;

one or more processors coupled to the computer memory;

wherein the instructions stored in the computer memory, when executed by the one or more processors, cause the one or more processors to perform a method comprising;

at a first replication site of a plurality of replication sites;

storing a data object in the computer memory, the data object having at least one access controlled data object data unit;

storing in the computer memory a first version vector for the access controlled data object data unit;

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

storing the data object change update in the computer memory, the data object change update having at least one data object data unit update and a second version vector for the data object data unit update;

determining, based at least in part on the first version vector and the second version vector, that the data object data unit update conflicts with the access controlled data object data unit;

in response to determining that the data object data unit update conflicts with the access controlled data object data unit, applying the data object change update to the data object only after the conflict has been deconflicted;

wherein applying the data object change update to the data object only after the conflict has been deconflicted includes;

obtaining results of a deconfliction between the data object data unit update and the access controlled data object data unit;

applying the results of the deconfliction to the access controlled data object data unit to produce a new version of the access controlled data object data unit;

merging the first version vector and the second version vector to produce a merged version vector;

incrementing a logical clock value in the merged version vector to produce a merged and incremented version vector, the logical clock value corresponding to the first replication site; and

associating the merged and incremented version vector with the new version of the access controlled data object data unit.

20. The apparatus of claim 19, wherein the access controlled data object data unit is a property, attribute, or field of the data object.

21. The apparatus of claim 19, wherein the access controlled data object data unit is a portion of a file or a portion of a document.

22. The apparatus of claim 19, wherein determining that the data object data unit update conflicts with the access controlled data object data unit includes:

comparing the first version vector to the second version vector; and

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

23. The apparatus of claim 19, wherein the conflict is manually deconflicted.

24. The apparatus of claim 19, wherein the logical clock value is incremented by one.

25. The apparatus of claim 19, wherein determining that the data object data unit update conflicts with the access controlled data object data unit includes detecting that the first version vector and the second version vector are neither ordered before nor ordered after one another.

26. The apparatus of claim 19, wherein the access controlled data object data unit is associated with an access control list;

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

wherein applying the data object change update to the data object only after the conflict has been deconflicted includes applying the access control list update to the access control list only after the conflict has been deconflicted.

27. The apparatus of claim 19, wherein the data object change update includes an identifier of the data object and a plurality of data object data unit updates, one of which is the data object data unit update;

and wherein the data object data unit update includes an identifier of the access controlled data object data unit.