宣言的ネットワーキングとインクリメンタル処理

はじめに

2020年1月に札幌で行われたJANOG45で、Cisco Systemsの河野美也さんと共同で「宣言的(Declarative)ネットワーキング」というセッションをやらせていただきました。その時の資料はこちらです。残念ながら30分と時間が限られていたため、十分にお伝えすることができなかった部分もあるため、こちらに補足記事としてまとめておくことにしました。

そもそも宣言的(Declarative)って何?

最近「宣言的」や「Declarative」という言葉をよく耳にするようになっていると思います。実は、宣言的/Declarativeという言葉はそう新しいものではなく、実はかなり前から使われている言葉です。プログラミング言語の世界では関数や述語論理に基づいたプログラミング言語などが従来型の命令的プログラミング言語との対比として「宣言的プログラミング言語」と呼ばれていました。比較的最近では、Ansibleなどの構成管理ツールやJenkinsなどのCI/CDツールにも宣言的な側面があると言われていますし、FlutterやSwiftUIなどのU/Iフレームワークも「宣言的U/I」などと呼ばれ注目されています。このように「宣言的」という言葉はさまざまな文脈でいろいろな意味で使われており、決定的な定義があるわけではありません。宣言的という言葉が持つ多面性については河野さんがこちらの記事で言及してくださっていますので是非ご一読ください。

しかし、最近「宣言的」という言葉をよく聞くようになったのはなんと言ってもKubernetesの影響でしょう。Kubernetesが宣言的であると言われるのは、Kubernetesでは各種リソースの望まれる状態(Desired State)をManifestとして定義する事ができて、現在の状態(Current State)とDesired Stateの間にズレがある場合は、コントローラがそれを検知し自動的にそのズレを修復するように動くようになっているからです。「どのようにしてそのズレを解消するかは問わない。ともかくDesiredな状態にしてくれ!」と指示をするので、Kubernetesは宣言的であると考えらています。Desired Stateと現在のStateを常に比較し、差異があればそれをなくそうとする動作はReconciliation Loopと呼ばれており、各コントローラに実装されています。Kubernetesに自己修復(Self-Healing)性があると言われるのは、Kubernetesの各種コントローラにこのようなReconciliation Loopが実装されているためです。

宣言的(Declarative)ネットワーキング

JANOG45のセッション後に幾つかのフィードバックをもらいました。その中の一つは以下のようなものでした。

非常に妥当なご意見だと思いますし、他にも同じように感じられた方も多かったようです。なぜ今日のネットワークはKubernetes的な宣言性を持ち得ていないのか、どのようにしたらそれを実現できるのか、という点に興味を抱いている人は多いんですね。これは大変興味深い話であり、私自身も大きな関心を持っています。

個人的には、今日のネットワークがKubernetes的な宣言性を持てていない理由の一つとして「Desired Stateを定義するのが難しく、Reconciliationするのも難しい」という点があるのではないかと思っています。KubernetesのDeploymentであれば、どのようなコンテナがいくつ動いているかを把握したり、アプリケーションが応答するかをlivenessProbeなどで監視して、Desired Stateとのズレがあったら基本的に再度コンテナを立ち上げ直す事でReconciliationを図ります。では、ネットワークのDesired Stateって何でしょう? おそらく「ホストAからホストBにパケットが届く事」あるいはL4まで考えれば「ホストA上のサービスCからホストB上のサービスDへパケットが届く事」ということになるのではないかと思います。このようなDesired Stateを検出するのはなかなか困難です。コンテナは一次元的な要素なので比較的シンプルですが、ネットワークはsourceとdestinationがある二次元的な要素ですので、N^2問題に直面します。ホストがN台あったとすると、全ての到達性を確認するためにはN*Nのprobeをしなければいけません。Network Policy(ACL)も含めてネットワークのDesired Stateを考えると複雑性はN*Nでは済まず、サービス数Mも含めて考えてN*M*N*Mでの到達性を把握する必要があります。パケットの到達性はsourceに依存するので、このようなprobeをどこからしたら良いのか、という点も悩ましいです。また、仮にこのようなProbeできてネットワークのDesired Stateと現在のStateにズレをうまく検出できたとしても、それをどのようにReconcileするかも難しいです。KubernetesのDeployment/Podの場合は、単純にコンテナを作り直す、という戦略を取っているわけですが、ネットワークの場合は、単純にネットワークを実現しているコンテナを再起動しても解決しない場合が多いと思います。ネットワークのエンドポイントに問題はなく、途中の経路に何か問題があって疎通性が阻害されている場合には、いくらエンドポイントを再起動してもおそらく問題は解決しないでしょう。

このように、現在のネットワークにKubernetes的な宣言的特性や自己修復性を持たせるのは簡単なことではないように思います(少しドメインを限定すればネットワークにも宣言性を持たせることは可能という考え方もあります[3])。ただ、上記のような宣言的ネットワーキング / Declarative Networkingの困難さに立ち向かおうとしている人はきっといるはずです。非常に有望な「研究課題」と言えるでしょう。

もう一つの宣言的ネットワーキングの側面

上記のようなネットワークのKubernetes的な宣言性は非常に興味深いトピックではありますが、私がJANOG45でお話をさせていただいたのは、これとはちょっとまた別の観点からの宣言的ネットワーキングの話で、SDNコントローラに宣言的なエンジンを用いることによっていかに堅牢で効率的なコントローラを実現できるか、という点でした。

