Sharding - Relational Postgre,Oracle complex , Non-Relational its simple, Design Challenges in sharding, Consistent Hashing

 Not exactly. Sharding is useful for both relational and non-relational databases, but it is generally more complex to implement in relational databases. MongoDB is well known for built-in sharding.

🔥 Ramesh Style

Think of sharding as:

One huge database → split data across multiple database servers.

Suppose we have 1 billion customers.

Without sharding

              Application
                   |
                   ↓
             ┌───────────┐
             │ DB Server │
             │ 1 Billion │
             │ customers │
             └───────────┘

Problems:

CPU  → 🔴
RAM  → 🔴
Storage → 🔴
I/O → 🔴

With sharding

                 Application
                     |
             Sharding Router
                     |
       ┌─────────────┼─────────────┐
       ↓             ↓             ↓
   DB Shard 1    DB Shard 2    DB Shard 3
   Customer      Customer      Customer
   1-10M         10M-20M       20M-30M

Now the workload is distributed.

---

Relational DB — Can we shard?

Yes. Absolutely.

For example, PostgreSQL, MySQL, Oracle, etc. can be sharded using different approaches/tools.

But the challenge is relational relationships.

Suppose:

CUSTOMER
---------
customer_id
name

ORDER
---------
order_id
customer_id
amount

If we shard by customer_id:

Shard 1
Customer 1-1M
Orders for those customers

Shard 2
Customer 1M-2M
Orders for those customers

Good if most queries are:

SELECT *
FROM orders
WHERE customer_id = 123;

But consider:

SELECT *
FROM customer c
JOIN orders o
ON c.customer_id = o.customer_id
WHERE ...

If related data is spread across shards, you may need:

Application
    ↓
Shard 1 ─────┐
             ├── Distributed JOIN
Shard 2 ─────┘

That becomes expensive and complicated.

---

MongoDB — Why sharding feels more natural

MongoDB was designed around documents, rather than relational tables and joins.

Example:

{
  "customerId": 101,
  "name": "Ramesh",
  "orders": [
    {"orderId": 1, "amount": 500},
    {"orderId": 2, "amount": 800}
  ]
}

You can shard using a shard key, for example:

customerId

Then:

customerId 1-1M
       ↓
   Shard 1

customerId 1M-2M
       ↓
   Shard 2

customerId 2M-3M
       ↓
   Shard 3

MongoDB provides built-in distributed sharding infrastructure.

---

⭐ Why MongoDB is commonly associated with sharding

Because MongoDB provides:

MongoDB
   |
   ├── Shard
   ├── Shard
   ├── Shard
   |
   ├── Config Servers
   |
   └── mongos routers

Conceptually:

Application
     |
     ↓
  mongos
     |
     ├────────→ Shard 1
     ├────────→ Shard 2
     └────────→ Shard 3

The router determines which shard owns the relevant data.

---

🔥 Important distinction

Don't say in an interview:

❌ "Sharding is not useful for relational databases."

Say:

✅ "Sharding is applicable to both relational and NoSQL databases. However, relational databases can make distributed joins, transactions, foreign keys and cross-shard consistency more complicated. MongoDB has built-in sharding capabilities and its document model can make certain sharding patterns more natural."

That's a much stronger Senior Architect answer.

---

Sharding vs Replication

Another very important interview distinction:

Replication

Same data copied to multiple nodes:

             Master
           /        \
          ↓          ↓
      Replica 1   Replica 2

Same data

Purpose:

HA
Read scaling
Disaster recovery

Sharding

Different data on different nodes:

Shard 1 → Customers 1-1M
Shard 2 → Customers 1M-2M
Shard 3 → Customers 2M-3M

Purpose:

Horizontal data scaling
Horizontal write scaling
Storage scaling

Easy memory trick

Replication = copy the data.
Sharding = split the data.

And in real production systems, you often combine them:

                Cluster
                   |
       ┌───────────┼───────────┐
       ↓           ↓           ↓
    Shard 1     Shard 2     Shard 3
      / \         / \         / \
     R1  R2      R1  R2      R1  R2

Sharding + Replication = scale + high availability.

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

