prefork サーバーと thundering herd 問題

Catalyst を POE で動かす Engine の Catalyst::Engine::HTTP::POE という実装が CPAN にあります。"Single-threaded multi-tasking Catalyst engine " だそうです。"Single-threaded" と言いつつも実装を覗いてみると環境変数 CATALYST_POE_MAX_PROC を 1 よりも大きく設定することで prefork する実装になってます。POEシングルスレッドではアプリケーション内で発生するブロックを避けることが難しいのでそのための実装じゃないかなと思います。

ところでこの Catalyst POE エンジン、prefork の実装はどのように行っているかというと POE から prefork と名の付いたイベントが発生するとおもむろに子プロセスを生成する、というのもの。複数のプロセスを立ち上げておいて accept(2) を発行することで、マルチプロセスでクライアントからの接続に応答するという普通の prefork なのですが特に accept(2) 呼び出しをシリアライズするようなことはしていないようです。

以前に読んだ本では accept(2) を複数のプロセスから呼び出すと問題があるのでシリアライズしる! とあったのですが、この Catalyst POE エンジンの実装ではそのような様子が見えないので大丈夫なのかな...と思い調べごとをしていたら深追いしてしまいました。以下、そのサマリです。

まずは Perl で、accept(2) を順列化しない prefork の echo サーバーの実装を書いて見ます。

#!/usr/local/bin/perl
use strict;
use warnings;
use IO::Socket;

my @children;

my $listen = IO::Socket::INET->new(
    LocalPort => 9999,
    Listen    => SOMAXCONN,
    Reuse     => 1,
) or die $!;

for (1..10) {
    unless (fork) {
        while (my $con = $listen->accept) {
            while ($con->sysread(my $buffer, 1024)) {
                $con->syswrite($buffer);
            }
            $con->close;
        }
        exit (0);
    }
}

$listen->close;
wait;

こんな感じで。エラー処理ですとか、ソケットのノンブロッキング処理とかをするとコードが複雑になるのでその辺は加味せず最小限のものにしてあります。

待機ソケットを作って子プロセスをたくさん生成し、その子プロセスそれぞれで IO::Socket->accept を呼びます。子プロセスを作った時点で、そのとき親が持っていたファイルディスクリプタはすべて子にもコピーされます。これで OS に accept(2) が発行されてクライアントからの接続を受け付けることができます。

なお Linux の場合は、子のそれぞれのファイルディスクリプタはプロセス構造体(カーネル内の task_struct 構造体) のメンバの配列のインデックスです。この配列の中身はファイル構造体へのポインタです。そして子プロセスにコピーされたファイルディスクリプタはすべて同じ一つの待機ソケットを示していることになります。ソケットが子にコピーされているのではなく、あくまでポインタがコピーされてるだけです。従って複数の子プロセスから accept(2) を発行するといっても別々のソケットに accept(2) が発行されているわけではなく、単一のソケットに対して各所から accept(2) が呼ばれているということになります。

さて、複数のプロセスが同時に accept(2) を発行するとどうなるか。accept(2) を発行するとブロッキングが発生し、プロセスはスリープ状態になります。クライアントから接続があると全てのプロセスは起床しますがどれか一つのプロセスがそのクライアント接続を獲得して処理を開始し他のプロセスはまたスリープに入ります。(実はこれが正確な説明じゃないというのは後で。) 従って、上記のプログラムは一応 prefork サーバーとして動きます。複数の端末から telnet しても、ちゃんとブロックされずにそれぞれに応答が帰ります。

が、accept(2) の度に複数の子プロセスが一斉に起き上がっては一つだけが起き続けて後は寝る、という実装はどうでしょう。明らかに非効率ですね。このように一つのコネクションが起点になってすべての preforked なプロセス/スレッドが起き上がってしまいシステムに負荷がかかる現象を "thundering herd" と呼ぶらしいです。

Linux の thundering herd 問題については以下の論文が詳しいです。なお、この論文の内容が当てはまるのは古いカーネルだけの話というオチがあるのは後述。

• CITI: Projects: Linux scalability: Accept() scalability on Linux

thundering herd が起きないようにするには、accept(2) がコールされる処理を順列化するのが定番です。Perlネットワークプログラミング―ソケットの使い方からクライアント/サーバーシステムの開発まで でも解説されているファイルロックによるアドバイザリロックを行う方法だと以下のようになります。 ファイルロックによるアドバイザリロックは thundering herd を避けるのが目的ではありませんでした。勘違いしていました。コメント欄参照。

