DynamoDB Mechanics: Partitioning, Replication, & Internal Consensus

Amazon DynamoDB is a fully managed, serverless NoSQL database service designed to provide single-digit millisecond latency at any scale. Achieving this requires distributing data dynamically across a partitioned network of storage nodes and utilizing distributed consensus protocols to manage replication and consistency.

1. Partitioning & Distributed Architecture

To scale throughput and storage, DynamoDB divides a table's data into physical allocations of SSD storage called partitions.

How Hashing Works

When a write request is received, S3 hashes the Partition Key (PK) of the item using the MD5 hashing algorithm to generate a 128-bit value. S3 maps this 128-bit hash range to identify the target partition.

graph TD
    Item[Write Item: PK = User123] --> HashFunc[MD5 Hashing Function]
    HashFunc --> HashValue[Hash Value: e.g., 7a2f...]
    HashValue --> Router[Request Router]
    Router -->|Range 0000 - 3fff| P1[Partition 1]
    Router -->|Range 4000 - 7fff| P2[Partition 2 - Target]
    Router -->|Range 8000 - bfff| P3[Partition 3]
    Router -->|Range c000 - ffff| P4[Partition 4]

Partition Limits:

Each individual partition has strict physical limitations:

• Storage Limit: Maximum 10 GB of data.
• Read Throughput: Maximum 3,000 Read Capacity Units (RCUs).
• Write Throughput: Maximum 1,000 Write Capacity Units (WCUs).

When a table grows past 10 GB, or when aggregate throughput exceeds the capacity limits of a single partition, DynamoDB automatically initiates a Partition Split, dividing the hash range of the partition in half and allocating new hardware.

2. Multi-Paxos Replication & Request Routing

For high availability and durability, each partition is replicated across three nodes, distributed across different Availability Zones (AZs) in a Replication Group.

flowchart TD
    %% Styling Definitions
    classDef client fill:#E1F5FE,stroke:#0288D1,stroke-width:2px,color:#01579B;
    classDef router fill:#FFE0B2,stroke:#F57C00,stroke-width:2px,color:#E65100;
    classDef leader fill:#FFF9C4,stroke:#FBC02D,stroke-width:2px,color:#F57F17;
    classDef follower fill:#F3E5F5,stroke:#7B1FA2,stroke-width:2px,color:#4A148C;
    classDef boundary fill:none,stroke:#B0BEC5,stroke-width:1px,stroke-dasharray: 5 5;

    Client["💻 Client Request"]
    Router["⚡ Request Router Fleet<br/>(Caches Partition Hash Map)"]

    subgraph RepGroup["Partition Replication Group"]
        Leader["👑 Paxos Leader (AZ1)<br/>(Handles Writes/Strong Reads)"]
        Follower1["👥 Paxos Follower (AZ2)<br/>(Replicates Log Chunks)"]
        Follower2["👥 Paxos Follower (AZ3)<br/>(Replicates Log Chunks)"]
    end

    Client ==> Router
    Router ==>|Direct Write Payload| Leader
    Leader ==>|1. Sync Write-Ahead Log| Follower1
    Leader ==>|1. Sync Write-Ahead Log| Follower2
    Follower1 -.->|2. Log Commit Ack| Leader
    Leader -.->|3. HTTP 200 OK| Router
    Router -.->|Success Response| Client

    class Client client;
    class Router router;
    class Leader leader;
    class Follower1,Follower2 follower;
    class RepGroup boundary;

The Request Flow Mechanics:

1. Request Router Fleet: Receives incoming requests. Routers are stateless and cache partition maps (which match hash ranges to physical storage node IP addresses). The router hashes the item PK, identifies the replication group leader, and forwards the payload directly.
2. Multi-Paxos Consensus: Each replication group elects a single Leader node using a lease-based Multi-Paxos protocol.
   • Writes: All write operations must hit the Paxos Leader. The Leader writes the edit to a local Write-Ahead Log (WAL) and replicates the log records to both Followers.
   • Quorum Commit: As soon as at least one Follower acknowledges the write (meaning 2 out of the 3 nodes have successfully committed the log record), the transaction is officially committed. The Leader replies 200 OK to the Request Router.
   • Reads: Eventually Consistent Reads route directly to any replica (Leader or Follower) to save bandwidth, while Strongly Consistent Reads are forced to query the Leader to guarantee they fetch the latest committed state.

3. Capacity Allocation: Adaptive Capacity & GAC

Historically, DynamoDB allocated provisioned capacity equally across all partitions. For example, if a table had 4 partitions and was provisioned with 400 WCUs, each partition was strictly capped at 100 WCUs. A spike to 120 WCUs on a single "hot" partition caused throttling, even if the other partitions were completely idle.

Adaptive Capacity

DynamoDB solved this partition-skew limitation by introducing Instant Adaptive Capacity:

• Dynamic Reallocation: If a partition is subjected to a spike in traffic, DynamoDB automatically dynamically allocates unused throughput from idle partitions to the hot partition.
• Table-Level Limit: As long as your aggregate table-level consumption stays below your provisioned maximum throughput, individual partitions can exceed their normal limits (up to their physical limits of 1k WCUs / 3k RCUs).

Global Admission Control (GAC)

To prevent Request Routers from overwhelming the storage node fleet during massive spikes, DynamoDB runs a distributed rate-limiting layer called the Global Admission Control (GAC).

