ISUCON12予選作問ネタメモ - 酒日記はてな支店

ISUCON12が大盛況のうちに無事終わって早3ヶ月が過ぎました。もうすっかり冬ですね。

私はISUCON12の予選作問チーム(兼ポータル運用係)だったので、この記事ではISUCON12の予選作問に当たってチームでどのような出題を考えていたのか、没ネタ、やらなかったこと、やれなかったことを含めてざっくばらんに公開してしまいたいと思います。

予選に参加されたかたは、実際にどの要素が採用されていたのかなどを問題を思い出しつつ、ご笑覧ください。

アイディア出し

まず最初に、予選作問チーム全員で問題の要素ネタを出しました。

箱庭諸島(CGIゲーム)みたいなやつ
- データベースがファイルデータベース　- 初期実装がRDBじゃない　- ファイルロックが必要
- ユーザーアクセスのタイミングでターン進行処理がある(定期実行バッチの代わり)
  - これをどうにかするのも面白そう
確率的にエラーになる外部APIをなんとかするとかやりたい
- 確率を入れると1分では運ゲー要素がでちゃって微妙かも
外部コマンド呼び出し、初期は都度起動stdinから入力、stdoutから出力して終了
- だけど起動しっぱなしでstdinからストリームで流しこむことができるようになっているのでそうすると起動コストが0になる
データベースがsqlite
- 無闇に全部MySQL/PostgreSQLに持っていかないで、更新不要なmasterdataはそのままsqliteにすると複数台で参照がスケールするのでよいとか
- マルチテナントデータベース(同一スキーマのDBが大量にある
  - 掲示板を作るたびにcreate databaseするとか
  - ベンチ開始時のinitの初期化が難しそう
複数台かつ非同期が本質的な解決になる問題
- Goで単にgoroutineで解決されないやつがいいな
2014年頃に流行った技術スタックで「お買い得なサービスを買ってきたのねん、プロモするのねん」みたいなやつ
Railsとかに代表されるフルスタックなWAFで作って「さぁ軽くして…!」みたいなやつ
- 移植する言語によってどんだけ重いWAFとかORMになるかみたいなのがあるから言語差激しそう
既に十分速いんだけどさらに雑巾を絞りきらないといけないサービス
予選の問題を解いてもらって高速化したものを機能追加しつつ本選にだして「さらに速くして!」

そしてこれらの要素を元に、具体的な問題を3案ほど立案しました。

【案1】マルチテナントな給与計算システム

****(伏字) みたいなSaaS
複数DBは初のお題
- 3台あるので最初から分割した状態、1000個DBありまーす
- 最初から水平分割
- マルチテナント
  - テナントを作るとDB(SQLite)が1つ作成される
  - 複数台にするにはSQLiteをやめてMySQL / PostgreSQL にするか、ワールド単位で物理ホストを分配するか
全体の管理用DBも1個ある (これはMySQL?)
- 全テナント横断でクエリするなにか(検索とか?)がある
SaaSなのでアクティブユーザー人数課金の計算が必要
更新した人のログが各テナントのDBに格納されていてすべてのテナントを収集する必要がある
全テナントをロックかけないと総課金売上の数字に不整合が起こる
全テナントに対してALTER TABLEが掛かる
SQLアンチパターンで言うところのマルチカラムアトリビュートなテーブルがある
- 運営からのおしらせにタグカラムがあるみたいな
テナントごとにリクエストがflockで排他されることでデータ保護を保証する仕組みがある
- SQLiteをやめても安易に複数台にするとロックがかからなくなって壊れる
- 何か別の手段でロックするかDBのトランザクションをちゃんと使うか
- 初期はテナント単位で丸ごとロック
- ロックを細粒にすれば並列に動作できるようになる
テナントごとのアクセス量を公平にする必要がある
- テナント単位でレスポンスに掛かった時間を積算、単位時間当たりの消費が多ければ回復までブロックされるみたいなの
- レイテンシが大きいといっぱいアクセスできない = スコアが伸びない
定期実行ジョブがある
- ターン進行(n秒に1回)
- 初期状態ではリクエストが来たタイミングで、処理されていなかったものがまとめて実行される
  - これをちゃんとバックグラウンド処理にすると表のリクエストを阻害しない(低レイテンシ)
  - バックグラウンドでcacheを作って配信とかすれば更に低レイテンシに
  - 負荷増加の要素としてターン進行が最初が10秒に1回程度だったのがどんどんリアルタイムに近くなっていく
社員に入社順に連番を出す必要があり、しかも退職したら間を詰めないといけない

【案2】データの署名をするだけのマイクロサービス

テーマは「毎分cronをqueueにしてなんとかする」
ジョブキューになにを使うかなど選択肢は多そう
MySQLにインデックスやります、みたいな初手が意味なくなっちゃうから本選向きかも
POSTとGETのAPIが1個ずつあるだけ
- 画面とかないので動作確認用 cli のバイナリ(リファレンス実装)が提供される
マイクロサービスなのでクライアントはいろんなやつがいる
- リトライを exponential back off してくるやつ
- 即時リトライでひたすら爆撃してくるやつ
署名を作る方法は運営が提供したバイナリを動かすしかない
- 署名には有効期限がある(生成後10秒とか?)
マイクロサービスなのでmetrics機能がある
- 過去5秒間のtokenごとのリクエスト回数、署名発行回数、発行した署名のバイト数合計、署名が取得されるまでのレイテンシ(avg, p90, p95, p99)
- POST時にログテーブルにエントリ作成
- GET時にログテーブルを更新
- 管理API /api/metrics で集計結果を取得できる

【案3】ユーザークラスごとの優先度をちゃんと処理するpriority qeueu的な何か

案2と同様の「なにかを遅延処理して返す」サービス
無料ユーザー、プレミアムユーザーがある
free のアクセスはお金にならないのでスコアにならない、premium のアクセスだけスコアとする
free には所定の rate limit を掛けてよい
- 規約には書いてあるが手が回っていないので現状何もしていない、という設定が初期状態
- やるつもりだけはあるので、アクセスログをDBに毎回書き込んでいる
- 別の手段で適切な rate limit を掛けられるなら、DBに書き込む必要はない
premium は遅延処理のレイテンシに保証がある
- 「n秒以内に完了していること」
- 保証レイテンシを(error budget的な意味で一定以上)超過するとサービスとして障害 = 失格
freeユーザーはrate limitを食らうと一定確率でpremiumになってくれる
- しかし、レイテンシがfreeの時と変わらないことを観測すると、premiumを解約してしまう
- ちゃんとpremiumとfreeで優先度に差を付けてあげる必要がある
freeユーザーの処理も一定以上遅延すると障害
- 単に放置するのではだめで遅くてもちゃんと処理はしないといけない
負荷が増えすぎてレイテンシが保証できなくなりそうなら、premiumの登録をsuspendしてよい