2018-09-26

ISUCON8 予選延長戦

ISUCON8予選はみごと惨敗に終わったのだが、運営とスポンサーのご厚意により一週間予選のサーバーへのアクセスが開放されたので、予選時のトラブルの検証とどうすれば今年の予選を突破できたのかをいろいろ追加実装して試してみた。

トラブルの原因

前回の記事で終了間際、初期実装に戻してもfailし続ける謎の現象に見舞われたことについて。
結論は、IPアドレスが書き換わっていた、というのが一番近い答えでした。
ISUCONの予選用のページにチームが使えるサーバーとそのIPアドレス一覧のページがあり、そのページでどのサーバーに対してベンチマークを走らせられるかも選べます。
我々はこのリストの一番上からisucon1,isucon2,isucon3と名前をつけて、ssh_configに設定をしておきました。
しかしなんと終了1時間前あたりにそのリストの順番がアナウンスなしに入れ替わっていたのです。
今回はisucon3を対象にベンチを走らせているつもりだったのですが、その入れ替わりの過程でisucon3が一番上に来ていたの気が付かず、実はisucon1を選んでいたのでした。
ただ、こんなのはアクセスログを見れば一発でわかったことなので、焦りは禁物ですね。

また、たまにfailする問題ですが、なんと初期実装にバグがあり、高負荷時に予約時間等の整合性がとれなくなることがありました。
具体的にはデータベースを叩くときにトランザクションをつくる前にクエリを発行して予約対象の座席を決定している部分です。
さらに、他のエンドポイントもトランザクションをつくらずに複数のクエリを発行しているため、書き込み処理がそのクエリ群にはなくても、他のエンドポイントからの処理を並列で実行していた場合にデータベースの内容が書き換わり、APIのレスポンスの内容がおかしくなりfailするパターンもあるようでした。
具体的に満たすべき仕様が与えられないコンテストで、高負荷時にはじめて発現するとはいえ、初期実装にバグがあるっていうのはいかがなものなのか…とは個人的には思うのですが、こういうこともあると今後は気を配ったほうが良さそうです。

予選通過のための戦略

今年のエントリまとめから予選通過したチームの戦略を読み解きたいと思います。

戦略その１: データベースの情報をすべてメモリ上に落とす

今回の問題の初期実装はとにかくデータベースのアクセスの仕方が非効率な部分が多く、これらを解決しなければなりません。
そこで、データベースアクセスをそもそもやめて、すべてメモリ上で操作すれば処理を格段に減らせるという戦略が考えられます。
参考: ISUCON8予選参加記 - math314のブログ

こちらの戦略、予選後の開放期間でためされた方もいて、なんと50万点を叩き出したようです（予選期間中での最高得点は9万点代）。
しかし、この戦略はデータベースアクセス全てを書き換えるため実装量がとても厳しいことになり、整合性をとるのが非常に難しい戦略でもあります。
また、サーバーは1台しか使えないことになります。
さらに、アプリケーションを終了させた後の整合性も検査対象のため、データベースへの書き込みも行わないと失格になります。
確かに、今回は非常に効果のある戦略だったようですが、実装力がないチームがうかつに手を出すと破滅しかねない危険な戦略です。

戦略その２；とにかく地道にクエリを改善し、3台フル活用する

初期実装には大量のN+1クエリが存在しているため、これらを地道に潰し、3台の与えられたサーバーに適切に役割を与える、でも十分に得点は叩き出せます。
多くのチームはこちらの戦略をとっていたようです。

特に、イベント情報取得の際のreservationsテーブルの叩き方は非常に非効率なので、ここをどう改善するのかが1つの鍵だったようです。また、予約時のreservationsテーブルへの書き込みも、ロックを取得するため、効率化が必要となります。

具体的には

N+1になっている箇所はJOINなどで潰す
sheetsテーブルは不変なので、初期化時にメモリに展開しておく
reservationsテーブルに適切なindexをつくる
- event\idとcanceled_atに対してなど
予約時にランダムに席をとってくる際のSQLでのORDER BY RAND()をやめて言語実装のランダムでおこなう
- ランダムに返す事自体は要求仕様なので変えてはいけない

また、複数台の活用ですが、初期実装の状態では1つのAPIリクエストに対して複数回データベースクエリを投げるため、そのオーバーヘッドが大きいためデータベースとウェブサーバーを別にした瞬間、タイムアウトで落ちるようになります。
しかし、データベースサーバーのCPUリソースはかなりかつかつの状態なので、データベースアクセスの最適化がある程度行われたのち、複数台の実装にすることでスコアが伸びることが期待されます。
特に/admin以下にあるCSVを出力するエンドポイントはCPUを大きく消費するため、複数台化は必須となったでしょう。

