Radium Software Development

HOME - ARCHIVE - ABOUT - RSS

Try to Use YouTube

2006-08-08

今夏の自由研究

YouTube 上で自作映像の配信を行ってみる。

機器の導入

画質を求めるならばデジタルビデオカメラの導入が適しているが,比較的高価であることが難点として挙げられる。画質を求めておらず,なおかつ自室での撮影に限定するならば,いわゆる「ウェブカメラ」を使用するのが最も手軽な方法であると言える。

機器の選択基準としては,最低限の画素数(30万画素程度)があること,設置が自在であること,余計なオマケが付いていないこと,そして何より安価であることを考慮に入れた。店頭での比較検討の結果,バッファローの BWC-30L01 を購入することにした。店頭販売価格は3千円ほどになる。

録画

ウェブカメラを使用しての動画のキャプチャーには Windows XP に付属の「ムービーメーカー」を利用することができる。ただ,このソフトは簡便性を重視しているがあまりにコンフィギュレーションの類が大雑把であるという欠点がある。

コンフィギュレーションを細かに行いたい場合は VirtualDub の使用が適している。 VirtualDub ならばキャプチャー時の設定を細かく行うことができるほか,内蔵のフィルターを利用して画質の補正などを行うこともできる。

060808_0.jpg

キャプチャー時の動画圧縮には DivX コーデックを使用することにした。ウェブカメラからの取り込み画像自体が元々かなり汚いため,だいたい 1Mbps 程度の帯域を確保しておけば,ほぼ劣化無しに動画を保存することができる。

音声の圧縮には Microsoft ADPCM コーデックを利用した。大抵の場合はこれで問題無いものと思われるが,今回のように音質が重視される内容の場合は無難に無圧縮 PCM を選択しておいた方がよかったのかもしれない。 ADPCM ではどうしても高音成分がシャリシャリしてしまう。

原因は不明だが,収録の際になぜか映像と音声が 0.5 秒程度ずれてしまうという問題が発生した。コンフィギュレーションの調整によって対処することは難しそうだったため,一旦収録を終えてから音声をずらして動画を再構築することによって対処した。再構築時に音声をずらすには "Audio" メニュー中の "Interleaving" から "Audio skew correction" を調整すればよい。

060808_1.jpg

また,その際に "Video" メニューから "Directo stream copy" を選択しておくことによって,再構築時の再圧縮を回避することができる。

060808_2.jpg

編集

映像の編集には Windows XP に付属の「ムービーメーカー」を利用した。「ムービーメーカー」は非常に単純なソフトではあるが,今回のように,フェードイン・アウトを入れたり,単純な字幕を入れたりする程度であれば,これで十分に事足らすことができる。

060808_3.jpg

編集の完了した映像は「LAN 用ビデオ (1.0 Mbps)」でエンコードを行った。 YouTube は映像の長さの制限(10分まで)の他に,容量による制限(100MB まで)も行っているため,無闇に画質を上げることはできない。また,どう頑張ってもサーバー側の処理によって画質は落とされてしまうものであるので,結局のところ 1Mbps 程度を選択しておくのが適当なのではないかと思われる。

アップロード

YouTube に映像のアップロードを行うには,まずアカウントを作成する必要がある。アカウントを作成するにはメールアドレスを登録する必要がある。 BugMeNot を利用するという手も考えられるが,あまり誠実な方法であるとは言えない。要求される個人情報は非常に少ない(メールアドレスと国籍・年齢程度)ため,アカウントを作成すること自体にあまり抵抗は感じられなかった。

アップロードの作業自体に戸惑うような点は何も無かった。どういった動画形式に対応しているのかいまいちよく分からないが,ムービーメーカーで作られるような形式であれば問題無くアップロードすることができるようではある。アップロードしてから数分間待つと,サーバー側での変換作業が完了し,誰でも映像を閲覧することが可能になる。ただし,検索にヒットするようになるには,もうしばらく待つ必要があるらしい。

今回作成した映像

個人的には既に長い付き合いのシンセサイザー KORG Electribe MX を利用して,少し変わった音作りの方法を試してみる ― というような内容の映像を作成した。内容は本当に大したこと無いが,何処かで誰かが趣味の幅を広げるための一助になれば幸いと考えている。

EMX bassline with Behringer effectors

