Maintaining consistency of database replicas
First Claim
1. In a computer network comprising at least one server for serving at least one client, said network being adapted for storing a plurality of database replicas, each of said database replicas comprising a plurality of data items, a method for maintaining consistency among corresponding data items in said database replicas without the need to examine content or version information for every one of said data items in any of said database replicas, comprising the steps of:
- generating a database version vector for each of at least a pair of said database replicas, each of said database version vectors comprising a plurality of version vector components, said version vector components being one-to-one associated with each of said servers having one of said database replicas, each of said version vector components reflecting the number of updates previously performed on said corresponding data item at said server;
associating version information with each of said data items in each of said database replicas;
maintaining one or more logs of updates associated with each of said database replicas;
each of said logs having the property that, for every data item x in a particular one of said database replicas and every server j that has one of said database replicas, said log for said particular database replica contains at least a log record 1(x,j) of the last update to data item x at server j that is reflected in said particular database replica'"'"'s copy of data item x, said log record containing at least the name of data item x and the total update count of all updates that server j had seen at the time of the last update made from server j to said particular database replica; and
determining which of said data items in each of said database replicas needs updating in order to restore complete consistency among each of said data items in a pair of said database replicas. comprising the steps, in combination of;
comparing the database version vectors of said pair of said database replicas in a component-wise fashion in order to make an initial threshold determination of whether any of said data items in any of said database replicas have been recently updated and thus require that a full comparison be made at the data item level; and
determining, without the need to examine said version information of all of said data items, which individual data items in each of said database replicas needs updating with updates present in corresponding data items of another database replica, comprising the steps of;
for every server j having one of said database replicas with a version vector component in its associated database version vector that is greater than the corresponding version vector component in the database version vector of said particular database replica, determining which of said log records 1(x,j) on said server j have a total update count that exceeds the total number of updates obtained from said corresponding version vector component of the database version vector for said particular database; and
determining therefrom that the corresponding data items in said particular database replica are older than the corresponding data items in said server j'"'"'s database replica and therefore need to be updated.
4 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for maintaining consistency in databases among data processors of a computer network involves an improved epidemic protocol involving the generation of database version vectors for database replicas. Overhead of the protocol grows linearly with the number of data items being copied during an update propagation, not with the number of data items as in typical epidemic protocols. Since this number is less than the total number of data items in the database, the present protocol promises significant reduction in overhead. A log record is generated including at least the name of the updated data item. The log record has an associated time stamp for the updated data item name in one embodiment or an associated version vector value in another. In the event of out-of-bound copying, an auxiliary log record is maintained.
-
Citations
32 Claims
-
1. In a computer network comprising at least one server for serving at least one client, said network being adapted for storing a plurality of database replicas, each of said database replicas comprising a plurality of data items, a method for maintaining consistency among corresponding data items in said database replicas without the need to examine content or version information for every one of said data items in any of said database replicas, comprising the steps of:
-
generating a database version vector for each of at least a pair of said database replicas, each of said database version vectors comprising a plurality of version vector components, said version vector components being one-to-one associated with each of said servers having one of said database replicas, each of said version vector components reflecting the number of updates previously performed on said corresponding data item at said server; associating version information with each of said data items in each of said database replicas; maintaining one or more logs of updates associated with each of said database replicas;
each of said logs having the property that, for every data item x in a particular one of said database replicas and every server j that has one of said database replicas, said log for said particular database replica contains at least a log record 1(x,j) of the last update to data item x at server j that is reflected in said particular database replica'"'"'s copy of data item x, said log record containing at least the name of data item x and the total update count of all updates that server j had seen at the time of the last update made from server j to said particular database replica; anddetermining which of said data items in each of said database replicas needs updating in order to restore complete consistency among each of said data items in a pair of said database replicas. comprising the steps, in combination of; comparing the database version vectors of said pair of said database replicas in a component-wise fashion in order to make an initial threshold determination of whether any of said data items in any of said database replicas have been recently updated and thus require that a full comparison be made at the data item level; and determining, without the need to examine said version information of all of said data items, which individual data items in each of said database replicas needs updating with updates present in corresponding data items of another database replica, comprising the steps of; for every server j having one of said database replicas with a version vector component in its associated database version vector that is greater than the corresponding version vector component in the database version vector of said particular database replica, determining which of said log records 1(x,j) on said server j have a total update count that exceeds the total number of updates obtained from said corresponding version vector component of the database version vector for said particular database; and determining therefrom that the corresponding data items in said particular database replica are older than the corresponding data items in said server j'"'"'s database replica and therefore need to be updated. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A processor for use in a computer network comprising at least one server for serving at least one client, said network being adapted for storing a plurality of databases comprising a plurality of data items, said processor for:
-
(i) generating a database version vector for each one of at least a pair of database replicas of said plurality of databases, each of said database version vectors comprising a plurality of version vector components, said version vector components being one-to-one associated with each of said servers having one of said database replicas, each of said version vector components reflecting the number of updates previously performed on said corresponding data item at said server; (ii) maintaining one or more logs of updates associated with each of said database replicas;
each of said logs having the property that, for every data item x in a particular one of said database replicas and every server i that has one of said database replicas, said log for said particular database replica contains at least a log record 1(x,j) of the last update to data item x at server j that is reflected in said particular database replica'"'"'s copy of data item x, said log record containing at least the name of data item x and the total update count of all updates that server j had seen at the time of the last update made from server i to said particular database replica; and(iii) determining which of said data items in each of said database replicas needs updating in order to restore complete consistency among each of said data items in a pair of said database replicas by; comparing database version vectors for a pair of database replicas in a component-wise fashion in order to make an initial threshold determination whether update propagation is required between at least said pair of database replicas; and determining which individual data items in each of said database replicas needs updating with updates present in corresponding data items of another database replica by, for every server j with one of said database replicas having a version vector component in its associated database version vector that is greater than the corresponding version vector component in the database version vector of said particular database replica, determining which of said log records 1(x,j) on said server j have a total update count that exceeds the total number of updates from the corresponding version vector component of the database version vector for said particular database, the corresponding data items in said particular database replica therefore being older and needing to be updated; and said processor further having access to memory for storing said generated database version vector. - View Dependent Claims (23, 24, 25)
-
-
26. A computer network comprising at least one server for serving at least one client, said network being adapted for storing a plurality of databases comprising a plurality of data items, said computer network comprising:
a processor for; (i) generating a database version vector in at least one of a pair of database replicas of said plurality of databases, each of said database version vectors comprising a plurality of version vector components, said version vector components being one-to-one associated with each of said servers having one of said database replicas, each of said version vector components reflecting the number of updates previously performed on said corresponding data item at said server; (ii) maintaining one or more logs of updates associated with each of said database replicas;
each of said logs having the property that, for every data item x in a particular one of said database replicas and every server j that has one of said database replicas, said log for said particular database replica contains at least a log record 1(x,j) of the last update to data item x at server j that is reflected in said particular database replica'"'"'s copy of data item x, said log record containing at least the name of data item x and the total update count of all updates that server j had seen at the time of the last update made from server j to said particular database replica; and(iii) determining which of said data items in each of said database replicas needs updating in order to restore complete consistency among each of said data items in a pair of said database replicas by; comparing database version vectors for said pair of database replicas in a component-wise fashion in order to make an initial threshold determination whether update propagation is required between at least said pair of database replicas; and determining which individual data items in each of said database replicas needs updating with updates present in corresponding data items of another database replica by, for every server j with one of said database replicas having a version vector component in its associated database version vector that is greater than the corresponding version vector component in the database version vector of said particular database replica, determining which of said log records 1(x,j) on said server j have a total update count that exceeds the total number of updates from the corresponding version vector component of the database version vector for said particular database, the corresponding data items in said particular database replica therefore being older and needing to be updated; and memory for storing said generated database version vectors and said log records. - View Dependent Claims (27, 28, 29, 30)
-
31. In a computer network comprising at least one server for serving at least one client, said network being adapted for storing a plurality of database replicas, each of said database replicas comprising a plurality of data items, a method for maintaining consistency among corresponding data items in said database replicas without the need to examine content or version information for every one of said data items in any of said database replicas, comprising the steps of:
-
generating a database version vector for each of at least a pair of said database replicas, each of said database version vectors comprising a plurality of version vector components, said version vector components being one-to-one associated with each of said servers having one of said database replicas, each of said version vector components reflecting the number of updates previously performed on said corresponding data item at said server; associating version information with each of said data items in each of said database replicas; maintaining one or more logs of updates associated with each of said database replicas;
each of said logs having the property that, for every data item x in a particular one of said database replicas and every server j that has one of said database replicas, said log for said particular database replica contains at least a log record 1(x,j) of the last update to data item x at server j that is reflected in said particular database replica'"'"'s copy of data item x, said log record containing at least the name of data item x and a timestamp assigned to data item x reflecting the time according to the clock on said server j that said data item x was last updated by server j; anddetermining which of said data items in each of said database replicas needs updating in order to restore complete consistency among each of said data items in a pair of said database replicas, comprising the steps, in combination of; comparing the database version vectors of said pair of said database replicas in a component-wise fashion in order to make an initial threshold determination of whether any of said data items in any of said database replicas have been recently updated and thus require that a full comparison be made at the data item level; and determining, without the need to examine said version information of all of said data items, which individual data items in each of said database replicas needs updating with updates present in corresponding data items of another database replica, comprising the steps of; for every server j with one of said database replicas having a version vector component in its associated database version vector that is greater than the corresponding version vector component in the database version vector of said particular database replica, determining which of said log records 1(x,j) on said server j have a timestamp that is later than the timestamp in the corresponding log record on said particular database; and determining therefrom that the corresponding data items in said particular database replica are older than the corresponding data items in said server j'"'"'s database replica and therefore need to be updated. - View Dependent Claims (32)
-
Specification