For prose text, what do you think about combining a document-scale CRDT, with fine-grained locking — e.g. splitting the document into a "list of lines/sentences", where lines have identity, and then only allowing one person to be modifying a given line at a time?
I've always felt like this was under-explored, given that in prose text it's almost always semantically incoherent for multiple people to be trying to change a single sentence in different ways at the same time anyway (i.e. they would each have a series of edits they want to do to line A to turn it into either A' or A"; but any result that's not either purely A' or A" will very likely be nonsensical. One could say that the A → A' transformation a user does to a sentence is intentionally transactional.)
I almost thought Notion would be a good example of this, but apparently not (https://www.notion.so/Real-time-collaboration-20a1873baf334d...) — they actually do allow multiple users to be editing the same leaf-node content block at the same time, and so have taken on the full scope of the CRDT problem.
> but I don’t want to force new clients to download the entire history nor do I want these big histories in my cache, so I end up wanting a hot/cold system; and building that kind of thing and dealing with the edge cases seems like more than 100 lines of code.
Yes, but these needs are able to be cleanly abstracted away on the backend — there are internally-complex infrastructure components (like CouchDB, or Kafka) that expose a pure CQRS model to clients, but internally are doing fancier stuff involving reducing changes onto snapshots and then exposing new CQRS streams that begin history with atomic "introduce all this stuff from a snapshot"-typed 'changes'.
There's also some convergent evolution happening here with non-replay sync strategies in blockchains (which can be more interesting to look at if you care about the serverless p2p Operational Transformation type use-case of CRDTs.)
Also, it leads to a poor user experience.
Also, I’m speaking about locking that’s fine-grained temporally as well as spacially: a line would only need to be locked with a ~10s TTL when a user begins to type in that line. Think of it like the user composing a transaction of modifications to the same line, and then committing it. A lot like typing a message into a chat program. Just the user having their cursor on the line, wouldn’t imply that the line is locked; it would only lock when they start typing.
This is already how group-chat apps work, mind you; if you’re an admin who can edit other people’s message lines, you nevertheless can’t edit someone else’s message line while they’re editing it. But they’re only considered to be editing it while they’re actively typing, and for a few seconds after that. If they go idle, someone else edits their message-line, and then you come back and try to submit your edit, it will be rejected. (Of course, that behaviour makes perfect sense for group chat software, where the only other people who can edit your text are moderators, and so moderation actions should “trump” user actions. In a p2p collaboration context, IMHO adding resistance/intentionality to per-line forking, but nevertheless allowing it, makes the most sense.)
Your suggestion also assumes that the network is reliable. What happens if a user takes a lock and there is a partition? If the document is P2P, there is no central authority; when should the other participants override the lock? How much overhead does that add to the protocol?
The main point is that there is no notion of a central clock in a distributed system; hence “lock temporally” is not precise. Relative to which participant? And what happens when messages are dropped? (Even the lock message might be dropped!) A distributed lock implementation is non-trivial.
https://lamport.azurewebsites.net/pubs/time-clocks.pdf
https://static.googleusercontent.com/media/research.google.c...
https://en.m.wikipedia.org/wiki/Fallacies_of_distributed_com...
If you're using a system where you're guaranteed to have knowledge of what other people are editing at all times, there's really no need to use CRDTs in the first place.
If you want collaboration between people, you have to structure it in a way that makes it a conversation, I believe.
I could almost see an idea that you could pattern it after musicians playing together, but that is a very particular kind of rehearsal that has not been done in any other practice, as far as I am aware. Improv may come close, but even that has very specific techniques that really don't make sense in a CRDT landscape.
> My biggest open question is how to design my centralized server side storage system for CRDT data. To service writes from old clients I need to retain a total history of a document, but I don’t want to force new clients to download the entire history nor do I want these big histories in my cache, so I end up wanting a hot/cold system; and building that kind of thing and dealing with the edge cases seems like more than 100 lines of code.
Yeah definitely more than 100 lines of code. I'm sad to report that in diamond types (my own CRDT) I've spent ~12000 lines of code in an attempt to solve some of these problems. I could probably get that down under 3000 loc in a rewrite if I'm happy to throw away some of my optimizations. Doing so would dramatically lower the size of the compiled wasm bundle too - though the wasm bundle is still comfortably under 100kb over the wire, so maybe its fine?
Regarding history, I have a lot of thoughts. The first is that with the right approach, historical data compresses really well. Martin Kleppman's automerge-perf data set has 260k edits ending in 100kb of text. The saving system I'm working on can store the entire editing history (enough to merge changes from any version) in this example with just 23kb of overhead on disk. I think that resulting data set might only need to be accessed in the case of concurrent changes, and then only back as far as the common ancestor. But I haven't implemented that optimization yet.
And yeah; I've been thinking a lot about what a CRDT-native database could look like too. There's way too many interesting and useful problems here to explore.
The Slack link from https://developers.notion.com works for me, maybe Slack has a DNS issue according to this article? https://www.theverge.com/2021/9/30/22702876/slack-is-down-ou...
The Slack link I mentioned is https://join.slack.com/t/notiondevs/shared_invite/zt-lkrnk74...
The "invite has expired"
It's linked in the footer of https://developers.notion.com/
I agree with your assessments here - CRDT is the way forward for most applications; no user wants to fiddle with a merge UI or picking versions like with iCloud. I think RxDB’s position here is from their CouchDB lineage.
> The biggest roadblock to their use is that they’re poorly understood. Well, that and implementation maturity.
I certainly have more understanding to do. My biggest open question is how to design my centralized server side storage system for CRDT data. To service writes from old clients I need to retain a total history of a document, but I don’t want to force new clients to download the entire history nor do I want these big histories in my cache, so I end up wanting a hot/cold system; and building that kind of thing and dealing with the edge cases seems like more than 100 lines of code.
It seems like the Yjs authors also recognize that CRDT storage on the server is an area to address, there was some work on a custom database in 2018, although my thinking is more about how to retrofit text CRDTs into my existing very conservative production cloud software stack than about writing to block storage.