I wonder how performance would change if using SQLite instead. You would get those range trees and indexes for free (hence much simpler implementation). Plus persistent storage, some guarantees, etc.
It'd be really fun to see if this approach can be adapted to sqlite's b-tree. But it might not work as-is. The b-tree implementation I have is quite a bit different from most b-trees because I'm storing offsets rather than "keys", and because I'm storing compacted runs of items rather than individual rows.
Which parts of SQLite have range trees? How would you see a CRDT implemented using SQLite? I've been thinking a lot about fitting SQLite into the world of CRDT, but haven't come up with a good-enough generalized approach.
> Rows are currently modeled as LWW maps. I.e., each column in a row is a LWW Register.
Multi value registers are also planned - though I'm not sure how that'll be implemented.
(One also has the opportunity to see failing writes to the LWW register, so for my app I can (in theory) potentially surface those somewhere to the user as a resolvable conflict.)
Yeah, I've seen this project. Looks pretty interesting!
Although probably the most challenging data type to get right would be RGA, especially for text. Not to mention rich text :)
Sets and registers in the end are pretty straight-forward as soon as one understand the idea of causality, partial order, and arbitrary total order. In terms of the implementation there's also not a lot to optimize I believe, and at worst you could simply store a counter along with the value.
But RGA is a whole different story. Especially in the context of SQLite, which doesn't have default page compression, or prefix compression for keys.
Still, one probably could put together something similar to how Yjs deals with that, and store chunks of data as rows in a table.
