Thursday, April 16, 2015

HTTP/2 is much faster than SPDY thanks to dependency-based prioritization

Background

HTTP/2 provides two methods to prioritize streams (e.g. files being served).

One method is called weight-based prioritization. In weight-based prioritization, every stream is given a weight, and the value is used by the server to proportionally distribute the bandwidth between the streams.

The other method is dependency-based prioritization. By using the method, web browsers can advise HTTP/2 servers to send the streams that are depended by other streams before sending the other streams. For example, by using dependency-based prioritization web browsers can request the server to send CSS or JavaScript files before sending HTML or image files.

As of this writing, out of the two popular web browsers that implement HTTP/2, only Firefox uses dependency-based prioritization.

Note: the background section has been rewritten due to the fact that the comparison with SPDY turns out to be wrong, as pointed out in the comment. The original version of the section is here. Rest of the blogpost stays in tact.

The case of Mozilla Firefox

The prioritization strategy of Firefox is as follows1:
  • send CSS and JavaScript files in <HEAD> before HTML and/or image files by using dependency-based prioritization
  • HTML streams are given 2.5x bandwidth above image streams (by using weight-based prioritization)
  • script files within <BODY> are in total given about the half bandwidths of the other files2

Below is the network time chart generated by Firefox 37.0.1 when accessing a sample web page3 (given 100ms network latency6) containing a number of CSS, script files, and images. H2O version 1.2.0 was used as the HTTP/2 server for running the benchmark.


By looking at the chart, you can see that many CSS, script files and images are requested in parallel at some time around 320ms, but that the download of files that block rendering (e.g. CSS and script files) complete before any of the images (even the smallest ones) become available. This is due to the fact, as I explained earlier, that Firefox notifies the HTTP/2 server that HTML and image files depend on the CSS and the script files to become rendered; therefore the server is sending the files being depended before sending the dependents. And thanks to the prioritization, all the files that are required to do the initial rendering arrives at the web browser (a.k.a. first-paint time) at around 1.0 seconds from start.

The case of Google Chrome

On the other hand Chrome's prioritization logic only uses the weight-based prioritization; the logic remains mostly same with that used in SPDY. Chrome assigns a predefined weight to each of the stream based on their types.

Table 1. Priority weight values used by Google Chrome4

TypeWeight
HTML256
CSS220
script183
image110

And here is the timing chart taken using Chrome (version 44.0.2371.0 canary) when accessing the same web page.


Unlike Firefox, CSS and script files are not arriving before the image files. If you look carefully, you will find a vague relationship between the size and the arrive time of the contents independent to their types. This is because each of the files are interleaved into a single TCP stream based on their weights, and because of the fact that the weight between the files do not differ much. Therefore the initial-paint time is as late as 1.5 seconds5.

Conclusion

As shown, dependency-based prioritization introduced in HTTP/2 brings non-negligible benefit in terms of web-site performance. In case of the benchmark, Firefox using dependency-based prioritization was 1.5x faster than Google Chrome only using weight-based prioritization when comparing the first-print timings.

My understanding is that the developers of Chrome is aware of this issue, so hopefully it will be fixed soon. I also hope that other web browser vendors will utilize dependency-based prioritization. As shown, it is clearly the way to go!



PS. And it should also be worth noting that HTTP/2 servers should implement the prioritization logics correctly. In case of H2O, the server both of the prioritization logics are fully implemented using a per-frame weight-based round robin with the frame size of 16Kbytes at maximum.

note 1: ref: HTTP/2 Dependency Prioritization in Firefox 37, Http2Stream.cpp line 1088 of Firefox
note 2: ref: nsScriptLodare.cpp line 306; I am not sure if this is the intended behavior, IMO script tags in BODY should given a priority equiv. to HTML or image files, and it might be the case that the condition of the if statement should be reversed.
note 3: http2rulez.com was used for testing the load speed, with the <script> tags at the end of the document moved into <HEAD>
note 4: ref: MapPriorityToWeight function of Chrome
note 5: the network chart of Chrome includes a 0.2 second block before initianting the TCP connection, which has been subtracted from the numbers written in this blog text.
note 6: An Ubuntu 14.04 instance running on VMware Fusion 7.1.1 on top of OS X 10.9.5 was used for running the server. Network latency was given using tc qdisc command. Both the web browsers were run directly on OS X 10.9.5.

