詩と創作・思索のひろば

ドキドキギュンギュンダイアリーです!!!

Fork me on GitHub

ISUCON7本戦で3位でした(ソン・モテメン・マサヨシ)

いろいろあって、本戦からだいぶ時間が経ってしまいました。チーム全体としての流れはSongmuさんが書いてくれているので、自分の視点でどうだったかな〜というのを時系列を無視して思い出しつつ書きます。

チームは、会社(はてな)の同僚で組んだ Songmu, masayoshi, motemen の3人。全員の名前からとって「ソン(ムー)・モテメン・マサヨシ」です。おしゃれ。リポジトリはここ

本戦の問題は Cookie Clicker をモデルにしたもの。競技の開始まですこし時間の余裕があったので、その間にオリジナルをプレイして、アプリケーションの仕様を学習した。話題になったときに遊んでなかったので、このとき初めてやったんだけど、たしかに中毒性がありそう……。

Cookie Clicker のほうは放置しつつ方針の相談。まあルームごとにサーバを割り当てて、オンメモリでやってく感じだよね、というのですぐに落ち着いた。ソースコードを読んだところ、ゲームのコア部分がえらく複雑そうで、ここはあんまり触りたくないなあという気持ちになってしまった(これがよくなかった)。

ともあれ MySQL の仕事をなくしていこう、ということで、効果はとくに期待せず、まずは肩慣らしにアイテム情報をハードコード。たしかその間に Songmu さんがルーム名のハッシュ値から振り分け先のサーバを決定するロジックを書いてたと思う。このとき Songmu さんがなんか単語をド忘れしてたらしく、「サーバをアレにする」「アレですよね」みたいな会話をしたんだけど、ちゃんと意図が伝わってたので面白かった。

想定どおり振り分けでスコアはあがるんだけど、ベンチマーカの振り分けが偏ってしまうとスコアに大きく影響があるので、競技中はもっぱら1台構成でスコア測定を安定させ、最後に4台構成でバーンとスコアを上げるという作戦をとった。あとサーバの振り分けも最終的にはラウンドロビンになった。

さて MySQL やめてオンメモリにするか、と考えていたころに masayoshi がアプリケーションがボトルネックですねー、と教えてくれたので、ついに出番だ! ということで go-torch によるプロファイリング を仕込んだ。予選のときも pprof と go-torch だけは使い方を覚えておこう、と準備していたものの出番がなかったのだ。結局アプリケーションのボトルは解消できず、MySQL は最後まで残った。

プロファイリングしてみると calcStatus と、その中の math/big 周辺の処理の重いことが見てとれたんだけど、ここでけっこう停滞してしまった。calcStatus をなんとかしないことにはスコアが上がらないことはわかっているんだけど、時間のかかる取り組みになることも見えていて、躊躇する気持ちが勝ってしまっていたのだと思う。例えばキャッシュを入れたとして、ここでロジックを壊してしまったときに検証するのが大変そうだなーという思いが先にきてしまうという……。

結局有効だったのは、クライアントからのアクセスごとにいちいち getStatus するのじゃなく、ルームにつきひとつだけ getStatus 計算用の goroutine を用意して、それを各クライアントに配るような形にしたことだった。これで math/big 周りの呼び出し回数を少し減らすことができ、スコア増につながった。最初チャンネルの close など雑に書いていたらリークしまくってたけど、おおむねすんなり実装できたのでよかった。

ちなみにこの方法は methane さんにコメントをもらっていて(Songmu さんの記事に対して)、

なるほどたしかに。もうちょっと周辺のコードを見ておけばよかった……。そういうコード理解の低さが今回の伸び悩みの原因だったなと思う。

閑話休題。あらためてプロファイリングすると、今度は GC の占める割合も大きくなってきていた。この時点で残り時間も心もとなかったので、パラメータ調整だけで容易にスコアの伸びが狙える GOGC 調整に手をつけはじめた。これは最初 GC 切ってみたらめちゃくちゃスコアが下がって(だったか、リソースを異様に食うようになったのだったかで)大笑いしてしまった……。GC 頻度を減らすことで、これでもそれなりにスコアが伸ばせた。

再起動後、ベンチガチャをしていたらいい点数が出たので各自ブラウザを閉じてフィニッシュ。個人的には最高順位の3位だったけど、賞金獲得はならず。終わってみるとやはり calcStatus がキモで、そこに真正面から取り組む気持ちを持てたかどうかが勝敗の分かれ道だったなー、と思った。しかしキャッシュ入れて fail したチームも多かったみたいで、難しい選択には違いなかったのだと思う。

今回の ISUCON は予選からすごく楽しませてもらったし、そのぶん運営は大変だったと思います。こんなイベントが年一で体験できるのは運営の皆さんのおかげで、感謝しかない。お疲れさまでした。そして来年も100万円ほしいでしゅ!

