41 ms·

Has anybody done any work or research integrating CRDT-ish text conflict resolution with a database transaction process? E.g. in MVCC when detection of version

Has anybody done any work or research integrating CRDT-ish text conflict resolution with a database transaction process? E.g. in MVCC when detection of version conflict (e.g. via timestamps) happens, the approach is generally to abort and retry; but if the conflict in the tuple/row is at textual level and can be resolved by this kind of algorithm, it seems this could handle some conflict resolution without full retry or abort?

samwillis 3y ago
Not quite the answer to your question, but there are quite a few people looking at doing eventually consistent database syncing with CRDTs. Two interesting ones are: https://electric-sql.com/ https://electric-sql.com/ - SQLite and Postgres syncing https://vlcn.io/ https://vlcn.io/ - SQLite syncing I've been experimenting with Yjs and merging documents in database via SQL, for both SQLite and Postgres. And allowing you to query the contents of those documents, similar to how you can query JSON. Early days, these are just tests: https://github.com/samwillis/yjs-sqlite-test https://github.com/samwillis/yjs-sqlite-test https://github.com/samwillis/yjs-pg-test https://github.com/samwillis/yjs-pg-test
- cmrdporcupine 3y ago
  Yeah I'm more interested in having this as part of the core DB tx commit logic, rather than as an ad-on or sync piece.
- agg23 3y ago
  I hadn't heard of Electric-SQL before. Was potentially interested, but the lack of native language bindings is a dealbreaker. I don't particularly like a centralized server being required for the sync either, but it's ok. VLCN is very interesting to me, and I really need to play around with it. It's not incredibly obvious to me how these extensions to SQLite play out in actual use.
  - stusmall 3y ago
    Have you looked at https://www.ditto.live/ https://www.ditto.live/ Full disclosure: I work there
    - agg23 3y ago
      I have actually, but I'm only interested in open source and self-hostable solutions, so I stopped looking at it pretty quickly, sorry.
  - thruflo 3y ago
    We (ElectricSQL) have some work underway on a Rust/WASM port of our core client component, that’s designed to open up more language support. This is a community contributed Dart/Flutter client https://github.com/SkillDevs/electric_dart https://github.com/SkillDevs/electric_dart that may also be a useful reference.
samsquire 3y ago
I am working toward that goal of integrating text diffing or CRDT diffing into a database. I wanted extremely high performance multimaster scalability of writes with linear scalability and semiautomatic text diffing and merging. I think this calls for an eventually consistent architecture. The idea is to implement the GUI so that diffs are exposed to the user if there is a conflict but otherwise use the Myers algorithm. I implemented a simple MVCC in Java. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro... And I implemented a 3 way text diff with myers algorithm based on https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm... https://github.com/samsquire/text-diff https://github.com/samsquire/text-diff I implemented an eventually consistent mesh protocol that uses timestamps to provide last write wins https://github.com/samsquire/eventually-consistent-mesh https://github.com/samsquire/eventually-consistent-mesh I implemented an barebones toy SQL and Graph cypher and document storage database https://github.com/samsquire/hash-db https://github.com/samsquire/hash-db I need to combine the ideas in each of these projects into a cohesive solution. I did some incomplete work on trying to implement the YATA algorithm.
toomim 3y ago
Yes, Matt Tantaman wrote a SQLite extension that gives it CRDT semantics! It's a CRDT-Sqlite or ... CR-Sqlite. Ha. https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite

samwillis 3y ago

Not quite the answer to your question, but there are quite a few people looking at doing eventually consistent database syncing with CRDTs. Two interesting ones are: https://electric-sql.com/ https://electric-sql.com/ - SQLite and Postgres syncing https://vlcn.io/ https://vlcn.io/ - SQLite syncing I've been experimenting with Yjs and merging documents in database via SQL, for both SQLite and Postgres. And allowing you to query the contents of those documents, similar to how you can query JSON. Early days, these are just tests: https://github.com/samwillis/yjs-sqlite-test https://github.com/samwillis/yjs-sqlite-test https://github.com/samwillis/yjs-pg-test https://github.com/samwillis/yjs-pg-test

cmrdporcupine 3y ago
Yeah I'm more interested in having this as part of the core DB tx commit logic, rather than as an ad-on or sync piece.
agg23 3y ago
I hadn't heard of Electric-SQL before. Was potentially interested, but the lack of native language bindings is a dealbreaker. I don't particularly like a centralized server being required for the sync either, but it's ok. VLCN is very interesting to me, and I really need to play around with it. It's not incredibly obvious to me how these extensions to SQLite play out in actual use.
- stusmall 3y ago
  Have you looked at https://www.ditto.live/ https://www.ditto.live/ Full disclosure: I work there
  - agg23 3y ago
    I have actually, but I'm only interested in open source and self-hostable solutions, so I stopped looking at it pretty quickly, sorry.
- thruflo 3y ago
  We (ElectricSQL) have some work underway on a Rust/WASM port of our core client component, that’s designed to open up more language support. This is a community contributed Dart/Flutter client https://github.com/SkillDevs/electric_dart https://github.com/SkillDevs/electric_dart that may also be a useful reference.

samsquire 3y ago

I am working toward that goal of integrating text diffing or CRDT diffing into a database. I wanted extremely high performance multimaster scalability of writes with linear scalability and semiautomatic text diffing and merging. I think this calls for an eventually consistent architecture. The idea is to implement the GUI so that diffs are exposed to the user if there is a conflict but otherwise use the Myers algorithm. I implemented a simple MVCC in Java. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro... And I implemented a 3 way text diff with myers algorithm based on https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm... https://github.com/samsquire/text-diff https://github.com/samsquire/text-diff I implemented an eventually consistent mesh protocol that uses timestamps to provide last write wins https://github.com/samsquire/eventually-consistent-mesh https://github.com/samsquire/eventually-consistent-mesh I implemented an barebones toy SQL and Graph cypher and document storage database https://github.com/samsquire/hash-db https://github.com/samsquire/hash-db I need to combine the ideas in each of these projects into a cohesive solution. I did some incomplete work on trying to implement the YATA algorithm.

toomim 3y ago

Yes, Matt Tantaman wrote a SQLite extension that gives it CRDT semantics! It's a CRDT-Sqlite or ... CR-Sqlite. Ha. https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite