dagoba: インメモリグラフデータベース

何かを単体で取り出そうとすると、それが宇宙に存在するあらゆるもの結びつき、決して断ち切れない透明な無数の糸で固く結ばれていることに我々は気が付く。

── ジョン・ミューア

自己でない何かを求めて世界の果てへと歩みを進めたもの ── 神、太陽、シェイクスピア、旅する商人 ── は、現実の世界を自力で歩んだという事実によって「自己」となる。

── ジェームス・ジョイス

太古の時代、まだ世界が若かったころ、全てのデータは一つのファイルに幸せに収まっていた。データをフェンスの向こうに移動させるときは、フェンスを下ろして、データを一つずつ移動させればそれで済んだ。パンチカードが一枚入り、パンチカードが一枚出ていく。人生は単純で、プログラミングは楽な仕事だった。

しばらくするとランダムアクセスの革命が起きて、データは野原を自由に駆け回るようになった。するとデータを管理する「牧羊犬」の役割が大きな問題となった: データの任意の箇所にいつでもアクセスできるなら、次に使われるデータなど知りようがない！ この問題に対処するため、データの間にリンクを張り、リンクの結びつきから形成されるグループを利用してデータの群れを管理する様々な技術が開発された¹。この設計においてデータの問い合わせとは、羊を一匹選び、それに結び付いているものを全て呼び寄せることに等しい。

後にプログラマーはこの手法を離れ、データをまとめる規則を中心とする手法に移行した²。この手法では内容の全く異なるデータを直接リンクで結ぶのではなく、データを小さなピースに分解し、各ピースに名前の付いた首輪を付けた上でひとまとまりのピースを小さな柵で囲うことでデータの内容に応じたクラスターを作成する。データの問い合わせは宣言的に行われ、部分的に分解された (リレーショナリストが「正規」と呼ぶ状態にある) データのピースを集めた「フランケンコレクション」がプログラマーに返される。

記録された歴史の大半において、このリレーショナルモデルは支配的な地位に君臨した。二つの言語大戦争や無数の小競り合いを経てもリレーショナルモデルの座を脅かす者は現れなかった。効率、スケーラビリティ、使い勝手を少し犠牲にすれば、およそデータベースモデルに望まれるものは全て提供される。このコストを長い間プログラマーは受け入れてきた。そしてインターネットが生まれた。

分散革命でまた全てが変わった。データは空間的制約から自由になり、マシンからマシンへと動き回るようになった。CAP を華麗に使いこなす理論家たちはリレーショナルモデルが独占する舞台に上がり込み、データの群れを管理する様々な新しいテクニックへの扉を開いた ── その中にはランダムアクセスデータを飼い慣らすために考案された最初期の試みを思い起こさせるものもあった。本章ではそういったテクニックの一つであるグラフデータベースと呼ばれるスタイルに注目する。

ファーストテイク

本章ではグラフデータベースを作成する³。その中で私たちは問題空間を探索し、設計に関する問題に対して複数の解決策を提示し、それぞれの解決策を比較してトレードオフを理解し、そして最終的に正しい解決策を選択する。コードを短くすることに通常以上の注意が払われる点を除けば、本章で示すのはプロのソフトウェア開発者が遠い昔から用いてきたプロセスの再現である。このプロセスを読者に教えること、そしてグラフデータベースを作成することが本章の目的となる⁴。

グラフデータベースを使うと一部の興味深い問題をエレガントな方法で解けるようになる。グラフは物事のつながりを非常に自然に表現できるデータ構造である。ここで「グラフ」とは数学の用語であり、頂点の集合と辺の集合から構成される。言い換えれば、いくつかの点をいくつかの線で結ぶとグラフになる。では「データベース」とは何か？ データベースは文字通りデータの基地baseであり、データを後で取り出すために置いておく場所である。

どのような問題がグラフデータベースで解けるだろうか？ あなたが家系図を眺めているとする: 両親がいる、祖父母がいる、祖父母の従妹がいる、といったことが分かる。このとき「Thor の従妹の子は？」「Freyja から見て Valkyries はどんな関係？」といった自然でエレガントな問いに応えられるシステムを作成したくなることだろう。

グラフを表すデータ構造のスキーマとしては、エンティティのテーブルと関係のテーブルを持つものが考えられる。このスキーマでは、Thor の親を取得するクエリを次のように書ける:

SELECT e.* FROM entities as e, relationships as r
WHERE r.out = "Thor" AND r.type = "parent" AND r.in = e.id

しかし、この方法を拡張して祖父母を取得するにはどうすればいいだろうか？ サブクエリを使うか、ベンダー固有の SQL 拡張を使うしかない。「従妹の孫」などが必要になった場合には、膨大な SQL を書くことになる。

私たちが書きたいのは簡潔かつ柔軟なクエリである: 抱えている質問を自然な形でモデル化し、それでいて似た質問に拡張できるクエリが望ましい。second_cousins('Thor') は簡潔であるものの柔軟性が全くない。上記の SQL は柔軟であるものの簡潔でない。

Thor.parents.parents.parents.children.children.children のような表現ができれば簡潔さと柔軟性のバランスが取れるように思える。このプリミティブを使えば簡潔で自然なクエリが書け、様々な同様のクエリを柔軟に作成できる。この特定の式は結果が多すぎるので役に立たないものの、これは例に過ぎない。

この種のインターフェースが可能な最も単純なデータベースはどんなものだろうか？ リレーショナルスキーマと同様に頂点のリストと辺のリストを用意して、ヘルパー関数を作る方法が考えられる。次のようになるだろう:

V = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ]
E = [ [1,2], [1,3],  [2,4],  [2,5],  [3,6],  [3,7],  [4,8]
    , [4,9], [5,10], [5,11], [6,12], [6,13], [7,14], [7,15] ]

parents = function(vertices) {
  var accumulator = []
  for(var i=0; i < E.length; i++) {
    var edge = E[i]
    if(vertices.indexOf(edge[1]) !== -1)
      accumulator.push(edge[0])
  }
  return accumulator
}

parents は「リストを走査し、何らかの計算をして結果を accumulator に付け足す」処理を行う関数である。ループの構文が不必要な複雑性をコードに加えているので、この事実が分かりにくいかもしれない。

parents が行うような処理のために特別に設計されたループ構文があれば便利である。実は、reduce 関数を使うとちょうどこの処理を行える: reduce はリストと関数を受け取り、リストの各要素に対して関数を評価する。そのとき関数には結果を記録する変数も渡され、その変数の最終的な値が関数の返り値となる。

reduce 関数を使って関数的スタイルに書き直すと、parents 関数 (および children 関数) は次のように書ける:

parents  = (vertices) => E.reduce( (acc, [parent, child])
         => vertices.includes(child)  ? acc.concat(parent) : acc , [] )
children = (vertices) => E.reduce( (acc, [parent, child])
         => vertices.includes(parent) ? acc.concat(child)  : acc , [] )

parents 関数は頂点のリストを受け取り、辺のリスト E に対する reduce を行う。注目している辺の子が入力として受け取った頂点のリストに含まれるなら、その辺の親を結果記録用のリストに追加する。children 関数は「親」と「子」を逆転させた parents 関数である。

上記のコードは正当な JavaScript であるものの、執筆時点で一部のブラウザが未実装の機能をいくつか使っている。次のコードならば全てのブラウザで実行できる:

parents  = function(x) { return E.reduce(
  function(acc, e) { return ~x.indexOf(e[1]) ? acc.concat(e[0]) : acc }, [] )}
children = function(x) { return E.reduce(
  function(acc, e) { return ~x.indexOf(e[0]) ? acc.concat(e[1]) : acc }, [] )}

parent 関数と children 関数は次のように利用する:

children(children(children(parents(parents(parents([8]))))))

この呼び出しは右から読み、「頂点 8 の親の親の親の子の子の子 (全員)」を表す。大量の頂点が入った配列が返るだろう。以上で欲しかった機能が手に入った。ここで一度これまでのコードをしばらく眺めてみてほしい。改善できる部分はないだろうか？

一つの大きな問題として、頂点と辺をグローバル変数としている点がある。このためデータベースは同時に一つしか存在できない。

また、頂点の配列 V を全く利用していないのは奇妙である。言い換えれば、必要な情報は全て辺の配列 E から得られている。これは頂点を表す値 (V の要素) が辺の表現で使われる整数と等しいためである。そのため「Freyja から見て Valkyries はどんな関係？」といった質問に答えるには、頂点にデータを加える必要がある。このとき頂点は複数の値から構成され、辺の配列は頂点の値ではなく頂点の参照から構成される。

辺に対しても同じことが言える: 現在のコードでは辺の「始点」と「終点」を記録できる⁵だけで、辺自体に情報を加えることはできない。「Loki に継親は何人いる？」や「Thor が生まれたとき Odin には何人の子がいた？」といった質問に答えるには、辺に情報を持たせる必要がある。

また、parent と children のコードが非常によく似ていることは目を凝らさずとも理解できる。さらに抽象化した関数を使って両者を書き換えることができるだろう。

他に問題を見つけられただろうか？

セカンドテイク

それでは発見された問題を解決しよう。頂点と辺をグローバル変数で表現すると複数のグラフを同時に作れなくなるものの、複数のグラフを作成したい場面は明らかに存在する。この問題を解決するには何らかの構造が必要になる。まずは名前空間から始めよう:

Dagoba = {} // 名前空間代わりのオブジェクト

Dagoba ではオブジェクトを名前空間として用いる。JavaScript のオブジェクトはキーとバリューの組を集めた順序無し集合にほぼ等しい。そもそも JavaScript には基礎的なデータ構造が 4 種類しかないので、オブジェクトが多用される。 (「JavaScirpt が持つ 4 種類の基礎的なデータ構造が何か知ってる？」はパーティにぴったりの質問である。)

続いてグラフが必要になる。グラフを古典的な OOP (オブジェクト指向) パターンで作成することもできる。しかし JavaScript はプロトタイプ型の継承を提供するので、ここではプロトタイプオブジェクトを利用してグラフを作成する ── プロトタイプオブジェクトは Dagoba.G と呼ぶ。そしてグラフのインスタンスはファクトリ関数 Dagoba.graph で作成する。この方式の利点の一つとして、ファクトリ関数から異なる種類のオブジェクトを返せる点がある。グラフオブジェクトの作成に何らかのクラスのコンストラクタを使うと、グラフを表すクラスを後から変更できなくなる。ファクトリ関数を使っておけば柔軟性が簡単に得られる。

Dagoba.G = {}                                // プロトタイプオブジェクト

Dagoba.graph = function(V, E) {              // ファクトリ関数
  var graph = Object.create( Dagoba.G )

  graph.edges       = []                     // 共有されないように新しいコピーを作る
  graph.vertices    = []
  graph.vertexIndex = {}                     // 探索の最適化で利用される

  graph.autoid = 1                           // 自動で増える ID カウンター

  if(Array.isArray(V)) graph.addVertices(V)  // V が配列なら V を頂点に設定する
  if(Array.isArray(E)) graph.addEdges(E)     // E が配列なら E を辺に設定する

  return graph
}

