isucon9q_bench.md

ISUCONのベンチマーカーとGo

catatsuy メルカリSRE

mercari.go #11 - connpass https://mercari.connpass.com/event/148913/

ISUCONとは

http://isucon.net

• お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル
• 競技者は与えられたWebアプリケーションを高速化する
  • 複数の言語による実装（ISUCON9予選ではGo/Perl/PHP/Ruby/Node.js/Python）を運営側が用意する
• ベンチマークを実行するとアプリケーションに対して仕様確認・負荷走行をしてスコアが出力される

私とISUCON

• ISUCON4：2位（初出場）
• ISUCON5：8位
• ISUCON6：運営（本選）
• ISUCON7：予選敗退
• ISUCON8：3位
• ISUCON9：運営（予選）

他にもpixiv社内ISUCON https://github.com/catatsuy/private-isu を作りました（ISUCON6の年）

• 社内ISUCONを公開したら広く使われた話 - pixiv inside [archive] https://devpixiv.hatenablog.com/entry/2016/09/26/130112

ISUCON9予選おさらい

ISUCON9 予選問題の解説と講評 : ISUCON公式Blog http://isucon.net/archives/53789931.html

• 椅子を売りたい人／買いたい人をつなげるフリマアプリ「ISUCARI」
• 「決済サービスAPI」「配送サービスAPI」という2つの外部サービスがあり、購入や配送の際にアプリケーションからこれらのAPIと通信を行う
• 新着商品タイムライン、カテゴリ・ユーザごと商品一覧、取引をしている商品一覧や商品詳細といったページがある
• スコアは売上額から算出される

今回のテーマ

• ISUCON9予選のベンチマーカーを題材にアーキテクチャやGoの書き方などを中心に説明
• 私がISUCON9予選のためにやったことについては以下の記事に詳しく書いたので是非読んでみてください
  • ISUCON9予選の出題と外部サービス・ベンチマーカーについて - catatsuy - Medium https://medium.com/@catatsuy/isucon9-qualify-969c3abdf011
  • 今回の発表資料も一部内容が重複しています

競技者にとって嬉しいベンチマークとは

• 実行したいときにすぐに実行できる
• 仕様が壊れていたらどこが壊れているのかちゃんと説明してもらえる
• アプリケーションに必要十分な負荷をかけてくれる
• 実装が同じならほぼ同じスコアを常に安定して出してくれる（ガチャ感がない）

ISUCON9予選ベンチマークのアーキテクチャ

• 過去のISUCONで起こった様々な問題を解決するためにISUCON5以降からほぼ同じアーキテクチャ

参考数値

参加チーム数

• 9月7日（土） 321組（755名）
• 9月8日（日） 277組（680名）

worker台数：40台

cf: http://isucon.net/archives/53786743.html

benchmarkerの心得

benchmarkerは

• リソース（メモリ・コネクション etc）がリークする
• 考慮漏れがある
• ロジックにミスがある

を前提にしたアーキテクチャにする

workerとbenchmarkerを分ける理由

• benchmarkerはリソースがリークするのでworkerからexecして都度死ぬように作る
  • benchmarkerを普通のCLIツールとして開発できるので開発も楽
• benchmarkerはファイルを差し替えるだけで、次回実行時から新しいバイナリで実行できる
  • benchmarkerがバグっていても、すぐにデプロイして差し替えられる
• benchmarkerが想定しないバグで終了しない可能性があるので、一定時間以上実行されたらworkerからkillしたい
  • benchmarkerは複雑なアプリケーションなので、異常時は外側の別の仕組みから殺したい

workerが担保する仕様

• portalにあるジョブキューのエンドポイントをpolling
• benchmarkerを適切なオプションで実行する
• benchmarkerを1つだけ実行することで仮想マシンのリソースを1つのbenchmarkerに占有させる
  • 他の競技者のせいでスコアが出にくくなる事態を避ける
• 一定時間以上終了しない場合はkillする
  • benchmarkerが暴走している可能性が高いので外から殺す
• benchmarkerの出力するスコアなどの情報をportalに送る
  • 標準エラー出力も送る（後述）
