Google I/O 2009レポート

開発チームが明かす、Google Waveの実装概要

2009/06/01 　グーグルが発表した新しいコミュニケーションプラットフォームの﹁Google Wave﹂が大きな反響を呼んでいる。技術的な詳細がかなり明らかにされているので、何が可能かはだいたい予想ができそうだが︵だからこそ発表時に会場を埋めていた4000人あまりの聴衆は興奮のあまり立ち上がって喝采を送ったのだが︶、誰も想像できなかったようなキラーアプリケーションが登場するのかどうか、あるいはWave自体がキラーアプリケーションなのか、それはまだ誰にも分からない。　レポート記事︵︻詳報︼Google Waveとは何なのか？︶への反響を見ると、さまざまな疑問を感じている人がいる。そこでここでは、直接Waveのプロジェクトリーダーに話を聞いたり、別セッションで開発チームが行った説明、およびオンラインドキュメントから読み取れたことなど、いくつか追加情報をまとめたい。ちなみに、Google I/Oの参加者にはWaveアカウントが発行されることになっているが、これを書いているいま、まだ案内は届いていない。

Waveはリアルタイム／同期通信だけか？

　まず、﹁リアルタイム﹂という点。ミリ秒単位の遅延しか感じられないチャットやゲームをHTMLページで行うというデモンストレーションに驚かされたために、レポート記事ではこの点を強調しすぎたようだ。Waveが﹁リアルタイム通信、同期通信だけのもの﹂という印象を受けた人もいた。それは誤解だ。　Waveではメール同様の非同期通信も可能だ。つまり、あなたが新規にWaveを作り、誰かに宛てたWave︵メッセージ︶を書けば、それはまずサーバに送られる。受信側︵Wave参加者︶は、その時点でオンラインでもオフラインでも構わない。オンラインであれば、すぐにそのWaveを開いて読むことができるが、オフラインであれば、メールのインボックスのように︵おそらく最終更新時刻の時間順で︶、自分が関与しているWave一覧が表示される。非同期のメッセージ交換が可能だからこそ、﹁今度の映画、何を見る？﹂というような投票を複数人の間で行える。同期通信だけであれば、とてもではないが投票は使い物にならない。

チャットだけではなく、中央にWaveをリストした「inbox」があるのが分かる。アイコンを見れば、新着メッセージ数を示しているらしい数字も見て取れる。左にはスパムフォルダすらある（さらによく見るとMuteボタンもある）

Waveはグーグルだけのサービスになるのか？

Waveプロジェクトの創始者でプロジェクトリーダーのラース・ラスムセン（Lars Rasmussen）氏

