Facebookはレイヤ4ロードバランサをIPVS(LVS)からXDPベースのものに乗り換えつつある
4月に開催されたnetdev 2.1で面白いセッションがあったのでメモ。
Facebookが使用しているレイヤ4のロードバランサに関する発表で、従来はIPVS (LVS) を使用していたが、XDPベースで自ら開発したものに移行しつつある、という内容。
XDP Production Usage: DDoS Protection and L4LB (slide)
XDP (eXpress Data Path) については以前のエントリで簡単に紹介した。
XDPを改めて簡単に紹介すると、Linuxカーネルのネットワークスタックの最下部 (NICに一番近い場所) でパケット処理を行う仕組みのことで、オーバーヘッドが非常に小さい高速パケット処理の実現を目的としている。XDPはeBPFを用いており、eBPFが提供するmapやhelper functionといった機能を用いて柔軟なプログラムが書けることに加え、JITによる高速化やカーネル自身の堅牢性をそのまま享受することができるとされている。
XDPがリリースされたのは2016年10月のカーネル4.8なので、半年程で実際の事例が出てきたことになる。
FacebookにおけるXDPのユースケース: L4LB & DDoS防御
FacebookはIPVS (LVS) ベースのレイヤ4ロードバランサ (L4LB, 通称Shiv) を利用していることが知られている。
Shivの役割はConsistent Hashによる負荷分散先の決定とIP encapsulation (IPIP) によるパケット転送である。また、ローカルにセッションキャッシュを持つことにより、Consistent Hashの弱点であるリマップ時のセッション切断問題をカバーしている。
今回の発表では、これらの機能をXDPの基盤上で実装したのちIPVSベースの既存環境を置き換えていることが明かされた。スライドでは下のグラフが示され、XDPで実装された新しいShivがIPVSベースのそれと比較して高いスループットを発揮しつつもCPU使用率が低く抑えられている、と述べられている*1。
(スライドp3より; それぞれ1本だけラインが離れているものがXDP, 固まっているものがIPVS)
また、DDoS防御のための仕組み (Dropletと呼ばれる) も併せて紹介されている。
DDoS防御にあたっては、攻撃パケットを可能な限り早い段階で検出・遮断することが望ましい。加えて、攻撃パケット検出のシグネチャはプログラマブルに構成・変更可能であることが望ましい。彼らはこれもXDP上に実装している。L4LBのプログラムの前にDDoS検出・遮断のプログラムが実行されるようにすることで、L4LBが余分なリソースを消費することを防いでいる。
(スライドp10より; #0 XDP Dumpはデバッグ用のもの)
ちなみに、XDPによるDDoS防御についてはCloudflareのエンジニアも同様の発表を行っている。こちらはよりBPFにフォーカスした内容。
XDP in practice: integrating XDP in our DDoS mitigation pipeline (slide)
実装の詳細
冒頭のビデオで発表部分が12分弱で収まっていることからも分かる通り、やっていること自体は非常にシンプルである。
ただその裏では、(発表内で直接は触れられていないものの) XDPやその基礎となるeBPFの機能がふんだんに使われていることが見て取れる。これらの機能はFacebookのエンジニア自身によって実装されたのちLinuxカーネルにマージされたものも少なくない。
BPF_MAP_TYPE_LRU_HASH: セッション維持のためのLRU cache
Consistent Hashを用いるL4LBではその特性上、分散先のリアルサーバが増減したタイミングで幾許かのTCPセッションが意図せず切断されてしまう。この弱点を補うため、いくつかのL4LB実装ではセッションテーブルを併用している。TCP SYNパケットがL4LBに到達すると同時にセッションテーブルにセッション情報を記録すれば、仮にConsistent Hashのリマップが発生したとしてもセッションテーブルに基づいてTCPセッションを維持できる、という仕組みである。ただセッションテーブルのサイズは有限であるため、何らかの方法でセッションテーブルのメンテナンスを行う必要がある。
そこで登場するのがeBPF map objectのひとつ、BPF_MAP_TYPE_LRU_HASHである。その名前が示す通り、Least Recently Used (LRU) なハッシュテーブルである。これを利用すれば、先に述べた要件を満たすセッションテーブルを容易に実現できる。
この機能は冒頭で紹介したセッションのスピーカーであるMartin Lauによって開発され、kernel 4.10以降で利用可能である。
xdp_adjust_head(): IP encapsulation
ShivはL3DSRによるリアルサーバへのパケット転送にIPIP方式を採用している。これはリアルサーバ宛てIPヘッダで元のVIP宛てパケットをカプセル化することでパケット転送を実現するものである*2。
これをXDPで実現するため、メモリページ上であらかじめ空間 (headroom) を確保しておき、そこにデータ(ここではリアルサーバ宛てのIPヘッダ)を追加するインタフェースが用意されている。このインタフェースがeBPF helper functionのひとつ、bpf_xdp_adjust_head()である。この機能も同じくMartin Lauによって開発され、kernel 4.10以降で利用可能である。
なお、NICドライバには通常のXDPサポートとは別にheadroom確保のサポートが要求される。
BPF_MAP_TYPE_PROG_ARRAY & tail call: 複数のeBPFプログラムを連携させる
XDPはその仕様上、1個のネットワークインタフェースに対して1個のeBPFプログラムのみアタッチすることができる。これは1個のネットワークインタフェースに対して複数の独立した処理を適用したい場合に都合が悪い。
これを解決するのがBPF_MAP_TYPE_PROG_ARRAY と bpf_tail_call() である。
上記エントリで紹介した通り、BPF_MAP_TYPE_PROG_ARRAYとbpf_tail_call()を組み合わせることで、複数のeBPFプログラムを連結して呼び出したり実行中のeBPFプログラムを動的に入れ替えたりできる。ちなみにこの機能を実装したAlexei StarovoitovもFacebookに在籍している*3。
余談: XDPの近況
2016年10月にXDPがリリースされてから約半年が経過したが、その間に様々なアップデートが行われた。
まず大きなトピックとしてNICドライバのサポート拡充が挙げられる。当初はMellanox mlx4のみであったものが徐々に拡充され、先日遂にIntel ixgbeサポートがnet-nextにマージされた。恐らくカーネル4.12でリリースされると思われ、XDPが利用可能な環境が大幅に広がることになる。また変わり種として、CaviumのARM SoCであるThunderXでのサポートもnet-nextにマージされている。
現時点では、下記のNICドライバで利用可能あるいは近日中に利用可能となる:
mlx4: Mellanox ConnectX-3mlx5: Mellanox ConnectX-4 or laternfp: Netronome Agilioqede: QLogic FastlinQvirtio_net: Virtiobnxt_en: Broadcom NetXtreme C-Seriesixgbe: Intel X5xx (82598, 82599) (from kernel 4.12?)thunderx: Cavium ThunderX (from kernel 4.12?)
また、NICドライバのサポートが無くてもXDPプログラムを実行できるようにする仕組み (“Generic XDP”) も登場した。
kernel/git/torvalds/linux.git - Linux kernel source tree - net: Generic XDP
これは主に開発用やお試し用を意図しており、パフォーマンスに関しては考慮されていない。これまでXDPプログラムを実行するには、対応NICが挿さったハードウェアを用意するか、あるいはe1000, virtio_netの環境を用意する必要があった。Generic XDPの登場により、より手軽に開発環境を整えられるようになる。
なお、各カーネルバージョン毎にサポートされるeBPF/XDP関連の機能やドライバの情報はiovisor/bccのドキュメントに纏まっている:
bcc/kernel-versions.md at master · iovisor/bcc · GitHub
XDPリリース直後の2016年12月にPLUMgrid*4がVMWareに買収される出来事があったものの、特に大きな影響も無くXDP周辺の発展は続いている様子である。eBPF自体を含め機能がどんどん拡充されており、かつXDPのユースケースも徐々に出始めてきたことで、今後の動向がますます楽しみ。
eBPF tail call 使い方メモ
eBPFにはtail callと呼ばれるプログラム呼び出し方法が存在する。 これは、ある実行中のBPFプログラムから別のBPFプログラムにジャンプするものである。あくまでジャンプであって、通常の関数呼び出しと違って呼び出し元に処理は戻らない。ユースケースとしては例えば、役割が違う複数のプログラムの独立性を保ったまま連携させたい場合に役立つ。
bpf: introduce bpf_tail_call() helper [LWN.net]
また、tail callの面白い点として、ジャンプ先のルックアップは BPF_MAP_TYPE_PROG_ARRAY という種類のBPF mapを使う点が挙げられる。このmapは通常のBPF map同様、プログラム実行中にユーザ空間側から動的に書き換えることができる。したがって、ジャンプ先のプログラムを動的に入れ替えたり、あるいはジャンプを取りやめるといったことが容易に実現できる。
通常の使用例
tail callを使うには、BPF_MAP_TYPE_PROG_ARRAY のBPF mapを用意した上で bpf_tail_call() helperを使えばよい。カーネルの samples/bpf/sockex3_kern.c が参考になる。
linux/sockex3_kern.c at master · torvalds/linux · GitHub
該当部分を抜粋する*1:
#define PARSE_VLAN 1 #define PARSE_MPLS 2 #define PARSE_IP 3 #define PARSE_IPV6 4 static inline void parse_eth_proto(struct __sk_buff *skb, u32 proto) { switch (proto) { case ETH_P_8021Q: case ETH_P_8021AD: bpf_tail_call(skb, &jmp_table, PARSE_VLAN); break; case ETH_P_MPLS_UC: case ETH_P_MPLS_MC: bpf_tail_call(skb, &jmp_table, PARSE_MPLS); break; case ETH_P_IP: bpf_tail_call(skb, &jmp_table, PARSE_IP); break; case ETH_P_IPV6: bpf_tail_call(skb, &jmp_table, PARSE_IPV6); break; } }
jmp_table がprogram arrayである。proto が ETH_P_8021Q であれば jmp_table[PARSE_VLAN] が示すファイルディスクリプタのBPFプログラムにジャンプする。なお、もしここでjmp_table[n] が有効なBPFプログラムでない場合、そのまま処理が続行(fall-through)される点に注意。逆にこの特性を利用すれば、トラブルシューティングの時だけデバッグ用のBPFプログラムを登録する、といったことが可能になる。
bccでの使用例
ここではiovisor/bccを使った場合の動作を試してみることにする。bccにはprog_array.call()という構文のsyntax sugarが用意されており、bpf_tail_call()と等価な処理を容易に実現できる。
ここでは例として、通常時は全てのパケットを通過するが、コマンドによって全てのパケットをドロップするXDPプログラムを考える*2。
XDP program
カーネル空間側で実行されるXDPのコードは下記の通り。通常時はprog_entryを実行するが、パケットをドロップさせたい時はprog_dropにジャンプさせる。jmp_tableがprogram arrayである。
なお、events.perf_submit() はログをカーネル空間からユーザ空間に送るのに使用する。これもbccのsyntax sugarで、bpf_perf_event_output()と等価である。
// xdp_chain.c BPF_TABLE("prog", int, int, jmp_table, 8); BPF_PERF_OUTPUT(events); struct event_t { u64 timestamp; char message[128]; }; int prog_drop(struct xdp_md *ctx) { struct event_t e = { .timestamp = bpf_ktime_get_ns(), .message = "Enter prog_drop\0", }; events.perf_submit(ctx, &e, sizeof(e)); return XDP_DROP; } int prog_entry(struct xdp_md *ctx) { struct event_t e_enter = { .timestamp = bpf_ktime_get_ns(), .message = "Enter prog_entry\0", }; events.perf_submit(ctx, &e_enter, sizeof(e_enter)); jmp_table.call(ctx, 0); struct event_t e_exit = { .timestamp = bpf_ktime_get_ns(), .message = "Exit prog_entry\0", }; events.perf_submit(ctx, &e_exit, sizeof(e_exit)); return XDP_PASS; }
動作を観察する
ここでは簡単のため、ユーザ空間側の処理はipython経由で逐次実行する。
まずは下準備としてプログラムのロードまでを実施する。ここでevents.open_perf_buffer()は前述したログを読み出すためのもので、bpf.kprobe_poll()を呼び出してログが到着するとprint_event()がコールバックされる。
$ sudo ipython
In [1]: %cpaste
Pasting code; enter '--' alone on the line to stop or use Ctrl-D.
:import ctypes as ct
:from bcc import BPF
:
:class Event(ct.Structure):
: _fields_ = [
: ("timestamp", ct.c_uint64),
: ("message", ct.c_char * 128),
: ]
:
:def print_event(cpu, data, size):
: event = ct.cast(data, ct.POINTER(Event)).contents
: print event.timestamp, event.message
:
:
:bpf = BPF(src_file="./xdp_chain.c")
:
:events = bpf["events"]
:events.open_perf_buffer(print_event)
:
:prog_entry = bpf.load_func("prog_entry", BPF.XDP)
:prog_drop = bpf.load_func("prog_drop", BPF.XDP)
:<EOF>
prog_entryをインタフェースens9にアタッチ。XDPでのパケット処理が開始される。
In [2]: bpf.attach_xdp("ens9", prog_entry)
ログは以下のようになっている。jmp_table に何も登録されていないためfall-throughされていることが確認できる。
In [3]: bpf.kprobe_poll() 87485224130884 Enter prog_entry 87485224144293 Exit prog_entry 87487208201839 Enter prog_entry 87487208220583 Exit prog_entry
この状態で、jmp_table[0] に prog_drop を登録してみる。
In [4]: jmp_table = bpf["jmp_table"] In [5]: jmp_table[0] = prog_drop.fd
外部からens9宛のpingが通らなくなり、パケットがドロップされるようになったことが確認できる。ログを確認すると、prog_dropが実行され、かつprog_entryの末尾部分に処理が戻っていないことも確認できる。
In [6]: bpf.kprobe_poll() 87669224146031 Enter prog_entry 87669224160730 Enter prog_drop 87671208094900 Enter prog_entry 87671208110055 Enter prog_drop
jmp_table[0]を削除すれば、再び最初の状態に戻る。
In [7]: del jmp_table[0] In [8]: bpf.kprobe_poll() 87875240128813 Enter prog_entry 87875240144164 Enter prog_drop 87877224181681 Enter prog_entry 87877224199698 Enter prog_drop 87879208128601 Enter prog_entry 87879208145440 Exit prog_entry
Virtio-netでXDPを動かすにはqemuのオプション変更が必要
Linuxカーネル4.10からvirtio_netがXDPをサポートするようになった。だが、動作させるには少しオプション変更が必要となる。
Qemuの起動オプションに下記を渡すことでここに記載のあるオフロード機能が無効になり、XDPが動作するようになる:
gso=off,guest_tso4=off,guest_tso6=off,guest_ecn=off,guest_ufo=off
virshであれば、該当NICのinterfaceセクションの下に下記設定を入れてあげれば良さそう:
$ virsh edit XDP-VM
<domain type='kvm'>
...
<devices>
...
<interface type='network'>
...
<model type='virtio'/>
<driver name='vhost' queues='4'>
<host gso='off' tso4='off' tso6='off' ecn='off' ufo='off'/>
<guest tso4='off' tso6='off' ecn='off' ufo='off'/>
</driver>
...
</interface>
...
</devices>
</domain>
Pitfall
上記設定をせずにXDPを使おうとすると、NICにプログラムをアタッチする段階でEOPNOTSUPP (Operation not supported) が返ってきて失敗する。また、ゲスト側のログに下のメッセージが出る:
$ dmesg ... [ 528.046901] virtio_net virtio4 ens9: can't set XDP while host is implementing LRO, disable LRO first
このメッセージと該当部分のコードを素直に読むと、ethtoolでlroないしtso/ufo/ecnを無効にしてやれば良さそうに見える。だが実際には前述した通りqemuのオプション側でこれらの機能を無効にする必要があるので注意が必要*1。
Reference
- XDP Newbie - Re: xdp on virtio_net
- Bug 1387477 – virtual interface offload for virtio - disable host ufo only will not work
*1:詳しくは追えていないがそういうものらしい https://www.spinics.net/lists/netdev/msg409656.html
Persistent eBPF map object with bcc
Linux kernel 4.4以降には，eBPF map/programを"永続化"する仕組みが実装されている．ここではその概要を説明しつつ，iovisor/bccを使って実際にその動作を確かめてみる．
Background: eBPF objectを複数プロセスで共有したい
eBPFにmapというデータ構造があることはXDPの紹介エントリのサンプルコード内で軽く触れた．
通常，mapはそれを作成したプロセスからのみ読み書き可能である．しかし，いくつかのユースケースにおいては，mapを複数のプロセスから読み書きできると都合が良いことがある．たとえば何からの統計情報(例えばパケットカウンタ)をmapに保存してそれを外部に転送したい場合，「統計情報をmapに保存するプロセス」と「収集された統計情報を加工して外部に転送するプロセス」とに分割したほうが，実装の見通しの観点から望ましい．また，mapに何らかの設定情報(例えばIPルーティングテーブル)を保存してパケットを加工したい場合，「ルーティングテーブルを参照してパケットの加工を行うプロセス」と「ルーティングテーブルのアップデートを行うプロセス」とに分割したほうが，安定性の観点から望ましい．
Kernel 4.4以前から，mapのfile descriptorをunix domain socket経由で他プロセスに共有することで，複数プロセス間でmapを共有することは可能ではあった．
この方法は汎用的である反面，決して簡単とは言い難い．そこで登場したのが，今回紹介するeBPF objectに特化した仕組みである．
Solution: eBPF objectをBPF filesystemに"ピン付け"する
Linux kernel 4.4から，eBPF objectをファイルシステム上のパスに割り当てる (“pinning”) する仕組みが実装された．
まず，eBPF objectとファイルシステム上のパスのマッピングを行うファイルシステム (ここでは仮にbpffsと呼ぶことにする) が用意されている．このファイルシステムを任意のパス (一般に/sys/fs/bpf) にマウントしておく．
linux/inode.c at master · torvalds/linux · GitHub
その上で，bpf(2) syscallに追加された BPF_OBJ_PIN コマンドを使ってpinningを行う．ファイルからeBPF objectを取得する際には同様に BPF_OBJ_GET コマンドを使う．
簡単なサンプルが以下に用意されている:
- Pin: prototype-kernel/bpf.c at master · netoptimizer/prototype-kernel · GitHub
- Get: prototype-kernel/bpf.c at master · netoptimizer/prototype-kernel · GitHub
Example: bccを使って複数プロセス間でeBPF mapの読み書き
C言語のコードから直接syscallを使ってpinningを行う例は既にいくつかある (例1, 例2) ため，ここではbccを使ってpython経由でeBPF mapのpinningと他プロセスからの読み込みを試してみる．例として，受信したパケット数をeBPFプログラムでカウントしてeBPF mapに書き込み，それを他のプロセスから読み込む場合を考える．
Code
counter.py: eBPF mapへの書き込み & pinning
受信したパケット数をカウントしてeBPF map “packet_counter” に書き込むプログラムである．このプログラムはtc-bpf(8)経由でネットワークインタフェースにアタッチされる．
from bcc import BPF, libbcc import pyroute2 import ctypes import time import sys code = """ #include <uapi/linux/bpf.h> #include <uapi/linux/pkt_cls.h> BPF_TABLE("array", uint32_t, long, packet_counter, 1); int counter(struct __sk_buff *ctx) { uint32_t index = 0; long *value = packet_counter.lookup(&index); if (value) *value += 1; return TC_ACT_OK; } """ def count_packet(iface, pin_path): bpf = BPF(text=code, cflags=["-w"]) func = bpf.load_func("counter", BPF.SCHED_CLS) counter = bpf.get_table("packet_counter") print("map fd: {}".format(counter.map_fd)) ret = libbcc.lib.bpf_obj_pin(counter.map_fd, ctypes.c_char_p(pin_path)) if ret != 0: raise Exception("Failed to pin map") print("Pinned at: {}".format(pin_path)) ip = pyroute2.IPRoute() ipdb = pyroute2.IPDB(nl=ip) idx = ipdb.interfaces[device].index ip.tc("add", "clsact", idx) ip.tc("add-filter", "bpf", idx, ":1", fd=func.fd, name=func.name, parent="ffff:fff2", classid=1, direct_action=True) print("Hit CTRL+C to stop") while True: try: print(counter[0].value) time.sleep(1) except KeyboardInterrupt: print("Removing filter from device") break ip.tc("del", "clsact", idx) ipdb.release() if __name__ == '__main__': iface = device = sys.argv[1] pin_path = sys.argv[2] count_packet(iface, pin_path)
実際にpinningを行っているのは下記の部分．現状，bccのpython bindingに専用のインタフェースが無いため，libbccの関数を直接呼び出している．
counter = bpf.get_table("packet_counter")
ret = libbcc.lib.bpf_obj_pin(counter.map_fd, ctypes.c_char_p(pin_path))
reader.py: pinningされたeBPF mapの読み出し
こちらのコードでmapの値を読み込む．
from bcc import libbcc, table import ctypes import sys class PinnedArray(table.Array): def __init__(self, map_path, keytype, leaftype, max_entries): map_fd = libbcc.lib.bpf_obj_get(ctypes.c_char_p(map_path)) if map_fd < 0: raise ValueError("Failed to open eBPF map") self.map_fd = map_fd self.Key = keytype self.Leaf = leaftype self.max_entries = max_entries def read_counter(map_path): counter = PinnedArray(map_path, ctypes.c_uint32, ctypes.c_long, 1) return counter[0].value if __name__ == '__main__': path = sys.argv[1] print(read_counter(path))
キモは下記の部分．下記コードでmapのファイルディスクリプタが取得できる．上記コードではbcc.table.Arrayを再利用している．
map_fd = libbcc.lib.bpf_obj_get(ctypes.c_char_p(map_path))
実行例
まずはbpffsをマウント．
$ sudo mount -t bpf none /sys/fs/bpf $ mount | grep bpf none on /sys/fs/bpf type bpf (rw,relatime)
続いてcounter.pyを実行．
$ sudo python counter.py eth0 /sys/fs/bpf/counter map fd: 4 Pinned at: /sys/fs/bpf/counter Hit CTRL+C to stop 0 37 38 39 70 ...
/sys/fs/bpf/counter が作成されていることが確認できる．
$ ls -l /sys/fs/bpf/counter -rw-------. 1 root root 0 Apr 8 14:23 /sys/fs/bpf/counter
この状態でreader.pyを実行．counter.py 側の出力とほぼ同じ値が取得できるはず．
$ sudo python reader.py /sys/fs/bpf/counter
253
なお，pinningしたobjectは生成元のプロセス(ここではcounter.py)を終了したとしても削除されない．削除するには明示的にunlinkする必要がある．
$ ls -l /sys/fs/bpf/counter -rw-------. 1 root root 0 Apr 8 14:23 /sys/fs/bpf/counter $ sudo unlink /sys/fs/bpf/counter $ ls -l /sys/fs/bpf/counter ls: cannot access '/sys/fs/bpf/counter': No such file or directory
References
- Persistent BPF objects [LWN.net]
- Background, solutionのセクションに書いた内容がより詳しく述べられている
- 初期のパッチ(v1; 実際にマージされたのはv2)を元に書かれているため，実際の実装とは内容が一部異なる．(
BPF_PIN_FD->BPF_OBJ_PIN,BPF_GET_FD->BPF_OBJ_GET)
- bpf: add support for persistent maps/progs
- 初期実装のコミット．LWNの記事同様，背景が詳しく述べられている
- BPFの現在 // Speaker Deck
- Map pinningだけでなく，BPF全般の最近の動向が纏まっている
Maglev Hashing with Python
今更ながら，GoogleのMaglev論文で提案されているMaglev Hashingを手元で実装してみた．
Maglev: A Fast and Reliable Software Network Load Balancer
Maglev Hashingとは
所謂Consitent Hashの一種．Maglevロードバランサにおけるリアルサーバ選択に使用されている．
上記論文のSection 3.4で詳細が説明されている．NSDI'16での発表スライドも併せて眺めると分かりやすい．
Maglev: A Fast and Reliable Software Network Load Balancer | USENIX
Slide: https://www.usenix.org/sites/default/files/conference/protected-files/nsdi16_slides_eisenbud.pdf
実装
Golang実装を参考にしつつ，Pythonで実装してみた．
Example
256エントリを追加した状態で，更に1エントリの追加・削除を行っている．
テーブルサイズを65537としたとき*1，1エントリの追加・削除で影響を受ける割合が 772 / 65537 = 1.2%程度に抑えられていることが分かる．
>>> h = MaglevHash(m=65537)
>>> for i in range(256):
... h.add("172.16.1.{}".format(i))
...
>>> h.populate()
65537
>>> h.add("192.168.1.1")
>>> h.populate()
772
>>> h.lookup("10.0.0.1")
'172.16.1.111'
>>> h.remove("172.16.1.111")
>>> h.populate()
700
>>> h.lookup("10.0.0.1")
'172.16.1.68'
なお，Maglev Hashingの評価は論文のSection 5.3で示されている．
Kargerらの手法*2やRendezvousと比べ，各エントリに均等に分散されることが示されている．また，テーブルサイズ m が十分に大きければ，エントリの追加・削除によって影響を受ける割合も小さくなることも示されている．ただし，mの値を大きくすることは計算量の増大に繋がるため，考慮が必要である．
留意点
論文中では実装の詳細が割愛されている．上記実装のうち，下記の点については注意が必要である:
Linuxカーネルの新機能 XDP (eXpress Data Path) を触ってみる
先日netdev 1.2に参加してみたところ，XDP(eXpress Data Path)の話題で持ち切りといった感じだった． というわけで，XDPについて一通り調べつつ，実際に触ってみた．
XDPとは何か？
誤解を恐れずに一言で言うと，「Intel DPDKのような高速パケット処理基盤をLinuxカーネル自身が用意したもの」であると理解している．このスライドでは
A programmable, high performance, specialized application, packet processor in the Linux networking data path
と言っている．
DPDKはユーザランドアプリケーションがNICを直接叩く(=カーネルのネットワークスタックをバイパスする)ことで高速処理を実現している．一方XDPは，カーネル内の最もNICドライバに近い場所でフックしてeBPFを実行することによりパケット処理を実現する．
eBPFはカーネル内でプログラムを実行するための汎用的な仕組みで，パフォーマンス計測やセキュリティ方面で使用されている，らしい．これまでもtc-bpf(8)のようにeBPFでパケット処理を行う仕組み自体は用意されていたが，XDPによってより早い段階でパケット処理を行えるようになった．
XDPの概要についてはiovisor.orgの説明ページや冒頭で触れたスライドが詳しい．
bpf-docs/Express_Data_Path.pdf at master · iovisor/bpf-docs · GitHub
パフォーマンス
パフォーマンスは現時点において，受信したパケットを全てドロップするケースで20Mpps, L3フォワーディングでも10Mpps程度を達成するとされている．
youtu.be (6:46あたりから)
動作環境
XDPを利用するには，カーネル自体に加えてNICドライバでもサポートが必要となる． 先日リリースされた4.8でXDPサポートおよびMallanox mlx4ドライバサポートが取り込まれたので，少なくともこれ以降のカーネルが必要となる．
開発用としてe1000をサポートするパッチも出ているが，まだリリースされていない．
xdp-vagrantでXDPを手軽に試す
ここまでに書いたように，XDPが動作する環境を準備するのは若干敷居が高い．そこで便利なのがxdp-vagrant.
これを使うと，XDPサポート済みカーネル*1 + e1000サポートパッチ + BCC導入済みな環境がvagrantで簡単に手に入る．
BCC(BPF Compiler Collection)はユーザランドで動作するツール群で，XDPプログラムの読み込みやカーネル側のデータの操作を補助してくれる．Pythonバインディングが用意されているので，XDPプログラムはCで書きつつ*2ユーザランド側のマネジメント廻りをpythonで書く，ということが容易に実現できる．
ちなみに，ユーザランドとカーネルの両方をCで書く場合のサンプルコードは下記にある．
linux/xdp1_user.c at master · torvalds/linux · GitHub
linux/xdp2_kern.c at master · torvalds/linux · GitHub
vagrant upまで
Vagrantfileがlibvirt providerを前提に書かれいているので，vagrant-libvirtプラグインが利用可能な環境を事前に作っておく必要がある．更に，vagrant-restartプラグインも必要．
加えて，オリジナルのVagrantfileだと何故か ubuntu/trusty64 boxが指定されているが，このboxはlibvirt pluginに対応していない．自分でlibvirt対応boxを用意するか，他のlibvirt対応boxで代用する必要がある．ここでは s3than/trusty64 を使うことにする．
$ git clone https://github.com/iovisor/xdp-vagrant
$ cd xdp-vagrant
$ cat <<EOF | patch -p1
diff --git a/Vagrantfile b/Vagrantfile
index 2ee7327..c4392c6 100644
--- a/Vagrantfile
+++ b/Vagrantfile
@@ -5,7 +5,7 @@
end
Vagrant.configure('2') do |config|
- config.vm.box = "ubuntu/trusty64" # Ubuntu 14.04
+ config.vm.box = "s3than/trusty64" # Ubuntu 14.04
config.vm.network "private_network", ip: "192.168.50.4"
# fix issues with slow dns https://www.virtualbox.org/ticket/13002
EOF
$ vagrant plugin install vagrant-libvirt vagrant-reload
$ vagrant up
$ vagrant ssh -c "uname -a"
Linux vagrant-ubuntu-trusty-64 4.7.0-07282016-torvalds+ #28 SMP Thu Jul 28 11:52:33 PDT 2016 x86_64 x86_64 x86_64 GNU/Linux
特定ポート宛パケットをドロップする例
bccに含まれるサンプルコード xdp_drop_count.py を参考に，80/tcpと8080/tcp宛てパケットを全てドロップしつつ，ドロップした総パケット数をポート毎にカウントするプログラムを書いてみた．
パケットが到着するたびに drop_80_8080 が呼ばれる．この関数でXDP_PASSを返せばパケットは通常のネットワークスタックに送られる．XDP_DROPでドロップ，XDP_TXでTX queueに直接送り込まれる．
上記のプログラムを実行した状態でホスト側からvagrant VMのeth1宛にncやcurlでパケットを送ると，ドロップカウンタがカウントアップしていくことが分かる．ドロップカウンタのインクリメントはカーネル側で行い，それをユーザランドのpythonプログラムから参照して出力している．
vagrant$ $ ls -l
total 8
-rw-rw-r-- 1 vagrant vagrant 2034 Oct 10 06:10 drop_80_8080.c
-rwxrwxr-x 1 vagrant vagrant 807 Oct 10 06:06 loader.py
vagrant# ./drop_packet.py eth1
In file included from /virtual/main.c:4:
In file included from include/linux/if_ether.h:23:
In file included from include/linux/skbuff.h:34:
In file included from include/linux/dma-mapping.h:6:
In file included from include/linux/device.h:24:
In file included from include/linux/pinctrl/devinfo.h:21:
In file included from include/linux/pinctrl/consumer.h:17:
In file included from include/linux/seq_file.h:10:
include/linux/fs.h:2658:9: warning: comparison of unsigned enum expression < 0 is always false [-Wtautological-compare]
if (id < 0 || id >= READING_MAX_ID)
~~ ^ ~
1 warning generated.
XDP loaded.
80: 1
80: 2
80: 2
8080: 1
80: 2
8080: 2
80: 2
8080: 2
80: 2
8080: 2
host$ echo | nc 192.168.50.4 80 # timeout as no response host$ echo | nc 192.168.50.4 8080 # timeout as no response host$ echo | nc 192.168.50.4 81 Ncat: Connection refused.
まとめ
Linuxカーネルに最近追加された高速パケット処理基盤XDPを少しだけ触ってみた．まだリリースされて間も無いということもあって利用可能な環境や関連資料は少ないものの，MellanoxをはじめとしたNICベンダも(eBPF hardware offload含め)サポートに積極的であるように見えるので，今後徐々に盛り上がっていくと思われる．
DPDKと比較してどうか，という部分に関しては，既存のネットワークスタックとの共存やeBPF関連ツールの流用が効く，といった点がアプリケーションを書く側にとって嬉しい点になりそう．
何れにしても，今後の展開が楽しみ．
ロードバランサのアーキテクチャいろいろ
少し前に，Facebookのロードバランサが話題になっていた．
このエントリを読んで，各種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)も存在する．
ロードバランスは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宛の通信は下記のような流れで処理される:
- RouterにVIP 192.0.2.2宛のパケットが屆く．このとき，router上には192.0.2.2/32の等コスト経路が複数存在するので，そのうちいずれか1経路を選択してパケットをフォワードする．
- MUXにパケットが屆く．MUXは自身のセッションテーブルを参照し，セッションが既に存在するか確認する．存在すればそれに従ってフォワード先のVMを決定する．存在しなければhashによって新たにフォワード先のVMを決定し，セッションテーブルに記録する．フォワード先のVMが決定されると，パケットをIPIPでカプセル化してVM宛にフォワードする．
- HAを通過してパケットがVMに屆く．このとき，HAは透過的にIPIPのデカプセル化を行う．
- VMが応答を返す．なお，このときのパケットのソースIPアドレスはVMの実IPアドレスになっている．
- 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である必要は無い．
Router
Per-flow Equal Cost Multi Path (ECMP) によるLayer 3レベルでのトラフィック分散を行う．Microsoftの例におけるrouterと全く同じ役割と動作を行う．
Layer 4 LB
Consistent HashによるLayer 4レベルでのトラフィック分散を行う．これもMicrosoftの例におけるMUXとほぼ同じ役割と動作を行う．実装はLVSとExaBGPを用いている．
Layer 7 LB
コネクションを終端し，アプリケーションに対するLayer 7レベルでのトラフィック分散(reverse proxy)を行う．実装はProxygenを用いている．
上で挙げた各層の要素はコンテナ化され，Kubernetesを使って任意の場所にデプロイされる． 余談だが，発表動画中では気軽に「任意の場所にデプロイ」と言って図まで描いている。だがしかし、ファブリック的ではないネットワークアーキテクチャでこれをそのまま真似すると，router-L4LB間の帯域が足りなくて辛い思いをすることになると予想される．Facebookのデータセンターは末端まで広帯域を用意していることが知られているが，こういうことをやってこそ出来る芸だと思う．
トラフィックフロー
VIP 192.0.2.1があるとしたとき，このVIP宛の通信は下記のような流れで処理される．
- RouterにVIP 192.0.2.1宛のパケットが屆く．このとき，router上には192.0.2.1/32の等コスト経路が複数存在するので，そのうちいずれか1経路を選択してパケットをフォワードする．
- L4 LBにパケットが屆く．L4 LBは自身のセッションテーブルを参照し，セッションが既に存在するか確認する．存在すればそれに従ってフォワード先のL7 LBを決定する．存在しなければhashによって新たにフォワード先のL7 LBを決定し，セッションテーブルに記録する．フォワード先のL7 LBが決定されると，パケットをIPIPでカプセル化してL7 LB宛にフォワードする．
- L7 LBにパケットが屆く．L7 LBはIPIPをデカプセル化した上でコネクションを一旦終端し，upstreamのアプリケーションに対してリバースプロキシを行う．
- アプリケーションがL7 LBにレスポンスを返す．
- L7 LBを経由してパケットがクライアントに送られる．L3DSRなので，レスポンスのパケットはL4 LBを通過しない．
事例3: CloudFlare
CDN事業者であるCloudFlareは，世界中にPoPを設置してコンテンツ配信を行っている． そんなCloudFlareのPoPにおけるロードバランス手法が下記の記事で紹介されている．
CloudFlareのアーキテクチャで特徴的なのは，ネットワークレベルで負荷分散と障害時の切り離しが完結している点である．またインターネットレベルでのIP Anycastによる耐耐障害性確保も実現している．
Architecture
おおまかな構成は下図の通り．
この構成では，ロードバランサにおける負荷分散機能を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宛の通信は下記のような流れで処理される．MicrosoftやFacebookのものに比べると非常にシンプル．
- RouterにVIP 192.0.2.3宛のパケットが屆く．このとき，router上には192.0.2.3/32の等コスト経路が複数存在するので，そのうちいずれか1経路を選択してパケットをフォワードする．
- Edge serverにパケットが屆く．パケットは特にカプセル化等はされておらず，通常のものと変わらない．
- Edge serverがレスポンスを返す．
- ルーティングテーブルに従ってパケットがクライアントに送られる．
余談: Google
GoogleのロードバランスといえばGFEだと思うが，明確な資料は見当たらなかった． 見付けられた範囲だと、下記の動画で簡単に言及がある程度である．
少し前にSeesawというものが公開されていたが，これがGoogle内部ではどういう位置付けでどの程度使われているのかよく分からないので何とも言えないところ．
追記 (2016-02-29 19:25)
Googleのロードバランサに関する情報を@rrreeeyyyさんに教えていただいた:
Google の LB は Maglev って名前が付いてて最近論文が公開されてる ( https://t.co/gr16vu5FMn ) / “ロードバランサのアーキテクチャいろいろ - yunazuno.log” https://t.co/GfYs2gJLWy
— れい (Yoshikawa Ryota) (@rrreeeyyy) 2016年2月29日
論文は下記のページに掲載されている．こんどの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間のどこかに同じ機能を持たせれば同様のことは実現できそうに見える．
