読者です 読者をやめる 読者になる 読者になる

FeliCa/Suicaについて調べた

SuicaFeliCa)がiPhone7とApple Watch series 2に搭載されることになったので、この機会にいろいろ調べてみた。まだ、憶測の域をこえないところはある。

Sony Japan | FeliCa | FeliCaとは | FeliCaって何?

How to protect from fraud?

  • 中央サーバでトランザクションを一元管理するしかないが、Suicaのような高速な応答性を求められるアプリケーションで、それをどのように実現するか?
  • 改札機器端末 → 駅 → 中央サーバ の階層型分散システム
    • 各階層でトランザクションのキャッシュを持つことで、中央サーバが応答不能になっても即座にサービス停止とはならない
      → 改札機器端末は各アカウントの3日分のトランザクションを蓄えられる容量があるらしい
    • 上階層へのトランザクションの更新処理は、キューに溜める非同期型になっているため、入場時の改札機器端末の応答速度は、カードと改札機器端末の間の処理にかかる時間に縮められる
    • 改札端末には各駅までの運賃がキャッシュされており、運賃計算時に即座に反応できるようになっている
    • 出場時の改札機器端末の応答速度を速めるため、入場時にある程度前もって計算してカードに保存しておく(e.g. 入場駅から定期区間の始めまでの運賃)

How to avoid data break?

  • FelicaFeliCa OS)はファイルシステム上に更新中のデータを二面持ちしているため、更新処理が完了しなかった場合(更新処理中に物理的にNFCの範囲外に離れてしまった場合)でも、元データに復旧する事ができる

  • カード側と改札機器端末側(リーダ/ライタ側)でデータの不整合が発生した場合(カード側で更新処理が完了したが改札機器端末側にそれを伝えられなかった場合)でも、中央サーバ側で不整合の状態を記録しておき、次回アクセス時にカード側の整合状態を中央サーバに伝達して不整合を修復する

http://www.sice.jp/ia-j/papers/jitk6-20050722-1305.pdf
http://www.sice.jp/ia-j/papers/jitk6-20050722-1305.pdf

Linuxのブートシーケンスの基礎まとめ

ファームウェアBIOS or UEFI)が

  • ハードウェアをスキャンする
  • [BIOSの場合] プライマリHDDのMBR(先頭のセクタ(512バイト))を見る(MBRの最後の2バイトは0x55 0xaa(MBR signature )になっている)
  • [UEFIの場合] プライマリHDDのGPTヘッダ(LBA1 or 最終セクタ)を見る

https://upload.wikimedia.org/wikipedia/ja/c/cc/GUID_Partition_Table.png

GPTとMBRはどのように違うのか? - かーねる・う゛いえむにっき

BIOS/UEFI/MBR/GPT

  • MBRでは232≒2.2TBまでのディスクしか扱えない
  • GPTでは264≒8.5ZBまでのディスクを扱うことができる
  • BIOSIntel CPUのリアルモード(16bitモード)でないと起動できないため、1MBまでのメモリしか利用できない
  • UEFIはプロセッサ非依存のため、32bitプロセッサなら32bit命令が、64bitプロセッサなら64bit命令が使えるため、潤沢なメモリを利用できる
  • BIOSはGPTに対応していないため、GPTに対応したUEFIを使う

ブートローダ

initrd/initramfs

  • initrdはブロックデバイスをgzip圧縮したもの
  • initramfsはファイルシステムをcpioでアーカイブしたものをgzip圧縮したもの
  • initrdにカーネルモジュールを追加しようとするとマウントが必要(etc.)
     → 扱いにくいのでObsolete
     → 現在では一般的にinitramfsを使う

