Pondering Bug Tracking Systems

As a programmer, I have many things to hack, but unfortunately I am not smart enough to remember everything to code after I slept. In the next morning, I usually forget some features to code. Bug Tracking System (BTS) is useful to keep remembering these tasks.  Joel Spolsky also  wrote an article about Bug Tracking Systems, and I totally agree with what he said; Bug tracking system is necessary to ship high quality code. 

I am using Bug Tracking Systems, such as Bugzilla, Trac, etc. (and also their Eclipse plug-ins). Once they are properly installed in a server machine, they works correctly, and I know many projects use these tools to share bug & new feature lists. 

However, their web interfaces are not fun to use; I have to input many things to post a bug or feature, such as priority of the bug, current program version, who to assign the task, etc. Almost all of them are unnecessary for writing code, and sometime I do not want share tribal tasks merely saying 'implement SomethingReader class', but without posting it, I might forget it due to some interruption of my work.

Because of these frustrations, I have recently switched to the Remember the Mlik (RTM) service to manage my bug & feature lists. RTM's AJAX-based rich web interface have some nice shortcut keys (e.g, 't' for a new task, 1, 2, 3 ... for selecting priorities), and with Google Gears installed on your browser, you can edit tasks while you are offline. As the name 'Remember the Mlik' indicates, RTM can be used to manage quite tribal tasks; you can simply post 'write this code and that' to RTM, while this message does not make sense for the other people, it is quite informative for 'me'. 

Free from explaining what to do for other people has a great effect on accelerating daily programming productivity.  I'm not saying 'BTS is unnecessary', rather I'm saying BTS is necessary for sharing bugs and features, but not for personal work management. Well-known BTSes have too rich features for the personal use. What I want to do is to take a memo at online using web interfaces I open every day, and Remember the Milk completely meets this demand. 

Googleはコンピューターに損害を与える可能性があります

Googleの検索結果に「このサイトはコンピューターに損害を与える可能性があります」と付くので、不思議に思っていたら、Googleのサイトそのものも損害を与える可能性があるそうで。

まぁ、それなら仕方がないか(笑)

関連: Google May Harm ... @ Twitter

Googleがサイトの危険性を判定するにはStopBadware.org (WikiPedia: http://en.wikipedia.org/wiki/StopBadware.org) の情報を使っているようですね。結局なんだったんだろう…。今は直っているみたいです。

(追記)

この件について、GoogleのOfficial Blogで説明がありました。人的ミスで'/' が有害サイトのパターンに含まれてしまったとか。

正規表現に見切りをつけるとき

Perl, Rubyなど手軽に使えるプログラミング言語に慣れてくると、あらゆるテキストデータの処理に正規表現(regular expression)を使ってしまいがちです。

けれど実は、正規表現の処理能力を超えるフォーマットというのが存在します。その典型的な例が、XMLやJSONのように、入れ子になったデータフォーマットです。

例えば、

(a, b, (c, d))

(a, b, (c, (d, e)))

というように、括弧がどんどん入れ子になっていく構造は、括弧のネストの深さを数えないと正しく解釈できません 。正規表現でも、一番外側の括弧の対応をとらえるために、/\(.*\)/、/\([^)]*\)/ などとはは書けますが、常に正しい括弧の対応をとっているとは限りませんし、もしうまくいったとしても、さらに内部の括弧をとらえるために、外側の括弧を取り除き、また同様の正規表現を内部の文字列に対して繰り返して適用する必要があります。

そして問題なのが、

(a, (b, c)), d, (e, f)

という文字列の場合。/\(.*\)/という正規表現では、以下のように色のついた範囲を拾ってしまいます。

(a, (b, c)), d, (e, f)

正規表現では、このようにちょっとしたデータ構造すら上手く構文解析できません。したがって、正規表現だけで文字列を処理する場合は、何らかの方法で括弧が2重、3重にならないように工夫する必要があります。（あるいは括弧内を再帰的に処理するプログラムを書くなど。）バイオ系のデータフォーマットでも、この正規表現の能力の限界を知らないがために、正規表現で処理できない入れ子になったデータを平気で書いてしまう人が多いので、手軽に処理したい場合は要注意です。（他にも2重引用符で囲まれた文字列の扱いも、正規表現では面倒な例です）

