ロードバランサのアーキテクチャいろいろ

少し前に,Facebookのロードバランサが話題になっていた.

blog.stanaka.org

このエントリを読んで,各種Webサービス事業者がどういったロードバランスアーキテクチャを採用しているのか気になったので調べてみた. ざっくり検索した限りだと,Microsoft, CloudFlareの事例が見つかったので,Facebookの例も併せてまとめてみた.

アーキテクチャ部分に注目してまとめたので,マネジメント方法や実装方法,ロードバランス以外の機能や最適化手法といった部分の詳細には触れないことにする.

事例1: Microsoft Azure 'Ananta'

MicrosoftのAzureで採用されている(いた?)ロードバランサのアーキテクチャは,下記の論文が詳しい.

Parveen Patel et al., Ananta: cloud scale load balancing. SIGCOMM '13 (スライド)

2013年10月に発表された論文.'Ananta' と名付けられたこのロードバランサは,論文執筆時点でbing.com等の実環境において約2年(すなわち2011年頃から)の運用実績があると述べられている.

一般的なアプライアンス型ロードバランサやLVS+keepalivedの環境が1+1構成でスケールアップが基本戦略になるのと対照的に,AnantaはN+1構成でスケールアウトが容易な点が特徴である.また実装面では,ハイパーバイザのレベルで諸々の処理を完結させることで,VM側にシステムの存在を意識させないようになっている.

Architecture

Anantaのおおまかな構成は下図の通り.図中には記載していないが,全体の動作を統括するAnanta Manager(AM)も存在する.

f:id:yunazuno:20160225191128p:plain

ロードバランスはRouter, Layer-4 LB, Host Agentの3階層で行われる*1.従来型のロードバランサがLayer 3からLayer 7までを(内部的な実装はともかく)単一の筐体でこなしていたのとは対照的である.なお上図だと各層間を同一L2で繋ぐように描いてしまったものの,当然その必要は無い.

Router

Per-flow Equal Cost Multi Path (ECMP) によるLayer 3レベルでのトラフィック分散を行う.

Routerは,次段のL4 LBからVIPの/32経路をBGPで受信している*2.このとき,コスト(Local PreferenceやMED)が同一であれば,routerはECMPでのパケットフォワーディングを行う. Per-flow ECMP*3を使用すれば,経路に変化が無い限り,すなわちL4 LBが増えたり死んだりしない限り,同一TCPセッションは常に同一のL4LBにフォワーディングされる.これにより,Routerではセッションを管理する必要が無い.

L4 LB (Multiplexer, MUX)

Consistent HashによるLayer 4レベルでのトラフィック分散を行う.論文中ではMultiplexer 'MUX' と呼ばれている.MUXは,自身が管理しているVIPの/32経路をBGPでrouterに広報する.これにより,VIP宛のトラフィックがMUXに引き込まれるようになる.

MUXはアプケーションが稼動しているVMトラフィックを分散する.このとき単純にConsistent Hashだけでフォワード先を決定してしまうと,VMやHyperVisorの増減が発生した際に既存セッションが誤ったVMにフォワードされてしまう.これを防ぐため,MUXは既存セッションの情報をセッションテーブルで保持・管理する.ただし,この情報はMUX間では共有されていない*4ため,場合によってはセッションが失われてしまう可能性がある.ちなみに,実装はWindows Filtering Platform(WFP)を用いている.

Host Agent (HA)

IPIPのデカプセル化やNATといった処理を透過的に行い,適切なVMトラフィックが屆くようにする役割を持つ.

VMやその上で動いているアプリケーションのヘルスチェックもここで行う.ヘルスチェックの結果はAnanta Managerに送られたのちMUXに反映される.実装はHyper-Vの仮想スイッチ*5を用いている.

トラフィックフロー

あるアプリケーションApp 2がVIP 192.0.2.2を使うとき,VIP宛の通信は下記のような流れで処理される:

