使用Spark图计算研究QQ千亿社交网络

《使用Spark图计算研究QQ千亿社交网络》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、使用Spark图计算研究QQ千亿社交网络嘉宾：黄俊腾讯社交网络•全球第二大社交网络公司•千亿社交关系链MostfamoussocialnetworksitesworldwideasofSeptember2016rankedbynumberofactiveusers(inmillions)腾讯图计算面临的问题关系链与节点关联计算慢•千亿关系链,存储量1.6T•任意和节点的关联操作可能导致数据膨胀常见图算法不易实现•大量图算法算法复杂度高•低复杂度算法需要重复多次迭代计算共同好友•问题:统计用户和好友的共同好友个数Commo

2、nFriendsbetweenNode_6andNode_5is4•目的:刻画用户间关系紧密程度的基础指标–广泛用于包括:陌生人/熟人分析,好友推荐,社团划分难点在哪?•中间数据膨胀–人均100好友计,需要至少160T以上空间•网络结构引出数据倾斜–用户在好友列表出现的次数(入度)存在幂律尾1.00E+091.00E+081.00E+071.00E+061.00E+05#ofUser1.00E+041.00E+031.00E+021.00E+011.00E+00110100100010000100000100000010

3、0000001000000001E+09InDegree计算方案•Phase1:统计邻居列表•Phase2:计算共同好友控制数据膨胀•利用GraphX图存储特性减少邻居表复制–节点属性(用户邻居)和边数据分别存储–遍历边时通过路由表(RoutingTable)获取节点邻居–一个用户在一个分区只需要复制一份邻居列表http://spark.apache.org/docs/latest/graphx-programming-guide.html定制化集群•大内存集群–节点所在边越分散,节点属性需跨机器获取–尽量让一个用户的所

4、有边都在同一个机器ConfigurationMachines180Executors360Executor-Cores2Executor-Memory60G(IncludeOverhead)Parallelism10000ExecuteTime2H10M优化项运行参数•spark.network.timeout=6000s•spark.yarn.executor.memoryOverhead=4096算法参数•StorageLevel.MEMORY_AND_DISK•PartitionStrategy.EdgeParti

5、tion2D算法优化•压缩存储邻居表共同好友–推广•解决关系链与用户属性的关联计算–GraphX图存储特性控制数据膨胀–定制化大内存集群•同样的系统可以解决类似的问题–好友列表可以扩展为任意的用户属性–例如:在玩游戏列表,兴趣向量•实现小时级的千亿关系链计算六度分离理论•Karinthy的<枷锁(Chains)>–两个完全陌生的人可以通过不超过五个人产生联系•Milgram的六度分离–任意两个陌生人只需要5.7个中间人就能互相认识社交平均距离•社交平均距离宏观刻画了社交网络用户的联系紧密程度社交网络的平均距离是指任意两个

6、用户的最短距离的均值.两个用户的最短距离是指连接他们的路径的最小关系链数•A和B需要5个用户介绍认识,最短距离为6.HyperANF算法1.每个节点存储一个”通讯录”,先记上自己的id2.每个节点给邻居发送自己的“通讯录”–邻居把得到的”通讯录”求并集,上面的人和自己距离≤1–更新自己的”通讯录”3.每个节点再给邻居发送自己的“通讯录”–继续做并集,这时”通讯录”上面的人和自己距离≤2–再次更新4.以此迭代,直到每个用户的”通讯录”包含了全网用户5.用户比较两次”通讯录”的变化,可以知道距离自己为k(迭代值)的用户数Bo

7、ldiP,RosaM,VignaS.HyperANF:Approximatingtheneighbourhoodfunctionofverylargegraphsonabudget“通讯录”的表示•HyperLogLogPlus计数器–add(Stringelement)•加入新元素到集合–count()•近似估计集合去重元素大小–merge(HyperLogLogPlusother)•返回两个集合的并集•特性–定长存储–结果只是近似值•不存储”通讯录”具体元素,用计数器替代http://static.googleuse

8、rcontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/40671.pdf算法实现使用Spark计算•整个算法可能需要数百轮迭代•缓存关系链避免重复I/O只更新有变化的节点•大量用户在开始几次迭代就已经认识