#!/usr/local/bin/perl
use strict;
use warnings;
use IO::Socket;
use Path::Class;
use Fcntl ':flock';

my $lock = file('lockfile');
$lock->touch;

local $SIG{INT} = sub {
    $lock->remove;
    exit(0);
};

my $listen = IO::Socket::INET->new(
    LocalPort => 9999,
    Listen    => SOMAXCONN,
    Reuse     => 1,
) or die $!;

for (1..10) {
    unless (fork) {
        while (1) {
            my $fh = $lock->openr or die $!;
            flock($fh, LOCK_EX);
            my $con = $listen->accept;
            flock($fh, LOCK_UN);
            $fh->close;

            while ($con->sysread(my $buffer, 1024)) {
                $con->syswrite($buffer);
            }
            $con->close;
        }
        exit 0;
    }
}

$listen->close;
wait;

$listen->accept の前後で flock でロックをかけます。flock は、ロックを獲得した以外のプロセスからの flock 発行に対してアプリケーションをブロックしますので、これによってある時間にはロックを獲得したプロセスだけが accept(2) 呼び出しをすることができます。これでめでたく thundering herd 問題は解決できました。ただし、ロックにファイルロックを使うのはあまり効率が良くないので、効率を重視するのであればセマフォなどもっと軽量なロック機構への置き換えが必要でしょう。

とまあ、ここまでは良かったのですが、実際に thundering herd が起こっている様子を見てみたいと思い、最初のプログラムのシステムコールをトレースしてみました。strace で -f をつけると子プロセスごとトレースを取ることができます。

