基于列族数据库构建分布式空间数据库

摘要：

​ 在海量空间数据的分布式存储管理方案中，在已有成熟的分布式数据库之上实现空间数据组织和索引，是一种比较便利的方法。本文以GeoMesa为例，探讨其中的主要实现技术机理。主要技术点来自于Anthony Fox等人2013年发表的论文Spatio-temporal Indexing in Non-relational Distributed Databases，James N. Hughes等人2015年发表的“GeoMesa: a distributed architecture for spatio-temporal fusion”论文，以及GeoMesa的官方文档。

1 背景知识

​ 移动传感器、微博等提供了大量带有地理标记的数据，在数量、速度和多样性方面呈现出典型大数据的4V特征。 这使人们不得不考虑使用诸如Accumulo和HBase之类的分布式数据库来管理这些海量数据。 不幸的是，现有的分布式数据库并没有专门的、符合标准的功能来管理时空数据，因此，出现了大量相关方面的软件系统，其中GeoMesa是最为典型，也最为成熟的解决方法。在介绍具体技术方法之前，有必要先了解一些基础知识。

1.1 列族数据库

​ 列族数据库是基于Google的BigTable技术形成的一种分布式数据库。其中key包含（行键、列、时间戳）等多维度信息。在物理存储方式上，横向按照列族拆分成不同的列存储文件，纵向上依据行键的排序、不重叠区间划分若干子表（tablet），并将其分配到多个RegionServer中，由RegionServer负责维护子表的创建、分裂、合并等执行动作。

​ 该存储方式带来了以下技术优势：

​ 一是对稀疏数据增强了压缩存储能力，没有value的cell可以不存储，这与关系型数据库有显著区别，也意味着可以几乎无限制地扩展行和列；

​ 二是并行数据访问能力，不同的子表分布存储在不同RegionServer上，从而有助于数据在不同节点上的合理分配，实现多点并行访问。

​ 典型的列族数据库包括BigTable、Accumulo、 HBase等。列族数据库的核心数据模型是多维稀疏map，与一般map中的不同之处在于，列族数据库的key由<行键，列键，时间戳>三个维度构成，可抽象为：

$$key(rowid:string, columnQualifiers:string, time:int64) \rightarrow value(BYTE[\,])$$

​ 其中：

• rowid： 行键，采用字符串类型，列族数据库依据行键的字典序做主索引。
• columnQualifiers： 列限定符或列键，字符串类型，可以是任一列族中任一列的限定符。理论上，列的数量可以根据需要扩展到无限多。在行内，列限定符按照字典序排序。
• time： 为时间戳，64位整型。

关于列族数据库在实现层面有以下几个要点：

• 列族数据库的索引特点是：仅根据行键索引到子表；子表内无索引，只能顺序扫描遍历。
• 列族数据库通常只有一个主索引（即行键），没有辅助索引
  • 由于稀疏表结构存储的存储特性，列族数据库难以实现辅助索引。如果希望实现对某一列或多列的索引，一种可能的做法是另外建表，并将需要索引的列限定符作为构造rowid的核心部分；但单独建表会形成另一份对数据库的完整拷贝。
• 行按“行键”以字典顺序排序，从最低到最高的字节字符串。
  • 为实现分布式存储，当表中行数到达一定阈值后，BigTable会根据行键排序结果将表分裂（split）为行键不重叠的若干子表（tablets），每个子表只存储某个行键区间内的数据。
• 列按列族分组存储，在列族中对列限定符按字典序排序。
  • 在物理存储的实现方式上，HBase为每一个列族单独设置一个存储文件（StoreFile）。为保持不同列族之间按照行键同步，当某个列族达到子表分裂阈值条件后，会触发其他列族同步进行子表分裂操作。这意味着如果一张表存在两个列族，其中列族A有100万行数据，列族B有1千万行数据，而表分裂阈值为100万行，那么列族A不会像想像的那样被分到一个子表中，可会跟随列族B被分割成10个子表。这种不均衡不仅会导致列族A的子表存储空间大量闲置，同时会造成列族A的访问效率大大降低。因此，HBase一般建议一张表的列族不要超过3个。 详情参见Hbase–为什么不建议在Hbase中使用过多列族。
