Amazon S3 の詳細解説 (STG407)

セッションノート

はじめに

• サーバーレベルで障害に対処するための戦略
• このシリーズでは S3 オペレーションの低レベルな詳細に焦点を当てる
• 今年の焦点：可用性を考慮した設計アプローチ
• システムレベルとサーバーレベルという 2 つの視点
• 障害アーキテクチャ、read-after-write consistency、障害への対処実装をシステムレベルで考察。
• 用語の定義
• 可用性：障害への対処
• 障害：故障する可能性があるコンポーネント（ドライブ、サーバー、ラック、建物）
• 障害の種類：恒久的な喪失、または一時的な利用不能（電源、ネットワーク、過負荷）
• 設計目標：目標（例：99.99% の可用性、イレブンナインの耐久性、read-after-write consistency）を中心にシステムを設計する。
• S3 の設計目標
• 高可用性と高耐久性を実現するよう設計
• read-after-write consistency は 2020 年に導入
• 2020 年以前は、整合性の保証に反することも許容可能な障害対処に含まれていた

整合性導入前の S3：障害への対処とインデックスサブシステム

整合性の定義

• 整合性：オブジェクトへの GET が、そのオブジェクトに対する直近の PUT を反映する性質。
• インデックスサブシステム
• オブジェクトのメタデータ（名前、タグ、作成時刻）を保持する
• すべてのデータプレーンリクエスト（GET、PUT、LIST、HEAD、DELETE）でアクセスされる
• ストレージサブシステムよりもインデックスへのリクエストの方が多い
• インデックスシステムの中核：インデックスエントリを永続的に保持する専用ストレージ。
• クォーラムベースのアルゴリズム
• クォーラムベースのアルゴリズムを使用して、複数のレプリカにデータを保存する
• 障害に対する許容力がある
• 単一の障害ドメインに障害が集中しないよう、サーバーは別々の Availability Zone（AZ）で稼働する
• 1 台のディスク、サーバー、ラック、または 1 つの Zone の障害が影響するのは、データのごく一部だけである。
• インデックスでのクォーラム実装
• 読み取りと書き込みでは、サーバーの過半数へ到達する必要がある
• 例：値 A の書き込みがすべてのノードで成功する
• 値 B の書き込み：1 ノードで障害が起きても、過半数のサーバーで B の書き込みに成功する（可用性への影響なし）
• リーダーが読み取りを開始：1 台のサーバーで障害が発生しても、残りの 2 台が値 B を返す
• 関連付けられたタイムスタンプにより競合を解決する（B が A に優先する）
• リクエストの途中でサーバー障害が発生しても、読み取りと書き込みは成功する
• 複数ノードがあり障害を許容できるため、システムを利用できる

分散システムにおけるクォーラムベースのアルゴリズム

概要

• クォーラムベースのアルゴリズムは、データの読み取りや書き込みなどの操作に最低限のノード数（クォーラム）の合意を求めることで、整合性と耐障害性を確保する。
• 一部のノードで障害が発生した際のデータ破損を防ぐ。

主な概念

クォーラム

• ノードの総数（N）、書き込みクォーラム（W）、読み取りクォーラム（R）を定義する。
• 読み取り処理：
• 読み取りリクエストを一連のノードへ送り、R 個のノードから応答を受信すれば処理は成功する。
• 書き込み処理：
• 書き込みリクエストを一連のノードへ送り、W 個のノードが確認すれば書き込みがコミットされる。
• 整合性：
• R + W > N という規則により、読み取り集合と書き込み集合は少なくとも 1 ノードで重なるため、どの読み取りでも最新の書き込み済みデータを確認できる。
• 耐障害性：
• ノードで障害が発生しても、システムがクォーラムを形成できれば動作を継続できる（例：5 台中 3 台のシステムは 2 台の障害に耐えられる）。

例と用途

データレプリケーション

• クラスター全体でデータのすべてのコピーの整合性を維持する（例：Cassandra などのデータベース）。
• 相互排他（Maekawa's Algorithm）：
• ノードは共有リソース（クリティカルセクション）へアクセスする許可を自身のクォーラムへ要求し、一度に 1 ノードだけが入れるようにする。
• 合意（Paxos）：
• 分散システムが 1 つの値に合意するための基礎的なプロトコルで、リーダー選出とステートマシンレプリケーションに不可欠である。

主なパラメータ（URW モデル）