ネットワークは非常に複雑な分散システムです。設定している最中に障害が起こり得ます。一般的にネットワーク設定は冪等ではありません(例えばポートを作った後にどこか別のノードで設定が失敗し、再度最初から同じ設定を入れようと思っても、すでにポートが作成済であればエラーになってしまうでしょう)。したがって、設定の途中で障害が起こったら単純に最初からやり直すだけではダメで、綺麗にロールバックしてやらなければいけません。ロールバックしている最中にまた別の障害が起こる、など多重障害が起こる可能性もあります。このようにさまざまなFailureシナリオにきちんと対応するするのは簡単ではありません。堅牢なSDNコントローラを作るのは非常に難しいことなのです。

Niciraの創業者の一人であるMatin Casadoから聞いた話なのですが、「Niciraでは幾つかのSDNコントローラを試作したが、上記のようなネットワークの複雑性からどれもなかなかうまくいかなかった。最終的に最も堅牢に動いたのはDatalogをベースにした宣言的なエンジンを使ったコントローラだった」とのことでした。この話を聞いて以来、私はずーっと宣言的なSDNコントローラに興味を抱いていました。

たまたまCiscoの河野さんも宣言的ネットワークに興味関心をお持ちである、ということを知り、それでは共同でJANOGでセッションをやってみましょう、ということになった次第です。河野さんからは宣言的ネットワークに関するさまざまな観点と考察を、私の方からは宣言的なSDNコントローラエンジンの適用事例の一つとして、OVNのコントローラにおけるDatalog技術の適用のお話をさせていただきました。OVN の概要とアーキテクチャに関してはこちらこちらを参考にしてください。

SDN コントローラとテーブル更新

一般的にSDNコントローラは多数のテーブルを扱います。その中でもフローテーブルは非常に巨大かつ動的に更新される必要があるものです。VMやコンテナは別のホストに移動する可能性があるので、それらのイベントに追従する形でフローテーブルを動的に更新してやらなければいけません。これを大規模な環境でやるのは思いの外大変です。

仮に2台のハイパーバイザ(Host1とHost2)と仮想マシンが3台(VM1、VM2、VM3)があり、VM1とVM2がHost1上で動いていて、VM3がHost2上で動いていたとしましょう。

SDNコントローラはそのような状況を表す以下のようなテーブルを持っているはずです。

Controller:

VM IP Host Port
VM1 10.10.10.101 Host 1 2
VM2 10.10.10.102 Host 1 3
VM3 10.10.10.103 Host 2 2

SDNコントローラはこのテーブルから各ハイパーバイザ(Host1、Host2)のフローテーブルを以下のように設定することになります。

Host1:

Match Action
dst=10.10.10.101 output:2 (local port)
dst=10.10.10.102 output:3 (local port)
dst=10.10.10.103 output:1 (tunnel port)

Host2:

Match Action
dst=10.10.10.101 output:1 (tunnel port)
dst=10.10.10.102 output:1 (tunnel port)
dst=10.10.10.103 output:2 (local port)

このようなフローテーブルの設定を行うには、概ね以下のようなコードをコントローラに実装すれば良いでしょう。

for h in Hosts:
  for vm in VM:
    if vm.host == h:
      h.add_flow(match="dst={vm.ip}", action="output:{vm.port}")
    else
      h.add_flow(match="dst={vm.ip}", action="output:{tunport}")

ここで、仮にVM2がHost1からHost2に移動(vMotion/Live Migration)したとしましょう。

コントローラはこのようなVMの移動を把握することができますので、自分が持っているテーブルを以下のように更新します。

Controller:

VM IP Host Port
VM1 10.10.10.101 Host 1 2
VM2 10.10.10.102 Host 2 3
VM3 10.10.10.103 Host 2 2

当然この変更に合わせてハイパーバイザ上のフローテーブルも更新しなければなりません。一番簡単な方法は、上にあげたロジックを再度実行することです。こうすれば適切なフローテーブルが新たに各ハイパーバイザに設定されるはずです。

Host1:

Match Action
dst=10.10.10.101 output:2 (local port)
dst=10.10.10.102 output:1 (tunnel port)
dst=10.10.10.103 output:1 (tunnel port)

Host2:

Match Action
dst=10.10.10.101 output:1 (tunnel port)
dst=10.10.10.102 output:3 (local port)
dst=10.10.10.103 output:2 (local port)

しかしこれはあまりに非効率です。テーブルが小さいうちはこのような実直な方法でも良いかもしれませんが、テーブルサイズが大きくなってきた場合、この方法は明らかにCPUやネットワーク帯域の無駄になります。大規模環境では設定にかかる時間も無視できないほど大きくなってしまうでしょう。もう少し良い方法はないでしょうか?

誰もがすぐに思いつくのはおそらく「変更があったところだけ更新をする」という方法でしょう。いわゆるインクリメンタルなアップデート処理をすれば良いわけです。アルゴリズム的にはこんな感じになるでしょう。

for h in Hosts:
  if old_vm.host == h:
    h.del_flow(...)
  else
    h.del_flow(...)
  if new_vm.host == h:
    h.add_flow(match="dst={new_vm.ip}", action="output:{new_vm.port}")
  else 
    h.add_flow(match="dst={newvm.ip}", action="output:{tunport}")

一見簡単そうな変更に見えるかもしれませんが、実は結構面倒な処理になります。このようなインクリメンタル処理のアルゴリズムはテーブル毎に個別に実装してやらなければいけません。OVNコントローラには数十個のテーブルがありますし、NSX-Tでは百を超えるテーブルがありますので、すべてのテーブルにこのようなインクリメンタル処理のアルゴリズムを個別に実装していくのはそう簡単な作業ではありません。また、テーブル間には依存関係がある場合があるので、一つの変更に対して、整合性を保つように複数のテーブルを注意深く更新していかなければなりません。設定の途中でエラーになった際のリカバリー処理なども考えると、テーブルごとにインクリメンタルな処理を実装する方式はかなり難度が高いことで、場合によってはコントローラの堅牢性を失いかねません。

