图计算介绍

tinkerpop3

赵亮
weston_contribute@163.com

1. 开始

<dependency>
  <groupId>org.apache.tinkerpop</groupId>
  <artifactId>gremlin-core</artifactId>
  <version>3.2.1</version>
</dependency>

图是由点和边组成的数据结构。当在计算机中构建一个图并应用于现代数据集和实践时，以计算为导向的二元图支持标签和key/value键值对。这种结构称为属性图。或更正式的成为一个有方向的，二元的，多属性的图。属性图的例子如果下图所示。

Tinkerpop3 是tinkerpop图计算框架的第三代化身。跟一般计算相似，图计算在结构（图）和处理（遍历）做了区分。图的结构是由点、边和属性定义的数据模型。图数据的处理是基于图结构进行分析。图处理的典型方式称为遍历。

TinkerPop3 结构API的基础组件

• Graph：维护点和边的集合，数据库访问如事务。
• Element：维护属性和标签（表示元素的类型）的集合。
  
  • Vertex：继承Element，并维护入边和出边集合。
  • Edge：继承Element，并维护入点和出点集合。
• Property<V>：字符串key关联V
  
  • VertexProperty<V>：字符串key关联V，并且V也可以是Property<U>的集合。

TinkerPop3 处理API的基础组件

• TraversalSource：遍历的生产者，domain specific language (DSL)，执行引擎。
  
  • Traversal<S,E>：数据流处理的功能，将类型为S对象转化为对象为类型为E对象。
    
    • GraphTraversal：遍历的DSL，是面向语义的原始图。
• GraphComputer：在多机器集群并行处理图的系统。
  
  • VertexProgram：通过消息传递进行通信，用逻辑并行的方式在所有点上执行的代码。
  • MapReduce：并行的分析图中所有的点，对结果进行归约的计算。

当一个图系统实现的TinkerPop3 的结构和处理API，则该系统是支持TinkerPop3的并且跟其他支持TinkerPop3的图系统在时间复杂度和空间复杂度是没有区别的。此文档对图结构和处理一分为二的进行讲解。

2. 图结构

图结构是一种拓扑结构，通过点、边和属性之前明晰的引用来表示。

Graph graph = TinkerGraph.open(); (1)
Vertex marko = graph.addVertex(T.label, "person", T.id, 1, "name", "marko", "age", 29); (2)
Vertex vadas = graph.addVertex(T.label, "person", T.id, 2, "name", "vadas", "age", 27);
Vertex lop = graph.addVertex(T.label, "software", T.id, 3, "name", "lop", "lang", "java");
Vertex josh = graph.addVertex(T.label, "person", T.id, 4, "name", "josh", "age", 32);
Vertex ripple = graph.addVertex(T.label, "software", T.id, 5, "name", "ripple", "lang", "java");
Vertex peter = graph.addVertex(T.label, "person", T.id, 6, "name", "peter", "age", 35);
marko.addEdge("knows", vadas, T.id, 7, "weight", 0.5f); (3)
marko.addEdge("knows", josh, T.id, 8, "weight", 1.0f);
marko.addEdge("created", lop, T.id, 9, "weight", 0.4f);
josh.addEdge("created", ripple, T.id, 10, "weight", 1.0f);
josh.addEdge("created", lop, T.id, 11, "weight", 0.4f);
peter.addEdge("created", lop, T.id, 12, "weight", 0.2f);

2.1 修改图

3. 图处理

处理图的基本方式是通过图遍历。TinkerPop3的图处理API允许用户通过语义友好的方式创建能在图结构上进行遍历。例如：“点1的朋友参与哪些软件开发？”，此语句可以通过以下遍历步骤表达：
1. 从点1开始。
2. 出边为knows的所对应的点。
3. 从朋友节点出发，经过created边到达软件节点。
4. 返回这些软件节点的name属性。

遍历（Traversals）是由TraversalSource大量产生。GraphTraversalSource是一个典型的“图导向的”DSL。它提供两种遍历方法：
1. GraphTraversalSource.V(Object... ids)：产生从图中的点（如果ids没有提供，则所有的点）开始的遍历。
2. GraphTraversalSource.E(Object... ids)：产生从图中的边（如果ids没有提供，则所有的边）开始的遍历。

V()和E()的返回类型就是GraphTraversal。GraphTraversal维持许多返回GraphTraversal的方法。通过这种方式，GraphTraversal就能支持功能组合。GraphTraversal中每个方法称为步骤（step），每个步骤调整之前的步骤（五个通用步骤的一种）中的结构。

