500行代码或更少
Dagoba：一个内存中的图数据库

Dann 喜欢构建事物，例如编程语言、数据库、分布式系统、聪明友善的人类社区，以及与他两岁的孩子一起建造的小马城堡。

序言

“当我们试图单独挑选任何事物时，我们会发现它被无数看不见的绳索紧紧地束缚着，这些绳索无法断开，与宇宙中的万物相连。”——约翰·缪尔

“走向世界尽头，并非为了穿越自身，上帝、太阳、莎士比亚、商业旅行者，在现实中穿越自身后，自身也变成了那个自身。”——詹姆斯·乔伊斯

很久以前，当世界还很年轻的时候，所有数据都快乐地排成一列行走。如果您想让您的数据跳过栅栏，您只需将栅栏放在它的路径上，然后每个数据依次跳过它。卡片输入，卡片输出。生活很简单，编程也很轻松。

然后，随机访问革命到来，数据在山坡上自由地漫游。管理数据变成了一个严重的问题：如果您可以在任何时间访问任何数据片段，您如何知道接下来要选择哪一个？开发了通过在项目之间形成链接¹来围捕数据的技术，通过它们的链接组合将单元组编组形成阵型。询问数据意味着选择一只羊并沿着与之连接的所有东西拉动。

后来的程序员背离了这一传统，对数据如何聚合强加了一套规则²。他们不是将不同的数据直接绑定在一起，而是按内容聚类，将数据分解成小块，收集在围栏中并用标签进行标记。问题被陈述性地提出，导致将部分分解的数据片段（关系型数据库人员称之为“规范”的状态）累积到一个法兰肯集合中，并将其返回给程序员。

在大部分有记录的历史中，这种关系模型占据着主导地位。它的统治地位在两次主要的语言战争和无数次冲突中都没有受到挑战。它提供了您在模型中可以要求的一切，只需付出低效、笨拙和缺乏可扩展性的少量代价。对于永恒，这是一个程序员愿意付出的代价。然后互联网出现了。

分布式革命再次改变了一切。数据摆脱了空间限制，并在机器之间漫游。掌握 CAP 的理论家打破了关系型垄断，为新的管理技术打开了大门——其中一些可以追溯到最早驯服随机访问数据的尝试。我们将研究其中之一，一种称为图数据库的风格。

第一步

在本章中，我们将构建一个图数据库³。在构建它的过程中，我们将探索问题空间，为我们的设计决策生成多种解决方案，比较这些解决方案以了解它们之间的权衡，并最终为我们的系统选择正确的解决方案。代码紧凑性优先级高于往常，但其他方面将与自古以来软件专业人员使用的过程相同。本章的目的是教授这个过程。并构建一个图数据库⁴。

使用图数据库将使我们能够以优雅的方式解决一些有趣的问题。图是一种非常自然的用于探索事物之间连接的数据结构。从这个意义上讲，图是一组顶点和一组边；换句话说，它是一堆由线连接的点。数据库？“数据库”就像一个数据堡垒。您将数据放入其中并从中获取数据。

那么，我们可以用图数据库解决哪些类型的问题呢？假设您喜欢跟踪家谱：父母、祖父母、远房表兄弟，诸如此类。您希望开发一个系统，允许您进行自然而优雅的查询，例如“谁是托尔的远房表兄弟？”或“弗雷娅与女武神有什么联系？”

此数据结构的合理模式是拥有一个实体表和一个关系表。对托尔父母的查询可能如下所示

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
}

上面函数的本质是遍历列表，为每个项目评估一些代码并构建结果累加器。不过，这还不够清晰，因为循环结构引入了一些不必要的复杂性。

如果有一种更具体的循环结构专为此目的而设计，那就太好了。碰巧的是，reduce 函数正是这样做的：给定一个列表和一个函数，它为列表的每个元素评估函数，同时将累加器贯穿每个评估过程。

以这种更函数式的风格编写，我们的查询更短更清晰

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 , [] )

给定一个顶点列表，我们减少边的数量，如果边的子节点在我们的输入列表中，则将边的父节点添加到累加器中。children 函数相同，但检查边的父节点以确定是否添加边的子节点。

这些函数是有效的 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 }, [] )}

现在我们可以说类似以下内容

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

它向后读取，让我们迷失在愚蠢的括号中，但在其他方面非常接近我们想要的东西。花点时间看看代码。您能看到任何改进方法吗？

我们将边作为全局变量处理，这意味着我们只能使用这些辅助函数一次构建一个数据库。这非常有限。

我们也根本没有使用顶点。这告诉我们什么？这意味着我们需要的一切都在 edges 数组中，在这种情况下是正确的：顶点值是标量，因此它们独立存在于 edges 数组中。如果我们想回答诸如“弗雷娅与女武神有什么联系？”之类的问题，我们需要向顶点添加更多数据，这意味着将它们设为复合值，这意味着 edges 数组应该引用顶点而不是复制它们的值。

对于我们的边也是如此：它们包含一个“入”顶点和一个“出”顶点⁵，但没有优雅的方式来合并其他信息。我们需要这些信息来回答诸如“洛基有多少继父母？”或“奥丁在托尔出生前有多少孩子？”之类的问题。

您无需费力就能看出我们两个选择器的代码非常相似，这表明它们可能来自一个更深层次的抽象。

您是否看到了其他问题？

构建一个更好的图

让我们解决我们发现的一些问题。将我们的顶点和边设为全局构造限制我们一次只能有一个图，但我们希望拥有更多。为了解决这个问题，我们需要一些结构。让我们从命名空间开始。

Dagoba = {}                                     // the namespace

我们将使用对象作为我们的命名空间。JavaScript 中的对象大多只是一组无序的键/值对。在 JavaScript 中，我们只有四种基本数据结构可以选择，因此我们将经常使用这种数据结构。（在派对上问人们一个有趣的问题是“JavaScript 中的四种基本数据结构是什么？”）

现在我们需要一些图。我们可以使用经典的 OOP 模式来构建这些图，但 JavaScript 为我们提供了原型继承，这意味着我们可以构建一个原型对象——我们将其称为Dagoba.G——然后使用工厂函数实例化该对象的副本。这种方法的一个优点是我们可以从工厂返回不同类型的对象，而不是将创建过程绑定到单个类构造函数。所以我们免费获得了一些额外的灵活性。

Dagoba.G = {}                                   // the prototype

Dagoba.graph = function(V, E) {                 // the factory
  var graph = Object.create( Dagoba.G )

  graph.edges       = []                        // fresh copies so they're not shared
  graph.vertices    = []
  graph.vertexIndex = {}                        // a lookup optimization

  graph.autoid = 1                              // an auto-incrementing ID counter

  if(Array.isArray(V)) graph.addVertices(V)     // arrays only, because you wouldn't
  if(Array.isArray(E)) graph.addEdges(E)        //   call this with singular V and E

  return graph
}

我们将接受两个可选参数：一个顶点列表和一个边列表。JavaScript 对参数相当宽松，因此所有命名参数都是可选的，如果未提供则默认为undefined⁶。我们通常会在构建图之前拥有顶点和边并使用 V 和 E 参数，但通常在创建时没有这些参数，而是以编程方式构建图⁷。

然后我们创建一个新对象，它拥有我们所有原型的力量，却没有它的弱点。我们为我们的边构建一个全新的数组（其他基本 JS 数据结构之一），为顶点构建另一个数组，一个名为vertexIndex的新对象和一个 ID 计数器——稍后将详细介绍这两个对象。（思考：为什么我们不能将它们直接放在原型中？）

