114 Pregel的C++AP Pregel已经预先定义好一个基类— Vertex类: template <typename Vertex Value, typename Edge Value, typename Message Value> class vertex i put tblic virtual void Compute(Messagelterator*msgs)=0 const string& vertex ido const int64 supersteel const; const Vertex value& Get ValueD Vertex value* Mutable Value OutEdgelterator GetOut EdgelteratorO void SendMessage To(const string& dest vertex. const Message Value& message); void Vote ToHalto; 在 Vetex类中,定义了三个值类型参数,分别表示顶点、边和消息。每一个顶点都 有一个给定类型的值与之对应 编写 Prege程序时,需要继承 Vertex类,并且覆写 Vertex类的虚函数 Compute0 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.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()
114 Pregel的C++AP 在 Pregel执行计算过程时,在每个超步中都会并行调用每个顶点上定义 的 Compute0函数 允许 Compute0方法查询当前顶点及其边的信息,以及发送消息到其他 的顶点 Compute方法可以调用 Getvaluer0方法来获取当前顶点的值 调用 Mutable Valued方法来修改当前顶点的值 -通过由出射边的迭代器提供的方法来查看、修改出射边对应的值 °对状态的修改,对于被修改的顶点而言是可以立即被看见的,但是,对 于其他顶点而言是不可见的,因此,不同顶点并发进行的数据访问是不 存在竞争关系的 整个过程中,唯一需要在超步之间持久化的顶点级状态,是顶点和其对 应的边所关联的值,因而, Pregel计算框架所需要管理的图状态就只包 括顶点和边所关联的值,这种做法大大简化了计算流程,同时,也有利 于图的分布和故障恢复 大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn •在Pregel执行计算过程时，在每个超步中都会并行调用每个顶点上定义 的Compute()函数 •允许Compute()方法查询当前顶点及其边的信息，以及发送消息到其他 的顶点 –Compute()方法可以调用GetValue()方法来获取当前顶点的值 –调用MutableValue()方法来修改当前顶点的值 –通过由出射边的迭代器提供的方法来查看、修改出射边对应的值 •对状态的修改，对于被修改的顶点而言是可以立即被看见的，但是，对 于其他顶点而言是不可见的，因此，不同顶点并发进行的数据访问是不 存在竞争关系的 整个过程中，唯一需要在超步之间持久化的顶点级状态，是顶点和其对 应的边所关联的值，因而，Pregel计算框架所需要管理的图状态就只包 括顶点和边所关联的值，这种做法大大简化了计算流程，同时，也有利 于图的分布和故障恢复 11.4 Pregel的C++ API
114 Pregel的C++AP ·1141消息传递机制 ·114.2 Combiner ·1143 Aggregator ·1144拓扑改变 1145输入和输出 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.4 Pregel的C++ API • 11.4.1 消息传递机制 • 11.4.2 Combiner • 11.4.3 Aggregator • 11.4.4 拓扑改变 • 11.4.5 输入和输出
11.4.1消息传递机制 顶点之间的通讯是借助于消息传递机制来实现的 的条可以通过Veex类的模板参数来设定 息都包含了消息值和需要到达的目标顶 消息值的数据类型 户定义函数 Fvertex) 在一个超步S中 个顶点可以发送任意数量 消息,这些消息将在下一个超步(s+1)中被其 他顶点接收 也就是说,在超步(S+1)中,当 Pregel计算框 ①23 架在顶点∨上执行用户自定义的 Computer方法时 ,所有在前一个超步S中发送给顶点V的消息,都4 可以通过一个迭代器来访问到。迭代器不能保证 消息的顺序,不过可以保证消息一定会被传送并 ①23④56 ③3④⑤5⑥ 且不会被重复传送 个顶点V通过与之关联的出射边向外发送消息、趣步超5超1 ,并且,消息要到达的目标顶点并不一定是与顶 点V相邻的顶点,一个消息可以连续经过多条连 通的边到达某个与顶点V不相邻的顶点∪,U可以 从接收的消息中获取到与其不相邻的顶点V的D 大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.4.1 消息传递机制 • 顶点之间的通讯是借助于消息传递机制来实现的 ，每条消息都包含了消息值和需要到达的目标顶 点ID。用户可以通过Vertex类的模板参数来设定 消息值的数据类型 • 在一个超步S中，一个顶点可以发送任意数量的 消息，这些消息将在下一个超步（S+1）中被其 他顶点接收 • 也就是说，在超步（S+1）中，当Pregel计算框 架在顶点V上执行用户自定义的Compute()方法时 ，所有在前一个超步S中发送给顶点V的消息，都 可以通过一个迭代器来访问到。迭代器不能保证 消息的顺序，不过可以保证消息一定会被传送并 且不会被重复传送 • 一个顶点V通过与之关联的出射边向外发送消息 ，并且，消息要到达的目标顶点并不一定是与顶 点V相邻的顶点，一个消息可以连续经过多条连 通的边到达某个与顶点V不相邻的顶点U，U可以 从接收的消息中获取到与其不相邻的顶点V的ID 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
11.42 Combiner Pregel计算框架在消息发出去之前, Combiner可以将发往同一个顶点 的多个整型值进行求和得到一个值,只需向外发送这个“求和结果” 从而实现了由多个消息合并成一个消息,大大减少了传输和缓存的 开销 在默认情况下, Pregel计算框架并不会开启 Combiner功能,因为,通 常很难找到一种对所有顶点的 Compute函数都合适的 Combiner 当用户打算开启 Combine功能时,可以继承 Combine类并覆写虚函 数 Combine 诵常只 口 Combiner助能,为;ege计算框架无法保证哪些消意会破合并, 也无法保证消息传递给 Combine0的顺序和合并操作执行的顺序 机器N A把值3发送给B 经过 Max combiner合并后 b 3 只把值3通过网络发送给B B B 3 Combiner B 2 C把值2发送给B 消息格式 顶点 图9-5 Combine应用的例子 《大数据技术原理与应用(第2版 厦门大学计算机科学系 林子雨 ziyulin@xmu. edu
《大数据技术原理与应用（第2版）》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 11.4.2 Combiner • Pregel计算框架在消息发出去之前，Combiner可以将发往同一个顶点 的多个整型值进行求和得到一个值，只需向外发送这个“求和结果” ，从而实现了由多个消息合并成一个消息，大大减少了传输和缓存的 开销 • 在默认情况下，Pregel计算框架并不会开启Combiner功能，因为，通 常很难找到一种对所有顶点的Compute()函数都合适的Combiner • 当用户打算开启Combiner功能时，可以继承Combiner类并覆写虚函 数Combine() • 此外，通常只对那些满足交换律和结合律的操作才可以去开启 Combiner功能，因为，Pregel计算框架无法保证哪些消息会被合并， 也无法保证消息传递给 Combine()的顺序和合并操作执行的顺序 A C B D 目标 顶点 值 消息格式 B 2 B 3 Max Combiner B 3 A把值3发送给B C把值2发送给B 经过Max Combiner合并后 只把值3通过网络发送给B 机器M 机器N 图9-5 Combiner应用的例子