• 所有操作在行级都是原子化的（Accumulo可以做到cell级）。
• 相关实体应存储在相邻行中，以提高读取效率。
• 列族数据库中的表属于稀疏表，空列不会占用任何空间
  • 创建大量列通常是可行的做法，即使大多数行中的大多数列均为空。
• 行键、列键和时间戳作为数据的一部分，是需要存储的。
  • 这和传统关系型数据库有很大的区别。
• 通过对行键、列族、列限定符和时间戳的过滤实现数据查询
  • 即列族数据库的查询只能反映在行键、列族、列限定符和时间戳上，无法对value实施查询。也就是说，如果value的某些信息需要查询，就必须要在行键、列族或列限定符中体现出来。
  • 行键的过滤是为了确定子表即RegionServer，列族的过滤是为了确定StoreFile，列限定符的过滤是为了得到符合条件的集合。
  • 集群端RegionServer是分布式的，因而可以在多个RegionServer上执行对列族和列限定符的过滤动作，进而达到分布式检索的效果。

​ 使用列族数据库的主要优势在于：

​ 多维键的形式提供了灵活的数据模型来存储结构化或半结构化数据。 由于没有关系型数据库复杂的关系和事务约束，因此可以对数据模型进行高度控制，从而实现图数据库、文档数据库、时序数据库和空间数据库等多种模式设计。

1.2 空间填充曲线

​ 列族数据库以字符串类型的行键、列键作为key的存储管理方式，对空间数据的存储是一个挑战。因为空间数据本身是多维数据，以大地坐标坐标系为例，一个经纬度点不具备列族数据库构建key所需的词典排序，因而无法直接在分布式数据库中进行索引。如果添加更多维度（如：高程和时间），则情况会变得更为复杂。

​ 空间填充曲线将多维空间映射到一维值空间，可以对经纬度点进行一维编码，从而使空间坐标转变为分布式数据库可以使用的字符串，是解决上述问题的一种方法。空间填充曲线除了起到降维编码的作用，同时还具备局部性和聚簇性特征（即索引空间中较近的单元，在原始空间中也应当较近），此特性对于提高分布式数据库中的查询效率至关重要。GeoMesa正是采用空间填充曲线来实现空间数据（可扩展到时空数据）的高效存储管理。

1.3 GeoMesa时空索引表的版本

在GeoMesa系统中，空间对象是被索引的主体。空间对象采用OGC的SimpleFeature数据模型，每个SimpleFeature由几何体、时间、属性键值对的集合构成。为减少磁盘使用、序列化/反序列化时间和网络传输成本，GeoMesa提供Avro、Kryo、二进制编码的SimpleFeature存储格式。为支持更一般的用例，GeoMesa还支持将空间对象的集合（list或map）作为value进行存储（即支持索引到空间对象的集合）。从公开的论文和文档分析，GeoMesa的时空索引表设计经历了2013、2015和目前版本三个进化阶段。

2 2013年的版本

2.1 设计要点

• 索引粒度：
  • 空间索引到150米左右，时间索引到1小时
• 双表设计：
  • 一张时空索引表，一张数据表，两者之间通过FeatureID建立联系
  • 两张表的rowID保持同步，从而保证索引表和数据表始终同步分区和分裂子表
• 检索机制：
  • 先根据时空查询窗口得到行键（范围集合）的后7位
  • 在前面补所有可能的shardID后，构成待查询行键范围和RegionServer集合
  • 在各RegionServer中，利用Accumulo的迭代器，对时空索引表的列族和列限定符按照更细粒度的空间和时间过滤，得到featureID集合
  • 在各RegionServer中，利用Accumulo的迭代器，对数据表的列族过滤，得到<key,value>集合

2.2 时空索引表设计

见下图。

（1）key设计

