Systems and Foundations For Massive-Scale Data Management

随着数据量的增长和新数据生成速度的提高，许多应用程序在高度并行的分布式数据管理系统上处理数据。本文主要从两个方面对分布式数据管理系统进行研究：(1)大规模数据管理系统的理论基础；(2)处理大规模图形数据的系统。在理论基础上，我的重点是理解分布式算法在回答关系数据查询方面的基本限制，并评估它们有多“好”。分布式算法在并行性水平、通信和计算成本以及它们所需的计算轮数（即机器同步）方面有所不同。我的目标是推导出在数据上执行任务的算法成本的下界或上界。具体来说，我打算研究两个问题：1。同步的能力：回答一个查询需要多少轮计算？2. 并行限制：可用于回答查询的最大机器数量是多少？在大规模图处理方面，我的重点是通用分布式图系统。大规模图形是许多应用程序的核心，例如web搜索、社交网络和遗传分析。总的来说，这些应用程序在图上执行以下任务：(1)批处理图算法；(2)机器学习算法；(3)寻找子图；(4)实时分析，如果图形正在演变。现有系统支持其中的一个或两个任务。我的目标是构建一个支持所有这些任务的系统，并基于及时数据流（TD）执行模型。TD是一个固有的流模型，它可以支持实时分析，但具有支持同步和异步计算的机制，可以支持批处理图算法、机器学习算法和子图查找。具体而言，我打算研究以下几个问题：1。通用图系统的TD算子。2. 查询语言和api可以有效地编译成这些TD操作符。3. 在有限的集群内存下高效的存储模型。4. 用于测试和调试运行在TD上的图形应用程序的工具。这项工作将为大规模数据处理建立理论基础，并产生一个开源原型系统，推进大规模图形处理的艺术状态。

As the volume of data grows, and the speed of new data generation increases, many applications process their data on highly-parallel distributed data management systems. The objective of this proposal is to study distributed data management systems with a focus on two areas: (1) theoretical foundations of massive-scale data management systems; and (2) systems for processing large-scale graph data.On theoretical foundations, my focus is on understanding the fundamental limitations of distributed algorithms for answering queries over relational data and evaluate how "good" they are. Distributed algorithms differ in their parallelism levels, communication and computation costs, and the number of rounds of computation, i.e., machine synchronizations, they require. My goal is to derive lower or upper bounds on the costs of algorithms that perform a task over data. Specifically, I intend to study two questions: 1. Power of synchronization: How many rounds of computation are needed to answer a query? 2. Limits of parallelism: What is the maximum number of machines that can be utilized to answer a query?On large-scale graph processing, my focus is on general-purpose distributed graph systems. Large-scale graphs are at the core of many applications, such as web search, social networks, and genetic analysis. Broadly, these applications perform the following tasks on graphs: (1) batch graph algorithms; (2) machine-learning algorithms; (3) finding subgraphs; and (4) real-time analysis if the graph is evolving. Existing systems support one or two of these tasks. My goal is to build a system that supports all of these tasks and is based on the timely dataflow (TD) execution model. TD is an inherently streaming model, which can support real-time analysis, but has mechanisms to support synchronous and asynchronous computations, which can support batch graph algorithms, machine-learning algorithms and subgraph finding. Specifically, I intend to study the following issues: 1. TD operators of a general-purpose graph system. 2. Query languages and APIs that efficiently compile to these TD operators. 3. Storage models that are efficient under limited cluster memory. 4. Tools for testing and debugging graph applications running on TD.This work will establish theoretical foundations for massive-scale data processing, and produce an open-source prototype system advancing the state of the art in large-scale graph processing.