　Waveを見て、私はもうSMTPは不要ではないかと思った。それで、﹁WaveはSMTPやIMAPを置き換えるプロトコルになると考えているか﹂とWaveプロジェクトの創始者、ラース・ラスムセン氏に聞いてみた。それまで陽気に応対してくれていたラスムセン氏だが、この質問には肩をすくめて渋い顔をしたまま、﹁それは分からない﹂とだけ答えた。つまらない答えだが、聞いた私が軽率で、答えたラスムセン氏が慎重だっただけだろう。どう見てもWaveはSMTPやIMAP/POPを置き換えるポテンシャルを持っているし、それ以上の何物かだ。メールシステムを作り直すとしたらどうやるかという問題意識でスタートしたと語っているのだから、質問自体がおかしかった。　質問はこうあるべきだった。﹁WaveがSMTPよりいいのは自明だ。では、SMTPを置き換えるような大きなシフトが起こるために必要なことは何だろうか？﹂。残念ながら、短時間のインタビューではそれを聞きそびれたが、私なりに考えたことをまとめたい。　Waveが広く普及するかどうかのカギの1つは、グーグル以外の大手ISPなどがWaveサービスを立ち上げるかにかかっているだろう。遅延を最小限に抑える最適化を徹底しているとはいえ、ネットワークの遅延という壁はソフトウェア技術だけでは越えられない。光の速度は結構速く、太平洋を往復しても60msしかかからない。人間が電話で遅延を面倒に感じるのは300msと言われてるので、実はたいしたことはない︵だから国際電話もSkypeもオッケーなわけだが︶。問題は経由するスイッチの数、ホップ数だ。　そう考えると、Waveサーバは多ければ多いほどよく、メジャーなISPがすべてWaveサーバを持つのが理想だろう。政治的、業界バランス的にいってもグーグルしかWaveサーバを立てないとしたら成功はおぼつかないだろう。　もう1つ、Waveが広まるのに欠かせないのは、HTML 5対応ブラウザの普及だ。クライアント側のWaveでオフライン編集機能を使うには、HTML 5のアプリケーションキャッシュ、ローカルストレージの機能が欠かせない。Waveでは手元の端末にあるファイルを操作して、その差分をオンラインになった時点でサーバに送り付ける形になる。こうしたことは、HTML 5だからこそできることだ。　SMTPが置き換わることなどあり得ないと思う人もいるかもしれない。なぜなら、こうしたシステムでは、全員と言わないまでも多数の人が移行しないと意味がない場合が多いからだ。しかし、メールプロキシのボットがあればどうだろうか。もしあなたがWaveを気に入れば、あなたはWaveをメール、ブログおよびコメント、Twitterなどのアグリゲータとして使えるかもしれない。Wave側からポストすることもできるだろう。つまり、利用者が少ないから利用価値が上がらず、利用価値がないから利用者が増えないという、いわゆる﹁ニワトリとタマゴの問題﹂が起こらないシナリオも考えられる。　もう1つ、レポート記事の初出時に私が誤解していたことがある。既存のブログサービスなどをWave対応とするのに特別に何かを実装する必要があるかのように書いたが、これは誤りだった。WaveはWebページへの埋め込み用のAPIを最初から用意しているため、既存WebページでのWave対応は簡単だ。

WebページにWaveを埋め込むためのAPIも用意されている（http://code.google.com/apis/wave/embed/）

　となると、Waveは一種のCMSとしても機能する。自分のWebサイトをWave対応としてしまえば、テキストの書き換えや追加︵つまりブログエントリの投稿のようなこと︶は、Wave経由でできることになる。この使い方であれば、たった1人であってもWaveを使い始めるメリットがある。　Waveという名前が暗示するように、Waveが徐々にインターネットに波のように広がっていく可能性は十分にあるだろう。

文字は全部見えちゃうの？

　リアルタイムということに絡んで、もう1つ、レポート記事で書かなかったために招いた誤解がある。タイプ中の文字が全部見えるのは気味が悪い、という指摘だ。　これはもっともな指摘で、メールやIMでタイプするときには、バックスペースキーを叩いて行きつ戻りつするのが普通だろう。いちいち全部見えたのでは困ることも多い。　この点について、ラスムセン氏は講演の中で言及していた。タイプ中の文字をすべて出すのをデフォルトとしているが、どうもそれはやりすぎで、それがいいのかどうか分からないという話だ。Waveは早期プレビュー版なので、この辺のモデルはいくらでも変わりうる。完全リアルタイム、準リアルタイム︵リターンキーをトリガーにしてサーバと通信するなど︶と、モードを分けるのがいいかもしれない。逆にモードの概念を導入するのは、いたずらに複雑さを増すだけだという議論もあり得るだろう。　もう1つ、メッセージが全部見えてしまうのかという点。レポート記事では書き漏らしたが、同じWave上にいる参加者の中で、特定の誰かとだけプライベートな会話をすることもできる。アーキテクチャ上はWaveの中にWaveletと呼ぶ会話スレッドの管理単位があって、Wavelet単位で参加者の読み書きのパーミッションを管理することになるようだ。

Waveのデータモデル。各WaveにはWaveletと呼ぶ会話スレッドが含まれていて、そのそれぞれの参加者が紐付いている。このため、同一Wave上でもプライベートメッセージのやり取りなどは可能

