開発

2022年01月14日

KLabサーバーサイドキャンプを開催しました

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

12/27 から年末年始をはさんだ5日間で、技術系インターン「KLabサーバーサイドキャンプ」を開催しました。 今春3月に第2回も企画しているので、 その宣伝も兼ねて開催報告をします。 (尚、エントリー最終締切日が1/24(月)に迫っているので興味を持って頂けた方はお早めにご応募ください)

キャンプの目的

このキャンプは、主にこれから就職活動を始める学生を対象にサーバーサイド開発を体験してもらい、今後の進路を考える上で参考にしてもらうことを目的としています。 そのため、Pythonでのある程度のプログラミング経験は前提としつつ、SQLやSSHなどを触ったことがない方でも参加できるように講義や課題を準備していました。

キャンプの内容

題材として、実際に遊べるリズムゲーム(音ゲー)を用意しています。

Screenshot_20220114-174050

このゲームにはユーザー登録機能と、複数人で同一曲を同時にプレイする機能があります。この2つの機能のために、参加者にはサーバーサイド・アプリケーションを実装してもらいます。

キャンプで利用する技術スタック

Codespaces

開発環境として GitHub Codespaces を利用しました。 Codespacesのおかげで、参加者の利用するOSやターミナル、SSH等に依存せずに、すぐに開発に取り掛かれる環境を用意できました。 初日はとりあえず環境を動かして軽く触るまでにする予定だったのですが、全くトラブルが起きなかったので2日目の講義の一部を急遽前倒しで実施することになったほどです。

Codespacesは現在のところ個人利用が限定ベータ版ですが、申し込みして有効になれば無料で利用できます。参加者はキャンプ終了後も自分のリポジトリでCodespaceを作り直して開発を続けることができます。

Python & FastAPI

言語はKLabのサーバーサイドでも使われている言語であるPythonを使いました。 一方で、フレームワークはKLabで使っているFlaskではなく、APIサーバーに特化したフレームワークとして FastAPI を選びました。 理由は、人気があり、とっつきやすいことです。特にType hintingを使って定義したデータモデルを使ってシリアライズとデシリアライズを自動でしてくれるので、複雑なことをしないのであればコントローラー部のコードがとても少なくて済みます。

MySQL

キャンプで一番体験してもらいたかった事がSQLを使った開発だったので、KLabが主に利用しているMySQLを使いました。 CREATE TABLE, INSERT, SELECT, UPDATE, DELETE 文などごく基本的なクエリの文法を講義で紹介し、参加者には自力でクエリを書いてもらいました。

また、講義ではインデックスやロックの必要性や適切に扱う難しさを紹介しました。実装が早かった参加者は、実際にそこまで挑戦されていました。サーバーサイド開発者が普段どういった問題を考え解決しているのか、少しでも伝わったら幸いです。

SQLAlchemy Core

SQLを読み書きする体験をしてもらいたかったので、ORMは使いませんでした。 しかしPythonからMySQLへ接続する低レベルのライブラリを直接使うのはさすがに問題があるので、SQL toolkitとして SQLALchemy の Core 部分だけを利用しました。

IPythonとmysql (シェル)

初めての使う技術を学びながら開発するためには、試行とフィードバックのサイクルを高速に回せるインタラクティブシェルが役に立ちます。 SQLを書くために mysql コマンドのシェルを、SQLAlchemyの使い方を調べるために ipython を使ってもらいました。

題材になったゲームについて

このキャンプのアイデアを持ちかけられたとき、「僕だけではショボいものしかできないから、ある程度見栄えのするゲームを作ってほしい」と返事していました。

すると、本当にゲーム開発者がそのために音ゲーを作成してくれました。さらにクリエイティブ部門も巻き込んで社内コンペが行われ、デザインやかわいいキャラクターまで作り込んでもらいました。関わってくださった皆様、本当にありがとうございます。

このゲーム単体で配布しても多くの人に楽しんでもらえそうなクオリティなのですが、残念ながらサーバーサイドとセットにならないと動かすことができません。このゲームは参加者だけの特典になります。

参加者の反響

参加者に書いていただいたBlog記事を紹介します。

また、キャンプ中の様子を #KLabServerSideCamp というハッシュタグをつけてツイートしてくれています。

感想

Codespacesの環境構築はいまいちベストプラクティスがわからずかなり試行錯誤しましたが、参加者が環境構築でつまづくことがなく、キャンプ終了後もCodespacesが利用できれば簡単に同じ環境を使えるので、採用して大正解でした。

