競プロ勢の皆さんもISUCONに参加して圧倒的成長しませんか?

2016年12月24日公開
この記事は Competitive Programming Advent Calendar 2016 の 24 日目の記事です。

競プロ勢の皆さんも ISUCON に参加して圧倒的成長しませんか?

ISUCON とは、Web アプリケーションを高速化するプログラミングコンテストです。 競技プログラミングはアルゴリズムを学ぶ上では最強の教材ですが、研究職以外では即戦力としては見られづらいという問題があります。 ISUCON には Web 業界で必要な基礎知識がつまっており、競技プログラミング勢がたくさん ISUCON に参加すれば、 競技プログラミング勢も Web 業界も躍進できるのではないかと思いこの記事を書きました。 また、競技プログラミング勢が入賞すれば、競技プログラミングの潜在的な価値が認められ競技プログラミングの認知度が上がることを期待しています。 Web 開発でボトルネックとなる場所は、知識で解決できるようなことは定番ソフトウェアであれば多くの場合すでに解決方法が提供されているため、 全探索してしまっているがインデックスを作れば高速化できるというような時間計算量が考慮されていないために起きることも多く、 競技プログラミングの経験が活かせると考えています。

はじめに

この記事では主に C++ を用いて ISUCON で勝つ方法について考えています。 日本の Web 業界では C++ を使う人が少ないため、ISUCON で参考実装として与えられていません。 しかし、競技プログラミングで広く使われていることからわかるように C++ は最速の言語です。 実際に Google は C++ を使って Web アプリケーションの開発を行っており、CPU のコストを抑えられています。 C++ も環境を整え慣れ親しめば、Web アプリケーション開発においても開発効率を落とさず効率的に高速化できることを示すため、 チーム Anago は C++ の独自サーバで ISUCON6 に参加し、無事決勝進出を果たしました C++ を自由自在に扱えることは競技プログラミング勢の強みでもあるので、この記事では ISUCON6 を通じて得られた経験をもとに、 参考実装で与えられていない言語で ISUCON に効率的に挑む方法を紹介します。

概要

C++ で Web アプリケーションをすべてを書き直すことができれば優勝間違いなしなのですが、残念ながら現実的ではありません。そこで C++ サーバは初期状態を参考実装の Web サーバのレスポンスをそのまま転送する設計にすることにより逐次的な開発を可能にします。逐次的な開発を行う方針としては大きく分けて以下のような方法があります。
  • フィルター形式 … Web アプリケーションで重い処理部分を特殊な文字列(例えば <!--hoge--> )に置き換えておき、C++ サーバで高速に処理してその部分を置換する手法です。参考実装言語の深い知識が不要という長所がありますが、ある程度大きな単位で書き換える必要があるという短所があります。ISUCON6 では主にこれを使いました。
  • コールバック形式 … Web アプリケーションから独自サーバを呼び出す手法です。関数単位での細かい逐次開発を行える長所がありますが、参考実装言語向けにコールバック処理を実装する必要がある短所やレイテンシーが大きくなりやすいという短所があります。
ブラウザ Web サーバ データベース
図 1: 典型的な Web サービスの構成
ブラウザ プロキシサーバ C++ サーバ Web サーバ データベース
図 2: ISUCON6 で用いた構成(赤は新たに追加された部分を示します)
図 1 は ISUCON で与えられる Web アプリケーションの典型的な構成、図 2 は ISUCON6 で用いた構成です。図 2 の構成ではプロキシサーバとして nginx を用いており C++ サーバで不足している機能が容易に補えます。例えば ISUCON6 決勝ではストリームを用いた問題が出題されましたが、C++ サーバでは未実装であったため、当該リクエストが来たときはプロキシサーバから直接 Web サーバにリクエストするように設定しました。また、静的ファイルをプロキシサーバで直接返すこともでき、C++ サーバで無駄にスレッドを消費するのも防げます。
C++ サーバでは Web サーバにリクエストする以外にもデータベースへのアクセスができるようにすると、レイテンシを大幅に減らすことができ気軽にデータへのアクセスができるようになります。また、起動時にデータベースの内容を予め読むようにしておくと、キャッシュを使いつつも永続性を保つことが容易になります。

