MD-HBase: A Scalable Multi-dimensional DataInfrastructure for Location Aware Services

MD-HBase：定位感知服务的可扩展多维数据基础设施

• 摘要
• 1.介绍
• 2.背景
• • A.基于位置的应用程序
  • B.线性化技术
  • C.多维索引结构
• 3.多维索引层
• • A.最长公共前缀命名方案
  • B.索引层
  • C.索引层实现
• 4.数据存储层
• • A. HBase概述
  • B.存储层的实现
  • C.优化
• 5.实验评估
• • A.插入吞吐量
  • B.范围查询
  • C. kNN查询
• 6.相关工作
• 7.结论

摘要

位置启用设备的无处不在导致了基于位置的应用程序和服务的广泛扩散。为了处理日益增长的数据规模，驱动这种基于位置的服务(LBS)的数据库管理系统必须应对数百万设备的位置更新的高插入率，同时支持对最新位置的高效实时分析。传统的DBMS具有多维索引结构，能够高效地处理时空数据。然而，流行的开源关系数据库系统被高插入率、实时查询需求和这些系统必须处理的TB的数据所淹没。另一方面，Key-value存储可以有效地支持大规模操作，但不支持支持LBS所必需的丰富查询功能所需的多属性访问。我们提出了MD-HBase，一个可扩展的LBS数据管理系统，它弥补了规模和功能之间的差距。我们的方法利用建立在键值存储上的多维索引结构。底层的键值存储允许系统保持高插入吞吐量和大数据包，同时确保容错和高可用性。另一方面，索引层允许有效的多维查询处理。我们提出了MD-HBase的设计，它在一个范围分区的键值存储上构建了两个标准索引结构-K-d树和Quad树。我们的原型实现使用HBase，一个标准的开源Key-value存储，可以使用一个适度的16个节点集群每秒处理数十万个插入，同时高效地实时处理多维范围查询和最近邻居查询，响应时间低至数百毫秒。
关键词：基于位置服务；键值存储；多维数据；实时分析；

1.介绍

在过去几年里，手持设备有了显著的增长，使人们了解其位置，并有可能不断报告用户的最新位置信息。这导致了大量基于位置的服务(LBS)，它们根据位置定制用户的体验。一些应用程序-如基于用户当前位置和历史的定制推荐和广告-具有即时的经济激励，而另一些应用程序-如基于位置的社交网络或位置感知游戏-则丰富了用户的一般体验。主要的无线服务提供商服务了数亿用户，数以百万计的设备不断地注册它们的位置更新是相当常见的。因此，驱动这些基于位置的服务的数据管理系统(DBMS)必须每分钟处理数百万个位置更新，同时回答驱动不同推荐和个性化服务的近实时分析和静态查询。
位置数据本质上是多维的，最小包括用户id、纬度、经度和时间戳。丰富的多维索引技术文献-例如，K-d树[2]、四叉树[3]和R-树[4]-增强了关系数据库(R DBMS)的能力，以有效地处理多维数据。然而，这些基于位置的服务面临的主要挑战是扩展系统，以维持高吞吐量的位置更新，并分析大量的数据以收集情报。例如，如果我们只考虑插入吞吐量，那么安装在商品服务器上运行的My SQL在每秒数万个插入的负载下就会变成瓶颈；并发回答查询时，性能会受到不利影响。高级设计，如将数据库分期、定义视图、数据库和应用程序分区以扩展、分布式缓存或移动到商业系统，将提高吞吐量；然而，这种优化对于设计、部署和维护是昂贵的。
另一方面，Key-value存储，包括Bigtable[5]等内部系统和HBase[6]等开源系统，已经证明可以扩展到数百万次更新，同时具有容错性和高度可用性。然而，Key-value存储并不支持高效的多属性访问，这是支持LBS所需的丰富功能的关键要求。在没有任何二次属性访问过滤机制的情况下，这种查询依赖于对整个数据的完全扫描。因此，Map Reduce[7]样式处理是分析键值存储的常用方法。即使认为Map Reduce框架提供了丰富的并行性，完全扫描也是浪费的，特别是当查询的选择性很高时。此外，许多应用程序需要基于用户当前位置的近实时查询处理。因此，基于用户陈旧位置的查询结果通常是无用的。因此，对周期性导入到数据仓库的数据进行批处理查询处理的设计不适合实时分析要求。
RDBMS为多维数据提供了丰富的查询支持，但不具有可伸缩性，而Key-value存储可以扩展，但不能有效地处理多维数据。我们的解决方案，称为MD-HBase，通过在Key-value存储上放置一个多维索引来利用两者的优点来弥补这个差距。我们使用线性化技术，如Z排序[8]将多维位置信息转换成一维空间，并使用范围分区的Key-value存储(HBase[6]在我们的实现中)作为存储后端。图1说明了MD-HBase的体系结构，显示了索引层和数据存储层。我们展示了这种设计如何允许标准的和经过验证的多维索引结构，如K-d树和Quad树，在键值存储的顶层，对基础存储的变化最小，对键值存储的操作的影响可以忽略不计。

