2016年8月4日
Dropboxが構築したMagic Pocketの中身：エクサバイトのストレージシステムの仕組み
(2016-05-06)by James Cowling
本記事は、原著者の許諾のもとに翻訳・掲載しております。
自社で構築した数エクサバイトのストレージシステム、 Magic Pocketを発表 して以来、多くの好意的なフィードバックをいただいています。この発表に続きまして、舞台裏からシステムの興味深い側面を見ていただくことができる技術ブログシリーズを投稿していこうと思います。保護の仕組み、運用ツール、ハードウェアとソフトウェアの境界線上の革新などです。しかし、まず、背景を説明する必要があるでしょう。本稿では、Magic Pocketのアーキテクチャ概略と設計で使われた基準についてお話しします。
紹介の投稿 で説明しましたように、Dropboxには、ファイルの内容と、ファイルやユーザについてのメタデータという2種類のデータが保存されます。Magic Pocketは、ファイルの内容を保存するのに使われるシステムです。保存するファイルは、ブロックに分割されて耐久性のためにレプリケーションされ、複数の地域にある当社のインフラストラクチャに分散されます。
Magic Pocketは、比較的単純なコアプロトコルを基盤としていますが、大きくて複雑なシステムでもありますので、どうしても簡単な説明で終わってしまう部分が出てくるでしょう。その場合、下のコメント欄にフィードバックをいただければ、今後の投稿で内容を掘り下げてご説明するよう努めます。
注意：社内では、毎回いちいち変だと思いながら「Magic（魔法の）」という単語を言わずに済むように、このシステムを簡単に「MP」と呼んでいます。本稿でもそうしたいと思います。
要件
イミュータブルなブロックの保存
Magic Pocketは、 イミュータブルなブロックを保存するシステム です。4メガバイトまでの暗号化されたファイルの塊を格納し、一度ブロックがシステムに書き込まれると、決して変化しません。イミュータブルであることによって、 随分 処理が楽になります。
ユーザがDropboxにあるファイルを変更すると、 FileJournal と呼ばれる別のシステムに全ての変更を記録します。この仕組みによって、スタック内で優先度が高い程可変性が上がるロジックを動かしながら、イミュータブルなブロックは単純に格納するだけになるのです。ミュータブルなブロックをネイティブで動作保証している大規模ストレージシステムはたくさんありますが、一般的には、下層に下りると、イミュータブルなストレージプリミティブに基づいています。
ワークロード
Dropboxの特徴は、データが 多い ことと、時間的局所性が高度であることです。データの多くは、アップロード後1時間以内に高頻度でアクセスされ、その後は頻度がどんどん下がっていきます。これには、理由があります。ユーザがDropbox内で頻繁に共同作業をしますので、ファイルは、アップロード後すぐに他のデバイスに同期される傾向にあるのです。しかし、確実に速いアクセスも必要です。例えば、1997年からの納税記録は恐らくそんなに頻繁には見ないでしょうが、必要な場合は、すぐに見たいと思うでしょう。当社には、かなり”コールドな”ストレージシステムがありますが、全てのブロックを少ない待ち時間で読み取るという要件があります。
このワークロードに対応するために、回転するメディア（”ハードディスク”のこと）に基づいてシステムを構築しました。耐久性、低コスト、記憶密度、非常に少ない待ち時間という利点があり、かつデータベースとキャッシュに半導体ドライブ（SSD）を確保しておけます。高度な初期レプリケーションと、最近のアップロードのキャッシュを行う一方、残りのデータには、より効率的なストレージエンコーディングを使っているのです。
耐久性
耐久性は、Magic Pocketにおいて譲れないものです。理論的には、耐久性は永久に保たれます。世界が滅亡するような小惑星衝撃による損失の方が、ランダムアクセスディスクの不具合より可能性が高いぐらいです。それならば、恐らくもっと大きな問題を心配するべきでしょう。データは、効率のために消失訂正符号を付与され、複数の地域で保存されています。この広範囲のレプリケーションによって、不測の事態や自然災害から確実に保護されるようになっているのです。
スケール
技術者として、これは面白い部分です。Magic Pocketは、初期の2桁ペタバイトの試作品から数エクサバイトの巨大なものへ、半年程度の間に進化しなければなりませんでした。これは、前例がない規模の変化です。この間、多くの時間をかけて考え、設計し、試作して、予測できるボトルネックを取り除かなければなりませんでした。この過程を通して、アーキテクチャが確実かつ十分拡張可能とすることができたので、不測の要件が出てきても対応することができたのです。
これまでに、不測の要件の例はたくさんありました。あるケースでは、通信量が突然増え、ネットワーククラスタをつなぐルータが飽和状態になり始めました。そのため、データ配置アルゴリズムとリクエストルーティングを変更し、クラスタ親和性（加えて、使用可能な記憶容量、クラスタ増加スケジュール等）をより良く反映させるようにしなければならず、当然クラスタ内ネットワークアーキテクチャも同時に変更しなければなりませんでした。
単純性
技術者なら、通常は複雑性が信頼性とは正反対であることを知っています。技術者の多くは、複雑なコンセンサスプロトコルを散々書いた経験から、 Paxos を再実装するのに丸1日かけるのは、普通は良いことではないと知っています。MPは、定足数によるコンセンサスや分散調整をできる限り避けます。また、フォールト・トレラントかつ拡張可能な場合には、集中型調整をよく利用します。ブロックインデックスに分散ハッシュテーブルやトライ木を選ぶこともできたのに、代わりにシャード分割された巨大なMySQLのクラスタを選択することがたびたびありました。これは、開発を簡素化し、分からないものを最小限にするという意味で、非常にすばらしい決定だったと後で分かりました。
データモデル
アーキテクチャそのものの前に、まずは、ストレージに格納されているものを理解しましょう。
MPは ブロック を保存します。これはファイルを外部から分からない形に固めたもので、容量は最大4MB です。
ブロックは圧縮され、暗号化されてMPへ渡されて保存されます。ひとつひとつのブロックにはキーまたは名前が必要で、ほとんどのユースケースではブロックにSHA256 ハッシュ を使っています。
しかしながら、数エクサバイトのストレージシステムの中では4MBは非常に小さなデータユニットであり、小粒すぎて、ディスクの交換やあるデータに消失訂正符号を付与する必要が生じても身動きがとれません。この問題を解決するために、ブロックを1GBの論理的なストレージの入れ物にまとめ、この入れ物を バケット と呼んでいます。同じバケット内のブロックに規則性がある必要はありません。たまたま、ほぼ同じタイミングでアップロードされたブロックというだけのことです。
信頼性を保つため、バケットは複数のハードウェアにレプリケーションされる必要があります。最近では、アップロードされたブロックが直接複数のハードウェアにレプリケーションされ、ストレージの効率化のため、最終的にブロックを入れたバケットが統合され、消失訂正符号が付与されます。これは ボリューム と呼ばれ、一連の物理ストレージのノード上でレプリケーションされた1つ以上のバケットを参照するために使われます。
要約： ブロック は ハッシュ で区別され、 バケット に書き込まれます。それぞれのバケットは、レプリケーションされるか、または消失訂正符号の形式で、複数のハードウェアにまたがったボリュームに格納されます。
アーキテクチャ
さて、要件とデータモデルが分かりました。Magic Pocketはどんなふうでしょうか？ こんな感じです。
上の図は大したものには見えないかもしれませんが、重要です。MPとは複数ゾーンのアーキテクチャであり、アメリカ合衆国の西部、中部、東部でサーバクラスタとなっています。MP内で各ブロックは最低2つの別々のゾーンへ個別に格納され、そのゾーン内部で確実にレプリケーションが作られます。こういった冗長性のおかげで十分に自然災害や大規模な停電への備えができます。さらに、明確な管理ドメインと理論上の境界が確立でき、コンフィギュレーションの誤りやゾーン間の絶え間ないやり取りから生じる輻輳を避けることができます。
（他に、複数ゾーンアーキテクチャを取り入れたアクセス頻度が低い（”よりコールドな”）データ向けの拡張機能がいくつかあります）
実際、ほとんどの機能はゾーンの中で行われています。入ってみましょう。
上の図のコンポーネントを１つずつ見ていきます。
フロントエンド
このノードはシステムの外から来たストレージのリクエストを受け付けます。同時にMagic Pocketへのゲートウェイになっています。ここではブロックの格納場所を決め、ブロックの読み込みや書き込みのためにコマンドを MP内へ発行します。
ブロックインデックス
ブロックインデックスは各ブロックが格納されるバケットの位置を示します。下記の図式のような巨大なデータベースとして考えてください。
ハッシュ → セル、バケット、チェックサム
（データ消去やゾーン間レプリケーションなどの機能をサポートするため、実際の図式はもう少し複雑です。）
ブロックインデックスは、シャード分割された巨大なMySQLのクラスタで、RPCサービスのレイヤに対応します。また、データベース操作と信頼性のための多くのツールを備えています。当初は専用のkey-valueストアを使う計画でしたが、MySQLのほうが優れていると判明しました。すでにDropboxのスタックを横断して数千ものデータベースノードが稼働していたので、大規模なMySQLの管理を通じて得た運用能力を大きく伸ばすことができたのです。
最終的にはもっと洗練されたシステムが作れるかもしれません。しかし今はこれで満足しています。key-valueストアは魅力があり、高いパフォーマンスを提供します。しかし、データベースは高い信頼性を持ち、長い年月にわたって当社のスキームと機能を容易に拡張できる豊かなデータモデルを提供するものです。
ゾーン間レプリケーション
ゾーン間レプリケーションのデーモンは、非同期的に全てのブロックを1つのゾーンから別のゾーンへレプリケーションします。それぞれのブロックは、ローカルでアップロードされてから1秒以内に別のゾーンへ書き込まれます。レプリケーションの時間差は当社の耐久性モデルに組み込まれ、データはローカルのゾーン内で十分に広範囲にわたってレプリケーションされています。
セル
セルは、それ自体で独立した論理ストレージのクラスタです。およそ50ペタバイトの生データを保存します。MPにさらに容量を増やしたい時は、一般的には必ず新しいセルが必要になります。セルは完全に論理的に独立しているため、セルそれぞれをラックから取り除けます。セル内において、物理的な多様性を最大限に確保するためです。
セル内でどのように機能しているか、内部を見てみましょう。
オブジェクトストレージデバイス（OSD）
セルの最も重要な特徴はOSDです。このディスクいっぱいのストレージの箱は、単体マシンなら1ペタバイトを超えるデータ、ラックごとなら8ペタバイトを超えてデータを持つことが可能です。このデバイスには、キャッシュやディスクスケジュール、データの妥当性などの管理においてとても複雑なロジックが必要です。しかしその他のシステムの観点から考えると、”頭の悪い”ノードと言えます。なぜなら、OSDはブロックを保存しますが、セルトポロジーを理解しているわけでも、分散型プロトコルに関与しているわけでもないからです。
レプリケーションテーブル
レプリケーションテーブルはセル内のインデックスです。インデックスは、データの論理バケットそれぞれと、バケットが格納されているボリュームおよびOSDをマッピングしています。ブロックインデックスのように、レプリケーションテーブルはMySQLデータベースとして保存されていますが、もっと小さい上に更新頻度もより低いです。レプリケーションテーブルに対し実行されるセットは、データベース上のメモリ内に適合しています。こういったデータベースは、少ない数の物理マシン上でも、読み込みスループットがかなり高くなります。
レプリケーションテーブルにおける図式は次のようになります。
バケット → ボリューム
ボリューム → OSD、オープン、型、世代
ここで重要なコンセプトはオープンフラグです。オープンフラグは、ボリュームが”オープン”か”クローズ”かを示します。ボリュームはオープンになると、新しいデータにのみ書き込みを許可します。クローズの場合は変更不可となり、セル内で安全に動かせるようになります。一度に全てのポイントがオープンとなるのは、少数のボリュームのみです。
型は、ボリュームの型を特定します。そのボリュームがレプリケーションされたものなのか、消失訂正符号を付与する仕組みの一つによってエンコードされたものなのか、といった型です。世代数は、データの一貫性を確実にするために使われます。例えば、ディスク破損した際にリカバリをしたり、ストレージレイアウトを最適化したりするために、ボリュームを移動させる場合のためです。
マスター
マスターという考え方は、セルの管理人やまとめ役としてとても優れています。システム内の複雑なプロトコルは、ほとんどがこのマスターにあります。マスターの主な役割は、OSDを監視し、一つでも破損が生じたら、データ修復の処理をトリガすることです。また、バックグラウンド処理も調整します。例えば、バケットがいっぱいになった時に新しいストレージバケットを生成したり、データが削除された時にガベージコレクションをトリガしたりします。ガベージコレクションが実行された後も、バケット一つ一つが小さくなりすぎたら、複数のバケットをマージします。
レプリケーションテーブルは、信頼できるボリュームの状態を保存します。これは、マスターをそれ自身で完全にソフトステートとするためです。マスターはデータ平面上には存在していないことを覚えていてください。つまり、生きたトラフィックはマスターを通らないため、マスターがダウンしてもセルは読み込みし続けることが出来るのです。マスターが無くても、セルは書き込みを受け取ることだって出来ます。その書き込みによって、最終的に利用可能なストレージバケットが無くなってしまうことはありえます。しかし、マスターが新しいストレージバケットを作る必要はありません。マスターが新しいバケットを生成するために振る舞わなくても、書き込むための他のセルが常に大量に存在するからです。
セル1つに対して1つのマスターが実行されます。このため、複雑なデータ格納場所を決定する処理を一点に集中できます。非常に複雑な分散型プロトコルを使用する必要もありません。この集中モデルでは、セルそれぞれのサイズに制限がかけられています。これにより、メモリとCPUがオーバヘッドしボトルネックとなってしまうことなく、100ペタバイト近くのデータを扱うことができるのです。幸い、複数のセルを持つ方式は、デプロイする観点から見てもとても便利です。複数のセルを持つと独立性が高くなり、連鎖して障害が発生してしまうことを回避できるのです。
ボリュームマネージャー
ボリュームマネージャーは、セルにとって縁の下の力持ちです。マスターからのボリュームを動かすリクエストや、ボリュームに消失訂正符号を付与するリクエストに応えます。一般的には、複数のOSDからの読み込み、他のOSDへの書き込み、そしてその後に処理を完了させるためにマスターへコントロールを返す、といったことを意味します。
ボリュームマネージャーのプロセスはOSDと同じ物理ハードウェア上で実行されます。これにより、セル内でアイドル状態のストレージハードウェアをまたがって要求される重い通信容量を、分割できるようになります。
プロトコル
ふう。ここまでは大丈夫でしょうか。非常に高度なMagic Pocketのアーキテクチャを論理的に理解されていることを願っております。MPのいくつかの核となるプロトコルについて、かなり大まかにですが概要をまとめておきます。また、今後の投稿で詳しく説明することも考えています。幸い、これらのプロトコルはもうかなり簡単です。
Put（置く）
フロントエンドはPutリクエストを受け取るよりも前に、数個の情報を準備しています。つまり、フロントエンドは、新しい書き込みを受信可能な、開いているボリュームのリスト以外にも、どのぐらいの容量が空いているのかを確認するために、各セルと定期的に交信しています。
Putリクエストを受信すると、フロントエンドは、まず（ブロックインデックスを使って）そのブロックがすでに存在するかどうかを調べます。そして、そのブロックを保存する対象となるボリュームを選択します。セルの負荷が均一に振り分けられ、ストレージクラスタ間のネットワークトラフィックが最小になるように、セルからボリュームが選ばれます。それから、フロントエンドは、現在ボリュームを保存しているOSDを確認するために、レプリケーションテーブルを参照します。
フロントエンドはこれらのOSDにストア命令を発行します。この命令が、応答の前にディスク（またはオンボードSSD）にそのブロックを全て同期させます。成功すれば、フロントエンドはブロックインデックスに新しいエントリを加え、正常にクライアントに戻ることができます。でも、OSDが1つでも途中で失敗すれば、フロントエンドは別のボリュームや、もしかすると別のセルに対してすぐに再試行します。ブロックインデックスが失敗すれば、フロントエンドは他のゾーンに向け、リクエストを転送します。マスターは失敗した処理の部分書き込みをきれいにするために、定期的にバックグラウンドでタスクを実行します。
*注釈：
- ブロックを置く
- ブロックの存在を確認
- ボリュームを検索する
- OSDに書き込む
- ブロックマッピングを書き込む
- 応答*
裏側ではいくつか微妙な細かい部分がありますが、結局のところ、どちらかというと単純です。フロントエンドがボリュームの中でOSDのサブセットへの書き込みを要求されるだけのような定足数に基づくプロトコルを採用していたなら、より複雑になるという犠牲を伴いますが、このリトライのいくつかを避け、もしかしたらより低いテイルレイテンシを実現していたかもしれません。再送信ベースのスキームのタイムアウトの賢明な管理は、既に低いテイルレイテンシという結果となり、非常に満足のいくパフォーマンスが得られています。
Get（取り出す）
Putプロトコルを理解すれば、Getを提供するプロセスの説明は不要でしょう。フロントエンドはブロックインデックスからセルとバケットを調べ、それからレプリケーションテーブルからボリュームとOSDを調べます。そしてそのOSDの1つからブロックを取り出し、もし無効な場合は、もう一度やり直します。
これまで述べたように、レプリケーションされたデータと消失訂正符号をMPに保存します。レプリケーションされたボリュームから読み取ることは簡単です。その理由はボリュームの各々のOSDが全てのブロックを格納するためです。
注釈：ブロックA、レプリケーションされたデータ
消失訂正符号化されたボリュームからの読み取りは、もう少し扱いに注意が必要かもしれません。各ブロックは、与えられた1つのOSDから丸ごと読み取れるようにエンコードするので、大部分の読み取りは単独のディスクスピンドルがヒットします。これは、ハードウエアの負荷軽減にとって重要なことです。もしそのOSDが利用できないなら、フロントエンドは他のOSDからエンコードされたデータを読み込み、ブロックを再構築する必要があります。この再構築には、ボリュームマネージャーが用いられます。
注釈：ブロックA、データエクステント、パリティエクステント、消失訂正符号化されたボリューム
上図のエンコードのスキームで、フロントエンドはOSD1から緑色で強調した部分、ブロックAを読み取ることができます。この読み込みに失敗すると、赤色で強調した部分、他のOSDの充分な数のブロックから読み込むことにより、ブロックAを再構築することができます。実際のエンコードは、この説明よりももう少し複難です。また、大部分の失敗シナリオでは、OSDのより小さなサブセットから再構築ができるように最適化されます。
修復
マスターは、セル内のボリュームを管理したり、処理が失敗した後にクリーンアップしたりするために様々なプロトコルを実行します。しかし、マスターが行う最も重要な処理は修復です。
修復は、ディスクに障害が発生するたびにボリュームを再レプリケーションするための処理です。マスターは、私たちのサービス発見システムを介して継続的にOSDの状態を監視し、OSDがいったん15分間オフラインになると修復処理を起動します。15分という時間は不要な修復を起動することなく、ノードを再起動するのに十分な長さです。しかし、迅速なリカバリを提供し、どんな脆弱な間隔も最小化できるくらい十分短いです。
ボリュームはセル全体にややランダムに分散しており、OSDはおのおの数千ずつのボリュームを保持しています。これは、もしOSDを1個失っても、他の何百ものOSDからいっせいに、ボリュームの完全なセットを再構築できることを意味します。
上の図では、OSD 3に障害が発生しましたが、ボリュームA、BおよびCをOSD1、2、4および5からリカバリすることができます。実際には、1個のOSDにつき数千のボリュームがあり、そのデータを数百のOSDで共有しています。これにより、数百のネットワークカードと数千のディスクスピンドル全体にわたる再構築トラフィックを均等にすることができ、その結果、リカバリ時間を最小限に抑えることができます。
OSDに障害が発生した時にマスターが最初に行うことは、障害が起きたOSD上にあった全てのボリュームをクローズにして、局所的にこの変更を反映するよう他のOSDに指示することです。ボリュームはクローズになっているので、新しい書き込みを受け付けることはなく、ボリュームを他に移動しても安全だということが分かっています。
それからマスターは 再構築計画 を作成します。その計画では、できるだけ多くのOSDに負荷が均等に分散されるような形で、コピー元OSDのセットとコピー先OSDのセットを選択します。このステップにより、特定のディスクまたはマシン上でトラフィックが急増するのを回避することができます。再構築計画によって、1個当たりのOSDに必要なハードウェアリソースはかなり少なくて済みます。また調整の中心となるマスターがなければ再構築計画を作り出すのは難しいでしょう。
データ転送プロセスには触れませんが、それには、コピー元からコピー先にデータをコピーし、必要に応じて消失訂正符号を付与して、再びマスターに制御を戻すボリュームマネージャーが関わっています。
最後のステップはかなり単純ですが、非常にクリティカルです。この時点で、ボリュームは、コピー元OSDとコピー先OSDの両方に存在しますが、データの移動は、まだコミットされていません。もし、マスターがこの時点で動かなくなると、ボリュームは元の場所に残ったまま、新しいマスターによって再び修復されます。修復処理をコミットするには、マスターは最初に新しいOSD上のボリュームの 世代番号 をインクリメントし、その後、レプリケーションテーブルを更新して、ボリュームとOSDの新しいマッピングを世代（コミット・ポイント）付きで保存します。世代番号をインクリメントしたので、たとえ故障したOSDが復旧しても、どのOSDがそのボリュームを保持しているか混乱することはないと分かっています。
このプロトコルによって、どのノードにいつ障害が起きても、システムが不整合状態にならないことが保証されます。私たちは、運用環境であらゆる異常を経験してきました。一例を挙げると、データベースのフロントエンドがフリーズしてしまい、復旧してレプリケーションテーブルにリクエストが転送されるまで、丸1時間かかったことがありました。その間、マスターも機能しなくなったので、再起動し、完全に異なる修復処理セットを発行しました。私たちの整合性プロトコルは、このような何が起きるかわからない障害に対しても完全に強固である必要があります。マスターはまた、照合確認、つまりOSDの状態を確認し、失敗した修復または不完全な処理をロールバックするなど多くのバックグラウンドプロセスを実行します。
オープン/クローズボリュームモデルは、ライブトラフィックがバックグラウンド処理を妨げないのを保証する鍵となります。また、このモデルによって、この2種類に分ける方法を実行しなかった場合よりもはるかに簡単な整合性プロトコルを使用することができます。
まとめ
ここまで読んでくれて、ありがとうございます！ この記事がMagic Pocketの動作や私たちのモチベーションを少しでも伝えられたら幸いです。
ここでの設計の第一原則は 常にシンプルであることです！ 分散ストレージシステムを設計することは大きな難題ですが、大きな規模で確実に動作し、正常に稼働していることを保証するために監視や検証を行うシステムやツールの全てをサポートするものを構築するのは、 もっとずっと 難しいことです。また、クールで目新しいからではなく、問題に対して適切なソリューションとなるように技術的な意思決定を行うことも非常に重要です。MPの大部分は、6人以下のチームによって作られました。チームは、メンバーに重要な事に焦点を当てるように要求し、プロジェクトの成功に大きな役割を果たしました。
詳細を割愛したところも確かに多々あります。（ 「ちょっと待った！ X、Y、Zが発生した場合、これは動作しないよ！」 というあなたの反応に備えて、私たちはそれについて考えてあります。保証します）。今後のブログ記事では、このような大規模システムの構築・運用に関する具体的な側面についてより詳細に論じていきますので、引き続きご注目ください。
