SocialCalc と EtherCalc

Audrey Tang

EtherCalc はオンラインスプレッドシートシステムである。複数のユーザーによる共同編集に最適化されており、ブラウザ内のスプレッドシートエンジンとして SocialCalc を使っている。Dan Bricklin (スプレッドシートの考案者) によって設計された SocialCalc は、エンタープライズユーザー向けの様々なソーシャルコラボレーションツールから構成される Socialtext プラットフォームの一部である。

Socialtext チームにとって、パフォーマンスは 2006 年に始まった SocialCalc 開発の主目標だった。この開発からは「JavaScript で行われるクライアントサイドの計算は、Perl で行われるサーバーサイドの計算より一桁低速であるものの、AJAX に必要なラウンドトリップで生じるネットワークレイテンシと比べれば高速」という教訓が得られた。

図 2.1. WikiCalc と SocialCalc のパフォーマンスモデル; JavaScript ランタイムの改善により、2006 年に 50 ms かかっていた処理は 2009 年には 10 ms 以下で済むようになった。

SocialCalc は全ての計算をブラウザで行い、サーバーはスプレッドシートの読み込みと保存でのみ利用される。Architecture of Open Source Applications の SocialCalc の章で最後に書いたように、私たちはチャットルームに似た単純なアーキテクチャを使ってスプレッドシートに共同編集の機能を導入した。

図 2.2. SocialCalc ではスプレッドシートを複数人が同時に編集できる。

しかし、この方式をプロダクション環境でテストするとパフォーマンスとスケーラビリティに関していくつかの欠点が判明し、十分なパフォーマンスを得るためにシステム全体にわたる書き直しが何度か行われた。本章では、どのように最終的なアーキテクチャにたどり着いたか、どのようにプロファイリングツールを使用したか、そしてパフォーマンスの問題を解決するために新しいツールをどのように開発したかを説明する。

設計上の制約

Socialtext プラットフォームはデプロイ先の選択肢として「behind-the-firewall (ファイアウォールの裏)」と「on-the-cloud (クラウドの上)」の両方を提供する。そのため、EtherCalc にはリソースとパフォーマンスに関してユニークな制約が課される。

執筆時点において、VMWare vSphere ベースのイントラネットデプロイで Socialtext は 2 個の CPU コアと 4GB の RAM を要求する。クラウドベースのホスティングでは、典型的な Amazon EC2 インスタンスがこの約 2 倍の性能 (4 コア CPU と 7.5 GB の RAM) を提供する。

behind-the-firewall デプロイの存在は、ユーザー自身ではデプロイ不能なマルチテナントシステム (例えば、後に Google Docs の一部となった DocVerse) のようにハードウェアを多く積んで問題を解決することはできないことを意味する。サーバーの性能は中程度としか仮定できない。

イントラネットへのデプロイと比べると、クラウドにホストされたインスタンスは優れた性能を持ち、オンデマンドの拡張が容易である。しかしブラウザとクラウドを結ぶネットワーク接続は遅いことが多く、切断と再接続が頻繁に発生する。

こういった制約によって形作られた EtherCalc のアーキテクチャは次の特徴を持つ:

メモリ: イベントベースのサーバーのおかげで、少ない RAM で数千個の並列接続を扱えるスケーラビリティを持つ。
CPU: SocialCalc のオリジナルの設計に基づき、ほとんどの計算と全てのコンテンツ描画はクライアントサイドの JavaScript にオフロードされる。
ネットワーク: スプレッドシートの内容ではなくスプレッドシートに対する操作を送信することで必要な帯域が減少し、低信頼なネットワークで発生する障害からの回復が可能になる。

最初のプロトタイプ

私たちが最初に手にしていたのは Perl 5 で実装された WebSocket サーバーだった。これは Feersum と呼ばれる、libev をベースとして Socialtext が開発したノンブロッキングウェブサーバーを利用していた。Feersum は非常に高速であり、一つの CPU で秒間 10,000 個を超えるリクエストを処理できる。Feersum に加えて、有名なクライアント JavaScript ライブラリ Socket.io を有効活用するために PocketIO と呼ばれるミドルウェアも利用された。PocketIO は WebSocket サポートを持たないレガシーブラウザに後方互換性を提供する。

最初のプロトタイプはチャットサーバーによく似ており、それぞれのコラボレーションセッションがチャットルームのように動作した: クライアントはローカルで実行したコマンドとカーソルの位置をサーバーに送信し、サーバーが同じルーム内の他のクライアントにそのデータをリレーした。