Behringer 社の安価なコンパクトエフェクターを連結して音作りに利用している。これらのエフェクターはいずれも 3000 円程度で購入することができる。 PC のプラグインソフト等を利用すればもっと簡単かつ安価に実現することのできる内容ではあるが,決してバーチャル製品では得ることのできない「ガジェット感」が独特の趣きを醸し出してくれる。プロユースはともかくとしても,趣味としてはその点が重要であると感じられる。

Failure-Oblivious Computing

2006-08-09

Martin Rinard, Cristian Cadar, Daniel Dumitran, Daniel M. Roy, Tudor Leu, William S. Beebee, Jr. Enhancing Server Availability and Security Through Failure-Oblivious Computing. In Proceedings of the 6th Symposium on Operating Systems Design and Implementation. December 2004.

C や C++ を始めとする非安全 (unsafe) な言語においては,不正なポインタの参照(配列のオーバーラン等を含む)を原因とした不具合が非常に多く見られる。また,これらの不具合はいわゆる「脆弱性」としてハッキングの突破口とされることが多い。ゆえに,これらの不具合を未然に防ぐことは,ソフトウェアの堅牢性を向上させるうえで非常に重要な課題であると言える。

Rinard らは "failure-oblivious computing" (エラー忘却型コンピューティング)と呼ばれる手法によって,これらの不具合を回避することを試みている。「エラー忘却」とは,エラーが発生してもそれを「無かったこと」にしてしまうという手法を指す。この手法においては,不正なポインタを経由したメモリ書き込みは完全に無視され,不正なポインタを経由したメモリ読み込みには適当な値が返され,あとは何事も無かったかのように処理が続けられてしまう。

エラー忘却処理の実装には,基本的に不正ポインタ参照の検出と同様の技術が使用されている。 Rinard らの実装は特に Ruwase らの CRED (C Range Error Detector) [CRED] に基づいている。従来の手法においては不正なポインタの参照を検出した瞬間にプログラムを停止させていたのに対して,エラー忘却手法においてはそれらに無効な応答を返したうえでプログラムを続行させる。

エラー忘却手法において懸念される問題としては,不正ポインタ参照の検出に要される負荷の問題や,エラーを無効化することが却って予期せぬ状態を作り出してしまう危険性などが挙げられる。しかし Rinard らはエラー忘却の機構を Apache や Sendmail 等の既存のソフトウェアに対して適用し,それらのソフトウェアを実際に運用してみることによって,それらの懸念が案外に問題とはならないことを実証した。

エラー忘却手法が案外にうまく適用できる理由としては,一般的なアプリケーションにおけるエラー波及範囲の狭さが指摘されている。大規模な算術演算を行うようなソフトウェアであれば,僅かなエラーが最終結果を大きく狂わすというシナリオも考えられるが,メールクライアントやウェブサーバーのようなごく一般的なアプリケーションにおいては,僅かなエラーは僅かな影響を及ぼすだけに終わる可能性が高いということを Rinard らは指摘している。

このようにエラー忘却手法は有効な手段であることが実証されたものの,多くの技術者・研究者は,このような手法に対して比較的厳しい見方を示している [lambda] 。直感的に分かるように,この手法は明らかにモラルハザードの原因となりうる。ソフトウェアの完成度が未熟な段階からこのような手法を導入すれば,エラーを正すためのモチベーションは徐々に薄れてしまい,いずれはエラー忘却の機構に頼り切った姿勢へと陥ってしまうことが危惧される。著者らもその点は強く認識しており,「傍観者効果」 (bystander effect) が発生する危険性をこの手法の欠点として示唆している。それを防ぐための確実な手段は,開発中のソフトウェアにはこの手法を適用しないことであるとも述べている。

Crash-Only Software

2006-08-14

George Candea, Armando Fox. Crash-Only Software. In Proceedings of the 9th Workshop on Hot Topics in Operating Systems (HotOS-IX). May 2003.

多くのオペレーティングシステムには,ある種のクラッシュ耐性が備えられている。システムによってその復元性能に差は見られるが,クラッシュによって不正にシステムが終了させられても,次の起動時には正常な状態へと復帰できるようになっている。

ここでひとつの疑問を投げかけることができる。もしクラッシュしても正常に復帰することが保証されているならば,そもそも正常に終了するための手続きは必要とされるだろうか? その保証があるのならば,常にクラッシュによって終了させても構わないのではないだろうか? 究極的には,クラッシュと正常終了を区別する必要など無いのではないだろうか?