Design challengs - data access/data access pattern challenges in sharding.

📚 Sharding — Class Notes | Ramesh Style

1. What is Sharding?

Sharding means horizontally partitioning data across multiple database servers (shards).

Instead of keeping all data in one DB:

                    Application
                         |
                         ↓
                  Single Database
                 1 Billion Records

we distribute it:

                     Application
                          |
                    Shard Router
              ┌───────────┼───────────┐
              ↓           ↓           ↓
           Shard 1      Shard 2      Shard 3
          Users 1-1M   Users 1M-2M   Users 2M-3M

🎯 Main purpose

Sharding
   ↓
Horizontal Scaling
   ↓
More CPU + RAM + Storage + I/O
   ↓
Handle larger data and traffic

---

2. Sharding Key

A sharding key determines which shard stores a particular record.

Example:

customerId

Suppose:

customerId = 101

Routing logic:

customerId
     ↓
Shard Key
     ↓
Shard Router
     ↓
Shard 1

Another customer:

customerId = 2,500,000
        ↓
    Shard 3

Important

Choosing a good shard key is one of the most critical decisions in sharding.

A bad shard key can create a hot shard.

---

3. Complexity Introduced by Sharding

Without sharding:

Application
     |
     ↓
    DB

With sharding:

Application
     |
     ↓
Shard Router
     |
 ┌───┼────┐
 ↓   ↓    ↓
S1  S2    S3

Now the application/system must know:

• Which shard contains the data?

• How should requests be routed?

• What happens when a shard fails?

• How are connections managed?

• How are transactions handled across shards?

Therefore:

Sharding improves scalability but increases architectural complexity.

---

4. Shard Routing

Shard routing means determining the correct shard for a request.

Example:

GET customer 101
       ↓
customerId = 101
       ↓
Shard Key
       ↓
Shard Router
       ↓
Shard 1

For:

GET customer 2500000

the router might send it to:

Shard 3

Flow

Request
   ↓
Extract Sharding Key
   ↓
Calculate/lookup shard
   ↓
Route request
   ↓
Correct shard
   ↓
Response

---

5. Limited Data Model

Sharding can influence how you design your data model.

Suppose:

Customer
   |
   └── Orders

If both are stored on the same shard:

Shard 1
 ├── Customer 101
 └── Orders of Customer 101

queries are relatively easy.

But if they are on different shards:

Shard 1                  Shard 2
Customer                 Orders
   |                       |
   └──────── JOIN ─────────┘

Now we have a cross-shard operation.

This can be expensive.

---

6. Cross-Shard Join

Consider:

SELECT *
FROM customer c
JOIN orders o
ON c.customer_id = o.customer_id;

Without sharding:

Application
     ↓
     DB
     ↓
Customer JOIN Orders

With sharding:

                Query
                  |
          ┌───────┴───────┐
          ↓               ↓
       Shard 1          Shard 2
      Customer A        Orders B
          \               /
           \             /
            Cross-shard
               JOIN

This can cause:

More network calls
        ↓
More latency
        ↓
More complexity

Interview point

Cross-shard joins are generally expensive and should be minimized through data modeling, co-location, denormalization, or other design techniques.

---

7. Limited Data Access Patterns

Suppose we shard by:

userId

Then this query is excellent:

SELECT *
FROM orders
WHERE user_id = 101;

Because the system knows:

userId = 101
      ↓
   Shard 1

Only one shard needs to be queried.

This is called a targeted query.

---

But consider:

SELECT *
FROM orders
WHERE amount > 10000;

There is no userId.

Which shard contains the matching records?

The system may need:

             Query
               |
       ┌───────┼───────┐
       ↓       ↓       ↓
     Shard1  Shard2  Shard3
       ↓       ↓       ↓
     Result  Result  Result
       └───────┼───────┘
               ↓
             Merge

This is commonly called a scatter-gather query.

Result:

Multiple shards
      ↓
More network calls
      ↓
More processing
      ↓
Higher latency

---

8. Denormalization

One solution to expensive cross-shard queries is denormalization.

Instead of:

Customer
   |
   ↓
Orders