然后我们在工厂内部调用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) {         // accepts a vertex-like object
  if(!vertex._id)
    vertex._id = this.autoid++
  else if(this.findVertexById(vertex._id))
    return Dagoba.error('A vertex with that ID already exists')

  this.vertices.push(vertex)
  this.vertexIndex[vertex._id] = vertex         // a fancy index thing
  vertex._out = []; vertex._in = []             // placeholders for edge pointers
  return vertex._id
}

如果顶点还没有_id属性，我们使用我们的 autoid 为其分配一个⁸。如果_id已经在我们的图中的顶点上存在，那么我们拒绝新顶点。等等，那什么时候会发生？顶点到底是什么？

在传统的面向对象系统中，我们期望找到一个顶点类，所有顶点都是该类的实例。我们将采取不同的方法，并将任何包含三个属性_id、_in和_out的对象视为顶点。这是为什么？归根结底，这归结于让 Dagoba 控制与主机应用程序共享哪些数据。

如果我们在addVertex函数内部创建一些Dagoba.Vertex实例，我们的内部数据将永远不会与主机应用程序共享。如果我们将Dagoba.Vertex实例作为参数传递给我们的addVertex函数，主机应用程序可能会保留指向该顶点对象的指针并在运行时对其进行操作，从而破坏我们的不变式。

因此，如果我们创建一个顶点实例对象，我们被迫提前决定是否始终将提供的数据复制到一个新对象中——这可能会使我们的空间使用量加倍——或者允许主机应用程序不受限制地访问数据库对象。这里存在性能和保护之间的张力，正确的平衡取决于您的特定用例。

顶点属性上的鸭子类型允许我们在运行时做出该决定，方法是深度复制⁹传入数据或将其直接用作顶点¹⁰。我们并不总是希望将平衡安全性和性能的责任交给用户，但由于这两组用例存在很大差异，因此额外的灵活性非常重要。

现在我们有了新的顶点，我们将把它添加到图的顶点列表中，添加到vertexIndex中以便通过_id高效查找，并为其添加两个额外的属性：_out和_in，它们都将成为边的列表¹¹。

Dagoba.G.addEdge = function(edge) {             // accepts an edge-like object
  edge._in  = this.findVertexById(edge._in)
  edge._out = this.findVertexById(edge._out)

  if(!(edge._in && edge._out))
    return Dagoba.error("That edge's " + (edge._in ? 'out' : 'in')
                                       + " vertex wasn't found")

  edge._out._out.push(edge)                     // edge's out vertex's out edges
  edge._in._in.push(edge)                       // vice versa

  this.edges.push(edge)
}

首先我们找到边连接的两个顶点，然后如果缺少任何一个顶点则拒绝该边。我们将使用一个辅助函数来记录拒绝时的错误。所有错误都通过此辅助函数传递，因此我们可以根据每个应用程序的基础来覆盖其行为。我们以后可以扩展此功能，允许注册onError处理程序，以便主机应用程序可以链接其自己的回调而无需覆盖辅助程序。我们可以允许根据所需的灵活性级别，为每个图、每个应用程序或两者都注册此类处理程序。

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

然后我们将新边添加到两个顶点的边列表中：边的输出顶点的输出边列表和输入顶点的输入边列表。

这就是我们现在需要的全部图结构！

输入查询

这个系统实际上只有两个部分：保存图的部分和回答有关图的问题的部分。保存图的部分非常简单，正如我们所看到的。查询部分稍微复杂一些。

我们将像以前一样开始，使用原型和查询工厂。

Dagoba.Q = {}

Dagoba.query = function(graph) {                // factory
  var query = Object.create( Dagoba.Q )

  query.   graph = graph                        // the graph itself
  query.   state = []                           // state for each step
  query. program = []                           // list of steps to take
  query.gremlins = []                           // gremlins for each step

  return query
}

现在是时候介绍一些朋友了。

一个程序是一系列步骤。每个步骤都像管道中的一个管道——数据从一端进入，以某种方式进行转换，然后从另一端出来。我们的管道并不完全按这种方式工作，但这是一个很好的第一近似值。

程序中的每个步骤都可以具有状态，而query.state是一个每步状态列表，其索引与query.program中步骤的列表相关联。

一个图灵是一种在图中穿梭执行我们指令的生物。在数据库中发现图灵可能是一件令人惊讶的事情，但它们可以追溯到Tinkerpop的Blueprints和Gremlin和Pacer查询语言。它们会记住去过哪里，并允许我们找到有趣问题的答案。

还记得我们想回答的关于雷神索尔的远房堂兄弟的问题吗？我们认为Thor.parents.parents.parents.children.children.children是一个表达它的好方法。每个parents或children实例都是我们程序中的一个步骤。这些步骤中的每一个都包含对其管道类型的引用，该管道类型是执行该步骤操作的函数。

在我们实际的系统中，该查询可能如下所示

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

每个步骤都是一个函数调用，因此它们可以接受参数。解释器将步骤的参数传递给步骤的管道类型函数，因此在查询g.v('Thor').out(2, 3)中，out管道类型函数将接收[2, 3]作为其第一个参数。

我们需要一种方法来向我们的查询添加步骤。这是一个用于此的辅助函数

Dagoba.Q.add = function(pipetype, args) { // add a new step to the query
  var step = [pipetype, args]
  this.program.push(step)                 // step is a pair of pipetype and its args
  return this
}

每个步骤都是一个复合实体，将管道类型函数与其要应用于该函数的参数组合在一起。我们可以在此阶段将两者组合成一个部分应用的函数，而不是使用元组¹²，但那样我们将失去一些以后会证明有用的自省能力。

我们将使用一小组查询初始化程序，这些初始化程序从图生成新的查询。这是一个启动我们大多数示例的初始化程序：v方法。它构建一个新的查询，然后使用我们的add辅助函数填充初始查询程序。这利用了vertex管道类型，我们很快就会看到它。

Dagoba.G.v = function() {                       // query initializer: g.v() -> query
  var query = Dagoba.query(this)
  query.add('vertex', [].slice.call(arguments)) // add a step to our program
  return query
}

请注意，[].slice.call(arguments)是JS的说法，意思是“请将此函数的参数数组传递给我”。你会被原谅认为arguments已经是一个数组，因为它在许多情况下表现得像一个数组，但它缺少我们在现代JavaScript数组中使用的许多功能。

急切的弊端

在我们查看管道类型本身之前，我们将绕道进入令人兴奋的执行策略世界。主要有两种思想流派：按值调用派别，也称为急切者，严格坚持在应用函数之前评估所有参数。他们对立的派别，按需调用者，则满足于拖延到最后一刻才做任何事情——他们，一言以蔽之，是懒惰的。

JavaScript 作为一门严格的语言，将在调用我们的每个步骤时处理它们。然后，我们期望g.v('Thor').out().in()的评估首先找到Thor顶点，然后找到通过传出边连接到它的所有顶点，最后从每个这些顶点返回它们通过传入边连接到的所有顶点。

在非严格语言中，我们将得到相同的结果——执行策略在这里没有太大区别。但如果我们添加了一些额外的调用呢？鉴于雷神索尔的关系网如此广泛，我们的g.v('Thor').out().out().out().in().in().in()查询可能会产生许多结果——事实上，因为我们没有将顶点列表限制为唯一的结果，它可能产生的结果比我们总图中的顶点数多得多。

