Maglev: A Fast and Reliable Software Network Load Balancer

GoogleのMaglevというロードバランサの論文の紹介です。

Transcript

1. CyberAgent, Inc. All Rights Reserved Maglev: A Fast and Reliable Software Network Load Balancer アドテクスタジオ Dynalyst 黒崎 優太
2. 黒崎 優太 • アドテクスタジオ Dynalyst エンジニア • 2年目 ◦ Scala, LXD • 今日はGoogleの論文の紹介をします 査読に参加しました 自宅に設置しました
3. 概要 • Maglevとは • ロードバランサ 3方式 ◦ ふつうのやつ(?) ◦ DNS-RR ◦ DSR • Maglevのアーキテクチャ ◦ ECMP ◦ 分散 Connection Tracking ◦ DSR
4. Maglevとは
5. Maglevとは • Googleの分散型L4ロードバランサ ◦ GCPのロードバランサの元になっている • 今日はタイトルになっているMaglevに関す る論文を解説します。
6. GCPのロードバランサ • Compute Engine Load Balancing hits 1 million requests per second! ◦ https://cloudplatform.googleblog.com/2013_11_01_archive.html • 1IPアドレス/ウォームアップなしでいきなり 100万RPSをさばける ◦ グローバルな ▪ 負荷分散 ▪ 障害耐性 ◦ ソフトウェアLB
7. 余談: Facebook • http://www.slideshare.net/pallotron/dhcp-at-facebook-evolution-of-an-infrastructure
8. ロードバランサ3方式: ふつうのやつ
9. • 普通すぎて(?)なんと言えばよいのやら… ◦ 一番わかりやすい例 ◦ NAPTする ふつうのやつ
10. ロードバランサ3方式: DNS RR
11. • DNSのAレコードを複数登録しておく ◦ RR = ラウンドロビン DNS RR example.com (198.51.100.1) example.com (198.51.100.2) example.com (198.51.100.3) example.com (198.51.100.4) Aレコードが複数あった場合に 毎回違うものが帰ってくるのを利用 (AWSのELBは前述のLBとDNS RRの 組み合わせ)
12. ロードバランサ3方式: DSR
13. • Direct Server Returnの略 L2 DSR 198.51.100.10 198.51.100.11 (lo: 198.51.100.10) 198.51.100.12 (lo: 198.51.100.10) 198.51.100.13 (lo: 198.51.100.10) 198.51.100.14 (lo: 198.51.100.10) s01 s02 s03 s04 198.51.100.10 に アクセス L2 SW
14. • Direct Server Returnの略 L2 DSR 198.51.100.10 198.51.100.11 (lo: 198.51.100.10) 198.51.100.12 (lo: 198.51.100.10) 198.51.100.13 (lo: 198.51.100.10) 198.51.100.14 (lo: 198.51.100.10) s01 s02 s03 s04 pc01 宛先MACアドレスを s02のものに書き換える (送信元/宛先IPは書き換えない) 198.51.100.10 に アクセス
15. • Direct Server Returnの略 L2 DSR 198.51.100.10 198.51.100.11 (lo: 198.51.100.10) 198.51.100.12 (lo: 198.51.100.10) 198.51.100.13 (lo: 198.51.100.10) 198.51.100.14 (lo: 198.51.100.10) s01 s02 s03 s04 198.51.100.10 に アクセス 宛先MACアドレスを s02のものに書き換える (宛先IPは書き換えない) 戻りパケットは LBを経由しない！ (DirectにReturnする！)
16. • 戻りトラフィックがどんなに大きくてもLBはリ クエストだけ転送すれば良いので ◦ 転送負荷が非常に低くなる！ ◦ 遅延も抑えられる！ ◦ 送信元IPが書き換わらない！ L2 DSR のいいところ
17. L3 DSR • 前述のDSRをL3で行う • L2 DSRだと各ネットワークセグメントごとにLB を設置しなければならない • →別セグメントにLBを設置！ ◦ このままだとパケットがセグメントを またげないのでL3に対応する必要が…
18. L3 DSR このままだとセグメントを 超えられない app-A app-B app-C L2 SW L2 SW L2 SW L2 SW L3 SW セグメントをまたぐ必要性
19. L3 DSR パケットをカプセリングする (トンネリング) app-A app-B app-C L2 SW L2 SW L2 SW L2 SW L3 SW セグメントをまたぐ IP TCP Data IP TCP Data IP 先頭にIPヘッダを付加する(IPIPトンネルの例) IP TCP Data LBでIPヘッダを1つ足す サーバでIPヘッダを1つ取る
20. L3 DSR パケットをカプセリングする (トンネリング) app-A app-B app-C L2 SW L2 SW L2 SW L2 SW L3 SW セグメントをまたぐ 戻りのパケットはカプセリング不要
21. Maglevのアーキテクチャ: ECMP
22. パケットは吸い込むもの • インターネット上では トラフィックは吸い込まれる ◦ 経路を広告すると、パケットが 送られてくる(吸い込まれるイメージ) ◦ 複数拠点で同じ経路を広告すれば、 近い方(コストが小さい方)に吸い込まれる
23. パケットは吸い込むもの • 同じアドレスレンジを広報しても、 近い方に吸い込まれる(IP AnyCast) 日本リージョン アメリカリージョン 198.51.100.1/24 は こっちですよ♪ 198.51.100.1/24 は こっちですよ♪
24. パケットは吸い込むもの • リージョン丸ごと障害が起きても大丈夫 198.51.100.1/24 は こっちですよ♪ 198.51.100.1/24 は こっちですよ♪ 一番近いところへ 日本リージョン アメリカリージョン
25. ECMP • Equal Cost Multi Path ◦ コスト(前のスライドで言う距離)が同じだった時 の挙動 ◦ 等コストの場合はルータがロードバランシングす る ◦ (今回の場合)インターネット接続部分 だけでなく、自組織内でも行っている
26. ECMP • 同じ距離(コスト)のルータが複数あったら？ アメリカリージョン 198.51.100.1/24 は こっちですよ♪ 198.51.100.1/24 は こっちですよ♪ 日本リージョン
27. ECMP • ロードバランスされる アメリカリージョン 198.51.100.1/24 は こっちですよ♪ 198.51.100.1/24 は こっちですよ♪ 日本リージョン
28. Maglevのアーキテクチャ: 分散 Connection Tracking
29. Connection Tracking • これがないと通信が崩壊する
30. Connection Trackingがない時… TCPのコネクションを確立してみる SYN
31. Connection Trackingがない時… TCPのコネクションを確立してみる SYN SYN/ACK
32. TCPのコネクションを確立してみる Connection Trackingがない時… SYN SYN/ACK ACK 身に覚えのない ACK コネクション 確立不能
33. Connection Trackingがある時！ TCPのコネクションを確立してみる SYN
34. Connection Trackingがある時！ TCPのコネクションを確立してみる SYN SYN/ACK
35. Connection Trackingがある時！ TCPのコネクションを確立してみる SYN SYN/ACK ACK コネクション 確立成功！ connection tracking
36. Connection Trackingのしくみ • 5-tuple ◦ 　 • 5-tupleの組み合わせで転送先を固定する • これでコネクションが維持される • ここまでは普通 ◦ (前述の3種類のLBもやってる) • どうやってこれをスケールアウトさせるか ◦ => 分散 Connection Trackingを実装したい！
37. スケールアウトさせるには • どのLBに通信が来ても同じ挙動をする必要 がある ECMP コネクション確立済
38. • どのLBに通信が来ても同じ挙動をする必要 がある ◦ 独立してコネクション 管理するとダメ スケールアウトさせるには 身に覚えのない コネクション ECMP クライアントは 1コネクションしか張っていな いので 1台としか通信できない コネクション確立済
39. • こうなってほしい ◦ 全台が同じ情報を持った状態 ◦ とはいえLB間でコネクションの情報を リアルタイムに同期するのは難しい スケールアウトさせるには コネクション確立済 ECMP ECMP 必ず1対1で通信が 成立する状態！
40. Consistent Hashing • http://www.slideshare.net/paulowniaceae/consistent-hash
41. Consistent Hashing • 円を用意します • ハッシュ関数を使って適当に サーバを置きます
42. Consistent Hashing • ハッシュ関数を使って適当にサーバと クライアントを 振り分けます ◦ 5-tupleを使う hash((srcIP, srcPort, dstIP, dstPort, proto))
43. Consistent Hashing • 各サーバは時計回り方向のクライアントを 処理する
44. • 複数LBでも一意な転送ができる！ Consistent Hashing hash( ) hash( ) Maglev nodes
45. • スケールアウトしても担当が変わる サーバが最小限 Consistent Hashing ↑増えた hash( ) hash( ) Maglev nodes
46. • バックエンドの数が変わっても均一にしたい Maglev Hashing (Consistent Hashingの応用) • https://blog.acolyer.org/2016/03/21/maglev-a-fast-and-reliable-software-network-load-balancer/ offset = hash1(hostname) mod M skip = hash2(hostname) mod (M-1) + 1 (M = 100より大きい素数) // offset = 3, skip = 4のとき B0 = [ 3, // (3 + 0 * 4) mod 7 0, // (3 + 1 * 4) mod 7 4, // (3 + 2 * 4) mod 7 1, // (3 + 3 * 4) mod 7 5, // (3 + 4 * 4) mod 7 2, // (3 + 5 * 4) mod 7 6, // (3 + 6 * 4) mod 7 ]
47. Maglevのアーキテクチャ: DSR
48. DSR • 前述のL3 DSR ◦ GREでカプセリング ▪ IPIPのようにヘッダを付加する方式 IP TCP Data IP TCP Data IP IP TCP Data LBでIP + GREヘッダを1つ足す サーバでIP + GREヘッダを1つ取る GRE
49. Maglevとは
50. Maglev論文のまとめ • ECMP + 分散connection tracking + DSR ◦ => Fast and Reliable Software Network Load Balancer • http://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/44824.pdf
51. 今日話さなかったこと
52. 疑問 • GCPはHTTP ロードバランサ(L7)も 用意されてるがどんな仕組みなのか • 1ノードあたりの性能高すぎない？ ◦ ショートパケットでも10Gbps出るらしい ▪ ユーザ空間でパケットを処理 (Intel DPDK的な)してるらしい
53. ご清聴ありがとうございました