Leaderless Replication

Introduction

In leaderless replication, there is no single leader node that coordinates write operations. Instead, write operations can be sent to any node, and these nodes coordinate to ensure data consistency.

Used in: Cassandra, Raik and NOT used in Dynamo DB(remember!)

How Leaderless Replication Works:

1. Write Operations:
   • A client sends a write request to multiple nodes simultaneously.
   • Each node independently writes the data and acknowledges the write.
2. Read Operations:
   • A client sends a read request to multiple nodes and may receive different versions of the data.
   • The client or a coordinating service reconciles these versions to provide a consistent view.
3. Quorum-Based Consensus:
   • To ensure consistency, a write is considered successful only if a quorum of nodes (typically a majority) acknowledges the write.
   • Similarly, a read is considered successful if a quorum of nodes returns the same version of the data.

---

Anti-Entropy

Propagates changes to the background !

How can we quickly tell which writes to send?? Solution: Merkle Trees!

---

Merkle Trees

How to build a merkle tree?? On the left we’ve the key-value pairs in a DB.

Comparing Merkle Trees: Logarithmic Time Complexity $O(logN)$ instead of linear time complexity $O(N)$ if we would’ve scanned the replication logs of both the DBs.