Some Critical Database Concepts  (ACID-CAP-FLP)

Those concepts are really important but we are trying to make small summaries below

Feel free to communicate by bulent.yucesoy@gmail.com

-----------------------

ACID (Atomicity, Consistency, Isolation, Durability) 

* Atomicity: 

Either commit all or nothing. 

* Consistency: 

Make consistent record in terms of validate all rules and constraints of transaction.

* Isolation:

Make sure that two concurrent transaction is unaware to each other. 

* Durability:

committed data stored forever. 
(there must no be a problem like; committed trx at memory couldn't be written at disk level and lost at memory)

---------------------

CAP theorem ( consistency,availability,partitioning )

In a distributed database system (a collection of interconnected nodes that share data.), you can only have
 2 out of the following 3 guarantees across a write/read pair: 

  Consistency, Availability, and Partition Tolerance 

one of them must be sacrificed.


* Consistency

A read is guaranteed to return the most recent write for a given client.

* Availability

A non-failing node will return a reasonable response within 
a reasonable amount of time (no error or timeout).

* Partition Tolerance

The system will continue to function when network partitions occur.


When there is no network partitioning, system can be CA. This is also provided with ACID.
When there is network partitioning, you can choose either becoming CP or AP
AP => we care availability, we dont care consistency, so query results must not return timeout or error.
      we request the latest possible recent result, we know that result can be stale but it is not a problem for us if we have mechanism to recover. 
      for example, we can synchronize and correct those issues later on when partitioning problem was solved.
      or we may use QUEUE mechanisms and push such transactions in queue and we may operate as batch when problems solved etc.
      availability is critical for 7*24 applications like credit card POS systems.
CP => we dont care availability so we can wait query result and result can be timeout or error, it is not problematic for us.
      we must chose this options if mission is so critical and we cant tolerate correcting possible stale results later on.

-------------

FLP theorem (Fischer Lynch Paterson)

A deterministic asynchronous consensus (or agreement) system can have at most 2 of 3. 

* Safety

Results are valid and identical at all nodes. 
( This looks like Consistency at CAP theorem )

* Liveness ( or GUARANTEED TERMINATION )

Non-failing nodes must always produce a result. Having no result is not acceptable.
( This looks like Availability at CAP theorem )

* Fault Tolerance

There can be failing nodes but total consensus system must always be probable to function amongst node failures.
(This looks like Partitioning at CAP theorem)

---------------

CAP and FLP difference

They are not same, but they may look similar.
Partitioning in CAP is different than Fault Tolerance at FLP.
Partitioning is problems at network level. Messages can not be distributed etc.
Fault Tolerance(FT) at FLP is something different. FT can be 2 levels. CFT ( Crash FT ) and BFT ( Byzantine FT)
Crash FT => nodes can crash
Byzantine FT => nodes can deliver wrong messages and those must be solved to arrive consensus.
Many algorithms exist for CFT ( Paxos/Raft/Kafka-Zookepeer) and BFT ( PBFT / RBFT / SBFT )