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

Ubuntu 16.04 で pystan を動かす

MCMC サンプラー Stan を Python から呼び出すためのライブラリ pystan を使ってみようとしたら ABI 問題のせいでちょっと嵌ったのでここにメモしておく。

Anaconda3-4.3.0-Linux-x86_64 をインストールした。 そして pystan を pip でインストールした。

pip install pystan

この状態で pystan を使ってみたところ、モデルをコンパイルするところで以下のようなエラーが出た。

>>> stanmodel = StanModel(file='model/model5-3.stan')
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-5-4435d7d1dfc2> in <module>()
----> 1 stanmodel = StanModel(file='model/model5-3.stan')
      2 stanmodel

/home/nojima/anaconda3/lib/python3.6/site-packages/pystan/model.py in __init__(self, file, charset, model_name, model_code, stanc_ret, boost_lib, eigen_lib, verbose, obfuscate_model_name, extra_compile_args)
    313                 os.dup2(orig_stderr, sys.stderr.fileno())
    314 
--> 315         self.module = load_module(self.module_name, lib_dir)
    316         self.module_filename = os.path.basename(self.module.__file__)
    317         # once the module is in memory, we no longer need the file on disk

/home/nojima/anaconda3/lib/python3.6/site-packages/pystan/model.py in load_module(module_name, module_path)
     48         pyximport.install()
     49         sys.path.append(module_path)
---> 50         return __import__(module_name)
     51     else:
     52         import imp

ImportError: /tmp/tmppaa8t0sa/stanfit4anon_model_d6577da659c87ba489087107d1a725f1_1731976423115490565.cpython-36m-x86_64-linux-gnu.so: undefined symbol: _ZTVNSt7__cxx1118basic_stringstreamIcSt11char_traitsIcESaIcEEE

これは、最近 libstdc++ の ABI の変更があり、Ubuntu 16.04 デフォルトの gcc に同梱されている libstdc++ は新しい ABI のものだが、Anaconda に同梱されているライブラリは古い ABI を使っており、うまくリンクできないのが理由っぽい。

ということで、Anaconda が利用しているバージョンである gcc-4.8 をインストールする。 幸いなことに Ubuntu 16.04 には gcc-4.8 パッケージが存在しているため、それを apt-get するだけでインストールできる。

sudo apt-get install gcc-4.8 g++-4.8

この方法でインストールした gccgcc-4.8 という名前で参照できる。gcc コマンドは依然として 5.4 であることに注意。

次に、Cython が gcc-4.8コンパイルに使うようにしなければならない。このためには CC 環境変数gcc-4.8 を指定すればよいらしい。

するとうまくコンパイルできた。

In [1]: from pystan import StanModel

In [2]: import os

In [3]: os.environ['CC'] = 'gcc-4.8'

In [4]: stanmodel = StanModel(file='model/model5-3.stan')
INFO:pystan:COMPILING THE C++ CODE FOR MODEL anon_model_d6577da659c87ba489087107d1a725f1 NOW.

In [5]:

記念にトレースプロットを貼っておく。

f:id:nojima718:20170304173332p:plain

明日使えない Linux の capabilities の話

(この記事は KMC アドベントカレンダー 2016 の3日目の記事です)

はじめに

みなさん以下のようなことで困ったことはないでしょうか?

ポート80を listen したいけど特権ポートなので、一般ユーザの権限で動くデーモンでは bind できない。

1024未満のポートは特権ポートと呼ばれ、一般ユーザの権限では bind することはできません。 この問題の解決策を考えてみます。

(なお、長々と説明を書いていますが、結論だけ知りたい人は一番下だけ読んで下さい)

root で起動

まず、root であれば特権ポートを自由に bind できるので、root で対象デーモンを起動すれば、特権ポートを bind できます。 しかし、デーモンを root として動作させるのは一般にリスクが大きいです。 もしそのデーモンに脆弱性があった場合、root 権限を悪用される可能性があるわけです。

