さらば、愛しき論理削除。MySQLで大福帳型データベースを実現するツール「daifuku」を作ってみた 先のエントリ「論理削除はなぜ「筋が悪い」か」で書いたとおり、データベースに対して行われた操作を記録し、必要に応じて参照したり取り消したりしたいという要求は至極妥当なものですが、多くのRDBは、そのために簡単に使える仕組みを提供していません。 daifukuは、RDBに対して加えられた変更をトランザクション単位でRDB内にJSONとして記録するためのストアドやトリガを生成するコマンドです。 % daifuku dbname tbl1 tbl2 > setup.sql のように実行すると、指定されたテーブル（ここではtbl1とtbl2）にセットすべきトリガや、更新ログを記録するためのテーブル「daifuku_log」を生成するCREATE TABLEステートメントなど、必要なSQL文をset

圧縮されたソート済の整数列ってのは汎用的なデータ構造で、たとえば検索エンジンの転置インデックスとか、いろんなところで使うわけです。で、検索エンジンの場合は速度重要なので、PForDeltaとか様々なデータ構造が研究されてる。 一方、H2O には、ブラウザキャッシュに載ってない js や css をサーバプッシュする仕組み「cache-aware server push」があって、何がキャッシュされているか判定するためにブルームフィルタを全ての HTTP リクエストに含める必要がある。 で、ブルームフィルタを圧縮しようと思うと、ブルームフィルタってのはソート済の整数列として表現できるので、これを圧縮しようって話になる。 検索エンジン等で使う場合は速度重要だけど、HTTPリクエストに載せる場合は空間効率のほうが重要になる。ってことで、空間効率が理論限界に近いゴロム符号（の特殊系であるライス符号

先月末の話になりますが、SAPジャパンさんを会場に開催されたデータ転送ミドルウェア勉強会で、私が中心になって開発しているHTTPサーバ「H2O」について話す機会をいただき、登壇してきました。 以下は当日使用したスライドです。なぜ今H2Oを開発しているのか、その背景にある現状認識と将来の方針について、日本語で説明してあるので、興味ある方はご覧ください。 発表の機会をくださった@repeatedlyさんと@frsyukiさん、会場を提供してくださったSAPジャパンさん、ありがとうございました。 H2Oの開発は順調に進んでおり、HTTP/2サーバプッシュへの対応も完了し、まもなく次のバージョンがリリースできるかと思います。今後ともよろしくお願いいたします。

GitHub には、タグを打つとソースパッケージを自動的にリリースするという機能があります。スクリプト言語においては、それぞれの言語について一般的なパッケージ管理システム注1があるため、この機能を使うことが少ないかと思いますが、デファクトのパッケージ管理システムが存在しないC等の言語で書かれたプログラムや、単独で動作する管理用のスクリプトを GitHub で開発・配布する際には、本機能はとても便利なものです。 しかし、この機能は git-archive コマンドのラッパーとして実装されているため、サブモジュールのファイルが含まれないという問題を抱えています。この点は GitHub の人たちも認識しているものの、今のところ GitHub で独自に対応するということは考えていないようです注2。 私がこの問題を 知ることになったのは、picojson の issue で指摘を受けたからです。pi

C言語の可変長引数は、型安全でない（まちがった型の引数を渡してもコンパイルエラーにならない）とされています。これは言語仕様の理解としては正しいのですが、特定の型の引数を任意の個数とる関数に限っては、マクロを使うことで型安全性を確保することができます。 任意の個数のdoubleを引数にとり、その和を返す関数「sumf」を例にあげて説明します。 C言語の可変長引数機構を使ってsumfを定義すると、以下のようになります。 #include <math.h> #include <stdarg.h> #include <stdio.h> static double sumf(double nfirst, ...) { double r = 0, n; va_list args; va_start(args, nfirst); for (n = nfirst; ! isnan(n); n = va_a

プログラミングの「常識」は時代とともに変化します。そのひとつが、サーバプログラムにおけるバッファ処理です。 1990年代後半から2010年頃までは、メモリ空間の大きさ（32bitすなわち4GB注1）を超える大きさのファイルを扱う時代でした。このため、httpdなどのサーバプログラムにおいても、入出力データをいったんテンポラリファイルとしてバッファリングする必要がありました。ですが、ファイルI/Oはメモリアクセスと比べると低速です。このため、小さなサイズのデータについてはメモリアクセスする一方で、大きなサイズのデータについてはファイルI/Oを用いる、という煩雑なコードを書く必要がありました。 しかし、2014年も暮れとなる今 、サーバサイドにおいては64bit環境のみを考えれば良い時代に入りつつあります。 もちろん、64bit環境といったところで、64bit空間の全てをユーザプロセスが使える

「if文（条件分岐）を使わず、max(a, b) を計算 別解 | 津田の開発な日記」に関連した話です。リンク先のブログ記事では、条件分岐を使わずにmax(a,b)を実装する方法が議論されています。 では、更に条件を厳しくして、「条件分岐も算術演算も使わずに」max(a,b)を実装することはできるでしょうか？ も ち ろ ん 可 能 で す 回 答 例 は 以 下 に あ り ま す なぜ、「もちろん」なのか。CPUは、ANDやOR、NOTのようなデジタルな論理回路から構成されています。であれば、当然、ビット演算（ビットシフトと&, |, ^）を使って、max(a, b)を実装することも可能なわけです。こんな感じ。 #include <stdio.h> #define BIT(n, pos) (((n) >> (pos)) & 1) static int mymax(int a, int

