Crsql – Multi-writer and CRDT support for SQLite | Hacker News Reader

Crsql – Multi-writer and CRDT support for SQLite

github.com

198 pointsfaizshah58 comments

> select crsql_as_crr('foo');

This would be better served as an INSERT, since it's a modifying operation. I suggest INSERT INTO crsql VALUES ('as_crr', 'foo'); (this involves creating an ephemeral table called crsql). Similarly, instead of select crsql_finalize() you should use INSERT INTO crsql VALUES ('finalize'). This is the preferred way of doing this kind of metadata operation in SQLite, see https://www.sqlite.org/fts5.html#special_insert_commands for some examples.

Does this support CRDTs other than last-write-wins registers?

I personally am working on this problem, but I am approaching it from ephemeral tables. This allows lots more flexibility at the cost of more complex syntax. For a simple last-write-wins register, you might use something like:

    CREATE VIRTUAL TABLE foo USING crdt(col LWW);
    INSERT INTO foo VALUES (1);
    UPDATE foo SET col = crdt_set(2);
    SELECT col, crdt_lww_timestamp(col_meta) FROM foo;

This weird update syntax allows you to use non-standard operations, though, which then allows you to implement things like ordered sequences (text) in a conflict-free manner (e.g. SET col = crdt_text_insert(col, 5, ', world')).

In your example, why does the INSERT in second row use the unqualified value (1), but the UPDATE in third row uses a wrapped value as crdt_set(2)?

Technically it isn't necessary to use the wrapped value when the wrapper function only takes a single parameter (because the virtual table could easily do the wrapping in this case). In the case of an insert, all wrappers only ever take a single parameter so it can be elided, but for updates some wrappers may require multiple parameters, so I opted for consistency and force all updates to use the wrapper methods, even when it only takes a single parameters.

Project author here (although not OP)

I like the idea of moving the syntax to inserts and had not seen https://www.sqlite.org/fts5.html#special_insert_commands

Will give it a shot & thanks for the resources.

> I personally am working on this problem, but I am approaching it from ephemeral tables.

Would love to trade ideas if you're open to it. @tantaman on twitter.

> Does this support CRDTs other than last-write-wins registers?

Not yet. I was thinking of collaborating with Seph to bring DiamondTypes in for sequence crdt support. If that is even possible -- just an idea at the moment.

You can use views with INSTEAD OF triggers to handle INSERTs.

OP here, sorry if you didn’t want this posted yet. I had never seen such a simple way to implement realtime collaboration so I thought I would share it.

np. Gives me a good reason to finish up those usage docs and example apps :)

I guess maybe i should read the linked papers, but i kind of dont get it. How do inherently conflicting updates get resolved? What happens when one writer sers bankBalance = 200 and the other sets bankBalance = 500; ? Or does just significantly limit the type of applications you can have?

I don't believe it is possible to arrive at any generic solution that resolves the kind of conflict that you are describing. The best they can do is keep the latest value at row+column level.

Notwithstanding, there are a lot of possible changes that can compose well, but with traditional databases it is hard to merge divergent datasets even if the changes are non-overlapping. That is where solutions like this improve the state of the art - by obviating a need for secondary sync/merge layer on top.

For the actual cell level conflicts the application developer will have to either write custom resolution or model the domain so that they can be resolved by user later.

Sure, but i would kind of expect the readme document to explain what happens (what is the consistency model) since this is not an obscure case but basically the primary use case for an ACID database like sqlite.

https://github.com/vlcn-io/cr-sqlite/tree/ca9a67f9050844458e...

It's not very clearly stated, but the links show it has "Last Write Wins" semantics for conflicting changes

https://bartoszsypytkowski.com/crdt-map/#crdtmapwithlastwrit... https://bartoszsypytkowski.com/operation-based-crdts-registe...

https://github.com/rqlite/rqlite might have the answer, it uses the Raft consensus protocol to solve time based conflicting issues like that.

rqlite author here, happy to answer any questions.

How hard would it be to release APE versions of the amd64 binaries of rqlite?

https://justine.lol/ape.html

No idea.

If a patch was provided, would you consider distributing the binaries on the github page?

