• TL;DR
• CAP
• Consistency model (eventual consistency)
• Consistency
• Availability
• Partition tolerance
• NoSQL DB
• Designing distributed key store
• References

TL;DR

The theorem formalizes the tradeoff between consistency and availability when there’s a partition.

In distributed systems, we follow the CAP Theorem, which states that in the event of a network failure (Partition), you can only provide two of the following three:

1. Consistency: Every read receives the most recent write or an error.
2. Availability: Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
3. Partition Tolerance: The system continues to operate despite an arbitrary number of messages being dropped or delayed by the network between nodes.

Pro Tip: Since network partitions are inevitable in the real world, you are almost always choosing between CP (Consistency) or AP (Availability).

What is the network partition? It happens when nodes in a network are unable to communicate with each other. Example, two ATM with network (balance, withdraw, deposit), we can partially apply withdrawing with inconsistency.

CAP

• Consistency: every node responds with the most recent version of the data, result of latest write. All clients have the same view of data.
• Availability: available node can send a response to clients. All clients can read and write if if data might be wrong.
• Partition Tolerance: the system continues working even if communication/network between any of the nodes is broken.

Why only 2?

• CP (Consistency and Partition Tolerance): The system will either give a consistent response or it will fail. It will never give an incorrect response.
• AP (Availability and Partition Tolerance): The system will always give a response even though it might be inconsistent.

Examples:

• In a social network, AP might make more sense. It is fine if we are not able to see a like/comment for a few seconds.
• In a banking system, CP might make more sense. A transaction should reflect if it has been done otherwise it might cause a big loophole. It is relatively fine if the system is unable to allow transactions for a while.

Consistency model (eventual consistency)

Consistency model defines the degree of data consistency.

• Strong consistency: any read operation returns a value corresponding to the result of the most updated write data item. A client never sees out-of-date data.
‣

Now good, why?

Strong consistency is usually achieved by forcing a replica not to accept new reads/writes until every replica has agreed on current write. This approach is not ideal for highly available systems because it could block new operations

• Weak consistency: subsequent read operations may not see the most updated value.
• Eventual consistency: this is a specific form of weak consistency. Given enough time, all updates are propagated, and all replicas are consistent.
‣

Good, why? Reconciliation and versioning.

Dynamo and Cassandra adopt eventual consistency, which is our recommended consistency model for our key-value store. From concurrent writes, eventual consistency allows inconsistent values to enter the system and force the client to read the values to reconcile.

‣

Example: YouTube number of views

Performing tasks with some delay, not necessary in real time.

Example: YouTube number of likes, no need to update database 1000 times in a second, if 1000 requests are coming. We can make it not immediately, but server can work on this normal load. Moreover, maybe we can create a hash-map in server, to have local counter. And server updates the database in every 5 minutes maybe.

Consistency

• All nodes see the same data simultaneously
• Read should return the last write operation, when data is written it should be
• All nodes should return the same data

Availability

• System remains operational all of the time
• Every request should get response even if multiple nodes are down
• Unlike a consistent system, there’s no guarantee that the response will be the most recent write operation

Partition tolerance

• System will not fail, even if message is delayed
• the network will be allowed to lose arbitrarily many messages sent from one node to another

NoSQL DB

• CA - not good, as fault tolerance is not guaranteed. PostgresSQL is relational and not distributed.
• CP - system can turn off inconsistent nodes until partition can be fixed. MongoDB. Used in big data. Only one primary node is used in write, secondary nodes duplicate the data, so the primary fails, a secondary node stands-in
• AP - all nodes are available, but they’re not all updated, won’t receive the most up-to-date version of the data. Apache Cassandra (no consistency), without primary node. When problem is resolved, then data is being synced.

Designing distributed key store

• Data partition — consistent hashing, easy scaling
• Data replication — copy data to next servers in ring, availability and reliability
• Consistency — If W + R > N, strong consistency is guaranteed (Usually N = 3, W = R = 2). W = write server, R = read server.
• Inconsistency resolution
• Handling failures
• System architecture diagram
• Write path
• Read path

References

• https://www.educative.io/blog/what-is-cap-theorem
• https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/