Tuesday, April 14, 2015

H2O version 1.2.0 released; bundles LibreSSL by default

This is the release announcement of H2O version 1.2.0. Full list of changes can be found in the Changes. The release includes a fix for a heap-overrun vulnerability in the proxy module; users of prior versions using the H2O as a reverse proxy are urged to upgrade to 1.2.0.

Aside from the bug fixes, we have adjusted the code-base so that no external dependencies would be required when building the standalone server.

One of the hustles while trying to install the older versions of H2O (or any other HTTP/2 server) was that it required the newest version of OpenSSL (version 1.0.2). This is because ALPN, a feature that became only available in version 1.0.2 is essential for the HTTP/2 protocol.

However it is often difficult to upgrade OpenSSL on existing systems, since it is used by other important softwares as well (SSH, etc.).

In H2O version 1.2.0, we have chosen to bundle LibreSSL. LibreSSL is not only considered more stable than OpenSSL; it also support new cipher-suites like chacha20-poly1305, which is the preferred cipher suite of Chrome for Android.

If CMake (the build tool used by H2O) does not detect OpenSSL version 1.0.2 or above, it would instruct the build chain to use LibreSSL being bundled. To enforce the use of libressl being bundled, pass -DWITH_BUNDLED_SSL=on as an argument to CMake (note: you might need to clear the build directory before running cmake). Or set -DWITH_BUNDLED_SSL=off to explicitly disable the use of libressl.

Version 1.2.0 also bundles other dependencies as well, so that the server can be installed as simply as by running cmake, make, and make install.

Have fun!

Tuesday, March 31, 2015

さらば、愛しき論理削除。MySQLで大福帳型データベースを実現するツール「daifuku」を作ってみた

先のエントリ「論理削除はなぜ「筋が悪い」か」で書いたとおり、データベースに対して行われた操作を記録し、必要に応じて参照したり取り消したりしたいという要求は至極妥当なものですが、多くのRDBは、そのために簡単に使える仕組みを提供していません

ないのなら、作ってみようホトトギス

というわけで作った。


daifukuは、RDBに対して加えられた変更をトランザクション単位RDB内JSONとして記録するためのストアドやトリガを生成するコマンドです。
% daifuku dbname tbl1 tbl2 > setup.sql
のように実行すると、指定されたテーブル(ここではtbl1tbl2)にセットすべきトリガや、更新ログを記録するためのテーブル「daifuku_log」を生成するCREATE TABLEステートメントなど、必要なSQL文をsetup.sqlファイルに出力します。

次に出力内容を確認し、mysqlのルートユーザ権限でSQLを実行すると、準備は完了。
% mysql -u root < setup.sql
あとは、トランザクションの先頭でdaifuku_begin()プロシージャを呼び出せば、以降同一のトランザクション内で加えられた変更は、全てdaifuku_logテーブルに単一のJSON形式の配列として記録されます。

daifuku_begin()には、任意の文字列を渡し、RDBの変更とあわせて記録することができるので、更新の意図や操作を行った者の名前等を記録することにより、監査や障害分析を柔軟に行うことが可能になります。

また、記録されるトランザクションログのid(daifuku_log.id)は@daifuku_idというセッション変数に保存されるので、アプリケーションではその値をアプリケーション側のテーブルに記録することで、操作ログをUIに表示したり、Undo機能注2を実装したりすることも可能でしょう。

実際に使ってみた例が以下になります。トランザクション内で行ったdirect_messageテーブルとnotificationテーブルに対する操作がJSON形式でdaifuku_logテーブルに保存されていることが確認できます注3
mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> call daifuku_begin('');
Query OK, 1 row affected (0.00 sec)

