Maintaining consistency of database replicas
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
14 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
- 2, and wherein each of the n database replicas comprises at least x number of data items, where x is≧
Specification