vmlinuz/vmlinux/bzImage/zImage

  • bootパーティションには、vmlinuzと呼ばれる、カーネルイメージを含むファイルが置かれている
  • vmlinuzは、カーネルイメージ(vmlinux)をgzip圧縮したものと、圧縮されたカーネルイメージを伸張し展開するコードをそれ自身に伴った形式ものである
  • このファイル形式をbzImageという
  • なお、zImageでは512KB以下のイメージしか扱えない

uImage

  • U-Boot用のカーネルイメージのファイル形式
  • U-Bootは、主に組み込み用途で使われるブートローダで、ネットワークブート(PXEクライアント)の機能を持つなど、高機能版のブートローダGRUBでネットワークブートをする場合は、おそらくNIC側のPXEクライアント機能を使う必要がある)

GRUBコマンド

  • GRUBプロンプトからブートする例
grub> set root=(hd0,1)
grub> linux /boot/vmlinuz-3.13.0-29-generic root=/dev/sda1
grub> initrd /boot/initrd.img-3.13.0-29-generic
grub> boot

Linux 上の GRUB 2 がブートできなくなったときの対処方法

U-Bootコマンド




カーネル

  • initrd/initramfsを展開して、初期ルートファイルシステムを読み書き可能な形式でマウントする (この初期ルートファイルシステムは「ミニ」ルートファイルシステムとも呼ばれる)
  • [initrdの場合] /linuxrcを、一時的なinitプロセスとして起動する
  • [initramfsの場合] /initを、一時的なinitプロセスとして起動する
  • 初期ルートファイルシステムに置かれているカーネルモジュールをロードして、様々なファイルシステムでフォーマットされているパーティションを認識する
  • 初期ルートファイルシステムからルートファイルシステムへマウントポイントを移す
  • [initrdの場合] 一時的なinitプロセスの終了後に、/sbin/initを実行して、initプロセス(PID=0)を起動する
  • [initramfsの場合] /initが、exec /sbin/initを実行して、initプロセス(PID=0)を起動する(execは現在のプロセスを別のプロセスで置き換える)

Systemd

  • /sbin/initは、現在systemdに置き換えが進んでおり、単に/sbin/initがsystemdへのシンボリックリンクになっているLinuxディストリビューションも存在する
  • systemdは、サービスの起動を並列に実行することによる起動処理の高速化、cronやxinetd(リソース効率化のため通信を検出した際にそのポートに対応するプロセスを起動するスーパーデーモン)に対応する機能の集約、cgroupによるリソース制御を用いたプロセスの優先度管理、などを行う

initプロセスが

  • /etc/inittabに書かれている通りrunlevelを設定し、該当する/etc/rc.d/rcXを実行する
  • スクリプトを実行する際は、forkによってinitプロセスがそのスクリプトを実行するプロセスの親プロセスとなる
  • initプロセスが、/etc/fstabに書かれている通り各パーティションをマウントする

fstab - ArchWiki

runlevel

  • runlevelの定義はOSに依存するが、0:停止、1:シングルユーザ、2:マルチユーザ(ネットワーク無、Xディスプレイ無)、3:マルチユーザ(ネットワーク有、Xディスプレイ無)、5:マルチユーザ(ネットワーク有、Xディスプレイ有)、6:リブート、のパターンが多い
  • Sで始まるファイルは起動用スクリプト(S=Start)であり、Kで始まるファイルは停止用スクリプト(K=Kill)になる

...

AVL木の更新状況が見たい

AVL木は平衡二分木の一つで、ノードの追加・削除のたびに木の再構成を行い、検索時の計算時間を最小に抑えるようなデータ構造を維持する。木の再構成を行わない場合、最悪の場合には木の片側のみを使ってしまい検索時にO(n)の時間がかかってしまうが、再構成を行うことにより木を厳密に平衡に保つためO(logn)の時間で検索できる。更新・削除にも時間がかかるが、その分検索の時間を速くすることを目的としている。

実装を進めるにあたって、更新時の回転操作を正しく理解するためにも、木構造そのものを見ることが出来る方が分かり易いだろう、ということで、まず木構造デバッグできるよう実装した。 ノードは双方向の連結リストになっているが、可視化する場合には幅優先探索によって同じ階層のノードを取得し、それをヒープ構造に入れることにした。ある階層の全てのノードがNULLになるまで、あるノードがNULLであっても子ノードの取得を続けるようにしているため、こうしておくと、あるノードの親がNULLかどうかも確認しやすい。見やすさのため、親がNULLの場合は何も出力が行わないようにする。NULLノードは[]で示している。

数字の隣はラベルで、AVL木において重要な役割を持つ。LEFT、EQUAL、RIGHT、はそれぞれ左部分木が深いか、平衡か、右部分木が深いか、が分かるようになっている。

Thanks to :

http://dopal.cs.uec.ac.jp/okamotoy/lect/2005/DSA/avl.pdf

  • 挿入を実施しながら木構造や回転を確認(モバイルだと崩れますが...)
$ java AVLTree
Please input the value for root node. : 8
('q' for quit, 'p' for print, 's' for search.)
Please input. : p
 8E---| 
 []  [] 

Please input. : 3
Please input. : 14
Please input. : p
 8E-------|     
 3E---| 14E---| 
 []  []  []  [] 

Please input. : 2
Please input. : 6
Please input. : p
 8L---------------|             
 3E-------|     14E-------|     
 2E---|  6E---|  []      []     
 []  []  []  []                 

Please input. : 12
Please input. : 15
Please input. : p
 8E---------------|             
 3E-------|     14E-------|     
 2E---|  6E---| 12E---| 15E---| 
 []  []  []  []  []  []  []  [] 

Please input. : 1
Please input. : 4
Please input. : p
 8L-------------------------------|                             
 3E---------------|             14E---------------|             
 2L-------|      6L-------|     12E-------|     15E-------|     
 1E---|  []      4E---|  []      []      []      []      []     
 []  []          []  []                                         

Please input. : 5
Rotate left at 6!
Please input. : p
 8L-------------------------------|                             
 3E---------------|             14E---------------|             
 2L-------|      5E-------|     12E-------|     15E-------|     
 1E---|  []      4E---|  6E---|  []      []      []      []     
 []  []          []  []  []  []                                 

Please input. : 7
Rotate left at 8!
Please input. : p
 5E-------------------------------|                             
 3L---------------|              8E---------------|             
 2L-------|      4E-------|      6R-------|     14E-------|     
 1E---|  []      []      []      []      7E---| 12E---| 15E---| 
 []  []                                  []  []  []  []  []  [] 

Please input. : 0
Rotate left at 2!
Please input. : p
 5E-------------------------------|                             
 3L---------------|              8E---------------|             
 1E-------|      4E-------|      6R-------|     14E-------|     
 0E---|  2E---|  []      []      []      7E---| 12E---| 15E---| 
 []  []  []  []                          []  []  []  []  []  [] 

Please input. : 20
Please input. : p
 5R---------------------------------------------------------------|                                                             
 3L-------------------------------|                              8R-------------------------------|                             
 1E---------------|              4E---------------|              6R---------------|             14R---------------|             
 0E-------|      2E-------|      []              []              []              7E-------|     12E-------|     15R-------|     
 []      []      []      []                                                      []      []      []      []      []     20E---| 
                                                                                                                         []  [] 

Please input. : 22
Rotate right at 15!
Please input. : p
 5R---------------------------------------------------------------|                                                             
 3L-------------------------------|                              8R-------------------------------|                             
 1E---------------|              4E---------------|              6R---------------|             14R---------------|             
 0E-------|      2E-------|      []              []              []              7E-------|     12E-------|     20E-------|     
 []      []      []      []                                                      []      []      []      []     15E---| 22E---| 
                                                                                                                 []  []  []  [] 

Please input. : q
$ 
  • のべ16ノードを挿入した木を100回作成(検索の確認は無し(0回))

f:id:nishidy:20160905232657g:plain

  • のべ10,000,000ノードを挿入した木を作成し、10回検索を実施して各時間を測定
$ java AVLTree 10000000 10
Found node 7443458 in 11830 ns.
Found node 1542990 in 7199 ns.
Found node 9059491 in 5348 ns.
Found node 2189518 in 5501 ns.
Found node 5773482 in 3459 ns.
Found node 7512803 in 4832 ns.
Found node 7103487 in 6813 ns.
Found node 5575799 in 5398 ns.
Found node 5292306 in 84161 ns.
Found node 8909173 in 20869 ns.
$ 

実装はこちら。削除は複雑なため未実装です。

AVLTree with debugging the tree in Java · GitHub

Sortアルゴリズムの消費メモリについて(続)

ソートにおいて、ソート対象の配列に対するポインタを操作すれば、各関数の中でソート対象の配列が持つ要素に対するメモリを確保する必要が無くなる。もし、ソート対象の配列の要素の型がポインタよりも小さいサイズであれば、その要素に対するメモリを確保した方が良いが、例えばソート対象の配列の要素が構造体である場合は、その要素に対するメモリ量が大きいので、ダブルポインタでポインタをソート対象として扱うべきである。ポインタのサイズはプラットフォームに依存するので、sizeof()で確認する。

ダブルポインタを用いてポインタに対してメモリを確保するソート(sort())と、データの型に対してメモリを確保するソート(_sort())、それからライブラリのソート(qsort())、を比較してみた。ソート処理全体で確保した総メモリ量と、mallocを呼んだ回数をカウントしている。なお、構造体のソート対象のキー(age)以外は、参照もしないので、初期化すらしていない。ダブルポインタを用いる方がメモリ量が小さいし速い。ただ、やはりライブラリのソートの方がかなり速い。

なお、前回のプログラムでQuick sortのmalloc回数が多かったのは、ソート対象の配列数が1になった場合にreturnしていないため。

$ ./structsort 5000000
Size of Data struct : 68
Size of a pointer : 8
(Size of short: 2)
(Size of int: 4)
(Size of long: 8)

Quick sort (double pointer): 5.22 sec.
1045MB,3385634
Good. Sorted.

Quick sort : 6.48 sec.
8887MB,3385634
Good. Sorted.

Quick sort (library function) : 3.20 sec.
Good. Sorted.

実装はこちら Sort function optimized with double pointer · GitHub

いかなる算術演算子も使わずに加算を実現する

という問題を解く。

答えは、ビット演算子をたくみに使って加算を実現する。 つまり、ビット演算子は算術演算子には含まれないので、使っても良い。

具体的には、XORによって各位の加算を実現し、ANDと左シフト演算子によって繰り上げを実現する。 繰り上げがなくなった時点で(ゼロになった時点で)、計算は終了する。

以下のように、デバッグしながら実行してみる。

#include <stdio.h>
#define BITS 32

void bit(int n){
        int i;
        for(i=0;i<BITS;i++)
                printf("%d", (n >> (BITS-1-i)) & 1);
        printf("\n");
}

int bitplus(int a, int b){
        bit(a); bit(b); printf("\n");
        if(b==0)
                return a;
        return bitplus( a^b, (a&b)<<1 );
}

int main(int argc, char* argv[])
{
        int a = atoi(argv[1]);
        int b = atoi(argv[2]);
        bit(a); bit(b); printf("\n");
        printf("Ans = %d\n\n", bitplus( a^b, (a&b)<<1 ));
        return 0;
}
$ ./bitplus 3 5
00000000000000000000000000000011
00000000000000000000000000000101

00000000000000000000000000000110
00000000000000000000000000000010

00000000000000000000000000000100
00000000000000000000000000000100

00000000000000000000000000000000
00000000000000000000000000001000

00000000000000000000000000001000
00000000000000000000000000000000