最近H2OというHTTPサーバを書いているのですが、プロファイルを取ってみるとsprintfが結構な時間を食っていて不満に感じていました。実際、sprintfは数値や文字列をフォーマットするのに十徳ナイフ的に便利なので、HTTPサーバに限らず良く使われる（そしてCPU時間を消費しがちな）関数です。 では、sprintfを最適化すれば、様々なプログラムが より高速に動作するようになるのではないでしょうか。ということで作ったのが、qrintfです。 qrintfは、Cプリプロセッサのラッパーとしてソースコードに含まれるsprintfの呼出フォーマットを解析し、フォーマットにあわせたコードに書き換えることで、sprintfを高速化します。 たとえば、以下のようなIPv4アドレスを文字列化するコード片を sprintf( buf, "%d.%d.%d.%d", (addr >> 24) & 0xf

tl;dr Many SQL query builders written in Perl do not provide mitigation against JSON SQL injection vulnerability. Developers should not forget to either type-check the input values taken from JSON (or any other hierarchical data structure) before passing them to the query builders, or should better consider migrating to query builders that provide API immune to such vulnerability. Note: 問題の発見者による日

Unix系OSの権限分離の変遷について（もしくはなぜ、アプリ単位の権限分離が求められるようになったか） [ブコメした件について。大筋でおかしなことは書いてないと思いますが、出典は確認していません] Unix系OSにおける権限分離は、伝統的に、利用者ごとに異なるuser idを割り振り、これを用いてアクセス制御を行うという方式で実現されてきた。また、デーモンプロセスについては、不要な権限付与を避け、デーモンプロセス間の相互作用を抑制するために、デーモンごとに専用の「user id」を発番するのが一般的な慣習とされるようになったという経緯がある。 しかし、2000年代に入ると、インターネットの普及とあいまって、クライアントサイドではこのような「利用者ごと」の権限分離では不十分という考え方がされるようになってきた。具体的には、 （オンラインバンクのパスワードに代表されるような）攻撃価値が高い情報

ウェブの脆弱性は、ウェブアプリケーションのバグに起因するものと、ウェブブラウザのバグに起因するものの２者に大別することができる。 ウェブアプリケーションを開発／提供する仕事に従事している者には、この前者、すなわち、ウェブアプリケーションのバグに起因する脆弱性を最小限に抑え込むことを求められる注1。 かといって、脆弱性がないことを保障するのは難しい。「ウェブアプリケーションにバグがあっても脆弱性とはならない（あるいは被害が限定される）ような設計」を採用するのが現実的だと考えられる。 OSにおける、プロセス間のメモリ分離やuserIDに基づいたファイルへのアクセス制御を考えてみると、OSがセキュリティを「強制」するため、アプリケーション側で不正なコードが実行されても脆弱性とならない、もしくは、影響を小さく抑え込むことができるようになっていることがわかる。 ウェブ技術における同様の例は数多いが、

Twitterに書いたことのまとめです。 プログラミング言語の仕様の一部として正規表現リテラルを提供することの得失について、JavaScriptを例に説明します。 ■より簡潔なコード 言うまでもありませんが、正規表現リテラルを使った方が簡潔なコードになります。 (new RegExp("abc")).exec(s) // リテラルを使わない場合 /abc/.exec(s) // リテラルを使った場合 また、正規表現リテラルがない場合は、文字列リテラルとしてのエスケープと正規表現としてのエスケープが二重に必要になる結果、コードの保守性が低下します注1。 new RegExp("\\\\n"); // リテラルを使わない場合 /\\n/ // リテラルを使った場合 ■エラー検出タイミング 正規表現リテラルがない場合、実際にその正規表現が評価されるまで記述エラーを検出することができません。正規表

JavaScriptで高速なコードを書く際の注意点。または私は如何にして心配するのを止めてJSXを作ることにしたか 本日、福岡で開催されたプログラミング言語のパフォーマンスを考えるイベント「ぷろぐぱ」で、「JSX 速さの秘密 - 高速なJavaScriptを書く方法」という演題で講演しました。 JavaScriptで速いコードを書こうとする際に陥りがちな罠を紹介し、それらの問題にJSXではどうやって対処しているか、プログラミング言語設計と最適化機能の実装を説明しました。プログラミング言語設計に興味がある方にとっても、JavaScriptを使ったプログラミングに興味がある方にとっても面白い内容になっているかと思います。

■■序論 徳丸さんのスライド「いまさら聞けないパスワードの取り扱い方」に見られるように、昨今、ウェブアプリケーションの設計要件として、サーバ内に侵入された場合でもユーザーのパスワードをできるだけ保護すべきという論調が見受けられるようになってきました。 上掲のスライドでは、その手法としてソルトつきハッシュ化を勧めています。しかしながらスライドに書かれているとおり、ソルトつきハッシュには、複雑なパスワードの解読は困難になるものの、単純なパスワードを設定してしまっているユーザーのパスワードについては十分な保護を提供できないという問題があります。そして、多くのユーザーは適切なパスワード運用ができない、というのが悲しい現実です。 ソルトつきハッシュを使った手法でこのような問題が残るのは、ウェブアプリケーションサーバに侵入した攻撃者がユーザーの認証情報をダウンロードして、認証情報をオフライン攻撃するこ