Dagoba.graph は二つの省略可能引数を持つ: V は頂点の配列を、E は辺の配列を表す。JavaScript はパラメータに関して厳密でない⁶ので、全ての名前付きパラメータは省略でき、省略されたパラメータの値は undefined となる。グラフオブジェクトを作成する時点で頂点と辺が分かっていて V と E のパラメータに値を渡せる場合もあれば、作成時点では頂点と辺が判明せずプログラムを通じてグラフオブジェクトを動的に作成する場合もある⁷。

これで以前のコードが持っていた欠点の一つが克服された: Dagoba.graph が返すグラフオブジェクトの辺と頂点は配列 (JavaScript が持つ基礎的なデータ構造の一つ) であり、呼び出しのたびに新しいものが作成される。グラフオブジェクトに付与されるプロパティ vertexIndex と autoid については後述する。(考えてみよう: これらのプロパティをプロトタイプオブジェクトに持たせられないのはなぜか？)

ファクトリ関数は二つの関数 addVertices と addEdges を呼び出す。これらを定義しよう:

Dagoba.G.addVertices = function(vs) { vs.forEach(this.addVertex.bind(this)) }
Dagoba.G.addEdges    = function(es) { es.forEach(this.addEdge  .bind(this)) }

何も難しいところはない ── それぞれ addVertex と addEdge に仕事を受け渡しているだけである。これらの関数も定義しよう:

Dagoba.G.addVertex = function(vertex) { // 頂点風のオブジェクトを受け取る
  if(!vertex._id)
    vertex._id = this.autoid++
  else if(this.findVertexById(vertex._id))
    return Dagoba.error('与えられた頂点と同じ ID を持つ頂点が既に存在します')

  this.vertices.push(vertex)
  this.vertexIndex[vertex._id] = vertex // インデックスを管理するトリック
  vertex._out = []; vertex._in = []     // プレースホルダー: 辺を指すポインタが入る
  return vertex._id
}

vertex が _id プロパティを持たない場合、autoid を使って _id が自動的に割り当てられる⁸。もし _id が過去に使われていたら、その頂点は処理できないのでエラーを出して処理を終える。はて、この状況はいつ発生するのだろうか？ そもそも頂点は正確にどんなオブジェクトなのだろうか？

古典的なオブジェクト指向システムでは任意の頂点が頂点クラスのインスタンスなので、頂点が何かを知りたければ頂点クラスの定義を探すことになる。しかし私たちは異なるアプローチを採用し、三つのプロパティ _id, _out, _in を持つ任意のオブジェクトを頂点とみなしている。なぜこうしたのだろうか？ 一言で言えば、ホストアプリケーションと共有するデータの制御を Dagoba に与えるためである。

もし addVertex 関数の中で Dagoba.Vertex のインスタンスを作成するなら、Dagoba が用いる内部データはホストアプリケーションと一切共有されない。一方で、もし addVertex 関数が引数に Dagoba.Vertex のインスタンスを受け取るなら、ホストアプリケーションは頂点オブジェクトへのポインタを取っておいて実行時に後から操作し、Dagoba が利用する不変条件を壊すことができてしまう。

つまり頂点オブジェクトを Dagoba.Vertex のインスタンスとする場合、渡されたデータを新しいオブジェクトに毎回コピーしてメモリを無駄使いする (可能性を生む) か、それともホストアプリケーションにデータベースオブジェクトへの自由なアクセスを許すかを前もって選択しなければならない。これは性能と安全性のトレードオフであり、正しいバランスはユースケースによって異なる。

これに対して、Dagoba のようにオブジェクトのプロパティを利用するダックタイピングを利用すれば、この判断を実行時まで遅らせることができる。ユーザーは手元にあるオブジェクトをディープコピー⁹してから Dagoba に渡すか、 そのまま Dagoba の頂点として使うかを自分で判断できる¹⁰。性能と安全性のバランスを取る責任をユーザーに押し付けることは望ましくないという考え方も当然ある。しかし二つのアプローチは大きく異なるので、この柔軟性は重要となる。

グラフが持つ頂点のリストに新しい頂点を加える処理が以上で書けた。_id による探索の効率化のため vertexIndex に要素が追加され、さらに _out, _in という辺の集合を表す二つの配列が作成される¹¹。

続いて addEdge を実装しよう:

Dagoba.G.addEdge = function(edge) { // 辺風のオブジェクトを受け取る
  edge._in  = this.findVertexById(edge._in)
  edge._out = this.findVertexById(edge._out)

  if(!(edge._in && edge._out))
    return Dagoba.error("与えられた辺の" + (edge._in ? '終点' : '始点')
                                         + "が見つかりません")

  edge._out._out.push(edge) // edge の終点の「自身が終点の辺」リストに edge を追加
  edge._in._in.push(edge)   // edge の始点の「自身が始点の辺」リストに edge を追加

  this.edges.push(edge)
}

最初に辺が結ぶ二頂点を見つける処理がある。いずれかの頂点が見つからなければエラーを出して処理を終える。このとき呼び出されるヘルパー関数 Dogoba.error を次に示す。Dagoba はエラーを返す前に必ずこの関数を呼び出すので、アプリケーションは関数をオーバーライドすることでエラー時の振る舞いを自由に変更できる。さらに手を入れて onError ハンドラを登録する仕組みにすれば、ホストアプリケーションはヘルパー関数をオーバーライドせずともコールバックを登録するだけで独自にエラーを処理できる。必要とされる柔軟性に応じて、エラーを処理するコールバックはグラフごと、アプリケーションごと、またはその両方で登録可能とできるだろう。

Dagoba.error = function(msg) {
  console.log(msg)
  return false
}

続いて新しい辺を頂点が持つ辺のリストに追加する処理が二つある: 辺の始点が持つ「自身が始点の辺」リストと、辺の終点が持つ「自身が終点の辺」リストに新しい辺が追加される。

これで今のところ必要なグラフに関するデータ構造が全て説明できた！

クエリの入力

Dagoba には本質的に二つの部分しかない: グラフを保持する部分と、グラフに関する質問 (クエリ) に答える部分である。前者はこれまで見たように難しくない。後者は少し難しくなる。

以前と同様に、クエリを作るファクトリ関数を使ったプロトタイプを作ってみよう:

Dagoba.Q = {}

Dagoba.query = function(graph) {        // ファクトリ関数
  var query = Object.create( Dagoba.Q )

  query.   graph = graph                // 考えているグラフ
  query.   state = []                   // 各ステップにおける状態
  query. program = []                   // 実行するステップ
  query.gremlins = []                   // 各ステップにおける「グレムリン」
  return query
}

いくつか用語を定義する。

プログラム (program) はいくつかのステップ (step) から構成される。それぞれのステップはパイプラインにおける一つのパイプのようなものと言える: 何らかのデータを受け取り、それに何らかの変形を施して出力する。正確には少し異なる動作をするが、最初に理解する比喩としてはこれで問題ない。

プログラムの各ステップは状態 (state) を持つことができる。query.program に含まれる各ステップが持つ状態からなるリストが query.state である。

グレムリン (gremlin) はグラフ中を飛び回って指示通りの仕事をする小動物である。どうしてデータベースにグレムリンが出てくるのかと驚いたかもしれないが、これは Tinkerpop のBlueprint と Gremlin and Pacer query languages から始まった伝統なので納得してほしい。グレムリンは頂点などの様々な情報を記憶できるので、グレムリンを利用すれば様々な興味深い質問に答えられる。

グラフに関する質問の表現方法に関して以前に考えたことを思い出してほしい。そのときは Thor.parents.parents.parents.children.children.children のような形式が質問の表現として優れていると結論したのだった。Dagoba では、この式の parent と children のそれぞれが一つのステップに対応する。ステップの操作を実行する関数をパイプタイプ (pipetype) と呼び、各ステップはパイプタイプへの参照を持つ。

Dagoba の実際のクエリは次のような形をしている:

g.v('Thor').out().out().out().in().in().in()

ステップは関数呼び出しで作成されるので、引数を渡すことができる。クエリのインタープリタはステップの引数をステップのパイプタイプに受け渡す。例えば g.v('Thor').out(2, 3) というクエリでは out のパイプタイプが [2, 3] を最初のパラメータとして受け取る。

クエリにステップを追加する手段が必要になる。そのためのヘルパー関数を定義しよう:

Dagoba.Q.add = function(pipetype, args) { // 新しいステップをクエリに追加する
  var step = [pipetype, args]
  this.program.push(step) // ステップはパイプタイプとその引数の組である
  return this
}

ステップは二つの要素からなる: パイプタイプ (関数) と、パイプタイプに渡すべき引数からなる二要素のタプル¹²がステップを表す。パイプタイプに引数を部分適用した関数を作れば二つ要素をステップの作成時に融合させることもできるものの、そうすると後で有用となるデバッグ情報が失われてしまう。

グラフに対する新しいクエリを作成するクエリ初期化関数をいくつか定義する。次に示す v メソッドは、以降の例で最初に使われることが多い。v は新しいクエリを作成し、ヘルパー関数 add を使って新しいクエリプログラムを組み立てる。このとき使われるパイプタイプ vertex については後述する。

Dagoba.G.v = function() { // クエリ初期化関数: g.v() -> query
  var query = Dagoba.query(this)
  query.add('vertex', [].slice.call(arguments)) // プログラムにステップを追加
  return query
}

なお、[].slice.call(arguments) は「現在の関数に渡された引数からなる配列」を得るためのイディオムである。arguments は多くの場面で配列のように振る舞うので配列だと思っている読者もいるかもしれないが、モダンな JavaScript で配列が持つ機能の多くを arguments は持たない。

積極評価の問題

様々なパイプタイプを見ていく前に寄り道をして、実行戦略という興味深い世界を紹介する。有名な実行戦略が二つある: 一つ目の積極評価 (eager evaluation) は eager beaver仕事の虫 とも呼ばれ、関数を適用する前に必ず全ての引数を評価することにこだわる。もう一つの遅延評価 (lazy evaluation) は積極評価の逆で、あらゆる値の計算を必要になる最後の瞬間まで先延ばしにする ── ある意味で、遅延評価は怠惰 (lazy) である。

JavaScript は積極評価の言語なので、ステップの結果は呼び出されるたびに計算される。例えば g.v('Thor').out().in() では最初に Thor の頂点を見つけ、その頂点の外向き辺の終点を全て見つけ、それらの頂点のそれぞれについて内向き辺の始点を全て見つけ、それらを集めたものが結果となる。

積極評価でない言語であっても最終的な結果は変わらない ── 上記の式の評価で実行戦略はそれほど意味を持たない。ただ、呼び出しをさらに増やしたらどうだろうか？ Thor に親戚が多ければ、g.v('Thor').out().out().out().in().in().in() というクエリは非常に多くの結果を生成する ── クエリの結果から重複を除去する処理がなければ、返り値がグラフの頂点数より多くなる可能性さえある。

