ISUCON10予選の感想戦をして7827点を出した
はじめに
弊チーム百万円ドリブンのISUCON10の本戦出場が決まりました。
予選当日の動きはメンバーのgnuの記事、aokabiの記事 に書かれているのでそちらを御覧ください。チームメンバーが最強なので僕は歌って踊っていただけで突破できました。感謝。僕は当日色々躓いたりして結局まともに貢献できなかったのでまじで感謝...
ISUCON用にこういうDBとの関係性可視化ツールを作っているので毎回使っているのですが、今回の予選の問題は上図のようにシンプルな関係となっており、非本質的な部分が削られているのだなぁと感じました。
感想戦
さて、予選が終わった段階で21位・2281点のスコアが出ていたのですが、我々は百万円ドリブンなので百万円にしか興味ありません。限界までチューニングをします。
予選当日でメンバーが重たいところを殆ど潰してくれたので、残りは getLowPricedChair、getLowPricedEstate、searchChairs、searchEstates だけでした。この記事ではこの処理をオンメモリにしてMySQLへの問い合わせオーバーヘッドを無くすというチューニングを行い、7827点を出します。
リポジトリはこちら。
chair, estate のオンメモリ
よく見るとchairs・estateのデータはそれぞれ35000件しかありません。またメモリも潤沢に2GBあるため、まるでオンメモリにしろと言われている気配すら感じます。Goのアプリ上でオンメモリにし、データの検索・追加・更新をO(logN)で行いたい気持ちになります。
getLowPricedChair, getLowPricedEstate
こちらは要するに、「データ全N個の中から値段の昇順でK個取得せよ」というクエリです。 データはオンラインで更新される可能性があるため、平衡二分探索木のデータ構造(挿入・検索がO(logN)ででき、常にソートされていてk番目の値がO(logN)で取れる)に乗せればよさそうです。 ここの探索木は標準ライブラリにないため自分で書いてもいいのですが、本質ではないのでhttps://github.com/wangjia184/sortedset を使うことにします。 それぞれの値段をソートの順序として用いる平衡二分探索木を使えば簡単にオンメモリにできますね。
searchEstates
こちらは要するに「データ全N個の中から、Rent・Height・WIdthで条件を絞り込み、Popularityの降順で並べたときに、[A,B]番目のデータを取得せよ」というクエリです(本当はFeaturesも見る必要がありますが殆どクエリが飛んでこないので無視します)。 また、Rent・Height・Widthはそれぞれ4種類(例：Height < 80, 80 <= Height < 110, 110 <= Height < 150, 150 <= Height) のいずれかであり、絞り込み条件に含まれない場合もあります(例：Heightの指定なし)。
結論から述べると、Popularityをソートの順序として用いる前記の平衡二分探索木を計125個、5x5x5の三次元配列として持てば、O(logN)でクエリ・追加・更新にそれぞれ対応できます。 条件が4種類(例：Height < 80, 80 <= Height < 110, 110 <= Height < 150, 150 < Height)あり、それを0,1,2,3番と対応させます。条件指定なしの場合は4番と対応させます。 例えば「Rent指定なし・80 <= Height < 110・110 <= Width < 150 」のクエリは、4番・1番・1番と対応します。更新のときは0~3番の対応するものと4番を更新すればよく、計8(=23)箇所更新すればよいですね。
searchChairs
こちらも殆どsearchEstatesと同じですが、条件が更に追加で3つ(Color, Kind, Depth)増えます。
これらの条件も同様に扱うと、前記の平衡二分探索木を計56875(=5x5x5x7x13x5)個、5x5x5x7x13x5の六次元配列として持てばO(logN)でクエリ・追加・更新にそれぞれ対応できます。
更新が64箇所必要ですが、まぁこれは仕方がないでしょう。
これを愚直に実装すると余裕でメモリ制限2GBはオーバーするので気をつけましょう。僕はこれでswap領域を作らずにメモリを食い尽くしたせいでサーバーが1台死んでしまいました
さいごに
やったことはISUCONというより競プロですね。
感想戦として上記の残りネックになっていた箇所に対してオンメモリ対応をすることで7827点を出すことができました、やったぜ。
追記：当初は7670点として記事を公開していましたがもう一度回したところ7827点が出たので更新しました。