我们可能只对获取一些唯一的结果感兴趣，因此我们将稍微更改查询：g.v('Thor').out().out().out().in().in().in().unique().take(10)。现在我们的查询最多产生10个结果。但是，如果我们急切地评估它会发生什么？在仅返回前10个结果之前，我们仍然需要构建无数的结果。

所有图数据库都必须支持一种机制来尽可能少地工作，并且大多数都选择某种形式的非严格评估来做到这一点。由于我们正在构建自己的解释器，因此程序的惰性求值是可能的，但我们可能不得不应对一些后果。

评估策略对我们思维模型的影响

到目前为止，我们对评估的思维模型非常简单

• 请求一组顶点
• 将返回的集合作为输入传递给管道
• 根据需要重复

我们希望为用户保留该模型，因为它更容易推理，但正如我们所看到的，我们不能再将该模型用于实现。让用户使用与实际实现不同的模型进行思考是痛苦的根源。泄漏的抽象就是这种情况的小规模版本；从大处着眼，它会导致沮丧、认知失调和愤怒退出。

不过，我们的案例几乎最适合这种欺骗：无论执行模型如何，任何查询的答案都将相同。唯一的区别是性能。权衡是在让所有用户在使用系统之前学习更复杂的模型，还是强迫一部分用户从简单模型迁移到复杂模型以更好地推理查询性能。

在处理此决策时需要考虑的一些因素是

• 学习简单模型与学习更复杂模型的相对认知难度；
• 首先使用简单模型然后升级到复杂模型所带来的额外认知负担与跳过简单模型而只学习复杂模型的额外认知负担；
• 需要进行转换的用户子集，就其比例大小、认知能力、可用时间等而言。

在我们的案例中，这种权衡是有意义的。对于大多数用途，查询将足够快地返回结果，因此用户不必担心优化其查询结构或学习更深层次的模型。那些需要优化的人是编写大型数据集上的高级查询的用户，他们也可能是最适合过渡到新模型的用户。此外，我们希望使用简单模型后再学习更复杂模型只会增加很少的难度。

我们很快将更详细地介绍这个新模型，但在此期间，请记住下一节中的一些要点

• 每个管道一次返回一个结果，而不是一组结果。在评估查询时，每个管道可能会被激活多次。
• 读/写头控制接下来激活哪个管道。头部从管道的末端开始，其移动方向由当前活动管道的结果决定。
• 该结果可能是上述图灵之一。每个图灵都代表一个潜在的查询结果，并且它们在管道中携带状态。图灵会导致头部向右移动。
• 管道可以返回'pull'的结果，这表示头部需要输入并将其向右移动。
• 'done'的结果告诉头部不再需要激活任何先前的内容，并将头部向左移动。

管道类型

管道类型构成了我们系统核心。一旦我们了解了每个管道类型的工作原理，我们将更好地理解它们如何在解释器中被调用和排序。

我们将首先创建一个放置管道类型的地方，以及一种添加新管道类型的方法。

Dagoba.Pipetypes = {}

Dagoba.addPipetype = function(name, fun) {              // adds a chainable method
  Dagoba.Pipetypes[name] = fun
  Dagoba.Q[name] = function() {
    return this.add(name, [].slice.apply(arguments)) }  // capture pipetype and args
}

管道类型的函数被添加到管道类型列表中，然后一个新方法被添加到查询对象中。每个管道类型都必须有一个相应的查询方法。该方法向查询程序添加一个新步骤及其参数。

当我们评估g.v('Thor').out('parent').in('parent')时，v调用返回一个查询对象，out调用添加一个新步骤并返回查询对象，而in调用也执行相同的操作。这就是使我们的方法链式API成为可能的原因。

请注意，使用相同名称添加新的管道类型会替换现有的管道类型，这允许运行时修改现有的管道类型。此决定的成本是多少？有哪些替代方案？

Dagoba.getPipetype = function(name) {
  var pipetype = Dagoba.Pipetypes[name]                 // a pipetype is a function

  if(!pipetype)
    Dagoba.error('Unrecognized pipetype: ' + name)

  return pipetype || Dagoba.fauxPipetype
}

如果我们找不到管道类型，我们将生成错误并返回默认管道类型，该类型充当空管道：如果消息从一侧进入，则将其从另一侧传出。

Dagoba.fauxPipetype = function(_, _, maybe_gremlin) {   // pass the result upstream
  return maybe_gremlin || 'pull'                        // or send a pull downstream
}

看到那些下划线了吗？我们用它们来标记在我们的函数中不会使用的参数。大多数其他管道类型将使用所有三个参数，并且具有所有三个参数名称。这使我们能够一目了然地区分特定管道类型依赖于哪些参数。

这种下划线技术也很重要，因为它使注释对齐得很好。不，说真的。如果程序"必须为人们阅读而编写，而仅偶然地为机器执行"，那么立即随之而来的是，我们最主要的关注点应该是使代码漂亮。

顶点

我们遇到的大多数管道类型都会接受一个图灵并产生更多的图灵，但这个特定的管道类型仅从字符串生成图灵。给定一个顶点ID，它会返回一个新的图灵。给定一个查询，它将找到所有匹配的顶点，并一次产生一个新的图灵，直到它处理完它们。

Dagoba.addPipetype('vertex', function(graph, args, gremlin, state) {
  if(!state.vertices)
    state.vertices = graph.findVertices(args)       // state initialization

  if(!state.vertices.length)                        // all done
    return 'done'

  var vertex = state.vertices.pop()                 // OPT: requires vertex cloning
  return Dagoba.makeGremlin(vertex, gremlin.state)  // gremlins from as/back queries
})

我们首先检查是否已经收集了匹配的顶点，否则我们将尝试找到一些顶点。如果有任何顶点，我们将弹出其中一个并返回一个位于该顶点上的新图灵。每个图灵都可以携带自己的状态，就像一个记录它去过哪里以及在穿越图的过程中看到了哪些有趣事物的日志。如果我们收到一个图灵作为此步骤的输入，我们将为退出的图灵复制其日志。

请注意，我们在这里直接修改状态参数，而不是将其传回。另一种方法是返回一个对象而不是图灵或信号，并通过这种方式传回状态。这使我们的返回值变得复杂，并产生了一些额外的垃圾¹³。如果JS允许多个返回值，这将使此选项更优雅。

尽管如此，我们仍然需要找到一种方法来处理这些变异，因为调用站点维护对原始变量的引用。如果我们有某种方法来确定特定的引用是否“唯一”——即它是该对象的唯一引用，会怎么样呢？

如果我们知道一个引用是唯一的，那么我们就可以获得不变性的好处，同时避免昂贵的写时复制方案或复杂的持久数据结构。只有一个引用时，我们无法分辨对象是否已被修改，或者是否已返回一个包含我们请求的更改的新对象：“观察到的不变性”得到维持¹⁴。

确定这一点有两种常见的方法：在静态类型系统中，我们可以利用唯一性类型¹⁵来保证在编译时每个对象只有一个引用。如果我们有一个引用计数器¹⁶——即使只是一个廉价的两位粘性计数器——我们可以在运行时知道一个对象只有一个引用，并利用该知识来获得优势。

JavaScript 没有这些功能，但如果我们真的非常自律，我们可以获得几乎相同的效果。我们会这样做的。目前。

