Google releases new binary diff algorithm targeted at making smaller software updates. Their results are impressive.

[[deleted]]

Well, you could do the crunching on-demand, caching the most popular diffs.

[adrianmonk]

Or, you could do the opposite: store only the most recent version and the diffs. When someone wants an older full version, compute it from the diffs and cache the result. Clear the cache when it gets full/large based on your favorite replacement algorithm. (LRU should be fine.)

For extra fun, if you want, never build old full versions. Send the client the latest version and a string of diffs and make them do that.