Part 7— Complete System Design Series

System Design Made Easy…

Welcome back peeps. In the last part ( links below) we covered in detail ( with examples) —

Projects Videos —

All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).

Subscribe today!

Solved System Design Case Studies — In depth

Design Instagram

Design Messenger App

Design Twitter

Design URL Shortener

Design Dropbox

Design Youtube

Design API Rate Limiter

Design Web Crawler

Design Facebook’s Newsfeed

Design Yelp

Design Uber

Design Tinder

Design Tiktok

Design Whatsapp

Most Popular System Design Questions

Mega Compilation : Solved System Design Case studies

All the Complete System Design Series Parts —

1. System design basics

2. Horizontal and vertical scaling

3. Load balancing and Message queues

4. High level design and low level design, Consistent Hashing, Monolithic and Microservices architecture

5. Caching, Indexing, Proxies

6. Networking, How Browsers work, Content Network Delivery ( CDN)

7. Database Sharding, CAP Theorem, Database schema Design

8. Concurrency, API, Components + OOP + Abstraction

9. Estimation and Planning, Performance

10. Map Reduce, Patterns and Microservices

11. SQL vs NoSQL and Cloud

Moving forward, this is the part 7 of the system design series where we will be covering —

1. Database Sharding
2. CAP Theorem
3. Database schema Design

Part 1 of this series can be found here —

Part 2 of this series can be found here —

Part 3 of this series can be found here —

Part 4 of this series can be found here —

Part 5 of this series can be found here —

Part 6 of this series can be found here —

And Most popular System Design Questions —

Let’s dive in!

Note : Please read System Design Important Terms you MUST know before reading this post.

Sharding

Pasta Resto Case:

Now everything is running well at your pasta resto and since you as an owner started taking customer online reservations, also added new dishes to your menu, new chefs — servers/waiters with payroll all in one database. Whenever you need any details, you just go to this database and retrieve the results.

