深掘り– category –
**本線を一周した人向け。** roadmap.sh のコースを1つ選んで、その中を細かく潰していく記録。**順路ではありません。** 必要になったコースだけ読んでください。
-
システム設計 深掘り
結果整合性とCAP定理 — リロードしたら件数が減った
レプリカを1台足した翌日、「投稿したのに一覧に出ない」「リロードしたら件数が減った」という報告が来ました。バグではなく、読む先を増やした瞬間から必ず起きることです。この記事では MySQL の primary 1台 + replica 1台を Docker Compose で立て、replica にわざと遅延を作って「書いた直後に自分の書き込みが読めない」ところを実測します。単調読み取りが崩れて件数が減る様子、返信が本文より先に見える因果の逆転も、実際にコマンドの出力として再現します。そのうえで強整合にする手段を3つ試します。primary から読む、SELECT ... FOR UPDATE、準同期レプリケーション。それぞれ何ミリ秒遅くなるかを測ります。最後に docker network disconnect で replica を切り離し、古い値を返すかエラーを返すかの二択しか無いことを目で見て、業務ごとにどちらを選ぶかの判断表を作ります。立てたものは全部消します。 -
システム設計 深掘り
可用性とSLO — 99.9%は月に43分しかない
「99.9%を目指します」と書いてから、それが月に何分の停止かを知りませんでした。この記事ではまず9の数を年・月・週・日の分数に直す小さなスクリプトを書き、99.9%が月43分しかないことを数字で確かめます。次に直列と並列で可用性がどう動くかを計算し、部品を足すと可用性が下がることを表で見ます。そのうえでVMに nginx とバックエンド2台を Docker Compose で立て、1台を止めた状態で curl を回し続けて「落ちていた時間」ではなく「失敗したリクエストの割合」を数えます。fail_timeout を変えて復旧時間が変わることを実測し、MTBF と MTTR から可用性を出し、SLA・SLO・SLI とエラーバジェットを月43分として計算します。最後に、個人サイトにどこまで必要かを金額と並べて判断します。 -
システム設計 深掘り
遅いアプリのアンチパターン7つ — 推測では当たらない
「遅いアプリ」には決まった書き方があります。この記事では Docker Compose で MySQL を1つ立て、1万件のダミーデータを入れ、遅くなる書き方を7つ、わざと自分の手で書きます。SQLを101回打つ版とJOIN 1回の版、全行を取ってアプリで絞る版とWHEREで絞る版、readFileSyncが他の全リクエストを止めるところ、リクエストごとに接続を作る版とコネクションプール、DBに文字列処理をさせて張り付かせる版とその逆、1本の重い処理が軽いAPIを巻き込むところ。すべて「悪い版を測る→直す→また測る」の形で、何倍になったかを数字で出します。最後に一番大事な実験として、推測で直した箇所が全体の2%しか占めていなかったことを実際に作って確かめ、症状から疑う場所を引ける表にまとめます。立てたものは全部消します。 -
システム設計 深掘り
メッセージキューの型 — 急ぎの仕事が後ろで待つ
キューを1本立てたら、5分かかる動画変換の後ろで、1秒で終わるパスワード再設定メールが待たされました。キューは「1本立てれば終わり」ではなく、型があります。この記事では RabbitMQ を1つ立て、同じメッセージを「分担する」形と「全員に配る」形の両方を実際に作り、ワーカーを2つ並べて届き方の違いを目で見ます。続いてワーカーを増やして処理時間が縮むのを実測し、prefetch を設定しないと遅いワーカーに仕事が積まれることを再現して直します。優先度キューでは急ぎを先に通したうえで、優先度の低い仕事が永久に処理されない飢餓をわざと起こし、対策を3つ比べます。さらに300件を一気に投げて負荷平準化を実測し、リトライの回数制限とデッドレターキューを実際に作り、順序が要る場合の2つの逃げ道、遅延キューやファンアウトの型、そして「キューを使わない」という選択まで。最後に立てたものを全部消します。 -
コンピュータ科学 深掘り
CPUの仕組みを自作する — 足し算しかしていない
CPUを「魔法の箱」で終わらせないために、手元で全部作って動かします。2の補数をJavaScriptで組んで引き算を足し算に置き換え、AND・OR・XOR・NOTの4関数だけから8ビット加算器を作って0〜255の全組み合わせでJavaScriptの + と一致することを確認します。命令が10個だけの極小CPUシミュレータを書いてフェッチ・デコード・実行を1サイクルずつ表示させ、レジスタ版とメモリ版でアクセス回数を数えます。最後に本物のCPUを lscpu と gcc -S で覗き、キャッシュの効き方を実測して、割り込みの回数が増える瞬間を vmstat で見ます。 -
コンピュータ科学 深掘り
スタックとキュー — call stack size exceeded の正体
終わらない再帰を書いて Maximum call stack size exceeded を出したとき、私は「JavaScriptが疲れた」くらいの理解でした。実際は、自分がその日 push と pop で作ったのと同じものが、言語の内側で溢れていただけでした。この記事では VM の中に ~/cslab/sq を作り、スタックとキューを手で書きます。全部 O(1) であることを実測し、わざとエラーを出して積める段数を数え、スタックトレースが下から読める理由を出力で確かめます。キューは配列の shift() で作ってから 10万件で測り、先頭の位置を持つ形に直して同じ測定で速くなることを見ます。最後に setTimeout と Promise の実行順を出して、イベントループもキューだったことを確かめて全部消します。 -
コンピュータ科学 深掘り
バランス木とB木 — 100万件が3段で届く
二分探索木は「毎回半分に絞れるから速い」と習いました。ところが 1,2,3,... と並んだ 10,000件を入れたら、高さが 10,000 になりました。木ではなく連結リストです。この記事では VM の中に ~/cslab/btree を作り、その症状を実測してから AVL木を自分で書きます。回転を図で暗記せず、単回転と二重回転を実装して、同じ 10,000件で高さが 14 に収まることを確かめます。赤黒木は実装せずルールだけ読み、B木がなぜデータベースの索引なのかを段数の計算で出します。最後にトライでオートコンプリートを作り、スキップリストと比べて、全部消します。 -
コンピュータ科学 深掘り
ハッシュテーブル — 10万件のincludesで止まる
10万件の配列に includes を書いたら画面が止まりました。Set の has に変えたら一瞬で終わり、そのとき私は「Setは速い」で納得してしまいました。この記事では VM の中に ~/cslab/hash を作り、その差が何倍あるのかを実測してから、ハッシュ関数とハッシュテーブルを自分の手で書きます。バケットの中身を表示して、どのキーがどこに入ったかを目で見て、わざと衝突させて O(1) が O(n) に落ちる瞬間を表にします。負荷率とリサイズを実装して、リサイズが起きた15回だけ平均の3万倍遅くなることを測ります。最後にハッシュと暗号化とエンコードを sha256sum と base64 で並べて確かめ、Object と Map と Set と WeakMap の使い分けを表にして全部消します。 -
コンピュータ科学 深掘り
ヒープとLRUキャッシュ — 10件欲しいだけで100万件ソート
ランキングの上位10件を出すために、私は100万件を毎回まるごとソートしていました。必要なのは10件なのに、残りの999990件を丁寧に並べ替えていたわけです。この記事では VM の中に ~/cslab/heap を作り、サイズ10のヒープを手で書いて、全部ソートする版と実測で比べます。ヒープが「木なのにポインタを1つも使わず、配列1本で持てる」ことを添字の計算で確かめ、内部配列を表示してヒープがソートされていないことを見ます。後半はLRUキャッシュを素朴な O(n) 版から O(1) 版へ直し、容量を変えながらヒット率を実測します。最後に LRU・LFU・MFU・FIFO・ランダムを同じアクセス列で走らせ、LFU が「昔たくさん使われたもの」に居座られて負ける瞬間を数字で出してから、全部消します。 -
コンピュータ科学 深掘り
線形探索と二分探索 — 1回引くだけなら並べると損
「二分探索のほうが速い」は、並べる時間を勘定に入れていない。ソートは O(n log n)、探索は O(log n)。1回しか引かないなら、線形探索のほうが速い。何回引いたら並べるべきかを、実際に交差点が出るまで測る。二分探索の実装でよく踏む3つの間違いをわざと出して直し、「見つからないときどこに入れるか」を返す版まで作る。最後にハッシュとの使い分け、総当たりが正解になる場面、そして git bisect が二分探索そのものだという話。