Consisten Hashing - Basically from dynamo concept - Talking Main concept of R+W > N configuration part.

 

📚 Class Notes: Consistent Hashing Replicas + R + W > N

Ramesh Style | Distributed Systems

This concept is very important for understanding Dynamo-style distributed databases, Cassandra-like systems, quorum reads/writes, and distributed consistency.

The easiest way to remember:

N = How many copies?
W = How many copies must confirm a WRITE?
R = How many copies must respond to a READ?

---

1. Replicas in Consistent Hashing

Consistent hashing answers:

"Which nodes are responsible for this key?"

Replication adds:

"Don't store the key on only one node; keep multiple copies."

Suppose:

Key = customer:101

Hash the key:

customer:101
      ↓
    hash()
      ↓
   Ring position
      ↓
   Node A

If replication factor is 3:

             Hash Ring

              Node A
                ↓
             Primary
                |
                ↓
             Node B
             Replica
                |
                ↓
             Node C
             Replica

So:

customer:101

     ┌─────────────┐
     ↓             ↓
  Node A         Node B         Node C
  Copy 1         Copy 2         Copy 3

---

2. Why Multiple Replicas?

Suppose:

Node A ❌

Without replication:

Data
 ↓
Node A ❌
 ↓
Unavailable

With replication:

              customer:101
             /      |      \
            ↓       ↓       ↓
          Node A  Node B  Node C
             ❌      ✅      ✅

The data is still available from B or C.

Therefore:

Replication provides fault tolerance and improves availability.

---

3. What is N?

N = total number of replicas for the data.

Suppose:

N = 3

means:

Key
 |
 ├── Replica 1
 ├── Replica 2
 └── Replica 3

If:

N = 5

then:

Key
 |
 ├── R1
 ├── R2
 ├── R3
 ├── R4
 └── R5

---

4. What is W?

W = Write quorum.

It means:

How many replicas must acknowledge a write before the system tells the client "write successful"?

Suppose:

N = 5
W = 3

Client writes:

             WRITE
               |
               ↓
        ┌──────┼──────┐
        ↓      ↓      ↓
       R1     R2     R3
       ACK    ACK    ACK

Once 3 required replicas acknowledge:

W = 3
   ↓
WRITE SUCCESS

Other replicas may catch up asynchronously, depending on the system.

---

5. What is R?

R = Read quorum.

It means:

How many replicas must respond to satisfy a read?

Suppose:

N = 5
R = 3

A read goes to replicas:

READ
  |
  ├── R1 → value
  ├── R2 → value
  └── R3 → value

Once 3 required replicas respond:

R = 3
   ↓
READ SUCCESS

Depending on the database, the system may compare returned versions/timestamps and select the latest value.

---

6. The Famous Formula

🔥 Remember:

             R + W > N

Why?

Because if:

R + W > N

then the set of replicas participating in a read and the set participating in a write must overlap.

That overlap is what helps provide stronger read-after-write consistency under the assumptions of the particular database/protocol.

---

7. Simple Example

Suppose:

N = 5
R = 3
W = 3

Calculate:

R + W
= 3 + 3
= 6

6 > 5

Therefore:

R + W > N

✅ True.

---

8. Visualize the Overlap

Five replicas:

R1   R2   R3   R4   R5

Write requires 3:

WRITE

R1   R2   R3
██   ██   ██

Read requires 3:

READ

             R3   R4   R5
             ██   ██   ██

There is an overlap:

WRITE → R1 R2 R3
READ  →       R3 R4 R5
              ↑
           OVERLAP

R3 participated in both.

That's the intuition behind:

R + W > N

---

9. What if R + W <= N?

Suppose:

N = 5
R = 2
W = 2

Then:

R + W = 4

4 > 5 ❌

There is no mathematical guarantee that the read quorum and write quorum overlap.

For example:

WRITE → R1 R2

READ  → R4 R5

No overlap.

R1 R2      R3      R4 R5
██ ██              ██ ██
↑                   ↑
WRITE              READ

The read might not contact any replica that acknowledged the latest write.

Therefore it can potentially return stale data, depending on the database's consistency protocol.

---

10. Important Example — N=5

Let's compare configurations.

Configuration A

N = 5
R = 3
W = 3

