3 ms·

I'm happy to see even further performance improvements towards rich-text CRDTs but at this point, I think the barrier to adoption isn't speed or compactness but

by matlin 3y ago

I'm happy to see even further performance improvements towards rich-text CRDTs but at this point, I think the barrier to adoption isn't speed or compactness but instead integration with existing backends and databases. I have a hunch that we're reinventing the wheel by creating new B-Tree implementations in Rust when we could be figuring out how to make an existing database do the hard work of storing and retrieving characters in the correct order. I know Martin Kleppmann has looked at Datalog being a potential solution to this problem but until we have a good full-stack solution to collaborative text editing, I don't think we'll see major adoption of these CRDT solutions.

samwillis 3y ago
I agree that full stack support is the missing pice that's need to make use explode. But I do think the current implementations will get there. CRDTs are fairly unique in that you need them to be exposed very close to the front of your stack in order to capture user intent, but you also need support further back in your stack for merging, replication, and querying. We have good front end support and there are multiple exciting projects building collaboration servers (PartyKit in particular looks awesome) for them. What I think is missing is support in database, that's what I've been experimenting with (below). If you are building an offline enabled app, having the ability to generate diffs and merge in database enables easy multi document sync. Also most general purpose CRDTs are a combination of JSON and XML like data structures, it's useful to be able to query the structures in your database. For example if you build a notes app that supports inline tags, it's useful to be able to query and index those from within the XML like structure without having to dump the whole thing out at another layer of your stack. Essentially, you need to capture user intent in the CRDT on the front end, but then have support through your whole backend. Yjs Postgres: https://github.com/samwillis/yjs-pg-test https://github.com/samwillis/yjs-pg-test Yjs SQLite: https://github.com/samwillis/yjs-sqlite-test https://github.com/samwillis/yjs-sqlite-test (These are just early experiments, I'm working on a cleaner shared implementation with support for various SQLite bindings, and better querying)
- matlin 3y ago
  Cool, I'll check out your repos. Supabase also has Postgres CRDT (https://github.com/supabase/pg_crdt https://github.com/supabase/pg_crdt). But, in general, I think searching in and across documents and database storage is going to a thorny problem even with existing, hyper-optimized CRDT algorithms. For example, if you just store your Yjs document as a binary blob in a Postgres column, Postgres becomes the bottleneck and all the fancy range-tree or b-tree optimizations are no longer that helpful on the server. Plus, it'd be great to have an document edit just be a tiny insert into the database that can be streamed to other clients rather than a big row update. This may because the focus of CRDTs seems to be rooted in a fully decentralized, P2P system but many developers want collaborative text editing in a more traditional client-server model.
  - deleted 3y ago
    [deleted]
- tantaman 3y ago
  Very cool. Left some comments related to some drawbacks I see of your current approach -- https://github.com/vlcn-io/cr-sqlite/issues/65#issuecomment-1553543630 https://github.com/vlcn-io/cr-sqlite/issues/65#issuecomment-... If you're open to resolving those I'd love to stick it into cr-sqlite :)
  - samwillis 3y ago
    Hey Matt, thanks. I will drop my thoughts into that thread tomorrow. Cr-SQLite is awesome, I found that thread a few weeks ago and actually had it on my list to get in touch.
dspillett 3y ago
> we're reinventing the wheel by creating new B-Tree implementations in Rust when we could be figuring out how to make an existing database do the hard work of storing and retrieving characters in the correct order That is liable to produce a significantly less efficient result in both computational complexity and storage requirements. The b-tree implementations used in existing databases are optimised for managing data in fixed(ish) size pages which I don't think matches the CRDT use case. Heck, there are projects looking at whether current implementations in DBs which were designed when spinning disks were the best online storage we had (or all but the very monied could afford in significant size) are sub-optimal enough in our current RAM-is-relatively-cheap and random-access-IO-is-massively-less-latent-than-it-used-to-be world that the compatibility hump might be worth making significant changes to pages sizes and other considerations in those structures for even the DB work they are designed for.
conradev 3y ago
Yeah, I would rather have Peritext inside of SQLite itself: https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite
smasher164 3y ago
Yeah, I think a good step would be to integrate a rich CRDT into sqlite, whether that's through CTEs, a custom extension, or library code that manages the tables. Layering a CRDT on top of an existing schema might not be very efficient though. You'd likely need to modify the db's internals. I have no evidence for this statement though :)