底层的键值存储提供了维持高插入吞吐量和大数据包的能力，同时确保容错和高可用性。索引层允许对多维范围和最近邻查询进行有效的实时处理，这些查询包含基于位置的应用程序的基本数据分析原语。我们评估键值存储中数据存储层的不同实现，并评估与这些不同实现相关的权衡。在我们的实验中，MD-HBase在跨越16个节点的适度集群上每秒获得超过200K次插入，同时支持响应时间小于1秒的实时范围和最近邻查询。假设设备每分钟报告一次位置更新，那么这个小型集群可以处理1000到1500万个设备的更新，同时在基于MapReduce或Z曲线的查询处理实现中提供一到两个数量级的改进。此外，我们的设计没有引入任何可伸缩性瓶颈，因此允许实现根据基础键值数据存储进行扩展。
贡献：
1.我们提出了MD-HBase的设计，该设计使用线性化来实现可伸缩的多维索引结构，该结构位于范围划分的键值存储上。2.我们演示了如何使用此设计来实现K-d树和Quad树这两个标准的多维索引结构。3.我们提出了键值存储中存储层的三种替代实现，并评估了与每个实现相关联的权衡。4.我们使用综合生成的位置数据对原型进行了详细评估，并分析了MDHBase的可扩展性和效率。
组织。第二节提供了基于位置的应用程序，线性化技术和多维索引结构的背景知识。第三节描述了索引层的设计和实现，第四节描述了数据存储层的实现。第五部分通过比较不同的设计选择，对MD-HBase进行了详细评估。第六节概述了相关文献，第七节总结了本文。

2.背景

A.基于位置的应用程序

位置数据点是多维的，具有空间属性（例如经度和纬度），时间属性（例如时间戳）和实体属性（例如用户的ID）。不同的应用程序以各种方式使用此信息。我们提供了两个简单的示例，这些示例说明了使用位置数据提供位置感知服务。
应用1：基于位置的广告和优惠券分发：考虑一家餐饮连锁店（例如麦当劳），在接下来的一个小时内运行促销折扣来宣传新小吃，并希望散发优惠券以吸引目前在其分布在全国各地任何一家餐馆附近的顾客。 LBS提供商发出多维范围查询，以确定距离该连锁店中任何一家餐厅5英里范围内的所有用户，并将优惠券交付给其设备。在预算有限的情况下进行类似活动的另一种方法是将优惠券限制为仅最接近餐厅位置的100个用户。在这种情况下，LBS提供程序将发出最近邻居查询来确定用户。无论哪种情况，考虑到该餐厅连锁店在全国（或全球）的存在，此类查询所分析的数据量都是巨大的。
应用程序2：基于位置的社交应用程序：考虑一种社交应用程序，该应用程序通知用户他/她当前在附近的朋友。在这种情况下，LBS提供者在用户当前位置周围发出范围查询，并将用户的朋友列表与结果相交。同样，考虑到当前社交应用程序的规模，LBS提供商必须处理其数千万至数亿用户的数据，以便为遍布全国的用户回答这些查询。
位置信息具有两个重要特征。首先，它在空间和时间上都固有地倾斜。例如，与农村地区相比，城市地区更加密集，而学区和商务区在工作日密集，而住宅区在晚上和周末则密集。其次，时间维度可能是无限的，并且会单调增加。稍后我们将讨论这些特征如何影响许多设计选择。

B.线性化技术

线性化[9]是将多维数据点转换为单维的方法，并且是MD-HBase中索引层的关键。线性化允许利用一维数据库（在本例中为键值存储）进行高效的多维查询处理。空间填充曲线[9]是最流行的线性化方法之一。空间填充曲线以系统的顺序访问多维空间中的所有点。 Z曲线[8]是空间填充曲线的示例。 Z曲线松散地保留了多维空间中数据点的局部性，并且易于实现。
但是，仅线性化还不足以进行有效的查询处理。基于线性化的多维索引层虽然设计简单，但导致查询处理效率低下。例如，将线性化系统上的范围查询分解为几个线性化子查询。但是，在子查询的数量和假阳性的数量之间存在折衷。由于大量假阳性，线性子查询数量的减少导致开销的增加。另一方面，消除误报会导致子查询数量显着增加。此外，这种朴素的技术对于在许多现实生活中的应用中固有的偏斜效果不强。

C.多维索引结构