进出

遍历图就像点汉堡一样简单。这两行代码为我们设置了in和out管道类型。

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

simpleTraversal函数返回一个管道类型处理器，它接受一个图灵机作为输入，并在每次被查询时产生一个新的图灵机。一旦这些图灵机消失，它就会发送一个“拉取”请求以从其前身获取一个新的图灵机。

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))     // query initialization
      return 'pull'

    if(!state.edges || !state.edges.length) {                 // state initialization
      state.gremlin = gremlin
      state.edges = graph[find_method](gremlin.vertex)        // get matching edges
                         .filter(Dagoba.filterEdges(args[0]))
    }

    if(!state.edges.length)                                   // nothing more to do
      return 'pull'

    var vertex = state.edges.pop()[edge_list]                 // use up an edge
    return Dagoba.gotoVertex(state.gremlin, vertex)
  }
}

前几行处理了in版本和out版本之间的差异。然后我们准备返回我们的管道类型函数，它看起来非常像我们刚刚看到的顶点管道类型。这有点令人惊讶，因为这个函数接受一个图灵机作为输入，而顶点管道类型则从无到有创建图灵机。

然而，我们可以看到这里使用了相同的节拍，并增加了一个查询初始化步骤。如果没有图灵机并且我们用完了可用边，那么我们就拉取。如果我们有一个图灵机但还没有设置状态，那么我们就找到任何朝适当方向延伸的边并将它们添加到我们的状态中。如果有一个图灵机，但其当前顶点没有合适的边，那么我们就拉取。最后，我们弹出一个边，并返回一个指向其所指顶点的全新克隆图灵机。

浏览这段代码，我们看到!state.edges.length在三个子句中都重复出现。我们很想重构它以降低这些条件语句的复杂性。有两个问题阻止我们这样做。

一个是相对次要的：第三个!state.edges.length的含义与前两个不同，因为在第二个和第三个条件语句之间state.edges已经发生了变化。这实际上鼓励我们进行重构，因为在一个函数内部同一个标签具有两种不同的含义通常不是理想的做法。

第二个问题更严重。这不是我们正在编写的唯一管道类型函数，并且我们会看到这些查询初始化和/或状态初始化的想法一遍又一遍地重复出现。在编写代码时，总是需要在结构化特性和非结构化特性之间进行权衡。结构太多，就会在样板代码和抽象复杂性方面付出高昂的代价。结构太少，就必须将所有管道细节都记在脑海中。

在这种情况下，对于十几个左右的管道类型来说，正确的选择似乎是尽可能相似地设计每个管道类型函数，并用注释标记组成部分。因此，我们抵制了重构这个特定管道类型的冲动，因为这样做会降低一致性，但我们也抵制了为查询初始化、状态初始化等设计正式结构化抽象的冲动。如果有数百个管道类型，那么后一种选择可能是正确的：抽象的复杂性成本是恒定的，而好处则随着单元数量的增加而线性增长。在处理如此多的活动部件时，任何可以用来加强它们之间规律性的方法都是有帮助的。

属性

让我们暂停片刻，考虑一下基于我们看到的三个管道类型的示例查询。我们可以这样询问索尔的祖父母¹⁷

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

但是如果我们想要他们的名字呢？我们可以在它后面加上一个映射

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

但这是一个非常常见的操作，我们更倾向于编写类似这样的内容

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

此外，通过这种方式，属性管道成为查询的组成部分，而不是附加在后面的内容。正如我们很快就会看到的，这有一些有趣的好处。

Dagoba.addPipetype('property', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  gremlin.result = gremlin.vertex[args[0]]
  return gremlin.result == null ? false : gremlin             // false for bad props
})

我们的查询初始化在这里非常简单：如果没有图灵机，我们就拉取。如果有图灵机，我们将把它的结果设置为属性的值。然后图灵机可以继续前进。如果它通过了最后一个管道，它的结果将被收集并从查询中返回。并非所有图灵机都有result属性。那些没有返回其最近访问的顶点的。

请注意，如果属性不存在，我们将返回false而不是图灵机，因此属性管道也充当一种过滤器。你能想到这种用途吗？这种设计决策的权衡是什么？

唯一

如果我们想收集索尔所有祖父母的孙辈——他的堂兄弟姐妹、兄弟姐妹和他自己——我们可以执行这样的查询：g.v('Thor').in().in().out().out().run()。但是，这会产生许多重复项。事实上，至少会有四份索尔本人的副本。（你能想到什么时候可能更多吗？）

为了解决这个问题，我们引入了一种名为“唯一”的新管道类型。我们的新查询产生的输出与孙辈一一对应

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

管道类型实现

Dagoba.addPipetype('unique', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  if(state[gremlin.vertex._id]) return 'pull'                 // reject repeats
  state[gremlin.vertex._id] = true
  return gremlin
})

唯一管道纯粹是一个过滤器：它要么不变地通过图灵机，要么尝试从前面的管道中拉取一个新的图灵机。

我们通过尝试收集一个图灵机来初始化。如果图灵机的当前顶点在我们的缓存中，那么我们之前就见过它，因此我们尝试收集一个新的。否则，我们将图灵机的当前顶点添加到我们的缓存中并将其传递。轻而易举。

过滤器

我们已经看到了两种简单的过滤方法，但有时我们需要更复杂的约束。如果我们想找到索尔的所有兄弟姐妹，他们的体重大于身高¹⁸会怎么样？这个查询会给我们答案

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

如果我们想知道索尔的哪些兄弟姐妹在诸神的黄昏中幸存下来，我们可以传递一个对象的过滤器

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

以下是它的工作原理

Dagoba.addPipetype('filter', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization

  if(typeof args[0] == 'object')                              // filter by object
    return Dagoba.objectFilter(gremlin.vertex, args[0])
         ? gremlin : 'pull'

  if(typeof args[0] != 'function') {
    Dagoba.error('Filter is not a function: ' + args[0])
    return gremlin                                            // keep things moving
  }

  if(!args[0](gremlin.vertex, gremlin)) return 'pull'         // gremlin fails filter
  return gremlin
})

如果过滤器的第一个参数不是对象或函数，那么我们将触发错误并传递图灵机。暂停一分钟，考虑一下替代方案。为什么当遇到错误时我们会决定继续查询？

这种错误可能有两个原因。第一个原因涉及程序员在 REPL 或代码中直接键入查询。运行该查询将产生结果，并生成程序员可观察到的错误。然后，程序员更正错误以进一步过滤产生的结果集。或者，系统可以只显示错误而不产生任何结果，并且修复所有错误将允许显示结果。

第二种可能是过滤器在运行时动态应用。这是一个更重要的案例，因为调用查询的人不一定是查询代码的作者。因为这在网络上，我们的默认规则是始终显示结果，并且永远不会破坏任何东西。在遇到麻烦时继续前进通常比屈服于我们的伤痛并向用户呈现可怕的错误消息要好。

对于那些显示过少结果比显示过多结果更好的场合，可以重写Dagoba.error以抛出错误，从而绕过自然控制流。

获取

我们并不总是希望一次获得所有结果。有时我们只需要少量结果；例如，我们想要十几位索尔的同龄人，因此我们一直追溯到原始母牛奥杜姆布拉

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

