[转]在HBase上查询地理信息系统（HBase in Action）

本章我们将进入一个使用HBase的新领域：地理信息系统（Geographic Information Systems）。GIS是个有趣的研究领域，因为它提出了两个重要的挑战：大规模数据处理的延迟和空间位置建模。我们将以GIS作为透镜来演示如何让HBase适应这些挑战。为了做到这些，你需要充分运用一些特有的行业知识。

8.1 运用地理数据

地理系统经常作为在线交互用户体验的基础来使用。想想那些基于位置的服务，例如Foursquare、Yelp或者Urban Spoon。这些服务致力于提供全球数百万地理位置相关信息。例如，用户依靠这些应用的服务在一个不熟悉的地区寻找最近的咖啡店。他们可不希望在他们和拿铁咖啡之间还需要一个MapReduce作业。我们已经讨论过HBase可以作为一个平台提供在线数据访问，所以HBase可以合理应对第一个挑战。如同上一章看到的，当HBase的模式被设计用来物理存储数据时，HBase可以提供低请求时间延迟。这顺便把你带到第二个挑战：空间位置。

GIS数据里的空间位置是微妙的。我们将花费本章很大篇幅介绍一个叫做geohash的算法，这是该问题的解决办法。其思路是把地球上一个地方的所有信息紧密地存储在一起。这样的话，当你想调查那个位置时，你可以发出尽可能少的数据请求。你也会希望地球上相邻位置的信息在硬盘上也是相邻存储。如果你正在访问市中心曼哈顿的信息，很可能你也会想得到切尔西和格林威治村的信息。你希望把这些数据和市中心的数据存得更近一些，比如说比布鲁克林或者皇后区的数据更近一些，你可能会获得更快的用户体验。

地理数据最简单的形式，也就是地球上的一个点，由两个同等相关维度决定：经度（X轴）和纬度（Y轴）。这只是一种简化。许多专业GIS系统可能在X轴和Y轴之外考虑Z轴，诸如高度或海拔。许多GIS应用也基于时间跟踪位置，这意味着上一章讨论的时间序列数据所面临的所有挑战。当设计系统提供低延迟数据访问时，上述两种维度的数据位置都很关键。HBase通过模式设计和行健的运用确定这两种维度的数据位置。有序的行健能够直接控制数据存储的位置。

当两个维度（也许四个维度）同等相关时如何保证空间数据的数据位置呢？例如，专门在经度上建立的索引表示，距离纽约市，芝加哥比西雅图更近。但是如图8-1所示，它也会告诉你，哥伦比亚的波哥大比哥伦比亚特区更近。仅仅考虑一个维度不足以满足GIS的需要。

如何组织数据以正确理解纽约城和华盛顿比纽约城和波哥大更近呢？在本章你将使用专门的空间索引（ spatial index）来应对这个挑战。你将使用这种索引作为两种空间查询的基础。第一种查询，“K个最近的邻居”，直接建立在这种索引上。第二种查询，“ 多边形区域内查询”，通过两次索引实现。第一种，单单基于空间索引就可以建立。第二种实现使用定制过滤器（ custom filter）的形式把工作尽可能转移到服务器端。这样会最大限度利用HBase集群来执行运算工作，并且把返回客户端的多余数据降到最低。同时，你将学习丰富的新行业知识，把HBase打造成一个完全胜任的GIS机器。人们常说，细节里面有魔鬼，所以让我们放大地图的比例，从国际城市间的距离问题转换为一个更加本地性的问题来加以解决。

8.2 设计一个空间索引

假设你正在访问纽约城，需要互联网接入。“哪里有最近的wifi热点呢？”一个HBase应用系统如何帮助你回答这个问题呢？什么样的模式设计可以解决这个问题呢？如何用一种可扩展的方式解决这个问题呢？

你需要快速访问到数据的相关子集。为了做到这一点，让我们从两个简单的、有联系的目标开始：

1 你希望在空间里彼此接近的点在硬盘上的存储位置点也是彼此接近的。

2 你希望当响应查询时返回尽可能少的点。

    如果可以实现这两个目标，你就成功建立了一个基于空间数据集的反应高度灵敏的在线应用系统。HBase提供给你完成这两个目标的主要工具是行健。在上一章你看到了如何在一个复合行健里为多个属性建立索引。根据华盛顿对比波哥大的例子，我们有一种直觉，上一章的做法不会适合第一个设计目标。试试没有坏处，尤其是如果你能够同时学点东西。因为上一章的做法实现很容易，所以在尝试更复杂的复合行健之前让我们先评估一下 基本的复合行健。