f:id:yunazuno:20160225191129p:plain

  1. RouterにVIP 192.0.2.2宛のパケットが屆く.このとき,router上には192.0.2.2/32の等コスト経路が複数存在するので,そのうちいずれか1経路を選択してパケットをフォワードする.
  2. MUXにパケットが屆く.MUXは自身のセッションテーブルを参照し,セッションが既に存在するか確認する.存在すればそれに従ってフォワード先のVMを決定する.存在しなければhashによって新たにフォワード先のVMを決定し,セッションテーブルに記録する.フォワード先のVMが決定されると,パケットをIPIPでカプセル化してVM宛にフォワードする.
  3. HAを通過してパケットがVMに屆く.このとき,HAは透過的にIPIPのデカプセル化を行う.
  4. VMが応答を返す.なお,このときのパケットのソースIPアドレスVMの実IPアドレスになっている.
  5. HAを通過してパケットがクライアントに送られる.このとき,HAはsource NATを行い,パケットのソースIPアドレスVMの実IPアドレスからVIPに書き換える.また,L3DSRなので,レスポンスのパケットはMUXを通過しない.

事例2: Facebook

このエントリの冒頭で挙げたエントリでも詳解されていたもの.

Building a Billion User Load Balancer | USENIX

MicrosoftのAnantaと同様,複数レイヤ分割によってスケールアウトが容易な構成になっている.

Facebookのシステムが優れているのは,単一IDC内におけるロードバランスだけでなく,PoP間トラフィックの最適化やGSLBによるユーザトラフィックの品質向上まで含めて考えられている点である.また実装面では,Microsoftのものと違って特定の環境に依存する要素が無く,よりポータブルになっている*6

Architecture

PoP間通信やGSLBに関する部分は置いておいて,単一IDC内だけに着目すると,おおまかな構成は下図の通り.Microsoftの例と同じく階層構造である.ロードバランシングはRouter, Layer 4 LB, Layer 7 LBの3階層で行われる.例によって階層間は同一L2である必要は無い.

f:id:yunazuno:20160225191126p:plain

Router

Per-flow Equal Cost Multi Path (ECMP) によるLayer 3レベルでのトラフィック分散を行う.Microsoftの例におけるrouterと全く同じ役割と動作を行う.

Layer 4 LB

Consistent HashによるLayer 4レベルでのトラフィック分散を行う.これもMicrosoftの例におけるMUXとほぼ同じ役割と動作を行う.実装はLVSExaBGPを用いている.

Layer 7 LB

コネクションを終端し,アプリケーションに対するLayer 7レベルでのトラフィック分散(reverse proxy)を行う.実装はProxygenを用いている.

上で挙げた各層の要素はコンテナ化され,Kubernetesを使って任意の場所にデプロイされる. 余談だが,発表動画中では気軽に「任意の場所にデプロイ」と言って図まで描いている。だがしかし、ファブリック的ではないネットワークアーキテクチャでこれをそのまま真似すると,router-L4LB間の帯域が足りなくて辛い思いをすることになると予想される.Facebookのデータセンターは末端まで広帯域を用意していることが知られているが,こういうことをやってこそ出来る芸だと思う.

トラフィックフロー

VIP 192.0.2.1があるとしたとき,このVIP宛の通信は下記のような流れで処理される.

f:id:yunazuno:20160225191127p:plain

  1. RouterにVIP 192.0.2.1宛のパケットが屆く.このとき,router上には192.0.2.1/32の等コスト経路が複数存在するので,そのうちいずれか1経路を選択してパケットをフォワードする.
  2. L4 LBにパケットが屆く.L4 LBは自身のセッションテーブルを参照し,セッションが既に存在するか確認する.存在すればそれに従ってフォワード先のL7 LBを決定する.存在しなければhashによって新たにフォワード先のL7 LBを決定し,セッションテーブルに記録する.フォワード先のL7 LBが決定されると,パケットをIPIPでカプセル化してL7 LB宛にフォワードする.
  3. L7 LBにパケットが屆く.L7 LBはIPIPをデカプセル化した上でコネクションを一旦終端し,upstreamのアプリケーションに対してリバースプロキシを行う.
  4. アプリケーションがL7 LBにレスポンスを返す.
  5. L7 LBを経由してパケットがクライアントに送られる.L3DSRなので,レスポンスのパケットはL4 LBを通過しない.

事例3: CloudFlare

CDN事業者であるCloudFlareは,世界中にPoPを設置してコンテンツ配信を行っている. そんなCloudFlareのPoPにおけるロードバランス手法が下記の記事で紹介されている.

blog.cloudflare.com