典型的なデータの流れを次の図に示す:

このワークアラウンドは新しいクライアントで発生する CPU の問題を解決するものの、全てのクライアントで多くのアップロード帯域が必要となるので、ネットワークのパフォーマンスが新しく問題となる。接続が低速なクライアントからのコマンドは反映が遅れてしまう。

さらに、サーバーはクライアントから送られて来るスナップショットの一貫性を確認する手段を持たない。そのため、誤った ── もしくは悪意のある ── スナップショットが送られると以降の新しい参加者に送信される状態が破損し、新しい参加者は既存の参加者と同じスプレッドシートを見ることができなくなる。

鋭い読者は、この二つの問題がサーバーでスプレッドシートのコマンドを実行できない事実から生じていることに気が付いたかもしれない。もしサーバーがコマンドを受け取るごとに自身の状態を更新できるなら、コマンドの履歴を保持する必要はない。

ブラウザ用の SocialCalc エンジンは JavaScript で書かれている。このロジックを Perl で実装する選択肢もあったものの、二つのコードベースを管理するのはコストが高すぎると判断された。また、組み込み可能な JavaScript エンジン (V8, SpiderMonkey) を使った実験も行われたものの、Feersum のイベントループ内で実行するとパフォーマンスに対する悪影響が大きいことが判明した。

最終的に、この問題はサーバーを Node.js で書き直すことで解決された。この書き直しは 2011 年 8 月に完了した。

Node.js へのサーバー移植

Feersum と Node.js はどちらも libev のイベントモデルをベースとしており、さらに Pocket.io の API は Socket.io の API とよく似ているので、最初の書き直しはスムーズに進行した。zappajs が提供する簡潔な API も手伝って、Perl バージョンと同じ機能を持った 80 行のサーバーが半日で完成した。

最初のマイクロベンチマークでは、Node.js への移植によってスループットが約半分になったことが示された。2011 年の典型的な Intel Core i5 CPU において、オリジナルの Feersum スタックは毎秒 5,000 リクエストを処理できたのに対して、Node.js 上の Express が処理できるのは毎秒 2800 リクエストだった。

このパフォーマンス低下は最初の JavaScript バージョンとしては許容できるとされた。ユーザーが体感するレイテンシが大きく増加する訳ではなかったのに加えて、パフォーマンスはこれから改善できるだろうと私たちは期待した。

その後、各セッションの状態をサーバー側の SocialCalc スプレッドシートで追跡する処理におけるクライアントサイドの CPU 負荷と使用帯域を削減する作業が続けられた。

サーバーサイド SocialCalc

サーバーサイドの SocialCalc で鍵となったテクノロジが jsdom だった。jsdom は W3C ドキュメントオブジェクトモデルの完全な実装であり、jsdom があると Node.js はシミュレートされたブラウザ環境でクライアントサイドの JavaScript ライブラリを読み込めるようになる。

jsdom を使うと、サーバーサイドの SocialCalc スプレッドシートをいくつでも作成できる。それぞれのスプレッドシートは約 30 KB のメモリを消費し、独自のサンドボックス内で実行される:

require! <[ vm jsdom ]>
create-spreadsheet = ->
  document = jsdom.jsdom \<html><body/></html>
  sandbox  = vm.createContext window: document.createWindow! <<< {
    setTimeout, clearTimeout, alert: console.log
  }
  vm.runInContext """
    #packed-SocialCalc-js-code
    window.ss = new SocialCalc.SpreadsheetControl
  """ sandbox

サンドボックス化された SocialCalc コントローラーがコラボレーションセッションごとに一つずつ作成され、このコントローラーがクライアントから受け取ったコマンドを実行する。サーバーは新しく参加したクライアントにコントローラーが保持する最新状態を転送するので、コマンドの履歴を保持する必要は全くない。

こうして満足いくベンチマーク結果が得られるようになると、続いて私たちは Redis ベースの永続化レイヤーを実装し、そして https://ethercalc.org/ を開設してパブリックベータテストを開始した。ここから半年にわたって、EtherCalc は非常によくスケールした。数百万回のスプレッドシート操作が行われ、その間インシデントは一件も発生しなかった。

2012 年 4 月、OSDC.tw カンファレンスで EtherCalc について発表した後、私は Trend Micro が主催するハッカソンに招かれた。このハッカソンで私たちは、リアルタイムウェブトラフィック監視システム用のプログラム可能な可視化エンジンを EtherCalc に対応させることになった。

