ISUCON10予選を3位で通過しました (vs descending index)
2020年9月12日に行われたISUCON10予選にチーム FetchDecodeExecWrite で参加し、3804点、3位で通過しました!やったことを書いていきます。
要点
- Descending Index が効いていると思い込み、その誤りに最後まで気付かなかった。
- 椅子に似合う物件検索を色々分割して頑張った。大きい変更で苦労したがそこそこ役に立った。
ISUCON9予選をギリギリ通過しました
2019年9月8日に行われたISUCON9予選にチーム FetchDecodeExecWrite で参加し、10470点でギリギリ通過しました。やったことを書いていきます。
スコア遷移
10:00 競技開始
kcz さんがアリババクラウドと戦っているのを見て応援していた。
マニュアルを熟読したつもりだったが、タイムラインの内容をある程度自由に弄っていいことは最後まで気づかなかった。
2110点
〜10:40 準備
pprof とか MySQL slow query とかの準備をした。
10:53 BcryptCost
pprof の結果 bcrypt が重かったのでとりあえず新規ユーザーの BcryptCost
を10から4(ライブラリで許される最低値)に変更した。しかし、重いのは既存ユーザーのパスワードの確認だったためあまり効果はなかった。
既存ユーザーのログインリクエストを基に平文パスワードを収集して、新たに sha256 などの軽いハッシュ関数の結果を入れることも考えたが、
- 各ベンチマークでユーザーの初回ログイン時に sha256 を保存する方式では、2度ログインするユーザーが少なそうなのであまり効果がない
- initial.sql (初期データ)に過去のハッシュを入れる方式では、収集が面倒な割に100%データが集まるとは限らず、最悪の場合「再試験後に新たなユーザーを使用して確認した結果スコアが大幅に下がり失格」となるかもしれない
ということで見送った。
11:38 getNewCategoryItems で items と categories を JOIN
次のクエリ
SELECT * FROM `items` WHERE `status` IN (?,?) AND category_id IN (?) AND (`created_at` < ? OR (`created_at` <= ? AND `id` < ?)) ORDER BY `created_at` DESC, `id` DESC LIMIT ?
で category_id IN
の対象が共通の parentID
を持つカテゴリ達だったので JOIN した
SELECT ... FROM items INNER JOIN categories ON categories.parent_id=? AND items.category_id = categories.id WHERE items.status IN (?,?) AND (items.created_at < ? OR (items.created_at <= ? AND items.id < ?)) ORDER BY items.created_at DESC, items.id DESC LIMIT ?
1210点 (謎)
11:48 SQLを別インスタンスに移行
応援してた
12:00 Campaign: 1
去年本戦のシェアボタンの悪夢が蘇ってくる仕様。とりあえず変更。その後もころころ適当に変えていた。 1510点
12:41 item.status を比較可能に
ステータスの on_sale
, sold_out
, trading
, stop
, cancel
を "1"
〜 "5"
に置き換えた。このように辞書順に並べればクエリの status IN (?, ?, ?)
とかが大小比較で書ける。
12:?? file descriptor の数を増やす
Nginxのファイル記述子の上限に引っかかっていたらしい。応援していた。
13:?? items が category.parent_id を持つように非正規化
items.cat_parent_id というカラムを用意して、上の JOIN が不要になった。
SELECT ... FROM items WHERE items.cat_parent_id = ? AND items.status <= ? AND (items.created_at, items.id) < (?, ?) ORDER BY items.created_at DESC, items.id DESC LIMIT ?
14:05 postBuy の2つのAPI呼び出しを並列化
応援してた
??:?? アプリケーションサーバーを2台構成にした
応援してた
16:27 getTransactions のリトライ
外部APIに502を返されても一発で諦めず、10回までリトライしたらisucariから500を返すことがなくなったらしい。すごい。
13:??〜16:41 nginx の worker_connections を増やした
地獄だった。campaginを1以上にするとfailするが、ベンチマーカーは「POST /buy: リクエストに失敗しました (item_id: 500**)」というメッセージ以外の情報を表示してくれず、Nginx や golang service、MySQL の error.log などを見ても有用な情報が見つからない。
自分の実装が間違っていたのかとか色々不安になってデバッグしても原因がなかなかわからなかった。
結局 Nginx の worker_connections を1024から4096に増やして解決したらしい。3人×3時間ぐらい無駄にした。つらかった。
Nginx のログに出てこないのは仕方ないが、ベンチマーカーが何も言ってくれないのがつらい。
7570点
16:59 BumpChargeSeconds を変えた(その後戻した)
最後まで bump の恩恵を把握できず終わった。残念。
17:03 カテゴリのデータ全体をメモリに載せた
カテゴリは一切変更されないので初回読み込み時にグローバル変数に保存した。
副作用として一つN+1クエリがなくなった。もう一つのN+1クエリも消したかったが実装工数の都合上最後まで消えなかった。
9230点
17:06 DBコネクション確立を何回でもリトライ
再起動試験時のインスタンスの起動順がわからないので、DBインスタンスが最後になってもいいようにコネクション確立をリトライしまくるようにしたっぽい。
17:21 items.status_le2 カラムの追加
当時一番重いクエリは WHERE items.cat_parent_id = ? AND items.status <= "2" AND ...
というやつだった。
これではインデックスが (cat_parent_id, status)
までしか効かずそれ以降の WHERE 条件や ORDER BY は全件探索になってしまっていた。
そこで status <= "2"
と status_le2 = 1
が同値になるようなカラム status_le2
を追加した。これでクエリ
SELECT ... FROM items WHERE items.cat_parent_id = ? AND items.status_le2 = 1 AND (items.created_at, items.id) < (?, ?) ORDER BY items.created_at DESC, items.id DESC LIMIT ?
に対しインデックス (cat_parent_id, status_le2, created_at DESC, id DESC)
が効いていた(はず)。
10310点
〜17:50 再起動試験とおみくじ
10470点!!!
17:40 アリババクラウドのRAMの設定忘れに気付く
急いでkczさんがアリババクラウドのコンソールから設定した。点数が0点から無限倍になった。やったー
その他
Nginxで静的ファイルを捌いたり負荷分散していたらしい。お疲れ様です。
結果
10470点で24位だった。ギリギリ本戦に進めてよかった。
反省点
仕様をちゃんと読まなかった。実際読んでいるつもりだったがタイムラインの内容に soldOut を含めなくてもいいということにすら気付けなかった。これを含めなければそもそも上の status_le2
は不要だったし、売り上げも大きく違っていたと思う。
今後は、仕様を1文字たりとも読み飛ばさず、怪しいところはリストアップしておくことを心掛けたいと思う。
本戦もがんばるぞい!
Hexagony コンバータを作成しました (1)
この記事は TSG Advent Calendar 2018 の23日目です。TSG のチームが今日 SECCON で優勝しました。おめでとうございます!
昨日は hakatashi さんの「koresuki-bot の話」の予定でした。
今日は Hexagony という言語(esolang)へのコンバータについてお話を書きます。
はじめに
6日目の記事で、Hexagony の独自コンバータを作りたいと言いました。
Hexagony を書くのはとても大変で、さらに最短を目指すとなるとかなり労力が必要ですが、自動化できそうなところが多数ありました。それらの自動化を書いて、より快適な Hexagony コーディングを目指します。
(この記事に(1)とついているのはまだ一部しか自動化できていないためです。次の TSG ゴルフ大会までには全て完成させます。)
XSS Challenge (xss.shift-js.info) writeup
Web セキュリティに*1入門したくなってつばめプロの xss.shift-js.info を解きました。
(少なくとも問09までは)セキュリティの勉強じゃなくて esolang ゲームのような気もしました(esolang は初学者じゃないです)が、とりあえず全部解いたので解法を書いておきます。
複数解法ある問題も多いらしいので、これが想定解かどうかはわかりません。
- CSP disabled
- 01 (☆☆☆)
- 02 (★☆☆)
- 03 (★☆☆)
- 04-1 (★☆☆)
- 04-2 (☆☆☆ + 04-1)
- 05 (★☆☆; 実装: ★★★)
- 06-1 (★★★)
- 06-2 (★☆☆ + 06-1)
- 06-3 (★★☆ + 06-2)
- 06-4 (★☆☆ + 06-3)
- 07-1, 07-2 (★☆☆)
- 08-1 (★☆☆)
- 08-2 (★★★)
- 09-1, 09-2 (★☆☆)
- CSP enabled
- 20 (★★☆)
- 21 (★☆☆)
- 22 (★★☆)
- 23 (★★★)
- 最後に
*1:いつも「入門する」にかかる格助詞がわからなくて困る
駒場祭 codegolf day2 writeup (or Haskellゴルフのすすめ)
この記事は TSG Advent Calendar 2018 の6日目です。
昨日は fiord さんの ちょっとしたlsのtips でした。
今日は駒場祭のコードゴルフの writeup を適当に書いていきます。
駒場祭がありました
今年の駒場祭で TSG はライブ放送を行いました。強い人々が CTF や競プロ、AI のライブに参加していたのでそれらに関する記事もアドベントカレンダーでたくさん書かれています/書かれる予定ですが、私はまともなことは書けないのでコードゴルフについて書きます。
コードゴルフ大会ページ - 問題 - 提出一覧
Ruby 40byte
Rubyの提出一覧
問題を見て最初に思い浮かんだのが正規表現を用いる方法でした。とりあえずその方法を愚直に Ruby で書きました(44byte):
gets.gsub! /1(?!....1......1....1)/,?0;print
無駄に引数なしの print
(引数がない場合グローバル変数 $_
を出力する)を使っていますが、それ以外はとても読みやすいコードです。
これを微修正したのが最短です(40bytes):
Rubyの正規表現で足し算 (2) 異なる桁数
この記事はTSG Advent Calendar 2017の10日目です。昨日の記事は id:gasin さんの SECCONにゆるふわ参加してみた話 - gasin’s blog でした。TSGでは(特に1年生の)新入部員を募集しています。
gasin.hatenadiary.jp
さて、TSGの先輩方と雑談しているときに出てきた「正規表現で2進数を扱ったりして遊ぶ」という話題を発展させて、正規表現で足し算の式が正しいか判定することについて考えます。
先日の記事「Rubyの正規表現で加算を判定する (1)」では次のようなRubyの正規表現を書きました:
ADD2 =~ "1+0=1" ADD2 =~ "011+001=100" ADD2 !~ "1+1=0" ADD10 =~ "1+1=2" ADD10 =~ "486+001=487" ADD10 !~ "123+456=789"
二進、十進それぞれ2番目の例において、数の先頭に余分な0
が付いています。これは前回紹介した正規表現に「A,B,C
は全て同じ桁数」という制約があったためです。
今回の目標は、この不自然な制約を、「数の先頭に余分な0
が付いていない*1」という(自然な)制約に変えて*2、自然な形式の足し算を判定する正規表現を作ることです。
※完成したものはGistにあります
続きを読む