• N：データコピー（ノード）の総数。
• W：書き込みクォーラム（書き込みの確認に必要なノード数）。
• R：読み取りクォーラム（読み取りの確認に必要なノード数）。

S3 のクォーラムベースシステム：高可用性と整合性の確保

S3 互換システムにおけるクォーラムの原則

• 高可用性と整合性のため、クォーラムの原則（ノードの過半数による合意）を利用する
• クラスター構成やエッジ構成（例：Amazon S3 on Snowball Edge）に関係する

S3 に類似したシステムでの仕組み

分散合意

• モニターまたはマネージャーがクォーラム（通常は 3 台以上）を形成し、ノードの状態を追跡する
• 利用可能なストレージノードをクライアントへ通知する。
• 書き込み処理：
• ストレージノードの過半数（クォーラム）が確認応答を返した場合にのみ、書き込みが成功する
• クラスター全体でデータの耐久性と整合性を確保する。
• 読み取り処理：
• 最新データを保証するため、レプリカのクォーラムを読み取り対象とする。
• 耐障害性：
• レプリカが合計 2f+1 個あれば、f 個のノード障害に耐えられる
• クォーラムが維持されている限り、新しいリーダーを選出して処理を継続できる

主な例

Amazon S3 on Snowball Edge

• Snowball Edge デバイスのクラスターは、S3 互換ストレージにクォーラムを使用する
• デバイスの状態とデータの可用性を管理する。
• Ceph：
• モニターと OSD（Object Storage Daemon）でクォーラムを使用する。
• S3 互換バックエンドとして、クラスターの状態とデータの可用性を維持する。
• Object Storage Daemon（OSD）は、Ceph のような分散システムでデータを保存する中核プロセスである。ローカルディスク（HDD/SSD）を管理し、大量の非構造化データのレプリケーション、復旧、分散を処理する個々のストレージユニットとして機能し、スケーラブルで耐障害性のあるオブジェクトストレージの基盤となる。
• 分散合意ライブラリ：
• GitHub は、リーダー選出とクォーラムに S3 の条件付き処理（ETag）を使用する。
• OSD の主な機能：
• データストレージ：実際のデータオブジェクトをローカルファイルシステム（XFS など）に保存する。
• データ管理：クラスター全体でデータのレプリケーション（コピー作成）と復旧（失われたデータの再構築）を管理する。
• ハートビート監視：他の OSD の状態を確認し、Ceph Monitor へ報告する。
• ネットワークアクセス：保存データへのネットワークアクセスをクライアントに提供する。

S3 Core とクォーラムベースの比較

Amazon S3（Core）

• グローバルインフラストラクチャ全体で、強力な read-after-write consistency をネイティブに提供する
• ユーザーがクォーラムを明示的に管理する必要はない。
• クォーラムベースの
• S3（クラスター／エッジ）：
• ユーザー管理の S3 互換デバイスクラスター内でクォーラムの概念を適用する
• クラスター内の整合性と可用性を確保する

S3 のシステムレベルの可用性設計とキャッシュ層

中心となる概念

• ルーティング先となる複数のノードと、障害に備えた余力
• 99.99% の可用性目標を達成するよう構成し、サイジングする。
• 2020 年以前の
• read-after-write consistency
• 読み取りと書き込みの両方でサーバーの過半数へ到達する必要があり、両者が重なるため、リーダーにはライターが書き込んだ値が見えていた
• 質問：2020 年以前の S3 が read-after-write consistency ではなかったのはなぜか？
• 答え：キャッシュ層。
• キャッシュ層
• S3 のフロントエンドは、頻繁にアクセスされるオブジェクトを大量にキャッシュする
• 不整合な読み取り：最後に書き込まれた値 C ではなく B が返される
• キャッシュでは読み取りと書き込みが重ならない
• キャッシュには可用性上の重要な特性がある（複数のホストがリクエストを受信でき、障害を許容できる）
• キャッシュでは読み取りと書き込みに重なりがない
• 2020 年以前は、整合性が設計目標に含まれていなかったため、これは許容できる障害対処法だった。
• キャッシュ層の例：
• 空のキャッシュノードがあり、ストレージには値 B がある
• リーダーがキャッシュノード経由で読み取り、値 B が返されてキャッシュに保持される
• C の書き込みでオブジェクトを上書きし、レプリカへ永続化する（C C C）
• 値 B と C が別々のノードにキャッシュされる（2020 年以前の設計）
• 読み取りが以前のキャッシュノードへルーティングされ、値 B が返される（不整合な読み取り）