この用途に対応するために、スプレッドシートを直接操作するための GET/PUT/POST コマンド、そして個別のセルに対するアクセスを提供する REST API が実装された。ハッカソンの間に書かれた全く新しい REST ハンドラは毎秒数百件の呼び出しを処理し、ブラウザ内のグラフや数式セルを鮮やかに更新した。実行速度の低下やメモリリークが起こる様子は無かった。

しかし最終日のデモで事件は起こった。実際の大規模なトラフィックデータと EtherCalc を連携し、ブラウザで開かれたスプレッドシートのセルに数式を打ち込んだところ、突然サーバーが固まり、アクティブな接続に一切応答できなくなってしまった。私たちは Node.js プロセスを再起動したものの、そのプロセスの CPU 使用率は 100% に急上昇し、また固まってしまった。

私たちは愕然としながらも小規模なデータセットに切り替えた。そちらでは上手く行ったので、なんとかデモを切り抜けることができた。しかし疑問は残る: どうしてサーバーは固まったのだろうか？

Node.js のプロファイル

CPU サイクルが何に費やされているかを調べるには、プロファイラが必要になる。

Perl で書かれた最初のプロトタイプは簡単にプロファイルできた。Perl には NYTProf という優れたプロファイラがあるためである。NYTProf を使うと、関数ごと、行ごと、opcode ごと、ブロックごとのタイミング情報を取得でき、さらにコールグラフの可視化や HTML レポートの生成もできる。長く実行されるプロセスに対しては Perl 組み込みの DTrace サポートを使って関数の実行開始と実行終了の統計をリアルタイムに確認することもできる。

Perl と比べると、Node.js のプロファイリングツールは十分とは言えない。執筆時点で DTrace のサポートは illumos ベースのシステムにおいて 32 ビットモードで実行するときに限られている。そのため多くの場合は Node Webkit Agent を利用することになる。このライブラリはプロファイリングのインターフェースを提供するものの、取得できるのは関数レベルの統計に限られる。

典型的なプロファイルセッションは次の形をしている:

# "lsc" は LiveScript コンパイラ
# WebKit エージェントを読み込み、app.js を実行する:
lsc -r webkit-devtools-agent -er ./app.js
# 別のターミナルで、プロファイラを起動する:
killall -USR2 node
# この URL を WebKit ブラウザで開くとプロファイリングが開始される
open http://tinyurl.com/node0-8-agent

高い負荷を再現するために、Apache のベンチマークツール ab を利用して大量の REST API 呼び出しを並列に行った。ブラウザサイドの操作 (例えばカーソルの移動や数式の更新) のシミュレーションではテストに特化したヘッドレスブラウザ Zombie.js を利用した (Zombie.js も jsdom と Node.js を利用する)。

プロファイルの結果、皮肉にも、jsdom 自体がボトルネックであることが判明した:

図 2.5 のレポートを見ると、CPU 時間の多くが RenderSheet 関数で消費されているのが分かる。この関数はサーバーがコマンドを受け取るたび実行され、数マイクロ秒をかけて各セルの innerHTML をコマンドの効果通りに更新する。

jsdom のコードは全て一つのスレッドで実行されるので、任意の REST API 呼び出しは一つ前のコマンドのレンダリングが終わるまでブロックする。並列性が高いとき、実行待ちコマンドのキューに隠れていたバグが悪さをして、最終的にサーバーが固まってしまっていた。

ヒープの使用を詳しく調査したところ、ほとんどのセルのレンダリング結果は参照されていないことが判明した。サーバーサイドではリアルタイムの HTML 表示が必要ないためである。スプレッドシートを HTML にエクスポートする API では唯一セルのレンダリング結果が参照されていたものの、スプレッドシートのインメモリ表現から各セルの innerHTML を再構築する処理はいつでも必ず実行できる。

そこで、私たちは jsdom を RenderSheet 関数から削除し、HTML のエクスポート用に最小限の DOM を 20 行の LiveScript で再実装した。この最適化後のプロファイル結果を図 2.6 に示す。

ずっと速くなった！スループットは 4 倍に、HTML のエクスポートは 20 倍高速になり、サーバーが固まる問題も解決された。

マルチコアスケーリング

この最適化が終わってようやく、EtherCalc を Socialtext プラットフォームに統合する準備が整ったと私たちは感じるようになった。統合が完了すれば、wiki ページなどと同様にスプレッドシートにも共同編集機能が提供されることになる。

