Pregel论文发表在2010年ACM／SIGMOD（ Special Interest Group on Management Of Data）上，其名字是欧拉七桥问题中那条河的名字。
Pregel志在构建通用图算法计算模型和引擎，基于网页库（链接关系），社交网络用户数据（社交关系），交通路线图（距离），新闻文章的相似性（聚类算法），疾病爆发路径，解决一些实际问题，如pagerank、社交发掘、交通推荐等问题。
在实际设计系统时，通常遵循如下的思路： 问题集合（如pagerank）-->问题模型抽象（矩阵迭代计算）-->计算范式（基于消息的并行计算，BSP计算模型）-->具体的系统（pregel）。
pregel的关键字：大规模（分布式），高效，通用，自动容错：
如果不是大规模，现在已经有较成熟的单机图算法库；BG，LEAD，NetworkX，JDSL，Standford
GraphBase，FGL
如果不要求高效，MR计算可以解决问题
如果不要求通用，否则针对具体算法实现一套分布式系统肯定最match
如果不要求容错，一些专用的并行图计算系统可更高效地解决问题，如Parallel
BGL和CGMgraph
为什么使用BSP计算模型？
Pregel计算系统的的核心是Valiant提出的BSP计算模型。V和S。S是序列执行的，故天生对异步系统中经常出现的死锁以及临界资源竞争免疫。同步性简化了算法实现。因为BSP模型在超级步之间需要数据同步，所以存在部分节点慢部分节点快的情况，可能你会觉得快节点因为空等而导致计算效率不高。但因为图计算的应用中顶点的数量要远远大于机器的数量，所以一台机器上会分布大量节点，上面既有慢节点又有快节点，当数量很大时就可以通过随机性实现负载均衡，使得实际的逻辑上的慢节点不存在）。
为什么使用消息通信的并行计算范式？
图计算一般具有比较差的内存访问局部性，适合消息传输的方式，如果使用MR的话，通常需要一个MR chain，序列化发序列化开销巨大；而基于消息通信的模型也能表达所有的图算法，且因为无需 remote reading，通过消息异步发送使得计算的实时性更高。
图的表示和计算：
Pregel计算模型使用非常直接的方式表示一张有向图：顶点（vertex）拥有一个ID一个值，每一条有向边（directed
edge）包含源顶点ID、目标顶点ID以及一个值。计算运行在顶点上，边上无计算。
1.将顶点按顶点ID分配到不同的partition，每个worker处理一个或多个partition；
2.所有worker都知道the set of
(partition) assignments for all workers，这就是路由信息；
3.每个worker可以当作vertex
id到vertex state的map，state包括vertex value和出边集合及它们的值。
4.master除了作作业协调工作，还维护来整个作业的状态，包括自定义的聚合值
5.聚合值先在每个实例进行局部聚合，然后在master进行汇总，下一个超级步开始前，master会把聚合值同志给所有worker。可以使用aggregator来检测是否满足收敛条件。
API的特点：
1.提供了VertexValue，EdgeValue，MessageValue集中类型抽象，通过PB来实现灵活性、扩展性
2.有一个string类型的id（address）
3.通过iterator来实现批量操作
4.自定义combiner优化消息传输和存储的数据量（combiner作用在输出或输入队列）
5.自定义aggregator收集全局信息
容错：
1.通过checkpoint，每个超级步开始前持久化，master自己也会保存aggregator的值
2.master主动发送心跳（ping）给所有worker，如果worker很长一段时间没有收到心跳，则主动结束；如果master没有收到worker回复，则标记该worker失败，重新调度。
3.如果worker故障，master重新分配到可用的worker集合，加载checkpoint的数据重新计算