チャンネルを使って、決まった数のリソースをgoroutine間で共有するパターン

生成が重いリソース(や重い処理の実行権)を goroutine 間で共有し使いまわすようなパターンです。よく知られていて名前がついていそうだけど、ぐぐっても分からなかったので書いておく。

コネクションプールに近い感じで、最初にリソースを生成したあと、それらを大事に取り回します。リソースが空いてなかったら goroutine は待つことにする。sync.Pool は「プールにあったら使うけど、なかったら新しく作る」くらいの感じなので、ちょっとスタンスが違う。

チャンネルによる実装は簡単で、以下のエントリにも書いたセマフォを応用すればよい。

ざっくりと書いてみた例がこちら: https://play.golang.org/p/QWAXsA_89Y

チャンネルによるセマフォの実装は、「バッファありチャンネルに何か(struct{})を挿入できた goroutine が実行の権利を持つ」というものでしたが、今回は「バッファありチャンネルからリソースを取得できた goroutine がリソースの権利を持つ」というふうになっています。

最初にリソースのプール(チャンネル)を作り:

pool := make(chan *worker, 5)
for i := 0; i < 5; i++ {
    pool <- &worker{i}
}

各 gorountine では、リソースをプールから取得。リソースを使い終わったらプールに戻します。プールに戻すまではリソースを占有できていることが保証されています。

    case w := <-pool:
        w.work()
        pool <- w
    }

リソースを取得しようとするとき、空いているものがなければブロックするので、セマフォの上位版ということになりますね。

最近のGoプロジェクトのMakefile

最近は仕事でも新しくGoのプロジェクトをイチからはじめることが増えてきて、コピペ元が欲しくなるので、スナップショットとして残しておきます。とくに Go でウェブアプリケーションを書くような場合を想定していて、npm エコシステムにも乗っていきます。

大まかな方針としては、

  • self-contained である
  • グローバルな環境を汚染しない
  • コマンド一発で開発環境が再現できる

……というところを目指します。

motemen/prchecklist がこれを達成しているつもりなので、以下、これを例に見ていきます。

依存ライブラリは dep なり何かしらのツールと Go 標準の vendoring で管理すればよい一方、そのツール自体であったり、他の開発中に必要なツール(golint とか gobump とか)であったりのインストールをどうするかという話。

npm であれば devDependencies というやつでうまいことやってくれますが、現行の Go の依存管理ツールではデファクトがない、というか依存管理ツールのデファクトが(少なくとも自分の中では)まだ定まってないので、これを Makefile でやる必要がある。

かといって依存ツールを単純に go get してはグローバルな環境を汚染してしまうことになるので、npm を真似て Go 製ツールのバイナリを .bin/ 以下に置くことにします。以下のように GOBIN 環境変数を指定すれば、バイナリを作業ディレクトリ以下にインストールできます*1

.PHONY: setup-go
setup-go:
   GOBIN=$(abspath .bin) go get -v \
        gobin.cc/go-bindata \
        gobin.cc/reflex \
        gobin.cc/mockgen \
        github.com/motemen/go-generate-jsschema/cmd/gojsschemagen

gobin.cc を使えばすっきり。

最初に make setup-go しなくてもうまいこと動くように、依存関係をきちんと書いてやります。

.PHONY: test
test: lib/web/web_mock_test.go
    ...

lib/web/web_mock_test.go: lib/web/web.go .bin/mockgen
    .bin/mockgen -package web -source $< GitHubGateway > $@

.bin/%: Makefile
    @$(MAKE) setup-go
    @touch $@

テストがモックのソースコードに依存し、それがさらに .bin/mockgen に依存するように宣言しています。そして .bin/ 以下のファイルは先ほどの setup-go タスクで生成するよう指定します。.bin/% の依存先として Makefile を書いているのは、go get するパッケージの一覧が Makefile に書いてあるから。

ここに書いたのとまったく同じ方法で npm パッケージ向けの設定も書けますが、その場合は

node_modules/.bin/%: package.json

のように書けばいいわけです。

このようにして、gonpm または yarn さえ入っていればだいたい再現可能な開発環境が作れました(だいたいというのは、Go ツールに非互換な変更が入ったときに壊れる、という懸念があるよね、というところです)。

余談になるけれど、Go ソースコードの watch & build にこれまでよく entr を使っていて、これが大変便利なんですが、パッケージマネージャによるユニバーサルなインストール方法というのがなく、このエントリに書いたような再現可能な環境を作るために Go 製の reflex を使ってみました。

ls **/*.go | entr -r sh -c '...'

reflex -r '\.go\z' -s -- sh -c '...'

になる感じで、汎用的に使えるツールです。わりとよさそう。

*1:$GOPATH/pkg は汚染されますが。これは自分にとっては問題にならない

はてなで一緒に働きませんか?