四叉树[3]和K-d树[2]是两种最流行的多维索引结构。他们以系统的方式将多维空间递归地划分为子空间，并将这些子空间组织为搜索树。四叉树沿所有维度将n维空间划分为2n个子空间，而K-d树则交替进行维分解。每个子空间对其中的数据点数都有最大限制，超出该限制后，子空间将被拆分。通常使用两种方法来分割子空间：基于特里的方法和基于点的方法[9]。基于特里的方法在一个尺寸的中点拆分空间，从而实现相等的尺寸拆分。而基于点的技术则将空间除以数据点的中位数，从而得到具有相同数量数据点的子空间。基于特里的方法可有效实施，因为它会产生规则形状的子空间。另一方面，基于点的方法对偏斜更鲁棒。
除性能问题外，基于树的Quad树和Kd树还具有允许将它们与Z曲线结合使用的属性。对四叉树或K-d树进行基于树的拆分会生成子空间，其中任何子空间中的所有z值都是连续的。图2提供了使用二维K-D树的示意图。使用四叉树的示例非常相似。不同的阴影表示不同的子空间，而虚线箭头表示z曲线遍历。显而易见，在任何子空间中，Z值都是连续的。该观察结果构成了MD-HBase索引层的基础。与基于线性化的索引结构或基于线性化值的B + 树索引相比，K-d和Quad树捕获数据分布统计信息。它们根据数据分布对目标空间进行分区，并限制每个子空间中的数据点数量，从而导致热点区域出现更多拆分。此外，四叉树和KD树保持原始空间中子空间的边界。这样可以对空间进行有效的修剪，并减少查询处理过程中误报的次数，因此对偏斜更鲁棒。而且，当执行用于kNN查询的最佳优先算法时，由于不规则子空间形状，因此不能使用基于B +树的最快实用算法。因此，MD-HBase使用这些多维索引结构，而不是基于线性化的简单一维索引。

3.多维索引层

现在，我们介​​绍MD-HBase中多维索引层的设计。具体来说，我们展示了如何使标准索引结构（如K-d树[2]和四叉树[3]）适合于分层放置在键值存储之上。索引层假定基础数据存储层存储按项的键排序的项，并对键空间进行范围划分。键对应于要索引的维度的Z值；例如位置和时间戳。我们使用基于树的方法进行空间分割。索引将空间划分为概念性子空间，这些子空间又映射到称为存储桶的物理存储抽象。索引层中的概念子空间与数据存储层中的存储桶之间的映射可以是一对一，多对一或多对多，具体取决于应用程序的实现和要求。我们为子空间开发了一种新颖的命名方案，以模拟基于树的K-d树和Quad树。这种命名方案称为最长公共前缀命名，它具有两个重要的属性，这些属性对于有效的索引维护和查询处理至关重要。下面讨论命名方案及其属性的描述。

A.最长公共前缀命名方案

如果将多维空间划分为大小相等的子空间，并且使用二进制值枚举每个维，则给定子空间的z曲线通过交织来自不同维的位来给出。图3说明了此属性。例如，子空间（00,11）的Z值表示为0101。我们用子空间中包含的点的Z值的最长公共前缀来命名每个子空间。

图4提供了一个在基于Trie的Quad树和Kd树中划分空间的示例。例如，考虑在2D空间上构建的四叉树。

图4（a）右上方的子空间由粗实线包围，由z值1100、1101、1110和1111组成，其最长公共前缀为11 ∗∗；该子空间因此命名为11 ∗∗。同样，用虚线包围的左下子空间仅包含0000，并将其命名为0000。现在考虑图4（b）中K-d树的示例。右半边的子空间用实线包围，用最长的公共前缀1表示，而左下角的由0000和0001组成的子空间称为000 *。此命名方案类似于前缀哈希树（PHT）[10]，它是分布式哈希表的一种变体。
MD-HBase利用了这种最长的通用前缀命名方案的两个重要属性。首先，如果子空间A包围子空间B，则子空间A的名称是子空间B的前缀。例如，在图4（a）中，包含0000-0011的子空间包围仅包含0000的子空间。子空间的名称00 *∗是后者名称0000的前缀。因此，在拆分时，可以根据拆分的维数附加位，从原始子空间名称派生新的子空间的名称。
其次，子空间名称足以确定所有维度上的区域边界。此属性源自以下事实：z值是通过交织来自不同维度的位来计算的，因此提高了范围查询的修剪能力。确定范围边界包括以下两个步骤：（i）提取名称，提取与每个维度相对应的位； （ii）通过为下限附加0和为上限附加1s来完成提取的比特，这两个边界值都包含在内。例如，让我们考虑图4（a）中的四叉树。用实线框包围的右上角的子空间命名为11。由于这是2D空间，因此垂直和水平尺寸的前缀均为1。因此，使用扩展规则，两个尺寸的范围均为[ 10,11]。推广到n维空间，四叉树在所有n维空间上划分一个空间，从而产生2n个子空间。因此，子空间名称中的位数将是维数的精确倍数。这确保了在步骤（i）中重建尺寸值将提供所有尺寸的值。但是，由于K-d树在其他维度上拆分，因此不能保证名称中的位数是维度数的倍数，在这种情况下，不同维度的前缀具有不同的长度。考虑图4（b）的Kd树示例，对于名为000 ∗的左下子空间，水平尺寸的前缀为00，垂直尺寸的前缀为0，因此水平尺寸的边界为[00， 00]，垂直尺寸为[00,01]。

