最近あるロードバランサにさわった時、参考のために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

新たに１接続増やしてみます。

$ 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

もう１接続増やしてみます。

$ 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が内部で管理している実サーバリストのうち、頭の方にある実サーバが選ばれるようです。

さらに、もう１接続増やしてみます。

$ 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のサーバに割り振られました！