5 ms·

I work on a collaborative text editing system (https://www.notion.so https://www.notion.so) and read a lot about CRDTs, thank you for your work in this area, pa

by jitl 5y ago

I work on a collaborative text editing system (https://www.notion.so https://www.notion.so) and read a lot about CRDTs, thank you for your work in this area, particularly https://josephg.com/blog/crdts-go-brrr/ https://josephg.com/blog/crdts-go-brrr/ 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.

deleted 5y ago
[deleted]
derefr 5y ago
> no user wants to fiddle with a merge UI or picking versions like with iCloud. 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-20a1873baf334d528bca621fa9717ccb 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.)
- tylerhou 5y ago
  There is no notion of “same time” in a distributed system — what if a client locks a line and disconnects? Also, it leads to a poor user experience.
  - derefr 5y ago
    My vision of this wouldn’t involve not accepting edits; but rather, the document would react to you trying to edit a locked block the same way macOS reacts to you trying to edit a locked document: offer to duplicate the block and then let you edit the duplicate. Both versions of the block would then appear in the document, perhaps with some annotation that they’re sibling forks of the same original text. (Compare and contrast: books that compare-and-contrast works with subtle changes between different versions, e.g. the four Gospels of the Bible.) 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.)
    - tylerhou 5y ago
      Group chat apps don’t care about preserving functionality when the network drops. But a document editor does. And editing a message is relatively rare in chat apps so they can afford to lock; editing a line is common in documents and the chance of a lock conflict is higher. 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://lamport.azurewebsites.net/pubs/time-clocks.pdf https://static.googleusercontent.com/media/research.google.com/en//archive/chubby-osdi06.pdf https://static.googleusercontent.com/media/research.google.c... https://en.m.wikipedia.org/wiki/Fallacies_of_distributed_computing https://en.m.wikipedia.org/wiki/Fallacies_of_distributed_com...
taeric 5y ago
While I am sympathetic to the idea that users don't like merges, they also hate idiotic combinations of data without their oversight. So, bit of a rock and a hard 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.
prox 5y ago
I really seen a lot of buzz recently about notion, cool work you are doing.
somenewaccount1 5y ago
Is there a developer community or forum for the notion.so api? The slack channel published on your developer website is down.
- jitl 5y ago
  We have the Slack you mentioned (invite: https://notiondevs.slack.com/join/shared_invite/zt-vkinpzs0-hJSEAAxJzPMuiCNvZETF2A#/shared-invite/email https://notiondevs.slack.com/join/shared_invite/zt-vkinpzs0-...) and a Stack Overflow tag (https://stackoverflow.com/questions/tagged/notion-api https://stackoverflow.com/questions/tagged/notion-api). The Slack link from https://developers.notion.com 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-outage-morning-disruption-work-chat https://www.theverge.com/2021/9/30/22702876/slack-is-down-ou...
  - somenewaccount1 5y ago
    Thank you for the correct link The Slack link I mentioned is https://join.slack.com/t/notiondevs/shared_invite/zt-lkrnk74h-YmPRroySRFGiqgjI193AqA 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/ https://developers.notion.com/
    - jitl 5y ago
      We’ve fixed the link in the footer there, thanks for letting me know.
josephg 5y ago
Oh cool! I've wanted something like notion for years. Ideally on top of CRDTs (so I own my own data). I really appreciate all the work your company is doing! Feel free to get in touch if you want to have a proper chat about this stuff. > 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.

by jitl 5y ago

deleted 5y ago

[deleted]

derefr 5y ago

> no user wants to fiddle with a merge UI or picking versions like with iCloud. 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-20a1873baf334d528bca621fa9717ccb 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.)

tylerhou 5y ago
There is no notion of “same time” in a distributed system — what if a client locks a line and disconnects? Also, it leads to a poor user experience.
- derefr 5y ago
  My vision of this wouldn’t involve not accepting edits; but rather, the document would react to you trying to edit a locked block the same way macOS reacts to you trying to edit a locked document: offer to duplicate the block and then let you edit the duplicate. Both versions of the block would then appear in the document, perhaps with some annotation that they’re sibling forks of the same original text. (Compare and contrast: books that compare-and-contrast works with subtle changes between different versions, e.g. the four Gospels of the Bible.) 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.)
  - tylerhou 5y ago
    Group chat apps don’t care about preserving functionality when the network drops. But a document editor does. And editing a message is relatively rare in chat apps so they can afford to lock; editing a line is common in documents and the chance of a lock conflict is higher. 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://lamport.azurewebsites.net/pubs/time-clocks.pdf https://static.googleusercontent.com/media/research.google.com/en//archive/chubby-osdi06.pdf https://static.googleusercontent.com/media/research.google.c... https://en.m.wikipedia.org/wiki/Fallacies_of_distributed_computing https://en.m.wikipedia.org/wiki/Fallacies_of_distributed_com...

taeric 5y ago

While I am sympathetic to the idea that users don't like merges, they also hate idiotic combinations of data without their oversight. So, bit of a rock and a hard 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.

prox 5y ago

I really seen a lot of buzz recently about notion, cool work you are doing.

somenewaccount1 5y ago

Is there a developer community or forum for the notion.so api? The slack channel published on your developer website is down.

jitl 5y ago
We have the Slack you mentioned (invite: https://notiondevs.slack.com/join/shared_invite/zt-vkinpzs0-hJSEAAxJzPMuiCNvZETF2A#/shared-invite/email https://notiondevs.slack.com/join/shared_invite/zt-vkinpzs0-...) and a Stack Overflow tag (https://stackoverflow.com/questions/tagged/notion-api https://stackoverflow.com/questions/tagged/notion-api). The Slack link from https://developers.notion.com 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-outage-morning-disruption-work-chat https://www.theverge.com/2021/9/30/22702876/slack-is-down-ou...
- somenewaccount1 5y ago
  Thank you for the correct link The Slack link I mentioned is https://join.slack.com/t/notiondevs/shared_invite/zt-lkrnk74h-YmPRroySRFGiqgjI193AqA 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/ https://developers.notion.com/
  - jitl 5y ago
    We’ve fixed the link in the footer there, thanks for letting me know.

josephg 5y ago

Oh cool! I've wanted something like notion for years. Ideally on top of CRDTs (so I own my own data). I really appreciate all the work your company is doing! Feel free to get in touch if you want to have a proper chat about this stuff. > 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.