開発

2014年04月25日

TCP高速化プロキシ「AccelTCP」を公開しました

はてなブックマークに登録

昨年末からずっとこんなことをしてまして、この時期になってようやく今年初のブログ記事です。 進捗的なアレがアレでごめんなさい。そろそろ3年目に突入の @pandax381です。

RTT > 100ms との戦い

経緯はこのへんとか見ていただけるとわかりますが「日本と海外の間を結ぶ長距離ネットワーク(いわゆるLong Fat pipe Network)において、通信時間を削減するにはどうしたらいいか?」ということを、昨年末くらいからずっとアレコレやっていました。

送信したパケットが相手に到達するまでの時間(伝送遅延)を削減するのは、光ファイバーの効率の研究とかしないと物理的に無理なので、ここで言う通信時間とは「TCP通信」における一連の通信を完了するまでの時間です。

伝送遅延については、日本国内のホスト同士であれば、RTT(往復遅延時間)はだいたい10〜30ms程度ですが、日本・北米間だと100ms以上、日本・欧州間だと200ms以上になります。

TCPは、実際にデータを送る前に3Wayハンドシェイクによってコネクションの確立する必要がありますが、伝送遅延の大きな回線では、このハンドシェイクを行うだけでそれなりの時間が掛かってしまいます。

55

また、データ送信時に発生するACK(確認応答)待ちによるアイドルタイムの増加もTCPのパフォーマンス低下の大きな要因です。TCPは、信頼性のある通信を担保するために、受信側からのACK応答を待ちながらデータを送信します。つまり、ACK応答が届くまでに時間が掛かると、それだけ何もせずに待っている時間が増えてしまい、その結果として通信全体に掛かる時間が大幅に増加してしまうのです。そして、通信全体に掛かる時間が増加するということは、スループットが低下するということです。

TCPのスループットの理論値は以下の計算式で求められます。

TCPスループット(bps)= ウィンドウサイズ(bit)/ RTT(sec)

例えば、ウィンドウサイズを64KBと仮定した場合、RTTが10msだとTCPスループットの理論値は51.2Mbpsとなりますが、RTTが100msの場合には5.12Mbpsになってしまいます。つまり、RTTが10倍になればスループットは1/10になるのです。

これは、例え1Gbpsや10Gbpsといった帯域の広い回線を使っていても同じです。TCPのスループットは伝送遅延に大きく影響されます。

このように、伝送遅延の大きなネットワークではTCPは性能を十分に発揮できないため、伝送遅延が大きいことを前提として、通信時間を短縮するための方法を模索するところが今回の出発点です。

TCPがダメならUDPを使えばいいじゃない!

TCPのハンドシェイクによるオーバーヘッドは、その後にやりとりするデータ量が少ないほど、通信全体に掛かる時間に対して占める割合が大きくなります。

例えば、HTTP通信でリクエストもレスポンスもデータ量が少ない場合、通信時間の50%はハンドシェイクによるオーバーヘッドが占めることになります。(※ KeepAliveを使わない場合)

ゲーム内で発生する通信の傾向を見てみると、ほとんどが数KB〜数十KBの小さなデータのやりとりだったため、ハンドシェイクによるオーバーヘッドの影響を大きく受けていそう、というかむしろハンドシェイクを省略するだけでかなり効果がありそうな感じです。

「Google先生のQUICみたいな感じで、UDPベースで信頼性のあるオレオレプロトコル自作すれば結構早くなりそうだよなー」とか妄想が膨らみますね。

そんなわけで、勢いでこんなもの作ってみました。

「IDTP(Iikanji ni Datagram de Transport Protocol)」(大人の事情で公開はなしですm(_)m)

名前の通り、データをUDPでイイ感じに運んでくれるプロトコルです。プロキシサーバでTCPのペイロードをUDPに乗せかえて運ぶことを想定して作りました。QUICに手を出さなかったのは、上に乗せられるプロトコルがSPDYに限定される(らしい)からということと、自分で作ってみるのも楽しいよなーと思ったからです。

とりあえず、数KBのファイルをRTTに近い時間でHTTP GET出来ることを目標にプロトタイプを作成したのですが、最初の実装では以下の機能を盛り込みました。

  • IPアドレス+ポート番号+セッションIDによるセッションの識別
  • SACKのような選択式確認応答
  • タイムアウトによる強制再送(SRTTベースのRTO計算めんどいので固定値)

とりあえず動くようになったので、北米のサーバと日本国内のサーバでベンチマークとった結果が⇩です。

31

お、10KB未満のデータに関してはバッチリRTTと同じくらい(=理論値でのほぼ最速)の時間になってますね!めでたしめでたし。

はい、これで完成とか言っちゃったら怒られちゃいますよね...
フロー制御も輻輳制御もない、つまり送信側は常に全力で送信しているので早くて当然なんですね。そして、トラフィックが一定量を超えるとパケロスが顕著に出はじめます。こうなると再送→パケロス→再送...と、絵に描いたような輻輳により通信が破綻してしまいます。

その後、フロー制御や輻輳制御、スロースタートの機能を盛り込み、一応「信頼性のあるトランスポートプロトコル」と名乗っても大丈夫そうなところまで作り込みました。

TCPへの回帰

ここまでやって、ふとあることに気づきます。

「コレ、もうTCPじゃね?」

確認応答、再送、フロー制御、輻輳制御、スロースタート...どこからどう見ても完全にTCPです。

TCPの欠点を補うために「UDPベースで信頼性のあるトランスポートプロトコルを作ろう」という試みは、誰もが一度はやったことあるんじゃないかと思いますが、ぼくのような素人だと真面目に作り込めば作り込むほどTCPになってしまうんですよね。

こうなると、ハンドシェイクを省略している意外はTCPとの差がほとんどありません。むしろ、標準のプロトコルスタックの方が圧倒的に洗練されているため、どう考えてもそっちを使うべきです。

そんなこんなで、半分ネタで作ったIDTPは、速攻でお役御免になりました。

結局、ふりだしに戻り「ベースの通信はTCPに任せたい!でもハンドシェイクは省略したい!」という、なんとも他力本願な考えに至ります。

TCPでハンドシェイクを省略...あれ、どっかで聞いたことあるような...

そうだよ!TFO(TCP Fast Open)だよ!TFOでやればいいんだよ!

結論:素直にクライアントとサーバのカーネルを3.6/3.7以上にしてTFOを使う。めでたしめでたし。

...まぁ、それで片付いてくれれば苦労しないんですが...^^;

TFOを採用するにあたって、以下のような懸念事項があります

  • 比較的新しいカーネルでなければ利用できない
  • クライアントアプリの改修が必要(iOSって対応してたっけ?)
  • NATやF/Wの介在によってTFOが失敗し、通常のハンドシェイクにフォールバックする可能性がある

全くの新規で環境を用意するなら問題にならないかもしれませんが、既に運用中のサービスに適用するとなると、めちゃくちゃハードルが高くなります。

そんなわけで、単純にTFOで全て解決!とはならないのでした。

ようやく本題の「AccelTCP」の話

長々と前置きを書いてしまいましたが、紆余曲折(だいぶ遠回り)した結果、今回の記事のタイトルにある「AccelTCP」を開発するに至りました。

AccelTCP(ACCELerlate TCP proxy)

AccelTCPは、伝送遅延の大きな回線におけるTCP通信を高速化するためのプロキシサーバ型のソフトウェアです。下記の図のように、クライアント側とオリジンサーバ側にそれぞれAccelTCPのプロキシを立てて、伝送遅延の大きな長距離ネットワーク上での通信を代理で行います。

47

コネクションプーリングによりTCP接続のオーバーヘッドを削減

プロキシサーバ間で、あらかじめ確立されたTCPコネクションを再利用する「コネクションプーリング」を行います。プロキシサーバ間のコネクションプーリングにより、TCPコネクションの確立時に発生する3Wayハンドシェイクのオーバーヘッドを削減し、比較的小さなデータのやりとりを行う通信の待ち時間を大幅に短縮できます。

TCPパラメータの最適化による高速化

プロキシサーバ間のTCP通信は、ウィンドウサイズなどのTCPパラメータをネットワークの特性に合わせ最適化することにより、データ転送効率が大きく向上します。

プロキシサーバ型によるメリット

