vgoを試してみる
Go1.11から導入されるvgoを試してみたメモ書きです。
基本的な流れは、和訳: A Tour of Versioned Go (vgo) (Go & Versioning, Part2)に沿っています。versioningが必要な理由や議論などは本記事では扱いません。
上記記事からvgoの開発が進みコマンドがいくつか変更になっていたので、同じくvgoを試す方の一助となればと思います。
今後も変更が入る可能性がありますが、x/vgoからgo本体にマージされたので、いい区切りかと思い、記事としてまとめることにしました。
環境
❯ vgo version
go version go1.10.3 darwin/amd64 go:2018-02-20.1
vgoのインストール
❯ go get -u golang.org/x/vgo
vgoを動かしてみる
サンプルプログラム
// hello.go package main // import "github.com/you/hello" import ( "fmt" "rsc.io/quote" // この時点では、cannot find packageになるけどvgoが解決してくれる ) func main() { fmt.Println(quote.Hello()) }
あとは何も書いていないgo.modも作っておく。
❯ touch go.mod
vgo build
❯ vgo build vgo: resolving import "rsc.io/quote" vgo: finding rsc.io/quote v1.5.2 vgo: finding rsc.io/quote (latest) vgo: adding rsc.io/quote v1.5.2 vgo: finding rsc.io/sampler v1.3.0 vgo: finding golang.org/x/text v0.0.0-20170915032832-14c0d48ead0c vgo: downloading rsc.io/quote v1.5.2 vgo: downloading rsc.io/sampler v1.3.0 vgo: downloading golang.org/x/text v0.0.0-20170915032832-14c0d48ead0c
これでbuildされるので、実行してみる。
❯ ./hello こんにちは世界。
空だったgo.modにも追記されている。
// go.mod module github.com/you/hello require rsc.io/quote v1.5.2
依存しているモジュールをvgo list -mで表示できる。
コマンドが変更になったので、vgo list -mだと1個しか出てこない。
→vgo list -m allで全部出てくる。
❯ vgo list -m all github.com/you/hello golang.org/x/text v0.0.0-20170915032832-14c0d48ead0c rsc.io/quote v1.5.2 rsc.io/sampler v1.3.0
Upgrade
-uオプションでupdated packageを確認できる。コマンドが変わって[]内にLATESTが表示されるようになった。
❯ vgo list -u -m all vgo: finding golang.org/x/text v0.3.0 vgo: finding rsc.io/sampler v1.99.99 github.com/you/hello golang.org/x/text v0.0.0-20170915032832-14c0d48ead0c [v0.3.0] rsc.io/quote v1.5.2 rsc.io/sampler v1.3.0 [v1.99.99]
golang.org/x/textをUpgradeしてみる。
❯ vgo get golang.org/x/text vgo: downloading golang.org/x/text v0.3.0
go.modが変わっている。
❯ git diff go.mod diff --git a/go.mod b/go.mod index 3200210..6246735 100644 --- a/go.mod +++ b/go.mod @@ -1,3 +1,6 @@ module github.com/you/hello -require rsc.io/quote v1.5.2 +require ( + golang.org/x/text v0.3.0 + rsc.io/quote v1.5.2 +)
listで見ても以下のようにv0.0.0-20170915032832-14c0d48ead0cからv0.3.0になっていることがわかる。
❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.3.0
rsc.io/quote v1.5.2
rsc.io/sampler v1.3.0
テストしてみる。
❯ vgo test all ? github.com/you/hello 0.016s [no test files] ? golang.org/x/text/internal/gen 0.078s [no test files] ok golang.org/x/text/internal/tag 0.011s ? golang.org/x/text/internal/testtext 0.043s [no test files] ok golang.org/x/text/internal/ucd 0.015s ok golang.org/x/text/language 0.073s ok golang.org/x/text/unicode/cldr 0.132s ok rsc.io/quote 0.015s ok rsc.io/sampler 0.013s
rsc.io/quoteのv1.5.2には以下のようにバグがあるが、上記のようにokとなる。
これは、allの意味が"今の module 中の全てのパッケージと、それらが再帰的に import している全てのパッケージ"だから。
❯ vgo test rsc.io/quote/... ok rsc.io/quote (cached) --- FAIL: Test (0.00s) buggy_test.go:10: buggy! FAIL FAIL rsc.io/quote/buggy 0.008s
vgo get -uですべてのmoduleをupgradeできる。
❯ vgo get -u
vgo: finding rsc.io/quote latest
vgo: finding golang.org/x/text latest
vgo: finding rsc.io/sampler latest
vgo: finding golang.org/x/text latest
vgo: finding rsc.io/sampler latest
rsc.io/samplerがv1.99.99にupgradeされた。
❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.3.0
rsc.io/quote v1.5.2
rsc.io/sampler v1.99.99
でもテストには失敗する。
❯ vgo test all vgo: downloading rsc.io/sampler v1.99.99 ? github.com/you/hello 0.016s [no test files] ? golang.org/x/text/internal/gen 0.032s [no test files] ok golang.org/x/text/internal/tag (cached) ? golang.org/x/text/internal/testtext 0.020s [no test files] ok golang.org/x/text/internal/ucd (cached) ok golang.org/x/text/language (cached) ok golang.org/x/text/unicode/cldr (cached) --- FAIL: TestHello (0.00s) quote_test.go:19: Hello() = "99 bottles of beer on the wall, 99 bottles of beer, ...", want "Hello, world." FAIL FAIL rsc.io/quote 0.014s --- FAIL: TestHello (0.00s) hello_test.go:31: Hello([en-US fr]) = "99 bottles of beer on the wall, 99 bottles of beer, ...", want "Hello, world." hello_test.go:31: Hello([fr en-US]) = "99 bottles of beer on the wall, 99 bottles of beer, ...", want "Bonjour le monde." FAIL FAIL rsc.io/sampler 0.014s
Downgrade
v1.99.99へUpgradeしたらテストに失敗してしまったので、Downgradeして戻すことにする。
戻せるバージョンに何があるのか確認。
❯ vgo list -m -versions all github.com/you/hello golang.org/x/text v0.1.0 v0.2.0 v0.3.0 rsc.io/quote v1.0.0 v1.1.0 v1.2.0 v1.2.1 v1.3.0 v1.4.0 v1.5.0 v1.5.1 v1.5.2 v1.5.3-pre1 rsc.io/sampler v1.0.0 v1.2.0 v1.2.1 v1.3.0 v1.3.1 v1.99.99
rsc.io/samplerを一つ前のversionv1.3.1へ戻す。
❯ vgo get rsc.io/sampler@v1.3.1 vgo: finding rsc.io/sampler v1.3.1 vgo: downloading rsc.io/sampler v1.3.1
rsc.io/samplerがv1.99.99からv1.3.1にdowngradeされた。
❯ git diff go.mod diff --git a/go.mod b/go.mod index 6246735..a62aa4e 100644 --- a/go.mod +++ b/go.mod @@ -3,4 +3,5 @@ module github.com/you/hello require ( golang.org/x/text v0.3.0 rsc.io/quote v1.5.2 + rsc.io/sampler v1.3.1 )
ちゃんとテストも通る。
❯ vgo test all ? github.com/you/hello 0.021s [no test files] ? golang.org/x/text/internal/gen 0.020s [no test files] ok golang.org/x/text/internal/tag (cached) ? golang.org/x/text/internal/testtext 0.031s [no test files] ok golang.org/x/text/internal/ucd (cached) ok golang.org/x/text/language (cached) ok golang.org/x/text/unicode/cldr (cached) ok rsc.io/quote 0.016s ok rsc.io/sampler 0.015s
もっと前のversionv.1.2.0にすることもできる。
rsc.io/quoteも依存しているので一緒にdowngradeする必要がある。
❯ vgo get rsc.io/sampler@v1.2.0 vgo: finding rsc.io/sampler v1.2.0 vgo: finding rsc.io/quote v1.5.1 vgo: finding rsc.io/quote v1.5.0 vgo: finding rsc.io/quote v1.4.0 vgo: finding rsc.io/sampler v1.0.0 vgo: downloading rsc.io/sampler v1.2.0
ただし、テストに失敗する。
❯ vgo test all vgo: downloading rsc.io/quote v1.4.0 ? github.com/you/hello 0.019s [no test files] ? golang.org/x/text/internal/gen 0.023s [no test files] ok golang.org/x/text/internal/tag (cached) ? golang.org/x/text/internal/testtext 0.035s [no test files] ok golang.org/x/text/internal/ucd (cached) ok golang.org/x/text/language (cached) ok golang.org/x/text/unicode/cldr (cached) --- FAIL: TestHello (0.00s) quote_test.go:12: Hello() = "こんにちは世界。", want "Hello, world." FAIL FAIL rsc.io/quote 0.017s --- FAIL: TestHello (0.00s) hello_test.go:31: Hello([fr en-US]) = "Bonjour le monde.", want "Bonjour la monde." FAIL FAIL rsc.io/sampler 0.012s
noneで依存しているモジュールをすべて削除できる。
❯ vgo get rsc.io/sampler@none vgo: finding rsc.io/quote v1.3.0
こうするとテストが通る（全然モジュールが残っていないけど）。
❯ vgo test all vgo: downloading rsc.io/quote v1.3.0 ? github.com/you/hello 0.009s [no test files] ok rsc.io/quote 0.009s
Exclude
v1.99.99がうまく動かないことを記録したい。
事前準備として、最新化しておく。
❯ vgo get -u
vgo: finding rsc.io/quote latest
vgo: finding golang.org/x/text latest
vgo: finding rsc.io/quote latest
vgo: finding rsc.io/sampler latest
vgo: finding golang.org/x/text latest
vgo: finding rsc.io/sampler latest
たしかにv1.99.99になっている。
❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.3.0
rsc.io/quote v1.5.2
rsc.io/sampler v1.99.99
go.modにexclude "rsc.io/sampler" v1.99.99を追加すればよい。
合わせてgo.modでrsc.io/sampler v1.3.1にするのも忘れずに。
❯ vgo list -m all
github.com/you/hello
golang.org/x/text v0.3.0
rsc.io/quote v1.5.2
rsc.io/sampler v1.3.1
ちなみに、rsc.io/sampler v1.3.1にするのも忘れると以下のようにエラーになってくれるのでちゃんとExcludeされている。
❯ vgo get -u vgo: github.com/you/hello() depends on excluded rsc.io/sampler(v1.99.99) with no newer version available
これでテストが通る。
❯ vgo test all ? github.com/you/hello 0.016s [no test files] ? golang.org/x/text/internal/gen 0.021s [no test files] ok golang.org/x/text/internal/tag (cached) ? golang.org/x/text/internal/testtext 0.021s [no test files] ok golang.org/x/text/internal/ucd (cached) ok golang.org/x/text/language (cached) ok golang.org/x/text/unicode/cldr (cached) ok rsc.io/quote (cached) ok rsc.io/sampler (cached)
Replace
依存していたrsc.io/quoteを置き換えてみる。
❯ git clone https://github.com/rsc/quote ../quote
../quote/quote.goを以下のように書き換える。
// Hello returns a greeting. func Hello() string { // return sampler.Hello() // これを消して return sampler.Glass() // こっちを追加 }
go.modの末尾にreplace "rsc.io/quote" v1.5.2 => "../quote"を追記する。
すると以下のようにreplaceされていることが確認できる。
❯ vgo list -m all github.com/you/hello golang.org/x/text v0.3.0 rsc.io/quote v1.5.2 => ../quote rsc.io/sampler v1.3.1
buildして実行する。
❯ vgo build ❯ ./hello 私はガラスを食べられます。それは私を傷つけません。
references
RustでTOMLを読み込む
toml-rsで、以下のPerson.tomlを読み込みます。
# Person.toml [profile] name = "Alice" age = 20
準備
toml-rsに加えて、
DeserializeにSerdeを使うので、Cargo.tomlに以下を追記します。
# Cargo.toml [dependencies] serde = "1.0" serde_derive = "1.0" toml = "0.4"
実装
パースは、toml::from_str()でできるので、パースするための構造体を定義します。
今回は、読み込み元のtomlファイルに値が存在しないことを考慮して、Optionにしましたが、確実に値が存在するのであれば、Optionにしないのもありだと思います。(参照するときにunwrap()だらけになりそうなので...)
#[derive(Debug, Deserialize)] struct Person { profile: Option<Profile>, } #[derive(Debug, Deserialize)] struct Profile { name: Option<String>, age: Option<i32>, }
ファイル読み込みからパースまでの実装です。
#[macro_use] extern crate serde_derive; extern crate toml; use std::fs; use std::io::{BufReader, Read}; #[derive(Debug, Deserialize)] struct Person { profile: Option<Profile>, } #[derive(Debug, Deserialize)] struct Profile { name: Option<String>, age: Option<i32>, } fn read_file(path: String) -> Result<String, String> { let mut file_content = String::new(); let mut fr = fs::File::open(path) .map(|f| BufReader::new(f)) .map_err(|e| e.to_string())?; fr.read_to_string(&mut file_content) .map_err(|e| e.to_string())?; Ok(file_content) } fn main() { let s = match read_file("./Person.toml".to_owned()) { Ok(s) => s, Err(e) => panic!("fail to read file: {}", e), }; let person: Result<Person, toml::de::Error> = toml::from_str(&s); match person { Ok(p) => println!("{:#?}", p), Err(e) => panic!("fail to parse toml: {}", e), }; }
実行
以下のようにパースできます。
❯ cargo run Person { profile: Some( Profile { name: Some( "Alice" ), age: Some( 20 ) } ) }
References
ルーター自作本を試す環境をnetnsの仮想ネットワークで実現する
ルーター自作でわかるパケットの流れ/小俣 光之を読みました。
本文にほとんどがソースコードのためひたすら写経しました。 ちなみに後半に差し掛かったあたりで気づいたのですが、サポートページでソースコードは公開されています。
「せっかく書いたのだから動かしたい！」という欲求が生まれたものの、本書に書かれているような物理機器が手元になかったので、netnsで仮想ネットワークを構築しました。
構成
ネットワーク構成図は以下のとおりです。
環境
手元にあった環境のため古いですが、vagrantで立てたlinux環境を使いました。
$ cat /etc/redhat-release CentOS release 6.6 (Final)
netnsを使ってネットワークを構築する
基本的にroot権限が必要です。
namespaceを区切る
host、RT、NextRouterをnamespaceを区切ることで実現します。
sudo ip netns add host sudo ip netns add RT sudo ip netns add NextRouter
以下で作成されたことが確認できます。
$ ip netns show RT host NextRouter
ケーブルをつなぐ
Linux Network Namespaceでは、vethを物理ケーブルだと思うとわかりやすいです。
構成図の通り繋いでいきます。
命名規則は<ホスト名>_<I/F名>としました。NextRouterだけ文字制限なのか設定できなかったのでNRと略しています。
I/Fは、本書中でルータのLAN側をeth0、WAN側をeth1と指定されていたので、その他の機器でも統一しています。
sudo ip link add host_veth1 type veth peer name RT_veth0 sudo ip link add RT_veth1 type veth peer name NR_veth0 sudo ip link add NR_veth1 type veth peer name Linux_veth0
上記でケーブルは繋いだので、各機器に所属させます。
sudo ip link set host_veth1 netns host sudo ip link set RT_veth0 netns RT sudo ip link set RT_veth1 netns RT sudo ip link set NR_veth0 netns NextRouter sudo ip link set NR_veth1 netns NextRouter
上記のip link setを実行する前は、ホストOS(CentOS)上でip link showとすると見えていたリンクが以下のようになっていると思います。
$ ip link show 1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00 2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state UP qlen 1000 link/ether 08:00:27:2d:82:3a brd ff:ff:ff:ff:ff:ff 10: Linux_veth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state DOWN qlen 1000 link/ether 1a:dd:55:e7:f4:bd brd ff:ff:ff:ff:ff:ff
ifconfigでもOKですが、この時点ではifconfig -aとしないとDOWNしているI/Fは表示されないはずです。
loとeth0はvagrantが割り当てているのもので今回の対象でないので、Linux_veth0だけになっていることに注目してください。
言い換えると、host_veth1、RT_veth0、RT_veth1、NR_veth0、NR_veth1がそれぞれのnamespaceに所属したので、ホストOS(CentOS)から見えなくなっています。
IPアドレスを採番する
/24単位でセグメントを分ける設計としました。また、hostは拡張性を見据え（今は関係ないですが。。。）、若番から採番します。
next hopになる機器は老番からの採番としています。
sudo ip netns exec host ip addr add 192.168.0.1/24 dev host_veth1 sudo ip netns exec RT ip addr add 192.168.0.254/24 dev RT_veth0 sudo ip netns exec RT ip addr add 192.168.1.1/24 dev RT_veth1 sudo ip netns exec NextRouter ip addr add 192.168.1.254/24 dev NR_veth0 sudo ip netns exec NextRouter ip addr add 192.168.2.1/24 dev NR_veth1 sudo ip addr add 192.168.2.254/24 dev Linux_veth0
確認コマンドのため、ここでは省略しますが、ip addr showで採番は確認できます。
I/Fを立ち上げる
各機器のI/Fをupさせます。loも忘れずに。
sudo ip netns exec host ip link set lo up sudo ip netns exec RT ip link set lo up sudo ip netns exec NextRouter ip link set lo up sudo ip netns exec host ip link set host_veth1 up sudo ip netns exec RT ip link set RT_veth0 up sudo ip netns exec RT ip link set RT_veth1 up sudo ip netns exec NextRouter ip link set NR_veth0 up sudo ip netns exec NextRouter ip link set NR_veth1 up sudo ip link set Linux_veth0 up
確認コマンドのため、ここでは省略しますが、ip link showでstateがUPになっていることが確認でき、ifconfigでも見えるようになります。
ルーティングを設定する
各機器のWAN側にデフォルトゲートウェイを設定します。
ホストOS(CentOS)とNextRouterには、LAN側へstatic routeを設定します。
- ホストOS(CentOS):
192.168.0.0/24,192.168.1.0/24 - NextRouter:
192.168.0.0/24
Direct Connectedになるセグメントはルーティング不要です。
sudo ip netns exec host ip route add default via 192.168.0.254 sudo ip netns exec RT ip route add default via 192.168.1.254 sudo ip netns exec NextRouter ip route add default via 192.168.2.254 sudo ip netns exec NextRouter ip route add 192.168.0.0/24 via 192.168.1.1 sudo ip route add 192.168.0.0/24 via 192.168.2.1 sudo ip route add 192.168.1.0/24 via 192.168.2.1
ip_forwardを有効化する
パケット転送を行えるようにip_forwardを有効化します。
ただし、RTは自作ルータのため転送機能があるためLinuxと機能が重複しないよう無効化します。
つまり、hostとNextRouterがip_forwardを有効化する対象です。
しかしnetnsでは、ネットワークまわりの設定だけがnamespaceごとに区切られていますが、ファイルシステムは共通のため、
sudo sysctl -w net.ipv4.ip_forward=1で設定するとRTも含めて全機器で有効化されてしまいます。
netnsでは、/etc/netns/<namespace名>が優先的に読み込まれるので、
RTについては、net.ipv4.ip_forward=0とした/etc/sysctl.confを/etc/netns/RT/sysctl.confとしてコピーしておけばOKです。
デフォルト値は、0のはずなので、念の為sysctl net.ipv4.ip_forwardでnet.ipv4.ip_forward = 0になっていることを確認したあと、以下のようにコピーしましょう。
sudo cp /etc/sysctl.conf /etc/netns/RT/
RT以外は共通で有効化するので以下を実行しましょう。
sudo sysctl -w net.ipv4.ip_forward=1
sysctl net.ipv4.ip_forwardでnet.ipv4.ip_forward = 1になっていればOKです。
自作ルータ
自作ルータのコードは、サポートページで公開されています。 もしくは本書を見ていただくのがよいと思います。
パラメータ
main.c中のパラメータは以下のように設定します。
PARAM Param = {"RT_veth0", "RT_veth1", 1, "192.168.0.254"};
実行してみる
hostからホストOS(CentOS)のveth0(192.168.2.254)にpingを打ってみましょう。
先に自作ルータを 起動せず にpingを打ってみましょう。
sudo ip netns exec RT bash #hostにログイン $ ping 192.168.2.254 -c 1 PING 192.168.2.254 (192.168.2.254) 56(84) bytes of data. --- 192.168.2.254 ping statistics --- 1 packets transmitted, 0 received, 100% packet loss, time 10000ms
予想通り、タイムアウトします。
では、いよいよ自作ルータを試します。
sudo ip netns exec RT bashでRTにログインしてからmakeした./routerを実行します。
(ログインしないとI/Fがないと怒られるはずです)
ping 192.168.2.254 -c 1 PING 192.168.2.254 (192.168.2.254) 56(84) bytes of data. 64 bytes from 192.168.2.254: icmp_seq=1 ttl=62 time=0.304 ms --- 192.168.2.254 ping statistics --- 1 packets transmitted, 1 received, 0% packet loss, time 0ms rtt min/avg/max/mdev = 0.304/0.304/0.304/0.000 ms
ちゃんとping応答がありました！
ルータ側のログ
おまけです。ルータ側のログを見てみましょう。
本書に記載のものに加えていくつか自分で見やすいようにデバッグログを追加しています。
<INFO>となっているものが追加したものです（デバッグしながらだったので他にもあるかも）。
$ ./router NextRouter=192.168.1.254 RT_veth0 OK addr=192.168.0.254 subnet=192.168.0.0 netmask=255.255.255.0 RT_veth1 OK addr=192.168.1.1 subnet=192.168.1.0 netmask=255.255.255.0 router start
ここまでがルータ起動処理です。RT_veth0とRT_veth1を自作ルータに割り当て、NextRouterのIPを設定しています。
--------AnalyzePacket------- <INFO> dst IP: 192.168.2.254 <INFO> subnet: 255.255.255.0 [0]:192.168.2.254 to NextRouter ----Ip2MacSearch---- Ip2Mac ADD [1] 192.168.1.254 = 0 <INFO> dst MAC: 00:00:00:00:00:00 Ip2Mac(192.168.1.254):NG Ip2Mac(192.168.1.254):Send Arp Request [0]:Ip2Mac:error or sending AppendSendData:[1] 192.168.1.254 98bytes(Total=1:98bytes)
上記が192.168.2.254宛にpingを打ったログです。
192.168.2.0/24は自作ルータのI/Fが持っているセグメントではないので、NextRouterへパケットを転送しようとしています。
しかし、NextRouterのIP192.168.1.254に紐づくMACアドレスを知らないので、Arp Requestを投げ、pingパケットはバッファに積んでいます。
--------AnalyzePacket------- [1]recv: ARP REPLY: 42bytes ----Ip2MacSearch---- AppendSendReqData:[1] 0 Ip2Mac EXIST [1] 192.168.1.254 = 0 Ip2Mac(192.168.1.254):OK dst MAC(Ip2Mac): 7e:85:60:2f:76:fb GetSendReqData:[1] 0 GetSendData:[1] 192.168.1.254 98bytes iphdr.ttl 64->63 write:BufferSendOne:[1] 98bytes
Arp Replyが返ってきました。これでNextRouterのMACアドレスを知ることができたのでバッファにあったpingパケットを[1](RT_veth1)から送出しています。
L3ホップになるのでttlも減算しています。
--------AnalyzePacket------- <INFO> dst IP: 192.168.0.1 <INFO> subnet: 255.255.255.0 [1]:192.168.0.1 to TargetSegment ----Ip2MacSearch---- Ip2Mac ADD [0] 192.168.0.1 = 0 <INFO> dst MAC: 00:00:00:00:00:00 Ip2Mac(192.168.0.1):NG Ip2Mac(192.168.0.1):Send Arp Request [1]:Ip2Mac:error or sending AppendSendData:[1] 192.168.0.1 98bytes(Total=1:98bytes)
宛先が192.168.0.1となっていることがからもわかるように、pingの戻りパケットです。
先程と同じようにArp RequestでIP-MACアドレス解決を図っています。
--------AnalyzePacket------- [0]recv: ARP REPLY: 42bytes ----Ip2MacSearch---- AppendSendReqData:[0] 0 Ip2Mac EXIST [0] 192.168.0.1 = 0 Ip2Mac(192.168.0.1):OK dst MAC(Ip2Mac): 02:01:1d:da:db:04 GetSendReqData:[0] 0 GetSendData:[0] 192.168.0.1 98bytes iphdr.ttl 63->62 write:BufferSendOne:[0] 98bytes
Arp Replyで192.168.0.1に紐づくMACアドレスが学習できたので、パケットを送出します。
ここでも、L3ホップになるのでttlも減算しています。
これらの処理が行われた結果、hostでもping応答を確認できたわけです。
最後に
Cでechoサーバやチャットサーバを書いたことがあったものの、写経時にtypoが多すぎてデバッグに時間取られました。 奇しくも動作をより理解する結果に繋がったので悪くはなかったかなと思っています。 本記事のnetnsも普段dockerがいい感じにやってくれる部分を知ることができたので、いい勉強になりました。
ちなみに、本記事タイトルは、本書タイトルそのままだと長くなりすぎなので、略しましたが通称あるんでしょうか。
- 作者: 小俣 光之
- 出版社/メーカー: 技術評論社
- 発売日: 2011/07/09
- メディア: 単行本（ソフトカバー）
- 購入: 4人 クリック: 130回
- この商品を含むブログ (12件) を見る
References
【Golang】DFS(深さ優先探索)による有向グラフのcycle detectを実装する
【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにしたの続きで、今度は有向グラフのcycle detectです。 Detect Cycle in Directed Graph Algorithmを視聴したので、実装してみることにします。
有向グラフにおけるDFSによるcycle detectのアルゴリズム
有向グラフでは、同じDFSによるcycle detectでも、無向グラフのときと異なり、White Set、Grey Set、Black Setという3つの集合を利用します。特にGrey Setは、無向グラフにおけるVisited Setの役割を果たします。
これらの集合を使い、以下のアルゴリズムでDFSによるcycle detectを行います。
- すべての頂点を
White Setに追加する White Setから頂点sを取り出す- 頂点
sをGrey Setに加える - 頂点
sの接続先である頂点cを順番に訪問する。未訪問の接続先がなくなった(葉のように元々接続先がない場合も含む)場合、頂点sをBlack Setに加え、一つ前に訪問した頂点を頂点sとして、4.を繰り返す - 頂点
cがBlack Setに含まれていれば、4.における次の頂点へ - 頂点
cがGrey Setに含まれていれば、cycleありとして探索終了 - 5.,6.のいずれでもない(=頂点
cがWhite Setに含まれる)場合は、3.から繰り返し White Setが空になったら、cycleなしとして探索終了
※sはstartの意で命名(White Setから取り出す度に設定されるので厳密には始点ではないですが)
※cはcurrentの意で命名
例：cycleあり
2→4→5→2のcycleがある例です。
頂点0から上記のアルゴリズムを適用した場合のWhite Set、Grey Set、Black Setの変化を表にまとめると以下の通りです。
| 頂点 | White Set | Grey Set | Black Set |
|---|---|---|---|
| - | 0,1,2,3,4,5 | - | - |
| 0 | 1,2,3,4,5 | 0 | - |
| 1 | 2,3,4,5 | 0,1 | - |
| 3 | 2,4,5 | 0,1,3 | - |
| 1 | 2,4,5 | 0,1 | 3 |
| 4 | 2,5 | 0,1,4 | 3 |
| 5 | 2 | 0,1,4,5 | 3 |
| 2 | - | 0,1,2,4,5 | 3 |
最終行の時点で、頂点2がGrey Setに含まれるため、cycleありとなります。
例：cycleなし
上記の例から2→4の辺を除き、cycleをなくした例です。
こちらも先程と同様に、White Set、Grey Set、Black Setの変化を表にまとめます。途中までは一緒ですね。
| 頂点 | White Set | Grey Set | Black Set |
|---|---|---|---|
| - | 0,1,2,3,4,5 | - | - |
| 0 | 1,2,3,4,5 | 0 | - |
| 1 | 2,3,4,5 | 0,1 | - |
| 3 | 2,4,5 | 0,1,3 | - |
| 3 | 2,4,5 | 0,1 | 3 |
| 1 | 2,4,5 | 0,1 | 3 |
| 4 | 2,5 | 0,1,4 | 3 |
| 5 | 2 | 0,1,4,5 | 3 |
| 2 | - | 0,1,2,4,5 | 3 |
| 5 | - | 0,1,4,5 | 2,3 |
| 4 | - | 0,1,4 | 2,3,5 |
| 1 | - | 0,1 | 2,3,4,5 |
| 0 | - | 0 | 1,2,3,4,5 |
| - | - | - | 0,1,2,3,4,5 |
White Setを探索し終わったので、cycleなしとなります。
設計
隣接リスト
【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにした同様に隣接リストで実装します。上記の例はそれぞれ以下のようにリストを持つことになります。
例：cycleあり
| 頂点 | 隣接リスト |
|---|---|
| 0 | 1,2 |
| 1 | 3,4 |
| 2 | 4 |
| 3 | - |
| 4 | 5 |
| 5 | 2 |
例：cycleなし
| 頂点 | 隣接リスト |
|---|---|
| 0 | 1,2 |
| 1 | 3,4 |
| 2 | - |
| 3 | - |
| 4 | 5 |
| 5 | 2 |
各Setをどうするか
White Set、Grey Set、Black Setをcolorという[]int型で実装することも考えましたが、有向グラフでは強連結でないグラフに対して扱いが難しくなりそうだったのでmapで実装します。
sliceとmapのdelete(+make)はどちらが速いのか - 逆さまにしたの結果が、無駄になってしまったのは残念ですが、Setと言っているのでmapのほうがわかりやすく実装できると考えて前に進むことにします。
実装
【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する - 逆さまにしたと同様に以下のようにGraphを定義します。
// Graph is a graph with n vertices and edges. type Graph struct { n int edges [][]int }
コンストラクタも同様です。
// NewGraph creates a new graph with n vertices. func NewGraph(n int) *Graph { g := &Graph{ n: n, edges: make([][]int, n), } return g }
辺の追加
AddEdgeは、無向グラフと異なり、片方向にだけ辺を追加する点に注意です。
// AddEdge adds a edge connects vertex u to v and v to u. func (g *Graph) AddEdge(u, v int) { g.edges[u] = append(g.edges[u], v) }
DFSによるcycle detectの実装
基本的には、記事の先頭で述べたアルゴリズムを実装していくだけですが、White Setから頂点を選ぶ操作は以下のように実装しました。
c := -1 for c = range wSet { break }
mapにはpopがないので、rangeでランダムに(mapに対するrangeは順序を保ちません)1つ取得し、breakしています。
これを踏まえた実装は以下です。
func dfs(c int, wSet, gSet, bSet map[int]struct{}, edges [][]int) bool { delete(wSet, c) gSet[c] = struct{}{} for _, n := range edges[c] { _, ok := bSet[n] if ok { continue } _, ok = gSet[n] if ok { return true } if dfs(n, wSet, gSet, bSet, edges) { return true } } delete(gSet, c) bSet[c] = struct{}{} return false }
呼び出し側では、初期化も含めて行っています。
func (g *Graph) ExistsCycle() bool { wSet := make(map[int]struct{}, g.n) gSet := make(map[int]struct{}, g.n) bSet := make(map[int]struct{}, g.n) for i := 0; i < g.n; i++ { wSet[i] = struct{}{} } for len(wSet) != 0 { c := -1 for c = range wSet { break } if dfs(c, wSet, gSet, bSet, g.edges) { return true } } return false }
テスト
最後に上述の例で正しく動作することを試してみます。
例：cycleあり
| 頂点 | 隣接リスト |
|---|---|
| 0 | 1,2 |
| 1 | 3,4 |
| 2 | 4 |
| 3 | - |
| 4 | 5 |
| 5 | 2 |
g := directed.NewGraph(6) g.AddEdge(0, 1) g.AddEdge(0, 2) g.AddEdge(1, 3) g.AddEdge(1, 4) g.AddEdge(2, 4) g.AddEdge(4, 5) g.AddEdge(5, 2) fmt.Println(g.ExistsCycle()) // true
例：cycleなし
| 頂点 | 隣接リスト |
|---|---|
| 0 | 1,2 |
| 1 | 3,4 |
| 2 | - |
| 3 | - |
| 4 | 5 |
| 5 | 2 |
g := directed.NewGraph(6) g.AddEdge(0, 1) g.AddEdge(0, 2) g.AddEdge(1, 3) g.AddEdge(1, 4) g.AddEdge(4, 5) g.AddEdge(5, 2) fmt.Println(g.ExistsCycle()) // false
References
sliceとmapのdelete(+make)はどちらが速いのか
Golangでmapとsliceどちらが速いのかに引き続いて、要素を削除する場合のベンチマークを取ってみる。
やり方
slice
メモリリークしないようにSliceTricksにある以下の方法で要素を削除する。
copy(a[i:], a[i+1:]) a[len(a)-1] = nil // or the zero value of T a = a[:len(a)-1]
map
組み込みのdeleteで削除する
delete(map[typeA]typeB, typeA)
条件
- sliceは
[]int型とする - mapは
map[int]int型とする - sliceから削除したい要素のindexは
n/2を使う - mapから削除したい要素を
n/2とする
環境
macOS High Sierra version 10.13.4（17E202） MacBook Pro (Retina, 13-inch, Early 2015) 2.7 GHz Intel Core i5 16 GB 1867 MHz DDR3 Intel Iris Graphics 6100 1536 MB
❯ go version go version go1.10.1 darwin/amd64
実装
map, sliceどちらも削除前の状態を毎回使いまわす必要があるが、どちらも参照型で実装されるので、毎回makeで作り直すことにする。
make自体がmapとsliceで差がある(Appendix参照)ので、それぞれmakeするだけベンチマークも測定し、差分(make+delete-make)を結果とする。
makeに掛かる時間は要素数に単調増加するので、それぞれ差分の計算は、同じ要素数でmakeした結果から求める。
ベンチマークの実装は以下の通り。
slice
func benchmarkOfDeleteFromSlice(n int, b *testing.B) { idx := n / 2 for i := 0; i < b.N; i++ { s := make([]int, n) copy(s[idx:], s[idx+1:]) s[len(s)-1] = 0 s = s[:len(s)-1] } } func benchmarkOfMakeSlice(n int, b *testing.B) { for i := 0; i < b.N; i++ { _ = make([]int, n) } }
map
func benchmarkOfDeleteFromMap(n int, b *testing.B) { idx := n / 2 for i := 0; i < b.N; i++ { m := make(map[int]int, n) delete(m, idx) } } func benchmarkOfMakeMap(n int, b *testing.B) { for i := 0; i < b.N; i++ { _ = make(map[int]int, n) } }
結果
要素数が少ないとmakeに掛かる時間が測定によってばらつきがあり、差分がマイナスになったが、要素数が1000を超えたあたりからmapよりsliceが有利であることがわかる。またsliceは削除に要する時間が要素数に依らず、ある程度一定の値となっている。
Appendix
ベンチマーク結果の生データは以下の通り。
BenchmarkOfDeleteFromSlice10-4 30000000 40.0 ns/op BenchmarkOfDeleteFromSlice30-4 20000000 66.5 ns/op BenchmarkOfDeleteFromSlice70-4 10000000 134 ns/op BenchmarkOfDeleteFromSlice100-4 10000000 229 ns/op BenchmarkOfDeleteFromSlice300-4 3000000 554 ns/op BenchmarkOfDeleteFromSlice700-4 1000000 1034 ns/op BenchmarkOfDeleteFromSlice1000-4 1000000 1478 ns/op BenchmarkOfDeleteFromSlice3000-4 300000 3903 ns/op BenchmarkOfMakeSlice10-4 50000000 33.8 ns/op BenchmarkOfMakeSlice30-4 20000000 59.6 ns/op BenchmarkOfMakeSlice70-4 10000000 119 ns/op BenchmarkOfMakeSlice100-4 10000000 173 ns/op BenchmarkOfMakeSlice300-4 3000000 494 ns/op BenchmarkOfMakeSlice700-4 2000000 938 ns/op BenchmarkOfMakeSlice1000-4 1000000 1465 ns/op BenchmarkOfMakeSlice3000-4 300000 3785 ns/op BenchmarkOfDeleteFromMap10-4 20000000 102 ns/op BenchmarkOfDeleteFromMap30-4 5000000 255 ns/op BenchmarkOfDeleteFromMap70-4 3000000 604 ns/op BenchmarkOfDeleteFromMap100-4 3000000 583 ns/op BenchmarkOfDeleteFromMap300-4 1000000 1546 ns/op BenchmarkOfDeleteFromMap700-4 500000 2992 ns/op BenchmarkOfDeleteFromMap1000-4 200000 6079 ns/op BenchmarkOfDeleteFromMap3000-4 100000 12120 ns/op BenchmarkOfMakeMap10-4 20000000 97.8 ns/op BenchmarkOfMakeMap30-4 5000000 251 ns/op BenchmarkOfMakeMap70-4 3000000 590 ns/op BenchmarkOfMakeMap100-4 2000000 580 ns/op BenchmarkOfMakeMap300-4 1000000 1563 ns/op BenchmarkOfMakeMap700-4 500000 3100 ns/op BenchmarkOfMakeMap1000-4 200000 5980 ns/op BenchmarkOfMakeMap3000-4 100000 11305 ns/op
すべてまとめてグラフにすると以下の通り。
makeのみの所要時間は以下の通り。
一貫して、sliceのほうがmakeに要する時間は少なかった。
sliceとmapの内部実装も以下の通りで、sliceのほうが初期化に掛かる時間が少ないと思われる。
sliceの内部実装
type slice struct { array unsafe.Pointer len int cap int }
mapの内部実装
// A hash iteration structure. // If you modify hiter, also change cmd/internal/gc/reflect.go to indicate // the layout of this structure. type hiter struct { key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/internal/gc/range.go). value unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go). t *maptype h *hmap buckets unsafe.Pointer // bucket ptr at hash_iter initialization time bptr *bmap // current bucket overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive startBucket uintptr // bucket iteration started at offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1) wrapped bool // already wrapped around from end of bucket array to beginning B uint8 i uint8 bucket uintptr checkBucket uintptr }
References
【nsdi'18論文】Stateless Datacenter Load-balancing with Beamerを読んだ
2018年4月9日〜11日に開催されていたnsdi'18で Community Awardに選ばれたStateless Datacenter Load-balancing with Beamerの論文を読んだのでメモ書きを残します。 こちらで発表も見れます。 自分の理解の範囲で記載しているので、詳細や正確性を求める方は本論文を読んだほうがいいです。
概要、背景
論文の内容は、タイトルそのままですが、データセンター向けのstatelessなLBを実装したという内容です。このLBの名前がBeamerです。 論文中では、TCPおよびMPTCP(multipath TCP)で実装したことが述べられています。
まずは、LBからサーバへのパケット振り分けについて見ていきましょう。
(本論文Figure 1より引用)
インターネットや外部からBorder routerにやってきたパケットに対して、Border routeはMUXのVIP向けにパケットを投げます。 MUXがLBだと思ってもらうとわかりやすいと思います。 DIP(direct IP)は、サーバの実IPを指しており、MUXの役割は、VIPに着信したパケットをサーバに振り分ける(Load-Balanceする)ことです。 従来のLBは、どのDIPに対して振り分けを行うかを、以下のような計算で決定します。
hash(srcIP, dstIP, srcPort, dstPort, protocol) % N
N: DIPの数
論文中では、5つの引数をfive-tupleと呼んでおり、flow単位の振り分けとしています。TCPでは、sequence numberが前後して届くと再送要求されるので、余計な再送要求が起こらないようflow単位の振り分けがよく行われます。物理的に同じスイッチ(QoSなどの優先制御がなければ、Queueで処理されるので順番が変わらない)、ケーブルを通れば、パケットの追い越しは起こらず、dropしていないのに再送要求されるということもないです。
しかし、flow単位の振り分けでは、以下のような要望があったときに問題が発生します。
- メンテナンスのため、サーバへの振り分けを止めたい
- 新しくサーバ追加したい
- サーバに障害が発生した
先程のhash(srcIP, dstIP, srcPort, dstPort, protocol) % Nから明らかなようにサーバ台数Nが変化すると振り分け先のサーバが変わってしまいます。サーバでTCP connectionのstateを持っているので、下記図のように途中でサーバBを追加した場合、青色の既存connectionの整合性が取れなくなってしまいます。
(本論文Figure 3より引用)
一般的なLBでは、サーバ台数が増減してもTCP connectionを維持したいので、flow単位のconnectionをすべて保持しています。ただし、そのコストも馬鹿にならず、40%くらいスループット落ちると述べられています。また、一般的なLBはSYN flood攻撃にも弱い点も指摘されています。
Beamerでの解決方法
上記を解決するため、Beamerでは、Bucketと呼ばれる中間層を設け、stable hashingを実現します。
Bucketは、サーバ台数Nに対して十分大きなサイズBを持ち(論文中だとB=100N)、b = hash(5tuple)%Bなどで実サーバとmappingします。
※ 論文中では、mapping方法に依存しない手法であり、rendezvous hashingやMaglevでも応用できると書かれています。だからこそハードウェアにも応用できるそうです。なお、本論文では貪欲法で、muxにアサインされる隣接バケットのサイズを最大にするようmappingしており、TCAMが節約できると主張しています。実際、以下のようにmappingをまとめることができるようです。
(本論文Figure 5より引用)
このようにmappinされたBucketは、全MUXで共有されます。この方法では、サーバ台数が増減してもBが変わらず、実サーバとのmappingを調整するだけで対応できます。
(本論文Figure 4より引用)
Data planeとControl plane
MUXは、実際のパケットを処理するため、Date planeとして働きます。 注意事項としては、カプセル化で16Bのオーバーヘッドがあることでしょうか。カプセル化自体は、TRILLやVXLAN、VPNなどネットワークまわりでは広く顔を出すのでおかしなことではありませんが、LBの振り分けとなるサーバまでの経路上でMTUが制御される場合などは注意が必要なためオーバーヘッドがどの程度あるのか知っておくことは大切です。
また、Beamerでは、Bucketのmappingが変わることを適切に管理してあげる必要があります。
この役割は、ContollerがControl planeで実現しており、Beamerは、Apache ZooKeeperを使っているそうです。
(発表資料P.35より引用)
図のようにBucketが更新(v2)された場合、ZooKeeper経由で各MUXに通知され、各MUXが最新のBucketをダウンロードして、一貫性を保ちます。論文中では、2-phase commitで実現していると書かれていますが、このあたりはあまり詳しくないので詳細は本論文を読んでください。
Daisy chaining
Beamerでは、既存connectionを適切に扱うためDaisy chainingを使っています。
Bucketの再構成には、以下の課題の課題があります。
- 既存connectionが壊れる
- 一貫性が失われる（他が使ってるmappingをつかってしまう）
例えば、下記図の青いconnectionのように、もともとMUX2からサーバAにmappingされていた場合を考えます。
(本論文Figure 6より引用)
Bucketの再構成によってこのconnectionがサーバBにmappingされた場合、
すでにestablishedな青いconnectionは、サーバAに振り分けられる必要があります。
Beamerでは、PDIP(previous DIP)という一つ前にmappingされた実サーバを覚えておき、一定時間は前のサーバに転送することで既存が壊れることを防ぎます。
ベンチマーク
まず1コアでのベンチマークです。ここでは、性能をpps(packet per second)を、パケットサイズが変化させて比較しています。
(本論文Figure 13より引用)
StatefulなLBに対して、short packetである64Bでも2倍程度の性能が出ています。 また、コアを2つにすればline rateと同レベルの性能になっています。
論文中で最終的な性能は、以下の図で記載されています。
(本論文Figure 14より引用)
128B packetに対して、8コア1サーバあたり23-33Mpps(bps単位で20-30Gbps)を処理できる結果です。 これは現状最速であるGoogleのMaglevの2倍の性能だそうです。
最後に
というわけで、Beamerの論文を読んだまとめでした。サーバ台数の増減があった場合、当然振り直しが起こるものの仕方ないと思っていたので、解決できるのかと驚きました。ベンチマークに用いた実装もGithubで公開されてます。
またGoogleのMaglevを知らなかったので関連研究を知る意味でも勉強になりました。Maglevは本論文の2年前に同じくnsdi'16で発表されたようなので、この辺も読まないとですね。Maglevの2倍というのは、この論文のFigure 10あたりっぽいです。
References
- Olteanu, Vladimir, et al. "Stateless Datacenter Load-balancing with Beamer." 15th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 18). USENIX} Association}, 2018.
- Stateless Datacenter Load-balancing with Beamer
- Stateless datacenter load-balancing with Beamer - the morning paper
- Beamer
- Stateless Datacenter Load Balancing with Beamer
- Eisenbud, Daniel E., et al. "Maglev: A Fast and Reliable Software Network Load Balancer." NSDI. 2016.
【Golang】DFS(深さ優先探索)による無向グラフのcycle detectを実装する
前回のDisjoint-set algorithmに引き続き、Cycle in Undirected Graph Graph AlgorithmのDFSによるcycle detect実装してみます。
前回は、自作のgraphパッケージを使いましたが、グラフの持ち方(データ構造)も検討しながらまとめたいと思います。
DFSによるcycle detectのアルゴリズム
まずDFSによるcycle detectを行うアルゴリズムの概要についてです。 DFSは、Depth-First Searchの略で、その名の通り深さ優先探索によってcycle detectを行います。 アルゴリズムは以下になります。
- 入力となる始点(頂点)
sに対して、現在訪れている頂点cをsとする - 頂点
cが訪問済みか確認する（訪問済みならcycleありを返して終了。未訪問なら後続のステップへ） - 頂点
cを訪問済みにする - 頂点
cに接続する頂点を順に訪れる
以下、2.から繰り返し
※cはcurrentの意で命名
すべての頂点の探索が終了すればcycleなしとして探索終了です。
例：cycleあり
以下の例でイメージを掴んでみましょう。
まず始点sを頂点0とします。各頂点からの接続されている頂点への移動は、一つ前の頂点以外である必要があります。ここではわかりやすいように、一つ前の頂点以外で最も値が小さい頂点に移動するとしましょう。
移動を表にまとめると以下のとおりです。
| 頂点c | 訪問済みの頂点 |
|---|---|
| 0 | 0 |
| 1 | 0,1 |
| 3 | 0,1,3 |
| 0 | 0,1,3 |
頂点3から頂点0に移動した時点でステップ2.の確認で頂点0(太字)が訪問済みであるため、cycleあり となります
例：cycleなし
先程の例から辺1-3を削除したものを考えてみます。
先程と同様に始点sを頂点0とし、移動を表にまとめると以下のとおりです。
| 頂点c | 訪問済みの頂点 |
|---|---|
| 0 | 0 |
| 1 | 0,1 |
| 2 | 0,1,2 |
| 3 | 0,1,2,3 |
すべての頂点を探索しても訪問済みの頂点がなかったため、cycleなし となります
設計
データ構造をどうするか
グラフのデータ構造といえば、隣接リストと隣接行列ですが、上記の例で考えたように次に訪れる頂点さえわかればよいので隣接リストを採用します。 上記の例では以下の表のようにグラフを保持します。
例：cycleあり
| 頂点 | 隣接する頂点 |
|---|---|
| 0 | 1,2,3 |
| 1 | 0,3 |
| 2 | 0 |
| 3 | 0,1 |
例：cycleなし
| 頂点 | 隣接する頂点 |
|---|---|
| 0 | 1,2,3 |
| 1 | 0 |
| 2 | 0 |
| 3 | 0 |
sliceかmapか
Goには、リストを扱うパッケージcontainer/listがありますが、Golangのcontainer/listでスタックとキューによるとsliceのほうが速いようです（自分でベンチマークは取っていないですが）。 sliceとmapのどちらで隣接リストを持つか決めるために、Golangのmapとsliceはどちらが速いのか - 逆さまにしたでベンチマークを測定した結果、要素の探索を行わないのであれば、sliceが有利でした。 また、グラフ探索アルゴリズムとその応用にも以下のように書かれていますが、隣接行列ではなく、隣接リストを採用する場合、対象とするグラフのEdgeが少ないことを期待します。
疎グラフに対して、高速・省メモリ
Golangのmapとsliceはどちらが速いのか - 逆さまにしたのベンチマークでは、要素数による違いを実感することはできませんでしたが、GoのパフォーマンスTipsメモに以下のように書かれており、上述の通り、グラフのEdge数(=要素数)は、少ないことを期待し、sliceを採用することにします。
100要素超えくらいからmapのアクセス速度一定の恩恵が発揮される。
頂点の数は予め与えられることとして、以下のようにGraph型を定義します。
// Graph is a graph with n vertices and edges. type Graph struct { n int edges [][]int }
コンストラクタは以下。
// NewGraph creates a new graph with n vertices. func NewGraph(n int) *Graph { g := &Graph{ n: n, edges: make([][]int, n), } return g }
辺の追加
GraphにAddEdgeを生やします。
// AddEdge adds a edge connects vertex u to v and v to u. func (g *Graph) AddEdge(u, v int) { g.edges[v] = append(g.edges[v], u) g.edges[u] = append(g.edges[u], v) }
今回は省略しますが、できれば以下をエラーチェックしたほうがよいでしょう。
uとvが同一頂点でないこと- 初期化の頂点に含まれていないこと
DFSによるcycle detectの実装
DFSの実装には、スタックを用いた実装と再帰を用いた実装がありますが、再帰のほうがコードがシンプルになることが多いので、再帰で実装することにします。 アルゴリズム自体は冒頭に書いた通りですが、実装のポイントを以下です。
- 訪問済みの頂点を
visitedとし、mapで持つ
→ Golangのmapとsliceはどちらが速いのか - 逆さまにしたでベンチマークを取った通り、探索まで含めるとsliceだと遅くなってしまいます。今回は、訪れた頂点が 既に訪問済みか を確認したいのでmapにします。set型がないGoでは、mapを用いてset型の代わりのデータ構造を実装することがありますが、この時、strct{}がGo上ではサイズ0となることからmap[int]strct{}として実装するのがよいです。
- 一つ前の頂点には戻らない
→ 直前にいた頂点に戻るようなDFSの実装にしてしまうと、visitedがtrueを返すので、2頂点目を訪れた時点で(falseを返すべきなのに)trueを返して終了です。直前の頂点をp(parentを意識した命名)として実装します。
上記2点を踏まえた実装は以下です。
func dfs(p, c int, edges [][]int, visited map[int]struct{}) bool { _, ok := visited[c] if ok { return true } visited[c] = struct{}{} for _, v := range edges[c] { if v == p { continue } return dfs(c, v, edges, visited) } return false }
dfsをGraph型の変数からメソッドとして呼び出せるように以下のように実装します。
func (g *Graph) ExistsCycle() bool { return dfs(-1, 0, g.edges, map[int]struct{}{}) }
ここで、pは直前に訪れた頂点がないためdfs()中のv == pがfalseになるようにp = -1としています。さらに探索を開始する頂点(冒頭のアルゴリズムにあるs)は、どこでもいいので、s = 0から始めています。
テスト
上記の例で正しく動作することを試してみます。
例：cycleあり
| 頂点 | 隣接する頂点 |
|---|---|
| 0 | 1,2,3 |
| 1 | 0,3 |
| 2 | 0 |
| 3 | 0,1 |
g := undirected.NewGraph(4) g.AddEdge(0, 1) g.AddEdge(0, 2) g.AddEdge(0, 3) g.AddEdge(1, 3) fmt.Println(g.ExistsCycle()) // true
例：cycleなし
| 頂点 | 隣接する頂点 |
|---|---|
| 0 | 1,2,3 |
| 1 | 0 |
| 2 | 0 |
| 3 | 0 |
g := undirected.NewGraph(4) g.AddEdge(0, 1) g.AddEdge(0, 2) g.AddEdge(0, 3) fmt.Println(g.ExistsCycle()) // false
