Lを探す日常

I lov esoteric programming

ISUCON10予選を3位で通過しました (vs descending index)

2020年9月12日に行われたISUCON10予選にチーム FetchDecodeExecWrite で参加し、3804点、3位で通過しました!やったことを書いていきます。

要点

  • Descending Index が効いていると思い込み、その誤りに最後まで気付かなかった。
  • 椅子に似合う物件検索を色々分割して頑張った。大きい変更で苦労したがそこそこ役に立った。
続きを読む

ISUCON9予選をギリギリ通過しました

2019年9月8日に行われたISUCON9予選にチーム FetchDecodeExecWrite で参加し、10470点でギリギリ通過しました。やったことを書いていきます。

スコア遷移
10時24分に初期スコア2000点を獲得したあと、正午にはなぜか1500点まで下がった。15時頃に4000点近くまではいくものの、並行して発生した問題で13時台から16時40分まで大量の0点(fail)の表示が並ぶ。16時41分に解決して7570点になった後は徐々にスコアを伸ばしていき、最後は17時51分に10470点を出して終了となった。
10時24分に初期スコア2000点を獲得したあと、正午にはなぜか1500点まで下がった。15時頃に4000点近くまではいくものの、並行して発生した問題で13時台から16時40分まで大量の0点(fail)の表示が並ぶ。16時41分に解決して7570点になった後は徐々にスコアを伸ばしていき、最後は17時51分に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にあります

*1:非零の数は「1」から始まる

*2:逆に01+01=10のような文字列は受け付けない

続きを読む

Rubyの正規表現で加算を判定する

正規表現における「再帰」をご存知でしょうか。一部の正規(自称)表現では再帰的なパターンを定義できるような拡張がなされており、Rubyが使っているOnigmoの正規表現でも再帰の機能が利用できます。この機能は「田中哲スペシャル」と呼ばれて多くの人に愛されているはずなのですが、なぜか2進数の処理に関する記述がググっても見つからなかったので、ここで2進数(と10進数)の足し算について書きたいと思います。

続きを読む