mysql> insert into direct_message (from_user,to_user,body) values (2,1,'WTF!!!');
Query OK, 1 row affected (0.01 sec)

mysql> insert into notification (user,body) values (2,'@yappo sent a new message');
Query OK, 1 row affected (0.00 sec)

mysql> commit;
Query OK, 0 rows affected (0.01 sec)

mysql> select * from daifuku_log\G
*************************** 1. row ***************************
    id: 4
  info: 
action: [
    [
        "insert",
        "direct_message",
        {},
        {
            "id":        "2",
            "from_user": "2",
            "to_user":   "1",
            "body":      ["V1RGISEh"]
        }
    ],[
        "insert",
        "notification",
        {},
        {
            "id":   "2",
            "user": "2",
            "body": ["QHlhcHBvIHNlbnQgYSBuZXcgbWVzc2FnZQ=="]
        }
    ]
]
1 row in set (0.00 sec)

大規模なコンシューマ向けウェブサービスでは、この種のトリガは使いづらいかもしれませんが、バックオフィス向けのソフトウェア等では工数削減と品質向上に役立つ可能性があると思います。

ってことで、それでは、have fun!


補遺:他のアプローチとの比較

同様の機能をアプリケーションロジックとして、あるいは手書きのトリガとして実装することも不可能ではありませんが、トリガを自動生成する daifuku のアプローチの方が、アプリケーション開発に必要な工数、バグ混入の可能性、データベースのロック時間の極小化等の点において優れていると考えられます。

また、過去の任意のタイミングにおけるデータベースの状態を参照する必要がある場合は、範囲型による時間表現を用いたデータベース設計を行うべきでしょうが、要件が操作の記録やUndoである場合には、そのような過剰な正規化は不要であり悪影響のほうが大きいです注4。ってかMySQLには範囲型ないし。


注1: 名前の由来は大福帳型データベースです。
注2: トランザクション単位のrevertではなくdaifuku_logテーブルに記録されたログを逆順に適用していった際に以前のテーブルの状態に戻ることを保証したい場合は、分離レベルをシリアライザブルに設定しておく必要があります。この点において、更新ログを主、現時点での状態を示すテーブルを従とするアプローチに対し劣位であることは、先の記事でも触れたとおりです。
注3: 文字列型等、制御文字やUTF-8の範囲外の値を含む可能性のある型のデータについては、base64エンコードが行われ、それを示すために配列としてログに記録されます。詳しくはman daifukuをご参照ください。
注4: 操作=トランザクションとは元来リレーションに1対1でマッピングされづらいものなので、過去の操作を取り扱うことが主目的の場合には、無理に正規化を行わない方が都合が良いケースが多いと考えられます。

Thursday, March 26, 2015

論理削除はなぜ「筋が悪い」か

論理削除が云々について - mike-neckのブログ」を読んで。

データベース設計において、「テーブルの書き換えをするな、immutableなマスタと更新ログによって全てを構成しろ」というこの記事の主張はモデリング論として全く正しい

だが、残念なことに、ディスクやメモリが貴重な資源だった時代の技術であるRDBは、そのようなモデリングに基づいて設計されたデータベースには必ずしも適していない

第一の問題は、RDBに対してなされる様々な「更新」(トランザクション)は不定形(どのテーブルをどのように修正するかはアプリケーション依存)だという点。不定形な「更新」を時系列にそってRDBに記録していくのは、設計と並走性の点において困難あるいは煩雑なコーディングが必要になる(というか、そのような「イベント」による「変化」はREDOログに書き、その更新された「状態」をテーブルに反映していくというのがRDBの「一般的な使われ方」)。

第二の問題は、ほとんどのデータベースアクセスは、更新が蓄積された結果である「現在の状態」を問い合わせるものになるが、immutableなマスタと更新ログによって構成されるデータベース設計においては、そのような問い合わせに効率的に応答するのが難しいという点である。

