Gマイナー志向

とくに意味はありません

HighLoad Cup 2021(Gold Rush) write-up

ロシア企業Mail.ruが主催するパフォーマンスチューニングコンテストHighLoad Cup 20201に参加したのでその報告。

Webサイト

https://cups.mail.ru/en/contests/goldrush

結果

Battle-Round 47位（63位以上がFinal進出）、Final-Round 37位でした。 Battle-RoundとFinal-Roundは内容は同じまま、Finalはチート対策でSEEDがランダムになっただけなので実質課題は1つです。 可もなく不可もなく、微妙なスコアですね。はい。

課題

簡単にまとめるとこんな感じです。

時間内に宝物を「探索」して「掘削」して「換金」するHTTPクライアントを実装せよ

ざっくりとした仕様は以下の通り。

  • 縦横3500x3500、深さ10の領域が与えられる
  • POST /exploreで指定した縦横範囲の探索ができる
    • 探索するとその範囲に含まれる宝物の数がわかる
    • 探索は範囲指定が可能(0,0の座標から3x4の範囲を探索など)
    • 探索ではどの深さに宝物があるかわからない
  • POST /digで指定した場所(x, y, depth)を掘削ができる
    • 1度に掘削できる深さは1のみ
    • 深さ2を掘削するためには先に深さ1を掘削しないといけない
    • 横に掘ることはできない
    • 掘削にはライセンスが必要
  • POST /licenseでライセンス取得ができる
    • ライセンスは無料と有料がある
    • 1ライセンスで掘削できる回数は無料と有料で異なる
    • 1度に保持できるライセンスは10まで
  • POST /cashで掘削された宝物をコインに換金できる
    • コインの数＝最終スコア
    • 有料ライセンスはコインを消費する＝最終スコアも減る

詳細は以下をご参照ください。

やったこと

以下、ネタバレ含みます。

  • 公式のpython実装を元にgolang実装で書き換え
  • ライセンスを10個取得して並行処理
  • 「探索」「掘削」「ライセンス取得」「換金」をそれぞれgoroutineにしてchannelで受け渡し
  • channelのcapを抑えめにすることで無駄なHTTPリクエストが発生しないように調整
    • それぞれの処理を複数workerを構成に
  • 有料ライセンスを使用してレイテンシ改善
    • ただし有料はコインを消費＝スコアが下がるのでいい塩梅を模索
    • コインが入手できるまでは無料ライセンス、入手できるようになったら1コイン消費で有料ライセンス
  • 1つのライセンスで複数回掘削できることから、ライセンスを掘削回数分コピーして一斉に同時掘削
    • 掘削完了を検知するためにsync.WaitGroupを活用しまくる
  • 4x4や8x8など広めの範囲から枝刈り全探索で効率化
    • 試行錯誤の結果、1x10、1x15、2x7あたりが何故か効率が良かったので採用
  • GOGC=off
  • ライセンス取得のレイテンシがボトルネックになるのでPOST /digのHTTPリクエストを投げた時点でライセンス取得を行う
  • net/http/httptrace.ClientTrace.WroteRequest を使って最速再取得を試みる
    • しかしWroteReuqestではエラー多発。GotFirstResponseByteであればエラーはなくなるものの改善効果なし
  • encoding/json を github.com/goccy/go-json に置き換え
    • go build 時のメモリ消費がネックに
    • 簡易なJSONは自力の文字列処理でencode/decodeすることでさらに軽量化
  • net/http を github.com/valyala/fasthttp に置き換え
    • CPU負荷は下がったがCPUがボトルネックになってなかったのであまり効果はなかった
  • HTTP Keep-Aliveが無効になっているので事前に net.Dial を行うことで自前コネクションプール
    • 思いついたときは勝利を確信したもののあまり効果はなかった

スコア上位がやっていた（らしい）こと

公式Telegramでの事後チャットを眺めていたのですが、こんな感じみたいです。

  • Battle-roundは宝物の配置が固定なため配置をハードコードして探索処理をスキップ
  • Final-roundはハードコード対策が行われたものの、サーバサイドがgolang実装なのを考慮して疑似乱数生成(PRNG)の使われ方を推測、宝物の配置パターンからSEEDを特定することで探索処理をスキップ

いやーこれは度肝抜かれましたね。主催側もここまですることを想定していなかったようです。まじかよスゲーなロシア。

ソースコード

サーバサイドのソースコードは全日程終了後公開されたので手元環境で再現可能です。わいわい。 https://github.com/All-Cups/highloadcup/tree/main/goldrush/server

まとめ

今回はHTTPクライアントを実装することもあって、これまでISUCONなどで培ってきたWebサービスに関する知識が生かせず苦労したのですが、その分HTTPクライアントに関する知見を多く得られたこと、またgoroutine、channel、syncパッケージを使った並行処理の良い練習になりました。今後どこかで活かせるといいですね。