Hacker News Reader

Comment by cmrdporcupine | Hacker News Reader

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?

View on HN

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-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...

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

I implemented an barebones toy SQL and Graph cypher and document storage database 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.

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/ - SQLite and Postgres syncing

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-pg-test

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.

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 that may also be a useful reference.

Have you looked at https://www.ditto.live/

Full disclosure: I work there

I have actually, but I'm only interested in open source and self-hostable solutions, so I stopped looking at it pretty quickly, sorry.

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.

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

Reply on news.ycombinator.com