構文解析

では、正規表現の能力を超えるデータはどう扱えばいいのか？一番のお勧めは、ANTLRを使って字句解析(lexer)、構文解析(parser)するプログラムを生成する方法です。一昔前なら、lex/yacc、flex/bison, JavaCCなどしか選択肢がなかったのですが、今は断然ANTLRが便利です。ここでは、JSONを例にとって説明します。以下は、JSONで書かれた配列の中に配列がある構造です。

[0, [1, 2]]

字句解析では、これを、

LBracket([), Number(0), Comma(,), LBracket([), Number(1), Comma(,), Number(2), RBracket(]), RBracket(])

というようにトークン（文字列の単位, lexer ruleとして記述）に分解していきます。そして、これらのトークンにマッチする文法（parser rule)を定義します（以下の例は、説明のために他のデータ型については省いて簡潔に書きました）

array: LBracket Value (Comma Value)* RBracket;

value: Number | array;

ここでは、括弧 [ ] の中に、ValueをComma(,)でつなげて複数個書けるルールを定義しています。Valueとしては、数字(Number)以外に配列(array)も使えるので、配列の中に配列があるような入れ子になったデータ構造もこれで解析できます。

参考までに、僕がANTLRで作成したJSONの文法を紹介します。ANTLRの記述を覚えるコストはかかりますが、1ページ分の記述量でJSONのように構文が複雑なものも処理できるようになります。以下に挙げるのは、ANTLRのリファレンス（英語）と、その背景にある理論の教科書で、コンピューターサイエンスの学科では講義によく使われていてどれもお勧めです。Aho, Ullman先生らのドラゴンブック第2版（Ullman先生の息子さんがCGで表紙を作ったとか）は読みごたえ十分ですし、Apel先生の本ではVisitorパターンの使いどころのような、実装に近い話題にも触れられていて読みやすいです。稲葉君絶賛のParsing Techniquesなどもあります。

構文解析の実践としては、ANTLRをダウンロードするとサンプルの文法がたくさん付いてくるので、それを真似して書くのも習得への早道かと思います。一度ANTLRで文法を書くと、Perl/Ruby/C/C#/Javaなどの言語用のlexer/parserを生成できるようになるので、どの言語を使っている人にもお勧めです。しかし、まだ日本語のリファレンスがないのが構文解析の敷居を高くしている原因でしょう。この記事が素晴らしき構文解析の世界への足がかりになればいいなと思います。

（実用上の補足）

