malewicz.sigmod10.pregel-google.pdf 互联网巨头谷歌之前的关于图数据库系统的文章，之前也是苦于图数据库相关的知识太少，希望通过不断收集和整理，让更多有志于在图数据库领域的同学少走弯路
GFS、MapReduce 和 BigTable 三篇技术论文（旧三驾马车），这也成为后来云计算发展的重要基石，如今 Google 在后 Hadoop 时代的新“三驾马车” -- Caffeine、Pregel...（1PB = 1024T） 另一篇介绍了 Pregel，Pregel 主要绘制大量网上信息之间关系的“图形数据库”。而最吸引人的一篇论文要属被称之为 Dremel 的工具。
由于谷歌的一篇名为 Pregel 的论文将该图计算模型大规模的推广，因此 BSP 模型有时也被称为 Pregel 模型。...如果你把每个点认为是一个 actor 的话，Pregel 在某种程度上很像我们之前提到的 Actor 模型。但与 Actor 模型不同的是，Pregel 中点的状态和消息是持久化且容错的。...容错 Pregel 中限定只能通过消息传递（而不是通过主动拉取）来进行通信，因此可以方便的将消息 batch 起来以减少等待。...即使在消息传输的过程中，可能会出现丢失、重复和不定时延迟，Pregel 仍然能够保证所有消息在目的节点上严格的被处理一次。...和 MapReduce 一样，Pregel 会进行对上层无感的错误恢复，以期简化所有基于 Pregel 的上层算的实现。
计算模式 图计算模式 目前基于图的并行计算框架已经有很多，比如来自Google的Pregel、来自Apache开源的图计算框架Giraph/HAMA以及最为著名的GraphLab，其中Pregel、HAMA...参考GraphX的Pregel代码，对一个大图，目前最佳的实践是： ?...进化的Pregel模式 GraphX中的Pregel接口，并不严格遵循Pregel模式，它是一个参考GAS改进的Pregel模式。定义如下： ?...这种基于mrTrilets方法的Pregel模式，与标准Pregel的最大区别是，它的第2段参数体接收的是3个函数参数，而不接收messageList。...它综合了Pregel和GAS两者的优点，即接口相对简单，又保证性能，可以应对点分割的图存储模式，胜任符合幂律分布的自然图的大型计算。另外，值得注意的是，官方的Pregel版本是最简单的一个版本。
在Pregel 平台上程序设计的最大特点就是从图中每一个节点出发，在执行计算的机器上保持顶点和边，用网状结构传输信息。...小可兴奋地说：我很想尝试用Pregel 去写一个图算法，在实际使用中应用Pregel 是怎么做的呢？ Mr. 王打开电脑中的一段代码，说：这就是Pregel 的C++ API。...其实Trinity 平台的API 和Pregel 的都是比较类似的，可以触类旁通。 在实际使用的过程中，需要定义的就是节点这个类。...小可：如果我想部署一个Pregel 平台，需要怎么做呢？ Mr. 王：一般来说，一个Pregel 平台都需要运行master 和worker 两种进程。
Pregel 运行原理 源码定义如下： def pregel[A: ClassTag]( initialMsg: A, maxIterations: Int = Int.MaxValue...只看定义和逻辑同样不太清楚，所以下边再介绍一下 Pregel 的迭代流程： 对于一个 graph 对象，只有激活态的点才会参与下一次迭代，激活态的条件是完成了一次发送/收到消息 A 的动作； 首先初始化所有节点...模式匹配的思路 知道 Pregel 的计算原理之后，那么怎么实现模式匹配呢，主要就是根据迭代的思想，不停地将边信息聚合到点上，在迭代的过程中控制发送消息的逻辑来实现特定模式的路径。...等等的这些问题，但是核心点不变，就是基于 Pregel 实现广度优先遍历，累积边形成路径信息，主要的逻辑基本都在于 sendMsg 这个方法，来控制发或者不发，来决定路径的走向，以满足模式匹配的业务要求...总结 利用 GraphX 的 Pregel API 进行广度优先遍历来实现模式匹配的好处： GraphX 有多种图算子可以灵活处理图数据； 基于 Pregel，使用路径当做消息可以灵活控制模式子图的结构
Pregel(ccGraph, initialMessage,maxIterations, EdgeDirection.Either)(......)最后调用的就是Pregel里的apply方法。...这个方法会在后面的Pregel对象里用到。...step4 执行Pregel的构造函数apply方法 可以看到，前面创建的ccGraph，initialMessage，maxIterations（最大迭代次数），EdgeDirection.Either...都当作参数传给了Pregel。...三、Pregel源码解析 Pregel是一个图处理模型和计算框架，核心思想是将一系列顶点之间的消息做传递和状态更新操作，并以迭代的方式进行计算。让我们继续深入看一下它的底层实现。
其中pregel迭代接口和aggregateMessages合并消息接口是较为重要而灵活的方法。...如果设计迭代算法，推荐使用pregel迭代接口，它能够正确地释放不再使用的中间计算结果。...使用pregel迭代接口能够很好地进行缓存优化。 ? pregel迭代接口基于Graphx的基础API实现，实现方式相当简洁，其代码不过20多行。...下面我们基于pregel接口来重新实现：计算每个顶点和离它最远的源顶点的距离。 ?...七，其它常用图算法 Graphx内置的一些图算法基本上是用pregel迭代API实现的。 还有一些非常经典的图算法不太适合使用pregel迭代API实现，因此它们在Graphx中没有对应的内置实现。
GraphX 提供了类似与Pregel 的操作，这是 Pregel 和 GraphLab 方法的融合。...当没有消息是，Pregel 停止迭代，并返回最终图形。 请注意，不像更标准的 Pregel的实现，在GraphX中顶点只能将消息发送到邻近的顶点，并且信息构建是通过使用用户定义的消息函数并行执行。...以下是类型签名 Pregel，以及一个 初始的实现 （注调用graph.cache已被删除）中： class GraphOps[VD, ED] { def pregel[A]( initialMsg...需要两个参数列表（即graph.pregel(list1)(list2)）。...我们可以使用 Pregel 运算符来表达计算，如在下面的例子中的单源最短路径。
对于迭代计算，我们建议使用Pregel API，它可以正确地解析中间结果。 Pregel API 图形是固有的递归数据结构，因为顶点的属性取决于其邻居的属性，而邻居的属性又依赖于其邻居的属性。...GraphX 公开了 Pregel API 的变体。 在高层次上，GraphX 中的 Pregel 运算符是限制到图形拓扑的批量同步并行消息抽象。...与 Pregel 不同，消息作为边缘三元组的函数并行计算，消息计算可以访问源和目标顶点属性。在超级步骤中跳过不接收消息的顶点。 Pregel 运算符终止迭代，并在没有剩余的消息时返回最终的图。...以下是 Pregel 运算符 的类型签名以及 其实现的草图（注意：为了避免由于长谱系链引起的 stackOverflowError ， pregel 支持周期性检查点图和消息，将 “spark.graphx.pregel.checkpointInterval...需要两个参数列表（即：graph.pregel(list1)(list2)。
后面还会提到BSP框架，它的一个著名实现是Google Pregel。 MPI这个框架很灵活，对程序结构几乎没有太多约束，以至于大家有时把MPI称为一组接口（API）。...这些功能在Google的系统里是分布式操作系统负责的，而Google MapReduce和Pregel都是在分布式操作系统基础上开发的，框架本身的代码量少很多，并且逻辑清晰易于维护。...Checkpointing是下文要说到的Pregel框架实现fault recovery的基础。 但是如果一个系统自己实现fault recovery，那还需要MPI做什么呢？做通信？...当我们踌躇于MPI的扩展性不理想而MapReduce的效率不理想时，Google MapReduce团队的几个人分出去，开发了一个新的并行框架Pregel。...当时Pregel项目的tech lead访问中国。这个叫Grzegorz Malewicz的波兰人说服了我尝试在Pregel框架下验证LDA。
小可：如果依然利用Pregel 平台的思想来解决问题，要怎么做呢？ Mr. 王：考虑到Pregel 平台具有面向节点编程的思想，我们就要考虑在比较大的图中较小的相邻结构。...这个搜索过程可以很好地利用Pregel 的思想。
对于迭代计算，我们建议使用 Pregel API，它可以正确的不持久化中间结果。 ...GraphX 公开了一个类似 Pregel 的操作，它是广泛使用的 Pregel 和 GraphLab 抽象的一个融合。 ...GraphX 中实现的这个更高级的 Pregel 操作是一个约束到图拓扑的批量同步（bulk-synchronous）并行消息抽象。...当没有消息遗留时，Pregel 操作停止迭代并返回最终的图。...下面的代码是 pregel 的具体实现。
代表之一是Google提出的Pregel系统[2]，Google称20%的数据处理是使用Pregel实现的，图计算是成功的数据挖掘处理框架。...然而，Google一直没有将Pregel的具体实现开源，外界争相对Pregel进行模仿实现。...图计算系统按BSP并行机制（Pregel）或异步并行机制（GraphLab）在计算集群上调度所有的顶点程序，并加入一定的容错机制，比如快照恢复。...由于Pregel采用同步执行模式等原因，速度较慢，目前GraphLab和GraphChi已经分别成为了分布式图计算系统和基于磁盘单机图计算系统的业界标杆。...Pregel: a system for large-scale graph processing.
Google 提出了 Pregel，一个针对图算法特点设计的分布式图计算系统，遵循 BSP 运算模型；之后 CMU Select 实验室 GraphLab 项目组提出了GAS 运算模型。。...虽然pregel 和 GraphLab 都是对于复杂机器学习计算的处理框架，用于迭代型（iteration）计算，但是二者的实现方法却采取了不同的路径：Pregel 是基于大块的消息传递机制，GraphLab...Pregel ：Google 在 2009 年提出，是图计算模型的开山祖师，后续很多工作都受到它的思想影响。不开源。 Giraph ：Facebook 基于 Pregel 思想的开源实现。...Gemini ：清华大学基于 Pregel 思想进行了多项改进的实现，性能优秀。仅提供免费 Demo，商业版不开源。
尽管如此，RDD仍然足以表示很多类型的计算，包括MapReduce和专用的迭代编程模型（如Pregel）等。...RDD可以用来描述Pregel、迭代式MapReduce，以及这两种模型无法描述的其他应用，如交互式数据挖掘工具（用户将数据集装入内存，然后执行ad-hoc查询）。...此外，我们还在Spark之上实现了Pregel和HaLoop编程模型（包括其位置优化策略），以库的形式实现（分别使用了100和200行Scala代码）。...在Pregel和HaLoop中，多次迭代之间采用一致性的分区置换策略进行优化，我们同样也允许用户指定这种优化。 （注: ?...首先讨论一些迭代式机器学习应用（4.1），然后看看如何使用RDD描述几种已有的集群编程模型，即MapReduce（4.2），Pregel（4.3），和Hadoop（4.4）。
limeng.blog.csdn.net/article/details/120814044 Spark REPL:https://limeng.blog.csdn.net/article/details/109953862 Pregel
本文利用一个初始示例代码，结合部分官方文档中的说明，对GraphX的部分功能方法进行了实践，在全部亲自运行通过后，对大部分代码添加了自己的理解和认识，并且在Pregel模型编程部分结合运行结果对其运行流程做了一定梳理...Operators Computing Degree Collecting Neighbors Join Operators mapReduceTriplets aggregateMessages Pregel...----- //----------------- aggregateMessages ----------------- //----------------- Pregel...println) //上述计算的意义是：找到每个顶点用户的比自身年龄大的邻居节点用户的平均年龄，即原本的计算目的 //结果为： // (1,42.0) // (6,60.0) // (2,60.0) Pregel...Iterator[(graphx.VertexId, Double)], // 第三部分：mergeMsg: (Double, Double) => Double val sssp = initialGraph.pregel
认识到这个问题后, 研究者们已经为一些需要中间数据复用的应用开发出了一些特殊的框架.比如Pregel 在做迭代式图计算的时候会将中间结果放在内存中....这种在迭代之间进行数据一致分区是像 Pregel 这种框架中的主要的优化计算方式....Pregel: Google 的 Pregel 是一个专门解决迭代图计算应用的模型, 它一开始看起来和面向数据集的编程模型的其他系统完全不同.在 Pregel 中, 一个程序运行一些列的相互协调的“ supersteps...Pregel 在每一次迭代中都是对所有顶点应用相同的用户定义的函数, 这个是使的我们用 RDDs 来实现这个模型的关键点....和 Pregel 一样, RDDs 允许将点的状态保存在内存中、控制它们的分区以减少网络通讯以及指出从失败中恢复.
Giraph originated as the open-source counterpart to Pregel, the graph processing architecture developed...Giraph adds several features beyond the basic Pregel model, including master computation, sharded aggregators
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
