所谓时空数据, 顾名思义, 包含了两个维度的信息: 空间信息与时间信息. 空间信息, 以地理位置点最为基础, 还包括线, 多边形以及更为复杂的多维结构. 最典型的时空数据, 莫过于移动对象的轨迹点数据, 如每隔 5 秒钟记录的车辆实时位置信息. 这类数据, 在物联网领域司空见惯, 在可预见的未来, 这类数据将会出现爆炸性的增长.
用 HBase 存放时空数据
时空数据, 尤其是移动对象位置点数据, 结构简单, 但关于吞吐量的要求却往往很高.
单从这点信息来看, 这类数据属于 HBase 的适用范畴.
先不谈论时间纬度与复杂的多边形数据, 我们先从最简单的地理位置点数据开始, 探讨一下如果用 HBase 来存储这类数据会遭遇哪些技术挑战.
地理位置点 Point 中包含两个信息: 经度 X 与纬度 Y, 按照传统的思路, 将一个 Point 存成一行数据, 而经度 X 与纬度 Y 则分别是构成这行数据的两个列, 可以为每一个 Point 设置一个 ID, 并以此 ID 作为数据 RowKey. 所有的 Points 在表中按 ID 字典顺序存放.
围绕地理位置点的典型的查询方式, 如 "查询某一个建筑附近有哪些酒店?", 按照刚刚表设计思路, 数据如按主键 ID 顺序存放, 某个建筑附近的所有酒店, 它们在主键顺序上却未必是相邻的 , 因此, 这个查询可能涉及扫描大量的无关数据.
可见, 针对最简单的时空数据类型, 传统 HBase 表设计思路已经显得非常低效, 传统关系型数据库基于 B-Tree 的数据组织结构也更是疲于应对. 再放大到整个时空数据的范畴, 要支持的典型场景更为复杂:
查询某一个地理区域在某个历史时间范围内发生的关键事件
查询某一个地理区域的人流量, 车流量信息
查询某一天上午先后在 A,B,C 三个地理区域出现过的具有某些特征的人
查询某嫌疑人在某一天的行动轨迹
归根结底, HBase 中的数据按照 RowKey 单维度排序组织, 而我们现在却面临的是一个多维数据问题. 因此, HBase 如果想很好的支持时空数据的存储, 需要引入时空索引技术.
从上面的查询场景来看, 原生 HBase 的访问接口难以直接支持这些能力, 因此, 时空数据领域需要更加专业的访问接口, 这是 GeoMesa 项目存在的关键原因.
常见的时空索引技术
关于时空索引, 已经有不少常见的技术, 这里, 我们主要介绍一下 R-Trees,Quad-Trees,K-D Trees 以及 Space Filling Curve 这四种技术.
R-Trees
R-Trees 源自论文《R-Trees: A Dynamic Index Structure For Spatial Searching》, 下面的图也源自此论文:
R-Trees 基于这样的思想设计:
每一个空间对象, 如一个多边形区域, 都存在一个最小的矩形, 能够恰好包含此时空对象, 如上图中的矩形 R6 所包含的弯月形区域. 这个最小包围矩形被称之为 MBR(Minimum Bounding Rectangle).
多个相邻的矩形, 可以被包含在一个更大的最小包围矩形中. 如 R6,R9 以及 R10 三个矩形, 可以被包含在 R3 中, 而 R11 与 R12 则被包含在 R4 中.
继续迭代, 总能找到若干个最大的区域, 以一种树状的形式, 将所有的时空对象给容纳进去, 如上图中的 R1, R2. 这样, 整个树状结构, 呈现如下:
从最小的矩形区域, 到最大的矩形区域, 就好比地图中的行政区域划分: 村 -> 县 -> 市 -> 省份. 查询时, 先从锁定的最大区域开始, 逐级缩小比例尺后, 就可找到最终的对象. 如若将上图中的 R1 与 R2 理解成两个平级的 "行政区域", 却又存在本质的区别: 不同的行政区域, 并不存在相互重叠, 而 R1 与 R2 却可能是重叠的.
R-Trees 的定义:
每一个 Leaf Node 包含 m 到 M 个索引记录(Root 节点除外).
每一个索引记录是一个关于 (I, tuple-identifier) 的二元组信息, I 是空间对象的最小包围矩形, 而 tuple-identifier 用来描述空间对象本身.
每一个 Non-leaf 节点, 包含 m 到 M 个子节点(Root 节点除外).
Non-leaf 节点上的每一个数据元素, 是一个 (I, child-pointer) 的二元组信息, child-pointer 指向其中一个子节点, 而 I 则是这个子节点上所有矩形的最小包围矩形.
如上图中, R3,R4 以及 R5, 共同构成一个 non-leaf 节点, R3 指向包含元素 R8,R9 以及 R10 的子节点, 这个指针就是 child-pointer, 而与 R8,R9 以及 R10 相关的最小包围矩形, 就是 I.
Root 节点至少包含两个子节点, 除非它本身也是一个 Leaf Node.
所有的 Leaf Nodes 都出现在树的同一层上.
从定义上来看, R-Trees 与 B-Trees 存在诸多类似: Root 节点与 Non-Leaf 节点, 均包含限定数量的子节点; 所有的 Leaf Nodes 都出现在树的同一层上. 这两种树也都是 自平衡 的.
前面也已经提到了, B-Trees 主要用来存放一维排序的数据元素, 而 R-Tree 存放的则是多维空间数据元素. 从查询方式上来看, 两者也存在显著的差异: B-Trees 更擅长于数据点查, 它的设计并不利于数据的范围查询. 基于空间元素的查询, 却以范围查询为主, 而且往往需要对多个子树进行并行查询, 例如, 在地图上划定某一个区域, 查询这个区域内有哪些公园, 可能有多个子树都与划定的这个区域存在交集. 从这一点看来, R-Tree 的搜索性能其实并没有很好的保障.
R-Trees 有多种变种, 如 R+-Trees,R*-Trees,X-Trees, M-Trees,BR-Trees 等等, 不再展开过多的介绍.
Quad-Trees
同很多数据结构类似, Quad-Trees 也存在多种变种, 最初的 Quad-Trees 设计源自论文《Quad Trees: A Data Structure for Retrieval on Composite Keys》, 下图源自论文, 是关于 Quad-Trees 的直观呈现:
上图中的 A,B,C,E,F,G 均为 Point, 以每一个 Point 作为中心点, 可以将一个区间分成 4 个象限.
假设, 先写入 Point A, 以 A 为中心, 将整个区间分成了 4 个象限.
写入 Point B,Point B 位于 A 的东北象限中, 同样, 以 B 为中心, 依然可以将 A 东北象限进一步细分为 4 个子象限.
写入 Point C,Point C 位于 A 的东南象限中, 以 C 为中心, 可以将 A 的东南象限细分成 4 个子象限.
.....
任何新写入的一个 Point, 总能找到一个某一个已存在的 Point 的子象限, 来存放这个新的 Point.
整个树状结构呈现如下:
可见, Quad-Trees 有几个鲜明的特点: 1. 对于非叶子节点, 均包含 4 个子节点, 对应 4 个面积不一的象限. 2. 不平衡, 树的结构与数据的写入顺序直接相关 .3. 有空的 Leave Nodes, 且所有的 Leave Nodes 则是 "参差不齐" 的(并不一定都出现在树的同一层中).4. 数据既可能出现在分枝节点中, 也可能出现在叶子节点中.
因为 Quad-Trees 存在诸多变种, 为了有所区分, 上面提到的最简单的这种 Quad-Tree, 被称之为 Point Quad-Trees. 还有一种典型的 Quad-Trees, 被称之为 Point Region QuadTrees(简称为 PR QuadTrees):
PR Quad-Trees 中, 每一次迭代出来的 4 个象限, 面积相同, 且不依赖于用户数据 Point 作为分割点, 或者说, 数据分区与用户数据无关 . 每一个划分出来的子象限中, 只允许存在一个 Point.
与 Point Quad-Trees 相比, PR Quad-Trees 允许两份不同的数据集, 拥有相同的分区信息. 但 PR Quad-Trees 存在的问题也明显: 1. 两个相邻的 Points, 可能在树的 Level 高度上相隔甚远. 2. 两份数据集如果追求相同的分区信息, 可能需要进行足够粒度的分割, 这可能导致空间浪费.
K-D Trees
K-D Trees 是一种针对高维点向量数据的索引结构, 一棵简单的 K-D Tree 如下图所示(原图源自 James Fogarty 的 "K-D Trees and Quad Trees", 但为了更直观, 关于分区分割线的线条做了改动):
与 Quad Trees 思想类似, K-D Trees 也是将整个区间进行不断分割, 不同之处在于, Quad Trees 每一次迭代, 将一个区间分割成四个象限, 而 K-D Trees 则是分成左右或上下两个区间. 如上图所示: S1 把整个空间分成了左右两个区间, 左侧区间中, 又被 S2 横向分割成了上下两个区间, 而 S3 又在 S2 的分割基础上, 将下部分分割成了左右两个区间,....
如果已经存在一批 Points, 则较容易针对这批数据构建出一棵趋于平衡的 K-D Tree, 如若接收实时写入的数据, 或者说数据更新频繁, K-D Tree 则难以维持平衡态, 除非对整棵树进行重构.
Space Filling Curve
如果将一个完整的二维空间, 分割成一个个大小相同的矩形, 可以将 Space Filling Curve 简单理解为它是一种将所有的矩形区域用一条线 "串" 起来的方法, 因 "串" 的方式不同, 也就引申出了不同的 Space Filling Curve 算法.
比较典型的如 Z-Order Curve:
再如 Hilbert Curve:
Space Filling Curve 事实上是为空间数据提供了一种一维排序的方法, 它拉近了空间数据与传统数据库的距离: 因为这意味着可以使用传统的 B-Tree 或 B+-Tree 索引, 来存储空间数据.
我们再借助于 Z-Order 的迭代构建过程, 来加深读者关于 Space Filling Curve 的理解:
如果将整个区间划分成 4 个象限, 第一轮迭代就是将这 4 个象限利用 Z-Order 曲线连接起来:
而后, 将第一轮迭代中的每一个象限, 再进一步细分成 4 个象限, 这样共变成了 16 个区间. 在第二轮迭代中, 再将 16 一个小区间用 Z-Order 曲线连接起来:
第三轮迭代再进一步拆分, 连接, 变成下图的样子:
每一次迭代, 都是在上一次迭代的 "方格" 基础上, 将每一个 "方格" 拆成了 4 个 "子方格", 这种思想与 Quad-Tree 的思路是一致的, 尤其是 PR Quad-Tree, 因此, 也可将 Space Filling Curve 理解成一种高效构建 Quad-Tree 的方式 , 但需要说明的一点是, Z-Order 论文的发布时间要远早于 Quad-Tree 论文的时间.
GeoHash
GeoHash 可以将 Point 编码成一个字符串, 如:
http://geohash.org 这个网站提供了经纬度与 Geohash 的在线转换能力. 从编码结果来看, 可以发现三个特点:
越高的精度, 字符串越长, 可对比上表中的 P1 到 P3 的 Geohash 值变化.
P3 所表示的区域涵盖了 P2, 而 P2 涵盖了 P1, 这层关系, 在生成的 Geohash 值中这样体现:
"ws10rn6y"(对应 P2)以 "ws10rn"(对应 P3)为前缀
"ws10rn6yp9ms"(对应 P1)以 "ws10rn6y"(对应 P2)为前缀.
位置相近的点, 生成的 Geohash 值也相似, 如 P2 与 P4, 两者纬度相同, 经度仅差 0.001, 在生成的 Geohash 值中仅最后一个字符有区别.
GeoMesa 官方资料中, 也给出了这样一个典型的例子:
针对 (-78.48, 38.03), 编码的过程, 如下:
第 1 步 : 经度二分
规则 : 先将完整的坐标系统 (-180.000 -90.000, 180.000 90.000) 按经度中点 0.000 进行二分, 如果处于左边则编码为 0, 处于右边, 则编码为 1.
结果 : 因 (-78.48, 38.03)处于左侧区间 (-180.000, 0.000), 因此, 实际编码为 0. 此时, (-78.48, 38.03) 所处的区间被缩小为(-180.000 -90.000, 0.000 90.000).
第 2 步 : 纬度二分
规则 : 基于第 1 步的结果, 再将 (-180.000 -90.000, 0.000 90.000) 按纬度中点 0.000 进行二分, 如果处于上侧则编码为 1, 处于下侧, 则编码为 0.
结果 : 因 (-78.48, 38.03)处于上侧区间 (-180.000, 0.000), 编码为 1, 与第一步的结果结合在一起, 编码变为 "01″. 此时, (-78.48, 38.03) 所处的区间被缩小为(-180.000 0.000, 0.000 90.000).
第 3 步 : 经度二分
规则 : 基于第 2 步的结果, 再将 (-180.000 0.000, 0.000 90.000) 按经度中点 - 90.000 进行二分, 同样, 如果处于左侧则编码为 0, 处于右侧, 则编码为 1.
结果 : 因 (-78.48, 38.03)处于上侧区间 (-90.000, 0.000), 编码为 1, 与前两步的结果结合在一起, 编码变为 "011″. 此时, (-78.48, 38.03) 所处的区间被缩小为(-90.000 0.000, 0.000 90.000).
第 4 步: 纬度二分
.....
就这样, 经度纬度不断交替二分迭代 , 每一步的输出结果如下表所示:
关于上表中的 Bounding Boxes 的不断编码, 可直观的体现在下图中:
通过 Base-32 Encoding, 可以将上表中的编码结果进一步编码成字符串. 例如, 基于 Base-32 编码规则:
因此,(-78.48, 38.03)的编码为 01100 10110 01010 00000 10110, 将其转换成对应的字符:
- 01100 -> d
- 10110 -> q
- 01010 -> b
- 00000 -> 0
- 10110 -> q
连在一起,(-78.48, 38.03)的最终编码结果变为: dqb0q
经 Geohash 编码后, 其顺序与 Z-Order 编码保持一致, 因此, 也可以将 Geohash 是针对 Z-Order 算法的 一种编码机制 .Geohash 编码带来的显著优势是: 以字符串字典顺序表达 Z-Order 顺序, 利用字符串的前缀匹配规则, 也可快速实现多边形区域的重叠计算, 但在编码效率上却并无任何优势, 如 sfcurve 项目中提供的 Z2 编码算法, 性能要远高于 Geohash 算法.
哪种时空索引可应用于 HBase?
HBase 基于 LSM-Tree 架构, 底层 HFile 文件以 B+ Tree 形式组织. 在不影响 HBase 现有架构的基础上, 我们来分别探讨一下各种时空索引与 HBase 结合的可能性.
从 R-Trees 的原始论文描述来看, 它的设计是为了充分利用 Disk Page 的优势, 这一点与 B-Tree 类似. 它支持良好的数据随机写入能力, 能够自平衡, 从设计上来看, 非常适合于矩形 / 多边形空间对象的存储. 既然是致力于磁盘上的索引设计, 对 HBase 现有架构带来较大的侵入性, 即使能对 HBase 进行改造, 与 B-Tree 类似的这种设计, 已经被证明难以支撑高吞吐量数据写入. 如果不做任何改造, 我们只能考虑如何将 R-Trees 的数据映射到 HBase 的 KeyValue 模型中 :HBase 的数据按 RowKey 排序, 从而能够按照 RowKey 快速检索, 如果将 R-Trees 的数据以 HBase 原生数据形态组织, 自然希望能提供一种方法, 使得 R-Trees 中的数据排序方式与 RowKey 的排序一致, 或者说, 如何为 R-Trees 中的数据对象找到一种 RowKey 生成机制, 使得 R-Trees 中的数据顺序就是 RowKey 的字典顺序. 但我们知道, R-Trees 中, 其实已经弱化了数据对象 "排序" 的含义, 一个节点与子节点之间, 更多是一种包含于被包含的关系, 一个空间对象可能归属于不同的分枝, 这取决于那种划分方案更优, 当一个 Leaf Node 承载的对象过多时, 也可能出现 Split. 如果按照传统的树遍历的顺序来理解 R-Trees 中的对象排序, 这种排序是不确定的. 这意味着, 我们无法构建出一种确定顺序的 RowKey.
再来看一下 K-D Trees:K-D Trees 是针对高维点向量而设计, 用来存储二维的 Point 数据, 自然也能很好的应对. K-D Trees 的结构, 与数据的写入顺序强相关, 也可以说, 同样的一批数据, 因顺序不同, 所构成的树的结构截然不同, 这个问题也存在于 Point Quad Trees 中, 因树结构的不确定性, 它们与 HBase 结合的最大障碍, 依然在于 如何将 Trees 中的数据映射到 KeyValue 模型中 .
PR Quad Tree 的分区则不依赖于数据本身, 更与数据的写入顺序无关, 但 PR Quad Tree 限制每一个 Point 都独占一个小方格的设计, 使得每一个 Point 可能处在树的不同层次 / 高度中, 而且随着数据的不断写入, 同一个 Point 所处的高度可能会发生变化: 如原来某一个方格中只有一个 Point, 但如果有新的数据写入后, 这个方格需要进一步被分拆成 4 个新的子方格, 原来的 Point 在树中的位置也发生了变化, 因此, PR Quad Tree 也无法直接应用于 HBase.
如果对 PR Quad Tree 进行稍加改造:
将完整空间经过 X 次迭代后, 预先将其划分成 4^x 个小方格.
所有的 Point 都必须存放在最小的方格中.
不限制每一个小方格中存放的 Points 的数量.
这样, 带来了三点 "确定性": 树的层次是确定的, 每一个小方格在树中的访问路径是确定的, 每一个 Point 所属的小方格也是确定的. 因此, 只要我们存在一种方法, 将每一个小方格的访问路径, 映射成 HBase 的 RowKey, 就完美解决了时空 Points 数据存放在 HBase 中的问题, 这种思路正是 Spatial Filling Curve 的核心思想 .
我们提到了两种常见的 Spatial Filling Curve: Z-Order Curve 与 Hilbert Curve. 评价一种 Spatial Filling Curve 的优劣, 有两个关键的维度:
距离保留度 : 将二维空间对象映射成一维曲线后, 两个对象在二维区间上如果是相近的, 那么, 在一维曲线中也应当是相近的. 一个更优的曲线, 理应更大程度上在一维曲线中维持对象在二维空间上的距离, 或者说, 应该有更高的距离保留度. 对于查询而言, 更高的距离保留度, 也往往意味着更高的 Caching 命中率.
编码复杂度 : 可以简单理解为将二维空间对象映射成一维曲线的计算复杂度.
Z-Order 曲线在距离保留度上, 略弱于 Hilbert 曲线, 但在编码复杂度上, 却比 Hilbert 曲线更低, 这是 GeoMesa 选择 Z-Order 曲线的关键原因.
- References
- R-trees: A Dynamic Index Structure for Spatial Searching
- The R+-Tree: A Dynamic Index For Multi-Dimensional Objects
- https://www.geomesa.org/documentation/
- https://github.com/davidmoten/rtree
- https://en.wikipedia.org/wiki/Z-order_curve
- https://www.slideshare.net/shakil0304003/b-tree-rtree
- https://en.wikipedia.org/wiki/Quadtree
- https://github.com/davidmoten/rtree
- https://github.com/varunpant/Quadtree
- Comparison of Advance Tree Data Structures
- Space-Filling Curves An Introduction
- A dive into spatial search algorithms
- James Fogarty: K-D Trees and Quad Trees
- https://en.wikipedia.org/wiki/Space-filling_curve
- http://geohash.org
- https://github.com/geomesa/geomesa-tutorials
- https://en.wikipedia.org/wiki/Geohash
- Spatial Keys - Memory Efficient GeoHashes
- GeoServer: CQL And ECQL
- GeoServer: ECQL Reference
- GeoMesa: Scaling up Geospatial Analysis
来源: http://www.tuicool.com/articles/u2YvUbe