宣言的コントローラエンジンとDatalog

OVNは大規模環境でも堅牢に動くProcution ReadyなSDNコントローラを目指していますので、まさに上記のような課題に直面することになります。

OVNではovn-northdとovn-controllerという2種類のコントローラが動いています。前者がネットワーク全体を管理するコントローラ、後者が各ハイパーバイザで動いているローカルのコントローラです。現在、ovn-northdコントローラにDatalogを使った宣言的な仕組みを適用する試みが行われています。

Datalogは一階述語論理に基づいた宣言的なプログラミング言語です。文法的にはPrologに似ていますが、Prologとはいくつかの点で異なり、演繹的データベースの問い合わせに使われることが多い DSL (Domain Specific Language) の一つです。

例えば、

Parent(Anakin, Luke).
Parent(Anakin, Leia).
Sibling(c1, c2) :- Parent(p, c1), Parent(p, c2), c1 != c2.

というDatalogのプログラムからは

Sibling(Luke, Leia).
Sibling(Leia, Luke).

という結果が導出されます。”:-” を含んだ行は「ルール」と呼ばれ、”:-” の右側の項が全て成り立つ時に”:-” の左側が成り立つ、という意味になります。”:-” を含まない行は「事実(Fact)」と呼ばれます。上記のDatalogプログラムをざっくりと日本語にすると、

Lukeの親はAnakinである(事実)。Leiaの親はAnakinである(事実)。c1とc2が共通の親を持っており、c1とc2が異なれば、c1とc2は兄弟である(ルール)。

ということになり、そしてそこから導かれる結果は、

LukeはLeiaと兄弟である。LeiaはLukeと兄弟である。

となります。

Datalogを使うと、先に紹介した手続き的なフローテーブルの書き換え処理を宣言的に記述する事ができます。例えば、

Host(1),
Host(2);
VM("VM1", "10.10.10.101", 1, 2),
VM("VM2", "10.10.10.102", 1, 3),
VM("VM3", "10.10.10.103", 2, 2);
Flow(h, "dst=${ip}", "output:${p}") :- Host(h), VM(_, ip, h, p).
Flow(h, "dst=${ip}", "output:1") :- Host(h), VM(_, ip, other, _), other != h.

というルールとFactから

Flow(1, dst=10.10.10.101, output:2).
Flow(1, dst=10.10.10.102, output:3).
Flow(1, dst=10.10.10.103, output:1).
Flow(2, dst=10.10.10.101, output:1).
Flow(2, dst=10.10.10.102, output:1).
Flow(2, dst=10.10.10.103, output:2).

という結果を自動的に演繹的に導出することができます。

また、VM2がHost 1からHost 2のポート3に移動したとすると、

VM("VM2", "10.10.10.102", 2, 3),

のようにFactをアップデートをすれば、それを反映した正しい結果、

Flow(1, dst=10.10.10.101, output:2).
Flow(1, dst=10.10.10.102, output:1).
Flow(1, dst=10.10.10.103, output:1).
Flow(2, dst=10.10.10.101, output:1).
Flow(2, dst=10.10.10.102, output:3).
Flow(2, dst=10.10.10.103, output:2).

という結果を得ることができます。このように、Datalogを使うとフローテーブルがどのようなルールに則っているべきかを宣言的に記述するだけで良くなり、SDNコントローラを実装する人間はどのようにハイパーバイザのフローテーブルを設定すべきか、そのロジックを考えなくて済むようになります。これはとてもありがたいことです。

Differential Datalog

Datalogを使うと、フローテーブルなど、SDNコントローラが扱わなければいけない各種テーブルの更新処理を宣言的に記述することができるようになります。手続き的に書くよりはるかにメンテナンス性の良い記述をすることができるようになるので、コントローラの堅牢性の向上に大きく貢献すると考えられます。

ただし、Datalogを使うだけでは、先ほど見たような「インクリメンタルな更新処理をいかに効率よく行うか」という問題を解決することにはなりません。そこで登場するのがDifferential Datalogです(DDlogと呼ばれることもあります)。

Differential DatalogはDifferential Dataflowという仕組みの上に作られていますので、まずDifferential Dataflowについて簡単に説明をしておきましょう。Differential Datalowはいわゆるビックデータ処理システムの一つと考えられますが、インクリメンタルな更新をとても効率よく処理することができるのが特徴です。

例えばTwitterのツイートにつけられているハッシュタグ間の相関関係を調べるために、ハッシュタグをノード、mentionをそれらのノードを繋ぐ辺として見立て、ハッシュタグの「グラフ」を作ることを考えてみましょう。いわゆるグラフから結合成分(Connected Component)を抽出する問題です。現在、Twitterで1日につぶやかれるツイートの数はおよそ5億個です。このような大量のデータからグラフの結合成分を抽出する処理はビッグデータ処理システムの代表格の一つであるMapReduceの得意分野の一つです。ただ、Twitterのように常に新しいツイートが行われる(すなわち入力が随時変化していく)ようなケースはMapReduceはあまり得意ではありません。入力が変化するたびに初めから再度計算をし直さなければいけないからです。一方、Differential Dataflowは入力の変化に応じてアウトプットを効率よく計算することができるため、入力の変化に応じた結果をリアルタイムに得ることができます。

Differential Datalogは、Differential Dataflowをバックエンドに用いたDatalog処理系で、VMware Research Groupで開発されました。Differential Dataflowをベースにしているので、優れたインクリメンタル更新処理性能を持ちつつ、Datalogによる宣言的なプログラミングが可能です。ユーザはどのようにインクリメンタル処理が行われるのかを意識する必要はなく、基本的にDatalogでルールやFactを記述すれば、入力の変化に追従して素早く出力を計算することができます。

