Maintaining consistency of database replicas

• US 5,765,171 A
• Filed: 12/29/1995
• Issued: 06/09/1998
• Est. Priority Date: 12/29/1995
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Rabinovich, Michael, Kononov, Alex, Gehani, Narain H.
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): Coulter, Kenneth R.
• Application Number:
  US08/580,954
• Time in Patent Office: 893 Days
• Field of Search: 395/200.01, 395/200.3, 707/203, 707/201, 707/8
• US Class Current: 1/1
• 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: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A replication protocol which includes associating a database version vector with each copy of the database in the system is provided. Each database version vector keeps track of the total number of updates to any data items in its respective database replica and from which server those updates were originally performed. During replication between two replicas, the database version vectors of the replicas are compared to efficiently determine if update replication is necessary. If the database version vectors are not identical, the server possessing the more recent version of the data items propagates those data items to the server whose replica is older using conventional update propagation techniques. Identical database version vectors indicate that update propagation is not necessary. As such, the protocol avoids examining every data item in the database in order to determine the necessity of update propagation, which is required in conventional replication protocols.

Claims

1. In a computer network comprising a plurality of servers and a plurality of database replicas comprising a plurality of data items, at least n database replicas corresponding to n number of servers, where n≧

2, and wherein each of the n database replicas comprises at least x number of data items, where x is≧

2, a method for operating the network including maintaining consistency among the x data items in the n replicas comprising;

associating version information with the x data items in each of the n replicas, the version information recording the number of updates performed reflected on its responsive data item copy and on which of the n servers that the updates were originally performed;

providing n database version vectors (DBVVs), each corresponding to one of the n database replicas;

maintaining each of the n DBVVs to indicate updates that were applied to any of the x data items in the DBVV'"'"'s respective database replica and originally performed by the corresponding server; and

directly comparing the n DBVVs to each other to make an initial threshold determination of whether any of the data items in any of the DBVVs have been recently updated and thus require that a full comparison be made at the data item level to determine which of the data items in each of the database replicas need updating in order to restore complete consistency among each of the data items in the n replicas.

2. The method of claim 1 wherein each of the DBVVs comprises at least n components which correspond to the n servers, each of the components indicates updates that are reflected in the DBVV'"'"'s respective database replica and originally performed by the corresponding server.

3. The method of claim 2 wherein maintaining each of the DBVVs comprises:

in response to a first one of n servers performing an update, modifying the DBVV corresponding to the first server by incrementing its component corresponding to the first server to reflect the update; and

in response to the first server copying one of the x number of data items from a second one of n servers, modifying the components of the DBVV corresponding to the first server to reflect any additional updates acquired as a result of the copying from the second server and on which of the n servers that the additional updates were originally performed.

4. The method of claim 2 further comprises the step of scheduling a replication session between a first and a second of the n servers for propagating updates to maintain consistency between the database replicas of the first and second servers.

5. The method of claim 4 wherein the replication session comprises the steps of:

determining whether propagation of updates from the database replica of the first server to the database replica of the second server is necessary; and

propagating updates from the first database replica to the second database replica if update propagation is determined to be necessary.

6. The method of claim 5 wherein the determining step comprises comparing the DBVVs associated with the first replica with the second replica, and wherein identical DBVVs indicates that update propagation is not necessary and non-identical DBVVs indicates that update propagation is necessary.

7. The method of claim 6 wherein update propagation comprises sending more recent data items in the first replica to the second replica.

8. The method of claim 7 wherein the data items that are to be sent are determined by comparing the version information of the data items in the first replica with the version information of the corresponding data items in the second replica to identify the data items which are more recent in the first replica.

9. The method of claim 8 wherein the version information comprises version vectors, the version vectors comprising at least n components corresponding to the n servers, each of the n components indicates the number of updates to the version vector'"'"'s respective data item by the corresponding server.

10. The method of claim 9 wherein in response to receiving the more recent data items, the second server modifies the components in its DBVV to reflect any additional updates acquired as a result of the update from the first server and on which of the n servers that the additional updates were originally performed as follows:

space="preserve" listing-type="equation">V.sub.k.sup.new =V.sub.k.sup.old +(V.sub.1k -V.sub.2k);

1≦

k≦

n

where V_k^new is the modified component of the second server'"'"'s DBVV corresponding to the k^th server, V_k^old is the original component of the second server'"'"'s DBVV corresponding to the k^th server, V_1k is the version vector component of the data item on the first server which corresponds to the k^th server, and V_2k is the version vector component of the data item on the second server which corresponds to the k^th server.

11. The method of claim 6 wherein updates are stored as update records that contain information sufficient to redo the update and the identity of the server on which the update was originally performed.

12. The method of claim 11 wherein update propagation comprises sending the update records from the first server to the second server.

13. The method of claim 12 wherein the version information comprises version vectors, the version vectors comprising at least n components corresponding to the n servers, each of the n components indicates the number of updates to the version vector'"'"'s respective data item by the corresponding server.

14. The method of claim 13 wherein the DBVVs, in response to receiving one of the update records from the first server, the second server increments the component in its DBVV corresponding to the server on which the update was originally performed.