让我们先来看看数据。纽约城有个开放数据项目，公布了许多数据集 [1] 。其中之一是所有城市wifi热点的列表 [2] 。我们不要求你熟悉GIS或GIS数据，所以我们做了点预处理。下面是那些数据的例子：

X Y ID NAME

1 -73.96974759 40.75890919 441 Fedex Kinko's

2 -73.96993203 40.75815170 442 Fedex Kinko's

3 -73.96873588 40.76107453 463 Smilers 707

4 -73.96880474 40.76048717 472 Juan Valdez NYC

5 -73.96974993 40.76170883 219 Startegy Atrium and Cafe

6 -73.96978387 40.75850573 388 Barnes & Noble

7 -73.96746533 40.76089302 525 McDonalds

8 -73.96910155 40.75873061 564 Public Telephone

9 -73.97000655 40.76098703 593 Starbucks

数据已经被处理成一个制表符分隔的文本文件。第一行是列名。X和Y列分别是经度和纬度值。每条记录有ID、NAME和许多其他列。

GIS数据的一个好处是非常适合图片处理！不像其他种类数据，从GIS数据建立一个有意义的视觉化展示不需要聚合——只需要投射数据点到地图上就可以看到你有什么了。示例数据如图8-2所示。

       根据前面概括的目标，现在你为模式设计进行一次相当有趣的wifi热点检查。按照目标1，在地图上338点接近441点，所以它们的记录在数据库里应该是彼此接近的。按照目标2，如果你想获取这样两个点，你也不应该取219点。

现在你有了目标，也有了数据，是到考虑模式的时候了。如同你在第4章所学的，行健的设计是HBase模式中你需要做的唯一最重要的事情，所以让我们从这里开始。

8.2.1 从复合行健开始

前面我们讲过把X和Y轴值串联起来做行健不是一个有效的模式。我们引用了华盛顿对比波哥大的例子作为证据。让我们看看为什么。先按经度再按维度把示例数据排序，然后把点连接起来。结果如图8-3所示。当我们按这种方式存储数据，把扫描返回结果从1到10排序。请特别注意第6、7步和第8、9步的距离。因为先按经度后按纬度，这种排序导致了很多南北位置簇之间的跳跃。

这种模式设计貌似满足目标1，但可能只是因为示例数据少。关于目标2则表现很糟糕。每次从北方位置簇跳到南方位置簇就意味着你读取了不需要的数据。还记得图8-1所示的波哥大对比华盛顿的例子吗？那正是在这种模式设计里遇到的问题。空间里彼此接近的点在HBase里不一定彼此接近。当你把这些转换成一次行健扫描，你不得不取出期望的经度范围里每一个纬度的点。当然你可以在设计里用临时办法弥补这个缺陷。你大概会创建一个纬度过滤器，作为RegexStringComparator附加到行过滤器（RowFilter）来实现这个补救措施。这种方式至少可以避免把多余的数据返回给客户端。但这不是理想的办法，因为为了执行过滤器逻辑，过滤器还是需要先从存储里读出数据。如果你能避开无关的数据，根本不碰那些数据是更好的选择。

这种模式设计在行健里把一个维度放在另一个前面，这暗示了一种在不同维度间有次序的关系，这是不应该存在的。你可以有更好的选择。为此，你需要学习一种GIS社区想出来解决这种问题的技巧：地理哈希（geohash）。

8.2.2 介绍geohash

如前面例子所示，经度和纬度在定义一个点的位置时同等重要。为了使用它们作为空间索引的基础，你需要一种联合它们的算法。这种算法会基于这两个维度生成一个值。这样，这种算法生成的不同值用一种平等考虑两个维度的方式来建立彼此关系。geohash正是这样做的。

geohash是一种把几个值转换成单个值的函数。为了让它工作，那些值中的每一个必须来自于一个有固定范围的维度。本例中，你打算把经度和纬度转换成单个值。经度维度限定在[-180.0, 180.0]范围，而纬度维度限定在[-90.0, 90.0]范围。还有很多办法可以把多维度减少到单个维度，但因为它的输出需要保持空间位置，我们这里使用geohash。

