3 ms·

Author here. Happy to answer questions if there are any!

benrbray 5y ago
Nice project! How was your experience using CRDTs? I often see the criticism thrown around that the history might become enormous even with regular usage. I'm curious what you have to say!
- sambigeara 5y ago
  Thanks! Really good question, particularly in this context. It's a problem I'm actively working on. For context: the underlying CRDT is basically a WAL housing all the events originating from user input. The app itself operates "local-first", so as events occur, it collects/flushes partial WALs which are separately aggregated and merged into full ones, and it's these which are shipped around to the various "remotes". These will (by definition) grow indefinitely. In order to try and alleviate some of this, I've written a "compaction" algorithm which retrospectively traverses the WAL and attempts to condense some of the events from many into one. For example, if there are 10 update events on the same item, omit the previous 9 and store only the most recent. It's pretty basic but it's had quite a significant impact thus far. Beyond that, I'm going to have to keep thinking and iterating! The things you get for "free" when building on top of CRDTs are just brilliant, though. For example - I originally built the mergeable WALs purely because it was more convenient for me when syncing notes between my home and work laptops. Turns out that that gave me the collaborative working stuff for free! The real time collab is pretty much a websocket which accepts arbitrary encoded strings and echoes them back to different users. The app itself decides whether or not it's useful and merges it accordingly. I thought that was pretty cool.
  - 3np 5y ago
    You also get robust undo/redo for free I guess! One thing that’s unclear to me: once all replicas are in sync up to a certain event (which should be trivially determinable here), can’t you go even further and discard all past events and replace it with the resulting state snapshot? Or maybe that’s what you mean with compacting 10 to 1 above? Obviously at the cost of the undo history :)
    - sambigeara 5y ago
      Yes! Perhaps not in the way that _some_ might interpret it, though; given it's append-only nature, undo events need to generate a new event, so in practice, you end up with a temporary pointer which traverses back and forth over the WAL, and new events being generated at the head. Admittedly, I actually use a separate legacy log for undo/redo at the moment, with a lifespan as long as a single client session. Room for improvement there (but it does the trick for now). > can’t you go even further and discard all past events and replace it with the resulting state snapshot Good question. Tis a tricky one to solve. If we were to maintain the WAL as a single source of truth, it will theoretically grow indefinitely due to the aggregation of delete-events (e.g. we _always_ need to know if a unique item has been deleted). As it stands, the compaction operates on all history, meaning we lose the richness of the history (whilst maintaining idempotency), but for benefit of reduced space and I/O requirements. If there was a need for point-in-time recovery or historical undo/redo, I could totally set a watermark level, e.g. "only compact up to N days ago".
ampdepolymerase 5y ago
Does it support character level collaboration (like Google docs) or is this just generic entry/line level sync? IIRC CRDTs do not work well for Google-docs type text editing because they cannot capture intent well.
- sambigeara 5y ago
  Currently it's at an entry/line level like you suggest, although theoretically I could flip (for lack of a better term) the algorithm and apply it laterally on a per character basis. The data structure is a WAL storing all mutation events, each of which has a reference to another uniquely identifiable item (by some UUID:timestamp combo). Rather than treating each line as a uniquely identifiable object, I could treat each character as such. Downside of the current implementation is that two people operating offline on the same line will see unpredictable results when they're able to sync again (basically it will just honour the most recent update event). The per-char change above would remedy that, I think!
- sambigeara 5y ago
  Actually, I'm intrigued by what you mean by this: > IIRC CRDTs do not work well for Google-docs type text editing because they cannot capture intent well. Could you elaborate? Appreciate the discussion
  - ampdepolymerase 5y ago
    They don't capture semantic intent that well compared to Operational Transforms when conflict arises. https://www.tiny.cloud/blog/real-time-collaboration-ot-vs-crdt/ https://www.tiny.cloud/blog/real-time-collaboration-ot-vs-cr... Some teams also encountered engineering problems using them. https://news.ycombinator.com/item?id=24186883 https://news.ycombinator.com/item?id=24186883 Done properly however, they can be magical. http://archagon.net/blog/2018/03/24/data-laced-with-history/#demo-concurrent-editing-in-macos-and-ios http://archagon.net/blog/2018/03/24/data-laced-with-history/...
    - sambigeara 5y ago