今回の罠

延長戦の中で気がついた罠についていくつか紹介したいと思います

初期実装のSQLクエリ

戦術の通り、トランザクションをつくるタイミングがおかしい、そもそもトランザクションをつくっていない、などの罠もありましたが、他にも初期実装にはバグではないが不要な文がいくつかありました。

HAVING節

初期実装に

1	SELECT * FROM reservations WHERE event_id = ? AND sheet_id = ? AND canceled_at IS NULL GROUP BY event_id, sheet_id HAVING reserved_at = MIN(reserved_at)

という部分がありました。
気持ちとしては同じsheet_idに対して複数のキャンセルされていない予約があった場合、reserved_atが最も小さいものを有効な予約とみなす、としたかったのでしょうが、このクエリは正しくありません。
なぜかというと、HAVING節はGROUPED BYされた後のエントリに対してフィルターをかけるものであり、その集約前のデータに対して、あるいは集約の仕方を指定するものではないからです。
MariaDBの公式ドキュメントにも

1	To filter grouped rows based on aggregate values, use the HAVING clause

とあります。
では、複数の予約があった場合はどうなるか。
その際ような際の仕様は不定で、今回のMariaDBで実験したところ、そのカラムはそもそも集約されず無視されていました。
標準のSQLではそもそもGROUP BYで指定していないカラムに関してはSELECT節で引っ張ってこれません。しかし、MySQLではその仕様が拡張され、そのようなカラムの場合、集約されたエントリ全てにおいて、そのカラムは同一であるならば、その同一の値が入ります。しかし、同一でない場合の値は未定義です。
参考: https://dev.mysql.com/doc/refman/5.6/ja/group-by-handling.html

そもそも、予約時のトランザクションの作り方が正しければ、同じsheet_idとevent_idに複数の予約が入ることはありません（トランザクションをつくる前のSELECT文で予約のない席を探しているため）。
なので、このHAVING節は完全にいらないものです。

FOR UPDATE

いろいろなところで使われていたFOR UPDATE文ですが、きちんと検証はしていないですが、これらは全く無意味だったと思われます。

MariaDBの公式ドキュメントを見てみましょう。
このFOR UPDATEがあると、次のデータベースの書き込みが発生するまで、他のトランザクションからの書き込みやロックの取得を防ぐことができます。
しかし、ドキュメントにあるように、この節はautocommitがオフになっている場合またはトランザクション外でないと効果がありません。
autocommitはデフォルトでは有効で、サーバーの元々のmy.cnfでは特に指定していないので、autocommitが有効だったようです。
そもそも、autocommitが無効だったとしたら、FOR UPDATEしたあとにデータベースをUPDATEやINSERTがないとCOMMITを実行しない限りロックを取得したままになるのですが、今回、COMMITをしていない箇所が結構ありました。

大量の外部からのアクセス

予選中でもあったのですが、外部からの攻撃が確認できました。これはそれなりにネットワークのリソースを食っていたようなので、場合によってはそれなりにパフォーマンスが低下していた可能性があります。
具体的には、アクセスログを見たところ、phpadminなどの怪しげなアクセスが記録されていたこと、journalctl -xeでsshでの認証失敗がたくさんあったことです。
今回のsshdの設定はパスワードログインを許可していたため、このような攻撃があったのでは、と思います。
denyhostsの導入や、アクセスログを見て一部IPアドレスをファイアウォールで弾くなどの設定が必要だったと思われます。

h2oプロキシが502 Gatewayエラーを返す

これはちゃんと検証できなかったのですが、h2oで80番ポートから8080番ポートへのプロキシで502が帰ってくることがあり、502を返してしまうとベンチマークがfailする、という問題が確認できました。
8080を直接叩くと問題は起きず、同じ内容のリクエストを投げても502が帰ってくる場合とそうでない場合もあり、原因はよくわかりませんでした。
予選中はそのような問題は起きませんでしたが、アクセスログに関する設定を外した他のサーバーでなぜか頻発しました。
エラーログのデフォルト設定では特に原因がつかめず、何が悪かったかはわかりませんでした。
他のチームは早々にnginxに切り替えていたので、延長戦では僕もnginxに切り替えて深くは原因追求しませんでした。

まとめ

来年はもうちょっと環境整備をしたうえで、SQLを早く最適化できるようになりたいですね

己の不学を恥じる