Giraph助力Facebook打造亿万用户间关系链

随着Facebook用户数的增加，Facebook希望能够测量基本的统计信息和高效地计算出用户之间的关联性，比如用户位置、兴趣爱好之间的关联性以及他们之间的亲和力、共同好友、查找潜在好友等信息。为了实现这些功能，他们采用一款开源的图论工具――Apache Giraph。该工具最早出自雅虎，后来将其捐赠给 了Apache软件基金会。

Giraph是一个高扩展性的交互图形处理系统，Facebook对Giraph进行了改进和提升，实现对不同实体间的万亿个连接进行了分析。Facebook将Giraph规模化并作为其Open Graph工具的核心。Giraph的整体计算模型被运用在Facebook服务器内并行巨大的网络图计算。

Giraph是如何工作的？ 

Giraph是基于批量同步并行模型，由哈佛大学计算机教授Leslie Valiantz在20世纪80年代开发的一类并行计算算法。BSP算法通过 一系列步骤跨多台计算机计算，在每一小步上，每台计算机都执行一点计算，再把结果传递到其它系统里，这些系统再继续执行下 一个步骤。

Giraph计算的输入是由点和直连的边组成的图。例如，点可以表示人，边可以表示朋友请求。每个顶点保存一个值，每个边也保存一个值。输入不仅取决于图的拓扑逻辑，也包括定点和边的初始值。 作为一个例子，考虑这样一个计算，查找从一个预设的初始人到社交图谱中的任何一个人的距离。在这个计算中，边的值是一个浮 点数表示相邻的人之间的距离，顶点V也是一个浮点数，表示从预设的顶点s到v的最短距离的上限值。预设的源顶点的初始值是0， 其它顶点的初始值是无穷大。

来自：Facebook

此外，Giraph引起大家关注的另一原因是基于Hadoop建立的，目前，很多企业都是Hadoop来部署大数据平台，Facebook便是其中之一。

在Facebook使用Giraph之前，对于大规模图形计算，人们曾使用诸如Hive和MapReduce等框架，它们可以实现大规模计算，但对比现在的计算速度，它们要慢50到100倍这样。

发现人与人之间的关联

举一个最简单的例子，Giraph使用手册上例举了一个实现单源最短路径算法，一个计算方法是从所有收到的消息中计算最小的值，如果那个值节点的当前值小，那最小的那个就被接受作为顶点的值，而且值和边的值就会沿着每一个外出的边发送。

从逻辑上来讲，任何节点之间的最短路径一般只有该节点到其邻居节点之间的距离。所以，基于Giraph模型，每个节点开始的第一步都是计算其最短路径，然后通知其邻居，如果其邻居节点找到更短路径，也会通知给开始节点，这样，就很容易找到最短路径。

在本月初，Facebook的一篇博客文章介绍了 Giraph是如何分配Facebook用户数据到特定的数据库服务器。当用户朋友信息被存储在同一个服务器上时，Facebook运行将会更高效，因为对于同样的操作，跨服务查找的次数也会明显减少。

Giraph为每个节点分配一个特定的设置，代表一个服务器，然后告诉其邻居节点所在地。在每个步骤中，它随机决定是否需要移动到另一组，与其邻居移动的数量成正比。 

Facebook在Giraph上取得的成效

作为一个迭代的图形处理库，Giraph具有容错和动态调节的功能。

在可扩展方面，Facebook可以在拥有上万亿连接的真实的社交图谱上运行一个迭代的页面排名，这一社交图谱由各类用户在4分钟之内交互产生，伴随适当的碎片收集和性能调节。除此之外，还可以聚集Facebook每月的活跃用户数据集，在几分钟内即可完成对如此大规模数据和变量的处理。

除图谱搜索外，Facebook还计划将Apache Giraph软件用在其他任务中，例如精准广告和数据排名。Facebook在社交领域的成功离不开其在技术领域的探索与创新，图形技术的应用更是推动了Facebook的发展。

文章翻译自：fastcolabs、gigaom

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