One unlucky day, the data base crashes!! All the data is gone :(

Now what?

Wouldn’t it be nicer if you had —

1. Made data base partitions to store above mentioned data entries separately on different database servers
2. Thought about creating database backups
3. Thought about how to scale the databases dynamically as the data load increases

Hard lessons!!

System Design Analogy:

Taking the same analogy forward, sharding is a very important concept in system design and a good understanding of sharding — database partitioning goes a very long way.

So what is sharding/Database partitioning?

In layman’s words, sharding is the technique to database partitioning that separates large and complex databases into smaller, faster and distributed databases for higher throughput operations.

Database sharding is a method of horizontally partitioning data across multiple separate databases, in order to distribute load and improve scalability. Each partition, or shard, is a self-contained subset of the data, and the shards are distributed across multiple servers.

Implementation of sharding in a database using Python and MongoDB:

• Install the Python MongoDB driver:

pip install pymongo

• Create a MongoDB cluster with two nodes:

mongod --replSet myCluster --port 27017
mongod --replSet myCluster --port 27018

• Initialize the MongoDB replica set:

import pymongo

client = pymongo.MongoClient('mongodb://localhost:27017,localhost:27018')
client.admin.command('replSetInitiate')

• Define a sharding key for the database collection:

shard_key = {'_id': 'hashed'}

In this implementation, we are using the _id field as the sharding key and using a hashed sharding algorithm.

• Enable sharding for the database:

client.admin.command('enableSharding', 'mydatabase')

• Create a sharded collection and shard it:

client.admin.command('shardCollection', 'mydatabase.mycollection', key=shard_key)

Now, the mycollection collection is sharded across both nodes of the MongoDB cluster.

• Insert data into the sharded collection:

db = client.mydatabase
collection = db.mycollection

for i in range(10000):
    collection.insert_one({'_id': i, 'data': 'some data'})

• Query the sharded collection:

result = collection.find({'_id': {'$gt': 5000}})

In this implementation, the query is only processed by one of the nodes in the MongoDB cluster, since the data is sharded across both nodes.

Queries are routed to the appropriate shard based on a shard key, which is a value that is used to determine which shard a particular piece of data belongs to.

Database sharding is a technique for horizontally scaling a database by dividing the data across multiple separate database instances, known as shards. Each shard contains a subset of the total data and operates independently, allowing the database to scale both storage capacity and processing power.

Here is a simple implementation of database sharding in Python using the sqlite3 module:

import hashlib
import sqlite3

SHARD_COUNT = 4

def get_shard_id(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % SHARD_COUNT

def execute_query(query, parameters):
    shard_id = get_shard_id(parameters[0])
    conn = sqlite3.connect(f"shard_{shard_id}.db")
    cursor = conn.cursor()
    cursor.execute(query, parameters)
    conn.commit()
    return cursor.fetchall()

def add_user(username, email):
    execute_query("INSERT INTO users (username, email) VALUES (?, ?)", (username, email))

def get_user(username):
    return execute_query("SELECT * FROM users WHERE username = ?", (username,))

if __name__ == "__main__":
    for i in range(SHARD_COUNT):
        conn = sqlite3.connect(f"shard_{i}.db")
        cursor = conn.cursor()
        cursor.execute("CREATE TABLE IF NOT EXISTS users (username text, email text)")
        conn.commit()
    add_user("john", "[email protected]")
    print(get_user("john"))

In this example, the get_shard_id function uses a hash function to determine which shard a particular piece of data should be stored on based on a key. The execute_query function uses the shard ID to connect to the appropriate database and execute the query. The add_user and get_user functions provide a simple interface for adding and retrieving user records, respectively.

The SHARD_COUNT constant determines the number of shards, and in this example we're using 4 shards. Each shard is represented by a separate SQLite database stored in a file with a unique name, such as shard_0.db, shard_1.db, etc.

Sharding can be used to distribute load across multiple servers and improve performance, but it can also make it more complex to maintain consistency and integrity of the data.

Why sharding?

To make databases —

1 . Faster and improve performance

2. Smaller and manageable

3. Reduce the transactional cost

4. Distributed and scale well

5. Speed up Query response time

6. Increases reliability and mitigates the after effects of outrages

There are two ways you can do sharding —

Horizontal Sharding — divide the database table’s rows into multiple different tables where each part has the same schema and columns but different rows in order to create unique and independent partitions.

Vertical Sharding — divide the database entire columns into new distinct tables such that each vertically partitioned parts are independent of all the others and have distinct rows and columns.

When should you think of implementing sharding?

When you are handling large amount of data

When network bandwidth is a bottleneck

When you want to make the read and write faster

CAP Theorem

Pasta Resto Case:

In your pasta resto, you have some rules for every one working there.

1. Consistency — Same menu, services level for every one

2. Availability — Always have an answer to a query

3. Partition Tolerance — Even if someone has called a day off, then also the resto works without any issues

System Design Analogy:

Taking same analogy, CAP is a very important concept in System Design. It’s the job of system designer/engineer to make sure at-least 2 (out) of 3 properties are satisfied for a networked shared data systems.

C stands for Consistency

This means the data is same across all the nodes ( i.e every user sees the same view of the data) and the when queried it returns most recent write.

Python code that demonstrates consistency in a distributed system:

import requests

# Request the menu from node 1
response1 = requests.get('http://node1.example.com/menu')
menu1 = response1.json()

# Request the menu from node 2
response2 = requests.get('http://node2.example.com/menu')
menu2 = response2.json()

# Check if the menus are the same
if menu1 == menu2:
    print('The menus are consistent')
else:
    print('The menus are not consistent')

A stands for Availability

The data be available at all the times ( may or may not be recent) and when queries it returns a response Always.

Python code that demonstrates availability in a distributed system:

import requests

# Request the services from node 1
try:
    response1 = requests.get('http://node1.example.com/services')
    services1 = response1.json()
    print('Node 1 is available')
except:
    print('Node 1 is unavailable')

# Request the services from node 2
try:
    response2 = requests.get('http://node2.example.com/services')
    services2 = response2.json()
    print('Node 2 is available')
except:
    print('Node 2 is unavailable')

# If both nodes are unavailable, return an error message
if 'services1' not in locals() and 'services2' not in locals():
    print('No nodes are available')

P stands for Partition Tolerance

The system should keep operating despite failures, or partitions or unprecedented outrage.

Implementation of partition tolerance in a distributed system:

import requests

# Define the minimum number of nodes needed for a quorum
QUORUM = 2

# Request the status from node 1
try:
    response1 = requests.get('http://node1.example.com/status')
    status1 = response1.json()
    print('Node 1 status:', status1)
except:
    print('Node 1 is unavailable')

# Request the status from node 2
try:
    response2 = requests.get('http://node2.example.com/status')
    status2 = response2.json()
    print('Node 2 status:', status2)
except:
    print('Node 2 is unavailable')

# Determine if we have a quorum
if ('status1' in locals() and status1 == 'OK') or ('status2' in locals() and status2 == 'OK'):
    print('We have a quorum')
else:
    print('We do not have a quorum')

NoSQL databases are considered to be AP ( Availability and Partition Tolerance ) systems.

CAP theorem states that it is impossible for a distributed system to simultaneously provide all three of the following guarantees: consistency, availability, and partition tolerance. Consistency means that all nodes see the same data at the same time, availability means that every request receives a response without guarantee that it contains the most recent version of the information, and partition tolerance means that the system continues to function despite arbitrary partitioning due to network failures.

The CAP theorem states that it is impossible for a distributed system to simultaneously provide all three of the following guarantees: consistency, availability, and partition tolerance. In other words, a distributed system must make a trade-off between these three properties.

Here is a simple implementation of the CAP theorem in Python using the redis module:

import redis

# Connect to the Redis database
r = redis.Redis(host='localhost', port=6379, db=0)

# Implement the SET operation with strong consistency
def set_strong_consistency(key, value):
    # Acquire a lock to ensure only one client can modify the value at a time
    while not r.set(key + "_lock", True, nx=True, ex=10):
        pass
    # Set the value
    r.set(key, value)
    # Release the lock
    r.delete(key + "_lock")

# Implement the GET operation with weak consistency
def get_weak_consistency(key):
    # Return the value directly, without any locking
    return r.get(key)

# Use the SET operation to write a value with strong consistency
set_strong_consistency("my_key", "my_value")

# Use the GET operation to read the value with weak consistency
print(get_weak_consistency("my_key"))

In this example, the set_strong_consistency function implements the SET operation with strong consistency, using a lock to ensure that only one client can modify the value at a time. This ensures that the value is always consistent, but may not be available if another client holds the lock.

The get_weak_consistency function implements the GET operation with weak consistency, simply returning the value directly without any locking. This ensures that the value is always available, but may not be consistent if another client is simultaneously modifying the value.

Why CAP theorem?

1. It lets you determine how you want to handle your distributed databases with there is possibility of inconsistencies, unavailability and connection errors/failures/outrage.
2. It helps you decide right distributed db system for your architecture.
3. It lets you decide the trade offs between the 3 constituents of the CAP theorem.
4. Simplifies the system design for you.

Database Schema Design

Pasta Resto Case:

As you’re pasta resto is now growing exponentially the data you need to store is also multiplying. So, as an owner who has faced db failure and outrage before, you think of the solutions which will help you better organize your data — customer data, inventory data, reservation data, manpower data, payrolls data, monetary details etc.

What’s the best way to store this data in an efficient way and if one category of data has some relationship with other then how to address it ( i.e like customer data — reservation data etc)?

You think of organizing it and drawing the data base schema for each above mentioned category of data.

System Design Analogy:

Taking the same analogy, Database schema design helps you —

1. Organize data into separate entities

2. Let’s you establish and organize the relationships between different entities

3. Eliminate data redundancy and inconsistencies in the data

4. Makes sure your data is correct and maintains the integrity of data.

5. Provides abstraction/security to sensitive data

6. Facilitates faster data retrieval and analysis

Database schema design is the process of creating a structured layout of a database, including the definition of tables, fields, relationships, and constraints. A well-designed schema can help to ensure data integrity, improve performance, and simplify data access and maintenance.

Here’s an example of how you might implement a database schema design using the SQLAlchemy ORM in Python:

from sqlalchemy import create_engine, Column, Integer, String
from sqlalchemy.orm import sessionmaker
from sqlalchemy.ext.declarative import declarative_base

Base = declarative_base()

class User(Base):
    __tablename__ = 'users'
    id = Column(Integer, primary_key=True)
    name = Column(String)
    age = Column(Integer)

engine = create_engine('sqlite:///example.db')
Base.metadata.create_all(engine)

Session = sessionmaker(bind=engine)
session = Session()

# Insert a new user into the database
user = User(name='John Doe', age=30)
session.add(user)
session.commit()

# Query the database to retrieve all users
users = session.query(User).all()

for user in users:
    print(user.name, user.age)

In this example, the User class is defined using the SQLAlchemy ORM. The __tablename__ attribute defines the name of the table in the database, and the Column objects define the columns in the table. The SQLAlchemy create_engine function is used to create an instance of the SQLite database engine. The Base.metadata.create_all function is used to create the table in the database. The SQLAlchemy sessionmaker function is used to create a session class, which provides a high-level interface for interacting with the database. An instance of the session class is created using the Session class, and this instance is used to perform CRUD operations on the database. In this implementation, a new user is inserted into the database using the add method of the session object, and the changes are committed using the commit method. The database is then queried to retrieve all users using the query method of the session object, and the results are printed to the console.

The most common approach to designing a database schema is to use a technique called normalization, which involves breaking down data into smaller, more manageable tables that are related to one another through relationships. This helps to minimize data redundancy and improve data integrity by reducing the potential for errors and inconsistencies.

Another important aspect of schema design is choosing the right data types and constraints for each field, such as setting primary keys, foreign keys, and indexes. These elements play a crucial role in organizing and searching the data efficiently.

Overall, schema design is an iterative process that requires a good understanding of the data and the requirements of the system that will use it.

To implement a thorough database schema design —

1. Implement normalization, join and establish entity relationships ( one-one, one-many, many — one, many — many)

2. Follow the naming conventions

3. Organize the data well ( with a unique identifier — primary key)

4. Take examples and Document it well

5. Determine the purpose of your data base

6. Build efficient tables ( with indexing)

7. Refine your design from time to time as more data gets added/removed

Normalization is the process of organizing data in a database to minimize redundancy and improve data integrity. It involves breaking down a large table into smaller, more manageable tables and establishing relationships between them.

The main goal of normalization is to reduce data duplication and improve data consistency.

There are several levels of normalization, each with its own set of rules. These include:

1. First Normal Form (1NF): This requires that each column in a table contain atomic values, meaning that it cannot be further subdivided. Each row must also have a unique identifier, known as a primary key.
2. Second Normal Form (2NF): This requires that all non-key attributes be functionally dependent on the primary key. In other words, each non-key attribute must be uniquely identified by the primary key.
3. Third Normal Form (3NF): This requires that all non-key attributes be independent of each other. In other words, no non-key attribute should be dependent on another non-key attribute.

Entity relationships are the connections between different tables in a database.

There are several types of entity relationships, including:

1. One-to-one (1:1): Each record in one table corresponds to exactly one record in another table.
2. One-to-many (1:N): Each record in one table can correspond to multiple records in another table, but each record in the second table corresponds to only one record in the first table.
3. Many-to-one (N:1): Each record in one table can correspond to only one record in another table, but each record in the second table can correspond to multiple records in the first table.
4. Many-to-many (N:N): Each record in one table can correspond to multiple records in another table, and vice versa.

More on Database Sharding, CAP Theorem Database schema Design —

Database sharding is a technique used in distributed databases to horizontally partition data across multiple servers or shards. The purpose of sharding is to improve scalability, performance, and availability of the database system by distributing the workload across multiple nodes.

Benefits and trade-offs of sharding:

Benefits:

• Improved scalability: Sharding allows the database to handle larger data sets and higher query loads by distributing the data across multiple servers.
• Increased performance: By distributing data and query load, sharding can improve read and write performance as the workload is divided among multiple shards.
• Higher availability: Sharding provides fault isolation, so a failure in one shard does not affect the availability of the entire database system.
• Cost-effective scaling: Sharding enables incremental scaling by adding more shards as the data and workload grow.

Trade-offs:

• Increased complexity: Sharding introduces additional complexity in terms of data distribution, query routing, and management of shards.
• Limited transactional capabilities: Sharded databases face challenges in maintaining strong consistency across shards, which can impact certain transactional use cases.
• Shard management overhead: Managing shard metadata, data distribution, and ensuring data consistency requires additional administrative effort.
• Query complexity: Queries that require data from multiple shards may require additional coordination and complexity.

Common use cases and scenarios where sharding is beneficial:

• Large-scale applications with high data volumes: Sharding is beneficial for applications dealing with large amounts of data that cannot be handled by a single server.
• High read or write workloads: Sharding can help distribute the read and write load across multiple servers, improving performance.
• Global or geographically distributed applications: Sharding enables data to be stored closer to users, reducing latency and improving response times.
• Scalability requirements: Sharding allows for horizontal scaling, enabling the database to grow as the application demands increase.

Sharding Strategies:

Horizontal vs. vertical sharding:

• Horizontal sharding: In horizontal sharding, data is partitioned based on rows or ranges of data. Each shard contains a subset of the data with a shared schema. This strategy is suitable when the data can be divided into independent subsets and when the workload can be evenly distributed across shards.
• Vertical sharding: In vertical sharding, data is partitioned based on columns or attributes. Each shard contains a subset of the columns of the data with its own schema. This strategy is useful when the data set has a large number of attributes and some attributes are accessed more frequently than others.

Key-based sharding, range-based sharding, and hash-based sharding:

• Key-based sharding: Key-based sharding involves assigning data to shards based on a specific attribute or key, such as a customer ID or geographical location. Each shard is responsible for a range of key values. This strategy allows for easy data location and routing based on the key.
• Range-based sharding: Range-based sharding involves dividing the data into ranges based on a specific attribute or key. Each shard is responsible for a specific range of values. This strategy works well when the data can be naturally divided into ranges and when queries often access data within specific ranges.
• Hash-based sharding: Hash-based sharding involves applying a hash function to a specific attribute or key to determine the shard where the data should be stored. This strategy provides a random distribution of data across shards, which can help evenly distribute the workload. However, it makes locating specific data more difficult.

Shard key selection considerations:

• Cardinality: The shard key should have high cardinality to ensure even data distribution across shards. High cardinality means that the values in the shard key are diverse and not heavily skewed towards certain values.
• Access patterns: The shard key should align with the typical access patterns of the application. It should be chosen based on the queries that are frequently executed, ensuring that data accessed together is stored within the same shard.
• Data skew: The shard key should be selected to minimize data skew, which refers to an imbalance in data distribution across shards. Data skew can lead to hotspots where a few shards are heavily loaded while others remain underutilized. Avoiding skewed data distribution helps maintain balanced query performance.
• Scalability and growth: The shard key should be chosen with future scalability in mind. It should allow for the addition of new shards without the need to reshuffle or redistribute the existing data. This helps in seamless expansion of the database as the application grows.

Shard metadata and management:

Shard metadata refers to the information about the shards in the database, such as their locations, size, status, and the range of data they contain. Efficient management of shard metadata is crucial for the proper functioning of a sharded database.

• Metadata storage: The metadata can be stored in a centralized metadata store or distributed across the shards themselves. Storing metadata centrally simplifies management but introduces a single point of failure. Distributing metadata adds complexity but improves fault tolerance.
• Shard management operations: Sharded databases require operations to manage shards, such as adding new shards, removing shards, and rebalancing data across shards. These operations need to be carefully planned and executed to ensure data integrity and minimize downtime.
• Monitoring and automation: Monitoring the health and performance of shards is essential. Automated processes can be implemented to detect and handle shard failures, rebalance data, and adjust the number of shards based on workload patterns.

Data Distribution and Replication:

Data partitioning and distribution across shards:

When data is partitioned and distributed across shards, several approaches can be used:

• Range partitioning: Data is divided based on a specific range of values. For example, customer records with last names starting from A to M can be stored in one shard, while last names starting from N to Z can be stored in another shard.
• List partitioning: Data is partitioned based on predefined lists or categories. Each shard is assigned specific values or categories of data. For instance, customer records from a specific country can be stored in one shard.
• Hash partitioning: Data is distributed across shards using a hash function applied to a chosen attribute. The result of the hash determines the shard to which the data belongs. This approach provides a random and even distribution of data.

Replication and consistency models in sharded databases:

Replication in sharded databases involves creating multiple copies of data across shards for increased availability and fault tolerance. Various replication models can be used:

• Master-slave replication: One shard serves as the master that handles both read and write operations, while the other shards (slaves) replicate the data from the master. This model improves read scalability but introduces replication lag for writes.
• Multi-master replication: All shards can accept both read and write operations, and changes are replicated across the shards. This model provides better write scalability but requires conflict resolution mechanisms.
• Consistency models: Sharded databases face challenges in maintaining strong consistency across shards due to the distributed nature of data. Various consistency models, such as eventual consistency and strong consistency, can be employed based on the application requirements and trade-offs.

Challenges in maintaining data consistency across shards:

Ensuring data consistency across shards in a sharded database can be challenging due to:

• Transactional coordination: Coordinating transactions that involve data from multiple shards requires additional complexity and coordination mechanisms. Techniques like two-phase commit or distributed transactions can be used to maintain consistency.
• Data conflicts: Concurrent updates to the same data across different shards can lead to conflicts. Conflict resolution mechanisms, such as timestamp ordering or conflict detection and resolution algorithms, are necessary to resolve these conflicts and maintain consistency.
• Cross-shard queries: Queries that require data from multiple shards introduce the challenge of ensuring consistent and up-to-date results. Techniques like distributed joins, query routing, and data aggregation across shards need to be implemented to handle these queries effectively.

Conflict resolution and synchronization techniques:

• Optimistic concurrency control: This technique allows multiple transactions to proceed concurrently without acquiring locks. Conflicts are detected during the commit phase, and appropriate resolution mechanisms, such as retrying the transaction or rolling back conflicting changes, are applied.
• Distributed consensus protocols: Consensus protocols like Paxos or Raft can be used to achieve agreement among nodes in a distributed system. These protocols enable coordination and conflict resolution in scenarios where strong consistency is required across shards.
• Conflict-free replicated data types (CRDTs): CRDTs provide conflict-free operations on replicated data by design. They ensure that concurrent updates can be applied in any order without conflicting with each other, ensuring eventual consistency across shards.

Query Routing and Load Balancing:

Routing queries to the appropriate shards:

• Shard-aware clients: Clients need to be aware of the sharding strategy and have the ability to route queries to the appropriate shard based on the query parameters or shard key. This can be done through client-side libraries or middleware components.
• Query routers: A dedicated query routing layer can be introduced between the clients and the database to handle query routing. The router receives incoming queries, determines the relevant shards based on the query parameters, and forwards the queries accordingly.

Load balancing strategies for evenly distributing traffic:

• Round-robin: Queries are distributed to shards in a cyclic manner, ensuring an even distribution of traffic. This strategy is simple to implement but may not take into account the varying workload or performance characteristics of shards.
• Dynamic load balancing: Load balancing algorithms that consider the current load and performance metrics of each shard can be used. This allows for intelligent routing decisions that optimize resource utilization and minimize response times.

Connection pooling and resource management in sharded environments:

• Connection pooling: In sharded environments, connection pooling becomes even more important to efficiently manage database connections. Connection pooling libraries or frameworks can be used to maintain a pool of reusable connections and manage their allocation to shards.
• Resource monitoring and scaling: Monitoring resource usage across shards helps identify performance bottlenecks and scalability issues. Automatic scaling mechanisms can be employed to add or remove shards dynamically based on resource utilization thresholds.

Sharding in Practice:

Sharding in relational databases (e.g., MySQL, PostgreSQL):

Relational databases like MySQL and PostgreSQL can be sharded by following these steps:

1. Choose a sharding strategy: Determine whether horizontal or vertical sharding is more suitable for the application’s requirements.
2. Define shard key: Select an appropriate shard key that aligns with the access patterns and evenly distributes data across shards.
3. Implement sharding logic: Modify the database schema and application code to incorporate sharding logic for data distribution and query routing.
4. Shard management: Establish mechanisms to manage shards, such as adding new shards, redistributing data, and monitoring shard health.
5. Replication and consistency: Configure replication mechanisms to ensure data availability and consistency across shards.

Sharding in NoSQL databases (e.g., MongoDB, Cassandra):

NoSQL databases like MongoDB and Cassandra are designed to scale horizontally and often have built-in sharding capabilities. Sharding in NoSQL databases typically involves:

1. Configure sharding: Set up the sharding configuration, including the shard key selection and the number of shards.
2. Data distribution: Insert data into the database, and the database automatically distributes the data across shards based on the shard key.
3. Query routing: Queries are automatically routed to the appropriate shard based on the shard key, ensuring that only the relevant shards are accessed.
4. Shard management: Monitor the health and performance of shards, and perform shard management operations such as adding or removing shards as needed.
5. Replication and consistency: Configure replication settings to ensure data durability and availability. Replication mechanisms such as replica sets or data replication across data centers can be used to maintain consistency and fault tolerance.

Sharding considerations in distributed systems and cloud environments:

In distributed systems and cloud environments, additional considerations arise when implementing sharding:

1. Elastic scalability: Sharding should support the ability to dynamically add or remove shards based on demand. This requires automated scaling mechanisms and coordination with the underlying infrastructure.
2. Fault tolerance and high availability: Sharding should incorporate fault-tolerant strategies to handle shard failures and ensure high availability. Replication, monitoring, and automated recovery mechanisms are vital for maintaining system resilience.
3. Network latency and data locality: Sharding should take into account the geographic distribution of users and data. Locating shards closer to users or specific regions can reduce network latency and improve overall performance.
4. Cloud-native sharding: Cloud providers often offer sharding solutions or managed database services with built-in sharding capabilities. Leveraging these services can simplify the deployment and management of sharded databases in cloud environments.

CAP Theorem:

The CAP theorem, also known as Brewer’s theorem, states that it is impossible for a distributed system to simultaneously provide Consistency, Availability, and Partition tolerance. The CAP theorem highlights the trade-offs that need to be made in the design of distributed systems.

Consistency, availability, and partition tolerance trade-offs:

• Consistency: Consistency refers to ensuring that all nodes in a distributed system have the same view of the data at the same time. In the context of the CAP theorem, consistency means that a read operation always returns the latest committed data. However, achieving strong consistency in a distributed system can impact system performance and availability.
• Availability: Availability means that the system continues to respond to requests, even in the presence of failures or network partitions. In the context of the CAP theorem, availability implies that the system remains operational and responsive to client requests, even if it means returning stale or outdated data.
• Partition tolerance: Partition tolerance refers to the system’s ability to function and maintain data consistency despite network partitions or communication failures. Partition tolerance ensures that the system can handle temporary network disruptions and still operate correctly.

The CAP theorem states that in the presence of a network partition (P), a distributed system must choose between maintaining Consistency © or providing Availability (A). Achieving both strong consistency and high availability simultaneously becomes challenging in distributed systems.

Consistency Models:

Strong consistency vs. eventual consistency:

• Strong consistency: Strong consistency guarantees that all nodes in a distributed system have the same view of the data at any given time. Any read operation will always return the latest committed value. Achieving strong consistency often requires coordination and synchronization among nodes, which can impact system performance and availability.
• Eventual consistency: Eventual consistency allows for temporary inconsistencies among nodes but guarantees that all replicas will eventually converge to the same state. After a period of time without updates or conflicts, all replicas will reflect the same data. Eventual consistency prioritizes availability and scalability but can lead to temporarily divergent views of data.

Linearizability, sequential consistency, and causal consistency:

• Linearizability: Linearizability is a strong form of consistency that ensures that each operation appears to execute instantaneously at a single point in time. Linearizability provides the illusion that operations are executed in a sequential order, regardless of the distribution or concurrency of the underlying system.
• Sequential consistency: Sequential consistency guarantees that the execution order of operations is preserved as if they occurred in a sequential manner. The order of operations performed by any node is consistent with the order observed by other nodes in the system. However, sequential consistency does not guarantee the same instantaneous response as linearizability.
• Causal consistency: Causal consistency ensures that causally related operations are seen in the same order by all nodes in the system. It preserves the causal dependencies between operations, even if they are not directly related to each other. Causal consistency provides a balance between strong consistency and scalability.

Consistency models in distributed databases:

Distributed databases often employ various consistency models based on the CAP theorem trade-offs and application requirements. Some common consistency models include:

• Read-your-writes consistency: Guarantees that any read operation by a client will return the latest value that it has written. This consistency model ensures that a client sees its own writes immediately.
• Monotonic read consistency: Ensures that if a client performs a sequence of read operations, it will not observe older versions of data after seeing a newer version. This consistency model provides a guarantee of progress in reading the latest data.
• Read-after-write consistency: Ensures that if a client writes a value to a distributed database, any subsequent read operation from the same client will return that written value. This consistency model guarantees that the client will see its own writes.

Availability and Partition Tolerance:

Understanding availability and fault tolerance:

• Availability: Availability refers to the ability of a system to remain operational and respond to client requests even in the presence of failures or network disruptions. An available system ensures that clients can access the system and receive responses within an acceptable timeframe.
• Fault tolerance: Fault tolerance is the ability of a system to continue operating and providing services in the presence of hardware or software failures. Fault-tolerant systems are designed to detect and recover from failures, ensuring continuous availability.

Network partitions and their impact on system behavior:

A network partition occurs when a distributed system is divided into separate subgroups due to a network failure or communication breakdown. In the presence of a partition, nodes in different subgroups cannot communicate with each other.

Network partitions can have significant impacts on system behavior:

• Split-brain: In a network partition, if the system does not have proper mechanisms to detect and handle partitions, it can lead to a split-brain scenario where each subgroup continues to operate independently, potentially causing conflicts and inconsistencies when the partition is resolved.
• Inconsistencies and conflicts: Network partitions can result in divergent views of data among subgroups. Updates made in one subgroup may not be immediately visible to other subgroups, leading to data inconsistencies and conflicts during reconciliation.

Strategies for handling network partitions:

To handle network partitions and maintain system functionality, various strategies can be employed:

• Quorum-based consistency: Quorum-based approaches ensure that a minimum number of nodes in a distributed system need to agree on an operation before it is considered successful. This helps maintain consistency during partitions by requiring a majority of nodes to agree on updates.
• Partition detection and healing: Implementing mechanisms to detect network partitions and automatically reconcile the system when the partition is resolved can help minimize the impact of partitions. Techniques such as distributed consensus algorithms or heartbeat-based monitoring can be used.
• Hybrid consistency models: Some systems adopt hybrid consistency models, where different consistency levels are applied based on the presence or absence of partitions. During normal operation, strong consistency can be maintained, while during partitions, eventual consistency or relaxed consistency models can be employed.

CAP Theorem in Distributed Systems:

Designing distributed systems with CAP theorem considerations:

When designing distributed systems, it is essential to consider the trade-offs presented by the CAP theorem:

• Understanding application requirements: Analyze the application’s needs in terms of consistency, availability, and partition tolerance. Determine which trade-offs are acceptable and prioritize the requirements accordingly.
• Choosing an appropriate consistency model: Select a consistency model that aligns with the application’s needs. Consider factors such as data integrity requirements, latency tolerance, and scalability.
• Replication and data distribution: Determine the replication strategy and data distribution approach based on the desired consistency and availability guarantees. Replicate data across multiple nodes to enhance fault tolerance and provide high availability.
• Handling partitions: Implement partition detection mechanisms and strategies to handle network partitions. This may involve using consensus protocols, quorum systems, or conflict resolution techniques to ensure consistency and availability during and after partitions.
• Data synchronization and conflict resolution: Establish mechanisms to synchronize data across replicas and resolve conflicts that may arise due to eventual consistency. Techniques like vector clocks, versioning, or conflict-free replicated data types (CRDTs) can be employed.

CAP theorem implications for system architecture and data storage:

The CAP theorem has implications for the architecture and data storage choices in distributed systems:

• Replication and consistency trade-offs: The choice of replication and consistency models directly affects system performance and availability. Strong consistency requires coordination and can introduce additional latency, while eventual consistency provides higher availability but may result in temporary data divergence.
• Data partitioning and scalability: Sharding and partitioning data across multiple nodes enable scalability but introduce challenges in maintaining consistency across partitions. The sharding strategy and key selection play crucial roles in balancing data distribution and query performance.
• Hybrid architectures: In some cases, hybrid architectures that combine different data storage technologies can be employed to optimize for specific use cases. For example, using a combination of a strongly consistent database and an eventually consistent cache can provide a balance between consistency and availability.

Database Schema Design:

Introduction to Database Schema Design:

Database schema design is the process of defining the structure, relationships, and constraints of a database. It plays a critical role in data organization, integrity, and performance.

Goals and principles of good schema design:

• Data organization: A well-designed schema organizes data in a logical and efficient manner, ensuring that related information is stored together and can be easily accessed.
• Data integrity: The schema should enforce data integrity constraints, such as primary key, foreign key, and unique constraints, to maintain data accuracy and consistency.
• Query performance: Schema design impacts query performance. By properly defining indexes, optimizing table relationships, and denormalizing data when necessary, the schema can enhance query execution efficiency.
• Scalability and flexibility: A good schema design allows for future scalability and accommodates changes in data requirements without significant disruptions or structural modifications.

Factors to consider when designing a database schema:

• Understand the data: Gain a thorough understanding of the data entities, attributes, and relationships involved in the application domain. This analysis helps identify the primary entities and their key attributes.
• Normalize the data: Apply normalization techniques to eliminate data redundancy and anomalies. Normalization forms (such as 1NF, 2NF, and 3NF) help structure the data and improve data integrity.
• Denormalization for performance: Consider denormalization selectively to optimize query performance. Denormalization involves duplicating or grouping data to reduce the need for complex joins or expensive calculations during queries.
• Relationship establishment: Define relationships (one-to-one, one-to-many, many-to-many) between entities using foreign keys. This ensures data consistency and enables efficient data retrieval.

Entity-Relationship (ER) Modeling:

ER modeling is a popular technique for database schema design. It represents the entities, attributes, and relationships of a system using entity-relationship diagrams (ERDs).

• Entities: Entities represent real-world objects or concepts that are stored in the database. Each entity is described by its attributes, which capture specific properties or characteristics.
• Attributes: Attributes are properties or characteristics of an entity. They provide additional information and describe the data associated with an entity.
• Relationships: Relationships establish connections between entities, representing how they interact or associate with each other. Relationships can be classified as one-to-one, one-to-many, or many-to-many, depending on the cardinality of the association between entities.
• Cardinality: Cardinality defines the number of occurrences of one entity that are associated with another entity in a relationship. It can be expressed as one-to-one (1:1), one-to-many (1:N), or many-to-many (N:M).

Normalization:

Introduction to data normalization forms (e.g., 1NF, 2NF, 3NF):

Normalization is the process of organizing data in a database to minimize redundancy, dependency, and anomalies. It helps improve data integrity, reduce storage space, and simplify data manipulation.

1. First Normal Form (1NF): In 1NF, data is organized into tables with atomic values. Each attribute contains only a single value, and there are no repeating groups or arrays.
2. Second Normal Form (2NF): 2NF builds upon 1NF and eliminates partial dependencies. It requires that every non-key attribute is fully dependent on the primary key and not on any subset of it.
3. Third Normal Form (3NF): 3NF further refines the schema design by eliminating transitive dependencies. It ensures that no non-key attribute depends on another non-key attribute through a chain of dependencies.

Decomposition and elimination of data redundancy:

Decomposition is the process of breaking down a table into multiple tables to eliminate redundancy and ensure data integrity. Redundancy occurs when the same data is stored in multiple places, leading to data inconsistency and increased storage requirements.

To eliminate redundancy, tables can be split based on functional dependencies and relationships. Common techniques include identifying candidate keys, creating separate tables for related entities, and using foreign keys to establish relationships between tables.

Benefits and trade-offs of normalization:

Normalization offers several benefits, including:

• Data integrity: Normalization helps maintain data integrity by reducing redundancy, ensuring consistency, and minimizing update anomalies.
• Efficient storage: By eliminating redundant data, normalization optimizes storage space and reduces data duplication.
• Simplified data manipulation: Normalized schemas provide clear data structures and relationships, making it easier to write queries, perform updates, and maintain the database.

However, normalization also has trade-offs:

• Increased complexity: Highly normalized schemas may require more complex joins and queries to retrieve data, potentially impacting performance.
• Update performance: As data is distributed across multiple tables, updating related information may require more complex operations.

Denormalization and Performance Optimization:

Denormalization techniques for improving query performance:

Denormalization is the process of intentionally introducing redundancy into a schema to improve query performance. It involves selectively combining tables or duplicating data to optimize read operations.

Common denormalization techniques include:

• Flattening tables: Combining multiple related tables into a single table to reduce the need for joins and simplify queries.
• Introducing redundant columns: Adding redundant columns to eliminate the need for joins or calculations during query execution.
• Creating summary tables: Generating pre-aggregated summary tables to improve the performance of complex queries or reports.

Trade-offs and considerations when denormalizing data:

While denormalization can improve query performance, it introduces trade-offs:

• Data redundancy: Denormalization increases data redundancy, which requires careful management to ensure data consistency and integrity.
• Increased storage requirements: Denormalization often leads to increased storage space as redundant data is introduced.
• Update anomalies: Redundant data can introduce update anomalies, where changes made to one instance of the data need to be propagated to all redundant instances.

Indexing and query optimization in denormalized schemas:

In denormalized schemas, indexing plays a crucial role in query optimization. Properly defined indexes can significantly improve query performance by facilitating efficient data retrieval.

Considerations for indexing in denormalized schemas include:

• Evaluate the trade-offs between index size and query performance. Too many indexes can slow down data modification operations while providing faster reads. Choose indexes strategically based on the query patterns and performance requirements.
• Monitor and update indexes regularly to ensure they remain effective as data changes over time. Outdated or unused indexes can negatively impact overall system performance.
• Consider the use of composite indexes that span multiple columns in denormalized schemas. Composite indexes can improve query performance for multi-column queries.

Schema Design Patterns:

Hierarchical data refers to data organized in a parent-child relationship. Two common schema design patterns for handling hierarchical data are:

1. Nested Sets: The nested sets model assigns each node in the hierarchy two additional attributes, “left” and “right,” representing the range of values within which the node exists. This approach allows efficient querying of subtrees and enables operations like finding descendants or ancestors of a node.
2. Adjacency List: The adjacency list model represents hierarchical relationships by storing a reference to the parent node within each child node. This pattern is simple to implement and understand but may require recursive queries for traversing the hierarchy.

Patterns for handling time series data, graph data, and document data:

1. Time Series Data: Time series data represents data points collected over time. A common schema design pattern for time series data is using a table with timestamped rows, where each row represents a data point. Additional columns can store attributes specific to the data series.
2. Graph Data: Graph data represents entities and their relationships. Graph databases such as Neo4j provide specialized schema designs for handling graph data efficiently. Nodes represent entities, and relationships connect the nodes to capture the associations between entities.
3. Document Data: Document-oriented databases like MongoDB are designed to handle document data. In this pattern, data is stored in a flexible schema, typically in JSON-like documents. The schema can evolve over time, allowing for dynamic and varied data structures.

That’s it for now!

Part 8 of Complete System Design Series

Keep learning and coding :)

Day 1 : SQL Basics and Kick start of Advanced SQL Series

Day 2 : SQL Basics, Query Structure, Built In functions Conditions

Day 3 : Most Important Commands, Joins and Filters

Day 4 : Set Theory Operations, Stored Procedures and CASE statements in SQL

Day 5 : Wildcards, Aggregation and Sequences in SQL

Day 6 : Subqueries, Group by, order by and Having clauses in SQL and Analytical Functions

Day 7 : Window Functions, Grouping Sets and Constraints in SQL

Day 8 : BigQuery Basics, SELECT, FROM, WHERE and Date and Extract in BigQuery

Day 9 : Common Expression Table, UNNEST Clause, SQL vs NoSQL Databases

Day 10 : Triggers, Pivot and Cursors in SQL

Day 11 : Views, Indexes and Auto Increment in SQL

Day 12 : Query optimizations, Performance tuning in SQL

Day 13 : Introduction to MySQL, PostgreSQL and Mongo DB, Comparison between MySQL and PostgreSQL and Mongo DB, Introduction to SQL and NoSQL Databases

Day 14 : MySQL in Depth

Day 15 : PostgreSQL inDepth

Anyways, For Day 15 of 15 days of Advanced SQL, we will cover —

PostgreSQL inDepth

Github for Advanced SQL that you can follow —

All the projects, data structures, algorithms, system design, Data Science and ML, Data Engineering, MLOps and Deep Learning videos will be published on our youtube channel ( just launched).

Subscribe today!

System Design Case Studies — In Depth

Design Instagram

Design Messenger App

Design Twitter

Design URL Shortener

Design Dropbox

Design Youtube

Design API Rate Limiter

Design Web Crawler

Design Facebook’s Newsfeed

Design Yelp

Design Uber

Design Tinder

Design Tiktok

Design Whatsapp

Most Popular System Design Questions

Mega Compilation : Solved System Design Case studies

Complete Data Structures and Algorithm Series

Complexity Analysis

Backtracking

Sliding Window

Greedy Technique

Two pointer Technique

Arrays

Linked List

Strings

Stack

Queues

Hash Table/Hashing

Binary Search

1- D Dynamic Programming

Divide and Conquer Technique

Recursion

Github —

Some of the other best Series —

30 Days of Natural Language Processing ( NLP) Series

60 days of Data Science and ML Series with projects

30 days of Data Structures and Algorithms and System Design Simplified

60 Days of Deep Learning with Projects Series

Data Science and Machine Learning Research ( papers) Simplified **

100 days : Your Data Science and Machine Learning Degree Series with projects

23 Data Science Techniques You Should Know

Tech Interview Series — Curated List of coding questions

Complete System Design with most popular Questions Series

Complete Data Visualization and Pre-processing Series with projects

Complete Python Series with Projects

Complete Advanced Python Series with Projects

Kaggle Best Notebooks that will teach you the most

Complete Developers Guide to Git

All the Data Science and Machine Learning Resources

210 Machine Learning Projects

30 days of Machine Learning Ops

Tech Newsletter —

If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :

For Python Projects —

For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML

Follow for more updates. Stay tuned and keep coding!

For other projects, tune to —

Build Machine Learning Pipelines( With Code)

Recurrent Neural Network with Keras

Clustering Geolocation Data in Python using DBSCAN and K-Means

Facial Expression Recognition using Keras

Hyperparameter Tuning with Keras Tuner

Custom Layers in Keras