如果没有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.addPipetype('take', function(graph, args, gremlin, state) {
  state.taken = state.taken || 0                              // state initialization

  if(state.taken == args[0]) {
    state.taken = 0
    return 'done'                                             // all done
  }

  if(!gremlin) return 'pull'                                  // query initialization
  state.taken++
  return gremlin
})

如果state.taken不存在，我们将将其初始化为零。JavaScript 有隐式强制转换，但会将undefined强制转换为NaN，因此我们必须在这里明确说明¹⁹。

然后，当state.taken达到args[0]时，我们将返回“done”，在前面的管道之前将其封闭。我们还重置了state.taken计数器，以便以后可以重复查询。

我们在查询初始化之前执行这两个步骤，以处理take(0)和take()的情况²⁰。然后我们增加计数器并返回图灵机。

作为

接下来的四个管道类型作为一个组工作，以允许更高级的查询。这个管道类型只是允许你标记当前顶点。我们将使用该标签与接下来的两个管道类型。

Dagoba.addPipetype('as', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  gremlin.state.as = gremlin.state.as || {}                   // init the 'as' state
  gremlin.state.as[args[0]] = gremlin.vertex                  // set label to vertex
  return gremlin
})

在初始化查询后，我们确保图灵机的本地状态具有as参数。然后我们将该参数的一个属性设置为图灵机的当前顶点。

合并

一旦我们标记了顶点，我们就可以使用合并来提取它们。如果我们想要索尔的父母、祖父母和曾祖父母，我们可以执行以下操作

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

这是合并管道类型

Dagoba.addPipetype('merge', function(graph, args, gremlin, state) {
  if(!state.vertices && !gremlin) return 'pull'               // query initialization

  if(!state.vertices || !state.vertices.length) {             // state initialization
    var obj = (gremlin.state||{}).as || {}
    state.vertices = args.map(function(id) {return obj[id]}).filter(Boolean)
  }

  if(!state.vertices.length) return 'pull'                    // done with this batch

  var vertex = state.vertices.pop()
  return Dagoba.makeGremlin(vertex, gremlin.state)
})

我们遍历每个参数，在图灵机的已标记顶点列表中查找它。如果我们找到它，我们将图灵机克隆到该顶点。请注意，只有到达此管道的图灵机才会包含在合并中——如果索尔的母亲的父母不在图中，她将不会出现在结果集中。

除了

我们已经看到了一些我们想说“给我索尔的所有兄弟姐妹，但索尔除外”的情况。我们可以使用过滤器来做到这一点

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()

但也有一些难以尝试过滤的查询。如果我们想要索尔的叔叔和阿姨会怎么样？我们如何过滤掉他的父母？使用as和except很容易²¹

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

Dagoba.addPipetype('except', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  if(gremlin.vertex == gremlin.state.as[args[0]]) return 'pull'
  return gremlin
})

在这里，我们正在检查当前顶点是否等于我们之前存储的顶点。如果是，我们将跳过它。

返回

我们可能提出的一些问题涉及进一步检查图，如果答案是肯定的，则返回到我们的原点。假设我们想知道菲约尔根的哪些女儿与贝斯特拉的儿子之一有孩子？

g.v('Fjörgynn').in().as('me')       // first gremlin's state.as is Frigg
 .in()                              // first gremlin's vertex is now Baldr
 .out().out()                       // clone that gremlin for each grandparent
 .filter({_id: 'Bestla'})           // keep only the gremlin on grandparent Bestla
 .back('me').unique().run()         // jump gremlin's vertex back to Frigg and exit

这是back的定义

Dagoba.addPipetype('back', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  return Dagoba.gotoVertex(gremlin, gremlin.state.as[args[0]])
})

我们正在使用Dagoba.gotoVertex辅助函数来完成这里的所有实际工作。现在让我们看看它以及其他一些辅助函数。

辅助函数

上面的管道类型依赖于一些辅助函数来完成其工作。在深入研究解释器之前，让我们快速浏览一下这些辅助函数。

图灵机

图灵机是简单的生物：它们有一个当前顶点和一些本地状态。因此，要创建一个新的图灵机，我们只需要创建一个具有这两个属性的对象。

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

根据此定义，任何具有顶点属性和状态属性的对象都是图灵机，因此我们可以直接内联构造函数，但将其包装在一个函数中允许我们在一个地方为所有图灵机添加新属性。

我们还可以获取一个现有的图灵机并将其发送到一个新的顶点，就像我们在back管道类型和simpleTraversal函数中看到的那样。

Dagoba.gotoVertex = function(gremlin, vertex) {               // clone the gremlin
  return Dagoba.makeGremlin(vertex, gremlin.state)
}

请注意，此函数实际上返回了一个全新的 Gremlin：旧 Gremlin 的克隆，并将其发送到我们期望的目的地。这意味着一个 Gremlin 可以驻留在一个顶点上，同时它的克隆被发送出去探索许多其他顶点。这正是 simpleTraversal 中发生的事情。

作为可能的增强示例，我们可以添加一些状态来跟踪 Gremlin 访问的每个顶点，并添加新的管道类型来利用这些路径。

查找

vertex 管道类型使用 findVertices 函数从一组初始顶点收集数据，以开始我们的查询。

Dagoba.G.findVertices = function(args) {                      // vertex finder helper
  if(typeof args[0] == 'object')
    return this.searchVertices(args[0])
  else if(args.length == 0)
    return this.vertices.slice()                              // OPT: slice is costly
  else
    return this.findVerticesByIds(args)
}

此函数以列表的形式接收其参数。如果第一个参数是对象，则将其传递给 searchVertices，允许执行以下查询：

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

否则，如果有参数，则将其传递给 findVerticesByIds，后者处理诸如 g.v('Thor', 'Odin').run() 之类的查询。

如果没有参数，则我们的查询看起来像 g.v().run()。对于大型图，您不会经常执行此操作，尤其是在我们返回顶点列表之前对其进行切片的情况下。我们进行切片是因为某些调用站点通过弹出项目来直接操作返回的列表，并在处理这些项目时进行操作。我们可以通过在调用站点进行克隆或避免这些操作来优化这种情况。（我们可以保留一个状态计数器而不是弹出。）

Dagoba.G.findVerticesByIds = function(ids) {
  if(ids.length == 1) {
    var maybe_vertex = this.findVertexById(ids[0])            // maybe it's a vertex
    return maybe_vertex ? [maybe_vertex] : []                 // or maybe it isn't
  }

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

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

请注意此处 vertexIndex 的使用。如果没有该索引，我们将不得不逐一遍历列表中的每个顶点以确定它是否与 ID 匹配——将一个常数时间操作变成线性时间操作，并将任何直接依赖它的 \(O(n)\) 操作变成 \(O(n^2)\) 操作。

Dagoba.G.searchVertices = function(filter) {        // match on filter's properties
  return this.vertices.filter(function(vertex) {
    return Dagoba.objectFilter(vertex, filter)
  })
}

searchVertices 函数对图中的每个顶点使用 objectFilter 辅助函数。我们将在下一节中查看 objectFilter，但在此期间，您能否想到一种以惰性方式搜索顶点的方法？

过滤

我们看到 simpleTraversal 对其遇到的边使用过滤函数。这是一个简单的函数，但对于我们的目的来说足够强大。

Dagoba.filterEdges = function(filter) {
  return function(edge) {
    if(!filter)                                 // no filter: everything is valid
      return true

    if(typeof filter == 'string')               // string filter: label must match
      return edge._label == filter

    if(Array.isArray(filter))                   // array filter: must contain label
      return !!~filter.indexOf(edge._label)

    return Dagoba.objectFilter(edge, filter)    // object filter: check edge keys
  }
}

第一种情况是根本没有过滤器：g.v('Odin').in().run() 遍历到 Odin 的所有边。

第二种情况根据边的标签进行过滤：g.v('Odin').in('parent').run() 遍历标签为“parent”的边。

第三种情况接受标签数组：g.v('Odin').in(['parent', 'spouse']).run() 遍历父边和配偶边。

第四种情况使用我们之前看到的 objectFilter 函数

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

  return true
}

