主内存数据库中的高性能基于位置的服务外文翻译资料

英语原文共 30 页，剩余内容已隐藏，支付完成后下载完整资料

主内存数据库中的高性能基于位置的服务

——Suprio Ray 1＆Rolando Blanco 2＆Anil K. Goel 2

Received: 12 January 2016 /Revised: 13 July 2016

Accepted: 25 October 2016

Springer Science Business Media New York 2016

摘要：随着移动设备的广泛应用和时空数据的爆炸性增长，基于位置的服务（LBS）已经成为我们日常生活中不可或缺的技术。 LBS应用程序的关键特征包括高速率的时间戳位置更新，以及许多并发的历史，现在和预测性查询。 LBS的商业提供商必须支持所有三种查询，并解决高更新率问题。虽然他们为此目的使用关系数据库，但传统数据库无法应对许多LBS系统日益增长的需求。对这些数据库中的时空索引的支持仅限于基于R-tree的方法。虽然研究界提出了一些先进的时空指标，但其中只有少数支持历史查询。这些索引技术支持历史查询，无法在LBS中维持较高的更新和查询吞吐量。涉及越来越大的主要记忆和不断增长的处理核心数量的技术趋势为解决其中一些问题提供了机会。我们提出了几个关键的想法，通过利用内存数据库技术来支持高性能商业LBS。利用现代机器中可用的非常大的内存，我们的系统在内存中维护过去N天的位置数据和索引。较旧的数据和索引保存在磁盘中。我们提出一个内存存储组织来实现高插入性能。我们还引入了一个新颖的时空索引，其维持版本化网格结构中的部分时间索引。部分时间索引被组织为压缩位图。通过广泛的评估，我们展示了我们的系统支持高插入和查询吞吐量，并且显着优于领先的LBS系统。

关键词 基于位置的服务、LBS、主内存数据库、时空指数

1.背景介绍

支持GPS的移动设备和传感器的激增使基于位置的服务（LBS）成为突出的技术。地理空间Web服务（如Google Maps）也在推广LBS应用程序中发挥了作用。 LBS作为移动资产跟踪的启用技术开始成为一系列新兴应用的推动力，如基于位置的游戏和社交网络，位置感知搜索和个性化广告和天气服务。因素的结合，包括移动设备的扩散和新兴应用的兴起，导致了时空数据的快速增长。除数据量外，LBS工作负载也显示Bvelocity的数据。 LBS应用程序的特征在于非常高的位置更新速率和许多并发的面向位置的查询。这些查询可以分为“历史”或“过去”查询，“现在”或“现在”查询以及“预测”或“未来”查询。 LBS的商业提供商必须支持所有三种查询，并处理高更新率。然而，由于客户群不断增长，许多客户无法通过现有技术来应对需求。

商业LBS产品需要满足多样化和经常冲突的功能。客户想要生成不同程度复杂性的报告。这些报告中的一些基于当前的查询或预测范围查询，而其他报告则根据过去的查询长时间运行历史报告。对于大型客户群，给定的LBS系统中的查询工作量可能很大。同时，服务提供商必须存储和有效地索引以非常高的频率接收到的位置更新。 Scaron;idlauskaset al。 [1]指出，这个速度可以容易地超过每秒100万或更多的位置记录更新。为了解决这个复杂的需求，商业LBS提供商依靠关系数据库来管理他们的数据。为了确定传统数据库在更新密集型时空工作负载下的运行情况，我们对LBS行业流行的关系数据进行了基准测试。如第3节所述，实现的最佳吞吐量约为50 K插入/秒，这在上下文中可以说很低。我们的目标是为全面的商业LBS系统构建数据库支持。为此，我们打算每秒支持100万个移动对象的数百万次更新，以及数千个并发的历史，现在和预测性查询。这提出了一些研究挑战，包括插入优化的数据库存储和高效的时空指标。

传统关系数据库的插入性能不足，即使数据库完全适用于内存。我们认为，为了满足基于位置的服务的性能需求，必须利用硬件和数据库技术方面的最新进展。现代服务器级机器具有较大的内存容量，有些则具有数百GB，甚至几TB的内存。每台机器配备了数十甚至数百个内核。数据库技术已经发展到利用丰富的内存和处理器能力，内存数据库是一个积极的研究领域。几个数据库供应商也有内存提供，如SAP HANA [2]和VoltDB [3]。关于主内存数据库存储设计，有一些可选的选项，如第2.1节所述。然而，我们认为可以实现比来自内存中行或柱状存储技术的插入吞吐量更好的插入吞吐量。位置记录更新是只插入操作。不需要从表中的随机位置删除记录。一个新记录可以随时插入表的末尾。要在表中插入新记录，必须获取新的记录标识（RID），这是每个记录的唯一标识符。这可以通过使用原子CPU指令递增RID计数器而不获取锁定来执行。此外，位置记录被存储而没有任何数据压缩，因为诸如字典编码的典型压缩技术对位置数据不是有益的。因此，可以避免压缩记录的相关成本。此外，与常规交易不同，位置更新不需要强大的一致性保证。即使错过了几个位置更新，也可能被认为是好的。

