Sunday, 23 August 2026

Ramesh Style - 📚 Consistent Hashing, Replication & Tunable Consistency - Class Notes

 

Ramesh Style | Interview Preparation

Explains how consistent hashing + replication leads to a tunable consistency model, using the coffee-shop/barista analogy.

1. Replication — Why Do We Need It?

Suppose our data is:

customer:101
favoriteCoffee = Cappuccino

Instead of keeping it on only one node:

Node A
  |
  └── customer:101

we keep multiple copies:

              customer:101
                    |
        ┌───────────┼───────────┐
        ↓           ↓           ↓
      Node A      Node B      Node C
      Copy 1      Copy 2      Copy 3

Why?

Redundancy. If one node fails, another copy can serve the data.

The source describes the replicas as peers, rather than a traditional master/subordinate arrangement; each independently owns a copy of the data.

2. The New Problem: Consistency

Replication solves:

Node failure
     ↓
Data still available

But creates another problem:

Replication
     ↓
Multiple copies
     ↓
Can all copies have the same value?

Example:

Node A → Cappuccino ✅
Node B → Cappuccino ✅
Node C → Coffee ❌

Node C didn't receive the latest update.

Now the system has to answer:

When is a write considered successful?

and:

How many replicas should agree before accepting a read?

The source explicitly identifies this as the consistency problem created by replication.

3. Eventual Consistency

Suppose:

Client
  |
  ↓
Node A
  |
  ├── Node B
  └── Node C

Client updates:

favoriteCoffee = Espresso

Initially:

A → Espresso
B → Espresso
C → Cappuccino

After replication catches up:

A → Espresso
B → Espresso
C → Espresso

So the replicas may temporarily disagree, but eventually converge.

This is:

Eventual Consistency

The source explains that if we choose low-latency operations, we may explicitly tolerate stale reads until replication catches up.

4. R + W > N

This is the key formula:

                 R + W > N

Where:

N = Number of replicas

Example:

N = 3
        Data
       / | \
      A  B  C

W = Write quorum

Number of replicas that must successfully receive/acknowledge the write.

W = 2

R = Read quorum

Number of replicas that must participate in the read.

R = 2

The source defines these exactly in terms of replicas involved in reads and successful writes.

5. Example: N=3, W=2, R=2

Calculate:

R + W > N

2 + 2 > 3

4 > 3 ✅

Therefore, the read and write quorums must overlap.

Write

             WRITE
               |
       ┌───────┼───────┐
       ↓       ↓       ↓
      A ✅     B ✅     C

Two replicas acknowledge:

W = 2

Write succeeds.

Later, read from two replicas:

             READ
               |
       ┌───────┼───────┐
       ↓       ↓       ↓
      A ✅     B ✅     C

Because:

2 + 2 > 3

there must be overlap between the read and write sets.

The source uses exactly this two-out-of-three example to explain strong consistency.

6. Low-Latency Configuration

Suppose:

N = 3
W = 1
R = 1

Then:

R + W
= 1 + 1
= 2

2 > 3 ❌

No quorum overlap is guaranteed.

Write

Client
  ↓
Node A ✅
  ↓
ACK immediately

The client doesn't wait for B and C.

Later:

A → new value
B → old value
C → old value

If the next read happens to hit B:

READ → Node B
         ↓
     old value

So the read can be stale.

The benefit is:

Very low latency.

The cost is:

Eventual rather than guaranteed immediate consistency.

The source explicitly describes 1 + 1 <= 3 as choosing low latency while accepting the possibility of stale reads.

7. The Trade-Off

This is the most important architectural idea.

Stronger consistency

R ↑
W ↑
   ↓
More replicas involved
   ↓
More waiting
   ↓
Higher latency

Lower latency

R ↓
W ↓
   ↓
Fewer replicas involved
   ↓
Faster response
   ↓
Possible stale reads

So:

             Consistency
                  ↑
                  |
                  |
                  |
                  |
                  +────────────→ Latency

You are effectively choosing the behavior appropriate for your application.

8. Tunable Consistency

One of the powerful ideas in this architecture is:

The application can choose its consistency semantics by selecting appropriate R and W values.

For example:

Stronger consistency

N = 3
R = 2
W = 2

2 + 2 > 3

Lower latency

N = 3
R = 1
W = 1

1 + 1 <= 3

So:

Application Requirement
          ↓
Choose R and W
          ↓
Consistency ↔ Latency trade-off

The source calls this a tunable consistency model that emerges from the architecture.

9. What Happens If Replicas Disagree?

Suppose:

Node A → Espresso
Node B → Espresso
Node C → Cappuccino

Now what?

The database needs mechanisms to resolve the disagreement.

The exact solution is implementation-specific; the source notes that different Dynamo-style/consistent-hash databases can solve this differently.

So in an interview:

Don't claim that every consistent-hashing database resolves conflicts in exactly the same way.

10. Entropy Problem

🔥 Important term from the source.

Suppose:

Node A → Espresso
Node B → Espresso
Node C → Cappuccino

C is behind.

The replicas are no longer synchronized.

