Flink gelly 转

What is Gelly?

image.png

Neighborhood Aggregations(邻居聚合)

image.png

image.png

Iterative Graph Processing

Vertex-centric

MessagingFunction: 给下一个超步发送的消息。

VertexUpdateFunction:定义一个节点对收到的消息如何去处理

image.png

operator收到两个输入：

the Solution Set： 当前输入的状态

the Workset, 图的一部分在下次迭代中会被重新计算

Vertex Centric迭代计算

image.png

image.png

Vertex Centric模型，也称为”像顶点一样思考”或”Pregel”，通过图顶点的角度表达计算。 该计算在迭代的每一步（称为超步）中同步地处理，在每个超步时，每个顶点执行一个UDF（User Defined Function）。 顶点之间通过消息进行通讯，任何一个顶点可以给图中任何其他的顶点发送消息，只要知道它的ID即可。

下面的图中展示该计算模型，虚线框和并行单元对应。在每个超步中，所有的活跃顶点并行执行相同的用户定义的计算。因为超步时同步执行的，因此每次超步中发送的消息都被保证发送了到下次超步的开始。

image.png

在Gelly中使用Vertex Centric迭代，用户只需要定义顶点的计算函数ComputeFunction即可。

该函数和最大迭代次数通过Gelly的runVertexCentricIteration函数参数指定。该方法在输入图上执行Vertex Centric迭代计算，并输出更新后顶点值的新图。可选的MessageCombiner函数可以被用于减少通信消耗。

让我们考虑基于Vertex Centric的单源点最短路径算法（SSSP）。算法开始时，除了源顶点初始值为0，每个顶点初始值为正无穷。第一次超步计算时，源顶点将距离传播给它的邻居。在接下来的超步中，每个顶点检查接收的消息并选择其中最小的距离值。如果该距离值比顶点当前值小，则更新顶点的值，并产生消息发送给其邻居。如果顶点在超步中没有更新它的值，则在下次超步时不会发送任何消息给它的邻居。当没有顶点的值发生更新或者达到了最大的超步迭代次数，算法将会收敛。在这个算法中，Message Combiner可以被用来减少发送给目标顶点的消息个数。

// 构建图Graph graph = ...// 最大迭代次数intmaxIterations =10;// 执行vertex-centric iterationGraph result = graph.runVertexCentricIteration(newSSSPComputeFunction(),newSSSPCombiner(), maxIterations);// 抽取结果DataSet> singleSourceShortestPaths = result.getVertices();//用户定义函数publicstaticfinalclassSSSPComputeFunctionextendsComputeFunction{publicvoidcompute(Vertex<Long, Double> vertex, MessageIterator<Double> messages){doubleminDistance = (vertex.getId().equals(srcId)) ?0d : Double.POSITIVE_INFINITY;for(Double msg : messages) {        minDistance = Math.min(minDistance, msg);    }if(minDistance < vertex.getValue()) {        setNewVertexValue(minDistance);for(Edge e: getEdges()) {            sendMessageTo(e.getTarget(), minDistance + e.getValue());        }    }}// 消息合并publicstaticfinalclassSSSPCombinerextendsMessageCombiner{publicvoidcombineMessages(MessageIterator<Double> messages){doubleminMessage = Double.POSITIVE_INFINITY;for(Double msg: messages) {          minMessage = Math.min(minMessage, msg);        }        sendCombinedMessage(minMessage);    }}

参考：

http://flink.iteblog.com/dev/libs/gelly/iterative_graph_processing.html#vertex-centric-1

作者：丹之

链接：https://www.jianshu.com/p/ff1bd928223b

來源：简书

简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。