% strace -f perl prefork_echo.pl
...
[pid  5467] <... getppid resumed> )     = 5459
[pid  5459] close(3 <unfinished ...>
[pid  5467] accept(3,  <unfinished ...>
[pid  5459] <... close resumed> )       = 0
[pid  5459] waitpid(-1, Process 5459 suspended
 <unfinished ...>
[pid  5468] getpid( <unfinished ...>
[pid  5469] getpid( <unfinished ...>
[pid  5468] <... getpid resumed> )      = 5468
[pid  5469] <... getpid resumed> )      = 5469
[pid  5468] getppid( <unfinished ...>
[pid  5469] getppid( <unfinished ...>
[pid  5468] <... getppid resumed> )     = 5459
[pid  5469] <... getppid resumed> )     = 5459
[pid  5469] accept(3,  <unfinished ...>
[pid  5468] accept(3,

という感じでサーバーを立ち上げると複数のプロセスが accept(2) でブロックされるのが分かります。ここである特定の端末から接続をすると、一斉に子プロセスが立ち上がる様子が見えるんだろう...と思い実際にやってみると

 <unfinished ...>
[pid  5460] <... accept resumed> {sa_family=AF_INET, sin_port=htons(2959), sin_addr=inet_addr("127.0.0.1")}, [16]) = 4
[pid  5460] ioctl(4, SNDCTL_TMR_TIMEBASE or TCGETS, 0xbfffe078) = -1 EINVAL (Invalid argument)
[pid  5460] _llseek(4, 0, 0xbfffe0b0, SEEK_CUR) = -1 ESPIPE (Illegal seek)
[pid  5460] ioctl(4, SNDCTL_TMR_TIMEBASE or TCGETS, 0xbfffe068) = -1 EINVAL (Invalid argument)
[pid  5460] _llseek(4, 0, 0xbfffe0a0, SEEK_CUR) = -1 ESPIPE (Illegal seek)
[pid  5460] fcntl64(4, F_SETFD, FD_CLOEXEC) = 0
[pid  5460] read(4,

と、予想に反して一つの子プロセスしか反応しません。あれれ。話が違う。thundering herd は起きてない?

ここで先の論文を詳しく読んで見ます。

• sock->state_change.................... (pointer to sock_def_wakeup)
• sock->data_ready...................... (pointer to sock_def_readable)
• sock->write_space..................... (pointer to tcp_write_space)
• sock->error_report.................... (pointer to sock_def_error_report)

The code for each one of these methods invokes the wake_up_interruptible() function. This means that every time one of these methods is called, tasks may be unnecessarily awakened. In fact, in the accept() call alone, Linux invokes three of these methods, essentially tripling impact of the "thundering herd" problem. The three methods invoked in every call to accept() in the 2.2.9 kernel are tcp_write_space(), sock_def_readable() and sock_def_wakeup(), in that order.

accept() の中で使われているいくつかのソケット用関数が wake_up_interruptible 関数(マクロ)を呼んでてそれが原因だと書いてあります。wake_up_interruptible はカーネルのスケジューラの重要なマクロでキューに溜まったプロセスのうち待機状態のものを起床させるものです。この辺は 負荷とは何か - naoyaのはてなダイアリー あたりも参照していただけるとこれ幸い。

それで、です。色々調べてみるとこの wake_up_interruptible などに関連するコードが、Linux 2.2 と Linux 2.4 以降では実装が異なっているそう。

v2.2までは、wake_up関数は対象となるWAITキューヘッドで待ちに入っている プロセスを全てRUN状態にしていたが、性能改善のためv2.4からは WAITキューヘッドで待ちに入っているプロセスのうち先頭のプロセスだけを RUN状態にすることができるようになった。

だそうで。確かに Linux 2.2 と 2.6 で wake_up 関数群を比較すると 2.2 では

• wake_up
• wake_up_interruptible

の二種類に対し 2.6 では

• wake_up
• wake_up_interruptible
• wake_up_all
• wake_up_interruptible_all
• wake_up_all_sync
• wake_up_interruptible_sync

と数が増えています。名前からもわかるとおり、プロセスをまとめて起床させるものとそうでないものとがあります。新しいカーネルでは先の論文にもあるソケット周りの関数では複数のうちひとつのプロセスだけを起床させる wake_up / wake_up_interruptible 関数が使われています。従って、accept(2) でプロセスが一斉に起動する thundering herd は発生しない、ということになります。

なお上記の引用部分ではカーネル 2.4 から...とのことでしたが論文にも挙がっている 2.2.9 とカーネル 2.2 系の最新のコードとではスケジューラ周りの実装がまたちょっと違っていて、2.2.9 では解説のとおり全部まとめてしか起床させられないものの、2.2.26 の kernel/sched.c では

void __wake_up(struct wait_queue **q, unsigned int mode)
{
        struct task_struct *p, *best_exclusive;
        struct wait_queue *head, *next;
        unsigned int do_exclusive;

        if (!q)
                goto out;
        /*
         * this is safe to be done before the check because it
         * means no deference, just pointer operations.
         */
        head = WAIT_QUEUE_HEAD(q);

        read_lock(&waitqueue_lock);
        next = *q;
        if (!next)
                goto out_unlock;

        best_exclusive = 0;
        do_exclusive = mode & TASK_EXCLUSIVE;
        while (next != head) {
                p = next->task;
                next = next->next;
                if (p->state & mode) {
                        if (do_exclusive && p->task_exclusive) {
                                if (best_exclusive == NULL)
                                        best_exclusive = p;
                        }
                        else {
                                wake_up_process(p);
                        }
                }
        }
        if (best_exclusive)
                wake_up_process(best_exclusive);
out_unlock:
        read_unlock(&waitqueue_lock);
out:
        return;
}

と TASK_EXCLUSIVE モードが導入されて待機プロセス一つだけを起床させることができるようになっているようです。

さて、話は変わって prefork なウェブサーバーの代表的な実装と言えばやはり Apache です。Apache は accept() 周りの実装はどうしてるか、と気になってちょっとコードを覗いてみました。server/mpm/prefork/prefork.c です。

static void accept_mutex_on(void)
{
    apr_status_t rv = apr_proc_mutex_lock(accept_mutex);
    if (rv != APR_SUCCESS) {
        const char *msg = "couldn't grab the accept mutex";

        if (ap_my_generation !=
            ap_scoreboard_image->global->running_generation) {
            ap_log_error(APLOG_MARK, APLOG_DEBUG, rv, NULL, msg);
            clean_child_exit(0);
        }
        else {
            ap_log_error(APLOG_MARK, APLOG_EMERG, rv, NULL, msg);
            exit(APEXIT_CHILDFATAL);
        }
    }
}

static void accept_mutex_off(void)
{
    apr_status_t rv = apr_proc_mutex_unlock(accept_mutex);
    if (rv != APR_SUCCESS) {
        const char *msg = "couldn't release the accept mutex";

        if (ap_my_generation !=
            ap_scoreboard_image->global->running_generation) {
            ap_log_error(APLOG_MARK, APLOG_DEBUG, rv, NULL, msg);
            /* don't exit here... we have a connection to
             * process, after which point we'll see that the
             * generation changed and we'll exit cleanly
             */
        }
        else {
            ap_log_error(APLOG_MARK, APLOG_EMERG, rv, NULL, msg);
            exit(APEXIT_CHILDFATAL);
        }
    }
}

と、accept をロック/ロック解除するための関数が用意されてます。またこの accept_mutex_* ではロックに色々な実装が使えるようになっていて、httpd.conf の AcceptMutex ディレクティブで設定できるようです。

さらにもう一つこんな箇所があります。

/* On some architectures it's safe to do unserialized accept()s in the single
 * Listen case.  But it's never safe to do it in the case where there's
 * multiple Listen statements.  Define SINGLE_LISTEN_UNSERIALIZED_ACCEPT
 * when it's safe in the single Listen case.
 */
#ifdef SINGLE_LISTEN_UNSERIALIZED_ACCEPT
#define SAFE_ACCEPT(stmt) do {if (ap_listeners->next) {stmt;}} while(0)
#else
#define SAFE_ACCEPT(stmt) do {stmt;} while(0)
#endif

コメントにもあるとおり、特定のアーキテクチャでは accept() は一斉に呼び出しても OK よ、その場合は SINGLE_LISTEN_UNSERIALIZED_ACCEPT を有効にしる! とのことです。Linux の場合ここの設定はどうなるか、configure マクロを覗いてみます。

case $host in
...
      ;;
  *-linux-*)
      case `uname -r` in
        2.0* )
            AP_SIG_GRACEFUL=WINCH
            ;;
        2.[2-9]* )

  echo "  forcing SINGLE_LISTEN_UNSERIALIZED_ACCEPT to \"1\""
  SINGLE_LISTEN_UNSERIALIZED_ACCEPT="1"

            ;;
        * )
            ;;
      esac
      ;;

