ISUCON11に「良心の呵責」というチームで参加して予選敗退しました

ポエム

ISUCON11に「良心の呵責」というチームで @44smkn と @kuwata0037 と参加しました。

isucon.net

結果としては予選敗退で最終スコアは34,976点(122位)でした。決勝進出は10~15万点あたりがボーダーのようだったのでまだまだでした。
結果は残念でしたが非常に楽しく学びのある1日でした。

コミュニケーションツールとか

チャットツールにはSlack、通話ツールにはDiscordを使っていました。当初は通話ツールとしてGoogle Meetを考えていましたが、6/30に無料期間が終わってしまい1時間制限がかかるようになってしまい変更しました。

SlackはGitHub連携を行ってIssueやPRのopen時や、@44smkn の謹製ツールでdeploy時に通知が届くようにしていました。

分析ツールとか

当日までは予選問題の確認や解説を読み込んでいました。また、前回参加者の振り返りブログを読んで何をやっていたのか当日のイメージつけたり、便利なツールを知ることから始めました。
（当たり前ですが）スロークエリやアクセス傾向をしっかり確認できるようにすることがチューニングの第1歩だなぁ、という感想です。
ツールとしては、 pt-query-digest や alp などを実際に使って過去問で試していました。

www.percona.com

github.com

ですが、ISUCONに対してNewRelicが支援を行っていて無料で使えるということもあり、全てNewRelicで当日は挑みました。

newrelic.com

当日やったこと

（誰も仕事としてバリバリ使ったことはないもののある程度読み書きができる）Goで解きました。
まず1時間くらいはマニュアルを読んだり実際に画面を見たりして内容の理解に努めました。その後はベンチマークをまずは回しつつ、NewRelicを仕込んで計測できる体制を作っていました。たしか初回ベンチスコアは2,500点くらいだった気がします。
その後はひたすら時間を多く使っているAPIやレスポンスが遅いAPIの実装の改修を行っていました。12時過ぎ頃には、POST /api/condition/:jia_isu_uuid はN件のデータをN回insertしていたのでbulkでinsertするように改修をしました。他に @kuwata0037 がindexを追加してくれたり、 @44smkn がDBのサーバ分離をしてくれたおかげでスコアが順調に伸びました。たしかお昼過ぎで2~3万は超えていたような気がします。この後は GET /api/isu と GET /api/trend のN+1に取り組んでいましたが、時間切れになってしまいました。

当日できなかったこと

予選終了後にDiscordで多くの方が対応内容を共有されていて非常の参考になりました。自分たちは過去問からN+1などばかりに目が行っていましたが、Ngnixの設定やDBのコネクションなど足元の設定でかなりスコアが改善されるそうでした。また、僕が取り組んでいた GET /api/trend のN+1もクエリに limit 1 を足すだけでとりあえずは良かったみたいでした。これは完璧を狙いすぎて全クエリを1つにしようした結果、シンプルな解法が見えていませんでした。

個人的に悔いが残る部分としてはミドルウェアの理解とクエリ力でした。普段の業務だとミドルウェア周りの設定ファイルはある程度できあがっており修正頻度も高くないため知らないことが多かったです。クエリ力も足りず引き際が見極めきれなかったのも時間を浪費する理由だったと思います。

他にも得点を上げるための施策がありそうですが他のブログを見て勉強しようと思います。

参加した感想

全体を通してISUCONは非常に楽しい大会でした。毎年出場する人がいるのもうなずけますし、やはり「あれをやっておけば...」と後悔するからこそ学習に精が出るし身につくのだな、と思いました。
特にチームメンバーには助けられ @44smkn にはインフラ周りを任せきりになり、 @kuwata0037 は気がつけばindexを貼ってスコアを伸ばす職人芸を見ました。通話でわいわい話しながら準備して当日も楽しめたので良かったです。

運営、NewRelicの方々もありがとうございました。

転売自体は悪くない

ポエム

経緯

こんなツイートをした。

そしたら知人からこんなリプがあった。

それに対し、高額転売についてその問題がその高額な価格に目が行きがちだけど、本当に解決しないといけないのは構造だよね、という話をした。

対岸でこっちを見ていた別の知人のそれっぽいまとめ。

高額転売と独禁法はここでは話が若干飛躍しているけれど、構造に問題があるという意味で共通していると思っている。
中途半端にツイートしたら案外興味を持つ人もいるんだなぁと思ったので、自分なりに思うことを書き散らしておくことにした。なのでこれはツイッターの延長であり放言です。

価格決定の構造

価格は需要と供給で決定する。他の要因もあるけれど基本的には需要と供給のバランスで決定する。価格設定は非常に奥深いもので、マーケティングの世界では重要なテーマになる。なぜなら、不確実な需要に対して企業がコントロールできるのは供給量と価格だからだ。 マーケティング用語に4P*1という言葉があり、その中にPriceが含まれている。そのくらい企業にとって価格設定は重要な話だ。
さらに、転売に関して知っておくべきことに価格弾力性*2がある。価格弾力性は価格の変化に応じて需要が変化する程度のこと。例えばコンビニで「あと20円Lチキが安ければついでに買うんだけどなぁ」ということがある。あれのことだ。
高額転売では価格弾力性が低い商品が狙われていると思う。価格の上昇で需要が著しく下がるのであれば高額転売は成立しないので。

価格競争

電気が3倍の価格になった場合、それを買わない人はいないだろう。しかし、他の業者が値上げせず元の価格のままだったらどうだろう。もちろん安い方を契約する。格安SIMの流れはまさにそうだったと思う。つまり、価格は需要と供給によって決定するけれど、供給業者が1つではない場合、品質が同じであれば安く提供する競合他社を選ぶ。

価格競争にはいくつか要因がある。まずはもちろん競合他社だ。トヨタであれば日産とかフォルクスワーゲンとかゼネラルモーターズ。全く同じ自動車は他社にはないけれど似たようなニーズを満たすのであれば最後は価格勝負になってくる。
他にはテスラのような新規参入もある。気がつけば電気自動車市場なんて言葉が生まれたくらいに競争が激化している。電気自動車は性能がかなり重視されるとは思うが、テスラはあまりに価格が高いので日経企業の既存の自動車メーカーの自動車を選ぶ人もいるだろう。
自動車はたまにしか使わないからタクシーのような代替品で済ませる人もいる。自分で運転することや自動車を保有することに執着がない人は、タクシーに乗車して支払う金額の総額が自動車の購入費用よりも安ければタクシーを選ぶだろう。

このように市場環境は複数の要因で成り立っている。今挙げた要因は5F*3と呼ばれるポーター*4が分類したものから例示した。

買い占めのメリット

5Fの中でも高額転売において非常に重要な要因は「売り手の交渉力*5」だと思う。これにより買い手へ強い態度で商売をすることができる。
各チャネル（Amazon、楽天、メルカリ ）で買い占めを行うことで本来は小売業者間で市場競争が行われていた商品を、特定の供給業者（ここでは高額転売業者）が独占販売する形になる。すると買い手は独占販売している高額転売業者からしか購入ができなくなるため、高額な価格でも購入せざるをえなくなる。だからこそ高額転売業者は高額に設定しても問題ない価格弾力性が低い商品を狙うと考えている。

価格の比較

これは余談だけれども、購買意思決定プロセスにはCDPモデル*6というものがある。そこには「情報探索」と「選択肢評価」というプロセスがある。インターネットの普及に伴ってECサイトで商品を購入でき配送が容易な地域に居住している人にとっては商圏というものが存在しなくなった。体感だけど、昔は家電を安く買うために電気屋をはしごして相見積もりをする話が多かった気もするけど、今となってはECサイトが標準価格になっている気がする。価格の参考情報がECサイトに集約されているため、高額転売業者はいくつかのECサイトを押さえることで市場全体の価格を決定することが可能になっているのではないかと思う。

だからやっぱり構造が悪い

世に言う転売erの倫理観がおかしいのは非常に正しいし、マスクの品薄と高額転売は社会的に損失でしかなかった。しかし、本当に悪いのはこの構造だと強く思う。
例えば地方でなかなか手に入らない商品を少し高い価格で販売するのは悪いことだろうか。極論だが商品を横に流している卸売業や小売業は悪いことをしているのだろうか。彼らは生産と消費を繋ぐ重要な役割を果たしている。本当に石を投げるべきは正しく自由市場で企業が価格競争を行って販売した商品を買い占め、自由市場を壊し、高額で販売することが可能な構造そのものだ。

おわりと補足

鉄は熱いうちになんとやらということで、かなり勢いで書いたので文章が散らかっているかもしれない。
興味がある人が読んで議論の種にでもなれば嬉しいです。元々は高額転売は構造を問題視せよって趣旨なので、社会がこっちの議論をしてくれるのは本望。

高額転売価格.com

高額転売は買い占めが前提にあるので、買い占めができない工夫が第一だけど、高額転売同士の価格競争を促すのもアリかもしれない。高額転売価格.com的な。一枚岩じゃないから勝手に値下げが始まるかもしれない。

toB

価格競争によって適正価格に落ち着くというのが自由市場だけれど、価格競争ができないtoBでの契約はかなり根深い問題なんだろうなと思う。

プラットフォーム料

これはまさに売り手の交渉力が強い例である。わかりやすいのはAppleとかGoogleとか。

*1:4P（ヨンピー）とは・意味｜創造と変革のMBA グロービス経営大学院

*2:価格弾力性とは・意味｜創造と変革のMBA グロービス経営大学院

*3:5F（ファイブフォース）とは・意味｜創造と変革のMBA グロービス経営大学院

*4:マイケル・ポーター - Wikipedia

*5:売り手の交渉力とは・意味｜創造と変革のMBA グロービス経営大学院

*6:https://www.jstage.jst.go.jp/article/acs/18/1_2/18_1_2_85/_pdf/-char/en

SQLアンチパターンを読んだ

読書感想文 DB

背景

最近になってDBの知識不足に危機感を憶えて色々と読んできた。

今回は度々引用されているのを見かけるSQLアンチパターンを読んだ。

SQLアンチパターン

SQLアンチパターン

  • 作者:Bill Karwin
  • 発売日: 2013/01/26
  • メディア: 大型本

DB関連は何かとアンチパターンから学習に入ることが多いような気がするが、この本がきっかけなんだろうか。それとも、目の前の仕様を満たす設計を行いそのようにアプリケーションに組み込めるけれど後になって実は悪手だったと気がつくことが多いからなのだろうか。どっちでも良いけど、アンチパターンから学ぶのは机上の空論ではない泥臭さがあって良いね。

本書の構成

構成はハッキリと分かれており下記のようになっている。

  1. 論理設計のアンチパターン
  2. 物理設計のアンチパターン
  3. クエリのアンチパターン
  4. アプリケーション開発のアンチパターン

また各章の構成は下記のようになっている。

  1. 目的
  2. アンチパターンの紹介
  3. アンチパターンの見つけ方
  4. アンチパターンを用いても良い場合
  5. 解決策

気になるところだけ掻い摘んで読めるので、とりあえず買って業務で目の前の課題に対応するアンチパターンを読んでそれを踏まないように注意するような使い方もできそう。

読んだ箇所のざっくりした感想

何冊か読んでいるためある程度理解した上で読むことができていた。また、経験的にわかっていることも多かった。しかし、もちろん初めて知ったものや無意識に踏んでしまいそうなアンチパターンもあったので、読んでいて非常に面白かった。

論理設計

ちゃんと正規化しようという趣旨の「ジェイウォーク（信号無視）」やちゃんと外部キーを使おうという趣旨の「キーレスエントリ（外部キー嫌い）」は経験的に理解しているものだった。これはDBの学習以前に治安の良いアプリケーションを作ろうと設計した経験がある人であれば無意図の非正規化や外部キーが存在しないことへの忌避感を感じるとは思う。

一方で、「EAV（エンティティ・アトリビュート・バリュー）」や「ポリモーフィック関連」、「マルチカラムアトリビュート（複数列属性）」、「メタデータトリブル」はかなり参考になった。
EAVとポリモーフィック関連は似ているが、問題意識は真逆だ。EAVは状態に応じてカラムが変化する場合、ポリモーフィック関連は色んな状態で共通のカラムを使用したい場合に発生する。

EAV

EAVとは状態によって属性が可変なエンティティのことを指す。つまりあるカラムの状態に応じてカラムが動的に必要になってくるということである。
EAVをプログラムで表現すると下記のようになる。

code

#[derive(Debug, Default)]
struct BugData {
    severity: String,
    version_affected: String,
}

#[derive(Debug, Default)]
struct FeatureRequstData {
    sponsor: String,
}

#[derive(Debug)]
enum State {
    Bug(BugData),
    FeatureRequst(FeatureRequstData),
}

#[derive(Debug)]
struct Issue {
    priority: String,
    version_resolved: String,
    state: State,
}

impl Issue {
    fn new(state: State) -> Self {
        Self {
            priority: "high".to_string(),
            version_resolved: "solved".to_string(),
            state: state,
        }
    }
}

fn main() {
    let bug = State::Bug(BugData::default());
    let feature_request = State::FeatureRequst(FeatureRequstData::default());
    println!("{:?}", Issue::new(bug));
    println!("{:?}", Issue::new(feature_request));
}

Issue { priority: "high", version_resolved: "solved", state: Bug(BugData { severity: "", version_affected: "" }) }
Issue { priority: "high", version_resolved: "solved", state: FeatureRequst(FeatureRequstData { sponsor: "" }) }

Rust Playground

テーブルとして表現したい場合にはどうすれば良いのかアンチパターンへの対処がいくつか記載されていた。

  • 1つのテーブルに各ステータスの和集合のカラムを作る
  • 諦めて別テーブルにする
  • BugとFeatureRequestそれぞれの差分のみテーブルに切り出して親をIssueとするリレーションを作る
  • JSONのまま突っ込む

JSONのまま突っ込むのは悪手に見えるが、ビジネス要因（要件を詰めていたりユーザの反応を見ていたり）で完全に構造が確定していない場合には有効な場面もあるだろう。
直感的にきれいなものは3つ目のリレーションをキレイに整理することだが、状態が2つくらいと少なく互いに関連して作用するものでもないなら別テーブルにしてしまっても良いのかな、とも思う。スキーマ変更時にどちらも修正する必要が出てくるので脆弱だけど。

ポリモーフィック

EAVでは状態に応じて詳細が紐付いているものだったが、ポリモーフィックの場合は複数の具体テーブルに共通的なカラムが存在しているものである。
つまり、Bug用のCommentとFeatureRequest用のCommentがあり、それぞれCommentという共通の構造が存在する。
これもプログラムを見るのが早い。（簡略のためis-aではなくhas-aの関係になっているけれど趣旨の複数の具体が共通を持つという構造に意識して着目したい）

code

use chrono::prelude::*;

#[derive(Debug)]
struct Comment {
    comment_date: DateTime<Utc>,
    comment: String,
}

impl Default for Comment {
    fn default() -> Self {
        Self {
            comment_date: Utc::now(),
            comment: "".to_string(),
        }
    }
}

#[derive(Debug, Default)]
struct BugComment {
    severity: String,
    version_affected: String,
    comment: Comment,
}

#[derive(Debug, Default)]
struct FeatureRequstComment {
    sponsor: String,
    comment: Comment,
}

fn main() {
    let bug_comment = BugComment::default();
    let feature_request_comment = FeatureRequstComment::default();
    println!("{:?}", bug_comment);
    println!("{:?}", feature_request_comment);
}

BugComment { severity: "", version_affected: "", comment: Comment { comment_date: 2021-05-11T01:14:45.455349Z, comment: "" } }
FeatureRequstComment { sponsor: "", comment: Comment { comment_date: 2021-05-11T01:14:45.455370Z, comment: "" } }

Rust Playground

この構造をテーブル表現に落とし込む際、CommentはBugCommentもしくはFeatureRequestCommentと紐付いているため外部キーを設定する。だが、その外部キーはBugCommentとFeatureRequestCommentのどちらを設定するのかはデータ次第になるため、どのように設定すればよいのかわからない。

このアンチパターンはBugとFeatureRequestの両方を受け入れられるようにComment側では外部キー制約をしないというものだ。しかしこれはあまりに脆弱である。

これの対処法は2つある。

  • 依存関係を逆転させてBugやFeatureRequestがCommentへの外部キーを持つ（↑の例示がhas-aだったので当然のように見えてしまう）
  • CommentとBugの両方の外部キーを持つBugCommentテーブルのような交差テーブルを作成する

RDBの世界に落とし込む際には一筋縄ではいかないことは外部キーを考えると納得だった。また、アンチパターンを受け入れて良いケースとしてORM側でこれらの整合性を担保されているケースを挙げていた。

物理設計

小数は「丸め誤差」が発生してしまうことや「闇雲インデックス」をしてもパフォーマンスに寄与しないということは、別の書籍でも学習済みだったので理解に苦しくなかった。
新しく知ったことは「31フレーバー」「ファントムファイル」の章だった。

31フレーバー

限定的な種別を表す際にどのような設計をすべきかという話。
例えば、Bugテーブルのstatusに未対応・調査中・修正中・確認中・解決済みというものを割り振りたいとする。その際BugテーブルのstatusカラムにCHECK制約を設けるとする。これがアンチパターンである。

このようなケースは場当たり的な改修を前に拡張性や移植を考慮する時間が取れないと発生しそうな気がするし、実感として気が回りきらない時にやってしまったかもなと思う。対処法としては、status用に別途テーブルを定義して、Bugテーブルはstatusテーブルの外部キーを持つというものだ。そうすることでBugテーブルはカラム変更でロックされることもないし、CHECK制約を加える必要もなくなる。

ファントムファイル

メディアファイルはDBに入れずにs3に入れてそのパスをRDBに格納することがあると思う。でもこれを判断なしに行うのはよくないねという話。今まで何気なしにパスを格納していたけれどこの章を読んで改めて認識が変わった。

これがアンチパターンである理由はいくつかある。ひとつはs3などのストレージからメディアファイルが削除されてしまった場合にRDBには存在しないファイルを指すパスが格納されていることになる。しかしそれに気が付かない。
また、トランザクション分離の観点でもRDBでは削除できずロールバックしたがストレージから実態を削除してしまった、ということが起こりうる。さらに、DBにはURLなどのパス用のデータ型はないため不整値を弾くことができない。

許容できるケースとしてはファイルのサイズがかなり大きかったり数がとても多くDBやネットワークを逼迫してしまう可能性がある場合。

クエリ

クエリは既存の知識の確認となるような内容が多かった。NULLの扱いとか。
「ランダムセレクション」では乱数の扱いでテーブルを丸々スキャンしないようにクエリを作ったり、「インプリシットカラム」ではselect時にカラムをちゃんと指定するとか、丁寧なSQLライフを心がけようと思いを新たにした。

だが「スパゲッティクエリ」の章は耳が痛かった。これは複雑なクエリひとつですべてを解決しないようにしようというもの。アプリケーションでは単純なクエリを心がけているが、redashとかレポートやグラフで可視化したいような時にはスパゲッティクエリを書いてしまいがちな気がした。気をつけたい。

アプリケーション開発

アプリケーション開発の章は純粋なRDBの知識ではないため別の態度で読む必要があった。
「リーダブルパスワード」「SQLインジェクション」「シー・ノー・エビル」は基本的な話だったので自分には目新しく感じるところはなかった。

非常に面白かったのは「ディプロマティック・イミュニティ」の章だった。問題は、アプリケーション開発のルールはデータベース開発には通用しないといった、データベースへの特別視・特権扱いをしてしまうことだ。これは、組織として体制や役職、業務フローに組み込まれてしまっているところはあると思う。例えば、ソフトウェアエンジニアとDBAの業務がきっぱり分かれていたり、データベースの知識や運用権限がデータベースを扱う一部の人に集中してしまったりなどだ。この章は、今までの章と異なりかなりメタ的な話だった。
アンチパターンの見つけ方には、データベースを特別視した発言を挙げていた。これはよく見かけるものだと思う。

これの対処法には文書化やバージョン管理、テストなど運用を一部の人だけに限定せず民主化することだ。より具体的には、ER図やテーブルスキーマ、セキュリティやインフラ構成などをしっかり形式知にしていくことである。思うに、それらに加えてどのような経緯で現状の形になったのか、他の選択肢はなかったのか、当時はどういう状況のため何を判断基準として意思決定したのか、という今後の意思決定のための情報が残されているとかなり健全になっていくはずだ。これはDBに限らない組織全てに関する話だと思う。

まとめ

当然に感じる知識や言語化されて整理された知識、そしてもちろん新しい知識があった。RDBに関連する本を何冊か読んできたけれど名著と言われるだけあって非常にわかりやすくて考えさせられるような話が多かった。また、明日にでも使える知識が多いので非常にためになった。
特に私はアプリケーション開発者なので、論理設計はとても参考になった。EAVとポリモーフィックは最初はなかなか分別がつかず、整理しきれていない部分があったがこうしてブログにして言語化してみると整理することができた。また、最後に書いたディプロマティック・イミュニティは非常に根が深いと思う。いち個人ではなかなか解決できないもので組織を横断して取り組む必要があると思う。社風も個人のDBへの向き合い方も関わってくる非常に難題だと感じている。少なくとも自分がこのような考えを巡らせてしまった時には本書のことを思い出して、積極的にDBの運用や構成にも関わっていければと思う。

無職転生の原作を読んだら1ヶ月が溶けた

ポエム

無職転生とは

無職が転生する話。なんやかんや困難が訪れなんやかんや解決していく、というのが話の主な展開。
2012年から小説家になろうで連載開始。2021年の冬アニメとして放送開始。

ja.wikipedia.org

公式サイトはスマホじゃないと開けない。 mushokutensei.jp

気がつけば原作を買っていた

このアニメ、作画がとんでもなく良い。なんとこのアニメのために会社を作ったらしい。

st-bind.jp

作画がすごくて興味が出たけれど、話の展開も気になってしまったので原作を1冊買ってしまった。これが生活崩壊の始まりだった。

Amazonの購入履歴を見てみると、原作1巻は2021/02/12、既刊最終巻の24巻は2021/03/19に購入していた。なので35日間で全巻読んだことになる*1。大体1.5日に1冊読んでいる計算になる。土日に一気読みではなく平日も朝昼晩と時間があれば読んでいたので、本当にずーっと読んでいた。

購入するまではブログを継続的に更新して、生活サイクルも23時頃に寝て6時半頃に起きる生活をしていたが、読み始めてからは3時過ぎに寝て9時過ぎに起きる生活をしていた。

感想

いわゆるなろう系というかご都合主義的なので、良い意味で頭を使わなくてもよく、最終的には物事が上手くいくのだろう、と思いながら読める。SAOもそうだったけれど死にそうになると必ず活路があったり、何か事故が起きる前に気がついたり、とにかく運が良かったりする。世界がとにかく主人公をお膳立てする。
表紙と目次から結末がわかってしまうことも多かったが、以前登場したキャラが別の話で繋がっていることがたまにあり、不意を突かれることもあった。こういうのは予め関係図を作っているのだろうか、それとも案外場当たり的だったりするのだろうか。気になる。
やんや言いつつも1.5日に1冊のペースで読むくらいには楽しんだ。次巻も楽しみ。

アニメでは割と描写を端折っているところもあるので、原作で読んだ記憶が良い感じに補完されて楽しんで観れている。今クール分は終わり、2クールは7月から始まる予定だ。作画はかなり大変だろうから、もし延期になっても気長に待ちたい。

値段

約1200円/冊を24冊買ったので、約3万円が飛んだ。最近のラノベは高い......。

*1:厳密には最終巻を読み切った日を足すけれど、1日増えるくらいだろう

【OSS探訪記】hq

Go OSS Concurrency

背景・モチベーション

Goで並行処理について公式ドキュメントや書籍を読んだが、実際にどのように使われているのか、そしてどのようなプロダクトがあるのか気になった。そこで、awesome-goを見て並行処理をしていそうなOSSを読んでみようと思う。
ざっくり気ままに読んでいきたいので誤読していたり大事なところを読んでいなかったりするかもしれない。OSSの紹介ではなく自己満足でただ読んでいくだけなので、解説についてはそこまで期待しないで頂ければと思う。気になった方が自分も読んでみようかなと思ってもらえると嬉しい。

対象OSS

今回はhqを読む。（さっそくawesome-goに含まれていないOSSなのだが、以前に作者の記事を読んでいて非常に面白かったのでコードも読んでみた）

github.com

これは何をするソフトウェア？

hqはジョブキューのライブラリ。詳細は作者が解説した記事があるのでそれを読むのが正確で理解は早い。あと、この記事は作者の解説記事を読んでいることはある程度前提にして話が進むので、流し読みせずに読まれる方は解説記事を一読された方が良いだろうと思う。

kohkimakimoto.hatenablog.com

hqは下記の特徴がある。

・Goによる実装で、シングルバイナリ

・スタンドアロンのHTTP APIサーバー。ジョブのデータベースも読み込みであるため、別途特別な依存を必要としないで動作する

・シンプルでプログラミング言語非依存。HTTP APIでジョブを投入し、ジョブはHTTP POSTメッセージをワーカーアプリケーション（Webアプリ）に送信するというアーキテクチャ

・フロントエンドとしてCLIとWebUIを組み込みでサポート

処理の流れはこんな感じ。

HTTP APIでジョブ(JSON)を投入します。HQはジョブを取り出し、ジョブに記載されたURLにHTTP POSTして、別途用意されたワーカー用のWebアプリケーションにジョブを実行させる、という流れになっています。

解説記事がめっちゃわかりやすい。いきなりREADMEや実装を読む前に解説があると非常に助かる。

実装を追う

ジョブキューとしてのおおまかな流れはわかったので、下記の実装を見てみようと思う。

  • Webサーバとして起動している箇所
  • ジョブをenqueueしている箇所
  • キューの構造
  • ジョブをdequeueしている箇所
  • ジョブの構造

Webサーバの起動

サーバの起動なのでそこまでmain関数から離れて定義されてはいないだろう。ということでmain関数を発見。mainの中でrealMainを呼び出している。

func main() {
    os.Exit(realMain())
}

https://github.com/kohkimakimoto/hq/blob/master/cmd/hq/hq.go#L11-L13

realMainの中ではurfave/cliを使ってCLIアプリとしてコマンドの設定を行いコマンドを実行している。設定に従いapp.Run(os.Args)でコマンドが実行される。

   app := cli.NewApp()
    app.Name = hq.Name
    app.HelpName = hq.Name
    app.Version = hq.Version + " (" + hq.CommitHash + ")"
    app.Usage = "Simplistic job queue engine"
    app.Commands = command.Commands

    if err := app.Run(os.Args); err != nil {
        printError(err)
        status = 1
    }

https://github.com/kohkimakimoto/hq/blob/master/cmd/hq/hq.go#L23-L33

コマンドの一覧は下記。ServeCommandがサーバの起動だろう。

// Command set
var Commands = []cli.Command{
    DeleteCommand,
    InfoCommand,
    ListCommand,
    PushCommand,
    RestartCommand,
    ServeCommand,
    StatsCommand,
    StopCommand,
}

https://github.com/kohkimakimoto/hq/blob/master/command/commands.go#L13-L23

さて、ServeCommandとは何なのか。定義に飛んでみるとserverActionがハンドラとして登録されており、serverActionではListenAndServe()を呼び出しサーバを起動していることがわかる。その過程でserver.NewApp(config)でAppを作っているようだ。

var ServeCommand = cli.Command{
    Name:   "serve",
    Usage:  "Starts the HQ server process",
    Action: serverAction,
    Flags: []cli.Flag{
        configFileFlag,
        logLevelFlag,
    },
}

func serverAction(ctx *cli.Context) error {
    config := server.NewConfig()

    if err := loadServerConfigFiles(ctx, config); err != nil {
        return err
    }

    applyLogLevel(ctx, config)

    app := server.NewApp(config)
    defer app.Close()

    return app.ListenAndServe()
}

https://github.com/kohkimakimoto/hq/blob/master/command/serve.go#L11-L34

NewAppを見るとAppという構造にEchoがラップされている。つまりWebサーバの実態はEchoだ。

func NewApp(config ...*Config) *App {
    var c *Config
    if len(config) == 0 {
        c = NewConfig()
    } else {
        c = config[0]
    }

    // create app instance
    app := &App{
        Config:  c,
        Echo:    echo.New(),
        DataDir: c.DataDir,
    }

    app.Echo.HideBanner = true
    app.Echo.HidePort = true
    app.Echo.Server.Addr = app.Config.Addr

    return app
}

https://github.com/kohkimakimoto/hq/blob/master/server/app.go#L58-L78

ついでなのでAppがどういう構造なのかも見てみる。ほとんど設定関連だがDB *bolt.DBやStore *Store、QueueManager *QueueManagerなどがある。（GenはジョブのIDを採番するためのもの。本筋とそこまで関わらないのでここで補足しておく）

