CRII: CSR: Partitioning Large Graphs in Deep Storage Architecture

许多对我们的社会很重要的计算应用，例如管理社会网络、分析人类基因组或模拟人类大脑连接，都严重依赖于大型图结构。在实践中，需要对大型图的表示进行分区并将其存储在机器集群中，以确保所需的响应时间和吞吐量。这种经典的跨服务器分区问题已经得到了广泛的研究，并且已经被证明是非常复杂的。此外，现代深度存储架构进一步复杂化了需要“跨层次”分区的问题，即将图放置到存储系统的不同层中。这一变化使现有的解决方案变得不足。本研究旨在寻求一种综合利用图结构和工作负载特征的方法，以在未来的深度存储架构中实现更好的分布式图表示性能。更具体地说，该项目包括两个协同研究任务，共同形成一个新的深度存储架构图分区解决方案。第一个任务是在线图放置算法，该算法可以根据精心设计的启发式评分将连续到达的图顶点和边即时分配到适当的服务器和特定的内部存储层。在第一个任务的基础上，第二个任务侧重于根据工作负载动态调整当前分区。这种调整基于一种新的提升/降级算法，该算法不仅可以提升/降级单个顶点，还可以根据马太效应改变其邻居的优先级。随着大型图结构的日益重要和新的存储技术的出现，现有的图存储系统在图分区方面面临着巨大的挑战。本研究的目标是在未来的存储架构中构建高效的分布式图形存储系统。此外，该项目将研究活动与教育和外联工作相结合，以培养具有广泛包容性和全球竞争力的科学劳动力。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many computing applications that are important for our society, e.g. managing social networks, analyzing human genomes, or modeling human brain connectivity, rely heavily on large graph structures. In practice, representations of large graphs need to be partitioned and stored on a cluster of machines to ensure the desired response time and throughput. Such a classic cross-server partitioning problem has been extensively studied and has been shown to be highly complex. Furthermore, modern deep storage architecture further complicates the problem with the need of "cross-hierarchy" partitioning, i.e., placing graphs into different layers of the storage systems. This change makes existing solutions inadequate. This research aims to pursue a holistic approach that exploits both graph structure and workload characteristics to achieve better performance for distributed graph representations in future deep storage architecture.More specifically, this project includes two synergistic research tasks, together forming a novel graph partitioning solution for deep storage architecture. The first task focuses on an online graph placement algorithm, which could instantly distribute the continuously arriving graph vertices and edges to proper server and specific internal storage layer based on an elaborate heuristic score. Building upon the first task, the second task focuses on adjusting current partitions dynamically according to the workloads. This adjustment is based on a new promotion/demotion algorithm that not only promotes/demotes a single vertex but also changes the priorities of its neighbors according to the Matthew Effect.With the increasing importance of large graph structures and the emergence of new storage technologies, existing graph storage systems experience significant challenges towards graph partitioning. This research effort aims towards building highly efficient distributed graph storage systems in future storage architecture. In addition, this project integrates the research activities with education and outreach efforts to train broadly inclusive and globally competitive science workforce.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.