Friday Facts #136 - Map Transfers

[sabriath]

To bNarFProfCrazy, I'm not going to argue with you about map mechanics, I was stating on what CAN be done and how to do it, not some fanciful thing from a point of ignorance.

This would be true if they used TCP, but they only use UDP, so they don't have those ACK messages.

I stated TCP, I never brought up UDP because I was straight-forward telling the factorio team to stop using UDP because TCP automatically comes with ACK messaging. Along with the fact that it has OOB ability, you get 2-in-1 servicing. UDP is meant for games that constantly send movement updates along with position (like first person shooters), the players do not have to worry about losing packets because the next packet will still have a position marker (this is why laggy players jitter, along with out-of-order and bad programmers). Factorio doesn't really need to worry about that with map dynamics...and that's what I've been trying to explain.

However your idea with the sending only the changes is worth being discussed.

If the chunk idea never happens, the very least that could happen is simply have the server have an open appended file that saves the changes of the current map...and when the file becomes X in size, a backup is saved for the entire map and a new append file is created. A packet can be sent to all clients letting them know at what incremental sync game tick the backup was generated for, and the client can also do a backup and start their own appended change file. When logging in, the client can simply say what the last game tick sync it remembers, and if the server can go back that far, it can generate a change log from the appendings (otherwise send it the new map entirely).

Use a standardized and real-world-proven protocol and be done.

First of all, standard "libraries" have built-in junk. They need to in order to service as many general uses of their work as possible, but not all of it gets used in every game. There is no need for HTTP requestor pings in a game that doesn't show webpages, for example.

And it's not like you'll get something like this out of "standardized" crap (and don't say you've seen it, because this is my personal protocol):

https://dl.dropboxusercontent.com/u/246 ... s/rudp.png

Instead you can send the sequence number of the highest received packet from each peer

Not necessary in TCP, and if you need it in UDP, you're probably doing something wrong.

[ratchetfreak]

-snip-

I wasn't talking about doing that in TCP. I was talking about UDP where you need to know if a packet gets dropped. But not all packets need resending depending on what gets sent over the wire.

[ikiris]

-snip-

I wasn't talking about doing that in TCP. I was talking about UDP where you need to know if a packet gets dropped. But not all packets need resending depending on what gets sent over the wire.

If you're using UDP and care if packets get dropped, something is fundamentally broken, and it isn't the protocol.

[Ojelle]

@Devs

How much do you learn from these replies here ? And how much do they influence decisions? I think they have more influence then I think.

And gl with the self coded thingy you have there!

[zp_wingman]

To all the people suggesting using a well known library:
I think you overlook one important requirement of Factorio networking (at least ingame, but doing the transfer using a different setup introduces its own problems, some of which were shown in the FFF):
Factorio networking needs to be as realtime as it can be.

Thats why most multiplayer games roll their own implementation, building directly atop UDP. This enables them to implement everything they need and leave out everything they don't. Every library or intermediate protocol will be detrimental to this point, and nearly always bring too much stuff you just don't need for your usecase.
See "Gaffer on Games: TCP vs UDP" for points why TCP is not really suited to game development, and most other libraries not specially designed for realtime state synchronization will have some kind of drawbacks, especially when implementing an all-hosts-are-equal system like Factorio deploys it.

Even protocols designed specifically for games have to make too many assumptions on priorities to be really useful:
Take the Steamworks networking API for example [and I trust Valve to have put some thought into it - note that this is neither Steam Matchmaking nor Source Engine networking, but an API provided by steam]:
IIRC (it's been a while) it abstracts networking away as far as you only having to decide if the data should be retransmitted on loss or not, and if it is a broadcast to your current game or if it should be a unicast message to a specific recipient. While this should allow for some good black-box optimizations, most games I know that use it are known to have problems with their networking (prominent example Magicka - they even advertise a better netcode for the sequel, where they don't use the steam networking functionality any more)