Candea らは,ここでひとつの興味深い実験を行っている。各種のオペレーティングシステムにおいて「正常終了の手続きを経てリブートした場合に要される時間」と「クラッシュを経てリブートした場合に要される時間」の比較を行うというものである。その結果は,反語的であるとしか言いようのないものとなっている。

060814_0.jpg
リブートするならクラッシュさせた方が手っ取り早い? 表は Candea らより。

どのような規模のシステムであっても,それが実世界に存在するものである限り,クラッシュの可能性を消し去ることはできない。従って,クラッシュに対する耐性は,どのようなシステムにも求められる特性のひとつとして考えなければならない。むしろ,クラッシュをシステムの常態のひとつとして組み入れるべきなのかもしれない。システムは常にクラッシュに遭遇しうることを前提として動作し,クラッシュののちには安全かつ速やかに復帰することができるようにしておく。このような思想を極端に押し進めれば,もはやクラッシュ以外による終了の手段を用意する必要さえ無くなってしまう。 Candea らは,この思想を「クラッシュオンリー」 (crash-only) と名付け,その実現に必要とされる様々な属性について考察を行っている(一種のデザインパターンを提示していると見てよい)。

しかし,何故にクラッシュしないシステムを構築することは不可能なのだろうか? ここで Candea らは,ソフトウェアの指令的 (prescriptive) 性質を指摘する。

例えば,実世界に存在する物理系を扱う場合ならば,ニュートン力学を始めとする種々の物理法則を適用することによってその挙動を理解することができる。そのような意味において,物理系は記述的 (descriptive) 性質を持つと言うことができる。これに対して,ソフトウェアは従うべき物理法則を持っていない。ソフトウェア設計者は,形式的モデルや不変性の証明を用いて自ら「法則」を組み立てなければならない。そのような意味において,ソフトウェアは指令的 (prescriptive) 性質を持つと言うことができる。

このような「指令的法則」は,システムをある種の抽象性をもって捉えたモデル ― いわゆる「抽象モデル」に関して構築されることが専らであるが,その抽象モデルはシステムの挙動を完璧に捉えているとは限らない。例えば,ある種のハードウェアについて発生しうるあらゆる種類の不調を適切に捉えることのできる抽象モデルなど過去に存在したことがあるだろうか? それが論理的に可能であるか不可能であるかという議論はさておき,その試みが恐ろしく困難なものであることは間違いない。

クラッシュオンリーの思想とは,このようなコンピューターシステムの世界を予測可能なものへと変えるための方法論のひとつであると考えることができる。システムを構成する各コンポーネントがクラッシュオンリーの規約に従っている限り,そこにはある種の単純性がもたらされる。あらゆるコンポーネントに対してクラッシュオンリーの属性を与えることは決して容易ではないが,それによってコンポーネントの統合は容易なものとなり,システム全体の信頼性は向上することを考えれば,その効果はシステムが大規模化し複雑化するほど重要なものになると考えられる。

クラッシュオンリーの思想は,マイクロリブート (microreboot), マイクロリカバリ (microrecovery), あるいは復旧指向コンピューティング (recovery oriented computing; ROC) の名で取り上げられることも多い [ITpro] 。また,スタンフォード大学は Crash-Only Software and Recursive Microreboots プロジェクトのページから多くの関連文献を参照することができる [Stanford] 。

Happy Hacking Keyboard

2006-08-15

060815_0.jpg

Happy Hacking Keyboard Professional 2

たかがキーボードに2万円も出すのは馬鹿げているような気もする。しかし,これ以外に選択肢は無いと思わせるだけの説得力を持っているのだから仕様がない。

「そうであるべきことが,すべてそうあるように作られている」 ― ミニキーボード好きにとっての Happy Hacking Keyboard Professional 2 は,全ての正しいデザインを寄せ集めた完全解の姿であるように感じられる。余りにも自然な姿をしたこの製品に2万円も払うことは躊躇われるかもしれないが,その自然さを知ってしまった次の瞬間からは,これ以外の製品が皆不自然に感じられるようになってしまう。そうなれば最後,いくら高かろうがこの製品を買うしか道は残されていない。