by matlin 3y ago

samwillis 3y ago

I agree that full stack support is the missing pice that's need to make use explode. But I do think the current implementations will get there. CRDTs are fairly unique in that you need them to be exposed very close to the front of your stack in order to capture user intent, but you also need support further back in your stack for merging, replication, and querying. We have good front end support and there are multiple exciting projects building collaboration servers (PartyKit in particular looks awesome) for them. What I think is missing is support in database, that's what I've been experimenting with (below). If you are building an offline enabled app, having the ability to generate diffs and merge in database enables easy multi document sync. Also most general purpose CRDTs are a combination of JSON and XML like data structures, it's useful to be able to query the structures in your database. For example if you build a notes app that supports inline tags, it's useful to be able to query and index those from within the XML like structure without having to dump the whole thing out at another layer of your stack. Essentially, you need to capture user intent in the CRDT on the front end, but then have support through your whole backend. Yjs Postgres: https://github.com/samwillis/yjs-pg-test https://github.com/samwillis/yjs-pg-test Yjs SQLite: https://github.com/samwillis/yjs-sqlite-test https://github.com/samwillis/yjs-sqlite-test (These are just early experiments, I'm working on a cleaner shared implementation with support for various SQLite bindings, and better querying)

matlin 3y ago
Cool, I'll check out your repos. Supabase also has Postgres CRDT (https://github.com/supabase/pg_crdt https://github.com/supabase/pg_crdt). But, in general, I think searching in and across documents and database storage is going to a thorny problem even with existing, hyper-optimized CRDT algorithms. For example, if you just store your Yjs document as a binary blob in a Postgres column, Postgres becomes the bottleneck and all the fancy range-tree or b-tree optimizations are no longer that helpful on the server. Plus, it'd be great to have an document edit just be a tiny insert into the database that can be streamed to other clients rather than a big row update. This may because the focus of CRDTs seems to be rooted in a fully decentralized, P2P system but many developers want collaborative text editing in a more traditional client-server model.
- deleted 3y ago
  [deleted]
tantaman 3y ago
Very cool. Left some comments related to some drawbacks I see of your current approach -- https://github.com/vlcn-io/cr-sqlite/issues/65#issuecomment-1553543630 https://github.com/vlcn-io/cr-sqlite/issues/65#issuecomment-... If you're open to resolving those I'd love to stick it into cr-sqlite :)
- samwillis 3y ago
  Hey Matt, thanks. I will drop my thoughts into that thread tomorrow. Cr-SQLite is awesome, I found that thread a few weeks ago and actually had it on my list to get in touch.

dspillett 3y ago

> we're reinventing the wheel by creating new B-Tree implementations in Rust when we could be figuring out how to make an existing database do the hard work of storing and retrieving characters in the correct order That is liable to produce a significantly less efficient result in both computational complexity and storage requirements. The b-tree implementations used in existing databases are optimised for managing data in fixed(ish) size pages which I don't think matches the CRDT use case. Heck, there are projects looking at whether current implementations in DBs which were designed when spinning disks were the best online storage we had (or all but the very monied could afford in significant size) are sub-optimal enough in our current RAM-is-relatively-cheap and random-access-IO-is-massively-less-latent-than-it-used-to-be world that the compatibility hump might be worth making significant changes to pages sizes and other considerations in those structures for even the DB work they are designed for.

conradev 3y ago

Yeah, I would rather have Peritext inside of SQLite itself: https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite

smasher164 3y ago

Yeah, I think a good step would be to integrate a rich CRDT into sqlite, whether that's through CTEs, a custom extension, or library code that manages the tables. Layering a CRDT on top of an existing schema might not be very efficient though. You'd likely need to modify the db's internals. I have no evidence for this statement though :)