Sharing and deconflicting data changes in a multimaster database system

Patent metadata

Field	Value
Publication number	US-RE48589-E
Application number	US-201514830420-A
Country	US
Kind code	E1
Filing date	Aug 19, 2015
Priority date	Jul 15, 2010
Publication date	Jun 8, 2021
Grant date	Jun 8, 2021

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.

First claim

What is claimed is:

1. In a multimaster database system comprising a plurality of sites, a method for sharing and deconflicting data changes, the method comprising:
at a first site of the plurality of sites, making a first change to a set of one or more links connecting two data objects by adding or removing one or more links from the set of links; wherein the set of links is associated at the first site with a first version vector for the set of one or more links; at a second site of the plurality of sites, making a second change to the set of links connecting the two data objects by adding or removing a link from the set of links; wherein the set of links is associated at the second site with a second version vector for the set of links; sharing the first change with the second site of the plurality of sites; receiving, at the second site, an update reflecting the first change to the set of links at the first site; wherein the update includes:
an identification of the set of links,
data reflecting the first change to the set of links at the first site, and
the first version vector for the set of links;
at the second site, comparing the first version vector for the set of links to the second version vector for the set of links to determine whether the first change to the set of links at the first set and the second change to the set of links at the second site are identical, ordered, or concurrent; wherein the method is performed by a plurality of computing devices.

2. The method according to claim 1 , wherein the second change to the set of links is made at the second site before the first change to the set of links is made at the first site; and wherein the method further comprises determining, based on the comparing, that the first and second changes are ordered.

3. The method according to claim 1 , wherein the second change to the set of links is made at the second site before the first change to the set of links is made at the first site; and wherein the method further comprises determining, based on the comparing, that the first and second changes are concurrent.

4. In a multimaster database system comprising a plurality of sites, a method for sharing and deconflicting data changes, the method comprising:
at a first site of the plurality of sites:
resolving two or more data objects together to produce a data object resolution change;
sharing the data object resolution change with one or more other sites of the plurality of sites;
at a second site of the plurality of sites:
receiving an update reflecting the data object resolution change made 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 vector for the data object;

comparing, for each of one or more of the two or more data objects, the version vector for the data object received in the update to a version vector at the second site for the data object to determine whether the data object resolution change and a version at the second site of the data object are identical, ordered, or concurrent;
determining, based on the comparing, that the data object resolution change is concurrent with a version at the second site of at least one of the two or more data objects; and
in response to determining that the data object resolution change is concurrent with a version at the second site of at least one of the two or more data objects, determining that the data object resolution change conflicts with a version at the second site of at least one of the two or more data objects;
wherein the method is performed by a plurality of computing devices.

5. One or more non-transitory computer-readable media storing instructions which, when executed by a plurality of computing devices, cause performing a method for sharing and deconflicting data changes in a multimaster database system comprising a plurality of sites, the method comprising:
at a first site of the plurality of sites, making a first change to a set of one or more links connecting two data objects by adding or removing one or more links from the set of links; wherein the set of links is associated at the first site with a first version vector for the set of one or more links; at a second site of the plurality of sites, making a second change to the set of links connecting the two data objects by adding or removing a link from the set of links; wherein the set of links is associated at the second site with a second version vector for the set of links; sharing the first change with the second site of the plurality of sites; receiving, at the second site, an update reflecting the first change to the set of links at the first site; wherein the update includes:
an identification of the set of links,
data reflecting the first change to the set of links at the first site, and
the first version vector for the set of links;
at the second site, comparing the first version vector for the set of links to the second version vector for the set of links to determine whether the first change to the set of links at the first set and the second change to the set of links at the second site are identical, ordered, or concurrent.

6. The one or more non-transitory computer-readable media of claim 5 , wherein the second change to the set of links is made at the second site before the first change to the set of links is made at the first site; and wherein the method further comprises determining, based on the comparing, that the first and second changes are ordered.

7. The one or more non-transitory computer-readable media of claim 5 , wherein the second change to the set of links is made at the second site before the first change to the set of links is made at the first site; and wherein the method further comprises determining, based on the comparing, that the first and second changes are concurrent.

8. One or more non-transitory computer-readable media storing instructions which, when executed by a plurality of computing devices, cause performing a method for sharing and deconflicting data changes in a multimaster database system comprising a plurality of sites, the method comprising:
at a first site of the plurality of sites:
resolving two or more data objects together to produce a data object resolution change;
sharing the data object resolution change with one or more other sites of the plurality of sites;
at a second site of the plurality of sites:
receiving an update reflecting the data object resolution change made 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 vector for the data object;

comparing, for each of one or more of the two or more data objects, the version vector for the data object received in the update to a version vector at the second site for the data object to determine whether the data object resolution change and a version at the second site of the data object are identical, ordered, or concurrent;
determining, based on the comparing, that the data object resolution change is concurrent with a version at the second site of at least one of the two or more data objects; and
in response to determining that the data object resolution change is concurrent with a version at the second site of at least one of the two or more data objects, determining that the data object resolution change conflicts with a version at the second site of at least one of the two or more data objects.

9. In a

Assignees

• Palantir Technologies Inc

Inventors

• Garrod John Kenneth
• Carrino John Antonio
• Brainard Katherine
• Scott Jacob
• Chang Allen

Classifications

• G06F16/2329 Primary

  using versioning · CPC title

• G06F16/273

  Asynchronous replication or reconciliation · CPC title