requiring a join, we may store commonly needed information together.

Example:

{
  "orderId": 101,
  "customerId": 500,
  "customerName": "Ramesh",
  "amount": 5000
}

Now the order query may not need to contact the Customer shard.

Trade-off

Denormalization
      ↓
Faster reads
      +
Less cross-shard querying
      ↓
But
      ↓
Duplicate data
      +
Consistency/update complexity

---

9. Caching

Another solution:

Application
     |
     ↓
   Cache
     |
     ↓
If not found
     |
     ↓
Multiple shards

For frequently requested cross-shard information:

Redis
 ↓
Cached result

can reduce expensive distributed queries.

---

10. Operational Challenges

Sharding doesn't end after deployment.

You now have:

Shard 1
Shard 2
Shard 3
Shard 4
...
Shard N

Each needs operational management.

Backup

Without sharding:

Backup DB

With sharding:

Backup Shard 1
Backup Shard 2
Backup Shard 3
...

---

11. Recovery

Suppose:

Shard 2 ❌

You need to recover:

Shard 2
   ↓
Replica / Backup
   ↓
Restore
   ↓
Rejoin system

The recovery strategy becomes more complicated as the number of shards increases.

---

12. Rebalancing

🔥 Very important concept.

Suppose initially:

Shard 1 → 30%
Shard 2 → 30%
Shard 3 → 40%

Application grows.

Now:

Shard 1 → 20%
Shard 2 → 20%
Shard 3 → 60% 🔴

Shard 3 becomes overloaded.

We need rebalancing.

Before:

Shard 1 → 30%
Shard 2 → 30%
Shard 3 → 40%

          ↓ Rebalance

After:

Shard 1 → 33%
Shard 2 → 33%
Shard 3 → 34%

This can involve moving large amounts of data.

---

13. Hot Shard

Bad shard-key selection can create a hot shard.

Example:

Shard key = country

Suppose:

India → 70% of users
USA   → 10%
UK    → 5%
Others → 15%

Then:

Shard India
████████████████████ 70% 🔥

Shard USA
██ 10%

Shard UK
█ 5%

One shard gets most of the traffic.

That's called a hotspot/hot shard.

Lesson

Good shard-key selection should distribute both data and workload.

---

14. Sharding + Replication

In real systems, we commonly combine both.

                    Cluster
                       |
          ┌────────────┼────────────┐
          ↓            ↓            ↓
       Shard 1      Shard 2      Shard 3
        /   \        /   \        /   \
       ↓     ↓      ↓     ↓      ↓     ↓
     Master Replica Master Replica Master Replica

Sharding gives:

Scalability

Replication gives:

High Availability

Therefore:

Sharding = split the data.
Replication = copy the data.

---

15. Key Limitations — Interview Table

Problem	Why?	Typical solution
More complexity	Multiple DB nodes	Sharding middleware/router
Cross-shard joins	Data distributed	Co-locate/denormalize
Scatter-gather queries	Query doesn't target one shard	Better shard key/indexing
Hot shard	Poor shard-key distribution	Choose better shard key
Rebalancing	Data grows unevenly	Automated rebalancing
Backup complexity	Multiple shards	Centralized backup strategy
Recovery complexity	Multiple failure domains	Replicas + automation
Distributed transactions	Data spans shards	Avoid where possible / use appropriate transaction design

---

⭐ Most Important Interview Concept: Shard Key

If interviewer asks:

"What is the biggest design consideration in sharding?"

Answer:

"Choosing the shard key."

A good shard key should ideally provide:

High cardinality
       +
Even distribution
       +
Good query targeting
       +
Low hotspot risk

For example:

userId
customerId
accountId

can be good candidates depending on the workload.

But a field like:

country

may create hotspots if one country dominates the traffic.

---

🧠 Complete Sharding Flow

                  APPLICATION
                       |
                       ↓
                 Shard Router
                       |
                 Sharding Key
                       |
              ┌────────┼────────┐
              ↓        ↓        ↓
           Shard 1  Shard 2  Shard 3
              |        |        |
              ↓        ↓        ↓
            Data     Data     Data

For a good targeted query:

Request
   ↓
