キュー– tag –
-
システム設計 深掘り
非同期処理とジョブキュー — 1つの遅い処理が全部を止める
画像を1枚上げるのに30秒待たされる画面を、待たせない形に組み替えます。まず3秒かかる処理を持つエンドポイントを本当に作り、hey で同時に叩いて、無関係な /health まで巻き込まれて遅くなるところを実測します。1つの遅い処理が全体を止める——本線のサーキットブレーカと同じ構図です。次にキューへ積んで 202 Accepted を返し、ワーカーに処理させ、同じ負荷で応答時間が戻ることを測ります。そのかわり利用者からは「終わったか」が見えなくなるので、結果の返し方をポーリング・Webhook・WebSocket/SSE の3方式で対比し、ポーリングを実装します。さらに同じ依頼が2回来ても2回実行されないよう、依頼IDで記録して冪等にします。最後にどこまで非同期にするかの判断表、非同期にすると増える仕事、無限に積まないためのバックプレッシャーまでやって、後片づけします。 -
コンピュータ科学 深掘り
スタックとキュー — call stack size exceeded の正体
終わらない再帰を書いて Maximum call stack size exceeded を出したとき、私は「JavaScriptが疲れた」くらいの理解でした。実際は、自分がその日 push と pop で作ったのと同じものが、言語の内側で溢れていただけでした。この記事では VM の中に ~/cslab/sq を作り、スタックとキューを手で書きます。全部 O(1) であることを実測し、わざとエラーを出して積める段数を数え、スタックトレースが下から読める理由を出力で確かめます。キューは配列の shift() で作ってから 10万件で測り、先頭の位置を持つ形に直して同じ測定で速くなることを見ます。最後に setTimeout と Promise の実行順を出して、イベントループもキューだったことを確かめて全部消します。 -
プログラム
配列は先頭への挿入が遅い — データ構造を自作する
配列と Map があれば大抵のプログラムは書けます。それなのに教科書には連結リスト・ハッシュ表・木が必ず出てくる。理由は「それぞれ何が速くて何が遅いかが違う」からです。まず配列の先頭挿入が遅いことを10万件で実測し、連結リストを書いて逆転させ、次にハッシュ表を40行で書いて Map の中身を開け、バケツを4つに減らして衝突が O(n) に近づくところを測ります。最後に二分探索木を書き、昇順に入れると一直線に潰れて再帰が Maximum call stack size exceeded で落ちるところまで実際に起こします。OS自作のフリーリストも、自作データベースの索引も、この3つのどれかでできていました。
1