Linux 2.2 以降では SINGLE... が有効になってました。先に述べたようにカーネル 2.2 でも新し目のものでは wake_up 関数の実装に改良が加えられているので 2.2 以降という指定なのでしょう、おそらく。また他の OS ではこの変数が有効にならないものも結構あります。OS によっては accept(2) を複数のプロセス/スレッドから呼ぶとエラーが返るものもあるそうで、その辺に一つ一つ対処しているのが分かります。

と、いうことで最初の実験から thundering herd 問題のありやなしや、Apache ではどうしてるのかなどをみていろんなことがつながってすっきりしました。めでたしめでたし。

もうちょっとだけ続きます。UNIXネットワークプログラミング〈Vol.1〉ネットワークAPI:ソケットとXTI には prefork の thundering herd を避けるための実装方法としてロックをかける以外に、ディスクリプタパッシングという手法を使ったものが紹介されています。ディスクリプタパッシングは ファイル記述子をUnixドメインソケット経由で渡す - bkブログ でも詳しく解説されているように、UNIXドメインソケットを使ってファイルディスクリプタを別のプロセスに転送する手法です。

子プロセスをそれぞれに accept() するのではなく、親で accept() してクライアントからの接続ソケットが取得できたら、そのファイルディスクリプタを prefork で待機していた子に渡してやって親はすぐにその接続ソケットを閉じる、というのもの。この方法ならそもそも accept() は親しか呼ばないので、thundering herd は起きようがありません。

なお、ディスクリプタパッシングではファイルディスクリプタを渡すと言っても数字そのままを渡すわけではありません。カーネル中のファイルテーブル内における、送信側プロセスが送信したディスクリプタに対応するエントリを参照する新しいディスクリプタを受信側のプロセスで作成(UNIXネットワークプログラミング 第2版 Vol.1 P.372)します。そのため親と子の通信は read(2)/write(2) や send(2)/recv(2) ではだめで、sendmsg(2)/recvmsg(2) の補助データ枠を使って送受信します。

と、いうことで本に載っているディスクリプタパッシングの prefork のコードを Perl に移植してみました。書籍のはウェブサーバーでシグナル周りの処理もちゃんと書かれてますが、ここでは必要最小限の部分だけを echo サーバーとして。

#!/usr/local/bin/perl
use strict;
use warnings;

package Child;
use base qw/Class::Accessor::Lvalue::Fast/;

__PACKAGE__->mk_accessors(qw/pid pipe status/);

package main;

use IO::Socket;
use IO::Select;
use Socket::MsgHdr;
use List::Util qw/first/;

my $listen = IO::Socket::INET->new(
    LocalPort => 9999,
    Listen    => SOMAXCONN,
    Reuse     => 1,
) or die $!;

my $select = IO::Select->new;
$select->add($listen);

my @pipes = IO::Socket->socketpair(AF_UNIX, SOCK_STREAM, PF_UNSPEC);
$select->add(@pipes);

