First of all, thank you all for this awesome library and community. I have the itch to develop a collaborative rich text editor for years, using ShareJS and Substance, but now with Y.js and Prosemirror, it all seems to be super close to what I have in mind
I have been experimenting with Y.js in an attempt to implement timeslider, similar to what Etherpad (Lite) has, and one that works with clients that may go offline/have an unstable Internet connection.
Currently, I have a working editor connected to the back-end server via y-websocket, and have a modified version of y-leveldb that saves all updates and produces a snapshot every 50 updates but without deleting the updates.
Suppose I understand correctly, in client-server topologies, once a client goes online afterward, the client will try to sync the latest copy of the certificate to the server, from which the server will store it as a single update at the end. However, if I want to respect the local changes as individual updates (say there are 100 updates in the local browser during offline, and I would like to store these 100 updates individually with timestamp), what would be the recommended way to achieve so?
I am sorry if I am misunderstanding the protocol/misusing some of the terminologies here. I am still trying to understand the algorithms under the hood, and any help would be much appreciated.
In Yjs, there are only snapshots. A snapshot allows you to reconstruct an old state. I feel that timestamps are unsuited for implementing a versioning approach. Don’t get me wrong, I love the Etherpad timeslider. But in practice nobody will use it. If you allow offline/p2p editing, the timeslider also won’t make any sense, because timestamps (the kind that refers to time) don’t reflect the state of a document.
Instead of a timeslider, you can create snapshots of your document. Then you can use these snapshots to revert to an old document state and even compute the differences between snapshots.
A short explanation why timesliders are not natural to CRDTs: Time is relative and you can create operations without the knowledge of some clients (there is no centrality that can be used to define a change as published). Even with timestamps associated to individual edits, a linearization of the edit history might not make sense to a user, because these edits may have been constructed in subnetworks. So the editor state of timestamp X might be different after syncing with other clients.
I think that Snapshots are much more powerful and better communicate to a user what they mean. Timesliders are better implemented with central authorities.
Thank you for your reply, and thank you for helping me understand the design rationale of Yjs better! I agree that time-slider is not something native to CRDT as a whole, given edits can take place out of order. And while in the design here, I hope the server acts as a central authority of some sort instead of local-first, I acknowledge this is a niche use-case and not what Yjs (and other CRDT solutions) is originally designed for.
A short explanation why timesliders are not natural to CRDTs: Time is relative and you can create operations without the knowledge of some clients (there is no centrality that can be used to define a change as published). Even with timestamps associated to individual edits, a linearization of the edit history might not make sense to a user, because these edits may have been constructed in subnetworks. So the editor state of timestamp X might be different after syncing with other clients.
I agree that a traditional linear representation of a document’s editing history does not make too much sense in the Yjs world. And given many software suites in the market that supports collaborative editing (CRDT or OT) are doing snapshots (automatic or manual), I can appreciate why. On top of that, what if I am to add a local timestamp whenever a local user does a particular operation so that the server can kinda reconstruct an editing trail of this user (given we can trust the timestamps)? If the set of operations can get sent to the server in whole (instead of just sending two deltas), the server will have enough information to reconstruct the editing history of a particular history, and may represent it as something like Github’s Network Graph). Of course, the storage, network traffic, and processing time will be concerns in a large-scale application, and I agree that most other users of Yjs probably won’t benefit from that.
I guess you can associate a timestamp with each update on the server. But you would also need to store every single update separately on the server. Then you can reconstruct the Yjs document using all updates before a certain timestamp.
You could also store a lot of snapshots instead. I’m not sure which approach would work better in practice. The advantage of using snapshots is that you don’t need to reconstruct the document all the time. Maybe you could simply take a snapshot after 5 seconds without any changes by any user.
A graph representation would definitely be interesting. A graph representation is much easier to implement if you have a central authority. In Yjs, you can merge with any peer at any time, so it is a bit harder to represent. But I think that would be very interesting.
Oh my, the deep dive video is such a good one. I am still midway there watching, and I start to piece together the philosophy behind Yjs’ implementation, filling many of the holes that I have overseen when I just read the code. It is just so cool. Thank you so much for doing that with Joseph - it was like a dream came true.
I guess you can associate a timestamp with each update on the server. But you would also need to store every single update separately on the server. Then you can reconstruct the Yjs document using all updates before a certain timestamp. You could also store a lot of snapshots instead. I’m not sure which approach would work better in practice. The advantage of using snapshots is that you don’t need to reconstruct the document all the time. Maybe you could simply take a snapshot after 5 seconds without any changes by any user.
Indeed, I believe it would need a data structure for each single update and another for snapshots (automatic or manual) so that we don’t need to go through all the updates. Since the time-slider (or the history feature as a whole) is not something most users would access all the time, we can probably put some of the older updates in colder storage, while maintaining the few latest snapshots and updates not yet in snapshots in hotter storage, for synchronization.
A graph representation would definitely be interesting. A graph representation is much easier to implement if you have a central authority. In Yjs, you can merge with any peer at any time, so it is a bit harder to represent. But I think that would be very interesting.
I imagine the graph representation to be reminiscent of git history. When it gets synchronized to the central authority, it is like a git merge - the merge commit contains a reference to both the original branch’s latest commit (authority’s updates/snapshots) and the merging branch’s latest commit (client’s updates). Unlike commits, CRDT updates are much more versatile and do not contain references to previous records, so I think both the client and the server will have to keep track of updates in a strictly incremental manner (which I believe y-leveldb is already doing). The server also needs to save individual updates (including the session ID and the client’s own incremental update sequence), which is currently not present to my knowledge.
If I am to hack on the internals of Yjs here, where would you suggest to start with? Should I first start with y-prosemirror to add in timestamp for each updates (which I think there should be no existing APIs for that?) and then y-protocols to create a new synchronization protocol that would require clients to send all its updates in serial instead of just a two-step handshaking? Or would you have any suggestions?
