File synchronization algorithms, part 2 of elephant
Don’t think about elephants.
The next refinement is to store history data when you look at the file trees. Every time you perform a synchronization you record some metadata for each file. You want to store the filename and the modification time. That way, when you do the next synchronization, you look at what changed between time X and time Y and apply those changes to the remote file tree, somewhat like generating a diff and then patching a tree. You do this twice - once for each direction (A to B and B to A). You can get conflicts, of course.
Conceptually, this looks like:
Compare this with the algorithm from part 1, which looks like this:
Note that if you have no history data, Algorithm 2 works exactly like Algorithm 1. Badly.
This all operates much like a version control system and has similar problems and implications. A VCS usually can’t detect renames of files or directories - you have to explicitly tell the VCS what you’ve done. When you want to perform a synchronization you have to traverse the entire directory tree to find out what’s changed - and this can be very time-consuming. The metadata has to be stored somewhere. Merges almost always require manual intervention and will often be unresolvable (either the user won’t know what to do and will just overwrite one side, or the file format won’t support lines-of-text style merging).
Also note the similar distinction between traditional client-server VCS (e.g. CVS, Perforce) and modern distributed VCS (Mercurial, git). Client-server VCS and propagates the nodes (or the actual files being worked on). Distributed VCS propagates the edges (or diffs). Algorithm 1 is looking purely at the file data and attempting to match it on both sides; algorithm 2 is looking at the changes between the ’sync points’ (or nodes) and propagating the changes.
The actions table for each file looks something like:
| File A change | File B change | Action |
|---|---|---|
| Created (checksum P) | Created (checksum P) | Nothing |
| Created (checksum P) | Created (checksum Q) | Merge |
| Deleted | No change | Delete |
| Deleted | Deleted | Nothing |
| No change | No change | Nothing |
| Modified | No change | Use file A |
| Modified | Modified | Merge |
(The actions for File A and File B can be interchanged - I didn’t feel like writing out those cases twice.)
If you include the possibility of renames (and horror of horrors, renames with modifies) then you can get a whole lot more combinations and it gets really nasty. I must give kudos to SourceGear for Vault for this: it does handle all of those nasty cases, a headache which I can do without.
Detecting what’s happened between time X and time Y is similarly mechanical. For a given file:
| Time X | Time Y | Change |
|---|---|---|
| Does not exist | Exists | Created |
| Exists | Does not exist | Deleted |
| Checksum P | Checksum P | Nothing |
| Checksum P | Checksum Q | Modified |
Without having looked at the source code, I’d say this is the algorithm that Unison uses. I’d also guess that most ‘proper’ synchronization programs use this. It’s the simplest thing that works in most cases.
Note that you also need to be able to reliably detect a change in a file. The (almost) infallible way to do this is to hash the file. I say almost because hash collisions do happen - they’re just extremely rare. ‘Extremely rare’ becomes a lot more common when you’re talking about a million files (32 bits of hash is not enough).
The other option is to look at the modification time of the file. Software can and does manipulate the modtime, however, and you might miss changes. Users might change the system time and confuse your sync program (if a change was made a long time ago). You might not be syncing to a device that has a real-time clock (some mobile phones, notably). You also have to sync the times between the two systems, but that’s not too hard.
Aaaanyway, the gist of it is:
- Checksums: reliable, slow (you have to read the entire contents of every file)
- Modification time: less reliable, much faster
Some filesystems such as JFFS2 keep a revision number on each block (roughly). If the revision number goes up, you can be assured that a write has happened regardless of what the modification time says. This is not a common feature, however, and probably not accessible to userspace programs anyway. There’s no easy solution here.
Next up: It still sucks. How to make it usable.