サーバはどうなってるの？

　Waveは﹁マッシュアップ﹂的に見える。Waveのプレゼンテーションが始まってからしばらくは、会場にいた聴衆の間には﹁これのどこがすごいんだ？﹂という白けた空気が漂っていたのではないかと思う。少なくとも私はそうだった。これから大きな発表があるのだとか、これからお見せするデモンストレーションがすべてHTMLページだということを決して忘れないでくださいなどとバイス・プレジデントが大げさに言うので期待したのに、﹁なんだマッシュアップ？プロダクティビティ・コラボレーション・ライブ・リアルタイム・タイムライン・ウィキ・スイート、えっと何それ？﹂という軽い落胆だ。　しかし、デモンストレーションが進むにつれて、だんだんWaveのインフラや設計がよく練られていることに、否応なく誰もが気付かされた。　さらに、Waveの内部アーキテクチャがどうなっているかを概説するセッションに参加して、私はそれが単なる既存ソフトウェアモジュールの寄せ集めやマッシュアップと呼べるようなものではないことを、ようやく理解した。　Google App Engineは﹁Jetty﹂というライトウェイトなOSSのHTTPサーバ、アプリケーションサーバを使っている。てっきり私はWaveもそうなのかと思ったのだが、ラスムセン氏に聞いたところ、Waveのサーバは完全にスクラッチから書き起こしたものだという。デモンストレーションでApp Engineで動いていたのはボットだけだった。　考えてみれば、WaveサーバはHTTPサーバというだけでなく、ほかのWaveサーバと接続するためにXMPPもしゃべらなくてはいけないし、何より、Waveオブジェクトを多人数編集環境でバージョン管理するために最適化されていないければならない。Cometを使うと同時接続数が多くなるので、スケーラビリティの確保も大きな技術的チャレンジだ。ラスムセン氏に聞いたところ、例えばWaveサーバでは独自にノンブロッキングI/Oを実装していて、同時接続数が増えたときにも遅延なくWaveオブジェクトの読み書きができるようにしているという。ミリ秒単位でリアルタイム性を追求しようと思ったら、Apacheなど既存HTTPサーバ向けにWaveモジュールを書くのではなく、フルスクラッチで書く必要があったというのは道理だ。

ナイーブな実装ではスケールせず、ドキュメントが壊れる可能性も

　同時編集環境におけるバージョン管理も、マッシュアップというような簡単な問題ではない。予測できない時間間隔を置いて接続、切断を繰り返す複数のクライアント・サーバ間で、同一オブジェクトに対して編集を行うのは、単純な話ではない。Waveを発表した午前の基調講演に続いて行われた午後のセッション﹁Google Wave: Under the hood﹂で開発チームメンバーが、Waveを支える実装の概要について説明を行った。　冒頭で、Wave開発チームの1人、アレックス・マー氏はまず、﹁ABCDE﹂という文字列をクライアント側、サーバ側︵多くの場合、実際にはもう1つ別のクライアントだろう︶でそれぞれ編集する例を挙げた。ナイーブな実装︵深く考えずに素朴に問題に当たるという意味︶だと、クライアント側とサーバ側で結果が﹁ACE﹂と一致すべきところ、編集タイミングの問題で一方が﹁ACE﹂、他方が﹁ACD﹂と食い違うことになりかねない。なぜなら、﹁n文字目を消去する﹂という操作では、操作対象が変化する前と後とでnの値が変わらなければならないからだ︵下図参照︶。

ナイーブな実装だと、リアルタイム共同編集では簡単に不整合が起こる

正しく動作させるには、サーバ側に送られた操作を適宜変換する必要がある

