写点什么

图计算之开局女朋友跑了

用户头像
Zhuan
关注
发布于: 19 小时前

前段时间,我大学室友的网恋女友被人拐走了。


恋爱谈着谈着,女友和半路杀出的王老五海誓山盟了,他还通过小红书路过了他们的婚礼,忍辱负重地刷出 666 的火箭。


我们说这家伙傻了,这种情况竟然没有直接冲上前去把那男的痛扁,如此自然地放下爱情,成全别人,绿帽侠见了都要甘拜下风。


这货反唇相讥,说“深圳”这个词的意思是深深的水沟,在深圳这条水沟里翻车,是上天在预示,他本非沟中物,他最终会游回大海,一遇风云化海王。


这话别人信没信我不知道,但这货跟我喝酒时,沟王的怂样真是让我气不打一处来。


我抓起他的酒杯,“兄弟,成为海王的第一步是什么?”


他抬起头,可怜兮兮地望着我。


我用图关联关系分析系统做了一个模型。

 

为什么是图关联分析系统,因为图数据是大数据发展的新热点。近年来,全球大数据进入加速发展时期,数据量呈现指数级爆发式增长,而这些大量数据中不同个体间交互产生的数据以图的形式表现,如何高效地处理这些图数据成为了业界及其关心的问题。很过用普通关系数据无法跑出来的结果,用图数据进行关联分析会显得异常高效。

 

提到处理图数据,我首先想到 NetworkX,这是网络计算上常用的 Python 包,可提供灵活的图构建、分析功能。但是我使用 NetworkX 跑大规模图数据时,不仅经常碰到内存不足的问题,而且分析速度很慢,究其原因,是 NetworkX 只支持单机运行。通过网上搜索,发现最近有一个名为 GraphScope 的系统不仅号称兼容 NetworkX 的 API,而且支持分布式部署运行,性能更优。这激起了我的好奇。

 

为了能够让我在抓取室友的潜在对象时能够飞快地分析与判断这妞有没有可能成为我兄弟的光、电和唯一的神话,同时出于对 GraphScope 图分析引擎的好奇,针对 GraphScope 和 NetworkX 的处理能力,我参考图计算中常用的测试框架 LDBC,通过一组实验来对比二者的性能。 

 

实验介绍

 

为了比较两者的计算效率,我用阿里云拉起了配置为 8 核 CPU,32GB 内存的四台 ECS,设计了三组比较实验,分别是 NetworkX 单机下的计算性能,GraphScope 单机多 worker 的计算性能以及 GraphScope 分布式多机多 worer 的计算性能。

 

数据上,我选取了 SNAP 开源的图数据集 twitter,来自 LDBC 数据集的 datagen-7_5-fb,datagen-7_7-zf 和 datagen-8_0-fb 作为实验数据,以下是数据集的基本信息:

· Twitter: 81,307 个顶点,1,768,135 条边

· Datagen-7_5-fb: 633,432 个顶点,34,185,747 条边,稠密图

· Datagen-7_7-zf: 13,180,508 个顶点,32,791,267 条边,稀疏图

· Datagen-8_0-fb: 1,706,561 个顶点,107,507,376 条边,这个数据集主要测试两个系统可处理的图规模能力

 

实验设计上我选择常用的 SSSP、BFS、PageRank、WCC 算法,以及较高复杂度的 All Pair shortest Path length 算法,以载图时间,内存占用和计算时间这三个指标为依据,对两个系统进行计算性能的比较。

 

NetworkX 是一个单机系统,在实验中只考虑 NetworkX 在单机环境下的运行时间;GraphScope 支持分布式运行,故进行两个配置,一个是单机 4worker,另外一个配置是 4 台机器,每台机器 4 个 worker。

 

实验结果

 

首先,GraphScope 的载图速度比 NetworkX 显著提升。

 

在前三个图数据集中,无论是 GraphScope 的单机多 worker 模式,还是 GraphScope 的分布式模式,载图速度都比 NetworkX 快:

 