音ゲーは本当によくできていて、音ゲーが好きな参加者が実装の間に(実装そっちのけで?)やりこんでくれていました。社内でたくさんの人を巻き込んで作ってもらったので、楽しんでもらえて良かったです。

あと、普段はSound Onlyでしかミーティングしてないので、インターン最終日の懇親会で、ビデオ通話で愛犬を見せびらかせたのが個人的に良かったです。

講義資料に足りない点があったり、APIを叩いて結果をprintするだけのテストコードにリクエストパラメータが1つ足りなかったりして、幾つかつまづきの原因を作ってしまったのが私の反省点です。 年末年始で忙しい中、一緒にサポートしてくれた開発者のメンバーはありがとうございました。

第2回について

冒頭で述べた通り、今春3月中旬ごろに第2回を計画しています。この記事や、参加者のBlog、ツイートを見て興味が湧いた方はぜひご応募ください。(エントリー最終締切日は、1/24(月)23:59までです)

第2回 応募ページ


@methane

songofacandy at 17:51|この記事のURLComments(0)
2019年09月03日

第一回 KLab Expert Camp「TCP/IPプロトコルスタック自作開発」を開催しました

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

KLab Expert Camp というイベントを8/26〜29の4日間で開催しました。

KLab Expert Camp とは

KLab Expert Camp は、技術的に深いテーマに取り組んでいる学生の発掘・育成を目的とした KLab の新しい取り組みです。
記念すべき第1回のテーマは「TCP/IPプロトコルスタック自作開発」で、以下のような触れ込みで開催しました。

