Cross-ACL multi-master replication

• US 9,189,492 B2
• Filed: 05/23/2014
• Issued: 11/17/2015
• 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:
  US14/286,485
• Publication Number:
  US 20140258233A1
• Time in Patent Office: 543 Days
• Field of Search: 707/634, 707/638
• US Class Current: 1/1
• 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 a first replication site of a plurality of replication sites;

receiving a first update to a data record from a second replication site of the plurality of replication sites;

receiving a second update to the data record from a third replication site of the plurality of replication sites;

wherein the first update comprises a first value for a first field of the data record and a first value for a second field of the data record;

wherein the second update comprises a second value for the first field and a first value for a third field of the data record;

wherein the first update does not include a value for the third field;

wherein the second update does not include a value for the second field;

responsive to receiving the first update, creating the data record in a database comprising the first value for the first field and the first value for the second field;

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

after the concurrency conflict is deconflicted, updating the data record in the database to include a deconflicted value for the first field and the first value for the third field from the second update;

wherein the method is performed by one or more computing devices at the first replication site.

2. The method of claim 1, wherein detecting the concurrency conflict comprises comparing a first version vector to a second version vector, and determining the concurrency conflict exists based on results of the comparing.

3. The method of claim 1, further comprising automatically deconflicting the concurrency conflict.

4. The method of claim 1, wherein the deconflicted value for the first field is one of the first value for the first field or the second value for the first field.

5. The method of claim 1, wherein the deconflicted value for the first field is neither the first value for the first field nor the second value for the first field.

11. One or more non-transitory computer-readable media storing instructions which, when executed by one or more computing devices at a first replication site of a plurality of replication sites, causes the one or more computing devices to perform the method of claim 1.

6. A method comprising:

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

receiving a first update to a file from a second replication site of the plurality of replication sites;

receiving a second update to the file from a third replication site of the plurality of replication sites;

wherein the first update comprises a first value for a first portion of the file and a first value for a second portion of the file;

wherein the second update comprises a second value for the first file portion and a first value for a third portion of the file;

wherein the first update does not include a value for the third portion;

wherein the second update does not include a value for the second portion;

responsive to receiving the first update, creating the file in a data storage medium comprising the first value for the first portion and the first value for the second portion;

responsive to receiving the second update, detecting a concurrency conflict between the first value for the first portion of the file in the data storage medium and the second value for the first portion in the second update;

after the concurrency conflict is deconflicted, updating the file in the data storage medium to include a deconflicted value for the first portion and the first value for the third portion from the second update;

wherein the method is performed by one or more computing devices at the first replication site.

7. The method of claim 6, wherein detecting the concurrency conflict comprises comparing a first version vector to a second version vector, and determining the concurrency conflict exists based on results of the comparing.

8. The method of claim 6, further comprising automatically deconflicting the concurrency conflict.

9. The method of claim 6, wherein the deconflicted value for the first field is one of the first value for the first field or the second value for the first field.

10. The method of claim 6, wherein the deconflicted value for the first field is neither the first value for the first field nor the second value for the first field.

12. One or more non-transitory computer-readable media storing instructions which, when executed by one or more computing devices at a first replication site of a plurality of replication sites, causes the one or more computing devices to perform the method of claim 6.

13. A method comprising:

at a first replication site of a plurality of replication sites, the first replication site comprising one or more computing devices and a first database, the one or more computing devices at the first replication site performing the steps of;

storing, in the first database, a data object comprising a first value for a first property of the data object, a first value for a second property of the data object, and a first value for a third property of the data object;

filtering, from a first update to be sent to a second replication site of the plurality of replication sites, the first value for the third property, based on a first access control list associated in the first database with the third property and based on a first access control filter that governs sharing of information in the first database by the first replication site with the second replication site;

filtering, from a second update to be sent to a third replication site of the plurality of replication sites, the first value for the second property, based on a second access control list associated in the first database with the second property and based on a second access control filter that governs sharing of information in the first database by the first replication site with the third replication site;

at a fourth replication site of the plurality of replication sites, the fourth replication site comprising one or more computing devices and a second database, the one or more computing devices at the fourth replication site performing the steps of;

receiving a third update to the data object from the second replication site;

receiving a fourth update to the data object from the third replication site;

wherein the third update comprises a second value for the first property and the first value for the second property;

wherein the fourth update comprises a third value for the first property and the first value for the third property;

responsive to receiving the third update, creating the data record in the second database comprising the second value for the first property and the first value for the second property;

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

after the concurrency conflict is deconflicted, updating the data record in the second database to include a deconflicted value for the first property and the first value for the third property from the fourth update.

14. The method of claim 13, wherein detecting the concurrency conflict comprises comparing a first version vector to a second version vector, and determining the concurrency conflict exists based on results of the comparing.

15. The method of claim 13, further comprising automatically deconflicting the concurrency conflict.

16. The method of claim 13, wherein the deconflicted value for the first property is one of the second value for the first property or the third value for the first property.

17. The method of claim 13, wherein the deconflicted value for the first property is neither the second value for the first property nor the third value for the first property.

18. The method of claim 13, wherein the first access control list associated in the first database with the third property comprises a security classification level;

and wherein the first access control filter is configured to prevent the first replication site from sharing, with the second replication site, information in the first database associated with the security classification level.

19. The method of claim 13, wherein the second access control list associated in the first database with the second property comprises a security classification level;

and wherein the second access control filter is configured to prevent the first replication site from sharing, with the third replication site, information in the first database associated with the security classification level.

20. A system comprising:

one or more computing devices and a first database at a first replication site of a plurality of replication sites;

one or more computing devices at a second replication site of the plurality of replication sites;

one or more computing devices at a third replication site of the plurality of replication sites;

one or more computing devices at a fourth replication site of the plurality of replication sites;

wherein the one or more computing devices at the first replication site are configured to;

store, in the first database, a data object comprising a first value for a first property of the data object, a first value for a second property of the data object, and a first value for a third property of the data object;

filter, from a first update to be sent to the second replication site, the first value for the third property, based on a first access control list associated in the first database with the third property and based on a first access control filter that governs sharing of information in the first database by the first replication site with the second replication site;

filter, from a second update to be sent to the third replication site, the first value for the second property, based on a second access control list associated in the first database with the second property and based on a second access control filter that governs sharing of information in the first database by the first replication site with the third replication site;

wherein the one or more computing devices at the fourth replication site are configured to;

receive a third update to the data object from the second replication site;

receive a fourth update to the data object from the third replication site;

wherein the third update comprises a second value for the first property and the first value for the second property;

wherein the fourth update comprises a third value for the first property and the first value for the third property;

responsive to receiving the third update, create the data record in the second database comprising the second value for the first property and the first value for the second property;

responsive to receiving the fourth update, detect a concurrency conflict between the second value for the first property of the data record in the second database and the third value for the first property in the fourth update;

after the concurrency conflict is deconflicted, update the data record in the second database to include a deconflicted value for the first property and the first value for the third property from the fourth update.