heroku/WAL-E — Issue #28: tombstones as an intermediate deletion phase
Author: fdr
Created: 2012-01-17 00:23:37+00:00
State: open

When writing reporting code over the very-large S3 archives WAL-E creates, it's pretty hard to know -- for sure -- whether something has been deleted. One does not want to make their cache of backups sensitive to transient failures, for example. As-is, my existing S3 backup scanners never presume a backup is ever deleted, just "not seen for a while". If one hasn't seen a backup for some period, it can be presumed it probably is no longer present.

That is somewhat too messy if one wants to know with much more tight guarantees what backups are available, as in the case of point-in-time-recovery.

A solution is to make deletions two-phase, whereby the first phase will emit tombstones into S3 (which should prevent base backup downloading, as a precaution to the user). Those tombstones can be left in place for some period which I will coin the "decay" time, in which reporting programs can delete (or soft-delete) the record pointing to the base backup and its meta-information.

After that period has passed, the data associated with that tombstone, if any (the deletion pass can occur either when tombstones are dropped or at tombstone-decay time), is deleted, along with the tombstone. Any lingering backup records in other systems that scan S3 to condense information about the available backups becomes a system anomaly rather than the common case, however it is thought that this situation will be 'sufficiently rare' that it's more likely to be a mis-administration by a human or a faulty program rather than an eventual consistency problem/race condition.