ISUCON8 本選出題記あるいはISUCONベンチマーカー負荷調整の歴史

ISUCON 8 の本選出題を同僚の @ken39arg と担当しました。参加された皆様、運営にご協力して頂いたすべての関係者の方々にお礼申し上げます。

恒例の #isucon pic.twitter.com/iXAjgfgbeZ
— fujiwara (@fujiwara) 2018年10月20日

問題についての講評は公式の ISUCON8 本選問題の解説と講評をご覧頂くとして、こちらでは今回、出題に導入された新要素である「シェア機能」について、どういう経緯で導入されたのか、裏話的なことを書いておきたいと思います。

「ベンチマークの負荷を自分で決めるのも、自動で際限なく負荷が上昇するのも実際のアプリケーションとは違うよね?」というところから思いついた機構なのですが、経緯についてはいろいろな前提と、歴史の理解が必要になります。結果的に長文になってしまいました。

ISUCONベンチマーカーとは

ISUCON という競技は、あらかじめ与えられた所定のアプリケーションに対して、運営が用意したベンチマーカーと呼ばれるホストから (HTTPなどの) リクエストが送信され、そのリクエストをどれだけ処理できたのかによってスコアが決定します。

ベンチマーカーのリクエストに一定時間応答できなかったり、アプリケーション的な不整合を検出したり、エラーを多数返したりすると、ベンチマークは失敗します。その状態を「fail」と呼び、スコアは 0 となります。

初期状態のアプリケーションには様々な問題が(ほぼ意図的に)仕込まれていて、それを解消したり、よりよいコード、構成、OSやミドルウェアの設定変更を行うことでスコアを上げていく、というのが競技のメイン要素です。

チューニングによりどれぐらいスコアが向上するのかは回によって異なりますが、今年の本選の場合は初期状態でのスコア 500 程度から、競技中の最高スコアで 50,000 程度、あらかじめ検証した時点では 100,000 以上まで、つまり200倍以上に上げることが可能です。

ここで難しいのは、「極端に遅い初期状態」と「チューニングが進んで100倍高速化された状態」のどちらに対しても、成功(pass)してスコアが残るベンチマークを行う必要がある、ということです。

初期の遅い状態のアプリケーションに多くのリクエストを送りすぎるとタイムアウト等で fail しますし、かといって高速なアプリケーションに送るリクエストが少なすぎると、スコアの差が出なくなる可能性があります。

原理的には初期でスコアが出ない状態で競技を開始することも可能ですが、競技者が行った変更が有効だったのかは基本的にスコアで判断するしかなく、初期スコアが 0 の場合は何が有効なのかを暗中模索することなります。これは非常にストレスが掛かる状態のため、初期状態でスコアが記録され、かつ何らかの有効な手を打つとスコアが向上する、というベンチマークを作成することが望ましいことになります。

ベンチマーカーの負荷調整の歴史

ここで歴史を紐解きます。

ISUCON1, ISUCON2 の時代は予選がなく、本戦であらかじめ複数台に配置されたアプリケーションで競技を行っていました。この時点では、ベンチマーカーは特に動的に負荷を増やすということはしていなかったと記憶しています。

workload 指定時代

ISUCON3 の出題を自分が担当することになり、予選が導入されました。

この当時の予選(4まで)は、AWS (Amazon Web Services)上で各競技者がアプリケーションとベンチマーカー(Goで実装されたバイナリのみ)が配置されたインスタンスを1台起動し、ローカルホスト上でベンチマークを実行する形態で行われました。

ベンチマークコマンドに -workload という引数があり、その引数を変えることで負荷を増加させることができるようになっていました。

これは、チューニング後のアプリケーションに対しても十分な負荷を供給するためのギミックだったのですが、いくつかの問題がありました。

競技者が十分に高速化されていないアプリケーションに対して workload 値の試行錯誤をしてしまう
- workload=1 でスコアが出た上で、CPU等のリソースに余裕があるようならば値を増加させていく想定でした
- その意図を読み取れない競技者が、workload の調整で時間を無駄にしてしまうことがありました
逆に、workload の指定に気がつかない競技者が、負荷を増やせないのでスコアを上げられない
ISUCON4 の予選においては workload に異常に大きな値を指定することにより、ベンチマークが規定時間になっても終了せず、不正に高いスコアを出すことが可能でした
- ISUCON4 本選出場の一部基準変更についての詳細

