Sharing and Deconflicting Data Changes In A Multimaster Database System

• US 20120016849A1
• Filed: 07/15/2010
• Published: 01/19/2012
• Est. Priority Date: 07/15/2010
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Scott, Jacob, Garrod, John Kenneth, Carrino, John Antonio, Brainard, Katherine, Chang, Allen
• Granted Patent: US 8,515,912 B2
• Time in Patent Office: Days
• US Class Current: 707/695
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation

Abstract

A computer-based method and system for sharing and deconflicting data changes amongst a plurality of replication sites. In a particular embodiment, data changes at sites to data objects are tracked by each site on a per-data object basis using per-data object version vectors. In another particular embodiment, data changes at sites to links connecting two data objects are tracked by each site on a per-link set basis using per-link set version vectors. In another particular embodiment, per-object version vectors are used to detect a conflict resulting from concurrent changes at two or more sites in which one of the concurrent changes includes an object resolution change.

Claims

1. In a multimaster database system comprising a plurality of sites, a method for sharing and deconflicting data changes, the method comprising:

making a change to a data object at a first site of the plurality of sites;

sharing the change to the data object at the first site with one or more other sites of the plurality of sites;

a computing device at a second site of the plurality of sites receiving an update reflecting the change to the data object at the first site;

wherein the update includes;

an identification of the data object,

data reflecting the change to the data object at the first site, and

a version of the data object at the first site;

the computing device obtaining a version of the data object at the second site; and

the computing device comparing the version of the data object at the first site to the version of the data object at the second site to determine whether the two versions are identical, ordered, or concurrent.

2. The method according to claim 1, wherein the version of the data object at the first site is represented by a version vector, and wherein the version of the data object at the second site is represented by a version vector.

3. The method according to claim 2, wherein comparing the version of the data object at the first site to the version of the data object at the second site comprises comparing the version vector representing the version of the data object at the first site to the version vector representing the version of the data object at the second site to determine whether the two version vectors are identical, ordered, or concurrent.

4. The method according to claim 3, wherein prior to the computing device receiving the update, making a change to the data object at the second site, the method further comprising:

in response to the computing device determining that the two version vectors are concurrent, attempting to automatically deconflict the change to the data object at the first site and the change to the data object at the second site.

5. The method according to claim 4, wherein attempting to automatically deconflict comprises determining whether the change to the data object made at the first site and the change to the data object at the second site are to different properties of the data object.

6. The method according to claim 5, the method further comprising:

in response to determining that the changes are to different properties of the data object,

incorporating the change to the data object at the first site into a copy of the data object at the second site to produce a new version of the data object at the second site,

merging the version vector representing the version of the data object at the first site and the version vector representing the version of the data object at the second site to produce a merged version vector, and

incrementing a particular element of the merged version vector to produce an incremented version vector representing the new version of the data object at the second site, the particular element corresponding to a logical clock for the data object at the second site.

7. The method according to claim 6, the method further comprising:

receiving an update at the first site reflecting the new version of the data object at the second site;

wherein the update received at the first site includes data that represents the incremented version vector; and

merging the version vector representing the version of the data object at the first site and the incremented version vector received in the update to produce a new version vector representing the version of the data object at the first site.

8. The method according to claim 3, wherein prior to the second computing device receiving the update, making a change to the data object at the second site, the method further comprising:

in response to determining that the two version vectors are concurrent, placing the update in a pending update queue at the second site.

9. The method according to claim 8, further comprising:

determining a version of the data object at the second site that is ordered before both (a) the version of the data object at the first site and (b) the version of the data object at the second site.

10. The method according to claim 9, further comprising:

receiving user specified input selecting one of (a) the version of the data object at the first site and (b) the version of the data object at the second site, as the correct version for the data object.

15. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 1.

16. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 2.

17. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 3.

18. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 4.

19. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 5.

20. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 6.

21. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 7.

22. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 8.

23. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 9.

24. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 10.

11. In a multimaster database system comprising a plurality of sites, a method for sharing and deconflicting data changes, the method comprising:

making a change at a first site of the plurality of sites to a set of one or more links connecting two data objects;

sharing the change with one or more other sites of the plurality of sites;

a computing device at a second site of the plurality of sites receiving an update reflecting the change to the set of links at the first site;

wherein the update includes;

an identification of the set of links,

data reflecting the change to the set of links at the first site, and

a version of the set of links at the first site;

the computing device obtaining a version of the set of links at the second site; and

the computing device comparing the version of the set of links at the first site to the version of the set of links at the second site to determine whether the two versions are identical, ordered, or concurrent.

12. The method according to claim 11, wherein the version of the set of links at the first site is represented by a version vector, and wherein the version of the set of links at the second site is represented by a version vector.

13. The method according to claim 12, wherein comparing the version of the set of links at the first site to the version of the set of links at the second site comprises comparing the version vector representing the version of the set of links at the first site to the version vector representing the version of the set of links at the second site to determine whether the two version vectors are identical, ordered, or concurrent.

25. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 11.

26. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 12.

27. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 13.

14. In a multimaster database system comprising a plurality of sites, a method for sharing and deconflicting data changes, the method comprising:

a first computing device at a first site of the plurality of sites resolving two or more data objects together;

sharing the resolution change with one or more other sites of the plurality of sites;

a second computing device receiving an update reflecting the resolution change made by the first computing device at the first site;

wherein the update includes;

an identification of each of the two or more data objects,

data that indicates that the two or more data objects were resolved together, and

for each of the two or more data objects, a version of the data object at the first site;

the second computing device obtaining, for each of the two or more data objects, a version of the data object at the second site;

the second computing device comparing, for each of the two or more data objects, the version of the data object at the first site to the version of the data object at the second site to determine whether the two versions are identical, ordered, or concurrent; and

in response to the second computing device determining that the version of at least one data object of the two or more data objects at the first site is concurrent with the version of the at least one data object at the second site, the second computing device determining that the resolution change made by the first computing device at the first site conflicts with the version of the at least one data object at the second site.

28. A computer-readable non-transitory medium storing processor-executable instructions for performing the method according to claim 14.