したがって、このやり方は却下です。

プロセス分割

プロセスを分割することでこの問題に対処する場合もあります。 nginx は、まず root として起動し、特権ポートを bind します。 そして、子プロセスを fork し、それらを一般ユーザとして実行します。 この際に、listening socket を open したままの状態にしておくことで、子プロセスでもその socket を利用することができます。

しかし、プロセス分割は結構大掛かりです。 Java や Go みたいにランタイムの都合上 fork できない場合もあります。 できればプログラム本体には手を入れないで対処できる方法が欲しいわけです。

capability

今までの話をまとめると

  • root は使いたくないけど
  • 特権ポートを bind したい

ということになります。 今回は Linux の capabilities という機能を用いてこれを実現していきます。

capabilities とは、root が持っている特権をいくつかのグループに分割し、それぞれを独立に enable, disable できるようにしたものです。

capabilities には例えば以下のようなものがあります。

  • CAP_DAC_OVERRIDE
  • CAP_DAC_READ_SEARCH
  • CAP_KILL
    • シグナルを送るときの権限チェックをバイパスする。
  • CAP_NET_BIND_SERVICE
    • 特権ポートにソケットをバインドできる。
  • CAP_SYS_TIME
    • システムの時刻を設定できる。

他にもいっぱい capability はあるので、興味のある人は man capabilities してみましょう。 今回の用途では CAP_NET_BIND_SERVICE を利用すればよさそうです。

File capabilities

プロセスに capabilities を持たせるひとつの方法として、実行ファイルに対して capabilities を設定する方法があります。 この方法を使うと、そのファイルを 誰が実行しても 指定した capabilities を持ってプロセスが起動するようになります。

ここでは例として、パーミッションを無視して任意のファイルを見れる超脆弱 cat を作ってみます。

# まず /bin/cat を自分用にコピー
$ cp /bin/cat ./mycat

# CAP_DAC_READ_SEARCH を付与する
$ sudo setcap cap_dac_read_search=eip ./mycat

# 確認
$ getcap ./mycat
mycat = cap_dac_read_search+eip

# まず普通の cat で /etc/shadow を見ようとしてみる (当然見れない)
$ cat /etc/shadow
cat: /etc/shadow: Permission denied

# 次に mycat で /etc/shadow を表示!!
$ ./mycat /etc/shadow
root:!:17042:0:99999:7:::
daemon:*:17001:0:99999:7:::
bin:*:17001:0:99999:7:::
...

このように catCAP_DAC_READ_SEARCH を付与することでパーミッションを無視して任意のファイルを表示できるようになりました。

sudo setcap cap_dac_read_search=eip ./mycatmycat に file capabilities を付加している部分です。 eip は立てるフラグの種類をしていしています、と言ってもこの時点では意味不明だと思いますが説明すると長くなるので省略します。

さて、冒頭の問題に戻りましょう。

特権ポートを bind する権限を与えたいので、CAP_NET_BIND_SERVICEsetcap を使って対象サービスの実行ファイルに付与すれば良さそうです。

しかし、この方法には問題があります。

file capabilities を使った方法では 誰が実行しても その特権を持ってしまいます。 一般ユーザは通常何の特権の持っていないので、一般ユーザにとっては setcap されたファイルを実行すると特権が増えることになります。 一般に、特権が増えるような系を作ってしまうと、脆弱性のリスクが増えるので、できるだけ避けたいです。

ということで、file capabilities を使わずに、デーモンに CAP_NET_BIND_SERVICE を付与する方法を考えてみます。

Ambient capabilities

ここまでをまとめると、

  • root として動いている親プロセス(今回の場合は init)が存在し、
  • この親プロセスから一部の capabilities (今回の場合は CAP_NET_BIND_SERVICE)だけを継承して、非rootユーザの子プロセスを spawn したい。
  • File capabilities は利用しない。

という要件になります。

実は、最近まで capabilities の継承ルールがクソなせいで、file capabilities を使わないと非rootユーザに capabilities を付与することはできませんでした(多分)。 しかし、Linux 4.3 で Ambient capabilities という機能が追加され、これが簡単にできるようになりました。

Ambient capabilities の説明に行く前に、簡単にプロセスの capabilities を説明します。

各プロセス(厳密にはスレッド)は、Permitted, Effective, Inheritable の3つのフラグセットを持っています。

  • Permitted, Effective, Inheritable はそれぞれ capability の集合を表すフラグセットです。
  • Effectiveカーネルによってパーミッションチェックをされるときに使われる capability の集合を表します。
  • PermittedEffectiveInheritable の superset を表します。Permitted に含まれていない capability を EffectiveInheritable に加えることはできません。

そして、Inheritableexecve(2) で他の実行ファイルを起動するときに継承される capability の集合を表し……ていたら何も問題なかったのですが、Inheritable に含まれる capabilities は条件が揃わないと子プロセスの PermittedEffective に継承されません。 特に、今回のように「非rootユーザ」で「file capabilitiesが設定されていないファイルを実行」する場合、PermittedEffective は常に空になります。

そこで、ambient capabilities を利用します。

ambient capabilities とは、簡単に言うと「子プロセスに継承される capabilities」を表すフラグセットです。 より厳密に言うと、これから実行するファイルに setuid ビットや setgid ビットがセットされておらず、かつ file capabilities も設定されていない場合、ambient capabilities が子プロセスに継承されます。

つまり、子プロセスに継承したい capability があるときは、ambient capabilities にそれをセットしてから exec すればいいわけです。

どうして最近まで存在しなかったのか疑問に思うぐらい、シンプルで自然な機能ですね。

systemd

以上より、冒頭の問題を解決するためには、「init が対象のデーモンを起動するときに ambient capabilities に CAP_NET_BIND_SERVICE を加えておけばよい」ということになります。

systemd はまさにその機能を持っているので、以下の指定をユニットファイルに書くことで簡単に CAP_NET_BIND_SERVICE を持った状態でデーモンを起動することができます。

AmbientCapabilities=CAP_NET_BIND_SERVICE

おわりに

一方ロシアは8080を使った。

Protocol Buffers が本当に遅いのか実際に確かめてみた

C++

Protocol Buffers で検索すると Protocol Buffersは遅い という MessagePack 作者による2008年の記事が未だに上位に来る。 一方で、Protocol Buffersは遅いのか という反論記事も見つかる。 一体遅いのか速いのかどっちなんだ!!ということで、ベンチマークを取ってみた。

2016年8月現在では、Protocol Buffer の最新バージョンは 3.0.0 であり、MessagePack の C++ バインディングの最新バージョンは 2.0.0 なので、これらのバージョンを使ってベンチマークを取ることにした。

ベンチマーク

元の記事を踏襲して、以下の4つのメッセージを使ってベンチマークを行った。

  • Test1: 2つの符号無し整数
  • Test2: 2つの符号付き整数
  • Test3: 8KBのバイト列
  • Test4: Test1 + Test2 + Test3

Test1 と Test2 は 223 個、Test3 と Test4 は 216 個のメッセージをシリアライズして所要時間を計測し、再びそれをデシリアライズして所要時間を計測した。 外乱の影響を抑えるため、それぞれのワークロードを10回ずつ実行して所要時間の最小値を最終結果とした。

環境:

Test1: 2つの符号無し整数

Serialize Deserialize Size
Protobuf 107 msec 145 msec 32 MB
MessagePack 100 msec 1929 msec 24 MB

シリアライズにかかる時間はほとんど同じだったが、MessagePack のデシリアライズが Protobuf の10倍以上遅い。

Test2: 2つの符号付き整数