初代 HHK との大きな違いは, USB への完全対応と,静電容量無接点方式の採用にある。たかが USB への対応にも隙は無く,内蔵のハブは USB 2.0 対応,ケーブルは取り外し可能となっている。特に後者の点は意外に重要で,持ち運び時に邪魔にならない,ケーブルを好きなものに交換することができる,等々のメリットがある。持ち運ぶ用が無くとも,ケーブルを巻き取り式の極細 USB ケーブルに取り替えるだけで,ずいぶんと机の上がすっきりする。ほとんどのキーボードがケーブルを直付けしている中で,このような発想に至った事は賞賛に値すると感じられる。

静電容量無接点方式の採用は,少々ふわついた感じのあった初代 HHK のキータッチを,ふわりとしながらも軽い「押し心地」の感じられるキータッチへと変えている。賛否両論あるかもしれないが,個人的には大きな改良であると感じられた。

上の写真では Microsoft Wireless Notebook Laser Mouse との組み合わせで使用している。こちらの製品も素晴らしいもので,小型ワイヤレスマウスにようやく親指ボタンが付いたという待望の製品だった。レシーバーを HHK の USB 端子に取り付ける際は 3DOF の首振り USB アダプタを介すと邪魔にならなくて良い。

Mac mini

2006-08-16

自分の部屋に置く PC は,小さくて静かなものにしたい。それでいて,ある程度のマシンパワーは欲しい。余計なレガシーデバイスなんかは要らない。余計なバンドルソフトも要らない。安心して使いたいから自作やマイナーブランドのものは避けたい。コストパフォーマンスは決して無視しない。そしてもちろん, OS は Windows を使いたい。

それらの要求を総合したところ,浮上してきたのは,意外にも Mac mini だった。

060816_0.jpg

Mac mini の Core Duo モデルは約 10 万円する。メモリを 1GB, HDD を 100GB に拡張したカスタマイズモデルは約 12 万円となっている。これに Windows XP Home Edition を加えると,総額税込みで 15 万円程となる。若干割高に感じられるかもしれないが,法外に高いという訳でもない。

Boot Camp の導入は噂に聞く通り非常に簡単である。むしろ, Boot Camp を入れる前に行わなくてはならない Mac OS のアップデートの方が手間がかかる。 Boot Camp から Windows XP のインストールは 30 分もあれば完了させることができる。

ひとたび Windows XP を入れてしまえば,あとは拍子抜けするくらい普通の Windows マシンとして使うことができる。静音 PC としてはかなり優秀で,ノート PC と同じかそれ以下の動作音だが,手元から離れた所に置く事ができるぶん Mac mini の方が勝手が良いと感じられる。

最大の弱点は HDD のアクセススピードにあると考えられる。やはり 2.5 インチのドライブではデスクトップ機の高速なドライブと比較して差が出てしまうようで,特に起動の際などに若干の不利が感じられる(他方で Mac OS の起動が速いことには心揺らぐものがあるが……)。

Static Checking

2006-08-21

Cormac Flanagan, K. Rustan M. Leino, Mark Lillibridge, Greg Nelson, James B. Saxe, Raymie Stata. Extended Static Checking for Java. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pages 234-245. June 2002.

多くの言語処理系において,実行前に判明する不具合というものはごく狭い範囲に限られている。一部の情報はコンパイル時にエラーや警告といった形で提示されるが,それらの多くは文法上の誤りなどのように,静的な要素に起因する誤りを検出しているに過ぎない。配列のオーバーランや不正なダウンキャストなどのように,動的な要素に起因する誤りがそこで検出されることはない。また,設計と実装の不一致などのように,プログラミング言語の扱う範疇に無い誤りについても検出することはできない。それらの誤りを検出するには,アサーションや単体テストなどのように実行時に検証を行う機構を用いるのが専らとなっている。

これに対し Flanagan らは,実際にコードを実行しなくとも,コードの静的な解析のみによって多くの不具合を検出することができると主張する。このような手法を静的検証 (static checking) と呼ぶ。

静的検証の手法の応用例としては, Java の検証器 (verifier) を挙げることができる。 Java の検証器はバイトコード(クラスファイル)の静的な解析を行うことによって,そのコードの安全性を検証する。もし安全性に問題が見られれば,そのコードは危険なものとして実行を拒絶される。 Java の世界においては,このような静的検証の手法が存在することによってはじめて,そのセキュリティモデルを成立させることができている。

ただし, Java の検証器において検証対象となるのはコンパイル後の生成コードにおける型安全性を中心としたものであり,その目的はあくまでも実行時のセキュリティの確保に置かれている。ソフトウェアの開発の段階において不具合を発見することに役立てようとするならば,より複雑な検証技術を用いなければならない。

