CRII: CSR: Partitioning Large Graphs in Deep Storage Architecture

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

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.