Maintaining consistency of database replicas

• US 6,098,078 A
• Filed: 12/23/1996
• Issued: 08/01/2000
• Est. Priority Date: 12/29/1995
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.), Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Kononov, Alex, Rabinovich, Michael, Gehani, Narain H.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US08/771,908
• Time in Patent Office: 1,317 Days
• Field of Search: 707/1-206, 395/182-200
• US Class Current: 707/610
• 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/959 Network
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

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.

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; 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.

2. The method as recited in claim 1 wherein said generating and comparing steps are performed by a processor of a computer of said network.

3. A method as recited in claim 2 wherein said processor of said computer is a processor of a server of said at least one server.

4. A method as recited in claim 2 wherein said processor of said computer is a processor of at least one client of said at least one server.

5. A method as recited in claim 1 wherein one of said pair of database replicas is stored in shared memory of said network.

6. A method as recited in claim 1 wherein one of said pair of database replicas is stored in memory of said at least one server.

7. A method as recited in claim 6 wherein one of said pair of database replicas is stored in memory of said at least one client.

8. The method of claim 1 further comprising the step of organizing, for a particular database replica, the log records corresponding to the last updates to every one of said data items by every one of said servers having one of said database replicas said log records being organized into a log vector having a plurality of components, each of said log vector components being one-to-one associated with one of said servers having one of said database replicas.

9. The method of claim 8 wherein each component of each of said log vectors is maintained as a doubly linked list, said doubly linked list having a head and a tail and containing log records of updates originated at said server associated with said log vector component, all of said log records in each of said log vector components being sorted in ascending order of said total update count contained in said log records, each of said log records being configured so as to point to both a predecessor and a successor one of said log records.

10. The method of claim 9 further comprising the step of associating an array of pointers with a data item.

11. The method of claim 10 wherein an element in the array of pointers points to the log record of the last update to the data item originated on the corresponding node.

12. The method of claim 9, wherein the step of determining which of said log records 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 replica comprises the step of selecting log records in the log vector component on said server j corresponding to said particular server, starting from said tail of said doubly linked list and proceeding to said head, until the first of said log records is encountered that has a total update count which does not exceed the number of updates in the corresponding component of said particular database replica database version vector.

13. The method of claim 12, wherein said server j sends log records selected from said log vector to the server of said particular database replica, in addition to any information sent during update propagation.

14. The method of claim 13, wherein a log vector is maintained on a server by the steps of:

associating an array of pointers with each data item, there being an element of said array for every component in said log vector;

storing, in the i-th element of the array of pointers associated with any data item x, a pointer to the log record of the last update to data item x which originated on server i;

when a server j performs an update to data item x, appending the corresponding record at the end of the component of said log vector corresponding to server j;

when a first server receives log records from a second server during update propagation, appending said received records to the corresponding components of said first server'"'"'s log vector, said appending being done in an order determined by the total update counts contained in said received records; and

when a server adds a new log record 1(x,j) to its associated log vector, removing from said log vector the log record pointed to by the j-th element of the array of pointers for data item x and updating said element to point to the newly added log record.

15. The method of claim 14, wherein each of said database version vectors is maintained on a first server by the steps of:

utilizing database version vectors as version information associated with every data item, the i-th component of the database version vector associated with any data item x on said first server recording the number of updates seen by server i and reflected in data item x on said first server;

initially setting all version vector components of said database version vector to 0;

incrementing the version vector component corresponding to said first server when said first server performs an update to any of said data items in the first server'"'"'s database replica; and

when any data item x on said first server is brought up-to-date with respect to a second server, for each server k such that the server k version vector component of the database version vector for data item x on said second server is greater than the server k version vector component of the database version vector for data item x on said first server, adding the difference between the two version vector components to said server k version vector component of said database version vector for data item x on said first server.

16. The method of claim 1 wherein each database version vector comprises n components where n is the number of nodes maintaining a replica of the database.

17. The method of claim 16 comprising the initial step of setting all components of each database version vector to 0.

18. The method of claim 16 further comprising the step of incrementing a component corresponding to node i of node i'"'"'s database version vector, when node i updates a data item.

19. The method of claim 16 further comprising the step of recording the time stamp of the update in a record corresponding to node i of node i'"'"'s database version vector, when node i does an update of a data item.

20. The method of claim 1 further comprising the step of generating an auxiliary version vector when a data item of a database replica is copied out-of-bounds.

21. The method of claim 20 further comprising the step of generating an auxiliary log record for updates to out-of-bound data items.

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.

23. The processor of claim 22, wherein each log record is maintained in said memory via a log vector, each log vector having a plurality of components, each of said log vector components being one-to-one associated with one of said servers having one of said database replicas, each of said log vector components containing the log records corresponding to the last updates to every one of said data items by one of said servers having one of said database replicas.

24. The processor of claim 22 wherein said memory is associated with said computer network.

25. The processor of claim 22 wherein said memory is associated with one of said server or said client.

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.

27. The network of claim 26, wherein each log record is maintained in said memory via a log vector, each log vector having a plurality of components, each of said log vector components being one-to-one associated with one of said servers having one of said database replicas, each of said log vector components containing the log records corresponding to the last updates to every one of said data items by one of said servers having one of said database replicas.

28. The network of claim 26 where each database version vector comprises n components where n is the number of nodes maintaining a replica of the database.

29. The computer network of claim 26 wherein said memory is associated with said computer network.

30. The computer network of claim 26 wherein said memory is associated with said processor.

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; 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 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.

32. The method of claim 31, wherein each of said database version vectors is maintained on a first server by the steps of:

utilizing database version vectors as version information associated with every data item, the i-th component of the database version vector associated with a data item x on said first server contains the time, according to the clock on a server i, of the last update originally performed by said server i and reflected in said data item x on said first server;

initially setting all version vector components of said database version vector to 0;

storing, in the version vector component corresponding to said first server, the time when said first server performs an update to any data item in said first server'"'"'s database replica; and

when all data items on said first server are brought up-to-date with respect to a second server, setting each version vector component of said database version vector on said first server to the maximum of the old version vector component value and the value of the corresponding version vector component in the database version vector of said second server.