GraphScope 单机模式载图速度平均比 NetworkX 快 5 倍,最高纪录——在 datagen-7_5-fb 上比 NetworkX 快了 6 倍。

 

分布式模式下 GraphScope 的载图时间比 NetworkX 平均快了 27 倍,最高纪录——在 datagen-7_7-zf 数据集上比 NetworkX 快了 63 倍。

 

在 datagen-8_0-fb 数据集上,NetworkX 因内存溢出无法载图,GraphScope 单机多 worker 和 GraphScope 分布式载图时间分别为 142 秒和 13.6 秒。

 

表一:载图时间对比


在 datagen-8_0-fb 数据集上,NetowrkX 在 32G 的内存上无法载完图,而 GraphScope 仅需要 24G 的内存即可载入在 datagen-8_0-fb 数据集。

 

表二:内存占用对比


再次,GraphScope 的计算速度比 NetworkX 显著提升。

SSSP 算法上,GraphScope 单机多 worker 模式平均要比 NetworkX 快 22 倍,最快在 datagen-7_7-zf 数据集上快了 32 倍。GraphScope 分布式模式下平均要比 NetworkX 快 103 倍,最快 datagen-7_5-fb 数据集上快了 182 倍。

 

表三: SSSP 计算时间对比(单位:秒)


BFS 算法上,GraphScope 单机多 worker 模式平均要比 NetworkX 快 13 倍,最快 datagen-7_5-fb 数据集上快了 22 倍。GraphScope 分布式模式下平均要比 NetworkX 快 16 倍,最快在 datagen-7_5-fb 数据集上快了 28 倍。

 

表四: BFS 计算时间对比(单位:秒)


PagerRank 算法上,GraphScope 单机多 worker 模式平均要比 NetworkX 快 62 倍,最快 twitter 数据集上快了 80 倍。GraphScope 分布式模式下平均要比 NetworkX 快 65 倍,最快在 twitter 数据集上快了 71 倍。

 

另外,Pagerank 计算过程中,NetworkX 在 datagen-7_7-zf 上内存溢出,没有完成计算,GraphScope 单机多 worker 模式和分布式模式计算时间分别为 25 秒和 22 秒;

 

表五:PageRank 计算时间对比(单位:秒)


WCC 算法上,GraphScope 单机多 worker 模式平均要比 NetworkX 快 44 倍,最快在 datagen-7_7-zf 数据集上快了 104 倍。GraphScope 分布式模式下平均要比 NetworkX 快 76 倍,最快 datagen-7_5-fb 数据集上快了 194 倍。

 

表六: WCC 计算时间对比(单位:秒)


在复杂度极高的 All pair shortest path length 算法上,NetworkX 在 twitter 图上即内存溢出,无法计算。GraphScope 在分布式模式下完成了 twitter 图的 All pair shortest path length 计算,耗时 76 分钟。

 

表七: All Pair Shortest Path Length(单位:秒)


总结

 

从实验结果可以看到,在同等条件下,无论在载图时间、内存占用和计算时间上,GraphScope 都要大大优于 NetworkX,性能优化可以达到几十倍甚至上百倍。

 

用在我的关联关系分析上也有同样的感受,我跑了 6 万条点和边,GraphScope 用 3 分钟左右就能跑出结果,而 NetworkX 耗费了 43 分钟,作为优秀且靠谱的数据科学家,我觉得 GraphScope 的处理能力挺让我惊喜。

 

我室友看蒙了。

这也正常,理工科才能改变世界。

我满意地点了点头。

我让他回去把小学一二年级开始,聊过天的女生全记下来;再找到她们的微博,把她们玩得来的、艾特过的女生再联系一波。我就不信了,这么多年的邻居、同学、同事加一起,还跑不出哪个妞会成为下一个女友的规则了。

 

室友轻咳了一声。

 

“说实话,你有过多少对象?”

 

我抬头,好整以暇地整理好新做的发型,表示这单得他买。

用户头像

Zhuan

关注

嘿!哈! 2021.06.19 加入

还未添加个人简介

评论

发布
暂无评论
图计算之开局女朋友跑了