Regarding uPNP: While a nice concept in theory, most implementations are so bad I still disable it on most consumer grade hardware, since it is generally too trusting regarding unknown senders to control a firewall protecting the private network from the internet. Also there are other people behind NATs without uPNP with no way of changing that - I know of some cable providers putting their customers behind carrier grade NATs so they don't need as many public IPv4 adresses - and uPNP does not work. Or on cellular networks. Or, or, or...
Also, uPNP forwards typically open up the port to everyone on the internet, while hole punching restricts the access to the specific people I'm playing with - so I actually prefer hole-punching to uPNP, working just fine most of the time without any configuration.

While IPv6 solves the NAT problem, you'd still need to open up the connection in the network firewall in most home setups - using either hole-punching or uPNP. Also there are still too many people without a true IPv6 connection, and asking them to set up tunneling is one of the faster ways to get people to just not play the game, since it is too much of a hassle.

[Kalissar]

This kind of post is why I read the FFF every week. It gives a really nice insight of what's going on in the code. That's very nice
Thank you very much.

[ratchetfreak]

-snip-

I wasn't talking about doing that in TCP. I was talking about UDP where you need to know if a packet gets dropped. But not all packets need resending depending on what gets sent over the wire.

If you're using UDP and care if packets get dropped, something is fundamentally broken, and it isn't the protocol.

If you are using UDP and don't care about dropped packets then your application is fundamentally broken.

[Mythoss]

Trying to play with my friend is really painful. He gets like 30 kbs when downloading from me (I have amazing Internet so it's on his end). Sometimes it takes 15 to 30 minutes for him to download the map each time. If I have him run speed test he gets about 1 mbps (he's on microwave internet). So we know it's something related to the game.

[sabriath]

-snip-

I wasn't talking about doing that in TCP. I was talking about UDP where you need to know if a packet gets dropped. But not all packets need resending depending on what gets sent over the wire.

If you're using UDP and care if packets get dropped, something is fundamentally broken, and it isn't the protocol.

If you are using UDP and don't care about dropped packets then your application is fundamentally broken.

1. I WAS talking about TCP....not only that, I was explaining that it should NEVER be UDP.....this is the problem that you're not understanding.
2. The ONLY time you use UDP is when you DON'T CARE about dropped packets....that's the point of the protocol.

Not only that....but it has a limitation of 576 bytes on the mtu in some areas, so a single transmit is strangled. I am pretty sure that I have more knowledge about networking and protocols than every person on these forums combined....so if I tell you something about TCP and UDP, you might want to take some notes. I hate being brash about it, but I'm not going to sit here and watch a troll-battle ensue over something so simple.

3. What reason would you not care about dropped packets? I answered this before, but to make this easier, I'll re-explain it.....player movement or visual appeal (such as a player reloading his weapon). When a player updates, a small packet of about 12 bytes is sent over UDP...2 bytes each of X, Y, DX, DY and a 4 byte game tick sync. If the packet is lost, it doesn't matter because the player will just send another packet in the next update. The client can simply deduce (by spline averaging and frame rate amping) the position the player is and will be over time based on the game tick......lost packets are averaged out.

Sending a map...which is a REQUIRED piece of data....is not for UDP. TCP is perfectly able to handle any of these types of transfers without having to waste CPU cycles inside the game, handling protocol specific algorithms....let the OS handle that, that's what it's for.

Hopefully this will be the end of the argument. If you and/or the programmers of this game still do not see it that way, that's fine....you can still catch fish with chocolate cake, even if you're doing it wrong.

[DaveMcW]

Hey Mr. Knowledge About Networking,

Here are some links that were already posted in this thread, and you probably knew everything in them anyway. But it might be interesting to re-read them.

https://en.wikipedia.org/wiki/UDP_hole_punching
http://gafferongames.com/networking-for ... dp-vs-tcp/

Summary

1. UDP is required for some routers to match-make correctly.
2. UDP can resend dropped packets faster than TCP.

[dee-]

Hey Mr. Knowledge About Networking,

Here are some links that were already posted in this thread, and you probably knew everything in them anyway. But it might be interesting to re-read them.

https://en.wikipedia.org/wiki/UDP_hole_punching
http://gafferongames.com/networking-for ... dp-vs-tcp/

Summary

1. UDP is required for some routers to match-make correctly.
2. UDP can resend dropped packets faster than TCP.

