Node.js– tag –
-
システム設計 深掘り
指数バックオフとバルクヘッド — リトライが障害を長引かせる
落ちかけている相手に素朴なリトライを投げると、負荷が3倍になって復旧を邪魔する。この記事では Node.js で「呼ぶ側」と「呼ばれる側」を自分で書き、わざと壊して、到達回数を数えます。素朴なリトライ・指数バックオフ・ジッタの3つを実測で比べ、バックオフだけでは再送の波が揃ってしまうことを確かめます。さらに、遅い相手が全体のコネクションを食い潰す様子をバルクヘッド(同時実行数の隔離)で止め、nginx の upstream で primary を1台落として backup へ切り替わるところを見ます。最後に、全部止めずに古いデータを返す「縮退」を実装し、どの型をいつ入れるかの優先順位で締めます。作業は VM の中の ~/rellab で行い、終わったら全部消します。 -
システム設計 深掘り
イベント駆動アーキテクチャ — 機能を足すたび注文APIが壊れる
注文が入ったらメールを送り、在庫を減らし、売上集計を更新する。この3つを注文APIから順に呼ぶ形で作ったところ、メールサーバーを1つ落としただけで注文そのものが500になりました。この記事では同じ機能を Redis Streams のイベント形に組み替え、購読側を1つ落としても注文が通ること、機能を1つ足しても注文APIを1行も触らずに済むことを実測します。そのうえで代償を正面から測ります。全体の流れがどこにも書かれていないこと、相関IDが無いと追跡できないこと、注文直後にメール履歴がまだ無いこと、同じイベントが2回届くことを、わざと起こして確かめます。続いてコマンドとイベントの違い、指揮者を置く形と各自が反応する形を比べ、CQRSでは20万件の集計クエリと、イベントで更新しておいた集計テーブルの実行時間を並べます。最後にイベントソーシングを小さく実装し、再生が遅くなるところまで見てから「大半のアプリには要らない」と結論を書き、立てたものを全部消します。 -
システム設計 深掘り
遅いアプリのアンチパターン7つ — 推測では当たらない
「遅いアプリ」には決まった書き方があります。この記事では Docker Compose で MySQL を1つ立て、1万件のダミーデータを入れ、遅くなる書き方を7つ、わざと自分の手で書きます。SQLを101回打つ版とJOIN 1回の版、全行を取ってアプリで絞る版とWHEREで絞る版、readFileSyncが他の全リクエストを止めるところ、リクエストごとに接続を作る版とコネクションプール、DBに文字列処理をさせて張り付かせる版とその逆、1本の重い処理が軽いAPIを巻き込むところ。すべて「悪い版を測る→直す→また測る」の形で、何倍になったかを数字で出します。最後に一番大事な実験として、推測で直した箇所が全体の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 が二分探索そのものだという話。 -
コンピュータ科学 深掘り
ソートアルゴリズム6種 — 並べ替えたら10が2の前に来た
3件の配列を並べ替えただけで 1, 10, 2 が返ってきたとき、私は自分のコードのどこかにバグがあると思って30分探しました。バグはありませんでした。この記事では VM の中に ~/cslab/sort を作り、バブル・選択・挿入・マージ・クイック・ヒープの6つを自分で書きます。同じ4種類のデータで、時間だけでなく比較回数と書き込み回数を数えて1枚の表にします。すでに並んでいるデータで自作クイックソートを走らせて Maximum call stack size exceeded を出し、軸の選び方を変えて直るところまでやります。同点データを並べ替えて「安定」が何のことかを出力で見て、最後に V8 の sort と全部を測り比べて ~/cslab を消します。