Deep dive on Amazon S3 (STG407)

Session Notes

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