The Ultimate Diff-off: Butler vs. casync vs. desync

What’s better than a relaxing day after finishing your exams?

SPREADSHEETS.

For context, this all began about two months ago when I was informed by a colleague at TF2c that they were looking into a system called desync for versioning as opposed to Butler which was (spoilers, still is) the incumbent versioning protocol/program.

This seemed like an eerie repeat of last year when TVN was binned in favour of Butler, OFToast II died and Adastral was born, but feelings aren’t cold hard data unfortunately. Time for some data crunching.

desync’s claim to fame was that it’s used by Valve for steam deck updates, and since the SteamPipe algorithm remains locked within Bellevue, this seemed promising. desync is also an improved version of casync, so I decided to test that too.

desync/casync work (put simply) in a fundamentally different way to how we implemented Butler. They both operate by splitting a file, or a directory tree tar’d up, into many chunks which are stored in a chunk store. This is where deduplication can occur. An index file referencing what chunks needed from the store is the end result. How they differ from each other is:

1. some very clever jiggery-pokery I don’t fully understand on behalf of desync
2. desync also has some neat S3 support for pulling chunks over the network
3. (most importantly) casync supports using a local folder as a “seed”, i.e a source of chunks that it’ll pull from instead of from the presumably remote store. desync doesn’t support this, instead maintaining a local chunk cache. Worse for storage space, but better for perf.

One other thing to point out is that they don’t support fully in-place upgrades, compared to butler (which operates purely in place).

We also need to consider how these are stored on the server for a given release:

• Butler: A patch needs to be generated for every version before it. This means that the amount of patches needed increases every update which gets a bit ..heavy on server storage. You also need to store a .zip archive of each version for verification but we won’t get into that now.

• casync/desync: A new version is chunked and added to the chunk store, and an index file generated. That’s it.

Now the testing! I decided on testing 3 different patch sizes, with the data set being Open Fortress initially, and testing locally initially.

• Large: an upgrade from revision 5 to revision 19. Butler patch size: 1.1GB

• Medium: an upgrade from revision 13 to revision 19. Butler patch size: 376MB

• Small: an upgrade from revision 18 to revision 19. Butler patch size: 32MB

The issue with testing is that these three systems are quite different, and as such metrics such as patch size were… unhelpful. We’d measure this when we try these over a network. The two main factors were patch generation time and patch application time - We want to be able to get updates processed ASAP and our no.1 priority is getting updates applied quick.

For these, I did the following for butler (straightforward):

Generation:

time butler diff [test ver] [v19] foo.patch

Applying:

time butler apply foo.patch [test ver]

I did the following for casync (which is a bit contrived to test properly - for generation, the store is initialised with the test version, then 19 added, for application it uses the old version as a seed.)

Generation:

casync make --store=[store] [test ver].caidx [test ver]
time casync make --store=[store] 19.caidx [v19]

Applying:

time casync extract --store=[store] --seed=[test ver] 19.caidx foo/

Finally for desync (which is the most contrived to test since you need to prep the local cache with the previous version on top of casync):

Generation:

desync tar -i -s [store] [test ver].caidx [test ver]
time desync tar -i -s [store] 19.caidx [v19]

Apply:

casync untar -i -s [store] -c [cache] [test ver].caidx foo/
time casync untar -i -s [store] -c [cache] 19.caidx bar/

Anyways, here are the results (Do take these results with caution - These tests aren’t exactly rigourous):

(apply)	butler	casync	desync
small	1.7s	56s	11s
medium	11s	1m3s	16s
large	26s	1m10s	25s

(gen)	butler	casync	desync
small	57s	26s	30s
medium	7m51s	26s	27s
large	8m35s	33s	22s

We can draw the following conclusions from this:

• Butler is the fastest at applying in general, especially with smaller patches.
• Butler is also significantly the slowest at patch generation, 22s for desync vs 8 minutes for butler is steep.
• desync is objectively better than its predecessor, casync in these tests.
• Butler is the best for the client, and the worst for the server (with the storage requirements and the patch gen time).

Overall, desync is looking like a reasonable compromise. Decent on both the client (if you ignore the sizeable local cache) and server!

Let’s now check network performance. This is the time to download and apply the patch by the client.

casync and desync both do their own network I/O so we don’t need to worry about this - but I’m using the stack we currently use on Beans for butler patch downloading - aria2c. This provides substantially better speeds.

One can argue that this is possibly unfair, however the results show that even if I used a more standard downloading solution (i.e one butler provides, or just curl) then I don’t think it’d have made much of a difference.

(dl+apply)	butler	casync	desync
small	10s	2m0s	30s
medium	33s	31m17s	5m38s
large	38s	N/A	N/A

…Ouch. I’ve investigated this, and I can’t seem to figure out why casync/desync take so long when pulling from a remote.

It’s important to note that it seems that casync/desync are better for backups as opposed to updating a folder like butler does. A pretty anti-climatic result, but the conclusion is that the status quo wins (for now)!

However, there’s more to do. We can optimise butler’s patching - we’ll be taking a look at this in part 2 - and I can guarantee you it’s more interesting than this.

Untill then, have a good day.

-intcoms/kmt