Vertex Macro | Financial Cloud Cloud · AWS Re:cap
AWS Re:cap 09: Deep dive on Amazon S3 (STG407)
Introduction
● Server Level Strategies for Handling Failures
● Series focuses on lower-level details of S3 operations
● This year's focus: designing for availability
● Approach
● Two angles: system level and server level views
● System level view on failure architecture, read-after-write consistency, failure implementation
● Defining Terms
● Availability: dealing with failure
● Failure: components that can fail (drives, servers, racks, buildings)
● Types of failure: permanent loss or transient unavailability (power, networking, overload)
● Design goals: system designed around goals (e.g., 99.99% availability, 11 9s durability, read-after-write consistency)
● S3's Design Goals
● Designed for high availability and durability
● Read-after-write consistency introduced in 2020
● Prior to 2020, acceptable failure handling included violating consistency guarantees
S3 Before Consistency Launch: Handling Failures and the Indexing Subsystem
Consistency Definition
● Consistency: property that an object GET reflects the most recent PUT to that object
● Indexing Subsystem
● Holds object metadata (name, tags, creation time)
● Accessed on every data plane request (GET, PUT, LIST, HEAD, DELETE)
● More requests go to the index than the storage subsystem
● Core of the indexing system: dedicated storage for durably holding index entries
● Quorum-Based Algorithm
● Data stored across replicas using a quorum-based algorithm
● Forgiving to failures
● Servers run in separate Availability Zones (AZs) to avoid correlation on a single fault domain
● Failure of any single disk, server, rack, or zone affects only a small subset of data
● Quorum Implementation in the Index
● Reads and writes required to hit a majority of servers
● Example: writing value A succeeds on all nodes
● Writing value B: one node fails, but B succeeds on a majority of servers (no availability impact)
● Reader initiates a read: one server fails, but the other two return value B
● Conflict resolution via associated timestamp (B wins over A)
● Reads and writes succeed despite server failures in the middle of requests
● System is available due to multiple nodes and allowance for failure
Quorum-Based Algorithms in Distributed Systems
Overview
● Quorum-based algorithms ensure consistency and fault tolerance by requiring a minimum number of nodes (quorum) to agree on actions like reading or writing data.
● Prevents data corruption when some nodes fail.
Key Concepts
Quorums
● Define the total number of nodes (N), write quorum (W), and read quorum (R).
● Read Operation:
● A read request goes to a set of nodes; the operation succeeds if responses from R nodes are received.
● Write Operation:
● A write request goes to a set of nodes; the write is committed if W nodes confirm it.
● Consistency:
● The rule R + W > N ensures that any read will see the latest written data, as the read set and write set must overlap by at least one node.
● Fault Tolerance:
● If a node fails, the system can still form a quorum (e.g., a 3-out-of-5 system tolerates 2 failures).
Examples & Applications
Data Replication
● Ensuring all copies of data remain consistent across a cluster (e.g., in databases like Cassandra).
● Mutual Exclusion (Maekawa's Algorithm):
● Nodes request permission from their quorum to access a shared resource (critical section), ensuring only one node enters at a time.
● Consensus (Paxos):
● A foundational protocol for distributed systems to agree on a single value, crucial for leader election and state machine replication.
Key Parameters (URW Model)
● N: Total number of data copies (nodes).
● W: Write quorum (nodes needed to confirm a write).
● R: Read quorum (nodes needed to confirm a read).
S3 Quorum-Based Systems: Ensuring High Availability and Consistency
Quorum Principles in S3-Compatible Systems
● Utilizes quorum principles (majority of nodes agreeing) for high availability and consistency
● Relevant in clustered or edge setups (e.g., Amazon S3 on Snowball Edge)
How It Works in S3-Like Systems
Distributed Consensus
● Monitors or managers form a quorum (usually 3+) to track node health
● Clients informed of available storage nodes
● Write Operations:
● Write succeeds only when a majority (quorum) of storage nodes acknowledge it
● Ensures data durability and consistency across the cluster
● Read Operations:
● Reads target a quorum of replicas to guarantee up-to-date data
● Fault Tolerance:
● Can tolerate f node failures with 2f+1 total replicas
● New leaders can be elected, and operations continue as long as a quorum remains
Key Examples
Amazon S3 on Snowball Edge
● Clusters of Snowball Edge devices use quorum for S3-compatible storage
● Manages device status and data availability
● Ceph:
● Use monitors and OSDs (Object Storage Daemons) with quorum.
● Maintains cluster state and data availability as an S3-compatible backend.
● Object Storage Daemons (OSDs) are the core data-storing processes in a distributed system like Ceph, acting as individual storage units that manage local disks (HDDs/SSDs) and handle replication, recovery, and data distribution for large amounts of unstructured data, making them fundamental for scalable, resilient object storage.
● Distributed Consensus Libraries:
● GitHub use S3's conditional operations (ETags) for leader election and quorum Key Functions of an
● OSD:
● Data Storage: Stores actual data objects on a local filesystem (like XFS).
● Data Management: Manages data replication (making copies) and recovery (rebuilding lost data) across the cluster.
● Heartbeat Monitoring: Checks other OSDs for health, reporting status to Ceph Monitors.
● Network Access: Provides network access to stored data for clients.
Core S3 vs. Quorum-Based
Amazon S3 (Core)
● Provides strong read-after-write consistency natively across global infrastructure
● No explicit user management of quorums
● S3 Quorum-Based (Clustered/Edge):
● Applies quorum concepts within user-managed clusters of S3-compatible devices
● Ensures internal consistency and availability within the cluster
S3's System Level Availability Design and Caching Layer
Central Concept
● Multiple nodes to route to and headroom for failure
● Configured and sized to achieve 99.99% availability goals
● Read-After-Write Consistency Before 2020
● Readers saw values written by writers due to overlapping reads and writes (both required hitting a majority of servers)
● Question: Why wasn't S3 read-after-write consistent before 2020?
● Answer: Caching layer
● Caching Layer
● S3's front end heavily caches frequently accessed objects
● Inconsistent read: value B returned instead of C (last value written)
● Reads and writes do not overlap in the cache
● Cache has key availability property (several hosts can receive requests, allowance for failure)
● No overlap in reads and writes in the cache
● Acceptable way to deal with failure before 2020 due to design goals not including consistency
● Caching Layer Example:
● Empty cache nodes with values B in storage
● Reader reads through a cache node, value B returned and resident in cache
● Write for C overwrites object, persists to replicas (C C C)
● Values B and C cached on separate nodes (design before 2020)
● Read routes to former cache node, returns value B (inconsistent read)
Solving the Overlap Problem with a Cache Coherency Protocol
Most Requested Feature: Consistency
● Consistency was the most requested feature before 2020
● Goal: solve the overlap problem in the caching layer
● Cache Coherency Protocol
● Needed to be fast, efficient, and available
● Retain property of multiple servers receiving requests while allowing some to fail
● Solution: replicated journal
● Replicated Journal
● Distributed data structure where nodes are chained together
● Writes flow through nodes sequentially
● Every node forwards to the next node
● Once through the journal, writes are sent to the quorum of storage nodes
● Journal keeps track of recent history and agrees on ordering
● Example: A comes before B
● Quorum-based system couldn't reason about ordering correctly
● Journal creates well-defined ordering for mutations
● Sequence Numbers and Watermarks
● All writes assigned a sequence number (increases over time)
● Example: A (sequence number 1), B (sequence number 2), C (sequence number 3)
● Storage nodes learn sequence number along with value
● Sequence number stored in cache along with value
● Cache node can ask if any writes arrived after a given sequence number
● Witness System
● Purpose: track high water mark for writes to the index
● Witness doesn't need to hold actual data, just sequence number
● Witness can overestimate last sequence number (safe to tell caller they're stale)
● Caller will read from storage and get correct result if told they're stale
Ensuring Failure Allowance and Consistency with Dynamic Reconfiguration
Witness System
● In-memory data structure (array of integers) next to the journal
● Allows cache nodes to ask if any writes came in after the cached value
● Modified read and write algorithm:
● Writes go to the journal
● Reads talk to the witness; if fine, return from cache; if stale, go to storage
● Lost Failure Allowance
● Original journal architecture: if a node fails, writes can't progress through the system
● Quorum services writes concurrently; journal sends writes through sequentially
● Node failure in journal can halt the entire system
● Dynamic Reconfiguration
● Introduced to fix failure allowance issue
● Nodes in the journal monitor each other's availability
● Pinging each other constantly; messages going through the system
● Nodes have up-to-date view of neighbor's availability
● When encountering an issue, nodes ask a quorum-based configuration system to reconfigure the journal
● Reconfiguration happens within milliseconds of a node failing
● Configuration system itself is quorum-based
● Result
● Cache with failure allowance and overlapping reads and writes
● S3 is now both consistent and highly available
● Retained high availability through consistency launch by designing for it
● System-Wide Availability Perspective
● Need many servers to choose from
● Only required to succeed on some
● Ability to reconfigure the system quickly in the face of failure
● Quorum-based algorithms are always present, even in systems like the journal
Dealing with Failure at the Implementation Level
Understanding Failure
● Question: What can fail?
● Correlated failures are crucial: failures that happen together
● Correlated failures essential for thinking about availability
● Quorum design: OK for one node to fail, but not if all nodes are in the same AZ or rack
Physical Failures
High-level physical view of S3
● Multiple Availability Zones (AZs)
● Each AZ has multiple racks of servers
● Each server has multiple hard drives
● Types of physical failures:
● Individual failures: hard drive motor breaks, platter gets scratched
● Correlated failures:
● Server failure: all attached hard drives appear to fail
● Rack failure: all drives in the rack fail (e.g., bad switch)
● AZ failure: entire AZ goes down (e.g., power outage)
● Logical Failures
● Example: deploying new software to the fleet
● Deploy to a few nodes at a time, ramp up gradually
● Set of servers with new software forms a failure domain
● If bug in new software, all those servers may fail together
● Need intelligent deployment strategy to tolerate potential failures
Designing Around Correlated Failures
Exposing Workloads to Multiple Failure Domains
● Replication of objects across multiple locations (e.g., AZs) for durability and availability
● Ensures data remains available even if a correlated failure domain (e.g., AZ, rack, server) fails
Understanding Failure Types
Fail-stop failure
● server or component stops functioning (e.g., power cord yanked)
● Easy to detect and react to in a tolerant system Fail-stop failure in a switch between
● AZs:
● Some requests continue to succeed (within the same AZ)
● Other requests start failing (traversing the failed switch)
● Results in a fuzzy failure mode where some requests succeed and some fail
Designing Around Fuzzy Failure Modes
● Redundancy is key: multiple switches between AZs
● 3 AZs in each region linked as a ring
● If a link fails (e.g., AZ1 to AZ2), can go the long way around (AZ1 to AZ3 to AZ2)
● Converts availability problem into a latency problem, preserving availability
● Powerful mental model: converting one kind of problem into a different kind of problem (e.g., availability to latency)
Challenges of Fail-Stop Failures in Stateful Systems
Fail-Stop Failures in Stateful Systems
● Tricky to reason about in systems like S3
● Can lead to states that are otherwise unreachable
● Crash Consistency
● System should return to a consistent state after a fail-stop failure
● Example: writing two lines of text to a file
● Normal execution: file has both lines
● Fail-stop failure during execution: file may have only the first line
● Enters an unreachable state in the absence of failure
● Designing Around Unreachable States
● Wrote a paper on Shodstor (storage node software) addressing this issue
● Focuses on reasoning about reachable states in the presence of failure and concurrency
Handling Gray Failures
Gray Failures
● More complex failure modes beyond fail-stop
● Example:
● A put request in S3
● Request comes from the internet to an S3 front-end server
● Front-end server fans data out to storage nodes
● Gray Failures Defined
● Failures that are not complete (e.g., fail-stop) but cause the system to behave unexpectedly
● Example: front-end web server accepts requests but can't reach some downstream hosts due to networking issues
● Server returns errors for failed requests but continues to accept and respond to requests
● Using Retries to Handle Gray Failures
● Powerful technique: if a request fails, retry it on a different path (e.g., different front-end web server)
● AWS SDKs have sophisticated retry strategies that intentionally retry requests on different IP addresses
● Retries allow trying a different path through the system
● Dangers of Retries in Distributed Systems
● Retries can lead to massive amplification of work if all services retry failed requests
● Example: failure at the bottom of the stack can result in 27 times more retries than original requests
● Can overload the system with excessive retries
● Intentional Design of Retry Strategies
● Need to be intentional when designing retry strategies to avoid overloading the system
● Example: fewer retries or no retries further down the stack, knowing that retries will occur higher up
● Ensures availability while protecting the system from excessive retries
● Gray Failures Due to Load
● Web server overloaded with work, manifesting as slow requests
● Powerful mechanism: timeouts (client times out slow requests and retries elsewhere)
● Challenges with Timeouts
● Timeouts not perfect and hard to design around, especially with retries
● Example:
● Overloaded web server with a queue of requests
● Client times out and retries elsewhere
● Server continues processing the timed-out request, unaware of the client's retry
● Results in server doing useless work on requests clients have given up on
● Congestive Collapse
● State where server processes only requests that have been timed out and retried elsewhere
● Chain reaction effect: overloaded server gets slower, causing more retries and queue buildup
● Self-feeding cycle where server spends all time on failed timeouts from retries
● Workaround: Inverted Queue Processing
● Mechanism to handle overloaded servers with full queues
● Process queue from the back (last in, first out)
● Unfair but penalizes some clients to make others very fast
Self-Healing System Design
Digging Out of Congestive Collapse
● Inverted queue processing: process queue from the back (last in, first out)
● Allows some requests to succeed, reducing backlog of slow timed-out requests
● Backoff and retry: clients back off and retry more slowly
● Gives server time to dig out of backlog
● Metastable Failure Mode
● State where system spends all time processing timed-out requests despite original problem being resolved
● System-Level Failure Recovery
● Goal: S3 should heal itself without manual intervention
● Example: web server not successfully responding to requests
● Clients retry elsewhere, but server needs to be removed from service
● Health Checks
● Essential tool for automatically healing servers
● Health check server sends requests to web servers to check functionality
● If server fails health check, it can be taken out of service (e.g., removed from DNS)
● Mitigates failures by preventing clients from reaching failing servers
● S3's Use of AWS Infrastructure
● S3 built on AWS using same infrastructure available to customers
● Web server capacity: network load balancers
● DNS: Route 53
● Health checks implemented using NLBs and Route 53
Ensuring Robust Health Checks and Global View of System Health
Danger of Single Health Check
● Health check server can fail, leading to incorrect detection of web server failures
● Example: health check server with network issue marks all web servers as bad
● Need to design for availability of both servers and health check system
● Multiple Perspectives for Health Checks
● S3 uses health checks from multiple sources:
● Same region
● Different region
● Public internet
● Combines signals to form a detailed view of web server health
● Helps diagnose correlated failures (e.g., networking issues)
● Avoiding Local Decisions
● Important tenet: never let local systems make local decisions about service health
● Example: original health check making local decision based on its view of the system
● Distributed systems require a global view to avoid mistakes with local decisions
● Global View of System Health
● Example: detecting and remediating failing hard drives
● Software detects failing hard drive
● Triggers remediation (e.g., power cycle, replacement by technician)
● Global Rate Limiter for Health Checks
● Health checking service must consult a global rate limiter before making changes to the system
● Example: health check detects failing hard drive and wants to take it out of service
● Rate limiter stops excessive removal of hard drives if health check service goes haywire
● Recap of Designing for Availability
● Define availability and correctness goals
● Design overall system architecture to meet goals (e.g., quorum-based architecture, strong consistency)
● Implement system pieces with understanding of failure modes and remediation without local decisions