Fossil and the CAP Theorem

The CAP theorem is a fundamental mathematical proof about distributed systems. A software system can no more get around it than a physical system can get past c, the speed of light constant.

Fossil is a distributed system, so it can be useful to think about it in terms of the CAP theorem. We won’t discuss the theorem itself or how you reason using its results here. For that, we recommend this article.

Fossil Is an AP-Mode System

As with all common DVCSes, Fossil is an AP-mode system, meaning that your local clone isn’t necessarily consistent with all other clones (C), but the system is always available for use (A) and partition-tolerant (P). This is what allows you to turn off Fossil’s autosync mode, go off-network, and continue working with Fossil, even though only a single node (your local repo clone) is accessible at the time.

You may consider that going back online restores “C”, because upon sync, you’re now consistent with the repo you cloned from. But, if another user has gone offline in the meantime, and they’ve made commits to their disconnected repo, you aren’t consistent with them. Besides which, if another user commits to the central repo, that doesn’t push the change down to you automatically: even if all users of a Fossil system are online at the same instant, and they’re all using autosync, Fossil doesn’t guarantee consistency across the network.

There’s no getting around the CAP theorem!

CA-Mode Fossil

What would it mean to redesign Fossil to be CA-mode?

It means we get a system that is always consistent (C) and available (A) as long as there are no partitions (P).

That’s basically CVS and Subversion: you can only continue working with the repository itself as long as your connection to the central repo server functions.

It’s rather trivial to talk about single-point-of-failure systems like CVS or Subversion as CA-mode. Another common example used this way is a classical RDBMS, but aren’t we here to talk about distributed systems? What’s a good example of a distributed CA-mode system?

A better example is Kafka, which in its default configuration assumes it being run on a corporate LAN in a single data center, so network partitions are exceedingly rare. It therefore sacrifices partition tolerance to get the advantages of CA-mode operation. In its particular application of this mode, a message isn’t “committed” until all running brokers have a copy of it, at which point the message becomes visible to the client(s). In that way, all clients always see the same message store as long as all of the Kafka servers are up and communicating.

How would that work in Fossil terms?

If there is only one central server and I clone it on my local laptop, then CA mode means I can only commit if the remote Fossil is available, so in that sense, it devolves to the old CVS model.

What if there are three clones? Perhaps there is a central server A, the clone B on my laptop, and the clone C on your laptop. Doesn’t CA mode now mean that my commit on B doesn’t exist after I commit it to the central repo A until you, my coworker, also pull down the copy of that commit to your laptop C, validating the commit through the network?

That’s one way to design the system, but another way would be to scope the system to only talk about proper servers, not about the clients. In that model, a CA-mode Fossil alternative might require 2+ servers to be running for proper replication. When I make a commit, if all of the configured servers aren’t online, I can’t commit. This is basically CVS with replication, but without any useful amount of failover.

CP-Mode Fossil

What if we modify our CA-mode system above with “warm spares”? We can say that commits must go to all of the spares as well as the active servers, but a loss of one active server requires that one warm spare come into active state, and all of the clients learn that the spare is now considered “active.” At this point, you have a CP-mode system, not a CA-mode system, because it’s now partition-tolerant (P) but it becomes unavailable when there aren’t enough active servers or warm spares to promote to active status.

CP is your classical BFT style distributed consensus system, where the system is available only if the client can contact a majority of the servers. This is a formalization of the warm spare concept above: with N server nodes, you need at least ⌊N / 2⌋ + 1 of them to be online for a commit to succeed.

Many distributed database systems run in CP mode because consistency (C) and partition-tolerance (P) is a useful combination. What you lose is always-available (A) operation: with a suitably bad partition, the system goes down for users on the small side of that partition.

An optional CP mode for Fossil would be attractive in some ways since in some sense Fossil is a distributed DBMS, but in practical terms, it means Fossil would then not be a DVCS in the most useful sense, being that you could work while your client is disconnected from the remote Fossil it cloned from.

A fraught question is whether the non-server Fossil clones count as “nodes” in this sense.

If they do count, then if there are only two systems, the central server and the clone on my laptop, then it stands to reason from the formula above that I can only commit if the central server is available. In that scheme, a CP-mode Fossil is basically like CVS.

But what happens if my company hires a coworker to help me with the project, and this person makes their own clone of the central repo? The equation says I still need 2 nodes to be available for a commit, so if my new coworker goes off-network, that doesn’t affect whether I can make commits. Likewise, if I go off-network, my coworker can make commits to the central server.

But what happens if the central server goes down? The equation says we still have 2 nodes, so we should be able to commit, right? Sure, but only if my laptop and communicate directly to my coworker’s laptop! If it can’t, that’s also a network partition, so N=1 on both sides in that case. The implication is that for a true CP-mode Fossil, we’d need some kind of peer-to-peer networking layer so that our laptops can accept commits from the other, so that when the central server comes online, one of us can send the results up to it to get it caught up.

But doesn’t that then mean there is no security? How does Fossil’s RBAC system work if peer-to-peer commits are allowed?

You can instead reconceptualize the system as “node” meaning only server nodes, so that client-only systems don’t count. This allows you to have an RBAC system again.

With just one central server, ⌊1/2⌋+1=1, so you get CVS-like behavior: if the server’s up, you can commit.

If you set up 2 servers for redundancy, both must be up for commits to be allowed, since otherwise you could end up with half the commits going to the server on one side of a network partition, half going to the other, and no way to arbitrate among the two once the partition is lifted.

(Today’s AP-mode Fossil has this capability, but the necessary cost is “C”, consistency! Once again, you can’t get around the CAP theorem.)

3 servers is more sensible: any client that can see at least 2 of them can commit.

Will there ever be a CP-mode Fossil? This author doubts it, but as I’ve shown, it would be useful in contexts where you’d rather have a guarantee of consistency than availability.