IP Library › Granted Patent US 10,936,573

Granted Patent B2

US 10,936,573 · App. 16/136,278 · Granted Mar 2, 2021

Cross-ACL multi-master replication

Inventors: Richard Allen Ducott, III (Burlingame, CA); Katherine Brainard (Burlingame, CA); John Kenneth Garrod (Palo Alto, CA); John Antonio Carrino (Palo Alto, CA)

Assignee: Palantir Technologies Inc.

G06F16/2308 G06F16/178 G06F16/1873 G06F16/27 G06F16/273 G06F21/6218 G06F2221/2141 G06F2221/2151

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 10,936,573
App. No.: 16/136,278
Granted: Mar 2, 2021
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

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 (99)

1. A computer-implemented method comprising:

storing in a computer database at a first replication site of a plurality of replication sites arranged in a multi-master topology, a data object comprising a first access-controlled data object data unit and comprising a second access-controlled data object data unit;

storing in the computer database at the replication site, a first version vector for the first access-controlled data object data unit;

wherein the first version vector comprises a plurality of elements;

wherein each element of the plurality of elements of the first version vector corresponds to a respective one of the plurality of replication sites;

wherein each element of the plurality of elements of the first version vector represents a known version number of the first access-controlled data object data unit at the respective replication site;

receiving, by a processor, from a computer network connecting the first replication site to a second replication site of the plurality of replication sites, a data object change update for the data object from the second replication site of the plurality of replication sites;

wherein the data object change update comprises a first data object data unit update;

wherein the first data object data unit update comprises a second version vector and comprises change data for the first access-controlled data object data unit;

wherein the second version vector comprises a plurality of elements;

wherein each element of the plurality of elements of the second version vector corresponds to a respective one of the plurality of replication sites;

wherein each element of the plurality of elements of the second version vector represents a known version number of the first access-controlled data object data unit at the respective replication site;

wherein the data object change update comprises a second data object data unit update;

wherein the second data object data unit update comprises change data for the second access-controlled data object data unit;

determining, by a processor, based at least in part upon the first version vector and the second version vector, that the first data object data unit has a conflict with the first access-controlled data object data unit; and

automatically applying, by a processor, the change data of the second data object data unit update to the second access-controlled data object data unit stored in the computer database at the first replication site only after the conflict has been deconflicted.

2. The method of claim 1 , wherein the data object corresponds to a data record in a database; and wherein the first access-controlled data object data unit is a property, attribute, or field of the data record.

3. The method of claim 1 , wherein the data object corresponds to a document of a file system; and wherein first access-controlled data object data unit is a portion of the document.

4. The method of claim 1 , wherein determining whether the first data object data unit update conflicts with the first access-controlled data object data unit includes comparing the second version vector for the first data object data unit update to the first version vector for the first access-controlled data object data unit to determine whether the first data object data unit update conflicts with the first access-controlled data object data unit.

5. The method of claim 1 , further comprising:

receiving, by a processor, a user selection that deconflicts the conflict, the user selection comprising a value represented by the change data of the first data object data unit update; and

based on the user selection, automatically applying the change data of the first data object data unit to the first access-controlled data object data unit stored in the computer database at the first replication site.

6. The method of claim 1 , further comprising:

receiving, by a processor, a user selection that deconflicts the conflict, the user selection comprising a value of the first access-controlled data object data unit stored in the computer database at the first replication site; and

based on the user selection, automatically not applying the change data of the first data object data unit to the first access-controlled data object data unit stored in the computer database at the first replication site.

7. The method of claim 1 , further comprising:

receiving, by a processor, a user selection that deconflicts the conflict, the user selection compromising a user specification of a particular value;

wherein the particular value is not a value represented by the change data of the first data object data unit;

wherein the particular value is not a value of the first access-controlled data object data unit stored in the computer database at the first replication site; and

based on the user specification, automatically applying data representing the particular value to the first access-controlled data object data unit stored in the computer database at the first replication site.

8. The method of claim 1 , further comprising:

based on a processor automatically deconflicting the conflict, automatically applying the change data of the first data object data unit to the first access-controlled data object data unit stored in the computer database at the first replication site.

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

storing in the computer database at the replication site, a first version vector for the first access-controlled data object data unit;

wherein the first version vector comprises a plurality of elements;

wherein each element of the plurality of elements of the first version vector corresponds to a respective one of the plurality of replication sites;

receiving, by a processor of the one or more processors, from a computer network connecting the first replication site to a second replication site of the plurality of replication sites, a data object change update for the data object from the second replication site of the plurality of replication sites;

wherein the data object change update comprises a first data object data unit update;

wherein the first data object data unit update comprises a second version vector and comprises change data for the first access-controlled data object data unit;

wherein the second version vector comprises a plurality of elements;

wherein each element of the plurality of elements of the second version vector corresponds to a respective one of the plurality of replication sites;

wherein the data object change update comprises a second data object data unit update;

wherein the second data object data unit update comprises change data for the second access-controlled data object data unit;

determining, by a processor of the one or more processors, based at least in part upon the first version vector and the second version vector, that the first data object data unit has a conflict with the first access-controlled data object data unit; and

automatically applying, by a processor of the one or more processors, the change data of the second data object data unit update to the second access-controlled data object data unit stored in the computer database at the first replication site only after the conflict has been deconflicted.

10. The one or more non-transitory storage media of claim 9 , wherein the data object corresponds to a data record in a database; and wherein the first access-controlled data object data unit is a property, attribute, or field of the data record.

11. The one or more non-transitory storage media of claim 9 , wherein the data object corresponds to a document of a file system; and wherein the first access-controlled data object data unit is a portion of the document.

12. The one or more non-transitory storage media of claim 9 , wherein determining whether the first data object data unit update conflicts with the first access-controlled data object data unit includes comparing the second version vector for the first data object data unit update to the first version vector for the first access-controlled data object data unit to determine whether the first data object data unit update conflicts with the first access-controlled data object data unit.

13. The one or more non-transitory storage media of claim 9 , further comprising instructions which, when executed by the one or more computer systems, cause the one or more computer systems to perform:

receiving, by a processor of the one or more processors, a user selection that deconflicts the conflict, the user selection comprising a value represented by the change data of the first data object data unit update; and

14. The one or more non-transitory storage media of claim 9 , further comprising instructions which, when executed by the one or more computer systems, cause the one or more computer systems to perform:

receiving, by a processor of the one or more processors, a user selection that deconflicts the conflict, the user selection comprising a value of the first access-controlled data object data unit stored in the computer database at the first replication site; and

15. The one or more non-transitory storage media of claim 9 , further comprising instructions which, when executed by the one or more computer systems, cause the one or more computer systems to perform:

receiving, by a processor of the one or more processors, a user selection that deconflicts the conflict, the user selection compromising a user specification of a particular value;

wherein the particular value is not a value represented by the change data of the first data object data unit;

wherein the particular value is not a value of the first access-controlled data object data unit stored in the computer database at the first replication site; and

16. The one or more non-transitory storage media of claim 9 , further comprising instructions which, when executed by the one or more computer systems, cause the one or more computer systems to perform:

based on a processor of the one or more processors automatically deconflicting the conflict, automatically applying the change data of the first data object data unit to the first access-controlled data object data unit stored in the computer database at the first replication site.

17. A computing system comprising:

one or more processors;

storage media; and

instructions stored in the storage media and which, when executed by the computing system, cause the computing system to perform: