基于全文数据库构建分布式空间数据库

摘要：

​ 利用现有商业和开源的分布式数据系统构建分布式空间数据库，是一种代价小、稳定性高的技术方案。其中，利用ElasticSearch、MangoDB等具备分布式部署能力的全文数据库构件分布式空间数据引擎，是最易实现的技术方案。根据大数据时代的分布式空间数据库)所述，空间数据索引主要有三种实现方式，一是在数据空间中进行划分，而后建立独立的索引结构，其缺点是索引需要与数据同步、索引更新复杂度高，优点是检索效率快；二是构造HASH函数，将多维空间中的数据映射到若干桶中，建立基于桶的索引结构，其优点是索引计算简单，缺点是不同的桶中数据规模不同，难以解决数据倾斜问题，此外也需要建立单独的索引结构，同样存在与数据同步的问题；三是将多维空间映射到一维值空间，直接借用成熟数据库内建的B+树索引，其优点是可直接移植到现有数据库中，缺点是需要将查询窗口映射到若干子区间，将单个查询转换为多个区间查询，计算复杂度较高，检索效率相对较低。本文所述方法属于第三类，并且重点针对全文数据库，借用全文数据库多节点分布式部署的功能实现分布式空间数据存储能力。本文核心围绕全文数据库中如何真正实现一维值的快速查询展开，并将其原理扩展值关系型数据库。有关多维空间如何映射到一维空间、映射至一维空间后的多区间查询算法如何实现等问题，在后面的文章中分别介绍。

一、全文检索基本原理和倒排索引

1.1 全文检索的对象是文档摘要数据，不是文档本身

• 全文检索的本质是对文档关键字和文档摘要数据的管理，而不是对文档本身的管理。例如：谷歌和百度搜索就是一种全文搜索引擎，它管理的对象就是经过网页分析后，存储在服务器端的网页摘要信息，一定记住，不是网页本身，而是经过信息提取后的网页摘要信息，包括网页链接地址、网页作者、网页快照等多个字段。

1.2 全文搜索引擎的工作原理

• 从互联网上爬取网页，并对网页进行结构分析和分词等关键字分析
• 从结构分析中得到网页摘要数据，存入正向存储文件中，每个网页都有唯一的一个ID与之对应
• 从关键字分析中得到网页中的关键字，存入倒排索引文件中
• 利用倒排索引文件，用户可以首先依据关键字查到对应文档的ID集合，然后到正向文件中得到ID对应的网页摘要信息（此时就存在哪些摘要放在前面，哪些摘要放在后面的问题，即所谓Page Ranking），用户依据网页摘要信息，选择感兴趣的网页链接，并进入实际网址。
• 凝练：输入关键字–>到倒排索引文件查找关键字对应的docId–>到正向存储文件中读取文档摘要信息–>进入实际网页链接。

1.3 倒排索引

• 通过上面原理可知，需要利用倒排索引文件找到网页链接。但是关键字和网页之间是多对多的关系，即一个网页中有很多关键字，而一个关键字可能对应多个网页，该如何处理这个问题呢？
• 建立一个关联表，表中每行为一个（关键字，文档ID）的组合，这个关联表就是倒排索引表的雏形；
• 但是这种组合如果是乱序组织的话，检索效率会很低，该怎么办呢？
• 鉴于搜索的习惯是由关键字找网页，因此，可以对上述关联表按照关键字做排序处理，这样速度就会有巨大的提升，而经过排序的关联表，就是最终的倒排索引表了。

二、倒排索引文件和正向文件的关系

• 2.1 倒排索引文件和正向文件同等重要

​ 由此可见，倒排索引文件和正向摘要文件在全文搜索引擎中同等重要，缺一不可，并且两者之间要保持同步。网上大部分介绍资料只突出了倒排索引原理，而缺少对倒排索引文件和正向文件的介绍。

• 2.2 倒排索引文件和正向文件本质上都是表结构

  • 倒排索引文件是由（关键字，文档id）构成的表结构，在Lucene中存储在.tis文件中；
  • 文档摘要文件是由（文档id，文档属性1，文档属性2…)构成的表结构，即每个网页摘要也是由若干字段构成，在Lucene中存储在.fdt文件中；
  • 文档id需要是唯一的，由于网址本身就局部唯一性，所以具备做标识符的基础，但采用定长的UUID也许是更好的选择；
  • 正是因为全文数据库的本质是表数据结构，只是这种表结构和常见关系型数据库的表结构实现方式不太一样，而且倒排表和正向数据表之间有着明确的关联关系。此外，关系型数据库在正向数据表之间还有约束关系，而全文检索数据库可能没有那么严格的约束条件。
  • 因此，只要管理对象是表结构的数据，且表之间关系不是特别复杂时，都可以采用全文检索引擎实现。这也是部分关系型数据库能够很容易地转移到全文数据库的原因。

• 2.3关键字检索的本质

  关键字检索的本质，实际上是一个Join的过程，即在倒排索引表和文档摘要表之间，基于文档id做一个Join运算。

三、Lucene中正向文件和倒排索引文件的存储方式

3.1 问题分析

​ 当要管理的网页（或文档）摘要信息太多时，就必须要存储在硬盘上，需要的时候再从硬盘上去读取。因此必须考虑其在硬盘上的存储结构（因为硬盘的IO速度相比内存，实在是太慢了），于是出现了大量的优化存储方法。

3.2 解决办法

​ 建立存储索引是对正向摘要文件和倒排索引文件优化存储的主要方法，其做法有点类似于Windows或Linux的文件系统。首先，不管是正向存储文件还是倒排索引文件，都必须存在一个可排序而且具备唯一性的字段，倒排索引数据和正向文档摘要数据都是基于该字段顺序存储的。其中：正向存储采用的是文档id，倒排索引采用的是关键字。

​ 依据唯一性字段对所有记录进行排序，并切分成很多区间，每个区间存储在一个外部存储的单位中（如：block、page、chunk等，这些单位内部一般都是占用连续的物理扇区），然后建立对这些区间的索引结构，以便告诉计算机，关键字或docId中从某段到某段，存储在哪个block中。这种索引结构通常是树结构（算法与数据结构瞧一瞧）。因此通常正向存储文件和倒排索引文件都有一个配套的索引文件，用于快速从数据文件中找到并读取相应的倒排索引记录和正向文档摘要记录。在Lucene和ES中正向文件的索引文件后缀名为.fdx，倒排索引文件的索引文件后缀名为.tii。

不管是正向文件、倒排索引文件还是它们的索引文件，最终都是要存储在硬盘上的，而且需要不断地更新，这里面涉及到很复杂的机制，此处不做大范围讨论。只需把关注点放在存储机制上。首先大家要对硬盘的存储机制有一定了解。硬盘采用柱面、磁道、扇区来标识磁存储介质的位置，当数据存储在硬盘上不同位置时，硬盘内的磁头要做抬起和读取等相应的机械动作，其所需的时间比读磁介质的时间要大。因此，为提高物理IO的效率，就要尽量减少磁头的这种机器动作次数。显而易见的做法，是把前后有一定关联性的数据存储在连续的若干个扇区上，这样只需要一次机械动作就能得到所有数据，从而使效率大大提升。

​ 在对正向文件、倒排索引文件和它们的索引文件设计时，就是严格按照上述考虑来的。首先确定硬盘中连续存储的物理存储单位大小（这个单位就是block），然后将表和索引的内容，往block里填。

3.3 存储格式的设计

• 正向文件、倒排索引文件的存储

  按照排序结果进行分区（Partition），分区的区间大小受限于block的大小，block内是连续的扇区，block之间不一定连续。但所有block之间，逻辑上依据关键字顺序存储，物理上不强制要求连续。

• .fdx,.tii索引文件的存储

  idx和fdx文件的设计也是基于分区的，每个分区内根据block大小存储多组索引信息（如：分区范围，该分区在.fdt或.tis文件中的block号，前一分区所在的block，后一分区所在block…）。这样通过索引文件，就可以很容易找到某个区间的数据记录在.fdt和.tis文件中在哪个block中了，具体细节不同系统可能不太一样，但大致是这么个意思。

• 内存/硬盘的二级存储机制

  • idx和fdx文件是可以全部读入内存的，在内存中更新并按照一定规则push到硬盘中；
  • 正向文件和倒排索引文件中的数据较大，通常不会全部读取到内存里面，但会在内存中建立缓存机制；
  • 为保证数据的安全性和效率，通常采用预写或预读的方式。预写即在写文件之前，先将本次写操作存到日志文件中，以便于写不成功的时候，还能再次执行；预读则是在读取文件的时候，将连续的block多读取一些进内存，这样下次有需要的时候，就不需要再做物理IO。

  3.4 全文检索的效率受限因素

  ​ 通过上述原理的分析，可以知道，一次全文检索的效率（时间），是由两个阶段组成的：一是根据关键字找到文档id；二是根据文档id找到文档摘要数据。而其中第一个阶段基本是在内存中基于树或hash等索引方式实现的，效率优化空间不大；重点需要优化的是第二个阶段，即保证以最小的物理IO数达到最大的效能，换句话说，同样检索一个区段的文档摘要数据，谁的方法从硬盘上读取的block越少，谁的效率就越高。