my @children;

for (0..5) {
    if (my $pid = fork) {
        push @children, Child->new({
            pid    => $pid,
            pipe   => $pipes[0],
            status => 0,
        });
    } else {
        $listen->close;
        $pipes[0]->close;

        while (my $con_fd = $pipes[1]->recvfd) {
            my $con = IO::Socket->new_from_fd($con_fd, 'w') or die $!;
            while ($con->sysread(my $buffer, 1024)) {
               $con->syswrite($buffer);
            }

            ## signal to parent
            $pipes[1]->syswrite($con->fileno);
            $con->close;
        }
        exit;
    }
}

while (1) {
    for ($select->can_read) {
        if ($_ eq $listen) {
            my $con = $listen->accept;
            my $child = first { $_->status == 0 } @children;
            $child or die "no idle child";
            $child->status = 1; # busy
            $child->pipe->sendfd($con->fileno);
            $con->close;
        } else {
            for my $child (@children) {
                if ($_ eq $child->pipe) {
                    $child->pipe->sysread(my $discard, 32);
                    $child->status = 0;
                    last;
                }
            }
        }
    }
}

sub IO::Socket::sendfd {
    my ($socket, $fd) = @_;
    my $outmsg = Socket::MsgHdr->new(buflen => 8192, controllen => 256);
    $outmsg->cmsghdr(SOL_SOCKET, SCM_RIGHTS, pack("i", $fd));
    $socket->sendmsg($outmsg);
}

sub IO::Socket::recvfd {
    my $socket = shift;
    my $inhdr = Socket::MsgHdr->new(buflen => 8192, controllen => 256);
    $socket->recvmsg($inhdr, 0);
    unpack('i', ($inhdr->cmsghdr)[2]);
}

親と子の通信には双方向パイプを使います。また、親ではパイプと待機ソケットの I/O を同時に面倒をみる必要があるので select(2) = IO::Select を使ってそれらを多重化します。

• クライアントからの接続があると親は子一覧からアイドルなプロセスを一つ選び、UNIXドメインソケットのパイプ経由でディスクリプタをその子に転送します。
• このとき選ばれた子にはビジー状態のマークをつけておきます。
• ディスクリプタを受け取った子はそのソケットからの読み取りを開始し echo サーバーの仕事をします。
• クライアントの接続が切れると親に対してその旨をパイプで通知します。
• 親は select(2) でパイプを監視することで子が仕事を終えたことをイベントとして受け取り、子をアイドル状態に戻します。

なお Perl 組み込みの関数では sendmsg() / recvmsg() はサポートされていません。そこで Socket::MsgHdr という XS モジュールのお世話になります。このモジュールを use すると IO::Socket に sendmsg() / recvmsg() メソッドが追加されます。スクリプトの末尾ではこの二つのメソッドを使って、IO::Socket でディスクリプタを送受信する sendfd() / recvfd() というメソッドを追加してあります。

まとめ

prefork サーバーの thundering herd 問題を起点に深追いした内容をまとめてみました。

• prefork サーバーは複数の子が accept(2) を同時に呼び出すことでそれを実現する
• accept(2) をまとめて呼ぶと環境によっては thundering herd 問題が発生する
• ロックを使って accept(2) を順列化することでこの問題を避けることができる
• Linux では 2.2 系の古いカーネルとそれ以降のカーネルで wake_up 関数群の実装が異なり、新しいものでは事象を待ち合わせているプロセス群から一つのプロセスだけを起床させることができる
• Linux では accept(2) による thundering herd 問題は古いカーネルでのみ発生する
  • 故に Catalyst::Engine::HTTP::POE の実装でも最近の OS では問題ない
• Apache では accept_mutex_* 関数で accept(2) の順列化を行っている
  • また configure スクリプトで OS ごとの accpet(2) の実装差異を吸収している
• thundering herd を避けるにはディスクリプタパッシングも使える
• Perl で sendmsg(2) / recvmsg(2) するには Socket::MsgHdr などを使う

といったことが分かりました。

カーネル周りの書籍は Linuxカーネル2.6解読室 がオススメですが、UNIXネットワークプログラミングについてはやはり

UNIXネットワークプログラミング〈Vol.1〉ネットワークAPI:ソケットとXTI

が本命でしょう。実は最近までまったく開かれないまま家に積読になってましたが、ときどき調べごとをするとほとんどのことがこの本のどこかに詳しく載ってたりして改めて古典の重要さを痛感しています。