　つまり、あるクライアントで﹁ABCDE﹂の﹁D﹂︵4文字目︶を消すという操作は、サーバ上では必ずしも同じ操作となるわけではないということだ。ほかのクライアントから受け入れた操作によって﹁ABCDE﹂の状態が﹁ACDE﹂に変わっている可能性がある。もし﹁D﹂を消すつもりで4文字目を消すと﹁ACD﹂となってしまう。こうした矛盾が起こらないようにするため、Waveでは各操作を変換する﹁オペレーション変換﹂を実装しているという。　サーバ側の状態、クライアント側の状態は時間とともに変化する。このため、オフライン状態が長時間続いて一連の操作がサーバ・クライアントの双方で蓄積していくと、サーバ側で必要となる操作変換の計算量は、サーバ側の操作の数をn、クライアント側の操作の数をmとすると、n×mのオーダーで増えていってしまう。これでは処理時間が掛かりすぎて、リアルタイム性を確保できない。　このためWaveでは、任意の2つの操作を1つの操作に合成する合成関数を実装したという。例えばユーザーが長期間ログインせず、複数の操作履歴が蓄積している場合でも、クライアント側に送る操作の数は、合成後の操作だけで済むことになる。参加者の数が多くなった場合、他ユーザーがサーバに送る操作もまとめて受け取ることができるだろう。

クライアント側とサーバ側の双方で編集作業をすると、それぞれでバージョンが進んでいく

　この2つの操作の行う「Operation Composer」（操作合成器）は、関数型プログラミング言語にあるzip系の関数のように働くという。任意の2本の操作ストリームをこの合成器に流し込むと、合成後の1本の操作ストリームが出てくる。この合成器、操作ストリーミングというモデルは、マルチコアCPU環境、あるいはデータセンターで非常によくスケールしそうだ。

合成を行う合成器は2つの操作ストリームを入力とし、1本の操作ストリームとして吐き出す

2段階の編集履歴を1つの操作にまとめる例。オレンジが要素の削除、グリーンが追加を表している。この例では合成の結果、「K」が省略されているのが分かる

　もう1つ、操作の合成に関して興味深いのは編集履歴の蓄積から任意のバージョンを引き出すときに最小限の計算量で済ませるために、「Composition tree」（合成ツリー）と呼ぶデータ構造を採用したという話だ。

合成ツリーのデータ構造。任意のバージョン間の変換は、log(n)回の処理で完了する