由于其在LBS应用中的重要性，索引移动物体一直是一个积极的研究领域。虽然已经提出了一些时空指标[4]，但大多数是基于B树或R树，因此它们受到潜在的限制。这些索引无法维持非常高的位置数据插入/更新率，并且这些索引中的大多数仅处理仅回答当前或预测性查询。只有少数人可以回答历史，现在和预测性查询。最近报道的支持历史和现在查询的LBS系统是MOIST [5]。 MOIST每秒可以实现8K 和60K的更新，一百个对象分别有一个和十个服务器。实现了基于内存的方法的潜力，最近提出了一种并行主内存移动对象索引技术[1]。它们通过利用高效的内存数据结构实现了良好的更新性能。然而，他们的系统被设计为仅支持当前查询，因为每个对象最多保留2个位置记录。因此，它不适合作为现实世界的LBS系统。为了提供商业LBS，必须保持每个对象的历史，并支持历史查询。我们提出了利用现代硬件资源的几个关键思想。它们概述如下：

1) 通过利用大容量存储容量，我们维护存储器中过去N（可配置）天的位置表数据和索引。 较旧的数据和索引维护在磁盘上。 我们还提出一种特别适合LBS的新型插入式高效主存储器。 我们的存储模型，列片段，通过创建允许在每个片段中无锁插入的B多项插入点来利用插入并行性。

2) 我们引入了一种新颖的并行内存空间时空指数，称为PASTIS（PArallel Spatio-Time-Index Index System）[6,7]。 PASTIS将空间域分解为网格单元，并且对于每个网格单元，维护访问单元的移动对象的部分时间索引。 这使得单独的线程可以同时处理不同网格单元的更新。 部分索引构造为压缩位图。 位图提供内存效率和快速按位操作。

3) 我们提出一种新颖的快速位图压缩技术。 虽然PASTIS可以使用诸如Wu等人提出的任何高级位图压缩技术。 [8]，我们的压缩位图提供的功能，如快速随机更新和逻辑位操作，非常适合我们的索引。

通过广泛的评估研究，我们证明我们的系统实现了出色的更新吞吐量（每秒更新数百万次），同时实现了非常好的查询执行吞吐量（每秒数千个查询）。例如，我们的系统每秒可以实现320万次的更新，其中100万个移动物体。我们系统的更新吞吐量明显优于报告的MOIST吞吐量和我们基准的关系数据库。本文的其余部分安排如下。相关作品在第2节中提到。在第3节中对具有LBS工作负载的传统数据库的性能进行了评估和讨论。我们在第5节中描述了第4节和系统组织中的设计注意事项。LBS和我们的空间的主内存存储的细节时间指数PASTIS分别在第6和7节。接下来，我们在第8节中介绍我们的压缩位图，并在第9节中讨论。我们描述第10节中的性能评估，结论在第11节。

2.相关作品

2.1主存储器

随着大型主机的出现，已经有一些项目涉及主内存数据库的存储组织。行存储数据库通常用于更新密集型工作负载，而面向列的数据库则用于分析工作负载。 SQL Server的OLTP引擎Hekaton [9]是面向行的主内存存储的一个例子。 IBM的Blink [10]也是一个行存储主内存数据库。 MonetDB [11]是第一个列存储数据库之一，它将主要内存中的中间结果实现。为了支持使用列存储的更新，除了读取存储之外，还会维护单独的写入高效存储。主内存列存储数据库C-Store [12]使用读优化存储（RS）和可写存储（WS），其中所有插入和更新由WS处理。数据由元组移动器的批量插入从WS移动到RS。 C-Store保留其数据，无需任何压缩。 SAP HANA是一个商业内存中的面向列的数据库，具有用于插入和更新的增量存储，以及支持分析查询的主存储[2]。三角洲商店中的记录定期合并到主商店。它使用字典编码来压缩数据。然而，数据的移动或合并过程是相对耗时的操作。我们将在第6节探讨LBS主存储器的设计空间，并提出一种称为列片段的插入式高效主存储器。

2.2时空指数