geohash并不是一种完美无缺的输入数据编码方式。对于发烧友来说，这个道理有点像把原始声音记录压缩后的MP3。输入数据大部分都在，但也只是大部分。和MP3一样，当计算geohash时你必须指定精度。你能够使用12个 geohash字符来定义精度，因为这是你能在一个8字节的Long数据类型里容纳的并且仍然能够表示一个有意义的字符串的最高精度。通过截取哈希值尾部的字符，你可以得到一个低精度的geohash和相应低精度的地图。在全精度代表一个点的地方，部分精度时在地图上代表一个区域，实际上是空间里一个方块界定的区域。图8-4解释了截取geohash尾部字符降低精度的表现。

对于一个指定的geohash前缀，在对应的那个空间里的所有点都使用相同的前缀。如果你能让查询落在一个geohash前缀的带边界方块里，所有匹配的点将共享一个相同的前缀。这意味着你可以在行健上使用HBase前缀扫描来得到一组和那个查询相关的点。这样就实现了目标1。但是如图8-4所示，如果你选择过低的精度，你会得到比需要的多得多的数据。这违背了目标2。你应该在边界附近工作，我们稍后介绍这些。现在，让我们看一些真实的位置点。

思考这三个位置：拉瓜迪亚机场（40.77° N, 73.87° W），肯尼迪国际机场（40.64° N, 73.78° W），和中央公园（40.78° N, 73.97° W）。他们的坐标分别geohash处理为值dr5rzjcw2nze、dr5x1n711mhd和dr5ruzb8wnfr。你可以在图8-5看到地图上的这些点，并且看到 中央公园离拉瓜迪亚机场比 肯尼迪国际机场近。按绝对距离看，中央公园离 拉瓜迪亚机场约5英里，而中央公园离肯尼迪机场约14英里。

因为中央公园离拉瓜迪亚彼此空间距离更近，你可以预期它们比 中央公园和肯尼迪机场共享更多的相同前缀字符。事实果然如此：

$  sort <(echo "dr5rzjcw2nze"; echo "dr5x1n711mhd"; echo "dr5ruzb8wnfr")

dr5ruzb8wnfr

dr5rzjcw2nze

dr5x1n711mhd

现在你理解了geohash的工作原理，我们将演示给你如何计算生成一个值。别担心；你不必哈希处理手上所有的点。为了高效运用HBase，理解其工作原理是有帮助的。使用geohash也类似，理解其构造原理将帮助你理解边界问题。

8.2.3 理解geohash

你已经看到的geohash值都被显示为Base32编码字母表 [3] 的字符串。事实上，geohash的位序列按照经度和纬度精度递增的顺序依次排列。

例如，40.78° N是纬度。它落在[-90.0, 90.0]范围的上半区 [4] ，所以它的第一个geohash比特位是1。因为40.78落在[0.0, 90.0]范围的下半区，它的第二比特位是0。第三个范围是[0.0, 45.0]，落在上半区，所以第三比特位是1。

通过对半切分值的区间和确定落在哪半区，计算出每个维度对应的数据位。如果数据点大于或等于中点，用1表示。否则，用0表示。这个过程重复进行，一次一次对半切分范围，然后根据目标点的位置选择1或0。在经度和纬度值上都执行这种二进制分区方式。最后通过编码把这些比特位编排在一起生成哈希值，而不是单独使用每个维度的比特位序列。这种空间分区方式是geohash有空间位置属性的原因。正是每个维度的比特位的编排方式支持了前缀匹配精度查询的技巧。

现在你理解了每个维度是如何编码的，让我们计算一个完整值。这种区间二等分进程和比特位选择一直重复，直到达到预期的精度。经度和纬度两者一起计算出一个比特位序列，它们的比特位是相互交织的，先是经度，再是纬度，直到目标精度。图8-6解释了这个过程。一旦比特位序列计算出来，它会被编码生成最后的哈希值。

现在你理解了geohash对你有用的原因以及它的工作原理，让我们把它用到你的行健里。

8.2.4 在有空间感知特性的行健里使用geohash

因为geohash计算开销不大，对于行健来说geohash是个极佳的选择，行健的前缀帮助你寻找最近的邻居。让我们把geohash应用到示例数据，按照geohash排序，看看在前缀上如何表现。我们使用一个函数库 [5] 计算出每个点的geohash，添加一列到原来的数据里。示例里的所有数据相对比较接近，所以你可以预期在这些点上好多前缀是重叠的：