それを受けて、ISUCON5 では workload が廃止され、競技者が任意の負荷を与える形ではなくなりました。

ちなみに自分は 5 で優勝をしているのですが、どのように初期でもチューニング後でも通る調整がなされていたのか、全く理解していません…このへんは出題した @tagomoris さん、@kamipo さんに今度教えてもらいたいところです。

自動負荷増加時代

ISUCON6 予選には、5と同様に負荷調整機構がありません。ただし、初期言語実装の7種類のうち、4言語でスコアが出ない状態で提供されていました。

ISUCON6 本選から、自動的に負荷が増加する機構が導入されました。

isucon6-final/matsuri.go at 6b7e659f3de2f455b1f76bf27531534a20f0f79f · isucon/isucon6-final · GitHub

// watcherIncreaseInterval秒おきに、 (まだ退室していないwatcherの数 - 既に退室したwatcherの数) の人数が入室する

タイムアウトするとユーザー(ベンチマーカーが与える負荷)が減り、5秒おきにユーザー(=負荷)が増えていく、という機構です。これは特に競技者へは伝えられていなかった仕様ですが、負荷の様子を観察していれば認識できるものでした。

その後、ISUCON7では1秒おきに、エラーが発生したり、レスポンスタイムが遅くなったりしていなければ負荷が増加するという機構になります。これはユーザに示されるベンチマーク実行結果にも「負荷レベルが上昇しました」「エラーが発生したため負荷レベルを上げられませんでした」というログにより、明示されるようになりました。

今回の ISUCON8 予選は、基本的に 7 の仕様が踏襲されていました。

自動負荷増加の問題

今回8本選の出題にあたり、自動で負荷が際限なく上がることについての問題意識が自分の中にありました。

レスポンスを返せば返すほど負荷が上昇してしまうと、最終的にはアプリケーションは負荷に耐えきれずに fail する状態になってしまいます。ベンチマーク走行時間が 60 秒であれば、60秒ギリギリでも死なない (しかしたとえば70秒走らせたら死ぬ) 状態に持っていくのがベストということになりますが、そのために意図的にエラーを返したり、レスポンスを遅らせるというのはかなり本末転倒感があります。

また、8の予選マニュアルには以下のような記述があります。

各ステップで失敗が見付かった場合にはその時点で停止します。ただし、負荷走行中のエラーについては、タイムアウトや500エラーを含む幾つかのエラーについては無視され、ベンチマーク走行が継続します。

負荷が際限なく上昇するために、負荷走行中のタイムアウトやエラーを原因として失敗させることができなくなってしまうのです。

ベンチマーカー(=ユーザー)に対してタイムアウトや500エラーをいくら返しても咎められない、というのは、アプリケーションを提供する側の意識としては望ましくないのでは、と思ったわけですね。

そのあたりを解決する方法は何かないか……

SNS シェア機能の発明

負荷を何らかの方法で競技者にある程度コントロールさせたい、けど明示的に数値を与えるのは違う、というのを解決する立て付けを考えて、予選の競技終了後の運営打ち上げの場でふと思いついたのが「SNSシェア機能」でした。

アプリケーションの機能により、特定の条件下でSNSでシェアが行われ、新規ユーザーが増加することで負荷が増加する
増加率はシェア機能の on/off を AB テスト的にコントロールすることで調整可能
ある時点でシェアを無効にすることで、際限のない負荷上昇を防ぐことが可能

ABテスト的に一部のユーザだけ(もしくは確率的に)有効にする、というのが思いつかない人も多かったようですが、一部の人は気づけていたので、そこは発想と経験ということで競技の要素になっていたと思います。

チューニングが進んだ状態での最適解は、まずシェアを全力で行い急速にユーザを呼び込みつつ、アクセスしているユーザ数や負荷をモニタリングし、負荷的に耐えきれる限界の人数になったらシェアを無効化する、というものになります。現状のリソースで耐えられるところを見極める、というモニタリング要素も競技要素としてありかなと思います。

また、今回のアプリケーションは基本的に JSON API のみのアプリケーションなので、以下のようなエラーの扱いをしています。