従って、現実的なデータベース設計においては、多くのテーブルが「現在の状態」をもつ、immutableなマスタと更新ログから合成可能な「現在の状態を表現するビュー」を実体化したものとして表現されることになる。

ふりかえって、論理削除とはなにか。「現在の状態を表現する実体化ビュー」に、過去の状態(かつて存在したデータであることを意味する「削除済」)をフラグとして付与したものである。

「現在の状態を表現する」ことを前提にしたビューであるところのテーブルに、過去の状態の一部だけを表現するフラグを追加するのが「筋が悪い」設計だというのは明らかだ。

過去の状態を参照すべき要件があるなら、そのテーブルが表現する情報についてはimmutableなマスタと更新ログを用意し、その射影として表現されるビューとして「現在の状態」を実現すべきである。そのようなビューは自動生成できるならしても良いし、手動で更新するなら、ストアドを使うか、あるいはアプリケーションのデータベースアクセス層において手続きをまとめる方法を考えるべきだろう。

ただ、immutableなマスタ、更新ログと「現時点のビュー」の3テーブルを準備・運用するというのはそれなりにコストがかかるので、筋が悪い「削除フラグ」(より一般化すれば状態フラグ)を使うかどうかはケースバイケースで判断するのもひとつの見識である。


まとめ:
  • データベース設計にあたっては、テーブルを「現在の状態」を表現するものとして設計するか、それとも「immutableなマスタと更新ログ、および現時点の状態を表現するビュー」として設計するかという、2つの選択肢がある
  • 前者は簡潔で性能が高くなるが、過去の情報を参照できないという問題がある
  • 「削除フラグ」というのは、「現在の状態」を表現するテーブルに過去の状態の一部を表現する機能を場当たり的に足したもの(なので筋が悪い)
  • それよりも、過去の情報を参照する要件がある場合(もしくはそのような要件が発生すると想定される場合)は、テーブル単位で「immutableなマスタと更新ログ」という設計を採用しつつ、現在の情報をビューとして表現することを考えた方がよい

こういった点を理解・検討した上で、「それでも削除フラグの方が楽だろう」という判断を下しているなら良いと思います。


追記: Re: 論理削除はなぜ「筋が悪い」か - Blog by Sadayuki Furuhashiで挙げられていた疑問点について
効率的にSELECTや更新ができるスキーマを作ろうとすると、VIEWやFUNCTIONなど、側に実装するコードが増えてくる。それらのコードは、上記のようにDB側に実装しても良い(するべき)だろうか?それともアプリケーションに実装するべきだろうか?
アプリケーション要件によるでしょう。

が、アプリケーション要件に関わらず正しく動作する方法が何かという問に対しては、RDB側でトリガ(あるいはストアド)として実装するのが安全だというのが答えになるでしょう。また、アプリケーションが操作可能な処理は「immutableなマスタ」と更新ログテーブルへの追記のみとし、両者への操作から「現在の状態を表現するビュー」を生成すべきであって、「現在の状態を表現するビュー」をアプリケーションが操作し、その変更内容をトリガでログに出力するという方式は避けるべきという話になるかと思います。

なぜか。そうしないと分離レベルや主キーの発番処理に起因する込み入った条件が色々…続きはお近くのDBAにご相談ください。
テーブルのスキーマは停止時間なしで変更する手法をいくつか思いつくが(PostgreSQLなら)、上記のレコードを削除する操作などはアプリケーションの変更を伴うので難しい(アプリケーションとDBのスキーマをアトミックに変更できない)
カラムのアクセス権は無停止で変更できませんか? つまり、アプリケーションを拡張した結果として削除フラグの存在が冗長になったのであれば、そのフラグの更新をストアドあるいはトリガで行われるように変更し、書き込み権限をドロップすればいいでしょう。

こんな感じかと思います。

Tuesday, March 24, 2015

released Server::Starter 0.21; no more external dependencies, easy to fat-pack

I am happy to announce the release of Server-Starter version 0.21.