060821_0.png
Image from Flanagan et al.

上の図は静的検証の種類とその性質を表している。横軸は検証に要される労力を,縦軸は検証の及ぶ範囲に対応する。型検証 (type checking) は比較的少ない労力によって実現することのできる技術ではあるが,それによって検証することのできる範囲は限られている。かと言って,プログラムの全機能を検証するには途方も無い労力が必要とされてしまう。 Flanagan らは,それらの中間をレベル ― つまり「それなりの労力でそれなりの不具合を発見できるもの」を目指そうとしている。

図中に引かれた "decidability ceiling" ― 「決定可能性による限界」の線は,静的検証を行うことのできる理論的な限界を示している。例えば配列のオーバーランなどのように,動的な要素に起因する誤りの多くはこの上に含まれる。これらの誤りについては,どのように高度な技術と多くの労力を注ぎ込んだとしても,静的検証によって健全性(全ての誤りを含むこと)と完全性(嘘の誤りを含まないこと)を実現することはできない。

しかし Flanagan らは,実践において「決定可能性による限界」が問題になることは殆ど無いと指摘する。たとえ不健全かつ不完全であっても,早期に誤りの可能性を提示することができれば,それはソフトウェア開発の工程において少なからぬ利益があると考えられる。 Flanagan らの検証器 (ESC/Java) は, Java コードにおける null 参照や配列のオーバーラン,不正なダウンキャスト,スレッドの競合状態,デッドロックなどを検出することができる。確かに,完全ではなくともこれらの不具合を早い段階において見つけることができるならば,それは非常に有り難いことであるに違いない。

また ESC/Java は注釈言語 (annotation language) を用いた設計面の要素の検証にも対応している。これは,いわゆる「契約による設計」 (design by contract) の手法がアサーションを用いて設計の記述を行っていくのに似ている。注釈言語を用いてオブジェクトの不変条件や関数の事前条件・事後条件を記述しておくと,それを静的検証にかけることができる。これによって,これまでは実行時に行う術しか無かった設計面の検証をも,実行前に済ませてしまうことができるようになる(ただしもちろん健全性・完全性は保証されない)。また,注釈言語の記述はコメントとしてコード内に行われることから,「良いコメントの指針」となることも指摘されている。場合によってはコメントの記述の誤りが検出されることさえありうる。

これまで静的検証の技術があまり広く用いられなかった理由としては,その技術的な困難さと共に,検証に要される労力の多さも一因にあるのではないかと思われる。 Flanagan らの実験によれば, 50 行以下の関数であれば 10 秒以内に検証を終えることができるものの,数百行に達する関数の場合はその検証に 1 分以上の時間が要される場合もある。 Javafe と呼ばれる約 30,000 行のプロジェクトを検証にかけた際には,その全ての処理に 73 分の時間が要された。また,既存のプロジェクトに対して検証を適用するには,不要な警告を潰すために適切な注釈を手作業で加えておく必要があるが, Javafe の場合はこの作業に 3 週間が費やされている。静的検証の技術が広く実用に耐えうるものとなるには,検証に要される時間の短縮と,注釈の手間の軽減が求められるのではないかと思われる。

Spec#

2006-08-22

静的検証器 ESC/Java の開発者の一人である K. Rustan M. Leino 氏は,現在 Microsoft Research において Spec# システム [Microsoft] の研究に携わっている [Leino] 。もちろん,氏が ESC/Java において培った技術は Spec# プロジェクトにおいても活かされている。

Spec# は Microsoft Research において研究の進められているプログラミング・システムの一種であり,言語仕様の上では C# のスーパーセットとして位置づけられる。システムの概要を一言で表すならば「C# 向け DbC 環境」(DbC = Design by Contract; 契約による設計)とでも言うべきものであり,開発と保守の両面からコストを軽減する技術となることが期待されている。

060822_0.jpg
Image from Leino's slide

Spec# では,関数の事前・事後条件,オブジェクトの不変条件をコード内に記述することが可能になっている。また,型の修飾の一種に「非ヌル型」 (non-null type) と呼ばれるものが追加されており,これはヌル参照を避けるための簡便な手段として役立てることができる。これらの表明は実行時の検証処理に反映されるほか, Boogie と呼ばれるコンポーネントによって静的検証にかけることもできるようになっている。静的検証を用いれば,コード自体は一切実行することなく,開発環境の中だけで対話的に検証作業を行うことが可能になる。

