一、图数据划分
如同人们所熟知的数据组织方式会影响读写性能，图数据的划分和布局也会对后续的处理性能产生影响。当图的规模超过单个处理器核或单个计算节点的处理能力时，就需要对图进行划分。现有的分布式图计算系统通常将数据的划分简单地等同于任务的划分，其划分目标主要有两方面：一是划分的大小尽量均匀，避免负载不均衡；二是尽可能地减少通讯开销，跨分块的边尽量少。对于一般的图来说，图划分问题是一个NP-完全问题，在实际应用过程中都是采用近似算法来完成的。多级图划分是目前最常用的图划分算法，其基本想法是不断通过收缩顶点和边来粗化（coarsen）图的结构，规模较小时使用已有的较好的算法来做划分，之后再逐步把图还原成原来的样子，并不断优化（refine）划分。这样的算法既能保证较快的速度，也能提供很好的划分结果。这里划分结果好坏的评判是与计算过程密切相关的，同样的划分结果针对不同计算场景的表现有可能存在较大的差异，并不存在所谓“唯一最优”的划分方法或结果。现有的分布式图计算系统通常将数据的划分简单地等同于任务的划分，因此数据划分与编程模型直接相关，可粗略地分成以下几类：
此文由 怡心湖 编辑，若您觉得有益，欢迎分享转发！：首页 > 常识论 » 从数据划分到任务执行的分布式图数据计算简介