The present disclosure generally relates to distributed computing systems and, in particular, to cross-access control list data replication in a multi-master database system.
In a typical multi-master computing system, data is stored at each replication site of a group of replication sites, data changes may be made at any site of the group, and data changes made at one site are propagated to the rest of the group. A multi-master system typically either employs a “synchronous” replication scheme or an “asynchronous” replication scheme for propagating a data change made at one site to the rest of the sites in the group.
With typical synchronous multi-master replication schemes, each data change is applied at all sites in the group immediately or at none of the sites if one or more of the sites in the group cannot accept the data change. For example, one of the sites may be offline or unavailable. Many synchronous multi-master replication schemes are implemented using a two-phase commit protocol.
In contrast, with typical asynchronous multi-master replication schemes, a data change made at a site is immediately accepted at that site but propagation of the data change to other sites in the group may be deferred. Because propagation of data changes may be deferred, if one or more of the sites in the group are temporarily unavailable, the available sites in the group can continue to accept data changes, queuing the data changes locally until they can be propagated to the rest of the group. For this reason, a multi-master system employing an asynchronous replication scheme is typically considered to be more highly available than one employing a synchronous replication scheme. However, asynchronous multi-master replication brings with it the possibility of data change conflicts that occur as a result of concurrent data changes.
A data change conflict can occur in a multi-master system employing an asynchronous replication scheme when the same data is changed at two sites before either one of those data changes can be propagated to the other. For example, assume that at site A, data representing a particular person's eye color is changed to “brown”, and after that data change but before that data change can be propagated to site B, data at site B representing the same particular person's eye color is changed to “green”. Without additional information, it is unclear which data change is the “correct” change that should be adopted by all sites in the group.
Typically, a multi-master system employing an asynchronous replication scheme provides a mechanism for “deconflicting” data change conflicts. In many cases, deconflicting a data change conflict means to detect and resolve the data change conflict such that the resolution of the data change conflict is adopted at all sites. In some cases, the multi-master system may be able to deconflict a data change conflict automatically without requiring user intervention. In other cases, user intervention is required to decide which of the concurrent data changes should be adopted as the “correct” data change.
One possible approach for detecting data change conflicts in a multi-master system employing asynchronous replication is through the use of version vectors (sometimes referred to as vector clocks). A version vector may be defined as a logical timestamp associated with a data change, and provides a partial ordering of the associated data change with respect to other data changes. The logical timestamp is called “logical” in that its value has no inherent relation to real “physical” time. Typically, the logical timestamp is represented as a list of logical clocks, one logical clock per site in the system. The partial ordering is called “partial” in that a version vector does not provide a total ordering of the associated data change with respect to all other data changes in the system. Instead, two version vectors associated with two distributed data changes (i.e., two data changes at two different sites) can be compared to determine whether one data change happened before the other or whether the two data changes happened concurrently and thus, are mutually inconsistent (i.e., represent a data change conflict). Use of version vectors for detecting mutual inconsistencies in distributed systems is well documented, see e.g., “Detection of Mutual Inconsistency in Distributed Systems”, published by the Institute of Electrical and Electronics Engineers (IEEE) as IEEE Transactions on Software Engineering, VOL. SE-9, No. 3, May 1983, the disclosure of which is hereby incorporated by reference.
When used in the context of a multi-master system, a single version vector is typically maintained at each site in the system. When a site propagates a data change to another site, the propagating site includes its current version vector in the notification. The site receiving the notification can compare its version vector to the version vector received in the notification. This comparison can be used to determine whether the propagated data change happened before, happened after, or happened concurrently with the latest data change at the site receiving the notification.
Access control adds an additional layer of complexity to multi-master replication on top of the complexity of detecting data change conflicts. In particular, some sites in a multi-master system may implement access control policies that limit the information that is shared with other sites in the group. Further, a site may share certain information with some sites in the group that it does not share with other sites in the system. Many existing multi-master replication solutions employ version vectors on a per-site basis for detecting data change conflicts. These solutions do not adequately address the complexity introduced by access control.
Consider, for example, a multi-master system with four sites A, B, C, and D in which site A propagates data changes directly to sites B and C and sites B and C propagate data changes directly to site D but site A does not propagate data changes directly to site D. Further assume that, for security policy reasons, site A does not propagate certain information to site B even if that certain information is changed at site A and that site A does not propagate other certain information to site C even if that other certain information is changed at site A. Assume further still that site A does propagate to site B the other certain information that it does not propagate under the security policy to site C and that site A does propagate to site C the certain information it does not propagate to site B. For example, site A may not propagate social security numbers to site B and may not propagate home address information to site C. Finally, assume that there are no restrictions on the information propagated from sites B and C to site D.
Next, assume the following sequence of events that occur in the multi-master system:
Event 1: A data record Ra is created at site A with values for the three fields of the data record: “Name”, “Social Security Number”, and “Home Address”.
Event 2: Site A propagates to site B information reflecting the data change to site A at Event 1 including the Name and Home Address information of the record Ra but for access control reasons not the Social Security Number information of the record Ra. As a result, a data record Rb is stored at site B with the values for the Name and Home Address fields received from site A.
Event 3: Site A propagates to site C information reflecting the data change to site A at Event 1 including the Name and Social Security Address information of the record Ra but for access control reasons not the Home Address information of the record R. As a result, a data record Rc is stored at site C with the values for the Name and Social Security Number fields received from site A.
Event 4: The value of the Name field of record Rb is changed at site B to “John M. Smith”. Concurrently, the value of the Name field of record Rc is changed at site C to “J. M. S.” creating a data change conflict.
Event 5: Site B propagates to site D information reflecting the data change to site A at Event 1 and the data change to site B at Event 4 including the Name “John M. Smith” from record Rb and the Home Address information from record Rb. A data record Rd is stored at site D with the values for the Name and Home Address fields received from site B.
Event 6: Site C propagates to site D information reflecting the data change at site A at Event 1 and the data change at site C at Event 4 including the Name “J.M.S.” from record Rc and the Social Security Number from record Rc.
At Event 6 in the above example, per-site version vectors could be used to detect at site D that the record Rc conflicts with the record Rd by virtue of the concurrent updates to the Name fields of records Rb and Rc at Event 4. However, site D cannot determine from use of per-site version vectors alone whether the data change at site B at Event 4, in addition to changing the value the Name field, also deleted the Social Security Number field from record Rb. Similarly, site D cannot determine whether the data change at site C at Event 4, in addition to changing the value of the Name field, also deleted the Home Address field from record Rc. Ideally, in this case where the Social Security Number field and the Home Address field were not deleted but instead were filtered at site A implementing an access control policy, the resulting record Rd at site D after Event 6 would have values for all of the Name, Social Security Number, and the Home Address fields. Specifically, the record Rd would have as the value of the Name field either “John M. Smith” or “J.M.S” depending on how this data change conflict is deconflicted at site D, the value of the Home Address field received from site B, and the value of the Social Security Number field received from site C. Alternatively, if the Home Address field was deleted at Event 4, then the record Rd at site D after Event 6 should reflect the deletions.
The above-example is provided to illustrate an example of an issue left unaddressed by existing multi-master replication solutions. Problems in the field include detection of data change conflicts in a multi-master system while at the same time facilitating differentiation between a situation where a conflicting data change is missing information because the missing information was filtered under an access control policy and a situation where a conflicting data change is missing information because the missing information was deleted as part of the data change. More generally, the problem is providing multi-master replication in access controlled replication environments in a manner that is in line with user expectations.
USPTO Backgrounds
USPTO Backgrounds