Datalogの宣言性とDifferential Dataflowの優れたインクリメンタル更新処理性能を兼ね備えているDifferential Datalogは、SDNコントローラにおけ各種テーブルの更新処理にとても向いている仕組みです。

実際にDifferential Datalogの差分更新がどれくらい高速なのか、簡単な実験をしてみましょう。

仮に100台のハイパーバイザー(Host0〜99)上に10,000台のVM(VM0〜9999)があり、VM0がHost0からHost1に移動した際のフローテーブルを計算するとします。まずは、フローテーブルのあるべき姿を定義するルールをDifferential Datalogで宣言的に定義します。

$ cat flowtable.dl
input relation Host(id: bigint)
input relation VM(vm: string, ip: string, host: bigint, port: bigint)
output relation Flow(host: bigint, matches: string, action: string)
Flow(h, "dst=${ip}", "output:${p}") :- Host(h), VM(_, ip, h, p).
Flow(h, "dst=${ip}", "output:1") :- Host(h), VM(_, ip, other, _), other != h.

このルールを使用するためには、これのコードをDifferential Datalogのコンパイラ(ddlog)にかけます。そうすると、このルールが埋め込まれたRustのコードが生成されます。

$ ddlog -i flowtable.dl -L ~/differential-datalog/lib/

ddlogによって生成されたRustコードをDifferential DataflowのライブラリとともにRustコンパイラでビルドすると、Differential Datalogで記述されたルールエンジンを備えた静的ライブラリとCLIツールが生成されます。

$ (cd flowtable_ddlog/ && cargo build --release)
Finished release [optimized] target(s) in 0.49s
$ ls -l flowtable_ddlog/target/release/
total 59100
drwxrwxr-x 34 shindom shindom 4096 Mar 17 09:23 build
drwxrwxr-x 2 shindom shindom 57344 Mar 17 09:36 deps
drwxrwxr-x 2 shindom shindom 4096 Mar 17 09:23 examples
-rwxrwxr-x 2 shindom shindom 15984984 Mar 17 09:36 flowtable_cli
-rw-rw-r-- 1 shindom shindom 2325 Mar 17 09:36 flowtable_cli.d
drwxrwxr-x 10 shindom shindom 4096 Mar 17 09:35 incremental
-rw-rw-r-- 2 shindom shindom 42098680 Mar 17 09:35 libflowtable_ddlog.a
-rw-rw-r-- 1 shindom shindom 2260 Apr 12 07:14 libflowtable_ddlog.d
-rw-rw-r-- 1 shindom shindom 219 Mar 17 09:23 libflowtable_ddlog.la
-rw-rw-r-- 2 shindom shindom 2350122 Mar 17 09:35 libflowtable_ddlog.rlib

今回の例だと、flowtable.dlに記述されたルールエンジンを持つライブラリlibflowtable_ddlog.a、libflowtable_ddlog.rlibと、CLIコマンドのflowtable_cliが生成されます。

本来であれば、このlibflowtable_ddlog.(a|rlib)を使ったコードをRust、C/C++、Java、Goなどで書くべきなのですが、今回は生成されたCLIツールを使って処理性能を簡易的に調べてみることにします。

100台のホスト上に10,000台の仮想マシンが動いている初期状態の作成と、そのうちの一台の仮想マシン(VM0)がホスト0からホスト1に移動をDifferential Datalogで書くと以下のようになります。これで、VMが一台ホストを移動した際のフローテーブルの更新を模擬することができます。また、かかった時間を調べるために、各処理の途中で時刻を表示するようにしてあります。

start;
insert Host(0);
insert Host(1);
      :
insert Host(98);
insert Host(99);
insert VM("VM0", "10.10.0.0", 0, 0);
insert VM("VM1", "10.10.0.1", 1, 1);
insert VM("VM2", "10.10.0.2", 2, 2);
      :
insert VM("VM9997", "10.10.99.97", 97, 9997);
insert VM("VM9998", "10.10.99.98", 98, 9998);
insert VM("VM9999", "10.10.99.99", 99, 9999);

echo initial setup started:;
timestamp;
commit;
echo initial setup finished:;
timestamp;
start;
delete VM("VM0", "10.10.0.0", 0, 0);
insert VM("VM0", "10.10.0.0", 1, 0);
echo update started:;
timestamp;
commit;
echo update finished:;
timestamp;

これをflowtable_cliに食わせてやると以下のような結果になります。

$ ./flowtable_ddlog/target/release/flowtable_cli --no-print < flowtable.dat
initial setup started:
Timestamp: 490458325506557
initial setup finished:
Timestamp: 490467825165438
update started:
Timestamp: 490467825243578
update finished:
Timestamp: 490467829061228

これを見て分かる通り、最初のフローテーブルの作成には約9.5秒かかっていますが、VMが移動した後のフローテーブルの更新には0.00381765秒しかかかっていません。フローテーブルの更新を実直に再計算するとフローテーブルの初期作成とほぼ同じ時間がかかると考えられるので、Differential Datalogのインクリメンタルアップデートの素晴らしい処理性能をご理解いただけるのではないかと思います。

Differential Datalog の OVN への適用

上で述べたように、現在OVNのovn-northdコントローラをDifferential Datalogを使って再実装する努力が行われています。この作業はOVNのGithubリポジトリのddlog-dev-v2というブランチで開発作業が進められています。

Differential Datalogを使ってテーブル処理を書く主なメリットは、

  • よりメンテナンス性の高いコードになる
  • インクリメンタルな更新による性能向上

の2点です。まず、メンテナンス性の高いコードになる、とう点をみてみましょう。以下は、OVNのmeterおよびmeter_bandテーブルを管理する部分のコードです(OVNはC言語で書かれています)。

