6 ms·

> “Distributed state is so fundamentally complex that I think we actually need CRDTs (or something like them) to reason about it effectively.” Gamedevs working

> “Distributed state is so fundamentally complex that I think we actually need CRDTs (or something like them) to reason about it effectively.” Gamedevs working on multiplayer FPSs and MMOs (which requires resolving incredibly complex state synchronizations at millisecond-scales) have done this for decades, and they haven’t been using any fancy CRDTs. Maybe they might have some ideas on how to achieve fast document synchronization as well? If you forget about P2P and only think about server/client type connections (since P2P doesn’t give you that much advantages in a Google-Docs type service), I think there’s a lot of overlap between multiplayer games and collaborative document editing, and maybe some cross-domain pollination might be needed to solve this problem.

nivenkos 5y ago
If you drop the P2P requirement, you can use Operational Transformations - https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation
dboreham 5y ago
> they haven’t been using any fancy CRDTs CRDT is actually "the tricks we have always used + math to prove whether they work or not". Read the papers. You'll find old school stuff like Lamport Clocks.
sunny--tech 5y ago
This is only tangentially related to your point, but Riot uses CRDTs for their chat system. https://technology.riotgames.com/news/chat-service-architecture-persistence https://technology.riotgames.com/news/chat-service-architect...
- cyber_kinetist 5y ago
  Maybe CRDTs are useful for implementing chat systems since the operational semantics for it are simple enough to make a CRDT system for it? The blog post I've read in the first link seems to say that CRDTs gets very complex when applying it to a domain where there are all kinds of different rich operations. I guess CRDTs aren't fundamentally the right solution for the collaborative document editing problem then?
User23 5y ago
> Gamedevs working on multiplayer FPSs and MMOs (which requires resolving incredibly complex state synchronizations at millisecond-scales) have done this for decades No they haven't. Servers crash and players drop all the time, and many things otherwise don't always act as intended. But practically it doesn't matter because nobody, not the developers and not the players, cares about whether or not their FPS is byzantine fault tolerant.
- cyber_kinetist 5y ago
  I mean, they aren't perfect, but you've got to admit they were solving a hard problem with immense technical constraints. And they certainly care about robust synchronization, since subpar netcode can absolutely determine the success or failure of certain types of games (shooters, fighting games). Players always whine about netcode all the time, although 100% byzantine fault tolerance is not the goal. Speaking of which, do you really need byzantine fault tolerance in a document editor? I mean, it would be really great if it were possible, but given the vast number of different operations you can perform in a document it seems like a really daunting task to do so both formally and practically. And Google Docs isn't really comparable to Bitcoin or airplane control systems anyway. Perhaps temporary periodic backups (like saving diffs to documents in 5-second intervals for a recent period window, so you can rollback if things seriously fuck up) as an escape hatch would be good enough?
hesdeadjim 5y ago
Realtime multiplay state sync isn't remotely like CRDT, it's an endless series of hacks where you attempt to send as little data as possible to have the best player experience as possible. Total smoke and mirrors. It's fantasy to assume a client has any real "truth" about the world over the span of milliseconds, and in practice you want the client to be as ignorant as possible because cheat programs will let people see through walls, see across the map, etc. You compensate through speculative prediction to try and make things like movement or gunshots feel lag-free, but again it's smoke and mirrors and a hundred things can cause that to go wrong. How do we resolve mis-predictions to the player? Hide it as best as possible through VFX is a great technique, or hope the users don't notice that a couple of their bullets had exactly zero effect because the server decided you shot outside the rollback buffer and didn't actually hit that other player. It's very game-dependent too. Valorant hits a 120hz tick rate through insane optimization, and if you have a low-latency connection your view of the world will be much, much more in sync with truth compared to a game like PubG that early on had a tick rate around 15hz (oof). It's always been a bucket list gamedev goal of mine to work on realtime multiplayer, but after a couple years of doing it I find myself fantasizing of a world where everyone is playing on a computer that isn't a potato with a connection that isn't jittery.
dnautics 5y ago
Not really a CRDT UseCase. Gamedev needs A<=>S and B<=>S, where S is a central server. CRDT is: A<=>B A<=>C B<=>C A<=>D ...
- cyber_kinetist 5y ago
  First of all, why do you need serverless P2P on a collaborative document editor? I can't really think of any substantial benefits of doing so. And If you're actually worrying about centralization, then why can't one user run the server as well as the client (which, reading some posts about CRDT performance, should be faster than the overhead of maintaining CRDTs anyway?)
  - dnautics 5y ago
    Latency.
    - cyber_kinetist 5y ago
      Isn't the latency about the same as P2P if a single user is hosting both the server and the client?