This divergence is called:

Entropy

The source describes entropy as the situation where one replica is out of date relative to another.

Goal

Replica A ─┐
Replica B ─┼──→ Same state
Replica C ─┘

The system needs repair/synchronization mechanisms to reduce this entropy.

11. Complete Architecture

                    CLIENT
                       |
                       ↓
                Consistent Hash
                       |
                       ↓
                  Hash Ring
                       |
          ┌────────────┼────────────┐
          ↓            ↓            ↓
        Node A       Node B       Node C
        Replica      Replica      Replica
           \           |           /
            \          |          /
             └──── Replication ──┘
                       |
                Multiple Copies
                       |
              ┌────────┴────────┐
              ↓                 ↓
           WRITE              READ
              ↓                 ↓
              W                 R
              └────────┬────────┘
                       ↓
                   R + W > N
                       ↓
               Quorum Overlap
                       ↓
             Stronger Consistency

12. Consistent Hashing vs Traditional Sharding

The source makes an important architectural distinction.

Traditional sharding can impose decisions about the number of shards early and growing the system may require significant migration or disruption.

Consistent hashing is designed to make cluster growth/shrinkage easier.

Traditional sharding

DB
 |
 ├── Shard 1
 ├── Shard 2
 └── Shard 3

Need more capacity
       ↓
Major migration/reorganization

Consistent hashing

Node A
Node B
Node C

      ↓ Add Node D

Node A
Node B
Node C
Node D

Only affected data ranges need movement

13. When Should We Use This Architecture?

🔥 Don't use distributed databases just because they are technically interesting.

The source's recommendation is:

If a single database server can comfortably handle your scale, a single database is generally simpler and offers more features.

Consider a Cassandra/consistent-hashing style system when you genuinely have requirements around:

  • Large scale

  • High transaction volume

  • Always-on availability

  • Horizontal scaling

  • Redundancy

  • Ability to grow/shrink the cluster

  • Frequently changing transactional/event data

The source emphasizes that scale needs to be part of the equation and describes this architecture as particularly suited to scalable, always-on, transactional workloads.

🎯 Ramesh Interview Notes

Q1. Why replicate data?

To provide redundancy, fault tolerance and continued availability when a node fails.

Q2. What problem does replication create?

Consistency — replicas may temporarily contain different versions of the data.

Q3. What is eventual consistency?

A system may temporarily return stale data, but replicas are expected to converge to the latest state.

Q4. What is R + W > N?

It ensures that the read and write replica sets overlap, providing the quorum condition needed for stronger consistency.

Q5. What does N mean?

Total number of replicas.

Q6. What does W mean?

Number of replicas required to acknowledge a successful write.

Q7. What does R mean?

Number of replicas required to participate in a successful read.

Q8. What is the trade-off?

R/W higher
   ↓
Stronger consistency
   ↓
Higher latency

R/W lower
   ↓
Lower latency
   ↓
Potential stale reads

🧠 Final Memory Trick

Remember 5 words:

N → NUMBER OF COPIES

W → WRITE ACKNOWLEDGEMENTS

R → READ AGREEMENTS

R + W > N → QUORUM OVERLAP

ENTROPY → REPLICAS OUT OF SYNC

And the complete story:

CONSISTENT HASHING
        ↓
Find where data belongs
        ↓
REPLICATION
        ↓
Keep multiple copies
        ↓
CONSISTENCY PROBLEM
        ↓
Choose R and W
        ↓
R + W > N
        ↓
Quorum overlap
        ↓
Stronger consistency

OR

Low R/W
        ↓
Lower latency
        ↓
Eventual consistency

This is the core mental model behind Dynamo-style distributed databases and the tunable consistency discussion in Cassandra-like systems.


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

Yes. The important point is that “consistent hashing database” is not one database category. Consistent hashing is a partitioning technique used by several distributed databases, caches, and storage systems.

1. Major databases using consistent hashing / Dynamo-style architecture

For your distributed-systems interview, focus mainly on these:

SystemConsistent hashing / token ringReplicationConflict approach
Apache Cassandra✅✅Last-Write-Wins (LWW)
Riak KV✅✅Vector/Dotted Version Vectors, siblings, application resolution
Amazon Dynamo✅ Original Dynamo design✅Vector clocks / application-assisted resolution
Project Voldemort✅✅Versioning / vector clocks
Redis ClusterUses hash slots rather than classic Dynamo ring✅Different model; not the same Dynamo conflict-resolution model

For interviews, Cassandra + Riak + Dynamo are the most useful examples to remember. Cassandra's current architecture explicitly describes partitioning using consistent hashing and replication across nodes. (Apache Cassandra)

2. Your main question: What happens when replicas disagree?

Suppose:

Key = customer:101

Node A → Espresso
Node B → Espresso
Node C → Cappuccino

This can happen because:

Client
   |
   ↓
WRITE
   |
   ↓
Node A
   |
   ├────→ Node B
   |
   └────→ Node C   ❌ network delay

At some point:

A → Espresso
B → Espresso
C → Cappuccino