Ans = 8

$ ./bitplus 65535 65536
00000000000000001111111111111111
00000000000000010000000000000000

00000000000000011111111111111111
00000000000000000000000000000000

Ans = 131071

$ ./bitplus 65535 65535
00000000000000001111111111111111
00000000000000001111111111111111

00000000000000000000000000000000
00000000000000011111111111111110

00000000000000011111111111111110
00000000000000000000000000000000

Ans = 131070

$ python
Python 3.4.3 (default, Oct 24 2015, 14:51:44) 
[GCC 4.2.1 Compatible Apple LLVM 6.1.0 (clang-602.0.53)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> int("10101010",2)
170
>>> int("01010101",2)
85
>>> quit()

$ ./bitplus 170 85
00000000000000000000000010101010
00000000000000000000000001010101

00000000000000000000000011111111
00000000000000000000000000000000

Ans = 255

$ ./bitplus 171 85
00000000000000000000000010101011
00000000000000000000000001010101

00000000000000000000000011111110
00000000000000000000000000000010

00000000000000000000000011111100
00000000000000000000000000000100

00000000000000000000000011111000
00000000000000000000000000001000

00000000000000000000000011110000
00000000000000000000000000010000

00000000000000000000000011100000
00000000000000000000000000100000

00000000000000000000000011000000
00000000000000000000000001000000

00000000000000000000000010000000
00000000000000000000000010000000

00000000000000000000000000000000
00000000000000000000000100000000

00000000000000000000000100000000
00000000000000000000000000000000

Ans = 256

右シフト演算

負の値を右シフトした場合、符号ビットが立っているので、1で埋められる。

...
        int k = -65535;
        bit(k);
        bit(k>>=10);
        bit(k<<=10);
...
11111111111111110000000000000001
11111111111111111111111111000000
11111111111111110000000000000000

なお、シフト対象となる左辺値の型のサイズより大きい値でシフトしようとすると、以下のようにMacApple LLVM version 7.0.2 (clang-700.1.81))ではwarningが出るが実行はできる。

...
        bit(k>>=64);
...
$ gcc bitplus.c 
bitplus.c:87:14: warning: shift count >= width of type [-Wshift-count-overflow]
        bit(k>>=64);
             ^  ~~
1 warning generated.

ただ、結果としての値は、シフト演算を行う前の値になっていた。

11111111111111110000000000000001

Cではこのようなシフト演算は規定外なので、何が起こるかはプラットフォームに依存する。

Goだと、以下の記事の通り、-1になる。

Goでは、nビットシフトは1ビットシフトをn回行ったのと同じ(CやJavaは違う) - Qiita

$ cat bit.go 
package main

import (
    "fmt"
)

func main() {
    var a int32 = -65535
    fmt.Printf("%b\n", a>>64)
}
$ go run bit.go 
-1

浮動小数点数のビット表現

IEEE 754 - Wikipedia

浮動小数点のビット表現を見てみる。float型の変数からアドレスを取得し、それをint型のポインタとしてキャストしてから、その値を取り出す。

#include <stdio.h>
#define BITS 32

void bitf(float f){
        int i;
        int n = *((int *)&f);
        for(i=0;i<BITS;i++)
                printf("%d", (n >> (BITS-1-i)) & 1);
        printf("\n");
}

int main()
{
        bitf(-10.5);
        bitf(10.5);
        return 0;
}
$ ./floatbit 
11000001001010000000000000000000
01000001001010000000000000000000

https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Float_example.svg/590px-Float_example.svg.png

符号部は、負数で1、正数で0。 仮数部と指数部の算出は以下の通り。 算出した指数部には規定通り127のバイアスを加える。

10.5 * 2^0
= 5.25 * 2^1
= 2.625 * 2^2
= 1.3125 * 2^3
= (1+0.3125) * 2^3