B.索引层

索引层利用最长的公共前缀命名方案将多维索引结构映射到一维基底中。图5示出了四叉树分区空间到索引层的映射。 K-d树的映射技术类似。现在我们描述如何使用索引层来有效地执行一些常见操作，然后讨论用于索引维护的空间分割算法。

1）子空间查找和点查询：确定点所属的子空间构成点查询以及数据插入的基础。由于索引层包括子空间名称的排序列表，因此确定某个点所属的子空间非常有效。回想一下，子空间名称确定了子空间包围的区域的边界。搜索子空间会找到最大前缀与查询点的z值匹配的条目；该条目对应的最大值小于查询点的z值。因此，以二进制搜索算法的终止条件将精确匹配比较替换为前缀匹配比较的前缀匹配二进制搜索就足够了。算法1提供了用于子空间查找的算法。为了回答一个点查询，我们首先查找对应于该点的zvalue的子空间。然后在子空间映射到的存储桶中查询该点。

2）插入：插入新数据点的算法（如算法2所示）类似于点查询算法。它首先查找与该点所属的子空间相对应的存储桶，然后将数据点插入存储桶中。由于存储分区可以容纳的最大点数限制，因此插入算法会检查存储分区的当前大小，以确定是否需要拆分。分割子空间的技术在第III-B5节中进行了说明。

3）范围查询：多维范围查询是基于位置的应用程序中最常见的查询之一。算法3提供了用于范围查询处理的伪代码。让是查询范围，ql是下限，qh是上限。
下界确定要扫描的第一个子空间。直到对应于上限的子空间的所有后续子空间都是潜在的候选子空间。令Sq表示候选子空间的集合。由于z曲线大致保留了局部性，因此Sqmight中的某些子空间不属于范围。例如，考虑图5所示的四叉树拆分。考虑范围查<[01,11]，[10,11]>此查询的z值范围是[0110,1111]，等于{01 ∗∗，10 ∗∗，11 ∗∗}。由于查询仅对应于空间的上半部分，因此名为10 ∗∗的子空间为假肯定。但是通过扫描索引可以消除这种误报。由于子空间名称仅足以确定子空间包围的区域的边界，因此仅当子空间的范围与查询范围相交时才扫描子空间中的点。该检查是廉价的，并且可以删除所有不相关的子空间。对于查询中包含的子空间，将返回所有点，而仅与查询相交的子空间需要进一步过滤。算法3中显示了查询处理的步骤。

4）最近邻查询：对于许多基于位置的应用程序，最近邻居查询也是重要的原始操作。算法4显示了在MD-HBase中进行k个最近邻居查询处理的步骤。该算法基于最佳优先算法，在该算法中，按照距查询点的距离的顺序扫描子空间[9]。
该算法包括两个步骤：子空间搜索扩展和子空间扫描。在子空间搜索扩展过程中，我们将逐步扩展搜索区域，并按照与查询点之间的最小距离的顺序对区域中的子空间进行排序。算法4将搜索区域的宽度增加到从查询点到扫描子空间的最远角的最大距离。下一步将扫描尚未扫描的最近子空间，并按与查询点的距离顺序对点进行排序。如果到第k个点的距离小于到最近的未扫描子空间的距离，则查询过程终止。

5）空间划分：K-d树和Quad树都限制每个子空间中包含的点数；当子空间中的点数超过此限制时，将拆分一个子空间。我们通过基础存储层的存储桶大小确定最大点数。由于索引层与数据存储层分离，因此在数据存储层中拆分的子空间将单独处理。索引层中的拆分依赖于前缀命名方案的第一个属性，该属性保证子空间名称是任何封闭的子空间名称的前缀。因此，在索引层中划分的子空间对应于用新子空间的名称替换与旧子空间的名称对应的行。创建的新子空间的数量取决于所使用的索引结构：K-d树仅在一个维度上划分子空间，从而产生两个新的子空间，而四叉树在所有维度上拆分一个子空间，从而产生2ⁿ个子空间。对于每个维度拆分，通过在与要拆分的维度相对应的位置在旧子空间名称后附加0和1来创建新子空间的名称。算法5为拆分后的子空间名称生成提供了伪代码。图6提供了2D空间中Quad树和K-d树在索引层中空间拆分的图示。


