Understanding the Dynamo Paper: Amazon’s Highly Available Key-Value Store.

In large-scale distributed systems, failures are inevitable nodes crashes and network partitions. Traditional databases prioritize strong consistency, but at Amazon’s scale, availability is often more critical. Dynamo is a distributed key-value store, meaning your data lives across many machines, not just one. When you write a value, it gets copied to several nodes for reliability.

The Dynamo paper presents a different approach: a key-value store designed to remain highly available even under failures, by embracing eventual consistency and pushing conflict resolution to the application layer.

The Trade-off: CAP Theorem in Practice

Dynamo is built around the constraints of the CAP theorem. It prioritizes:

• Availability (A): Every request receives a response
• Partition Tolerance (P): The system continues to operate despite network splits

To achieve this, Dynamo relaxes sacrifices strong consistency in favor of eventual consistency. Since clients can connect to any node to perform writes, the system cannot guarantee that every read will immediately reflect the latest write. Instead, different read requests may return different results depending on which replicas respond and how up-to-date they are.

A read may not always return the most recent write but the system will converge over time.

System Architecture: Any Node Can Serve

Unlike leader-based systems, Dynamo allows a client to connect to any node. That node becomes the coordinator for the request and communicates with replicas.

This diagram shows the overall architecture of Dynamo. A client can send requests to any node in the cluster, which then acts as a coordinator. The coordinator node is responsible for forwarding the request to multiple replicas. This design improves availability because the system does not depend on a single leader node.

This design:

• Eliminates single points of failure
• Improves availability
• Enables horizontal scalability

Writes: Always Accepted, Never Overwritten

The coordinator sends the write to multiple replicas. Instead of overwriting existing data, each write creates a new version of the object, tagged with a vector clock. This ensures that the system preserves the history of updates.

Dynamo preserves history instead of destroying it.

Tracking causality and conflicts

Dynamo uses vector clocks to track relationships between versions. They help answer a key question: Did one version of data come after another, or were they created independently?

A vector clock is typically represented as a list (or map) of (nodeId, counter) pairs, where each node maintains its own logical counter. For example:

[N1=1, N2=2]

This means:

• Node N1 has made 1updates
• Node N2 has made 2update

This diagram shows a causal relationship between versions.

A client first sends a write request to Node N1, which creates version v1. As part of this write, N1 increments its entry in the vector clock (e.g., from [N1=0, N2=0] to [N1=1, N2=0]). This updated version is then propagated, and Node N2 receives it before performing its own write. When N2 creates the next version (v2), it builds on top of v1 and increments its own counter, resulting in [N1=1, N2=1]. Because each version is aware of the previous one, they form a causal chain where every version logically descends from its predecessor. Since causality is preserved, Dynamo can safely treat the latest version as the correct one, and no conflict arises.

This diagram shows a concurrent update scenario that leads to a conflict.

A client sends a write request to Node N1, which creates version v1 by incrementing its vector clock (e.g., [N1=1, N2=0]). However, this update is not yet seen by Node N2. Independently, another client sends a write request to Node N2, which creates version v2 starting from the same initial state and increments its own counter, resulting in [N1=0, N2=1]. Since N2 did not observe N1’s update (and vice versa), neither version is aware of the other. As a result, there is no causal relationship between v1 and v2. These versions are considered concurrent, and neither descends from the other.

Dynamo detects this situation using vector clocks and preserves both versions as conflicting siblings, leaving the responsibility of resolving the conflict to the application.

Causality determines consistency in Dynamo: when updates are aware of each other, they form a chain; when they aren’t, they create conflicts.

Reads

During a read operation, the coordinator node may receive multiple versions of the same object from different replicas. Instead of resolving the conflict internally, Dynamo returns all conflicting versions to the client. The application is then responsible for merging these versions and writing back a resolved result if needed.

The Core Consistency Model

At the heart of Dynamo lies a simple but powerful rule set based on causal ordering using vector clocks.

For every write, Dynamo compares the vector clock of the incoming version with the existing version(s) and determines one of three outcomes:

1. Existing version descends from the new version: The incoming write is older (stale) than what is already stored, so the write is discarded.
2. New version descends from the existing version: The incoming write is a direct successor of the current version, so previous version is replaced with new version.
3. Neither version descends from the other: The two versions are concurrent. Each was created independently on different nodes, so both versions are preserved as siblings (conflict)

If the counters on the first object’s clock are less-than-or-equal to all of the nodes in the second clock, then the first is an ancestor of the second and can be forgotten. Otherwise, the two changes are considered to be in conflict and require reconciliation.

To be continued — Consistent Hashing, Quorums, Gossip Protocol…