高並列性サーバプログラムの実装（サーベイ編）
より多くのクライアントからの同時アクセスを捌くためにサーバプログラムのパフォーマンス改善が必要になってきた。世に言う C10K 問題とかその話に近い。C10K 問題については下記の Web サイトを参考にすると良いが、簡単に言うと「ハードウェアの性能上は問題なくても、あまりにもクライアントの数が多くなるとサーバがパンクすること」である。
この文章は10年以上前に書かれたものであるが、ハードウェアの性能が劇的に向上した現在でもこの問題は考慮する必要がある。解決法（最適な実装方法）に関しては未だ議論が絶えないように見えるというかノウハウになっていて具体的な実装方法はあまり出てきてないように思える。解決策についていろいろ調べて出てくるのはこれらのサイトである。
インターネットサーバでの Pthread と epoll (1)
ネットワークプログラムのI/O戦略 - sdyuki-devel
特に２つめのブログでは I/O 戦略を非常に詳しく解説しているので一読を勧める。このブログでは 1 コネクション 1 スレッド実装に対して「Webサーバーには本当に向いていない」と言及しているが、一方で現実的に 1 コネクション 1 スレッドでも問題ないと評価しているブログも見つけた。評価方法が不明確ではあるが、ハードウェアの性能向上を考えると十分あり得る結論だと思う。ここら辺は自分で計測し、評価をとってみようと思う。
Kazuho@Cybozu Labs: 「サーバ書くなら epoll 使うべき」は、今でも正しいのか
結論としては「ネットワークプログラムのI/O戦略」という記事が勧めている、マルチスレッド・イベント駆動方式 (Wavy 方式) を採用することにする。この実装については下記のブログにて述べられている。
マルチコア時代の高並列性IOアーキテクチャ Wavy - Blog by Sadayuki Furuhashi
ただし今回はなるべくシンプルな実装を心がけるために、タスクキューを利用しない。
epoll におけるレベルトリガーとエッジトリガー
epoll を利用したプログラミングをやっていて「レベルトリガー」と「エッジトリガー」という聞き慣れない単語を目にした。
これらの言葉はどうやら電子工学や制御工学などでよく利用される言葉のようである。調べるとマイコン制御などの記事が多く出てくる。IT 用語辞典 e-Words によると・・・
エッジトリガ
割り込み通知などにおいて、信号がある状態から別の状態へ変化した時点でトリガが引かれる方式。
レベルトリガ（レベルセンス）
信号レベルが変化した瞬間ではなく「信号レベルがある基準より上か下か」という信号の状態に注目してトリガのオン・オフを決める方式。
なるほど・・・なんとなく分かった。
つまりこれらの概念を epoll に適用すると・・・
エッジトリガ
epoll が管理しているディスクリプタのうちどれかが読み書き可能になった「瞬間」に epoll_wait() 関数が帰ってくる。
レベルトリガ
epoll が管理しているディスクリプタから読み書きできる（通常は読みか？）「状態」にあるディスクリプタが存在すれば epoll_wait() 関数が帰ってくる。
言葉で書くとややこしいので実際の実装に落とし込んで考えてみる。
エッジトリガでの epoll_wait 時に管理ディスクリプタが読み書き可能になると、epoll_wait() 関数が帰ってき、読み書き可能になったディスクリプタを取得することができる。この時、読み書き可能になったディスクリプタに対して何もせずに再び epoll_wait() を呼び出すと次のイベント（読み書き可能になるディスクリプタが現れる）まで epoll_wait() は帰ってこない。
一方レベルトリガでの epoll_wait は、ディスクリプタの「状態」によって epoll_wait() が帰るため、上記の様に epoll_wait で上がってきたディスクリプタに対して何もせずに再び epoll_wait をすると、すでに先ほどのディスクリプタは読み書きできる「状態」にあるのですぐに epoll_wait が帰ってくる。
このエッジトリガとレベルトリガの性質を利用して次回は複数スレッドから epoll_wait を呼び出すスレッドプール型のプログラムについて言及する。
tail -f は古い・・・らしい・・・
FUSE デバッグの中で /var/log/system.log を
# tail -f /var/log/system.log
で開きっぱなしにすると便利だと言及したが、つい最近 Facebook である記事が回ってきた。
タイトルは tail -f を使うのをやめよう！というなんとも驚きの内容。
これに関しては日本語のブログ記事も見つかる。日本語に長けている人はこちらを参照すると良いだろう。
「tail -f」を使うのは情弱、情強は「less +F」を使う
どうも「情強」は less +F を利用するらしい。元記事にこんな内容がある。
Simply put, it allows you to switch between navigation and watching mode. We all have been there: You are watching a file with tail -f, and then you need to search for something in this file, or just navigate up and down. Now you need to exit tail (or open a new shell), and ack this file or open it with vim to find what you are looking for. After that, you run tail again to continue watching the file. There's no need to do that when you are using less.
tail -f だと検索したりするときいちいち閉じて vim で開いてとか面倒だろ？とのこと。うむ確かに。今度からは less +F を利用してみよう。
FUSE におけるデバッグ手法 (OSX FUSE編)
OSX FUSE を利用していてデバッグに困った。
今回の実装では FUSE をダウンロードした example というディレクトリに入っている hello.c というプログラムを変更しながら実装をしているのだが、デバッグが難しい。
というのも、main 関数で呼ばれている fuse_main 関数がコールされるとプログラムがデーモン化してしまい、いくらプログラム内で printf なり std::cout なりしても標準出力には何も表示されない。
デーモン化しないように FUSE が提供しているローレベル API を利用してプログラミングするという手もある。これは hello_ll.c として example にプログラムがあるが、そこまでして複雑なことをする必要はないので却下。
うむむ。このままでは得意技である printf デバッグ（笑）が出来ないではないか・・・
無論デバッガ （gdb とか lldb とか）を使えって言うのは分かるんだけれども、どうもうまく動いてくれない・・・とりあえず printf 系だけでも出来れば何とかなるのにな・・・ということで、syslog を利用してデバッグできるように DPRINTF という関数を作成した。
syslog.h でなく標準エラー出力に出したい場合を考慮して #define SYSLOG_ENABLE と定義した場合のみ、syslog 関数を利用しそれ以外は fprintf 関数を利用する仕組みとなっている。
これを利用するとデバッグ情報が /var/log/system.log に出力される。常に system.log を開いたままコンソールに表示しっぱなしにできると便利。これは tail コマンドを利用すると可能。
# tail -f /var/log/system.log
この -f オプションにより、新たに生成されたログがどんどん表示される。
これでひとまず簡易的なデバッグは出来るようになった。この関数はいろいろな場面で利用できそうだ。
FUSE を利用したインターフェース作成
クラウドベースのストレージシステムを作成していると Client インタフェースをどのように実現するのかが重要となる。
これまでは C++ の Client API を提供し、ユーザ側で自由に実装してもらう（というのは建前で実際はユーザインタフェースを作成するのが面倒だった）ようにしていたが、いわゆるファイルシステムのようにアクセス出来るインターフェースがあった方が便利かなと思い FUSE を利用し実装することを決意。
FUSE とは File system in Userspace のことであり、FUSE を使用すると、ファイルシステムの内部について理解したり、カーネル・モジュールのプログラミングを学習したりしなくても、ユーザー空間のファイルシステム・フレームワークを開発することができる。
(出典) FUSE を使用して独自のファイルシステムを開発する
FUSE の特徴は本家（ FUSE: Filesystem in Userspace ）のサイトに
・シンプルなライブラリAPI
・シンプルなインストール（パッチを当てたりカーネルの再コンパイルは必要ない）
・セキュアな実装
・非特権ユーザでも実行可能
・Linux kernels 2.4.X and 2.6.X で動作
と記述されている。
そもそもは Linux 上でのみ動作するものであったようだが、Mac 上で動作する MacFUSE （現在は OSX FUSE）や Windows 上で動作する Dokan などの実装があるようである。
OSX FUSE は 2015年2月に2.7.5がリリースされており現在でも更新されているプロジェクトであるおことが分かる。
Home - FUSE for OS X
一方で Dokan の方は Windows8 でも Windows7 モードで動作するという情報はあるものの、2011年1月以来アップデートが来ていない。
Dokan
調べてみるとどうも Dokan プロジェクトはストップしたようで、代わりとして現在 Windows で動作する FUSE 的なものは Callback File Ssytem (CBFS) があるようだ。これはアクティブに更新されるものの残念ながらライセンス料が必要となってしまう。
Usermode filesystem for your Windows applications - Callback File System® (CBFS®)
うう・・・だれかオープンソースプロジェクト Dokan を引き継いでいる人はいないのか？と調べたところ Dokan をフォークさせ dokanx というオープンソースプロジェクトを立ち上げている人を発見。
Commits · BenjaminKim/dokanx · GitHub
万が一プロジェクトが終わったとしても有志で引き継げるオープンソースプロジェクトはすばらしい！
さてさて 2015年現在でも Linux, MacOS, Windows のプラットホームにおいて FUSE はまだ現役で使えることが判明。というわけで私も FUSE を利用した Client インタフェースを作成することとしよう。
プラットホームは MacOS X (10.9) で OSX FUSE を利用しての実装。とりあえずダウンロード&インストールを完了させ、example ディレクトリ内にある hello プログラムを動作させることに成功。コード内容は非常にシンプルなのでなんかうまくできそう。
AL-FEC の利用
FEC (Forward Error Correction): 前方誤り訂正は非常に多くの分野で利用されている。FEC は伝送データにあらかじめ冗長データを付加することで、各種ノイズによりビット誤りが発生した場合、受信側でその誤り検出と訂正を可能とする技術である。
この FEC をアプリケーション層で利用し、パケットロスなので失われたデータの一部を回復させる目的で作られたものが AL-FEC (Application Layer FEC) である。ネットワークにおけるデータ伝送を伴うアプリケーションの場合、IP 層 (Layer 3) より上の層は二元消失通信路 (BEC) である。つまり 0 と送信されたデータが誤って 1 と受け取られることはあり得ず、その代わり送信されたデータが途中でロスしてしまう可能性がある。つまり消失場所さえアプリケーション側で分かれば AL-FEC には誤り検出機能は不要であり、誤り訂正（消失回復）機能だけ必要となる。そのため、 FEC を Erasure Coding （消失訂正符号）と呼ぶ場合もある。
この AL-FEC を利用したアプリケーション開発をしたいのだが、オープンソースが蔓延するこの世の中で 1 からフルスクラッチで書くには腰が重い。そこでオープンソース実装を探したところ OpenFEC を発見。
よっしゃ、アプリケーション開発に簡単に利用できる！と思うのはまだ早い。当然オープンソースにはライセンスの問題が存在する。
OpenFEC のほとんどは CeCCIL-C という GNU/LGPL と似たライセンス形態をとっているためライブラリとしてリンクして利用する分には問題ない。しかし OpenFEC のうち LDPC Staircase に関する部分は CeCCIL という GNU/GPL に似たライセンス形態をとっているため、それを利用したプログラムを作成し・配布するとソースコードの開示が求められる。
つまり、LDPC Staricase をプロプライエタリなソフトウェアから利用するためには自分でコードを書く必要があるのか・・・
LDPC Staircase 自体は RFC5170 に記述されている。
この RFC に関して日本語で簡単に解説しているブログがこちら。
頑張ってプログラム書くか・・・と思ってたところ、このブログの下の方に別のライブラリ情報を発見。
どうやら OpenFEC の前身のよう。てかこの人たちが RFC5170 書いたんだ・・・なんかいろいろ繋がってくる。このページで配布している LDPC FEC Codes のライセンスは GNU/LGPL なのでかなり自由に利用可能だ。当然今後 LDPC のアルゴリズムを変更したり機能追加する可能性もあるが、その部分のコードを公開さえすれば問題ないので OK！
とりあえずこれをベースに実装をしてみようかな。もしダメだったら・・・あきらめて１から実装するか・・・
waf の導入
大学の研究室で Espresso というシステムを開発している。これは基本的に C++ で書かれているので最初（プログラム全体が小さいうち）は手作業で Makefile を書いていたのだが、さすがにそろそろ限界が近づいてきたのでビルドシステムを導入することを決意。
Linux 環境でプログラムをソースコードからインストールしたことがある人は分かるだろうが、Autotools や CMake、Ant などのことである。
今回はそのうち、Python ベースで記述された waf というビルドシステムをプロジェクトに導入したのでそのメモ。
waf - The meta build system - Google Project Hosting
今回は下記のブログを参考にした。
waf チュートリアル - 純粋関数型雑記帳
基本的な waf のコンセプト、インストールの方法はこのブログがおそらく一番参考になる。しかし、私がダウンロードした waf-1.8 系においては仕様変更があったようで、このブログの通りにしても動かない。（実はココでハマッった）
というわけで本家本元のドキュメントを漁ることに。（結局ドキュメントを見るのが一番と改めて認識）
waf-1.8系のドキュメント: The Waf Book
具体的には、上記のチュートリアルブログにある wscript の書き方を以下のように変更する必要がある。
これでうまくいく。なお、Library を作るときは以前のように features で指定するのではなく bld.program を bld.stlib (静的ライブラリ) や bld.shlib (ダイナミックライブラリ）を指定すれば良い。詳しくはドキュメント参照のこと。
