全体概要

本セミナーは、2014年前後に急速に高まった「大規模グラフデータ処理」という技術的潮流を、その歴史的背景・社会的動機・具体的な実装技術の三層から体系的に解説するものです。

出発点となる問いは明快です。「Webスケールの情報から、人間が理解しうる知識をどのように抽出するか」というものです [p.4]。ページランクに代表される初期の大規模データ処理が文書の「量」を扱うものだったとすれば、2010年代の転換点はデータの「質的なグラフ構造」へと関心を移したことにあります [p.33]。FacebookのOpen Graph [p.37]、GoogleのKnowledge Graph [p.44]、MicrosoftのSatori [p.52] と相次いで登場した「知識グラフ」構想は、検索が「文字列のマッチング」から「意味と関係の探索」へと進化しつつあることを示しています。

こうした潮流を支える基盤技術として、本セミナーは三つのシステムを詳述します。GoogleのPregelはBSP（Bulk Synchronous Parallel）モデルに基づく「頂点のように考える」計算パラダイムを確立しました [p.78]。ApacheのGiraphはPregelのオープンソース実装として、Facebookの実運用環境で兆単位の辺を処理するまでにスケールされています [p.156]。MicrosoftのTrinityは、ディスクではなく分散メモリ上にグラフ全体を保持するという「Memory Cloud」アーキテクチャによって、低遅延なオンライン検索と高速なオフライン解析を同時に実現するまったく異なるアプローチを採ります [p.184]。

セミナーの深層には、知識グラフへの関心が単なるビジネス上の競争を超えて、人間の認知能力・言語能力の解明や機械学習など、ITの最も長期的な課題と結びついているという洞察があります [p.7]。「問題を立てるだけの条件がそろってきた」という講師の言葉は、技術史上の転換点を静かに、しかし確かに告げています。

—

講義のロードマップ

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

■ Part I: グラフとグラフデータ処理

グラフという数学的対象が、ソーシャルネットワークから生物学的ネットワーク、輸送網、深層学習のニューラルネットまで、現実世界の多様な構造を統一的に表現できることを示します [p.13, p.14]。そのうえで、グラフデータを扱う際の「処理スタイル」の違い——リレーショナルDBとグラフDBの本質的な差異——を整理し、本セミナーが対象とするWebスケールの大規模グラフ処理の位置づけを明確にします [p.26, p.27]。

■ Part II: 検索の進化と大規模グラフデータ処理

2000年代のMapReduceによるバッチ処理から、2010年前後のリアルタイム処理・グラフ構造重視へという大規模データ処理の「第二世代への転化」を、GoogleのCaffeine、Facebook Open Graph、Knowledge Graphなど実際の技術イベントの時系列で追います [p.30〜p.34]。検索が「文字列」から「もの（エンティティ）と関係」を扱う段階に進化しつつある現状を、Google・Facebook・Microsoftの競争を通じて俯瞰します。

■ Part III: Google Pregel

Googleが2010年のSIGMOD論文で発表したPregelは、Leslie ValiantのBSP（Bulk Synchronous Parallel）モデルにインスパイアされた大規模グラフ処理エンジンです [p.79]。「頂点のように考える（Think like a vertex）」という計算パラダイムのもと、数十億頂点・数兆辺規模のグラフをスケーラブルかつFault-tolerantに処理する仕組みを実現しました [p.78]。

■ Part IV: Apache Giraph

ApacheのGiraphはPregelのオープンソース実装として始まり、FacebookのHadoopエコシステム上で実運用されています [p.153]。Pregelの基本モデルを継承しつつ、Master Computation・Sharded Aggregators・Nettyによる非同期通信・byte[]シリアライズ最適化などを追加し、兆単位の辺を処理できるまでにスケールされました [p.154]。

■ Part V: Microsoft Trinity

TrinityはMicrosoft Researchが開発した「Memory Cloud上の分散グラフエンジン」です [p.183]。ディスクベース処理の限界を分散メモリで突破し、オンライン低遅延検索（Facebook規模のグラフで3-hop探索を100ms以下）とオフライン大規模解析（10億ノードを60秒）を単一システムで両立します [p.188]。PregelやGiraphとは異なり、インメモリのKey/Valueストアを基盤に据えた、まったく異なるアーキテクチャ思想を持ちます。