remram 5y ago
Those games have an authoritative central server, so using OT or something akin to OT is trivial. Even in P2P games or games with a weaker server, a given entity is owned by a single machine. This is a much simpler setup.
jitl 5y ago
The major difference in constraint is how much user intention/data it's acceptable to discard, especially when a user message arrives later than expected. In a multiplayer game, it's fine to discard all user intention that arrives a few minutes "late" - gameplay has moved on, and the client should discard local state and just use the server state. But this is totally unacceptable for a text editing application. CRDTs or Operational Transforms are strategies that allow accepting user edits and preserving their intention even if the user is days or weeks behind or diverged from the server state. I'm not aware of a real-time multiplayer game that allows such high latency for user input. I like this talk on Overwatch's data model (entity-component-system model) https://www.gdcvault.com/play/1024001/-Overwatch-Gameplay-Architecture-and https://www.gdcvault.com/play/1024001/-Overwatch-Gameplay-Ar... - the discussion of netcode starts at timestamp 22:30
- cyber_kinetist 5y ago
  So the primary reason of CRDTs is to enable offline editing? The issue is, I don't think CRDTs will help with offline editing either. If the user edits are days / weeks behind and the documents have severely diverged, then merging two documents becomes less of a theoretical logic problem and more of a pragmatic domain-specific problem that might even require the input of the user (like a merge-tool). CRDTs will ensure that the output is deterministic and correct, but it will not guarantee how "natural" or "reasonable" the output will look, and I think you would have to eventually use a bunch of clever heuristics or even provide a mergetool for the user to cleanly resolve differences.
  - jitl 5y ago
    > offline editing I guess, offline is relative? Most games I play consider >300ms ping to be offline, but I should be able to edit a document with >300ms ping. That said, a lot of CRDT research is focused on totally local, peer to peer editing. > it will not guarantee how "natural" or "reasonable" the output will look I don’t think your assumptions are correct. CRDT algorithms designed for text structures like those used by Automerge (RGA) or Y.js (YATA) do a good job preserving user intent even for concurrent edits to a text. Users won’t end up with the letters in a sentence interleaved, and it’s actually pretty rare in to encounter concurrent insertions at the same position - those are the most troublesome for both time complexity and intention preservation. Most other kinds of document edits - like edits on a order of paragraph items - are much easier.
phailhaus 5y ago
> Gamedevs working on multiplayer FPSs and MMOs (which requires resolving incredibly complex state synchronizations at millisecond-scales) have done this for decades ...no they haven't? Those aren't distributed systems. There is an authoritative server that holds the source of truth, and players sync up with it. A truly distributed game would have each game client contain the full world state, and would synchronize with every other player rather than an authoritative server.

nivenkos 5y ago

If you drop the P2P requirement, you can use Operational Transformations - https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation

dboreham 5y ago

> they haven’t been using any fancy CRDTs CRDT is actually "the tricks we have always used + math to prove whether they work or not". Read the papers. You'll find old school stuff like Lamport Clocks.

sunny--tech 5y ago

This is only tangentially related to your point, but Riot uses CRDTs for their chat system. https://technology.riotgames.com/news/chat-service-architecture-persistence https://technology.riotgames.com/news/chat-service-architect...

cyber_kinetist 5y ago
Maybe CRDTs are useful for implementing chat systems since the operational semantics for it are simple enough to make a CRDT system for it? The blog post I've read in the first link seems to say that CRDTs gets very complex when applying it to a domain where there are all kinds of different rich operations. I guess CRDTs aren't fundamentally the right solution for the collaborative document editing problem then?

User23 5y ago

> Gamedevs working on multiplayer FPSs and MMOs (which requires resolving incredibly complex state synchronizations at millisecond-scales) have done this for decades No they haven't. Servers crash and players drop all the time, and many things otherwise don't always act as intended. But practically it doesn't matter because nobody, not the developers and not the players, cares about whether or not their FPS is byzantine fault tolerant.

cyber_kinetist 5y ago
I mean, they aren't perfect, but you've got to admit they were solving a hard problem with immense technical constraints. And they certainly care about robust synchronization, since subpar netcode can absolutely determine the success or failure of certain types of games (shooters, fighting games). Players always whine about netcode all the time, although 100% byzantine fault tolerance is not the goal. Speaking of which, do you really need byzantine fault tolerance in a document editor? I mean, it would be really great if it were possible, but given the vast number of different operations you can perform in a document it seems like a really daunting task to do so both formally and practically. And Google Docs isn't really comparable to Bitcoin or airplane control systems anyway. Perhaps temporary periodic backups (like saving diffs to documents in 5-second intervals for a recent period window, so you can rollback if things seriously fuck up) as an escape hatch would be good enough?