060822_1.jpg
Image from Leino's slide

Spec# は単に C# 向けの DbC 環境として見ただけでも興味深いものだが,それに静的検証の技術を応用しようとしている点は特に面白く感じられる。果たして静的検証の技術は,一般的な C# プログラムに対して有益なものとなりうるのだろうか? その答えを氏らが何らかの形で見せてくれることを期待したい。

Failure-Obliviousness in Google

2006-08-23

Rob Pike, Sean Dorward, Robert Griesemer, Sean Quinlan. Interpreting the Data: Parallel Analysis with Sawzall. Scientific Programming Journal, 13(4):277-298, 2005.

プログラミング言語 Sawzall は Google 社内において開発されたデータ処理言語の一種である。その設計は同社の基盤技術である GFS [Ghemawat] や MapReduce [Dean] に合わせて特化されており,処理の並列性に関して非常に高いスケーラビリティを実現している。そのデータ処理言語としての利便性は非常に高く,今や Google 社内において最も広く用いられている言語の一つとなっている(ただし,ウェブサーチのインデクス生成には C++ コードが用いられているとのことなので,それ以外のアプリケーションに広く用いられているものと推察される)。

興味深いことに, Sawzall はエラー忘却型コンピューティング (failure-oblivious computing) [Rinard] の手法を採り入れている。エラー忘却型コンピューティングとは,プログラムの実行中に発生したエラーを「無かったこと」にすることによってシステムの頑健性を高めるという手法である。やや乱暴な手法ではあるが,バッファーオーバーランなどを悪用した攻撃に対して高い耐性を発揮することが確かめられている。

通常, Sawzall におけるエラーは無定義値 (undefined value) と呼ばれる概念によって扱われる。無定義値は I/O エラーやゼロ除算などが発生した際に返却される値であり,これを読み取ろうとするとプログラムは停止する。プログラム側では def 述語関数を用いて無定義値を検出し,適切な対処を行うことが求められている。

060823_0.png
Image from Pike et al.

ところが, Sawzall に用意されている「実行時フラグ」 (run-time flag) を有効にすると,無定義値の読み取りによるプログラムの停止は行われなくなる。そして,無定義値に関わる処理は全て省略される ― つまり「無かったこと」にされてしまう。アプリケーションをリリースする際には,このようなフラグを有効にすることが推奨されている。

Pike らはこのようなポリシーを採用した理由として,テラバイト級のデータが持つ特殊性を指摘する。いかに注意深くエラー処理を設計したとしても,広大かつ多様なデータを扱ううちには,誰も考え得なかったような驚くべきデータに出くわすことがある。そのような,言わば「狂ったデータ」に対して逐一丁寧な対処を行っていくのは,果たして賢い方法であると言えるだろうか? Pike らは, Sawzall が扱うような種類のデータに限って言えば,そのような「狂ったデータ」を無視してやるだけでシステムの安定性を確保することができると主張する。

NStatic

2006-08-26

ブログ Smart Software の Wesner Moise 氏は,同氏の持つ AI 技術を応用した最初の製品として, NStatic と呼ばれる静的検証ツールの開発を行っている。製品の概要と開発の進捗については同氏のブログに詳しい [SmartSoftware] 。

静的検証とは,プログラムを静的に解析することによって,そのプログラムの「正しさ」を確かめる技術のことを指す。つまるところ,プログラムを動作させることなくテストすることを可能にする。このような技術を用いることによって,プログラムに含まれる不具合の発見を早期に行うことが可能になると考えられている。

060826_0.jpg
Image from Smart Software

060826_1.jpg
Image from Smart Software

NStatic は,将来的には様々な言語に対応することが予告されているが,まず最初は C# 専用の検証ツールとしてリリースされる予定になっている。また, Spec# [Microsoft] 形式の注釈の記述にも対応しており,これにより設計上の意図を検証の対象に含めることが可能になっている。

リリースのスケジュールに関しては,未だ詳しく語られていない。非公開ベータのリリースは既に行われており,近い将来に公開ベータのリリースが行われる模様である。