sabriath already gave an example when to use UDP:
when data packets are stateless
- missing or duplicated packets can be ignored as soon as a newer packet comes in, as the old packets have at that moment all gone stale
- the order of incoming packets is not important as they carry a timestamp and the most recent can always be determined


TCP downsides as from one of the above sources:

So in our simple multiplayer game, whenever a packet is lost, everything has to stop and wait for that packet to be resent. On the client game objects stop receiving updates so they appear to be standing still, and on the server input stops getting through from the client, so the players cannot move or shoot.

But that's exactly the usecase for Factorio.
The data is inherently stateful, as only deltas are sent over the wire.
To maintain determinism, the simulation HAS TO stop until all previous packets have come in, no packet may be skipped at all.
The game has the necessarity to pause the simulation on delayed packets, regardless of using UDP or TCP to move packets.

You can try to cover this up by allowing user interactions on "old data" and then catch up the map when updates come in and try to apply the user-actions on the fresh map, then send your deltas again to the peers.
But it's a kind of guessing game as you assume the map-piece you interact with will be still in the state it was when the packets paused as it will be when the map is again fully updated. Thus actions the player performed on old data have to be un-doed when they manifest as being illegal (e.g. picking up items to the inventory that actually have been removed in the meantime, etc.)

The less interference is expected (e.g. two players in very different places at the map), the easier it is to allow different "time speeds" and asynchronous simulations. But as soon as the "two realities" come closer and begin to influence each other, the event timelines have to be meshed and reassembled correctly and in a consistent linear way to maintain simulation determinism for both sides.

At least that's what I think Factorio does

[landwaster]

Solution:
1. Set up a map webserver at your company. This server does not run the main website or reside on the same machine.
2. Individual player run servers contact this webserver by visiting a status page to verify it is up.
2a. If it is not available, the mechanism falls back on the old slow unrealiable transfer code for now. This old fallback mechanism should be replaced with a reliable UDP implementation at some point, look up "realiable udp." For now, don't worry about it and focus on perfecting the rest of my solution.
3. The player run game servers, seeing that the webserver is available, perform an upload. Their map data is stored on the webserver. If it is the first time the map is begin transmitting for this map session, the whole map is transmitted. If it is merely an update of an existing game session then only the changes are sent.
4. Delta compression can be used to transmit only parts of the map that have actually changed. Zero coding can encode away repeating zeroes. Additional deflate compression on the resulting data can be used to get the data even tighter.
5. The webserver keeps the original map and all the deltas. It associates these with an identifier of that game server, unique identifier and version of the map of that game session. You can use UUID for these identifiers. These are all stored in an sql database.
6. When a player connects to the game server, the game server provides the game server uuid, session uuid.
7. The client contacts the webserver where maps are stored and provides these identifiers. It also provides the map version it currently has. If the version matches the existing version stored on the webserver, it receives a reply that no further action is needed and the client completes connecting to the server.
8. If the client's map version does not match, the webserver delivers each of the delta patches that are missing. The client then applies each patch sequentially to their current map data. Make sure to back up their original map data in case this patching fails, so it can be tried again.
9. The client then verifies the hash, something like SHA512, of the final combined map against the one provided by the webserver. If it matches, the client can connect and begin playing. If it does not, attempts to patch again are conducted. To speed this process, a hash can be matched after each applied patch so the entire patching process does not have to be repeated, only the patches that failed. This means the webserver keeps a table in the sql server (resides on a separate machine) of the original map + its hash, each patch and its hash, and each map patch combined + its hash. At any point the client can verify these hashes to confirm the patching process is proceeding smoothly.
10. No incoming ports need to be opened by any of the player clients or player run game servers during this procedure, because all connections are made outgoing via REST web services to your master map webserver bypassing the need for players to configure their firewall.

Note: bsdiff could be used for handling the binary deltas to perform the patching. The code is available under the original bsd license so you only have to mention his copyright notice in your documentation.

Hope this idea helps.

-landwaster

EDIT: The procedure above is only for the initial connection. During realtime gameplay, the state changes can be negotiated with the game server and its clients for optimal performance.

[zp_wingman]

But that's exactly the usecase for Factorio.

