Garbage collection of tombstones for optimistic replication systems

• US 7,290,019 B2
• Filed: 02/13/2004
• Issued: 10/30/2007
• Est. Priority Date: 03/03/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Teodosiu, Dan, Bjørner, Nikolaj S., Yavorskiy, Rostislav
• Primary Examiner(s): Gaffin; Jeffrey
• Assistant Examiner(s): Ponikiewski; Tomasz
• Application Number:
  US10/779,030
• Publication Number:
  US 20040177100A1
• Time in Patent Office: 1,355 Days
• Field of Search: None
• US Class Current: 707/638
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method and system for synchronizing objects among members of a replica set. Objects on members of the replica set are quickly synchronized via a join algorithm that takes advantage of version vectors. When an object is deleted, the object is tombstoned (i.e., marked as “dead”). Tombstones are also replicated between the connected members of the replica set. After a period of time (e.g., a timeout), the tombstones are deleted. A slow sync algorithm executes periodically to ensure that objects that were not deleted via replicated tombstones are eventually deleted. An époque algorithm provides that members that have been offline for a long period of time will update their objects before they participate in a join synchronization.

Claims

1. A computer implemented method for deleting replicated objects and providing for garbage collection of tombstones within a replica set, the method comprising:

the computing system replicating an object that resides on a member of the replica set to at least one other member of the replica set, the replica set including at least two members;

deleting the object on at least one member of the replica set and indicating on that member of the replica set that the object has been deleted via at least one tombstone indicating the deletion of the object;

deleting at least one of the at least one tombstone; and

thereafter;

locating the object or a modified form of the object, having replaced the object, on a member of the replica set;

locating a different member of the replica set upon which the object has been deleted and upon which the tombstone indicating the deletion of the object has been deleted;

comparing version information of the member of the replica set with version information of the different member of the replica set;

determining when the object on the member of the replica set is subsumed by the different member of the replica set; and

when having determined that the object on the member of the replica set is subsumed by the version information of the different member of the replica set, deleting the object or modified form of the object from the member of the replica set.

2. The method of claim 1, wherein locating the object or a modified form of the object, having replaced the object, comprises finding a record in a database of a first member of the replica set, the record indicating a version of the object and that the object is live.

3. The method of claim 1, wherein determining that the object is subsumed by the version information comprises determining that the version of the object is less than or equal to the second member'"'"'s last-known version of any object on the first member.

4. The method of claim 1, wherein locating the object or a modified form of the object, having replaced the object, comprises finding a record in a database of a first member of the replica set and a record in a database of a second member of the replica set, each record indicating a version of the object residing on its respective member and that the object is live.

5. The method of claim 1, wherein comparing version information comprises:

obtaining a first and second version vector for the first and second members, respectively, the first version vector indicating a last-known version of any object on the second member and the second version vector indicating a last-known version of any object on the first member;

determining that the version of the object of the first member is subsumed by the second version vector;

determining that the version of the object of the second member is subsumed by the first version vector; and

determining that the versions of the objects are different from each other.

6. The method of claim 1, wherein deleting at least one of the at least one tombstone comprises deleting all of the tombstones.

7. The method of claim 1, wherein the object is associated with a version.

8. The method of claim 7, further comprising setting the version of the object when the object is created.

9. The method of claim 7, further comprising updating the version of the object when the object is modified or deleted.

10. The method of claim 1, wherein the object as it exists on a member of the replica set is prevented from being modified on that member after indicating that the object is deleted via the one or more tombstones.

11. The method of claim 1, wherein each member of the replica set maintains a version vector, the version vector indicating its respective member'"'"'s last-known version of any objects in each of the other members of the replica set.

12. The method of claim 11, wherein the version vector of a member that is synchronizing with another member is updated to the maximum of the version vectors of that member and the other member.

13. The method of claim 11, wherein not having information in a version vector for a particular member indicates that the last-known version of the particular member is zero.

14. The method of claim 13, wherein a version vector of a particular member is incremented each time an object is created, changed, or deleted on the particular member.

15. The method of claim 1, wherein the object is associated with a global identifier that remains constant as the object is modified, deleted, and replicated.

16. The method of claim 1, wherein deleting at least one of the at least one tombstone occurs after a period of time.

17. The method of claim 16, wherein the period of time depends on how many tombstones exist.

18. The method of claim 16, wherein the period of time depends on a measure of a generation rate for tombstones.

19. The method of claim 1 wherein processing information other than the one or more tombstones occurs when a member resumes communication with other members in a replica set before attempting to synchronize via a join if the member has not communicated with the other members over a period of time.

20. The method of claim 19, wherein the period of time exceeds a timeout at which tombstones are deleted.

21. The method of claim 1, wherein comparing version information is throttled to conserve bandwidth or computing resources.

22. A computer program product comprising a computer-readable storage medium having recorded thereon computer-executable instructions which, when executed, perform the method of claim 1.

23. A computer system comprising one or more computer processors and one or more computer-readable storage media storing computer-executable instructions that, when executed, implement the method recited in claim 1.