尽管从概念上讲很简单，但是在分割空间时仍然存在许多实现上的复杂性。这些复杂性来自以下事实：索引层在键值存储中作为表维护，并且大多数当前键值存储仅在单个键级别支持事务。由于拆分至少涉及三行（旧子空间名称为一行，新子空间名称为至少两行），因此与其他并发操作相比，这种更改不是事务性的。例如，与拆分并发的分析查询可能会观察到不一致的状态。此外，还需要其他逻辑来确保拆分的原子性。如[11]中建议的将索引保持为键组之类的技术可用于保证多键事务的一致性。我们将这些扩展留作以后的工作。另外，由于删除在LBS中不是很常见，因此我们省略了删除操作。但是，删除和合并子空间可以作为空间拆分算法的直接扩展来处理。

C.索引层实现

索引层是子空间名称的排序序列。由于子空间名称编码边界，​​因此索引层实质上在子空间之间强加了顺序。在先前的讨论中，我们将索引层表示为排序的子空间名称的整体层。一个分区索引足以满足许多应用程序需求。假设每个存储桶可容纳约10⁶个数据点。索引层中的每一行都存储很少的信息：子空间名称，到相应存储桶的映射以及一些用于查询处理的其他元数据。因此，每个索引表行100个字节是一个很好的估计。基础键值存储将其数据跨多个分区进行分区。考虑到键值存储中分区的典型大小约为100 MB [5]，索引分区可以维护约10⁶个子空间的映射。使用单个索引分区可以转换为大约10¹²个数据点。该估计值可能会根据实现方式或所使用的配置而有所不同。但是它提供了合理的大小估计。
我们的实现还对索引层进行了分区，以实现更好的可伸缩性和负载平衡。我们利用Bigtable中的B+树样式元数据访问结构来对索引层进行分区，而不会造成任何性能损失。 Bigtable及其实现中使用的开放源代码变体HBase，使用两级结构将键映射到其对应的表。顶层结构（称为ROOT）从不分区，并且指向另一层（称为META），后者指向实际数据。图7说明了该索引的实现。将索引层无缝集成到Bigtable的ROOT-META结构中不会由于索引访问而引起任何额外的开销。此外，优化（例如缓存索引层和同一主机上的客户端之间的连接共享）可减少对索引的访问次数。因此，在索引结构中添加此附加级别将在规模和访问数据项的间接级别数量之间取得良好的平衡。使用与上述相似的分析，通过这种二级索引结构索引的点数的保守估计为10²¹。

4.数据存储层

MD-HBase的数据存储层是范围分区的键值存储。我们使用BigTable的开源实现HBase作为MD-HBase的存储层。

A. HBase概述

HBase中的表由一个称为区域的拆分集合组成，其中每个区域都存储键空间的范围分区。它的体系结构包括三层B+树结构；存储数据的区域构成最低级别。如III-C节所述，这两个较高的上层是称为ROOT和META区域的特殊区域。 HBase安装由一组称为区域服务器的服务器组成，这些服务器负责为区域的子集提供服务。区域是动态分配给区域服务器的； META表维护区域到区域服务器的映射。如果某个区域的大小超出了可配置的限制，则HBase会将其分为两个子区域。这允许系统在插入数据时动态增长，同时通过为热点区域创建更细粒度的分区来处理数据偏斜。

B.存储层的实现

存在许多实现数据存储层的设计选择，有趣的是分析和评估与每个设计相关的权衡。我们的实现使用如下所述的不同方法。
1）表共享模型：在此模型中，所有存储桶共享一个HBase表，其中数据点按其对应的Z值（用作键）进行排序。我们的空间分割方法可确保子空间中的数据点在表中是连续的，因为它们共享一个公共前缀。因此，通过保留存储桶的开始和结束键来管理存储桶。该模型允许有效的空间分割，这仅相当于更新索引表中的相应行。另一方面，此模型将子空间限制为仅映射到单个存储桶。
2）每个存储分区表模型：该模型是另一个极端，我们为每个存储分区分配一个表。因此，数据存储层由多个HBase表组成。该模型提供了将子空间映射到存储桶的灵活性，并通过允许对不同表的操作进行并行调度来实现更大的并行度。但是，由于将数据点从子空间移动到新创建的存储桶，因此在该技术中划分子空间非常昂贵。
3）混合模型：此混合模型在表共享模型和每个存储桶的表之间取得平衡。首先，我们对空间进行分区，并为每个结果子空间分配一个表。在此初始静态分区之后，如果子空间由于溢出而被拆分，则新创建的子空间与父子空间共享同一表。
4）每个存储区模型的区域：HBase表包含许多区域。因此，另一种方法是对整个空间使用单个表，并将每个区域用作存储桶。 HBase中的区域分割非常有效，并且可以异步执行。因此，这种设计的空间分割成本低，同时能够有效地并行化跨不同存储桶的操作。但是，与讨论的其他三个模型相反，该模型是侵入性的，需要更改HBase。将一个挂钩添加到拆分代码中，以便根据所使用的索引结构来确定适当的拆分点。

C.优化

有几种优化可能会进一步提高存储层的性能。
1）空间分割模式学习：空间分割会引入影响系统性能的开销。因此，拆分的高级预测可用于执行异步拆分，这将减少对拆分期间执行的插入和查询的影响。一种方法是学习拆分模式以减少空间拆分的发生。位置数据具有固有的偏斜，但是，如前所述，这种偏斜通常可以通过维护和分析历史信息来预测。由于MD-HBase存储历史数据，因此索引结构固有地维护了数据分布的统计信息。为了估算未来将拆分新存储桶的次数，我们查找了过去分配给相同空间区域的存储桶数量。例如，当我们为区域（[t0，t1]，[x0，x1]，[y0，y1]）分配新的存储桶时，我们将为区域（[t0- ts，t1-ts]，[x0， x1]，[y0，y1]）。直觉是，过去的存储桶拆分模式是未来的很好的近似预测指标。
2）随机投影：数据偏斜使某些子空间变得很热，无论是插入还是查询。一种优化是将一个子空间映射到多个存储桶，并使子空间中的点分布在多个存储桶之间。当点随机分布时，这种技术称为随机投影。在子空间中插入数据点时，我们随机选择与子空间相对应的任何存储桶。包含子空间的范围查询必须扫描映射到该子空间的所有存储桶。因此，随机投影技术自然扩展了我们的原始算法；但是，它会在负载平衡和查询成本的潜在增加之间进行权衡。

5.实验评估

现在，我们对MD-HBase的原型实现进行详细评估。我们使用HBase 0.20.6和Hadoop 0.20.2作为底层系统来实现我们的原型。我们评估与存储层的不同实现相关的权衡，并将我们的技术与仅使用HBase线性化的MapReduce样式分析和查询处理进行比较。我们的实验是在Amazon EC2集群上执行的，集群大小从4到16个节点不等。每个节点包含4个虚拟核心，15.7GB内存，1,690GB HDD和64位Linux（v2.6.32）。我们按第四部分所述评估存储层的不同实现：模拟Kd和Quad树（TPB / Kd和TPB / Quad）的每个存储桶表，模拟Kd和Quad树（TS / Kd和TS）的表共享设计/ Quad），以及每个存储桶设计的Kd树区域（RPB / Kd）3。基线是使用z曲线线性化（ZOrder）的实现，没有任何专门的索引。我们还在Map Reduce中实现了查询，以评估执行数据完全并行扫描的MapReduce系统（MR）的性能；我们的评估使用了Hadoop运行时。我们的评估使用合成生成的数据集，这主要是由于需要巨大的数据集（数百GB）以及需要控制不同方面（例如偏斜和选择性）以更好地了解系统的行为。使用实际数据进行评估留待以后的工作。

A.插入吞吐量

支持高插入吞吐量以进行位置更新对于维持大量定位设备至关重要。我们在具有4、8和16个商品节点的群集上使用存储层的五种不同实现方式评估了插入性能。图8绘制了插入吞吐量与系统负载的关系图。我们将负载生成器的数量从2个更改为64个；每个生成器每秒产生10,000个插入的负载。我们使用的合成空间偏斜数据集使用Zipfian分布，其中Zipfian因子为1.0，代表中等偏斜数据。使用Zipfian分布可以使我们控制时滞，同时可以快速生成大型数据集。 RPB / Kd系统和ZOrder系统都显示了良好的可伸缩性。在16节点群集上，RPB / Kd和ZOrder实施实现了每秒约220K位置更新的峰值吞吐量。在定位设备每分钟注册一次位置更新的系统中，此部署可以处理1千万-1千5百万个设备。每个存储桶和表共享设计的表可伸缩性较低的主要原因是与拆分存储桶相关的成本。另一方面，每个存储区的区域设计使用HBase区域拆分机制异步拆分存储桶，该机制相对而言不昂贵。 TPB / TS系统会阻止其他操作，直到存储桶拆分完成。在我们的实验中，TPB设计需要大约30到40秒才能拆分一个存储桶，而TS设计则需要大约10秒。即使这些设计导致在群集上分配插入负载时具有更多的并行性，但存储桶拆分开销限制了这些设计所承受的峰值吞吐量。

B.范围查询