プロキシサーバ型を採用することにより、クライアントおよびサーバサイドのプログラムを改修することなく「AccelTCP」を利用できます。また、プロキシサーバの設置により通信区間が分割され、各通信区間の往復遅延時間が減少します。これは、パケット消失時の再送時間の短縮につながり、通信全体の高速化が期待できます。

HTTPプロキシモード

ネームベースのバーチャルホストに対応するために、プロキシサーバによるHTTPリクエストのホストヘッダ書換えとXFFヘッダ挿入を行うHTTPプロキシモードを備えています。

通信データの暗号化とSSLオフロード機能を搭載

プロキシサーバ間の通信はSSL/TLSにより暗号化され、安全にやりとりできます。また、SSLオフロード機能を搭載しているためSSL非対応サーバのSSL化や、サーバからSSLの処理を分離することも可能です。

ぶっちゃけ大したことやってないけど、データ量が小さい場合はそれなりに効果あります。

53

使い方

READMEだけ見ても分かりにくいと思うので、簡単な使い方の説明です。

ビルド

AccelTCPをビルドするには以下のライブラリが必要です。

ライブラリが揃っていれば、makeするだけでビルド終了です。

$ git clone https://github.com/KLab/AccelTCP.git
$ cd AccelTCP
$ make

プロキシの起動方法

まず、サーバプロキシを起動します。クライアントプロキシからの接続を 10381 ポートで待ち受け、オリジンサーバ(133.242.5.116:80)に転送するには、下記のように起動します。--server がサーバプロキシとして動くためのオプションです。

$ ./acceltcp -- --server 10381:133.242.5.116:80

次に、クライアントプロキシを起動します。クライアントからの接続を8080ポートで待ち受け、サーバプロキシ(192.168.0.1:10381)に転送するには、下記のように起動します。--http オプションは、HTTPプロキシモードを有効にするためのオプションです。HOSTヘッダを --http-host オプションで指定した内容に書き換えます。--connection-num オプションは、クライアントプロキシからサーバプロキシに対して事前に接続しておくTCPコネクションの数です。

$ ./acceltcp -- --http --http-host=www.klab.com --connection-num=100 8080:192.168.0.1:10381

これで、クライアントプロキシの8080ポートへのアクセスが、オリジンサーバ(133.242.5.116)の80ポートへ転送されます。

オプションの説明とか

オリジンサーバに対してSSLで接続する場合には、サーバプロキシを以下のように起動します。

$ ./acceltcp -- --server --ssl-connect 10381:133.242.5.116:80

クライアントプロキシとサーバプロキシの間もSSL化する場合には、それぞれ以下のように起動させます。なお、デフォルトではカレントディレクトリにある server.crt と server.key が使用されますが、それぞれ --ssl-certificate と --ssl-privatekey で上書き指定できます。

$ ./acceltcp -- --server --ssl-accept --ssl-connect 10381:133.242.5.116:80
$ ./acceltcp -- --ssl-connect --http --http-host=www.klab.com --connection-num=100 8080:192.168.0.1:10381

更に、クライアントプロキシもSSLで待ち受ける場合には下記のようになります。これで全区間の通信がSSL化されます。

$ ./acceltcp -- --server --ssl-accept --ssl-connect 10381:133.242.5.116:80
$ ./acceltcp -- --ssl-accept --ssl-connect --http --http-host=www.klab.com --connection-num=100 8080:192.168.0.1:10381

その他に、--rbuf と --sbuf オプションで受信送信それぞれのソケットバッファのサイズが変更できたりもします。

おわりに

本件はIDCフロンティアさんとの共同研究ということで、超特急で検証用のサーバ設定してもらったり、IDTPが暴発して大量のトラフィック流し過ぎてご迷惑をお掛けしたりしちゃってホントごめんなさいなこともありましたが、久しぶりに没頭できるネタを振ってもらって有り難い限りです。まだまだこれで終わりではないので、もっと突っ込んで輻輳制御のモジュールとかも書いてみたりしたいなぁと思っています。

外部の方から見たら「KLab=ケータイのゲーム作ってる会社」というイメージが強いと思うんですけど、中にはこんなことやってる人もいるよーってことで、こういうのが好きな人がKLabに興味持ってくれると個人的にとっても嬉しいです。

おしまい。



@pandax381


klab_gijutsu2 at 11:00|この記事のURLComments(0)TrackBack(1)
2014年01月09日

マルチコアプログラミングで遊ぼう!

はてなブックマークに登録

マルチコアプログラミングで遊ぼう!Part 1



Introduction


この50年間はムーアの法則のお陰で しかし、数年前から動作クロック引き上げの限界が現実化し[5,p.14-24]、そしてCPUアーキテクチャ自体も すでにかなり複雑化しており、このレベルでのチューニングもすでにかなり進んだ状態です。

計算力引き上げの面では、SIMD命令がかなり増え、内部のデータの幅も増え、数倍の速度向上につながってきました(最新のCPUでは512bit幅になろうとしている[6])。

とはいえ、SIMDやベクタ計算で数倍の速度向上につながる計算パターンは限られています。

自然に効率よく複数のプログラムを動かすには同時実行できるコア数を増やすほかにありません。 ムーアの法則がもうしばらく有効で、トランジスタの集積度を高めることができるのであれば、それらをさらなるSIMD化のために割くよりは搭載コア数を増やすことに使ったほうが現実的です。

How : More power for one application


マルチコアは、互いに独立した複数のアプリケーションを同時実行する(例えばOS上で別々のプロセス・スレッドとして実行する)上ではシンプルに速度向上へ寄与しますが、単一アプリケーションで簡単に力を引き出せるかというと、そこには解決すべき課題があります。

同じアプリケーション内で多数のスレッドを利用すると、それぞれの起動、停止、スレッド間の同期、データアクセスの一貫性といった問題に直面します。 さらに、デッドロックを引き起こすケースを慎重に避ける必要があり、これらの問題は実行するスレッド数が増えれば増えるほど複雑さを増します。

これをうまく管理するのは現実的とは言えません。

出来る限り、プログラムの開発時に並列実行される事を出来るだけ意識しないで済むモデルのほうが分かりやすいと言えます。

OSが無ければ、HWだけですと(例えばゲーム機)、1コア = 1 スレッドになります。(HyperThreadingの話もあるので、Physicalコアとロジカルコアを無視します) アプリケーション内の部分部分を別のコアに割り当てられれば、リソースを最適に利用する事が出来ます。

OSの場合、スレッドの実行の仕方はOSのスケジューラーによって決められますが、今回のやり方ではアプリケーション内部で、なんらかのメカニズムを使って、アプリケーションが自分のロジックでスケジューリングをおこなう必要があります。 また、OSと違って処理をタイマーによって切り替える方法をとらず、自分の作業を出来るだけ十分短くして、終わったら次の作業を実行するというやり方にします。

このため、作業の切り替えコストが重要になります。

つまり、アプリケーションの中で「今度する仕事」の一覧を持ち、スケジューラーのポリシーに従ってそのリストから次に実行する「仕事」 を決める。

Framework :


今回紹介するフレームワークは個人的に作ったマルチコアのスケジューラーです。
こちらです:https://github.com/KLab/EnCore

開発にあたって、次の資料が参考になりました。
[1]http://molecularmusings.wordpress.com/2012/04/05/building-a-load-balanced-task-scheduler-part-1-basics/
[2]http://software.intel.com/en-us/articles/do-it-yourself-game-task-scheduling/
[3]http://www.1024cores.net/home/scalable-architecture/task-scheduling-strategies

このフレームワークの仕組みは

  1. スレッド毎に仕事の一覧を持つ
  2. スレッドが現在の仕事を終えると次の仕事を取りに行く
  3. スレッドが次の仕事を取りに行った時に、自分のリストが空であれば、隣のスレッドの仕事を取りに行く
つまり、仕事がなくなるまではスレッドが仕事の一覧を実行し、暇になった時に隣のスレッドの仕事を取ろうとします。 このフレームワークでは仕事は「Task」と言います。 基本的に立ち上げるスレッド数はコア数と同じです。環境によりますが、通常これらはOSのスケジューラによって各スレッドが別々のコアに割り当てられます。 現在の実装はWindows版ですが、他のOS・環境へと簡単に移植できます。

Thread and tasks

