Managing Tombstones
Tombstones represent items that have been deleted from a replica. Primarily, tombstones help protect against reintroducing deleted items into a replica. To avoid potential performance or storage problems, tombstones must be periodically cleaned up. This cleanup should be carefully managed to avoid reintroducing deleted items.
Representing Tombstones
A replica can use any method to track deleted items. To perform this task, we recommend that a replica use a tombstone bit or a tombstone log.
Tombstone Bit
A replica defines that the metadata for an item contains a Boolean value that indicates whether the item has been deleted from the item store. When an item is deleted, this value is set to true in the metadata entry for that item. Using a tombstone bit is efficient for storage if lots of deleted items must be tracked because it only requires one additional bit per item. This method is less efficient for enumerating or cleaning up tombstones because the whole metadata store must be searched.
Tombstone Log
A replica maintains a separate log that lists items that have been deleted from the item store. When an item is deleted, an entry is added to the tombstone log. Using a tombstone log is inefficient for storage if lots of deleted items must be tracked because the log must contain an ID for each item that has been deleted. This method is efficient for enumerating or cleaning up tombstones because the list contains only deleted items.
Tombstone Cleanup
Each replica in a synchronization community contains knowledge only about its own state and not the state of any other replica. Therefore, it is impossible to determine when a tombstone has been replicated throughout the community. Therefore, for any particular replica, determining when and how to clean up tombstones is a completely local decision. For example, tombstones could be cleaned up based on the local timestamp or on space requirements. A replica could have a policy that tombstones cannot occupy more than 10 percent of the data set.
After a tombstone is cleaned up, a replica does not know about the deletion, but still must prevent the item from being reintroduced either in its own store or on another replica. To help prevent this problem, the creation version for each item and the forgotten knowledge of the replica are kept in the metadata store for the replica. When a replica cleans up a tombstone, it must record the tombstone version in its forgotten knowledge.
Recording Cleaned Up Tombstones by Using Managed Code
To record that metadata for a deleted item has been removed from the metadata store of a replica, call ForgetTo on the ForgottenKnowledge object of the replica. This method requires the version of the deleted item.
Recording Cleaned Up Tombstones by Using Unmanaged Code
To record that metadata for a deleted item has been removed from the metadata store of a replica, call IForgottenKnowledge::ForgetToVersion on the IForgottenKnowledge object of the replica. This method requires the version of the deleted item.
Providing Forgotten Knowledge to Sync Framework
If a replica tracks cleaned up tombstones by using forgotten knowledge, its associated provider must provide the forgotten knowledge to Sync Framework methods that require it, such as ChangeBatch (for managed code) or IProviderSyncServices::CreateChangeBatch (for unmanaged code). The provider must also save the forgotten knowledge along with the updated knowledge during synchronization, such as in its StoreKnowledgeForScope method (for managed code) or ISynchronousNotifyingChangeApplierTarget::SaveKnowledge method (for unmanaged code).
If a replica does not clean up tombstones and does not maintain forgotten knowledge, its associated provider must pass null (for managed code) or NULL (for unmanaged code) to Sync Framework methods that have a forgotten knowledge parameter.
Tombstone-Related Scenarios
Two tombstone-related scenarios to consider are an out-of-date replica that is requesting synchronization and a replica that sends an update to a deleted item. Sync Framework detects both of these scenarios.
Detecting an Out-of-Date Replica
In this scenario, the destination replica is out-of-date with respect to the source replica. Because the source replica has cleaned up its tombstones, there are deletions that the source replica no longer knows about. Therefore, the source provider cannot send changes that represent these deletions to the destination provider. Before changes are applied, Sync Framework, compares the forgotten knowledge of the source replica with the current knowledge of the destination replica. If the destination knowledge does not contain the forgotten knowledge, Sync Framework identifies the destination replica as out-of-date and begins a recovery synchronization.
If an application has registered an event handler, Sync Framework will give the application the opportunity to continue with or stop the full enumeration. In managed code, the FullEnumerationNeeded event will fire. In unmanaged code, the application will receive an ISyncCallback::OnFullEnumerationNeeded callback.
If the application has not registered an event handler, the full enumeration will automatically occur. A full enumeration enables Sync Framework to compare changes from the source provider with items in the destination replica and so determine which items must be deleted from the destination replica. Any item in the destination replica that does not have a corresponding change from the source provider is deleted from the destination replica.
Detecting an Update to a Deleted Item
In this scenario, the source replica is out-of-date with respect to the destination replica. This occurs when the source replica has not been synchronized since the last time the destination replica cleaned up its tombstones. A problem can occur when an item was deleted on the destination replica, has subsequently had its tombstone cleaned up from the destination replica, and that same item was updated on the source replica. The item appears in the change batch that the source provider sends to the destination provider. The destination provider must recognize that this item is not a new item; otherwise, the item will be incorrectly reintroduced into the destination replica.
Be aware that the current version for an item from the source replica is not useful to compare with the current knowledge of the destination replica, because the current version of the item that would be reintroduced is not contained in the current knowledge of the destination replica. Instead, the creation version of the item from the source replica is compared to the current knowledge of the destination replica to determine whether the item was previously known by the destination replica. Because the deletion of the item must have happened after the creation of the item and the current knowledge of the destination replica contains the deletion, the current knowledge must also contain the creation.
Therefore, before a new item is added to a destination replica, Sync Framework compares the creation version of the item to the current knowledge of the destination replica. If the destination knowledge contains the creation version of the item, the item was previously known but has been deleted and forgotten. The item is treated as an update-delete conflict.
See Also
Reference
ISyncCallback::OnFullEnumerationNeeded
FullEnumerationNeeded