1. map：将进来的遍历对象转化为另一个对象（S → E）。
2. flatMap：将进来的遍历对象转化为另一些对象的迭代器。（S → E*）。
3. filter：允许或不允许一些遍历者参与下一个步骤。（S → S ∪ ∅）。
4. sideEffect：
5. branch：

3.1 遍历器

当执行一个遍历时，遍历源是为表达式的左边，遍历的中间部分（例如：out('knows'和values('name')）是步骤。遍历右边（traversal.next()'d）的是结果（例如："vadas" 和 "josh"）。

在TinkerPop3中，在遍历过程中传播的对象是由Traverser<T>包装的。遍历器在TinkerPop3中是一个新的概念并且提供的方法步骤是无状态的。遍历器维护所有关于遍历的元数据，例如：一个遍历穿越一个循环多少次，遍历器的历史路径，正在被遍历的当前对象等等。可以通过一个步骤来访问遍历器的元数据，一个典型的例子就是path()步骤。

gremlin> g.V(marko).out('knows').values('name').path()
==>[v[1], v[2], vadas]
==>[v[1], v[4], josh]

注意：
Path calculation is costly in terms of space as an array of previously seen objects is stored in each path of the respective traverser. Thus, a traversal strategy analyzes the traversal to determine if path metadata is required. If not, then path calculations are turned off.

另一个例子就是：repeat()步骤，考虑遍历器通过遍历表达式的某特殊部分的穿越次数。

gremlin> g.V(marko).repeat(out()).times(2).values('name')
==>ripple
==>lop

注意：
A Traversal’s result are never ordered unless explicitly by means of order()-step. Thus, never rely on the iteration order between TinkerPop3 releases and even within a release (as traversal optimizations may alter the flow).

4. Gremlin语言的变体

Gremlin 是用java 8编写的。有多种Gremlin的变体如Gremlin-Groovy、Gremlin-Scala、 Gremlin-JavaScript、Gremlin-Clojure（又被称为Ogre），最好将Gremlin看作为不绑定某种特定编程语言的一种图遍历方式。对于开发者，Gremlin变体和编程语言一样，能充分利用语言的风格。实现Gremlin的编程语言至少必须支持函数链（如果gremlin变体希望提供除了已经提供的步骤以外更为灵活的步骤，那么最好支持lambdas/Anonymous function）。
在整个文档中，提供的示例都是用gremlin-groovy写的。因为这种交互编程环境不需要代码编译。如果开发者对Gremlin-java有兴趣，有一些Groovy-to-Java模式，呈现如下：

g.V().out('knows').values('name') (1)
g.V().out('knows').map{it.get().value('name') + ' is the friend name'} (2)
g.V().out('knows').sideEffect(System.out.&println) (3)
g.V().as('person').out('knows').as('friend').select().by{it.value('name').length()} (4)

g.V().out("knows").values("name") (1)
g.V().out("knows").map(t -> t.get().value("name") + " is the friend name") (2)
g.V().out("knows").sideEffect(System.out::println) (3)
g.V().as("person").out("knows").as("friend").select().by((Function<Vertex, Integer>) v -> v.<String>value("name").length())

1. All the non-lambda step chaining is identical in Gremlin-Groovy and Gremlin-Java. However, note that Groovy supports ' strings as well as " strings.
2. In Groovy, lambdas are called closures and have a different syntax, where Groovy supports the it keyword and Java doesn’t with all parameters requiring naming.
3. The syntax for method references differs slightly between Java and Gremlin-Groovy.
4. Groovy is lenient on object typing and Java is not. When the parameter type of the lambda is not known, typecasting is required.

5. 图系统结构

TinkerPop 是由多个可共同操作的组件组成的架构。 core TinkerPop3 API是整个架构的基础，它定义了什么是点、边和属性。一个图系统至少要实现 core API。一旦实现，就可在系统中是有gremlin遍历语言。然而图系统的提供者还可以特定的TraversalStrategy优化策略，允许系统在执行Gremlin查询时对其进行优化（例如索引查询，步骤重排序）。如果使图系统具有处理功能（OLAP），则需要实现GraphComputer API，它定义了消息或遍历器是如何在工作者（线程或机器）之间进行交互和传递的。一旦实现，Gremlin遍历可以在图数据库（OLTP）和图处理器（OLAP）上执行。注意，Gremlin语言是基于图的领域特定语言，根据点和边来解释图。用户也可以创建自己的领域特定语言。最后，采用Gremlin Server使用用户连接支持Tinkerpop的图系统，Gremlin Server 提供了可配置的交互接口和度量。这就是Tinkerpop。