皆さんはシステムを設計する時にスケーラビリティや耐障害性についてどうやって見積もっていますか? The Site Reliability Workbookの第12章では、Google内部で利用されているシステムの設計方法 “Non-Abstract Large System Design”について紹介しています。 この記事ではその設計方法について解説します。

Non-Abstract Large System Design (NALSD) とは

どんなシステムも最終的には、ネットワークに接続されたコンピューター上で実行します。 Googleの長年の経験から、SREは実リソースを見積もる力が必要だと分かりました。 そのためには、Non-Abstract (非抽象的) な設計する能力が必要となります。

NALSDは反復的に設計を繰り返し、各設計の長所・短所を調べます。 それぞれの設計フェーズでは、以下の質問をします。

  • 実現可能か : その設計は魔法を使わずに構築できるか?
  • もっと良い方法があるか : 合理的に実現できるもっと簡単な方法はないか?
  • 実行可能か : 実際の制約条件(予算や時間など)の範囲内に収まるか?
  • 回復性はあるか : 障害が発生するとシステムはどうなるか?

ここからはGoogle AdWordsを例にしてNALSDの設計プロセスを紹介します。

Google AdWords

Google AdWordsはGoogle検索にテキスト広告を表示します。 広告主はダッシュボード上で、広告とキーワードごとのCTR (click-through rate) という、広告が表示された回数に対するクリックされた割合を確認できます。

初期要件

広告主が気にするのは、ダッシュボードがすばやく表示され、表示されるデータが最新のものであることです。 各設計フェーズで一貫したゴールを設定するために、ダッシュボードに対して以下のSLOを設定します。

  • 99.9%のダッシュボードのクエリが1秒未満で完了
  • 99.9%のCTRが5分以内のデータ

検索クエリと広告クリックは、以下のレートを想定します。

  • 500,000件/秒の検索クエリ
  • 10,000件/秒の広告クリック

単一マシン

CTRの計算は、検索システムと広告配信システムのログから計算できます。 Web検索時のログをクエリログ 、広告クリック時のログをクリックログと呼びます。 それぞれのログには以下の情報が含まれます。

  • クエリログ … 時刻、クエリID、検索キーワード、広告ID
  • クリックログ … 時刻、クエリID、広告ID

ダッシュボードを表示するのに、毎回クエリログとクリックログをスキャンするのは非効率的です。 クエリIDと検索キーワードにインデックスを持つデータベースを使用すると、1秒以内に結果がわかるはずです。 2つのログをクエリIDでJOINすると、それぞれの検索でのCTRが分かります。

計算

まずはシステムの容量を見積もるために、ぞれぞれのログの大きさを計算します。

  • 時刻 … 64bit整数型
  • クエリID … 64bit整数型
  • 検索キーワード … 500バイト未満の文字列
  • 広告ID … 3つの64bit整数型
  • その他のメタデータ … 500 - 1,000バイトの情報

余裕のある見積もりをするために、各クエリログを2KBに切り上げます。 24時間で生成されるクエリログは

  • (5✕105 クエリ/秒) ✕(8.64 ✕104 秒) ✕(2✕103バイト) = 86.4TB/day

クエリ件数に対して2%のクリックが発生し、データベース上のインデックスのオーバーヘッドを考慮して、1日辺り100TBに切り上げます。 1日あたり100TBのディスク書き込みが発生するので、新たな考慮事項が挙げられます。 たとえば一般的な4TB HDDは200IOPSです。 各ログに対して1回ディスク書き込みするなら、2,500ディスクが必要となります。

  • 5✕105 クエリ/秒 / (200IOPS) = 2,500 ディスク

評価 計算結果を無視したとしても、他の懸念点もあります。 1台のマシンに収めると、単一障害点が多くなってしまい、マシンの再起動だけでもSLOを下回る可能性があります。

この設計は実現不可能に思えますが、考察することは無駄ではありません。 この情報を元に次の設計を考えます。

LogJoiner

全てのクエリからオンデマンドにクエリIDで検索できるデータストアを QueryStore と名付けます。 詳しい振る舞いについてはBigtableを参照してください。

CTRダッシュボードには、広告IDと検索キーワードに対する、表示回数とクリック回数が必要です。 LogJoinerはクリックログをストリーム処理して、QueryStoreのデータにJOINします。 その結果を広告IDと検索キーワードをキーにした ClickMap というデータストアに保存します。 また広告IDと検索キーワードをキーにした、クエリIDを QueryMap というデータストアに保存します。

LogJoinerの基本設計 (The Site Reliability WorkbookのFigure 12-1より)

計算

LogJoinerがクリックログを処理するのに必要なネットワークスループットは以下のとおりです。

  • (104 クリック/秒) ✕(2 ✕103 bytes) = 160 Mbps

LogJoinerはクエリIDから該当のクエリログをJOINするために、QueryStoreにアクセスします。 その時に必要なネットワークスループットは以下のとおりです。

  • (104 クリック/秒) ✕(8 bytes) = 640 Kbps
  • (104 クリック/秒) ✕(2 ✕103 bytes) = 160 Mbps

