Show HN: Pg_CRDT – an experimental CRDT extension for Postgres

by kiwicopple • 4 years ago

296 38 4 years ago

This is an experimental extension for CRDTs, pg_crdt: GitHub repo[0]. It supports Yjs/Yrs and Automerge.

The linked blog post [1] describes how we're thinking about this extension in a Supabase context. I want to emphasise this part: "pg_crdt has not been released onto the Supabase platform (and it may never be). We’re considering many options for offline-sync/support and, while CRDTs will undoubtedly factor in, we’re not sure if this is the right approach."

[0] GitHub repo: https://github.com/supabase/pg_crdt

[1] Blog post: https://supabase.com/blog/postgres-crdt

kiwicopple9• 4 years ago

For quick viewing, here's how it works in Postgres (using Yjs):

    create table posts (
      id serial primary key,
      content crdt.ydoc default crdt.new_ydoc()
    );
  
    insert into posts (content)
    values (crdt.new_ydoc());

    update posts 
    set content = content || crdt.new_ydoc()
    where id = 1;

The heavy-lifting is done by the teams at Yjs[0] and Automerge[1], who have re-implemented their JS libs in Rust. This made it possible for us to wrap them into a Postgres extension using pgx[2] (which is fast becoming a de-facto tool at supabase)

[0] Yjs: https://github.com/yjs/yjs

[1] Automerge: https://github.com/automerge/automerge

[3] pgx: https://github.com/tcdi/pgx

samwillis2• 4 years ago

Super excited to see this Paul, and amused to see the nod to my comment in the post :-)

I'm going to enjoy getting stuck into this! (When I'm not stuck driving for six hours... just a quick coffee break reading this)

Support for CRDT columns within a db to enable JSON like indexing/querying capabilities is fundamental to then building some exciting further developments. Supporting both Yjs and Automerge is exactly the right route forward.

samwillis2• 4 years ago

Had a chance to take a little more of a look, did you investigate querying/indexing within the documents? (Didn't spot any sign in the repository)

Without the ability to index properties, or do ad-hock queries, on the documents there is little reason to to the merging in-DB. It then makes more sense to merge outside the DB and save both the raw CRDT object and a serialised JSON next to it for querying. I assume that if you had found it's performance better, indexing+querying would have been the next step?

However I'm not surprised you found performance not ideal, I suspect a layer in-front of PG throttling writes is the only way forward for a real-time use case.

Personally I find the offline + eventual consistency the most interesting use case. The ability to sync a users document set to a local db (SQLite or a future mini-pg/supabase) with local querying and then merge them back later. This could be as basic as a three column table (guid, doc, clock), the clock being a global Lamport like clock to enable syncing only changed documents.

Horusiath• 4 years ago

Yrs (Yjs on Rust) maintainer here: we actually had some idea about building extension to Postgres ;) Great to see that others share the excitement about this idea as well. See: https://github.com/y-crdt/y-crdt/issues/220

kiwicopple9• 4 years ago

perfect, we'd love to collaborate with you. I'll jump into your github after our Launch Week (this week), or feel free to reach out directly (contact details in my bio)

cyanydeez• 4 years ago

I really hope plv8 maintainers can finally ditch v8 And pave the way for using yjs in all tits glory.

Unfortunately, v8 basically is a bloated mess and postgres just stopped supporting it cause it's build process is horrendous.

zombodb• 4 years ago

Always nice to see pgx being used in the wild! Awesome work.

Smaug123• 4 years ago

Forgive me, I'm still recovering from the flu and am having some trouble thinking, but I didn't find your "Why not build this into Realtime?" section very compelling. If you've already got a central source of truth (so you don't currently need the peer-to-peer nature of CRDTs), isn't it faster to iterate on your solution if you implement the merge semantics within the central source of truth that you have full control over? I'm not convinced from your post that turning the database into a component of a peer-to-peer distributed system is predictably worthwhile; it's certainly predictably going to be very complex. It smacks to me of spending a great deal of engineering effort to keep your options much further open than I've seen you justify.

kiwicopple9• 4 years ago

Thanks, perhaps I can try explaining it from another angle.

At the moment, every tool in supabase is decoupled from the other tools. The only thing that each tool depends on is Postgres. This is beneficial, because now we don't need to build interfaces - Postgres is the interface.

Putting this implementation into Realtime would introduce a second dependency for some tools or create a burden for the developer. For example, this query goes directly to PostgREST:

    supabase.from('posts').update({ title: 'Hello', content: 'World' });

