論文紹介: “Globally Synchronized Time via Datacenter Networks”

本記事は システム系論文紹介 Advent Calendar 2016の4日目, 12/04 のための記事です.

はじめに

4日目 n_kane の担当分では今年の ACM SIGCOMM 2016 より時刻同期話ということで以下の論文を取り上げます.

• タイトル: Globally Synchronized Time via Datacenter Networks
  • 著者 Ki Suh Lee et al. (Cornell University)
  • 出展: ACM SIGCOMM 2016, Session 5, Datacenters 1
  • 論文へのリンク
  • スライド資料へのリンク

セッション自体の括りはデータセンター, 内容としても DC 環境での分散システム向けの時刻同期をターゲットにしています. このあたりは個人的な興味ではなかったのですが, 最近時刻同期関連(GPS, NTP, PTP 等等)を勉強しようと思っておりました. その矢先にこの論文を見つけたため今回取り上げることにしました.

対象としている問題

NTPやPTPをベースにした時刻同期はもはや無くてはならないプロトコルですが, ナノ秒レベルでの時刻同期が必要な場合, 精度に非決定性があるというのが本論文で取り上げ解決策を提示している問題です.

NTPはマイクロ〜ミリ秒, PTPはサブナノ秒の精度で時刻(クロック)同期が可能なプロトコルです. これらのプロトコルでは細かい差異はあるにせよ共に, 2台の計算機の間でRTTを測定し これをもとに一方向遅延(OWD One Way Delay)と相互のクロックの差(Offset)を算出, 時刻やクロックを合わせ, クロック発振器がそれを維持し定期的に再計測を行うという方法で 同期を行います.

この流れの RTT 計測, クロックの維持, 再計測に非決定的な誤差を生む要因がある, と本論文では主張しています. NTP, PTPはともに UDP ベースのプロトコルでありネットワーク帯域を消費しているため 間の経路の経路, 輻輳, 機器類のバッファリングや送受信のスケジューリングによる影響を受けます. ベースとなるRTT計測は往路復路が同じであることを前提としていますが, これが常に満たされるとは限りません. クロックの維持も誤差要因となります. 原子時計と異なり一般的なx86の計算機に積まれたクロックはそれぞれに 一定の誤差を生じながら動くため, 時が進むにつれズレが発生します. この補正のためには頻繁な再計測・再同期を行う必要がありますが, あまりに同期対象や頻度が多い場合に時刻同期に帯域を取られてしまうといった問題があります.

解決策

この論文では時刻同期を Ethernet で直結された2台の計算機間において PHY レイヤで行うことで 前節の問題を解決しようとしています. キモはEthernet で接続された計算機間では「既にNIC同士のクロックが同期されている」という点です. Figure 2 にクロックドメインについての図が掲載されていますが, Ethernetのフレームを送受信するにあたって送信側と受信側は実質同じ回路になっており 送信側のクロックに併せて動作をしていると考えることができます.

このNICレベルでのクロック同期を, システムレベルでのクロック同期に利用するというのが 本論文で提示する手法になっています. この手法を用いたクロック同期として DTP (Datacenter Time Protocol) とそれを実装した 10Gbit Ethernet PHY を取り上げています.

ポイント

この論文で DTP の推しポイントとして主張されているのは以下の3点です.

1. 802.3プロトコルのハックによるオーバーヘッド実質0のプロトコル
2. ナノ秒レベルでの同期で誤差が予測可能
3. スイッチを用いたスケーラブルなクロック同期が可能

1. オーバーヘッド実質0のプロトコル

NTPやPTPと同じく DTP も RTT の計測からの一方向遅延の算出を基本としています. 最終的なクロック合わせをオフセットの計算ではなく「一番速いやつに合わせる」 というアルゴリズムの違いはありますが, やっていることはあまり替わりません.

大きな違いは先にも述べたとおり DTP では Ethernet の PHY レイヤで伝送を行う点です. 具体的には PHY の PCS (Protocol Control Sublayer) のスクランブル/デスクランブル化の直前に, 処理を差し込むことでこのレイヤで伝送されているコントロールブロックに載せて DTPのデータを送受信します.

このレイヤでは実際のデータ(Ethernetフレーム)転送の間にリンク維持やエラー通知を目的とした コントロールブロックの送受信が行われています. このうちDTPが有効なリンクでは Idle キャラクタの部分に DTP のデータを載せ送受信することとしています. PCSの上位レイヤには Idle キャラクタを正しく戻してやることで, Ethernetのデータ転送の帯域を実質的に 使うこと無くDTPのやりとりを行うことが可能となっています.