• 終了ステータスが非0の場合はbenchmarkerがpanicしているので運営・競技者共に異常であることが分かるようにする
• benchmarkerよりも圧倒的にシンプルなプログラムなので基本は死なない前提
  • とはいえportal側は一定時間以上レスポンスが返ってこない場合を想定するべき
• ファイルディスクリプタの上限値を上げる
  • 子プロセスにも適用されるのでbenchmarkerの上限値も上がる
• ISUCON9予選ではbench-workerという名前で実装

アプリケーションとしてのbenchmarker

• 複数のシナリオに沿ったリクエストとレスポンスの検証を並行に行う
  • 並行プログラミングを頑張る必要がある
  • contextで全てのシナリオとリクエストが殺せるように
• 初期データ・現在のデータがどうなっているかを管理する
• 競技者のアプリケーション側のチートを検出できるようにする
• 遅い初期実装に対しても、速い最適化された実装に対しても適切な負荷をかけて適切なスコアを出せるように

CLIツールとしてのbenchmarker

• IPアドレスなどの必要な情報をオプションとして受け取る
• 標準出力にスコアなど必要な情報を決められたフォーマット(JSON)で出す
  • 競技者に見せたいメッセージも出力する

type Output struct {
	Pass     bool     `json:"pass"`
	Score    int64    `json:"score"`
	Campaign int      `json:"campaign"`
	Language string   `json:"language"`
	Messages []string `json:"messages"`
}

https://github.com/isucon/isucon9-qualify/blob/master/cmd/bench/main.go#L22-L28

• ベンチマークが実行できれば基本は終了ステータス0で終了する
  • 終了ステータスが非0の場合は基本panicしている
• 標準エラー出力は何を出しても良い
  • 標準エラー出力はportal上で運営だけが見れるようにしておくとトラブル時に原因調査できる
  • panicしたときのログも見れる

benchmarkerのpackage構成

• cmd/bench/main.go
  • main関数
• bench/asset
  • 初期データ・現在のデータの管理。リクエスト生成やレスポンス検証に使われる
• bench/fails
  • morikuni/failureを前提にして競技者に見せるエラーメッセージを管理する（後述）
• bench/scenario
  • シナリオを管理。触る必要がある変数も多い上に、とにかく複雑になる
• bench/server
  • 外部サービスを管理
• bench/session
  • アプリケーションにリクエストを送って、レスポンスの簡単な検証やJSONの解釈などを行う
  • contextを渡せるようにしてcontextで外から殺せるようにする

benchmarkerのフェーズ

• いくつかのフェーズに分けて、どこかで失敗したら即終了するようにする
  • 明らかにおかしいレスポンスを返しているアプリケーションはさっさと停止する
  • worker台数よりも競技者の方が圧倒的に多いので早めに終了しないとキューが詰まってしまう
  • ちなみにこの仕組みが導入されたのはISUCON7予選から
• アプリケーションの仕様確認などの考慮すべき事項が整理できる
  • 最初に厳密にチェックしておけば、その後の確認はある程度割り切れる
• メインのフェーズ内でアプリケーションが正しく動いているか常に確認するcheckと、最低限の確認で負荷をかけるloadを動かす
  • 理想的には全リクエストを確認するべきだが、それをやるとbenchmarkerのパフォーマンスが出し切れず、最適化されたアプリケーションよりも遅くなる可能性がある
  • checkとloadは競技者から区別できてはいけない
  • 過去にloadのリクエストはログアウト状態しかなかったので、ログアウト時のキャッシュを強くするだけでスコアがはねる問題があった
  • checkとloadを別の仕組みで行う場合はHTTPヘッダーの順番などで気付かれる可能性がある

ISUCON9予選benchmarkerのフェーズ

• initialize
  • 初期化リクエストを送る
  • /initializeにリクエストを送ることで、外部リソースのURLを指定する・DBのデータを初期データのみにする
• verify
  • 初期チェック：正しく動いている確認する
  • ここで失敗したらメッセージを出して即終了する
• validation
  • メイン処理：checkとloadの大きく2つの処理を行い、動作確認するgoroutineと負荷をかけるgoroutineを起動する
  • 1分経過したらcontext経由ですべてのリクエスト・シナリオを殺す
    • スコア計算などに影響があるため