四、多维数据如何优化检索效率

4.1 什么是多维数据

​ 多维数据指的是类似二维平面、三维立体、四维时空等维度较多的数据。由于计算机本身的地址是线性的，所以传统的数据库系统，都是主体面向一维数据设计的，在多维数据的存储时，就会遇到新的问题。例如：在三维空间中选择一个范围，怎样从线性地址空间中找到这个范围里的数据？

​ 解决该问题的本质，是如何实现多维空间向一维线性空间的映射，很多时候还要求双向一一映射。不仅如此，为了适应多维空间的邻近搜索需要，在多维空间中相邻的点，在一维线性空间中应当也相邻，这被称为局部性要求；反之在一维线性空间中的点，反向映射到多维空间时，还要能够保证在多维空间中不能出现某些维的膨胀，这个被称为聚簇性要求。

多维空间先一维空间映射的方法有很多种，有些方法已经固化在我们的脑子里面。最典型的是矩阵和张量在内存中的存储方式，就是一种基于各维度下标的映射。但采用下标方式存在一个比较严重的问题，就是在两行之间无法满足局部性要求，在上一行行尾和下一行行首列之间，无法满足聚簇性要求。

目前实现聚簇性和局部性的主要方法是将通过空间填充曲线（Spatial Filling Curves，SFC，典型如：Hilbert曲线、peana曲线、z序曲线等）或某种映射函数（如：Payamid，iMaxMin等），将多维空间映射到一维值空间。

4.2 如何利用SFC和全文检索引擎实现多维数据的高效检索

根据全文检索两个阶段的特点，可以从两方面提升检索效率，一是在倒排索引表的检索阶段，实现快速找到docID；二是在正文摘要提取阶段，依据docID快速从物理存储中读取摘要数据。其中：

• 第一个阶段如何优化

  由于第一个阶段的检索主体在内存中进行，而且类似Lucene和ES都有树型结构和相应的检索算法，所以提升效率的空间不大，通常也就是在毫秒级。可以尝试建立以SFC编码作为关键字的方法，但其主体是加快了获得docID的效率，实现了docID的关联，并不能提升获取正向文档摘要数据的效率。

• 第二个阶段如何优化

  Lucene和ES在用户未指定的情况下，一般会自建docID，而该ID和数据在多维空间中的分布没有任何关系，既不能保证局部性，也不能保证聚簇性，其空间检索效率是极低的。最恶略的情况是分布在同一个区域的N个数据，可能散布在N个block中，从而造成N次物理IO。为此，可以将SFC应用到docID的设计中，具体做法可以采用“SFC编码+随机码”的方法生成docID，这样既能保证局部性和聚簇性，又能保证唯一性。

五、有关多维数据的降维方法

​ 实现降维的方法很多，但其中空间填充曲线方法由于计算简单，使用比较广泛。请参考：

• 基于空间填充曲线的降维方法

• 另外一类多维空间向一维值空间转换的方法)

  有关空间填充曲线的聚簇性分析，请参考：

• 空间填充曲线的聚簇性分析

​ 另外，使用一维值空间对空间对向索引，处理点类型数据效率很高，但是在处理具有范围的空间对象（如：多点、线、多线、环、多边形、TIN等，统称为非零范围空间对象）时，会面临单值索引还是多值索引的问题，也是利用空间填充曲线、GeoHash等方法时的通用技术问题。相关技术讨论和解决防范，请参考：

• 非零范围空间对象的索引方法之XZ序曲线索引
• 非零范围空间对象的索引方法之尺度分割索引

六、向关系型数据库的推广及分布式实现

（1）相关系型数据库的推广

​ 本文所述方法同样适用于关系性数据库，不同之处在于：

• 关系型数据库中的主键，类似于全文数据库中的docID或自定义ID

• 关系型数据库中的主键尽量采用整型，从而是B+树的效益发挥到最大

（2）分布式部署时需考虑的因素

当采用分布式部署模式时，无论是分布式全文数据库还是分布式关系型数据库：

• 分区方案

  • 需要充分考虑分区的原则，特别要将数据分布特征考虑到分区方案中，以避免数据倾斜问题导致的性能下降

• 数据库参数配置

  • 配置好数据库的一些参数（如：填充率），因为B+树涉及索引节点和叶子节点分裂的问题，为了避免频繁地节点分裂造成效率下降，通常各节点只使用40%左右的填充率来构建索引，也就是说本来节点可以指向或存储M条记录，但创建索引时只使用其中40%，剩余60%是提供给后续变更的余量；当剩余60%也使用殆尽时，才重新构建新的索引。