Three Different Ways to beat CAP Theorem
The Cap Theorem can be summarized with three words; strong consistency, availability and partition tolerance. As you know, You must pick two out of three. Unfortunately, You actually have only two options — not three. You can not be avoid or defeat network faults in any way. So, you can choice only between strong consistency and availability. I would like to explain the this problem in more detail in another article and talk about PACELC theorem.For now, I do not want to get off the point.
I have to say that, I will not talk about “tricks” or “workarounds” to beat “CAP”. I will describe alternative ways that you can use to beat CAP. In Reality, You have only three different ways to beat CAP.
- Broadcast Protocols
- CRDTs
- Eventually Consistent and Highly Available Data Store
Broadcast Protocols
A broadcast protocol that guarantees every replica receives the same updates in the same order event in the presence of faults and a deterministic function that handles updates on each replica.
Network communication over wan -like the internet, only offers p2p (unicast) communication protocols — like TCP. If you want to deliver a message to a group of processes, you must need a broadcast protocol(multicast).
There are many different implementations of broadcast protocols and the differ on the guarantees the provide.
- best-effort broadcast protocol
- reliable broadcast protocol (eager, uniform, majority-ack uniform or lazy)
- gossip broadcast protocol
best-effort broadcast protocol
It guarantees that if the sender does not crash, the message is delivered to all non-faulty processes in a group. A simple way to implement it is to send the message to all processes in a group one-by-one over reliable links but if sender fails mid-way, some processes will never receive the message. You can check this repository for a simple implementation of BEB.
reliable broadcast protocol
It guarantees that the message is eventually delivered to all non-faulty processes in the group, event if the sender crashes before the message has been fully delivered. One way to implement reliable broadcast is to have each processes re-transmit the message to the rest of the group the first time it is delivered. This approach is also known as eager reliable broadcast -ERB. Although it guarantees that all non-faulty processes eventually recieve the message, It’s costly as it requires sending the message N² times for a group of N processes. The number of messages can be reduced by re-transmitting a message on delivery to a random subset of processes. You can check this repository and this one for a simple implementations.
gossip protocol
It is a probabilistic protocol, it does not guarantee that a message will be delivered to all processes. That said, it is possible to make that probability negligible by tuning the protocol’s parameters. Gossip protocols are particularly useful when broadcasting to a large number of processes, like thousands or more, where deterministic protocol would not scale.
CRDTs
A broadcast protocol does not delivery messages in the same order across all replicas will inevitably lead to divergence. One way to reconcile conflicting writes is to use consensus to make a global decision that all replicas need to agree with. But, this method is very challenging! You must ask the following questions to you:
- Which variation of eventual consistency do i need?
- How do i guarantee eventual delivery?
- Which method do i use to my replicas? convergence or strong convergence?
Suppose that, We replicate an object on N replicas, where the object is an instance of data type that supports query and update operations -i.e. string, integer etc.
A client can send an update or query operation to any replica
- when a replica receives a query, it immediately replies using the local copy of the object
- when a replica receives an update, it first applies it to the local copy of the object and then broadcasts the updated object to all replicas
- and when a replica receives a broadcast message, it merges the object in the message with its own.
It can be shown that each replica will converge to the sample state if;
- the object’s states from a semilattice
- and the merge ops returns the least upper bound between the objects’ states
A data type that has these properties is also called a convergent replicated data type which is part of the family of conflict-free replicated data types. Also, there re many data types that are designed to converge when replicated, like counters, sets, and graphs. CRDTs very tough topic. I want to recommend this article to deeply understand what it does and what it does not.
Eventually Consistent and Highly Available Data Store
As you know, Cassandra and Riak have been inspired by Amazon’ Dynamo DB. (like many others.)
In this data stores, every replica can accept write and read requests. When a client wants to write a data to the data store, it sends a write request to all N replicates in parallel, but waits to gets an ack back from just W replicas(a write quorum)
Similarly, when a client wants to read an data from the data store, it sends a read request to all replicas but waits just for R replicates. (a read quorum) and, returns to the client the most recent data. To resolve conflicts, data behave like LWW or LW registers depending on the implementation flavor.
When W + R > N, the write quorum and the read quorum intersect with each other and at least one read will return the latest version. This does not guarantee linear-izability, though. Typically, W and R are configured to be majority quorums. But, one cruel problem with this approach is that a write request sent to a replica might never make it to the destination. In this case, the replica is not eventually consistent no matter how long it waits. To ensure that replicas converge, two anti-entropy mechanism are used: read-repair and replica synchronization. For more details, you can use this link.
In conclusion, You can beat CAP with these three different ways but which one to use of them or how one to use of then is entirely up to you. But if you are thinking of designing a distributed system, please consider these notes!
I am thinking of talking about PACELC in my next article. Until then, keep in touch!
