More efficient multiplayer map download

[domgetter]

This is a suggestion on how the map is downloaded from a headless server in multiplayer mode.

As it stands, when a player connects, all other clients are paused while the new client downloads the map. This is okay for high download speeds, consistent connections, and few players, but if any of these change, and as the game progresses, it starts to affect gameplay poorly.

This suggestion is simple, yields great benefit to multiplayer gameplay, but requires some work in the way of development.

Suggestion: When a new player connects, instead of copying a zip of the game, make a tar.gz of the current state of the game and copy that over. In the meantime, don't pause the game for other players. When the tar.gz file has been copied (let's call this base.tar.gz), pause the game for current players, make another tar.gz of the game (let's call this current.tar.gz), and make a binary patch with xdelta between base.tar.gz and current.tar.gz. The patch will be no more than a few hundred kilobytes, according to my tests. Send the patch over, have the new player apply the patch to their copy of base.tar.gz, and then sync up to the game as if they had downloaded the original zip and extracted.

Benefits:

• Current players will not have to wait around for the full duration of a download.
• A player who is momentarily disconnected will be able to reconstruct the most current version of the game by telling the server what base they have, and getting a patch instead of a full download. So this is good for inconsistent connections.
• Servers will have a greatly reduced bandwidth load for players constantly connecting and disconnecting.
• For a single player on a server, they'll never have to download the full map after the first play since the map won't change between connections.
• This doesn't have to be a required method. Both the current way of doing things, and this way can be possible with the same game. It would be up to the server to do it one way or another.

Evidence:

I have a headless server running in a CentOS VPS. I connected to my server, and my client downloaded mp-download.zip. I then copied this to a different directory and named it mp-download-orig.zip. I then played for 2 minutes until a save occurred. After that, I disconnected and reconnected to the server, which resulted in another ~8.6 MB download of mp-download.zip. I copied this mp-download.zip and renamed it mp-download-new.zip.

I then unzipped both into mp-download-orig/ and mp-download-new/ respectively. Then I ran `tar -czf download-orig.tar.gz mp-download-orig/` and `tar -czf download-new.tar.gz mp-download-new/`. Then `xdelta delta download-new.tar.gz download-orig.tar.gz download-tar-gz-diff`. After an `ls -la`, I got this:

Code: Select all

$ unzip mp-download-orig.zip -d mp-download-orig/
$ unzip mp-download-new.zip -d mp-download-new/
$ tar -czf download-orig.tar.gz mp-download-orig/
$ tar -czf download-new.tar.gz mp-download-new/
$ xdelta delta download-new.tar.gz download-orig.tar.gz download-tar-gz-diff
$ ls -la
drwxr-xr-x 4 domgetter domgetter     4096 Apr  2 16:12 .
drwxr-xr-x 7 domgetter domgetter     4096 Apr  2 15:51 ..
-rw-r--r-- 1 domgetter domgetter  8360935 Apr  2 16:05 download-new.tar.gz
-rw-r--r-- 1 domgetter domgetter  8353529 Apr  2 16:05 download-orig.tar.gz
-rw-r--r-- 1 domgetter domgetter   325893 Apr  2 16:12 download-tar-gz-diff
drwxr-xr-x 3 domgetter domgetter     4096 Apr  2 15:44 mp-download-new
-rw-r--r-- 1 domgetter domgetter  8968251 Apr  2 15:41 mp-download-new.zip
drwxr-xr-x 3 domgetter domgetter     4096 Apr  2 15:44 mp-download-orig
-rw-r--r-- 1 domgetter domgetter  8962909 Apr  2 15:33 mp-download-orig.zip

As you can see, the patch file is only ~319 kilobytes, while a full map download is ~8.6 MB. xdelta is an open source binary diff/patch creation/application tool. It automatically works with gzip, as well. It can be compiled freely into the client, which brings me to my last point:

Costs:

• Developers will have to integrate a diffing/patching tool into the server and the client, though xdelta looks most promising.
• (added in edit 1) Xdelta is GPL, which may cause issues with integrating it directly into the client. Some research will have to be done by the devs on how to use it or any other binary diffing tool.
• There is a trade-off here between bandwidth and processing. Creating the diffs and patches isn't free, although it happened in a reasonable amount of time with my tests. With xdelta, it didn't take longer than a second to make a diff between the zipped tar files.
• (added in edit 2) The diffs and patches would require the delta-making peer to hold on to the base save file until the asking peer is ready for the delta. Of course, peers by default hold on to 3 autosaves, so this probably won't be as big of an impact. But I don't know how big save files get, so this is something to consider.
• Servers may have to hold on to more savegames from the past to have more diff bases. This is probably configurable.

Final thoughts:

• Not a silver bullet: If the client and server don't share a recent base tar, then the client will have to download the whole thing anyway.
• I don't know how this idea integrates with how the game operates normally, in terms of syncing and all that jazz. It may be un-implementable for other reasons.
• This is more beneficial for people running servers, as the download speed would be greatly reduced overall, although players still benefit from not having to wait for others as long, even if it's the first time the new player connects.
• I don't know how this would work for peer-to-peer, but since a headless server is more-or-less a peer, it would seem that this solution would work for regular multiplayer games as well.
• (added in edit 1) There are other binary diffing tools to look into. I only tried this out with xdelta.

Let me know what you think!

[bobucles]

That's actually a pretty clever method. The bulk of the download doesn't interrupt gameplay, and the player only needs a final update to connect.

[Khaylain]

That seems like a really smart way to do it. I wonder if it would be useful/possible (to keep savegame ovearhead low) to have a decreasing number of savegames for comparison the longer the game has progressed.
Like having a savegame for comparison/diff every 2 minutes or so for the last 15 minutes, then every 10 minutes to the 1 hour mark, then every 30 minutes to the 3 hour mark, then every hour to 6 hours. And perhaps after six hours you'd have to download the newest created save and then wait for a diff to bring you up to speed.

Or perhaps it's not needed to have so many saves, perhaps every 5 minutes up to 30 minutes and then a player would have to download the newest created save and wait for the diff.
Does that make sense? I'm not a programmer, but it still fascinates me.

[sillyfly]

Wouldn't it make more sense to perform the diff on the raw level.dat, and then compress the delta?

I may perform some tests, but I suspect it could lead to better results.

Edit: Nevermind, apparently xdelta automatically decompresses gzip, so it was working with the raw data to begin with.

[sillyfly]

One issue - as far as I can tell, xdelta is only available under GPL, which will almost certainly not suit Factorio (would mean it has to be GPL as well).

[ske]

Some threads ago something similar was suggested and shot down because they didn't think it would work out. The problem with the other idea was that the client would be sent in-game updates while connecting to keep up to date (catch up until the current state) and the devs found that this somehow wouldn't work (I didn't really understand why not).

Your idea just modifies the download phase by splitting it into two stages. The joining phase is the same (but with less data to download then). To me it seems pretty much implementable and should result in a considerable reduction of delays in the game.

[sillyfly]

I think the issue with the previous suggestion was that the suggestion was basically sending the replay data to the connecting peer, and have them replay it at maximum speed. This means you are bound by the processing power of the joining machine, trying to simulate Factorio as fast as it can.
Simply applying a binary diff patch is possibly much easier, and a could be done faster (but of course this should be tested).

[domgetter]

One issue - as far as I can tell, xdelta is only available under GPL, which will almost certainly not suit Factorio (would mean it has to be GPL as well).

I am not a lawyer, but to my understanding, if your application only acts as an interface to a GPL work, your application doesn't need to be GPL as well. It would be different if the devs took xdelta's source code and modified it and called functions directly within it. Here, I'm only suggesting packing it up alongside and calling to it as if it had been installed separately on the user's computer. It might even be possible to simply ship the xdelta executable along with the client, but I'm not certain.

As I said, I'm not a lawyer, so I don't know for certain, so I'll put this in the list of "costs" as a consideration.

[sillyfly]

Hmm... Yes, as far as I understand it, supplying the executable separately (rather than linking against it) is possible, but could have other shortcomings (from a "you must accept the license of this third party tool when you install Factorio" clause, to the potential loss of efficiency associated with switching to an external process and back, to the technical details of having to call an external tool on different operating systems).

[ratchetfreak]

one issue with the more advanced "features" like rejoining

The peer creating the delta needs both the new version and the version the joining pear has. This means quite a bit of duplication of save data.

For a fresh join without interrupting existing players it's not a big issue, just 2 autosaves and a pause for the patch download. Then the server can throw away the first autosave

[domgetter]

This means quite a bit of duplication of save data.

This is true, and something to consider. Of course, peers by default save 3 autosaves at any given time, and deltas can be created between them easily.

I'll change the costs list to make this more clear though, thank you.

[nuhll]

Or just stream the world, like WoW. But all is better then its now.

[ssilk]

moved from implemented suggestions back to suggestions

[DarkShadow44]

FWIW, xdelta is under the Apache Public License: https://github.com/jmacd/xdelta

I tested four saves I consider big:

• big: Just an empty widely explored world
• reactor: A massive nuclear reactor setup, otherwise empty world
• vanilla: My save that started as vanilla, biggest one I have so far
• se: Space exploration save from me, lots of explored planets

How tests were done:

• Save files with fast/max compression, for comparison (factorio extra settings, autosaves compression level)
• Save files as uncompressed (same setting)
• Let Factorio run on high speed for 10 in game minutes (36000 ticks)
• Save uncompressed again
• Diff the saves with different tools

Diff creation is timed using the "time" command (real time).
All elements are "Size in MB @ time taken to diff".

hdiffz from https://github.com/sisong/HDiffPatch, has a permissible license and it says it can be multithreaded. Didn't get that to work, but if it works it seems very promising.
hdiffz is uncompressed (while xdelta is compressed) so I compressed it afterwards with "zstd -3", just lightly to not affect time too much.

Code: Select all

                        se               vanilla           reactor           big
0) raw                  686.3            153.1             182.1             217.7
1) Factorio fast        290.5             63.8              61.8             101.2
2) Factorio max         266.7             56.6              56.4              92.0
Diffs
3) xdelta               15.4 @ 11.0s     11.0 @ 2.4s       46.3 @ 15.4s      1.0 @ 1.5s
4) hdiffz                5.6 @ 22.3s      8.7 @ 7.4s       45.3 @ 14.2s      0.7 @ 2.7s

As you see the difference is miniscule compared to the original save. So, assuming the client has a recent copy the sever still has, we can save over 95% of bandwith!
It depends on why the file is big though, it seems to work well with surface data (mostly static) but entity data changes too often to be deduplicated usefully.

TL;DR: This seems perfect for multiplayer, and I'd love to have that in game. The improvements are just too good to pass up. Especially when download speed is limited.