講演資料


講義資料スライドの表紙

講義資料スライドの表紙です。スライド画像、または下の要約文中の青いページ番号リンクをクリックすると、別のタブで無駄なノイズのない、純粋なPDFビューア画面が起動し、指定されたページへ直接ジャンプして快適に閲覧できます。

全体概要

本セミナーは、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]。

  • 論理展開:
  • GoogleのデータセンターはMassive ScaleかつHighly Efficient Serversで構成され、社会インフラの一部となっている [p.10], [p.11]
  • Googleの検索ストレージは約40PBに相当し、Facebookでは友人関係が1000億に上る [p.19], [p.20]
  • 大規模分散技術は一般企業・開発者とも無縁ではなく、ここから派生した技術が時代のIT技術を形成していくと予測される [p.28]
  • GoogleのInnovations in Software年表（GFS→MapReduce→BigTable→Dremel→Spanner→Colossus）がセミナー全体の見取り図となる [p.30]

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

  • この部の核心:

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

  • 論理展開:
  • GFSはMasterとChunkserverの階層構造を持ち、クライアントはMasterからチャンクの場所を取得してChunkserverと直接通信する [p.34]
  • MapReduceはInputのSplit→Map→中間ファイル→Reduceの流れで動作し、Masterが全体を調整する [p.37]
  • BigTableはGFS上に構築され、SSTableとログという二つの基本構造でimmutableなデータを管理する [p.72]
  • BigTableシステムはMaster・Tablet Server・GFS・Chubby Lock Serviceから構成される [p.40]

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

  • この部の核心:

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

  • 論理展開:
  • ストレージ容量の増大とともにMasterのメタデータ管理量が増加し、秒あたり数千のオペレーションがボトルネックになった [p.54], [p.59]
  • 64MBのチャンクサイズや単一Masterのフェイルオーバーに数分かかる点が、GmailのようなインタラクティブなアプリにとってNGとなった [p.67], [p.74]
  • 対応策として複数Cell・複数GFSマスターによるNameSpaceの分割管理が導入された [p.60], [p.61], [p.62]
  • 最終的にBigTableの利点を生かした分散マスターシステム（Colossus）のデザインへ移行することが明言された [p.58]
  • 同時期にMegastoreが開発され、Gmail・Picasa・Calendar・Android Market・AppEngineの主力ストレージとなった [p.47], [p.49]

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

  • この部の核心:

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

  • 論理展開:
  • 旧インデックスは複数の層構造で主要層は2週間に一度の更新だったが、Caffeineは連続的な更新を実現 [p.87], [p.88]
  • MapReduceは「落ちこぼれ」問題とリアルタイム更新への非適合が致命的とされ、Googleは自ら限界を認めた [p.100], [p.101]
  • CaffeineはBigTableを変化させたデータベースドリブンのインデックスシステムで、Colossus（GFS2）が底部を支える [p.98]
  • MapReduceは死んだわけではなく他の多くのGoogleサービスで継続利用されているが、インデックスシステムでの利用は大幅に減少 [p.105]

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

  • この部の核心:

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

  • 論理展開:
  • MapReduceでは新ドキュメント追加のたびにリポジトリ全体の再スキャンが必要だったが、Percolatorはインクリメンタルな処理を実現 [p.110], [p.111]
  • BigTableのタイムスタンプとLock/Write/Dataの三カラム構造でSnapshot Isolation Semanticsを実現する [p.116], [p.117]
  • ObserverはカラムへのWriteをトリガーとしてトランザクション内で実行され、アプリはObserverの連鎖として構造化される [p.118]
  • Percolatorに移行した結果、インデックスの遅延は数日から数分に短縮され、リポジトリは3倍に拡大した一方、処理コストは約2倍になった [p.122], [p.129]
  • Bigtable上でのTransaction実装詳細（Prewrite→Commit Wait→Secondary Commit）がコードレベルで解説される [p.142], [p.144], [p.146], [p.149]

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

  • この部の核心:

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

  • 論理展開:
  • ネストした構造データをRepetition Level・Definition Levelという二つの整数で符号化し、カラム指向で格納する独自手法 [p.159], [p.162]
  • SQLライクな言語でWITHIN句による集約等をサポートし、出力はProtocol Bufferのスキーマとして定義される [p.164]
  • RootサーバーからLeafサーバーへの木構造でクエリを分散実行し、集約結果を上位に返す [p.165], [p.166]
  • 3000ノード・850億レコードでのベンチマークにおいて、DremelはMR-recordsの約100倍、MR-columnsの約30倍高速 [p.167]
  • Google社内でのクロール分析、Androidマーケット、Maps、Bigtableの管理等、広範な用途で活用されている [p.157]

■ 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]。

  • 論理展開:
  • Universe→Zone→ZoneMaster→Spanserver→Paxos状態マシン→Tablet→Colossusという階層的アーキテクチャ [p.241], [p.242], [p.245], [p.246]
  • TT.now()はTTinterval[earliest, latest]を返し、εはその半幅。GPS・原子時計双方の独立障害モードに対応する [p.280], [p.283], [p.284]
  • StartルールはTT.now().latestを、Commit WaitルールはTT.after(s)=trueを待つことで外部整合性を証明する [p.306], [p.307], [p.308]
  • Read-OnlyトランザクションはLock-freeで実行され、sread = LastTS()によりブロックを最小化する [p.295], [p.327]
  • Directoryがデータ移動とレプリカ配置の単位となり、アプリが地理的レプリカ設定を制御できる [p.258], [p.264], [p.265]
  • Googleの広告システムF1への適用でsharded MySQLを置き換えた実績がある [p.171], [p.230]

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

  • この部の核心:

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

  • 論理展開:
  • Charles DickensやFrank Lloyd Wright、The Beatlesの検索結果右側に、生没年・子女・作品等の構造化情報が表示される [p.203], [p.204], [p.205]
  • コンテキスト（言語・場所・年度）とパーソナライゼーション（過去の検索履歴・クリック履歴）は概念的に区別される [p.201]
  • ?pws=0パラメータでパーソナライゼーションを無効化できるが、コンテキストは依然有効となる [p.202]

■ 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]。

  • 論理展開:
  • Snapshot IsolationではStart-Timestamp時点のコミット済みスナップショットから読み込み、読み込みがブロックされることはない [p.219], [p.220]
  • First-Commiter-Wins原則により、同一区間内に競合するコミットが存在する場合は後発がアボートされる [p.222]
  • SpannerはBigTableに似たバージョン付きkey-valueストアから出発し、テンポラルなマルチバージョンデータベースへ進化した [p.232]
  • Tabs(ecommit:1) [p.308]
  • ZoneレベルのアーキテクチャからDirectory・Fragment・INTERLEAVE IN構文によるデータモデルまで、Spannerの実装全体が体系的に解説される [p.241], [p.258], [p.275]