现在，我们使用索引结构和存储层的不同实现来评估范围查询性能，并将性能与ZOrder和MR进行比较。 MR系统过滤出与查询范围匹配的点，并报告匹配数据点的汇总统计信息。
我们使用Brinkhoff等人的基于网络的模型生成了约四亿个点。 [12]。我们的数据集模拟了40,000个沿旧金山湾区街道移动10,000步的对象。由于运动路径基于真实地图，因此该数据集代表了真实世界的数据分布。使用其他模型来模拟运动的评估是未来的工作。我们在Amazon EC2中的四节点集群上执行了范围查询。
图9绘制了不同设计的范围查询响应时间与选择性变化的关系。从图9可以明显看出，所有MD-HBase设计选择都优于基准系统。特别是对于高度选择性的查询，我们的设计比使用简单的Z排序或使用MapReduce的基准实现显示出一两个数量级的改进。此外，我们提出的设计的查询响应时间与选择性成正比，与MR实现中的整个数据集的暴力并行扫描相比，它断言了索引层的收益，这在MR实现中是最慢的。考虑并且独立于查询选择性。

在仅使用Z排序（ZOrder）的设计中，系统在查询区域的最小Z值和最大Z值之间进行扫描，并过滤掉不与查询范围相交的点。如果扫描范围跨越多个存储桶，则系统会并行化每个存储桶的扫描。尽管ZOrder设计显示出比MR更好的性能，但与我们提出的方法相比，响应时间几乎差了十倍，特别是对于具有高选择性的查询。 ZOrder性能较差的主要原因是由于线性化引入的点的映射失真而导致的误报正扫描。表I报告了ZOrder设计的误报（与查询范围匹配但不包含匹配数据点的存储桶）的数量。例如，在选择性查询率为0.1％的情况下，扫描的28个存储桶中有22个为假阳性。误报的次数取决于查询范围与存储区边界的对齐方式。在理想匹配的理想情况下，查询性能预计将接近我们提出的设计。但是，这样的理想查询在实践中可能不会经常被观察到。我们提出的设计可以进一步优化每个区域内的扫描范围。由于我们将目标空间划分为规则形状的子空间，因此当查询区域部分与子空间相交时，MD-HBase可以从查询区域和子空间的边界计算出存储桶中的最小扫描范围。相反，ZOrder设计将目标空间划分为不规则形状的子空间，因此必须扫描所选区域中的所有点。
对MD-HBase的不同替代设计的深入分析表明，TPB设计可带来更好的性能。TS设计经常导致高磁盘争用，因为某些存储桶位于同一基础键值存储的数据分区中。即使我们在TS设计中将存储桶扫描顺序随机化，也未观察到磁盘访问争用的显着减少。因此，TPB设计优于TS设计。对于高选择性的查询，与其他设计相比，RPB设计具有更长的响应时间。但是，这是我们为RPB设计选择实现方式的产物。在RPB设计中，我们重写了存储区拆分的数据透视计算，并将存储区维护任务委托给HBase，从而最大程度地减少了插入开销。但是，由于HBase以序列化形式存储存储桶边界信息，因此用于查询处理的索引查找必须对区域边界进行反序列化。结果，对于具有非常高选择性的查询，索引查找成本主导了总响应时间。
比较K-d树和Quad树，我们发现K-d树在具有高选择性的查询中具有更好的性能。但是，随着选择性降低，Quad树的响应时间会缩短。与K-d树相比，K-d树创建的存储桶数量更少，而Quad树提供了更好的修剪。在高选择性查询的情况下，子查询的创建成本决定了总响应时间。每个子查询通常扫描一个短范围，而扫描存储桶的时间则占总响应时间的一小部分。结果，与四叉树相比，K-d树具有更好的性能。另一方面，在低选择性查询的情况下，要扫描的点数在总响应时间中占主导地位，因为每个子查询都倾向于扫描很长的范围。因此，查询性能取决于索引结构的修剪能力。
我们还期望存储桶大小可能会影响整体性能。选择存储桶大小是在插入吞吐量和查询性能之间的权衡。较大的存储桶降低了存储桶拆分的频率，从而提高了插入吞吐量，但在查询处理期间限制了子空间修剪能力。

C. kNN查询

现在，我们使用与先前实验相同的数据集，评估MD-HBase对k个最近邻居（kNN）查询的性能。图10绘制了kNN查询的响应时间（以秒为单位），该响应时间是要返回的邻居数的函数。我们将k分别设为1、10、100、1,000和10,000。在该实验中，对于k≤100不会出现搜索区域的扩展，导致所有设计的性能几乎相似。 TPB / Quad设计具有最佳性能，响应时间约为250ms，而其他设计的响应时间则在1500ms至2000ms左右。当我们将k增加到1K和10K时，响应时间也增加；但是，由于使用了best first搜索算法，这种增长并不是指数级的。例如，当我们将k从1K增加到10K时，在最坏的情况下响应时间仅增加了三倍。