戦略

ここでは ISUCON6 に C++ サーバで挑んだ経験から、次回以降も採用する戦略や次回から予定している戦略を紹介します。

Docker を用いてポータブルな環境を構築する

ISUCON では OS やソフトウェアのバージョンが事前に発表されることはなく、C++ サーバのセットアップに大きく時間が取られました。Docker を用いて Linux 環境上でさえあれば事前に用意したスクリプトを実行するだけで常に期待通りに動くような環境を構築する予定にしています。
Docker にはいくつかオーバーヘッドがあるため、オーバーヘッドを最小化するため以下の隔離機能を停止して使います。
  • ネットワークの分離の停止 … ネットワークの分離によって Docker プロセスが転送のため大きくCPUの消費するためホストネットワークを使用する設定にします。
  • 一部ファイルシステムのマウント … Docker が自動的に提供するファイルシステムは遅いため必要に応じてマウントします。例えば nginx は POST リクエストを受けたときにファイルを一時的に書き出しますが、この書き込み先が Docker 上のファイルシステムにあると遅くなる場合があります。
  • (任意)プロセスの分離の停止 … 一部の OS でネットワークの分離の停止を行うときにプロセスの分離も行わなければ、権限まわりでエラーを起こすことがあるため任意でプロセスの分離を停止します。
Docker がデフォルトで提供するイメージで apt 等のコマンドを実行するとレポジトリがアメリカにあるために時間がかかることがあります。国内のレポジトリを設定することをおすすめします。予め Docker イメージを作っておきダウンロードするだけにしておけばさらなる高速化が可能になるかもしれません。

GitHub と bazel を使ってチームで開発しやすい環境を作る

チームでの開発は GitHub を経由して行います。極力同じファイルを編集する必要がなくなるような方針(例えばリンクするだけでハンドラーが登録されるような設計)で開発すると、git 上でコンフリクトする頻度が減りマージする手間が省けます。競技プログラミングのコンテストでは多くの場合 1 つのファイルで完結するため不要ですが、複数のファイルに分けて書くためにはビルドツールが不可欠で、bazel がその他の有名なツール(例えば CMake 等)と比較して文法が非常に直感的で便利です。

Web でよく使われるライブラリを準備する

Web 用言語に遅れを取らないために以下のようなライブラリを使えるようにしておくと便利です。
  • HTTP 接続ライブラリ … 参照実装に HTTP 接続できるようにしておく必要があります。外部サービスを模したものが与えられ HTTP2 を話す可能性があるため、余裕があれば HTTP2 で接続できるようにしておくと良いかもしれません。
  • データベース系ライブラリ … MySQL への接続は必須です。Redis、PostgreSQL、MongoDB、memcached 等を用いた出題はあり得るので余裕があれば準備しておくのが吉かもしれません。
  • 文字列系ライブラリ … 文字列の処理が簡単にできれば開発に余裕ができます。正規表現はその他の方法で代替できるため必須ではありませんが、Web 開発では頻出ですので使えるようにしておくと良いかもしれません。
  • エンコード系ライブラリ … BASE64 エンコード、URL エンコード、JSON エンコード等は Web 開発において頻出です。
  • ハッシュ系ライブラリ … MD5、SHA1、SHA256等もよく用いられています。
  • 日付関数系ライブラリ … HTTP ヘッダーとして与えられるの日付や MySQL に保存されている日付を処理することがあります。

データベースのインデックスの張り方を学ぶ

