腾讯QQ有着国内最大的关系链,而共同好友数,属于社交网络分析的基本指标之一,是其它复杂指标的基础。借助Spark GraphX,我们用寥寥100行核心代码,在高配置的TDW-Spark集群上,只花了2个半小时,便完成了原来需要2天的全量共同好友计算。这标志着QQ千亿级别的关系链计算进入了小时级别时代,并具备复杂图模型的快速计算能力。
共同好友数可以用于刻画用户与用户间的关系紧密程度,包括 陌生人/熟人分析,好友亲密度,好友推荐,社团划分等各个方面,是社交网络分析的最基础指标。其计算逻辑非常简单明了。为了简化模型和降低计算量,这里加了几个约束:
显而易见,用户5和6的共同好友数为4。这个计算貌似非常简单,但是当图的规模扩展到腾讯的级别:用户数(点)为十亿级别,关系数(边)为千亿级别时,那这个问题就一点都不简单了。
大致估算一下,假设每个节点平均的好友数是100,每个点id为Long型,占用8个字节,如果用普通Join计算的话,那么中间的数据量大概是1 billion* 800*800B=640TB
,需要通过网络传输640TB的数据,这个量非常的恐怖了,想在一个SQL中完成,几乎是不可能的。原来旧的计算方式,只能通过分而治之的方法实现。通过把关系链表,按号段拆分60份,分别连接用户好友全量表,分成多个SQL任务运行。这样做每个SQL任务都需要载入一次全量关系链,磁盘 I/O 时间严重拖慢计算进度,整个过程需要耗费超过两天的计算时间。
其实共同好友数是典型的图问题之一,因此很自然的,我们想到了引入新的图计算框架和模型,来优化计算过程,让这个过程更加高效和科学。
目前的分布式图计算框架,并没有太多好的选择,在过去一年半中,业界的分布式图计算框架,进展基本停滞。经过反复选择,我们还是选择了GraphX,主要原因有如下3个:
基于这样的考虑,我们选择了GraphX作为共同好友算法的底层框架,并从软件和硬件两方面入手,进行了一系列的优化。
基于GraphX的图模型思想,我们进行数好友模型的简化。整个过程分为两个阶段:
这个阶段,使用GraphX的aggregateMessages,定义好sendMsg和mergeMsg的方法,就可轻松实现。
这个阶段,需要充分利用GraphX的Triplet特性。需要为了实现Triplet功能,GraphX在设计上消耗了很多的内存,无论我们是否使用,它都在那里,静静的占用着内存,所以我们要充分利用好它,将数好友的过程,简化为一次Triplet的遍历。 如果没有这个特性,为了数好友之间的共同好友,就要把一个好友的所有一度好友,发送到它所有的邻居之上,这样的消息广播量,是非常巨大的,会形成消息风暴,相当于计算二跳邻居。根据我们在腾讯数据量上的测试,这个在现有的硬件下,是无法实现的。
这2个阶段经过最终优化之后,代码非常的简洁,只要聊聊的数十行代码,便完成了20亿级别的点,千亿级别的边的共同好友计算,可谓于无声处听惊雷。将众多的技术难点,都通过GraphX的优化,化解消弭于无形之中。由于产品的需求,这个计算需要是精确数,而不能是近似值,在数好友的过程中,很多的优化方法,不能被用上,否则的话,可以进一步的提升速度。
在分布式系统中,往往会倾向于用大量的小低配机器,来完成巨大的计算任务。其思想是即便再复杂的计算,只要将大数据,分解为足够小的数据片,总能在足够多的机器上,通过性能的降低和时间的拖延,来完成计算任务。但是很遗憾,在图计算这样的场景下,尤其是GraphX的设计框架,这个是行不通的。
要发挥GraphX的最佳性能,最少要有128G以上的内存
主要原因有两个是:
其实这两个问题,在Spark的其它机器学习算法中,或多或少都会有,也是分布式计算系统中,经常面临的问题。但是在图计算中,它们是无法被忽略的问题,而且非常的严重。所以,这决定了GraphX需要大的内存,才能有良好的性能。
在正常情况下,128G内存,减掉8G的系统占用,剩下120G。这时配置每个Executor 60G内存,2个Core,每个Core分到30G的内存。这时不需要申请太多的Executor,经过合理的性能优化,全量关系链计算,可以运行成功。
即便有了良好的模型和硬件保障,在面对QQ如此巨型的关系链时,依然需要熟练运用GraphX的技巧,并避开各种雷区,才能最终到达终点。简单总结两点:
Persist(MEMORY_ONLY)
,或者Persist(MEMORY_AND_DISK)
。可以把RDD和Graph,Cache到内存中,方便多次调用而无需重新计算。那么是否对所有的RDD,或者图,都Cache一下,是最佳的选择呢?答案是未必。
判断是否要Cache一个Graph或RDD,最简单和重要的标准,就是
该Graph,是否会在后续的过程中,被直接使用多次,包括迭代。
如果会,那么这个Graph就要被Persist,然后通过action触发
如果不会,那么反过来,最好把这个Graph直接unpersist掉
一个Graph被Cache的话,一般最终体现为2个RDD的Cache,一个是Edge,一个是Vertex,其占用量是非常巨大的。在整体空间有限的情况下,cache会导致内存的使用量大大加剧,引发多次GC和重算,反而会拖慢速度。在QQ全量的关系链计算,一个全量图是非常大的,因此如果在一个图没被多次使用,那么先unpersist,再返回给下一个计算步骤,反而成了最佳实践。
示例代码如下:
val oneNbrGraph = computeOneNbr(originalGraph) oneNbrGraph.unpersist() val resultRdd = oneNbrGraph.triplets.map { ………… }
当然,既然unpersist了,切记 它只能被再用一次了。经过反复多次优化之后,在高配置集群的资源充足情况下,使用如下配置项:
|配置项|配置值| |---|---| |executors | 360 | |executor-cores | 2 | |executor-memory | 50g | |并行度 | 10000 |
总共消耗18T的内存,可以在2个半小时左右,完成整个QQ关系链的计算。BTW:
整个的优化过程,貌似风轻云淡,但是中间经过了反复调优,多次在0.1的抽样数据和1.0的全量数据之间切换,优化每一步的操作,将硬件和GraphX的性能压榨到极致,才最终得到这个结果。
在这个过程中,我们发现无论应用层再怎么优化,核心层的软肋,始终制约着上层算法的性能。包括 Graph中最大限度的预创建和 RDD Cache的激进使用等问题,都会导致性能和稳定性不足,使得很多算法在腾讯级别的图数据下,显得捉襟见肘。其实这也难怪,GraphX的代码,从1.3版本开始,便已经一直没有变动,基本是在吃Core优化的红利,沾光提高性能,没有任何实质性的改进,如果要继续使用,在核心上必须有所提升才行。
腾讯作为拥有国内最大的关系链,在图计算的领域,无论是处于框架,模型,还是存储,都大有可为,可以做很多的事情。腾讯的数据平台部,作为公司的大数据支撑平台,欢迎在这方面有兴趣的业界同仁,和我们进行更多的合作和交流,共同在腾讯关系链上,玩出更多社交智能的火花。