しばらくしてユーザーが興味を持つのは重複を除いた結果の最初の数個だけだと分かり、クエリが g.v('Thor').out().out().out().in().in().in().unique().take(10) に変更されたとする。このときクエリの結果は最大でも 10 個である。しかし積極評価を使うと、最初の 10 個しか使わないのにもかかわらず途中で大量の頂点が生成される可能性がある。

あらゆるグラフデータベースには実行する処理を可能な限り少なくする仕組みが必要であり、多くは何らかの形の遅延評価を採用する。本章ではクエリのインタープリタを自分たちの手で作成しているので、プログラムを遅延評価する仕組みを実装することもできる。しかし、それにはコストが伴う。

評価戦略の変更が持つメンタルモデルへの影響

ここまでクエリの評価を考えるときのメンタルモデルは非常に単純だった:

• 頂点の集合をリクエストする。
• 受け取った集合をパイプの入口に流し込む。
• 同じことを必要なだけ繰り返す。

このメンタルモデルは理解しやすいので、この通りの説明をユーザーに提示すべきだと思うかもしれない。しかし上述した理由により、このモデルの通りにグラフデータベースを実装することはできない。現実の実装と異なるメンタルモデルをユーザーに持たせることは混乱の元でしかない。これは不完全な抽象化 (leaky abstraction) より悪い事態と言える。いずれユーザーの失望や認知的不協和、あるいは「キレ落ち」を引き起こすだろう。

ただ、このメンタルモデルの問題がそれほど大きくないのも確かである: 実行モデルがどうであれクエリの結果は変わらず、パフォーマンスが変わるだけに過ぎない。ここには次のトレードオフが存在する:

• 全てのユーザーにシステムを使うに先立って複雑なモデルを学習させる。
• クエリのパフォーマンスを深く理解したいと望む一部のユーザーに単純なモデルから複雑なモデルへ移行させる。

このどちらを取るかを考えるとき、考慮すべき事項がいくつかある:

• 単純なモデルと比べたときの複雑なモデルの認知的難易度
• 単純なモデルを飛ばして複雑なモデルだけを学ぶのではなく最初に単純なモデルを学んだ後に複雑なモデルへ進む場合に追加で発生する認知的負荷
• メンタルモデルの移行を必要とするユーザー (その比率、必要とされる認知的能力、費やせる時間など)

Dagoba では、二つのメンタルモデルを用意しても構わないと考えられる。なぜなら、ほとんどのクエリに対する結果は十分高速に計算できるので、大部分のユーザーはクエリ構造の最適化やモデルの深い理解を必要としないからである。大規模なデータセットに対する複雑なクエリを書くユーザーが新しいメンタルモデルへの移行を必要とする可能性は高いものの、そういったユーザーが移行を負担に感じる可能性は低い。さらに、事前に単純なモデルを学んでいたとしても複雑なモデルの学習が格段に難しくなるわけではないと思われる。

この新しいモデルについては後で詳しく見る。ここでは次の点を頭に入れてから進んでほしい:

• それぞれのパイプは結果を一つずつ生成する。全ての結果をまとめて生成することはない。
• クエリを評価する中で、それぞれのパイプは何度も実行される。
• 「入出力ヘッド」が次に実行するパイプを制御する。入出力ヘッドは最初パイプラインの末尾を指し、アクティブなパイプの実行結果に応じて左右に移動する。
• パイプの実行結果が先述したグレムリンである可能性もある。グレムリンは一時的なクエリの評価結果を表し、他のパイプに何らかの状態を伝える。パイプの実行結果がグレムリンのとき、入出力ヘッドは先頭に向かって移動する。
• パイプの実行結果が「pull」だと、入出力ヘッドは先頭に向かって移動する。
• パイプの実行結果が「done」だと、入出力ヘッドは末尾に向かって移動する。「done」は自身より前にあるパイプの再実行が必要でないことを表す。

パイプタイプ

パイプタイプは Dagoba というシステムの中心に位置する。様々なパイプタイプの振る舞いを理解すれば、インタープリタでどのように組み合わされ実行されるかも理解しやすくなるだろう。

まずパイプタイプを保管する場所と、そこに新しいパイプタイプを追加する関数を作成する:

Dagoba.Pipetypes = {}

Dagoba.addPipetype = function(name, fun) { // チェイン可能なメソッドを追加する
  Dagoba.Pipetypes[name] = fun
  Dagoba.Q[name] = function() {
    // パイプタイプと引数をキャプチャする
    return this.add(name, [].slice.apply(arguments)) }
}

この関数を呼び出すとパイプタイプの関数がパイプタイプのリストに追加され、クエリオブジェクトに新しいメソッドが追加される。全てのパイプタイプには対応するクエリメソッドが存在する。このメソッドはクエリプログラムに新しいステップを追加し、そのとき自身に渡された引数も記録する。

クエリ g.v('Thor').out('parent').in('parent') を評価するとき、最初の v の呼び出しはクエリオブジェクトを返す。次の out の呼び出しは this を通して渡されたクエリオブジェクトに新しいステップを追加し、そのクエリオブジェクトを返す。in の呼び出しでも同様となる。これでメソッドチェーンを使ってクエリを組み立てる API が完成した。

次の点を考えてみてほしい: 上記の実装だと、同名のパイプタイプを複数作ると最後に作成されたものが使われる。そのため既存のパイプタイプを実行時に変更できる。この設計で何が失われただろうか？ 他にどんな選択肢があるだろうか？

名前でパイプタイプを取得する関数も実装しておく:

Dagoba.getPipetype = function(name) {
  var pipetype = Dagoba.Pipetypes[name] // パイプタイプは関数である

  if(!pipetype)
    Dagoba.error('未定義のパイプタイプ: ' + name)

  return pipetype || Dagoba.fauxPipetype
}

指定されたパイプタイプが見つからないときはエラーを生成してデフォルトのパイプタイプ Dagoba.fauxPipetype を返す。このパイプタイプは空のパイプのようなものであり、入力されたデータをそのまま出力する:

Dagoba.fauxPipetype = function(_, _, maybe_gremlin) {
  // 結果を上流に渡すか、「pull」を下流に渡す
  return maybe_gremlin || 'pull'
}

引数のアンダースコアは関数本体で利用しない引数を表す。多くのパイプタイプは三つの引数を全て利用するので、引数に名前が付けられる。利用しない変数の名前をアンダースコアにすれば、特定のパイプタイプが依存するパラメータを定義からすぐに読み取ることができる。

このアンダースコアを使うテクニックはコメントを垂直に揃えやすくなるという意味でも重要である。本気で言っている: プログラムは「人間にとっての読みやすさを優先して書くべきであり、機械にとっての実行しやすさを優先して書くべきではない」なら、私たちの一番の懸念事項はコードの見た目であるべきだということになる。

vertex

本章で触れる多くのパイプタイプは一つのグレムリンを受け取って複数のグレムリンを生成する。しかし、次の vertex パイプタイプは文字列だけからグレムリンを生成する。頂点 ID を受け取った場合は新しいグレムリンを一つ返し、クエリを受け取った場合はマッチする頂点を一つずつ返す。

Dagoba.addPipetype('vertex', function(graph, args, gremlin, state) {
  if(!state.vertices)
    state.vertices = graph.findVertices(args) // 状態の初期化

  if(!state.vertices.length)                  // 動作終了
    return 'done'

  // 最適化: ここで頂点がコピーされている
  var vertex = state.vertices.pop()
  // 受け取ったグレムリンの状態をコピーする
  return Dagoba.makeGremlin(vertex, gremlin.state)
})

マッチする頂点の検索を以前に実行したかどうかを最初にチェックし、実行していなければ検索を実行する。マッチする頂点が一つでもあれば、マッチ結果から頂点を一つポップして、その頂点を持ったグレムリンを返す。グレムリンはそれぞれ状態 (これまでに通過したパイプタイプの記録など) を持つので、グレムリンを引数に受け取った場合はそれを返り値のグレムリンにコピーする。

状態を表す引数 state は直接改変され、返り値には含まれない点に注目してほしい。グレムリンやシグナルではなくオブジェクトをパイプタイプから返すようにして状態を呼び出し側に伝える設計も考えられる。ただ、そうすると返り値が複雑になってゴミが増える¹³。JavaScript が複数の返り値をサポートしていれば、この設計はもっと魅力的になっていただろう。

関数の中で状態を改変する場合、呼び出し側が元の値への参照を保持している状況で問題が発生する。どうすれば特定の参照が「唯一」である ── 同じオブジェクトを指す参照が他に存在しない ── ことを判定できるだろうか？

参照が唯一だと分かれば、高価なコピーオンライトや複雑な永続データ構造に頼ることなく不変性の恩恵を得られる。なぜなら、唯一の参照が指すオブジェクトが変化したとき、それが改変されたのか新しいオブジェクトに置き換えられたのかは外部からは分からないためである。「観測不変性 (observed immutability)」は保持される¹⁴。

参照の唯一性を判定する方法はいくつか知られている: 静的型付けのシステムでは、一意型¹⁵ (uniqueness type) を利用してコンパイル時にオブジェクトが参照を一つしか持たないことを保証する方法がある。参照カウント¹⁶の仕組みがあれば、実行時にオブジェクトの参照が唯一かどうかを判定し、その事実を利用した処理を行える ── 参照の唯一性を判定するだけなら、カウンターは 2 ビットで十分である。

JavaScript は一意型も参照カウントも持たない。しかし「非常に注意深いプログラミング」という手法によって同じ効果を得ることはできる。今のところは Dagoba でもこの方法を採用する。

in と out

グラフの走査はハンバーガーの注文と同じくらい簡単に行える。二つのパイプタイプ in, out は次の二行で定義できる:

Dagoba.addPipetype('out', Dagoba.simpleTraversal('out'))
Dagoba.addPipetype('in',  Dagoba.simpleTraversal('in'))

simpleTraversal 関数の返り値はパイプタイプであり、グレムリンを入力として受け取り、クエリされるたびに新しいグレムリンを生成する。グレムリンが全ていなくなると、「pull」リクエストを送って新しいグレムリンを自身の前のステップから新しいグレムリンを呼び寄せる。

Dagoba.simpleTraversal = function(dir) {
  var find_method = dir == 'out' ? 'findOutEdges' : 'findInEdges'
  var edge_list   = dir == 'out' ? '_in' : '_out'

  return function(graph, args, gremlin, state) {
    if(!gremlin && (!state.edges || !state.edges.length)) // クエリの初期化
      return 'pull'

    if(!state.edges || !state.edges.length) {             // 状態の初期化
      state.gremlin = gremlin
      state.edges = graph[find_method](gremlin.vertex)    // マッチする辺を取得
                         .filter(Dagoba.filterEdges(args[0]))
    }

    if(!state.edges.length)                               // これ以上すべきことはない
      return 'pull'

    var vertex = state.edges.pop()[edge_list]             // 辺を一つ消費する
    return Dagoba.gotoVertex(state.gremlin, vertex)
  }
}