CloudFlareのアーキテクチャで特徴的なのは,ネットワークレベルで負荷分散と障害時の切り離しが完結している点である.またインターネットレベルでのIP Anycastによる耐耐障害性確保も実現している.

Architecture

おおまかな構成は下図の通り.

f:id:yunazuno:20160225191124p:plain

この構成では,ロードバランサにおける負荷分散機能をECMPで行い,分散先の追加・削除機能をBGP自身で行う.MicrosoftのMUXやFacebookのL4/L7 LBに該当するような明確なロードバランサは存在しない.

Router

ECMPによるLayer 3レベルでのトラフィック分散を行う. Routerは,後段のedge serverにインストールされたBGP speakerからの/32経路を受信している.この経路をそのままインターネット(他のAS)に広報することで,edge serverは外部からアクセス可能になる.

Edge server

CDNのキャッシュやプロキシ機能を提供する. 各Edge serverにはBGP speaker*7がインストールされており,routerに対して自身のVIPを広報する.各edge serverが同一のコストで広報を行えば,routerからECMPによって負荷が分散される. また,VIPは複数のPoPで同一のものを使用している.従って,インターネットに対するIP anycastが行われている.

冒頭でも述べた通り,構成の面白い点は障害時の動作である. たとえばEdge serverが死んだ場合,そのサーバからrouterに対する経路広報が止まるため,そのサーバは自ずと負荷分散対象から外される. また,電源障害や上流回線全断などによってPoP自体が死んだ場合,そのPoPからインターネットへの経路広報が止まるため,そのPoPへはアクセスされなくなる.クライアントはIP Anycastによって他のPoPに自動的に迂回される.

トラフィックフロー

VIP 192.0.2.3があるとしたとき,このVIP宛の通信は下記のような流れで処理される.MicrosoftFacebookのものに比べると非常にシンプル.

f:id:yunazuno:20160225191125p:plain

  1. RouterにVIP 192.0.2.3宛のパケットが屆く.このとき,router上には192.0.2.3/32の等コスト経路が複数存在するので,そのうちいずれか1経路を選択してパケットをフォワードする.
  2. Edge serverにパケットが屆く.パケットは特にカプセル化等はされておらず,通常のものと変わらない.
  3. Edge serverがレスポンスを返す.
  4. ルーティングテーブルに従ってパケットがクライアントに送られる.

余談: Google

GoogleのロードバランスといえばGFEだと思うが,明確な資料は見当たらなかった. 見付けられた範囲だと、下記の動画で簡単に言及がある程度である.

www.youtube.com

少し前にSeesawというものが公開されていたが,これがGoogle内部ではどういう位置付けでどの程度使われているのかよく分からないので何とも言えないところ.

github.com

追記 (2016-02-29 19:25)

Googleのロードバランサに関する情報を@rrreeeyyyさんに教えていただいた:

論文は下記のページに掲載されている.こんどのNSDIで発表される予定

Maglev: A Fast and Reliable Software Network Load Balancer

Abstractと図をざっくり眺めた程度だと,こちらも複数レイヤ分割構成でECMPやconsistent hashを活用している様子.あとで論文を詳しく読む予定. 情報ありがとうございました!

まとめ

Microsoft, Facebook, CloudFlareにおけるロードバランサのアーキテクチャを調べて簡単にまとめてみた. 最近のクラウド環境であればロードバランサ機能は当然用意されているが,それらの内部では(Azureに限らず)ここで挙げたような技術が活用されていると考えられる.クラウド様々である. また,ロードバランサに限らず,機能ごとのレイヤ分けやBGP+ECMPの活用といった考え方は,様々な局面で参考にできそう.

*1:実際にはHost Agentは負荷分散の機能は無い.

*2:実際には,Routerの負荷を考慮してもう少し集約された経路を使用している,と論文中では述べられている

*3:source ip, source port, destination ip, destination port等のhashによりパスを選択する方式; これに対してパケット毎にランダムにパスを決定するのがper-packet ECMP

*4:少なくとも論文執筆時点では未実装; DHTのようなアプローチで解決できるよ,と筆者らは言っている

*5:恐らくHyper-V Extensible SwitchをWFPで拡張したもの思われる

*6:もちろん,AnantaもHAを必ずしもハイパーバイザに組み込む必要は無くて,MUX-App間のどこかに同じ機能を持たせれば同様のことは実現できそうに見える.

*7:Birdを使用している