はじめに

AWSのALBでも重み付けルーティングが採用されたように、LBでは重み付けの機能がよくありますが、Facebookでは時間やイベントなどによるトラフィック変化に対応するため、エッジサーバー上のLBの重み付けを動的に変化するようにしています。
この、動的な設定を行うために、Taijiというシステムが作られています。

Taijiは、世界中にあるFacebookのエッジサーバーがどのデータセンターへリクエストを回すかをユーザーのソーシャルデータから決めています
また、Taijiが落ちないように事前のテストや障害に対するフォールバックを用意しています。

今回の記事では、facebook researchが公開した「Taiji: Managing Global User Traffic for Large-Scale Internet Services at the Edge」から、Taijiの仕組みとテストに注目して紹介します。

ルーティング

Taijiは、エッジからデータセンターへのルーティングテーブルを動的に作成するシステムです。Taijiが作成する結果を基に、エッジ上にあるLBがルーティングをしています。

Facebookも他の会社と同じように、エッジノードとデータセンター内にある多数のサーバーで構成されています。エッジノードは静的コンテンツの配信や、データセンターへのリバースプロキシを担っています。かつて、リバースプロキシ先のデータセンターへのルーティングは静的に行っていましたが、サービスの規模がグローバルになり運用が辛くなったため、動的なルーティングをするためにTaijiが作成されました。

Taijiは「Connection-aware routing」という独自のルーティング方法を採用しつつ、下図のようにPipelineとRuntimeという２つのコンポーネントから出来ています。

f:id:mrasu:20191124152728g:plain

この章ではそれぞれについて、紹介します。

Connection-aware routing

Facebookはユーザーを基にリクエストを流すデータセンターを決めています。これは、

ステートフルなリクエストを同じデータセンターに割り当て続ける
似たコンテンツを使用するであろうユーザーを同じデータセンターに割り当てることでキャッシュ効率などを上げる

ということを目的としています。このルーティング方法が「Connection-aware routing」です。
Connection-aware routingでは、ソーシャル上のユーザーの近さを基にした完全二分木を使っていて、葉をbucket、節をsectionと呼んでいます。このツリーはオフラインで計算されていて、この情報を基に割り当てるデータセンターが決定されます。
下図で雰囲気が解ると思います。
f:id:mrasu:20191124152847j:plain

ちなみに、ユーザーの住所や属性を使わずに、ソーシャルな情報からツリーを作成しているのはアクセス元の正確な地域が取れないこと、プライバシー上の懸念からです。また、ソーシャル関係の情報でも、一方的な関係(一方的なフォローなど)や一時的な関係は配信コンテンツの同一性に関係がないため、要素を除外してツリーを作成しています。

またLBについて、エッジにあるLBはデータセンターが付与するCookieを使用してユーザーを識別します。そのため、最初の通信はTaijiの結果を使用せずに近くのデータセンターへ流されています。

Runtime

TaijiのコンポーネントはRuntimeとTraffic Pipelineの２つで出来ています。
Runtimeはエッジがデータセンターに流す割合を計算して、結果をTraffic Pipelineに渡すことが仕事です。アウトプットは

// fraction=割合  
{edge: {datacenter: fraction}}

という形をしています。Runtimeは

各サービスが要求する内容を定義したpolicy
エッジやデータセンターの稼動(キャパシティや稼働率など)
トラフィック量やエッジ・データセンター間のレイテンシ

などの情報を基に、各エッジがどのデータセンターにどのくらい流す必要があるかを定期的に計算します。

Traffic Pipeline

Traffic Pipeline はRuntimeの出力を入力として、エッジがどのユーザーをどのデータセンターに流すか定義したルーティングテーブルを作成することが仕事です。LBはこの結果を基にリクエストを流します。アウトプットは

// bucket=ユーザーの集合  
{edge: {datacenter: {bucket}}}

という形をしています。事前に計算したユーザーのツリー(Connection-aware routingの節参照)から、以下を考慮しつつデータセンターにbucketを割り当てています。

同じバケットは前回と同じデータセンターが割り当てられるようにする (ステートフルな通信では、データセンターが変わると再確立が必要なため)
同一segmentにあるbucketは同一データセンターに割り当てる(より良い効率を目指すため)
segmentが大きい場合には、適当に分割する

安定

TaijiはFacebookが提供する多くのサービスに対して、トラフィックのルーティングをしているので、問題があるとあらゆるサービスに影響します。そのため、落ちないことと、間違った計算をしないこと、両方が強く重視されます。

テスト

Taijiにおいて、プログラムが落ちてしまうような問題は、大量のユニットテストやインテグレーションテストで発見が可能です。
しかし、セマンティックな問題(式のミスなど)は本番で実際に動かしてアラートがでないと問題に気づきません。そのため、他にもテストを用意しています。

トラフィックを模したリグレッションテスト
ポストモーテムで、問題が起きた時の入力・設定・policyを記録し、テストで状況を再現することによって問題が再発しないかをチェックします
週次のトラフィックを再現してチェック
新しいサービスを載せたり、policyを変更したりする場合には、Facebookに来る１週間のトラフィックのパターンを再現し、Taijiがどう振る舞うかをチェックします
コンポーネントの入出力バリデーション
各コンポーネントの入出力に異常な変化がないかをチェックします
例えば、設定の変更がRuntimeの出力に意図しない変化起こさないかどうかや、データセンターへのトラフィックが閾値を超えないか、などをチェックします

間接的な問題に対処する

Taiji以外の問題によって、Taijiが正常に動かなくなることも問題となります。
そのため、以下の施策も実施しています。

新規インフラへの段階的な最適化
新しいハードウェアを稼働するなど、データセンターの許容量が変わることがあります。その時に、１回のルーティング変更で新しい許容量に最適化するのではなく、複数回に分けて最適化することによって、過度にアクセスが増えることを抑制しつつウォームアップを可能にしています。
ソーシャルな変化を緩和する
Connection-aware routingに使用するオフラインでのツリー更新に際して、5%以上のユーザー移動が起きないようにしています。
モニタリングシステムの障害への対応
Taijiが入力として使用するデータにはモニタリングシステムを使用する物があるため、モニタリングシステムに障害があるとTaijiが十分な機能を提供できなくなります。その場合にはサービスオーナーに対してアラートが飛びます(Taijiは自動に調整しません)
データセンター障害への対応
天災などによりデータセンターが落ちた場合
- 即時の対応として、障害を検知したLBは別のデータセンターに流すようになります。
- Taijiは、事前の負荷試験を通して得たデータセンターの許容量に従い、落ちたデータセンターのトラフィック分を生きているデータセンターに分配するようにルーティングを変更します。
世界的なイベントへの対応
ワールドカップや大晦日など世界的にトラフィックが変化するイベントでは、変化が大きすぎるためTaijiは対応出来ません。そのため、他の負荷対策が必要になります。