0.3125 * 2 = 0.625 (0)
0.625 * 2 = 1.25 (1)
0.25 * 2 = 0.5 (0)
0.5 * 2 = 1.0 (1)

指数部は3+127=130で10000010仮数部は2ビット目と4ビット目が立つので0101、となるので、-10は1_10000010_01010000...となる。

動的計画法とメモ化の実行状況が見たい

N x N のマス上にいくつか穴が開いていて、2マスを使うドミノを置いて、穴以外のマスを埋めることができるか、という問題があるとする。愚直に一つずつ試していくやり方としては、動的計画法が使える。ドミノは2マス使うので、縦に置くか、横に置くか、の選択肢がある。それぞれで処理を再帰呼び出しで分岐して、最終的にマスを埋めることができたかどうか、を判定すればよい。

ただし、これだけだとスケールしない。全く同じ盤面が何度も出てくるのに、毎回調べなければならないからだ。マスを埋めることができなかった、と判断された盤面が再度現れたときには、答えは分かっているのだから、それ以上処理を継続する必要はないはずだ。それを実現するのがメモ化(つまりキャッシュ)。動的計画法は、このようにメモ化と組み合わせて実現される。

Cの実装

メモ化に使うデータ構造をどうするか、つまり、盤面を覚えておく効率的なデータ構造、を考えなければいけない。ここでは、ドミノ(< >^ Vで示される)で埋めたマスが連続する数と、埋まっていないマス(_)が連続する数、を配列として持つことにする。つまり、

< > < >
+ ^ _ +
+ V _ _

という盤面があるとすると、6 3 1 2 になる。穴(+)についてはこだわらなくて良いので、それまでカウントしていた方の一部としてカウントする。今回は、盤面に対する情報はTrueかFalseなので、キャッシュの配列に含まれる場合はTrue(マスを埋めることができなかった)と考えれば良い。

マスを埋めることができた場合には、その盤面を出力している。また実行結果には、キャッシュにヒットした回数も出力している。

f:id:nishidy:20160828125539g:plain

  • 8x8マス。30回連続で別の盤面を実行。

f:id:nishidy:20160828131607g:plain

Javaの実装

上記のようなデータ構造は使いづらい。盤面を覚えておくのであれば、全ての盤面に対して一意のIDを割り当てることができればいいので、そういう用途ではmd5ハッシュ値が使える。JavaのDigestUtils(標準ライブラリでは無い)を使って実装した。注意すべきなのは、ドミノがどの方向で置かれていても同じように扱う必要があるので、盤面をコピーしてドミノの部分を共通のマークに入れ替えてからハッシュを取る必要がある。

f:id:nishidy:20160828132115g:plain

アルゴリズムについて

このような問題に対して動的計画法とメモ化を使うのは、やり方として間違っていないものの、データ範囲が大きくなるにつれて収束が難しくなる。Code Jamで言えば、Smallまではこのやり方で問題無いが、Largeを解くためには、このように愚直に試すやり方ではなく、盤面を俯瞰的に見ることでうまくいくかどうかを検証するアルゴリズムが必要になる。

なんとなく以下のような構造が出てくると、うまくいかないということは分かる...

+ _ +
_ _ _

Kubernetes background and network configuration

Kubernetesとそれに関連するミドルウェア

Kubernetesはdockerなどのコンテナのスケジューリングやロードバランスを担うクラスタリング制御用運用管理ツール。様々なミドルウェアを組み合わせて使うモジュラー型のアーキテクチャになっている。

etcdは分散KVSで、Zookeeperと同じようなもの。コンセンサスアルゴリズムによる合意形成の手段を実装することにより、分散環境におけるKVSのスケーラビリティとリダンダンシーを実現している。 etcdは、Linuxディストリビューションの一つであるCoreOSのアプリケーションとして提供されているが、今回はCentOS上で使用している。

