Papers
Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases
Alexandre Verbitski, Anurag Gupta, Debanjan Saha, Murali Brahmadesam, Kamal Gupta, Raman Mittal, Sailesh Krishnamurthy, Sandor Maurice, Tengiz Kharatishvili, Xiaofeng Bao · ACM SIGMOD International Conference on Management of Data (SIGMOD) 2017, 2017
The problem: in the cloud, the database bottleneck became the network
The paper starts from an observation: in a traditional relational database, the performance limit came from CPU and disk, but in the cloud compute is decoupled from storage and data is spread across many nodes and disks in a multi-tenant fleet. In this setting, individual disks stop being the hot spot and the bottleneck shifts to the network between the database tier, which issues the I/O operations, and the storage tier, which executes them. Beyond packets per second and bandwidth, there is traffic amplification, since a high-performance database sends its writes to many nodes in parallel, and the slowest node, disk or network path (the outlier) can dominate response time. The authors also point to sources of stalls in the engine: a cache miss that forces a wait for a disk read, eviction of dirty pages, checkpoints and background writes that cause stalls, and multi-phase commit protocols such as 2PC, which tolerate poorly the failures and latency of distributed systems at scale. The proposed answer is Aurora, a relational database service for OLTP workloads that pushes redo log processing down to a purpose-built, multi-tenant, scale-out storage service, reducing network traffic and enabling fast recovery and fault-tolerant, self-healing storage.
Durability at scale: 4/6 quorum across three zones and 10 GB segments
To tolerate failures, replicated systems use quorums: with V copies, a read requires Vr votes and a write requires Vw votes, and two rules guarantee consistency: Vr + Vw > V (every read sees the most recent write) and Vw > V/2 (prevents conflicting writes). The common approach, three replicas with 2/3 quorums, is considered insufficient by the authors. The reason is that, at any given moment, some disks or nodes are already failed due to background noise, and the loss of an entire Availability Zone (AZ) is a correlated failure: if, in addition to it, a node in another AZ is having problems, the quorum breaks. Aurora therefore uses 6 copies of each piece of data across 3 AZs, two per AZ, with a write quorum of 4/6 and a read quorum of 3/6. This allows losing an entire AZ plus one node (AZ+1) without losing data, and losing an entire AZ without losing write capability. To shrink the window of vulnerability to a second failure, the volume is partitioned into 10 GB segments, each replicated six times in a Protection Group (PG). Segments are the unit of failure and repair: a 10 GB segment can be repaired in about 10 seconds on a 10 Gbps network, so losing the quorum would require two independent failures in the same window on top of an AZ failure. The volume can grow up to 64 TB.
The log is the database: reducing write amplification
Replicating each segment six times with a 4/6 write quorum would be unfeasible with a traditional engine like MySQL, which generates many types of I/O per application write: redo log, binlog, data pages, a second write of the page (double-write, against partial pages) and metadata files, many of them in sequential, synchronous steps. In Aurora, the only thing that crosses the network from the database tier is redo log records: no page is written, not in the background, not at checkpoint, not on cache eviction. The storage tier applies the log to materialize pages, continuously in the background or on demand, and from a correctness standpoint the engine treats materialized pages as a simple cache: the log is the database. The records are grouped into batches per PG and sent to the six replicas, and the database waits for acknowledgment from 4. Most of the storage node's work is asynchronous; only receiving the record and persisting it to disk are on the synchronous path. In the paper's experiment (SysBench write-only, 100 GB, 30 minutes), Aurora processed 27,378,000 transactions versus 780,000 for mirrored MySQL, 35 times more, with 0.95 I/Os per transaction versus 7.4, that is, 7.7 times fewer I/Os per transaction on the database node, even while amplifying writes six times.
Consistency without 2PC: LSNs, VDL, asynchronous commit, and reads without quorum
Instead of an expensive, chatty consensus protocol like 2PC, Aurora takes advantage of the fact that the log advances in order: each record receives an increasing LSN (Log Sequence Number), generated by the database. Each transaction is broken into atomic mini-transactions, whose last record is a consistency point (CPL). Storage computes the VCL, the highest LSN for which all previous records are available, and the VDL (Volume Durable LSN), the highest CPL less than or equal to the VCL, which is how far the volume is considered durable. Storage nodes that missed records recover them by talking to each other (gossip). So that the database does not run too far ahead of storage, it does not allocate an LSN greater than the current VDL plus a limit (LAL, currently 10 million), which creates backpressure. Commits are asynchronous: the thread that receives the COMMIT records the commit LSN in a wait list and moves on to other work; the transaction is only acknowledged to the client when the VDL reaches or passes that LSN, and a dedicated thread sends the acknowledgments. Reads, in normal operation, do not need a quorum: the database defines a read-point (the VDL at the time of the request) and, since it tracks which segment is already complete up to that point, reads directly from a suitable segment. A read quorum is only used in recovery, when the runtime state has been lost.
Replicas, fast recovery, and measured results
A single writer and up to 15 read replicas mount the same shared storage volume, so replicas add no storage cost or disk writes. To reduce lag, the writer's log stream is also sent to the replicas, which apply only records with LSN less than or equal to the VDL and apply mini-transactions atomically; the paper says the replica typically lags the writer by 20 ms or less. In recovery, traditional databases (ARIES-style) replay the log from the last checkpoint, which is expensive. In Aurora, redo application happens continuously in storage, so, on restart, the database only queries a read quorum of each PG to recompute the VDL and truncate records above it; the paper states that recovery usually takes less than 10 seconds, even after a crash with more than 100,000 writes per second. In the results (Aurora based on MySQL 5.6, service available since July 2015), throughput scales linearly with instance size, reaching 5 times that of MySQL 5.7 on the largest (121,000 writes/s and 600,000 reads/s). On writes with 100 GB, up to 67 times faster; at 1 TB out of cache, 34 times. At 10,000 writes/s, replica lag was 5.38 ms on Aurora versus 300 seconds on MySQL.
See the ideas at work
Practice the designs that use this paper in the System Design school.