• 行键（9个字符）： shardID（2字符）+ hash（Geohash的第1个字符，5000公里分辨率）+ month（6个字符）
• 列族（3个字符）：由Geohash的第2-4个字符构成，20公里左右分辨率
• 列限定符（26个字符）：FeatureID（19个字符）+ hash（Geohash的第5-7个字符）+ hour（4个字符）

（2）value取值

• 论文中未明确，因cell值没有实际意义，应当可以是1字节的占位符。

（3）非点类型数据的索引方案

• 对非零范围的空间对象进行多尺度geohash剖分，生成网格集合，并为每个网格都生成一个FeatureID索引项

2.3 数据表设计

（1）key设计

• 行键：与时空索引表相同，且保持同步

• 列族：以FeatureID作为列族名

• 列限定符：以属性名称作为列限定符

（2）value取值

• 经过编码的SimpleFeature数据

2.4 特点总结

（1）随机分片，实现时空数据分布存储

​ 在rowID前端定义了两个字符的shardID编码段，将同一区域的空间对象通过随机分配shardID的方式均匀存储到不同RegionServer中，实现了分布式存储同时，为并行查询奠定了基础；

（2）行键、列族、列限定符中均含有时空索引信息

​ 在行键、列族、列限定符中，定义不同尺度的空间和时间编码，特别是在列族设计上，采用了GeoHash串的部分中间字符作为列族名称，通过大量列族实现不同空间区域数据的列式存储；

（3）空间对象的ID（featureID）作为列限定符的前缀

​ 空间对象ID作为列限定符编码的组成部分，通过对列限定符的过滤得到满足条件的FeatureID集合；

（4）分布式检索支持

​ 利用服务器端的过滤器或迭代器机制，实现基于行键和列键的筛选与过滤，巧妙地利用shardID实现了分布式并行过滤。

（5）空间索引到150米分辨率，时间索引到小时。

2.5 优缺点

（1）优点：

• 空间和时间的尺度可动态调整，具备了时空检索的能力
• 利用shardID实现了数据的散列，使同一地区的数据能够散列分布存储在不同区域

（2）缺点：

• 列族过多不符合列族数据库的技术特点。
  • 其列族最大可以达到 $32^3$ ，过多列族会带来很严重的现实性问题
  • HBase数据库中每个列族为一个StoreFile，列族多就需要维护更多的StoreFile，而HBase的实现机制是每个StroeFile在内存中都有一个MemTable，这会导致内存消耗非常大
  • HBase中不同列族在子表分裂时要保持同步，致使数据少的地区可能会跟随数据多的地区发生同步子表分裂，从而由于区域不平衡导致大量存储资源耗费，并拖慢数据少的地区的查询效率.
• 双表设计本质上来源于对传统关系型数据库的理解，是为了兼顾属性查询检索需要的一种设计，论文中通过在两张表中做迭代来实现时空检索，其效率是个比较大的问题。
• 增加shardID的目的是为了实现数据的散列分布，以便充分实现后续的分布式查询和计算任务。其好处是在所有的RegionServer中都分布有同一地区的数据，缺点是所有地区一视同仁，难以根据地区热度不同动态调整该地区的RegionServer数量配置。

3 2015年的版本

3.1 设计要点

（1）**索引粒度：**空间到150米，时间到天

（2）**单表设计：**将时空索引表和数据表合并为一个表

（3）行键粒度更细

• 取消了shardID设计，增加了行键的时空索引粒度，在降低行内数据爆炸的概率的同时，提高了人工分区配置的灵活性。

（4）检索机制：

• 先根据时空查询窗口、数据类型构造行键（范围）集合
• 根据行键范围，确定RegionServer集合
• 在各RegeionServer中，利用过滤器，对列族进行更细粒度的空间过滤，得到包含FeatrueID在内的<key,value>集合

（5）新增属性索引和featureID索引

• 支持了属性索引查询和featureID索引查询能力

• 考虑到列族数据库机制上难以实现辅助索引，所以2015版本中为属性索引和featureID索引单独创建表，相当于一个空间对象存在三份拷贝，技术细节见参考文献