プロダクション環境における公平な応答時間を保証するために、私たちはリバースプロキシ用の nginx サーバーを開発した。このサーバーは limit_req ディレクティブを使って API コールのレートを制限する。この手法は両方のホスティングシナリオ (behind-the-firewall と on-the-cloud) で期待通りの動作をすることが確かめられた。

ただ、Socialtext は小規模および中規模のエンタープライズに向けて三つ目の選択肢を提供する: マルチテナント (multi-tenant) ホスティングである。マルチテナントホスティングでは単一の大きなサーバーが 35,000 以上の組織にサービスを提供し、それぞれの組織が 100 人程度のユーザーを持つ。

このシナリオでは、レートリミットが全ての顧客による REST API コールで共有される問題が発生する。クライアントの事実上のレートリミットが非常に厳しく ── 毎秒 5 リクエスト程度に ── なっていた。前節で説明したように、この制限は計算を一つの CPU でしか行わない Node.js が原因で生じる。

マルチテナントのサーバーで全ての CPU を利用するには、どうすればいいだろうか？

通常の Node.js サービスをマルチコアホストで実行するシナリオであれば、それぞれの CPU コアごとにプロセスを前もって作成するクラスターサーバーのアーキテクチャを利用しただろう:

しかし、EtherCalc は確かに Redis によるマルチサーバースケーリングをサポートするものの、クラスターサーバーのアーキテクチャを利用すると単一のサーバー内で起こる Socket.io のクラスタリングと RedisStore の相互作用によってロジックが非常に複雑になり、デバッグも格段に複雑になる。

さらに、このアーキテクチャを使ったとしてもクラスター内の全てのプロセスが CPU バウンドな処理を行っている間は新しい接続が依然としてブロックされる。

このため、固定された数のプロセスを前もってフォークするのではなく、サーバーサイドのスプレッドシートごとに一つのバックグラウンドスレッドを用意する方式が望ましい。このときコマンド実行のタスクは全ての CPU コアに分散される。

この方式を実装するには、W3C の Web Worker API がピッタリだった。この API は元々ブラウザ向けに策定されたもので、スクリプトをバックグラウンドで独立した形で実行する方法を定義する。サーバーサイドで使えば、メインスレッドをブロックすることなく時間のかかるタスクを中断せずに実行できるようになる。

こうして私たちは Web Worker API の Node.js 向けクロスプラットフォーム実装 webworker-threads を作成した。

webworker-threads を使うと、SocialCalc スレッドの作成とデータのやり取りは非常に簡単になる:

{ Worker } = require \webworker-threads
w = new Worker \packed-SocialCalc.js
w.onmessage = (event) -> ...
w.postMessage command

この解決法だとシングルコアのイベントサーバーとマルチコアのイベントクラスターサーバーのいいとこ取りができる: 必要な場合は EtherCalc に多くの CPU 時間を割り当てることができ、単一 CPU 環境ではバックグラウンドスレッドの作成から生じるオーバーヘッドは無視できる程度となる。

得られた教訓

制約によって身軽になる

Fred Brooks は著書 The Design of Design で、制約が設計者の検索空間を狭めることで集中を助け、設計プロセスが前進することがあると主張した。この「制約」には自発的 (人工的) な制約も含まれる:

設計タスクに対する人工的な制約には「好きに緩められる」という素晴らしい特徴がある。理想的には、そういった制約によって設計者の思考が設計空間の未探索な領域に押し出され、創造性が刺激されることが期待される。

EtherCalc の設計において、こういった制約は数多くのイテレーションを通じてコンセプト的完全性 (conceptual integrity) を保つ上で非常に重要だった。

例えば、ホスティングシナリオのそれぞれ (behind-the-firewall, on-the-cloud, multi-tenant) に最適化された並列アーキテクチャを持つサーバーを作る選択肢は魅力的に思える。しかし、そのような「早すぎる最適化」はコンセプト的完全性を大きく傷つける結果に終わっただろう。

この選択肢を EtherCalc は取らず、CPU、メモリ、ネットワークの使用量を同時に最小化してリソース要件を全て満たすアーキテクチャを採用した。さらに、RAM 要件が 100 MB にも満たないことから、Raspberry Pi などの組み込みプラットフォームでも EtherCalc を簡単に実行できるようになった。

この自発的な制約があったおかげで、三つのリソース全てが制限される PaaS 環境 (例えば DotClout, Nodejitsu, Heroku) に EtherCalc をデプロイすることも可能になった。これによって個人用スプレッドシートサービスの立ち上げが非常に簡単になり、独立した利用者からのコントリビューションが増加した。

最悪が最良