flannelはネットワーク管理用ツールで、VXLANなどのオーバーレイのエンドポイントを作る。etcdとflannelが協調してクラスタ内のネットワークを形成する役目を持つ。

Kubernetesで実際にコンテナを作成するにはkubectl create -f pod.yamlでPodの作成を実行する。PodはKubernetesの概念において一つのノード上に存在するコンテナの集まりを指す。以下は、一つのコンテナのみを作成する最もシンプルなPodの設定ファイル。なお、replica数の指定なども設定ファイルに記述することになる。

# pod.yaml
apiVersion: v1
kind: Pod
metadata:
  name: nginx-pod
spec:
  containers:
    - name: nginx-container
      image: nginx
      ports:
      - containerPort: 80

なお、kubernetes がどのノードにPodを作成するか、はおまかせになるが、下記のように確認することはできる。

[xxx@master ~]$ kubectl describe pods nginx-pod
Name:           nginx-pod
Namespace:      default
Node:           minion2/10.140.0.4
...

ちなみに、yamlの設定ファイルを部分的に管理しておいて、後でマージして一つの大きな設定ファイルを作る、といったことがSpruceというOSSを使うとできるらしく、インフラのコード化を考えると重宝しそう。以下のスライドを参照のこと。

flanneldのコンフィグとして、etcdのURLエンドポイントとキーを指定する。flanneldが管理する、クラスタとして割り当てるネットワークサブネットは、etcdctlコマンドでetcdに登録する。なお、etcdへの登録や参照にはREST APIが提供されているので、curlを使ってPOSTメソッドで行うこともできる。

