ISUCON14の延長戦をやってます
以下の記事の続きです。
前回は椅子の総移動距離を管理するカラムを追加することにより、非常に重いクエリを軽量化しました。が、スコアはまだまだ伸びません。
なお、最終的なコードは以下のリポジトリで公開しています。
マッチングアルゴリズム
アプリケーションマニュアルにあるとおり、椅子とライドのマッチングは一定間隔（初期実装では500ms）でリクエストされる内部APIによって実現しています。 この実装がよろしくなく、ベンチマークの結果を見ると次のようなログが頻出します。ライドがマッチングされるまでの時間に多くのユーザーが不満を抱えていることがわかります。
100.0%のライドは椅子がマッチされるまでの時間、50.0%のライドはマッチされた椅子が乗車地点までに掛かる時間、100.0%のライドは椅子の実移動時間に不満がありました
本戦当時も、このログからマッチングアルゴリズムが足を引っ張ってるなと気付くことができました。今回はここの改善に取り組みます。
なお、初期実装では「ここがまずいから直してくれ」と言わんばかりのコメントが書いてあります。当時これを見つけてめっちゃ笑いました。
// MEMO: 一旦最も待たせているリクエストに適当な空いている椅子マッチさせる実装とする。おそらくもっといい方法があるはず…
アルゴリズムの改善
完全な変更内容は以下のPull Requestにまとまっています。
改善方針
初期実装のアルゴリズムでは、一回のリクエストで常にひとつのライドしかマッチングしないようになっています。 あまりにも効率が悪いので、以下のように一回のリクエストでバルク的にマッチングする方針としました。
- マッチング待ちのライドをすべて取得する
- 現在空いている椅子を、その位置情報とともにすべて取得する
- ライド毎にループする
- 椅子毎にループし、ライドの始点との距離を計算する
- 最も近い距離にいた椅子を抽出し、ライドとのマッチング対象とする
- 椅子が複数のライドに割り当てられないよう、2で抽出された椅子を椅子の一覧から除外する
- ライドと椅子のマッチング情報を登録する
- 椅子を空いてない状態（
is_free = FALSE）にする
3のループはライドの登録日時順で回しました。 ライドに長時間椅子がマッチングしないとクリティカルエラーになってしまうため、とにかく一番待たせているライドを最優先でマッチングするようにしています。
また、最も近い距離にいた椅子を割り出すためのしきい値として 400 という距離を設定しています。
解説記事にもあるとおり、ライドはサービス提供エリア内を移動することから、同エリア内に存在する椅子に限定してマッチングさせ、別エリアにいるような椅子とのマッチングは見送ったほうが効率が良くなります。 400 は解説記事の参考実装に出てくるしきい値で、その値をそのまま頂戴しました。
Too many connections との格闘
上記の改善アルゴリズムを実装すると、負荷走行中に Too many connections というメッセージとともに500エラーが頻発し、ベンチがコケるようになりました。トランザクションの構成など細かい調整をしましたが、根本的な解決にはならなかったため、MySQLサーバーのパラメータを調整することにしました。
MySQLサーバーのデフォルト値では、max_connectionsパラメータは151に設定されています。database/sql パッケージのコネクションプールはデフォルトで無制限にコネクションを確立するようで、おそらくアルゴリズム改善によってユーザーが増加し、同時リクエスト数が増えたことでコネクション数の上限をオーバーしてしまったのでしょう。
この問題を解決するため、 /etc/mysql/mysql.conf.d/conn.cnf ファイルを作成し、次のような設定を入れました。
[mysqld] max_connections = 1000
併せて、アプリケーションコード側でもコネクションプールの設定を調整します。設定根拠は以下の記事を参考にしました。昔会社の先輩に教えてもらった記事で、今でもバイブル的にブックマークしている記事のひとつです。
SetMaxOpenConns はMySQLサーバーのmax_connectionsを最大値としつつ、同時接続するサーバー数で割ります。現状は1インスタンスしか使ってないのでそのまま1,000を設定しました。
SetMaxIdleConns は SetMaxOpenConns 以上であれば良いとのことなのでそのまま1,000とします。
SetConnMaxLifetime はベンチマーカーが負荷走行をかける時間以上にせっていしておけば良さそうです。負荷走行が60秒程度で完了するので、少し長めにとって80秒としました。
db.SetMaxOpenConns(1000) db.SetMaxIdleConns(1000) db.SetConnMaxLifetime(80 * time.Second)
これらの設定を追加することで、無事Too many connecitonsから解放され、ベンチが通るようになりました。
まとめ・次回予告
この変更を取り込んだ結果、スコアが一気に17,000点程度にまで上昇しました。これまでにないジャンプアップ、そして本戦当時の最高スコアを大幅更新です。やった！
ようやく、今まで見たことない景色を見れる位置まできました。また更にチューニングを続けていきます。つづく。
