歴史: Go 1.14以前、ランタイムは中央ロックによって保護された単一のグローバルタイマーヒープを維持していました。タイマーを作成または変更するすべてのゴルーチンがこのロックを争奪し、高スループットのネットワークサーバーで数千の同時接続を管理する際に深刻なスケーラビリティのボトルネックを生じさせました。
問題: コア数が増えたことで、グローバルタイマーのロックは直列化ポイントとなりました。ゴルーチンがtime.AfterFuncを呼び出したり、既存のタイマーを変更したりすると、グローバルロックを取得し、4-ヒープ構造を更新し、必要に応じて専用のタイマースレッドを起こす必要がありました。この直列化されたアクセスは、タイマー操作がCPUコアと共に水平方向にスケーリングされるのを妨げ、負荷下での尾部レイテンシを劣化させました。
解決策: Go 1.14はタイマーシステムを再設計し、Pごとのタイマーヒープを使用するようにしました。各論理プロセッサは、自身の64-ヒープ（4-ヒープの変種）を維持します。タイマーが作成またはリセットされると、ランタイムはタイマーの状態ワードに対して原子比較とスワップ操作を用いたロックフリーアルゴリズムを実行します（タイマーはruntime.timer構造体で表されます）。タイマーが所有者とは異なるPによって変更された場合、ランタイムは原子更新を使用して、元のゴルーチンをブロックせずにヒープ間で移動させます。タイマー処理は現在、スケジューラのfindRunnableループに統合されており、各Pはグローバル同期なしでローカルヒープをスキャンできるようになっています。
// タイマー変更の概念的表現 func resetTimer(t *timer, when int64) { // 原子操作を使ったロックフリーの状態遷移 for { old := atomic.Load(&t.status) if old == timerWaiting || old == timerRunning { // 原子性で奪うまたは更新を試みる if atomic.CompareAndSwap(&t.status, old, timerModifying) { t.when = when // ローカルPのヒープ内で再バランス atomic.Store(&t.status, timerWaiting) break } } } }
問題の説明: Goで書かれた高頻度取引ゲートウェイが、市場オープン時に10msを超えるレイテンシスパイクを経験しました。CPU使用率は低かったものの、プロファイリングにより、すべてのミューテックス競合の40%がruntime.timer操作から発生していることがわかりました。接続の読み取り期限をSetReadDeadlineを介して延長する操作が問題でした。運用チームは当初ネットワークのレイテンシを疑いましたが、Goの実行トレーサーがグローバルタイマーのロックを犯人として特定しました。
検討された異なる解決策:
一つのアプローチは、標準ライブラリの外でユーザースペースのタイミングホイールを実装することでした。これにより、タイマーを有効期限に基づいてバケットにシャーディングし、固定サイズの循環バッファを使用しました。この方法はランタイムのロック競合を排除しましたが、重要な複雑さをもたらしました：トレーディングチームはホイールの進行を維持するために別のゴルーチンを管理しなければならず、長いタイムアウトのためにオーバーフローバケットを処理し、ランタイムの保証なしでメモリの安全性を確保する必要がありました。さらに、ホイールの粒度はサブミリ秒取引の要件には不十分であり、実装のメンテナンスの負担をリスクとしていました。
別の考慮された解決策は、time.Timerオブジェクトを積極的にプールして再利用し、アロケーションを最小限に抑えることでした。これによりGC圧力は低下しましたが、Reset()またはStop()を呼び出す際のグローバルタイマーのロックでの根本的な競合は解決されませんでした。チームはまた、time.Tickerを使用して期限のバッチチェックを試みましたが、これは超過した場合に即座に接続を終了するという取引所の要件に違反しており、規制仕様に準拠しませんでした。
選択された解決策と結果: チームはGo 1.15に移行し（Pごとのタイマー改善を取り入れて）、直接のSetReadDeadline呼び出しを、time.AfterFuncコールバックを通じて期限延長を管理するカスタム接続ラッパーに置き換えました。この変更により、すべての利用可能なPにわたってタイマーエントリーが分散され、ミューテックス競合が無視できるレベルに減少しました。その結果、ピーク取引量中のp99レイテンシが95%削減され（12msから0.6msへ）、ゲートウェイが100,000の同時接続をスケジューラの劣化なしに処理できるようになりました。
ランタイムはゴルーチンがP間を移動する際にタイマーの移動をどのように処理し、なぜタイマーは単にゴルーチンに従うことができないのか？
タイマーは作成されたPまたは最後にリセットされたPにバインドされ、ゴルーチンにはバインドされません。ゴルーチンがワークスティーリング中にP間で移動すると、タイマーは元のPのヒープに残り、毎回のコンテキストスイッチ中の原子オーバーヘッドを回避します。タイマーが発火すると、ランタイムは関連するゴルーチンが異なるPで実行されていることを認識し、そのPの実行キューにコールバックをエンキューします。この分離は重要です。なぜなら、タイマーヒープはヒープ不変性の維持を必要とし、ゴルーチンと共にタイマーを移動させることは毎回の奪取中に元のPと移動先Pのタイマーヒープをロックする必要があり、このことがPごとの設計が排除した競合を再導入するからです。
タイマー実装において、4状態の原子状態マシン(timerIdle, timerWaiting, timerRunning, timerModifying)が必要な具体的な競合条件は何ですか？
状態マシンは「失われたウェイクアップ」競合を防ぎます。タイマーが実行のために選択された後だがコールバックが実行される前に、後の時間にリセットされる場合です。原子状態がない場合、P Aはそのヒープからタイマーを選択し（実行中としてマーク）、同時にP Bがそれをリセットする可能性があります。4つの状態は、Reset操作がtimerModifyingまたはtimerRunning状態を見ることを保証し、タイマーが安全に変更できるまでスピンします。候補者はしばしば、timerModifyingが状態変更中にトランジェントスピンロックとして機能し、古いデータでコールバックが実行されるのを防ぐか、完全にドロップされるのを防ぐことを見逃します。
ランタイムはなぜタイマーに対して67-ヒープ構造を維持するのか、そしてこれがキャッシュライン最適化にどのように関連しているのか？
64-ヒープ（4-ヒープ）は、ツリーの深さをlog₄(n)レベルにまで減らし、sift-upとsift-down操作中のポインタチェイシングとキャッシュミスを最小限に抑えます。標準のバイナリヒープでは、各比較は2つの子を読み込む必要があり（潜在的に2つのキャッシュライン）、4-ヒープでは一度に4つの子を読み込み、現代のx86_64アーキテクチャの60バイトのキャッシュラインに収まります。この構造は意図的な妥協です。比較の数はレベルごとに増えますが、キャッシュミスが大幅に減少し、Pごとに何千ものタイマーを管理する際のタイマーヒープ操作のレイテンシを支配します。