# /etc/sysconfig/flanneld
FLANNEL_ETCD="http://10.140.0.2:2379"
FLANNEL_ETCD_KEY="/atomic.io/network"```
# /atomic.io/network/config
{
    "Network": "10.20.0.0/16",
    "SubnetLen": 24,
    "Backend": {
        "Type": "vxlan",
        "VNI": 1
    }
}

VXLANにおける宛先解決

enakai00.hatenablog.com

上記の記事で特におもしろいのは、Linuxカーネルが発行するL3MISSというイベントによってアプリケーションにMACアドレス解決を移譲する、L2MISSによってアプリケーションにIPアドレスの取得を移譲する、というところ。 VXLANでは、どのようにUnknown Unicastの宛先VTEPを解決するかは、VTEPの実装に依存しているようだ。etcdのような仕組みを持たない場合は、単にマルチキャストによって全てのVTEPに解決を促すことになるだろう。 これを見ると、もうARPリクエストのようにマルチキャストやブロードキャストでMACアドレスを解決するという手法は時代遅れなのかもしれない。

なお、flannelを使わずにOpen vSwitchを使うこともできる。こちらの方が、OpenFlowのAPIを使って柔軟にネットワークの制御ができるはず。

http://kubernetes.io/docs/admin/ovs-networking/kubernetes.io

VXLANを使わないネットワーク構築方法

techblog.yahoo.co.jp

VXLANはオーバーレイなので、カプセリングのオーバーヘッドにより、データ転送のスループットが犠牲になる。これを避けるために、ピュアなL3ルーティングによってクラスタ内のネットワーク接続性を担保する方法もある。上記の記事は、flannelではなくCalicoを使った、BGPでのIPルーティングによるネットワーク構築方法になる。

クラスタを一つのASとみなしてプライベートAS番号を割り当てて管理している。BGPピアはメッシュで接続する必要があるため、BGPスピーカが増えた際のAS内のIntra BGP (iBGP)でのフルメッシュによる負荷を削減するために、ルートリフレクタを使ってスター型のピアリングを構成している。

おまけの、トラブル事例もおもしろい。サーバの前段に置いたロードバランサーARP応答させるため、サーバに直接届くARP要求には応えない設定にしておいたために、サーバ内のVMからのARP要求にも応えることが出来なかった、という問題のようだ。

Google Compute Engineでの構築

実際にGCE(GKE?)を使って、KubernetesでのPod構築と、VXLANによる疎通確認を行った。詳細な設定については他のソースに譲るが、外部に公開するサービスとしてのIPアドレスには0.0.0.0を使用する、service_account_key_fileを設定する、といった点には注意したい。sudo ss -untplでListenしているポートの確認を行いながら進めた方が良い(sudoを付けないとサービスの名前が取れないので、サービスでgrepをかけることができなくなる)。あるノードのホスト(10.140.0.4)から、別のノードのコンテナ(10.20.4.2)に対してPingを実施している。flannelデバイス(10.20.52.0)が、オーバーレイネットワークのソースアドレスになっている。10.140.0.0/16がアンダーレイ(物理ネットワーク)、10.20.0.0/16がオーバーレイ(仮想ネットワーク)になる。

受信側でtcpdump(-T vxlan)によってVXLANパケットをキャプチャしている。

[xxx@minion2 ~]$ ping 10.20.4.2
PING 10.20.4.2 (10.20.4.2) 56(84) bytes of data.
64 bytes from 10.20.4.2: icmp_seq=1 ttl=63 time=1.53 ms
64 bytes from 10.20.4.2: icmp_seq=2 ttl=63 time=0.365 ms
64 bytes from 10.20.4.2: icmp_seq=3 ttl=63 time=0.332 ms
64 bytes from 10.20.4.2: icmp_seq=4 ttl=63 time=0.347 ms
64 bytes from 10.20.4.2: icmp_seq=5 ttl=63 time=0.357 ms
64 bytes from 10.20.4.2: icmp_seq=6 ttl=63 time=0.373 ms
64 bytes from 10.20.4.2: icmp_seq=7 ttl=63 time=0.450 ms
64 bytes from 10.20.4.2: icmp_seq=8 ttl=63 time=0.336 ms
^C
--- 10.20.4.2 ping statistics ---
8 packets transmitted, 8 received, 0% packet loss, time 7001ms
rtt min/avg/max/mdev = 0.332/0.511/1.533/0.388 ms

[xxx@minion2 ~]$ ip r
default via 10.140.0.1 dev eth0  proto static  metric 100 
10.20.0.0/16 dev flannel.1  proto kernel  scope link  src 10.20.52.0 
10.20.52.0/24 dev docker0  proto kernel  scope link  src 10.20.52.1 
10.140.0.1 dev eth0  proto dhcp  scope link  metric 100 
10.140.0.4 dev eth0  proto kernel  scope link  src 10.140.0.4  metric 100 
169.254.169.254 via 10.140.0.1 dev eth0  proto dhcp  metric 100 
[xxx@minion1 ~]$ sudo tcpdump -i eth0 -T vxlan host 10.140.0.4
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on eth0, link-type EN10MB (Ethernet), capture size 65535 bytes
16:07:19.808846 IP minion2.c.kubernetes-test-141313.internal.52229 > minion1.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1
IP 10.20.52.0 > 10.20.4.2: ICMP echo request, id 1291, seq 1, length 64
16:07:19.808945 IP minion1.c.kubernetes-test-141313.internal.54591 > minion2.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1
IP 10.20.4.2 > 10.20.52.0: ICMP echo reply, id 1291, seq 1, length 64
16:07:20.809721 IP minion2.c.kubernetes-test-141313.internal.52229 > minion1.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1
IP 10.20.52.0 > 10.20.4.2: ICMP echo request, id 1291, seq 2, length 64
16:07:20.809804 IP minion1.c.kubernetes-test-141313.internal.54591 > minion2.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1
IP 10.20.4.2 > 10.20.52.0: ICMP echo reply, id 1291, seq 2, length 64
16:07:21.809474 IP minion2.c.kubernetes-test-141313.internal.52229 > minion1.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1

その他

ロードバランスやフェイルオーバーなども実際にさわってみたい。