岡野原君が自然言語処理関連で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」など、データベースに関連する様々な教科書を紹介しています。
- 論文ファイブ 稲葉君によるプログラミング言語関連の論文紹介。これを見ると、データベース屋とプログラミング言語屋さんはとても似た問題を扱っていると感じる
- 昨年の論文を振り返る 岡野原君による自然言語・圧縮関連の論文紹介。
0 件のコメント:
コメントを投稿