In the release I have removed dependencies to perl modules not in core (e.g. Proc::Wait3, List::MoreUtils, Scope::Guard).

Without dependencies on XS modules it would now be easier to install the module on any system.

The change also opens the possibility to fat-pack the `start-server` script; it can be accomplished by just running the fatpack-simple script.
$ fatpack-simple start_server
-> perl-strip Server/Starter.pm
-> perl-strip Server/Starter/Guard.pm
-> Successfully created start_server.fatpack
$ 

Have fun!

Thursday, March 19, 2015

「技術的負債」は避けるべき? - 割引率を使って考えてみた

「技術的負債」をコントロールする定量評価手法への期待 からの続きです。

ソフトウェアサービス企業における技術責任者の最も重要な仕事のひとつが、エンジニアリングの効率化です。そのためには、サービスの初期開発コストだけでなく、運用コストを織り込んだ上で正しい技術的判断を行っていく必要があります。

「技術的負債」という言葉は、この運用コスト最適化の重要性を指摘する上で、とてもキャッチーなフレーズだと考えられます。しかし、「技術的負債」を産まないように、あるいは負債を早めに返していこうとすると、開発工数が大きくなってしまうという問題もあります。

初期開発コストと運用コストのバランス注1を、どのようにとっていけば良いのでしょう?

同等の機能を提供する「ソフトA」と「ソフトB」を考えてみます。ソフトAは、初期開発工数が6だが、2年目以降の維持工数が毎年4かかるとします注2。ソフトBは、初期開発工数が10で、維持工数が毎年1かかるとしましょう。ソフトAはPHPファイル1枚に必要な処理をひたすら羅列したクソコード、ソフトBはMVCを念頭にレイヤ分割された、きれいなコードなんてイメージすると、こんな工数感覚になってもおかしくないかと思います。

ソフトAとソフトB、どちらを開発すべきかという問いに対する答えが、そのソフトを使い続ける(改善し続ける)期間によって変わることは、表1を見ずとも明らかだと思います。では、その期間を合理的に見積もる手法が必要になります。
表1. 初期開発と維持工数
年度ソフトAソフトB
工数(単年)工数(累計)工数(単年)工数(累計)
1661010
2410111
3414112
4418113
5422114


ここで登場するのが「割引率」という概念です。

割引率は一般に、将来の発生する可能性のある利益を現在の価値に変換して評価するために用いられる概念ですが、同様に、将来発生する可能性のある費用を評価する目的でも使うことができます注3

たとえば、新規サービスの場合を考えると、2年目も継続してサービスを改善しつづける可能性は決して高くないと思います(仮に改善を続ける可能性が50%だとすると、割引率(1÷改善継続可能性−1)は100%になります)注4。n年後に改善を続けている可能性が0.5nであるなら、現在価値に修正した累計コストは以下のような表になります。
表2. 初期開発と維持工数(割引率100%)
年度ソフトAソフトB
工数(単年)工数(累計)工数(単年)工数(累計)
1661010
2280.510.5
3190.2510.75
40.59.50.12510.875
50.259.750.062510.9375

表からも明らかなように、ソフトAの累計工数がソフトBを上回ることはありません(厳密に言うと、ソフトAの割引後の累計工数が10に収束するのに対し、ソフトBの工数は11に収束する)。この結果はつまり、仮に翌年も継続してサービスを改善しつづける可能性が50%なら、ソフトBのアプローチよりも、ソフトAのアプローチのほうがコスト効率的に優れているということを示しています。

逆に、上場企業の事業の基盤となっているようなソフトウェアについては、割引率が10%を切ることがあってもおかしくないはずですが、仮にn年後に改善を続けている可能性が0.9n(割引率11%)であるなら、現在価値に修正した累計コストは下表のようになり、今度は逆に、ソフトBのアプローチの方が優れているということになります。
表3. 初期開発と維持工数(割引率11%)
年度ソフトAソフトB
工数(単年)工数(累計)工数(単年)工数(累計)
1661010
23.69.60.910.9
33.2412.840.8111.71
42.91615.7560.72912.439
52.624418.38040.656113.0951