3.2 编码结构

​ 编码结构见下图。

（1）key设计

• 行键（30个字符）：hash（GeoHash前2个字符，约630公里分辨率）+ value类型（1个字符）+ FeatureTypeName（16个字符）+ hash（GeoHash第3-5个字符，约2.5km）+ date（8个字符，到1天）
• 列族：hash（GeoHash的第6-7个字符，约150米分辨率）
• 列限定符： FeatureID（19个字符，应当可配置）

（2）value取值

• 单个feature或多个feature的集合，缩略数据项（只包含FeatureID和几何体）
• 单个feature或多个feature的集合，完整数据项（包含FeatureID、几何体和其他SimpleFeature支持的属性键值对）

3.3 技术特点

（1）空间优先分区

​ 新方案将空间编码作为前缀，由于HBase等数据库按照行键范围进行分区，因此这种rowid的设计本质上是按照空间分区，即不同区域的数据存储在不同的RegionServer上。其好处在于可以通过对不同地区的数据热度分析，人工设定分区的大小，使热度大的地区分区内的行数少些，RegionServer数量多多些，热度小的地区则反之。因为GeoHash具备聚簇性和局部性，所以基本能够保证这种灵活性。

（2）行键的时空区分粒度增强

​ 新方案的rowID中空间索引粒度到2.5公里左右，时间索引粒度到天，降低了由于索引粒度过大产生行内数据爆炸的可能性。

（3）列族数大大减少

​ 新方案中列族名称只有两个GeoHash字符，意味着最大 $32^2 = 1024$ 个列族。

（4）面向应用的value取值设计

​ 针对时空数据的可视化和分析两种使用场景，定义了缩略数据和完整数据两种类型的value

（5）对大尺度区域支撑效果，好于小尺度区域

​ 行键的空间索引粒度为2.5km，对于大城市、地区、省、国家、区域和全球这样的大尺度控制粒度足够，但对城镇、乡村等小尺度区域，则无法使用更细的控制粒度，进而很难做进一步的分区优化。

4 当前版本

4.1 设计要点

（1）大量采用二进制形式替换原来的字符串形式，存储效率大增

• 如：GeoHash直接采用二进制编码、时间采用周计数、value采用二进制硬编码等

（2）单表方案

• 继承了前一版本的单表方案
• 时空索引信息体现在行键上，属性信息体现在列族和列限定符编码上

（3）全rowID时空索引

• 时空索引统一体现在行键上，彻底放弃了用列族来做时空索引的方法

（4）索引粒度

• 采用8字节的二进制Z序时空编码，索引粒度较之前版本的150米和天更优

（5）检索机制

• 通过时空查询窗口构造rowID的前缀集合
• 利用rowID前缀对rowID进行过滤，结合特定关键字列族‘F’，获得空间对象实体的<key,value>集合，value为二进制硬编码的SimpleFeature。
• 通过rowID前缀对rowID进行过滤，结合用户指定属性组和属性列，获得空间对象的属性<key,value>集合，value为相应的属性取值。

4.2 编码结构

（1）key设计

• rowid： 周计数（2字节）+ 二进制时空编码（8字节）+ FeatureID（默认为UUID）

• 列族：

  • 对于空间对象的SimpleFeature数据，系统保留专用的列族名称关键字，如：Accumulo中的‘F’列族
  • 对于空间对象的属性数据，用户可以将若干属性包装到一个自定义的属性组中，用属性组名称作为列族名；由于列族名作为数据的一个组成部分也要存储，所以官方建议越短越好，尽量为1个字符
  • GeoMesa中保留了一些用户不能使用的单字符关键字列族名，如：‘d’、‘f’、'a’等。

• 列限定符：

  • 对于空间对象的SimpleFeature数据，无列限定符
  • 对于空间对象的属性数据，以属性名称作为列限定符

（2）value取值

• 对于空间对象的SimpleFeature数据，为硬编码的SimpleFeature
• 对于空间对象的属性数据，为二进制的属性值

4.3 技术特点

（1）时间优先分区