• final check
  • 最終チェック：ベンチマーカー側の記録とアプリケーションの/reportsの記録を付き合わせて最終的なスコアを算出する

https://github.com/isucon/isucon9-qualify/blob/master/cmd/bench/main.go#L104-L182

benchmarkerで考えなければならないこと

• 返すべき情報を返しているかチェック
  • チェックしていないものは全部チート可能なのでチェックする必要がある
  • 情報が返ってきている前提のコードを書くとnil pointer dereferenceやindex out of rangeなどでpanicする原因となる
  • 異常系の動作を完璧に実装するのは無理なので、簡単にデプロイできるようにして都度直せるようにする
• 厳密にチェックしすぎると誤判定が起こる
  • リクエストとレスポンスの間に更新が入った場合は古いデータが返ってくるので厳密にチェックするとエラーになる
• シナリオは以下の点に気をつける
  • 時間が来たらシナリオとリクエストを確実に殺す
  • 単なるfor文にするとエラー時や何らかの穴を突かれて暴走する可能性があるので一定よりも早く動かないようにする
  • 最適化しにくい特定のパスの速度を落として、最適化しやすいパスへのリクエストを増やすチートができないように特定のgoroutineから一定以上のリクエストをしないようにしておく

https://github.com/isucon/isucon9-qualify/blob/master/bench/scenario/check.go#L14-L263

func Check(ctx context.Context) {
	var wg sync.WaitGroup
	closed := make(chan struct{})

	// 中略

	wg.Add(1)
	go func() {
		defer wg.Done()

	L:
		for j := 0; j < ExecutionSeconds/10; j++ {
			ch := time.After(10 * time.Second)

			s1, err = activeSellerSession(ctx)
			if err != nil {
				fails.ErrorsForCheck.Add(err)
				goto Final
			}

			// 色々やっていく

		Final:
			select {
			case <-ch:
			case <-ctx.Done():
				break L
			}
		}
	}()

	go func() {
		wg.Wait()
		close(closed)
	}()

	select {
	case <-closed:
	case <-ctx.Done():
	}
}

benchmarkerのエラー処理

• 運営は生のエラーを見たいが、競技者にはこちらで用意したメッセージを見せたい
  • 適切なメッセージは関数呼び出し元からは分からないので、実際にエラーが発生した箇所で都度メッセージを付与する必要がある
  • 運営はエラーが発生した箇所やコールスタックなど見れる情報は全て見たい
• 致命的なエラーなどエラーにも深刻度によっていくつか種類が必要
  • ISUCON9予選では『致命的なエラー』『HTTPステータスコードやレスポンスの内容などに誤りがある』『一定時間内にレスポンスが返却されない・タイムアウト』の3種類で扱いが異なる
  • https://github.com/isucon/isucon9-qualify/blob/master/docs/manual.md#スコア計算
• エラーが起こっても他の処理は続行されて、最後にまとめてメッセージを競技者に見せたい
  • エラー数によって減点・失格もある
  • Webアプリケーションとの最大の違いはここ

morikuni/failure

• Go製のアプリケーションのエラーハンドリングを簡単に扱うためのライブラリ
• Goのerrorに対してエラーコード・エラーメッセージを付与できる
  • コールスタックも出せる
• 機能が充実している
  • failure.New failure.Wrap failure.Translateでエラー生成・ラップ・変換ができる

https://github.com/isucon/isucon9-qualify/blob/master/bench/scenario/normal.go#L154-L163

if nextCreatedAt > 0 && nextCreatedAt < item.CreatedAt {
	return session.ItemSimple{}, failure.New(fails.ErrApplication, failure.Messagef("/new_items/%d.jsonはcreated_at順である必要があります", categoryID))
}
if item.Category == nil {
	return session.ItemSimple{}, failure.New(fails.ErrApplication, failure.Messagef("/new_items/%d.json のカテゴリが返っていません (item_id: %d)", categoryID, item.ID))
}

if item.Category.ParentID != categoryID {
	return session.ItemSimple{}, failure.New(fails.ErrApplication, failure.Messagef("/new_items/%d.json のカテゴリが異なります (item_id: %d)", categoryID, item.ID))
}