(I can have a look, I'm just not very familiar with go intricacies)

Sure, would be happy to consider.

That isn't how CRDT's work though. In the example of mutating a bank balance, there would be addition operations and subtraction operations. So /eventually/ all nodes would arrive at the same balance. It's a bit like event sourcing but lower-level.

Depends on the type of CRDT. You can have a CRDT which supports setting a register (or column value in a row) to a particular value. This is what Crsql appears to do as one sibling comment indicated. There are a number of ways to resolve conflicting updates, but Crsql chooses LWW (last writer wins).

Right, but its how SQL works. So did this project get rid of SQL? What does it mean in context to join SQL and CRDTs together?

You don't update the account.ballance, you insert a new transaction for that account with the amount required. At eod, you calculate and update the correct balance.

That isn't necessarily "how SQL works". Sure, you might design your schema like that. But many accounting systems don't necessarily store a "balance" except perhaps as a performance optimisation. They derive the balance from the history of transactions that have occurred on an account. And a transaction is, essentially, a + or - value.

Indeed it can be argued that CRDTs are a natural fit for SQL because it is essentially a derivative of set theory

If you are essentially going to just have inserts that are not dependent on any reads, why are you bothering with fancy algorithms like CDRT? That is the trivial case.

I think the question is whether this particular CRDT has any notion of transactions to make sure the database is left in a consistent state after a merge.

As I understand it, the only guarantee we get from all CRDTs is that all copies end up in the same state irrespective of merge order. And then there are some trivial examples, like counters, where this state is also logically consistent. But that is not guaranteed in general.

So what about the classical example of transferring an amount from account A to account B if account A has sufficient funds?

I think for a CRDT to support such cases (for arbitrary schemas) it would have to have some notion of atomicity and some way to specify preconditions.

It's complicated, but you can grok it: https://en.m.wikipedia.org/wiki/Conflict-free_replicated_dat...

The part i dont understand is as far as i understand, CRDT requires data types with commutative update functions, but SQL does not have that. The part i dont understand is how these two technologies that seem to have conflicting requirements are being joined.

Columns are LWW (last writer wins) registers within rows which are LWW maps. When concurrent writes occur because peers may not be communicating, there is typically an arbitrary but convergent selection based on peer id.

There's different strategies for solving conflicts but CRDTs wouldn't be a good fit where you need a total ordering of all transactions -- such as bank deposits.

You can handle bank deposits with a counter CRDT.

https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

Ideas in CRSQL are remarkably similar to Marmot (https://github.com/maxpert/marmot) except that it doesn't require an extension to be installed, and it can run as sidecar. I can see how having extension makes it simple to intercept writes, and transactions. Since marmot builds on top of NATS, and JetStreams work using Raft, it can easily scale and keep the libsqlite on disk guarantees intact.

Marmot looks interesting, but I am curious how it deals with conflicts. What happens if two writes for the same field happen on two different dbs, and they are conflicting?

Since each write is logged into a JetStream. The last writer will win for conflicting changes.

But since you don't have NATS message ordering (from different sources), it's possible that different DBs in the cluster will end up out of sync, right?

So per-node there is an order of changes (read internals doc), and all of changes are sent to JS in that commit order. These changes when replayed will always eventually result in same values.

I am talking about writes that come from 2 different nodes. If 2 different nodes, each making a different write at the exact same time, you would need some global ordering or consensus in order to order them. Otherwise you might end up in a different state on different nodes.

I'd originally done a sidecar route but ultimately went the extension route for portability.

It’s an interesting choice for sure because I heard a lot of ifs and buts for loads of eventually consistent scenarios on why people wanted to not make any changes to their code and don’t really wanna load extensions. Loading extensions is definitely better in terms of transaction control. I did a lot of soul-searching before settling for sidecar approach. In order to not be an interface and stay away from binding complications for various platforms I opted for sidecar. Once done I was already able to scale out of box stuff like PocketBase.

One of the best things about SQLite is its license (or maybe I should say lack thereof).

While SQLite extension authors are free to choose whatever license they wish, I wish more would follow the core’s example.

(I realise there are legal doubts about the validity of “public domain” in some jurisdictions - I think ultra-permissive licenses such as 0BSD are effectively equivalent to public domain. Apache is a lot more restrictive than 0BSD.)

If only we had a license to make them do that (jk).

I do actually like the sqlite blessing. It is really wholesome.

A couple of questions:

1) Does the CRDT require synchronized clocks? I always felt that was the weakness of stuff like Google's Spanner (and its main competitor, can't remember the name). There just has to be some other way to derive ordering, maybe using pseudorandom sequences generated from the same seed or using time deltas from the last update or something? Although those might be spoofable/cheatable.