3 + 3 > 5

✅ Stronger consistency relationship.

---

Configuration B

N = 5
R = 1
W = 5

1 + 5 > 5

✅ Read is very fast.

Every successful write requires all 5 replicas.

---

Configuration C

N = 5
R = 5
W = 1

5 + 1 > 5

✅ Every read checks all 5.

Writes can be fast because only one acknowledgement is required.

But this configuration has different availability/latency characteristics.

---

11. Consistency vs Availability

This is where CAP comes back.

Increasing:

R ↑
W ↑

generally means:

More replicas involved
       ↓
Potentially stronger consistency
       ↓
But higher latency / lower availability

Reducing them:

R ↓
W ↓
       ↓
Fewer replicas required
       ↓
Lower latency
       ↓
Better availability
       ↓
Potentially weaker consistency

So there is a trade-off.

---

12. Failure Example

Suppose:

N = 5
R = 3
W = 3

Two replicas fail:

R1 ❌
R2 ❌
R3 ✅
R4 ✅
R5 ✅

We still have:

3 available replicas

So:

READ → 3 replicas → possible
WRITE → 3 replicas → possible

The system can continue, assuming the particular implementation permits those operations under that failure state.

---

13. Three Replicas Fail

Now:

R1 ❌
R2 ❌
R3 ❌
R4 ✅
R5 ✅

Available:

2 replicas

But:

R = 3
W = 3

We can't reach the quorum.

Therefore:

READ  → ❌
WRITE → ❌

Availability is sacrificed to maintain the configured quorum requirement.

---

14. Very Important: R + W > N Is Not Magic

Interviewers may appreciate this nuance.

The formula provides a quorum overlap condition, but real consistency depends on:

• How versions are tracked

• Conflict resolution

• Read repair

• Hinted handoff

• Anti-entropy repair

• Failure detection

• Network partitions

• The database's exact consistency protocol

So don't say:

❌ "R + W > N guarantees perfect consistency."

Better:

✅ "R + W > N guarantees that the read and write quorums overlap, which helps ensure that a read contacts at least one replica involved in the successful write, subject to the database's consistency and conflict-resolution mechanisms."

That's the architect-level answer.

---

15. R + W + N — Easy Memory

              N
              ↓
      Total replicas
              |
       ┌──────┴──────┐
       ↓             ↓
      W              R
      ↓              ↓
  Write quorum   Read quorum
       |             |
       └──────┬──────┘
              ↓
          R + W > N
              ↓
        Quorum overlap
              ↓
       Stronger consistency

---

16. Connection with Consistent Hashing

Now combine the two concepts.

Step 1 — Consistent hashing

Key
 ↓
Hash
 ↓
Hash Ring
 ↓
Primary node + next nodes

Step 2 — Replication

Key
 |
 ├── Node A
 ├── Node B
 └── Node C

Step 3 — Quorum

N = 3

W = 2
R = 2

R + W = 4

4 > 3

Therefore:

Consistent Hashing
       ↓
Find replica nodes
       ↓
Replication
       ↓
N copies
       ↓
Quorum
       ↓
R + W > N
       ↓
Read/Write overlap

---

⭐ Interview Class Notes

What is N?

Total number of replicas maintained for a key.

What is W?

Number of replicas that must acknowledge a write before it is considered successful.

What is R?

Number of replicas that must respond to satisfy a read.

What does R + W > N mean?

The read and write quorums must overlap, helping prevent a successful read from completely missing the replicas that acknowledged the latest write.

Example

N = 5
R = 3
W = 3

3 + 3 > 5
6 > 5

✅ Quorum overlap.

---

🧠 Ramesh Final Memory Trick

Think of 5 teachers holding copies of your marks:

Teacher 1
Teacher 2
Teacher 3
Teacher 4
Teacher 5

N

"How many teachers have a copy?"

N = 5

W

"How many teachers must confirm my new marks?"

W = 3

R

"How many teachers do I ask when checking my marks?"

R = 3

Because:

R + W > N
3 + 3 > 5

there must be some overlap between the teachers who confirmed the update and the teachers you ask when reading.

🔥 Remember:

N = Copies
W = Write confirmations
R = Read confirmations
R + W > N = Read/Write quorum overlap