https://github.com/isucon/isucon9-qualify/blob/master/bench/session/webapp.go#L268-L278 https://github.com/isucon/isucon9-qualify/blob/master/bench/session/webapp.go#L286-L298

req, err := s.newGetRequest(ShareTargetURLs.AppURL, "/settings")
if err != nil {
	return failure.Wrap(err, failure.Message("GET /settings: リクエストに失敗しました"))
}

req = req.WithContext(ctx)

res, err := s.Do(req)
if err != nil {
	return failure.Wrap(err, failure.Message("GET /settings: リクエストに失敗しました"))
}
// 中略
rs := &resSetting{}
err = json.NewDecoder(res.Body).Decode(rs)
if err != nil {
	return failure.Wrap(err, failure.Message("GET /settings: JSONデコードに失敗しました"))
}

if rs.CSRFToken == "" {
	return failure.New(fails.ErrApplication, failure.Message("GET /settings: csrf tokenが空です"))
}

if rs.User == nil || rs.User.ID == 0 {
	return failure.New(fails.ErrApplication, failure.Message("GET /settings: userが空です"))
}

参考URL

• エラー設計について / Designing Errors - Speaker Deck https://speakerdeck.com/morikuni/designing-errors
• https://github.com/morikuni/failure

morikuni/failureとfails

• morikuni/failureで生成されたエラーを今回用意したfailsで集めてスコア算出と最終的なメッセージを生成する
• failure.StringCodeでエラーの種類を表現

https://github.com/isucon/isucon9-qualify/blob/master/bench/fails/fails.go#L10-L19

const (
	// ErrCritical はクリティカルなエラー。少しでも大幅減点・失格になるエラー
	ErrCritical failure.StringCode = "error critical"
	// ErrApplication はアプリケーションの挙動でおかしいエラー。Verify時は1つでも失格。Validation時は一定数以上で失格
	ErrApplication failure.StringCode = "error application"
	// ErrTimeout はタイムアウトエラー。基本は大目に見る。
	ErrTimeout failure.StringCode = "error timeout"
	// ErrTemporary は一時的なエラー。基本は大目に見る。
	ErrTemporary failure.StringCode = "error temporary"
)

• errorが発生したらfailsでAddしていく
• 標準エラー出力は運営側が好きに出していいのでコールスタックを含めて標準エラー出力にPrintする
• エラーの種類によってメッセージを変えると競技者に減点内容が分かりやすいのでエラーコードによってメッセージを一部変更
• エラーコードを付与し忘れた箇所があるのでエラーコードが無ければErrApplication扱いにしている
• エラーメッセージが付与されていないエラーは実装ミスなので競技者に連絡してもらう文言を出力している
• エラー数によってスコアが変わるのでエラーコード毎の数をカウントしている

https://github.com/isucon/isucon9-qualify/blob/master/bench/fails/fails.go#L64-L100

type Errors struct {
	Msgs []string

	critical    int
	application int
	trivial     int

	mu sync.Mutex
}

func (e *Errors) Add(err error) {
	if err == nil {
		return
	}

	e.mu.Lock()
	defer e.mu.Unlock()

	log.Printf("%+v", err)

	msg, ok := failure.MessageOf(err)
	code, _ := failure.CodeOf(err)

	if ok {
		switch code {
		case ErrCritical:
			msg += " (critical error)"
			e.critical++
		case ErrTimeout:
			msg += "（タイムアウトしました）"
			e.trivial++
		case ErrTemporary:
			msg += "（一時的なエラー）"
			e.trivial++
		case ErrApplication:
			e.application++
		default:
			e.application++
		}

		e.Msgs = append(e.Msgs, msg)
	} else {
		// 想定外のエラーなのでcritical扱いにしておく
		e.critical++
		e.Msgs = append(e.Msgs, "運営に連絡してください")
	}
}

適切な負荷をアプリケーションにかけるには

• ISUCONのベンチマークは遅い初期実装に対しても、速い最適化された実装に対しても適切な負荷をかけてスコアを出す必要がある
• 過去のISUCONのベンチマーカーにはworkloadという仕組みで負荷を競技者側が調整できる仕組みがあった
  • これはベンチマーカーを作る側からすると入力された数値で負荷を調整すればいいのでやりやすい仕組みだが、競技者側からすれば何を意味するかわかりにくいという欠点がある