この方法の利点として Ethernet の伝送を邪魔しないこと, 高頻度にクロック同期が可能であることが挙げられます. Idleキャラクタのコントロールブロックは Ethernet フレームが流れる時はその前後に, 何も流れていない時は継続的に差し込まれるため Ethernet の帯域を消費しません. いわゆる10GbE, 100GbEといった速度はこの制御系の通信を除いたものであるためです. このコントロールブロックは輻輳している場合でも 1280〜7680ns の間隔で挿入が可能です. ワーストケースでも数usの周期でクロック同期を回すことが可能であるため, 精度の維持

2. ナノ秒レベルで誤差予測可能なクロック同期

DTP では同期誤差が「4T」に決定的(deterministic)に収まるように設計されています. ここで T は最も速いクロックの周期であり, 10Gbit Ethernetの場合は T = 1 / f = 1 / 156.25MHz = 6.4 nsとなるため, 25.6ns内に収まることになります.

この誤差予測が可能なのは PHY レイヤで同期しているためソフトウェアスタックが介在しないこと, 直結されているため間に何も入らないことにより誤差導入要素が(ほぼ)無いためです. 遅延要因としてはケーブル上の伝搬遅延やエンドポイントでの処理遅延が存在しますが これらは動的には変化しないと仮定を置くことができ, 事前に予測が可能です 一部 Clock Domaing Crossing, 相手のTXに乗ったクロックと自分のTXのクロック間の 遅延を解決するのにランダム性のある誤差が生じますがこれもどちらか速いほうの1クロック内に 収まるということのようです.

複数のPHYを計算機に挿すことでPTPのBoundary Clockのようにネットワークを跨がって時刻を 同期することも可能です. この場合でも「4TD + 8T」に誤差が収まるとしています. ここで D はホップ数を挿します. スモールワールド現象に則って6ホップ経由すればデータセンターの 全ての計算機にリーチできると仮定すると, どの計算機の間でも 153.6ns 以内に誤差が収まる クロック同期が可能となります.

3. スケーラブルな時刻同期

DTP は Ethernet が直結された2台間で行うことが基本ですが, スイッチがDTPをサポートすることで 2台以上のクロック同期が可能となっています. 前提としてスイッチの全ポートが同じクロックを共有するスイッチチップにより制御されていることが 必須にはなりますが, これを基軸として全ポートと DTP のやりとりを行うことで現在の最速クロックに 合わせるという動作が可能です.

評価

有効性の評価としてこの論文では DTP が PTP と比べて非決定性を抑制できていることを確認しています. PTPでは負荷の状況をなし, 中度, 重度と変えたときに300ns程度内, 25us程度内, 100us程度内と 誤差が大きくなっていきまた定常的にもブレが大きいことが見て取れます. 一方の DTP ではMTU 1500バイトの通常のEthernetややジャンボフレームの場合に負荷を掛けても ワーストケースで 4T = 25.6 ns内に常に収まっていることが確認できます.

まとめとおわりに

ここでは Ethernet の PHY レイヤを用いたクロック同期手法 DTP (Datacenter Time Protocol) についての論文を取り上げました. 時刻同期というよりはクロック同期であり, PTPと比してさらにハードウェアのサポートが必要であること, 同期ピア間でケーブルの直結が必要であることなど制約がより強い手法ではあります. ただし誤差の予測がネットワークを跨いでも可能であり必ずしも局所的にしか使えないといったものでもないようです.

スイッチの実装はまだ構想段階のようなので論文中の前提がフィールドで適用できるかどうかや, DTP を実装する NIC PHY のコストや性能への実際の影響についてはより調査や実験が必要と感じました. 個人的には IEEE 802.11ae の PCS をある意味ハックしているのが面白く感じました. また REFERENCES に時刻同期関連の一通りが並んでいるので大変にありがたい文章です.

後付け: 他の候補

その他, 今回紹介しようと思った候補としては以下に挙げるものがありました.

• ACM SIGCOMM 2016: Inter-Technology Backscatter: Towards Internet Connectivity for Implanted Devices, Iyer et al (University of Washington)
• ACM SIGCOMM 2016: Evolve or Die: High-Availability Design Principles Drawn from Google’s Network Infrastructure, Govindan et al (Google/USC)