1 概括

Piccolo是New York大学在OSDI 2000上发表的paper Piccolo: Building Fast, Distributed Programs with Partitioned Tables【1】提出来的一个新的分布式计算编程模型，Piccolo允许计算单元跑在不同的机器上，更重要的是它对计算过程中的共享状态数据的访问有很好的本地性，同时解决了在运行时写数据的冲突等问题。

它和MapReduce的区别在于能够轻松访问中间状态（其实就是中间结果,之后都采用中间结果的说法），由于MapReduce需要把中间结果保存到HDFS，开销比较大，所以对需要频繁访问中间结果的运算效率不高，而Piccolo把中间结果保存在内存中，Piccolo中叫做in-memory table，Piccolo对in-memory table抽象出key-value简单的操作接口，方便操作。

当然用MPI等传统的编程框架，再加上shared-memory也可以解决这种问题，但是MPI这种low-level的编程框架编写代码非常复杂，而shared-memory的性能不高。

对于之前提到的对中间结果访问密集型的场景，论文中举了几个例子：

1、PageRank，在计算一个网页的PageRank分值的时候，需要访问这个网页周围的网页的PageRank值，它周围网页的PageRank值就是被频繁访问的中间结果。

2、K-means聚类算法【2】。K-Means先选取k个对象作为初始的聚类中心，然后计算剩下的对象和聚类中心的距离，根据他们与聚类中心的距离将他们分配到就近的聚类中心，然后得出新的聚类中心，再计算其它对象和新的聚类中心的距离，重复如此，直到收敛为止。在重新计算聚类中心的时候，需要这个聚类下所有对象到之前的中心的距离，它也是分布在不同节点，同时需要被频繁访问的。

可以知道的是，类似的场景大部分出现在数据挖掘的场景下。

好了废话少说，下面分析一下Piccolo是如何实现的