• ISUCON6本選で初めて採用されたのが、自動でリクエスト数が増えていき、タイムアウトが出たら減らす仕組み
  • これと似た仕組みはその後の歴代の出題でも採用された
  • しかしこの仕組みはタイムアウトエラーが発生するまでリクエスト数を増やし続けるので、タイムアウトエラーを避けることはできない
  • 閾値を超えるかどうかで負荷が大きく揺れるので、スコアが安定せず、再現性が低いスコアを出してしまう
  • 特に今回の予選の問題の場合、リクエスト数を増やした瞬間にタイムアウトエラーが頻発する現象があり、自動で負荷を増やしていく仕組みを用意することは困難だった
• 今回はキャンペーンとして与える数値で負荷をかけるgoroutine数を増やす仕組みに
  • これによってベンチマーカーよりもアプリケーションが早くなった場合にスコアが頭打ちになる問題は起こるが、その代わりに安定したスコアを出すことができる
  • 今回は「人気者出品」という別のイベントも発生していた（後述）

https://github.com/isucon/isucon9-qualify/blob/master/bench/scenario/scenario.go#L66-L76

if campaign > 0 {
	log.Printf("=== enable campaign rate setting => %d ===", campaign)
	for i := 0; i < campaign; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			<-time.After(time.Duration((i+2)*100) * time.Millisecond)
			log.Printf("- Start Load worker %d", i+3)
			Load(ctx)
		}(i)
	}

参考URL

• ISUCON8 本選出題記 あるいはISUCONベンチマーカー負荷調整の歴史 - 酒日記 はてな支店 https://sfujiwara.hatenablog.com/entry/2018/10/25/084543

人気者出品

• キャンペーンを有効にするとbenchmarkerで発生するイベント
• 1人のユーザーが高額の出品をして、その商品を大量のユーザーが購入しようとする
  • 成功すればサービスの信頼性が上がって商品単価が上昇する
• 機能要件は以下
  • 複数のユーザーが購入に成功したらcritical error扱いにする
  • 全員が失敗したらapplication errorで減点
  • 一定数が失敗したら商品単価は上がらない
• 並行処理としては人気者出品が今回のbenchmarkerの実装で一番おもしろいと思います

https://github.com/isucon/isucon9-qualify/blob/master/bench/scenario/campaign.go#L132-L237

ISUCONとHTTPS

• ISUCONは競技者が各自アプリケーションを起動する性質上、証明書を用意するのが困難
• ISUCON6本選がISUCON史上初HTTPSを採用した回だったが、オレオレ証明書だった
• ISUCON8本選がHTTPSでかつ正当な証明書を採用
  • 本選でチーム数が限られていたのでワイルドカード証明書で各競技者に別々のドメインをDNSに登録することで対応していた
• 予選でHTTPSを採用したのはISUCON9予選が初
  • Let's Encryptで発行した正当な証明書 (isucon9.catatsuy.org)
  • 全競技者が同じ証明書とホスト名のアプリケーションを使用
• DNSに登録されていないので、benchmarkerはHostヘッダーとTLSのServerNameを明示的に指定する必要がある
  • req.Hostを書き換えるのと、http.TransportのTLSClientConfigのServerNameを指定する
  • Hostヘッダーはreq.Header.Set("Host", "example.com")しても上書きできないので注意

参考URL

• Goでproxy serverを作るときにハマるポイント - Mercari Engineering Blog https://tech.mercari.com/entry/2018/12/05/105737
• https://github.com/isucon/isucon9-qualify/blob/master/bench/session/new113.go#L21

ISUCONとhttp.TransportとHTTP/2

• http.TransportのTLSClientConfigは変更するとHTTP/2を使えなくなる
  • ISUCON6本選はnet/httpパッケージのコードをすべてコピーしてパッチを当てる男前実装にした
  • golang.org/x/net/http2のhttp2.ConfigureTransportを呼び出すのがかつては良かった
    • Goで証明書を無視するクライアントでHTTP2を使いたい - Qiita https://qiita.com/catatsuy/items/ee4fc094c6b9c39ee08f
  • Go 1.13から入ったForceAttemptHTTP2を今回は採用
    • 一番簡単で実装の差異を気にしなくて良い
    • しかしGo 1.13がリリースされたのはISUCON9予選の直前で、開発時にはまだリリースされていなかったので、build tagsを使ってGo 1.13の時だけ有効になるようにしている

