Highly Scalable Graph Processing

图数据在许多应用中变得越来越重要，因为图自然地建模复杂的结构，显式地表示由顶点表示的实体之间的关系。一种特定类型的图已经增加了重要性并提出了特别的挑战，即事务图，其中每条边表示由顶点表示的实体之间的事务。一个常见的例子是产品图，其中顶点表示客户和目录项目，并且每条边表示用户操作(例如，购买项目、喜欢项目、将项目放入购物车)。这些图表上的操作和实时分析的实时处理是一个重要的问题，也是这项发现拨款提案的主题。这些图形可以非常大且非常动态，并以高速添加边。例如，阿里巴巴报告称，他们维护着具有数十亿个顶点(代表客户和目录项目)和超过1000亿条边(代表点击、添加到购物车、订单等行为)的图表。这些是流图，其中(通常)边从一个或多个源流传送到一个或多个处理节点。这些图表的流速率非常高-阿里巴巴报告的峰值速率为32万笔交易(边)/秒-这带来了巨大的处理挑战。这些图表上的工作负载有两种类型：事务型(例如，一旦边到达就对表示购买的边进行操作-称为在线事务处理或OLTP)和分析型(例如，基于最近的用户活动的推荐-通常称为在线分析处理或OLAP)。目前的技术水平是使用不同的系统处理这两个工作负载，但组织表示非常希望能够在单个图形上处理单个系统中的这两个工作负载。我研究的长期目标是研究在具有非常高的流速率的非常大的流图上处理OLTP和OLAP工作负载的体系结构和技术。在这个大的框架内，我打算研究以下具体问题：1.流图的连续处理。主要目标是研究能够处理大型流图上的大量持久OLTP查询的健壮系统架构。2.流图上的窗口图分析。目标是研究处理流图上的OLAP工作负载的机制，这是很困难的，因为这些是迭代的，需要多次遍历数据。我们将研究窗口处理技术，以补充针对OLTP工作负载采用的连续处理。3.图形处理的硬件辅助。其目标是研究在统一架构(CPU+GPU+FPGA)中使用GPU和FPGA来协助高流速率下的大容量OLTP和OLAP处理。

Graph data are of growing importance in many applications, because graphs naturally model complicated structures with explicit representation of the relationships among entities represented by the vertices. One particular type of graph that has increased in importance and poses particular challenges is transactional graphs where each edge represents a transaction between entities represented by the vertices. A common example is a product graph where the vertices represent customers and catalog items and each edge represents a user action (e.g., buying an item, liking an item, putting an item in the shopping cart). Real-time processing of actions and real-time analytics on these graphs is an important problem, and the subject of this discovery grant proposal. These graphs can be very large and very dynamic with edges added at high speed. For example, Alibaba has reported that they maintain graphs with several billion vertices (that represent customers and catalog items) and in excess of 100 billion edges (that represent behaviours such as clicks, adding to shopping cart, orders, etc). These are streaming graphs where (typically) edges are streamed from one or more sources to one or more processing nodes. The streaming rate of these graphs are very high - Alibaba reports peak rates of 320k transactions (edges)/sec - raising significant processing challenges. The workloads on these graphs are of two types: transactional (e.g., acting on an edge that represents a purchase as soon as the edge arrives - what is known as On-line Transaction Processing or OLTP) and analytical (e.g., recommendation based on recent user activity - what is usually referred to as On-line Analytical Processing or OLAP). The current state-of-the-art is to handle these two workloads using separate systems, but organizations have expressed a great desire to be able to process both workloads within a single system over a single graph. The long-term objective of my research is to study architectures and techniques to process OLTP and OLAP workloads on very large streaming graphs with very high streaming rates. Within this broad framework, I intend to study the following specific problems: 1.Continuous processing of streaming graphs. The primary objective is to investigate robust system architectures that can process a large number of persistent OLTP queries on large streaming graphs. 2.Windowed graph analytics over streaming graphs. The objective is to investigate mechanism for processing OLAP workloads on streaming graphs, which is difficult because these are iterative requiring multiple passes over data. We will investigate windowed processing techniques to complement continuous processing adopted for OLTP workloads. 3.Hardware assist for graph processing. The objective is to study the use of GPUs and FPGAs in a unified architecture (CPU+GPU+FPGA) to assist high volume OLTP and OLAP processing under high streaming rates.