4 ms·

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

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".

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".