Record tracking in database replication

• US 5,819,272 A
• Filed: 07/12/1996
• Issued: 10/06/1998
• Est. Priority Date: 07/12/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Benson, Max L.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/678,978
• Time in Patent Office: 816 Days
• Field of Search: 707/10, 707/201, 707/8, 707/202, 707/203, 395/182.04, 395/703
• US Class Current: 1/1
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

In a one aspect, a technique for tracking the status of records in replicated databases. Sets of identifiers (e.g., record identifiers or change numbers) are stored by individual replicas, and in some cases conveyed between replicas. The sets comprise lists of intervals, with each interval being either a single number (in the case of the interval containing only one identifier) or a pair of numbers representing the low and high bounds of the interval. Stored as lists of intervals, the sets can usually be efficiently compressed for compact storage or transmission. The technique is particularly useful for tracking the status of message records in distributed messaging systems. It is also particularly useful in "push" replication schemes as the status information represented by the sets of identifiers can be replicated simply by each replica sending its set of identifiers to other replicas. In a second aspect, a technique for handling per user read/unread data in a distributed database such as a client/server messaging system, particularly server transparent distributed databases, in which the replica server accessed by a user can change transparently to the user. Copies of the per user read/unread data are stored on a first server (e.g., the user'"'"'s home server on which the user'"'"'s mailbox is stored in a messaging system) and on the replica server currently accessed by the user. Changes made to the replica copy to reflect records read by the user are written back to the copy stored on the first server.

Claims

1. In a distributed database in which a plurality of replicas are stored on different servers connected to a network, and in which users access the replicas from a plurality of clients connected to the network, a computer implemented method of storing per user read/unread data indicating which of a plurality of records in the database have been read by particular users, the method comprising:

storing a first copy of the per user read/unread data on a first server;

determining the identity of a second server on which an accessed replica is stored;

copying the first copy of the per user read/unread data for that user from the first server to the second server to create a replica copy of the data;

updating the replica copy of the per user read/unread data on the second server to reflect records read by the user on the replica stored on the second server, and

updating the first copy of the per user read/unread data with changes made to the replica copy of the per user read/unread data.

2. The method of claim 1, wherein the first copy of the per user read/unread data is a master copy associated with a particular user.

3. The method of claim 2, wherein the per user read/unread data comprises numbers representing records read by the user associated with the data.

4. The method of claim 2, wherein the replica accessed by the user may change over time transparently to the user, and the identity of the second server on which the replica is stored is redetermined when the user accesses the database.

5. The method of claim 4, wherein the replica copy of the per user read/unread data is updated on the first server when the user finishes accessing the database.

6. The method of claim 4, wherein the replica copy of the per user read/unread data is updated on the second server at about the same time as updates are made to the master copy on the first server.

7. The method of claim 1, wherein the database is a messaging system and the database records are messages.

8. The method of claim 4 wherein the master copy of the per user read/unread data is kept on the same server as the messaging system mailbox of the user corresponding to the data.

9. The method of claim 1, wherein the per user read/unread data for a user is included essentially only in replicas accessed by that user.

10. The method of claim 4, wherein the step of copying the master copy of the per user read/unread data comprises:

examining a field indicating the identity of the last server from which the master copy of the per user read/unread data was updated, and

copying the per user read/unread data to the second server if the last server is a different server from the second server.

11. The method of claim 1, wherein the per user read/unread data comprises a set of change numbers currently assigned to records read by the user.

12. The method of claim 11 wherein the per user read/unread data comprises change numbers without associated record identifiers.

13. The method of claim 12 wherein the set of change numbers further comprises superseded change numbers.

14. The method of claim 13 wherein the set of change numbers further comprises change numbers of deleted records.

15. The method of claim 14 wherein the set of change numbers further comprises change numbers assigned for purposes other than identifying records changed in the database.

16. The method of claim 15 wherein the set of change numbers is stored as a list of intervals.

17. The method of claim 11 wherein for replication conflict records a plurality of change numbers, each corresponding to a record included in the replication conflict record, are included in the set of change numbers.

18. The method of claim 11 further comprising determining whether a particular record has been read by a user by determining whether the change number of the record is included in the set of change numbers of the per user read/unread data.

19. The method of claim 11 further comprising determining the number of records unread by a particular user by comparing the change numbers making up the per user read/unread data to a set of change numbers for all records in the database to determine the number of records read, and subtracting that number from the total number of records in the database.

20. A computer program, residing on a computer readable medium, for storing per user read/unread data for the records of a distributed database in which a plurality of replicas are stored on different servers connected to a network, and in which users access the replicas from a plurality of clients connected to the network, the computer program comprising instructions for:

storing a first copy of the per user read/unread data on a first server;

determining the identity of a second server on which the accessed replica is stored;

copying the first copy of the per user read/unread data for that user from the first server to the second server to create a replica copy of the data;

updating the replica copy of the per user read/unread data on the second server to reflect records read by the user on the replica stored on the second server; and

updating the first copy of the per user read/unread data with changes made to the replica copy of the per user read/unread data.

21. The method of claim 20, wherein the first copy of the per user read/unread data is a master copy associated with a particular user.

22. The method of claim 21, wherein the per user read/unread data comprises numbers representing records read by the user associated with the data.

23. The method of claim 21, wherein the replica accessed by the user may change over time transparently to the user, and the identity of the second server on which the replica is stored is redetermined when the user accesses the database.

24. The method of claim 23, wherein the master copy of the per user read/unread data is updated on the first server when the user finishes accessing the database.

25. The method of claim 23, wherein the replica copy of the per user read/unread data is updated on the second server at about the same time as updates are made to the master copy on the first server.

26. The method of claim 20, wherein the database is a messaging system and the database records are messages.

27. The method of claim 26 wherein the master copy of the per user read/unread data is kept on the same server as the messaging system mailbox of the user corresponding to the data.

28. The method of claim 20, wherein the per user read/unread data for a user is included essentially only in replicas accessed by that user.

29. The method of claim 23, wherein the step of copying the master copy of the per user read/unread data comprises:

examining a field indicating the identity of the last server from which the master copy of the per user read/unread data was updated, and

copying the per user read/unread data to the second server if the last server is a different server from the second server.

30. The method of claim 20, wherein the per user read/unread data comprises a set of change numbers currently assigned to records read by the user.

31. The method of claim 30 wherein the per user read/unread data comprises change numbers without associated record identifiers.

32. The method of claim 31 wherein the set of change numbers further comprises superseded change numbers.

33. The method of claim 32 wherein the set of change numbers further comprises change numbers of deleted records.

34. The method of claim 33 wherein the set of change numbers further comprises change numbers assigned for purposes other than identifying records changed in the database.

35. The method of claim 34 wherein the set of change numbers is stored as a list of intervals.

36. The method of claim 30 wherein for replication conflict records a plurality of change numbers, each corresponding to a record included in the replication conflict record, are included in the set of change numbers.

37. The method of claim 30 further comprising determining whether a particular record has been read by a user by determining whether the change number of the record is included in the set of change numbers of the per user read/unread data.

38. The method of claim 30 further comprising determining the number of records unread by a particular user by comparing the change numbers making up the per user read/unread data to a set of change numbers for all records in the database to determine the number of records read, and subtracting that number from the total number of records in the database.

39. A method for tracking the status of records in a distributed database in which a plurality of replicas are stored on different servers connected to a network, a method of storing a set of identifiers, the method comprising:

using an interval to represent a series of identifiers in the set;

describing the interval with a low and a high bound,

the low bound being a number representative of the smallest number in the series of identifiers; and

the high bound being a number representative of the largest number in the series of identifiers.

40. The method of claim 39 wherein the set includes singletons as well as intervals, a singleton being the case in which the set of identifiers consists of a single number.

41. The method of claim 39 wherein the set contains a plurality of intervals, each described by a low and a high bound.

42. The method of claim 39 wherein the set is conveyed from one replica to another replica to update a corresponding set stored on the other replica.

43. The method of claim 42 wherein the identifiers are change numbers.

44. The method of claim 42 in which the distributed database is a messaging system, and the records are messages.

45. A computer program, resident on a computer readable medium, for a distributed database in which a plurality of replicas are stored on different servers connected to a network, the computer program comprising instructions for:

storing sets of identifiers to identify selected records of the database;

using an interval to represent a series of identifiers in the set;

describing the interval with a low and a high bound,

the low bound being a number representative of the smallest number in the series of identifiers; and

the high bound being a number representative of the largest number in the series of identifiers.

46. The computer program of claim 45 wherein the set includes singletons as well as intervals, a singleton being the case in which the set of identifiers consists of a single number.

47. The computer program of claim 45 wherein the set contains a plurality of intervals, each described by a low and a high bound.

48. The computer program of claim 45 wherein the set is conveyed from one replica to another replica to update a corresponding set stored on the other replica.

49. The computer program of claim 45 wherein the identifiers are change numbers.

50. The computer program of claim 48 wherein the identifiers are record identifiers.

51. The method of claim 48 in which the distributed database is a messaging system, and the records are messages.