If the "content" part of this is a CRDT, then suddenly the developer needs to know that that particular field needs to be sent through realtime (psuedo-code):

    supabase.from('posts').update({ title: 'Hello' });
    supabase.from('posts').merge({ content: 'World' });

Or we'd need to build some automatic-routing logic into the libraries (or PostgREST), which is also complex.

In my view, CRDTs are a data problem, and therefore probably a database problem. If we can make Postgres act like "just another peer", then it simplifies the architecture.

isn't it faster to iterate on your solution if you implement the merge semantics within the central source of truth that you have full control over?

We have full control over both Realtime and Postgres (at least the extension), so this is less of a concern. We're also less worried about fastest iteration than finding the correct solution long-term

danbruc5• 4 years ago

I do not get peoples' obsession with CRDTs. They are useful in a limited set of use cases when your operations are commutative but having only commutative operations is pretty rare except for some almost exotic use cases. Distributed document editing is for some reason a reoccurring theme but document editing operations are all but commutative. What people then build with all kinds of ad hoc conflict resolution strategies is barely worth being called a CRDT - nothing there is conflict-free, you are just defining conflicts away. Sometimes that works okay, at least for a limited uses case, but the resulting operations are rarely general, and sometimes they are just weird.

kiwicopple9• 4 years ago

I touch on this in the blog post:

    I personally believe CRDTs are the future. *For some things.*

    It’s possible that developers will need to be selective about their “level” of offline support 
 
    [example table for a blog post]   
 
    Perhaps it’s not that important if the title has a “last write wins” strategy, because it’s rarely updated and less likely to have a merge conflict. But it is critical to use a smarter algorithm for the content of the blog post, especially in a team where multiple users are editing a blog post at the same time.

danbruc5• 4 years ago

The C in CRDT is for conflict-free, i.e. there must not be any conflicts between operations. Incrementing and decrementing a counter, the final result will be the same independent of the order of operations. You can almost not get any further away from a CRDT than last write wins. And for more complicated merge strategies you are essentially guessing what the desired result is but you do not know and everything really depends on the quality of your guesses.

Like the example with the changed fruits in the list, maybe one or the other should end up in the final result, maybe both, maybe none. The correct conflict resolution strategy is not obvious and highly dependent on the use case, that is why I said that implementations are usually not general or they are only general in the sense that you can plug in any behavior you like. Compare this with a real CRDT like a counter, there there is absolutely no doubt about the desired outcome.

preseinger3• 4 years ago

CRDTs ... are useful in a limited set of use cases when your operations are commutative

As you correctly observe, very few applications that exist today have data models with operations that satisfy the requirements of CRDTs, including e.g. commutativity. But CRDTs were never meant to be a "swappable" state layer for existing applications. The idea has always been that applications would need to change how they interact with state, to a model which does satisfy those requirements. Such models can absolutely generalize, it just takes a bit of thinking.

Existenceblinks• 4 years ago

About to say the same, solving application level conflict for well-defined data structure could also skip the CRDT which is sort of protocol level altogether. Plus, real-time collaboration is just for poor work process. It's very rare any app would want synchronous operations on data from different actors at the same time without work process. Even brainstorming isn't a good fit for this type of communication.

nixpulvis• 4 years ago

I for one respect the need to resolve merge conflicts.

matlin• 4 years ago

Last Writer Wins is not the most compelling use case for CRDT because if those fruits were denormalized into Postgres rows, you'd already have the behavior described. A more interesting example, might be if both users were inserting a new fruit, one at the beginning and one at the end. What should the sequence of fruits be after that? Likely a list with both new fruits included. But it depends on the domain and use case.

In general, Sequence CRDTs seem to be the most difficult and most interesting area of continuous research. In my own work, I've implemented a sequence CRDT to create a distributed log of events across users that then (because the order is guaranteed to eventually be the same for each device) can just be reduced to whatever data structure you need. It means, we end up with one CRDT to rule them all and then can just write the "conflict resolution" in simple term with the business logic.

jamil73• 4 years ago

Last Writer Wins is not the most compelling use case for CRDT because if those fruits were denormalized into Postgres rows, you'd already have the behavior described.

I'm not sure from the article, but I'm guessing the difference here is that it will apply the updates in the correct order (using last writer wins) regardless of when the yjs doc hits the server. I guess the idea here is you can get decent offline-ish support without directly storing timestamps, version numbers, soft-deletes etc and associated logic.