这允许我们使用过滤器对象查询边

`g.v('Odin').in({_label: 'spouse', order: 2}).run()`    // finds Odin's second wife

解释器的本质

我们已经到达叙事之山的顶峰，准备接受我们的奖品：解释器。代码实际上相当紧凑，但模型具有一定的微妙之处。

我们之前将程序比作管道，这是一个编写查询的好模型。但是，正如我们所看到的，我们需要一个不同的模型来进行实际的实现。该模型更像是图灵机而不是管道：有一个读写头位于特定步骤之上。它“读取”步骤，更改其“状态”，然后向右或向左移动。

读取步骤意味着评估管道类型函数。如上所述，这些函数中的每一个都将整个图、其自身参数、可能的一个 Gremlin 及其自身局部状态作为输入。作为输出，它提供一个 Gremlin、false 或“pull”或“done”的信号。此输出是我们准图灵机读取以更改机器状态的内容。

该状态仅包含两个变量：一个用于记录已“完成”的步骤，另一个用于记录查询的 results。这些变量会更新，然后机器头要么移动，要么查询结束并返回结果。

我们现在已经描述了机器中的所有状态。我们将有一个最初为空的结果列表

  var results = []

最后一个“完成”步骤的索引，该索引位于第一个步骤之后

  var done = -1

我们需要一个地方来存储最近一个步骤的输出，它可能是一个 Gremlin——也可能什么也没有——所以我们将其称为 maybe_gremlin

  var maybe_gremlin = false

最后，我们需要一个程序计数器来指示读写头的位置。

  var pc = this.program.length - 1

除了……等等。我们如何获得惰性 ²²？从渴望系统构建惰性系统的传统方法是将函数调用的参数存储为“thunk”，而不是对其进行评估。您可以将 thunk 视为一个未评估的表达式。在 JS 中，它具有头等函数和闭包，我们可以通过将函数及其参数包装在一个不带参数的新匿名函数中来创建 thunk

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

在实际需要之前，不会调用任何 thunk，这通常意味着需要某种类型的输出：在我们的例子中，是查询的结果。每次解释器遇到新的函数调用时，我们都会将其包装在一个 thunk 中。回想一下我们最初的查询公式：children(children(children(parents(parents(parents([8]))))))。每一层都将是一个 thunk，像洋葱一样包裹起来。

这种方法有几个权衡：一个是空间性能变得更难以推理，因为可能创建了庞大的 thunk 图。另一个是我们程序现在表示为单个 thunk，此时我们无法对其进行太多操作。

第二点通常不是问题，因为编译器运行其优化和所有 thunk 在运行时发生之间存在阶段分离。在我们的例子中，我们没有这种优势：因为我们正在使用方法链来实现流畅的界面 ²³ 如果我们也使用 thunk 来实现惰性，我们将为每次调用的新方法添加 thunk，这意味着当我们到达 run() 时，我们只有 thunk 作为输入，并且无法优化我们的查询。

有趣的是，我们的流畅界面隐藏了我们的查询语言和常规编程语言之间的另一个区别。查询 g.v('Thor').in().out().run() 可以重写为 run(out(in(v(g, 'Thor'))))，如果我们不使用方法链。在 JS 中，我们将首先处理 g 和 'Thor'，然后是 v，然后是 in、out 和 run，从内到外工作。在具有非严格语义的语言中，我们将从外到内工作，仅在需要时处理每个连续的嵌套参数层。

因此，如果我们从语句的末尾开始评估我们的查询，使用 run，然后逐步返回到 v('Thor')，仅在需要时计算结果，那么我们就有效地实现了非严格性。秘密在于我们查询的线性。分支使过程图复杂化，并且还引入了重复调用的机会，这需要记忆化来避免浪费工作。我们查询语言的简单性意味着我们可以基于我们线性的读写头模型实现一个同样简单的解释器。

除了允许运行时优化之外，这种风格在仪器易用性方面还有许多其他好处：历史记录、可逆性、逐步调试、查询统计信息。所有这些都易于动态添加，因为我们控制解释器并将其保留为虚拟机评估器，而不是将程序简化为单个 thunk。

解释器揭晓

Dagoba.Q.run = function() {                 // a machine for query processing

  var max = this.program.length - 1         // index of the last step in the program
  var maybe_gremlin = false                 // a gremlin, a signal string, or false
  var results = []                          // results for this particular run
  var done = -1                             // behindwhich things have finished
  var pc = max                              // our program counter

  var step, state, pipetype

  while(done < max) {
    var ts = this.state
    step = this.program[pc]                 // step is a pair of pipetype and args
    state = (ts[pc] = ts[pc] || {})         // this step's state must be an object
    pipetype = Dagoba.getPipetype(step[0])  // a pipetype is just a function

这里 max 只是一个常数，step、state 和 pipetype 缓存有关当前步骤的信息。我们已经进入了驱动循环，并且在我们完成最后一步之前不会停止。

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

使用其参数调用步骤的管道类型函数。

    if(maybe_gremlin == 'pull') {           // 'pull' means the pipe wants more input
      maybe_gremlin = false
      if(pc-1 > done) {
        pc--                                // try the previous pipe
        continue
      } else {
        done = pc                           // previous pipe is done, so we are too
      }
    }

为了处理“pull”情况，我们首先将 maybe_gremlin ²⁴ 设置为 false。我们在这里通过将其用作传递“pull”和“done”信号的通道来重载我们的“maybe”，但一旦其中一个信号被吸出，我们就回到将此视为一个适当的“maybe”。

如果我们前面的步骤尚未“完成” ²⁵，我们将向后移动头部并重试。否则，我们将自己标记为“完成”，并让头部自然向前落下。

    if(maybe_gremlin == 'done') {           // 'done' tells us the pipe is finished
      maybe_gremlin = false
      done = pc
    }

处理“done”情况甚至更容易：将 maybe_gremlin 设置为 false 并将此步骤标记为“done”。

    pc++                                    // move on to the next pipe

    if(pc > max) {
      if(maybe_gremlin)
        results.push(maybe_gremlin)         // a gremlin popped out of the pipeline
      maybe_gremlin = false
      pc--                                  // take a step back
    }
  }

我们完成了当前步骤，并将头部移动到下一个步骤。如果我们到达程序的末尾并且 maybe_gremlin 包含一个 Gremlin，我们将将其添加到结果中，将 maybe_gremlin 设置为 false 并将头部移回程序中的最后一步。

这也是初始化状态，因为 pc 从 max 开始。因此，我们从这里开始并逐步返回，并且至少为查询返回的每个最终结果在此处再次结束。

  results = results.map(function(gremlin) { // return projected results, or vertices
    return gremlin.result != null
         ? gremlin.result : gremlin.vertex } )

  return results
}