Serialize Deserialize Size
Protobuf 112 msec 147 msec 32 MB
MessagePack 102 msec 1954 msec 24 MB

Test1 とほぼ同じ結果になった。 上で挙げた記事では Protobuf の符号付き整数のシリアライズ後のサイズが非常に大きいと書いてあるが、sint を使えば MessagePack と同じサイズになる。 (Protobuf と MessagePack のサイズ差はタグの有無によるもの)

Test3: 8KBのバイト列

Serialize Deserialize Size
Protobuf 162 msec 42 msec 512 MB
MessagePack 121 msec 79 msec 512 MB

バイト列のシリアライズは MessagePack の方が速かった。逆にデシリアライズは Protobuf の方が速い。

Test4: Test1 + Test2 + Test3

Serialize Deserialize Size
Protobuf 165 msec 66 msec 513 MB
MessagePack 123 msec 83 msec 513 MB

Test3 と同じくシリアライズは MessagePack の方が速く、デシリアライズは Protobuf の方が速いという結果になった。

考察

ベンチマークの結果から、バイト列のシリアライズは MessagePack の方が速いが、デシリアライズや整数のシリアライズは Protobuf の方が速いことがわかった。 したがって、2016年の現在においては Protobuf は別に遅くないと思ってよさそう。

ベンチマークプログラム

https://gist.github.com/nojima/005cf04bfa35a1fb971adc43b54abbef

protocol buffer 3 をビルドしてインストール

C++

最近 version 3 が出た protobuf を試しに動かしてみたメモ。

導入手順

Releases から C++アーカイブをダウンロードしてきて展開する。(protobuf-cpp-3.0.0.tar.gz というやつ)

展開後のディレクトリに cd して、以下の手順でビルドする。

./configure
make -j $(nproc)

後は、sudo make install && sudo ldconfig すればインストールできるが、個人的に野良インストールはしたくないので、deb パッケージを作ることにする。別に deb を作りたくない人はこの手順は無視してOK。

# ./deb に make install する
mkdir deb
make install DESTDIR=$(pwd)/deb

mkdir ./deb/DEBIAN

# control ファイルを書く
cat > ./deb/DEBIAN/control <<EOF
Package: nojima-protobuf
Version: 3.0.0-1
Maintainer: Nobody <nobody@example.com>
Architecture: amd64
Description: protocol buffer
EOF

# postinst スクリプトを書く (ldconfig するだけ)
cat > ./deb/DEBIAN/postinst <<EOF
#!/bin/sh -e
ldconfig
EOF
chmod +x ./deb/DEBIAN/postinst

# deb パッケージ化する
fakeroot dpkg-deb --build -Z gzip ./deb ./

# できた deb パッケージをインストールする
sudo dpkg -i ./nojima-protobuf_3.0.0-1_amd64.deb

試しに動かしてみる

以下の内容を person.proto という名前で保存する。

syntax = "proto3";

message Person {
    string name = 1;
    int32 id = 2;
    string email = 3;
}

protocコンパイルして C++ソースコードを生成する。

protoc --cpp_out=./ person.proto

すると person.pb.hperson.pb.cc というファイルができる。

これを使って person を encode するコードを書いてみる。 以下の内容を encode_person.cc という名前で保存する。

#include <cstdlib>
#include <fstream>
#include <iostream>
#include "person.pb.h"

int main(int argc, char** argv) {
    // Verify that the version of the library that we linked against is
    // compatible with the version of the headers we compiled against.
    GOOGLE_PROTOBUF_VERIFY_VERSION;

    if (argc != 2) {
        std::cerr << "Usage: encode_person FILE\n";
        std::exit(1);
    }

    Person person;
    person.set_name("Yusuke Nojima");
    person.set_id(42);
    person.set_email("nojima@example.com");

    std::fstream output(argv[1], std::ios::out|std::ios::trunc|std::ios::binary);
    if (!output) {
        std::cerr << "ERROR: failed to open file: " << argv[1] << "\n";
        std::exit(1);
    }
    if (!person.SerializeToOstream(&output)) {
        std::cerr << "ERROR: failed to serialize person.\n";
        std::exit(1);
    }

    return 0;
}