開発の動機として、マルチコアを活かせて多くの環境で動作するコードにしたいという考えがありました。また、十分シンプルで簡単に変更が出来て、実験的な機能を実装出来るが欲しかった。 結果として1500行ぐらいで十分遊べるシステムになってます。

フレームワークにはすでに様々な機能を実装していますが、今回は概念の説明に留めて詳細の説明を省略し、基本機能のみを使用します。

First Test : Push/Pop Performance



まず、フレームワークを利用してみましょう。
#include "LX_MultiTasking.h"
#include <stdio.h>
そして、フレームワークに今回実行する「仕事」を定義します。 Taskクラスを継承して自分のtaskを定義します。
class TestTask : public Task {
public:
  TestTask();
  void Execute(u8 worker);
  u32 m_time;
};
そして実装します。
TestTask::TestTask() {
  m_time = 0; // 実行回数を初期化
  TSK_SetRunFunction((execFunc)&TestTask::Execute); // 実行する関数を設定
}

void TestTask::Execute(u8 worker) {
  WRK_PushExecute(worker,this); // 現在のThreadに次の仕事を設定する
  m_time++; //実行回数を増やす
}
そして、システムを起動し、タスクを登録して、実行します。
int main(int argc, char* argv[])
{
  // Setup library
  if (WRKLIB_Init()) {
    // Feed 2 cores : Create 2 tasks and queue them on workers.
    TestTask* pTaskT1 = new TestTask();
    TestTask* pTaskT2 = new TestTask();
    WRK_PushExecute(0, pTaskT1);
    WRK_PushExecute(1, pTaskT2);

    // Start Cores : 2 threads.
    WRK_CreateWorkers(2, false, 16384, NULL);
    
    // Check Performances
    u32 sec = 0;
    Sleep(1000);
    while (1) {
      printf("Execution Count, Core1:%i Core2:%i %i\n", pTaskT1->m_time, pTaskT2->m_time, ++sec);
      pTaskT1->m_time = 0;
      pTaskT2->m_time = 0;
      Sleep(1000);
    }

    delete pTaskT1; delete pTaskT2;
    
    // Never reach here in our test but let's be clean anyway.
    WRKLIB_Release();
  }
}
実行結果は、モバイルAMD K-140@1420MHzにおいて平均720万回/秒/コアでした。

つまり、
  1. タスクをpopして
  2. そしてexecuteコールして
  3. タスクをpushして
  4. タスク実行回数を+1する
を200サイクル以内で完了できていることになります。(リリース版) 詳細なプロファイルはとっていませんが、ソースコードの流れを見るとおそらく30%がexecute関数内で消費されています。つまり意図した通りスレッド実行が忙しい状態にあり、スレッド同士のロックは発生せず140~150サイクル以内にはタスクの切り替えができています。

Warning:
今回のエンジンのソースはまだVisual C++ 2010 Expressでしかコンパイルしていないので、おそらくGCCでのコンパイルやLinuxでの動作には少し変更が必要です。

例えばゲームエンジンであれば、3Dオブジェクト毎のアニメーション計算、AIのステートマシン管理・Scriptなど、音声・Audio管理、ゲーム内のオブジェクトのアップデート、物理計算、 描画用のculling、ライトの計算、描画自体、パーティクル・システム、その他のタスクがたくさん存在します。さらに、タスク同士の依存性が少なく、並列化に問題なく動く。

このようなシステムで簡単にマルチコアを使いこなす事が可能になります。つまりプログラムをたくさんの細かな作業ブロックに切り分け、依存関係に気をつけながら、仕事のリストに登録すると、依存関係が守られる限りにおいてそれらが実際にどのCPUで実行されるかを意識することなくアプリケーションの正常な動作を実現できます。

今回の記事はこの辺で終わりますが、今後に考えているシリーズの中で
  • このフレームワークのAPIの使い方
  • 実験的に作成するテスト
  • serial的な問題をどこまで並列化出来るのか
  • 実際にマルチコアプログラミングで起きる問題(例:false sharing、memory bandwidth、cache alignment、thread affinityなど)
をテーマにして、記事を書きたいと思います。
@rpiquois
klab_gijutsu2 at 18:09|この記事のURLComments(0)TrackBack(0)
2012年05月23日

KLab勉強会#6のお知らせ

はてなブックマークに登録

時間が経つのは早いもので、前回の開催から約3年が経とうとしているKLab勉強会ですが、あまり難しいことは気にせず、しれっと#6を開催したいと思います。

今回は、弊社でソーシャルゲームを開発しているエンジニアが、普段の業務を題材にしたセッションをお送りします。

開発者同士の交流を目的として、さほど堅苦しくない、ゆる〜い感じの集いにしたいと思っていますので、興味のある方は気軽にご参加ください。

※終了後に会費制(4000円から5000円くらい)で懇親会を予定しています。

開催要項

日時
2012/6/25 (月) 19:00-21:00 (18:30受付開始)
場所
KLab株式会社 ミーティングルームMLK
東京都港区六本木6-10-1 六本木ヒルズ森タワー22F
(アクセス方法)
参加費
無料
人数
50名程度

参加方法

ATNDの KLab勉強会#6 から参加登録してください。

※ 登録時にアンケート(懇親会に参加する/しない)の選択をお願いします。

セッション

  1. タイトル
    『名状し難きDBアンチパターン』
    講師
    牧内 大輔(KLab株式会社)
    概要

    ソーシャルゲームでは多くのページでユーザデータの更新が発生するため、スキーマやインデックス、クエリのチューニングが必須となります。

    良い実装をするためには悪い実装を知っているに越したことはありません。 ここでは自社案件の中で実際に遭遇した混沌と、如何に回避したかを紹介したいと思います。 なおSANチェックはありませんのでご安心ください。

  2. タイトル
    『ソーシャルゲームのデータマイニング的な話』
    講師
    高田 敦史(KLab株式会社)
    概要

    ソーシャルゲームの日々の運用を支えるデータの蓄積・レポート・分析。 AWSを活用したデータ解析の実践について説明します。 Elastic MapReduceの利用法やデータの可視化についてもお話したいと思います。

  3. タイトル
    『圧縮されたログファイルの活用ツール』
    講師
    於保 俊(KLab株式会社)
    概要

    あなたの現場ではアクセスログの保存先をどうしていますか? もしドキュメント指向DBとかその他の洗練された方法で蓄積されているなら・・・ この話はこんなこともできるんだ〜と聞いてください。 もし、弊社のように過去からの負の遺産でbzip2で固めてとっていて、 活用するのが大変と思っているのなら、 いくつかのログのユースケースでのソリューションがこれかなと思います。 すなわち、圧縮されたログを途中から解凍してみせます。


klab_gijutsu2 at 09:00|この記事のURLComments(0)TrackBack(0)
2011年12月08日

ソーシャルアプリのボトルネック調査例(strace編)

はてなブックマークに登録

KLab Advent Calendar 2011 「DSAS for Social を支える技術」の6日目です。


はじめに

ソーシャルゲームの開発では、仕様変更への柔軟な対応が求められることが多い上、突発的なアクセス増加にも耐えられる応答性能が要求されます。

一昔前までは、サービスの性能を担保するにはきちんとアーキテクチャを設計し、入念に動作チェックして、負荷試験して、プロファイル取って・・・みたいなことをリリース前にひらすやるのが理想だと思っていた頃もありました。


しかし、ソーシャルゲームの世界ではリリース直後からイベントやキャンペーンなどの追加開発が入ったり、ユーザの動向やコミュニティを参考にして仕様を変更することが多いので、リリース前に頑張ってチューニングしていても、その性能を担保し続ける事が難しいといった現状があります。

まあ、これはこれで刺激があって楽しい面もありますし、遊んでくれているユーザの皆様にできるだけ良いサービスを提供したいという気持ちもあるので、きちんと運用ができるように様々な工夫をしていますが、所詮プログラムは人間が書くものなので、時には思わぬ爆弾を仕込んでしまい、著しく応答性能が悪くなってしまうこともあったりします。


このような問題のほとんどは、原因さえわかってしまえば容易に解決できるケースが多いので、イカに速くボトルネックを見つけ出すかが鍵となります。

ボトルネック調査といっても、発生している事象によってアプローチの仕方は様々です。DBサーバに想定以上のI/Oが発生している場合は、slowログを見てexplainするでしょうし、接続エラーやタイムアウトが頻発している場合はネットワークの品質を疑って、スイッチのログを確認したりもするでしょう。