キャッシュコヒーレンシープロトコルによる重複問題の解決

最も要望の多かった機能：整合性

• 2020 年以前、整合性は最も要望の多かった機能だった
• 目標：キャッシュ層における重複問題を解決する。
• キャッシュコヒーレンシープロトコル
• 高速、効率的かつ可用である必要があった
• 一部のサーバーに障害が発生しても、複数のサーバーがリクエストを受信できる特性を維持する
• 解決策：複製ジャーナル。
• 複製ジャーナル
• ノードをチェーン状に接続した分散データ構造
• 書き込みはノードを順番に通過する
• 各ノードが次のノードへ転送する
• ジャーナルを通過した書き込みは、ストレージノードのクォーラムへ送信される
• ジャーナルは直近の履歴を追跡し、順序について合意する
• 例：A は B より前に来る
• クォーラムベースのシステムでは順序を正しく判断できなかった
• ジャーナルは変更に対して明確な順序を作る。
• シーケンス番号とウォーターマーク
• すべての書き込みに、時間とともに増加するシーケンス番号を割り当てる
• 例：A（シーケンス番号 1）、B（シーケンス番号 2）、C（シーケンス番号 3）
• ストレージノードは値とともにシーケンス番号を受け取る
• キャッシュには値とともにシーケンス番号を保存する
• キャッシュノードは、指定したシーケンス番号より後に書き込みがあったかを問い合わせられる。
• Witness
• システム
• 目的：インデックスへの書き込みのハイウォーターマークを追跡する
• Witness は実際のデータを保持する必要はなく、シーケンス番号だけを保持する
• Witness は最後のシーケンス番号を過大評価してもよい（呼び出し元に古いと伝えるのは安全）
• 古いと通知された呼び出し元はストレージから読み取り、正しい結果を取得する

動的再構成による障害許容と整合性の確保

Witness システム

• ジャーナルの隣にあるインメモリデータ構造（整数の配列）
• キャッシュノードは、キャッシュされた値より後に書き込みがあったかを問い合わせられる。
• 変更後の読み書きアルゴリズム：
• 書き込みはジャーナルへ送られる
• 読み取りは Witness と通信し、問題がなければキャッシュから返し、古ければストレージへアクセスする。
• 失われた障害許容力
• 当初のジャーナルアーキテクチャでは、ノードに障害が発生すると書き込みがシステム内を進めなくなる
• クォーラムは書き込みを並行して処理する一方、ジャーナルは書き込みを順番に通過させる
• ジャーナル内のノード障害により、システム全体が停止する可能性がある。
• 動的再構成
• 障害許容の問題を解決するために導入された
• ジャーナル内のノードは互いの可用性を監視する
• 常に相互に ping し、メッセージがシステム内を通過する
• 各ノードは隣接ノードの可用性を最新の状態で把握する
• 問題が発生すると、ノードはクォーラムベースの構成システムへジャーナルの再構成を要求する
• ノード障害から数ミリ秒以内に再構成が行われる
• 構成システム自体もクォーラムベースである。
• 結果
• 障害を許容し、読み取りと書き込みが重なるキャッシュ
• S3 は整合性と高可用性を両立するようになった
• 整合性を考慮して設計したことで、その導入時にも高可用性を維持した。
• システム全体の可用性という視点
• 選択できるサーバーが多数必要
• 一部で成功すればよい
• 障害に直面したとき、システムを迅速に再構成できる
• ジャーナルのようなシステムでも、クォーラムベースのアルゴリズムは常に存在する

実装レベルでの障害対応

障害を理解する

• 質問：何が故障し得るか？
• 相関障害、つまり同時に発生する障害が極めて重要
• 可用性を考えるうえで、相関障害が不可欠
• クォーラム設計：1 ノードの障害は許容できても、すべてのノードが同じ AZ またはラックにあってはならない

物理障害

S3 を物理面から俯瞰

• 複数の Availability Zone（AZ）
• 各 AZ に複数のサーバーラック
• 各サーバーに複数のハードドライブ。
• 物理障害の種類：
• 個別障害：ハードドライブのモーター故障、プラッターの傷。
• 相関障害：
• サーバー障害：接続されたすべてのハードドライブが故障したように見える
• ラック障害：ラック内のすべてのドライブが故障する（例：スイッチの不具合）
• AZ 障害：AZ 全体が停止する（例：停電）。
• 論理障害
• 例：フリートへの新しいソフトウェアのデプロイ
• 一度に少数のノードへデプロイし、徐々に拡大する
• 新しいソフトウェアを実行する一連のサーバーが障害ドメインを形成する
• 新しいソフトウェアにバグがあると、それらすべてのサーバーで同時に障害が発生する可能性がある
• 潜在的な障害に耐えられる、インテリジェントなデプロイ戦略が必要