hesdeadjim 5y ago

Realtime multiplay state sync isn't remotely like CRDT, it's an endless series of hacks where you attempt to send as little data as possible to have the best player experience as possible. Total smoke and mirrors. It's fantasy to assume a client has any real "truth" about the world over the span of milliseconds, and in practice you want the client to be as ignorant as possible because cheat programs will let people see through walls, see across the map, etc. You compensate through speculative prediction to try and make things like movement or gunshots feel lag-free, but again it's smoke and mirrors and a hundred things can cause that to go wrong. How do we resolve mis-predictions to the player? Hide it as best as possible through VFX is a great technique, or hope the users don't notice that a couple of their bullets had exactly zero effect because the server decided you shot outside the rollback buffer and didn't actually hit that other player. It's very game-dependent too. Valorant hits a 120hz tick rate through insane optimization, and if you have a low-latency connection your view of the world will be much, much more in sync with truth compared to a game like PubG that early on had a tick rate around 15hz (oof). It's always been a bucket list gamedev goal of mine to work on realtime multiplayer, but after a couple years of doing it I find myself fantasizing of a world where everyone is playing on a computer that isn't a potato with a connection that isn't jittery.

dnautics 5y ago

Not really a CRDT UseCase. Gamedev needs A<=>S and B<=>S, where S is a central server. CRDT is: A<=>B A<=>C B<=>C A<=>D ...

cyber_kinetist 5y ago
First of all, why do you need serverless P2P on a collaborative document editor? I can't really think of any substantial benefits of doing so. And If you're actually worrying about centralization, then why can't one user run the server as well as the client (which, reading some posts about CRDT performance, should be faster than the overhead of maintaining CRDTs anyway?)
- dnautics 5y ago
  Latency.
  - cyber_kinetist 5y ago
    Isn't the latency about the same as P2P if a single user is hosting both the server and the client?

remram 5y ago

Those games have an authoritative central server, so using OT or something akin to OT is trivial. Even in P2P games or games with a weaker server, a given entity is owned by a single machine. This is a much simpler setup.

jitl 5y ago

The major difference in constraint is how much user intention/data it's acceptable to discard, especially when a user message arrives later than expected. In a multiplayer game, it's fine to discard all user intention that arrives a few minutes "late" - gameplay has moved on, and the client should discard local state and just use the server state. But this is totally unacceptable for a text editing application. CRDTs or Operational Transforms are strategies that allow accepting user edits and preserving their intention even if the user is days or weeks behind or diverged from the server state. I'm not aware of a real-time multiplayer game that allows such high latency for user input. I like this talk on Overwatch's data model (entity-component-system model) https://www.gdcvault.com/play/1024001/-Overwatch-Gameplay-Architecture-and https://www.gdcvault.com/play/1024001/-Overwatch-Gameplay-Ar... - the discussion of netcode starts at timestamp 22:30

cyber_kinetist 5y ago
So the primary reason of CRDTs is to enable offline editing? The issue is, I don't think CRDTs will help with offline editing either. If the user edits are days / weeks behind and the documents have severely diverged, then merging two documents becomes less of a theoretical logic problem and more of a pragmatic domain-specific problem that might even require the input of the user (like a merge-tool). CRDTs will ensure that the output is deterministic and correct, but it will not guarantee how "natural" or "reasonable" the output will look, and I think you would have to eventually use a bunch of clever heuristics or even provide a mergetool for the user to cleanly resolve differences.
- jitl 5y ago
  > offline editing I guess, offline is relative? Most games I play consider >300ms ping to be offline, but I should be able to edit a document with >300ms ping. That said, a lot of CRDT research is focused on totally local, peer to peer editing. > it will not guarantee how "natural" or "reasonable" the output will look I don’t think your assumptions are correct. CRDT algorithms designed for text structures like those used by Automerge (RGA) or Y.js (YATA) do a good job preserving user intent even for concurrent edits to a text. Users won’t end up with the letters in a sentence interleaved, and it’s actually pretty rare in to encounter concurrent insertions at the same position - those are the most troublesome for both time complexity and intention preservation. Most other kinds of document edits - like edits on a order of paragraph items - are much easier.

phailhaus 5y ago

> Gamedevs working on multiplayer FPSs and MMOs (which requires resolving incredibly complex state synchronizations at millisecond-scales) have done this for decades ...no they haven't? Those aren't distributed systems. There is an authoritative server that holds the source of truth, and players sync up with it. A truly distributed game would have each game client contain the full world state, and would synchronize with every other player rather than an authoritative server.