High Level Design

Database

---

Topics :

1. SQL vs NoSQL
2. No-SQL DB categories
3. Reason to use SQL DB
4. Reason to use No-SQL DB
5. CAP theorem
   • Definition
   • choice of DB based on CAP properties

SQL vs No-SQL

---

Sno	Relational Database	Non Relational Database
Structure	Structured	Unstructured
schema	pre-defined schema	distributed
Storage	data in rows and columns	dynamic schema
Scalability	vertically scalable , possible to scale across multiple servers(challenging and time consuming)	Horizontally scalable, Cost effective
Reliability Or ACID compliance	ACID Complaint Data reliability ,guarantee of transactions.	Sacrifice ACID compliance for performance and Scalability.
Example-	MySQL, PostgreSQL, MariaDB	KeyValue store, DocumentDB WideColumnDB GraphDB

No-SQL DB categories

---

Type	Storage	Example
Key value Store	Data : Array of key and value pair.	Redis,Dynamo
Document DB	Data : Document grouped into collection	MongoDB
Wide Column DB	Data : each row different no. of columns	Cassandra
Graph DB	Data : Nodes	Neo4j,Neptune

Reason to use SQL DB

---

1. You need to ensure ACID compliance :
   • ACID compliance
     1. Reduces anomalies
     2. Protects integrity of the database .
     3. Usage – for many E-commerce & financial app ACID compliant DB is the first choice .
2. Your data is structured & unchanging .
   • If your business is not experiencing rapid growth or sudden changes
     • No requirements of more servers
   • data is consistent

Reason to use No-SQL DB

---

When all other components of system are fast, querying & searching for data becomes bottleneck .
NoSQL prevent data from being bottleneck .
Big data is large success for NoSQL.

1. To store large volumes of data ( little/no structure)
   • No limit on type of data.
   • Document DB – Stores all data in one place. ( No need of type of data)
2. Using cloud & storage to the fullest .
   • Excellent cost saving solution . ( Easy spread of data across multiple servers to scale up)
   • No headache or additional Stw
   • NoSQL DBS like Cassandra , designed to scale across multiple data centres out of the box.

CAP theorem

---

Definition and meaning (for self understanding):

The three letters in CAP refer to three desirable properties of distributed systems with replicated data: consistency (among replicated copies), availability (of the system for read and write operations) and partition tolerance (in the face of the nodes in the system being partitioned by a network fault).

1. Consistency – 
   Consistency means that the nodes will have the same copies of a replicated data item visible for various transactions. A guarantee that every node in a distributed cluster returns the same, most recent and a successful write. Consistency refers to every client having the same view of the data. There are various types of consistency models. Consistency in CAP refers to sequential consistency, a very strong form of consistency. 
   • How achieved – achieved by updating several nodes before allowing reads [ to do – how multiple nodes write below read is achieved technically?]
     
2. Availability – 
   Availability means that each read or write request for a data item will either be processed successfully or will receive a message that the operation cannot be completed. Every non-failing node returns a response for all the read and write requests in a reasonable amount of time. The key word here is “every”. In simple terms, every node (on either side of a network partition) must be able to respond in a reasonable amount of time. 
   • How achieved – achieved by replication data across different servers [ to do – how replication achieved technically/manually?]
      
3. Partition Tolerance – 
   Partition tolerance means that the system can continue operating even if the network connecting the nodes has a fault that results in two or more partitions, where the nodes in each partition can only communicate among each other. That means, the system continues to function and upholds its consistency guarantees in spite of network partitions. Network partitions are a fact of life. Distributed systems guaranteeing partition tolerance can gracefully recover from partitions once the partition heals. 
   • How achieved – achieved by data being sufficiently replicated across combination of nodes/network to keep system up.

Choosing a Database based on Data Requirements:

For selecting a database for the application, considering the nature of your data & we need to prioritise the most critical CAP properties:

1. Prioritize Consistency: If data integrity is important and stale reads are unacceptable (e.g., financial transactions), choose a database that emphasizes consistency (like relational databases with strong consistency models). This might involve sacrificing some availability during network partitions.
2. Prioritize Availability: If consistent data reads are less crucial, but system responsiveness is essential (e.g., high-traffic social media platforms), prioritize availability. Eventual consistency models (like NoSQL databases) might be suitable. These systems guarantee data consistency eventually, but reads during partitions might return outdated data.
3. Prioritize Partition Tolerance: If your application operates in geographically distributed environments or anticipates frequent network issues, partition tolerance becomes crucial. Choose databases designed for high availability even during partitions (e.g., Geo-distributed databases).

Theorem

The CAP theorem states that distributed databases can have at most two of the three properties: consistency, availability, and partition tolerance. As a result, database systems prioritise only two properties at a time. (P- being )

Note – In normal operations, your data store provides all three functions. But the CAP theorem maintains that when a distributed database experiences a network failure, you can provide either consistency or availability.

Why not all 3 properties ?

We cannot build a data-store which is :