以上のように、技術選択における正解は割引率の高低によって大きく左右されます

また、割引率は事業の形態のみならず、ソフトウェアの種類によっても大きく異なります。私個人の経験を振り返っても、サーバサイドの管理用ミドルウェア → データベース等ハードウェアの能力に影響をうけるサーバサイドミドルウェア → クライアントサイドのミドルウェア → アプリケーションの順で割引率が高くなっていく印象があります。

適切な値がいくらか、ということは俄には答えにくい問題かもしれませんが、「割引率」という概念自体は経営層にとっては常識レベルのものなので、経営層と事業継続にかかる感覚値を普段から共有し、技術判断にフィードバックしていくということが、技術責任者に求められる役割なのかな、と思う次第です。

参考リンク:
とあるスタートアップを抜け、CTOを辞めた話。 - nobkzのブログ
「「技術的負債」を問いなおす」というタイトルでJAWS DAYS 2014で話してきた #jawsdays - delirious thoughts

注1: 企業の情報システム投資では、初期コストに保守等のコストを加えた「総所有コスト(TCO)」の極小化を目標とするのが有効なアプローチだと考えられています。
注2: ソフトウェアが陳腐化する外的要因は周辺技術の進歩です。その速度は一定であると置くのが妥当ですから、ソフトウェアの保守コストは毎年一定であると考えるのが正しいことになります。「ソフトウェアの保守が時間とともに難しくなる」と感じられるとしても、それは過去の保守投資が過小であった結果だと解釈すれば良い話です。モデルを無駄に複雑化する理由はありません。
注3: つまり、事前に使用年数を見積もることが困難なシステムがあるなら、通常のTCOではなく、保守を続ける年数を確率分布として修正したTCOを用いてコストを予測すれば良いということです。
注4: 割引率は毎年一定になるとは限らないでしょう。たとえば2年間で資金を使い切る前提でサービスを提供している場合には、2年間は割引率が低く、3年目にがくっと上がる形(失敗するサービスが過半であるという前提を置くなら、それこそ100%を超える値)になると思います。

Friday, March 6, 2015

H2O version 1.1.0 released with bug fixes and enhancements in proxy etc.

This is a release announcement of H2O version 1.1.0, the optimized HTTP server with support for HTTP/1 and HTTP/2.

In 1.1.0 we have gone through a major refactor of the proxy implementation, and added three notable features to the H2O standalone server.

Support for x-reproxy-url header #197

With help from @lestrrat, H2O now recognizes the x-reproxy-url header sent by upstream servers, and if found, substitutes the response with the response obtained from the URL specified by the header.

When the feature is activated (by adding the line reproxy: on to the configuration file), any HTTP URL can be served by using the x-reproxy-url header.

There is no support for x-reproxy-file header. Instead, if the authority of the URL matches one of the host entries of the configuration file, then the reproxied request will be handled internally by the handlers of H2O.

Load distribution among upstream servers #208

To resolve the address of the upstream server, H2O calls getaddrinfo each time it needs to connect to the servers. As of version 1.1.0 the call is executed asynchronously (by using dedicated threads for the task), and if multiple entries are returned by the name resolver (e.g. DNS, /etc/hosts, et. al.) then H2O connects to one of them selected at random.

The change neatly constitute as a basis for load balancing. By adjusting the name resolver, you can at any time add or remove an upstream server, or change the selection weight between the servers by using sophisticated DNS servers like
MyDNS
.

This is only a first step. We plan to polish up the feature for better load balancing.

Directives for tweaking the response headers #204

Following directives have been introduced for mangling the response headers, modeled after those provided by the Apache HTTP server: header.add, header.append, header.merge, header.set, header.setifempty, header.unset.


For more information, a full list of changes with references can be found in the version 1.1.0 changelog; list of configuration directives can be found by running h2o --help.