CRDT resources
wiki.nikitavoloboev.xyz
wiki.nikitavoloboev.xyz
It's better to post the most interesting item on the list. That increases the chance that there's something specific to talk about.
https://hn.algolia.com/?dateRange=all&page=0&prefix=true&sor...
My concern is thread quality. Lists of "resources about X" don't have anything really to discuss beyond "X in general", and maybe supplying links that didn't make the list. That's not, in the general case, enough to support a curious conversation—when it comes to forum threads, "generic" implies "shallow" and "repetitive".
In this case the thread wasn't so bad, probably because CRDTs aren't in the most-discussed-topic set [1]. So as a generic submission it's better than, say, a list of Rust resources or something [2]. Still, we have to derive moderation principles for the general case, and this principle (about lists) is surprisingly reliable and solid.
[1] https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
[2] https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
My understanding is that CRDT's rely on having a safe place to store data on the user's machine (otherwise it's a bit like doing a `git clone` to receive new data, rather than a `git pull`).
Is this not a major limitation for people hoping to use it for web apps?
I wonder about the energy consumption aspect of content adressing. Redundancy eats resources.
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.
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.
https://technology.riotgames.com/news/chat-service-architect...
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?
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.
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?
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.
CRDT is:
A<=>B A<=>C B<=>C A<=>D ...
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?)
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.
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-Ar... - the discussion of netcode starts at timestamp 22:30
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.
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.
That said I think games are in many cases behind (except fighting games because they care a bit more about outcome accuracy), I think a big part of it is that most rely on pre-made physics systems that might be impressive at rolling around particles and ragdolls but are not designed for multiplayer games to the slightest so they kinda start blowing up when you start mucking around with their states (I suspect this is why fighting games are ahead imo since they often has bespoke essentially 2d sims).
I actually implemented a coop multiplayer prototype over WebSockets for a wolf-style raycasting FPS game I had made for 7dfps that was based on OT (like many fighting games are). It's fairly simplistic (if you bring over the collision and physics work inside the OT simulation).
OT was a good choice since it would eliminate desynchronization issues, and since I was using websockets that are reliable and but can have some lag getting things reliable from the get-go was a better option.
---
1: The server runs a single truth state a second or so back in time (sent over to clients upon connection). The server never re-simulates anything (clients will, see below)
2: The server keeps a log of events back to the truth cutoff point, once the truth cutoff is passed they're not needed by the server anymore (unless some laggy client hasn't received them yet, but if that clients goes too far behind it should be dropped so no issues for the server about overflowing).
3: Upon connecting clients synchronize time with the server before receiving state and all existing messages.
4: New game states are produced immutably from the previous (with any messages tied to the point in time).
5: When shooting,etc the client sends a timestamped message to the server, the server MIGHT elect to discard or re-time any message a client sends before logging and broadcasting (this is why the time synchronization earlier was important, clients should be created at the "now" point in time or might be re-timed by the server to deter hacking).
6: A client keeps all states between the truth and now, the server will inform clients as the truth moves forward in time so they can discard old states, any message can come from the server as being timed between truth and now and all "old" messages causes a rebuild of states between the message time and "now" (The "now" state is what we display to the user)
7: A client display-cache synchtonizes with "now" and renders, if a server sent "old" messages that caused an enemy to change direction back in time the cache will handle tweening or snapping (and this is totally separated from the simulation).
Since the client created a message at "now" it would've been sent directly to the display cache (and triggered immediate feedback to the user), past changes by the server can undo things (f.ex. if you just died before shooting) but handling that smoothly is not related to the simulation code that can remain clean but rather the display cache handler.
---
Sadly I only did this as a side-project and some contracts took over so it's been kinda bit-rotting after I left it mid-refactor (it was kinda messy and tied to the game it was written for), but the architecture felt quite stable once working (one minor issue might is that it works best with fixed-point math due to floating point numbers potentially diverging, even if gradual checkpoints by the server could be introduced).
...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.
Resist using acronyms before defining them. Don't just do it because everyone else does it. You are only creating barriers for people who might be interested in what you are talking about. I know people do this intentionally too. Don't be so insecure. You don't need to invent special language to remain relevant.
Another user commented on a similar thing earlier today: https://news.ycombinator.com/item?id=28997945
There are 2 variants which confusingly have a very similar acronym:
- CmRDT: Commutative Replicated Data Types (also known as operation-based CRDTs). These CRDTs replicate state by transmitting update operations to peers. Peers are always able to apply these operations in any order and without conflicts.
- CvRDT: Convergent Replicated Data Types (also known as state-based CRDTs). These CRDTs replicate state by transmitting the entire object every time an update is made to a local replica. Peers are able to merge the state they receive with their local copy without conflicts.
Why I find that funny is that I made that repo on a whim while I was doing my own reading, and then did nothing with it. Maybe I tweeted it? But somehow it SEOed well with Google for a stretch and I've been getting a steady stream of stars on that repo ever since. I assume it was because I created it when CRDTs were still early and so it got the clicks.
I'm sure a lot of folks here know what it's like to try to put projects out there and go looking for traction. It's always made me chuckle that one of my biggest successes was the unintentional one.
A big thing i'm currently learning with them is to write a content addressable system with a more forgiving merge policy between parties.
Yea i often see people nitpick CRDT about user intention, and where it should be `ADBC` or `ABCD`, but in my case i'm focusing on multi-device, not multi-user - and even in multi-user it's still best-in-breed when you are designing away from centralization.
I'm still struggling to learn the more complex approaches to CRDT. So many resources focus on the low hanging fruit of CRDT. Grow counters, basic text editing, etc. I need to build the full suite of data structures; maps, sets, lists, etc.
Redis uses CRDTs for active-active architectures [1] and for some of their native data structures [2].
Riak also uses them in their data store [3].
And looks like PayPal might use them for consensus purposes (I found this while looking up the Riak talk so I haven't actually watched it) [4]
1: https://redis.com/blog/diving-into-crdts/
2: https://redis.com/videos/active-active-geo-distribution-redi...
3: https://www.youtube.com/watch?v=f20882ZSdkU&ab_channel=Erlan...
Firefox on Android.
Or did you observe that 100% of the people who blogged about CRDTs implemented CRDTs and then wrote a blog post?
Joking aside though, CRDTs are still a pretty esoteric space and all the various blog posts came in handy when I was researching how to build my own CRDT.
Most of the resources I've seen on CRDTs are from whitepapers and those can be difficult to read if you don't have a math background. I gave a talk at a Papers We Love [1] explicitly because I found the academic papers a big turn off from many people interested in the space.
[1]: https://www.youtube.com/watch?v=1Bs3Fj9rvks&t=2169s&ab_chann...
https://arxiv.org/abs/2004.00107#
The link takes you to our Merkle-CRDTs paper, which includes a nice intro to CRDTs in general, so no prior knowledge needed!