Now the distributed database has to determine:

Which version should win?

And this is where different databases behave differently.

3. Cassandra — Last Write Wins

Cassandra uses timestamps on mutations and resolves conflicting mutations using Last-Write-Wins. (Apache Cassandra)

Example:

Node A → Espresso   timestamp 100
Node B → Espresso   timestamp 100
Node C → Cappuccino timestamp 105

Cassandra says:

105 > 100

Therefore:

Cappuccino wins

After repair/replication:

Node A → Cappuccino
Node B → Cappuccino
Node C → Cappuccino

Cassandra memory trick

Cassandra → Latest timestamp wins.

⚠️ Important: LWW can discard a concurrent update. So "latest" doesn't necessarily mean "semantically correct."

4. Riak — More Sophisticated Conflict Handling

Riak takes a different approach.

It can use causal context, including vector clocks/dotted version vectors, to understand the relationship between versions. (docs.riak.com)

Imagine:

             Original
                |
        ┌───────┴───────┐
        ↓               ↓
    Update A          Update B
    Espresso          Cappuccino

These updates happened concurrently.

Riak may not be able to say:

Espresso > Cappuccino

or:

Cappuccino > Espresso

So instead it can preserve both as siblings.

customer:101

   ├── Espresso
   └── Cappuccino

The application can then decide what the correct business value should be.

Riak explicitly supports sibling values when concurrent versions cannot be causally resolved. (docs.riak.com)

5. Why are siblings useful?

Imagine:

Bank account

Two clients simultaneously update it.

If the database simply says:

Last write wins

one update could disappear.

Instead:

Version 1 → ₹1000
Version 2 → ₹1200

The system can expose both versions:

       Conflict
          |
    ┌─────┴─────┐
    ↓           ↓
 ₹1000         ₹1200

Application logic can determine the correct resolution.

This is one reason Riak's conflict model is different from Cassandra's LWW approach. (docs.riak.com)

6. Dynamo — Where the Idea Came From

Amazon's original Dynamo paper is the foundation for this style of architecture.

The basic philosophy was:

High Availability
       +
Replication
       +
Partitioning
       ↓
Eventual Consistency

But the cost is:

Multiple replicas
       ↓
Concurrent writes
       ↓
Conflicting versions
       ↓
Conflict resolution required

The Dynamo design used versioning/vector clocks to detect relationships between versions and could defer some conflict resolution to the application. (docs.riak.com)

7. Very Important Distinction

Don't memorize:

❌ "Consistent hashing resolves conflicts."

That's incorrect.

Instead:

Consistent Hashing
        ↓
Determines WHERE data belongs
        ↓
Replication
        ↓
Creates multiple copies
        ↓
Concurrent writes
        ↓
Replicas may disagree
        ↓
Conflict-resolution mechanism
        ↓
Database-specific

This is the key interview concept.

8. Complete Example

Let's take:

N = 3

Node A
Node B
Node C

Consistent hashing determines:

customer:101
       ↓
Hash Ring
       ↓
A → B → C

Replication factor = 3:

customer:101

A → Replica 1
B → Replica 2
C → Replica 3

Now two clients update concurrently.

Client 1 → A → Espresso

Client 2 → C → Cappuccino

Temporary state:

A → Espresso
B → old value
C → Cappuccino

Now:

             CONFLICT
                |
       ┌────────┴────────┐
       ↓                 ↓
   Espresso          Cappuccino

What happens next?

Cassandra

Timestamp comparison
        ↓
Latest timestamp wins
        ↓
One value
        ↓
Replicas converge

Riak

Causal/version analysis
        ↓
Can conflict be resolved?
      /       \
    YES       NO
    ↓          ↓
 Resolve    Siblings
             ↓
       Application may
       resolve conflict

Dynamo-style design

Version information
       ↓
Detect concurrent versions
       ↓
Resolve according to
system/application strategy

9. Where R + W > N Fits

Now connect this to your previous class notes.

Consistent Hashing
       ↓
Find replicas
       ↓
N replicas
       ↓
       ├──────────────┐
       ↓              ↓
     WRITE           READ
       ↓              ↓
       W              R
       └──────┬───────┘
              ↓
          R + W > N
              ↓
        Quorum overlap

But remember:

Quorum overlap does NOT tell us how conflicting concurrent versions are semantically resolved.

That's a separate problem.

⭐ Interview Answer

If interviewer asks:

"What happens if replicas disagree in a consistent-hashing database?"

Say:

"Consistent hashing itself doesn't resolve replica conflicts; it only determines data placement. When replicated copies diverge because of concurrent writes or network partitions, the resolution mechanism is database-specific. Cassandra uses timestamp-based Last-Write-Wins, while Dynamo-style systems such as Riak can use causal metadata such as vector clocks or dotted version vectors and may preserve conflicting versions as siblings for application-level resolution." (docs.riak.com)

🔥 One-line memory:

Consistent Hashing = WHERE, Replication = HOW MANY, Quorum = HOW MANY ACK, Conflict Resolution = WHICH VALUE WINS.

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)