Nice project! How was your experience using CRDTs? I often see the criticism thrown around that the history might become enormous even with regular usage. I'm curious what you have to say!

sambigeara 5y ago
Thanks! Really good question, particularly in this context. It's a problem I'm actively working on. For context: the underlying CRDT is basically a WAL housing all the events originating from user input. The app itself operates "local-first", so as events occur, it collects/flushes partial WALs which are separately aggregated and merged into full ones, and it's these which are shipped around to the various "remotes". These will (by definition) grow indefinitely. In order to try and alleviate some of this, I've written a "compaction" algorithm which retrospectively traverses the WAL and attempts to condense some of the events from many into one. For example, if there are 10 update events on the same item, omit the previous 9 and store only the most recent. It's pretty basic but it's had quite a significant impact thus far. Beyond that, I'm going to have to keep thinking and iterating! The things you get for "free" when building on top of CRDTs are just brilliant, though. For example - I originally built the mergeable WALs purely because it was more convenient for me when syncing notes between my home and work laptops. Turns out that that gave me the collaborative working stuff for free! The real time collab is pretty much a websocket which accepts arbitrary encoded strings and echoes them back to different users. The app itself decides whether or not it's useful and merges it accordingly. I thought that was pretty cool.
- 3np 5y ago
  You also get robust undo/redo for free I guess! One thing that’s unclear to me: once all replicas are in sync up to a certain event (which should be trivially determinable here), can’t you go even further and discard all past events and replace it with the resulting state snapshot? Or maybe that’s what you mean with compacting 10 to 1 above? Obviously at the cost of the undo history :)
  - sambigeara 5y ago
    Yes! Perhaps not in the way that _some_ might interpret it, though; given it's append-only nature, undo events need to generate a new event, so in practice, you end up with a temporary pointer which traverses back and forth over the WAL, and new events being generated at the head. Admittedly, I actually use a separate legacy log for undo/redo at the moment, with a lifespan as long as a single client session. Room for improvement there (but it does the trick for now). > can’t you go even further and discard all past events and replace it with the resulting state snapshot Good question. Tis a tricky one to solve. If we were to maintain the WAL as a single source of truth, it will theoretically grow indefinitely due to the aggregation of delete-events (e.g. we _always_ need to know if a unique item has been deleted). As it stands, the compaction operates on all history, meaning we lose the richness of the history (whilst maintaining idempotency), but for benefit of reduced space and I/O requirements. If there was a need for point-in-time recovery or historical undo/redo, I could totally set a watermark level, e.g. "only compact up to N days ago".

ampdepolymerase 5y ago

Does it support character level collaboration (like Google docs) or is this just generic entry/line level sync? IIRC CRDTs do not work well for Google-docs type text editing because they cannot capture intent well.

sambigeara 5y ago
Currently it's at an entry/line level like you suggest, although theoretically I could flip (for lack of a better term) the algorithm and apply it laterally on a per character basis. The data structure is a WAL storing all mutation events, each of which has a reference to another uniquely identifiable item (by some UUID:timestamp combo). Rather than treating each line as a uniquely identifiable object, I could treat each character as such. Downside of the current implementation is that two people operating offline on the same line will see unpredictable results when they're able to sync again (basically it will just honour the most recent update event). The per-char change above would remedy that, I think!
sambigeara 5y ago
Actually, I'm intrigued by what you mean by this: > IIRC CRDTs do not work well for Google-docs type text editing because they cannot capture intent well. Could you elaborate? Appreciate the discussion
- ampdepolymerase 5y ago
  They don't capture semantic intent that well compared to Operational Transforms when conflict arises. https://www.tiny.cloud/blog/real-time-collaboration-ot-vs-crdt/ https://www.tiny.cloud/blog/real-time-collaboration-ot-vs-cr... Some teams also encountered engineering problems using them. https://news.ycombinator.com/item?id=24186883 https://news.ycombinator.com/item?id=24186883 Done properly however, they can be magical. http://archagon.net/blog/2018/03/24/data-laced-with-history/#demo-concurrent-editing-in-macos-and-ios http://archagon.net/blog/2018/03/24/data-laced-with-history/...
  - sambigeara 5y ago