我们现在已经退出驱动循环：查询已结束，结果已保存，我们只需要处理并返回它们。如果任何 Gremlin 设置了其结果，我们将返回该结果，否则我们将返回 Gremlin 的最终顶点。我们可能还想返回其他内容吗？这里的权衡是什么？

查询转换器

现在我们为查询程序提供了一个很好的紧凑解释器，但我们仍然缺少一些东西。每个现代 DBMS 都将查询优化器作为系统的重要组成部分。对于非关系数据库，优化查询计划很少能像其关系数据库“表亲” ²⁶ 那样产生指数级的加速，但它仍然是数据库设计的重要方面。

我们可以做些什么最简单的事情可以合理地称为查询优化器？好吧，我们可以编写一些小函数来转换我们的查询程序，然后再运行它们。我们将把一个程序作为输入，并获得一个不同的程序作为输出。

Dagoba.T = []                               // transformers (more than meets the eye)

Dagoba.addTransformer = function(fun, priority) {
  if(typeof fun != 'function')
    return Dagoba.error('Invalid transformer function')

  for(var i = 0; i < Dagoba.T.length; i++)  // OPT: binary search
    if(priority > Dagoba.T[i].priority) break

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

现在我们可以将查询转换器添加到我们的系统中。查询转换器是一个函数，它接受一个程序并返回一个程序以及一个优先级级别。优先级较高的转换器放置在列表的前面。我们确保 fun 是一个函数，因为我们稍后将对其进行评估 ²⁷。

我们将假设转换器的添加数量不会过多，并线性遍历列表以添加新的转换器。如果这个假设被证明是错误的，我们将留下一个注释——二分查找对于长列表来说在时间上更有效，但会增加一点复杂性，并且不会真正加快短列表的速度。

为了运行这些转换器，我们将在解释器的顶部注入一行代码

Dagoba.Q.run = function() {                     // our virtual machine for querying
  this.program = Dagoba.transform(this.program) // activate the transformers

我们将使用它来调用此函数，该函数只是将我们的程序依次通过每个转换器

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

到目前为止，我们的引擎以简单性换取性能，但这种策略的一个好处是它为全局优化留下了空间，如果我们选择在设计系统时进行本地优化，这些优化可能不可用。

优化程序通常会增加复杂性并降低系统的优雅性，从而使其更难以推理和维护。为了提高性能而打破抽象屏障是最恶劣的优化形式之一，但即使是看似无害的事情，例如将面向性能的代码嵌入到业务逻辑中，也会使维护变得更加困难。

鉴于此，这种“正交优化”方式尤其吸引人。我们可以将优化器添加到模块甚至用户代码中，而不是将其与引擎紧密耦合。我们可以单独或成组地测试它们，并且通过添加生成式测试，我们甚至可以自动化此过程，确保我们可用的优化器能够很好地协同工作。

我们还可以使用这个转换器系统添加与优化无关的新功能。现在让我们来看一个这样的例子。

别名

发出像 g.v('Thor').out().in() 这样的查询非常简洁，但这是索尔的兄弟姐妹还是他的朋友？两种解释都不完全令人满意。最好明确说明我们的意思：要么是 g.v('Thor').parents().children()，要么是 g.v('Thor').children().parents()。

我们可以使用查询转换器，只需几个额外的辅助函数即可创建别名。

Dagoba.addAlias = function(newname, oldname, defaults) {
  defaults = defaults || []                     // default arguments for the alias
  Dagoba.addTransformer(function(program) {
    return program.map(function(step) {
      if(step[0] != newname) return step
      return [oldname, Dagoba.extend(step[1], defaults)]
    })
    }, 100)                                     // 100 because aliases run early

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

我们正在为现有步骤添加一个新名称，因此我们需要创建一个查询转换器，以便在遇到新名称时将其转换为旧名称。我们还需要在主查询对象上添加新名称作为方法，以便将其提取到查询程序中。

如果我们可以捕获缺失的方法调用并将它们路由到一个处理程序函数，那么我们或许能够以较低的优先级运行此转换器，但目前没有办法做到这一点。相反，我们将以 100 的高优先级运行它，以便在调用别名方法之前添加它们。

我们调用另一个辅助函数将传入步骤的参数与别名的默认参数合并。如果传入步骤缺少参数，我们将使用别名的参数填充该位置。

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”边来进一步细化我们的数据模型。然后我们的别名将如下所示

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 函数，允许我们在别名中使用其他别名，并像这样调用它

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

现在，我们不再需要

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

只需要说 g.v('Forseti').cousins() 即可。

不过，我们引入了一个小问题：当 addAlias 函数解析别名时，它也必须解析其他别名。如果 parents 调用了其他一些别名，而当我们正在解析 cousins 时，我们必须停止解析 parents，然后解析它的别名等等？如果 parents 的某个别名最终调用了 cousins 会怎么样？

这将我们带入了依赖项解析²⁸的领域，这是现代包管理器的核心组件。有很多巧妙的技巧可用于选择理想版本、树形抖动、通用优化等，但基本思想相当简单。我们将创建一个包含所有依赖项及其关系的图，然后尝试找到一种方法来排列顶点，同时使所有箭头都从左到右。如果我们能够做到这一点，那么顶点的这种特定排序称为“拓扑排序”，并且我们已经证明我们的依赖项图没有循环：它是一个有向无环图 (DAG)。如果我们未能做到这一点，那么我们的图至少包含一个循环。

另一方面，我们预计我们的查询通常会比较短（100 步将是一个非常长的查询），并且我们将拥有数量合理的转换器。与其处理 DAG 和依赖项管理，我们可以从转换函数中返回“true”（如果任何内容发生了更改），然后运行它直到它不再产生效果。这要求每个转换器都是幂等的，但对于转换器来说，这是一个有用的属性。这两种途径的优缺点是什么？

性能

所有生产图数据库都共享一个特定的性能特征：图遍历查询相对于总图大小而言是常数时间²⁹。在非图数据库中，请求某人的朋友列表可能需要与条目数量成正比的时间，因为在朴素的最坏情况下，您必须查看每个条目。这意味着如果对十个条目进行查询需要 1 毫秒，那么对一千万个条目进行查询将花费近两周时间。如果您的朋友列表由 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.G.findInEdges  = function(vertex) { return vertex._in  }
Dagoba.G.findOutEdges = function(vertex) { return vertex._out }

自己运行这些代码，体验图数据库的差异³²。

序列化

将图存储在内存中非常棒，但我们首先如何将其加载到内存中？我们看到我们的图构造函数可以接收顶点和边的列表并为我们创建一个图，但是一旦图构建完成，我们如何将顶点和边取出来？

我们的自然倾向是执行类似 JSON.stringify(graph) 的操作，这会产生非常有帮助的错误“TypeError: Converting circular structure to JSON”。在图构建过程中，顶点与它们的边链接，所有边都与它们的顶点链接，因此现在所有内容都相互引用。那么我们如何再次提取我们漂亮的整洁列表呢？JSON 替换函数来救援。

JSON.stringify 函数接收要进行字符串化的值，但它还接收两个附加参数：一个替换函数和一个空格数³³。替换器允许您自定义字符串化的过程。

我们需要以略有不同的方式处理顶点和边，因此我们将手动将两侧合并到单个 JSON 字符串中。

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

这些是顶点和边的替换器。

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 格式相当挑剔。即使剂量很小，也很容易错过某些东西，并且很难直观地确认正确性。

我们可以将两个替换函数合并到一个函数中，并通过执行 JSON.stringify(graph, my_cool_replacer) 在整个图上使用这个新的替换函数。这使我们无需手动处理 JSON 输出，但生成的代码可能会变得相当混乱。自己尝试一下，看看您是否能够想出一个良好分解的解决方案来避免手动编码 JSON。（如果它适合在推文中发布，则加分。）

持久化

持久化通常是数据库中最棘手的部分之一：磁盘相对安全但速度较慢。批量写入、使其原子化、日志记录——这些很难既快速又正确地实现。

幸运的是，我们正在构建一个内存中数据库，因此我们不必担心任何这些！不过，我们可能偶尔希望在本地保存数据库的副本，以便在页面加载时快速重新启动。我们可以使用我们刚刚构建的序列化程序来完成此操作。首先让我们将其包装在一个辅助函数中

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

在 JavaScript 中，每当将对象强制转换为字符串时，都会调用对象的 toString 函数。因此，如果 g 是一个图，则 g+'' 将是图的序列化 JSON 字符串。

fromString 函数不是语言规范的一部分，但它非常方便。

Dagoba.fromString = function(str) {             // another graph constructor
  var obj = JSON.parse(str)                     // this can throw
  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)
}

我们在名称前加上一个伪命名空间，以避免污染域的 localStorage 属性，因为那里可能会变得非常拥挤。通常还存在存储限制，因此对于较大的图，我们可能希望使用某种 Blob。

如果来自同一域的多个浏览器窗口同时进行持久化和反持久化，也可能存在问题。localStorage 空间在这些窗口之间共享，并且它们可能位于不同的事件循环上，因此可能存在一个窗口不小心覆盖另一个窗口工作的可能性。规范中规定应该有一个互斥锁来要求对 localStorage 进行读/写访问，但它在不同浏览器之间的实现不一致，即使有了它，像我们这样简单的实现仍然可能遇到问题。

如果我们希望我们的持久化实现能够感知多窗口并发，那么我们可以利用在更改 localStorage 时触发的存储事件来相应地更新我们的本地图。

更新

我们的 out 管道复制顶点的传出边，并在每次需要时弹出一个。构建新的数据结构需要时间和空间，并且会给内存管理器带来更多工作。我们本可以改为直接使用顶点的传出边列表，使用计数器变量跟踪我们的位置。你能想到这种方法有什么问题吗？

如果有人在我们在查询过程中访问了某条边时删除了它，这将改变我们的边列表的大小，并且由于我们的计数器不正确，我们将跳过一条边。为了解决这个问题，我们可以锁定查询中涉及的顶点，但这样一来，我们将要么失去定期更新图的能力，要么失去拥有长期存在的查询对象以按需响应更多结果请求的能力。即使我们在单线程事件循环中，我们的查询也可能跨多个异步重新进入，这意味着像这样的并发问题是一个非常现实的问题。

因此，我们将付出复制边列表的性能代价。不过，仍然存在一个问题，即长期存在的查询可能无法看到完全一致的时间顺序。我们将遍历我们在访问顶点时属于该顶点的每条边，但我们在查询期间以不同的时钟时间访问顶点。假设我们保存一个查询，例如 var q = g.v('Odin').children().children().take(2)，然后调用 q.run() 来收集奥丁的两个孙子。一段时间后，我们需要再提取两个孙子，因此我们再次调用 q.run()。如果奥丁在这段时间内又多了一个孙子，我们可能会看到它，也可能看不到它，具体取决于我们第一次运行查询时是否访问了父顶点。

解决这种不确定性的一种方法是更改更新处理程序，为数据添加版本控制。然后，我们将更改驱动程序循环，将图的当前版本传递给查询，这样我们始终可以看到查询首次初始化时世界的一致视图。为我们的数据库添加版本控制也为真正的交易以及以类似 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。

不过，这有一些问题。首先，这种 as/merge 技术仅在图中存在每条路径时才有效：如果我们缺少托尔曾祖父之一的条目，我们将跳过有效条目。其次，如果我们只想对查询的一部分而不是整个查询执行此操作会发生什么？如果有多个 all 呢？

为了解决第一个问题，我们将不得不将 all 视为不仅仅是 as/merge。我们需要每个父级 Gremlin 实际上跳过中间步骤。我们可以将其视为一种传送——从管道的一端直接跳到另一端——或者我们可以将其视为某种分支管道，但无论哪种方式，它都会使我们的模型变得有些复杂。另一种方法是将 Gremlin 视为以某种暂停动画的形式穿过中间管道，直到被一个特殊的管道唤醒。但是，确定暂停/取消暂停管道的范围可能很棘手。

接下来的两个问题更容易解决。要修改查询的一部分，我们将用特殊的开始/结束步骤将其包装起来，例如 g.v('Thor').out().start().in().out().end().times(4).run()。实际上，如果解释器知道这些特殊的管道类型，我们就不需要结束步骤，因为序列的末尾始终是特殊的管道类型。我们将这些特殊的管道类型称为“副词”，因为它们像副词修饰动词一样修饰常规管道类型。

为了处理多个 all，我们需要运行所有 all 转换器两次：一次在 times 之前，为所有 all 唯一标记，另一次在 times 之后，再次为所有已标记的 all 唯一标记。

仍然存在搜索无限数量的祖先的问题——例如，我们如何找出哪些伊米尔的子孙被安排在诸神黄昏中幸存下来？我们可以进行诸如 g.v('Ymir').in().filter({survives: true}) 和 g.v('Ymir').in().in().in().in().filter({survives: true}) 之类的单个查询，并手动收集结果，但这非常糟糕。

我们希望使用这样的副词

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

它将像 all+times 一样工作，但不会强制限制。不过，我们可能希望对遍历强加特定的策略，例如稳固的 BFS 或 YOLO DFS，因此 g.v('Ymir').in().filter({survives: true}).bfs() 将更灵活。以这种方式表达它使我们能够以简单的方式陈述复杂的查询，例如“检查诸神黄昏幸存者，跳过每一代”：g.v('Ymir').in().filter({survives: true}).in().bfs()。

总结

所以我们学到了什么？图数据库非常适合存储您计划通过图遍历查询的互连³⁴数据。添加非严格语义允许在您出于性能原因无法在急切系统中表达的查询上使用流畅的接口，并允许您跨异步边界。时间使事情变得复杂，来自多个视角的时间（即并发）使事情变得非常复杂，因此，每当我们可以避免引入时间依赖性（例如，状态、可观察效应等）时，我们就会使对系统的推理变得更容易。以简单、解耦和痛苦的未优化风格构建为以后的全局优化打开了大门，并且使用驱动程序循环允许正交优化——每个优化都不会引入大多数优化技术标志性的脆弱性和复杂性。

最后一点不能过分强调：保持简单。为了简单起见，避免优化。通过找到正确的模型来努力实现简单。探索多种可能性。本书中的章节充分证明了高度非平凡的应用程序可以具有一个小型、紧凑的内核。一旦您为正在构建的应用程序找到了该内核，就要努力防止复杂性污染它。构建挂钩以附加其他功能，并始终维护您的抽象屏障。熟练地使用这些技术并不容易，但它们可以为您提供应对原本棘手问题的杠杆作用。

致谢

非常感谢 Amy Brown、Michael DiBernardo、Colin Lupton、Scott Rostrup、Michael Russo、Erin Toliver 和 Leo Zovic 对本章做出的宝贵贡献。