3 图计算
图计算主要指基于全图结构计算点边或点边子集属性的过程。如PageRank描述点的中心性，点边介数（Betweenness）则是描述点边的连通重要性。图计算可以作为对图查询的一个补充，图查询是直接获取关联的信息，而图计算的目标则是计算出基于关联结构蕴藏在点边中的信息，而且，图计算结果本身可以再存储到图数据库中作为图查询的查询目标。对于希望借力图计算提升业务效果的同行来说，重点要关注两个方面，首先是图计算的结果怎么用，其次是如何高效算出图计算的结果。
对于图计算能起到多大作用问题，难以一概而论。鉴于图计算任务大都是计算和资源均密集型的，明确图计算对业务助力的效果应该优于图计算在计算效率上的提升。 图计算算法可达数十种，每种有各自适用的场景。图计算的结果可以是点边具体的属性，如PageRank，Betweenness，置信度传播，聚集系数等等；也可以是点边子集所对应的属性或结构，如社区类的连通分量、图聚类、图分割、图染色等等，以及子图类的生成图、生成树、斯坦纳树、最大独立集、K-Core等等。图计算的结果确实在特定的场景下起到过非常关键的作用，如PageRank、斯坦纳树等，但在支付场景的欺诈人群识别实践中，基于资金网络得到的图计算结果对分类效果的支撑提升比较有限，离开特定的场景需求暴力使用图计算的结果难以达到预期的效果。
已有的图计算工作的宣传也侧重计算效率的提升，并没有很全面地解答图计算对业务的提升效果如何。例如，对于连通分量来说，作为经典的图计算的问题，在各大公司内部什么场景，起到多大的业务提升作用？如果存在图计算比较全面地、大幅地提升业务效果（不是效率）的案例，是不是应该有比较多关注图计算的同行已经周知？期待有相关经验的同行能够分享图计算针对业务大幅提升效果的成功案例，笔者也是在较长的一段时间里一直关注图计算在业务中的落地效果。结合自己的实践经验，确实看到过图计算对业务的一定程度的提升，但是提升幅度相比于图计算的投入成本而言，并未达到预期。因此，目前还在持续观察图计算是否能在业务上发挥更大的、更全面且更高效的作用。
图计算算法众多，但是大都可以通过传播迭代的方式实现目标的收敛计算。对于计算和资源均密集的图计算任务，如果直接计算精确的结果，对应的算法复杂度容易达到O(N^2) 甚至更高，在大规模图上计算的执行时间不可承受。已有的图计算系统主要是基于点中心框架的计算，通过定义单点的算子，来实现点粒度的并发，同时多次迭代来收敛至计算目标。类似于Hadoop/Spark生态对行的抽象：开发者只需要对行进行低代码量的开发就能够调度大规模的集群对大规模数据实现计算；点中心图计算则是对点的抽象：开发者仅需要开发基于点的低代码量的函数/算子，就能够调度大规模的集群对大规模图数据实现高效计算。
-
stage的划分是触发action的时候从后往前划分的，所以本图要从RDD_G开始划分。
-
RDD_G依赖于RDD_B和RDD_F，随机决定先判断哪一个依赖，但是对于结果无影响。
-
RDD_B与RDD_G属于窄依赖，所以他们属于同一个stage，RDD_B与老爹RDD_A之间是宽依赖的关系，所以他们不能划分在一起，所以RDD_A自己是一个stage1;
-
RDD_F与RDD_G是属于宽依赖，他们不能划分在一起，所以最后一个stage的范围也就限定了，RDD_B和RDD_G组成了Stage3;
-
RDD_F与两个爹RDD_D、RDD_E之间是窄依赖关系，RDD_D与爹RDD_C之间也是窄依赖关系，所以他们都属于同一个stage2;
-
执行过程中stage1和stage2相互之间没有前后关系所以可以并行执行，相应的每个stage内部各个partition对应的task也并行执行;
-
stage3依赖stage1和stage2执行结果的partition，只有等前两个stage执行结束后才可以启动stage3;
-
我们前面有介绍过Spark的Task有两种：ShuffleMapTask和ResultTask，其中后者在DAG最后一个阶段推送给Executor，其余所有阶段推送的都是ShuffleMapTask。在这个案例中stage1和stage2中产生的都是ShuffleMapTask，在stage3中产生的ResultTask;
-
虽然stage的划分是从后往前计算划分的，但是依赖逻辑判断等结束后真正创建stage是从前往后的。也就是说如果从stage的ID作为标识的话，先需要执行的stage的ID要小于后需要执行的ID。就本案例来说，stage1和stage2的ID要小于stage3，至于stage1和stage2的ID谁大谁小是随机的，是由前面第2步决定的。
Executor是最终运行task的苦力，他将Task的执行结果反馈给Driver，会根据大小采用不同的策略：
-
如果大于MaxResultSize，默认1G，直接丢弃;
-
如果“较大”，大于配置的frameSize(默认10M)，以taksId为key存入BlockManager
-
stage的划分是触发action的时候从后往前划分的，所以本图要从RDD_G开始划分。
-
RDD_G依赖于RDD_B和RDD_F，随机决定先判断哪一个依赖，但是对于结果无影响。
-
RDD_B与RDD_G属于窄依赖，所以他们属于同一个stage，RDD_B与老爹RDD_A之间是宽依赖的关系，所以他们不能划分在一起，所以RDD_A自己是一个stage1;
-
RDD_F与RDD_G是属于宽依赖，他们不能划分在一起，所以最后一个stage的范围也就限定了，RDD_B和RDD_G组成了Stage3;
-
RDD_F与两个爹RDD_D、RDD_E之间是窄依赖关系，RDD_D与爹RDD_C之间也是窄依赖关系，所以他们都属于同一个stage2;
-
执行过程中stage1和stage2相互之间没有前后关系所以可以并行执行，相应的每个stage内部各个partition对应的task也并行执行;
-
stage3依赖stage1和stage2执行结果的partition，只有等前两个stage执行结束后才可以启动stage3;
-
我们前面有介绍过Spark的Task有两种：ShuffleMapTask和ResultTask，其中后者在DAG最后一个阶段推送给Executor，其余所有阶段推送的都是ShuffleMapTask。在这个案例中stage1和stage2中产生的都是ShuffleMapTask，在stage3中产生的ResultTask;
-
虽然stage的划分是从后往前计算划分的，但是依赖逻辑判断等结束后真正创建stage是从前往后的。也就是说如果从stage的ID作为标识的话，先需要执行的stage的ID要小于后需要执行的ID。就本案例来说，stage1和stage2的ID要小于stage3，至于stage1和stage2的ID谁大谁小是随机的，是由前面第2步决定的。
Executor是最终运行task的苦力，他将Task的执行结果反馈给Driver，会根据大小采用不同的策略：
-
如果大于MaxResultSize，默认1G，直接丢弃;
-
如果“较大”，大于配置的frameSize(默认10M)，以taksId为key存入BlockManager
-
else，全部吐给Driver。
（编辑：柳州站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