「OSを作ってみたい」「コンパイラを作ってみたい」と思う人が多いように「プロトコルスタックを作ってみたい」と思う人も多いのではないでしょうか。今回の KLab Expert Camp のテーマは、そんな皆さんにピッタリの「TCP/IPプロトコルスタック自作開発」です。担当講師が開発している教育用のプロトコルスタック(https://github.com/pandax381/microps)を教材に、Ethernetフレームを組み立てて送受信するところから ARP、IP、ICMP、UDP、TCP などのプロトコルを全て自分の手で実装することで、これまでブラックボックスだったプロトコルスタックの処理を紐解いていきます。

参加にあたっては、開発環境やプログラミング言語に関する初歩的な知識は身につけていることを期待していますが、期間中は KLab の講師陣が手厚くサポートしますのでご安心下さい。また、意欲的な参加者においては、期間中に追加機能の実装や組み込み機器への移植などへのチャレンジングな取り組みも支援します。

また、参加者には各自の取り組みたい内容に応じて2つのコースの何れかを選択してもらう形をとりました。

【基本コース】 教材となるリファレンス実装の解説を通じてプロトコルスタックそのものへの理解を深める

【応用コース】 リファレンス実装の別言語への移植や機能追加など各自がテーマを決めて取り組む

開催の経緯

定期的にこんなツイートをしながら、年に1〜2人のペースで前途有望な学生を低レイヤ沼に引きずり込んでるんですけど、たまたま5人くらいの学生が同じタイミングでリアクションしてくれまして。それだけの反響があるのは嬉しいものの、個別に対応してあげるのはおじさんの体力的にちょっと厳しそうだなという感じもあって「もういっそのこと全員集めて一緒にやればいいのでは???」という考えに至ったわけです。

そして、インターン関連をとりまとめている人事の担当者に「こんな感じで何人か集めてやりたいんだけど」と雑に話をしたところ「イイっすね!なんならもう少し集めてイベントにしちゃいます???」みたいな凄いノリの良い返事をもらって、1週間くらい経ったら「例のイベントの企画、Go出ました!」と、あっさり開催が決まってしまった感じです。

取り急ぎ告知に向けてイベントの名称を決めようということになったのですが、これが結構難しくて... パッと思いつくものはだいたい既に他で使われてるんですよね。Expert Camp は僕の出した案なんですけど「Expert...ちょっとイキりすぎでは...?」みたいな意見もあったりして。最終的には「カッコ良さそうだからいいじゃん」「僕(自称)エキスパートだから無問題」という感じで落ち着きました。

そんなこんなで漕ぎ着けたイベント告知が以下のツイートです。

万人に向けたイベントでもないし、SNSを通じてニッチな層に届けばいいやくらいの軽い気持ちだったので、イベントの告知は僕の個人アカウントによる上記のツイートのみです。 この時点ではマジでどのくらい集まるのか未知数で「追加で数名集まったらわいわい楽しくできそうだけど、果たして応募してくれる人はいるのだろうか...」と不安な気持ちでいっぱいでした。

そんな不安をよそに、つよつよの学生達や「拙者、この分野は素人でござるが」みたいなこと言い出しそうな強い大人の方々にもRTされ、それなりに拡散されることになりました。面白そう!と反応してくれたみなさん、本当にありがとうございました。

そして、いざ蓋を開けてみると総勢20名以上の学生がエントリーしてくれ、最終的に13名の参加者が決まりました。 募集しておいてなんですが「世にはプロトコルスタックを自作したい学生がそんなにいるのか...」と正直びっくりしましたね。

(多数エントリーいただいて嬉しかった一方で、運営のリソース的に希望者全員を受け入れることができず、参加者を絞らなければならなかった点はすごく心残りです。残念ながら今回は参加できなかった方も次回の開催につなげることができたらその際はまたエントリーして欲しいなと思います)

開催までの準備

告知から開催まではちょうど4ヶ月くらいあったので、そのあいだに人事の担当者と細かなことを決めつつ準備を進めていきました。といっても、僕が雑に「あれやりたい」「これやりたい」と言ったものを、イベント慣れしている人事の担当者がよしなにアレンジして的確に落とし込んでくれるという連携プレーで進めていきました。だいぶ無茶振りもしたと思うのに、いい感じでまとめてくれて本当にありがとうございました。

以下は個人的に気に入っていて満足しているポイントです。

  • 参加者と運営メンバー全員分のIDカード(プラスチック製)
  • お昼のお弁当
  • 最終日に授与した修了証
IMG_1449

どれも過去に自分が参加したり運営に携わったイベントで「これ良かったなぁ」「嬉しかったなぁ」と印象に残っていたものを盛り込んでもらいました。 参加者からのアンケートでも「お弁当おいしかった!」とか「記念に残るものがもらえて嬉しかった!」とか、それなりに喜んでもらえていたようで、すごく嬉しいです。

あとは、教材として使う予定の「リファレンス実装」をもう少し理解しやすい作りに改良したり、解説用の資料を作ったりと、なかなか忙しくギリギリまで準備を進めていました。

イベント期間中の様子

運営スタッフや参加者が以下のハッシュタグを付けてツイートしてくれているので、これらのタイムラインを追ってもらうと、どんな雰囲気で開催されていたのか分かる思います。(ごはんのツイートが多いので飯テロ注意)

#KLabExpertCamp

#プロトコルスタック自作

開催してみて

まず、これだけの人数の参加者に集まってもらえたことが驚きと共に一番うれしかったです。そして、皆さん起床ミッションに失敗することもなく初日から最終日まで黙々と開発に取り組んでくれていたのが本当に凄いと思いました。

あと、このイベントを開催した目的のうちの1つでもあるんですけど、参加者同士の交流が活発に行われていたようで良かったです!尊い。いや、これまで個別にインターン生として受け入れていた学生達とのやり取りの中で「ニッチな分野になるとなかなか周りで同じレベル感で話せる友達や仲間がいなくて寂しい(とくに地方の場合)」という話が上がることが多かったんですよ。なので、今回のイベントでは全国各地から同じニッチな分野に興味を持っている学生が集まる絶好の機会だし、そういった交流の場としても機能して欲しいなと思っていたのでした。

このイベントに参加して「TCP/IPを完全に理解した」となった方、その先に進んで「TCP/IPまるでわからん」となった方「TCP/IPチョットデキル」の域に達した方、得られたものはそれぞれ異なると思いますが、参加者全員に「楽しかった」と思ってもらえていたら開催した甲斐があったかなと思うし、第2回はもっとクオリティ高くヤルぞ!という気持ちになります。

謝辞

もともとこのイベントは僕が一人で講師を務めるつもりで企画がスタートしたのですが、予想を上回る参加人数となったことから、社内のエンジニアに協力を仰いで講師やサポート役を引き受けてもらいました。

また、社内からだけではなく外部の方にも講師役を引き受けて頂きました。

ねりさんはプロトコルスタック自作クラスタとして以前から認識していて、#tcfm のミートアップでのLTやサイボウズ・ラボユースでの活躍を見て「ヤバイ人がいる」とウォッチしていたのですが、こんな雑な絡み(なんとこれが初コンタクトなんですよ)にも関わらず、快く引き受けていただき本当にありがとうございました。

僕はR&D部門に所属しているものの、学問として研究をしたことがないため、研究者の立場として参加者に対してアドバイスや相談に対応してくれていたのはものすごく心強かったし、めちゃくちゃカッコいいなと感じました。

他にも、めんどくさい細々としたタスクを含めキッチリこなしてくれた人事の担当者や、仕事の合間にIDカードのデザインを引き受けてくれたデザイナーさんなど運営に関わってくれたみなさん、ほんとうにありがとうございました!

参加者のブログ記事

最後に、観測できている範囲で参加してくれたみなさんが書いてくれたブログ記事へのリンクを貼っておきます。

TCP/IP プロトコルスタックを自作した - kawasin73のブログ

KLab Expert Campに参加したよ。 - よくきたわね、いらっしゃい

KLab Expert Camp に参加しました - veqcc’s diary

KLab Expert Camp にチューターとして参加した - Around The Computer

KLab Expert Campに参加してきました - teru_0x01.log

KLab Expert Campに参加した - 抹茶うまい

第1回 KLab Expert Campに行ってきました(TCP/IPプロトコルスタック自作インターン) - 迫真の氷結晶

pandax381 at 18:23|この記事のURLComments(0)
2017年12月25日

外部向け HTTP 通信の再送検知ツールを作った話

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

このエントリは KLab Advent Calendar 2017 の最終日の記事です。

こんにちは。インフラ担当 高橋です。

このエントリでは、つい先日、少し変わった仕組みの外部向け HTTP 通信の 3way ハンドシェイクの再送検知ツールを作りましたのでご紹介します。

きっかけ

このツールを作ったのは、DSAS の外部で発生するネットワーク障害を検知できるようにするためです。

例えばこのような障害がありました。

DSAS は複数のデータセンタで稼働しているのですが、ある日、特定データセンタの Web サーバから外部 API への接続が重くなる事象が発生しました。

原因は外部ネットワークからの DDoS 攻撃により、データセンタのネットワークの一部区間が飽和状態になったことによるものでした。

外部ネットワーク障害 その1

またある日は、特定のデータセンタの Web サーバから外部の特定 API に接続ができなくなりました。

原因は外部ネットワークの途中経路の ISP で伝送装置が故障したことで、経路変動が発生し、通信が不安定になったことによるものでした。

外部ネットワーク障害 その2

このように DSAS 外部で発生するネットワーク障害の原因は様々であり、対応も状況によって都度変化します。DSAS 内のネットワーク、データセンタの回線、その先の途中経路、外部 API のサーバなど、切り分けしなければならない箇所は多くあります。

特に途中経路の障害というのは、データセンタの回線や外部 API には問題が発生しておらず、障害箇所の切り分けにも時間がかかります。

このような障害はサービスへの影響に直結するため、インフラ担当はできるだけ早く障害に気づき、対応を開始しなければなりません。

そのため、インフラ担当が DSAS 外部で発生するネットワーク障害を検知できる仕組みを導入することにしました。

どのようにして検知するか

障害を検知するには、障害が発生しそうな箇所を想定し、そこを監視する必要があります。

DSAS 内部とは異なり、DSAS 外部で発生するネットワーク障害の原因は千差万別で、且つ監視できる箇所は限られてきます。

何を検知するか

まずは、先ほど例に挙げた障害を振り返ってみることにします。

このような障害の場合、DSAS のサーバやスイッチは正常なためアラートは発生しません。案件担当からの「外部 API の応答が遅い、もしくはタイムアウトしてエラーになる」といった問い合わせがきっかけで障害に気づくことになります。

つまり、外部 API への HTTP 接続の応答が遅くなったり、タイムアウトが発生していることをきっかけに障害を検知しているということになります。

それでは、外部 API への HTTP 接続の応答時間が長ければネットワーク障害が発生しているかというと、外部 API の処理に時間がかかっている可能性もあり、そうとは言い切れません。

このような障害が発生すると、インフラ担当は モニタリングシステム (Ganglia) のグラフを確認します。

グラフには HTTP の外向きの通信についての項目があり、該当時刻に Web サーバで SYN パケットの再送が大量に記録されていました。

HTTP 通信の SYN パケットの再送が起きているということは、外部 API に SYN パケットが届かなかったり、外部 API からの SYN/ACK パケットが Web サーバに届かなかったりしている可能性が高いです。

これを監視すれば DSAS 外部のネットワーク障害を検知できそうです。

何を使って検知するか

直接、監視サーバから外部への HTTP 監視を行うには、ヘルスチェックのような監視用 URL が必要になりますが、インフラ担当では用意することができませんので、案件担当と連携して監視対象 URL のリストを作成し、管理しなければなりません。

DSAS では複数案件のサービスが稼働しており、その全ての案件のリストを管理するのは大変ですので、それは避けたいという思いがありました。

それに加えて今回は、HTTP 接続の応答時間やステータスコードではなく、SYN パケットの再送を監視する必要があります。

「監視対象 URL を管理せずに、外部向け HTTP 通信の SYN パケットの再送を検知したい」

この要望を叶えることのできるツールが、意外と身近にあることに気づきました。

モニタリングシステムのグラフ作成に使用している tcpeek です。

tcpeek とは

tcpeek は KLab が作成した 3way ハンドシェイク時に発生するエラーを監視・集計するネットワークモニタで、エラー検出、再送検出、フィルタ、データ出力といった機能を備えています。

GitHub - pandax381/tcpeek: TCP 3way-handshake monitor

こちらのエントリに詳細が書いてあります。

ログからは見えてこない高負荷サイトのボトルネック

再送検出

指定したインタフェースを監視し、タイムアウト時間内に SYN の再送が発生すると SYN Segment Duplicate (dupsyn)、接続先から SYN/ACK が再送されてくると S/A Segment Duplicate (dupsynack) がカウントされます。

タイムアウト時にも再送は発生していますが、tcpeek の再送検出は 3way ハンドシェイク成功時に再送が発生していればカウントされるようになっています。

想定される原因としては、途中経路の帯域の輻輳やパケ落ちなどが挙げられます。

エラー検出

指定したインタフェースを監視し、RST パケットを受け取ると Connection Rejected (reject)、ICMP Destination Unreachable パケットを受け取ると ICMP Unreachable (unreach)、接続がタイムアウトすると Connection Timed Out (timeout) がカウントされます。

タイムアウトについては、アプリケーションによりタイムアウトまでの時間は異なりますので、tcpeek 起動時に指定するタイムアウト時間 (デフォルト 60秒) を超えたセッションは Connection Timed Out としてカウントされるようになっています。

想定される原因としては、接続先の TCP リセット、途中経路のルーティングテーブルの消失、接続先の無応答などが挙げられます。

tcpeek を使った SYN パケット再送検知の仕組み

tcpeek を使えば外部向け HTTP 通信に絞った 3way ハンドシェイクの再送発生 (dupsyn / dupsynack) や接続失敗 (reject / unreach / timeout) の計測値を取得することができますので、そのカウントが増えたらインフラ担当に通知するツールを作成することにしました。

====== TCPEEK SUMMARY ======
----------------------------
 http-out
----------------------------
 success
     total           17457
     dupsyn              3
     dupsynack           0
 failure
     total             113
     reject             39
     unreach            45
     timeout            29
============================

tcpeek は Web サーバで動作しますので計測値は Web サーバで取得することになります。

Web サーバから直接インフラ担当に通知する仕組みだと、多数の Web サーバで HTTP の再送が発生すると通知の数が大量になってしまいます。

そのため、Web サーバの計測値をキャッシュに格納して集約し、検知ツールでキャッシュにある統計情報をチェックする仕組みにしました。

監視の仕組み

計測値のカウントが増えており、その数がしきい値を超えていると slack とメールでインフラ担当に通知します。こちらは slack への通知例です。

slack通知

おわりに

今回、このツールを作る際に一番悩んだのが、通知内容としきい値の設定方法でした。

Web サーバ単位でカウントを通知すると、台数が多いと通知が縦に長くなってしまい、特に slack では扱いづらくなるため、案件単位で通知をまとめるようにしました。

また、Web サーバ毎にしきい値を設定すると、特定の接続先の障害で再送などが発生した場合、何台の Web サーバで再送が発生しているのか状況を把握しづらくなるため、案件の Web サーバ全台の合計カウント数をしきい値としています。

この 2点はまだまだ改善の余地があると思っており、これからもブラッシュアップしていきたいです。

もちろん tcpeek は外部向け HTTP 通信だけではなく、様々な通信のフィルタを作成し集計できますので、他の通信に対してもこの検知の仕組みは適用できます。

takahashi_yo at 12:48|この記事のURLComments(0)
2017年04月14日

Brocade VDX NOS 7.0 は Python が動く!

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

KLab では物理のサーバインフラを複数システム運用していますが、最近そのうちの1つでネットワークスイッチのリプレースを実施しようとしています。新たに導入するスイッチは Brocade 社の VDX6740 なのですが、このスイッチの OS である NOS 7.0 では、なんとスイッチ上で Python を動かすことができます。ということで少し触ってみました。

とりあえず触ってみる

使い方は、 UNIX の shell から Python を使うのと同じ感覚です。まず、通常通りスイッチに ssh などでログインします。

$ ssh -l admin vdx-switch


Welcome to the Brocade Network Operating System Software
admin connected from 192.168.0.10 using ssh on sw01
sw01#
この状態で VDX の CLI コマンドを入力するのと同様に、pythonと入力すれば、python が対話モードで起動します。
sw01# python
Python 3.3.2 (default, Apr 28 2016, 15:57:52)
[GCC 4.3.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>
見て分かるように、バージョンは 3.3.2 です(ちょっと古いですね…)。

探索

普段 Python のスクリプトを利用するのと同様に python コマンドの引数にスクリプトファイル名や -m でモジュール名を指定すれば、対話モードを起動するのではなく、指定した Python スクリプトを動かすこともできます。

sw01# python -m pydoc
pydoc - the Python documentation tool

pydoc ...
Show text documentation on something. may be the name of a
Python keyword, topic, function, module, or package, or a dotted
reference to a class or function within a module or module in a
package. If contains a '/', it is used as the path to a
Python source file to document. If name is 'keywords', 'topics',
or 'modules', a listing of these things is displayed.
(略)

ライブラリ類はどうなっているのか、 python -m pydoc modulesの結果を整形したものを、Linux OS にインストールされていた同じバージョン 3.3.2 の Python のものと比べてみました。比較対象の Python 環境は概ね素に近い環境のはずです(ちょっと余計なものが見えてますが…)。左が VDX のもので、右が Linux のものになります。

2d1
< CLI
25a25
> _dbm
29a30
> _gdbm
36a38
> _lzma
103d104
< curl
137a139
> idlelib
147a150
> lib2to3
192d194
< pycurl
196d197
< pythonStarup
203d203
< requests
252a253,254
> turtle
> turtledemo
254a257
> unittest
1つめの CLI は、Pythonスクリプトから VDX の CLI コマンドを発行するためのライブラリです。それ以外では HTTP 関連のライブラリが追加されているようです…

さすがに setuptoolspip は入ってないので VDX の Python 環境内から新規パッケージを追加するのは無理そうですが、標準ライブラリの範囲内であればひと通り使えそうです。

ユーティリティの作成

ということで、早速ちょっとしたスクリプトを作ってみました。こちらで公開しています。

diff.py

スイッチの運用をする上で、同じ設定を複数のポートに施すことはよくありますが、本当に同じ設定になっているのか、という確認を CLI 上で行うには、人間の目で頑張ってチェックするしかなく、機械的行うにはスイッチの外に show コマンドの結果などをもっていって行う必要があります。しかし、毎回スイッチ上でのコマンドの実行結果を手元にコピーして比較するのは面倒でした。

Pythonの標準ライブラリには difflib があるので、diffコマンドぽいものを作ってみました。スイッチ上のファイル同士や引数に渡されたコマンド列の実行結果を使ってdiffを取ります。詳しい使い方は github にある README.mdを見て下さい。

sample__port_parse_and_compose.py

こちらは別に作ったスクリプトの、コマンド引数の解析部分を抜き出したものです。スクリプトに対して操作するスイッチのポート番号を指定するための引数を解析する argparse コードとチェック用関数、VDXスタイルのポート番号表現を組み立てる関数が入っています。VDX用のスクリプトを作成される際に活用できそうでしたら、作成されるスクリプトの目的に合うように修正しつつ、お使いください。

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内検索
    Archives
    このブログについて
    DSASとは、KLab が構築し運用しているコンテンツサービス用のLinuxベースのインフラです。現在5ヶ所のデータセンタにて構築し、運用していますが、我々はDSASをより使いやすく、より安全に、そしてより省力で運用できることを目指して、日々改良に勤しんでいます。
    このブログでは、そんな DSAS で使っている技術の紹介や、実験してみた結果の報告、トラブルに巻き込まれた時の経験談など、広く深く、色々な話題を織りまぜて紹介していきたいと思います。
    最新コメント