LVS(Linuxロードバランサ)のスケジューラの実装をみてみた
最近あるロードバランサにさわった時、参考のためにLVSのlc(Least-Connection)スケジューラの実装を確認していました。lcスケジューラは文字通り、接続数が一番少ないサーバに処理を割り振るアルゴリズムを実装しています。ただ実際の実装を見ると、もう少し複雑なことをしていたので、メモしておきます。
要するに
lcスケジューラは、内部的には、実サーバのオーバーヘッドを一つ一つ計算し、そのオーバーヘッドが一番小さな実サーバに処理を割り振ります。このときオーバーヘッド=TCP接続の数とするのではなく、TCP接続の状態によって重み付けした値でオーバーヘッドを計算していました。
具体的には、Activeな(=ESTABLISHED状態の)TCP接続は、Inactiveな(=ESTABLISHED状態ではない)TCP接続と比べて256倍の重みで計算していました。例えば、Activeな接続が1、Inactiveな接続が0の実サーバと、Activeな接続が0、Inactiveな接続が255の実サーバでは、前者のサーバに新規の接続は割り振られます。
以下は、実装と実際の挙動を確認してみたときのメモです。
実装をみてみる
今回はこちらから取得したLinux 3.13.0のコードを使用しました。
lcスケジューラの実装
lcスケジューラは、linux-3.13/net/netfilter/ipvs/ip_vs_lc.c
で実装されています。新規接続の割り振り先を決めるときに呼ばれるip_vs_lc_schedule
という関数があるのですが、その中の以下の処理で割り振り先を決めています。
list_for_each_entry_rcu(dest, &svc->destinations, n_list) { if ((dest->flags & IP_VS_DEST_F_OVERLOAD) || atomic_read(&dest->weight) == 0) continue; doh = ip_vs_dest_conn_overhead(dest); if (!least || doh < loh) { least = dest; loh = doh; } }
ユーザ空間で走るコードとはちょっと見た目が違いますが、基本的にはsvc->destinations
から辿れる実サーバのリンクリストを使い、オーバーヘッドが最小の実サーバを取得しているだけです。
この中で呼ばれているip_vs_dest_conn_overhead(dest)
の定義を見てみます。linux-3.13/include/net/ip_vs.h
の中です。
static inline int ip_vs_dest_conn_overhead(struct ip_vs_dest *dest) { /* * We think the overhead of processing active connections is 256 * times higher than that of inactive connections in average. (This * 256 times might not be accurate, we will change it later) We * use the following formula to estimate the overhead now: * dest->activeconns*256 + dest->inactconns */ return (atomic_read(&dest->activeconns) << 8) + atomic_read(&dest->inactconns); }
親切なコメントにあるとおり、Activeな接続は256倍の重みで計算しています。
接続状態管理の実装
せっかくなのでもう少し見てみます。ここまでに出てきたactiveな接続とinactiveな接続(↑のコードにおけるdest->activeconns
とdest->inactconns
)は、そもそも何が違うのでしょうか?
これらの定義は、linux-3.13/include/net/ip_vs.h
のip_vs_dest構造体の中にあります。実サーバごとにactiveconnsという変数とinactconnsという変数を保持しています。
/* * The real server destination forwarding entry * with ip address, port number, and so on. */ struct ip_vs_dest { // 省略 /* connection counters and thresholds */ atomic_t activeconns; /* active connections */ atomic_t inactconns; /* inactive connections */ atomic_t persistconns; /* persistent connections */ __u32 u_threshold; /* upper threshold */ __u32 l_threshold; /* lower threshold */ // 省略 };
隣でpersistconnsという変数も定義しています。これはLVSのPersistentオプションをセットした時に使われるようです。同じクライアントからのリクエストは同じ実サーバに割り振る設定です。
さらにその下では、スレッショルドを定義しています。これはLVSのu-threshold/l-thresholdオプションをセットした時に使われます。接続数がu-thresholdを超えるとOVERLOADフラグが立ち、新規接続の割り振りがされなくなります。OVERLOAD状態の実サーバを割り振り先候補から外す処理は、実は上述のip_vs_lc_schedule関数の中にありました!OVERLOADフラグはl-thresholdを下回ると外されます。
話がそれましたが、activeconnsとinactconnsの値はどこで設定しているのでしょうか。探してみると、新規接続を割り振るときにlinux-3.13/net/netfilter/ipvs/ip_vs_conn.c
のip_vs_bind_dest関数の中で設定しているのと、TCP接続の状態が変化したときにlinux-3.13/net/netfilter/ipvs/ip_vs_proto_tcp.c
のset_tcp_state関数の中で設定しているのが見つかりました。前者の方は基本的にinactconnsをインクリメントしているだけなのでスキップして、後者のほうを見てみます。
具体的には、以下のような処理になっています。
if (!(cp->flags & IP_VS_CONN_F_INACTIVE) && (new_state != IP_VS_TCP_S_ESTABLISHED)) { atomic_dec(&dest->activeconns); atomic_inc(&dest->inactconns); cp->flags |= IP_VS_CONN_F_INACTIVE; } else if ((cp->flags & IP_VS_CONN_F_INACTIVE) && (new_state == IP_VS_TCP_S_ESTABLISHED)) { atomic_inc(&dest->activeconns); atomic_dec(&dest->inactconns); cp->flags &= ~IP_VS_CONN_F_INACTIVE; }
TCP接続の状態がESTABLISHEDになったらactiveconnsを増やし、その他の状態になったらinactconnsを増やしています。
new_stateという変数にTCP接続の状態が保持されているようです。この変数は、linux-3.13/net/netfilter/ipvs/ip_vs_proto_tcp.c
のset_tcp_state関数の以下にあります。
new_state = pd->tcp_state_table[state_off+state_idx].next_state[cp->state];
state_offがパケットの方向、state_idxがSYN/ACKなどのフラグ、cp->stateが現在の状態を示しており、その上で、以下のtcp_state_tableを利用して状態を出しています。
static struct tcp_states_t tcp_states [] = { /* INPUT */ /* sNO, sES, sSS, sSR, sFW, sTW, sCL, sCW, sLA, sLI, sSA */ /*syn*/ {{sSR, sES, sES, sSR, sSR, sSR, sSR, sSR, sSR, sSR, sSR }}, /*fin*/ {{sCL, sCW, sSS, sTW, sTW, sTW, sCL, sCW, sLA, sLI, sTW }}, /*ack*/ {{sES, sES, sSS, sES, sFW, sTW, sCL, sCW, sCL, sLI, sES }}, /*rst*/ {{sCL, sCL, sCL, sSR, sCL, sCL, sCL, sCL, sLA, sLI, sSR }}, /* OUTPUT */ /* sNO, sES, sSS, sSR, sFW, sTW, sCL, sCW, sLA, sLI, sSA */ /*syn*/ {{sSS, sES, sSS, sSR, sSS, sSS, sSS, sSS, sSS, sLI, sSR }}, /*fin*/ {{sTW, sFW, sSS, sTW, sFW, sTW, sCL, sTW, sLA, sLI, sTW }}, /*ack*/ {{sES, sES, sSS, sES, sFW, sTW, sCL, sCW, sLA, sES, sES }}, /*rst*/ {{sCL, sCL, sSS, sCL, sCL, sTW, sCL, sCL, sCL, sCL, sCL }}, /* INPUT-ONLY */ /* sNO, sES, sSS, sSR, sFW, sTW, sCL, sCW, sLA, sLI, sSA */ /*syn*/ {{sSR, sES, sES, sSR, sSR, sSR, sSR, sSR, sSR, sSR, sSR }}, /*fin*/ {{sCL, sFW, sSS, sTW, sFW, sTW, sCL, sCW, sLA, sLI, sTW }}, /*ack*/ {{sES, sES, sSS, sES, sFW, sTW, sCL, sCW, sCL, sLI, sES }}, /*rst*/ {{sCL, sCL, sCL, sSR, sCL, sCL, sCL, sCL, sLA, sLI, sCL }}, };
解読しづらいのですが、よくみると、例えばESTABLISHED状態(sES)の接続にINPUT方向のFINフラグが立ったパケットが来たら、CLOSE-WAIT状態(sCW)とするんだな、といったことがわかります。恐ろしく面倒ですね。
実験してみる
lcスケジューラの挙動を、実験して確認してみます。192.168.1.1がVirtual IP、10.0.3.77と10.0.3.195が実サーバのIPです。実験のため、IP 10.0.3.77の実サーバへのリクエストは60秒かけてレスポンスを返すようにしました。
まず、現在 次のような状況だとします。
$ sudo ipvsadm -Ln IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 192.168.1.1:8080 lc -> 10.0.3.77:8080 Route 1 1 0 -> 10.0.3.195:8080 Route 1 0 2
新たに1接続増やしてみます。
$ sudo ipvsadm -Ln IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 192.168.1.1:8080 lc -> 10.0.3.77:8080 Route 1 1 0 -> 10.0.3.195:8080 Route 1 0 3
合計接続数だとIP10.0.3.77のサーバのほうが少ないですが、新たな接続はIP10.0.3.195のサーバに割り振られました。
この調子で、IP10.0.3.195のサーバに256接続されているところまで増やしました。この段階では、2つの実サーバのオーバーヘッドは同じ値のはずです。
$ sudo ipvsadm -Ln IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 192.168.1.1:8080 lc -> 10.0.3.77:8080 Route 1 1 0 -> 10.0.3.195:8080 Route 1 0 256
もう1接続増やしてみます。
$ sudo ipvsadm -Ln IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 192.168.1.1:8080 lc -> 10.0.3.77:8080 Route 1 1 0 -> 10.0.3.195:8080 Route 1 0 257
まだIP10.0.3.195のサーバに割り振られます。実装をみると、オーバーヘッドが同じ場合は、IPVSが内部で管理している実サーバリストのうち、頭の方にある実サーバが選ばれるようです。
さらに、もう1接続増やしてみます。
$ sudo ipvsadm -Ln IP Virtual Server version 1.2.1 (size=4096) Prot LocalAddress:Port Scheduler Flags -> RemoteAddress:Port Forward Weight ActiveConn InActConn TCP 192.168.1.1:8080 lc -> 10.0.3.77:8080 Route 1 2 0 -> 10.0.3.195:8080 Route 1 0 257
ようやくIP10.0.3.77のサーバに割り振られました!
まとめ
lcスケジューラはTCP接続の状態によって重み付けをしていることがわかりました。TIME-WAIT状態の接続とかはそこそこ長い間残る割に負荷は小さいので、このような実装は効果がありそうです。
ちなみにコードを読んでいて、IPVSはnetfilter機能で実現していることを知りました。iptablesとかで使われている機能ですが、こんなところでも使われているんですね。
参考にしたページ
ipvsadmの使い方 http://memogakki.es.land.to/linux/index.php?ipvsadm
TCPの状態遷移 http://qiita.com/mogulla3/items/196124b9fb36578e5c80
IPVSのPersistentオプション http://www.ducea.com/2008/06/16/lvs-persistence/