• The repository format invariants are always preserved: it's never corrupted, even when clients are interrupted.

• Avoid if possible the user ever needing to decide to break a lock: this is toilsome, probably hard for a human to decide absolutely reliably, and tends to cause problems for scripts or automated operations, where there is no human to punt to.

• Readers should be "physically" read-only: they don't need permission to write and so they cannot write a lock file.

• Support deletion of old versions and any objects they reference. (This might be manually or automatically triggered to free up space or to remove things that are older than a retention period.)

• Support storing archives on a remote machine over sftp or on an object store such as S3. So we cannot rely on Unix flocks, etc. And, remote archives will not always be accessed from a single machine.

Assume that clients may be interrupted, disconnected, or crash, at any time. (It's OK if they try to clean up, but we can't assume it will always work.)

We'll assume that the files written up to any moment when the client is interrupted will all be readable in future. This is not quite true, if for example the archive is written to a local filesystem and the machine abruptly loses power or crashes while a backup is underway: filesystems generally don't guarantee a perfect ordering across files, and so we may end up with the archive referencing blocks that aren't present, or that are corrupt.

However, in that circumstance it's very hard to make any guarantees at all about what will be seen after recovery, and so we mostly handle this by read operations being tolerant of missing blocks. (There is an ancillary problem here that really future backups should notice that the blocks are missing or corrupt, and try to avoid referencing them. But this is out of scope for this document.) Hopefully abrupt reboots that lose in-flight file IO are rare.

We also assume that readers see files immediately after they are written, i.e. the archive filesystem is strongly globally consistent. This didn't used to be true for S3 and GCS, but now it is. Here too, it seems very hard to do anything without this assumption, without relying on some external consistency mechanism.

All machines involved have reasonably-accurate clocks, within say a minute of true time.

During a backup, Conserve first writes data blocks and then writes index hunks that reference those blocks. Index hunks may also reference blocks already in the archive, either if the file is unchanged from the previous backup, or if the file hash matches something else that was stored. (There's no guarantee that the match will be against the directly previous backup.)

This ordering ensures that if the client is interrupted, every referenced block will be stored, although it's possible that some blocks were stored that are not referenced by any index hunks.

During garbage collection (which is run as part of deletion), Conserve lists all present blocks, walks all indexes to discover all referenced blocks, and then finds all blocks that are not referenced by any index, and deletes them.

The problem is that if garbage collection races with a backup being written, it may see the new blocks as unreferenced and decide to delete them, even though they are imminently about to be referenced by new index hunks.

It seems the main thing we need is mutual exclusion between backups and garbage collection. It would be OK for any number of backups to write to the same archive simultaneously, but we should not search for unreferenced blocks at the same time that blocks and index hunks are being written.

(Or maybe there is some other solution that would let them run simultaneously?)

The current solution in 0.6.15 is that deletion refuses to start if there's an incomplete backup underway, and backups refuse to start if there's a GC_LOCK file in the archive.

This is OK but not ideal. If the gc is interrupted, which is plausible because it does a lot of work and so takes a long time, the lock can be left behind, and so the user has to decide whether to manually break it (which is against one of the goals.)

Similarly, the last backup being incomplete is a poor proxy for "is there a backup process still running." The backup might have been interrupted weeks ago. If the user wants to clean up the interrupted backup, Conserve refuses: they need to complete a new backup first.

We might think of never deleting blocks added in the most recent backup: but new index hunks can reference arbitrarily-old blocks, so this doesn't help.

Similarly, we could emphasize deleting particular backups rather than deleting unreferenced blocks, and then delete the blocks that were uniquely referenced by the to-be-deleted backup. But it still might happen that the currently-underway backup chooses to add a new reference to this apparently-obsolete block.

Earlier versions of Conserve (0.5?) avoided this problem by keeping a per-band block directory, which does make it easy to delete all the band's blocks, but at the price of a lot of duplicate block data. So that's not a very good solution.

We could also try keeping a file lock in a directory on the client machine, representing that a logical lock is held on some remote archive.

A different approach to mututal exclusion between backups and GC is to write a lease file in the archive, as say a json file LEASE in the root.

The lease file asserts that a process needs mutual exclusion and that it is still alive.

To prevent stale leases we include in the lease the time it was last refreshed.

If the lease is less than say five minutes old, it is still valid, and any contending writers must wait. (Possibly five minutes is too long and one minute would be enough.)

While the process is still working, it should periodically check and refresh the lease, well ahead of its expiration date.

If it discovers the lease was stolen, it can no longer continue and should loudly exit. (This should never normally happen, but seems conceivable if a user manually deletes the lease file, if there is a bug, etc.) The backup process could exit before writing a new index hunk; the gc process could exit before deleting any blocks.

Checking and renewal of the lease could be done from a background thread, which should mean it's always renewed promptly.

Checking and reading back the lease also protects against filesystems or transports that don't reliably detect conflicting attempts to create a single file.

A single lease per archive would block two backup processes from running simultaneously. In general they could safely co-exist. (It wouldn't be very useful to do this at the moment, but with multiple backup series sharing a blockdir it might be useful.)

At the price of adding a bit more complexity we could have a directory with multiple shared leases (for backups), and a single exclusive lease (for gc). Acquiring the exclusive lease requires checking there are no shared leases and vice versa. Stale shared leaese might accumulate and need to be removed by gc, too.

Add a custom footer

Add a custom sidebar