GEOHASH X Y ID NAME

1 dr5rugb9rwjj -73.96993203 40.75815170 442 Fedex Kinko's

2 dr5rugbge05m -73.96978387 40.75850573 388 Barnes & Noble

3 dr5rugbvggqe -73.96974759 40.75890919 441 Fedex Kinko's

4 dr5rugckg406 -73.96910155 40.75873061 564 Public Telephone

5 dr5ruu1x1ct8 -73.96880474 40.76048717 472 Juan Valdez NYC

6 dr5ruu29vytq -73.97000655 40.76098703 593 Starbucks

7 dr5ruu2y5vkb -73.96974993 40.76170883 219 Startegy Atrium and Cafe

8 dr5ruu3d7x0b -73.96873588 40.76107453 463 Smilers 707

9 dr5ruu693jhm -73.96746533 40.76089302 525 McDonalds

的确如此，前缀共有5个相同字符。还不错！这意味着你使用一个简单的范围扫描就可以进行距离查询和满足目标1。为上下文需要，图8-7把这些数据放到了地图上。

这比复合行健方式好得多，但也决不是完美的。所有这些点密集放在一起，彼此相差几个街区而已。但为什么只匹配了12个字符中的5个？我们希望空间接近的数据能够存储得更近一些。回想图8-4，通过5个、6个、7个字符的前缀扫描覆盖的空间区域在大小上的区别是显著的——远超过几个街区。如果你能做两次6个字符前缀的扫描而不是一次5个字符前缀的扫描，你朝着目标2大大前进了一步。或者，做5次或6次7个字符前缀的扫描会怎么样呢？这次带着更多的视角，让我们看看图8-8。6个字符前缀和7个字符前缀的geohash方块是重叠的。

和目标查询区域相比较， 6个字符前缀的匹配区域太大了。更糟糕的是，这次查询需要执行两次那些区域太大的6个字符前缀的扫描。从上下文可以看出，5个字符相同前缀包含的数据更是远超过你的需要。依赖前缀匹配的做法导致扫描了巨量多余的数据。当然，这是一种交换。如果你的数据在这个精度水平不算稠密，扫描执行得少，那么这种耗时长点儿的扫描也不是多大问题。如果扫描不返回过多多余数据，你就可以把远程过程调用（RPC）压力降到最低。如果你的数据是稠密的，扫描运行次数多，那么较短的扫描可以减少网络上传输的多余位置点的数量。此外，现在还有一件事情正在变得更为有利，那就是并行计算。每个短扫描可以在自己的CPU核上并行执行，但是整个查询的速度仍然由最慢的那个扫描决定。

让我们卷动地图到曼哈顿的另一个部分，离我们已经研究的地方并不远。请看图8-9。注意中心方块的geohash有六个前缀字符（dr5ruz），和东向、东南向和南向的方块相同。但是只有5个字符（dr5ru）和西向和西南向方块相同。如果5个相同字符前缀是糟糕的，那么北边整行匹配的前缀更是糟糕，只有2个字符（dr）相同！这不会每次都发生，但是的确以惊人的高频率发生。作为一个反面例子，东南 向方块（dr5ruz9）的全部8个邻居都有6个相同字符前缀。

    Geohash是有效的，但是你不能只是使用一次简单的自然前缀匹配。根据这些插图，看起来这种数据的优化处理方式是扫描中心方块和它的8个邻居。在把不必要的网络IO数据量降到最低的同时，这种方式将确保正确的结果。幸运的是，针对那些邻居的计算操作只是简单的比特位操作。解释那种操作的细节超出了我们的兴趣范围，所以我们相信geohash函数库能够提供那种特性。

不是所有线性化技术都可以用来创建各维度平等的geohash

Geohash是在近似模拟数据空间。也就是说，它是一个基于多维度输入值计算单维度输出值的函数。本例中，输入的维度只有2，但是你可以想象有更多维度时如何工作。这是一种线性化的方式，geohash不是唯一的一个。其他技术，诸如Z轴次序曲线 [6] 和希尔伯特曲线 [7] 等，也是常见的。它们都属于空间填充曲线 [8] 类别：这种曲线定义为单一的、不中断的、接触空间所有分区的线条。这些技术无法在一维线条上完美地建模二维平面并且在那些空间维持对象的相关特征。因为geohash的错误情况比其他技术少，所以我们选择了geohash。