ISUCON4 予選参考解答(オンメモリ版)

2014年10月20日 12:13

レポート

参加者の皆さん、 ISUCON4 予選、お疲れ様でした。
ISUCON4 運営チームの @rosylilly です。
すでに予選問題の解説記事もあがっていますが、この記事では、ベンチマーカー実装者が予選参加者となるべく同じ状況で、出来る限り高得点を出すことを重点に置いたピーキーな解答例について解説します。
※ 別解となる、この記事ほどピーキーではない @sorah による解答記事はこちらです。

また、実装されたソースコードは GitHub にて公開しています。

前提

実装時間は皆さんとおなじ8時間程度を想定しています
この実装はすべて僕一人で行います
- 架空の想定として、運営チーム(@mirakui, @sorah, @rosylilly)で予選に参加している状況としています
- @mirakui と @sorah がまったく別の実装を行っている設定です(去年の予選と同じ状況)
僕は出題者であり、ベンチマーカー実装者
- 問題を把握する時間などはほぼスキップできる
- すでにどういう解法にするかある程度検討がついている

手始めに(2分)

僕の手元で EC2 インスタンスを立ち上げて真っ先にやることは

sudo service nginx stop
sudo service mysqld stop
sudo chkconfig nginx off
sudo chkconfig mysqld off

で Nginx と MySQL を停止させます。

Nginx 及び MySQL を停止させるのは、この2つに一切依存しない実装をする、と最初から決めているためです。この2つはおそらく並行作業中の @mirakui と @sorah が触っているはずなので、僕の時間内にうまくいくかどうかわからないギャンブル実装に合わせていれた変更による手戻りや、設定のコンフリクトなど、想定されうる諸問題を最初から発生させないように、僕の実装からは完全に除外するためにサービスの停止を行います。

実装方針

まずは、実装方針を固めます。実装方針はおおまかに3点。以下のように定めました。

他のミドルウェアに依存しない
- Redis であれ、 Memcached であれ、2人が使っていそうなので依存しません
- これはベンチマーク対象をスイッチした時に事故を起こさないための措置です
  - 最終的な AMI 作成時に事故を起こすと失格になってしまいかねません
Go 言語で実装するが、参考実装のフォークは行わず、フルスクラッチで書く
- Martini が入っていて便利そうなのはいいのですが、最終的にどこがボトルネックになるのかわからない以上、型による制約が多く、人の手の入った状況から書き換え難い Go ではベース実装が足かせになると踏んでの判断です

ISUCON4 予選参考解答(Redis版)

2014年10月20日 12:00

レポート

ISUCON4 予選お疲れさまでした! 予選問題の Ruby 初期実装などを担当した @sora_h です。

予選はたのしんでいただけましたでしょうか? 本記事では、ざっくりとそこそこのスコアを出す解き方を紹介しようと思います。
※@rosylillyによる、高得点を出すことを重点に置いたピーキーな解答例はこちらです

前提

一人でやる
一応8時間経過時点でスコアをとる
- ただし出題者であるので問題の把握などの時間は短縮されていることに注意。
Ruby の実装を利用する
ある程度、現実味のあるチューニングが主
- ベンチマーカーの実装を利用したりしない

また、この記事で出来た実装は GitHub に掲載しています: https://github.com/sorah/isucon4-qualifier-sorah

初期スコア

とりあえず立ち上げて動かした時のスコアは success:6030 fail:0 score:1303 でした (workload=1)

チューニング

ここからチューニングしていきます。

失敗数のカウンタを Redis にのせかえる (2 時間経過)

問題を読むとログを残す必要は一切ない事がわかるので、とりあえず mysql でログを取るのをとめて、Redis をカウンターとして利用するように変更します。

ただし、MySQL でも適切な index を張ればスコアが出せます。この辺は好みだと思われます。

isu4:user:<id>, isu4:ip:<ip> をカウンタとして連続失敗数を記録 (INCR)
isu4:last:<id>, isu4:nextlast:<id> を最終ログイン記録に利用