Is it? TCP includes much more than just resending packets, some of which can be disabled (e.g. Nagle), but some not. How does Factorio profit from the in order delivery?
I don't know what exactly Factorio transmits, but let's assume a Client needs to inform a client about 2 distinct things in the same simulation step.
If it sends them via TCP and a packet of the first info is lost, TCP will hold back the second information, even though it was already received. In an UDP usecase, the second information could already be parsed and made ready to be fed into the simulation. Depending on how much work you have to do with incoming information before it needs to be sychronized with the complete world state, this may free some valueable time.

And even if the inherent properties of TCP would be useful, things like hole-punching might still make UDP be the better choice for the P2P architecture Factorio uses.

I don't really understand the solution with the webservers. Wube should host the maps? permanently(so the host only uploads deltas)? where, why? and suggesting filediffs on binary data? And then you suggest as a fallback to implement reliable UDP, but that is already what they are doing...?

But in the end, as long as it works I don't really care

[Zeblote]

let's assume a Client needs to inform a client about 2 distinct things in the same simulation step.

They'd be processed in the same order on all clients to preserve determinism

[zp_wingman]

They'd be processed in the same order on all clients to preserve determinism

And there is no work that needs to be done between receiving bytes and applying them to the world state? I think of sanity checks, filling structs / queues, handing data to the lua engine - thats what I meant with before it needs to actually be in sync. Also there are things not effecting the GameState, like comparing the current state hashes to ensure they are still in sync.

Just curios: how is the order of actions within a simulation step determined between the clients? Is it actually a requirement to be exactly the same?

[kovarex]

Just curios: how is the order of actions within a simulation step determined between the clients? Is it actually a requirement to be exactly the same?

Yes, it is required to be the same. The order is well defined, first you apply actions of player 1, then player 2 .. etc. To make it possible, you always need actions from all player to make the step.

[ikiris]

Trying to play with my friend is really painful. He gets like 30 kbs when downloading from me (I have amazing Internet so it's on his end). Sometimes it takes 15 to 30 minutes for him to download the map each time. If I have him run speed test he gets about 1 mbps (he's on microwave internet). So we know it's something related to the game.

Actually this explains it. The ISP isn't qos shaping a subrate link properly somewhere in the path, so they've got a lot of overflow drops. Either that or their network is massively oversubscribed, but I expect it's the former.

[LumoNeon]

So, the network talk is good.

Thoughts on save/transfer.

Would implementing a transfer method similar to Redis make since?

So in Redis - redis <dot> io , when a replica requests to join, the Donor node will create a RDB file, this is a dump of the data-set as it is currently, not how it got to that state. So this in essence is the save file. Redis then un-pauses and starts transferring this file, and any further operations are stored, in memory, though an on-disk file similar to the AOF, Append Only File should be fine, and it's any operations that happen after that RDB file was created, for the new slave node, so in Factorio this should be the data that's already flying over the wire, and is in the case of Redis if there are other slaves.

Now that the map has been transferred the client is then caught up by transmitting the AOF data to the client. At this point the client is caught up and joins without any further interruption.

If the network is exceptionally slow, then either the client will not be able to keep up to date during standard game play and should be dropped, or you could attempt to process the AOF and compress it, by reading back through it and finding things that can be removed, or pause, save again, bindiff, then transfer the bdiff and hope the AOF is smaller as the binary diff would hopefully transfer faster.

While none of this addresses the network code, it could make player joining a less painful experience for players that are in-game already.

Redis is Three Clause BSD licensed, though the idea of state transfers with such a method is far from unique to Redis and has been used in a number of other databases throughout history, and I can say replicating MySQL and PostgreSQL this ends up implemented somewhere in there. MySQL Galera also takes such an approach and manages it with rsync, or other pluggable methods. So I doubt there is anything encumbered on such a method.

Cheers,

[Zeblote]

Now that the map has been transferred the client is then caught up by transmitting the AOF data to the client. At this point the client is caught up and joins without any further interruption.

What if you have a huge map and the client can't process it faster than the server, never catching up?

[LumoNeon]

Now that the map has been transferred the client is then caught up by transmitting the AOF data to the client. At this point the client is caught up and joins without any further interruption.

What if you have a huge map and the client can't process it faster than the server, never catching up?

Keep reading, I addressed that.