Use delta-compression to speed up joining a multiplayer game

[mrudat]

TL;DR

Create and send deltas (delta compression) to update a multiplayer save to the latest version to reduce the bandwidth and time required to join a server.

What ?

Every time a new multiplayer save is created, create a delta file between the latest save and the previous save, for example, using librsync/xdelta/etc. on the uncompressed data.

The delta file should only contain the data that has changed since the last save and should be tiny compared to the save as a whole.

The delta file name should include the tick from the old save file. This allows the client to request all deltas since the tick in the save it has, and the server to efficiently supply the required files or report that it no longer has the required deltas and the client needs to fetch a fresh save.

When a client connects, if it does not have an existing save or the save it has is too old, it will download the latest full save.

If the client (now) has a recent save, it will download and apply any deltas before loading the save and catching up as usual.

This should improve the experience for both returning and new players.


Old deltas can be removed when the total size of the delta files exceeds the size of the latest save, as it no longer saves bandwidth to download the deltas.

As

, using delta files allows for the possibility of requesting delta files in a torrent-like manner (in terms of impact on server bandwidth) from other clients, as unlike saves, delta files are static and long-lived.

It is also possible that, depending on bandwidth constraints, downloading more data in the form of deltas from multiple clients may be faster than downloading the latest save from the server.

To optimise save files for delta-compression,

It could also help to serialise by how recently an entity was last changed, as that would mean cold data could be efficiently skipped and hot data transferred in full.

Perhaps associate each entity with the last save it was changed in (which would be serialised in the save), and remove the association when it gets changed so you maintain the most recently updated order.

It might also benefit from loading 'hot' entities nearby in RAM.

Why ?

Using delta compression to transfer multiplayer saves should result in a significant reduction in bandwidth required and, thus, the time needed to join a server.

---

Copied from

Edit: many many edits.

[Illiander42]

Prove the save files are exactly the same for returning players.

[mrudat]

Prove the save files are the same for returning players.

That's pretty easily done; rsync and xdelta are both byte-accurate, and the save itself has a checksum, which I believe is sent to the server to verify that the save you just loaded matches a previous state on the server.

Or do you mean prove that the local save matches the old save that the delta is based on? I believe both rsync and xdelta confirm the original file + delta have correctly recreated the target file, but you could store the n-1 and n save's checksums to double-check that nothing got missed.

[Illiander42]

Prove the save files are the same for returning players.

Or do you mean prove that the local save matches the old save that the delta is based on?

This, obviously. And now do it without needing to sent nearly as much data as just sending the whole file.

[mrudat]

Or do you mean prove that the local save matches the old save that the delta is based on?

This, obviously. And now do it without needing to send nearly as much data as just sending the whole file.

Rsync can do it for a fraction of the file size, but it requires a checksum file of that old save or a copy of the old save.

If you use rsync directly, it's possibly more efficient to compute an on-the-fly delta from the save you think is right and the current save; the worst-case scenario is a fraction larger than a straight download (transmitting checksums in addition to the save).

That said, it should be sufficient to send the save's checksum and tick, grab the delta file for that tick (if it still exists), and check if the checksum (that we would need to store in the delta earlier) matches the expected value. If not, it's not a valid save.

You can download the delta, and as part of attempting to apply the delta, it verifies that the final file is correct (which verifies the original file was correct). I believe you could stream the delta file and abort on checksum failure, which would be slightly more expensive in terms of bandwidth than a rsync checksum verify, but not by much.

That said, that could only happen if the correct save and the local (modified) save had a checksum collision, which seems sufficiently unlikely to happen often, but a process to abort applying an invalid delta during download/apply would still be necessary.


Hmm. It could be more straightforward to use librsync to update the local save to the latest version instead of keeping deltas; if the hot parts of the save are constantly changing, applying a chain of deltas doesn't buy you much, as you keep downloading the changed state of the hot objects, only to overwrite them in the next delta. The stored deltas would be nearly identical to the data sent by librsync (the changes to the hot objects), no matter how old the original save was.


For significantly more work than just feeding the save to librsync, you could create a custom delta algorithm that creates a 'hot' delta that includes the parts that change every save and a 'cold' delta for the parts that were only changed in this delta; effectively doing a second level of delta compression.

You'd apply all the 'cold' deltas (new chunks, static entities like power poles or walls) and the last 'hot' delta to come up to date.


Hmm, thinking about delta algorithms, I suspect that git might do the right sort of delta compression if you were to commit a series of uncompressed saves to a git repository and explicitly request only the data to checkout the current commit.

[Illiander42]

You're basically saying we should force replay for multiplayer games, and send the replay instead of the save file.

Go turn on replay for a megabase game, and compare the file size to a non-replay game of similar size.