コラム

CTC教育サービス・ホーム　＞　コラム　＞　グーグルのクラウドを支えるテクノロジー　＞　第148回　ネットワークスイッチにおけるハッシュ関数の課題（パート2）

グーグルのクラウドを支えるテクノロジー

CTC 教育サービス

[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes

第148回　ネットワークスイッチにおけるハッシュ関数の課題（パート2） (中井悦司) 2023年4月

はじめに

　前回に続いて、2022年に公開された論文「Hashing Design in Modern Networks: Challenges and Mitigation Techniques」を紹介していきます。この論文では、ECMPなどのマルチパス技術を用いた現代のデータセンターネットワークにおける、負荷分散用のハッシュ関数に関わる課題が説明されており、論文の筆者らが考案した、数学的な理論に基づいた解決策が紹介されています。

「Color recombining」によるハッシュ関数の再利用

　前回の記事では、ECMPによる負荷分散におけるハッシュ関数の課題を説明しました。複数の階層からなるネットワークアーキテクチャーでは、それぞれのスイッチが使用するハッシュ関数に相関があると、使用する経路に偏りが生じるという問題です。たとえば、図1は、Googleのデータセンターで実際に利用されていたClosトポロジーのネットワークを説明のために少し単純化したものです。このネットワークで、左下のスイッチS1から右下のスイッチS2に至る経路を考えると、ECMPによる負荷分散が8回行われます。したがって、互いに相関の無い、8種類の独立なハッシュ関数が必要となります。しかしながら、この環境で使用しているスイッチングチップには6種類のハッシュ関数しか実装されておらず、このままでは、経路の偏りを避けることができません。

fig01

図1 Closトポロジーネットワークにおけるハッシュ関数の構成（論文より抜粋）

　そこで、冒頭の論文の筆者らは、このネットワーク上のパケットの流れを分析して、「Color recombining」が発生するスイッチを特定しました。これは、前段のスイッチで2つの経路に分かれたパケットの一部が合流する地点となるスイッチで、特に、それぞれの経路から同じ割合のパケットが合流する部分を表します。たとえば、図1で、S4aからS5aとS5bを経由してS4bで合流する流れを考えます。S4aはハッシュ関数h4で経路を分けて、S5bはハッシュ関数h5で経路を分けます。この時、S5aとS5bは、いずれも、受け取ったパケットの半分をS4bに転送するので、S4bは、S4aにおいてハッシュ関数h4で均等に分かれたパケットのそれぞれから、ちょうど50%ずつのパケットを受け取ります。
　それでは、このようにしてS4bに集まったパケットに対して、再び、ハッシュ関数h4を適用するとどうなるでしょうか？　もともと、S4aでハッシュ関数h4で均等に分かれたものを50%ずつ集めているわけですから、これらは、ハッシュ関数h4で再び均等に分けることができます。つまり、S4bでは、ハッシュ関数h4を安全に再利用できるのです。同様の考察を行うと、S2では、ハッシュ関数h2を再利用できることがわかります。これにより、図1の構成では、必要なハッシュ関数を8種類から6種類に減らすことができたということです。

「Coprime theory」を利用した解決策

　前述の「Color recombining」は、必要なハッシュ関数の個数を減らす対応策となりますが、これを適用するには、複数の経路に分かれたパケットが再び合流する地点が必要となります。そのため、Closトポロジーのネットワークにはうまく適用できますが、図2のようなメッシュ型のトポロジーには適用できません。図2は、データセンター内のクラスター群と他のデータセンターのクラスター群を相互接続する中継地点となるネットワークを表します。

fig02

図2 メッシュトポロジーのデータセンターネットワーク（論文より抜粋）

　あるいは、第136回からの記事で紹介したように、現在のGoogleのデータセンターでは、Spineブロックを取り除いた、図3のようなトポロジーを採用しています。ここでは、ToR（Top of Rackスイッチ）とミドルブロックからなる、複数のサーバーブロックが光スイッチで相互接続されており、Trafiic Engineeringなどの最適化により、ネットワークの経路が動的に変化します。そのため、Color recombiningが発生するスイッチを単純に特定することはできません。

fig03

図3 Spineブロックを持たないネットワークトポロジー（論文より抜粋）

　冒頭の論文の著者らは、このような場合にも利用できる対応策として、「Coprime theory」に基づいた方法を提案しています。これは、「互いに素な2つの自然数q1、q2」について成り立つ定理に基づいたもので、ハッシュ関数Hに対して、H1=H%q1、H2=H%q2で2つの新しいハッシュ関数を定義した際に、q1、q2が一定の条件を満たしていれば、H1とH2は近似的に独立した（相関を持たない）ハッシュ関数になるというものです。ここに、a%bは「aをbで割った余り」を表します。従って、ネットワーク機器が提供するハッシュ関数Hを元にして、新たなハッシュ関数H1=H%q1、H2=H%q2を構成することができれば、同じハッシュ関数Hを安全に再利用できます。たとえば、パケットを2つの経路に分ける場合、H%2（Hを2で割った余り）ではなく、H%q1%2（もしくは、H%q2%2）の値で経路を選択します。
　ただし、H%q1%2という計算処理は、既存のネットワークチップには実装されていませんので、次の方法で擬似的にこの計算処理を実現します。たとえば、物理ポート0と物理ポート1に出力ポートを振り分ける場合、はじめに、ネットワークスイッチの「論理ポート機能」を用いて、q1個の論理ポートを定義した上で、ネットワーク機器のECMP機能を用いて、q1個の論理ポートにパケットを振り分けます。「論理ポートn」には、「H%q1=n」を満たすパケットが転送されると考えてください。その上で、「論理ポートn」に対して、「物理ポートn%2」をマッピングします。「論理ポート0=物理ポート0、論理ポート1=物理ポート1、論理ポート2=物理ポート0、論理ポート3=物理ポート1・・・」といった対応です。この結果、物理ポート0には「H%q1%2=0」と満たすパケットが、物理ポート1には「H%q1%2=1」を満たすパケットが転送されます。
　なかなかよく考えられた仕組みですが、これですべてうまく行くという保証はまだありません。たとえば、q1は素数なので、論理ポートの個数は偶数にはなりません。つまり、物理ポート0と物理ポート1に対して、厳密な意味で均等に振り分けることはできません。より一般には、k個の物理ポートに振り分けるとした際に、q1がkの倍数にはならないという状況になります。また、先ほど説明したように、H1とH2の独立性はあくまでも近似的なものです。つまり、この解決策がどこまで有効に機能するかは、近似の有効性にも依存してきます。そこで、冒頭の論文では、実環境のデータを用いたシミュレーションによって、この手法の実際の効果を検証しています。

次回予告

　今回は、2022年に公開された論文「Hashing Design in Modern Networks: Challenges and Mitigation Techniques」に基づいて、大規模なデータセンターネットワークにおける、ECMPを用いた負荷分散の問題点について、これを解決する2つの手法を紹介しました。次回は、これらの手法の有効性に対する検証結果を紹介します。

Disclaimer：この記事は個人的なものです｡ここで述べられていることは私の個人的な意見に基づくものであり、私の雇用者には関係はありません｡