Faster CRDTs: An Adventure in Optimization
&gt; If you want database semantics instead of document semantics, as far as I know nobody has done this well on top of CRDTs yet.<p>This is very interesting to me.  CRDTs for databases sounds fantastic.  Databases have much much richer data types and transactional semantics than collaborative text editing, and this makes applying CRDTs to databases harder.<p>Let&#x27;s start with the basics.  CRDTs are all about designing or picking monoids that fit the problem and allow one to get a very good approximation of the semantics one is after, if not even exactly.<p>What does that mean for databases?  Well, for one, every data type in a database will have to have a monoid associated with it -- this is... limiting, but limiting is good if the benefit is that we don&#x27;t need any more complex mechanisms to get convergence in a distributed database.  For example, we can have a table of &quot;likes&quot; where they can only increase additively, so we&#x27;ll make that BIGINT with the ADDITIVE monoid or whatever.  But `BIGINT with the ADDITIVE monoid` is the easy stuff.  The hard part is PRIMARY and UNIQUE KEYs.<p>So what about unique keys?  Well, we can have monoids for those too.  Like tiebreakers based on timestamps.  Especially since we have delineated transactions (BEGIN; ..; COMMIT;) we know that if some INSERT fails eventually then the whole transaction containing it fails (unless that INSERT is of the OR IGNORE &#x2F; ON CONFLICT DO NOTHING variety).<p>The real problem with CRDT and databases is that CRDT is incompatible with SQL transactional semantics.  Similarly for CRDT and filesystems and POSIX semantics.  You can&#x27;t tell if some transaction will commit successfully until you&#x27;ve heard from all collaborators enough to know that it must have.  Instead you can consider every local transaction that succeeds locally as committed, but then later every possible conflict has to be resolvable in some way.  This gets tricky real fast.  It might be easier to start with &quot;trivial&quot; transactions like POSIX file rename(2).  If two applications decide to rename the same file to different names, and both observe success, and eventually only one of those renames succeeds, then it has to appear to the loser that the winner came along and renamed the file after the loser did.  This sequence of events:<p><pre><code>  loser                        winner
  -----                        ------
  rename(&quot;&#x2F;a&#x2F;b&quot;, &quot;&#x2F;a&#x2F;c&quot;) = 0
                               rename(&quot;&#x2F;a&#x2F;b&quot;, &quot;&#x2F;a&#x2F;d&quot;) = 0
</code></pre>
would have to look to the loser like:<p><pre><code>  loser                        winner
  -----                        ------
  rename(&quot;&#x2F;a&#x2F;b&quot;, &quot;&#x2F;a&#x2F;c&quot;) = 0
                               rename(&quot;&#x2F;a&#x2F;c&quot;, &quot;&#x2F;a&#x2F;d&quot;) = 0
                                          ^
                                          |
                                          &#x2F;
                   note the difference --+
</code></pre>
But, of course, POSIX has something to say about this, and that is &quot;nope!&quot;.  POSIX says &quot;no&quot; because if the loser and the winner share notes they&#x27;ll find that what appears to the loser to have happened is not at all what happened.  There are very specific rules about observability of writes, and order of events, that POSIX has that a CRDT distributed filesystem simply must break.  The loser&#x27;s successful rename(2) call should have been visible to the winner, so the winner should have lost the race to rename that file.  Still, it&#x27;s a pretty good compromise for the benefits of CRDT.<p>Similarly for O_CREAT | O_EXCL: the loser can imagine that the winner unlinked the file created by the loser then created a replacement.  Again, we&#x27;ve left the land of POSIX at that point, but again, it can be a pretty good compromise for <i>some applications</i>.<p>SQL transactions are infinitely more complex than POSIX ones, but I think the analysis of the POSIX case generalizes to SQL ACID transactional semantics: you can&#x27;t quite have that with CRDT.  You might find more of some successful-looking-to-you transaction undone or changed later by a collaborator&#x27;s in ways that, if you were to look at the actual events, you&#x27;d be annoyed violate ACID.  And again, for some applications this probably just won&#x27;t work.  Though, too, we might come up with monoids that help us reach acceptable semantics.<p>For example, in Active Directory each domain controller gets its own pool of RIDs (relative identifiers) for assignment to new users and groups and machine accounts, so there can be no conflicts about those, but there is no sub-namespacing of the <i>names</i> of those things, so the rule AD uses is that the loser&#x27;s user&#x2F;group&#x2F;namespace gets renamed to something like &quot;copy_of_{original_name}&quot;.  Also, AD requires a strong primary role for the DC that hands out RID ranges for allocation, which again means we&#x27;re leaving the land of CRDT for some things.  So in AD one might find a user&#x2F;group&#x2F;machine unexpectedly renamed like that (but it rarely ever happens).<p>But if the application was using atomic transactions to decide whether to have destructive external side-effects, such as &quot;sell!!!&quot;, &quot;launch missiles&quot;, etc., then this kind of shifting sands transactional semantics may be... unsatisfying.<p>CRDT resembles eventual correctness in a way.  It&#x27;s not that local state is ever incorrect, but that a sequence of events is impossible in a system with traditional ACID transactional semantics.<p>All this said, just note that I&#x27;ve done zero work in this area, just lots of thinking.  I&#x27;ve this idea that one could use PG logical replication publications and subscriptions, and monoid choices encoded in COMMENTs, and suitable functions, to implement a CRDT scheme on top of PG to explore this space.  Basically, each collaborating server publishes its view of a log of local transactions and subscribes to all the others&#x27; (in separate schemas), then periodically it applies the others&#x27; logs to the local source of truth.  For simple applications that might even suffice instead of a database that natively supports CRDT.  I <i>have</i> done work on encoding useful schema metadata in COMMENTs using JSON, so I&#x27;m pretty confident that this is something worth exploring.<p>One thing that is clear is that some of this space has been explored already.  For example, again, AD has done so for PRIMARY&#x2F;UNIQUE KEYs!  Indeed, AD even implements a hybrid approach to multi-mastering a distributed database, with an &quot;infrastructure master&quot; for some things, and CRDT for others.  AD&#x27;s metaschema is LDAP&#x27;s, with some enhancements (especially an ObjectDN syntax for &quot;relations&quot; or &quot;pointers&quot;) that make it a lot more like a relational database.  And AD is a general purpose database that achieves these things.  So it&#x27;s not like this space is completely new -- there are a few giants&#x27; shoulders to stand on.