正規表現の中に自己を含めて循環定義できるRubyやPerlなどの処理系なら、入れ子もなんとか処理できるみたいです。以下はPerlのコード例。(「詳細 正規表現 第3版」を参考にしました）

$str = "(a (b, c)), (d), (e, f)";
$paren = qr/\([^()]*(?:(??{$paren})[^()]*)*\)/;
while ($str =~ /($paren)/g) {
print $1, "\n";
}

実行結果

(a (b, c))
(d)
(e, f)

括弧のパターンにマッチすると、その都度中身の正規表現がlazyに変わっていくというトリッキーな技です。このような正規表現は以下に述べるような形式言語理論上の正規表現の定義には含まれないのでご注意あれ。ただ、Perlで処理できるとしても、二重引用符とか、様々な括弧の種類に対応するように再帰型正規表現を書いていくと、ANTLRのparser ruleを書くのと似た状況になるとは思います。(追記）Perl6のRulesという機能では、ANTLRのような文法定義を書けるとか！ 入れ子が必要なときは、これを使いましょう、ということですね。

(コンピューターサイエンス的な補足）

細かい話をすると、正規表現は文脈自由文法というクラスのサブセットで、入れ子の構造をもった文法は、文脈自由だけれど正規表現ではありません。これは、pumping lemmaを使って証明できます。情報系の学科なら、計算量理論などの講義で習うはず。オートマトンにスタックをつけたプッシュダウンオートマトン（文脈自由文法と同じ表現能力を持つ）なら、このような入れ子をうまく処理できます。このあたりの話は「計算理論の基礎」という教科書に丁寧に書かれてあって（大学院入試の勉強のときにかなりお世話になりました）、コンピュータサイエンスの基礎のうち、オートマトン、NP完全問題など計算量にかかわる部分について学ぶのに優れた本です。（最近は第2版もでているようですが、3冊に分かれてしまって少々買いにくくなってしまいました。分けた方が持ちやすいのかな？）

Top 5 Database Research Topics in 2008

岡野原君が自然言語処理関連で2008年に読んだ論文のベスト5を紹介しています。それに倣って、僕も個人的にインパクトのあった2008年のデータベース研究のベスト５を集めてみました。

• Michael J. Cahill, Uwe Röhm and Alan D. Fekete. Serializable Isolation for Snapshot Databases. SIGMOD 2008. (ACM DOI)

真っ先に思い浮かんできたのがこの論文。SIGMOD2008のベストペーパーでもあります。僕自身、トランザクション処理を長く研究していた経験から、Serializability（ディスクのread/writeの順番をあるプロトコルに従って入れ替えても、データベースの検索・更新結果に影響を与えない）を保障しつつ、一秒間あたりに処理できるトランザクションの数（つまりスループット）を上げるのは、ものすごく難しいことを実感していました。ロックの粒度、デッドロックの回避、インデックスのconcurrency(同時読み書き）管理などなど、同時に考えないといけない要素が多すぎるのです。

では、現在の商用DBMSではどう高速化しているかというと、snapshot isolationと言って、データベースのある時点での状態(これをsnapshotと呼ぶ）を保持し、readerはsnapshotを参照し、writerは新しいsnapshotを作るようにして、読み書きが衝突しないようにしています。これは確かに性能が出るのですが、特定のread-writeパターンで、serializabilityが崩れてしまい、トランザクションをやり直す（rollbackする) か、あるいは、rollbackが起こらないように検索・更新のworkloadを設計するのが大変でした。

この論文は、そんなsnapshot isolationを、性能をほとんど落とさずserializableにする話で、実装も簡単にできるという素晴らしさ。著者に会ったときにソースコードが欲しいと話したらBerkeleyDB上での実装を公開してくれました。（この話は「PFIに行きました」のエントリでも言及しています)。First AuthorのCahillさんは、Sleepycat (BerkeleyDBの開発元、現在はOracleに買収）で七年働いていたBerkeleyDBの開発者で、こんな改良を施すのもお手のものだとか。どうりでこんな研究ができるわけだと納得。

今後、トランザクションの教科書に一節が追加されるような非常にインパクトのある研究です。各種DBベンダーもこの方式を実装し始めているのではないかな、と思っています。（複雑なトランザクションの処理で新たなボトルネックが出てくる可能性はありますが）

参考文献：Alan Fekete , Dimitrios Liarokapis , Elizabeth O'Neil , Patrick O'Neil , Dennis Shasha, Making snapshot isolation serializable. ACM Transactions on Database Systems (TODS), June 2005　(なぜsnapshot isolationをserializableにできるか、という証明部分。こちらも面白い）

• S Harizopoulos, DJ Abadi, S Madden and M. Stonebraker. OLTP Through the Looking Glass, And What We Found There. SIGMOD 2008.
  

もう一つもトランザクション関連。MITのStonebraker教授(PostgreSQLを作った先生）のお弟子さんたちの研究ですが、現在主流のrow-oriented storage（テーブル行単位でディスクに配置していくもの）で、ロックマネージャーを外し、ログを外し、、、とやっても、トランザクションで100倍の性能を上げるのは難しい、ということを示した論文。近年、彼らの研究は面白くて、C-Store (列ごとにテーブルを分割して圧縮。性能抜群）や、 H-Store(トランザクションの意味を考えて、仕事の単位を分割、sequentialに処理して速度を稼ぐもの)など、One-size doesn't fit all (DBMSも用途に応じたものが必要）という時代の流れをリードしていく存在で、要注目です。

• Taro L. Saito and Shinichi Morishita. Relational-Style XML Query. SIGMOD 2008.　(ACM DOI)

手前味噌で申し訳ないのですが、XMLで表現されるデータ構造を「そのまま保持することに価値がある」と錯覚していた時代に区切りをつけるために、どうしてもこの研究が必要でした。ポイントは、XMLの構造そのものが重要なのではなく、XMLが含んでいるデータモデル(スキーマ）の方が大事で、「XMLの木構造はそのデータモデルの一表現にすぎない」、と示したことです。（参考：「Leo's Chronicle: XML時代の終焉 ~ XMLから再びCoddへ」）木をそのまま維持しなくてもよいようになると、XPath, XQueryなどの問い合わせ言語、インデックス、ストレージなど、従来のXML研究を見直していくことができ、木構造に捕らわれていては難しかったもの（例えば、木構造を保持した索引で、サイズが小さくかつ、更新しやすいものは、未だに作られていません）でも、木構造を捨てることで様々な最適化が期待できるようになりました。

• C. Olston, B. Reed, U. Srivastava, R. Kumar and A. Tomkins. Pig Latin: A Not-So-Foreign Language for Data Processing SIGMOD 2008.
  

Yahoo!のグループによる、分散計算と、構造化データを意識した新しい問い合わせ言語の設計、実装です。GoogleのMap-Reduceでは、分散計算を手軽に書けるのが特徴ですが、key, valueのペアでデータを出力するという枠組みは低レベルすぎで、構造を持ったデータをどんどん組み立てて処理を続けていくプログラムを書くには大変でした。

Yahoo!のPig Latinでは、データをグループ化したり、ネストさせたりする処理を導入して、プログラマの負担を軽減することを狙っています。似たような例として、フラットなSQLでは書きにくいのだけれど、XQueryだと階層をたどってデータを出力するプログラムが書きやすいという話があります。言語の能力的にはどちらが上ということもないのですが、「書きやすさ」は歴然と違う。SQLやkey->valueだけでは不便だったことを改善していく試みは、Relational-Style XML Query(XQueryでも不便だった階層を持ったデータの扱いを簡単にする）にも通じるところがあって、非常に関心を持ってウォッチしています。

• Remembering Jim Gray. Communications of the ACM 2008, Vol 51. No. 11.
  

最後は論文ではなく、雑誌記事の紹介です。1998年にTuring Award（コンピュータ系での言わばノーベル賞）を受賞し、 2007年にボートに乗って遭難してしまったJim Gray。トランザクション処理で大きな功績を残した、そんな彼に寄せられた記事を集めた特集号です。一人の研究者にこれほどのtributeが集まるのはすごいことです。Jim Grayは、ロックの粒度（テーブル単位、レコード単位のロックなど）を織り交ぜて使う手法を開発するなど、今なおその技術はDBMSの実装に使われています。トランザクション処理は非常に身近な存在です。銀行しかり、駅の改札もしかり。現代社会でJim Grayの恩恵を受けていない人はいないと断言しても良いです。

僕自身、Jim Grayとは巨大な生物データの扱いについてメールで議論したこともあり（駆け出しの研究者の僕にも、丁寧に返事をしてくれるような優しい人でした）、そんな彼が遭難したと聞いたときは、心にぽっかり穴があいたような、そんな気持ちになりました。僕だけでなく、やはり、これだけ多くの研究者に慕われているこの人の話題は外せない、ということで。2008年は彼の功績を振り返ってみるよい機会になった年でした。

以上、僕個人としてのトップ５研究でした。データベースは領域が広いので、興味が違えば、まったく別のランキングになるとは思います。SIGMOD, VLDB, ICDEなど国際会議もいくつかあるのですが、実際に会議に参加して雰囲気を肌で感じることができたのはSIGMODだけなので、とても偏ってますね。他の研究者による別の切り口での紹介も欲しいな、と思います。

関連エントリー

• Leo's Chronicle: ぜひ押さえておきたいデータベースの教科書 トランザクション処理やデータベースの基礎、 Jim Grayの書いた「Transaction Processing」など、データベースに関連する様々な教科書を紹介しています。
• 論文ファイブ   稲葉君によるプログラミング言語関連の論文紹介。これを見ると、データベース屋とプログラミング言語屋さんはとても似た問題を扱っていると感じる
• 昨年の論文を振り返る　岡野原君による自然言語・圧縮関連の論文紹介。

なぜIEはFirefoxより優れているか？

Firefoxでこんなことできる？

(Diggで見つけました）