当k≤100时，TPB / Quad设计优于其他设计。由于扇出较大，四叉树的存储桶尺寸往往比K-d树的存储桶尺寸小。因此，与TPB / Kd设计相比，TPB / Quad的存储桶扫描时间更短。但是，两种TS设计对于小k都有几乎相似的响应时间。我们将此归因于其他因素，例如存储桶寻道时间。由于TPB设计为每个存储桶使用不同的表，因此对存储桶中所有点的扫描不会引起对存储桶中第一点的搜索。另一方面，TS设计在扫描存储桶的所有点时必须搜索对应于存储桶的第一个条目。如前所述，RPB设计具有较高的索引查找开销，这会增加响应时间，尤其是在k大时。但是，这是一个实现工件。将来，我们计划探索RPB的其他实施选择，这些选择可能会改善其性能。
由于ZOrder和MR系统没有任何索引结构，因此kNN查询处理效率低下。一种可能的方法是迭代扩展查询的区域，直到检索到所需的k个邻居为止。但是，该技术对许多参数（例如初始查询范围和范围扩展率）敏感。由于没有索引，因此没有合适的标准来确定初始查询区域。因此，我们在比较中不包括这些基准系统。但是，预期ZOrder和MR的性能将比提出的方法明显差。

6.相关工作

在过去的几年中，可伸缩的数据处理（用于大量更新和数据分析）一直是人们关注的一个领域。在处理大量更新时，键值存储在扩展到大数据量方面非常成功。示例包括Bigtable [5]，HBase [6]等。这些数据存储具有相似的设计理念，它们以可伸缩性和高可用性为主要要求，而丰富的功能为次要。众所周知，这些系统可以扩展到数TB的数据，缺乏有效的基于多属性的访问限制了它们在基于位置的应用程序中的应用。另一方面，在考虑可伸缩数据处理时，除并行数据库之外，MapReduce [7]，[13]是最主要的技术。事实证明，这样的系统可扩展到PB级数据，同时具有容错能力和高可用性。但是，这样的系统主要适用于批处理。此外，在没有适当的多维索引的情况下，MapReduce样式处理必须扫描整个数据集以回答查询。 MD-HBase通过为多维数据提供索引结构来补充键值存储和MapReduce样式处理。如我们的原型所示，我们建议的索引层可以直接与Key value存储一起使用。同样，索引层也可以与MapReduce集成在一起，以限制对误报的检索。
最近，在许多其他技术中已经使用了将线性化用于将多维数据点转换为一维空间的方法。例如，詹森（Jensen）等人 [15]使用Z阶和希尔伯特曲线作为空间填充曲线，并使用线性化值构造B +树索引。陶等 [16]提出了一种高效的索引技术，用于使用B树索引的集合进行高维最近邻搜索。作者首先使用局部敏感哈希来减少数据点的维数，然后应用Z排序对数据集进行线性化处理，然后使用B树索引对其进行索引。我们的方法与这些方法相似，不同之处在于我们使用线性化的数据点构建了一个K-d树和一个基于Quad树的索引。但是，MD-HBase中索引层和数据存储层的组合类似于B +树，让人联想到Bigtable设计。索引层中的子空间修剪是加快范围查询性能的关键，而范围查询性能对于具有高维度的数据点而言变得更加困难。在这种情况下，Tao等人使用了降维技术[16]可用于提高修剪能力。
另一类方法使传统的多维索引更具可伸缩性。 Wang等 [17]和张等 [18]提出了类似的技术，其中系统具有两个索引层：全局索引和局部索引。该空间被划分为几个子空间，并且每个子空间都分配有一个本地存储。全局索引组织子空间，而局部索引组织子空间中的数据点。 Wang等 [17]在R树索引数据库的集群上构建了内容可寻址网络（CAN）。 Zhang等人[18]使用R树作为全局索引，使用K-d树作为局部索引。因此，MD-HBase仅具有全局索引。但是，可以扩展它以在数据存储层中添加本地索引。

7.结论

可扩展的位置数据管理对于启用下一代基于位置的服务至关重要。我们提出了MDHBase，这是一种可扩展的多维数据存储，支持高效的多维范围和最近邻查询。 MD-HBase在范围分区的键值存储上分层多维索引结构。使用基于线性化的设计，我们的实现对标准索引结构（例如K-d树和Quad树）进行分层。我们在标准基础上的开放源代码键值存储HBase上实现了我们的设计，而对基础系统的更改却很少。通过全面的实验评估，证明了所提出设计的可扩展性和效率。我们使用节点集群进行评估，通过维持每秒每秒成千上万个位置更新的插入吞吐量，同时实时响应多维范围查询和最近邻居查询（响应时间不到一秒），证明了MD-HBase的可扩展性。将来，我们计划通过添加更复杂的分析运算（例如，天际线或多维数据集）并探索索引和数据存储层的其他替代设计来扩展我们的设计。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！