Wednesday, November 11, 2015

mruby で同期呼出を非同期化する話(もしくは H2O の mruby ハンドラでネットワークアクセスする話)

■背景

H2Oではバージョン1.5より、mrubyを用い、Rackのインターフェイスに則った形でハンドラを書けるようになっています。

この機能を提供している目的は、正規表現による書き換え等を用いる複雑な設定ファイルではなくプログラミング言語を用いることで、ウェブサーバの設定をより簡潔に拡張しやすくするためです(Apacheのmod_rubyやmod_perlのようにウェブアプリケーションをウェブサーバ内で実行可能にすることではありません)。

とは言っても、現実のウェブサーバの設定においては、外部のデータベース等に問い合わせた結果に基づいたルーティングが必要になることがあります。

H2Oのようなイベントドリブンなウェブサーバ上で動作する、同期モデルを採用するRackインターフェイスを用いて記述されるハンドラ内において、データベースへの問い合わせをどのように実現すれば良いか。問い合わせが同期的だと、その間ウェブサーバの処理が止まってしまうので、Rubyで問い合わせ関数が呼ばれたタイミングで、ウェブサーバ側に処理を戻したいわけです。

そんなこんなで
とツイートしたところ、
という流れになりました。

その後、考えたところ、
という気がしてきたので、まずはPoCを書いてみることにしました。

■Fiberを使って、同期コールを非同期化するPoC