2) Is there any workaround for the lack of foreign key constraints? Those are critical to what makes query builders like Laravel's Eloquent relations easy to reason about (especially for deletions and other cascade operations). For example, maybe a dirty flag on the row could get cleared once eventual consistency was reached and all FK constraints were met? I think the other limitation with uniqueness on only 1 primary key could be addressed through composite keys or a hash of other keys somehow, so is not a dealbreaker.

> Does the CRDT require synchronized clocks?

No. CRDT are Commutative. You can apply a set of updates in any order and achieve the same result. This is a core feature.

"Provably, replicas of any CRDT converge to a common state that is equivalent to some correct sequential execution. As a CRDT requires no synchronisation, an update executes immediately, unaffected by network latency, faults, or disconnection"

https://hal.inria.fr/inria-00555588/

see https://crdt.tech/

Just in case someone stumbles upon this, here is a great explanation of how CRDTs work that was on HN a few days ago:

https://news.ycombinator.com/item?id=33694568

The secret sauce is the use of a Lamport timestamp (instead of a clock) as a logical time counter, which is a sequence number or local count of the number of writes. The sequence number gets sent by each peer for each write. Most of the time, the CRDT can derive which event happened first by comparing sequence numbers from each peer.

In pathological cases, like two users making a slightly different edit to the same item with the same last-known state on two different devices while they're in a tunnel disconnected from wireless internet, a tie-breaking rule determines which edit wins. That could be as simple as favoring the peer id which comes first alphanumerically.

In practice, peers write to the CRDT and then receive a series of update events that may oscillate or contradict the peer's notion of what happened, until eventual consistency is reached. So in a video game, both players might shoot and think they killed one another until the CRDT determines that one player shot first. As long as the game is stateless and can reflect the last known state received from the CRDT, then it will eventually come to correctly show that one player won. But it might have some undesired animation in the meantime showing the wrong player winning.

Also I suspect that a real game would have a more advanced tie-breaking heuristic that does include some notion of local time. For example, if the max ping is capped at 5 seconds or something, then the CRDT could use dead reckoning to place constraints on when each write could have happened. But it would only be used in rare cases when ordering can't be derived deterministically. It could also use a majority vote from each peer like with Raft/Paxos (I think), but that might stray into something too complex to implement or too vulnerable to cheating.

I am interested in how this works.

I started writing a postgres synchronizer.

I got as far as hashing the data In the database but I need to write a synchronization endpoint that does similar to a rolling hash to determine what data to send to other clients.

One problem I encountered is detecting the winning write.

There are a lot of features being developed for SQLite now. Are they mostly standalone external "patches/extensions" or being rolled into the official release?

I am hoping it does not get into the official releases. At least not for a couple of years.

SQLite is open source but closed for contributions, the main author doesnt really take public contributions. I doubt any of these extensions make it into the main codebase.

Sqlite is probably the best counter example to the whole cathedral and the bazaar thing.

There's libsql, a fork of SQLite, that intends to be an "open contribution" version of SQLite.

How active is that?

This is phenomenal! I'm going to try experimenting with this. Hats off to the author.

I was trying to re-implement a JSON CRDT on top of SQLite for my notes app, but this just made the whole database a CRDT!

It looks like it doesn't have sequence support? Dang -- I'll wait a while then.

yeah, not yet. yjs and automerge have rust ports so _maybe_ (big maybe) sequence crdts can be added by creating a virtual table interface to those projects. TBD.

That would be cool. One I issue I could see coming up is that automerge and yjs keep everything in memory (the reason why a DB CRDT is preferable in the first place), so I'm wondering how you'd make use of their APIs without doing a bunch of (de)serialization.

I know that DiamondTypes does write to disk and acts much like a db itself. I was thinking it could be possible to expose that library as a virtual table in SQLite.

lmk if you need any help getting things set up.

Would this ever be applicable to Postgres as well? Looks really neat

This mainly only applies in scenarios where there are multiple databases that accept writes for a particular object. This is common in client-side databases (ex: sqlite) since each client has its own copy of an object.

This would only apply to Postgres, if there is multi-master replication, and the writes for a particular object can go to multiple master databases. Multi-master replication means that there are multiple backend databases that can accept writes.

Typically you avoid this scenario by partitioning writes for an object to 1 master database. This way each master database is responsible for its own disjoint set of object and so there is no chance of conflicts.

Another way to avoid the issue is to just avoid multi-master replication, and stick to only having 1 master database to accept writes.

Replication for sqlite

That's an oversimplification

Reply on news.ycombinator.com