こんにちは。23Mの@mazreanです。
参加記に引き続いて、ISUCON14感想戦でこの記事を書いている時点で最高得点の40万点を出したのでその方法について解説していきます。
mazrean
改善内容については参加記で説明したものの説明は省いているため、最初からなぞる場合は参加記を確認することをお勧めします。
また、自分で言うのは何ですが内容的にもかなり面白いことをやっていると思うので是非読んでみてほしいです。
ここからは本題の40万点出すためのチューニングに入ります。
前提
本題の手順に入る前に、問題のシナリオや、少し変わったライブラリを使ったりしているのでその説明をします。
問題のシナリオ
今回の対象となるISURIDEはライドシェアサービスです。
当日マニュアル・アプリケーションマニュアルの情報から状況をまとめると以下のようになります。
- 主にユーザー・椅子・管理者の3種類のクライアントが存在
- ユーザーの配車要求(以降ライド)と椅子をマッチングさせる
- 完了ライド数が多いほどスコアが増加
また、今回の問題ではこれに加えて以下の重要な情報がベンチマーカーログで出ています。
-
これまでに地域内の評判によってx人、既存ユーザーの招待経由でx人が新規登録しました
ユーザーは「地域の評判」が良いと増える
-
x%のライドは椅子がマッチされるまでの時間、x%のライドはマッチされた椅子が乗車地点までに掛かる時間、x%のライドは椅子の実移動時間に不満がありました
「地域の評判」マッチング時間、乗車待ち時間、移動時間の3つできまりそう
-
-
一定の売上が立ったためオーナーの椅子が増加します
椅子は管理者が売り上げを確認すると増加
- 実はここは自力で気づけず、30万点超えた後作問メンバーの@ryoha と話して「これやった？」を聞かれて初めて気が付きました
これらを組み合わせると、以下のようになります。
- 配車要求から支払い完了までの流れを高速化することで直接的なスコア増加
- マッチングアルゴリズムの改善によりスコアに直結する処理の同時実行数増加
- 椅子が足りなくなったら管理者関連の改善をすることでスコアに直結する処理の同時実行数増加
- 椅子不足になると「ライドが長時間マッチングされませんでした」のエラーが出やすくなるため、fail率低下効果もある
- 逆に、15万点近くで初めて椅子が足りなくなるため、それまでは管理者関連改善効果は薄い
これを踏まえて、管理者によるリクエストは少ないのもあり、序盤は徹底的に直接的なスコア増加につながる箇所とマッチングを改善、椅子が足りなくなった段階で管理者関連の改善にシフトします。
badger
この問題のかなり大きな負荷のポイントとして、椅子による現在位置投稿があります。椅子が移動するたびにリクエストが来るため凄まじい量の書き込みリクエストが飛んできます。また、椅子は現在位置の投稿が完了するまで移動しないらしいため、ここを高速化することで直接的なスコア増加にもつながります。
その他にもライドの状態などもスコアに直結するAPIで頻繁に書き込みが行われます。
そこで、今回の感想戦で投入したのが埋め込み型key-valueストアのbadgerです。badgerはGo言語のライブラリとして利用可能な高速なkey-valueストアで、MySQLなどの別プロセスで動作するDBと比べて通信分のコストが発生しなくなりスコアの限界を上げることができます。「DB通信コストくらい大したことなくない？」と思う方も多いと思いますが、限界までチューニングするとjsonエンコードすらしていられない負荷の領域になるので、これが効いてきます。
反面、key-valueストアな分当然relationの扱いは苦手な他、別インスタンスへDBを逃がすこともできなくなるため、ISUCON本番では柔軟性がなくなり効果を発揮しづらい改善のように思います。
やったこと
ここからは実際にやった改善とスコアの推移を解説していきます。本番終了時の最高スコアは26,710点なため、そこからの改善になります。また、全部改善を書いているととてつもなく長くなってしまうので、崖ができた改善のみの紹介になります。
mazreanアプリケーション通知のSSE&イベントバス対応(31,454点)
アプリケーションの通知をSSEに対応させ、かつイベントバスによりrideの状態変化のイベントをDBを経由せずに受け取れるようにします。
これによりDBの負荷軽減とイベント伝達までのラグ削減により配車要求から支払い完了までの流れが高速化して点が上がります。
椅子通知のSSE&イベントバス対応(46,286点)
アプリケーションと同様に椅子の通知もSSEとイベントバスを用いた実装に変えます。
この部分の注意点として、アプリケーション通知と椅子通知のSSEの挙動の違いがあります。アプリケーション通知はライド完了時点でアプリケーション側からSSEのコネクションを切ってくるのですが、椅子通知ではライド完了後もSSEのコネクションを使いまわすようになっており、しかもコネクションが切れた後再接続しません。このため、椅子通知ではライド終了時にコネクションを切る実装をすると、椅子に2回目以降のマッチングイベントが届かなくなります。この挙動のさらに厄介な点がベンチマーカー側はどの椅子をマッチングさせたか知ることができないためGET /api/app/nearby-chairsとの整合性の問題が起きるまでエラーがです、fail理由が「付近の椅子情報が想定よりも足りていません」になるという点です。これの原因特定に半日くらいかかりました…
getLatestRideStatusesのオンメモリキャッシュ(75,038点)
ライドの状態を複数取得している場合、オンメモリキャッシュを使っていなかったためオンメモリキャッシュを使うように修正します。
これにより一気にDB負荷が軽減し、本選当日の優勝スコアを超えました。
appGetNearbyChairs内のchair locationオンメモリキャッシュ使用(104,350点)
chair locationのオンメモリキャッシュはしていたのですが、appGetNearbyChairsで使っていなかったため使う用に修正しました。
ride statusのオンメモリキャッシュ方式変更(125,394点)
ride statusのキャッシュをstatusの更新があるたびに破棄する実装にしていたのですが、そこそこcache missが起きている結果DBの負荷を下げ切れていないことが分かったので、破棄せずにしっかり更新するように修正します。
chair locationをbadgerに移動(13,3876点)
大本のデータをMySQLに置きオンメモリキャッシュしていたchair locationをbadgerに移します。これにより、POST /api/chair/coordinateの負荷がMySQLから消えてDB負荷が下がります。
たしかこのあたりからDBのCPUネックからアプリケーションのCPUネックに移った気がします。
appGetNearbyChairs内のride statusオンメモリキャッシュ使用&Nginxのworker connection増加(188,429点)
ride statusのオンメモリキャッシュをappGetNearbyChairsで使っていなかったため使う用に修正しました。
これによって最初に2048まで上げていたNginxのworker connectionが足りなくなりread: connection reset by peerで落ちるようになったので、Nginxのworker connectionを4096まで上げ、これに伴いworker_rlimit_nofileも16384まで上げました。
この時点でユーザー不足フェーズが終わり、椅子不足フェーズに突入します。
また、これに伴いNginxのCPU使用率が大きく上がっており、同一インスタンスに載っているアプリケーション以上にCPUを使う状態となります。
マッチングアルゴリズム改善(216,180点)
ベンチマーク時にはライドが30秒以内にマッチングされ無ければfailするという制約があるため、椅子不足に突入するとマッチングの期限を考慮して期限が近いライドを優先的にマッチングするようにする必要があります。そのため、優先度の計算式にライド作成からの経過時間を反映するようにします。具体的にはを優先度に追加しました。ただ、これ自体ではfail率が下がるだけで点数は上がりませんでした。
その後、椅子不足を解消する方法に悩んで迷走している中で思いついた気が付いたのが、「ベンチマーク開始30秒以降に追加されたライドにはマッチング期限が実質的にない」という点です。どういうことかというと、ライドのマッチング時間の制限はそもそもベンチマーカーによる制約です。つまり、ベンチマーク終了後にこの30秒の期限を迎えるライドはどれだけ長く待たせても問題ないということです。むしろ、追加後すぐにマッチングできなかったライドは最後までマッチさせない方が悪評がベンチマーク中発生せず、ユーザー増加によりライドが増え、適切なマッチングができる確率が上がります。これを踏まえ、余裕をもってベンチマーカー開始から35秒以上経過してから追加されたライドには、それまでとは反対に時間経過で優先度を下げるようにしました。なお、ルールには抵触していないように思いますが、ベンチマーカーハックでズルだと思います。これにより、1万5000点程度点が上がり20万点に到達しました。
ただ、最終的にはこんなことをしなくても最後まで多すぎるほどのライドが追加され続ける状態となっており、このベンチマーカーハックを消しても点数が変わらない状態となっていたことを確認しています。
activeな椅子一覧のオンメモリキャッシュ(250,130点)
appGetNearbyChairsで使用していたactiveな椅子一覧をオンメモリキャッシュします。これによりDBアクセスに使うアプリケーションCPUが減って点が上がります。
マッチングの優先度改善(336,850点)
20万点を超えるときに追加したライド作成からの経過時間で優先度が上がるようにするの計算式ですが、「fail率少し下がらないかなぁ」程度の気持ちでにして、優先度の上昇の勾配を変えました。
その結果、なぜか30万点を超えます。これに関しては未だに自分でもなぜこうなったのか確実な説明が思いつかないです。ただ、ベンチマーク時のスコアの動きを見た感じ、椅子不足になり上昇速度が変わらなくなるまでの時間が短くなるように見えたので、序盤のマッチングまでの時間が減ることでユーザー増加がより速くなったとかかと思います。
owner関連のAPIの速度向上(389,765点)
このタイミングで作問メンバーでtraPメンバーの@ryohaから「owner周り速くした？」と聞かれたことで椅子増加のギミックに気づき、owner関連のAPIに改善を入れます。具体的にはGET /api/owner/salesのN+1をつぶしています。
これによって、椅子が増加して点数が大幅アップします。
Go 1.24へバージョンアップ(417,923点)
このあたりでもはやアプリケーションのCPU負荷要因としてオンメモリキャッシュへのアクセス時のGoのmap型へのアクセスが出てくるレベルになっていたのと、作問メンバーでtraPのOBの@to-hutohuさんから「1.24で入るswisstableどのくらい効果あるか気になるから試してみてほしい」という要望を受けて、Go1.23から1.24にバージョンを上げます。
この結果、40万点を超えることに成功します。
その他
ユーザー・椅子の状態分布可視化
ユーザー・椅子がどの状態で止まっているか見えないのが辛かったので、Prometheusのメトリクスを追加してGrafana上でユーザーの状態を可視化していました。これにより今どこを改善するべきかかなり見やすくなりました。
細かい修正について
どの他、説明しきれなかった効果の小さい調整も色々行っています。具体的には、以下のような改善などを行っています。
- Nginx-アプリ間のUNIX domain socket通信
- 各種オンメモリキャッシュ
- Goのコンパイル時のPGO
- jsonのエンコード/デコードのsonicへの置き換え
- 椅子の現在位置投稿APIのjsonエンコードのstrings.Builderでの組み立て
- Nginx、MySQLの設定調整
行った順番などの関係で崖を作っていないだけで最終的な点数にはこれらも貢献している可能性が高いので、ここまでの解説した改善だけでは40万点に到達しない可能性がある点に注意してください。
複数台構成のサーバー配置について
ここまでの解説を見て複数台構成について全く触れていないのが気になった人もいると思います。実は、サーバー構成については、isucon14当日の1台目にアプリとNginx、2台目のMySQLを置く2台構成から最終的に変わっていません。
ここまでで説明した通り、最終的にはアプリとNginxが乗っている1台目サーバーがCPU負荷100%で張り付いているので3台目にどちらかを移動させたくなります。実際に試してみたのですが、結果としてはNginx-アプリ間がUNIX domain socketで繋げなくなる悪影響の方が大きいようで点が落ちてしまいました。
また、この対処としてはNginxを引き剥がしてアプリで直にリクエストを受けるという手も考えられますが、そこはやはりNginxのコネクション管理がGo標準のnet/httpより優秀なようで、Goの設定周りを色々弄ったうえでもCPUは空くがスコアが下がる、という結果になりました。
さらに点が上がる余地
自分の所管としては、まだ点が上がる余地はあると思っています。
というのも、椅子の数を増やすにあたって重要なowner関連APIでまだMySQLへのリクエストが飛んでおり、ここをオンメモリキャッシュすることでさらなる椅子の増加が見込めます。
流石に疲れたのと、他のもろもろをやらないといけないので手を放しますが、このあたりをつぶせば少なくとも45万点、ひょっとすると50万点くらいは行くかもしれません。
まとめ
ここまでカリカリチューニングをしてISUCON14感想戦で40万点を出した話を書きました。結構限界近くまでチューニングしたと思うので、達成感はあります。
ただ、一方でISUCONは厳しい時間制限の中で高い点を出してこその競技だとは思うので、来年こそは本番で勝ちたいです。
