Percolator: 大規模データ用の逐次更新処理システム

作者 Jean-Jacques Dubray , 翻訳者 吉田 英人 投稿日 2010年10月9日

セクション

設計/アーキテクチャ

トピック

Google ,

Architecture ,

パフォーマンス&スケーラビリティ ,

MapReduce ,

トランザクション

共有 |

原文(投稿日：2010/10/05)へのリンク

データを収集，蓄積する量が驚異的な速さで増大していくにつれ，かっては世界中で Google のものであったスケーラビリティへの要請はより一般的なものとなり，ソリューションとして求められる機会も多くなった。Daniel Peng，Frank Dabek の両氏は，Google のインデックスシステムである Percolator を詳説する論文を発表した。Percolator は数十ペタバイト規模のデータを数千台のマシン上に蓄積し，一日あたり数十億の更新処理を実行するシステムだ。

ドキュメントをクロールして Web のインデックスを更新する，という作業では，新たなドキュメントの獲得に従って，既存ドキュメントの巨大なリポジトリを継続的に更新する必要があります。このタスクは，大規模なデータリポジトリを独立的な小さな変化の反映によって変更する形式のデータ処理の好例です。この種の処理は，既存のインフラストラクチャの能力的なギャップに存在しています。データベースでは，これらのタスクに伴うストレージやスループットの要請に適しません。[一方で] 大規模なバッチを作成することで効率性を実現する MapReduce やその他のバッチ処理システムでは，この種の独立した小規模な更新を処理できないのです。

それでも両氏によれば，インデックス処理そのものは一括処理可能なタスクであって，MapReduce 処理の連続によって実行することは不可能ではない。問題になるのはリンクの存在だ。これのためにインデックスの更新は，一連の再クロール処理の終了後に新しいページに対して MapReduce 処理を実行するだけでは不十分であり，リポジトリ全体に対して処理しなければならなくなる。事実，Percolator 以前の検索インデックスはこのような方法で作成されていたのだ。実行時に生じる遅延が，このアプローチでは主要な問題となる。

解決の鍵は，逐次処理(incremental processing)を最適化する能力にある。Percolator の背景にある設計上の重要な概念のひとつに，リポジトリへのランダムアクセス機能の提供がある。ドキュメントを個別に処理することによる，MapReduce への大域的処理の必要性回避がその目的だ。Percolator はまた，複数マシン上の複数のスレッドでリポジトリを操作可能とするために，スナップショット分離 (snapshot isolation) を通じて行間およびテーブル間の ACID準拠のトランザクションを提供するように設計されている。さらにユーザが指定した列の変更毎にシステムによって起動され，計算状態のトラッキングを行う "オブザーバ" も用意されている。

加えて著者らは言う。

Percolator は逐次処理を目的として開発されています。既存の一般的なデータ処理タスクの代替を目指したものではありません。処理結果を細分化できない種類の処理 (ファイルの並べ替えのような) を扱うのは MapReduce の方が適しています。

Percolator は強固な一貫性，膨大なデータ量と CPU を要する計算処理に適したシステムだ。Google の場合，主要なアプリケーションは ライブ Web 検索インデックスなどの Web ページ処理である。Percolator によって同社は，クロールしたドキュメント処理の平均遅延時間の2桁オーダでの削減，ドキュメントの平均保持時間の50% 減少を実現している。

Percolator はBigTable 分散ストレージシステム上に構築され，クラスタの全マシン上で動作するワーカ (Worker)，BigTable タブレットサーバ (BigTable tablet server)，Google ファイルシステムチャンクサーバ (Google File System chunkserver) という３つのバイナリで構成されている。

すべてのオブザーバは Parcolator のワーカにリンクされています。ワーカは BigTable の更新されたカラムをスキャン ("通知 / Notification") し，ワーカプロセス内のファンクションを呼び出して対応するオブザーバを起動します。オブザーバは BigTable タブレットサーバに，読み込みあるいは書き込みの RPC を送信することによってトランザクションを実行します。この RPC は GFS チャンクサーバにも転送されます。

Percolator には集中的なトランザクション管理や，大域ロック検出の機構が存在しない。従来の DBMS 上で OLTP タスクを実行する場合のような低レイテンシ要件を持たないことから，数十秒単位のトランザクションコミットの遅延を引き起こすロックを排除する目的でレイジーアプローチ (lazy approach) を採用しているのだ。

この方法でトランザクションの競合によるレイテンシは増加しますが，システムを数千台のマシンにまでスケールすることが可能になるのです ...強力なトランザクションの恩恵がなくてもデータを逐次処理することは可能です。しかしトランザクションは，ユーザにとってシステム状態の把握と，長期持続されるリポジトリでのエラー発生の回避を容易なものにしてくれるのです。

Percolator のアーキテクチャは，桁外れに多数の一般マシンのような構成においても直線的にスケールする。パフォーマンスの面で見ると Percolator は，MapReduce と DBMS の中間程度である。分散アーキテクチャであることから同一量のデータ処理に対して DBMS よりもはるかに多くのリソースを使用する上，30倍ものオーバーヘッドが発生しているためだ。しかし MapReduce との比較では，ランダム検索をサポートするリソースの配備によって極めて低いレイテンシでのデータ処理を実現している。このシステムは2010年4月から Google の Web 検索インデックスを提供し始めているが，許容できる範囲のリソース増加でレイテンシの削減を実現できている。

読者であるあなたは現在あるいは今後において，巨大データセットを操作するニーズをお持ちだろうか？Phil Wehlan 氏が現在，これと同じ質問に対するフィードバックを求めている。