1. continually available
2. sequentially consistent
3. partition failure tolerant .

Because to be consistent all reads should see the same data from all distributed dbs but if network suffers failure/lag/partition (very likely in distributed system) , update in one partition might not make it to other partitions, resulting in client reads the data from out-of-date partition , solution is – Stop serving request from out of date partition. (service is no linger 100% available.)

The following figure represents which database systems prioritise specific properties at a given time:

1. CP(Consistency and Partition Tolerance)-  A CP database delivers consistency and partition tolerance at the expense of availability. When a partition occurs between any two nodes, the system has to shut down the non-consistent node (i.e., make it unavailable) until the partition is resolved.
   • Example databases: MongoDB
   • How does it(MongoDB) offers CP? –
     1. MongoDB is a CP data store—it resolves network partitions by maintaining consistency, while compromising on availability.
     2. MongoDB is a single-master system—each replica set can have only one primary node that receives all the write operations. All other nodes in the same replica set are secondary nodes that replicate the primary node’s operation log and apply it to their own data set. By default, clients also read from the primary node, but they can also specify a read preference that allows them to read from secondary nodes.
     3. When the primary node becomes unavailable, the secondary node with the most recent operation log will be elected as the new primary node. Once all the other secondary nodes catch up with the new master, the cluster becomes available again. As clients can’t make any write requests during this interval, the data remains consistent across the entire network.
2. AP(Availability and Partition Tolerance)-An AP database delivers availability and partition tolerance at the expense of consistency. When a partition occurs, all nodes remain available but those at the wrong end of a partition might return an older version of data than others. (When the partition is resolved, the AP databases typically resync the nodes to repair all inconsistencies in the system.)
   • Example databases: Cassandra
   • How does it(Cassandra) offers AP? –
     1. It’s a wide-column database that lets you store data on a distributed network. However, unlike MongoDB, Cassandra has a masterless architecture, and as a result, it has multiple points of failure, rather than a single one.
     2.  Cassandra is an AP database—it delivers availability and partition tolerance but can’t deliver consistency all the time. Because Cassandra doesn’t have a master node, all the nodes must be available continuously. However, Cassandra provides eventual consistency by allowing clients to write to any nodes at any time and reconciling inconsistencies as quickly as possible.
3. CA(Consistency and Availability)- A CA database delivers consistency and availability across all nodes. It can’t do this if there is a partition between any two nodes in the system, however, and therefore can’t deliver fault tolerance
   • Example databases: RDBMS

Random Points around DBs-

1. No NoSQL DB offers CA
2. For NoSql – P(Partition Tolerant) Of CAP – is mandatory and it offers either Availability or Consistency.

---

---

Partitions and shading

---

make connection points/sentences out of bellow points –

To cope with following problem –

1. Reba-lacing
2. uneven traffic distributions

Consistency and Availability

use consistent hashing (what is it ? and how does it helps)

to deal with trade-off availability vs consistency : Quorum (how does it work in actual)

R+w>N

One will overlap ensuing strong consistency

Inconsistency resolution – why THIS PROBLEM

Versioning and vector locks – are used to solve inconsistency problems – [ACCEPTABLE SOLUTION [dynamo db not seen the problem in prod] but can encounter problem ]

Failure Handling

• Detection
• resolution

Detection – emthod if 2 or more sources say a servir is down – we can bevieve , ineffiinet soln -all-to-all maping fives info but not efficient where larhe no of sys exists.

Better solution – use decentralised failure detection method like – gossip protocol -if heart beat is not received for a specified amt of time ift is considered offline (real word example using this scenario )

Temporary failure solution

1. Strict quorum
2. Sloppy quorum
   • Hinted-hand-off – for handling temporary failure

Permanent failure solution

Permanent failure solution – Anti-entropy protocol to keep replicas in sync.

Anti-entropy involves comparing each piece of data on replicas and updating
each replica to the newest version. A Merkle tree is used for inconsistency detection and
minimizing the amount of data transferred.

Process –

To compare two Merkle trees, start by comparing the root hashes. If root hashes match, both
servers have the same data. If root hashes disagree, then the left child hashes are compared
followed by right child hashes. You can traverse the tree to find which buckets are not
synchronized and synchronize those buckets only

Using Merkle trees, the amount of data needed to be synchronized is proportional to the
differences between the two replicas, and not the amount of

Handling data center outage
Data center outage could happen due to power outage, network outage, natural disaster, etc.
To build a system capable of handling data center outage, it is important to replicate data
across multiple data centers. Even if a data center is completely offline, users can still access
data through the other data centers.

Note-

Write flow-

Inorder to store data – first save the commitlog and save data in caache then after a threshold – push to db SSTable (Sorted String tbale – sorted by <K,v>) – Note – above is working of cassandra , what problem does it solves?

Read flow-

check in cache is exists return . if not exists in cache the using bloom filter check in db efficiently (ToDo: Working of bloom filter?)

https://en.wikipedia.org/wiki/Bloom_filter