データベースを完全に捨てることは難しいため、データベースの最低限のチューニングは必要となります。SQL サーバは結構賢く、インデックスを適切に設定しておけば適切に使われます。何でソートしておけば高速に読むことができるかを競技プログラミングで培った経験から判断できると思います。使われているクエリを確認し(コードを読む以外にもスロークエリログを確認したり、EXPLAIN するなどして確認するとより確実性が増します)、適切なインデックスを設定します。phpMyAdmin 等の GUI でデータベースを扱えるソフトウェアを準備しておくと便利です。

nginx でログ収集や静的ファイルの配信、リクエストの転送を行う

プロキシサーバとして nginx を使うので基本的な設定ができる必要があります。以下は転送の基本的な設定です。他にも転送の方法や HTTPS の解除方法は事前に調べておくと良いと思います。どのようなリクエストが飛んできているかを手早く確認したいので、nginx でログ収集をできるようにします。静的ファイルも nginx で返せるようにするとバックエンドの負担が減ります。nginx は起動時にコンパイル時に指定されたファイルを読もうとしてうまく起動しないことがあり、与えられたサーバイメージに含まれている nginx と競合してしまう可能性があるため、ソースコードからビルドし直すか Docker に閉じ込めると良いでしょう。
worker_processes auto;

events {
  worker_connections 8096;
  multi_accept on;
  use epoll;
}

http {
  sendfile on;
  tcp_nopush on;
  tcp_nodelay on;
  keepalive_timeout 15;

  upstream app {
    server 127.0.0.1:8000;
    keepalive 16;
  }

  server {
    listen 80;

    location / {
      proxy_pass http://app;
      proxy_redirect off;
      proxy_set_header X-Real-IP $remote_addr;
      proxy_buffering off;
      proxy_buffer_size 128k;
      proxy_buffers 100 128k;
      proxy_http_version 1.1;
      proxy_set_header Connection "";
    }
  }
}

init.d スクリプトを用いた自動起動の設定

ISUCON ではサーバプログラムを自動起動する設定をしなければなりません。systemd や supervisord で設定するのが今風ですが、練習で数年前のイメージを使ったりすると思うので CentOS や Ubuntu のある程度古いバージョンでも使えるようにするために init.d で起動を行います。

Linuxカーネルパラメータの設定

初期状態は Web サービス用にチューニングされていないため、ポートの枯渇等がよく起きます。おまじないだと思って以下を実行しても良いと思います。
cat <<'EOM' > /etc/sysctl.conf
net.core.netdev_max_backlog=32768
net.core.rmem_max = 16777216
net.core.somaxconn=32768
net.core.wmem_max = 16777216
net.ipv4.ip_local_port_range= 10000 65535
net.ipv4.tcp_fin_timeout=10
net.ipv4.tcp_max_syn_backlog=32768
net.ipv4.tcp_rmem = 4096 349520 16777216
net.ipv4.tcp_timestamps = 0
net.ipv4.tcp_tw_recycle=1
net.ipv4.tcp_tw_reuse=1
net.ipv4.tcp_wmem = 4096 65536 16777216
net.ipv4.tcp_rfc1337=1
net.ipv4.tcp_keepalive_probes=5
net.ipv4.tcp_slow_start_after_idle=0
net.core.somaxconn=65535
EOM
sysctl -p

その他

ISUCON は複数人で参加するためチーム内のコミュニケーションが非常に大切です。Slack や Google Docs を予め共有しておくと、問題の概要をまとめたり、コマンドを共有できたりして何かと便利です。コンテスト開始時にサーバの IP アドレスを予め /etc/hosts に書き込んでおきアドレスのやりとりをやりやすくするなど細かな工夫も限りあるコンテスト時間の中では効いてきますし、ベンチマークを実行するときに声掛けが必要になったりするので、コンテスト前にチーム練習をするのもおすすめです。

さいごに

C++ サーバを用いた環境テンプレートは ISUCON7 予選までに余裕をもって公開する予定です。競プロ勢の皆さんがの参加・入賞を楽しみにしています。