相関障害を考慮した設計

複数の障害ドメインにワークロードを分散

• 耐久性と可用性のため、オブジェクトを複数の場所（例：AZ）へレプリケートする
• 相関する障害ドメイン（例：AZ、ラック、サーバー）で障害が発生しても、データを利用可能な状態に保つ

障害タイプを理解する

Fail-stop 障害

• サーバーまたはコンポーネントが機能を停止する（例：電源コードが抜ける）
• 耐障害システムでは検出と対応が容易。
• AZ 間のスイッチにおける Fail-stop 障害：
• 一部のリクエストは引き続き成功する（同じ AZ 内）
• その他のリクエストは失敗し始める（障害が発生したスイッチを通過するもの）
• 一部のリクエストは成功し、一部は失敗する曖昧な障害モードになる

曖昧な障害モードを考慮した設計

• 冗長性が鍵：AZ 間に複数のスイッチを設ける
• 各リージョンの 3 つの AZ をリング状に接続する
• リンク（例：AZ1 から AZ2）に障害が発生しても、迂回経路（AZ1 から AZ3 を経て AZ2）を利用できる
• 可用性の問題をレイテンシーの問題へ変換し、可用性を維持する
• 強力な思考モデル：ある種類の問題を別の種類へ変換する（例：可用性からレイテンシーへ）

ステートフルシステムにおける Fail-stop 障害の課題

ステートフルシステムにおける Fail-stop 障害

• S3 のようなシステムでは、推論が難しい
• 通常では到達し得ない状態につながる可能性がある。
• クラッシュ整合性
• Fail-stop 障害後、システムは整合性のある状態へ戻る必要がある
• 例：ファイルに 2 行のテキストを書き込む
• 通常の実行：ファイルには両方の行がある
• 実行中の Fail-stop 障害：ファイルには最初の行しかない可能性がある
• 障害がなければ到達し得ない状態に入る。
• 到達不能状態を考慮した設計
• この問題に対処する Shodstor（ストレージノードソフトウェア）に関する論文を執筆した
• 障害と並行処理が存在する状況で、到達可能な状態について推論することに重点を置く

Gray failure への対処

Gray failure

• Fail-stop よりも複雑な障害モード
• 例：
• S3 の PUT リクエスト
• インターネットから S3 フロントエンドサーバーへリクエストが届く
• フロントエンドサーバーがストレージノードへデータを分散送信する。
• Gray
• failure の定義
• 完全な停止（Fail-stop など）ではないものの、システムが予期せぬ動作をする障害
• 例：フロントエンドウェブサーバーはリクエストを受け付けるが、ネットワークの問題で一部のダウンストリームホストへ到達できない
• サーバーは失敗したリクエストにエラーを返すが、引き続きリクエストを受け付けて応答する。
• 再試行による Gray
• failure への対処
• 強力な手法：リクエストが失敗したら、別の経路（例：別のフロントエンドウェブサーバー）で再試行する
• AWS SDK には、意図的に別の IP アドレスへリクエストを再試行する高度な再試行戦略がある
• 再試行により、システム内の別経路を試せる。
• 分散システムにおける再試行の危険性
• すべてのサービスが失敗したリクエストを再試行すると、処理量が大幅に増幅する可能性がある
• 例：スタック最下層の障害によって、元のリクエストの 27 倍もの再試行が発生する可能性がある
• 過剰な再試行によりシステムが過負荷になる可能性がある。
• 再試行戦略の意図的な設計
• システムの過負荷を避けるため、再試行戦略を意図的に設計する必要がある
• 例：上位層で再試行されることを踏まえ、スタック下位層では再試行回数を減らすか、再試行しない
• システムを過剰な再試行から保護しながら可用性を確保する。
• 負荷による Gray
• failure
• ウェブサーバーに処理が集中し、リクエストの遅延として現れる
• 強力な仕組み：タイムアウト（クライアントは遅いリクエストをタイムアウトし、別の場所で再試行する）。
• タイムアウトの課題
• タイムアウトは完全ではなく、特に再試行と組み合わせる場合、考慮した設計が難しい
• 例：
• リクエストのキューを抱えた過負荷のウェブサーバー
• クライアントがタイムアウトし、別の場所で再試行する
• サーバーはクライアントの再試行を知らず、タイムアウトしたリクエストの処理を続ける
• その結果、クライアントが断念したリクエストに対し、サーバーが無駄な処理を行う。
• 輻輳崩壊
• サーバーが、タイムアウトして別の場所で再試行されたリクエストだけを処理する状態
• 連鎖反応：過負荷のサーバーが遅くなり、再試行とキューの蓄積がさらに増える
• サーバーが、再試行によって生じたタイムアウト済みリクエストだけに時間を費やす自己増幅サイクル。
• 回避策：キューの逆順処理
• キューが満杯の過負荷サーバーへ対処する仕組み
• キューの末尾から処理する（後入れ先出し）
• 不公平ではあるが、一部のクライアントに不利益を与えることで、他のクライアントを非常に高速に処理する

