7.3.1有向图和顶点 pregel计算模型以有向图作为输入 °有向图的每个顶点都有一个 String类型的顶点D 每个顶点都有一个可修改的用户自定义值与之关联 ·每条有向边都和其源顶点关联,并记录了其目标顶点ID ·边上有一个可修改的用户自定义值与之关联 顶点(1 边e1 Stng类型的顶点D 可修改的用户自定义值 边上有一个可修改的用户自定义值 4 3
7.3.1有向图和顶点 •Pregel计算模型以有向图作为输入 •有向图的每个顶点都有一个String类型的顶点ID •每个顶点都有一个可修改的用户自定义值与之关联 •每条有向边都和其源顶点关联，并记录了其目标顶点ID •边上有一个可修改的用户自定义值与之关联 String类型的顶点ID 可修改的用户自定义值 边上有一个可修改的用户自定义值 边e1 顶点
7.3.1有向图和顶点 在每个超步S中,图中的所有顶点都会并行执行相同的用户自定义函数 每个顶点可以接收前一个超步(S1)中发送给它的消息,修改其自身及其 出射边的状态,并发送消息给其他顶点,甚至是修改整个图的拓扑结构 在这种计算模式中,“边”并不是核心对象,在边上面不会运行相应的 计算,只有顶点才会执行用户自定义函数进行相应计算 用户定义函数 F/vertex ○表示顶点 表示发送消息 超级步(S1) 超级步S 超级步(S+1)
7.3.1有向图和顶点 •在每个超步S中，图中的所有顶点都会并行执行相同的用户自定义函数 •每个顶点可以接收前一个超步(S-1)中发送给它的消息，修改其自身及其 出射边的状态，并发送消息给其他顶点，甚至是修改整个图的拓扑结构 •在这种计算模式中，“边”并不是核心对象，在边上面不会运行相应的 计算，只有顶点才会执行用户自定义函数进行相应计算 表示顶点 表示发送消息
73.2顶点之间的消息传递 采用消息传递模型主要基于以 消息 下两个原因: 1)消息传递具有足够的表达 能力,没有必要使用远程读取(me Compute) 值 或共享内存的方式 (2)有助于提升系统整体性能。 大型图计算通常是由一个集群 完成的,集群环境中执行远程 数据读取会有较高的延迟; Pregel的消息模式采用异步和 Compute Computed 批量的方式传递消息,因此可 以缓解远程读取的延迟 图9-2纯消息传递模型图
7.3.2顶点之间的消息传递 图9-2 纯消息传递模型图 采用消息传递模型主要基于以 下两个原因： （1）消息传递具有足够的表达 能力，没有必要使用远程读取 或共享内存的方式 （2）有助于提升系统整体性能。 大型图计算通常是由一个集群 完成的，集群环境中执行远程 数据读取会有较高的延迟； Pregel的消息模式采用异步和 批量的方式传递消息，因此可 以缓解远程读取的延迟
7.33 Pregel的计算过程 Pregel的计算过程是由一系列被称为“超步” 用户定义函数 的迭代组成的 在每个超步中,每个顶点上面都会并行执行 用户自定义的函数,该函数描述了一个顶点V① (1 在一个超步S中需要执行的操作 ②2 该函数可以读取前一个超步(S-1)中其他顶点 发送给顶点的消息,执行相应计算后,修改 顶点∨及其出射边的状态,然后沿着顶点∨的 出射边发送消息给其他顶点,而且,一个消 616 息可能经过多条边的传递后被发送到任意已 知|D的目标顶点上去 这些消息将会在下一个超步(S+1)中被目标顶 超级步(S1) 超级步S 超级步(S+1) 点接收,然后象上述过程一样开始下一个超 步(S+1)的迭代过程 ○表示顶点 表示发送消息
7.3.3Pregel的计算过程 •Pregel的计算过程是由一系列被称为“超步” 的迭代组成的 •在每个超步中，每个顶点上面都会并行执行 用户自定义的函数，该函数描述了一个顶点V 在一个超步S中需要执行的操作 •该函数可以读取前一个超步(S-1)中其他顶点 发送给顶点V的消息，执行相应计算后，修改 顶点V及其出射边的状态，然后沿着顶点V的 出射边发送消息给其他顶点，而且，一个消 息可能经过多条边的传递后被发送到任意已 知ID的目标顶点上去 •这些消息将会在下一个超步(S+1)中被目标顶 点接收，然后象上述过程一样开始下一个超 步(S+1)的迭代过程 表示顶点 表示发送消息 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
7.33 Pregel的计算过程 在 Pregel计算过程中,一个算法什么时候可以结束,是由所有顶点的状态 决定的 ·在第0个超步,所有顶点处于活跃状态,都会参与该超步的计算过程 个顶点不需要继续执行进一步的计算时,就会把自己的状态设置为 停机”,进入非活跃状态 旦一个顶点进入非活跃状态,后续超步中就不会再在该顶点上执行计算, 除非其他顶点给该顶点发送消息把它再次激活 当一个处于非活跃状态的顶点收到来自其他顶点的消息时, Pregel计算框 架必须根据条件判断来决定是否将其显式唤醒进入活跃状态 ·当图中所有的顶点都已经标识其自身达到“非活跃( inactive)”状态,并 且没有消息在传送的时候,算法就可以停止运行 不需要执行进一步 计算就设置为停机 活跃 非活跃 收到消息后被唤醒 图9-3一个简单的状态机图
7.3.3Pregel的计算过程 图9-3 一个简单的状态机图 •在Pregel计算过程中，一个算法什么时候可以结束，是由所有顶点的状态 决定的 •在第0个超步，所有顶点处于活跃状态，都会参与该超步的计算过程 •当一个顶点不需要继续执行进一步的计算时，就会把自己的状态设置为 “停机”，进入非活跃状态 •一旦一个顶点进入非活跃状态，后续超步中就不会再在该顶点上执行计算， 除非其他顶点给该顶点发送消息把它再次激活 •当一个处于非活跃状态的顶点收到来自其他顶点的消息时，Pregel计算框 架必须根据条件判断来决定是否将其显式唤醒进入活跃状态 •当图中所有的顶点都已经标识其自身达到“非活跃（inactive）”状态，并 且没有消息在传送的时候，算法就可以停止运行