struct band_entry {
    int64_t rate;
    int64_t burst_size;
    const char *action;
};

static int
band_cmp(const void *band1_, const void *band2_)
{
    const struct band_entry *band1p = band1_;
    const struct band_entry *band2p = band2_;

    if (band1p->rate != band2p->rate) {
        return band1p->rate > band2p->rate ? -1 : 1;
    } else if (band1p->burst_size != band2p->burst_size) {
        return band1p->burst_size > band2p->burst_size ? -1 : 1;
    } else {
        return strcmp(band1p->action, band2p->action);
    }
}

static bool
bands_need_update(const struct nbrec_meter *nb_meter,
                  const struct sbrec_meter *sb_meter)
{
    if (nb_meter->n_bands != sb_meter->n_bands) {
        return true;
    }

    /* A single band is the most common scenario, so speed up that
     * check. */
    if (nb_meter->n_bands == 1) {
        struct nbrec_meter_band *nb_band = nb_meter->bands[0];
        struct sbrec_meter_band *sb_band = sb_meter->bands[0];

        return !(nb_band->rate == sb_band->rate
                 && nb_band->burst_size == sb_band->burst_size
                 && !strcmp(sb_band->action, nb_band->action));
    }

    /* Place the Northbound entries in sorted order. */
    struct band_entry *nb_bands;
    nb_bands = xmalloc(sizeof *nb_bands * nb_meter->n_bands);
    for (size_t i = 0; i < nb_meter->n_bands; i++) {
        struct nbrec_meter_band *nb_band = nb_meter->bands[i];

        nb_bands[i].rate = nb_band->rate;
        nb_bands[i].burst_size = nb_band->burst_size;
        nb_bands[i].action = nb_band->action;
    }
    qsort(nb_bands, nb_meter->n_bands, sizeof *nb_bands, band_cmp);

    /* Place the Southbound entries in sorted order. */
    struct band_entry *sb_bands;
    sb_bands = xmalloc(sizeof *sb_bands * sb_meter->n_bands);
    for (size_t i = 0; i < sb_meter->n_bands; i++) {
        struct sbrec_meter_band *sb_band = sb_meter->bands[i];

        sb_bands[i].rate = sb_band->rate;
        sb_bands[i].burst_size = sb_band->burst_size;
        sb_bands[i].action = sb_band->action;
    }
    qsort(sb_bands, sb_meter->n_bands, sizeof *sb_bands, band_cmp);

    bool need_update = false;
    for (size_t i = 0; i < nb_meter->n_bands; i++) {
        if (nb_bands[i].rate != sb_bands[i].rate
            || nb_bands[i].burst_size != sb_bands[i].burst_size
            || strcmp(nb_bands[i].action, sb_bands[i].action)) {
            need_update = true;
            goto done;
        }
    }

done:
    free(nb_bands);
    free(sb_bands);

    return need_update;
}

/* Each entry in the Meter and Meter_Band tables in OVN_Northbound have
 * a corresponding entries in the Meter and Meter_Band tables in
 * OVN_Southbound.
 */
static void
sync_meters(struct northd_context *ctx)
{
    struct shash sb_meters = SHASH_INITIALIZER(&sb_meters);

    const struct sbrec_meter *sb_meter;
    SBREC_METER_FOR_EACH (sb_meter, ctx->ovnsb_idl) {
        shash_add(&sb_meters, sb_meter->name, sb_meter);
    }

    const struct nbrec_meter *nb_meter;
    NBREC_METER_FOR_EACH (nb_meter, ctx->ovnnb_idl) {
        bool new_sb_meter = false;

        sb_meter = shash_find_and_delete(&sb_meters, nb_meter->name);
        if (!sb_meter) {
            sb_meter = sbrec_meter_insert(ctx->ovnsb_txn);
            sbrec_meter_set_name(sb_meter, nb_meter->name);
            new_sb_meter = true;
        }

        if (new_sb_meter || bands_need_update(nb_meter, sb_meter)) {
            struct sbrec_meter_band **sb_bands;
            sb_bands = xcalloc(nb_meter->n_bands, sizeof *sb_bands);
            for (size_t i = 0; i < nb_meter->n_bands; i++) {
                const struct nbrec_meter_band *nb_band = nb_meter->bands[i];

                sb_bands[i] = sbrec_meter_band_insert(ctx->ovnsb_txn);

                sbrec_meter_band_set_action(sb_bands[i], nb_band->action);
                sbrec_meter_band_set_rate(sb_bands[i], nb_band->rate);
                sbrec_meter_band_set_burst_size(sb_bands[i],
                                                nb_band->burst_size);
            }
            sbrec_meter_set_bands(sb_meter, sb_bands, nb_meter->n_bands);
            free(sb_bands);
        }

        sbrec_meter_set_unit(sb_meter, nb_meter->unit);
    }

    struct shash_node *node, *next;
    SHASH_FOR_EACH_SAFE (node, next, &sb_meters) {
        sbrec_meter_delete(node->data);
        shash_delete(&sb_meters, node);
    }
    shash_destroy(&sb_meters);
}

かなりの量のコードで、それなりに複雑です。

一方、これと同じ処理をDifferential Datalogで記述すると、

/* Meter_Band table */
for (mb in nb.Meter_Band) {
    sb.Out_Meter_Band(.uuid_name = uuid2name(mb._uuid),
                      .action = mb.action,
                      .rate = mb.rate,
                      .burst_size = mb.burst_size)
}

/* Meter table */
for (meter in nb.Meter) {
    sb.Out_Meter(.name = meter.name,
                 .unit = meter.unit,
                 .bands = set_map_uuid2name(meter.bands))
}

