Google Researchにて「Large-scale Incremental Processing Using Distributed Transactions and Notifications」という論文が公開されました。GoogleはこれまでMapReduceにて大規模な処理を扱っていましたが、常にデータ全体に対して行わなければならず、小さな更新をたくさん行うような処理には向いていません。これに対し、Web検索エンジンのようにクローラがWebページを取得するたびに逐次的に処理を行い、短い間隔で検索インデックスの更新を可能にしたシステム「Percolator」を構築しました。論文ではPercolatorの概要やアーキテクチャ、導入による効果検証について書かれています。

Percolatorの特徴は、ペタバイト級のリポジトリに対してランダムアクセスが可能な点です。また、利用者側がリポジトリの状態を確認できるACID（Atomicity, Consistency, Isolation, Durability）トランザクションや処理状況を確認できるオブザーバが用意されています。PercolatorシステムはBigtable上に構築され、クラスタ内の各マシンでPercolatorワーカ、Bigtable tabletサーバ、そしてGFS chunkサーバの3つのプログラムが実行されています（図2⁠）⁠。また、スナップショット分離を実現するためのタイムスタンプやグローバルなデッドロック検出機構の代わりに軽量ロックを導入するなどの機構を備えています。

Percolatorのポリシーとして、トランザクションの遅延に寛容なことも特徴的です。場合によってはトランザクションコミットが十数秒も遅延する可能性がありますが、トランザクション実行中のマシンに障害が発生してロックが残ってしまっても、クリーンアップを行って全体に影響を及ぼさないようにすることが可能です。

Percolatorは論文でも指摘しているように、決してどんな処理にでも適用できる万能なシステムではありません。ファイルソートのように結果を小さな更新に分割できないような処理はMapReduceが適していますし、データが大規模でなかったり大きなトランザクション遅延が許されないような処理はRDBMSに任せたほうが良いです。しかし、大規模なデータに対して逐次的な更新処理を行うにはPercolatorは非常に適しており、実際にWeb検索エンジンに導入したことでドキュメントの平均処理時間は100分の1に、検索結果に表示されるまでの平均時間は50％削減するなどの効果が得られました。

ちなみに、「⁠Percolator」という単語は「コーヒー沸かし器」の意味ですが、Googleの新しい検索エンジンが「Caffeine」と呼ばれていることからコーヒー関連の名前を付けるのが決まりになっているのかもしれません。

URL：http://research.google.com/pubs/pub36726.html