最初の部分は in と out の違いを吸収するための変数を定義し、この後は全て返り値となるパイプタイプ関数の定義となる。この関数は先ほど見たパイプタイプ関数 vertex とよく似ている。引数に受け取ったグレムリンを state に取り込むのを見て驚いたかもしれない。vertex ではグレムリンを何もないところから作成していた。グレムリンを状態に取り込むのは、生成元の頂点が同じときグレムリンも同じにするためである。

ただ、他の部分が vertex と似ていることは理解できるだろう。クエリの初期化ステップがあるだけで、「在庫から一つ取り出して処理する。在庫が底をついたら新しいものを仕入れる」という基本的な流れは同じである。ここでの「在庫」とは注目している頂点からの外向き辺およびグレムリンであり、それぞれグラフオブジェクトのメソッドおよび返り値 'pull' を使って「仕入れ」が行われる。

上記のコードでは !state.edges.length が三か所で使われている。リファクタリングをしてコードの複雑性を削減したくなるかもしれないが、そのリファクタリングを妨げる問題が二つある:

一つ目の問題は比較的軽微である: 三つ目の !state.edges.length は最初の二つと意味が異なる。二つ目と三つ目の間で state.edges が変化するかもしれない。ただ、同じ関数の中で同じ式が異なる意味を持つのは理想的ではないので、この事実はリファクタリングが必要な理由でもある。

二つ目の問題はより深刻である。これから私たちはパイプタイプ関数をいくつも書くことになり、クエリや状態の初期化処理は何度も登場する。コードを書くときは、構造化された部分と構造化されていない部分のバランスを常に意識する必要がある。構造が多すぎればボイラープレートや複雑な抽象化に大きなコストを奪われることになり、構造が少なすぎれば重要でない細かな事項を大量に頭の中に入れておく必要が生じる。

現在のコードではパイプタイプの個数は最大でも数ダース程度なので、パイプタイプ関数のスタイルを可能な限り似せて、関数を構成する部分ごとにコメントを付けるのが良い選択に思える。よってコードの一貫性を保つため、このパイプタイプ関数をリファクタリングしたい欲求に抗うことにする。また、クエリや状態の初期化といった構造を抽象化する仕組みもあえて作成しない。もしパイプタイプが数百個も存在するなら、抽象化が正しい選択肢になるかもしれない: 抽象化によって加わる複雑性のコストは一定であるのに対して、その利益は抽象化を使うたびに線形に増えていく。可動部分が非常に多いなら、それらの間に共通要素を強制的に埋め込む仕組みは必ず有用となる。

property

ここで一旦手を止めて、ここまでに作成した三つのパイプタイプを使ったクエリの例を考えよう。Thor の祖父母は次のクエリで取得できる¹⁷:

g.v('Thor').out('parent').out('parent').run()

では、祖父母の名前が知りたい場合はどうすればいいだろうか？ この場合は map メソッドを使うことができる:

g.v('Thor').out('parent').out('parent').run()
 .map(function(vertex) {return vertex.name})

ただ、結果のプロパティの取得はよく使う操作なので、次のように書けるのが望ましい:

g.v('Thor').out('parent').out('parent').property('name').run()

さらに、こうするとプロパティを取得する処理がクエリの一部分となり、クエリの後に付け足される外部処理でなくなるのも都合がいい。後述するように、この仕組みには興味深い利点が存在する。

パイプタイプ property の実装を示す:

Dagoba.addPipetype('property', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                      // クエリの初期化
  gremlin.result = gremlin.vertex[args[0]]
  // プロパティが存在しないならグレムリンを殺す
  return gremlin.result == null ? false : gremlin
})

クエリの初期化に難しいところはない: グレムリンがいなければ pull する。グレムリンがいるなら、その result を引数で指定されたプロパティの値に設定する。その後グレムリンは次のステップに進む。これが最後のステップならクエリオブジェクトの run メソッドがグレムリンの result プロパティを収集してクエリの結果とする。なお、全てのグレムリンが result プロパティを持つわけではない。result プロパティを持たないグレムリンは vertex プロパティに最後に訪れた頂点を持つ。

指定されたプロパティが存在しないときグレムリンではなく false が返ることに注目してほしい。つまりパイプタイプ property はフィルタの一種として機能している。この事実は何かの役に立つだろうか？ この設計にはどのようなトレードオフが存在するだろうか？

unique

Thor の祖父母の孫 ── いとこ、兄弟、彼自身など ── を全て集めたいとする。このとき書くべきクエリは g.v('Thor').in().in().out().out().run() である。しかし、これを実際に実行すると重複する要素が大量に入った配列が返る。例えば、少なくとも 4 個の Thor が返り値の配列に含まれることは数学的に証明できる (Thor の個数が 4 より多くなるのはどんなときか？)。

この問題を解決するのがパイプタイプ unique である。クエリの最後に unique を加えて次のようにすれば、全ての要素が一度だけ含まれる配列が返る:

g.v('Thor').in().in().out().out().unique().run()

パイプタイプ unique の実装を示す:

Dagoba.addPipetype('unique', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                  // クエリの初期化
  if(state[gremlin.vertex._id]) return 'pull' // 重複する要素を無視する
  state[gremlin.vertex._id] = true
  return gremlin
})

unique は単なるフィルタと言える: グレムリンをそのまま次のステップに渡すか、そうでなければ前のステップに新しいグレムリンを要求する。

最初にグレムリンを要求することでクエリを初期化する。もしグレムリンの保持する頂点がキャッシュ state に存在するなら、その頂点は以前に見たことがあるので、それを無視して新しいグレムリンを要求する。グレムリンが持つ頂点がキャッシュに存在しなければ、それをキャッシュに追加してから次のステップに渡す。何も難しいところはない。

filter

簡単なフィルタとして機能するパイプタイプを二つ見てきた。もっと複雑な条件が必要な場合はどうするべきだろうか？ 体重が身長より大きい Thor の兄弟¹⁸を知りたいときは？ このクエリは次のようにパイプタイプ filter を使うと書ける:

g.v('Thor').out().in().unique()
 .filter(function(asgardian) { return asgardian.weight > asgardian.height })
 .run()

ラグナロクで生き残る Thor の兄弟を知りたい場合も filter が利用できる:

g.v('Thor').out().in().unique().filter({survives: true}).run()

パイプタイプ filter の実装を示す:

Dagoba.addPipetype('filter', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                          // クエリの初期化

  if(typeof args[0] == 'object')                      // オブジェクトによるフィルタ
    return Dagoba.objectFilter(gremlin.vertex, args[0])
           ? gremlin : 'pull'

  if(typeof args[0] != 'function') {
    Dagoba.error('フィルタが関数でもオブジェクトでもありません: ' + args[0])
    return gremlin                                    // とりあえず実行を進める
  }

  if(!args[0](gremlin.vertex, gremlin)) return 'pull' // フィルタで除去された
  return gremlin
})

もしフィルタの第一引数がオブジェクトでも関数でもなければエラーを発生させ、その上でグレムリンを素通りさせる。少し立ち止まって他の選択肢を考えてみてほしい。上記のコードでエラーが発生したときクエリの実行を続けるようにしたのはどうしてだろうか？

エラーが発生する状況は二つ考えられる。一つ目はプログラマーがクエリを入力する状況で、クエリが実行されたときにプログラマーが確認・理解できるエラーメッセージが表示される。これを受けてプログラマーはエラーを修正し、正しい結果だけが残るようにする。この状況だけを考えるなら、エラーメッセージだけを表示して結果を一つも生成しない設計も可能である。このときプログラマーは結果が生成されるようになるまでエラーを修正することになる。

二つ目の可能性として、フィルタが実行時に動的に適用される状況が考えられる。このときクエリを利用するコードを書いたプログラマーがクエリを組み立てるコードを書いたとは限らないので、一つ目の状況よりずっと慎重な対処が求められる。Dagoba はウェブで使われるので、どんなときでも結果を返して処理を止めないことがデフォルトのルールとなる。トラブルが起きたとき不気味なエラーメッセージを出して死ぬよりは、結果が意味をなさなくても通常の動作を続ける方が望ましいことが多い。

大量の結果を表示するぐらいなら結果が少なくなった方が望ましい場合は、Dagoba.error をオーバーライドして例外を送出するようにすれば自然な制御フローを断ち切るようにできる。

take

クエリの結果を全て一度に手に入れなくても構わない、あるいは少数の結果しか利用しない場合がある。そのような場合はパイプタイプ take が利用できる。例えば Thor と同年代の親戚を 12 人知りたいときは、豊穣の牛 Auðumbla まで遡る次のクエリが必要になる:

g.v('Thor').out().out().out().out().in().in().in().in().unique().take(12).run()

最後の take(12) を付けないと、クエリの実行に長い時間がかかることだろう。しかし遅延評価を採用したインタープリタのおかげで、take を付ければ実行時間は非常に短くなる。

結果が一つだけあれば十分なこともある: 一つの結果を使って処理を行い、それから次の結果の処理に移るようなパターンも take を使って実装できる:

q = g.v('Auðumbla').in().in().in().property('name').take(1)

q.run() // ['Odin']
q.run() // ['Vili']
q.run() // ['Vé']
q.run() // []

Dagoba のクエリは非同期環境でも動作するので、必要になったときに結果を計算する使い方ができる。上記のコードからも分かるように、結果が出尽くすと空の配列が返る。

パイプタイプ take の実装を示す:

Dagoba.addPipetype('take', function(graph, args, gremlin, state) {
  state.taken = state.taken || 0 // 状態の初期化

  if(state.taken == args[0]) {
    state.taken = 0
    return 'done'                // 動作終了
  }

  if(!gremlin) return 'pull'     // クエリの初期化
  state.taken++
  return gremlin
})

まず state.taken が存在しなければ 0 で初期化する。JavaScript は暗黙の型強制規則を持つものの、undefined を数値にすると NaN になるので、明示的な初期化が必要となる¹⁹。

その後 state.taken が args[0] に達すると 'done' が返り、自身より前のパイプがふさがれる。このとき state.taken のカウントをリセットし、クエリを何度も評価する場合の準備を整える。

これらの二つのステップがクエリの初期化より前に実行されるのは、take(0) と take() のケースに対応するためである²⁰。その後はカウンターを進め、グレムリンを返す。

as

これから紹介する四個のパイプタイプは協調して動作し、これまでより高度なクエリを可能にする。一つ目のパイプタイプ as は現在の頂点にラベルを付ける。このラベルは次の二つのパイプタイプで利用される。

Dagoba.addPipetype('as', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                 // クエリの初期化
  gremlin.state.as = gremlin.state.as || {}  // 状態の初期化
  gremlin.state.as[args[0]] = gremlin.vertex // 頂点にラベルを付ける
  return gremlin
})

クエリを初期化したら、グレムリンの状態に as プロパティが存在することを保証する。その後、存在が保証された gremlin.state.as の引数で指定された名前 arg[0] のプロパティにグレムリンが現在持っている頂点を設定する。

merge

ラベルが付いた頂点はパイプタイプ merge で取り出せる。例えば Thor の親、祖父母、曾祖父母を見つけたいときは次のようにする:

g.v('Thor').out().as('parent').out().as('grandparent').out().as('great-grandparent')
           .merge('parent', 'grandparent', 'great-grandparent').run()

パイプタイプ merge の実装を示す:

Dagoba.addPipetype('merge', function(graph, args, gremlin, state) {
  if(!state.vertices && !gremlin) return 'pull'   // クエリの初期化

  if(!state.vertices || !state.vertices.length) { // 状態の初期化
    var obj = (gremlin.state||{}).as || {}
    state.vertices = args.map(function(id) {return obj[id]}).filter(Boolean)
  }

  if(!state.vertices.length) return 'pull'        // 現在のバッチが終了
  var vertex = state.vertices.pop()
  return Dagoba.makeGremlin(vertex, gremlin.state)
})

この関数はグレムリンに記録された頂点のラベルを調べ、引数のいずれかをラベルに持つ頂点を state.vertices に記録する。このパイプタイプに到達したグレムリンだけがマージの対象となることに注意してほしい ── もし Thor の母親の両親がグラフに存在しなければ、Thor の母親はクエリの結果に含まれない。

except

filter を使えば「Thor の兄弟、ただし Thor 自身は除く」というクエリを書くことができる:

g.v('Thor').out().in().unique()
           .filter(function(asgardian) {return asgardian._id != 'Thor'}).run()

as と except を使うと、さらに理解しやすく書ける:

g.v('Thor').as('me').out().in().except('me').unique().run()

filter を使って書きにくいクエリも存在する。「Thor の伯父と叔母、ただし Thor の両親は除く」は filter を使って書けるだろうか？ as と except を使うと簡単に書ける²¹:

g.v('Thor').out().as('parent').out().in().except('parent').unique().run()

パイプタイプ except の実装を示す:

Dagoba.addPipetype('except', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull' // クエリの初期化
  if(gremlin.vertex == gremlin.state.as[args[0]]) return 'pull'
  return gremlin
})

この関数は引数に受け取ったラベルを持つ頂点をグレムリンの状態から読み取り、それが現在の頂点と同じかどうかを判定する。もし同じなら、その頂点はスキップする。

back

パイプタイプ back を使うと、「グラフを詳しく調べて初めて判定できる条件が成り立つ頂点を求める」タイプのクエリが書ける。例えば「Fjörgynn の娘で Bestla の息子との子供を持つ者は誰か？」という質問には、back を使った次のクエリで答えられる:

g.v('Fjörgynn').in()        // グレムリンの vertex は Fjörgynn の子
 .as('me')                  // 現在のグレムリンの vertex に 'me' というラベルを付ける
                            // ラベルはグレムリンの state に保存される
 .in()                      // グレムリンの vertex は Fjörgynn の孫となる
 .out().out()               // 現在のグレムリンをクローンしつつ曾祖母に移動する
 .filter({_id: 'Bestla'})   // 曾祖母が Bestla であるグレムリンだけを残す
 .back('me').unique().run() // グレムリンの頂点を 'me' のラベルを付けた頂点に戻して終了する

パイプタイプ back の定義を示す:

Dagoba.addPipetype('back', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull' // クエリの初期化
  return Dagoba.gotoVertex(gremlin, gremlin.state.as[args[0]])
})

実際の処理を行うのはヘルパー関数 Dagoba.gotoVertex である。この関数を含めて、今までに使ってきたヘルパー関数を続いて解説する。

ヘルパー関数

これまでに示してきたパイプタイプ関数ではいくつかのヘルパー関数が使われていた。インタープリタに取り掛かる前にそれらのヘルパー関数を簡単に見ておこう。

グレムリン

グレムリンは単純な小動物である: 処理中の「現在の頂点」と何らかの状態を保持する。そのため、新しいグレムリンの作成は二つのプロパティを持つオブジェクトを作るだけで済む:

Dagoba.makeGremlin = function(vertex, state) {
  return {vertex: vertex, state: state || {} }
}

この定義より、vertex プロパティと state プロパティを持つ任意のオブジェクトはグレムリンとみなされるので、この短いコンストラクタを呼び出し側にインライン展開することもできる。ただ、コンストラクタを関数にしておけばグレムリンに新しいプロパティを追加するときに必要な作業が一つの関数の編集だけとなる。

既存のグレムリンを別の頂点に移動させることもある。次の gotoVertex 関数はパイプタイプ back と関数 simpleTraversal で利用した:

Dagoba.gotoVertex = function(gremlin, vertex) {     // グレムリンをクローンする
  return Dagoba.makeGremlin(vertex, gremlin.state)
}

この関数が新しいグレムリンを返していることに注意してほしい: 引数に受け取ったグレムリンのクローンを新しい頂点に移動させている。このため現在のグレムリンを手元においたままクローンのグレムリンを他の頂点に送り出す処理が可能になる。これはまさに simpleTraversal が行う処理である。

可能な改善の一つとして、グレムリンに訪れた全ての頂点を記録する状態を追加し、それを利用する新しいパイプタイプを追加することが考えられる。

探索

パイプタイプ vertex は次に示す findVertices 関数を使ってクエリを始める初期頂点の集合を収集する:

Dagoba.G.findVertices = function(args) { // 頂点を見つけるヘルパー関数
  if(typeof args[0] == 'object')
    return this.searchVertices(args[0])
  else if(args.length == 0)
    return this.vertices.slice()         // 最適化: スライスは遅い
  else
    return this.findVerticesByIds(args)
}

findVertex は引数にリストを受け取る。その第一要素がオブジェクトなら searchVertices を呼ぶので、次のようなクエリが可能となる:

g.v({_id:'Thor'}).run()
g.v({species: 'Aesir'}).run()

引数のリストに要素が存在して第一要素がオブジェクトでないなら、引数は findVerticesByIds に渡される。この処理は g.v('Thor', 'Odin').run() といったクエリで利用される。

g.v().run() などのクエリでは、findVertices 関数に渡される引数のリストが空となる。こういったクエリは大きなグラフに対して実行すべきではない: 全ての頂点からなるリストのコピーが作成される。呼び出し側が pop メソッドなどを通して返り値を直接改変する可能性があるので、コピーは避けられない。返り値を改変するときはコピーしてから行うよう定めるか、そもそも改変を禁止すれば最適化が可能になる (後者の場合は pop メソッドを呼び出す代わりにカウンターを状態に保存することになる)。

findVerticesByIds 関数の実装を次に示す:

Dagoba.G.findVerticesByIds = function(ids) {
  if(ids.length == 1) {
    var maybe_vertex = this.findVertexById(ids[0]) // 頂点が見つからない可能性がある
    return maybe_vertex ? [maybe_vertex] : []
  }

  return ids.map( this.findVertexById.bind(this) ).filter(Boolean)
}

Dagoba.G.findVertexById = function(vertex_id) {
  return this.vertexIndex[vertex_id]
}

findVertexId 関数で vertexIndex を使っていることに注目してほしい。このインデックスが無ければ、頂点のリストを走査して引数の ID とマッチするかどうかを一つずつ判定しなければならない ── 定数時間で済む操作が線形時間となり、この関数を \(O(n)\) 回の呼び出す操作の実行時間は \(O(n^2)\) となってしまう。

searchVertices 関数の実装を次に示す:

Dagoba.G.searchVertices = function(filter) {     // filter が持つプロパティの値が
  return this.vertices.filter(function(vertex) { // 全て一致する頂点を返す
    return Dagoba.objectFilter(vertex, filter)
  })
}

この関数はグラフの全ての頂点に対してヘルパー関数 objectFilter を呼び出している。objectFilter の実装は次節で示すが、頂点を遅延評価で探索する方法を今の時点で考えられるだろうか？

フィルタ

以前に示した simpleTraversal 関数にはグラフの辺をフィルタリングする filterEdges 関数を利用していた。この関数は単純かつ強力であり、他の場所でも利用される:

Dagoba.filterEdges = function(filter) {
  return function(edge) {
    // フィルタが存在しない: 全て通す
    if(!filter)
      return true

    // フィルタが文字列: 文字列とラベルのマッチを判定
    if(typeof filter == 'string')
      return edge._label == filter

    // フィルタが配列: いずれか文字列とラベルのマッチを判定
    if(Array.isArray(filter))
      return !!~filter.indexOf(edge._label)

    // フィルタがオブジェクト: プロパティのマッチを判定
    return Dagoba.objectFilter(edge, filter)
  }
}

最初のケースではフィルタが存在しない: クエリ g.v('Odin').in().run() を実行すると Odin に向かう辺が全て走査される。

二番目のケースは辺のラベルを受け取る: クエリ g.v('Odin').in('parent').run() を実行すると 'parent' のラベルが付いた辺が走査される。

三番目のケースはラベルを要素とする配列を受け取る: クエリ g.v('Odin').in(['parent', 'spouse']).run() を実行すると、'parent' または 'spouse' のラベルの付いた辺が走査される。

四番目のケースでは以前にも登場した objectFilter 関数が利用される。実装を次に示す:

Dagoba.objectFilter = function(thing, filter) {
  for(var key in filter)
    if(thing[key] !== filter[key])
      return false

  return true
}

フィルタオブジェクトを使った辺のクエリは次のように行う:

// Odin の二番目の妻を見つける
g.v('Odin').in({_label: 'spouse', order: 2}).run()

インタープリタ

これで私たちはようやく解説の山の頂上にたどりつき、賞品を受け取る準備が整った: インタープリタである。コードは非常に短いものの、モデルは少し込み入っている。

本章ではパイプタイプ関数が一度に全ての頂点を生成するメンタルモデルを最初に示した。このメンタルモデルはクエリを書く上では有用であるものの、その後に見たように実装では異なるモデルが必要になる。そのモデルはパイプラインよりはチューリングマシンに近い: 「入出力ヘッド」が特定のステップを指し、そのステップを「読む」処理を行い、処理の結果に応じて「状態」を変更し、右か左に移動する。

ステップを「読む」とは、パイプタイプ関数を評価することを意味する。今までの例で見てきたように、パイプタイプ関数はグラフ、クエリへの引数、グレムリン、そしてステップの状態を引数に受け取る。出力はグレムリンまたは値 false, 'pull', 'done'のいずれかである。インタープリタが持つ「チューリングマシン」はパイプタイプ関数の出力を読み、その値に応じて状態を変更する。

このチューリングマシンの状態を表す変数は二つしかない: 一つは「完了」した最後 (最も右の) ステップを記録し、もう一つはクエリの結果を記録する。これらの変数を通して状態が更新されると、入出力ヘッドが移動するか、クエリが完了して結果が返る。

これでチューリングマシンの状態と動作が説明できたので、コードを見ていこう。まず結果を格納する変数 results が空配列で初期化される:

  var results = []

「完了」した最も右のステップを表す変数 done は、最初のステップの一つ左に初期化される:

  var done = -1

さらに、最後に実行したステップの出力を記録する変数が必要となる。ステップの出力はグレムリンまたは値 false, 'pull', 'done' のどれかなので、変数の名前は maybe_gremlin とする:

  var maybe_gremlin = false

