来自http://www.royans.net/arch/pregel-googles-other-data-processing-infrastructure/说明google有20%的计算由Pregel完成：
“ Inside Google, MapReduce is used for 80% of all the data processing needs. That includes indexing web content, running the clustering engine for Google News, generating reports for popular queries (Google Trends), processing satellite imagery , language model processing for statistical machine translation and even mundane tasks like data backup and restore.
The other 20% is handled by a lesser known infrastructure called “Pregel” which is optimized to mine relationships from “graphs”.”
google在SIGMOD2010上就Pregel发表了一片论文，以下是阅读笔记：
Pregel: A System for Large-Scale Graph Processing
by Grzegorz Malewicz, Matthew H. Austern, etc. from Google Inc.
摘要：Pregel是一种面向图算法的分布式编程框架，采用迭代的计算模型：在每一轮，每个顶点处理上一轮收到的消息，并发出消息给其它顶点，并更新自身状态和拓扑结构（出、入边）等。
Computational Model: Programs re expressed as a sequence of iterations, in each of witch a vertex can receive messages sent in the previous iteration, send messages to other vertices, and modify its own state and that of its outgoing edges or mutate graph topology.
大规模的图问题面临的挑战：
1、构建分布式框架：每次引入新算法或数据结构都需要花很大的精力；
2、依赖分布式平台入MapReduce等，存在易用性和性能等问题，不适用于图算法（图算法更适合消息传递模型）；
3、单机：无法适应问题规模的扩大；
4、现存的并行图模型系统：没有考虑到大规模系统比较重要的问题如容错性等。
Pregel计算模型：
- 基于BSP模型(Valiant’s Bulk Synchronous Parallel model——Leslie G. Valiant, A Bridging Model for Parallel Computing. Comm. ACM 33(8), 1990, 103-111)；
- 所有节点构成有向图；
- 消息传递模型；
- Pregel计算包含一连串的Supersteps，在每个Superstep，框架对所有的顶点调用一个用户定义的函数。该函数读取当前节点V在上一个superstep中接收到的消息，向其它顶点（可以是任何节点，数目可变）发送消息（用于下一个superstep），更改V的状态和出边。
- 并行：每个顶点独立地进行本地操作，所有的消息都是从第S步发送到第S+1步。
Pregel框架的实现：
- 由集群管理系统进行作业调度：完成资源分配、作业重启和转移等；
- 用GFS或BigTable进行持久存储；
- （Master-slave结构）有一个节点（机器）扮演master角色，其它节点通过name service定位该顶点并在第一次时进行注册；
- master负责对顶点集合进行切分到各节点（也可以用户自己指定，考虑load balance等因素），根据顶ID哈希分配顶点到机器（一个机器可以有多个节点，通过name service进行逻辑区分）；
- 节点间异步传输消息；
- 通过checkpoint机制实行容错（更高级的容错通过confined recovery实现：log），节点向master汇报心跳（ping）维持状态。
具体实现细节：
- 顶点类Vertex包含vertices、edges、messges三种相关数据，采用protocol buffer实现易变类型；
- 用户通过重写Compute()函数（C++中的虚函数）定义每个superstep中顶点进行的操作；GetValue()和MutableValue()函数分别得到和修改顶点关联值；
- Message Passing：发送消息时根据目标顶点是否在本地使用不同的方式；master用barrier机制实现；
- Combiners：（某些应用）将收到的消息进行合并，默认不启动；
- Aggregators：（如min、max、sum）每个superstep钟每个顶点提供一个值给aggregator使用，系统通过reduce操作得到一个全局值，该值可被下一个superstep中的所有顶点使用；
- Topology Mutations:在算法执行过程中可以改变拓扑结构，使用lazy机制；
- Input and Output：Pregel提供常见格式文件的读写，通过继承Reader和Wirter类实现特别的需求。
应用实例：
PageRank、
SSSP（单原点最短路）、
Bipartite Matching(二分匹配：随机算法)、
Semi-Clustering（比如求社会化网络中的交往圈）。
Future work：
- 目前所有的计算状态均保存在RAM，下一步将保存部分数据至磁盘（解决更大规模数据情况下内存不够的问题）；
- 顶点分配：减小节点间的通信，向动态分配机制转变；（个人点评：集群管理器的实现决定顶点划分（调度）、作业恢复（容错）等机制，对于整个模型非常重要。）
- 目前面向稀疏图，稠密图（或通信特别多）的图算法仍旧无法解决。
