GoogleのJeff Dean（Senior Fellow, システム & インフラグループ）による、Velocity Conference 2014のキーノートスピーチです。

Jeffは、オブジェクト指向言語によるプログラムの最適化で博士号を取得。DEC/Compaqの研究所の勤務をへて、1999年にGoogleに入社。以降、BigTable / MapReduce / Spanner / Google Translate / Google Brainなど、同社の大規模分散システムの構築に一貫して携わってきています。

例えば、検索結果のレスポンスを向上させるには、その裏で、Web / Images / Local / News / Video / Blogs / Booksなどのサブシステムへのクエリを走らせ、その計算結果を短時間でまとめなくてはいけないチャレンジがある。

Googleのサーバは共有環境。ハードウェアの有効利用という意味ではよいが、一方で、台数が増えれば増えるほど、想像してない障害が起きる可能性があがるということ。

（大規模分散システムでのパフォーマンスの向上は）ロングテールとの戦いになる。例えば、あるサーバのレスポンス時間が平均10ミリ秒とかなり高速だが、99%tileでは1秒かかるとする。それを1台だけ使うと、リクエストの1%が1秒以上かかるということだが、それを100台使ってレスポンスをまとめなくてはいけないと、63%のリクエストの処理が1秒かかってしまう。

遅延を減らす基本的なテクニックとしては、

• サービスの優先順位をつける。サーバにおけるリクエストのキューや、ネットワークトラフィックの優先付けする。
• サイズの大きなリクエストは分割する。
• パフォーマンスコストの大きなバックグランドジョブを調整する。上限値を設定したり、負荷が下がるまで実行を先延ばしする。

次に、障害耐性と障害変動性を考慮する。RAIDディスク、ECCメモリ、分散システムのコンポーネントなど、予備のリソースに頼るが、

• 障害耐性の考え方は、「信頼できないものをうまく組み合わせて、信頼できる状況をつくる。」ということ。ハードウェアがクラッシュなどが起きる確率は、1日数十秒という単位。
• 障害変動性の考え方は、同じ予備のリソースに頼るが、「何が起きるか予測しがたい状況の中、予測できるかたちをつくる。」ということ。遅延などはかなり頻繁に起きる。ミリ秒単位で起きるので、それへの準備が必要。

遅延への対処のパターンとしては、

• 1) リクエスト間の対応: システムの最近のメトリックスを取得/分析して、将来のリクエストで起きる遅延を改善するアクションをとる。典型的なのは、サーバ間のロードバランスの調整。数十秒から数分の単位での対応。
• 2) リクエスト単位での対応: 優先度の高いリクエストを遅いサブシステムでどう対応するか？ユーザを待たせている今すぐに対応しなくてはいけない。

1) の具体策としてはまず、動的なパーティションの設定。

• 大規模なデータや計算は、マシン当たり10-100個のパーティションを設定して分散させる。
• 1台のマシンで負荷が高くなりすぎれば、適切な負荷になるまで必要な数だけのパーティションを他のマシンで処理するように移せる。かなり柔軟に調整できる。
• 1台のマシンが障害を起こしても、そこに入っていたパーティションの処理を他のマシンに肩代わりさせる。もし100個のパーティションが入ったマシンがダメになっても、もし他にマシンが100台あれば、その全てのパーティションが一気に分散処理できる。障害復旧の時間が短い仕組みにできる。

次に、優先的なレプリケーション。

• 使用頻度の高いアイテムを多くレプリケーションする。
• 例えば、クエリシステムにおいて、静的なアイテムの対応しては、アクセス頻度が高く、アクセスできなかったときのデメリットが大きい重要なドキュメントを、あらかじめ多くコピーを用意する。また、動的には、中国語でのクエリが増えてくると、中国語のドキュメントのコピーを増やすといった対応が考えられる。

また時には、遅延すると仮稼働に変えることがある。

• サーバのレスポンスが遅くなった際、処理しているデータのせいかもしれないけど、よくあるのが、干渉の影響。同じ共有サーバで処理している他のジョブが、CPU/ネットワークの負荷を高くしていて、それの影響を受けてしまう可能性。
• 他のサーバに、処理が遅くなったサーバのパーティションのコピーを用意して処理させる。処理が遅くなったサーバには、偽のリクエストを送り続けて、遅延が改善するか監視し、問題がなくなれば本番に復旧させる。

2) のリクエスト単位における障害変動性への対応とは、1件の優先順位の高いリクエストの処理内でアクションをとること。達成したいのは、遅延を減らし、リソースを過度に使用せず、安全にシステムを稼働させること。

もし1件の悪いリクエストが、大規模な分散システムのツリー内でどんどん伝播していくと、最後には多くの末端のサーバ群が障害を起こす。それを防ぐために、わずかな遅延にはなるが、カナリアリクエストを送る。つまり、リクエストを、まずは全体のサーバツリーの中での一つの経路だけに送り、問題がなければ、全体に伝播させるという方法。もし、問題があれば、もう一度、一つの経路でリトライして確認する。

また、バックアップへのリクエストにも工夫をこらしている。

• 遅延を起こさないように用意したレプリカにクライアントからリクエストが送られて処理される場合、特に多くのクライアントと多くのレプリカがあれば、どこのレプリカのキューが処理が早いかは把握しづらい。
• 一つのレプリカに送ったリクエストが処理されないので、別のレプリカにもリクエストを送り、そちらの方が早く結果が返ってくると、最初のレプリカへのリクエストをキャンセルする。このパターンだと、遅延は抑えられる可能性が高いが、最初のレプリカでも処理が既に開始されている可能性が高いので、処理コストがかかってしまう。
• そこで新たな方法として、まずは最初のレプリカサーバにリクエストを送る。そこには、別のレプリカサーバにもリクエストが送られる旨のタグがついている。2ミリ秒以内に、別のレプリカサーバにリクエストが送られる。そこには、最初のレプリカサーバにもリクエストが送られた旨のタグが付与される。どちらかのサーバで、リクエストの処理が始まれば、すぐにその情報がもう片方のサーバへ送られ、処理がキャンセルされる。
• この方法だと、バックアップを利用しないケースと比較して、99%tileで40%前後改善する。
• 下記のような別のバージョンも考えられる。
  • 一定以上の遅延の際は、更に三つ目のレプリカサーバにリクエストを送る。
  • 他でリクエストの処理が始まった情報を受取ったサーバのキューを削除するのではなく、優先順位を下げる。
  • リードソロモン符号のような仕組みを導入する。

#google