4 ms·

As a somewhat interested observer of the CRDT space, I always wondered if it would be possible to create a more general purpose "structured data" CRDT. I.e that

As a somewhat interested observer of the CRDT space, I always wondered if it would be possible to create a more general purpose "structured data" CRDT. I.e that the user define a model/schema to describe semantically valid states. If you just merge e.g JSON you might end up in a state that's syntactically valid, but doesn't make any sense. Similar how the Pretext algorithm know that bold/italic/underlining operations are additive while highlighting colouring is not, I'm thinking the user could control the schema to declare that "state: notStarted" and "completionDate: 2023-09-04" is incompatible

paulgb 3y ago
> I always wondered if it would be possible to create a more general purpose "structured data" CRDT. Technically yes; one approach would be to use a list CRDT containing representations of operations on the data structure. Each replica would play the operations forward and reject any that broke the schema to “project” the operations onto a local representation of the shared data structure. So in your example, the operation to set state: notStarted would be rejected if a completion date were present. Besides the fact that the computational cost of the data structure will only ever grow, another consideration is that even though you are locally only appending to the list of operations, operations from peers may arrive that are not at the end of the global order. This approach would only guarantee that the data is consistent and meets the schema — it doesn’t guarantee that merges are semantically what a user would expect.
refset 3y ago
CRDT synthesis feels like a promising direction, e.g. see "Katara: Synthesizing CRDTs with Verified Lifting"/ https://arxiv.org/abs/2205.12425 https://arxiv.org/abs/2205.12425 / previous discussion https://news.ycombinator.com/item?id=32977887 https://news.ycombinator.com/item?id=32977887
refulgentis 3y ago
I've hoped for so long that I've sort of given up: inevitably each implementation requires very specific judgement calls about what edits mean and even after all the computer science, is missing fundamental things. (c.f. first footnote about deletes aren't un-doable). Every time I look into it I end up at "might as well write real syncing code, it'll be done by the time I have this compiling and a UI around it"
iudqnolq 3y ago
You can get a surprisingly long way by just saying each field has atomic and independent changes. That's what Figma does. For structured data it seems to map well to what the user expects. If Bob drags something five pixels right and Jane drags it ten pixels then they find it reasonable if the state is five or ten; fifteen or 7.5 would be surprising. You can also implement what you want at read time. "notStarted = !state.completionDate && !state.started". Edit: Figma does this with their own server and client that intelligently handle invalid states like the parent pointers forming a loop. So it's not quite fair to say it's "just" that simple.
- jitl 3y ago
  This is fine for everything except text

paulgb 3y ago

> I always wondered if it would be possible to create a more general purpose "structured data" CRDT. Technically yes; one approach would be to use a list CRDT containing representations of operations on the data structure. Each replica would play the operations forward and reject any that broke the schema to “project” the operations onto a local representation of the shared data structure. So in your example, the operation to set state: notStarted would be rejected if a completion date were present. Besides the fact that the computational cost of the data structure will only ever grow, another consideration is that even though you are locally only appending to the list of operations, operations from peers may arrive that are not at the end of the global order. This approach would only guarantee that the data is consistent and meets the schema — it doesn’t guarantee that merges are semantically what a user would expect.

refset 3y ago

CRDT synthesis feels like a promising direction, e.g. see "Katara: Synthesizing CRDTs with Verified Lifting"/ https://arxiv.org/abs/2205.12425 https://arxiv.org/abs/2205.12425 / previous discussion https://news.ycombinator.com/item?id=32977887 https://news.ycombinator.com/item?id=32977887

refulgentis 3y ago

I've hoped for so long that I've sort of given up: inevitably each implementation requires very specific judgement calls about what edits mean and even after all the computer science, is missing fundamental things. (c.f. first footnote about deletes aren't un-doable). Every time I look into it I end up at "might as well write real syncing code, it'll be done by the time I have this compiling and a UI around it"

iudqnolq 3y ago

You can get a surprisingly long way by just saying each field has atomic and independent changes. That's what Figma does. For structured data it seems to map well to what the user expects. If Bob drags something five pixels right and Jane drags it ten pixels then they find it reasonable if the state is five or ten; fifteen or 7.5 would be surprising. You can also implement what you want at read time. "notStarted = !state.completionDate && !state.started". Edit: Figma does this with their own server and client that intelligently handle invalid states like the parent pointers forming a loop. So it's not quite fair to say it's "just" that simple.

jitl 3y ago
This is fine for everything except text