Method and system for purging tombstones for deleted data items in a replicated database

• US 6,256,634 B1
• Filed: 06/30/1998
• Issued: 07/03/2001
• Est. Priority Date: 06/30/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hartmann, Ronit, Moshaiov, Lior
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Lewis, Cheryl
• Application Number:
  US09/107,719
• Time in Patent Office: 1,099 Days
• Field of Search: 707/101, 707/202, 707/206, 709/203, 709/208
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• 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/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and system coordinates the purging of tombstones for data items deleted from a directory service database of a message queuing system. The directory service database is a replicated database with a plurality of servers, and the data items owned by one server are replicated by all other servers in the system. The directory service database supports a synchronization mechanism for a slave server to request for replication data from a master server. To support the synchronization mechanism, a tombstone is set up each time a server deletes a data item from its local database. For a slave server of a first type, the master server purges the tombstone after receiving an acknowledgment from the slave server for receipt of replication information regarding the deletion. For a slave server of a second type, the master server purges the tombstone after the tombstone has become sufficiently aged. If the slave server of the second type fails to receive the replication data and makes a synchronization request for a range of write operations including the deletion and the master server has already purged the tombstone for the deleted item, a full synchronization is performed between the master and slave servers such that the slave server reconstructs a fresh copy of data items currently in the database of the master server.

Claims

1. A method of purging tombstones for memorializing deleted data items in a replicated database in which a slave server maintains a replica of data items stored by a master server, comprising the steps of:

performing a deletion by a master server to delete a data item stored by the master server;

setting up by the master server a tombstone for the deleted data item;

transmitting, from the master server to the slave server, a replication packet containing replication data regarding the deletion; and

purging, by the master server, the tombstone for the deleted data item after an age of the tombstone has reached a pre-selected threshold.

2. A method as in claim 1, wherein the age of the tombstone is indicated by a time stamp of the tombstone and an operation sequence number of the tombstone.

3. A method as in claim 1, further including the step of sending a message from the master server to the slave server indicating an extent to which the master server has purged tombstones for data items deleted by the master server.

4. A method as in claim 1, further including the step of assigning an operation sequence number to the deletion of the data item for identification thereof, and wherein the replication data includes the operation sequence number of the deletion.

5. A method as in claim 1, further including the steps of:

transmitting, from the slave server to the master server, a synchronization request for information for updating the replica maintained by the slave server;

determining, by the master server, whether the synchronization request specifies an update range that covers the deletion of the data item and the tombstone for the deleted data item is purged by the master server; and

performing a full synchronization to reconstruct the replica of the slave server to match the data items stored by the master server when the update range specified in the synchronization request covers the deletion of the data item and the tombstone for the deleted data item is purged by the master server.

6. A method as in claim 5, wherein the step of performing the full synchronization includes retaining by the slave server the replica of data items during the full synchronization to allow the slave server to serve read requests for said replica of data items.

7. A method as in claim 6, wherein each data item has an operation sequence number associated therewith, and wherein the step of performing the full synchronization includes:

setting operation sequence numbers of data items of the replica maintained by the slave server to zero;

transmitting, from the master server to the slave server, replication data regarding the data items stored by the master server;

reconstructing the replica of the slave server according to the replication data regarding the data items stored by the master server; and

deleting, after the reconstructing, data items of the replica with a zero sequence.

8. A computer-readable medium having computer executable instructions for performing the steps recited in claim 7.

9. A method as in claim 6, wherein each data item has a unique identification number and an operation sequence number associated therewith, and wherein the step of performing the full synchronization includes:

sending from the master server to the slave server a sorted list of the unique identification numbers of data items stored by the master server and the associated operation sequence numbers thereof;

comparing, by the slave server, the sorted list sent by the master with a sorted list of unique identification numbers of data items in the replica of the slave server with associated operation sequence numbers thereof to identify data items in the replica that are not on the sorted list of the master server and data items in the replica that are on both the sorted lists of the master server and the slave server but have different associated operation sequence numbers on the two sorted lists; and

deleting from the replica the data items not on the sorted list of the master server;

sending a request from the slave server to the master server for data items that are on both sorted lists but with different associated operation sequence numbers on the two sorted lists.

10. The method of claim 1, further including the steps of:

transmitting replication data regarding the deletion to a second slave server which maintains a second replica of the data items of the master server;

awaiting, by the master server, an acknowledgment from the second slayer server of receipt of the replication data before purging the tombstone for the deleted data item.

11. A method of purging tombstones for memorializing deleted data items in a replicated database having first, second, and third servers each having a local database and the second and third servers each maintaining a replica of data items maintained by the first server, comprising the steps of:

