面向多维度矩阵存储的海量空间数据管理模型源码分析（以TileDB为例）

先丢个石头引来金玉满堂哈，然后，以TileDB为例子介绍其基本组成结构（后期会对每一块进行优化说明），最后以高级别数据分析支持为展望云计算和大数据的新玩法和思路。

空间数据管理是驱动未来诸多商业的核心所在，空间数据类型可以分为三个类型，分别是栅格数据，矢量数据以及图数据。栅格数据例如，遥感影像数据就是典型的包含诸多像素单元的正规网格化数据。矢量数据包含点、线面数据广泛用于制图社交数据分析，而以地下管网为代表的图数据存储在城市规划，地铁线路辅助设计等应用中。空间数据管理是包含数据模型，存储和索引，以及为支持空间查询、可视化分析为一体的地理信息科学。作为对科技工作者的致敬，在编辑此文时也链接了一下对中科院地理遥感与数字地球所李教授的最新关于海量矢量数据管理的文章地址（Big spatial vector data management: a review）。具体来讲，在数据模型方面，大规模使用面向对象的矢量数据管理模型。这样，以键值形式存储到NoSQL数据库中，键代表对象的唯一标识，而矢量数据结构遵从OGC的WKT格式进行内容存储。关系型数据存储很早就存在了，例如Oracle, PostgreSQL了，NoSQL数据库比较鲜明的特点是分布式，可扩展，不用预先定义表结构。另外一个较重要的原因是云原生支持。不过，NoSQL也没能改变GIS空间查询处理分析慢的根本问题。于是，大家都开始折腾以Hadoop为代表的空间数据管理模型。例如比较出名的Hadoop-GIS， SptialHadoop是建立在以HDFS和MapReuce为支撑基础上的空间数据管理方式。矢量数据的管理就介绍到这里了，本文重点关注的是同时适用于栅格和矢量数据的矩阵数据管理模型（说下背景，团队核心成员有以水利遥感以及土壤环境监测，农田水利方面的一流高校老师）。

这里要介绍的是来自VLDB的TileDB， 先说明下，Array和矩阵其实真没撒区别，按照翻译来讲，它是数组的意思，也就是多维数组存储模型，我简单叫它多维矩阵模型（数组和矩阵在这里可以互换）。与其它数组存储模型SciDB、ArrayStore相比，它支持稀疏矩阵的有效存储和访问和更新。SciDB采用正规维度分割数据块，对某一部分数据的访问通常需要读这些大的分块，对其中一个像素的更新会导致严重的写延时。和之前说的Hadoop不适合具有读写更新需求的空间数据存储一样的道理，分块冗余存储的底层设施会依据某个固定的数据分块大小存储多个数据分块，怎么弄都得全部读取分块数据（也可能分块的大小小于128MB, 具体是不是128MB，要依据Hadoop集群管理人员的策略决定），而TileDB解决了这个问题。不过，有些地方我还是不赞同TileDB的MIT大神说法（用SQL查询和处理海量矩阵数据而不用写low level程序，其实也不一定就很low，哈哈！）

TileDB数据模型包含Array，dimensions，attributes，domains , coordinates以及cells。按照中文翻译分别表示数组，维度，属性，域，坐标和矩阵单元。每一个数组都由维度和属性构成。每一维度都有其名称和类型，其取值范围构成与之对应的domain。 所有这些维度域值的任意组合构成了定位数组单元cells的坐标coordinates。每个cell存储的是属性值。这里属性有可能是0个或者多个，每个属性的值有可能是固定的1个值，也有可能是一个定长或变长值元组。属性的取值类型是原子类型（int, float或者是char）, 属性的取值也可能是变长原子类型元组。 在TileDB中矩阵类型要么是稀疏的，要么是密集的，判断是撒类型取决于cell中是否有空值。为了有效地支持存储，它引入了一个叫全局单元序列（global cell order）的概念。用户首先会为这些多维数据划分空间瓦片（Space tiles），通过为每一维指定一个瓦片范围（tile extent）,多维数组在逻辑上被映射成大小相等的分块（这里大小相等是逻辑上的）。用户同时也会决定如何访问分块中的数组单元cell的顺序，例如行优先，或列优先。最后，在遍历整个矩阵时，会指定tile的遍历次序，也是行优先或者列优先。这样做的好处是用户的对矩阵单元的访问会促进底层组件的物理数据的合理组织以支持有效的读操作。之前说通过指定瓦片范围来组织存储，但对于稀疏矩阵来说，空的单元或者是单元中包含变长数据都会导致瓦片的大小（这里的大小是物理上的大小）不同。从而导致对这些数据的处理会产生“任务倾斜”。还记得火热的Apache Spark么？ 调度任务到数据所在的位置，数据积累的越多，任务调度的也越多，延时就越大，道理一样的就不多说了。 至于如何解决这个问题，TileDB给出了答案，它用一个叫data tile的逻辑概念表示非空数据单元的集合。用capacity表示在一个data tile 中非空单元的个数。这样还是可以依据之前说的全局单元序列来管理稀疏矩阵。在介绍矩阵压缩，跟踪数组元素的更新操作以及矩阵元数据管理和分析源代码前，本文先介绍其系统架构以及矩阵的物理存储模型。

如图1所示，存储管理器保持对所有已打开矩阵的状态管理，C-API表示向外部暴露的数组操作接口，主要有初始化，读写，合并以及表示完成操作。每一个已打开数组的分片元数组（fragment）也会被保存到进程的堆空间中，这样多线程可以共享访问这些分片元数据。这里说的fragment，可以简单理解为对矩阵进行更新的时间戳标识的镜像数据，这种镜像数据通常是原始矩阵中的某些子区域变化产生的新的数据区域。这样分片的累加就会形成当前矩阵的最终表示，主要是为了促进读写效率。

图1，系统架构图

对于TileDB的物理存储来讲，每一个array，都会有一个文件目录对齐进行存储。在这个文件目录中，该矩阵的每一个分片数组（fragment）都会对应一个目录进行存储。此外，还包含一个特别的目录专门用于存储array schema的二进制表示。在分片数组（fragment）目录中按照每一属性对应一个文件的方式进行存储。特别需要注意的是，属性文件中的内容为按照global cell order（GCO）遍历的属性数据二进制值。 此外，在分片数组（fragment）目录还包含一个专门的文件用于存储分片元数据的二进制值。举例说明，一个矩阵包含两个属性a1, a2,这两个属性分别是定长数据类型整形，一个是变长数据类型，GCO遍历的模式指定为空间瓦片范围2×2，瓦片在矩阵上的遍历顺序按行优先策略，在瓦片中的数组单元遍历策略按行策略。这样对于固定属性来说，在数组对应的分片文件中生成一个a1.tdb文件，存储其二进制内容，对于变长属性来说，除了存储其数组单元的值之外，同样存储的另外一个文件存储说明其在矩阵中的数据偏移位置。

图2，密集矩阵的物理存储

作为结束，本文先不继续讲解稀疏矩阵的物理存储（存储的方式都差不多），为了支持对海量高维数据分析，arrayudf已经被正式提出了（还不清楚的google一下）。它使得，之前说的用声明式的语言描述所要访问数组元素以及对这些元素进行操作成为可能。从本质上来讲，TileDB只是做了简单的矩阵存储操作，为了支持快速的分析，我们将会在云计算和大数据栏目介绍新的解决思路。后续会依次补充源代码分析，架构演化以及实际应用效果。和以前读博一样，依然坚持在深夜写这些觉得还算有用的内容，希望能持续这种状态，不多说了下次再见！