そして最後に、入出力ヘッドの位置を表すプログラムカウンタが必要になる:

  var pc = this.program.length - 1

後はメインループを書くだけだ...ただちょっと待ってほしい。遅延評価²²はどうすれば実装できるだろうか？ 積極評価のシステムで遅延評価の仕組みを作る古典的な手法は、呼び出された関数と渡された引数を「サンク (thunk)」にまとめるというものである。サンクは未評価の関数呼び出しを表すと考えることができる。JavaScript はファーストクラスの関数とクロージャを持つので、関数と引数を新しい無名関数で包めば同じ処理を実装できる。作成される新しい無名関数は引数を取らない:

function sum() {
  return [].slice.call(arguments).reduce(function(acc, n) { return acc + (n|0) }, 0)
}

function thunk_of_sum_1_2_3() { return sum(1, 2, 3) }

function thunker(fun, args) {
  return function() {return fun.apply(fun, args)}
}

function thunk_wrapper(fun) {
  return function() {
    return thunker.apply(null, [fun].concat([[].slice.call(arguments)]))
  }
}

sum(1, 2, 3)              // -> 6
thunk_of_sum_1_2_3()      // -> 6
thunker(sum, [1, 2, 3])() // -> 6

var sum2 = thunk_wrapper(sum)
var thunk = sum2(1, 2, 3)
thunk()                   // -> 6

どのサンクも必要になるまで評価されていない。サンクが「必要」とは、その値が何らかの出力で使われることを意味する。Dagoba ではクエリの結果が出力となる。新しい関数呼び出しを見つけたインタープリタは、その呼び出しをサンクに包む。本章で最初に考えた形式のクエリ children(children(children(parents(parents(parents([8])))))) をこの仕組みで処理するとすれば、サンクの中に何重にもサンクが入れ子になったタマネギのようなサンクが作成される。

このアプローチにはいくつかトレードオフがある: まず、空間使用量の推定が困難になる。サンクを頂点とする複雑で巨大なグラフが構成される可能性があるためである。次に、プログラム全体が一つのサンクとして表されるので、通常の関数呼び出しを使って書いていれば可能だった操作の一部が不可能になる。

二つ目の問題は通常それほど深刻にならない。様々な最適化が実行されるコンパイル時とサンクが作成される実行時は分離されているためである。しかし、Dagoba では滑らかなインターフェースを実現するためにメソッドチェーン²³を利用しているので、遅延評価のためにサンクを使うと新しいメソッドが呼び出されるたびにサンクが作成されることになる。すると最後の run() への入力は全てサンクとなり、クエリの最適化が不可能になる。

興味深いことに、Dagoba の滑らかなインターフェースによって隠蔽されるクエリ言語と通常のプログラミング言語の違いがもう一つある。クエリ g.v('Thor').in().out().run() をメソッドチェーンを使わずに書けば run(out(in(v(g, 'Thor')))) となる。この呼び出しを処理するとき、JavaScript エンジンは最初に g と 'Thor' を評価し、その後 v, in, out, run と内側から外側に向かって評価する。積極評価でない意味論を持つ言語では外側から内側に向かって、必要になった引数と呼び出しだけが処理される。

このため、クエリの評価を最後の run から始めて最初の v('Thor') に向かって必要になった結果だけを計算しながら行えば、積極評価でない評価戦略が事実上実装できたことになる。ここでの秘密はクエリの線形性である: 条件分岐があるとプロセスグラフが複雑になる。また、呼び出しが重複する可能性も生まれ、再計算の無駄を省くにはメモ化が必要になる。Dagoba のクエリ言語が単純なおかげで、線形の入出力ヘッドのモデルを使った単純なインタープリタの実装が可能になっている。

実行時の最適化が可能になるのに加えて、このスタイルには計装が容易になるという利点もある: 履歴の表示、実行の反転、ステップごとのデバッグ、クエリの統計収集といった機能を動的に追加することは難しくない。これは、Dagoba がプログラムを単一のサンクにまとめるのではなく、クエリを評価する仮想機械であるインタープリタを直接制御しているためである。

インタープリタの正体

それでは、run メソッドのコードを見ていこう:

Dagoba.Q.run = function() {                 // 仮想機械を実行してクエリを評価する

  var max = this.program.length - 1         // プログラムの最後のステップのインデックス
  var maybe_gremlin = false                 // グレムリンまたは値 false, 'pull', 'done'
  var results = []                          // クエリの評価結果
  var done = -1                             // done より前のステップは完了済み
  var pc = max                              // 仮想機械のプログラムカウンタ

  var step, state, pipetype

  while(done < max) {
    var ts = this.state
    step = this.program[pc]                 // ステップはパイプタイプと引数の組
    state = (ts[pc] = ts[pc] || {})         // ステップの状態は必ずオブジェクト
    pipetype = Dagoba.getPipetype(step[0])  // パイプタイプは単なる関数

max は定数であり、step, state, pipetype が現在のステップに関する情報を保持する。変数を初期化したら仮想機械のメインループに入り、最後のステップが完了するまでループを続ける。

    maybe_gremlin = pipetype(this.graph, step[1], maybe_gremlin, state)

まず、ステップのパイプタイプ関数に引数を渡して呼び出す。

    if(maybe_gremlin == 'pull') { // 'pull' は新しい入力の要求を意味する
      maybe_gremlin = false
      if(pc-1 > done) {
        pc--                      // 一つ前のパイプに戻る
        continue
      } else {
        done = pc                 // 一つ前のパイプが完了しているなら、このパイプも完了
      }
    }

パイプタイプ関数の返り値が 'pull' の場合、まず maybe_gremlin を false に設定する²⁴。仮想機械へのシグナル 'pull' と 'done' はパイプタイプ関数に渡す maybe_gremlin の値としては不適当なので、シグナルの処理が終わったら maybe_gremlin には false が代入される。

一つ前のステップが完了²⁵していなければ、入出力ヘッドを後ろに進めて同じ処理を実行し、新しい入力の生成を試みる。一つ前のステップが完了しているなら、このステップにも完了の印を付けて入出力ヘッドを通常通り前に進める。

    if(maybe_gremlin == 'done') {           // 'done' は処理の完了を意味する
      maybe_gremlin = false
      done = pc
    }

パイプタイプ関数の返り値が 'done' の場合、処理はさらに簡単になる: maybe_gremlin を false にして、このステップに完了の印を付けるだけで済む。

    pc++                                    // 次のパイプに移動する

    if(pc > max) {
      if(maybe_gremlin)
        results.push(maybe_gremlin)         // パイプラインからグレムリンが出力された
      maybe_gremlin = false
      pc--                                  // 一つ前のパイプに戻る
    }
  }

これで現在のステップが処理できたので、続いて入出力ヘッドを次のパイプに移動させる。もし現在のステップがプログラムの最後のステップで maybe_gremlin がグレムリンなら、そのグレムリンはパイプラインが生成した結果なので results に加える。その後 maybe_gremlin を false に設定し、入出力ヘッドをプログラムの最後のステップに戻す。

pc の初期値は max なので、パイプラインが値を生成するとプログラムカウンタは初期状態にリセットされる言える。この後はパイプラインを逆向きに移動しながら処理が進み、クエリの結果一つごとに少なくとも一度は処理が最後のステップに戻る。

  results = results.map(function(gremlin) { // 収集された結果または頂点を返す
    return gremlin.result != null
         ? gremlin.result : gremlin.vertex } )

  return results
}

while ループを抜けた時点で仮想機械のメインループは終了している: クエリの評価が完了し、結果は results に収められている。最後に返り値を組み立てる処理がある。results に収められたグレムリンが持つ result プロパティまたは vertex プロパティを集めて返り値とする。これら以外の値を返したい状況は存在しないだろうか？ この設計のトレードオフは何だろうか？

クエリの変形

これでクエリプログラムのコンパクトなインタープリタが手に入ったものの、まだ足りないものがある。モダンな DBMS はシステムの最も重要な構成要素としてクエリオプティマイザを必ず備えている。非リレーショナルなデータベースではクエリの最適化によってリレーショナルデータベースで見られるような指数的な速度改善が得られることはまずない²⁶ものの、クエリの最適化がデータベース設計の重要な側面であることに変わりはない。

「クエリの最適化」と呼べる最も単純な処理は何だろうか？ 具体的には分からなくても、その処理はクエリを実行前に変形するはずである。つまり入力にプログラムを受け取り、それと異なるプログラムを出力する。この処理を行う関数を「トランスフォーマー」と呼ぶことにしよう。これからトランスフォーマーを管理するシステムを作成する。

まずは addTransformer 関数を実装する:

Dagoba.T = [] // トランスフォーマー (more than meets the eye)

Dagoba.addTransformer = function(fun, priority) {
  if(typeof fun != 'function')
    return Dagoba.error('トランスフォーマー関数が不正です')

  for(var i = 0; i < Dagoba.T.length; i++)  // 最適化: 二分探索
    if(priority > Dagoba.T[i].priority) break

  Dagoba.T.splice(i, 0, {priority: priority, fun: fun})
}

これでトランスフォーマーをシステムに追加できるようになった。トランスフォーマーはプログラムを受け取ってプログラムを返す関数と優先度 (priority) から構成される。優先度の高いトランスフォーマーはリストの前方に配置される²⁷。トランスフォーマーの関数は後に評価されるので、当然 JavaScript の関数である。

上記のコードではシステム全体で利用されるトランスフォーマーの個数がそれほど多くないことを仮定し、トランスフォーマーの挿入位置を線形探索で計算している。将来この仮定が破られるときに備えたコメントも残してある ── リストが長いときは二分探索を使うと探索を高速化できる。ただ、そうすると複雑性が増す上にリストが短いときは二分探索を使ってもたいして速くならない。

トランスフォーマーを実行するには、次の一行をインタープリタに追加するだけで済む:

Dagoba.Q.run = function() {                     // 仮想機械を実行してクエリを評価する
  this.program = Dagoba.transform(this.program) // トランスフォーマーを適用する

ここで呼び出される Dagoba.transform 関数は、登録されたトランスフォーマーを一つずつ順番に適用する:

Dagoba.transform = function(program) {
  return Dagoba.T.reduce(function(acc, transformer) {
    return transformer.fun(acc)
  }, program)
}

ここまでに書いてきた Dagoba のエンジンではパフォーマンスを犠牲にして単純性を取ってきた。この戦略が持つ利点の一つとして、後から大域的な最適化が行いやすいことがある。システムを設計するそばから局所的な最適化をしていると、後からシステムを大規模に変更することが難しくなりがちである。

プログラムを最適化するとシステムの複雑性が増し、分かりやすさが失われて理解・保守が難しくなることがよくある。パフォーマンスのために抽象化を破るのは最もひどい最適化の一つである。さらに、パフォーマンスが重要なコードをビジネスロジックに埋め込むといった一見すると無害に思える最適化でさえ保守のコストを増加させる。

そのため、Dagoba におけるトランスフォーマーのような「直交する最適化」は特に有用性が高い。最適化関数をエンジンと密結合させる必要はなく、そのコードは別のモジュール、あるいはユーザーコードの中にだって書くことができる。最適化関数は単一あるいはグループでテスト可能であり、自動生成テストの手法を用いればテストさえ自動化し、利用可能な最適化関数が互いに干渉せずに動作することを確認できるようになる。

トランスフォーマーの仕組みを使って最適化とは関係ない新しい機能を追加することもできる。次はこの例を見よう。

エイリアス

クエリ g.v('Thor').out().in() は非常にコンパクトに書けている。しかし、このクエリが表すのは Thor の兄弟だろうか、それとも Thor 夫婦だろうか？ どちらの解釈も全くの間違いとは言い切れない。関数の名前から意味が分かれば便利である: このクエリは g.v('Thor').parents().children() または g.v('Thor').children().parents() となる。

トランスフォーマーを使うと、いくつかのヘルパー関数を用意するだけでエイリアス (別名) の仕組みを実装できる:

Dagoba.addAlias = function(newname, oldname, defaults) {
  defaults = defaults || [] // エイリアスに対するデフォルト引数
  Dagoba.addTransformer(function(program) {
    return program.map(function(step) {
      if(step[0] != newname) return step
      return [oldname, Dagoba.extend(step[1], defaults)]
    })
    }, 100) // 優先度を高くして最初の方で実行させる

  Dagoba.addPipetype(newname, function() {})
}

既存のステップに新しい名前を付けるには、新しい名前を古い名前に変換するトランスフォーマーが必要になる。また、新しい名前をメインのクエリオブジェクトのメソッドとして追加し、クエリプログラムを組み立てるときに利用できるようにもしなければならない。

存在しないメソッド呼び出しを捕捉して他のオブジェクトに転送するヘルパー関数が存在するなら、このトランスフォーマーを低い優先度で実行することもできる。しかし、そういった関数は存在しない。そこで高い優先度 100 をトランスフォーマーに割り当て、エイリアスのメソッドが呼び出される前に追加されることを保証している。

上記のコードで使われる extend 関数は処理中のステップの引数とエイリアスのデフォルト引数を統合する関数である。もし処理中のステップが引数を持たないなら、エイリアスのデフォルト引数が設定される:

Dagoba.extend = function(list, defaults) {
  return Object.keys(defaults).reduce(function(acc, key) {
    if(typeof list[key] != 'undefined') return acc
    acc[key] = defaults[key]
    return acc
  }, list)
}

これで上述したエイリアスが定義できるようになった:

Dagoba.addAlias('parents', 'out')
Dagoba.addAlias('children', 'in')

子から親へ向かう辺と親から子へ向かう辺に 'parent' というラベルを付けて、データモデルをさらに特殊化することもできる。このとき addAlias 関数の呼び出しは次のようになるだろう:

Dagoba.addAlias('parents', 'out', ['parent'])
Dagoba.addAlias('children', 'in', ['parent'])

同様に配偶者、継親、振られた元恋人といった辺も追加できる。addAlias 関数を改良すれば、祖父母、兄弟、従兄弟に対するエイリアスも作成可能になるはずである:

Dagoba.addAlias('grandparents', [ ['out', 'parent'], ['out', 'parent']])
Dagoba.addAlias('siblings',     [ ['as', 'me'], ['out', 'parent']
                                , ['in', 'parent'], ['except', 'me']])
Dagoba.addAlias('cousins',      [ ['out', 'parent'], ['as', 'folks']
                                , ['out', 'parent'], ['in', 'parent']
                                , ['except', 'folks'], ['in', 'parent']
                                , ['unique']])

最後の cousins エイリアスはかなり複雑である。addAlias 関数をさらに拡張して、エイリアスの定義で他のエイリアスを使えるようにするべきかもしれない。そうすれば cousings を次のように作成できる:

Dagoba.addAlias('cousins',      [ 'parents', ['as', 'folks']
                                , 'parents', 'children'
                                , ['except', 'folks'], 'children', 'unique'])

このときクエリ g.v('Forseti').cousins() は次のクエリと同じになる:

g.v('Forseti').parents().as('parents').parents().children()
                        .except('parents').children().unique()

ただ、こういった機能を実装するには一つ問題がある: addAlias 関数はエイリアスを正しい順序で解決していかなればならない。もし cousins が parents を使うなら、parents は cousins より前に解決する必要がある。また、二つのエイリアスが (誤って) 互いに相手を参照する状況にも対処が必要となる。

これはモダンなパッケージマネージャが抱えるのと同じ問題であり、「依存関係の解決」と呼ばれる²⁸。理想的なバージョン選択やツリーシェイキングなどの一般的な最適化を行うための高度なテクニックが数多く知られているが、基本的なアイデアは非常に単純である。考えている対象の依存関係を表すグラフを作り、そのグラフの頂点を横一列に並べて全ての辺が左から右に向かうようできるかどうかを考える。もしできるなら、その頂点の並べ方を「トポロジカル順序 ('topological ordering)」と呼ぶ。トポロジカル順序が存在するとき、グラフは閉路を持たない有向非巡回グラフ (directed acyclic graph, DAG) となる。逆にトポロジカル順序が存在しない (条件を満たすように頂点を並べられない) なら、グラフは少なくとも一つの閉路を持つ。

一方で、Dagoba が処理する典型的なクエリはそれほど長くない。100 個のステップを持つクエリは非常に長い部類に入る。また、トランスフォーマーの個数も多くない。そのため「DAG を使った依存関係管理」のような難しいことを考えなくても、トランスフォーマーの関数に変化があったら true を返すように定めて、何か不都合が起きるまで実行を進めてしまえば問題は起こらないと考えられる。このときトランスフォーマーは冪等であることが求められるものの、これは自然な条件だと言える。二つのアプローチの利点と欠点は何だろうか？

パフォーマンス

製品レベルのグラフデータベースはどれも、パフォーマンスに関する次の特性を持つ: グラフ走査クエリをグラフ全体のサイズに関して定数時間で実行できる²⁹。通常のデータベースでは、誰かの友達のリストを取得する処理には全エントリーの個数に比例する時間がかかる: 最悪の場合には全てのエントリーを調べなければならないからである。これは、10 エントリーのデータベースに対して 1 ミリ秒で実行できるクエリは 1000 万エントリーのデータベースに対しては 2 週間近くかかることを意味する。友達のリストを紙に書いて Pony Express³⁰ で送った方が早く届く！

この絶望的なパフォーマンスを回避するために、ほとんどのデータベースは頻繁にクエリされるフィールドにインデックスを張ることで \(O(n)\) の検索時間を \(O(\log n)\) に落とす仕組みを備えている。インデックスの利用により検索時間は大きく改善されるものの、書き込み時のパフォーマンスは多少悪化し、データベースが使用する空間量は大きく上昇する ── インデックスのサイズがデータベースの二倍になることは珍しくない。空間量と検索時間のバランスが取れるように注意深くインデックスを調整することは、多くのデータベースで避けられないチューニング作業である。

グラフデータベースでは頂点と辺の間に直接的な結び付きが作成されるので、この問題は発生しない: グラフの走査はポインタをたどるだけで完了する。全エントリーのスキャンも、インデックスも、追加の処理も必要ない。友達のリストを取得するコストはグラフの大きさに関わらず一定であり、空間や書き込みコストが追加でかかることはない。ただ、グラフを使ったアプローチの欠点の一つとして、グラフ全体が一つのマシンのメモリに載るかどうかにパフォーマンスが大きく影響を受けることがある。グラフデータベースを複数のマシンに効率的にシャーディングする手法に関しては現在でも活発に研究が行われている³¹。

以上の理論的事実は Dagoba の小宇宙の中でも辺を見つける関数を入れ替えることで観察できる。全ての辺を調べるナイーブなバージョンの検索関数を次に示す。本章で最初に示した実装と非常に良く似ているものの、これまでに構築してきたシステムに収まるように書き直されている:

Dagoba.G.findInEdges  = function(vertex) {
  return this.edges.filter(function(edge) {return edge._in._id  == vertex._id} )
}
Dagoba.G.findOutEdges = function(vertex) {
  return this.edges.filter(function(edge) {return edge._out._id == vertex._id} )
}

辺に対するインデックスを追加したバージョンの検索関数を次に示す。小さなグラフでは問題ないかもしれないが、大きなグラフを扱えばインデックスに関する古典的な問題に直面するだろう:

Dagoba.G.findInEdges  = function(vertex) { return this.inEdgeIndex [vertex._id] }
Dagoba.G.findOutEdges = function(vertex) { return this.outEdgeIndex[vertex._id] }

Dagoba の本来の実装を次に示す。純粋で美しい index-free adjacency である:

Dagoba.G.findInEdges  = function(vertex) { return vertex._in  }
Dagoba.G.findOutEdges = function(vertex) { return vertex._out }

ここに示したコードを Dagoba に組み込んでクエリを実行し、グラフデータベースの本質的な違いを体験してみるとよい³²。

シリアライズ

グラフをメモリ上に構築できるのは素晴らしい。しかし、そのグラフはどのように構築するのだろうか？ 以前に示したグラフのコンストラクタ Dagoba.graph は頂点のリストと辺のリストを受け取ってグラフを作成する。構築済みのグラフから頂点と辺を取り出すにはどうすればいいだろうか？

JavaScript プログラマーとして自然な選択肢は JSON.stringify(graph) であるものの、これを実行すると TypeError: Converting circular structure to JSON という絶望的に分かりにくいエラーメッセージが表示される。グラフの構築で頂点は自身が属する全ての辺に関連付けられ、辺は自身が接続する二つの頂点に関連付けられる。そのため Dagoba のグラフオブジェクトには閉路がそこら中に存在する。どうすれば一列に並んだ素敵なリストを抽出できるだろうか？

JSON.stringify は文字列化する値の他に引数を二つ取る: 関数 replacer と空白文字である³³。replacer を使うと値を文字列にする処理をカスタマイズできる。

グラフオブジェクトを JSON に書き出すときは頂点と辺の扱いを少し変える必要がある。そのため、頂点のリストと辺のリストはそれぞれ手動で JSON 文字列に変換し、最後に一つの JSON にまとめる:

Dagoba.jsonify = function(graph) {
  return '{"V":' + JSON.stringify(graph.vertices, Dagoba.cleanVertex)
       + ',"E":' + JSON.stringify(graph.edges,    Dagoba.cleanEdge)
       + '}'
}

頂点のリストおよび辺のリストの変換で使う replacer は次の通りである:

Dagoba.cleanVertex = function(key, value) {
  return (key == '_in' || key == '_out') ? undefined : value
}

Dagoba.cleanEdge = function(key, value) {
  return (key == '_in' || key == '_out') ? value._id : value
}

二つの関数の違いは閉路を生み出す可能性がある部分の扱いだけである: 頂点では辺リストを完全にスキップし、辺では各頂点を ID で置き換える。こうればグラフの構築で発生する閉路を完全に除去できる。

Dagoba.jsonify は JSON を手動で操作するものの、JSON は非常にデリケートなフォーマットなので、これは一般に推奨されない。上記のような単純なコードでも、正確性を視覚的に確認しにくいコーナーケースを見逃す可能性が大いにある。

二つの replacer 関数を一つにまとめれば、グラフオブジェクト全体を JSON.stringify(graph, my_cool_replacer) で JSON 化できる。こうすれば手動で JSON を組み立てる必要はなくなるものの、コードは汚くなるかもしれない。実際に書いてみて、上手くリファクタリングできるかどうか試してみるとよい (1 ツイートに収まるならボーナスポイント)。

永続化

永続化はデータベースの中でも厄介な部分となることが多い: ディスクは比較的安全であるものの低速であり、書き込みのバッチ化・アトミック化やジャーナルの管理といった操作を高速かつ正確に実装するのは難しい。

幸い、私たちが作っているのはインメモリのデータベースなので、永続化は考える必要はない！ ただ、データベースをローカルに保存してページの読み込み時に素早くグラフを復元することはあるかもしれない。グラフの保存にはシリアライザをそのまま利用できる。まずヘルパー関数を用意する:

Dagoba.G.toString = function() { return Dagoba.jsonify(this) }

JavaScript ではオブジェクトを文字列に型強制するときオブジェクトの toString メソッドが呼び出される。上記の定義があれば、グラフオブジェクト g に対する g + '' はグラフを JSON 文字列にシリアライズした結果を返す。

fromString メソッドは言語仕様に含まれないものの、定義しておけば便利である:

Dagoba.fromString = function(str) { // もう一つのグラフコンストラクタ
  var obj = JSON.parse(str)         // 例外を送出する可能性あり
  return Dagoba.graph(obj.V, obj.E)
}

この二つの関数を使えば永続化関数が書ける。次のコードに toString 関数は含まれないものの、確かに使われている。どこで呼び出されるか分かるだろうか？

Dagoba.persist = function(graph, name) {
  name = name || 'graph'
  localStorage.setItem('DAGOBA::'+name, graph)
}

Dagoba.depersist = function (name) {
  name = 'DAGOBA::' + (name || 'graph')
  var flatgraph = localStorage.getItem(name)
  return Dagoba.fromString(flatgraph)
}

ドメインごとに用意される localStroage は Dagoba 以外のプログラムからも利用されるので、プロパティを汚染しないようにプロパティ名の先頭に DAGOBA:: を付けている。通常 localStroage の容量は小さいので、大きなグラフでは Blob などが必要になるだろう。

別の問題として、同じドメインのページを開く複数のブラウザウィンドウが同時にグラフの永続化関数を使う状況がある。そういったウィンドウは localStorage の空間を共有し、異なるイベントループを実行することもある。そのため注意しないと、あるウィンドウが書き込んだデータに別のウィンドウが上書きしてしまう状況が生まれる。localStorage への書き込み・読み込みアクセスにはミューテックスが必要だと仕様には書かれているものの、ブラウザ間の実装は一貫しておらず、Dagoba のような単純なプログラムでも問題が発生する可能性からは逃れられない。

複数ウィンドウによる並行処理をサポートする永続化を実装したいなら、localStorage が変更されたときに発火する storage イベントを利用すればローカルのグラフを適切に更新できる。

グラフの改変

パイプタイプ out は頂点の外向き辺のリストを自身の状態にコピーし、必要とされるたびに頂点を一つずつ出力する。新しいデータ構造を作成すると時間と空間が消費され、メモリマネージャに負荷がかかる。頂点が持つ外向き辺のリストを直接利用すれば、次に使う頂点のインデックスだけを管理するだけで済むように思える。このアプローチの問題点が分かるだろうか？

パイプタイプ out が以前に出力した頂点をクエリの途中でグラフから削除すると、out が注目している辺リストの長さが変化する。このときカウンターを使っていると、カウンターがずれて辺が一つ飛ばされてしまう。クエリに関係する頂点をロックすれば問題は解決されるものの、そうするとグラフをいつでも改変できる性質が失われるか、そうでなければリクエストが要求されたときに限ってオンデマンドに値を生成する長寿命のクエリオブジェクトが作成できなくなる。シングルスレッドのイベントループを実行しているだけだとしても非同期処理によって処理が途中で他のコードに移る可能性はあるので、並行処理の問題は現実の問題となる。

そのため、辺のリストのコピーで生じるパフォーマンスの低下はこういった問題を回避するためのコストと言える。ただし、こうすれば問題が完全に無くなるわけではない: グラフが改変されるとき、寿命の長いクエリが時系列的に一貫しない結果を返す可能性がある。特定の時刻に特定の頂点が持っていた辺が全て出力されることは確かでも、クエリ中に訪れる全ての頂点で辺のリストが同じ時刻に取得されるわけではない。例えば、クエリ var q = g.v('Odin').children().children().take(2) を q.run() で実行して Odin の孫の名前を二つ取得し、それから Ordin に孫が新しく二人できたとする。このとき、もう一度 q.run() を実行したときの結果は最初のクエリで訪れた頂点、そして新しい孫が誰の子かに依存して変化する。

この非決定性を修正する方法の一つとしてデータのバージョン付けが考えられる。その上でグラフの現在バージョンをクエリに渡すようにメインループを変更すれば、クエリは自身が初期化された時点でのグラフに対する結果を一貫して返せるようになる。Dagoba にバージョンの概念を追加すれば、真のトランザクションや STM 風の自動化されたロールバック/リトライへの扉も開かれる。

将来の方向性

曾祖父母までの先祖全員を取得するクエリを以前に示した:

g.v('Thor').out().as('parent')
           .out().as('grandparent')
           .out().as('great-grandparent')
           .merge(['parent', 'grandparent', 'great-grandparent'])
           .run()

とても不格好に思える。さらに、この書き方はスケールしない ── 六世代前までの先祖全員を取得したい場合はどうすれば？ あるいは、特定の条件を満たす先祖を見つけるまで家系図を遡るには？

次のようなクエリが書ければ便利である:

g.v('Thor').out().all().times(3).run()

クエリのトランスフォーマーを全て実行すると、このクエリは次のクエリと等価になる:

g.v('Thor').out().as('a')
           .out().as('b')
           .out().as('c')
           .merge(['a', 'b', 'c'])
           .run()

トランスフォーマーの動作の概要を示す。times がまず実行され、次のクエリへと変換される:

g.v('Thor').out().all().out().all().out().all().run()

その後 all が実行される。それぞれの all は一意に生成されたなラベルを持った as となり、最後の as の後ろに生成された全てのラベルに対する merge が追加される。

ただ、このアプローチには問題点もある。まず、このクエリは途中で途切れる路が存在しないことを仮定している。例えば Thor のある曾祖父母夫妻のエントリーがグラフに存在しないなら、その二人の子はクエリの結果に含まれない。次に、上記のクエリが大きなクエリの一部だったらどうなるだろうか？ もし all が複数あったら？

一つ目の問題を解決するには、all を as と merge に展開する以上の操作が必要になる。親のグレムリンがステップをスキップできるようしなければならない。グレムリンがテレポートする ── グレムリンがパイプラインの別の場所にワープする ── と考えてもよいし、パイプラインが分岐すると考えてもよい。いずれにせよモデルは現在より複雑になるだろう。別のアプローチとしてはグレムリンを「睡眠」状態にしてパイプラインを素通りさせ、特別なパイプで起こして使うという方法もある。ただ、パイプの停止・停止解除の実装は厄介だろう。

次の二つの問題は難しくない。クエリの一部分だけを改変するには、特別な start/end ステップで包めばよい。例えば g.v('Thor').out().start().in().out().end().times(4).run() などとなる。実を言えば、もしインタープリタが特別なパイプタイプがどれかを知っているなら end は必要ない: end の次には必ず特別なパイプタイプがある。こういった特別なパイプタイプを「副詞 (adverb)」と呼ぼう。副詞が動詞の意味を変えるのと同じように、副詞のパイプタイプは通常のパイプタイプの意味を変えるために存在する。

複数の all を扱うには、全ての all トランスフォーマーを二度実行しなければならない: 一度目の実行は times の前で、それぞれの all を一意なラベルを付ける。二度目の実行は times の後で、ラベルの付いた all に一意な別のラベルを追加し、そして適切な引数の付いた merge を追加する。

この機能があったとしても、先祖を限りなく遡りながら検索を行うクエリはまだ書けない ── 例えば、Ragnarök を生き残るとされている Ymir の子孫はどうすれば検索できるだろうか？ g.v('Ymir').in().filter({survives: true}) や g.v('Ymir').in().in().in().in().filter({survives: true}) といった個別のクエリを書いて手動で結果を収集することも不可能ではないものの、かなりお粗末である。

次のように使える副詞 every が望まれる:

g.v('Ymir').in().filter({survives: true}).every()

every は反復回数に上限が指定されない all(...).times(...) のように動作する。走査の戦略を指定可能にもできるだろう: 堅実な BFS と向こう見ずな DFS を用意すれば、g.v('Ymir').in().filter({survives: true}).bfs() といったクエリが可能になる。副詞 every があれば「Ymir から奇数世代だけ離れた Ragnarök の生存者を世代ごとに見せて」という複雑な要求にも g.v('Ymir').in().filter({survives: true}).in().bfs() という簡単なクエリで答えられる。

まとめ

本章で何を学んだだろうか？ 互いに何らかの関係で結び付いたデータ³⁴に対してグラフ走査を通じたクエリを行いたいとき、グラフデータベースは優れた選択肢である。積極評価でない意味論を実装すると、パフォーマンス上の理由で積極評価では不可能な滑らかなインターフェースが可能になり、非同期処理でも利用できるようになる。時間によって問題は複雑になり、並行処理が絡んで複数の時間が登場すると問題は非常に複雑になる。そのため時間的な依存関係 (状態や観測可能な影響など) を避けるとシステムの理解が容易になる。単純かつ疎結合なシステムを一切最適化されていなくても構わないので最初に作っておくと、後から行う大局的な最適化への扉を開けたままにできる。また、処理全体を制御する「メインループ」を用意すると直交する最適化を適用しやすくなる ── 多くの最適化テクニックにつきものである変更に弱いコードや複雑なコードを避けられる。

最後の点はどれだけ強調しても強調しすぎることはない: コードは単純に保つべきだ。単純性を犠牲にして最適化を取ることを避け、正しいモデルの選択によって単純性を達成することに注力しなければならない。そのためには様々な選択肢を検討する必要があるだろう。本書には全く自明でないアプリケーションが短くてタイトなカーネル (核) を持てることの証明がいくつも載っている。自分が作成しているアプリケーションのカーネルを見つかったなら、その後はカーネルを汚す複雑性と戦い続ける必要がある。追加機能用のフックを構築し、抽象化のバリアを何としてでも保持することが求められる。こういったテクニックは簡単に使いこなせるものではないものの、愚直に取り組むだけでは歯が立たない問題に挑戦する上で助けになることは間違いない。

謝辞

本章の執筆を大きく助けた Amy Brown, Michael DiBernardo, Colin Lupton, Scott Rostrup, Michael Russo, Erin Toliver, Leo Zovic に深く感謝する。