C10K問題の今と未来
唐突ですが、一回目の記事を書きます！
今回は、主にウェブサーバー、具体的にはLinuxのSO_REUSEPORT（プログラミング言語としてはC言語)の話題になります。背景として、弊社では、広告配信がいわゆるネイティブアプリケーションであるため、ウェブサーバーの開発を行っているといったことが挙げられます。そもそも今回の記事を書いたきっかけは、弊社でSO_REUSEPORTを使用し始めており、それについて紹介したいと考えたからです。
特にC10K問題については
TheC10kProblem - 「C10K問題」（クライアント1万台問題）とは、ハードウェアの性能上は問題がなくても、あまりにもクライアントの数が多くなるとサーバがパンクする問題のこと
が詳しいので今回は説明を省略します。 また、Linux（正確にはKernel 3.9以降）におけるSO_REUSEPORTについては、
或るプログラマの一生 » Linux Kernel 3.9 の SO_REUSEPORT
を一読されると概要はつかめるかと思います。ここでいうSO_REUSEPORTは、特に言及が無い限りLinuxのものをさしておりますので、BSD系におけるそれとは異なりますので予めご了承ください。
ウェブサーバーの作成
自社でHTTPを話すアプリケーションを作成する際に、やはり既存のウェブサーバーを参考にするのは非常に容易に思いつく手段です。 弊社では、nginxをリバースプロキシや簡単なソフトウェアバランサとして使用している実績があり、そのパフォーマンス（特にスケーラビリティ）が非常に良いことは実感しています。また、CPU(コア数）だけ設定すればチューニングは不要というようなプログラムを作りたいという希望もあったので、安直ではありますが、自然にepollを使用したevent-drivenなプログラムを作成していこうという方針になりました。 １プロセスあたり複数のリクエストを同時並行的に処理でき、また、ちょうど世の中には libevent のようなライブラリ（HTTPまで実装されている！）があるのも後押しになりました。
スケーラビリティの確保
C10K問題をクリアするというのはNginxという先駆者を参考にしているので当然の話ですが、一方で負荷分散のデザインがなかなか固まりませんでした。 ユーザーからのリクエストをバランシングする方法は実に様々ですが、スケーラビリティを確保するということを念頭に当初思いついた案は次のような物でした。
案１「とにかくみんなacceptする」
細かい点は置いておいて、まず素朴な案としてはとりあえずスレッド（プロセス）ごとに同じソケットを監視してしまえということが思い浮かびます。ロジックとしては以下のような感じです。
- socket() bind() listen()して１つだけソケットを作成
- スレッド（またはプロセス）を必要なだけ立ち上げる
- 各々で同じソケットを監視してリクエストを待つ
- リクエストが来たらacceptを試みる
図１. みんなacceptしに行くパターンの動作イメージ
上の通りこの案は、実際の動作は無視できるとはいえエラーがたくさん起きるため、人によっては気持ち悪いと感じるかもしれせん。実際acceptが１リクエストにたいして全スレッド（プロセス）分発生するのでオーバーヘッドもあります。逆に利点としてはロジック自体シンプルですし、実際プログラムもシンプルに書けるということがあります。ただし、シンプルといっても同じソケットである必要があるため、既存のシングルスレッドのプログラムを単純に複数立ち上げるだけではできません。
案２「リクエストをacceptするスレッドが一人」
次に思いつくのは、acceptは排他的なので一人だけでやってほかのワーカー（返事を作る人たち）にソケットを渡すという方式です。実はmemcachedがこれで実装されているみたいなのですが、簡単に図にするとこんな感じです。
- socket() bind() listen()して１つだけソケットを作成
- スレッド（またはプロセス）を必要なだけ立ち上げる
- 1スレッドだけ着信を待ち受ける。その他はpipeを待つ。
- リクエストが来たらacceptして、ソケットをpipe経由でほかのスレッドへ
図２. memcachedっぽい何か
案１と違って、動作上は非常にすっきりしたように見えます。しかしこの実装だと素朴な疑問として、accept担当のスレッドは暇なのかどうかや、ワーカーはコア数分立ち上げればいいのかacceptするスレッドを引いてコア数-1立ち上げるのかという議論もあり、当初の方針である「CPU(コア数）だけ設定すればチューニングは不要」から逸れてしまいます。
案３「平等 (みんなにacceptする機会を与える)」
案１と案２で作ってみたもののやはりぱっとしないので、nginxの実装を調べてみることにします。 すると以下のようにaccept()を各ワーカー間で持ち回りにしていることが分かります。
図３. ランダムにacceptするlockを一定期間保持する
起動後ワーカーが一斉にmutexを獲得しようとします。一定リクエストを処理したらmutexを解放することで、すべてのワーカーがリクエストを分散して処理できるようにしています。 先ほどの案２と違って、ワーカー数=CPU(コア)数で余計な心配がありません。また、ワークロードが不均一な場合には、重たい処理をしているほどmutexを獲得しにいく頻度が減りますので、結果的にうまいこと負荷分散もできているように見えます。 今まで出てきた案の中で一番良さそうかつ実績のあるこの方式ですが、やはりacceptをしに行くスレッドは瞬間的には一人ですので、性能的には案２と大差ないと考えられます。また、何よりも今まででてきた中で最も実装するものが多くなりそうです。
SO_REUSEPORTの台頭
上述の案をためしてみたのですが、（当たり前ですが）案１の「とにかくみんな取りにいく（acceptしにいく)」が非常に簡単かつ速くコードが書けてしまいます。 そして、３案を試しているうちにSO_REUSEPORTがマージされたLinux Kernel 3.9を知ることになります。
Linuxに追加されたSO_REUSEPORTは具体的に何がうれしいか、当該部分(__inet_lookup_listener内)を抜き出してくると
Before (Kernel 3.2)
sk_nulls_for_each_rcu(sk, node, &ilb->head) {
score = compute_score(sk, net, hnum, daddr, dif);
if (score > hiscore) {
result = sk;
hiscore = score;
}
}
SO_REUSEPORTが追加される前は、接続要求があった時にcompute_scoreで受信アドレスを指定しているか等優先度はあるものの、単純にlistenしているソケットを探しているため、このままでは常に同じソケットが選ばれます。
しかしSO_REUSEPORTが追加された3.9以降では以下のように
After (Kernel 3.16)
sk_nulls_for_each_rcu(sk, node, &ilb->head) {
score = compute_score(sk, net, hnum, daddr, dif);
if (score > hiscore) {
result = sk;
hiscore = score;
reuseport = sk->sk_reuseport;
if (reuseport) {
phash = inet_ehashfn(net, daddr, hnum, saddr, sport);
matches = 1;
}
} else if (score == hiscore && reuseport) {
matches++;
if (((u64)phash * matches) >> 32 == 0)
result = sk;
phash = next_pseudo_random32(phash);
}
}
接続要求があった時にlistenしているソケットをラウンドロビンで選んでいることが分かります。 これを採用すると、はじめの素朴な案1並みにシンプルなプログラムが書けます。
図4. SO_REUSEPORTを利用したときの動作イメージ
また、既存のプログラムを活用するという意味では、SO_REUSEPORTをセットして複数立ち上げるだけで簡単なロードバランシングができてしまいます。
今回の記事は以上になります。 普段の仕事で使っているものの感想も幾分混じっている記事で、イマイチだったかもしれませんが、感想やご指摘いただけますと今後の参考にさせて頂きたいと思います。
それでは、また次回をご期待ください。