userId = 101
   ↓
Shard Router
   ↓
Shard 1
   ↓
Response

For a bad/non-targeted query:

Request
   ↓
No shard key
   ↓
Shard 1 ──┐
Shard 2 ──┼──→ Scatter
Shard 3 ──┘
             ↓
           Gather
             ↓
           Merge
             ↓
         Response

---

🎯 Ramesh Interview Summary

Remember these 5 points:

1. Sharding
   ↓
   Split data horizontally

2. Shard Key
   ↓
   Determines where data goes

3. Cross-Shard Operations
   ↓
   Expensive and complex

4. Rebalancing
   ↓
   Required when data/workload becomes uneven

5. Sharding + Replication
   ↓
   Scalability + High Availability

🔥 One-line interview answer

"Sharding provides horizontal scalability by distributing data across multiple nodes, but it increases application and operational complexity. The biggest challenges are choosing the right shard key, avoiding hotspots, minimizing cross-shard joins and scatter-gather queries, and managing rebalancing, backup, recovery, and distributed transactions."

------

Read Replication will handle more read traffic, Sharding -  will handle more write traffic, Now we are going to talk on consisent hashing topic:

📚 Consistent Hashing & Replication — Class Notes

Ramesh Style | Distributed Systems

These two concepts are often used together in distributed databases, caches, and systems like Redis.

The easiest way to remember:

Consistent Hashing → Where should the data go?
Replication → How many copies of the data should we keep?

---

1. Consistent Hashing

Definition

Consistent hashing is a technique for distributing data across multiple nodes while minimizing data movement when nodes are added or removed.

Normal hashing:

hash(key) % numberOfNodes

looks simple, but it has a major problem.

---

2. Problem with Normal Hashing

Suppose we have 3 servers:

Server 0
Server 1
Server 2

We use:

hash(key) % 3

Suppose:

User A → hash = 10
User B → hash = 20
User C → hash = 30

Now add Server 3:

Server 0
Server 1
Server 2
Server 3

Now we calculate:

hash(key) % 4

Many keys get a different result.

Before:
Key A → Server 0
Key B → Server 1
Key C → Server 2

After:
Key A → Server 2
Key B → Server 0
Key C → Server 3

💥 A huge amount of data needs to move.

---

3. Consistent Hashing Solution

Instead of directly doing:

hash(key) % N

we create a hash ring.

Think of it like a clock:

                    0
              ┌───────────┐
          330 /             \ 30
             /               \
        300 |                 | 60
            |                 |
        270 |                 | 90
             \               /
          240 \             / 120
              └───────────┘
             210 180 150

The entire hash space forms a circle.

---

4. Put Servers on the Ring

Suppose:

Node A → hash position 50
Node B → hash position 150
Node C → hash position 270

Conceptually:

                    0
                    |
               Node A(50)
                    |
                    |
               Node B(150)
                    |
                    |
               Node C(270)
                    |
                    |
                  back to 0

---

5. Where does data go?

Hash the key.

Suppose:

hash("user:101") = 80

Find position 80 on the ring.

Move clockwise until you find a node.

             Node A
              50
               |
               | ← key = 80
               |
               ↓
             Node B
             150

Therefore:

user:101 → Node B

Memory trick:

Hash the key → put it on the ring → walk clockwise → first node owns the key.

---

6. What happens when a node is added?

Suppose:

Node A
Node B
Node C

Now add:

Node D

Node D gets a position on the ring.

        A
        |
        D   ← new node
        |
        B
        |
        C

Only the keys in the region affected by Node D need to move.

Before

Some keys → Node B

After

Some of those keys → Node D

Other keys remain where they were.

Therefore:

Only a relatively small portion of data needs to move.

This is the biggest advantage of consistent hashing.

---

7. Node Removal

Suppose:

A
B
C

Node B crashes:

A
B ❌
C

Keys previously assigned to B can move to the next node according to the ring.

Keys belonging to B
          ↓
      Next node
          ↓
          C

Again, we avoid reshuffling the entire dataset.

---

8. Virtual Nodes

🔥 Important interview concept.

If each physical server gets only one position:

A ---------------- B ---------------- C

distribution might not be perfectly balanced.

So we create virtual nodes.

Instead of:

Server A → one position

we use:

Server A
 ├── A1
 ├── A2
 ├── A3
 ├── A4
 └── A5

Similarly:

Server B → B1 B2 B3 B4 B5
Server C → C1 C2 C3 C4 C5

Ring:

A1 → B1 → C1 → A2 → B2 → C2 → A3 → ...

This improves load distribution.

Why?

Because each physical server owns multiple small regions instead of one large region.

---

9. Benefits of Consistent Hashing

① Dynamic scalability

Add nodes:

Node A
Node B
Node C

       ↓ Add Node D

Node A
Node B
Node C
Node D

Only part of the data moves.

---

② Less data movement

Normal hashing:

Node count changes
      ↓
Many keys remapped
      ↓
Huge data movement

Consistent hashing:

Node count changes
      ↓
Limited keys remapped
      ↓
Less data movement

---

③ Better availability

When combined with replication:

Consistent Hashing
       +
Replication
       ↓
Scalable + Fault Tolerant

---

10. Replication

Now let's understand the second concept.

Replication means maintaining multiple copies of the same data on different nodes.

Example:

             Data
              |
        ┌─────┴─────┐
        ↓           ↓
     Node A       Node B
     Copy 1       Copy 2

If Node A fails:

Node A ❌

Node B ✅
Copy available

This improves availability and fault tolerance.

---

11. Why do we need Replication?

Without replication:

User Data
    ↓
Node A
    ↓
Node A crashes
    ↓
💥 Data unavailable

With replication:

User Data
   |
 ┌─┴────┐
 ↓      ↓
A       B
Copy   Copy

If A crashes:

A ❌

B ✅

The application can continue using B depending on the system's architecture.

---

12. Synchronous Replication

Suppose:

Client
  |
  | WRITE
  ↓
Primary
  |
  ├────────→ Replica 1
  |
  └────────→ Replica 2

The write is considered successful only after required replicas acknowledge it.

Client
  ↓
Primary
  ↓
Replica 1 ✅
  ↓
Replica 2 ✅
  ↓
ACK to Client

Advantage

Stronger consistency.

Disadvantage

Higher latency.

If a replica is slow:

Primary
   ↓
Replica slow 🐌
   ↓
Client waits

---

13. Asynchronous Replication

Here:

Client
  |
  ↓
Primary
  |
  ↓
ACK immediately
  |
  ↓
Client continues

Meanwhile:
Primary → Replica

Flow:

Client
   ↓
Primary
   ↓
ACK ✅
   ↓
Client

Primary
   ↓
Replica
   ↓
Replication later

Advantage

Lower latency and better availability.

Risk

If primary crashes before replication:

Primary
   |
   | New data
   ↓
❌ Crash

Replica
   |
   ↓
Doesn't have latest data

Potential data loss.

---

14. Synchronous vs Asynchronous

Feature	Synchronous	Asynchronous
Write acknowledgement	After required replicas confirm	Primary can acknowledge first
Consistency	Stronger	Eventual
Latency	Higher	Lower
Availability	Can be reduced if replicas unavailable	Generally better
Risk of lost recent writes	Lower	Higher

Memory trick:

Sync = Wait for replicas.
Async = Don't wait for replicas.

---

15. Master-Slave / Primary-Replica

Common architecture:

             Primary
                |
       ┌────────┼────────┐
       ↓        ↓        ↓
   Replica 1 Replica 2 Replica 3

Writes:

Client
  ↓
Primary

Reads may be served by replicas depending on consistency requirements:

Client
  ↓
Replica

If primary fails:

Primary ❌
   ↓
Failover
   ↓
Replica promoted
   ↓
New Primary

This connects directly to your Redis Sentinel topic.

---

16. Consistent Hashing + Replication Together

🔥 This is the most important architecture to understand.

Suppose:

                 Hash Ring
        ┌────────────────────────┐
        │                        │
      Node A                   Node B
      Primary                 Primary
        │                        │
      A-Replica                B-Replica
        │                        │
        └────────────────────────┘

