【nsdi'18論文】Stateless Datacenter Load-balancing with Beamerを読んだ

2018年4月9日〜11日に開催されていたnsdi'18で Community Awardに選ばれたStateless Datacenter Load-balancing with Beamerの論文を読んだのでメモ書きを残します。 こちらで発表も見れます。 自分の理解の範囲で記載しているので、詳細や正確性を求める方は本論文を読んだほうがいいです。

概要、背景

論文の内容は、タイトルそのままですが、データセンター向けのstatelessなLBを実装したという内容です。このLBの名前がBeamerです。 論文中では、TCPおよびMPTCP(multipath TCP)で実装したことが述べられています。

まずは、LBからサーバへのパケット振り分けについて見ていきましょう。

f:id:cipepser:20180513130438p:plain
(本論文Figure 1より引用)

インターネットや外部からBorder routerにやってきたパケットに対して、Border routeはMUXのVIP向けにパケットを投げます。 MUXがLBだと思ってもらうとわかりやすいと思います。 DIP(direct IP)は、サーバの実IPを指しており、MUXの役割は、VIPに着信したパケットをサーバに振り分ける(Load-Balanceする)ことです。 従来のLBは、どのDIPに対して振り分けを行うかを、以下のような計算で決定します。

hash(srcIP, dstIP, srcPort, dstPort, protocol) % N
N: DIPの数

論文中では、5つの引数をfive-tupleと呼んでおり、flow単位の振り分けとしています。TCPでは、sequence numberが前後して届くと再送要求されるので、余計な再送要求が起こらないようflow単位の振り分けがよく行われます。物理的に同じスイッチ(QoSなどの優先制御がなければ、Queueで処理されるので順番が変わらない)、ケーブルを通れば、パケットの追い越しは起こらず、dropしていないのに再送要求されるということもないです。

しかし、flow単位の振り分けでは、以下のような要望があったときに問題が発生します。

  • メンテナンスのため、サーバへの振り分けを止めたい
  • 新しくサーバ追加したい
  • サーバに障害が発生した

先程のhash(srcIP, dstIP, srcPort, dstPort, protocol) % Nから明らかなようにサーバ台数Nが変化すると振り分け先のサーバが変わってしまいます。サーバでTCP connectionのstateを持っているので、下記図のように途中でサーバBを追加した場合、青色の既存connectionの整合性が取れなくなってしまいます。

f:id:cipepser:20180513132238p:plain
(本論文Figure 3より引用)

一般的なLBでは、サーバ台数が増減してもTCP connectionを維持したいので、flow単位のconnectionをすべて保持しています。ただし、そのコストも馬鹿にならず、40%くらいスループット落ちると述べられています。また、一般的なLBはSYN flood攻撃にも弱い点も指摘されています。

Beamerでの解決方法

上記を解決するため、Beamerでは、Bucketと呼ばれる中間層を設け、stable hashingを実現します。 Bucketは、サーバ台数Nに対して十分大きなサイズBを持ち(論文中だとB=100N)、b = hash(5tuple)%Bなどで実サーバとmappingします。

※ 論文中では、mapping方法に依存しない手法であり、rendezvous hashingやMaglevでも応用できると書かれています。だからこそハードウェアにも応用できるそうです。なお、本論文では貪欲法で、muxにアサインされる隣接バケットのサイズを最大にするようmappingしており、TCAMが節約できると主張しています。実際、以下のようにmappingをまとめることができるようです。

f:id:cipepser:20180513135246p:plain
(本論文Figure 5より引用)

このようにmappinされたBucketは、全MUXで共有されます。この方法では、サーバ台数が増減してもBが変わらず、実サーバとのmappingを調整するだけで対応できます。

f:id:cipepser:20180513151329p:plain
(本論文Figure 4より引用)

Data planeとControl plane

MUXは、実際のパケットを処理するため、Date planeとして働きます。 注意事項としては、カプセル化で16Bのオーバーヘッドがあることでしょうか。カプセル化自体は、TRILLやVXLAN、VPNなどネットワークまわりでは広く顔を出すのでおかしなことではありませんが、LBの振り分けとなるサーバまでの経路上でMTUが制御される場合などは注意が必要なためオーバーヘッドがどの程度あるのか知っておくことは大切です。

また、Beamerでは、Bucketのmappingが変わることを適切に管理してあげる必要があります。 この役割は、ContollerがControl planeで実現しており、Beamerは、Apache ZooKeeperを使っているそうです。

f:id:cipepser:20180513140228p:plain
(発表資料P.35より引用)

図のようにBucketが更新(v2)された場合、ZooKeeper経由で各MUXに通知され、各MUXが最新のBucketをダウンロードして、一貫性を保ちます。論文中では、2-phase commitで実現していると書かれていますが、このあたりはあまり詳しくないので詳細は本論文を読んでください。

Daisy chaining

Beamerでは、既存connectionを適切に扱うためDaisy chainingを使っています。 Bucketの再構成には、以下の課題の課題があります。

  • 既存connectionが壊れる
  • 一貫性が失われる(他が使ってるmappingをつかってしまう)

例えば、下記図の青いconnectionのように、もともとMUX2からサーバAにmappingされていた場合を考えます。

f:id:cipepser:20180513135553p:plain
(本論文Figure 6より引用)

Bucketの再構成によってこのconnectionがサーバBにmappingされた場合、 すでにestablishedな青いconnectionは、サーバAに振り分けられる必要があります。 Beamerでは、PDIP(previous DIP)という一つ前にmappingされた実サーバを覚えておき、一定時間は前のサーバに転送することで既存が壊れることを防ぎます。

ベンチマーク

まず1コアでのベンチマークです。ここでは、性能をpps(packet per second)を、パケットサイズが変化させて比較しています。

f:id:cipepser:20180513143745p:plain
(本論文Figure 13より引用)

StatefulなLBに対して、short packetである64Bでも2倍程度の性能が出ています。 また、コアを2つにすればline rateと同レベルの性能になっています。

論文中で最終的な性能は、以下の図で記載されています。

f:id:cipepser:20180513145002p:plain
(本論文Figure 14より引用)

128B packetに対して、8コア1サーバあたり23-33Mpps(bps単位で20-30Gbps)を処理できる結果です。 これは現状最速であるGoogleのMaglevの2倍の性能だそうです。

最後に

というわけで、Beamerの論文を読んだまとめでした。サーバ台数の増減があった場合、当然振り直しが起こるものの仕方ないと思っていたので、解決できるのかと驚きました。ベンチマークに用いた実装もGithubで公開されてます。
またGoogleのMaglevを知らなかったので関連研究を知る意味でも勉強になりました。Maglevは本論文の2年前に同じくnsdi'16で発表されたようなので、この辺も読まないとですね。Maglevの2倍というのは、この論文のFigure 10あたりっぽいです。

References