2021SC@SDUSC

图分割

一些高层次的理解有助于我们对可扩展性算法的设计和API的优化使用。当一个Graph 很大或者需要分布式运行时.需要对Graph进行划分。常用的划分方法有边分割与顶点分割， 如下图所示。

 

GraphX采用了顶点切分的方法来分布 图的划分，而不是使用边的切分。GraphX按照图中顶点的方式划分，能同时减少交互与 存储的开销。逻辑上，将边划分到不同机器， 并允许顶点跨越多台机器。边的具体分割方 法取决于Partitionstrategy。通过使用Graph. partitionBy方法，用户可以选择不同的划分策略对Graph重新划分。默认的分区策略是当Graph构造时提供的边的初始划分。用户可以方 便地切换到2D分区，如下图所示。

 

分区策略

Partitionstrategy中已经定义了一些分区策略，我们逐个来看：

(1 ) EdgePartition 1D

EdgePartition 1D仅使用源顶点的Vertexld分配边到分区，相同源顶点的边会被划分到一 个分区。其算法实现是将源顶点的Vertexld乘以mixingPrime这个很大的数，然后除以分区数，求余数，见下列代码清单。

case object EdgePartitionlD extends Partitionstrategy (
override de f getPartition (src: Vertexld, ds t: VertexI d, numParts: PartitionlD): PartitionlD = { val mixingPrime: Vertexld = 1125899906842597L (math.abs(src * mixingPrime) % numParts).tolnt

(2) EdgePartition2D

EdgePartition2D是一种二维分区策略，见代码清单10-26。其算法的步骤如下：

1. )求取小于分区数numParts的平方根的最小整数ceilSqrtNumParts;
2. )计算列号col ：计算源顶点Vertexld和mixingPrime的乘积除以ceilSqrtNumParts的 余数；
3. )计算行号row :计算目标顶点Vertexld和mixingPrime的乘积除以ceilSqrtNumParts的 余数；
4. )分区：由表达式(col * ceilSqrtNumParts + row) % numParts 决定。

   case object EdgePartition2D extends Partitionstrategy {
   
   override de f getPartitionfsrc: Vertexld, ds t:
    VertexId, numParts: PartitionlD): PartitionlD = (
   
   val ceilSqrtNumParts: PartitionlD = math.ceil(math.sqrt(numParts))
   .tolnt val mixingPrime: Vertexld = 1125899906842597L
   
   val col: PartitionlD = (math.abs (src * mixingPrime) % ceilSqrtNumParts)
    .tolnt val row: PartitionlD = (math.abs (dst * mixingPrime) % ceilSqrtNumParts)
    .tolnt (col * ceiLSqrtNuniParts +- row) % numParts
   
   }

(3 ) RandomVertexCut

RandomVertexCut通过对源顶点和目标顶点的Vertexld求取哈希值，然后除以分区数 numParts取余数，见下列代码清单。

case obj ect RandomVertexCut extends Partitionstrategy (

overr ide def getPartition (src: Vertexld, dst: VertexI d, numParts: PartitionlD): PartitionlD = ( math.abs((src, dst).hashCode()) % numParts }

}

(4 ) Canon i ca 1 Random VertexC ut

CanonicalRandomVertexCut是RandomVertexCut的升级版，需要判断源顶点和目标顶点的

 

大小，以不同的对偶顺序求取哈希值，最后除以分区数numParts取余数，见下面代码清单。

case object CanonicalRandomVertexCut extends Partitionstrategy 
( override def getPartition(src: Vertexld, dst: Vertex Id, numParts:

PartitionlD): PartitionlD = 
( if (src < dst) ( math.abs((src, dst).hashCode()) % numParts } 
else ( math.abs((dst, src).hashCode()) % numParts } } }