LogJoinerはJOINした結果から、クエリID、広告ID、検索キーワード、時刻をClickMapに保存します。 これらのデータは1KB未満であるため、保存に必要なネットワークスループットは以下のとおりです。

  • (104 クリック/秒) ✕(103 bytes) = 80 Mbps

合計で400Mbpsなので、実現可能な転送速度です。

続いてデータサイズです。 ClickMapはクリック毎の時刻とクエリIDが保存されます。 広告IDと検索キーワードは線形係数が小さいので無視します。 ClickMapの1日あたりのデータサイズは次のとおりです。

  • (104 クリック/秒) ✕(8.64 ✕104 秒) ✕(8 bytes + 8 bytes) = 14 GB/day

オーバーヘッドを考慮して1日20GBに切り上げます。

QueryMapはクエリIDごとの広告IDを保存します。 各検索には3つの広告IDが表示されるので、1日あたりのQueryMapのデータサイズは以下のとおりです。

  • 3 ✕ (5 ✕105 クエリ/秒) ✕(8.64 ✕104 秒) ✕(8 bytes + 8 bytes) = 2 TB/day

2TBは十分小さいですが、単一マシンの設計よりハードドライブに保存できない事がわかっています。 次のステップではLogJoinerのシャーディングを考えます。

LogJoinerのシャーディング

クエリログとクリックログをJOINできることがわかりました。 クエリIDのハッシュ値をシャード数Nでmodして送信先のLogJoinerを選ぶと、複数のLogJoinerを並列に実行できます。 クリック数が増えても、LogJoinerを水平スケールすることで対応できます。

シャーディングの仕組み (The Site Reliability WorkbookのFigure 12-2より)

QueryMapが必要なIOPSを維持するには、同様にシャーディングが必要です。 QueryMapは広告IDでシャーディングします。

システムにスケーラビリティがあるのは分かりました。 次の問題は信頼性です。 今の設計ではLogJoinerの結果を保存する前にクラッシュすると、その作業をやり直す必要があります。 そのためダッシュボードへの反映が遅れてSLOに影響します。 LogSharderが2つのシャードに同じログを送ることで、1つのLogJoinerに障害が発生しても問題ありません。

シャードの複製を作成することで、障害による影響を減らせますが、ゼロにはできません。 それはエラーバジェットがリスクをカバーします。

評価 シャーディングされたコンポーネントで処理できるのが分かりました。 しかし1つのデータセンターでホストすると単一障害点となります。 複数データセンターを使用するよう設計を進化する必要があります。

ログのシャーディング (The Site Reliability WorkbookのFigure 12-3より)

複数データセンター

複数データセンターで実行可能なClickMapは実現可能でしょうか? 一般的な分散システムを構築するときは、3または5のレプリカを作成して、Paxosのような合意アルゴリズムを使用します。 果たしてこれは実際に機能するでしょうか。 またどんなリソースがどれくらい必要になるでしょうか。

計算 数百km離れたDC間でPaxosアルゴリズムを実行するにはおよそ25ミリ秒かかるのがわかっています。 つまり毎秒40回までのオペレーションしか実行できません。 LogJoinerのシャーディングの設計で各ログにレプリカを導入するので、1秒あたりのトランサクション数を2倍にし、20,000クリック/秒と1,000,000クエリ/秒で計算します。

1秒あたりのクエリ数をオペレーション数で割ることで、必要なタスクの最少数が分かります。

  • (1.02 ✕106 クエリ/秒) / (40 オペレーション/秒) = 25,500 タスク

各タスクのメモリ量 (2TBのQueryMap) は

  • (4 ✕1012 bytes) / (25,500 tasks) = 157 MB/task

そしてマシン毎のタスク数は

  • (6.4 ✕1010 bytes) / (1.57 ✕108 bytes) = 408 タスク/マシン

1台に多くのタスクを集約できることが分かります。

ClickMapとQueryStoreの合計スループットは

  • (1.02 ✕106 クエリ/秒) ✕(2 ✕103 bytes) = 16 Gbps

タスク毎のスループットは

  • 16 Gbps / 25,500 tasks = 80 KB/秒 = 640 Kbps/タスク

そしてマシン毎のスループットは

  • 408 tasks ✕640 Kbps/task = 256 Mbps

各マシンに64GB RAMがある場合64台のマシンでデータを提供でき、ネットワークインターフェイスが1Gbpsなら25%の帯域しか使用しません。

複数DCの設計 (The Site Reliability WorkbookのFigure 12-4より)

おわりに

この記事ではGoogleで利用されている、システムの設計方法を解説しました。 設計プロセスは単一のマシンから始まり、複数DCで稼働する、スケーラビリティや耐障害性を備えたシステムができあがりました。 それぞれの設計フェーズで元の要件を満たすだけでなく、耐障害性などの新たな要件も発見できました。

本文中に、突然Bigtableが出てきたり、QueryStoreへの転送について原文でも解説されていませんでしたが、おそらく紹介したNALSDを使って同様に設計することができます。

実際はスケールできるマネージドサービスを使ったり、複数DCで稼働するシステムを直接実装することは多くないとは思います。 しかしそれらを組み合わせても、スケーラビリティや耐障害性とSLOへの影響は常に考えておく必要があります。 たとえパブリッククラウドを利用していたとしても、この章で紹介されている設計方法は役立つでしょう。