# Incast ## 定義 Incast(多対一輻輳)とは、多数のフローが短い時間内に同一スイッチポートへ殺到し、スイッチのパケットバッファを枯渇させる現象である。データセンターの Partition/Aggregate 通信パターンに起因し、1 つの集約(アグリゲータ)リクエストに対して多数のワーカーが同期して応答を送信することで発生する。浅バッファスイッチでは 1 パケットの損失でも TCP タイムアウト(RTO)が発生し、アグリゲータの締め切りを超過させる。 ([[@2010__SIGCOMM__Data Center TCP (DCTCP)]]) ### 発生メカニズム 1. アグリゲータが N 台のワーカーへ同時にリクエストを送信 2. ワーカーの応答が高度に同期して集約用スイッチポートに殺到(Incast) 3. 共有メモリスイッチのバッファが枯渇し、パケットが廃棄される 4. 各応答は 2 KB 程度の小さいフローでも、N 個が同期するとバッファを超過する 5. TCP タイムアウト(RTO_min = 300 ms がデフォルト)により、その応答はアグリゲータの締め切り(10〜100 ms)を必ず超過する ### 本番環境での観測 Microsoft の本番データセンター(6000 台超)では、Incast が実際に発生しアプリケーション収益に影響することが確認されている。開発者は 2 つの回避策を適用していた: - **応答サイズの制限**: 全応答がスイッチメモリに収まるよう 2 KB に制限 - **ジッタリング**: 10 ms 窓内でランダムな遅延を意図的に挿入。中央値レイテンシが増加する副作用がある(図8参照) RTO_min を 1 ms や 300 µs に下げる提案(先行研究 [Vasudevan+, SIGCOMM 2009])も存在するが、タイムアウトは回避できてもキュー蓄積によるレイテンシ増加は解消できない。 ## 横断的知見 - **Incast 解消のアプローチは「タイムアウト短縮」と「キュー長制御」の 2 種類が存在し、後者が根本解決策である**: RTO_min の短縮(Vasudevan+ SIGCOMM 2009)はタイムアウトを減らすが、バッファが枯渇しない状況でのキュー蓄積由来のレイテンシは解消できない。DCTCP(Alizadeh+ SIGCOMM 2010)は ECN による段階的輻輳制御でキュー長を低く保つことで、パケット損失そのものを回避する。(Source: [[@2010__SIGCOMM__Data Center TCP (DCTCP)]]) - **深バッファスイッチは Incast の部分的な緩和策にすぎず、短メッセージのキュー蓄積という副作用を生む**: Cisco CAT4948(16 MB バッファ)を使うと、TCP の Incast によるクエリ完了時間は DCTCP と同等になるが、短メッセージ(100 KB〜1 MB)の完了時間が 80 ms 超に悪化する。これはバッファが大きいほど長フローによるキュー蓄積も増大するためである。(Source: [[@2010__SIGCOMM__Data Center TCP (DCTCP)]]) - **アプリケーション層でのスライディングウィンドウによる incast 緩和**: Facebook memcache では all-to-all 通信パターン(ウェブサーバ全台が全 memcached サーバに通信)により、多数の応答が同時にスイッチに殺到する。TCP/ECN ではなく**クライアント側スライディングウィンドウ**で同時リクエスト数を制限する方式を採用している。ウィンドウサイズが小さすぎると逐次処理が増えレイテンシ悪化、大きすぎると incast でパケット損失→DB フォールバックが多発という U 字型の最適点が存在する。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) - **DCQCN が解決しようとするインキャストは Incast と異なる構造を持つ**: DCTCP が対象とする Incast は TCP スロースタートと 2 の 1 削減に起因するバースト問題。DCQCN が対象とする問題は RoCEv2 + PFC 環境での head-of-line blocking と被害者フロー問題であり、輻輳発生後の伝播経路が異なる。(Source: [[@2010__SIGCOMM__Data Center TCP (DCTCP)]], [[@2015__SIGCOMM__Congestion Control for Large-Scale RDMA Deployments]]) ## 未解決の問い - DCTCP でも解消できない「ワーカー数が非常に多く初回 RTT の 1 パケットだけでバッファを超過する」ケースへの対処法は何か。トラフィックスケジューリング以外の選択肢はあるか。 - Incast はデータセンター内だけでなく、CDN のオリジンサーバーへの集約や AI クラスタでの all-reduce にも類似した構造が存在するか。 - RTO_min の短縮と ECN ベース輻輳制御の組み合わせは相乗効果があるか。DCTCP + 短 RTO の共存はどう設計するか。 ## 関連 - 概念: [[データセンター輻輳制御]] / [[Partition/Aggregate]] / [[分散キャッシュ]] - ソース: [[@2010__SIGCOMM__Data Center TCP (DCTCP)]] / [[@2013__NSDI__Scaling Memcache at Facebook]] - エンティティ: [[Mohammad Alizadeh]] / [[Albert Greenberg]] / [[Facebook]] ## 出典 - [[@2010__SIGCOMM__Data Center TCP (DCTCP)]] - [[@2013__NSDI__Scaling Memcache at Facebook]]（§3.1——memcache の all-to-all 通信に起因する incast とスライディングウィンドウ緩和）