最近は YouTubeチャンネル や Fantiaファンクラブ を始めたりしてみてます。 昨日 (2022-07-23) はISUCON12のオンライン予選でした。
今回もいつも通りのメンバー (@__math, @misodengaku, @chibiegg) で チームTakedashi として参加しました。
分担は明確には決めてないもののいつもの感じで以下の通り。
・chibiegg (私) インフラ/デプロイ/プルリク管理/データ整備/コーディング
・__math (まーす先生) コードリーディング/修正方針の検討/コーディング
・misodengaku (みそでん) コードリーディング/ミドルウェアチューニング/コーディング
今回の予選問題は、 マルチテナントSaaS型 ISUCON 「ISUPORTS」 (eSportsではない) のリーダーボード (スコア表示画面) でした。
この時点までの得点推移はこんな感じでした。
再起動後の 17時22分 に 52957点(ベストスコア) を出したので作業完了としました。
先にまとめを書くと、今回は地道な下準備を5時間ぐらいやったおかげで最後の方にわかりやすく効果的な対策を入れることができたことが勝因だと思います。
5時間もデータクレンジングやプロファイリング、DBの載せ替えなんかやってスコアが全く上がらないと不安になりがちですが、その先の修正の見通しを信じて落ち着いて作業したのがよかったですね。
あと、いつものことですが3人の作業分担が完璧なのも重要です。
ここからは主にどんなことをしたか時系列で紹介しようと思います。
10:00 コンテスト開始
私がすぐに CloudFormation サーバでサーバを作成。
作成が完了したらSSHログインし、ホームディレクトリとnginxの設定をgit管理下に置く。
.gitignore を作成し、初期データなど重いデータや一時ディレクトリなどを除外するのが重要。
3台のサーバで設定を変えることを想定して、docker-compose-go.ymlやnginxの設定はホスト毎に別になるように調整。
アプリケーションサーバとデータベースサーバはいつも分けることにしているので、01をアプリケーションサーバ、03をDBサーバとしてつかうようにする。
この間他の2人にはドキュメントをよく読んでもらう。コードをgitにコミットした時点でみそでんがpprofを入れていた。
この時点で 10:33 ぐらい (コミット b077bcd 時点)
10:53 visit_history に INDEX を入れる
admin DB の visit_history テーブルにいい感じのINDEXがなかったので入れる。(コミット 74c0d70)
INDEX `tenant_id_competition_id_idx` (`tenant_id`, `competition_id`)みそでんがNginxのログをltsvにしたり、alpで集計するための準備をしてた。 (コミット d5ce51b 時点)
11:53 competitionScoreHandler (CSVアップロード) において、必要なデータのみをINSERTする
これまでの間にまーす先生がコードを読んでどこが重いかどうやって直すかを検討してくれているので着手する。
player_scoreテーブルには全てのスコアが記録される構造になっているが、実際に利用されるのは各プレイヤーの最新情報だけであることがわかっていたので、CSVの全件をINSERTせずに最新の情報のみをINSERTするようにした。(PR #1 必要なものだけINSERT)
12:10 competitionScoreHandler においてバルクINSERT
上記修正の直後に、1件INSERTからバルクインサートにした。 (PR #2 player_scoreをBulkInsert )
最後の方で修正するが、0件の時には実行しないようにしないとsqlxがエラーを吐くので注意。
13:38 visit_history の重複排除
visit_historyテーブルにはPlayerのアクセスログが残っているが、こちらも全てのレコードは利用されない。
UNIQUE INDEX を作成し、いらない場合はレコードが作成されないようにした。
PR #4 distinct visit history
13:49 テナントDBを一つにする
この作業が最も重かった。オリジナルの実装ではテナント毎にSQLite3のDBファイルが作成されるようになっている。我々はテナントのDBもMySQLにしたかったし、複数のテナントの情報を一つのテーブルに入れたかった。
みそでんにpprofを見てもらってもSQLiteの処理が大半でSQLiteを剥がしたい気持ちでいっぱいに。
そこで、MySQLに変更する前段階として SQLIte3 のDBを一つにする作業に着手する。
私が初期データのファイルを一つにマージする作業、まーす先生がそれに合わせて実装を変更する作業をすることにした。
最初は愚直にSQLIte3の初期データを全てSQL文に変換し、一つにしたSQLIte3データを作成しようとしたが件数が多すぎて全然作業が進まない。そこで、先に各データベースの中身をスリム化することにして、以下のようなSQLを発行した。これによって初期DBのサイズを300MBぐらいから10MBぐらいまで削減でき、簡単に扱えるようになった。
これは先にやった対策の通り、player_score は competition, player 毎に最新の情報しか使っていないため古いレコードを削除する処理である。
CREATE TABLE player_score_new (
id VARCHAR(255) NOT NULL PRIMARY KEY,
tenant_id BIGINT NOT NULL,
player_id VARCHAR(255) NOT NULL,
competition_id VARCHAR(255) NOT NULL,
score BIGINT NOT NULL,
row_num BIGINT NOT NULL,
created_at BIGINT NOT NULL,
updated_at BIGINT NOT NULL
);
INSERT INTO player_score_new
SELECT
a.id, a.tenant_id, a.player_id, a.competition_id, a.score, a.row_num, a.created_at, a.updated_at
FROM
player_score as a
INNER JOIN (SELECT
b.tenant_id, b.player_id, b.competition_id,
MAX(b.row_num) AS row_num
FROM
player_score as b
GROUP BY
b.tenant_id, b.player_id, b.competition_id) AS t
ON a.tenant_id = t.tenant_id AND a.player_id = t.player_id AND a.competition_id = t.competition_id
AND a.row_num = t.row_num;
DROP TABLE player_score;
ALTER TABLE player_score_new RENAME TO player_score;
VACUUME;
PR #3 merged tenants
14:03 テナントDBをMySQLに置き換える
上の作業によってテナントのDBが一つに統合されたので、MySQLへの移行は簡単だった。
MySQLにINDEX付きでいい感じにテーブルを作成し、マージしたDBを作成する時に使ったSQLをそのまま流し込んだ。
ここで重要だと思っているのは、Adminデータベースとテナントデータベースを別のサーバに設置したことだと思っている。
03をAdminデータベース、02をテナントデータベースにすることで負荷を分散するようにした。
この辺りでCPU利用率が アプリケーションサーバ(01) 100%ぐらい、テナントDB (02) 200%ぐらい、Admin DB (03) 150%ぐらい、だったので分けたのは多分正解だと思う。
この時点では実は全然スコアは上がっていない。ここまでの下準備があればこの先スコアが上がることがわかっているので地道に作業をしている感じ。
PR #5 tenant mysql
14:42 competitionRankingHandler の改善
まーす先生が competitionRankingHandler の改善をしていた。
player_score に最新のデータのみが入ることなったので、順位を出すのが簡単になった。
PR #6 optimize competition-ranking-handler, #8 removed distinct check, #10 optimize ranking
14:58 トランザクションの採用
予選後のLiveの講評でfujiwaraさんがおっしゃっていた通り、なぜかこの開発者はトランザクションを知らないことになっており、ファイルロックが利用されている。
これは遅いので適当にトランザクションを使うように実装を修正した。
この時の修正は雑すぎて、トランザクションが不要なSELECTでもトランザクションを発行してるのはご愛嬌。
この時点で4万点を突破。
実はSQLiteの時点で、ロックを削除しただけのコード (データ整合性がないのでエラーが出るが) で2万点ぐらい出ることもあることがわかっていたが、MySQLにすでに載せ替えていたおかげでスコアが高かったと思う。
PR #9 トランザクション
15:25 playerHandle の N+1問題解決
この前後でみそでんにN+1問題の解決をしてもらっていた。
PR #11 playerHandler N+1
16:10 competitionsAddHandler で 429 Retry-After を返す
この辺りでまーす先生がこの仕様を思い出す。
ISUCONではよくあるが、負荷が上がりすぎてスコアが下がる問題を対策するために一部のエンドポイントで429を返すことが許可されていたりする。
今回はコンテストを開催するAPIで429とRetry-Afterを返すことでPlayerの参加を抑制することができた。
テナントDBに負荷がかかりすぎていたのでこれを実施、雑に10%ぐらい捨てる実装でスコアが高かったのでそうしておいた。
PR #13 competitionsAddHandler で 429
16:58 player と player_score でオンメモリキャッシュを利用する
重すぎる金額計算など本来やるべきことは見えていたが、この時点で十分スコアが高く大掛かりなことをやる気持ちは無くなっていた。
Zoomで通話をしていたが「スコア上げたい気持ちはあるけど、守りに入るのが正解よね」的なまーす先生の発言にみんなで同意 (笑)。
安全で簡単な作業として player と player_score をメモリにキャッシュすることにした。
PR #15 キャッシュ, #16 Playerのキャッシュ, #17 use cache on ranking
17:01 visit_history への INSERT を非同期実行に
ログのINSERTは非同期でいいじゃんと言うことでまーす先生がGoルーチンに。
PR #18 async visit_history
17:20頃 再起動試験
ここまでの間にみそでんがMySQLの設定をいじったりしてくれているので動作確認。
色々なログの出力を抑制をするような設定変更を施し、systemdの設定を見直し。
問題がなさそうなのでサーバを3台とも再起動。
再起動後にベンチマークをとった結果が最もベストで 52957点 を記録。
ミスをすると怖いのでこの時点で作業を終了、サーバからログアウトしコンテスト終了を待つ。 ]]>
(書きかけ)
これまで予選3回、本戦3回と参加させていただいているISUCONですが、今回のISUCON8でようやくランクインすることができました。
うまくやれば優勝できていたと思われるだけに悔しいーー！
まだまだ精進しないと…という感じです。
感想はともかく、何をしたか、何をしていれば優勝できたか、他に何をやることがあったかまとめておきたいと思います。
メンバーはいつもの3人、 @__math @misodengaku @chibiegg。
SECCONで一緒に出てる @aki33524 は前回と同様釣りに出かけていました。
明確に決めてるわけではないのですが、役割分担としては以下のような感じです。
- @__math (まーす先生) アルゴリズム、コーディング
- @misodengaku (みそでん) データベース、エスパー
- @chibiegg 取りまとめ、インフラ、お茶汲み係、雑用
時系列順に
まずは時系列にやったこととその効果をスコアで振り返りたいと思います。
競技中はソースコード、設定ファイル全てをGitHubで管理しています。
ブランチ毎に作業をして、切り替えながらベンチマークを実行し、バグ無く実装できたものをmasterにマージする方法でやっていました。
そのため、スコアのグラフはところどころ複数の機能実装を交互にテストしているため、実装と効果の関係を誤って記載しているかもしれない点についてはご了承ください。
事前準備 (こたまご)
GitHubにプライベートリポジトリを作成し、二人を招待しておく。
SlackのチャンネルにGitHub連携を設定しておく。
10:00 開始直後 (こたまご)
2人にマニュアルとソースコードを見てもらっている間に作業効率化のための準備をしました。
簡単なAnsibleのplaybookを書いて、基本的な設定を行います。
Ansibleでやる必要もないのですが、やっておくとあとで一括作業が必要になった時に慌てずにできるので良いです。が、今回はあんまり使いませんでした。
- SSH公開鍵の登録 (authorized_keys)
- わかりやすいホスト名の設定
- sudoをパスワードなしで実行できるように
それから、初期実装や設定ファイルとうのディレクトリ (/home/isucon/isucon2018-final) にあるファイルをリポジトリに登録します。
Nginxのアクセスログをalpで解析できるようにLTSVフォーマットでファイルに出力するように設定。
とりあえず、この状態で初期スコアをベンチマークで測定しました。
この時点で把握した状況は以下の通り。
- ネットワークの帯域は余裕、ピークで数Mbpsいくぐらい
- アプリケーションとMySQLがCPUを食い合ってる
- 静的ファイルへのアクセスは多く無い
- 全体の応答時間のうち、 /info /orders へのリクエストが支配的
- スコアは500点強
11:00 DBとアプリケーションサーバを分離 (みそでん、こたまご)
MySQLとアプリケーションがCPUを食い合ってるのはよくないので分離。
サーバ01をアプリケーションに、サーバ02をMySQLに使うようにしました。
全サーバで共通のdocker-compose.ymlが利用されていましたが、これでは各サーバで動かすコンテナを変更できないので、サフィックスをつけて管理することに。
みそでんにスロークエリのログを吐いてもらうように設定して、再度ベンチマークでスコア測定。
- スコアは800強
- 2つ遅いクエリが見つかる
- SELECT * FROM trade ORDER BY id DESC
- SELECT m.t, a.price, b.price, m.h, m.l FROM (SELECT … FROM trade WHERE … GROUP BY t) m JOIN …..
11:20 明らかに遅くて不要なSQLを修正 (まーす先生)
スロークエリを出すまでも無く、遅いクエリのうちの一つが、コードを見るとLIMIT 1で良いことにまーす先生がぱっと見で気づく。LIMIT 1を適用してベンチマーク。
- スコアが10倍近い5000点強に
この時点で何チームか4000点から5000点代になっており、同様の対応をしたと想定されます。
11:50頃 /info の高速化のための下準備 (まーす先生)
まーす先生が /info を高速化すべく、いくつかのプルリクエストに分けて動作確認しつつ改修を進める。
add sec,min,hou #7
add indexes #9
ロウソク足の計算がしやすいように、tradeテーブルに秒まで、分まで、時までのカラムを追加し、インデックスを張った。
カラムを追加したのみで、利用はしていないためスコアへの影響はなし。
12:00頃 ロードバランスできるように準備 (こたまご)
データベースを使い続ける方針にしたので、使っていない残り2台もアプリケーションサーバとして利用できるように設定。
この時点でサーバ01でNginx+App、サーバ02でMySQL、サーバ03と04でApp、という構成に。
ただし、Initializeが全台に対して行われるための仕組みを作っていなかったので、いつでもロードバランスできる状態にはしておきつつ、一旦サーバ01だけで処理するようにしておきました。
また、あんまり効果はないと思われたが、精神衛生上、静的ファイルはできるだけNginxから応答されるように設定しました。
案の定スコアへの影響はなし。
13:20頃 isuloggerへの送信にバルクリクエストを採用 (こたまご)
isuloggerへのログ送信は秒間リクエスト数に制限がありました。
仕様書を見ると、バルクリクエストがあったためこちらを利用することにしました。
- ログの発生時は実際には送信せずchanに突っ込む
- バックグラウンドでchanからログを収集
- 定期的にまとめて送信
という挙動を実装しました。
実装とついでに吐いたログからわかったことは以下の通りです。
- スコアが1000程上がって、6000弱になった
- 今の所秒間リクエスト数を超えるようなログは発生していない
ログの送信がバックグラウンド処理になった影響で少しだけスコアが上昇します。
この時点では秒間リクエスト数の制限にかかるほどではなかったのであまり大きな効果になっていませんが、この実装をしておかないとこの後詰まることになります。
14:00頃 ロードバランスできるように初期化機能を実装 (まーす先生、こたまご)
初期化を全ノードに実行できる準備 #11
ロードバランスを再度有効化 #12
ベンチマーカーは実行開始前に一度だけ /initialize を実行します。
ロードバランスするとこの初期化リクエストは1つのアプリケーションプロセスにのみ届きます。
その時点で、全てのアプリケーションプロセスを初期化する必要があるため、内部APIを用意し (/internalInitialize) 全てのサーバの初期化を行うように実装しました。
また、設定をsettingテーブルから都度参照するようになっていたのをやめ、グローバル変数に持つように改修することでDBへのアクセスを減らしています。
ちゃんと動作はするようになったものの、数百程度のスコア上昇しかおきませんでした。
14:10頃 不要な行ロックを削除 (まーす先生)
コード上に怪しい SELECT * FROM user WHERE … FOR UPDATE があったので、不要じゃないかとFOR UPDATEを削除。
この時点ではスコアに大きな影響はなかったが、残していた場合この後で困っていたと思われる。
14:30頃 SNSでの拡散を開始 (こたまご)
みそでんがSNSシェアを有効にするフラグがあると発言。(さすがエスパー担当)
それを聞いた私が、もしかしてtrueにするとアクセスが増えるようにベンチマークができているのではと気づく。
ドキュメントを読み返すと同様の趣旨が書いてあった。(読んだけどなんのことかわからずその時はスルーしてしまっていたと思われる)
あまりにもtrueを返しすぎると、ユーザー増加に耐えられずタイムアウトが増えてしまうので、とりあえず1/8の確率でtrueを返すようにする。
- スコアが1万点を超える
- リクエストが増えたことでボトルネックがわかりやすくなった
このあたりで1万5000点の特別賞をチームNaruseJunが獲得。
このフラグに気づくのがあと10分早かったらーーと悔やまれます(笑)。
15:20頃 /infoのローソク足をキャッシュ (まーす先生、こたまご)
雑な /info キャッシュ #15
雑じゃないロウソク足のキャッシュ #16
- ローソク足は、直近のものは変化するが過去のものは変化しない
- ローソク足は、秒単位で更新されれば良い
という性質もと、私が雑にレスポンス丸ごとメモリにキャッシュする実装、まーす先生が丁寧にロウソク足をメモリにキャッシュする方法をそれぞれ実装しました。
私の雑なキャッシュでも特に問題はなく、一気に25000点弱に。
まーす先生の丁寧なキャッシュもバグ無く動作したため、両方をマージしました。
丁寧にロックまでしてキャッシュを管理していたものの、ロックをしない私の雑キャッシュでも問題なく動作したためロックを削除した結果、28000点ぐらいまで上昇しました。
15:50頃 約定条件のチェックが不要だった (まーす先生)
前々から処理が冗長だと気づいていた RunTrade 関数にメスを入れ始める。
初期実装では、注文があるたびにRunTrade関数を利用して約定可能なものを全て約定してから応答を返していた。
その際に、RunTrade関数を呼ぶ前に約定する可能性があるかどうかを確認するロジックがあったが、このロジックが重く不要だったため、小手始めにごっそり削除。
少しスコアが上がり、3万点弱に。
16:10頃 ユーザーの情報をメモリにキャッシュ (こたまご)
settingテーブルと同様、リクエストの度にデータベースを参照しにいくようになっていたユーザー情報をメモリにキャッシュするように修正。
ついでに吐きすぎていた不要なログを削除。
ついに3万点を超える。
16:50頃 RunTrade (約定処理) をシリアルにバックグラウンドで実行するように (まーす先生)
上記の通り、注文処理が来る度に実行されていた約定処理を、約定処理要求だけフラグにもち、実際の約定処理はバックグラウンドでシリアルに実行されるように修正。
これによりスコアが37000程度に上昇。
17:30頃 /info 内の注文価格情報をキャッシュ (まーす先生)
ache lowest/highest value (GET /info Only) #22
もっとも安い売り注文と、もっとも高い売り注文の価格の計算を求めるSQLが重く、キャッシュすることに。
これにより5万点を超える。競技中4万点を超えたチームはtakedashiだけだった。
17:30頃 再起動試験や最後の調整を行う (こたまご、みそでん)
データベースやアプリケーションがサーバ再起動時にちゃんと上がって来るように設定されているかみそでんにチェックしてもらいました。
並行して再起動試験を行い、どの程度スコアが下がるか調査。
この時点でサーバ自体を再起動する勇気がなかったのがこの後の敗因の一つとなります。
また、Nginxのアクセスログや、スロークエリを出さないように設定したことで競技中最高得点の51,834点を記録。
時系列外 (みそでん)
みそでんにはデータベース周りの細かいチューニングを行ってもらっていました。
今回はDBのダンプファイルが提供されていなかったためバックアップを取っておいてもらったり、コネクション数を調整してもらったり、バッファサイズを調整してもらったり…
試行錯誤が必要なので、githubのコミットには細かくは残っていません…
最終計測
48000点ほどのリクエストを捌いたものの、33件のリクエストを落としてしまった (400エラーを返していた) ため、減点により31939点に。
ステータスコードが400なのがちょっときになるが、OS起動後でデータベースのファイルがOSのページキャッシュに載っておらず十分なおパフォーマンスが出せなかったことが原因と思われます。
また、SNSシェア率を100%にしてたため、パフォーマンスが追いつかなくなった時にエラーが頻発してしまう問題も抱えていました。
ほんとはやるべきだったこと、まだまだあるやるべきこと
この先も書こうと思っていますが、明日はU-22プログラミング・コンテストの審査会のため続きは明日終わってから書きます。
おやすみなさい…
さくらインターネット Advent Calendar 2015 24日目
こんばんは！さくらインターネットのこたまごです。
本日は、毎年のクリスマスイブ恒例「さくらの聖夜」でした。
詳しい内容は後日、オウンドメディアのさくらのナレッジに掲載されると思いますので、写真を交えて速報をお届けしますっ♪
事前打ち合わせ
ちゃっかり撮られてた
「お宝写真大放出！さくら創業20年の歴史を振り返る」
創業20年に突入する節目に、社長の田中と研究所所長の鷲北が、写真で創業からを振り返りました。
社長と所長
ユーザの皆様
「14年ぶりに復帰した理由、今後の構想～インフラ側から支えるIoT～」
後半は、創業メンバで、フェローの小笠原と、Cerevoの岩佐社長による、IoT Platformの発表でした。
なぜ小笠原がさくらインターネットに帰ってきたか、これから何をやるのかについて語るという内容だったのですが、勢い余ってさくらのIoT Platformを発表してしまいました。
具体的にはさくらが3G/LTEの通信モジュールを提供する、さくらのクローズドなネットワークに接続されており、センサの値をさくらのプラットフォーム上に記録したり、モジュールに対してデータを送信したりすることができる、という内容です。
送信するところから、貯めるところまでをハードウエア込みで一貫して提供することによって、IoTへの敷居をぐっと下げることが目的です。
モジュール構成
システム構成
ユーザーイベントだと思っていたのに、びっくりされた方もいらっしゃったかと思います笑
締め
ということで、お越しくださった皆様、ネット中継でご覧くださった皆様、本日はありがとうございました！
変わり続けるさくらインターネットを来年もどうぞよろしくおねがいします♪
最後の最後に、社長の田中も想定価格などを話始めるので、プレッシャーを感じている図。
実はこの土日にはISUCON5と同時にTrendMicro CTFのオンライン予選もやっていました。
こちらにもチーム竹田氏の以下の四人でメンバー登録して参加していました。
が、きひろちゃん以外はISUCONの方で体力をもっていかれていてあまり参加できなかったのが申し訳なかったです…きひろちゃんごめん…
わたしは、3問着手して、2問だけ答え出しました。
Click on the Different Color
ブラウザでアクセスすると、箱が幾つが含まれる画像が表示される。一箇所だけ違う色のがあるのでクリックすると次に進む。というページでした。最近SNSでも見かけたやつですね。
手でやっていては埒があかないので、Pythonで自動化していくと、最後にフラグが返ってきました。
下の動画を見るとおもしろいですが、最後の方は小さくて到底人間にはクリックできません笑
なので、答えは TMCTF{U must have R0807 3Y3s!} (You must have robot eyes!) でした！
Captcha
こちらはログインするとCaptchaが出てきて、連続で500回正解すると良い感じ。こちらも手でやっていては埒があかないので、Pythonで自動化しました。
画像からノイズを除去して、二値化。それからtesseract-ocrで文字列にして、簡単なチェックに通った場合のみ送信することで自動化できました。
ところが、大文字小文字や、数字の0とアルファベットのOを誤認識するなど、一部の文字を含む場合にはスキップするようにすると全然すすまなくて、学習させないとだめかなぁと思った時に、これはもしや、と、画像ファイルにアクセスしないようにして同じ答えを投げ続けるとどんどん点数が上がるじゃないですか！
ということで、脆弱性のあるCaptchaでした。というオチです。TMCTF{217dae3fd34cee799658d4552e37827f}
つまり、今年のSECCON決勝戦のこれといっしょですね！
OCRじゃなくて人間が学習するべきでした…
CAPTCHA ノイズ除去
Calculate it
TCPで接続すると、次から次に四則演算の問題が出題される感じ。Pythonから接続してevalしたらOK。
だと思ってたのですが、途中からローマ数字や、英語表記とか出てきて眠気に負けて断念。
ローマ数字はネットで変換プログラムを見つけてきて対応したのですが、英語表記は次のようなのもでてきてパースが大変そうだったのであきらめました。
7 * 10 – 30 1 THOUSAND 2 HUNDRED 30 4 + 50 – 3 * 7 HUNDRED 20 5
これは後できひろちゃんが解きました。
まとめ
本当は9月に行われる予定だったのですが、問題サーバから問題が漏れた？ようで、一ヶ月延期になっちゃって…
ISUCONとかぶったので本腰を入れて解くことができなかったのが残念です。
SECCON運営メンバが作問してるだけあって、面白い問題がおおかったので本当はちゃんとときたかったです。
このチームでちゃんと解いてたら本戦いけたかな…来年に期待。
「お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル、それがISUCONです。過去の実績も所属している会社も全く関係ない、結果が全てのガチンコバトルです。」(公式説明)であるISUCON5のオンライン予選に参加してきました。
メンバーは、CTFの時のメンバーと同じく、チーム竹田氏の、
- @__math
- @misodengaku
- @chibiegg (自分)
で参加しました。3人参加が上限なので、いつものメンバのきひろちゃん (@aki33524) も含めた4人のうちから3人で出場しました。
ISUCONは Iikanjini Speed Up Contest の略で、Webアプリケーションがデプロイされたイメージを渡されて、その上で何をしてもいいからとにかくパフォーマンスを上げることが競技内容です。
オンライン予選
今回はイメージと競技マニュアルをもらった時点で次のことがわかっていました。
- Ubuntu 15.04
- フロントはNginx
- アプリケーションは次の言語で実装されてる (どれか好きに選んでもいいし、書き直してもいい)
- Ruby
- Perl
- Python
- PHP
- Java (正常に動作しない)
- GoLang (正常に動作しない)
- Scala (正常に動作しない)
- DBはMySQL
- インスタンスはGoogle Cloud Platformのn1-highcpu-4 (vCPU x 4、メモリ 3.6 GB)
今回パフォーマンスを上げるアプリケーションはこちら！
その名も ISUxi！足跡機能もあって、どこかでみたことあるアプリケーションです。
これが超絶重い…特にトップページなんかかなり待たされます…これを最適化してくわけですね。
大まかにやったことは以下のような感じです。
- 設定関係
- gunicornをUNIXソケットに
- MySQLへの接続をUNIXソケットに
- 静的ファイルはNginxで提供
- ファイルディスクリプタ数の上限変更
- 各種プロセス数の調整
- MySQLの一時ディレクトリをRAMディスクに移動
- MySQLの各種パラメータ調整
- アプリケーション関係
- ユーザーテーブルを全てオンメモリで持つ (変更が無く、5000レコードしかなかったため)
- 各種SQLの最適化
- ロジックで判定しているところをSQLで判定させるとか
- 1レコードずつ取得するようなことが無いように
- あしあとテーブルのスキーマ変更
- etc…
ISUCON4は結構設定まわりのチューニングだけで本戦出場できる感じだったのに対し、今回はアプリケーションの規模も大きく、実装の方にも手を出さないと本戦出場できなさそうな感じになってました。
途中はMySQLのクエリログを全て取得して、スコアのために測定される1分間でどこのクエリが時間を占めているのかを調査してそこから潰していきました。
特にトップページがLIMIT 1000とかのSQLを3回も吐いてるのでかなり重く、トップページを改善するだけで1万点以上上がったのではないかと思います。
あとはあしあとテーブル。記事にアクセスがあるたびにレコードが追加されるのですが、これを日付、アクセスユーザー毎にGROUP BYしてSELECTするのでとっても重いのです…
こちらは (ユーザーID、アクセスユーザーID、日付、最終アクセス日時) の形にスキーマを変更し、あしあとは INSERT…ON DUPLICATE KEY UPDATEにすることで、 SELECT時のパフォーマンスをかなり改善することに成功しました。
こんな感じで進めていくことで、最初はもたついていたISUxiもとっても快適に動作するようになり、スコアも16000点以上出すことができました。
最後に再起動テストをしたのですが、なぜかスコアが下がってしまって、最終スコアは14795点になってしまったのですが、無事263チーム中12位で予選通過することができました！
たぶんPython+MySQLのデフォルト構成のままではこれぐらいのスコアが上限なきがしますので、かなり健闘した方だと自負しています。
ほんとはRedisにデータを載せ替えたり、もっとオンメモリで処理したかったのですが、それは本戦で頑張ることにします♪
コードはGitで管理していて、ブランチ切って作業して、テストケース通ったらmasterにマージってしていたのですが、最後のほうはもう直接masterにマージしちゃってますね笑 (コミットユーザは合ってません)
おまけ (準備編)
去年の傾向から、MySQLを使うのだろうなとは思っていたので、事前に別のインスタンスでPHPMyAdminを用意してました。
これがデータ構造を把握したり、ちょっとSQLを試したりするのに超便利で、準備しておいてよかったものNo.1かもと思ってます。
さくらのレンタルサーバとは
VPSとは異なり，OSの管理をさくらインターネットが行い，一部の権限だけをユーザーが持つホスティングサービスです．
root権限のあるVPSとは違い，できることと使えるリソースは限られますが以下の機能がセットアップなしで利用できます．
さらに，OSやApacheのセキュリティアップデートなどのメンテナンスもさくらが行うので，(自分が設置したもの以外)メンテナンスを意識せずに使えるため，これまでVPSでやってきた人にとっても思った以上に便利だと思います．
- ApacheによるWebサーバ + CGI
- メールサーバ (SMTP/POP3/IMAP)
- データベースサーバ(MySQL)
- PHP, Python, 等々のコマンド
- CRON
詳しい仕様は サービスサイト に任せるとして本題に入ります．
ある程度ApacheやDjangoについて理解できている人向けにあっさりと説明します．
Djangoを動かす
一般的な設置方法との違い
レンサバのApacheには mod_wsgi のようなPython向けのモジュールが入っていないため，一般的なデプロイ方法では設置できません．また，常時起動のデーモンプロセスを起動させることもできないため，FastCGIサーバとしてDjangoを動作させることもできません．
そこで，言語問わずCGIモードに対応していることを用いてCGIとしてDjangoを動かします．
Djangoのアプリケーションを作成する
今回はデプロイの説明のため，Webアプリケーションの作成に関しては触れません．サンプルとして以下に公開しているDjangoのプロジェクトを利用して説明します．
chibiegg/django-example-python2
さくらのレンタルサーバを契約する
さくらのレンタルサーバオンラインサインアップ より，さくらのレンタルサーバを契約します．MySQLはスタンダードプラン以上で利用できます．すでに契約しているひとは持っているアカウントでOKです！
2週間の無料お試し期間もあります．(この記事も2週間お試し期間をつかって書いています)
契約すると，仮登録完了メール等でパスワードが通知され，最終的に以下のようなコントロールパネルにログインできると思います．
今回は初期ドメイン chibiegg-201505.sakura.ne.jp で契約したとして説明します．
データベースを作成する
コンパネ左のメニューから データベースの設定 をクリックします．
“データベースの新規作成” をクリックし，適当なデータベース名とパスワードを決めて，データベースを作成します．
パスワードは今後作成する全てのデータベースで共通になります．（変更可能）
また，文字コードはUTF-8を指定します．
作成後に表示されるデータベースサーバ名を控えておきます．(いつでも参照可能です)
今回は mysql508.db.sakura.ne.jp でした．
SSHでログインして作業する
サブディレクトリを初期ドメインのルートディレクトリにする
標準では /home/chibiegg-201505/www/ がルートディレクトリになりますが，さくらのレンタルサーバでは一つの契約で複数のドメインのWebサイトを提供できます．このとき，ドメインごとに別ディレクトリを指定すると便利なので， /home/chibiegg-201505/www/chibiegg-201505.sakura.ne.jp/htdocs/ が chibiegg-201505.sakura.ne.jp のルートディレクトリになるように ~/www/.htaccess を作成します．
RewriteEngine on
RewriteCond %{HTTP_HOST} chibiegg-201505.sakura.ne.jp [NC]
RewriteCond %{REQUEST_URI} !(^/chibiegg-201505.sakura.ne.jp) [NC]
RewriteRule .* /chibiegg-201505.sakura.ne.jp/htdocs%{REQUEST_URI} [L]
pyenvのセットアップ
標準ではPythonのバージョンが2系しかなく，また，pipなども利用できないため，pyenv と pyenv-virtualenv を利用し，プロジェクトごとにバージョンとパッケージを選択できるようにします．
pyenvに関しては基本的に一般的な方法そのままです．
git clone https://github.com/yyuu/pyenv.git ~/.pyenv git clone https://github.com/yyuu/pyenv-virtualenv.git ~/.pyenv/plugins/pyenv-virtualenv
でインストールし， ~/.bash_profile を以下のようにします．
export PYENV_ROOT="$HOME/.pyenv" export PATH="$PYENV_ROOT/bin:$PATH" export TMPDIR="$HOME/tmp" export PYTHON_PATH=./ eval "$(pyenv init -)" eval "$(pyenv virtualenv-init -)"
今後pyenvを使うときは bash を使います．
chsh -s /usr/local/bin/bash bash source ~/.bash_profile
次回からはSSHログイン時にbashが起動します．
今回のプロジェクトで使う環境をセットアップする
pyenv install 2.7.9 pyenv virtualenv 2.7.9 django-example-python2 pyenv activate django-example-python2 pip install django mysqlclient
Djangoのファイルを設置する
bash mkdir -p ~/www/chibiegg-201505.sakura.ne.jp/htdocs cd ~/www/chibiegg-201505.sakura.ne.jp git clone https://github.com/chibiegg/django-example-python2.git cd django-example-python2 pyenv local django-example-python2
Djangoの設定ファイルを修正する
~/www/chibiegg-201505.sakura.ne.jp/django-example-python2/src/myprj/production_settings.py を以下のように編集します．
この時，ディレクトリやホスト名，データベースの接続情報は環境に合わせてください．
# encoding=utf-8
from .settings import *
DEBUG = False
ALLOWED_HOSTS = ["chibiegg-201505.sakura.ne.jp"]
DATABASES = {
'default': {
'ENGINE': 'django.db.backends.mysql',
'NAME': 'chibiegg-201505_myprj',
'USER': 'chibiegg-201505',
'PASSWORD': 'PASSWORDISHERE',
'HOST': 'mysql508.db.sakura.ne.jp',
'OPTIONS': {
"init_command": "SET storage_engine=InnoDB",
}
}
}
STATIC_URL = '/static/'
STATIC_ROOT = '/home/chibiegg-201505/www/chibiegg-201505.sakura.ne.jp/htdocs/static/'
migrate (syncdb) する
VPSの時と同じようにモデルからテーブルを作成し，スーパーユーザの作成と，静的ファイルの生成を行います．
cd ~/www/chibiegg-201505.sakura.ne.jp/django-example-python2/src python manage.py migrate --settings=myprj.production_settings python manage.py createsuperuser --settings=myprj.production_settings python manage.py collectstatic --settings=myprj.production_settings
CGIを作成する
ここまでは，どこにデプロイするときも同じです．本来であれば，mod_wsgiや，FastCGI(gunicorn)を使いますが，CGIモードで動かすためにcgiのスクリプトを ~/www/chibiegg-201505.sakura.ne.jp/htdocs/django.cgi に作成します．
ひな形を用意してますので，ダウンロードして使います．
cd ~/www/chibiegg-201505.sakura.ne.jp/htdocs wget --no-check-certificate https://raw.githubusercontent.com/chibiegg/django-cgi/master/django-python2.cgi mv django-python2.cgi django.cgi chmod +x django.cgi
このスクリプトには，実行環境に合わせて3箇所編集・追記する場所があります．
pythonのバイナリの場所を指定する
一行目のpythonのパスを，pyenvの環境のpythonにします．
今回は /home/chibiegg-201505/.pyenv/versions/django-example-python2/bin/python ですので，一行目を以下のようにしました．
#!/home/chibiegg-201505/.pyenv/versions/django-example-python2/bin/python
プロジェクトのパスを追加する
# Change this to the directory above your site code. の行の後にDjangoのプロジェクトのパスを追加します．
sys.path.append("/home/chibiegg-201505/www/chibiegg-201505.sakura.ne.jp/django-example-python2/src")
利用するDjangoの設定を指定する
末尾のほうの application.settings を今回利用する myprj.production_settings に変更します．
.htaccessでリダイレクトの設定をする
ここまでで http://chibiegg-201505.sakura.ne.jp/django.cgi/admin/ にアクセスしてみましょう．
ちゃんとDjangoの管理サイトにアクセスできると思います．
ただ，これではカッコ悪いので，ちゃんとRewriteでURLを /admin/ だけになるようにしましょう．
~/www/chibiegg-201505.sakura.ne.jp/htdocs/.htaccess を以下のように作成します．
<IfModule mod_rewrite.c>
RewriteEngine on
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^(.*)$ /django.cgi/$1 [QSA,L]
</IfModule>
これで http://chibiegg-201505.sakura.ne.jp/admin/ でちゃんとアクセスできるようになりました．
Python3を使う場合
pyenvを入れたのでPython3系列も利用可能です．CGIファイルがバージョンによってことなりますので，
https://raw.githubusercontent.com/chibiegg/django-cgi/master/django-python3.cgi
を利用してください．
]]>昨年の9月にオンライン予選が開催された，SECCON CTF 2014の決勝戦に参加してきました．
昨年はチーム”竹田氏”という名前で決勝戦に出場していたチームの一人と入れ替わり，チーム”Mr. Takeda”として参加しました．
英語表記になったのは，今年からマルチバイトはだめと言われたためで大意はありません．懇親会等でも”たけだし”と呼ばれたので漢字表記のほうが定着しているようです．
国内だけの大会だったはずが，世界大会になり，さらには世界的なハッキングコンテストが開催されるDEFCONの出場権がついてくることになったため，有名な海外のチームもやってきて超難関な決勝戦になってしまいました．Twitterでは，「国内野球大会かと思って参加したら、突然優勝賞品にワールドシリーズ出場権が追加されて、参加チームにヤンキースをはじめ世界の超一流プロチームが集まっていて、ふと隣を見るとイチローがアップを始めていた」と例えられていました(笑)
今回の目標は半分冗談で1桁の順位と決めていたのですが，24チーム中 9位の成績を収めることができ，メンバー一同騒然となる，総合的にはとてもうれしい結果を残すことができました．
SECCON CTF 2014 決勝戦スコア
6台のサーバが用意されており，攻撃に成功するとフラグと呼ばれる文字列が手に入ります．これをスコアサーバに送信することで，ひとつあたり100点が加算されます．
また，各サーバに定期的に更新される自分のチームのDefence Keywordを書き込むと，5分ごとに得点が入るルールがあります．
残念ながら，本題のフラグは一つも取ることができなかったのですが，他のメンバーが解いている間にDefence Keywordをなんとかしてそのタイミングにサーバに書き込むことを続けていました．
これにより，3+α個のフラグに相当する得点ができたので，なんとかチームに貢献できてよかったです．
予選ではないDefence Keywordを賭けた他のチームとの攻防戦はとても楽しかったです．
SECCONの詳細は後で加筆することにして，問題のWriteUpを先に書いておきます．
サーバ壱
Redmineのデザインそっくりな”Secmine”というユーザー登録が必要な架空のサイトについての問題でした．
Secmine 登録ページ
メニューから，管理者に対して任意のURLを開かせることができる脆弱性がありましたので，クロスドメインの問題を避けながらなんとかセッションか，その他の情報を管理者から奪取すればよさそうというところで頓挫．
このサーバでは，チームで登録したアカウント数のランキング上位に5分ごとに得点できる状態になっていたのですが，単位時間あたりに登録が可能な回数が制限されているため，一番最初に気づいたチームが独占状態で，参戦するのはやめました．
Secmine アカウント数ランキング
サーバ弐
以下のような種類があるCAPTCHAがついた掲示板でした．
掲示板
CAPTCHAには，
- 単純に文字列
- 四則演算
- 図形の位置をマウスで合わせる
- 一部が欠けた図形の位置をマウスで合わせる
- 文字列の位置をマウスで合わせる
というパターンがありました．
CAPTCHA パターン
ここで，ランキングというページを見ると，5分間に投稿された回数がアクセス元IPアドレス別にランキングされており，1位を取ると管理ページにアクセスする権利が得られ，無事一つのフラグをゲット．
掲示板管理ページ
ちなみに，このページで表示されるCAPTCHAのタイプやその他のパラメータを調整することができ，他のチームの邪魔をすることもできます．
もう一つどこかに攻撃できる点があるはずなんですが，ここで頓挫．
このサーバでは，最新数件が含まれる”History”に自分のチームのDefence Keywordが本文として書き込まれていると5分ごと得点が入るのでなんとかしてCAPTCHAを自動化してたくさん投稿する作戦を立てました．
“文字列”，”四則演算”，”図形”の3パターンだけを自動化すると絞り込んで，Pythonでノイズを除去し2値化，オープンソースのtesseract-ocrでデコード，四則演算の場合には計算した結果を送信．円の場合には左上の座標を算出し送信し，無事自動化しました．ところが，画像処理が挟まるためすごくおそい…．5分間で数百回が限度でした．
CAPTCHA ノイズ除去
その後他のチームが5分間に数千という回数の投稿をしてきたので，脆弱性をついてCAPTCHAをスキップする作戦に変更．
調査をしてみると，”cap_token”というCookieがあり，それと答えが1対1に対応する上に，何度でも通ってしまう脆弱性が見つかりました．これを突いて，CSRFトークンと，固定の答えだけを1度目のだけ画像解析を使い，2度目以降は同じ答えを使い回すことで大幅に速度を向上させました．
ここまでくると，Pythonを使わずにbashとcurlコマンド(+α)だけで実装すればさらなる高速化が期待できると考えたので，シェルスクリプトを作成．チーム全員に配布し各人100プロセス以上並列に起動させて，もはやDDoS状態でした．
掲示板投稿ランキング
私たちのチームは192.168.4.0/24なのですが，ここに載ってるタイミングで1万リクエスト以上成功しています．
この時点で，チームの現在のDefense Keywordをスコアサーバから取得する必要があるのですが，このページ，WebSocketでできてるんです．
なので取得が面倒くさい．そこで，PythonでWebSocketクライアントを書いて，取得した最新のDefence KeywordをHTTPで配信するサーバを立てました．
これにより，他のメンバーはDefense Keywordをcurl等でGETするだけで利用できます．この設計が後々サーバ伍ですごく役に立つことに．
サーバ参
オーバーフローの脆弱性があるプロセスが用意されており，ROP(Return-Oriented Programming)の手法を用いて攻撃する問題．
@aki33524が解いたのでWriteUpにリンク張ります．
サーバ四
mips, h8300, m32r, mn10300, rxのアーキテクチャで動作する脆弱性のあるプロセスに対し攻撃をかける問題．逆アセンブルしてコードを読むと，オーバーフローが起きる問題を見つけたのですが，攻撃コードを考える時間がなくて断念．
サーバ伍
よくわからないHTTPサーバが動いてる．どうやら4台あるよう．@misodengakuがひとつフラグをゲットしたので，WriteUpにリンク張ります．
二つ目以降のフラグが手に入らなかったのですが，どうやらこの問題はWebの問題ではなくて，TCP/IPの問題だったそうで，不正なIPヘッダのダミーのパケットが返って来るために通信できないポートがあったそうな．
そのダミーパケットをうまく選別して，iptablesでDROPさせればつながるポートがあるらしい．だれかWriteUp書いたらリンクはります．
ネットワークの問題って気付けば解けたのに！これが個人的にはすごく悔しいです．
Webの問題に見せかけるのずるい…
このサーバでは，トップページに自分のDefence Keywordを書いておけば，5分ごとに得点できました．
パスワードがかかっていないSubversion-WebDAVが動いているのを発見したので，ファイルをすべて消して，自分のDefence Keywordのファイル名のファイルだけを作成しサーバにコミットするスクリプトを無限ループで実行．
ここにDefence Keywordが書き込めていたのは，準優勝のHITCONとうちだけだったようです．
ここで，サーバ弐のときに準備しておいたキーワード配信サーバが役に立ちました．
サーバ六
様々な方法で暗号化された文字列を元に戻す問題．@__mathが説いたのでWriteUpにリンク張ります．
このサーバでは本題とは別に，Pythonで書いた暗号・復号プログラムを投稿し，最も短いコードかつ，誰にも解かれていないスクリプトを投稿できているチームに5分ごとに得点が入る構造になっていました．
最初のうちは @__math がまともに投稿して，何度か得点していたのですが，これ以上は難しいという短さまで到達．得点が加算されるタイミングを分析して，INPUT=OUTPUTという全く暗号化していないけれども最も短いコードをその瞬間に投げることで，何度か得点することができました．
追記
NHKにしっかり映ってた
連投で自分が関わった問題のWrite Upを書きましたが、他のメンバーやチームが解いた情報をいくつかリンクしておこうと思います。
このブログの記事
他のメンバーの記事
他のチームの記事
- @kusano_k さん “SECCON 2014 オンライン予選（英語）Write-up”
- Welcome to SECCON (Start, 100)
- Easy Cipher (Crypto, 100)
- Shuffle (Binary, 100)
- Reverse it (Binary, 100)
- jspuzzle (Web, 100)
- REA-JUU WATCH (Web, 200)
- Bleeding “Heartbleed” Test Web (Web, 300)
- XSS Bonsai (aka. Hakoniwa XSS Reloaded) (Web, 500)
- QR (Easy) (QR, 200)
- Get the key.txt (Forensics, 100)
- Choose the number (Programming, 100)
- The Golden Gate (Programming, 400)
- Get the key (Network, 10100)
- Get from curious “FTP” server (Network, 300)
- MMAさん Writeups for SECCON 2014 オンライン予選（英語）
あと、これは途中まで準備して、@misodengaku に解いてもらいました。
Web 300の、”Bleeding “Heartbleed” Test Web”。
どうみても、OpenSSLのHeartbleed脆弱性があるかどうかするテストページです。脆弱性があるサーバが必要なのかな？と思い、さくらのクラウドに脆弱性のあるUbuntu 12.04を構築しました。
レスポンスのHTMLを見てみると、DBにインサートされてることがわかる。
さらに、同一時刻にリクエストを投げると、あきらかなSQLエラーが。
ということは脆弱性があるふりをして、SQLインジェクションを起こせそう…？というところで @misodengaku にまかせたら解いてくれました。
具体できにどんなレスポンスを投げたのか気になるところ…
追記
みそでんがWrite Upを書いてくれました。“SECCON 2014 オンライン予選2に出た”
“; SELECT flag AS time FROM ssFLGss; —
でOKだそうです。
]]>他にもQRコードには手をつけていたのですが、最後まで解けず…
その一つがQR 200の、”QR (Easy)”
なんと、パンケーキにQRコードが書いてある…しかも食べられてる！
しかし、大丈夫！QRコードは右半分に生データ、左半分にリードソロモンエラー訂正符号が入っているため、右半分あれば読める！
@misodenngaku が見える部分を画像にしてくれた。
これをQRコード、バージョン3の訂正レベルHの規則に従って、復元してみた。が、SECCONまでは読めたけどそこからがよくわからない…
Excelのbin2hexは8bitまでしか対応してないけど、Numbersならもっといけたので助かった。
もう一つが、QR 400の”BBQR”。バーベキューアールっていうネタ。
QRコードでBBQされている…焼く前に写真撮って欲しいものである。さっきとちがって、左半分が残っている。幸い制御情報がすべてあるので、バージョン3、訂正レベルH、マスクの種類もすべてわかったので、とりあえず綺麗な画像にしてみた。
リードソロモンで訂正するには何バイトかまだ足りない…というところであきらめた。
]]>