• 以相对于参考历元的周计数作为rowid的前缀，实际上实现了时间优先的分区策略

（2）全rowid时空索引，列族数量趋于固定

• 完全放弃了用列族或列限定符做时空索引的方法
• 列族主要用于属性管理，官方建议尽量所有属性在一个列族中，以避免多列族出现的效率下降问题

（3）时空控制粒度更细

• 直接采用8字节定长的Z序二进制码参与rowid构造，不再使用GeoHash字符串
• 时空表达的粒度更细，从而适应了更多场景

（4）配置灵活性强

• 时空粒度更细，赋予人工的灵活性越大
• 同时对分区方案的科学性要求更高
• 针对所要管理的空间范围，应合理地控制Z编码方案并定义配套的分区方案

5 总结

（1）分布式空间数据库的本质

• 分布式数据库的本质是将海量空间数据合理的散列存储在不同节点上
• 通过多节点的分布式并行检索和分析，来优化海量数据总体的检索和分析效率
• 例如：
  • 2013版本通过随机分配的shardID来实现随机散列分布
  • 2015版本通过GeoHash的前2个字符来实现数据按照空间散列分布
  • 当前版本通过周计数来实现数据按照时间散列分布
• 对于海量时空数据而言，就是将热点时间热点区域的数据尽量散列存储到不同节点上去

（2）分区策略和分区方案是关键

​ 列族数据库的分布式基于分区实现，因此，采用何种分区策略和配置何种分区方案成为空间数据组织管理的关键点，

• 分区策略：
  • 由应用的特点决定，主要用于明确依据哪些要素和优先级进行分区可以实现更为有效的散列分布，最终体现在rowid的编码设计上
  • 对于时空数据，在rowid上需要有相应的编码体现，空间填充曲线编码是最常用的技术手段
  • 不同要素在rowid中的编码位序，决定了其参与分区的优先级
  • 如何在定长空间编码段中，既保证聚簇性和局部性，又实现多尺度性，是一个需要解决问题
  • 分区策略和应用实践有非常密切的联系，原则上应当依据使用特点进行专门设计
• 分区方案：
  • 由分区策略约束的数据特征决定，依据分区策略rowid形成的数据集，应当计算其数据分布上的统计特征，并依据这些特征决定每个分区中rowid的范围
  • 解决数据倾斜问题，是通过控制不同地区所占有的分区数量来实现的
  • 考虑到填充曲线的聚簇性特点，某地区分区数量的增加意味着配置给该地区的资源更为丰富，同时可能也意味着采用了更高层级的填充曲线
  • 如何利用数据统计特征，自动计算分区方案是一个研究热点问题

（3）分布式空间数据库的设计要考虑列族数据库的约束条件

​ 分布式空间数据库应当充分考虑列族数据库的实现机制和其弱点有针对性的设计。在列族数据库中，在物理层面实际可调配的对象包括以下三个：

• 表（Table）：可以考虑为海量空间数据设计多个表

• 分区（Tablet）：可以考虑为海量空间数据设计多个分区

• 列族（StoreFile）：可以设计多个列族（StoreFile）

  其中：

• 多表方案：意味着占用更多的计算和存储资源，HBase官方推荐尽量在一张表里解决问题

• 多列族方案：多列族意味着需要管理更多的StoreFile和MemStore，同时要维持多列族之间的同步分裂和合并，HBase官方建议列族小于3

• 由此可见，在列族数据库中，真正可选用的方案只有多分区方案，这也是目前GeoMesa的主要调配模式。

​ 综上所述，目前基于分布式数据库实现的空间数据库，技术路线已经相当成熟。由于大量有关子表分裂和合并、并发控制等工作都有底层分布式数据库来解决，所以其技术实现复杂度并不是很高，且易于实现。但同时，此种类型的分布式空间数据库受限于分布式数据库自身限制，可能在时空数据的组织灵活性上稍有欠缺，而HadoopGIS、SpatialHadoop等直接基于HDFS构建自身的分区和索引方案，走出了另外一条技术路线。