• The GAC tracks token-bucket rates globally across the entire router fleet in memory.
• Instead of each router guessing a storage node's available capacity, the GAC distributes and leases tokens to routers, allowing them to reject requests at the entry point rather than overloading storage node Paxos queues.

4. Local vs. Global Secondary Indexes

When querying attributes other than the base table's primary keys, you must use Secondary Indexes.

GSI Replication & Backpressure Throttling

Unlike LSIs, which reside in the same physical partition as their base item, GSIs are stored in entirely separate partition spaces.

• Asynchronous Propagation: When a write commits to the base table, a background process (using DynamoDB Streams technology under the hood) asynchronously reads the base table's log and applies the write to the GSI partition.
• GSI Backpressure: If a GSI partition is under-provisioned, it cannot keep up with the write rate of the base table. To prevent the GSI replication lag from growing indefinitely, DynamoDB exerts Backpressure. The base table will proactively throttle writes until the GSI catches up.

5. Replica Recovery & Disk Fault Tolerances

Because DynamoDB runs on commodity drives, SSD failures and storage node crashes are routine.

• Log Synchronicity: Since writes are committed only when 2 out of 3 replicas have persisted the log, a single node crash does not interrupt read/write availability.
• Node Bootstrapping: When a failed node recovers or new hardware is provisioned:
  1. The node boots up and queries the Paxos Leader to identify the last committed log sequence number.
  2. If the gap is small, the Leader streams the missing log files to the node to catch it up.
  3. If the node has been offline too long (or has suffered a complete disk replacement), S3 copies a snapshot of the database partition state from a surviving replica and streams the log records created since the snapshot began.

6. Critical Q&A: Advanced Systems Engineering

Q1: What happens during a partition split in DynamoDB, and is there any query downtime during the split?

Answer: There is zero query downtime during a partition split. When a split is triggered (due to data size exceeding 10 GB or sustained thermal capacity limits), the Paxos replication group continues to serve reads and writes on the old partition. In the background, the storage engine allocations spin up two new replication groups (Target Partition A and Target Partition B). The data is copied to the new partitions based on the split hash ranges. Once the background copy is complete, a quick metadata pointer update is committed in the Namespace Directory Service to route traffic to the new ranges. Any in-flight transactions are resolved, and the old partition is safely decommissioned.

Q2: How does a write transaction work across multiple items in DynamoDB, and how does it guarantee ACID properties?

Answer: DynamoDB TransactWriteItems uses a two-phase commit (2PC) protocol managed by a specialized coordinator fleet.

1. Phase 1 (Prepare): The transaction coordinator locks the target items on their respective Paxos leaders to ensure no concurrent updates can occur. It verifies that conditional checks for all items are met.
2. Phase 2 (Commit): If all locks are acquired and checks succeed, the coordinator writes a transaction commit record to a local ledger. It then commands all Paxos leaders to apply the writes and release their locks. If any single check fails or a lock cannot be acquired, the entire transaction is rolled back, and all locks are released, ensuring absolute Atomicity.

Q3: Why does Global Secondary Index (GSI) throttling cause base table write throttling, and how can we prevent it?

Answer: S3 enforces a safety limit on GSI replication queues to prevent uncontrolled log backlogs. If a GSI partition is throttled (due to lack of provisioned WCUs or a hot key on the index), replication lag increases. If this lag crosses a critical threshold, S3 exerts backpressure, throttling writes on the base table.

• Prevention: Use On-Demand Capacity Mode so S3 auto-scales both base and index capacities, or ensure your GSI WCUs are provisioned at least equal to or higher than the base table's WCUs. Additionally, avoid high-cardinality index keys that target a narrow partition space.

Q4: If the Paxos Leader suffers a hardware failure, how long does failover take, and what happens to in-flight read and write operations?

Answer: If the Paxos Leader fails, the lease expires (typically within 1.5 to 3 seconds). The two remaining Followers detect the absence of the Leader heartbeat and run a Paxos ballot election to elect a new Leader.

• Writes: Any write request sent to the old Leader will fail with an HTTP 5xx error or timeout. The AWS SDK automatically retries these requests.
• Eventually Consistent Reads: Are unaffected since they can be served by the surviving Follower.
• Strongly Consistent Reads: Will fail during the 1.5-3 second failover window until a new Leader is elected and establishes its log lease.

Q5: How does a Paxos Leader distinguish between a slow network link to a follower and a completely dead follower when calculating write quorum?

Answer: The Paxos Leader does not distinguish. It simply relies on a strict count of acknowledgments. If a write payload is sent to both Followers, and Follower A responds in 1 millisecond while Follower B is delayed by network congestion, the Leader immediately commits the write as soon as it receives the response from Follower A. The Paxos protocol only requires a majority (2 out of 3). As long as the Leader and one Follower are communicating, writes commit at full speed. Follower B will catch up asynchronously when it receives the log stream.

References & Further Reading

• SOSP 2022 Academic Paper: Amazon DynamoDB: A Scalable, Predictable, and Fully Managed NoSQL Database Service
• AWS Database Blog: How Amazon DynamoDB Adaptive Capacity Accommodates Uneven Data Access Patterns
• AWS Developer Guide: Partitions and Data Distribution in DynamoDB
• AWS Architecture Blog: Under the Hood of Amazon DynamoDB Global Tables and Multi-Paxos Consensus

This content is reserved for Premium Members.