Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-06-30
2001-07-03
Breene, John (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S203000, C709S208000
Reexamination Certificate
active
06256634
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to a replicated database, and more particularly to the replication of data items in a replicated database, such as one used in a message queuing system for providing directory service.
BACKGROUND OF THE INVENTION
A message queuing system implements asynchronous communications which enable applications in a distributed processing network to send messages to, and receive messages from, other applications. A message may contain data in any format that is understood by both the sending and receiving applications. When the receiving application receives a request message, it processes the request according to the content of the message and, if required, sends a response message back to the original sending application. The sending and receiving applications may be on the same machine or on separate machines connected by a network. While in transit between the sending and receiving applications, the message queuing system keeps messages in holding areas called message queues. The message queues protect messages from being lost in transit and provide a place for an application to look for messages sent to it when it is ready.
In a proposed message queuing system, a replicated database is maintained for providing directory service for message queuing and routing operations. This directory service database includes a plurality of local databases maintained by respective directory servers on different machines. Each directory server maintains not only data items created by itself but also a replica of data items created by all other servers in the directory service database. When a server creates, modifies, or deletes its data items, it sends replication message packets to the other servers so that they can update their respective replicas. In the context of data replication, a server sending replication information is referred to as a “master,” and a server receiving the replication information is referred to as a “slave.” If a slave server learns or suspects that it has not received all of the replication information from a master server, it sends a synchronization request to the master server to obtain the missing replication information. To support the synchronization operation, when a server deletes a data item from its local database, it sets up a tombstone to memorialize the deletion so that the deletion can be replicated by other servers. As the configuration of the message queuing system changes over time, data items representing message queuing objects, such as message queues, are constantly created and deleted. With more and more data items deleted from the directory service, the number of tombstones increases correspondingly. Without an effective way to purge the tombstones, the tombstones may grow in an unbounded way and ultimately may fill up the memory space of the directory service database. On the other hand, if the tombstones are purged prematurely, i.e., before other servers have learned about the deletion, the synchronization operation cannot be performed properly.
SUMMARY OF THE INVENTION
In accordance with the present invention, there is provided a method and system for purging tombstones for deleted data items in a replicated database in which data items owned by one server are replicated by other servers. When a master server in the replicated database deletes a data item from its local database, it sets up a tombstone for the deleted data item and sends replication data regarding the deletion to one or more slave servers each of which maintains a replica of the master server's data items. The timing for purging the tombstone by the master server depends on the types of the slave servers receiving the replication data. For a slave server of a first type, the tombstone is purged only after the master server has received an acknowledgment from the slave server for receipt of the replication data regarding the deletion. For a slave server of a second type, the master server purges the tombstone after the tombstone has become sufficiently aged, without requiring the slave server to acknowledge that it has received the replication data regarding the deletion. In the event that the slave server fails to receive the replication data regarding the deletion and later requests for a synchronization to update its replica when the master has already purged the tombstone for the deletion, the master server cooperates with the slave server to perform a full synchronization to completely reconstruct the slave server's replica of data items of the master server. Efficient full synchronization methods are provided to enable the slave server to continue to serve read requests for the data items being updated during the full synchronization process.
Other advantages will become apparent with reference to the following detailed description when taken in conjunction with the drawings in which:
REFERENCES:
patent: 4499576 (1985-02-01), Fraser
patent: 4584679 (1986-04-01), Livingston et al.
patent: 4623886 (1986-11-01), Livingston
patent: 4736369 (1988-04-01), Barzilai et al.
patent: 4769815 (1988-09-01), Hinch et al.
patent: 4853842 (1989-08-01), Thatte et al.
patent: 5063562 (1991-11-01), Barzilai et al.
patent: 5163131 (1992-11-01), Row et al.
patent: 5247676 (1993-09-01), Ozur et al.
patent: 5285445 (1994-02-01), Lehnert et al.
patent: 5287103 (1994-02-01), Kasprzyk et al.
patent: 5367523 (1994-11-01), Chang et al.
patent: 5526358 (1996-06-01), Gregerson et al.
patent: 5526489 (1996-06-01), Nilakantan et al.
patent: 5557748 (1996-09-01), Norris
patent: 5572522 (1996-11-01), Calamvokis et al.
patent: 5572582 (1996-11-01), Riddle
patent: 5689706 (1997-11-01), Rao et al.
patent: 5758184 (1998-05-01), Lucovsky et al.
patent: 5761507 (1998-06-01), Govett
patent: 5764625 (1998-06-01), Bournas
patent: 5777987 (1998-07-01), Adams et al.
patent: 5778384 (1998-07-01), Provino et al.
patent: 5799321 (1998-08-01), Benson
patent: 5806065 (1998-09-01), Lomet
patent: 5812773 (1998-09-01), Norin
patent: 5812819 (1998-09-01), Rodwin et al.
patent: 5815667 (1998-09-01), Chien et al.
patent: 5819042 (1998-10-01), Hansen
patent: 5819272 (1998-10-01), Benson
patent: 5832514 (1998-11-01), Norin et al.
patent: 5835727 (1998-11-01), Wong et al.
patent: 5838907 (1998-11-01), Hansen
patent: 5845081 (1998-12-01), Rangarajan et al.
patent: 5854901 (1998-12-01), Cole et al.
patent: 5864669 (1999-01-01), Osterman et al.
patent: 5872968 (1999-02-01), Knox et al.
patent: 5875301 (1999-02-01), Duckwall et al.
patent: 5875306 (1999-02-01), Bereiter
patent: 5881051 (1999-03-01), Arrowood et al.
patent: 5887275 (1999-03-01), Nguyen et al.
patent: 5901138 (1999-05-01), Bader et al.
patent: 5920697 (1999-07-01), Masters et al.
patent: 5922049 (1999-07-01), Radia et al.
patent: 5956340 (1999-09-01), Afek et al.
patent: 6012059 (2000-01-01), Neimat et al.
Hornick and Zdonik, “A Shared, Segmented Memory System for an Object-Oriented Database”, ACM Transaction on Office Information Systems, vol. 5, No. 1, pp. 70-95, Jan. 1987.*
Chawathe et al., “Change Detection in Hierarchically Structured Information”, ACM, pp. 493-504, Jun. 1996.*
Blakeley et al.,Messaging and Queuing Using the MQI, McGraw Hill, Inc.; New York, NY, Jan. 1995.
Douglas E. Comer,Interneting with TCP/IP, vol. 1: Principles, Protocols and Architecture, Second Edition, Chapter 19, Jan. 1991.
Andrew S. Tanenbaum,Computer Networks, Third Edition, Prentice Hall, New Jersey; pp. 577-622; Jan. 1996.
Microsoft Message Queuing Services: A Guide to Reviewing Microsoft Message Queuing Service Release 1.0, Microsoft Corporation, Redmond, Washington, Jan. 1997.
Comer, Douglas E.,Internetworking With TCP/IP vol. 1: Principles, Protocols, and Architecture, Chapter 6: Determining an Internet Address at Startup (RARP) and Chapter 18: Client-Server Model of Interaction, pp. 83-88, 293-309, Prentice-Hall, Englewood Cliffs, New Jersey, Jan. 1991.
Benaloh, Josh et al,The Private Communication Techonology (PCT) Protocol, Internet Draft, available from http://premium.microsoft.com/msdn/library/bkgrnd/html/pct/hm
Hartmann Ronit
Moshaiov Lior
Breene John
Lewis Cheryl
Leydig , Voit & Mayer, Ltd.
Microsoft Corporation
LandOfFree
Method and system for purging tombstones for deleted data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for purging tombstones for deleted data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for purging tombstones for deleted data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2502799