スコアはこの時点で "success:29430 fail:0 score:6357" (workload=1)

これはあまりスコアに影響はなかったのですが、少し後で users テーブルも redis にのせることにより、
完全に mysql をとりのぞいています。

nginx で静的ファイルを配り、app process との接続を UNIX ドメインソケットに

commit 4d3d6fd12ad97b6b39b5d732aef4c5316e2be3d5

ISUCON4 予選問題の解説と講評＆ AMIの公開

2014年10月14日 10:28

レポート

こんにちは、ISUCON4 運営チームの @mirakui です。 @rosylilly @sora_h とともに ISUCON4 の問題作成と運営を担当しています。

さて、予選に参加していただけたみなさんは楽しんでいただけたでしょうか。今回は、予選問題の振り返りをしたいと思います。

予選問題「いすこん銀行」

今回の予選問題は、「いすこん銀行」という架空の銀行の Web サービスがテーマでした。

銀行とはいっても、実は銀行としての機能は一切ないハリボテで、今回用意したのは ログイン機能 のみです。ログインって機能なの？と思うかもしれませんが、実際のウェブサービスを作る上で、ログイン部分の設計は単純では済みません。

それは、近年増加している「パスワードリスト攻撃」のような、不正ログインの対策を行わなければならないからです。

「いすこん銀行」には、ログイン画面と、ログインに成功した時に表示されるマイページの2画面しかありません。
ログイン画面でユーザ名とパスワードを入力し、ログインに成功するとマイページに遷移することができますが、失敗した場合、エラーメッセージを表示してログイン画面に戻ります。

このとき「いすこん銀行」は次のような条件で不正なログインとみなし、それ以降はログイン禁止にします。

一つのユーザIDに対して試みたログインで、連続3回以上パスワードを間違えた場合、それ以降そのユーザIDはログイン不可能になる

同一IPアドレスから試みたログインで、連続で合計10回以上パスワードを間違えた場合、それ以降そのIPアドレスからはログイン不可能になる

今回の予選問題は、とにかくシンプルな問題にすることを意識して設計されました。最初は、銀行アプリケーションなので暗証番号表を用意しようとか、他アカウントへの振込み機能を作ろうとか言っていたのですが、~~工数の都合~~シンプルさを重視して、最終的にログイン機能のみを残しました。

ISUCON4 オンライン予選の利用言語比率

2014年09月30日 16:12

レポート

櫛井です。
昨年に続き、オンライン予選の利用言語比率を公開します。

オンライン予選は185組の参加でしたが、利用した言語はAMI提出時に記入してもらっているため、AMI未提出・スコア登録無しのチームを除いた149チームでの数値となります。

オンライン予選利用言語比率

利用率の全体ランキングは以下の通りです。利用言語は自由記入でしたが複数を入力したチームはありませんでした。

ruby　　 27.5% 41組
perl 　　18.7% 28組
php 　　16.1% 24組
go 　　16.1% 24組
python　 7.3% 11組
node.js 　7.3% 11組
c++ 　　 0.6% 1組
scala 　　0.6% 1組
未回答　 5.3% 8組

ご参加いただいた皆さんの感想などはこちらにまとめています。
ISUCON4 オンライン予選関連エントリまとめ : ISUCON公式Blog

ISUCON4 オンライン予選関連エントリまとめ

2014年09月28日 18:30

レポート

2014.10.21 13:00 更新
登録エントリ数 85件

--
櫛井です。

オンライン予選にご参加いただいた皆さん、ありがとうございました！
こちらでは感想エントリや何をしたかに言及されたエントリをまとめていきます。見つけた順です。もしここに載っていないものがある場合は ISUCON4 オンライン予選のブログ書いたよ！フォームで教えていただけると助かります。重複はこちらでチェックしますのでドシドシお願いします。

予選のTweetはこちらでまとめています
ISUCON4 オンライン予選 Tweet まとめ#isucon - Togetterまとめ

参加者
・ISUCON4 予選に出てきた - あおみかんのブログ