全体概要

本セミナーは、Googleが2003年から2006年にかけて公開した三つの画期的な技術論文——GFS（Google File System）、MapReduce、BigTable——を起点として、それらがその後どのように進化・刷新されたかを追跡する、技術史的な探求です [p.31]。

21世紀初頭、GoogleをはじめAmazon、Apple、Facebookといった企業が、かつてない規模の大規模分散システムをネットワーク上で稼働させ始めました [p.3]。これらの企業の競争力の源泉は、巨大なデータセンターを所有し、その上で革新的なサービスを提供し続ける技術力にあります [p.26]。Googleの検索システムCaffeineが毎秒処理するデータ量は紙に印刷すると4.8kmの高さに相当し [p.19]、FacebookのHadoopクラスタでは30分ごとに105TBのデータがスキャンされるという [p.20]。このような「ビッグデータ」の時代において、いかにリアルタイム性を追求しながら正確なトランザクションを担保するかが、現代の大規模分散システムの最重要課題となっています [p.25]。

GFSは単一マスター設計という簡潔さゆえに急速に普及しましたが、データ量がペタバイト規模に達すると、マスターのボトルネック問題が顕在化しました [p.54]。これを受けてGoogleは、分散マルチマスターシステムである「Colossus（GFS2）」への移行を進め [p.97, p.103]、バッチ処理に特化していたMapReduceに代わり、BigTable上でのリアルタイムなインデックス更新を実現する新検索システム「Caffeine」を2010年に稼働させました [p.83]。Caffeineを支えるのは、BigTableに分散トランザクションを加えた「Percolator」であり [p.114]、これはWebスケールの分散トランザクションの「存在証明」として高く評価されています [p.126]。

さらに本セミナーでは、ペタバイト級のデータをインタラクティブに分析する「Dremel」（BigQueryの前身）[p.152]、そしてGPSと原子時計を活用してグローバル規模の外部整合性を実現する新世代分散データベース「Spanner」[p.169]、加えてGoogleの検索を意味理解の次元へと引き上げる「Knowledge Graph」[p.197] を取り上げます。GFSからColossus、MapReduceからPercolator、BigTableからSpannerへという進化の軌跡は、バッチ処理からリアルタイム処理へ、弱い整合性から強い整合性へという、現代の大規模分散技術の本質的な転換を体現するものです。

—

講義のロードマップ

ここでは、セミナーの講演資料がどのようなパートから構成されているかを示します。また、それぞれのパートのポイントを紹介します。

■ Part 1: 大規模分散システムの成立と背景

GoogleやFacebook、Amazonといった企業が、なぜ前例のない大規模分散システムを構築する必要に迫られたのかを、ビジネス的・技術的両面から明らかにします。単なるデータ量の増大ではなく、リアルタイム性の追求と正確なトランザクション担保という二律背反を克服することが、現代ITの核心的な課題であることを提示します [p.25, p.26]。

■ Part 2: すべての起点——GFS、MapReduce、BigTable

2003〜2006年に公開されたGoogle三部作は、大規模分散処理の礎となりました。GFSはペタバイト規模のクラスタファイルシステムであり [p.32]、MapReduceは関数型モデルに基づく大規模並列処理フレームワーク [p.35]、BigTableは数千台のサーバー上でペタバイトまでスケールする構造化データの分散ストレージです [p.38]。これら三つが互いに依存しあうことで、Googleのインフラ全体が成立しています。

■ Part 3: GFSからGFS2（Colossus）へ——進化の限界と突破

GFSの単一マスター設計はシンプルさゆえに急速に普及しましたが、2009年の大規模障害 [p.42] を契機に、その限界が白日のもとに晒されます。Sean Quinlanによる「GFS: Evolution on Fast-forward」[p.52] は、バッチ処理向けに設計されたGFSがインタラクティブなサービスに対応しきれない構造的な問題を告白した重要な証言です。Googleはこの教訓から、分散マルチマスターのColossus（GFS2）へと移行します。

■ Part 4: Caffeine——新しい検索システムとMapReduceの退場

2010年6月、GoogleはMapReduceベースのバッチ型インデックスシステムを廃し、BigTable上でリアルタイムにインデックスを更新するCaffeineを稼働させました [p.83, p.84]。これは「数十億のドキュメントをバッチ処理するシステム」から「数十億の個別バッチを処理するシステム」への根本的な転換であり [p.96]、インデックスの遅延を数日から数分へと劇的に短縮しました [p.89]。

■ Part 5: Percolator——BigTableへの分散トランザクション実装

Caffeineを支える技術基盤がPercolatorです [p.107]。Percolatorは、BigTableにマルチロウトランザクションとObserverパターンを追加し、インクリメンタルなインデックス更新を可能にしました。Two-Phase CommitをBigTableの特別カラム（c:data、c:lock、c:write）を利用して実装することで、Webスケールの分散トランザクションの「存在証明」を実現しています [p.126]。

■ Part 6: Dremel——インタラクティブなビッグデータ分析

Dremelは、数千ノードを用いてペタバイト規模のデータをMapReduceの100倍のスピードで分析する、インタラクティブなクエリシステムです [p.152]。木構造のクエリ実行アーキテクチャ、SQL様の検索言語、そして入れ子構造データのカラム型格納という三つのアイデアの組み合わせが、その圧倒的な性能を生み出しています [p.154, p.155]。

■ Part 7: Spanner——GPSと原子時計が支えるグローバル分散DB

Spannerは、key-valueストアの拡張性とRDBのACIDトランザクション処理能力を融合した、Googleの次世代グローバル分散データベースです [p.169]。最大の革新はTrueTime APIであり、GPS受信機と原子時計を組み合わせることで時刻の不確実性を10ms以下に抑え [p.185, p.192]、分散トランザクションへのグローバルに意味のあるコミットタイムスタンプ割り当てを実現しました。これは「グローバルなスケールで外部整合性を実現した初めてのシステム」です [p.173, p.236]。

■ Part 8: Knowledge Graph——新しい検索技術

2012年5月にアメリカで開始されたKnowledge Graphは、検索を「文字列のマッチング」から「意味・概念の理解」へと転換するGoogleの新しい検索技術です [p.197]。「正しいものを見つける」「最良の要約を得る」「さらに深く広く探索する」という三つの特徴により、検索結果のパーソナライズとコンテキスト理解が高度化されます [p.199]。

■ Part 9: 資料編——Snapshot Isolation とSpannerの詳細実装

Spannerを理解するための理論的補足として、Snapshot Isolationの基本概念とSpannerの実装詳細が補遺として収録されています [p.217]。Start-Timestamp・Commit-Timestamp・First-Commiter-Winsという三つの概念がSnapshot Isolationの核心を成し [p.219, p.221, p.222]、SpannerのTrueTime APIとPaxos Leader Leasesの組み合わせがいかにして外部整合性を保証するかが数学的に証明されます [p.308]。