Moise 氏の述べるところからすると, NStatic は非常に野心的な製品であることが伝わってくる。また, NStatic はあくまでも副次的な製品であり,本来の目標は AI 技術を応用した文書作成補助ツールを開発することにあるとも述べられている。両製品共に挑戦的な内容であり,どこまでが本気なのか量りかねる側面もある。同氏の自信と知識の豊富さを見る限りでは,一応に狙い通りのものを作り上げることは可能であろうと思われるものの,それが一般にどの程度まで実用的なものであるかは,やはり量りかねるものがある。

MapReduce

2006-08-31

Jeffrey Dean, Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. In OSDI'04, 6th Symposium on Operating Systems Design and Implementation, pages 137-150, 2004.

関数型プログラミングを会得しない限り, Google に強大なスケーラビリティをもたらしたアルゴリズム ― MapReduce を発明することはできないだろう。 -- Joel Spolsky [Joel]

たしかに MapReduce は面白い。これほどまでに単純なプログラミングモデルによって,あの巨大なクラスターが駆動しているというのだから,面白くないはずは無い。ただ,その面白さに目を奪われてしまうと,それが分散処理における無数のソリューションのうちのひとつに過ぎないという事実をも忘れてしまいかねない。 Joel Spolsky が MapReduce 云々から Java 批判を展開したとしても,それを気に病む必要は無い。氏はケレンでやっているのであって, Java にクロージャを付け足したところで収まるような話ではないのだから [LtU] 。

概要

MapReduce は Google 社の Jeffrey Dean らによって開発された分散処理のためのプログラミングモデルである。同名の C++ ライブラリとして 2003 年初頭から運用が開始され,論文が執筆された 2004 年末の時点で同ライブラリを使用するプログラムは 900 ほど存在すると記されている。その代表的な応用例としては, Google News や Froogle におけるクラスター解析, Google Zeitgeist [Google] におけるクエリー統計などが挙げられる。もちろん,最も重要な応用例は,同社最大のサービスであるウェブ検索のためのインデクス生成処理であるに違いない。それまで専用の分散処理によってまかなわれていたインデクス生成の工程は,現在では MapReduce を使用したものとして全面的に書き換えられている。

"MapReduce" という名称は,大規模データの処理を「map タスク」と「reduce タスク」の2段階から構成することに由来する。いかにも関数型言語ファンが喜びそうなネーミングだが [LtU] ,実際には「フィルター」と「アグリゲーター」の2段階から構成されると言った方が分かりやすいかもしれない。現に [Pike] らなどはそのような説明を行っている。

060831_0.png
Image from Pike et al.

map タスクは,膨大な量の元データを分解し,必要な情報を抽出し,有用な形へと変換し出力する,いわゆる「フィルター」の役目を担う。 reduce タスクは,抽出された情報を集約し,一塊のデータとして出力する,いわゆる「アグリゲーター」の役割を担う。このうち map タスクが純粋にフィルターとして振舞う(副作用が無い)ならば,この処理を複数のマシンで手分けして行うことができる。たとえ処理対象のデータがテラバイト単位で存在したとしても,その処理を数百台のマシンへと効率良く分配することができたならば,現実的な時間内で処理することが可能になると考えられる。

動作

MapReduce の動作を説明するには,論文の冒頭に挙げられている単語カウントの例を用いるのが分かりやすくてよい。ここでは,膨大な文書 ― 例えば「ウェブ上のテキスト全て」などから,単語の出現頻度を調べたいとする。

まず最初にその膨大な文書を,数十台から数百台のワーカー (worker) 上で動く map タスクへと分配する。 map タスクは渡された文書を単語毎に分割し,その単語毎に "<word,1>" というような<キー,値>の対を発行する。この対はワーカーのローカル記憶領域内に存在する中間ファイル (intermediate file) へと蓄積される。

060831_1.png

この map タスクの擬似コードは以下のようなものになる([Dean] より引用)。

map(String key, String value):
  // key: 文書名
  // value: 文書の内容
  for each word w in value:
    EmitIntermediate(w, "1");

map タスクが完了したならば,次に,単一ないしは複数のワーカー上において reduce タスクが開始される。 reduce タスクはワーカーを巡回し,あるキーに関連付けられた値を列挙し集約する。単語カウントの例で言えば,キー(単語)毎に関連付けられたカウント値(中身はすべて "1")を列挙し,その総計をとることによって集約を行えばよい。

060831_2.png

この reduce タスクの擬似コードは以下のようなものになる([Dean] より引用)。