performing a deletion by the first server to delete a data item from the local database of the first server;

setting up by the first server a first tombstone for the data item deleted by the first server;

transmitting, from the first server to the second server, a first replication packet containing replication data regarding the data item deleted by the first server;

transmitting, from the first server to the third server, a second replication packet containing replication data regarding the data item deleted by the first server;

receiving an acknowledgement from the second server to the first server regarding receipt of the first replication packet; and

purging, by the first server, the first tombstone after receiving the acknowledgement from the second server and after an age of the first tombstone has reached a pre-selected threshold.

12. A method as in claim 11, wherein the age of the first tombstone depends on a time stamp and an operation sequence number of the tombstone.

13. A method as in claim 11, further including the steps of:

deleting, by the second server, the data item deleted by the first server from the replica maintained by the second server upon receiving the first replication packet;

setting up by the second server a second tombstone for deletion of the data item from the replica of the second server; and

sending, by the second server, a third replication packet containing replication data regarding the deleted data item to a fourth server of the replicated database, the fourth server maintaining a replica of data items maintained by the second server.

14. A method as in claim 13, further including the step of purging, by the second server, the second tombstone after the first server has purged the first tombstone and after an age of the second tombstone has reached the pre-selected threshold.

15. A method as in claim 11, further including the steps of:

transmitting, from the third server to the first server, a synchronization request for information for updating the replica of the third server;

determining, by the first server, whether the synchronization request specifies an update range that covers the deletion of the data item and the first tombstone is purged by the first server; and

performing a full synchronization to reconstruct the replica of the third server to match the data items of the first server when the update range specified in the synchronization request covers the deletion of the data item and the first tombstone is purged by the first server.

16. A computer-readable medium having computer executable instructions for performing the steps recited in claim 15.

17. A replicated database system comprising:

a first server having a first database for storing data items, a deletion table for storing deletion records for data items deleted by the first server from the first database, and a purge table for storing data regarding purge operations performed by the first server on the deletion records in the deletion table, each deletion record in the deletion table having a time stamp for deletion of a corresponding data item, the purge table including a field indicating an extent to which the first server has purged the deletion records in the deletion table; and

a second server having a second database for maintaining a replica of the data items stored in the first database,

the first server programmed to place a deletion record in the deletion table for a data item deleted from the first database, send replication data regarding the deleted data item to the second server for updating the replica maintained by the second server, and purge the deletion record after the deletion record has reached a pre-selected age.

18. A replicated database system as in claim 17, further including a third server having a third database for maintaining a replica of the data items stored in the first database, and wherein the first server programmed to purge the deletion record for the deleted data item after receiving an acknowledgment from the third server for receiving replication data sent by the first server regarding the deletion of the deleted data item.

19. A computer-readable medium having stored thereon a data structure comprising:

a first data field containing data representing an identification number identifying a data owner in a replicated database, the data owner owning data items each having an operation sequence number associated therewith; and

a second data field containing data representing a purged sequence number identifying an operation sequence number up to which a server in the replicated database maintaining said data structure has purged tombstones set up for data items owned by said data owner and deleted by the server.

20. A computer-readable medium having stored thereon a data structure comprising:

a first data field containing a unique identification number of a data item deleted from a local database of a server in a replicated database;

a second data field containing a sequence number associated with the deletion of the data item from the local database;

a third data field containing a time stamp indicating a time of the deletion of the data item, and

a fourth data field containing a unique identification number for an owner of the deleted data item.

21. A computer-readable medium having computer-executable instructions for performing steps comprising:

performing a deletion by a master server in a replicated database to delete a data item stored by the master server;

setting up by the master server a tombstone for the deleted data item;

transmitting, from the master server to a slave server in the replicated database, a replication packet containing replication data regarding the deletion, the slave server maintaining a replica of the data items stored by the master server; and

purging, by the master server, the tombstone for the deleted data item after an age of the tombstone has reached a pre-selected threshold.

22. A computer-readable medium having computer-executable instructions for performing steps comprising:

performing a deletion by a first server in a replicated database to delete a data item from a local database of the first server;

setting up by the first server a first tombstone for the data item deleted by the first server;

transmitting, from the first server to a second server in the replicated database, a first replication packet containing replication data regarding the data item deleted by the first server, the second server maintaining a replica of data items in the local database of the first server;

transmitting, from the first server to the third server in the replicated database, a second replication packet containing replication data regarding the data item deleted by the first server, the third server maintaining a replica of data items in the local database of the first server;

sending an acknowledgment from the second server to the first server regarding receipt of the first replication packet; and

purging, by the first server, the first tombstone after receiving the acknowledgment from the second server and after an age of the first tombstone has reached a pre-selected threshold.