> [!abstract] 概要(Abstract の日本語訳)
> データセンターは世界最大級かつ最速のネットワークを収容している。その速度とは対照的に、またその速度の結果として、これらのネットワークは非常に小さな時間スケールで動作する──100 Gbpsのポートは単一パケットを最大500 nsで処理し、エンドツーエンドのネットワーク遅延は1ミリ秒未満である。本研究では、大規模な本番データセンターにおけるラック単位トラフィックの極めて高分解能な測定(数十から数百マイクロ秒)を用いて、そのきめ細かな挙動を探る。我々の結果は、データセンターにおける輻輳や同期的挙動といったネットワークイベントの特性評価には、実際にこのような測定が必要であることを示している。実際、我々が測定したラックにおけるバーストの70%超が、最大でも数十マイクロ秒しか持続しないことを観測した。これはほとんどの既存の測定フレームワークよりも桁違いに高い分解能の範囲である。より粒度の粗い測定によって観測される輻輳イベントは、実際にはより小さなµburstの集合である可能性が高い。したがって、我々はエッジにおけるトラフィックが、他の指標が示唆するよりも著しく不均衡であることを見出した。測定粒度への含意を超えて、我々はこれらの結果が将来のデータセンターの負荷分散および輻輳制御プロトコルに情報を与えることを期待する。
## 論文情報
- タイトル: High-Resolution Measurement of Data Center Microbursts
- 著者・所属: Qiao Zhang([[University of Washington]])、Vincent Liu([[University of Pennsylvania]])、Hongyi Zeng([[Facebook]], Inc.)、Arvind Krishnamurthy([[University of Washington]])
- 媒体・発表年: IMC '17(Internet Measurement Conference)、2017年11月1〜3日、ロンドン、英国
- DOI: [10.1145/3131365.3131375](https://doi.org/10.1145/3131365.3131375)
- 生データ公開先: https://github.com/zhangqiaorjc/imc2017-data(論文中の脚注に記載)
## 概要
本論文は、Facebookの本番データセンターのToR(Top-of-Rack)スイッチを対象に、25µs〜300µs級の超高分解能カウンタ収集フレームワークを独自構築し、既存の分単位SNMP測定やパケットサンプリングでは捉えられない「µburst(1ms未満の高利用率期間)」の存在と性質を初めて定量的に示した実測研究である。Web・Cache・Hadoopという性質の異なる3種類のラックを比較し、バーストの持続時間分布・バースト間隔・パケットサイズ分布・アップリンク負荷分散・サーバ間相関・共有バッファ占有の6つの観点から特性評価を行っている。
## 問題設定
- **入力**: 本番データセンターのToRスイッチが保持するバイトカウンタ・パケットサイズヒストグラム・ピークバッファ利用率という3種類のスイッチ統計カウンタを、独自フレームワークで25µs〜300µs粒度でポーリングした時系列データ。
- **前提条件**: 対象は3層Clos網([[@2018__IMC__A Large Scale Study of Data Center Network Reliability|参考: データセンターネットワーク信頼性の関連文献]]と同様の一般的構成)における ToR-server 間リンク。測定は Web・Cache・Hadoop の3種のアプリケーションが稼働する各10ラック、計30ラックを対象に、24時間にわたり1時間ごとに2分間のランダムなインターバルを抽出する形で行われた(合計720インターバル、約5億データ点、250 GB)。フルデータを保持すれば数百テラバイトに達するため、この間引きサンプリングが必要になった。
- **必要なデータ**: スイッチASIC側のカウンタをCPU(スイッチプラットフォームに搭載された汎用マルチコアCPU)がポーリングし、分散コレクタサービスへ送信する専用計装。既存のSNMPやsFlowでは到達できない粒度が必要。
## 提案手法
- **アーキテクチャ**: 現代のスイッチがパケット処理用ASICとは別に、制御プレーン処理用の汎用マルチコアCPUを搭載している点を利用する。ASICが保持するカウンタをCPU側から低遅延でポーリングし、サンプルをバッチ化したうえで分散コレクタへ送信する。専用コアを割り当てれば高精度なタイミングを得られるが、精度を犠牲にすればCPU利用率を20%以下に抑えられる。
- **カウンタ設計と最小ポーリング間隔の決定**: バイトカウンタでは、サンプリング欠損率(missed intervals)を実測しながら最小ポーリング間隔を手動で決定した。1µs間隔では欠損率100%、10µsで約10%、25µsで約1%となり、25µsが採用された(下表 Table 1)。欠損が発生してもタイムスタンプとバイト数から正確なスループットを再計算できる設計になっている。
- **収集する3種の統計**:
- **バイトカウント**: スイッチポートごとの累積送受信バイト数。25µs粒度で低損失にポーリング可能。スループット計算に使用。
- **パケットサイズ**: ASICが送受信パケットを複数バケットにビニングしたヒストグラム。バイトカウンタとほぼ同じ粒度で取得可能。
- **ピークバッファ利用率**: 直近の測定以降のバッファ利用率のピーク値を保持し、読み取り後にリセットする。ポーリングを取りこぼしてもバーストを見逃さない設計。ただしポーリングに50µsを要し、他の2カウンタより粒度が粗い。
- **バースト定義とMarkov連鎖による相関検証**: 測定期間内でエグレスリンクの利用率が50%を超える状態を「hot」(x_t=1)と定義し、連続するhotサンプル区間を1回のバーストとする。バースト間の相関を検証するため、25µs区間ごとの hot/not-hot を2状態1次マルコフモデルとして遷移行列を推定し、尤度比 r = p(x_t=1|x_{t-1}=1) / p(x_t=1|x_{t-1}=0) を計算した。
## 新規性
既存研究は大きく2つのアプローチに限定されていた: (1) tcpdump やsFlow・iptablesによるパケットサンプリング(Facebookの本番では1/30,000程度の確率でしかサンプリングされない)、(2) SNMPに代表される分単位の粗粒度カウンタ収集。いずれも数十〜数百マイクロ秒スケールのバースト挙動を捉えられない。ハードウェア改造による高精度測定の提案([10, 12, 14, 20])も存在するが、大規模本番環境への広範な展開実績がなかった。本研究は、既存の運用中スイッチプラットフォームに搭載済みの汎用CPUを転用することで、追加ハードウェアなしに25µs粒度の本番測定を実現した点が新規性である。
## 実験設定
- **実験環境**: Facebookの本番データセンター内、3層Clos網の ToR-server 間リンク(10 Gbpsイーサネット)。ToRはさらに40 Gbpsまたは100 Gbpsでfabricスイッチ層に接続。
- **データセット**: Web(ステートレスなwebリクエスト応答)・Cache(memcache的な読み取り主体のキャッシュ、leader/followerで構成される[[@2013__NSDI__Scaling Memcache at Facebook|Scaling Memcache at Facebook]]的アーキテクチャ)・Hadoop(オフライン分析用、インタラクティブパスに含まれない)の3種、各10ラック、24時間分。
- **比較対象**: 明示的なbaseline手法との比較ではなく、測定粒度そのものを比較変数として扱う(25µs〜300µs の高分解能 vs 1s〜4分の低分解能)。
- **評価指標**: バースト持続時間のCDF、バースト間隔のCDF、パケットサイズ分布、アップリンク利用率のMAD(平均絶対偏差)、サーバ間Pearson相関係数、正規化ピーク共有バッファ占有率。
## 実験結果
### 粗粒度測定では輻輳を説明できない
4分間隔でランダムサンプリングしたToR-serverリンクの平均利用率と平均ドロップ率の散布図では、利用率とドロップ率の相関係数はわずか0.098だった。
**Figure 1: 利用率とドロップ率の散布図(粗粒度)**
![[_attachments/imc17-final60/fig01-drop-vs-utilization-scatter.png]]
(Figure 1. ToR-serverリンクのドロップ率と利用率の散布図。4分粒度で1時間に1回サンプリングし24時間分をプロット。輻輳による廃棄のみを含みパケット破損は含まない。相関係数は0.098と弱い。)
低利用率ポート(∼9%、webのクリティカルパス)と高利用率ポート(∼43%、オフラインデータ処理)を1分粒度で12時間観測すると、いずれもドロップは測定粒度(1分)より短いバースト状に発生し、後続区間ではドロップがゼロになることが多い。
**Figure 2: 2種のポートにおけるドロップの時系列(1分粒度、12時間)**
![[_attachments/imc17-final60/fig02-drops-timeseries.png]]
(Figure 2. (a) 低利用率ポート(∼9%)、(b) 高利用率ポート(∼43%)。いずれもドロップがバースト状に集中し、後続の多くの区間ではドロップがゼロになる。)
### µburstの存在と持続時間分布
25µs粒度で計測すると、バーストの大部分は1サンプリング周期(25µs)のみで終了する。90パーセンタイル持続時間は全3ラック種別で200µs以下であり、Webラックが最短(50µs、2サンプリング周期)、Hadoopラックが最長の裾を持つが、それでもほぼ全てのバーストは0.5ms以内に終息する。
**Figure 3: µburst持続時間のCDF(25µs粒度)**
![[_attachments/imc17-final60/fig03-cdf-microburst-duration.png]]
(Figure 3. Web・Cache・Hadoopともに60%超のバーストが単一サンプリング周期(25µs)以内で終了しており、25µs自体が測定粒度としてなお粗すぎる可能性がある。)
### バーストの相関(マルコフ連鎖)
2状態マルコフモデルの遷移行列(下表)から尤度比を算出すると、Web=119.7、Cache=45.1、Hadoop=15.6となり、いずれも1から大きく乖離した。これは高利用率サンプルが独立到着ではなく強く相関していることを示す。
**Table 2: バーストマルコフモデルの遷移行列**
| p(x_t \| x_{t-1}) | Web x_t=0 | Web x_t=1 | Cache x_t=0 | Cache x_t=1 | Hadoop x_t=0 | Hadoop x_t=1 |
|---|---|---|---|---|---|---|
| x_{t-1}=0 | 0.997 | 0.003 | 0.984 | 0.016 | 0.958 | 0.042 |
| x_{t-1}=1 | 0.641 | 0.359 | 0.279 | 0.721 | 0.345 | 0.655 |
(Table 2. Burst Markov Modelの遷移行列。尤度比 r_web=0.359/0.003=119.7、r_cache=0.721/0.016=45.1、r_hadoop=0.655/0.042=15.6。)
### バースト間隔
バースト間隔(inter-burst duration)はバースト持続時間よりもはるかに裾が長い分布を示す。Cache・Webラックでは間隔の40%が100µs未満だが、間隔が長引く場合は数百ミリ秒オーダーに達し、バースト持続時間より数桁大きい。Kolmogorov-Smirnov適合度検定により、バースト到着が指数分布(ポアソン過程)に従うという帰無仮説はp値がほぼ0で棄却された。
**Figure 4: バースト間隔のCDF(25µs粒度)**
![[_attachments/imc17-final60/fig04-cdf-interburst-time.png]]
(Figure 4. バースト間隔(ミリ秒、対数軸)のCDF。バースト持続時間(Figure 3)と比べて著しく長い裾を持つ。)
### バースト内外でのパケットサイズ分布の変化
バースト期間中はバースト外と比べて大きいパケットの割合が増える傾向がある。Cacheラックでは大パケット比率が約20%相対増加、Webラックでは他サイズ帯からの寄与を含め約60%の相対増加が見られた。Hadoopは元々ほぼ全パケットが大サイズ(MTUフル)であるため、この効果は目立たない。
**Figure 5: バースト内/外のパケットサイズ分布(100µs区間)**
![[_attachments/imc17-final60/fig05-packetsize-histogram.png]]
(Figure 5. (a) バースト内、(b) バースト外のパケットサイズヒストグラム(Web/Cache/Hadoop)。バースト内で大パケット([1023-1518]バイト帯)の比率が高まる傾向はWeb・Cacheで顕著。この差はバーストがランダムな衝突ではなく、アプリケーション層の挙動変化によって生じることを示唆する。)
### 全体的なリンク利用率
バースト・非バースト期間を通じたリンク利用率は、いずれのアプリケーションでも極めて裾の長い分布を示す。特にHadoopはサンプリング期間の10%でほぼ100%の利用率に達し、CacheとHadoopは多峰性(multimodal)の利用率分布を持つ。Hadoopポートはバースト状態に費やす時間の割合が最も高く(∼15%)、50%を高利用率閾値としてもおおむね頑健な結果になっている。
**Figure 6: リンク利用率のCDF(25µs粒度)**
![[_attachments/imc17-final60/fig06-cdf-link-utilization.png]]
(Figure 6. Web・Cache・Hadoopそれぞれのリンク利用率CDF。3種とも長い裾を持ち、バースト時は総じて高強度である。)
### アップリンクの負荷分散(ECMP)の実効性
ToRスイッチはECMPで4本のアップリンクへ負荷分散するが、フローレベルでのハッシュに起因して短時間スケールでは不均衡になりうる。40µs粒度での4本のアップリンク間MAD(平均絶対偏差)は、Hadoopラックの90パーセンタイルで平均偏差100%に達し、中央値でも全3ラック種別が25%を超えるMADを示した。一方、1sの粒度で見ると同じリンクはほぼ均衡して見える。
**Figure 7a: エグレス方向のMAD(40µs vs 1s)**
![[_attachments/imc17-final60/fig07a-mad-egress.png]]
(Figure 7(a). 40µs粒度(実線)と1s粒度(破線)でのアップリンク利用率MAD比較。実線は破線よりも右に(不均衡側に)大きくシフトしている。)
**Figure 7b: イングレス方向のMAD(40µs vs 1s)**
![[_attachments/imc17-final60/fig07b-mad-ingress.png]]
(Figure 7(b). イングレス側も同様の傾向を示し、インターコネクト通過によって分散が大きく増加するわけではないことを示唆する。)
### サーバ間相関(Pearson相関係数)
ToR-server方向の利用率についてサーバ対ごとのPearson相関係数をヒートマップ化すると、Webラックはほぼ無相関(ステートレスなユーザリクエスト駆動のため)、Hadoopラックは緩やかな相関、Cacheラックはサーバ部分集合間で強い相関を示した。これはCacheサーバへのリクエストがwebサーバから集団的(scatter-gather)に発行されるためである。
**Figure 8: ラック内サーバ間Pearson相関係数のヒートマップ(250µs粒度)**
![[_attachments/imc17-final60/fig08-heatmap-correlation.png]]
(Figure 8. (a) Webラック、(b) Cacheラック、(c) Hadoopラック。Cacheラックのみサブセット間で強い正相関(濃い赤)のブロックが見られる。)
### バーストの方向性(アップリンク vs ダウンリンク)
300µs粒度でhotなポートの内訳を見ると、Web・Hadoopラックはダウンリンク(サーバ向け)側に偏っており(Hadoopのhotサンプルのうちアップリンクはわずか18%)、多数のサーバから単一の宛先へのfan-inがバーストの主因であることを示す。逆にCacheサーバは応答が要求よりも大幅に大きい非対称通信パターンのため、アップリンク側でバーストが起きやすい。
**Figure 9: アップリンク/ダウンリンクのhotポート比率(300µs粒度)**
![[_attachments/imc17-final60/fig09-uplink-downlink-hotports.png]]
(Figure 9. Web・Hadoopはダウンリンク側にバーストが偏り、Cacheはアップリンク側に偏る、対照的な傾向を示す。)
### µburstと共有バッファの関係
Hadoopラックは他の2種よりもToRの共有バッファへの負荷が著しく大きい。Hadoopは50ms区間内でポートの100%を同時に50%超利用率へ駆動することがある一方、Web・Cacheはそれぞれ最大71%・64%にとどまった。バッファ占有はHadoopでhotポート数に対してより急峻に(非線形に)増加する。
**Figure 10: 正規化ピーク共有バッファ占有 vs hotポート数(300µs粒度)**
![[_attachments/imc17-final60/fig10-buffer-occupancy-vs-hotports.png]]
(Figure 10. (a) Web、(b) Cache、(c) Hadoopの箱ひげ図。Hadoopのみhotポート数の増加に伴いバッファ占有の中央値・分散が顕著に増大する。)
## 考察
本論文は、輻輳・負荷分散の実効性・サーバ間同期といったデータセンターネットワークの根本的な挙動が、測定粒度に強く依存して見え方が変わることを示した。とりわけ「利用率とドロップ率の弱い相関」という従来の観測結果(Section 3)は、実際には輻輳が短命なµburstの集合として発生していることの副産物であるという説明を与えている。著者らは、負荷分散にはマイクロフロー単位の分割を、輻輳制御にはRTT未満の低遅延輻輳シグナルを、パケットペーシングにはハードウェア/ソフトウェア双方でのより積極的な機構を、それぞれ設計上考慮すべきだと結論づけている。ただし、µburstの直接的な原因(アプリケーション挙動かランダムな衝突か)を厳密に特定するには、スイッチと エンドホストの計測をマイクロ秒単位で相関させる必要があり、著者らの現行デプロイではそれが実現できていない点を明示的な限界として述べている(脚注2)。
## 強み / 弱点・課題
- **強み**: 追加のハードウェア無しに、運用中の本番スイッチプラットフォームに搭載済みの汎用CPUを活用して25µs粒度の測定を実現した点。3種の性質が大きく異なるワークロード(Web/Cache/Hadoop)を横断して一貫した方法論で比較し、負荷分散・バッファ挙動・パケットサイズ分布まで多面的に特性評価している点。生データを公開している点(再現性)。
- **弱点・限界**: 測定対象がToRスイッチに限定されており(著者ら自身は先行研究からToR層が輻輳の大部分を占めると根拠づけている)、fabric層・spine層は対象外。単一の運用者(Facebook)の単一データセンターの一部という限定的なサンプルであり、他のデータセンターへの一般化可能性は明言されていない。25µs自体もなお粗すぎる可能性が指摘されており(60%超のバーストが単一サンプリング周期内で終了)、スイッチCPU-ASIC間のレイテンシに起因するサンプリング粒度の物理的な下限が存在する。µburstの原因(アプリケーション挙動 vs ランダムな衝突)を直接検証できていない。