Zenn
⚙️

Kubernetes 大規模クラスタで MAC アドレスが衝突した話

2021/10/10に公開
Kubernetes
network
#
cni
#
確率
tech

概要

ovs-cni という CNI を用いた際に、 MAC アドレスの衝突が発生するという問題が起きました (https://github.com/k8snetworkplumbingwg/ovs-cni/issues/206)。発生環境は 100 台の worker node、24 個の vlan、 各 vlan ごとに 1000 個のインターフェイスという状態でした。

結論から言いますと、「普通に」使った場合は衝突確率は最大でも0.0639(%)なので気にする必要はありません。「普通」が何を意味するか、算出根拠は、等を知りたい方は以下をお読み下さい。

MACアドレスについて

MACアドレスと言うと「ハードウェアに固有のアドレス」であるため衝突はしないという説明が一般的かと思います。ただ、 Kubernetes クラスタにおいては、仮想インターフェイスを多用するため、MACアドレスも自動生成したものを使用しています。では自動生成した場合にどのぐらいの確率で衝突が起こるかを考える記事になります。

衝突確率の求め方

まず、衝突確率を計算するための式を立てます。わかりやすく書くつもりではありますが、数学が苦手な方は読み飛ばしていただいて構いません。

まず簡単な例として 6 面体のサイコロを 3 回振った場合を考えます。
出目が衝突するとは、少なくとも2つのサイコロが同じ目を出していると言い換えられます。
全ての出目のパターンは6^{3}通りです。
また、全ての面が異なるパターンは(6! / (6 - 3)!) = 6 \times 5 \times 4通りです。
なので、少なくとも2つのサイコロがが同じ目を出す確率は(6^{3}-(6! / (6 - 3)!)) / 6^{3} = 0.444...
となり、確率はおよそ 44.4(%) となります。

これを一般化し、出目のパターンを possibility、試行回数を trials と書くと、衝突の確率は
(possibility^{trials} - (possibility! / (possibility - trials)!)) / possibility^{trials}
と表すことができます。

衝突確率

では上の式を用いて確率を計算していきます。MACアドレス長は 48bit ですが、 ovs-cni において MAC アドレスは 02:00:00:XX:XX:XX の形式を振っているため、実際の MAC アドレス空間は 24bit です。よってpossibility = 2^{24} = 16,777,216です。また、vlanが24個あり、それぞれが1000のインターフェイスを持つことからtrials = 24 \times 1000 = 24,000です。これを上式に当てはめて計算すると、衝突確率は99.9(%)となり、衝突が起こったのが必然であるとわかります。お気づきの通り、衝突発生の原因は 02:00:00:XX:XX:XX 形式の MAC アドレスです。そのため、これは ovs-cni 固有の不具合であると言えます。

この不具合の後、MACアドレスを 0A:58:XX:XX:XX:XX に変更する修正が入り、MACアドレス空間は32bitに拡張されました。possibility = 2^{32} = 4,294,967,296となったわけです。trialsは変わりません。これを上式に当てはめて計算すると、衝突確率は6.48(%)となり、かなり改善されています。

さらに、これまで自前で行っていたMACアドレス割当を廃止し、SetupVeth()関数に割当を任せるように変更しました。これはip link addコマンドを使った場合に相当し、MACアドレス空間を46bitに拡張することができました。MACアドレス長である 48bit よりも 2bit 少ない理由は、下記2bitが固定されているためです。それぞれのbitの意味については https://en.wikipedia.org/wiki/MAC_address を参照して下さい。

unicast/multicast bit = 0
globally unique/locally administered bit = 1

46bitに拡張することでpossibility = 2^{46} = 70,368,744,177,664となり、衝突確率は0.000409(%)まで下がりました。

ovs-cni にて発生した問題についてはこれで解決ですが、さらにインターフェイスが増えた場合を考えます。Kubernetesは「コンテナ数は300,000以下であること」というベストプラクティスを公表しています。
https://kubernetes.io/docs/setup/best-practices/cluster-large/
これに沿うように
possibility = 2^{46} = 70,368,744,177,664
trials = 300,000
の条件で計算すると衝突確率は0.0639(%)となります。なので、今のところはMACアドレスの衝突については気にしなくても大丈夫そうですが、Kubernetesの性能向上等によりコンテナ数のベストプラクティスに変化があった場合は再度計算が必要になります。

Discussion