自己修復システムの設計

輻輳崩壊からの脱出

• キューの逆順処理：キューの末尾から処理する（後入れ先出し）
• 一部のリクエストを成功させ、低速でタイムアウト済みのリクエストのバックログを減らす
• バックオフと再試行：クライアントがバックオフし、よりゆっくり再試行する
• サーバーにバックログ解消の時間を与える。
• 準安定障害モード
• 元の問題が解消しているにもかかわらず、システムがタイムアウト済みリクエストの処理だけに時間を費やす状態。
• システムレベルの障害復旧
• 目標：S3 が手動介入なしに自己修復する
• 例：リクエストへ正常に応答していないウェブサーバー
• クライアントは別の場所で再試行するが、そのサーバーをサービスから外す必要がある。
• ヘルスチェック
• サーバーを自動修復するための重要なツール
• ヘルスチェックサーバーはウェブサーバーへリクエストを送り、機能を確認する
• サーバーがヘルスチェックに失敗すると、サービスから除外できる（例：DNS から削除）
• 障害中のサーバーへクライアントが到達できないようにして、障害を軽減する。
• AWS インフラストラクチャの
• S3 による利用
• S3 は、顧客も利用できるものと同じインフラストラクチャを使って AWS 上に構築されている
• ウェブサーバーのキャパシティ：Network Load Balancer
• DNS：Route 53
• NLB と Route 53 を使用してヘルスチェックを実装する

堅牢なヘルスチェックとシステム状態のグローバルビューの確保

単一ヘルスチェックの危険性

• ヘルスチェックサーバー自体に障害が発生し、ウェブサーバーの障害を誤検出する可能性がある
• 例：ネットワークに問題があるヘルスチェックサーバーが、すべてのウェブサーバーを異常と判定する
• サーバーとヘルスチェックシステムの両方の可用性を考慮して設計する必要がある。
• 複数の視点によるヘルスチェック
• S3 は複数のソースからヘルスチェックを行う：
• 同じリージョン
• 別のリージョン
• パブリックインターネット
• シグナルを組み合わせ、ウェブサーバーの状態を詳細に把握する
• 相関障害（例：ネットワークの問題）の診断に役立つ。
• ローカルな判断の回避
• 重要な原則：ローカルシステムがサービスの状態をローカルに判断することを決して許さない
• 例：元のヘルスチェックが、自身から見えるシステムの状態に基づいてローカルな判断を行う
• 分散システムでは、ローカルな判断による誤りを避けるため、グローバルな視点が必要。
• システム状態のグローバルビュー
• 例：障害が発生しつつあるハードドライブの検出と修復
• ソフトウェアが障害の兆候があるハードドライブを検出する
• 修復を開始する（例：電源の再投入、技術者による交換）。
• ヘルスチェック用のグローバルレートリミッター
• ヘルスチェックサービスがシステムを変更する前に、グローバルレートリミッターへ問い合わせる必要がある
• 例：ヘルスチェックが障害の兆候があるハードドライブを検出し、サービスから外そうとする
• ヘルスチェックサービスが異常動作した場合、レートリミッターがハードドライブの過剰な除外を止める。
• 可用性を考慮した設計のまとめ
• 可用性と正確性の目標を定義する
• 目標を満たすシステム全体のアーキテクチャを設計する（例：クォーラムベースのアーキテクチャ、強整合性）
• 障害モードを理解し、ローカルな判断に頼らず修復できるよう、システムの各部分を実装する