Hixon102• 4 years ago

Hm, I am a bit worried about using PostgreSQL with CRDT (Limitations section from the blog). I guess that PostgreSQL doesn't like frequently updates, because of MVCC. Maybe it is OK to use PG as a cold storage, if you have another application, which would work with hot data (like, when users change something), and eventually store it inside PG.

kiwicopple9• 4 years ago

unless we can figure out how to overcome those limitations, you're right. Potentially some sort of throttling system for CRDT updates (offloaded to a background worker so that it's non-blocking?). If anyone else has ideas/approaches which could work in a PG-only context, we'd love to hear them

Hixon102• 4 years ago

Maybe you can research a bit pluggable table storage interface in PostgreSQL. It is possible either to implement your storage, which works fine with CRDT, or try to find some storage implementation, which works fine with such usage pattern (like, https://wiki.postgresql.org/wiki/Zheap )

cranium• 4 years ago

CRDTs are really cool if your merging function behaves intuitively in the context of your application. You can easily implement a distributed VCS by using the Last Writer Wins, but it would be a nightmare to work with – imagine having your modifications rolled back because someone committed after you.

In the same way some operations are embarrassingly parallelizable (think adding elements to a set), some operations are inherently conflicting: editing elements of the same text, image, directory,... More than trying to decide in all cases which modification wins, we should detect when there are multiple legitimate options and ask the user to choose. Like a merge conflict in Git for example.

The application state feels so clean when conflicts can't arise or are automatically dealt with. But we have to acknowledge there are only so much datastructures that can merge automatically and still be intuitive for the user.

preseinger3• 4 years ago

+1, I think the most valuable lesson we've learned w.r.t. CRDTs at the moment is that valid merge operations basically don't generalize, and basically have to leverage properties that are application-specific. This isn't a fatal flaw, it just constrains the design space.

moralestapia2• 4 years ago

Hi @kiwicopple, hope you can still read this.

This is very nice and comes handy to me as I've been working for months on a couple projects using Yjs for which I adapted a Postgres persistence layer.

My only issue with this right now is that the code doesn't seem to have a license so please add (an open source ;)) one so I know I can deploy it with no worries :)

kiwicopple9• 4 years ago

Sorry about that - it will be PostgreSQL licenced (as long as the rest of the crates allow it). I’ll fix it today.

Can you explain more about your persistence layer and how it works?

moralestapia2• 4 years ago

Sure thing!

In all honestly, to say it was a "persistence layer" is a bit of a stretch since it was not an additional layer per se, but here's what we did.

Context: I was the CTO for a sort-of text editor SaaS that allowed auditors to write reports collaboratively, these guys usually work together in teams that visit companies for a couple days/weeks, so our solution made everything much easier for them.

Anyway we tried many different CRDT(-like) solutions (automerge, etc...) and we eventually settled for yjs. All clients were coordinated and synced through a centralized server, with websockets providing the transport; we didn't make use of y-websocket though, we rolled our own thing since we needed a lot of custom functionality (see ahead).

Now on to persistence, we were already using Postgres in our backend so we wanted to store this data in there as well. Every "document" was internally a CRDT structure to which all collaborators connected to. Our solution was to create an extra yjs client for each of these documents (i.e. another hidden collaborator), whose role was to listen to all changes from the CRDT and storing them to the db, and viceversa, akin to what a data historian does, running inside our custom websocket server.

So, each time a new document had to be instanced, we first enabled the historian and recovered the relevant CRDT log before sending it to the user, and when all connections were closed this historian made sure everything was committed and deallocated itself to free server resources.

It was a bit complex but it worked quite well in production. It also had some sort of a nice composability element in the sense that we could just "add" an historian client to any existing pool of yjs peers and enable persistence for them transparently. These historians were easy to adapt/extend themselves so, for instance, we could make them use MySQL instead or any other db stack; then again, just by making them join an existing pool of peers, that smallish network gained a particular function. It was an interesting paradigm. I hope my explanation made sense.

Unfortunately that startup went kaput so I'm back at consulting, but some clients request this sort of functionality from time to time so I'll give this (pg_crdt) a try and add it to my stack of tools. Btw, Supabase is great, I've been following you for a couple years, you're really building a great product. Congrats!

Show HN: Pg_CRDT – an experimental CRDT extension for Postgres

Related Stories