4 ms·

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 pe

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.

deleted 4y ago
[deleted]
josephg 4y ago
All the CRDTs I'm looking at here are doing the work in memory only. Adding a good persistence layer is a big missing piece here. But some people are working on adding CRDTs to sqlite: https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite 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. I went into a lot more detail about what it might look like here: https://github.com/vlcn-io/cr-sqlite/issues/65#issuecomment-1325620964 https://github.com/vlcn-io/cr-sqlite/issues/65#issuecomment-...
burdiyan 4y ago
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.
- AlexErrant 4y ago
  https://github.com/vlcn-io/cr-sqlite/ https://github.com/vlcn-io/cr-sqlite/ > Tables are modeled as GSets... > 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.)
  - burdiyan 4y ago
    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.

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.

deleted 4y ago

[deleted]

josephg 4y ago

All the CRDTs I'm looking at here are doing the work in memory only. Adding a good persistence layer is a big missing piece here. But some people are working on adding CRDTs to sqlite: https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite 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. I went into a lot more detail about what it might look like here: https://github.com/vlcn-io/cr-sqlite/issues/65#issuecomment-1325620964 https://github.com/vlcn-io/cr-sqlite/issues/65#issuecomment-...

burdiyan 4y ago

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.

AlexErrant 4y ago
https://github.com/vlcn-io/cr-sqlite/ https://github.com/vlcn-io/cr-sqlite/ > Tables are modeled as GSets... > 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.)
- burdiyan 4y ago
  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.