必要な場面で必要な情報を取り出す手段を知っていることが、ボトルネックを調査する上で必要とされるスキルなのかもしれません。

えーっと、、すっかり前置きが長くなってしまいましたが、今回はstraceを使ってアプリケーションのボトルネックを調査した例を紹介してみたいと思います。


apacheのプロセスを覗いてみる

「実稼動中のapacheをstraceなんかして本当に解析できるの?」と疑問に感じる方もいるかもしれませんが、実際にやってみると以外と簡単です。

# strace -p 8139 -tt -T -e trace=network,poll
15:21:01.490665 accept(3, {sa_family=AF_INET, sin_port=htons(xxxxx), sin_addr=inet_addr("x.x.x.x")}, [16]) = 11 <0.000011>
 -- snip --
15:21:02.039149 accept(3, {sa_family=AF_INET, sin_port=htons(xxxxx), sin_addr=inet_addr("x.x.x.x")}, [16]) = 11 <0.000007>
 -- snip --
15:21:02.727402 accept(3, {sa_family=AF_INET, sin_port=htons(xxxxx), sin_addr=inet_addr("x.x.x.x")}, [16]) = 11 <0.000007>
 -- snip --
15:21:03.625652 accept(3, {sa_family=AF_INET, sin_port=htons(xxxxx), sin_addr=inet_addr("x.x.x.x")}, [16]) = 11 <0.000009>

apacheの子プロセスをstraceすると上記のような結果となります。accept(2) を境界にしてリクエスト毎の処理を追うことができそうです。

15:21:04.244882 accept(3, {sa_family=AF_INET, sin_port=htons(37421), sin_addr=inet_addr("x.x.x.x")}, [16]) = 11 <0.000011>
15:21:04.254675 socket(PF_INET, SOCK_DGRAM, IPPROTO_IP) = 20 <0.000007>

15:21:04.254702 connect(20, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("0.0.0.0")}, 28) = 0 <0.000007>
15:21:04.254749 poll([{fd=20, events=POLLOUT}], 1, 0) = 1 ([{fd=20, revents=POLLOUT}]) <0.000055>
15:21:04.254829 sendto(20, "W\"..., 43, MSG_NOSIGNAL, NULL, 0) = 43 <0.000018>
15:21:04.254873 poll([{fd=20, events=POLLIN}], 1, 5000) = 1 ([{fd=20, revents=POLLIN}]) <0.000014>
15:21:04.254918 recvfrom(20, "W\"..., 1024, 0, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("127.0.0.1")}, [16]) = 79 <0.000006>
15:21:04.254974 socket(PF_INET, SOCK_STREAM, IPPROTO_IP) = 20 <0.000007>
15:21:04.255018 connect(20, {sa_family=AF_INET, sin_port=htons(11211), sin_addr=inet_addr("x.x.x.x")}, 16) = -1 EINPROGRESS (Operation now in progress) <0.000019>
15:21:04.255059 poll([{fd=20, events=POLLIN|POLLOUT|POLLERR|POLLHUP}], 1, -997199722) = 1 ([{fd=20, revents=POLLOUT}]) <0.000098>
15:21:04.255182 getsockopt(20, SOL_SOCKET, SO_ERROR, [0], [4]) = 0 <0.000005>
15:21:04.255219 sendto(20, "get "..., 38, MSG_DONTWAIT, NULL, 0) = 38 <0.000014>
15:21:04.255255 poll([{fd=20, events=POLLIN|POLLERR|POLLHUP}], 1, -997199722) = 1 ([{fd=20, revents=POLLIN}]) <0.000174>
15:21:04.255456 recvfrom(20, "VALUE "..., 8192, MSG_DONTWAIT, NULL, NULL) = 3655 <0.000007>

15:21:04.367211 socket(PF_INET, SOCK_STREAM, IPPROTO_IP) = 21 <0.000009>
15:21:04.367408 socket(PF_INET, SOCK_DGRAM, IPPROTO_IP) = 22 <0.000010>
15:21:04.367445 connect(22, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("0.0.0.0")}, 28) = 0 <0.000010>
15:21:04.367511 poll([{fd=22, events=POLLOUT}], 1, 0) = 1 ([{fd=22, revents=POLLOUT}]) <0.000007>
15:21:04.367551 sendto(22, "e("..., 43, MSG_NOSIGNAL, NULL, 0) = 43 <0.000027>
15:21:04.367614 poll([{fd=22, events=POLLIN}], 1, 5000) = 1 ([{fd=22, revents=POLLIN}]) <0.000008>
15:21:04.367663 recvfrom(22, "e("..., 1024, 0, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("127.0.0.1")}, [16]) = 79 <0.000007>
15:21:04.367761 connect(21, {sa_family=AF_INET, sin_port=htons(3306), sin_addr=inet_addr("x.x.x.x")}, 16) = -1 EINPROGRESS (Operation now in progress) <0.000025>
15:21:04.367837 poll([{fd=21, events=POLLIN|POLLPRI}], 1, 30000) = 1 ([{fd=21, revents=POLLIN}]) <0.000246>

 -- snip --
15:21:04.381269 shutdown(21, 2 /* send and receive */) = 0 <0.000011>
15:21:04.382572 shutdown(11, 1 /* send */) = 0 <0.000015>

このログの黄色の部分は、11211番ポートへ接続してgetという文字列を送信してることからmemcachedへの問い合わせでしょう。また、水色の部分は3306番ポートに接続しているので、MySQLへ接続していることがわかります。

そして、memcachedから値を取得し、MySQLへ接続するまでに100ms以上の時間がかかっていることが読み取れます。したがって、この処理のボトルネックは、SQLでもネットワークでもなく、MySQLへ接続するまでのアプリケーションコードの中にあると推測できます。

straceで把握できるのはここまでですが、アプリケーションのボトルネックを発見するための有力な手がかりにはなるのではないでしょうか。

ただ、さすがに稼働中の全サーバの全プロセスをトレースするのは大変すぎるので、「問題が見つかればらっきー☆」な気持ちで、アクセスが増える時間帯だけ、一部のサーバだけでstraceをかけてみるところから始めるのがよいと思います。


まとめ

本来であれば、この手の問題は試験環境などでXDebugなどを使ってプロファイルを取るのが定石だと思いますが、試験環境で再現させる事が難しい事象も数多くあります。このようなケースでは、アプリケーションの中でデバッグプリントを仕込み、ログを大量に出力させながら調査するといった手法を取ったりすることもありますが、今回ご紹介したstraceや、ltrace、oprofile、LatencyTOPなどのツールをうまく利用することで、調査にかかる時間や手間を減らせる可能性もあります。

ただ、この手のツールはアプリケーションエンジニアには馴染みが薄く、どちらかというとサーバエンジニアやネットワークエンジニアの得意分野な気がしています。不慣れなツールを頑張って駆使しようとする意気込みも素敵ですが、どうしても困った時には、最寄りのサーバ担当者に「アプリケーションプロセスをトレースしてちょ!」と依頼してみるのも悪くはないと思っています。

まあ、要は何が言いたかったかというと、「これは僕が自分で解決しなければいけない問題さ!」と信じて一人で頑張るだけでなく、ダメもとでいいので、たまにはサーバ屋とか、ネットワーク屋とか、八百屋とか、魚屋とかにも相談してみると、もしかすると別の視点から問題解決の糸口が見つかるかもしれないよ!、、というお話でした。



最後に念のため補足

straceでapacheプロセスをトレースする際は、httpd.confに

MaxRequestsPerChild 0

を指定しないと、プロセスが勝手に終了してしまうのでご注意ください。

また、straceは昔からバグが多いことでも有名です。できるだけ新しいバージョンを使い、事前に安全な環境でテストしてから利用することをおすすめします。


klab_gijutsu2 at 22:59|この記事のURLComments(0)TrackBack(0)
2008年12月02日

KLab の若手エンジニアがブログを始めました

はてなブックマークに登録

この度、KLab(株)の若手エンジニアがブログを始めることになりました。

KLab若手エンジニアの これなぁに?

日々の業務における技術的トピックや、何気なく使っている便利なライブラリの内部で行われている処理を覗いた時のハナシ。これ等をブログというカタチで面白いものを発信できるのでは、という発想からこのブログをはじめることとなりました。