そしてコンパイルして実行。

g++ -Wall -o encode_person encode_person.cc person.pb.cc -l protobuf
./encode_person person01

すると person01 というファイルにそれっぽい何かが出力される。

$ xxd person01
00000000: 0a0d 5975 7375 6b65 204e 6f6a 696d 6110  ..Yusuke Nojima.
00000010: 2a1a 126e 6f6a 696d 6140 6578 616d 706c  *..nojima@exampl
00000020: 652e 636f 6d                             e.com

次に、シリアライズされた person を decode するものを書いてみる。 以下の内容を decode_person.cc という名前で保存する。

#include <cstdlib>
#include <fstream>
#include <iostream>
#include "person.pb.h"

int main(int argc, char** argv) {
    // Verify that the version of the library that we linked against is
    // compatible with the version of the headers we compiled against.
    GOOGLE_PROTOBUF_VERIFY_VERSION;

    if (argc != 2) {
        std::cerr << "Usage: decode_person FILE\n";
        std::exit(1);
    }

    std::fstream input(argv[1], std::ios::in|std::ios::binary);
    if (!input) {
        std::cerr << "ERROR: failed to open file: " << argv[1] << "\n";
        std::exit(1);
    }

    Person person;
    if (!person.ParseFromIstream(&input)) {
        std::cerr << "ERROR: failed to parse person.\n";
        std::exit(1);
    }

    std::cout << "name = " << person.name() << "\n";
    std::cout << "id = " << person.id() << "\n";
    std::cout << "email = " << person.email() << "\n";

    return 0;
}

そしてコンパイルして実行。

$ g++ -Wall -o decode_person decode_person.cc person.pb.cc -l protobuf
$ ./decode_person person01
name = Yusuke Nojima
id = 42
email = nojima@example.com

読めた!!

TODO

ベンチマーク取りたい。

[追記] ベンチマーク取った → Protocol Buffers が本当に遅いのか実際に確かめてみた

ICFPC 2016 に参加しました (チーム: モダン焼き フジ)

ICFP Programming Contest にcosさん、qwertyさん、seikichiさんとチーム名「モダン焼き フジ」で参加しました。 チーム名は大学生のころによく行ったモダン焼き屋さんの名前から取りました。

最終結果はまだ公開されていないけど、Leaderboard が凍結された時点では13位でした。

レポジトリ: https://github.com/seikichi/icfpc2016

0日目

去年のICFPCでは、メンバーの環境が Ubuntu, Mac, Cygwin とバラバラだったため、環境ごとに微妙に使えるコンパイラオプションとかライブラリとかが異なって非常に面倒だったので、今回は環境をそろえようということになった。 ということで Ubuntu 16.04 をまずセットアップ。

また、去年は CI 環境をコンテストが始まってから用意していたけど、時間の無駄なので今年は事前に用意することにした。 ということで seikichiさんが Jenkins をセットアップしてくれた。 CI サーバは Google Compute Engine の 1CPU インスタンスを利用した。

Makefile もある程度作りこんだものをこの時点で書いておいた。

1日目

全員で問題文を読む。 大雑把に言うと、折り紙のシルエットとスケルトンが与えられるので、どのように折ったらその形になるのかを答えよという問題だった。 個人的に苦手意識の強い平面幾何の問題であり、さらにどうやって探索したらいいのか全く見当がつかない。 これまで参加したICFPCの中で最大の絶望感を味わった。

f:id:nojima718:20160811215546p:plain

とりあえず問題の可視化とスコアリングができないと話にならないので、自分とseikichiさんがビジュアライザを、cosさんとqwertyさんがスコア計算プログラムを作ることになった。