シカゴで開催された YAPC::NA 2006 に招待されたとき、私はオープンソースの世界の将来を次のように予想した:

証明はできませんが、こう考えています。来年 JavaScript 2.0 は自身をブートストラップし、完全にセルフホスト可能な言語となり、JavaScript 1 へのコンパイルが可能になり、あらゆる環境における「次に来るもの (Next Big Thing)」の座を Ruby から奪うのではないでしょうか。

CPAN と JSAN は統合されると思います: JavaScript は全ての動的言語に対する共通バックエンドになり、Perl をブラウザ、サーバー、データベース内部で実行でき、そのとき同じ開発ツールが使えるようになるはずです。

なぜなら、皆さんご存じのように、悪い方が良いworse is betterのですから、最悪worstのスクリプト言語は最良bestとなる定めにあるからです。

ネイティブと同等の速度で動作する新しい JavaScript エンジンが次々と登場した 2009 年ごろ、この予想は現実となった。執筆時点において、JavaScript は「一度書けば、あらゆる場所で実行できる (write once, run anywhere)」仮想マシンとなった ── 他の主要なプログラミング言語を JavaScript にコンパイルしたとしても、パフォーマンスのペナルティはほとんど生じない。

クライアントサイドのブラウザとサーバーサイドの Node.js に加えて、JavaScript の Postgres データベースへの組み込みも行われている。そして、そういったランタイム環境で共有できる無料かつ再利用可能なモジュールの巨大なコレクションが存在する。

コミュニティが突如として成長したのはどうしてだろうか？ EtherCalc を開発する中で、飛び立ったばかりの NPM コミュニティに参加して感じたのは、JavaScript が制約をほとんど持たず、様々な利用法に応じて柔軟に姿を変えられるために、イノベーター (例えば jQuery や Node.js) が文法やイディオムに集中できる事実である。それぞれのチームは制約の少ない共通のコアから自身の考える優れた要素 (Good Parts) を抽象化できる。

このとき、新しいユーザーには非常に単純な言語のサブセットが提供される: 逆に、経験を積んだ開発者には今までより優れたコードの書き方を考案することが期待される。言語開発チームが中心となって予想されるユーザーの全てに対して完璧な言語を作成するのではない、JavaScript の草の根的な開発プロセスは、Richard P. Gabriel の有名な格言「悪い方が良いworse is better」を体現したものと言えるだろう。

LiveScript 再訪

Perl の Coro::AnyEvent は非常に分かりやすい構文をしているのに対して、Node.js が持つコールバックベースの API では何重にも入れ子になった再利用が難しい関数が必要になる。

様々なフロー制御ライブラリを実験した後、この問題は LiveScript によって解決された。LiveScript は JavaScript にコンパイルされる新しい言語であり、Haskell と Perl に大きく影響された構文を持つ。

実は、EtherCalc の開発で使われてきた言語は 4 つある: JavaScript, CoffeeScript, Coco, LiveScript である。イテレーションのたびに表現力は強くなり、js2coffee や js2ls といったツールのおかげで後方および前方の互換性は完全に保たれた。

LiveScript は独自のバイトコードではなく JavaScript にコンパイルされるので、関数スコープのプロファイラと完全な互換性を持つ。LiveScript コンパイラが生成するコードはモダンなネイティブランタイムを活用し、人間の手で最適化された JavaScript コードと同程度の性能を持つ。

構文について言うと、LiveScript は入れ子になったコールバックを backcall や cascade といった新しい構文で置き換える。こういった構文は関数的そしてオブジェクト指向的な合成を可能にする強力な構文的ツールを提供する。

初めて LiveScript に触れたとき、私は「Perl 6 から抜け出そうとしている小さな言語」という印象を持った ── この目標は、JavaScript と同じ意味論を採用し、構文的な使いやすさだけに集中することで格段に達成しやすくなっていた。

結論

SocialCalc は詳細に定義された仕様とチーム開発プロセスを持っていたのに対して、2011 年中ごろから 2012 年末まで EtherCalc は一人で開発された実験プロジェクトだった。このプロジェクトは Node.js がプロダクションでの利用に耐えるかどうかを見極めるための実験場としても機能した。

このプロジェクトは制約が緩く自由な実験が可能だったので、様々な言語、ライブラリ、アルゴリズム、アーキテクチャの選択肢を探索する素晴らしい機会となった。全てのコントリビューター、コラボレーター、インテグレーターに感謝する。様々なテクノロジの実験をするよう私に促してくれた Dan Bricklin と Socialtext の同僚には特に感謝している。ありがとう！