作者：Safiollah Heidari，Rajkumar Buyya
发表期刊：IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
发表日期：2021年8月
一、背景
1. 大规模图处理的重要性：随着数据量的快速增长和图处理任务复杂性的增加，传统的单机处理能力已经难以满足需求，云计算环境成为主要选择。
2. 云计算的潜力和挑战：图处理任务对资源需求具有显著的异构性（如计算密集型、内存密集型任务），现有的资源管理机制在满足性能需求的同时优化成本方面存在不足。
3. 资源异构性的影响：对于图处理任务，不同算法和操作对资源的需求各异（如邻居遍历需要高内存带宽，路径搜索可能需要更高的计算能力）。
4.自动扩展的重要性：现有的扩展算法通常未充分考虑任务负载的动态性以及云资源的异构特性，可能导致资源浪费或性能下降。
二、创新点
1.推动云环境中的大规模图处理应用：通过优化资源分配和自动扩展策略，解决了图处理任务在资源动态性和异构性上的关键难题，为社交网络分析、推荐系统和路由优化等实际应用提供支持。
2.降低云计算成本：在按需计费的云环境中，通过精准的负载预测和资源调度，显著减少了计算资源的浪费，为企业和研究机构降低了运行成本。
3.提升资源利用效率：考虑了云平台中异构资源的性能特性和成本差异，使计算、存储、通信等资源得到更高效的利用，优化了云平台的整体性能。
4.促进动态资源管理技术的发展：通过提出适应动态负载和异构资源的扩展算法，为自动扩展技术的研究和应用提供了新的方向。
三、自动扩展架构（Auto-Scaling Architecture）
Master节点（核心控制中心）：
- Monitoring Module（监控模块）：实时跟踪每台工作节点（VM）的状态。
- Decision-Making Module（决策模块）：根据监控模块收集到的指标，分析当前虚拟机（VMs）、网络和图本身的状态。制定扩展或缩减资源的策略。
- Partition Distributor Module（分区分配模块）：根据决策模块的策略，将图数据的不同分区分配到可用的VMs上，按照计算策略分配任务，以实现负载均衡和高效计算。
四、基于特性动态重新分区的算法
全局同步发生时的调整策略：
场景1（第8-10行）：
如果两个分区（P1和P2）的大小之和小于某个小型VM的内存容量：将P1和P2合并到该小型VM中，释放当前占用的VM。
场景2（第11-13行）：
如果P1和P2的大小适合当前VM（但太大以至于不能放入小型VM）：将P1和P2合并到当前VM，释放当前VM中无用的资源。
场景3（第14-16行）：
如果P1的大小适合与相邻分区一起放入某些相邻VM：将P1迁移到这些相邻VM中，释放P1当前所在的VM。
基于优先级调整资源分配：
设置优先级：
使用计算得到的PP和WP为分区和工作节点设置优先级。
增减VM：
如果任务负载变重，可以增加VM；负载减轻时，减少VM以节省成本。
重新映射分区和工作节点：
根据优先级将分区分配给合适的工作节点。
五、实验及结果
实验环境：
实验在模拟的云环境中进行，该环境支持异构虚拟机（VMs），以体现真实云资源的特性。
配置了多种类型的VM实例：
m1.large：高性能计算型实例，适用于高计算任务，成本较高。
m2.medium：平衡型实例，适合多任务并行处理。
m1.small：轻量型实例，适用于轻负载任务，成本较低。
模拟异构资源特性，包括不同VM的：
CPU计算能力。
内存容量。
网络带宽和延迟。
数据集：
实验结果：
在不同数据集上处理最短路径算法的总执行时间
处理连接组件算法在不同数据集上的总执行时间
与其他框架相比，iGiraph-Heterogeneity-aware 在大规模图处理任务中完成时间更短。分区算法减少了高通信负载的分区分配到低性能机器的情况。高效分区分配策略有效利用了异构资源的特性。分区策略考虑了分区特性和机器性能，减少了通信开销和资源浪费。
不同框架下单源最短路径（SSSP）的处理成本
连通组件（CC）在不同框架上的处理成本
在所有数据集上，iGiraph-Heterogeneity-aware 的处理成本最低。
Twitter 数据集的处理成本下降尤为显著，SSSP：成本从 $8.84（Giraph） 降低到 $3.303（iGiraph-Heterogeneity-aware），降幅约 62.6%。CC：成本从 $8.5（Giraph） 降低到 $3.43（iGiraph-Heterogeneity-aware），降幅约 59.6%。
六、总结
该论文提出的iGiraph-Heterogeneity-aware框架通过动态扩展和分区优化实现了大规模图处理的高效性和成本节约，尤其适用于以货币成本为优先的公有云应用场景。