　上図の﹁Op4、Op5、Op6、、、﹂とあるのは1つ1つの操作に対応する。一連の操作は編集履歴だ。こうした履歴があるときに、例えばOp3の状態からOp14の状態に移行するには、素朴にやると11個の操作を適用する必要がある。事前に合成しておけばよさそうなものだが、すべての状態の組み合わせで合成後の操作を保持するのは計算量でもメモリ効率の点でも非現実的だ。　そこでノード当たり2つの子ノードを持つツリーを構成し、n個の操作適用処理が必要な場面で、O(n)ではなくO(log(n))の計算量で済むように工夫しているという。上図の例だと、Op3からOp14へは、 ●﹁Op5〜Op8﹂を合成した操作 ●﹁Op9〜Op12﹂を合成した操作 ●﹁Op13、Op14﹂を合成した操作という3つの操作で済ませることできる︵これらの操作は事前に合成しておくのだろうが、合成後のデータ量もlog(n)で済む︶。13個の操作が3個になると聞いてもピンと来ないかもしれないが、1万個の操作が13個、10万個の操作が16個で済むといえば、効率のいいデータ構造とアルゴリズムを考えることの重要さが分かるだろう。　クライアント・サーバ間のWaveプロトコルで、もう1つ興味深いのは、クライアントから操作︵差分︶を送るときにサーバから明示的に送信許可︵ACK︶を受け取る必要があるということだ。クライアントがサーバに連続して操作を送れるのは1度に1つに制限しているという。サーバは送られてきた操作を、確実にサーバ上のドキュメントに適用してから、次の差分をクライアントから受け取るようにする。こうすることで、サーバは単一の状態を保持しておくだけで済む。もし、こうしたACKのやり取りがなければ、サーバ上には、各サーバ・クライアントのペアについて、それぞれでドキュメントの状態を保持する必要があるうえに、状態を管理するアルゴリズムも複雑になってしまうのだという。　ただし、クライアントは操作を送り出してからACKを待つものの、ユーザー自身は待つ必要はない。ユーザーがタイプするキー操作など各種操作はローカルにキャッシュされ、サーバからACKが来るとそれらの操作をまとめて送るからだ。　操作の合成や合成器、合成ツリーなどは、おそらくどれも﹁真っ当なエンジニアリング﹂というべきもので、グーグルにしかできないことだとは思わない。実際、﹁Operational Transformation﹂という研究分野には10年以上の蓄積があり、グーグルが参考文献に上げているXeroxの論文は1995年のものだ︵論文のPSファイル︶。　ただ、こうした1つ1つでヘマをしないこと、また、一般的に知られているアルゴリズムやフレームワークであっても、それを現実の問題に適用して最適化していること、その積み重ねがWaveの驚くべきリアルタイム性に結実しているのは間違いないだろう。O(log(n))で済むアルゴリズムが存在しているのに、O(n)やO(n^2)といった、非常にまずい実装のために、不必要に﹁重たい﹂アプリケーションというのは世の中にあふれている。例えば、メールボックスなどに対する操作などでデータ量が増えるにつれて、1分とか2分、あるいは耐えきれないほど延々と待たされた経験はないだろうか。本当は1秒で済むアルゴリズムが存在していることをプラグラマが知らない、あるいは思いつかないだけということはあり得る。グーグルの凄みは、マッシュアップ的に見えるWaveのようなWebアプリケーションでも、その内部の最適化を徹底していること、あるいは徹底できる人材を集めていることだ。　最適化という意味では、一見Waveとは関係がないように見えるWebブラウザのGoogle Chromeも無関係ではない。Chromeに搭載されているJavaScriptエンジン﹁V8﹂のチームでは現在、DOM関連の操作の高速化を模索しているという。これは、innerHTMLなどでHTMLツリーにノードを追加するような処理、つまりまさにWaveクライアントがやっているようなダイナミックにHTMLページを書き換えるような処理に対する高速化を意味する。V8チームのマッズ・エイジャー︵Mads Ager︶氏の説明によれば、V8ではガベージコレクション︵使用済みメモリの回収︶に﹁世代別ガベージコレクタ﹂を採用していて、ほとんどのサイクルは1、2ミリ秒で終わるという。Webブラウザに限らず、ガベージコレクションは一般的にアプリケーションが一瞬固まるようなユーザー体験につながる。普通のWebサイトを見ているような場合は問題にならないが、Waveのようなリアルタイム性の高いアプリケーションではユーザー体験を大きく左右するだろう。　いずれにしても、履歴付き構造化ドキュメントというオブジェクトを同期／非同期環境で複数人で共有し、それをWebブラウザ越しにリアルタイムで同時編集する環境を提供する、というのは決して単純な話ではない。これまでにもオンライン共同編集ツールやCometを使ったリアルタイムコミュニケーションツールはあったが、リアルタイムに1文字単位、しかもドキュメントのどこにでも変更が加えられるというものはなかった。　Google Docsは、実はリアルタイム性がそれほど高くなく、相手の打った文字が見えるまでに何秒か掛かる。Gtalkはリアルタイム性は高いが、互いのメッセージを書き換えることはできないし、追記のみだから、Waveに比べればだいぶ単純だ。Google Spreadsheetsでもセルごとに排他ロックをかけて、同じ場所を複数人が同時に編集できないように制限している。同時編集に付きまとうコンフリクトという難しい問題を回避するためだろう。　2007年初頭にスタートしたというWaveプロジェクトは当初5人のチームだったが、現在は約50人にまで膨らんでいるという︵プロジェクトリーダーを含め、そのほとんどはオーストラリアのグーグル社員だそうだ︶。年内にもエンドユーザー向けサービスが開始するというGoogle Wave。どんなユーザーインターフェイスで登場するのか、実際のインターネット環境でどれぐらいリアルタイム性とスケーラビリティを持つことになるのか、いまからその登場が楽しみだ。