ビジュアライザだけであれば Python とか Ruby とかで書くのが楽そうだが、どうせソルバを作るときに C++ 用の入力関数が必要になるので、コードの再利用性を考えてビジュアライザも C++ で書くことにした。 ビジュアライザを作る過程で、問題のspecにアホみたいに大きい座標が含まれていることがわかった。 したがって多倍長有理数を扱う必要があるので、GMP を使うことにした。 C++用のクラスも用意されていて意外と便利だった。

スコア計算は結構面倒そうだから実装には結構時間がかかりそうだなと思っていたら、cosさんがモンテカルロ法による実装をさっくり作ってしまって凄い(小並感

昼食後、弱くてもいいから何かソルバを作ろうということで、seikichiさんが初期状態から並行移動して重心の位置を合わせるだけのソルバを作った。 一瞬だけランキングで2位になった。

その後、x軸、y軸に並行に何回か折るだけのソルバを作った。 これで単に長方形になるように折っただけの問題は解けるようになった。 また、予め与えておいた角度を全探索することで、既知の角度で回転している長方形は解けるようになった。 問題の制約として、全ての座標が有理数でないといけないという制約があるため、みんな似通った角度で回転させるので、この(頭の悪い)方法でもそこそこ正解したりもした。 また、長方形を適当にスケーリングしてみて resemblance を稼ぐみたいなこともやった。 (この時点では、このコンテストにおいては厳密解のみが正義で近似解に人権はないことに気付いていなかった)

ソルバを動かすのに時間がかかるようになってきたので、GCEで16コアのVMを借りた。

自分が長方形ソルバを作っている間にcosさんがスコア計算を高速化したりライブラリを整備したりしていた。 また、seikichiさんがソルバの性能(解けた問題の数、平均resemblanceなど)を Jenkins でグラフ化してくれるやつを作ったり、問題が増えた時に自動で fetch してきて git レポジトリに push してくれるやつを作ったりしていた。 その裏でqwertyさんが手計算で黙々と提出用の問題を作っていた。

f:id:nojima718:20160811221105p:plain

3時ぐらいに寝た。

2日目

起きたら11時だった。 qwertyさんは早起きして問題を作っていた模様。さすがすぎる。

cosさんが任意の直線で紙をfoldする関数を作った。 これでようやく我々のチームも長方形以外の形が折れるようになった。

fold関数を使って凸包ソルバを作った。 サイズ制限にさえ引っかからなければ、シルエットが凸である形は厳密に折れるようになった。 例えば以下の形が折れるようになった。

f:id:nojima718:20160811215749p:plain

その後、Twitter をしているとモダン焼き フジに言及している人を見つけた。

seikichiさんがすごい勢いで Jenkins のパイプラインを整備していた。 新しい問題が追加されたら自動で既存のソルバ群が実行され最良のスコアが自動で提出される感じのシステムが構築されていた。 その裏でqwertyさんが黙々と提出用の問題を作ったり、兜とか風車とかを手で解いたりしてた。

f:id:nojima718:20160811215647p:plain

12時過ぎぐらいに寝た。

3日目

起きたら11時だった。 qwertyさんは早起きして問題を作っていた模様。さすがすぎる。

そろそろ探索を書かないとまずいということで、全探索ソルバを書いた。 最終形から unfold していく方針は unfold 時にどの面とどの面に別れるかがわからないため難しいと判断して、初期状態から直線を適当に選んで fold していく方針にした。

このとき、スケルトンに現れている直線の集合をそのまま探索の候補として使うことはできない。 なぜなら、ある直線にそって紙を折ると、それまでの折り目がその直線によって反射されてしまうので、最終的なスケルトンに現れない場合があるので。 そこで、深さ0ではスケルトンに現れる直線の集合を候補として使い、深さnでは深さn-1の候補集合に加えて最後に選んだ直線で候補集合を反射したものを候補とするようにした。

この全探索はその見た目どおり計算量が凄まじく、実行してすぐに答えが返ってくるのは max_depth=2 までで、max_depth=3 だと10秒以上待たされるし、max_depth=4 だと返ってこない。

また、前から fold していく方針なので、初期状態で紙がどれぐらい回転及び平行移動しているかを求めないといけない。 とりあえず多くの場合で使えそうなヒューリスティックとして、スケルトンに含まれる直線から「同じ点をどちらかの端点に持ち」「互いに直交しており」「直線が水平になるように回転したときに、あらゆる有理数座標が有理数座標に移る」ような2直線を選んできて、その2直線と初期状態の紙の角を合わせるという方針を取った。

全探索ソルバによって、3手以内で折れる問題は解けるようになったが、実際の問題はもうちょっと手数のかかる問題が多い。 例えば、紙を水平方向に3回折って 1/8 の幅の長方形を作った後に1~2回適当に折るみたいな問題がいっぱいある。 ということで、全探索ソルバに初期値を与えることができるようにした。 これで下図のような既知の初期状態(1/8長方形、1/16長方形、1/2三角形など)からちょっとだけ折ったような問題には答えられるようになった。

f:id:nojima718:20160811220444p:plain

また、既存の問題を平行移動したり回転したりしただけの問題が大量に存在しているが、これもそのうちのひとつを解けば、初期値付き全探索ソルバが max_depth=0 で答えを見つけてくれるようになった。

その後は seikichi さんが問題一覧を見れるウェブサービスを作ったり、既に正解した問題を自動計算の対象から外したり、念のため全問題再提出などを行ったりしていた。 qwerty さんと cos さんは黙々と手で問題を解いていた。 自分は凸包ソルバや全探索ソルバをちょっと弄って何かできないか試していたが、結局そこから5問しか解けなかった。

まとめ

最終的に 3528 問中 1872 問を解くことができた。 1日目の絶望感からすると結構健闘したような気はする。

Kafka の勉強 (2日目)

昨日の記事に引き続き、Kafka の設計についてドキュメント を読んでいく。

4.3 Efficiency

4.2 節ではディスクの効率について議論した。 ディスクの効率以外で、この種のシステムでよくある非効率性は、次の2つだ。

  • 小さな多数の I/O オペレーション
  • 過剰なバイトコピー

小さな I/O オペレーションはサーバ側、クライアント側の両方で発生しうる。

この問題を避けるために、Kafka のプロトコルは「メッセージセット」というメッセージをグループ化するための概念を持つ。 これにより、ネットワークのラウンドトリップに伴うオーバーヘッドを償却できる。 また、サーバは複数のメッセージを一度にログファイルに追記でき、consumer は連続する多数のメッセージを一度に取得できる。 このシンプルな最適化により、速度が10倍になる。

もう一つの非効率性はバイトコピーである。バイトコピーはメッセージの量が少ないうちは問題にならないが、負荷が高まってくると非効率性が顕在化する。これを解消するために、Kafka は producer, broker, consumer で共通のバイナリメッセージフォーマットを使用する。 したがって、この三者の間ではデータチャンクを修正なしで転送できる。

broker が保持するメッセージログはそれ自体単なるファイルのディレクトリで、各ファイルはメッセージセットの列を追記していったものである。 メッセージセットのフォーマットは producer や consumer が使うものと同じフォーマットを利用する。 共通のフォーマットをディスク上のフォーマットとしても使うことで、ログチャンクのネットワーク転送を最適化することができる。 最近の Unix にはページキャッシュからソケットへの極めて高度に最適化された転送の仕組みが用意されている。 Linux では sendfile(2) システムコールがそれである。

sendfile について理解するために、データをファイルからソケットに転送する一般的な方法について考える。

  1. OS がディスクからデータを読んでカーネル空間のページキャッシュに入れる
  2. アプリケーションはカーネル空間からデータを読んでユーザ空間のバッファに入れる。
  3. アプリケーションはカーネル空間に存在するソケットバッファにそのデータを書く。
  4. OS はソケットバッファのデータを NIC のバッファに書く。

これは明らかに非効率で、4回のコピーが行われている。 sendfile を利用すれば、ユーザ空間へのコピーをすることなしにページキャッシュから直接ネットワークにデータを送ることができる。

所感

sendfile 便利(小並感

ゼロコピーを達成するために producer, broker, consumer の間でバイナリフォーマットを揃えるのは力強い感じで好感がもてる。 Kafka のレイヤーで一切メッセージをいじれなくなるので、相当強い意思がないとできない最適化だと思った。

Kafka の通信を TLS 化する仕組みとかあるけど、sendfile にこだわるなら平文じゃないと行けないのかなぁ。

Kafka の勉強 (1日目)

Kafka のドキュメント を読みながらわかったことをメモしていく。

設計に興味があるので 4. Design から読む。

4.1 Motivation

以下のような性質を持つデータハンドリングプラットフォームが欲しい。

  • 高いスループット
  • 低いレイテンシ
  • partitioned, distributed, real-time processing
  • fault-tolerance

4.2 Persistence

Don't fear the filesystem

Kafka はメッセージを保存するためにファイルシステムをヘビィに使っている。 多くの人が「ディスクは遅い」と思っているが、適切にディスク上の構造を設計すればネットワークと同じぐらい速くできる。 実際、6台の 7200rpm SATA からなる RAID-5 アレイに対するシーケンシャル書き込み速度は 600MB/sec ぐらいになる。

また、最近の OS はメインメモリをディスクキャッシュに積極的に利用するようになってきている。 モダンな OS であれば、空きメモリ全てをディスクキャッシュとして利用できる。 アプリケーションがもし独自にキャッシュ機構を持つならば、(Direct I/O などでファイルキャッシュを迂回しない限り) 2重にキャッシュを保持することになってしまう。

さらに、Java アプリケーションの場合、

  • Java のオブジェクトのメモリオーバーヘッドはとても大きく、データサイズは2倍以上になる。
  • Javaガーベジコレクションはヒープ内のデータが増えるにつれて遅くなっていく。

という問題もある。

ゆえに、ファイルシステムとページキャッシュを利用する戦略は、インメモリキャッシュを利用する戦略に対して優っている。

さらに、以下のような利点もある。

  • ページキャッシュはサービスが再起動しても消えない。一方、インメモリキャッシュは消えるので、ファイルから再構築するか、完全に空の状態からスタートする必要がある。
  • キャッシュとファイルシステムの間の一貫性をより簡単に担保できる。

したがって、「データをメモリにできるだけためて、空きメモリがなくなったらディスクにフラッシュする」のではなく、「全てのデータを受け取ったら直ちに fsync なしでファイルシステムに書き込む」という設計にした。fsync をしない書き込みは、実質的にはカーネルのページキャッシュへの転送を意味する。

所感

最初 Kafka がインメモリキャッシュを使わずにファイルキャッシュを利用する設計になっているということを聞いたときは、そのほうが実装が楽なのかなぁという程度に思っていたけど、実はインメモリキャッシュよりもファイルキャッシュのほうが優れているという考察の下でこの設計を行ったと知って驚いた。 確かに、ネットワークと同程度のスループットが出ればボトルネックにはならないわけだから、RAID で束ねれば 10Gbps ぐらいのネットワークならば戦えると。ただし、シーケンシャルアクセスが前提となっているので、topic 数とか partition 数が増えてくると(ランダムアクセスに近づくので)辛そう。

あと、fsync しない設計なので、突然の電源断とかがあると直近のメッセージは失われることになる。これは分散しているから別のノードから取ってくればリカバーできるよということだろうか。落雷でデータセンターごと停電とかしたら嫌だな…。UPS に祈りをささげておかないと。