のようになります。非常にシンプルに記述できますので、可読性に優れ、バグの混入の可能性も低くすることができると考えられます。これがDifferential Datalogを使う一つ目のメリットです。

Differential Datalogを適用することのもう一つのメリットは、インクリメンタルアップデートの性能向上です。eBayのHan Zhouが、Cで実装されたovn-northdを使った場合とDifferential Datalog版のovn-northdを使った時のスケールテストの結果を共有してくれています [1]。結果は以下の通りです。

Cバージョン 67分47秒
DDlogバージョン 7分39秒

Differential Datalogを使うことで、およそ10倍程度の性能向上があったことになります。残念ながらこのテストの詳しいテストシナリオははっきりしないのですが、OVNを使ったOpenStack環境でスケール試験を行なったようです。

また、RedHatのMark Michelsonらが別の性能評価をしています。Markが行ったテストは、1つの論理ルータの下に159個の論理スイッチを作り、それぞれの仮想スイッチに92個の論理ポートを作った上でACLを適用する、というものです [2]。その結果をグラフしたのが以下になります。

View post on imgur.com

 

このテストは約15,000論理ポートを順次作成していく、というシナリオなので、インクリメンタルな処理性能を測るのにあまり適したシナリオではありませんが(インクリメンタルな処理性能が最も顕著に現れるのは、すでにある大規模な環境に若干の更新をした場合です)、それでもCでの実装に比べるとDifferential Datalog (DDlog)の実装の方がかなりいい性能が得られていることが分かります。

今後に向けて

テクノロジーとしては非常に有望なDifferential Datalogですが、課題もあります。

Differential Datalogは従来の手続型言語とは大きく異なります。今までCで書いてきた人が「明日からDatalogで書いてね!」と言われてもパラダイムが全く異なりますのでなかなか難しいのではないかと思います。ツールチェーンも少々複雑です。上述の通り、Differential DatalogのコンパイラRustのコードを吐き出します。また、Differential Datalogのコンパイラ自身はHaskellで書かれています。OVNはCで書かれているので、Differential Datalog版のovn-northdの動きを調べる際には、CやDifferential DatalogだけではなくRustや場合によってはHaskellの知識も求められることになります。これらの言語およびそこで使われているツールチェーンを一通り学習するのはそれなりの時間を要するでしょう。また、Differential Datalogにはデバッグの機能も盛り込まれてはいるものの、皆さんが普段使い慣れているデバッガに比べるとまだまだプリミティブです。

ovn-northdのDifferential Datalog実装は現時点ではまだmasterとは別ブランチとなっており、masterブランチではCを使った開発が引き続き行われています。したがって、Cで書かれた新機能がmasterブランチに追加されたら、その機能をDifferential Datalogで実装して、追従していかなければなりません。これをタイムリーにやっていくのものなかなか大変です。完全にDifferential Datalogに移行ができればこのような悩みは無くなりますが、それにはもっともっとテストをしなければなりません。具体的にはCバージョンで生成されるテーブルとDifferential Datalogバージョンから生成されるテーブルがいかなる場合(障害時も含めて)で差異がない、という状態にならないとCバージョンからDifferential Datalog版に移行することはできません。これにはまだ時間がかかると思われます。また、現時点でDifferential Datalogが適用されているのはovn-northdだけです。理論的にはローカルコントローラであるovn-controllerの方にもDifferential Datalogを適用することができますが、まだ未対応です。

これらの課題がありつつも、Differential Datalogは定性的には素晴らしい特性を持っていますので、今後はOVNだけではなく、大規模なSDN環境における宣言的かつインクリメンタル処理を効率よく行う仕組みとして広く使われていくようになるのではないかと思います。NSX-TのコントローラはNiciraのコントローラと同様、Datalogベースの宣言的なエンジンを備えていますが、そこにDifferential Datalogによる差分更新機能を適用することも検討されているようです。また、Differential Datalogは非常に汎用的な仕組みですので、今後はSDNだけでなく広く分散システムに対する宣言的なアプローチとして使われていく可能性もあります。引き続き注視をしていきたいと思います。

参考リンク

[1] https://mail.openvswitch.org/pipermail/ovs-dev/2019-July/360604.html
[2] https://mail.openvswitch.org/pipermail/ovs-dev/2019-July/360889.html
[3] https://codeout.hatenablog.com/entry/2020/07/06/130233

Photo by Irvan Smith on Unsplash

オーバーレイネットワークと私

日頃から仕事でお世話になっている方からこんな記事を教えてもらった。2004年の記事だが、当時IntelのCTOだったPat Gelsinger(現VMwareのCEO)がオーバーレイネットワークの構想を持っていたのには驚かされる。Patが思い描いていた世界は(当時彼がIntelにいたということを考えると)全てのデスクトップやノートブックPCにまでオーバーレイネットワークが伸びていき、そこで色々なネットワークサービス面に接続して使う、というような姿だったのではないかと想像する。今日のオーバーレイネットワークは我々の手元のPCまで届いているとは言い難い状況だが、クラウドやデータセンターにおいてはそれに近い姿が実現されているので、2004年にこのような世界観を持っていたPatの先見性には驚かされるばかりである。

Patのような先見の明を持ち合わせていたわけではないが、なぜか私もこれまでオーバーレイネットワークに携わることがとても多かった。今回はその辺を少し振り返ってみようと思う。