Consistent hashing decides:

Which node owns this key?

Replication decides:

Where should copies of this key exist?

So:

                DATA
                  |
        ┌─────────┴─────────┐
        ↓                   ↓
Consistent Hashing       Replication
        ↓                   ↓
Which node?             How many copies?
        ↓                   ↓
Partition data          Fault tolerance

---

17. Failure Example

Suppose:

Key = user:101

Hash
 ↓
Node B

Replication factor = 3:

user:101
   |
   ├── Node B
   ├── Node C
   └── Node D

Now:

Node B ❌

Copies remain:

Node C ✅
Node D ✅

So data remains available.

---

18. Node Addition Example

Initially:

A
B
C

Add D:

A
B
C
D

Consistent hashing:

Only affected hash ranges
        ↓
Move some data
        ↓
D

Replication then ensures the moved data continues to have the required number of copies.

---

19. Challenges

A. Node Failure

Node A ❌
    ↓
Detect failure
    ↓
Promote replica / route elsewhere

Need:

• Failure detection

• Failover

• Data recovery

• Replica synchronization

---

B. Replication Overhead

Suppose:

Original data = 1 TB
Replication factor = 3

Approximate storage requirement:

1 TB × 3
   =
3 TB

Plus network traffic for replication.

So replication improves reliability but costs:

Storage
+
Network bandwidth
+
CPU

---

20. CAP Connection

This connects directly to what we just studied.

Replication
     ↓
Multiple copies
     ↓
Network partition
     ↓
Replicas may disagree
     ↓
Consistency vs Availability trade-off

For example:

Primary
   X
Replica

If they cannot communicate:

Choose availability

Continue serving requests:

Replica → accepts operations

But state may diverge.

Choose consistency

Stop/reject unsafe operations:

Replica → reject

Availability is reduced.

---

🧠 Complete Class Diagram

                 DISTRIBUTED DATABASE
                         |
              ┌──────────┴──────────┐
              ↓                     ↓
       CONSISTENT HASHING       REPLICATION
              ↓                     ↓
       Where data goes?       How many copies?
              ↓                     ↓
        Hash Ring             Primary + Replicas
              ↓                     ↓
       Shard selection         Fault tolerance
              ↓                     ↓
       Add/remove node         Node failure
              ↓                     ↓
      Minimal data movement    High availability
              |
              ↓
       Virtual Nodes
              ↓
       Better load balance

---

🎯 Interview Questions

Q1. What problem does consistent hashing solve?

It minimizes data redistribution when nodes are added or removed from a distributed system.

---

Q2. How does consistent hashing work?

Keys and nodes are mapped onto a hash ring. A key is assigned to the next node clockwise in the ring. When nodes change, only the affected portion of the keyspace needs to be remapped.

---

Q3. Why use virtual nodes?

Virtual nodes assign multiple positions to each physical node, improving load distribution and reducing hotspots.

---

Q4. What is replication?

Maintaining multiple copies of data across different nodes to improve availability and fault tolerance.

---

Q5. Synchronous vs asynchronous replication?

Synchronous replication waits for required replica acknowledgements before confirming the write, providing stronger consistency but higher latency. Asynchronous replication acknowledges earlier and replicates later, providing lower latency but a greater possibility of losing recent writes.

---

Q6. What happens when a node fails?

Node fails
    ↓
Failure detection
    ↓
Replica available?
    ↓
Yes
    ↓
Failover / rerouting
    ↓
Continue serving

---

⭐ Final Ramesh Memory Trick

Remember these four questions:

Consistent Hashing
      ↓
"WHERE?"
      ↓
Which node should store my data?


Replication
      ↓
"HOW MANY?"
      ↓
How many copies should I maintain?


Sharding
      ↓
"HOW TO SPLIT?"
      ↓
How do I distribute the dataset?


Failover
      ↓
"WHAT IF NODE DIES?"
      ↓
How do I continue serving?

🔥 One-line interview answer

"Consistent hashing determines where data should be placed with minimal redistribution when nodes change, while replication maintains multiple copies of that data for fault tolerance and availability. Together they provide a foundation for scalable and highly available distributed systems."