【投稿済みの記事やテーマ】
symfony × MySQL × Shift_JIS: 0×5c関連
0×5c問題について書いてみました。
他にもsymfonyのトランザクションについても書いています。 PHPやsymfonyについての記事はこれからどんどん書いていく予定です!

Rhinoを使おう
拡張性とポータビリティにすぐれた JavaScript 処理系 Rhino(ライノー)を紹介しています。 JavaScriptやActionScript、Flex等RIAに関する記事等もどんどん書いていきます!

C/C++ のコードを Flash Player 上で動かす Alchemy
先日 Adobe Labs がプレビューリリースしたAlchemy というプロジェクトを試した記事です。 新しい技術に挑戦した際のトピックスなども織り交ぜていきます。

まだまだ未熟な若手エンジニアですが、技術・知識に対するアグレッシヴなアプローチや新しいものを試すチャレンジ等見どころ満載なブログです!

コメントなど大歓迎です、ぜひチェックしてください!!


klab_gijutsu2 at 14:41|この記事のURLComments(0)TrackBack(0)
2008年11月12日

まくおをFreeBSDやMacOSXでも動くようにしました

はてなブックマークに登録

先日公開したまくおさんですが、 Linux以外の環境では全然ビルドが通らないことに公開後に気がつきました。 気になって気になって夜も寝れなかったので(笑)、手元にあったFreeBSD7.0とMacOSX10.4でも動くようにしてみました。

また、specファイルと起動スクリプトを頂きました ので同梱しておきます。
これは、とても助かります!、ありがとうございます!>Naoyaさん

というわけで、今回は「LinuxではビルドできるけどFreeBSDではエラーになる点」をいくつか紹介したいと思います。

ftimegettimeofday に変更

何を血迷っていたのか、現在時刻を取得するためにftimeを使っている箇所がありました。 マニュアルにもきちんと「この関数は古いものである。使ってはならない。秒単位の時間で十分なら、 time(2) が利用できる。 gettimeofday(2) でマイクロ秒が得られる」って書いてありますね。

tzset 後のtimezone参照をやめて localtime を使うようにした

makuosan はベースディレクトリにchrootする機能があります(-c オプション)
また、makuosan のログはsyslog に出力していますが、chrootすると/etc/localtime が見えなくなるため、syslogに記録される 時間が9時間ほどタイムスリップしてしまいます。(たしかproftpdのchroot機能などでも似たような問題があったと思います)

しかし、chroot先に/etc/localtimeを勝手にコピーするわけにもいかな いので、環境変数の"TZ"に"JST-9"のような文字列で時差を設定します。すると、/etc/localtime がなくても日本標準時で ログが記録されるようになります。

問題は、環境変数の"TZ"に設定する文字列をどのように生成するかですが、それを以下のようなコードで実装していました。
extern char *tzname[2];
extern long timezone;

void settzenv()
{
  char TZ[256];
  tzset();
  sprintf(TZ,"%s%+ld",tzname[0],timezone);
  setenv("TZ",TZ,0);
}
tzset するだけで必要な値がグローバル変数に入るので便利だなーなんて軽く考えていましたが、FreeBSDでは同名の関数が あるのでエラーになってしまいます。

そのため、localtime 関数を使ってtm 構造体をセットし、tm_gmtoff メンバとtm_zone メンバを利用して文字列を生成するようにしました。

  time_t ttime;
  struct tm *t;
  char tz[256];
    
  time(&ttime);
  tzset();
  t = localtime(&ttime);
  sprintf(tz, "%s%+ld",   t->tm_zone, -(t->tm_gmtoff/3600));
  setenv("TZ", tz, 0);


おまけ: libcryptが必要な理由

