Synchronisation/replication are such a common requirement I'm surprised there's not some well known checklists or patterns or best practices. e.g. merits of looking at times of changes vs keeping a log of changes, techniques to avoid and correct divergence over time, etc

I agree.

There is some basic knowledge on how to achieve the replication, but, in our case, a lot of it was improvised and we're not sure what is the best approach.

We tried to minimize the overhead (keep as little information as possible) and that was more or less the only guidance we used.

"Because the concept is simple, achieving all three of the CAP properties at the same time is not possible."

I know that Paxos is considered hard to implement correct, but is there a reason to believe that in the general case, the more strict guarantees we need the more complex the algorithm has to be?

Well, consistency and availability are the problem here. While enforcing one of the property, you lose on the other. Not sure how would you achieve those opposing properties without introducing huge amount of complexity.

In this case, replication consists of communication between 2 instances, and when one them fails you need to pick consistency or the availability.

Paxos and Raft introduce consensus using multiple instances communicating with each other to mitigate those problems. Implementing correctly communication with 2 instances is hard enough, implementing it correctly for n instances is for sure harder.

In Memgraph, we actually tried to implement Raft and we did manage to some degree, but the effort was too much, especially when you look at the results we got (protocol that didn't work for many edge cases).

Any chance you’ll have aphyr take it out for a spin with Jepsen?

We'll probably put the replication feature in the Memgraph Community soon. At that point, we'll make a PR to the Jepsen repo with all our tests included + yea, additional testing will be possible. That's always good. As they say, once you wrote a bunch of tests for your code, please leave it to the others to test it as well :D

thanks for the detailed response. Did you try to implement Raft yourself or use something like etcd for coordination? It would be great to write about this journey too in the future.

We implemented Raft as a C++ library from scratch. We can probably publish that as s standalone implementation (open-source it). The main problem was the write performance and network communication overhead, even for read queries. There are some known solutions for all that. None of the Memgraph users required Raft type of guarantees, so we decided to go with a more straightforward and faster solution. It doesn't mean we won't get back to Raft in the future if required :D

open sourcing such projects is always a good thing :)