近年来,大规模图数据处理的需求日益强烈,一些图计算模型被提出,例如Pregel^[1]模型,GAS^[2,3,26]模型。它们可以分为离线和流式两类。流式图计算引擎有PHISH^[4,5],Flink^[6,7],但在工业界使用比较少。工业界常用的图计算引擎是离线方式的,例如Pregel,GraphLab^[8,9],GraphX^[10]。因此,如何在GraphX上实现一个流式图计算引擎具有实际应用价值。上述图计算引擎,包括GraphX,都基于一个假设,即计算节点的性能是相同的,并且图是平均分割的。但是,在企业环境中,一个集群中的计算节点性能会存在不平衡的情况。这时平均分割的图计算时间会被计算最慢的节点所制约。因此,研究在不平衡集群上基于流式的图计算模型的图分割算法具有现实意义。针对上述问题,本文以实验室承担的实际项目为背景,分析了不平衡集群上图分割算法需要考虑的因素,提出了一种针对不平衡集群的流式图分割算法,并在GraphX的基础上实现了一个流式图计算引擎。之后,本文比较了在点分割模型下不同流式图分割算法和本文提出的算法的表现,使用不同数据集,在不同集群大小、不同集群不平衡程度的集群上进行测试,证明了本文所提出算法在集群不平衡程度增大时,能较好地控制运算时间的增长。与其他同类系统相比,本文工作具有以下特点:1)已有的流式图分割算法主要有哈希分割、平衡分割、分块分割^[11,12]等,但它们都没有考虑集群不平衡性的问题。针对计算性能受最慢节点限制的问题,本文提出了一种基于不平衡集群的流式图分割算法PASGIC（Partitioning Algorithm for Streaming Graph on Imbalance Cluster）。该算法动态监测集群运算节点的CPU和内存变化等性能指标,根据这些指标,采用贪心策略来进行图的分割,让图计算引擎在计算每个迭代时,减少因为某些机器性能低下导致的整体计算时间延长。实验表明,相对于常用的随机和贪心图分割算法,PASGIC在不平衡集群上的处理速度要高出5%以上和16%以上。2)GraphX在工业界使用广泛,但不支持流式的图数据处理。本文对GraphX的运行模式和图分割方式进行了扩展,设计并实现了一个流式图计算引擎GraphA,并在该引擎上实现了PASGIC算法。该引擎具有自动探测集群不平衡性、根据不平衡性动态分割图、根据计算时间自动添加和释放计算节点资源等功能。实验表明,GraphA可以正确处理流式图数据,并对需要进行资源操作的预测召回率超过75%。3)在对流式图计算引擎的验证方面,目前缺乏对集群不平衡性度量指标。本文提出了一种度量集群不平衡性的指标体系。基于此指标体系,使用6个不平衡性不相同的集群和不同的数据集对GraphA引擎进行了验证。实验表明,GraphA能够根据集群的不平衡性对边进行合理的分割。