29 Mar 2015
Paracel十问
Paracel的是什么？
Paracel是豆瓣开发的一个分布式计算框架，它基于参数服务器范式，最初是为机器学习算法设计的。Paracel支持数据和模型的并行，为用户提供简单易用的通信接口，比mapreduce式的系统要更加灵活。Paracel同时支持异步的训练模式，使迭代问题收敛地更快。此外，Paracel程序的结构与串行程序十分相似，用户可以更加专注于算法本身，不需将精力过多放在分布式逻辑上。参数服务器是什么？
参数服务器是一个全局分布式的key-value存储，用来存储算法的模型或者说参数，当计算节点需要某个参数的时候，可以从参数服务器上读取。用户还可以定义不同的函数在参数服务器端对参数进行更新、过滤等操作。在大部分情况下，计算节点之间的通信都是通过参数服务器进行的。什么是模型并行？数据并行和模型并行如何同时满足？
模型并行指的是将算法的模型参数分布式存储。随着算法数据量的增加和算法模型的越来越复杂，许多模型已经不能装入单机的内存中了，因此需要将模型并行，从而满足可扩展性的要求。数据和模型的同时并行是一个很大的挑战，数据的并行往往意味着计算性能的可扩展，而模型的并行往往意味着内存使用的可扩展，一个好的分布式算法需要满足这两方面的扩展性要求。在一般情况下，模型和数据是对应的，因此如何切分输入数据的结构决定了模型的切分方式。Paracel定义了一套输入数据格式，提供了将数据切分成有向图、二分图、无向图、稀疏矩阵和绸密矩阵的接口，用户可以按照算法需要，直接将输入数据并行读取成这些数据结构，做到模型的并行。做Paracel项目的初衷是什么？
豆瓣有Dpark工具来处理海量数据，然而对于性能要求较高和较复杂的问题，Dpark无法很好地满足需求。为了提高分布式算法的开发效率，增强代码的复用能力，我们在2013年底开始做Paracel项目，意为提供一个较通用易用的算法平台。Paracel和Spark/GraphLab的主要区别是什么？
Spark和GraphLab都是非常成功的分布式计算框架，它们各自有着很多吸引用户的优点，但也存在一些局限性。Spark提出了RDD的概念并赋予其一系列的transformation和action接口，若把这些接口想成是一组基，那么用户就可以用这组基组合成不同的算法或应用。值得注意的是，这组基虽然通用，但往往不够灵活，特别是对特定领域的问题。例如图算法，Spark基于Google的Pregel模型实现了Bagel模块供用户使用，而非基本的RDD操作可以满足。另外，Spark的RDD操作更适合窄依赖的场景，数据的局部性考虑不够，多少会影响性能。
GraphLab论证了机器学习问题都可以转化成图计算的方式，相比Spark更侧重于计算性能。不过用户需要首先将问题转化成GraphLab的模型，这会影响开发效率。同时对于一般的算法工程师，GraphLab门槛有点过高，用户必须先理解其原理和分布式逻辑才能进行开发。
相比之下，Paracel较GraphLab更上层，强调简单易用性，而较Spark更底层，提供了灵活通用的通信接口。算法开发者可以更加专注于问题本身而不必过于关注分布式逻辑。
当然，Paracel还很不成熟，功能和社区都不完善，还有许多要向Spark和GraphLab学习的地方。如何安装Paracel？
先安装Paracel的一些依赖，然后在集群上部署Paracel。详细的步骤请参见文档的对应章节。如何在Paracel框架中进行分布式算法开发？
用户可以模仿Paracel项目里alg目录下的例子来开发自己的应用，详细的介绍请参见Paracel入门教程的对应部分。什么是straggler问题？Paracel是如何解决的？
由于一些软件和硬件的原因，节点的计算能力往往不尽相同。对于迭代问题来说，每轮迭代结束时算地快的节点都要等待算地慢的节点算完，再进行下一轮迭代，这种等待在节点数目增多的时候变地尤为明显。这是BSP模型的一个经典问题，一般有两种思路来解决这个问题：第一种办法是在切分数据时预留一些数据，再对剩下的数据做均分。在每轮迭代结束时，算地快的节点会继续计算这些预留的数据以等待算地慢的节点完成本轮计算。简单来说，就是让算地较快的节点算更多的数据，即做某种特定的负载不均衡。这时，开发者需要写许多与算法逻辑无关的调度代码来实现这种策略。Paracel则采用了一种更通用的方式，我们放宽了“每个迭代步都等待”的约束条件：当在一轮迭代结束时，算地快的节点可以继续下一轮迭代，但不能比最慢的节点领先参数s个迭代步。当领先超过s个迭代步时，Paracel会强制它进行等待。这样的异步控制方式一方面从整体上省去了等待时间，另一方面也能间接地帮助算地慢的节点赶上。从优化问题的角度，虽然每个迭代步收敛地慢了，然而每个迭代步的时间开销变少了，总体上收敛也就变快了。Paracel是只适合机器学习算法的训练框架吗？
Paracel最初确实是针对机器学习问题做的抽象。但随着项目的推进，我们逐渐发现Paracel的范式同样适用于图算法和科学计算问题。举例来说，我们在Paracel的toolkits中有两个图算法的例子：Max Vertex Value和Pagerank，前者的实现我们采用了Pregel(Google对BSP的图抽象)的方式而后者我们采用了Paracel的范式。事实上，用Paracel的范式实现图算法更加直接和高效。Paracel目前有哪些局限性？未来发展是怎样的，下个版本会加入哪些功能？
目前这个版本的Paracel没有做容错，因此稳定性欠佳，这将作为我们在下一个版本的主要解决的问题。另外，Paracel目前只支持文本文件，我们也将尽快加入对压缩格式以及其他文件的支持。Paracel streaming和像Spark那样的data flow接口也是我们正在努力开发的模块。
Hong Wu at 16:00
