大規模分散システムの現在 — GFS, MapReduce, BigTableは、どう進化したか
セミナー概要
21世紀の初頭、かってない巨大な規模の分散システムがネットワーク上で稼働を始めました。 現在のITを領導しているのは、こうした大規模分散システムを所有し、その上でサービスを提供しているGoogle, Amazon, Apple, Facebookといった企業達です。
クラウドの「利用」については、すでに多くの人の関心が集り、また多くの導入事例も積み上がっています。今回のマルレクは、それとは少し異なる角度から、大規模分散システムの技術の変化に焦点をあわせて、クラウドの現在を考えようと思います。
なぜ、私たちは、単にクラウドの「利用」だけではなく、大規模分散システムの技術の変化に注目する必要があるのでしょうか？
第一に、現代の大規模分散システムが取り組んでいるのが、規模の拡大の要求に最大限応えながら、同時に、リアルタイムの応答性を追求するという、現代のIT技術のもっとも重要な課題の一つだからです。
Web上のネットワーク・メディアの発展によって、止まることなく増え続けるWebスケールのアクセスと情報の増大の中で、リアルタイム性を追求するというのは、決して容易な課題ではありません。
第二に、現代の大規模分散システムは、大規模な情報をリアルタイムにハンドルしながら、同時に、正確なトランザクションを担保することを求められています。新しいネットワーク・マーケットの台頭とその規模拡大の中で、こうした課題の重要性は高まっています。ただ、それは、技術的に非常に挑戦的なものです。
大規模なデータ処理には、MapReduceが役に立ちます。ただ、MapReduceはバッチ型の処理で、リアルタイム性は欠けています。
NoSQL DBが提起した、Eventually Consistency の概念は、重要なものです。ただ、こうした原理的な限界と現実のトランザクション処理の間には、埋められるべき領域が、沢山残っています。
今回は、Googleのシステムの進化を中心に、大規模分散システムの技術の変化とその現在を考えて見よう と思います。
講演資料
- 大規模分散システムの成立
- すべては、ここから始まったGFS, MapReduce, BigTable
- GFSからGFS2へ
- Caffeine 新しい検索システム
- Dremel インタラクティブなデータ分析
- Spanner 新しい分散データベース
- Knowledge Graph 新しい検索技術
- 資料編
1. 大規模分散システムの成立
クラウドとクラウド・デバイスの時代
クラウドの時代は、21世紀になってから本格的に始動した。すぐ後を追って、クラウド・デバイスの時代が始まった。
- 2004年 Google上場
- 2004年 Google GFS,MapReduce,BigTable の論文公表
- 2006年 Amazon EC2, S3
- 2007年 Apple iPhone
- 2008年 Microsoft Azure
- 2008年 Google Android
- 2012年 Facebook上場
2. すべては、ここから始まったGFS, MapReduce, BigTable
Googleの大規模分散技術
21世紀のクラウドとクラウド・デバイスの時代を牽引してきたのはGoogleである。Googleは、大規模分散処理のシステム技術においてもいまだ卓越した地位を占めている。彼らは、処理のリアルタイム化・正確なトランザクションの実現にむけて、そのインフラ技術の見直しをすすめている。
The Google File System
GFSは、安価なPCサーバからなるクラスタ上に構築された分散ファイルシステムである。クラスタは、 2,000台以上のchunkserverからなり、Googleには、30以上のClusterがある。GFSは、ペタバイトサイズのファイルシステムであり、read/write 2,000MB/s 以上の性能がある
MapReduce: Simplified Data Processing on Large Clusters
MapReduce は、関数型のプログラミング・モデルに基づいた、大規模なデータ・セットの処理・生成を行う
Bigtable: A Distributed Storage System for Structured Data
Bigtable は、数千台のサーバ上のペタバイト単位の非常に大きなサイズにまでスケールするようにデザインされた、構造化されたデータを管理する、分散ストレージ・システムである。
3. GFSからGFS2へ
2009年７月、Google大規模障害
2009年7月2日, 6:45 AM から12:35 PM まで、Google App Engineに大規模な障害発生。
この障害の根本的な原因は、データセンタ内のノードが、サーバー側できちんとしたチェックを行わずに、不適切に構成されたFileHandleを送りつけたことに起因するGFS Master serverのバグであった。これを処理しようとして、Masterは、スタック・オーバーフローを起こした。
GFS: Evolution on Fast-forward
事故直後の2009年８月1日、Sean Quinlanは、ACMとのインタビューに応え、GFSのデザインの見直しを示唆。
http://queue.acm.org/detail.cfm?id=1594206
4. Caffeine 新しい検索システム
Our new search index: Caffeine
本日、Caffeineと呼ばれる新しいWebインデキシング・システムが完成したことを報告します。Caffeineは、Web検索で、以前のインデックスより50パーセント新しい結果を提供します。それは、私たちが提供してきた中で、最大のWebコンテンツのコレクションです。
それが、ニュースであれ、ブログであれ、フォーラムへの投稿であれ、それが公開されると、以前に可能だったものよりはるかに早く、関連するコンテンツへのリンクを見つけることが出来ます。
では、なぜ、私たちは新しいインデキシング・システムを構築したのでしょうか？ Web上のコンテンツは、開花の時期を迎えています。単にサイズや数が増えたばかりではなく、ビデオや画像、ニュースやリアルタイムに更新されるものが登場し、普通のWebページもリッチで複雑なものになっています。加えて、人々の検索に対する期待も、以前に比べて高度なものになっています。検索者は、最新の関連するコンテンツを見つけることを望み、公開者は、公開した瞬間にでも、それが見つかることを期待します。
Caffeineでは、私たちは、巨大な規模でWebページのインデックス付けを行います。実際、Caffeineは、毎秒 数十万のページをパラレルに処理します。もし、それを紙で積み上げたら毎秒3マイルの高さになるでしょう。Caffeineは、一つのデータベースに約一億ギガバイトのストレージをあてています。そして一日に数十万ギガバイトの割合で情報を追加しています。この情報を蓄えるには、大型のiPadが、625,000個必要です。 これを端から端にならべると、40マイル以上になります。
私たちは、Caffeineを未来を胸に抱いて構築しました。単に新しい情報を与えるだけでなく、オンライン上の情報の増大とともにスケールし、より関連する検索結果をユーザーに届ける、さらに高速で分かりやすい検索エンジンを構築する、それは強固な土台なのです。ですので、期待して注目してください。今後の数ヶ月のうちにも、さらなる改良が行われることを。
Google Caffeine jolts worldwide search machine
本質的には、Googleはバッチ型のインデックス・システムから、その場でリアルタイムでインデックスを更新するシステムに移行したのだ。
「我々の技術は、ページをクロールするやいなやページにインデックスをつけることを可能にした。過去には、インデックスの更新の度に、Web全体の分析を行っていたので、我々は大規模なバッチで（しばしば数十億ページに及ぶ）ページにインデックスをつけていた。Caffeineでは、Webの小さな部分で分析が出来るので、 インデックスを連続的に更新出来る。」
「このことは、次のようにも考えることが出来る。我々は、数十億のドキュメントのインデックス付けのバッチから、（それぞれ一つの文書に対して）数十億の「バッチ」を処理するシステムに変わったのだと」
Google search index splits with MapReduce
新しい検索のインフラは、GFS分散ファイルシステムの改修版を使用している。これは、Google File System 2、GFS2と呼ばれていたのだが、Googleの内部では、LipkovitzがいうようにColossusとして知られているという。
「Caffeineはデータベース・ドリブンで、BigTableを変化させたインデックス・システムである。Googleは、このシステムを論じた論文を、来月行われるUSENIX Symposium on Operating Systems Design and Implementation (OSDI) で発表する。」
「我々は、非常に膨大なデータから出発して、それを処理してきた。８時間かそれくらい後に、この全体の処理の出力がなされる。その結果をまた、サービス用のシステムにコピーする。我々は、そうした処理を連続的に行ってきた。」
MapReduceは、Googleが望むように出来るだけ早くインデックスを更新することを、Googleに許さなかった。リアルタイムWebの時代、Googleは数秒のうちにインデックスを更新することを求められていた。
過去数年の間、MapReduceは、MITのデータベースの権威 Mike Stonebraker のような人々から批判を受けてきた。Lipkovitzによれば、Google自身、大分前から「同じような認識」に到達していたという。
「MapReduceは、リアルタイムに近い出来事に必要な計算には、向いていない。MapReduceは、一連のバッチ処理からなる。一般的には、最初の処理が終わるまでは、次のフェーズあるいは次の処理を始めることは出来ない。」
「MapReduceは、“おちこぼれ”の問題に悩まされていた。map-reduceの一連のシリーズに基づいたシステムを作ろうとすれば、ある程度の確率で、何かうまくいかないことが起きる。その確率は、処理の数を増やそうと思えばそれだけ大きなものになる。問題が起きた時、ほんの少しの時間ですむ処理でさえも、何も出来なくなる。だから、我々は、MapReduceを取り除いた。」Caffeineでは、Googleは、既にBigTableに格納されているWebマップを直接変更することで、インデックスを更新出来る。このシステムは、BigTable上で動く、あるフレームワークを含んでいる。Lipkovitzは、それを従来のデータベース・プログラミングでの「データベース・トリガー」にたとえた。「それは完全にインクリメンタルだ。」Googleは、新しいページがクロールされる度に、全体を再構築することなく、必要に応じてインデックスを更新出来る。
Incrementally Indexing the Web with Percolator
↑クリックで資料へ
Large-scale Incremental Processing Using Distributed Transactions and Notifications
↑クリックで資料へ
5. Dremel (Big Query)インタラクティブなデータ分析
Dremel: Interactive Analysis of Web-Scale Datasets
↑クリックで資料へ
Dremelのアイデア
第一。分散検索エンジンで利用されている、木構造のアーキテクチャー。Web検索と同様に、検索は、木構造をたどって行われ、それを書き換える。検索結果は、下位の木構造から得られる答えを集約することで行われる。
第二。Dremelは、SQL-likeな検索言語をサポートする。それは、HiveやPigとはことなり、Map-Reduceには変換されずに、ネーティブに検索を実行する。
第三。Dremelは、カラム単位で分割されたデータ構造を利用する。カラム型のストレージは、読み込むデータを少なくして、圧縮が簡単に出来るので、CPUのコストを削減する。カラム型のデータ・ストアは、リレーショナルなデータの解析には採用されてきたが、我々の知る限り、ネストしたデータ構造へのその拡張は、行われてこなかった。
Dremelが利用されている領域
- クロールされたWebドキュメントの解析
- Androidマーケットで、インスロールされたアプリの追跡
- Google製品のクラッシュ報告
- Google BooksのOCRの結果.
- スパムの解析
- Google Mapのmapタイルのデバッグ
- BigtableインスタンスのTabletマイグレーションの管理
- Googleの分散ビルドシステム上での実行テスト結果
- 数十万のディスクのDisk I/O 統計
- Googleデータセンターで実行されているジョブの、リソース・モニタリング
- Googleのコードベースの、シンボルと従属性
結論
- スキャンベースの検索は、一兆個以上のディスク上のデータセットに対して、インタラクティブなスピードで実行出来る。
- 数千ノードを含むシステムで、カラムとサーバーの数に関して、ほとんどリニアーなスケーラビリティーを達成出来る。
- DBMSとまったく同様に、MapReduceは、カラム型のストレージの恩恵を受ける。
- レコードの収集とパージングは、コストがかかる。ソフトウェアの層は（検索実行の層を超えて）、直接カラム指向のデータを利用出来るようになる必要がある。
6. Spanner 新しい分散データベース
Spanner: Google’sGlobally-Distributed Database
↑クリックで資料へ
Spannerとは何か？
- 分散マルチバージョンデータベース
- 汎用のトランザクション(ACID)
- SQL言語のサポート
- スキーム化されたテーブル
- Semi-relationalなデータモデル
- Spanner概観
- 特徴: Lock-freeな、分散readトランザクション
- 特質: 分散トランザクションの外的整合性保証
- グローバルなスケールでは、最初のシステム
- 実装: Concurrency controlとReplicationと2PCの統合
- 正当性とパフォーマンス
- 可能にした技術: TrueTime
- Interval-basedなグローバル時間
7. Knowledge Graph 新しい検索技術
Google Knowledge Graph新しい検索の三つの特徴
- 正しい「もの」を見つける。（Find the right thing）
- 最良の要約を得る。（Get the best summary）
- さらに深く、さらに広く。（Go deeper and broader）
