Simba: Spatial In-Memory Big data Analytics

abs

大型空间数据变得无处不在。因此，为基于位置的服务（LBS）的众多应用提供快速、可扩展和高吞吐量的空间查询和分析至关重要。传统的空间数据库和空间分析系统是基于磁盘的，并为IO效率而优化。但是，越来越多的数据被存储和处理在内存中以实现低延迟，CPU时间成为新的瓶颈。我们提出了Simba（空间内存大数据分析）系统，该系统为大空间数据提供可扩展和高效的内存空间查询处理和分析。Simba以Spark为基础，在一个商品机集群上运行。特别是，Simba扩展了Spark的SQL引擎，通过SQL和DataFrame API支持丰富的空间查询和分析。**它在RDDs上引入了索引，以便处理大空间数据和复杂的空间操作。**最后，Simba实现了一个有效的查询优化器，利用其索引和新的空间感知优化，以实现低延迟和高吞吐量。在大型数据集上进行的大量实验表明，与其他空间分析系统相比，Simba的性能更加优越。

intro

近年来，空间数据的数量激增。智能手机上的移动应用和各种物联网（IoT）项目（如智能城市的传感器测量）产生了大量的空间维度的数据。更重要的是，空间维度在这些应用中经常发挥重要作用，例如，用户和司机的位置是Uber应用最关键的特征。如何以低延迟和高吞吐量来查询和分析这样的大型空间数据是一个基本的挑战。大多数传统和现有的空间数据库和空间分析系统都是面向磁盘的（例如Oracle Spatial、SpatialHadoop和Hadoop GIS[11, 22]）。由于它们已经针对IO效率进行了优化，在扩展到大型空间数据时，其性能往往会恶化。

如今，实现低延迟和高吞吐量的一个流行选择是在商品机集群上使用内存计算。像Spark[38]这样的系统通过使用分布式内存存储和计算提供低查询延迟和高分析吞吐量，在大数据处理方面取得了巨大成功。最近，Spark SQL[13]通过类似SQL的查询接口和DataFrame API对Spark进行了扩展，以对不同的底层数据源（例如来自DFS的数据）进行关系处理。这样的扩展提供了有用的抽象，以支持在分布式内存空间上进行简单和用户友好的大数据分析。此外，SQL的声明性也为查询优化提供了丰富的机会，同时极大地简化了终端用户的工作。

然而，现有的分布式内存查询和分析引擎，如Spark、Spark SQL和MemSQL，都没有为空间查询和分析提供本地支持。为了使用这些系统来处理大量的空间数据，人们必须依靠UDFs或用户程序。由于UDF（或用户程序）位于查询引擎内核之外，底层系统无法优化工作负载，这往往导致查询评估计划非常昂贵。例如，当Spark SQL通过UDF实现空间距离连接时，它必须使用昂贵的cartesian product方法，而这种方法对于大数据来说是不可扩展的。

在这些观察的启发下，我们设计并实现了Simba（空间内存大数据分析）系统，它是一个分布式内存分析引擎，支持对大空间数据的空间查询和分析，其主要目标是：简单而富有表现力的编程接口、低查询延迟、高分析吞吐量和出色的可扩展性。特别是，Simba有以下明显的特点。

• Simba用一类重要的空间操作扩展了Spark SQL，并在SQL和DataFrame API中为它们提供了简单而富有表现力的编程接口。

• Simba支持对RDD（弹性分布式数据集）进行（空间）索引，以实现低查询延迟。

• Simba设计了一个SQL上下文模块，可以并行地执行多个空间查询，以提高分析吞吐量。

• Simba为逻辑和物理优化器引入了空间感知优化，并使用基于成本的优化（CBO）来选择良好的空间查询计划。

由于Simba是基于Spark的，它继承并扩展了Spark的容错机制。与依赖UDFs支持空间查询和分析的Spark SQL不同，Simba在其索引支持、查询优化器和查询评估器的帮助下支持此类操作。由于这些模块是为空间操作量身定做的，因此Simba在回答空间查询和分析大型空间数据方面实现了出色的可扩展性。

5 INDEXING

索引对于空间查询和分析的有效处理非常重要，特别是对于多维数据和复杂的空间操作，如kNN和空间连接。特别是，索引是在Simba中建立一个有效的优化器的关键组成部分。由于Simba是一个内存分析引擎，减少磁盘IO不是索引的主要重点。相反，Simba利用索引来减少查询延迟，并通过减少CPU成本来提高查询吞吐量。例如，在处理范围查询时，索引可以帮助Simba修剪不相关的RDD分区，为底层Spark引擎释放更多的CPU资源，从而提高查询吞吐量。

Simba直接在RDDs上建立（空间）索引，以加快查询处理速度。具体来说，表被表示为记录的RDD（即RDD[Row]）。因此，对表的记录进行索引就成为对RDD中的元素进行索引。然而，RDDs是为顺序扫描而设计的，因此随机访问非常昂贵，因为它可能成为RDD上的一次全扫描。一个额外的复杂性是，我们想在不改变Spark核心的情况下引入索引支持，原因在第3节中解释。为了克服这些挑战，我们通过引入一个名为IndexRDD[Row]的新抽象来改变索引表的存储格式，并采用两级索引策略，可以容纳各种索引结构来支持Simba中的不同查询。

IndexRDD 回顾一下，一个表中的记录被存储为Row对象（Row objects ），每个表被存储为一个包含多个分区的Row的RDD。为了增加对表的索引支持，我们将RDD分区中的所有记录（即Row对象）打包成一个数组，这就给每个记录一个唯一的下标作为其索引。这样的改变使得RDD分区内的随机访问成为一个有效的操作，成本为O(1)。为了在Simba中实现这一点，我们引入了IPartition数据结构，如下所示。