最後に少しだけ、プロジェクトサイトに書いていなかったことを書いておきます。
(もちろん後で追記しますが(^^;

makuosanではファイルの同一性をチェックする機能でmd5を使っています。

 $ msync --check

また、ネットワークに流れるデータを暗号化するためにblowfishを使っています。

 $ echo himitsu > keyfile
 $ chmod 400 keyfile
 $ makuosan -b dokka -k keyfile
これらの機能は、opensslのライブラリを利用しているので、ビルドにはopensslの ヘッダファイルとライブラリが必要です。


klab_gijutsu2 at 12:50|この記事のURLComments(0)TrackBack(0)
2008年08月01日

社内コードコンペ - お題:最速なCIDRブロックマッチ判定 〜 稲田の場合: hamanoが倒せない 〜

はてなブックマークに登録

おさらい


このコードのウリ

安井さんが2分探索で実装しているという話を聞いて、「それ、TRIE(トライ)で書いた方が速いしシンプルに 書けるんじゃね?」と思って、コードコンペに参加しました。

TRIEそのもの解説は、先日の濱野さんの物と同じなので省略します。

2分探索等だとO(log n) (nは登録されているcidrの数)の計算量になりますが、TRIEを使うと計算量はO(m) (mはアドレスの長さ) となり、登録するcidrの数が増えてもほとんど遅くなりません。 また、2分探索に比べると、探索部分のコードが非常にシンプルになるのもTRIEの魅力です。

基本的に濱野さんと比じ処理なのですが、性能で若干負ける代わりに、可読性や柔軟性はこちらの方が 高いと自負しています。

コード解説

まず、最初のバージョンはこんな感じになっていました。この頃は「アドレス帯がかぶっている時は 狭いアドレス帯を優先する」という要求がなかったこともあり、非常にシンプルです。

/* データ構造 */
typedef struct ADR_TRIE {
  const char *type;
  struct ADR_TRIE *child[TABLE_SIZE];
ADR_TRIE;

/* 葉からはchildを削ってメモリ節約する. */
typedef struct ADR_TRIE_LEAF {
  const char *type;
} ADR_TRIE_LEAF;
...

    /* 探索部分 */
    ADR_TRIE *pt = &trie_root;
    while (pt && (!pt->type)) {
      int b = addr >> 24;  /* このころはアドレスはuint32_tだった */
      pt = pt->child[b];
      addr <<= 8;
    }
    if (pt) return pt->type;

このコードを実装している間、IRCでは濱野さんが同じアイデアを提案していました。
hamano``> 256 分木つくって 1オクテットずつ読んで分木すれば、最低4回の遷移で判別出来る
hamano``> メモリ空間が大きくなるかもしれませんが、この程度のデータ量ならそれほど大きくならないと思います
hamano``> 僅か数命令で判別出来るのでこれ以上の最適化は無いかも
YasuiML> やってみて★ 
hamano``> あんまり、差が出ないのでイマイチ乗れないなぁ
hamano``> 問題を国判別に拡張しません?^^; 

そして、上の実装ができて、コードを安井さんに渡しました。

YasuiML> こみったす
katsumiD> 2段のテーブル引きにしたらどだろう
katsumiD> 上位16bit と 下位16bit にわけて
YasuiML> うほ
YasuiML> yasui-m@sag15:~$ ./cidrlookup 5000000 210.153.84.128 210.169.176.128 222.7.56.128 209.85.238.120 60.32.85.216
YasuiML> loop  : 5000000
YasuiML> elapse: 6.8481210
YasuiML> avg   : 0.0000003
YasuiML> 稲田さんのはやいすね!!
YasuiML> 一秒以上差がつきましたかあ

と褒められて、良い気になっていました。(この時点では、ベンチマークの内容が違い、経過時間がまったく異なります)

しかし、次の日、濱野さんがより高速なコードをコミットしました。その中身を読んでコードを読んで衝撃が走りました。

return type[tab[addr[3]][tab[addr[2]][tab[addr[1]][tab[addr[0]][1]]]]];

なんだこの[]だらけのコードは!分岐なしか!テーブル参照回数が同じである以上、 分岐を消さないと絶対勝てない!と思い、慌てて対抗して分岐を削除してみました。

  pt = pt->child[*addr++]; /* addrは、ネットワークバイトオーダーで格納されたアドレスの先頭アドレス */
  pt = pt->child[*addr++];
  pt = pt->child[*addr++];
  pt = pt->child[*addr++];
  return pt->type;

分岐を削除するためのhackとして、葉の形を変えました。分岐削除前は、pt->childを持たないようにしてメモリ消費を 抑えていたのですが、葉もpt->childを持ち、pt->child[n] == ptとしておくことで、短いサブネットアドレスでも4回の テーブルルックアップを実行するようにしました。分岐が減る代わりに、サブネットアドレスが短い場合はテーブルルック アップが増えるのですが、今回はマイクロベンチだからテーブルはほぼ確実にキャッシュに載っていますし、テストに使った アドレスもサブネットアドレスが長い物ばかりだったので、分岐を削除することでかなり速度を稼げました。

おわりに

ここに載せている以外にもいろいろと寄り道したのですが、最終的に、これ以上にできそうなアイデアは全て等価なものが 濱野さんのコードで実現済みという状況になってしまい、負けを認めました。 でも、メモリの確保の仕方が柔軟に対応できる点や、コードを読んで構造を把握しやすいかなどの面で、本採用を狙っています。

ベンチマーク

5つのとあるIPアドレスのそれぞれについてどのグループに属するか判定する、という処理を5,000,000回実行したときの総所要時間(elapsed)と1回の判定に要した時間の平均(average)です。

ベンチマークは、同じハードウエアのx86とx86_64の環境の2つでとりました。_8が、1テーブルでアドレス1byte分処理するバージョンで、 _16が1テーブルでアドレス2byte分処理するバージョンになります。16の方がテーブル参照が2回で済むので高速ですが、 メモリ使用量がバカみたいに増えるので、普通に使うなら8の方になります。

x64環境に置いてはかなり善戦していますが、hamanoさんにはあと一歩届きませんorz

x86

時間
name        elapsed[sec]  average[usec]
========================================
apr        59.379924      2.375197
ip-country  3.739187      0.149567
yasui-a     2.727045      0.109082   # インラインアセンブラ
yasui-c     0.975544      0.039022   # C言語
hamano-1    0.234664      0.009386
hamano-2    0.142496      0.005700
inada-n_16  0.175591      0.007023
inada-n_8   0.208570      0.008342

x86_64

name        elapsed[sec]  average[usec]
========================================
apr        52.340651      2.093626
ip-country  0.664034      0.026561
yasui-c     0.706095      0.028244
hamano-2    0.107557      0.004302
inada-n_16  0.116348      0.004653
inada-n_8   0.137042      0.005481
続きを読む
klab_gijutsu2 at 08:00|この記事のURLComments(0)TrackBack(0)
2008年07月31日

社内コードコンペ - お題:最速なCIDRブロックマッチ判定〜 hamanoの場合: あ ありのまま 今 起こった事を話すぜ!『コードコンペだと思ったらゴルフコンペだった』な(ry 〜

はてなブックマークに登録

おさらい


はじめに

社内 irc で盛り上りを見せている、IPv4 アドレスの判定問題に取り組んでみました。

まず既にある実装としては、CPAN モジュールの IP::Country という実装がある様で、この実装は、判定データから2分木を構築し 1ビットずつ遷移して行くという実装のようです。

IPv4 に限定すると 1 bit ずつの判定でも高々 32回の参照になるのでこの時点ですでに O(1) なのですが、メモリをたくさん使用する代わりにもっと早い実装を考えてみると IPv4 であれば 4G のテーブルを用意しておけば、たった 1度の参照で判定出来ます。

このことから早さとメモリ空間のトレードオフとなる、この2つのアルゴリズムの間で今回のデータ量に適したところを探っていくことにしました。

実装1:このコードのウリ

まず実装が簡単そうな 1オクテットずつ遷移する実装を行ってみました。データ構造は以下のような感じで、この図では 192.168.1.2 を sakanaya の ネットワーク範囲として判定するケースを表しています。

この様なテーブルを構築しておく事で 4回の lookup で判定することが出来ます。メモリの使用量は short * 256 のテーブルが300 個程度ですので 150k でした。

実装1:コード解説

判定のコードはこんな感じになりました。

const char *cidr_lookup(unsigned char *addr, int len)
{
    return type[tab[tab[tab[tab[1][addr[0]]][addr[1]]][addr[2]]][addr[3]]];
}

そう、実はこのコードコンペ。アルゴリズムは最初から O(1) なので、アルゴリズムではなくコード(命令数)の短さが速さを決定する、ゴルフコンペだったのです。

実装1:ベンチマーク

x86

name        elapsed[sec]  average[usec]
========================================
apr        59.379924      2.375197
ip-country  3.739187      0.149567
yasui-a     2.727045      0.109082   # インラインアセンブラ
yasui-c     0.975544      0.039022   # C言語
hamano-1    0.234664      0.009386560

実装2:このコードのウリ

最初の実装で十分早かったのですが、この頃には細部までチューニングされたもっと早い実装が登場してきていたので、こちらも負けずとチューニングを行ってみることにしました。

次の実装はもう少しメモリを使用して大きなテーブルを使うことにしました。

この実装は、最初の bigtable でメモリを 32M 使用しますが、lookup が 2 回で済むの以前の実装より早くなりました。

実装2:コード解説

判定のコードはこんな感じです。ネットワークオーダーでの下位 24bit と残りの1オクテットが使いたかったので。union を定義しています。

typedef union{
    uint32_t all;
    unsigned char o[4];
}addr_t;

const char *cidr_lookup(addr_t *addr, int len)
{
    return type[tab[bigtab[addr->all & 0xffffff]][addr->o[3]]];
}

実装2:ベンチマーク

x86

name        elapsed[sec]  average[usec]
========================================
apr        59.379924      2.375197
ip-country  3.739187      0.149567
yasui-a     2.727045      0.109082   # インラインアセンブラ
yasui-c     0.975544      0.039022   # C言語
hamano-1    0.234664      0.009386
hamano-2    0.142496      0.005700

x86_64

name        elapsed[sec]  average[usec]
========================================
apr        52.340651      2.093626
ip-country  0.664034      0.026561
yasui-c     0.706095      0.028244
hamano-2    0.107557      0.004302

とうとうマシン語にして 10 ステップ程度となり、これ以上の最適化は大変そうなので、ここで断念することにしました。

最後に、この実験で使用したコードを載せておきます。探索以外の部分のコードはあまりキレイに書けていませんがご了承くださいm(--)m

続きを読む
klab_gijutsu2 at 08:00|この記事のURLComments(0)TrackBack(0)
2008年07月30日

社内コードコンペ - お題:最速なCIDRブロックマッチ判定 〜 安井の場合: バイナリサーチのあれとこれ〜

はてなブックマークに登録

おさらい

前回に引き続きコードコンペのお話で、今回は安井の出番です。 前回は導入だったせいもあり、あまり速いコードはできてきませんでしたが、さてさて今回はどうでしょうか。


このコードのウリ

「IPアドレスのマッチング」とは、言い替えれば「32ビット値の検索」です。そこで私の中で真っ先に頭をよぎったのは、バイナリサーチ(二分探索)という手法でした。今回のネタはデータ数が300個弱ということなので、 IP::Country のようにビット単位で二分木検索するよりも、ソート済みのリストからバイナリサーチしたほうが計算量は少なくて済むだろうと考えました。

コード解説

泥臭い処理(ファイルからCIDRブロックを読み込んでソート済みの配列を生成する部分)は末尾に掲載します。 ここでは、ソート済みのCIDRブロックリストから、IPアドレスを検索する関数を紹介します。(とはいってもある種お決まりのコードですけどね(^^;

cide_lookup()

char *cidr_lookup(void *ipaddr, int len)
{
  int half;
  int cmin = 0;
  int cmax = listcount;
  uint32_t addr;

  if(len != 4)
    return(NULL);
  addr = ntohl(*(uint32_t *)ipaddr);

  /* バイナリサーチで範囲を絞りこむ */
  while(cmax - cmin > 7){
    half = (cmin + cmax)>>1;
    if(addr < cidrlist[half]){
      cmax = half;
    }else{
      cmin = half;
    }
  }

  /* 絞りこんだ結果((最大7個)の中からマッチするものを探す */
  while(cmin<(cmax--)){
    if((addr & masklist[cmax]) == cidrlist[cmax]){
      return(typelist[cmax]);
    }
  }
  return(NULL);
}

通常のバイナリサーチの実装では、検索終了条件を以下のようにすると思います。

  • 目的の値が見付かったとき
  • (cmin == cmax)になっても目的の値が見付からなかったとき
cidr_lookup()では、検索要素数が7個未満になった時点でバイナリサーチを中断し、残りの要素をリニアサーチして結果を返すようにしています。それはなぜかというと、

  • 配列に格納されているのはCIDRブロックのネットワークアドレスなので
    • 検索対象のIPアドレスとの同値データは存在しない
    • ネットマスクとのANDをとらなければマッチしているか判定できない
  • ネットワークアドレスが同じでネットマスク長が異なるケースが考えられる
    1. 192.168.0.0/16
    2. 192.168.0.0/17
    3. 192.168.0.0/18
  • このような場合、192.168.0.1は(3)にマッチしなければいけない
という理由があるためです。そこで、リストの絞りこみにバイナリサーチを利用し、絞りこんだ結果からネットワークアドレスが一致する要素を検索するようにしました。今回の例ではCIDRブロックの数が512個未満なので、バイナリサーチのループ回数は以下の通り7回となります。
検索回数
検索要素数
1
511
2
255
3
127
4
63
5
31
6
15
7
7
そして、残った7個のCIDRブロックに対してネットワークアドレスのマッチングをすればよいので、最大でも14回の数値比較で結果を得ることができます。これならば、32ビットの二分木検索(IP::Country)よりも計算量は少なくて済むはずです。

アセンブラでも書いてみた

もう、だいぶ昔の話になりますが、アセンブラ(6502,Z80,68000)で遊んでいた時期がありました。ちょうどそのころ、バイナリサーチ、バブルソート、クイックソートなどの「アルゴリズム」と呼ばれるものにはじめて遭遇し、「これはすごい!」と純粋に感動していたことを覚えています。

その記憶が甦ったのか、なにを血迷ったのかわかりませんが、なぜかふと、「cidr_lookupをアセンブラで書き直せばもっと速くなるんでね?」と思い、インラインアセンブラで書き直してみたのがこちらのコードです。処理の内容は上記のものとまったく同じです。

そして、それぞれでベンチマークをとってみたところ、このような結果になりました。
※gccの最適化オプションは-O3を指定しました。

結果をみてびっくりしました。Cで書いた方が圧倒的に速かったのです。 アセンブラで書いたコードは、そのままでは64bit環境で動かないですし、メンテナンス性もわるいですし、コーディングにも時間がかかります。それでも高速に動作すれば使いどころはあるかなあと思っていましたが、今回は少し残念な結果に終わってしまいました。コンパイラの最適化ってすごいです!さすがです。

おわりに

今回の件で、単純にアセンブラで書き直しただけでは速くならないことを体感しました。しかし、このアセンブラのコードも、まだまだ高速化できる余地がいっぱい残っています。(というか、ツッコミどころ満載かもしれません(^^;;

どれだけコンパイラに近付くことができるかわかりませんが、もっと速くなるようにもう少しいじってみたいと思います。「この辺をこうしたら速くなるぞ」みたいなアドバイスをいただけると、大変ありがたいです。


ベンチマーク

5つのとあるIPアドレスのそれぞれについてどのグループに属するか判定する、という処理を5,000,000回実行したときの総所要時間(elapsed)と1回の判定に要した時間の平均(average)です。

ベンチマークは、同じハードウエアのx86とx86_64の環境の2つでとりました。

x86

name        elapsed[sec]  average[usec]
========================================
apr        59.379924      2.375197
ip-country  3.739187      0.149567
yasui-a     2.727045      0.109082   # インラインアセンブラ
yasui-c     0.975544      0.039022   # C言語

x86_64

name        elapsed[sec]  average[usec]
========================================
apr        52.340651      2.093626
ip-country  0.664034      0.026561
yasui-c     0.706095      0.028244
続きを読む
klab_gijutsu2 at 08:00|この記事のURLComments(0)TrackBack(1)
2008年07月29日

社内コードコンペ - お題:最速なCIDRブロックマッチ判定 〜 ひろせの場合 - IP::CountryとAPRを使ってみた 〜

はてなブックマークに登録

突然始まった社内コードコンペ

ある晴れた日のことです。 「とあるIPアドレスが、 予め与えられている複数のCIDRブロックのどれかに含まれるかどうか」、 を判定するロジックを書こうとしていました。

どうせならばと、いくつか違った方法で実装してみてベンチマークをとって最良のものを採用しようと思い、いく通りかの実装方法を考えてみました。この方法は速そうだけどメモリ消費が多そうとか、この方法は明らかに遅いけど一応実装してみるかーなどなど。

ってなことを社内IRCであーでもないこーでもないとひとりつぶやきながらコードを書いていたところ、案の定、興味を持った何人かが釣れました。フフフ。

そんな流れで釣れたエンジニアを巻き込んで、お題についてコードを書いて競う社内コードコンペがはじまりました(ちなみに、優勝賞品はカレーです)。

お題自体はそれほど複雑なものではないのですが、書く人によって意外と趣向が違ったりしておもしろかったので、 本エントリも含めこれから何回かにわけて、参加者自らが自分のコードの解説や自慢をするエントリをお届けしたいなと思います。

お題

まず、お題についてまとめておきます。

  • 『グループ』は複数のCIDRブロックから成り立っています
  • 『グループ』は複数あります
  • とあるIPアドレスが、どの『グループ』に所属するかを、当該グループのいずれかのCIDRブロックに含まれるかどうかで判断する、というのがお題です。
  • もし、グループを越えて含まれるCIDRブロックが複数ある場合は、よりネットマスクが長いものを採用します。
  • ベンチマークでは、CIDRマッチ処理の部分のみを計測対象とし、初期化処理は測定対象には入れません

具体例はこんな感じです。

2つのファイル、yaoyaとsakanayaがあり中身はこうだとします。

$ cat yaoya
172.16.0.0/16

$ cat sakanaya
10.0.1.0/24
10.1.1.0/24
10.2.1.0/24

そして、検査対象のIPアドレスが10.1.1.1だとします。

このIPアドレスは、sakanayaの2つめのCIDRの10.1.1.0/24に含まれるので、グループsakanayaに属している、ということになります。

本データでは、グループ数が20個程度、総CIDRブロック数が270個程度です。つまり、それほど大きなデータではありません。


このコードのウリ

というわけで、第1回はひろせのコードです。こんにちは。

モットーはいかにコードを書かないで済ますかwで、既存の実装の流用やライブラリを使って書いてみました。

最初にお伝えしておくと、わたしのコードがいちばん遅かったです。壊滅的に遅かったです。次回以降はびゅんびゅんに速いコードが出てきますので、今回は導入程度と思っていただき、おもしろげなコードは次回以降にご期待ください。

コード解説

今回は2種類紹介します。APRを使ったものと、IP::Countryのコードを流用したものです。

共通部分

まずは共通部分のコードを。次回以降もこの部分は共通です。

cidr_initialize()で初期化処理をして、cidr_lookup()でマッチ判定をやります。 cidr_loopupには、コマンドの引数で指定されたIPアドレスをstruct in_addrに変換して渡しています。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <sys/socket.h>
#include <netinet/in.h>

#include <arpa/inet.h>

void  cidr_initialize();
char *cidr_lookup(void *ipaddr, int len);

int main(int argc, char *argv[]) {
  int i, j;
  int nipaddr = argc - 1;
  char *label;
  struct in_addr addrs[nipaddr];

  if (argc < 2) {
    fprintf(stderr, "missing argument\n");
    return -1;
  }

  nipaddr = argc - 1;
  for (i=0; i<nipaddr; i++) {
    int ret = inet_aton(argv[i+1], addrs+i);
    if (!ret) {
      fprintf(stderr, "bad address: %s", argv[i+1]);
      return -2;
    }
  }

  cidr_initialize();
  for (j=0; j<nipaddr; j++) {
    label = cidr_lookup((void *)&addrs[j].s_addr, 4);
    printf("result: %s = %s\n", argv[j+1], label);
  }

  return 0;
}

 

その1 APRのapr_ipsubnet_test

長いわりには見るところが少ないので、コードは末尾に掲載します。

初期化関数のcidr_initialize()では、CIDRのデータファイル群を読んで、APRの関数apr_ipsubnet_create()でcidrlist[]を用意しています。

判定関数のcidr_loopup()では、cidrlist[]のそれぞれについて、マッチするかどうかapr_ipsubnet_test()を使って判定しています。

このあたりの処理は、実はApacheのAllowやDenyディレクティブで、CIDRブロックが指定された場合のと同じです。

さてさて、このコードはかなり遅いです。
APRのAPIを使う以上、初期化処理などが必要なのは仕方ないのですが、それよりなにより判定処理がリニアなので、CIDRブロックの数が多くなればなるほど遅くなるのは火を見るより明らかです。

なのでこのコードは、最速を目指しているのではなく、比較用にApacheのAllow, Denyと同じ実装のものを用意してみた、といった位置づけと思ってください。

参考:

 

その2 IP::Country

お次は、PerlのモジュールであるIP::Countryからロジックを拝借したものです。

IP::Countryは、IPアドレス帯と国名の対応データベースを元に、とあるIPアドレスがどの国に割り当てられているかという情報を返すものなのですが、これのデータを差し換えて、今回のお題に使っちゃおうというのが魂胆です。

さて、IP::CountryにはIP::Country::Fastというものが含まれていて、これはどんな処理をするかというと、CIDRを(最大で)32bitのビットの並びとしてみて、0と1で二分木を構築しておきます。で、判定処理をするときは、この二分木を辿ってリーフから国名を取り出します。

末尾にベンチマークの結果を掲載しますが、APRのに比べると段違いで速いです。 採用するのはこのコードでいいかなーと思っていたのですが、コンペ参加者によりこの記録はあっさりと抜かれることとなります...

参考:

おわりに

今回のコードはなんのヒネリもなく、面白味という点ではちょっと物足りなかったのではないかと思います。が、今回は導入ということでご容赦いただき、次回以降にご期待いただければ!と思います。

ベンチマーク

5つのとあるIPアドレスのそれぞれについてどのグループに属するか判定する、という処理を5,000,000回実行したときの総所要時間(elapsed)と1回の判定に要した時間の平均(average)です。

ベンチマークは、同じハードウエアのx86とx86_64の環境の2つでとりました。

x86

name        elapsed[sec]  average[usec]
========================================
ip-country  3.739187      0.149567
apr        59.379924      2.375197

x86_64

name        elapsed[sec]  average[usec]
========================================
ip-country  0.664034      0.026561
apr        52.340651      2.093626
続きを読む
klab_gijutsu2 at 08:00|この記事のURLComments(1)TrackBack(0)
2008年02月19日

サタデーにコードをフィーバーしてきました!

はてなブックマークに登録

先週の土曜日(2/16)にウノウさんで開催されたサタデーコードフィーバーというイベントに参加させて頂きました。普段は会社の自分の席でコードを書くことが多いわけですが、やはりメールが気になったりチャットが気になったりと様々な誘惑(?)があって思うように進まない事があります。まあ、家にいても会社にいても誘惑はそれぞれあるわけで、私にとってもっとも集中してコードが書ける環境は、実は通勤途中の電車の中だったりします。(ちなみに、先日公開したrepcachedの大半は電車の中で書いたというのは内緒です(笑)

そんなわけで、気分をかえてウノウで趣味の開発してみませんか? のエントリを見た瞬間、迷わずメールを出していました。

続きを読む
klab_gijutsu2 at 07:00|この記事のURLComments(0)TrackBack(0)
2007年06月19日

オープンソースを楽しむエンジニア達のこだわり 〜 デバッグ情報を得る

はてなブックマークに登録

前回、ftrace で引数を表示するためにスタックフレームの位置を得る方法を 紹介しましたが、実際に引数の値を得るためにはプロトタイプ情報(引数の数 や型情報)が必要になることが解りました。

通常通りコンパイルした実行バイナリファイルには変数の型情報は含まれてい ませんが gcc のコンパイルオプションに -g を付けるとオブジェクトファイ ルに型情報を含め、様々なデバック情報を含めることが出来ます。今回はこのデバッグ情 報の詳細と利用する方法について紹介してみたいと思います。

続きを読む
klab_gijutsu2 at 14:15|この記事のURLComments(0)TrackBack(0)
2006年10月30日

PHP Extension を作ろう第2回 - 引数と返値

はてなブックマークに登録

前回の Hello World のサンプルプログラムで一通りの PHP Extension の作成手順を見てきました。しかし helloworld() の様に引数も返値も無い関数だけではプログラミング言語として不便ですので今回は PHP と PHP Extension におけるデータタイプの詳細と引数、返値の渡し方について見ていきましょう。
続きを読む
klab_gijutsu2 at 14:35|この記事のURLComments(0)TrackBack(0)
2006年10月26日

PHP Extension を作ろう第1回 - まずは Hello World

はてなブックマークに登録

PHP で汎用的なライブラリを作成するフレームワークには大きく分けて2種類あるようです。
ひとつは PEAR のように PHP でクラスライブラリを作る方法、もう一つが今回紹介する PECL の様に PHP 自体を拡張するモジュールを書く方法です。

  • なぜ PHP Extension ?


  • ひとつは、過去に C で書かれた既存のライブラリを流用したい場合に PHP Extension を作成すれば自然に PHP のコードに結合することが出来ます。また、PEAR の様に PHP で書いたコードと比べると若干高速になります。

    続きを読む
    klab_gijutsu2 at 21:33|この記事のURLComments(0)TrackBack(5)
    2006年08月04日

    [補足記事]Apache 2.0 の hook 一覧(apache module 開発事初め その3-3)

    はてなブックマークに登録

    先日この記事において hook の呼び出しに関してコメントを頂きました.
    実際のところよく分かってない部分もあったので,hook に関してまとめてみました.続きを読む
    klab_gijutsu2 at 21:11|この記事のURLComments(2)TrackBack(1)
    2006年07月27日

    [補足記事]ディレクティブ処理関数登録マクロ一覧 (apache module 開発事初め その3-2)

    はてなブックマークに登録

    前回の記事で後回しにした AP_INIT_XXX() シリーズの一覧です.続きを読む
    klab_gijutsu2 at 17:09|この記事のURLComments(0)TrackBack(0)
    2006年07月21日

    ディレクティブの処理と設定値の利用 (apache module 開発事初め その3)

    はてなブックマークに登録

    今回は前回の記事で予告した通り,Apache の(いくつかのタイプの)モジュールが動作するべきか否かをどうやって判断するか,というお話です.タイトルは「ディレクティブの処理」となっていますが,モジュールがディレクティブを処理することと今回のテーマは密接に結びついています.

    続きを読む
    klab_gijutsu2 at 21:22|この記事のURLComments(7)TrackBack(0)
    2006年07月14日

    アクセス制御モジュールを作ってみる (apache module 開発事初め その2)

    はてなブックマークに登録


    前回の記事では,apxs が生成したテンプレートをそのまま動かしてみましたが,今度は少しコードを書いてみましょう.同じ handler を作っても面白くないので,アクセス制御をするモジュールにしてみます.Apache のアクセス制御は2種類あって,一つはユーザ認証を目的としたもので,mod_auth の眷属がそれです.もう一つはリクエストの別の側面,例えばクライアントのアドレスによってアクセスを許可したり拒否したりするもので,標準モジュールでは mod_access がそれに当たります.あまり複雑なことをしても話が見えにくくなるので,今回作るモジュールではランダムにアクセスを許可したり拒否したりすることにします.

    続きを読む
    klab_gijutsu2 at 18:31|この記事のURLComments(4)TrackBack(1)
    2006年07月12日

    apache module 開発事始め

    はてなブックマークに登録


    先日は,必要に迫られて Apache 1.3 の mod_access を改造したというを書きました.その時は単にあるものを改造しただけでしたが,ふと思い立って,一から Apache 2.0 用のモジュールを書いてみました.書く上で色々 Web サイトを探してみたのですが,あまり日本語の入門向けの文章が見あたらなかったので,開発する上で分かったこと(と言うほど大したものじゃないですが)をまとめておこうと思います.

    続きを読む
    klab_gijutsu2 at 22:52|この記事のURLComments(6)TrackBack(1)
    Blog内検索
    このブログについて
    DSASとは、KLab が構築し運用しているコンテンツサービス用のLinuxベースのインフラです。現在5ヶ所のデータセンタにて構築し、運用していますが、我々はDSASをより使いやすく、より安全に、そしてより省力で運用できることを目指して、日々改良に勤しんでいます。
    このブログでは、そんな DSAS で使っている技術の紹介や、実験してみた結果の報告、トラブルに巻き込まれた時の経験談など、広く深く、色々な話題を織りまぜて紹介していきたいと思います。
    最新コメント
    最新トラックバック
    Archives