7.34实例 A B 活跃 超步0 非活跃 3.6 6 超步1 A. B C 'D 6 6 超步2 6 超步3 图94一个求最大值的 Pregel计算过程图
7.3.4实例 图9-4 一个求最大值的Pregel计算过程图 活跃 非活跃 AB C D AB C D AB C D 3 6 6 2 2 1 6 6 6 6
74 Pregel的C++AP Pregel t已经预先定义好一个基类— Vertex类 template <typename Vertex Value, typename Edge Value, typename Message Value> class vertex i oublic virtual void Compute(Messagelterator* msgs)=0; const string& vertex ido const Int64 superstepo const const Vertex Value& Get Value Vertex value* Mutable value OutEdgelterator GetOut Edgelterator(; void SendMessage To(const string& dest vertex const Message value& message) void Vote ToHalto ·在 Vetex类中,定义了三个值类型参数,分别表示顶点、边和消息。每一个顶点都 有一个给定类型的值与之对应 编写 Pregel程序时,需要继承 Vertex类,并且覆写 Vertex类的虚函数 Compute0
7.4 Pregel的C++ API Pregel已经预先定义好一个基类——Vertex类： template <typename VertexValue, typename EdgeValue, typename MessageValue> class Vertex { public: virtual void Compute(MessageIterator* msgs) = 0; const string& vertex_id() const; int64 superstep() const; const VertexValue& GetValue(); VertexValue* MutableValue(); OutEdgeIterator GetOutEdgeIterator(); void SendMessageTo(const string& dest_vertex, const MessageValue& message); void VoteToHalt(); }; •在Vetex类中，定义了三个值类型参数，分别表示顶点、边和消息。每一个顶点都 有一个给定类型的值与之对应 •编写Pregel程序时，需要继承Vertex类，并且覆写Vertex类的虚函数Compute()
74 Pregel的C++AP 在 Pregel行计算过程时,在每个超步中都会并行调用每个顶点上定义 的 Compute函数 ●允许 Compute方法查询当前顶点及其边的信息,以及发送消息到其他 的顶点 Compute方法可以调用 GetValue0方法来获取当前顶点的值 调用 Muta| evalue方法来修改当前顶点的值 通过由出射边的迭代器提供的方法来查看、修改出射边对应的值 对状态的修改,对于被修改的顶点而言是可以立即被看见的,但是,对 于其他顶点而言是不可见的,因此,不同顶点并发进行的数据访问是不 存在竞争关系的 整个过程中,唯一需要在超步之间持久化的顶点级状态,是顶点和其对 应的边所关联的值,因而, Pregel计算框架所需要管理的图状态就只包 括顶点和边所关联的值,这种做法大大简化了计算流程,同时,也有利 于图的分布和故障恢复
•在Pregel执行计算过程时，在每个超步中都会并行调用每个顶点上定义 的Compute()函数 •允许Compute()方法查询当前顶点及其边的信息，以及发送消息到其他 的顶点 –Compute()方法可以调用GetValue()方法来获取当前顶点的值 –调用MutableValue()方法来修改当前顶点的值 –通过由出射边的迭代器提供的方法来查看、修改出射边对应的值 •对状态的修改，对于被修改的顶点而言是可以立即被看见的，但是，对 于其他顶点而言是不可见的，因此，不同顶点并发进行的数据访问是不 存在竞争关系的 整个过程中，唯一需要在超步之间持久化的顶点级状态，是顶点和其对 应的边所关联的值，因而，Pregel计算框架所需要管理的图状态就只包 括顶点和边所关联的值，这种做法大大简化了计算流程，同时，也有利 于图的分布和故障恢复 7.4 Pregel的C++ API
74 Pregel的C++AP ·74.1 消息传递机制 74.2 Combiner ·74.3 Aggregator 7.44 拓扑改变 74.5 输入和输出
7.4 Pregel的C++ API • 7.4.1 消息传递机制 • 7.4.2 Combiner • 7.4.3 Aggregator • 7.4.4 拓扑改变 • 7.4.5 输入和输出
7.4.1消息传递机制 顶点之间的通讯是借助于消息传递机制来实现的 每条消息都包含了消息值和需要到达的目标顶 点D。用 以通过 Vertex类的模板参数来设定 消息值的数据类型 在一个超步S中,一个顶点可以发送任意数量的 消息,这些消息将在下一个超步(S+1)中被其 他顶点接收 2 也就是说,在超步(S+1)中,当 Pregel计算框 架在顶点V上执行用户自定义的 Compute方法时 ①②3④ 所有在前一个超步S中发送给顶点V的消息,都 可以通过一个迭代器来访问到。迭代器不能保证 的顺序,不过可以保证消息一定会被传送并 ①②③④⑤ 5 会被重复传送 6 6 个顶点V通过与之关联的出射边向外发送消息 级步(S1) 超级步S 超级步(S+1) 并且,消息要到达的目标顶点并不一定是与顶 点V相邻的点, 消息可以连续经过多条连 通的边到达某个与顶点V不相邻的顶点U,U可以 从接收的消息中获取到与其不相邻的顶点∨的|D
7.4.1消息传递机制 • 顶点之间的通讯是借助于消息传递机制来实现的 ，每条消息都包含了消息值和需要到达的目标顶 点ID。用户可以通过Vertex类的模板参数来设定 消息值的数据类型 • 在一个超步 S中，一个顶点可以发送任意数量的 消息，这些消息将在下一个超步（S+1）中被其 他顶点接收 • 也就是说，在超步（S+1）中，当Pregel计算框 架在顶点 V上执行用户自定义的Compute()方法时 ，所有在前一个超步 S中发送给顶点 V的消息，都 可以通过一个迭代器来访问到。迭代器不能保证 消息的顺序，不过可以保证消息一定会被传送并 且不会被重复传送 • 一个顶点 V通过与之关联的出射边向外发送消息 ，并且，消息要到达的目标顶点并不一定是与顶 点 V相邻的顶点，一个消息可以连续经过多条连 通的边到达某个与顶点 V不相邻的顶点 U，U可以 从接收的消息中获取到与其不相邻的顶点 V 的ID