私は1997年にAscend Communicationsに入社したのだが、当時Ascendはアクセスサーバーとして圧倒的なシェアを持っていて、どのISPもAscendを使っていた時代だった。そんな中、ネットワーク業界の経験がない私がAscendのSEとして飛び込んでいったわけで、最初の1年は「自分は本当に役に立っているのだろうか?」と自問自答する日々だった。PPPの16進ダンプを見るだけですらすらデバッグができる人たちがゴロゴロしている中で、自分は何をしたらいいのかと悩んでいたのである。であれば、他の人とは少し違ったことをやろう、と思い、当時Ascend MAXが持っていたAscend Tunnel Management Protocol (ATMP) を触り始めたのが、私にとってオーバーレイネットワークとの最初の出会いであった。当時はダイアルアップ系のトンネリングプロトコルとしては、ATMP、PPTP、L2Fなどベンダー色が強いものが乱立していたため、IETFとして標準的なトンネリングプロトコルを作ろうということでL2TP (Layter 2 Tunneling Protocol) が生まれた。AscendがL2TPの仕様策定にも関わっていたこともあり、私も比較的早い段階でL2TPの実装に触ることができた。ちょうどその頃、VPN周りの検証や運用に関する知見などの共有を目的とするグループvpnops(発起人は当時IRIにおられた松本直人さん)でL2TPの相互接続性の試験をしようということになり、幸い私にもお声がけを頂き検証に参加することとなった。この相互運用試験時のデバッグのためにtcpdump用のL2TP dissectorを書いて持って行ったのだが、このコードをのちにitojunさんがtcpdumpのtrunkにマージをしてくださったのは良い思い出である。

こんなことをしているうちにそこそこL2TPに関する知見が溜まっていったわけだが、丁度そんなタイミングでNTTが初のインターネット定額サービス(フレッツISDN)を始めるにあたりL2TPを使うかもしれないということで、Ascendで一番L2TPと戯れていたと思われる私がこのプロジェクトに引き込まれることになった。このプロジェクトは私にとって人生の転機となるプロジェクトであり、その際にお世話になった方々には本当に感謝しても仕切れない。そんなこんなでL2TPどっぷりな日々を送ることになり、気がつけば私もL2TPプロコルのコントロールメッセージを全てそらで言えるようになっていた(笑)

Ascendでの心残りはIPsecができなかったことだ。プロトタイプの製品はあったものの、残念ながら市場に出る製品にはならなかった。個人的にはIPsecにとても興味があったので、2000年にAscendからCoSine Communicationsという会社に移った(IPsecだけが理由ではないが、IPsecは大きな動機の一つであった)。CoSineがやっていたのは、完全な仮想ルータをIPsecでトンネルすることでオーバーレイ型のVPNを実現する、というものであった。当時は仮想ルータという概念はまだ一般的ではなく、VRFが出てきたばかりという時代だったので、CoSineがやろうとしていたことは当時としてはかなり先進的であったと思う(一方、ソフトウェアの品質はお世辞にも高くはなかったので、色々ご迷惑をおかけしました。すみません)。

当時はVPNに関しては2大派閥があった。Peerモデル派とオーバーレイモデル派である。Peerモデル派の代表はBGP/MPLS VPN(いわゆるRFC2547/RFC4364)。それに対してCoSineがやっていたのはオーバーレイモデルなVPNである。注意したのいのは、ここでいう「Peer vs オーバーレイ」というのはデータプレーンでのオーバーレイ(トンネル/カプセル化)をするかどうかの話ではなく、サービスプロバイダが顧客の経路情報に関与するかどうか、という話である。Peerモデルは顧客の経路情報とサービスプロバイダの経路情報を同じように扱うモデルである。顧客経路とサービスプロバイダのバックボーンの経路を対等(peer)に扱うのでこのように呼ばれている。一方、オーバーレイモデルではサービスプロバイダは顧客の経路情報には関与せず、顧客側の経路制御は顧客側で行う。典型的には、トンネル上でルーティングプロトコルを動かして顧客経路を交換するモデルだ。

Peerモデル vs オーバーレイモデルに関してはIETFのMailing Listでもしばしば宗教論争が起こった。当時はPeerモデル派が優勢で、Peerモデル派からは「オーバーレイモデルなどスケールするはずがない」など、こてんぱんに言われることも多く、悔しい思いをしていたのを良く憶えている。真っ向から対立していた両陣営の主張の正当性はさておき、商業的に成功したのは圧倒的にBGP/MPLS VPNであったのはみなさんよくご存知の通りである。

ひょんなことから2011年にNiciraと出会い、Niciaに行くことになった経緯についてはこちらをご参照いただきたいが、はからずもNiciraもまたオーバーレイ技術をベースとする会社であった。Niciraが開発していた製品「NVP」は、ネットワーク機能をハードウェアから切り離しネットワークの抽象化を行う、というアーキテクチャとなっており、STT(Stateless Transport Tunneling)を使って仮想スイッチ間をトンネルして仮想ネットワークを作り出す、というものであった。Niciraは2012年にVMwareに買収され、NVPはNSXとして製品に取り込まれ、年間1000億円の市場に成長した。

Nicira/VMwareのあと、2016年にViptelaというSD-WANのスタートアップに行ったが、SD-WANもやはりオーバーレイ技術をベースにしたものである。多くのSD-WAN製品はIPsecトンネルで作られるオーバーレイネットワークだ。SD-WANの柔軟性と普遍性はコントローラの存在だけでなく、オーバーレイアーキテクチャによるところも大きい。先の「Peerモデル vs オーバーレイモデル」的な観点で見ると、CPE同士で経路を交換するSD-WANはオーバーレイモデル的なVPNということになる。2000年の頃には「スケールしない」などと散々非難をされたオーバーレイモデルのVPNが、CPEの性能向上やクラウド上のコントロールプレーンの利用により、15年の時を経て実際に大規模環境で動いているのを見るとなんだか嬉しい気分になる。