https://github.com/golang/go/blob/eb4e5defb41459703c82b50d456280870ee00cb2/src/net/http/transport.go#L353-L382

func (t *Transport) onceSetNextProtoDefaults() {
	// 中略
	if !t.ForceAttemptHTTP2 && (t.TLSClientConfig != nil || t.Dial != nil || t.DialTLS != nil || t.DialContext != nil) {
		// Be conservative and don't automatically enable
		// http2 if they've specified a custom TLS config or
		// custom dialers. Let them opt-in themselves via
		// http2.ConfigureTransport so we don't surprise them
		// by modifying their tls.Config. Issue 14275.
		// However, if ForceAttemptHTTP2 is true, it overrides the above checks.
		return
	}
	t2, err := http2configureTransport(t)
	if err != nil {
		log.Printf("Error enabling Transport HTTP/2 support: %v", err)
		return
	}
	t.h2transport = t2

	// Auto-configure the http2.Transport's MaxHeaderListSize from
	// the http.Transport's MaxResponseHeaderBytes. They don't
	// exactly mean the same thing, but they're close.
	//
	// TODO: also add this to x/net/http2.Configure Transport, behind
	// a +build go1.7 build tag:
	if limit1 := t.MaxResponseHeaderBytes; limit1 != 0 && t2.MaxHeaderListSize == 0 {
		const h2max = 1<<32 - 1
		if limit1 >= h2max {
			t2.MaxHeaderListSize = h2max
		} else {
			t2.MaxHeaderListSize = uint32(limit1)
		}
	}

• http.Transportを都度生成しないとHTTP/2にしたときにコネクションがまとめられる
  • ISUCONのベンチマーカーはアプリケーションに対して負荷をかける必要があるので、都度コネクションを張りたい
    • ISUCONのベンチマーカーでGoのhttp.Clientをhttp2で使おうとしてハマった話 - Qiita https://qiita.com/catatsuy/items/bf3a1a5ffde1f5802d5a
• ちなみに今回のベンチマーカーは研修や練習などでも使いやすいようにHTTPでも問題なく動くようにしたので、TLSの証明書を用意しなくても動かせる
  • HTTP/2は動かない

おまけ：売り上げをスコアにした件について

• 例年はGET 1点、POST 5点、というようなリクエスト数に基づくスコア
  • 細かいところは例年違う
• ISUCON9予選はおそらく史上初リクエスト数に基づかないスコア算出方法になった
  • 実際のサービスでもレスポンスが遅ければ、サービスを使っている人がストレスに感じて離脱して売り上げが落ちるので、それをISUCONで表現したい
• 例年は各エンドポイントに対して適切なシナリオを作って適宜負荷をかけていけばいい感じのスコアを出せる
• しかし売り上げをスコアにしたということはGETのエンドポイントは加点にならないということ
  • 競技として成立させるにはリクエスト数が多いエンドポイントを適切に最適化すれば高いスコアが出るように作る必要がある
• 負荷をかけたいエンドポイントに対してリクエストを送って負荷をかけて、それが成功したら初めて売り上げに繋がるシナリオをいくつも作ることで実現
  • GETのエンドポイントを高速化すると売り上げ回数が増える→スコアが上がる
• 適切なシナリオを作らないとGETのエンドポイントを最適化してもスコアに変化が出なかったり、負荷をかけたいエンドポイントに対して負荷をかけきれないなどの問題が起こる
  • シナリオの完成度がbenchmarkerの質に直結する
• スコアの安定さには一切寄与しない
  • むしろシナリオの作成難易度が跳ね上がるので余程の自信が無ければ実装しない方が良い
  • 今回のbenchmarkerでは割とまともに動いているはずです

最後に

• ISUCONは過去の出題で起こったことを解決するためにアーキテクチャも進んできました
• benchmarkerはGoらしいプログラムを色々書く必要があります
• やることが多いので泥臭いプログラムですが、興味のある方は読むと楽しめると思います