reduce(String key, Iterator values):
  // key: 単語
  // values: カウント値のリスト
  int result = 0;
  for each v in values:
    result += ParseInt(v);
  Emit(AsString(result));

これで,各単語に関して出現頻度が導出されたことになる。

各タスクは,入出力として<キー,値>の対を用いる。これに注目するとデータの流れを簡潔に把握することができる。

map: <文書名, 文書内容> ⇒ [<単語,"1">, <単語, "1">, ...]
reduce: <単語, ["1", "1", ...]> ⇒ <単語, カウント値>

map タスクは入力を細かな中間情報へと分解し, reduce タスクはその中間情報を集約する。たったそれだけであると考えると,かなり制約の厳しいプログラミングモデルであるように感じられるかもしれない。しかし,このようなプログラミングモデルでも様々な処理を実現することが可能であることを Dean らは提示している。一例を挙げれば,ウェブページのいわゆる「逆リンク」リストを生成するには次のような MapReduce を適用すればよい。

map: <URL, ページ内容> ⇒ [<リンク先, URL>, <リンク先, URL>, ...]
reduce: <リンク先, [URL, URL, ...]> ⇒ <リンク先, 逆リンクリスト>

ただし,もちろんのこと,すべての処理が 1 回の MapReduce の適用によって済まされる訳ではなく,複数の MapReduce を組み合わせることによって処理を達成する場合も見られる。例えばウェブ検索のインデクス生成処理においては MapReduce の反復が 5 回から 10 回ほど行われていると記されている。

効率

MapReduce に見られる大きな特徴のひとつとして,そのスケーラビリティの高さが挙げられる。以下のグラフは, Sawzall 言語によって組まれた簡単なログ解析の処理を異なるコンフィギュレーションにおいて実行し,その結果をプロットしたものである。

060831_3.png
Image from Dean et al.

実線は処理完了までに要された時間を表し,点線は処理に費やされた総マシン時間(延べ処理時間)を表している。理想的なスケーラビリティのもとでは,実線は反比例曲線を描き,点線は水平線を描くはずである。実際には点線が多少右肩上がりになっている(マシンが増えるほど余計な処理時間が費やされている)ものの,その増分は 3 割ほどに抑えられている。マシン数を 50 台から 600 台 ― つまり 12 倍へと増やしているにも関わらず,マシン時間の増加がこの程度に抑えられているという事実は,十分なスケーラビリティがそこにあることを実証していると言える。

ちなみに,論文が執筆された時点において,単一の処理に割り当てられるマシン数の平均は 157 台であり,1ヶ月間に消費される総マシン時間は約 8 万日であったと記されている。

特殊性

MapReduce を構成するタスクのうち map タスクが並列実行可能であることは自明に思われる。他方で reduce タスクの方は,個々の操作が可換 (commutative) ないしは結合法則を満たす (associative) とすれば階層的に並列実行することが可能だが, MapReduce においてはそのいずれも前提として設けられていない。 reduce を並列実行するには,単純に出力ファイルの数を増やしてしまう(集約処理を分割する)か,あるいは combiner と呼ばれる特殊な機構(map ワーカー上で部分的な集約を行うもの)を用いなければならない。このような点を見る限りでは,明らかに map タスクの方が並列実行に特化されており, reduce タスクの並列性の低さが目に付いてしまう。

このような map と reduce の間に見られる非対称性は,恐らく Google の扱う問題領域の特殊性から生じるものであろうと思われる。上の単語出現頻度の例などでは出力をひとつに集約する必要があったが,多くのクラスター解析においては出力をひとつに集約する必要は避けられるものなのではないかと思われる。また,出現頻度の例にしてみても,正確な解を求めるのではなく近似解を許すのであれば,特殊な手法を用いることによって集約処理の軽量化を図ることができる [Charikar] 。

Dean らも参考文献に挙げているように,結合法則を満たす操作を並列実行するための一般的な手法は過去にも数多く存在した。そのうえで Dean らが行った事とは,実世界の大規模なクラスターにおいて運用可能な形態へと洗練したこと,強固な耐障害性を備えさせたこと,そして,並列化技術の心得が無い技術者でも容易に理解することのできる単純なプログラミングモデルを提示したこと,等が指摘される。ただし,それらの改良は Google の扱う特殊な問題領域にあってこそ初めて可能となったものであり,他の領域へと展開が可能であるとは限らないことを心に留めておく必要があるのではないかと思われる。