时空索引的主题已经通过大量研究来解决。 Spade [13]是一个众所周知的基准，用于比较一些这些指标。它们包括B 树方法，包括B x -tree [14]和B双重树[15]，基于树的索引，如RUM树[16]，TPR树[17]和TPR * -tree [18]和四叉树索引STRIPES [19]。这些方法可以根据是否支持对历史，现在，预测或过去，现在和未来的数据进行索引。 Nguyen-Dinh等提供对时空访问技术近期发展的综合调查[4]。已经提出的组合的时空访问方法可以大致分为三类：基于B树，基于R树和网格。 BB x -index [20]是一种B树技术，扩展了B x -tree [14]。 B x -tree将对象位置转换为一维空间填充曲线（SFC）代码，并使用B树对这些位置进行索引。 BB x -index维护一个B x -trees的森林，每个树分别是一个单独的时间戳间隔。在基于R树的技术中，HR-tree [21]是最早的。它为每个更新生成一个新的逻辑R树，这导致显着的空间使用和差的性能。 STR-tree [22]使用R-tree来索引以连接的线段表示的移动物体轨迹。然而，当轨迹很长时，这种方法表现不佳，这自然会随着时间的推移而发生。随后的工作，MV3R-tree [23]使用多个版本的R树，就像BB x -tree索引对于B x -trees一样。 R PPF -tree [24]是另一种基于R树的索引，其中两个连续样本之间的对象的过去位置被线性内插，并且部分持久性被应用于TPR树以捕获过去的位置。未来位置通过最后一个样本的线性函数获得。诸如BB x-index和MV3R-tree之类的索引使用版本化的数据结构。在索引时间数据的上下文中，已经提出了几个版本索引结构（例如，[25,26]）。 HV-tree [27]是最近的版本索引之一，它尝试优化内存层次结构的所有级别的性能，而不仅仅是两个级别。

由于B-tree和R-tree都是外部访问方式，因此在支持非常高的更新速率时，它们是不可扩展的。 由于需要不断维护目标结构，因此基于R-tree的方法尤其对于更新繁重的工作负载而言表现不佳。 另一方面，基于B树的访问方法比查询丰富的工作负载的R树更差，因为R树可以比B树更有效地修剪搜索空间。 由于涉及数百万移动对象和数千个同时查询的工作负载，两者都不能维持较高的吞吐量。

由于大型主机的可用性，最近的一些研究项目集中在内存索引技术上。 MOVIES方法[28]通过让查询在索引结构的只读副本上运行来实现并发查询和更新，但这需要频繁重建短命期数据结构。 Scaron;idlauskaset al。 [1]通过使用细粒度的并发控制机制来避免这个Bstop的世界问题。 但是，它们只支持当前查询（不是历史查询或预测查询），而MOVIES仅支持预测查询。

MOIST [5]是一个建立在键值存储上的自定义LBS系统。 它采用流量脱落和历史数据归档。 MD-HBase [29]是另一个在范围分区的键值存储上构建K-d树和四叉树索引的LBS基础设施。 它支持现在的范围查询。 我们的索引系统支持所有三种类型的范围查询，同时提供比这些方法更好的吞吐量。

3.问题描述

我们工作的上下文是传统的关系数据库与基于位置的服务（LBS）中典型的工作负载的性能。 商业LBS提供商需要处理一套复杂的需求，包括需要支持非常高的插入吞吐量和许多并发的时空查询。 在本节中，我们提供了两个开源关系数据库的详细评估和分析：MySQL和PostgreSQL。 此外，我们使用代码分析来确定性能瓶颈。

为了执行评估研究，我们生成了一个数据集，其中包含1000个记录，对应于在1000个时间戳期间为10,000个移动对象生成的位置记录。 该合成数据集由移动轨迹生成器MOTO [30]使用TIGER数据集[31]中的德克萨斯州的折线形状文件作为输入。 磁盘上的数据集大小为445 MB（如表1所示）。 为了进行实验，我们使用了具有16 GB RAM，8个3.0 GHz Intel Xeon CPU内核，6 MB缓存和880 GB 7200-RPM SATA磁盘的机器。 我们运行Ubuntu 10.04 Lucid。 在所有情况下，我们创建了一个数据库表位置（用于存储记录）以及空间索引，如果这样的索引由底层数据库引擎支持。

MySQL是非常流行的关系数据库，特别是与许多LBS提供商，因为它的高记录插入性能。 它提供了几个存储引擎的灵活性，其中MyISAM和InnoDB是最广泛使用的。 MyISAM支持基于R-tree的空间索引，不支持事务。

InnoDB另一方面支持交易，但它不支持空间索引。在LBS的上下文中，当数据集可以用空间索引索引（如R-tree）时，我们对MySQL的性能特别感兴趣。因此，进行了第一组实验以评估MySQL与MyISAM的插入吞吐

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[137621]，资料为PDF文档或Word文档，PDF文档可免费转换为Word