type App struct {
    // Configuration of the application instance
    Config *Config
    // Logger
    Logger echo.Logger
    // LogfileWriter
    LogfileWriter reopen.Writer
    // LogLevel
    LogLevel log.Lvl
    // Echo web framework
    Echo *echo.Echo
    // AccessLog
    AccessLogFile *os.File
    // AccessLogFile
    AccessLogFileWriter reopen.Writer
    // DataDir
    DataDir string
    // UseTempDataDir
    UseTempDataDir bool
    // DB
    DB *bolt.DB
    // Store
    Store *Store
    // Background
    Background *Background
    // katsubushi
    Gen katsubushi.Generator
    // QueueManager
    QueueManager *QueueManager
}

https://github.com/kohkimakimoto/hq/blob/master/server/app.go#L27-L56

Appがわかったので先ほどのListenAndServeの中身を見ていく。ちょっと行数が多いが基本的にはEchoの起動設定と起動など。ジョブキューとしての本筋と関連しそうなのはメソッドの先頭で行っているapp.Open()だ。

func (app *App) ListenAndServe() error {
    // open resources such as log files, database, temporary directory, etc.
    if err := app.Open(); err != nil {
        return err
    }

https://github.com/kohkimakimoto/hq/blob/master/server/app.go#L203-L207

Openでは先ほどのスニペットのコメントにある通り、Echo以外で必要なリソースの初期化処理を行っている。100行近いコードなので抜粋。下記のように初期化してAppに代入している。QueueManagerについては起動も同時に行っている。これでジョブを受け付け実効する準備が完了するのだろう。

   // setup bolt database
    db, err := bolt.Open(app.BoltDBPath(), 0600, nil)
    if err != nil {
        return err
    }
    app.DB = db
    logger.Infof("Opened boltdb: %s", db.Path())

    // store
    app.Store = &Store{
        app:    app,
        db:     db,
        logger: logger,
    }

    if err := app.Store.Init(); err != nil {
        return err
    }

    // queue
    app.QueueManager = NewQueueManager(app)
    app.QueueManager.Start()

https://github.com/kohkimakimoto/hq/blob/master/server/app.go#L137-L158

ということで、コマンドでserveを渡すとEchoのWebサーバが起動するようだ。

Enqueue

次にこのWebサーバでどのようにEnqueueしているのかを見ていく。これはREADME.mdに記載があり、/jobに対してPOSTするとのこと。 https://github.com/kohkimakimoto/hq/blob/master/README.md#post-job

ではさっそくPOST /jobを探そう。サーバに設定されているハンドラの一覧は下記。POST /jobに対応するのはCreateJobHandlerだ。

func setupAPIHandlers(e *echo.Echo, prefix string) {
    e.Any(prefix, InfoHandler)
    e.GET(prefix+"stats", StatsHandler)
    e.POST(prefix+"job", CreateJobHandler)
    e.GET(prefix+"job", ListJobsHandler)
    e.GET(prefix+"job/:id", GetJobHandler)
    e.DELETE(prefix+"job/:id", DeleteJobHandler)
    e.POST(prefix+"job/:id/stop", StopJobHandler)
    e.POST(prefix+"job/:id/restart", RestartJobHandler)
}

https://github.com/kohkimakimoto/hq/blob/master/server/app.go#L58-L78

CreateJobHandlerの中でリクエストの中身からJobを作ってapp.QueueManager.EnqueueAsync(job)という記述がある。また、app.Store.CreateJobという記述もある。解説記事に書いてあるが、このジョブキューはメモリとKVSのどちらにもジョブを登録するので、これらはその話と対応する処理なのだろう。メソッド全部を載せるにはやや長いので抜粋。

   job := &hq.Job{}
    job.ID = id
    job.CreatedAt = katsubushi.ToTime(id)
    job.Name = req.Name
    job.Comment = req.Comment
    job.URL = req.URL
    job.Payload = req.Payload
    job.Headers = req.Headers
    job.Timeout = req.Timeout

    if err := app.Store.CreateJob(job); err != nil {
        return err
    }

    app.QueueManager.EnqueueAsync(job)

https://github.com/kohkimakimoto/hq/blob/master/server/handlers.go#L50-L64

まずapp.Store.CreateJobを見てみる。メソッドの最初の行に以下のように書いてある。s.dbとUpdateに渡している関数のtx *bolt.Txから、Storeはboltのクライアントとして定義されていそうな予感。

   return s.db.Update(func(tx *bolt.Tx) error {

https://github.com/kohkimakimoto/hq/blob/master/server/store.go#L74

Storeの定義に飛んでみるとやはりそうだった。app.Store.CreateJobの中で色々やっていそうだけど、boltにジョブを突っ込んでいる処理だとは思うので、一旦これで理解を留めて先に進む。

type Store struct {
    app    *App
    db     *bolt.DB
    logger echo.Logger
}

https://github.com/kohkimakimoto/hq/blob/master/server/store.go#L15-L19

先ほどのCreateJobHandlerのapp.QueueManager.EnqueueAsyncに話を戻そう。呼び出しているEnqueueAsyncの定義を読むと、これはジョブをキューに登録しているものだ。また、同時にgoroutineでQueueという変数のchanにjobを積んでいることがわかる。m.RegisterWaitingJob(job)はいまいちわからないので読む必要がありそう。

func (m *QueueManager) EnqueueAsync(job *hq.Job) {
    m.RegisterWaitingJob(job)

    go func() {
        m.Queue <- job
    }()
}

https://github.com/kohkimakimoto/hq/blob/master/server/queue.go#L51-L57

RegisterWaitingJobがやってることはmapにジョブを登録する処理だった。ジョブは待機ジョブとして登録される様子。

func (m *QueueManager) RegisterWaitingJob(job *hq.Job) {
    m.statusMutex.Lock()
    defer m.statusMutex.Unlock()

    m.WaitingJobs[job.ID] = &WaitingJob{
        Job: job,
    }
}

https://github.com/kohkimakimoto/hq/blob/master/server/queue.go#L79-L86

ついでなので、RegisterRunningJobとRemoveRunningJobも見ておく。やってることはジョブのステータス変更だが、Mapで管理しているので、各Mapから該当するIDのデータをdeleteしている。

func (m *QueueManager) RegisterRunningJob(job *hq.Job, cancel context.CancelFunc) {
    m.statusMutex.Lock()
    defer m.statusMutex.Unlock()

    m.RunningJobs[job.ID] = &RunningJob{
        Job:    job,
        Cancel: cancel,
    }

    // remove waiting jobs
    delete(m.WaitingJobs, job.ID)
}

func (m *QueueManager) RemoveRunningJob(job *hq.Job) {
    m.statusMutex.Lock()
    defer m.statusMutex.Unlock()

    delete(m.RunningJobs, job.ID)
}

https://github.com/kohkimakimoto/hq/blob/master/server/queue.go#L59-L77

ここまでで、boltにデータを格納しつつQueueManagerのQueueというchanにジョブを積む、という流れがわかった。作者の解説記事にもあるが、途中でプロセスが死んでもboltから取り出せるのでジョブをロストしないようにするための設計だ。

Queueの構造

では、さっきから度々登場していたQueueManagerの定義を確認する。先ほどまではEnqueueを見ていたが、ここからはDequeueのための定義も含まれている。

type QueueManager struct {
    App         *App
    Queue       chan *hq.Job
    Dispatchers []*Dispatcher
    WorkerWg    *sync.WaitGroup

    // job status
    statusMutex *sync.Mutex
    WaitingJobs map[uint64]*WaitingJob
    RunningJobs map[uint64]*RunningJob
}

https://github.com/kohkimakimoto/hq/blob/master/server/queue.go#L9-L19

Dispatcherは名前からして明らかにDequeue関連なので一旦後回し。他にはWatingJobとRunningJobが気になる。これらの定義を見てみるとJobをラップしたものだった。これらの構造体でラップすることでJobのステータスを表しているようだ。RunningJobの方はジョブとCancelを抱き合わせているので取り回しが便利そう。

type WaitingJob struct {
    Job *hq.Job
}

type RunningJob struct {
    Job    *hq.Job
    Cancel context.CancelFunc
}

https://github.com/kohkimakimoto/hq/blob/master/server/queue.go#L114-L121

キューの構造自体はシンプルだった。状態毎のMapにジョブのIDで登録・削除をしていく。sync.Mapを使えばMap操作前後でロックの確保・開放の処理が必要なくなるのかな、と思うなどした。けれどこれは実装当時はsync.Mapがなかったのかもしれないし、もしかしたらsync.Mapでは実現できない何かがあるかもしれない。これは細かい話なので次に進もう。

Dequeue

さて、QueueManagerが保持していたDispatcherの定義を確認しよう。と思ってみてみたらかなり小さい構造だった。

type Dispatcher struct {
    manager    *QueueManager
    NumWorkers int64
}

https://github.com/kohkimakimoto/hq/blob/master/server/dispatcher.go#L20-L23

構造体の定義の少し下にある実装を見てみるとloopというメソッドがdispatcherには生えており、これがディスパッチャとしての実態だった。ここではQueueからジョブを取り出して、Worker数に応じて同期・非同期に処理を行っていくようだ。dispatchAsyncの方はgoroutineで処理されるのだろう。

func (d *Dispatcher) loop() {
    m := d.manager
    logger := m.App.Logger
    config := m.App.Config

    for {
        job := <-m.Queue
        logger.Debugf("dequeue job: %d", job.ID)

        if atomic.LoadInt64(&config.MaxWorkers) <= 0 {
            // sync
            d.dispatch(job)
        } else if atomic.LoadInt64(&d.NumWorkers) < atomic.LoadInt64(&config.MaxWorkers) {
            // async
            d.dispatchAsync(job)
        } else {
            // sync
            d.dispatch(job)
        }
    }
}

https://github.com/kohkimakimoto/hq/blob/master/server/dispatcher.go#L25-L45

dispatchとdispatchAsyncの中身を確認する。どちらの処理も大差はなくgoroutineで処理を行うかどうかが違うだけで、workを呼び出していることがわかる。

func (d *Dispatcher) dispatchAsync(job *hq.Job) {
    manager := d.manager

    manager.WorkerWg.Add(1)
    atomic.AddInt64(&d.NumWorkers, 1)

    go func() {
        defer func() {
            manager.WorkerWg.Done()
            atomic.AddInt64(&d.NumWorkers, -1)
        }()

        d.work(job)
    }()
}

func (d *Dispatcher) dispatch(job *hq.Job) {
    manager := d.manager

    manager.WorkerWg.Add(1)
    atomic.AddInt64(&d.NumWorkers, 1)
    defer func() {
        manager.WorkerWg.Done()
        atomic.AddInt64(&d.NumWorkers, -1)
    }()

    d.work(job)
}

https://github.com/kohkimakimoto/hq/blob/master/server/dispatcher.go#L47-L74

workを見てみる。ここでは主な処理はジョブのステータス変更とジョブの処理を行っている。ジョブの処理がworkだと思っていたけど、本体はrunHttpWorkerだった。結構長いのでコードを適宜抜粋する。ちなみにスニペットと実装されている順序は異なる。（最後のスニペットはdeferで囲まれており記述はメソッドの中間あたり。ただ処理は最後にされるのでスニペットも最後に載せた）

   // keep running job status.
    manager.RegisterRunningJob(job, cancel)
    defer manager.RemoveRunningJob(job)

    if job.Canceled {
        return
    }

    now := time.Now().UTC().Truncate(time.Millisecond)
    // update startedAt
    job.StartedAt = &now
    if e := store.UpdateJob(job); e != nil {
        logger.Error(e)
    }

   // worker
    err = d.runHttpWorker(job, ctx)

       // Update result status (success, failure or canceled).
        // If the evaluator has an error, write it to the output buf.
        if err != nil {
            logger.Errorf("worker error: %v", err)
            job.Success = false
            job.Failure = true
            job.Err = err.Error()
        } else {
            job.Success = true
            job.Failure = false
        }

        // Truncate millisecond. It is compatible time for katsubushi ID generator time stamp.
        now := time.Now().UTC().Truncate(time.Millisecond)

        // update finishedAt
        job.FinishedAt = &now

        if e := store.UpdateJob(job); e != nil {
            logger.Error(e)
        }

https://github.com/kohkimakimoto/hq/blob/master/server/dispatcher.go#L79-L139

では、本丸のrunHttpWorkerを見てみる。やってることは案外単純でJobからPayloadやURLを取り出してその通りにnet/httpでリクエストを送っている。これ以上の説明のしようがないのでコードを全部載せてしまった方がわかりやすい気がしてきた。

func (d *Dispatcher) runHttpWorker(job *hq.Job, ctx context.Context) error {
    var reqBody io.Reader
    if job.Payload != nil && !bytes.Equal(job.Payload, []byte("null")) {
        reqBody = bytes.NewReader(job.Payload)
    }

    // worker
    req, err := http.NewRequest(
        "POST",
        job.URL,
        reqBody,
    )
    if err != nil {
        return errors.Wrap(err, "failed to create new request")
    }

    // set context
    req = req.WithContext(ctx)

    // common headers
    req.Header.Add("Content-Type", "application/json")
    req.Header.Add("User-Agent", WorkerDefaultUserAgent)
    req.Header.Add("X-Hq-Job-Id", fmt.Sprintf("%d", job.ID))

    // job specific headers
    for k, v := range job.Headers {
        req.Header.Add(k, v)
    }

    // http client
    client := &http.Client{
        Timeout: time.Duration(job.Timeout) * time.Second,
    }

    resp, err := client.Do(req)
    if err != nil {
        return errors.Wrap(err, "failed to do http request")
    }
    defer resp.Body.Close()

    statusCode := resp.StatusCode

    job.StatusCode = &statusCode
    body, err := ioutil.ReadAll(resp.Body)
    if err != nil {
        return errors.Wrap(err, "failed to read http response body")
    }
    job.Output = string(body)

    if resp.StatusCode != http.StatusOK {
        return fmt.Errorf(http.StatusText(resp.StatusCode))
    }

    return nil
}

https://github.com/kohkimakimoto/hq/blob/master/server/dispatcher.go#L141-L195

ふむふむ。Dequeueの雰囲気が掴めた。

ジョブの構造

最後にジョブがどういう定義になっているのかを確認する。URLとPayloadは先ほどのrunHttpWorkerで見た。他はジョブの状態を表していることがわかる。

type Job struct {
    ID         uint64            `json:"id,string"`
    Name       string            `json:"name"`
    Comment    string            `json:"comment"`
    URL        string            `json:"url"`
    Payload    json.RawMessage   `json:"payload"`
    Headers    map[string]string `json:"headers"`
    Timeout    int64             `json:"timeout"`
    CreatedAt  time.Time         `json:"createdAt"`
    StartedAt  *time.Time        `json:"startedAt"`
    FinishedAt *time.Time        `json:"finishedAt"`
    Failure    bool              `json:"failure"`
    Success    bool              `json:"success"`
    Canceled   bool              `json:"canceled"`
    StatusCode *int              `json:"statusCode"`
    Err        string            `json:"err"`
    Output     string            `json:"output"`
    // status properties.
    Waiting bool `json:"waiting"`
    Running bool `json:"running"`
}

https://github.com/kohkimakimoto/hq/blob/master/hq/structs.go#L25-L45

まとめ

ということでhqをざっと読んでみた。hqは作者のありあまる親切心がREADMEや解説記事ににじみ出ており非常にわかりやすい。OSSを読んでいく上で入門的だ。内容はWebサーバを立ててKVSとchanを活用してジョブを登録・取出を行い、ジョブに保存されているURLとPayloadでリクエストを投げるというものだった。並行処理なのでロックであったり状態管理については非常に参考になる。
なんだかまとめるまでもなく記事の前半で作者の解説記事から引用してきた処理の流れ通りの説明になってしまった。それだけあの解説記事が親切でわかりやすいということで。

次回に読むOSSは決めているのだが、次回がいつやってくるのか怪しいので伏せておく。読んでいて楽しかったので失踪せずに続けたいものだ。

失敗から学ぶRDBの正しい歩き方を読んだ

DB 読書感想文

以前の達人に学ぶDB設計に引き続き下記の本を読んだ。 prelude.hatenablog.jp

失敗から学ぶRDBの正しい歩き方 (Software Design plus)

失敗から学ぶRDBの正しい歩き方 (Software Design plus)

  • 作者:曽根 壮大
  • 発売日: 2019/03/06
  • メディア: 単行本（ソフトカバー）

読んだ背景

それっぽく何が良いのかのわかったので、アンチパターンから学んでいこうという理由から。本書の内容をおおまかに分類すると「設計」「SQL」「管理」に分けられる（主観）。SQLについてはアンチパターンというよりはJOINやロックの仕組みをちゃんと押さえましょうね、という話が主だった。達人に学ぶDB設計に引き続いて設計をもう少し知りたくなったので、今回は「設計」の章についての感想を残しておく。

感想

達人に学ぶDB設計では正規化など正攻法？について学べることが多かったが、この本ではアンチパターンから学んでいくため納得させられる話が多かった。この本を読む前は実際の業務で扱うような複雑さに対処できるほどの知識はなかったので、改めてテーブル設計の難しさを感じた。

失われた状態、フラグの闇、隠された事実

これらの章に共通していたのは、データが一体何なのかわからない、ということである。

失われた状態では、過去の状態がわからないため過去の状態を元にした処理を行うことができない。例でも触れられていたが、状態が失われる設計をしていると返品による払い戻し処理などができなくなってしまう。例えば、消費税や割引額が現在と過去で変わってしまった場合、払い戻しの金額がわからなくなる。このようにその時の状態とその時のデータというものは履歴として控えておく必要があるものがあるのだ。しかし、何でもかんでも履歴として残しておくとデータサイズが増えてしまったり、状態を意識したSQLを発行する必要が出てきて複雑度が増すので、ちゃんと過去の状態・データを参照する可能性があるものだけを見定める必要はある。あと本書では触れていなかったけれど、外部キーを持つようなテーブルであったら、親が履歴を必要とする場合、子も履歴を控えた方が良いケースもあると思うので、テーブルのデータだけで完結せず、より俯瞰して設計する必要がありそう。色んなことを考えさせてくれる章で、自分も気づかずアンチパターンを踏んでいそうだな、とすごく思った。

また、似たようなものとしてフラグの闇という章がある。これは名前の通りだがフラグによる状態管理の話だ。やりがちなアンチパターンとして削除フラグがある。削除フラグが存在すると削除されたデータと削除されていないデータで似たようなデータが増えるため、カーディナリティが低くなる。カーディナリティとは列に格納されるデータにどのくらいの種類があるかを意味しており、カラムのデータの濃度のようなものである。似たようなデータが多い場合は重複があるため濃度が下がる。これによりINDEXが効きづらくなったり一意に選び取れずにメモリ効率が悪くなったり色々起きる。このようなフラグへの対処としては、事実のみを保存できるようなテーブルを設計するということだ。削除フラグでは削除済みのテーブルを作る。

さらに、隠された事実という章では、フラグに似ているが、論理ID・スマートカラムなる話が出てくる。これはIDに意味を持たせたもので、学籍番号がイメージしやすい。学籍番号は入学年度と学部学科のIDを繋げたものであるが、そのように複数の意味を持たせたIDのことを論理IDなどと呼ぶ。単一のカラムだけでなく、あるデータの属性によって入る値が変わるカラムなども同様である。これはカラムではなくテーブル単位で複数の意味を持ってしまっている。属性によってカラムの値が変わるのであれば、属性に応じてテーブルを分けた方が良い。
似たようなアンチパターンとしてEAVが上げられていた。これはtype・valueのように属性名と属性値をカラムとして持つテーブルのことで、取り出すまで属性名や属性値が一切わからない。これも本来であれば属性に応じてカラムやテーブルを用意すべきである。
しかるに、正規化をしっかり行って、カラムやテーブルに複数の意味を持たせないようにしようということである。

強すぎる制約、簡単すぎる不整合

これらの章では最適を目指した結果、それが悪手になってしまっているようなものを扱っていたように思う。DBMS側の制約とアプリケーション側の制約を適切に使うことでより良い設計ができる。

強すぎる制約では、いま現在の仕様に従って制約を作っていくと仕様変更に弱いテーブルになってしまうという話だった。制約はデータの整合性を保つために必要なものであるが、こだわって作りすぎるとイレギュラーな場合にデータを投入することすらできなくなってしまう。例えば、日時のカラムで現在時刻以降しか受け付けない制約があったとする。その場合、過去日のテストデータはどうやって用意すればよいだろうか。また、障害時にデータをどのようにリストアすればよいだろうか。
制約はテーブルだけではなくアプリケーションでバリデーションをかけてあげることで担保する方法もある。これはもちろんDB側での制約ではないため、バグが混入していると不正なデータが格納されてしまう恐れがあるが、それはそれでアプリケーション側の設計で担保すべきことでもある。要は制約をかける場所も段階的に分けることで設計を考えるべき、ということだ。

逆に、正規化を行い完璧な制約を組む話とは裏腹にパフォーマンスのために非正規化したくなる時もある。この場合はアプリケーションで整合性を担保するしかない。あるデータを変更した場合は、それに関連するデータの変更はDBMSではなくアプリケーションの責務となる。そのため、ビジネスロジックが複雑になり時間が経っても意図を残しておける運用が求められる。
これには制約を上手く使うことで回避できることもある。例えば、あるカラムのデータが特定の値だった場合は、このカラムのデータの値はこのようになるはず、という制約を組むことで非正規化されていたとしても不正なデータは混入しづらくなる。カラムに応じて制約を作るような設計は先ほどの複数の意味を持つテーブルなのでは？という疑問が湧いてくるが、パフォーマンスを上げる必要があるテーブルの場合はこの矛盾と付き合いながらベストではなくベターな解決策が必要になる。その際はこの話は非常に参考になるだろうと思った。

キャッシュ中毒

パフォーマンスの鍵だが、アーキテクチャの複雑度を大きく上げる要因でもある。

キャッシュはメモリ上のキャッシュしか考えていなかったが、それ以外にも色々あることを知った。
まず、クエリキャッシュ。これは実行されたクエリの結果がDBMS側で保持されているもの。これにより同じクエリが叩かれた時にすぐにデータを返すことができる。しかし、実行されたクエリの結果が、キャッシュなのか最新情報なのかわからなかったり、テーブルが更新されるとクエリキャッシュはクリアされてしまう。
続いて、マテリアライズド・ビューである。これは先ほどのクエリキャッシュと似ているが、実際にテーブルを作成することが違い。そのため、このマテリアライズドビューに対してINDEXを貼ったり、クエリを発行したりできる。しかし、テーブルを作成しているため、作成の元となるクエリに関係するテーブルに変更があったり、データに大きな変更があると再構築の必要がある。この再構築コストはもちろんテーブルが大きいほどかかってしまうのだが、コストがかかるようなテーブルだからこそキャッシュをしているわけなので、今回の文脈においてもやはり再構築は非常にコストが高い。
最後に、アプリケーションキャッシュである。これはredisやmemcachedなどである。RDBMSを介さないので非常に高速に動作する。しかし、他のキャッシュ同様に状態管理はやはり難しい。

キャッシュの注意点としてはデータの状態を意識することが難しいことに尽きる。参照時にどの状態なのかわかりづらいため、障害時は特に問題の切り分けが難しくなる。また、どのデータがキャッシュされているのか把握しづらいため、デバッグの難易度が高くなる。

キャッシュと付き合っていくためには、キャッシュヒット率や更新頻度を推測・計測をしっかり行っていく必要がある。また、複雑性を極力下げるためにもキャッシュの対象と範囲を見極め、生存期間と更新方法を明確にする。キャッシュがキャッシュであることを自明にしていくことで扱いやすくする。

まとめ

横着して設計を怠るとその時の生産性は一見上がったように見えるがその負債は障害時に支払うことになる。アンチパターンを見ていて思ったが、書籍の情報以上に考えることが多い。きっと筆者は文章以上の経験をやはり積んだ上で、厳選して載せているのだろう。SQLアンチパターンを引き合いにしていることが多くあったので、次回はそれを読んでみようと思う。

競技プログラミング in Go #3

競プロ Go

前回 prelude.hatenablog.jp

今回

今回は下記の記事を参考に迷路の最短路と特殊な状態の列挙のAtCoderの問題を解いていく。 qiita.com

幅優先探索

問題：C - 幅優先探索
解答：Submission #20044513 - AtCoder Beginner Contest 007

考えたこととか

[][]runeにしておくと、距離を保存する時に '1'~'9' までしか入れられないから面倒だった。距離用に [][]intの多次元配列を用意して、距離を見たい時はそっちから参照するようにした。

チーズ(Cheese)

問題：E - チーズ (Cheese)
解答：Submission #20049509 - 第１０回日本情報オリンピック 予選（オンライン）

考えたこととか

めちゃくちゃ苦戦した。計4回提出したが、大まかな方針は間違っていなかった。自作のqueueのパフォーマンスが悪かったため、queueについて少し計算を加えるような実装になっているとTLEやMLEが発生してしまっていた。これを通した時はqueueはそこまで原因になっていないと思っていたが、色々試す中で結果的にqueueに対する走査が減ったようでACとなった。これは時間を置いて再度解きたい。

Grid Repainting

問題：D - Grid Repainting
解答：Submission #20050170 - AtCoder Beginner Contest 088

考えたこととか

最大になる時は最短経路を通過する時なので、.の総数から最短経路のマスの数を引けば良い。素直な問題だったのですぐ解けた。

Darker and Darker

問題：A - Darker and Darker
解答：Submission #20050717 - AtCoder Grand Contest 033

考えたこととか

#を通過できないように前処理を入れたらあとはBFSをする。探索時に数字を渡しておいて、maxを取っていけば探索終了時にそれが答えになる。これも素直な問題だったのですぐ解けた。

器物損壊！高橋君

問題：C - 器物損壊！高橋君
解答：Submission #20134936 - AtCoder Regular Contest 005

考えたこととか

コストの扱いを考慮することはできていたけれど、上手く実装できなかった。ARC005には解説がないため、検索をして探したところ01BFSを使うと良いとのこと。なんのことかわからなかったので調べたらすごくわかりやすい記事を発見した。

itliberta.tech

これによりコストが低い選択肢が優先的に処理されるようになるため、障害物を避けた経路をより選択して探索を行うことができる。また、同じノードにたどり着く複数の経路があったとしても、01BFSではコストが低い選択肢を先に処理しているため、訪問済みとしてそのノードにチェックを入れて後続の探索で打ち切ることができる。

キューにpushFrontを実現するため、SliceTricksを見ながら実装を行った。
SliceTricks · golang/go Wiki · GitHub

しかしこれはTLEになってしまう。 f:id:TakumiKaribe:20210214191418p:plain

先ほどのチーズ(Cheese)ではキューの実装が悪かったためにTLEになっておりキューに対する処理を減らすことでACできたが、今回はそうはいかなかった。そのため他の人の01BFSを使った解答を見たら下記のパッケージを使っていることがわかった。
go/src/container/list at master · golang/go · GitHub

SliceTricksの実装だとappend時に配列をたくさん作ることになり、特にpushFrontでは要素の長さだけ毎回メモリを確保してしまっていたのだと思う。なのでcontainer/listのようにlinked listになっていると非常に高速になった。

One-stroke Path

問題：C - One-stroke Path
解答：Submission #20176878 - AtCoder Beginner Contest 054

考えたこととか

探索できたものを数えれば良いのでそう実装していたのだがWAになってしまった。サンプルだけ通っていて何が起きているのかわからず解説を読んで通した。

WAの原因はindexの取り違いだった。for-rangeで回していた二次元配列の値をindexと間違えていて、DFSで誤った値が処理されていた。二次元配列のループはfor-rangeにせずにふつうにiをインクリメントしながら走査してvec[i][j]と値を見た方が直感的な気がした。

解説に載っていたDFSの前後でvisitedをtrue/falseとするコードはすごく良かったので取り入れて解答した。これを読む前はDFSで再帰する際にcopyして渡していたので、かなりメモリ効率が良くなったと思う。

カード並べ

問題：D - カード並べ
解答：Submission #20177931 - 第９回日本情報オリンピック 予選（オンライン）

考えたこととか

数が少ないので全部列挙してしまうのが良さそう。また、数字だと桁を考慮しないといけないので数字で扱うよりも文字列で扱って、mapのlenを取る実装が良さそう。懸念として文字列の結合コストがある。ここだけは気になる。

実際に実装してそれでOKだった。ただ、選択した数字のインデックスに対応して[]boolをtrueにして選び取る実装をしてしまい時間を食ってしまった。[]intにして選択したものをappendしてその順序を維持してmapに突っ込む。AC。

One-stroke Pathで学んだdfsの前後で状態をコントロールする実装ができたので嬉しい。

まとめ

DFSもBFSも特に迷わず実装できているけれど、状態をどうコントロールするのかまだスラスラ書けないので制約が増える度に手が遅くなるのを感じる。ただ書いていてすごく楽しい。