オーバーレイにはオーバーヘッドは付き物である。この性能的なオーバーヘッドを理由にオーバーレイ技術が批判されるケースをしばしば目にするが、これは非常に近視的なものの見方ではないかと思う。新しいオーバーレイネットワーク技術が生まれると、それは通常ハードウェアが想定していないカプセル化であるため、性能が劣化する。しかし、そのような問題はハードウェアの進化とともに解決されていくことが多い。特にカプセル化などはハードウェアで扱いやすい問題に属すると思うので、多くの場合時とともに性能的な問題は解決されていく。長期的にはオーバーレイによる「抽象化」がもたらす技術の進化の方がはるかに大きな意味を持つと思う。

ネットワークの話ではないが、いくつか例をあげてみたい。近代的なコンピュータとオペレーティングシステムは仮想メモリシステムを使っている。仮想アドレス空間を物理アドレス空間にマップしてメモリを使っているわけだが、これはCPUが持つMMUやTLBなどの仕組みによって大きな性能劣化なく仮想メモリシステムが使えているわけである。今日、性能的なオーバーヘッドを理由に仮想メモリシステムを否定する人はいないだろう。それよりもアドレス空間の仮想化によって得られるメリットのが方が遥かに大きいのは明らかだからだ。もう一つ別の例を挙げよう。x86 CPUの仮想化も当初は性能的なオーバーヘッドが大きく実現困難と思われていたが(それを現実的な速度でやって見せて世の中をびっくりさせたのがVMwareだったわけだが)、その後Intel VTやAMD-VなどのCPUによる仮想化支援機能によって、大きな性能の劣化なくx86の仮想化ができるようになった。今日、CPUの仮想化のメリットはおそらく誰も否定しないだろうし、性能的オーバーヘッドは相対的に無視できるほど小さくなっている。オーバーレイネットワークによるネットワーク抽象化もこれらと同じ話であると思う。イノベーションは抽象化から生まれ、抽象化する事で発生するオーバーヘッドは、多くの場合ハードウェアがのちに解決してくれるのである。

私自身、初めからこのようなことを考えて約20年間一貫してオーバーレイ・ネットワークに携わってきたわけではない。「たまたま」といえばそうなのだが、きっとオーバーレイによる抽象化とそこから生まれるワクワク感がきっと本質的に好きなのだろうと思う。

今までネットワーク機器は自分たちの手の届くところにあったので、ネットワーク機器を直接「触る」ことでネットワークを構築、管理をしてきた。しかし、これからはクラウドの時代である。クラウドにも当然物理ルーターや物理スイッチはあるが、通常我々はそれらを直接触ることはできない。物理ネットワーク機器に直接触れない環境でどのようにネットワークをエンド to エンドで構築・管理していけば良いのだろうか? クラウド時代においては、オーバーレイでネットワークを作りエンド to エンドで管理していくのは必然の事のように思える。そんなわけで、これからも大いにオーバーレイネットワークに絡んでいきたいと思う次第である。

Photo by Joshua Forbes on Unsplash

ネットワーク仮想化とNSXに関する本が出ます

いままでなにか形になったものを残したいとずっと思っていましたが、少しだけ目標が叶いました。このたび、ヴイエムウェアの同僚たち数名と「詳解VMware NSX ネットワーク仮想化の基礎と応用」という書籍を出す事になりました。

詳解VMware NSX
詳解VMware NSX

翻訳本ではなく完全書き下ろしです。500ページを越えるボリュームなので、ちょっとお値段も張ってしまい申し訳ありませんが、もしご興味があれば買ってみてください。

章立ては以下のようになっています。

  • Chapter 01 技術背景と定義
  • Chapter 02 標準化とメリット
  • Chapter 03 既存ネットワークの課題
  • Chapter 04 ネットワーク仮想化のAPI
  • Chapter 05 NSXの技術解説
  • Chapter 06 OpenStackとNeutron
  • Chapter 07 SDDCとNSX

この中で私は「Chapter 05 NSXの技術解説」の前半部分といくつかのコラムを書かせていただいています。いままでも本の執筆や雑誌等への寄稿はそれなりにやっていましたが、名前が陽に出る形のものは今回がはじめてで、ちょっと感慨深いものがあります。

この本を出したいと思ったきっかけは、われわれの日々の活動の中にありました。ネットワークの仮想化というのはまだ新しい概念で、世の中で十分に浸透しているものではありません。したがってお客様の中にはネットワーク仮想化について十分に理解されていなかったり、場合によっては勘違いされていたりということがままありました。しかし、このような状況も無理はありません。いままでほとんど情報が世に出ていなかったのですから。そこで、われわれがネットワーク仮想化とNSXに関する本を書いて、このような状況を変えていかねば、と思った次第です。

この本を出すのは簡単ではありませんでした。構想からほぼ1年。途中頓挫しそうになったこともありましたが、なんとかやり遂げる事ができました。また、世界に先駆けて日本でこのような本を出せたのも意義深いことであると思っています。これもひとえに他の著者さん(水本さん、田中さん、横井さん、高田さん、小椋さん)が日々の業務の傍ら頑張ってくれたおかげです。特に、執筆者としてだけではなく、本プロジェクトをリードもしてくれた田中さんの、ともするとさぼりがちな筆者一同への激励と “ケツ叩き”(笑)のおかげで、なんとかvForum Tokyo 2014というヴイエムウェア(株)のイベントまでに出版をするという目標が達せられました。また、我々の不慣れな文章の編集に連日の徹夜でおつき合いくださった株式会社Heculaの丸山弘詩様と株式会社インプレスジャパン畑中二四様にも感謝をしたいと思います。

本を出すのが我々のゴールではありません。この本によってみなさんのネットワークの仮想化についての理解が少しでも深まり、NSXをより身近なものに感じていただけるようになれば幸いです。