ざっと、以下のような感じになります。Rack ハンドラ自体を Fiber 内に置き、その入出力と、非同期化したい関数(ここでは DB#query)が呼ばれたタイミングで Fiber.yield を呼ぶことで、メインループ(これは実際には C で書くことになる)へ制御を戻しています。

# DB class that calls yield
class DB
  def query
    return Fiber.yield ["db#query"]
  end
end

# the application, written as an ordinary Rack handler
app = lambda {|env|
  p "received request to #{env["PATH_INFO"]}"
  [200, {}, ["hello " + DB.new.query]]
}

# fiber that runs the app
runner = Fiber.new {
  req = Fiber.yield
  while 1
    resp = app.call(req)
    req = Fiber.yield ["response", resp]
  end
}
runner.resume

# the app to be written in C
msg = {"PATH_INFO"=> "/abc"} # set request obj
while 1    
  status = runner.resume(msg)
  if status[0] == "response"
    resp = status[1]
    break
  elsif status[0] == "db#query"
    # is a database query, return the result
    msg = ""
  else
    raise "unexpected status:#{status[0]}"
  end
end
p "response:" + resp[2].join("")

やろうと思えばできることはわかりました。しかし、この手法には制限が2点あります。
  • fiber 内からしか呼べない - それでいいのか?
  • fiber 内で、Cコードを経由して呼ばれた ruby コードから Fiber.yield できない
いずれも大した問題ではないですが、ここに付記しておきます(後者は mruby の場合、大きな問題にならないと認識されているようです。参照: twitter.com/yukihiro_matz/status/664276538574049280)。

■プロトコルバインディングの実装手法

さて、これで行けそうだということは分かったのですが、可能であることと、それが良いアプローチであることが等価であるとは限りません。そもそも、プロトコルバインディングはどのように書かれるべきなのでしょうか。2種類に大別してプロコンを書きたいと思います。

  • Cライブラリのラッパーを書く
    • Cライブラリが、非同期モデルをサポートしている必要がある
    • イベントループ (libuv, libev, ...) 毎に対応が必要
    • プロトコルを実装しなくて良い
  • rubyでバインディングを書く
    • プロトコルを実装する必要がある
    • rubyで書ける!
    • 各バックエンド (libuv, libev, ngx_mruby, h2o, ...) が同じ ruby API (TCPSocketのサブセットで良いと思う) を提供すれば、イベントループ毎の対応が不要
    • Cより遅いかも…

個人的には、rubyでバインディングを書くアプローチが好みです。速度が遅いかも…という点については、Perl IO を用いた HTTP 実装を推進してきた立場から言うと、スクリプト言語のI/Oレイヤの負荷はネットワーク通信を行うプログラムにおいては多くの場合問題にならないと考えます。問題になるとすれば、通信データのパーサですが、ここのみをネイティブコード化するという手法で十分に対応できることは、Plack や Furl に慣れた Perl プログラマであれば納得できる話かと思いますし、(m)ruby においても同等かと思います。

■まとめ

長くなりましたが、H2O (あるいはイベントドリブンなプログラム一般)から、同期的に書かれたネットワーククライアントを呼び出す mruby スクリプトを起動する方法については、
  • 同期的に記述されたアプリケーションを Fiber を使ったラッパーで非同期化する
  • ホストプログラムは、Fiber を通じて、TCPSocket と互換性のある同期ソケット API を提供する
  • プロトコルバインディングは、Rubyで(もしくは、Ruby の TCPSocket と C で書かれたプロトコルパーサを組み合わせて)提供する
という形で行うのが最善ではないかと思いました。

Friday, November 6, 2015

ソート済の整数列を圧縮する件

圧縮されたソート済の整数列ってのは汎用的なデータ構造で、たとえば検索エンジンの転置インデックスとか、いろんなところで使うわけです。で、検索エンジンの場合は速度重要なので、PForDeltaとか様々なデータ構造が研究されてる。

一方、H2O には、ブラウザキャッシュに載ってない js や css をサーバプッシュする仕組み「cache-aware server push」があって、何がキャッシュされているか判定するためにブルームフィルタを全ての HTTP リクエストに含める必要がある。

で、ブルームフィルタを圧縮しようと思うと、ブルームフィルタってのはソート済の整数列として表現できるので、これを圧縮しようって話になる。

検索エンジン等で使う場合は速度重要だけど、HTTPリクエストに載せる場合は空間効率のほうが重要になる。ってことで、空間効率が理論限界に近いゴロム符号(の特殊系であるライス符号)を使うことになる。

ってことで、作ったのがgithub.com/kazuho/golombset

今週ちょっとcodecをいじって、あと気軽に試せるようにコマンドラインインターフェイスを追加した。

なので、こいつを git clone して make して、以下のような感じで使うことができる。

(100, 155, 931) というソート済の整数列をエンコード
% (echo 100; echo 155; echo 931) | ./golombset --encode | od -t x1
0000000    41  90  6d  c0  ff
0000005

同じ整数列をエンコードしてデコード
% (echo 100; echo 155; echo 931) | ./golombset --encode | ./golombset --decode
100
155
931

(100,155,931)という3つの数値を含むソート済の整数列を5バイトにエンコードできていることがわかる。

もうちょっと実際的な例として、偽陽性が1/100の確率で発生するブルームフィルタに、100個の要素を突っ込むんでエンコードすることを考える。適当にランダムな値を用いてそのようなフィルタを作成しエンコードしてみると、結果が102バイトであることがわかる。

% perl -MList::MoreUtils=uniq -e 'my @a = (); while (@a < 100) { @a = uniq sort { $a <=> $b } (@a, int rand(10000)); } print "$_\n" for @a' | ./golombset --encode | wc -c
     102

つまり、CSSやJavaScriptのような、ブラウザのレンダリングにクリティカルな影響を与えるファイルが100個あるとして、それらがウェブブラウザのキャッシュ内に存在するかを判定するためのブルームフィルタをHTTPリクエストに添付するためのオーバーヘッドは100バイト程度である、ということになる。さらに、リクエストを2回以上繰り返す場合は、HPACKによる圧縮が効く。

以上が、これなら現実的だよねってんで H2O の cache-aware server push は実装されたのでした、という経緯と、それにあわせて作ったライブラリの紹介でした。

それでは、また。

参考:
ImperialViolet - Smaller than Bloom filters
Golomb-coded sets: smaller than Bloom filters (giovanni.bajo.it)