随着GPS和无线通信技术的进步，源源不断地生产具有地理位置或空间范围的各类数据时空流^［1］。时空流不仅具有流式数据实时、易失性、无限的特点，而且具有时空数据高维、时空相关性的特点^［2］。为支持快速准确的计算，如何实现大规模高维数据时空流的高效存储与检索已成为关键问题。

通用的Apache Flink^［3］等分布式流计算框架并不支持对时空数据的特别处理，在不考虑时空邻近性的情况下，通过哈希分区或随机分区的方式将传入的流数据随机分发至可用节点，导致时空查询成本较高。ZHANG等^［4］基于Storm采用分布式格网索引建立了移动对象的实时索引，实现高效的索引更新和空间查询。GeoFlink^［5］拓展了Flink提供的针对时空流的高速处理方法，将数据流逐条加载至分布式内存格网索引。受限于内存容量和数据的实时性，这些方法并不支持对时空流的大范围时间查询。时间序列数据库InfluxDB^［6］按照时间范围分区，写入通常发生在最新的分区，可实现流数据的快速插入。但其仅提供基于文件和内存的倒排索引，无法支持有效的时间范围查询及空间查询。

格网索引、K-D树索引等空间索引常被用于实现有效数据分区和高效查询^［7］。赵馨逸等^［8］提出了基于Geohash和R-tree的时空索引（Geohash and R-tree based index for spatio-temporal data，GRIST）结构，采用Geohash设计中的自适应分裂方法，并增加R树索引节点合并策略，以适应大规模时空数据的构建。然而，传统时空索引仅面向数据查询，不具提供面向实时数据的快速插入能力。Bulk-loading技术通过一次插入多个元组分担插入及索引调整的开销^［9］。杨良怀等^［2］提出了一种面向海量时空流的分布式批量构建R树索引的方法，有效提高索引构建效率。但批量插入的方式不适合用于数据在到达时对时空查询立即可见的场景。

为了在不进行批处理的情况下提高插入性能，日志结构合并树（the log-structured merge-tree，LSM-Tree）^［10］采用内存—磁盘结构实现索引的快速更新，已被广泛应用于各种先进的分布式数据库。现有研究较少关注LSM树索引对空间数据的支持^［11］。BÖXHM等^［12］利用格网索引及Z曲线将空间数据变换为一维字符串，顺序存储在B⁺树索引中，通过在B⁺树中查询包含所选范围的格网最长字符串前缀即可检索。WaterWheel模型^［13］根据主键和时间属性范围将时空流分区存储并建立B⁺树索引。但当面向连续查询任务时，WaterWheel将串行执行每个查询请求，导致多个节点在执行子任务后处于空闲状态，集群的并行能力无法得到充分利用。蔡瑞初等^［14］面向交通流实现了分布式存储系统，在构建索引时，通过提取上一个时间窗口构造的B树的前几层，并将其作为当前时间窗口的索引模板，实现对时空流的快速索引。除了B⁺树索引，AsterixDB等^［15］用R树作为LSM树的二级索引空间数据，但未进行分布式实现。

HBase^［16］为LSM B⁺树的典型分布式实现，相较于传统数据库，HBase具有扩展性高、存储速度快等特点^［17］。大量研究基于HBase存储时空流数据。由于HBase并不支持原生的多维访问^［18］，对于非行键上的查询须进行全表扫描。针对交通流，李欣^［19］采用Geohash编码设计了HBase混合时空编码行键，对每条记录进行索引，利用行键进行高效点查询和范围查询。陆婷等^［17］利用多源缓冲区结构对流数据进行划分，并优化HBase行键设计，将数据均衡分布在集群各服务器，采用多线程插入技术保证交通流的高效存储性能。MD-HBase^［20］基于HBase的索引层思想，利用线性化技术与K-D树等建立二级空间索引关联空间分区，加大了查询范围。MA等^［18］提出了UQE-index 3层索引结构，分别索引时间分区和空间分区并对应存储在HBase区域。UQE-index采用数据存储与索引分离技术，当数据插入导致节点分裂时，需要再同步存储至索引结构。李攀宇等^［21］利用基于HBase的时空分块二级索引结合行键设计，解决了热点问题并实现时空范围的高效查询。然而，由于二级时空索引与数据存储分离具有高耦合性，面对高速时空流，HBase方案无法同时实现快速索引更新和时空范围的高效查询^［22］。

综上所述，通用的流处理框架并不支持时空数据，当前大量研究利用时空分区的方式将时空流存储至分布式键值数据库，由于索引与存储分离，且索引更新开销过大，无法提供较好的时空流快速插入与高效范围查询。对此，本文从实时更新的LSM树出发，探索时空索引与数据存储的融合方式，并引入轻量级的空间填充曲线分区方式设计分布式调度与存储方案，从而实现索引实时更新与时空高效查询。提出了一种顾及流数据时空邻近性的动态时空调度策略；采用预分区方式构建基于LSM树的八叉树索引（OCTree based on LSM-Tree，LSM-OCTree），实现批量合并计算；提出面向时间分片的分布式存储方案，用于支持时空流的存储与查询。

现有的分布式流计算框架缺少对时空流的适配设计，通常将传入的时空数据随机分发至可用节点。在执行时空查询任务时，需要在集群中全局查找计算节点以获取满足查询条件的数据。由于全局查询耗时过长以及节点交互需要昂贵的网络通信，时空查询时延较长。对此，本文提出了一种时空调度策略，利用时空数据的紧耦合性，将时空邻近的数据分至同一结点，在进行局部查询的同时降低数据传输的开销。另外，对输入数据流进行均匀划分，确保节点间的任务量均衡，提高连续查询任务的执行效率。

空间填充曲线具有局部有序性，其中，Hilbert曲线比Z曲线和Gary曲线的聚类效果好^［23］。本文首先利用Hilbert曲线将时空数据的空间位置映射为一维数值，再使用水库抽样算法^［24］对输入时空流持续采样；根据Hilbert值大小对样本数据进行排序；最后根据节点数及并行实例数确定数据的划分。在此调度模式下，具有空间邻近的数据被划分至同一节点进行处理和存储。且各节点的任务负载相似。当对计算节点进行时空查询时，不需要像传统模式一样进行全局查找，通常满足查询要求的数据均位于本地节点。

此外，由于流是无限的，流入数据的时空分布可能随时发生变化。为获得更好的查询性能，同时保持各节点任务量均衡，对时间范围进行分割，当前时间分片以上一时间分片的采样队列为标准重新划分数据。如图1所示，采样器持续采样时空流，t₀，t₁，t₂，t₃，t₄为时空流重分区各时间点，当前时间分片为t₄至现在，上一时间分片为t₃至t₄。在t₄时刻将上一时间分片采集的样本按Hilbert值大小排序，依据节点数或并行度计算样本的分位点。t₄至现在，分发器将当前输入时空流按照计算所得分位点进行数据分发，直至下一时间点再重新计算分位点，这样，即使数据的时空分布有所变化，各节点仍能保持较好的查询性能。进一步，将针对各节点的数据建立分布式时空索引，以实现高效实时存储和低延迟时空查询。

时空流需要保证数据处理的低延迟性，在数据流入节点时进行快速存储以保证高效计算。传统的时空索引仅面向数据查询，难以保证数据的插入更新效率。本文在研究LSM树的基础上，针对时空流的高效更新问题，提出LSM-OCTree，兼顾了时空数据的更新和查询效率。

LSM树由一个驻留在内存中的和多个位于磁盘的索引树组成^［10］。只在内存中进行数据更新，当内存中的数据量达到阈值后，系统将数据批量按序写入磁盘。同时，系统通过多次合并，不断将小文件组织成有序的大文件，减少读数据时磁盘的I/O次数。由此可见，基于LSM树的分布式存储系统可极大提高数据的写入能力并保持良好的读取性能。

八叉树是一种常用的时空索引，对二维空间进行四叉树划分，对时间维度进行二叉树划分，从而将整个时空进行八叉树递归划分^［25］。如果某个子空间的数据量达到阈值，则需将该子空间划分至更深的层级。八叉树的优势在于使用规则格网直接索引点数据，并且各叶节点是不相交、不重叠的。LSM-OCTree用预先分区的方式，在数据插入前先将八叉树划分为一定层级，形成多个时空立方体，并在内存中以时空立方体为单位进行数据处理并持久化。

LSM-OCTree需要先建立最大包围框。以全球范围或传感器所在区域为空间界限，如经度范围为［-180°， 180°］、纬度范围为［-90°， 90°］。由于空间域是有限的而时间域是无限的，时间范围可以按需定义。建立八叉树后，继续对空间进行预分区，将所有数据存放于该层级及以下结点。为保持LSM-OCTree中每块数据的时空邻近性，将预分区后八叉树中的一个或多个邻近时空立方体作为数据块单位。也就是说，预分区的深度取决于预设时空立方体的大小。如图2所示，此时数据插入内存C₀层八叉树预分区层级①的2个节点。插入结束后将C₀层的索引树持久化到C₁层。当C₁层数据量达到阈值时，将C₁层的两数据块合并至C₂层。图2中指示的C₂层索引树的层级②的灰色节点中包含层级①的4个灰色节点数据。C₁层索引通过不断合并到达C_n 层。合并完成，C_n 层的索引树将包含指定时空范围的所有数据。

此外，八叉树是一种典型的树形索引。随着数据的插入，索引不断被分裂和调整，虽然可以保证各子空间中数据分布的均匀性，但对数据的高速插入有一定影响。为减少索引调整产生的开销，需将每个时空立方体划分为适当层级。当插入数据时，子空间暂时不会分裂。结合时空调度策略，首先将时空流在时间维度上进行划分。针对同一空间区域的立方体，当前时间分片将基于前一时间分片确定预划分层级。这种方式可以增强数据在内存中快速写入索引的能力。

LSM-OCTree在进行时空查询时，需要查询磁盘的每层每个索引文件，并将结果合并输出。随着时空数据的不断输入，磁盘中的索引文件不断增多，时空查询需要扫描的文件也逐渐增多，查询效率降低。因此，需要合并数据块以保持高效的查询性能。但LSM树的合并会占用部分系统资源，影响此期间的系统性能。常规的八叉树合并为遍历树中的全部数据然后逐个插入目标树，效率较低。为减少合并对系统整体性能的影响，需要进行高效的数据批量合并计算。

本文采用的八叉树预分区方式可实现数据的批量合并。由于LSM-OCTree中的每块数据只保存八叉树预分区层级中一个或多个节点及其子节点，任何2个数据块的任意数据节点互不相交。如图3所示，灰色节点表示该节点或其子节点存有数据，白色节点表示该节点未存数据。在合并过程中一般只出现2种情况。第一类情况，2个数据块的数据分别存储在同一上层父节点下的一个或多个子节点，如图3（a）所示。解决方法，只要批量地将其中一个数据块的数据复制到另一个数据块该父节点相应的其他子节点下。第二类情况，2个数据块的公共父节点在预分区层级之上的某一层，如图3（b）所示。同样，只要将数据复制到相应的节点即可。预分区和批量

合并模式能大大减少磁盘读写次数，提高合并效率，从而降低LSM树合并对系统总体性能的影响。

根据时空流的特性及LSM-OCTree的特点，提出面向时间分片的索引构建策略。如图4所示，W₁，W₂，…，W_k 分别表示时间分片，C₀，C₁，…，C_n 分别表示LSM树的层，C₀位于内存，C₁至C_n 位于磁盘。首先将时空范围进行八叉树预划分，其中每层时空立方体的时间范围对应一个时间分片。结合动态时空调度方案，八叉树预分区的阶数与Hilbert曲线的阶数相同。同一时间窗口，每个节点将处理部分空间区域的数据，即该时间窗口层的时空立方体均匀分布于各节点。沿数据流入方向，先将每个时间窗口的数据插入位于内存的C₀层八叉树索引，再作为C₁层中一个完整的数据块进行持久化。当C₁层中的数据块数量达到一定大小时，将C₁层最老的2个数据块合并至C₂层。例如，图4显示目前集群中一个并行实例在内存中接收处理W_k 时间窗口中的数据，上一时间窗口W_k-1的数据经持久化后存储，W_k-5和W_k-6时间经持久化的数据块已合并至C₂层，合并后的数据块存储了所在节点2个时间窗口的数据。最后，通过索引的不断合并，各节点形成一棵完整的存储指定时空范围所有数据的LSM-OCTree。随着时间的推移，后续又将形成一棵新的LSM-OCTree。

此外，由于时空流的持续输入，LSM-OCTree的C₀，C₁，…，C_n 层各保存了一定时间段内的数据块。为提高时空查询的效率，在内存中维持一个时间索引，该索引记录每层每个数据块的时间范围，节省了常规LSM树查询时需要遍历每层每个数据块的开销。

以该存储方案为基础的时空查询流程：给定查询条件Q（R_t，R_a ），R_t，R_a 分别表示时间范围和空间范围；如果此时内存时间窗口包含R_t，则在内存八叉树中通过判断最大包围框完成时空范围搜索；如果查询数据位于持久化磁盘，需要先通过查询内存时间索引得到LSM-OCTree中与R_t 时间相交的层级及数据块，再对每个数据块进行查询，最后将符合条件的数据加入结果集。

集群共有4个节点，各自搭载Intel（R） Xeon（R） Silver 4210 20核处理器、2.20 GHz主频、256 GB内存，采用CentOS 8.2系统、JDK 8。

所用数据下载自纽约市官方网站（https：//www1.nyc.gov/），为2014年美国纽约出租车数据集。该数据集包括出租车上客位置和下客位置，单日新增点数据约为百万条，数据总量为千万级。数据空间4至范围为［-74.258 945， 40.496 477， -73.734 772， 40.919 380］，单日数据在空间上的分布如图5所示。数据以四元组的形式d = （id， x， y， t）表现，id，x，y，t分别表示点的编号、经度、纬度和时间戳。

首先将数据逐步加载至内存，再根据一定的流速读取数据，模拟时空流。

为评估分布式环境下时空调度策略的有效性，将时空调度策略与采用常规的随机分发、哈希分发的存储结构的查询性能进行比较（图6）。由图6可知，采用时空调度策略的查询时延整体低于采用随机分发与哈希分发的查询时延。这是由于常规的分发方式使得符合查询条件的数据位于各个节点，查询时需要通过昂贵的网络通信进行交互。而时空调度策略能动态地将时空邻近的数据平均分发至各节点，减少了节点之间的数据交互，节省了全局查询和数据复制的开销，因此可提高查询效率。

面向时空流的查询，较典型的为连续请求时空数据，即使用查询流。实验将查询流按照时空分发至相应节点，并请求位于查询空间范围的当前时间分片数据，时空调度策略与常规调度模式的计算速率比较如图7所示。由图7可知，在常规调度模式下，虽然并行度增加，但每秒执行的查询任务量基本无变化。其原因为常规调度模式没有考虑时空数据的分布相关性，无法通过判断时空范围分发时空查询任务，同时符合查询条件的数据可能位于各个分区。因此需要在每个分区并行执行各查询任务，并通过网络带宽或大量磁盘空间读写进行数据交换。在此情况下，连续查询任务的执行类似于串行查询，无法充分利用集群的并行能力。而在时空调度策略下，随着并行度的提升，平均每秒执行的连续查询任务也逐步增加。但由于受CPU等计算机资源的限制，当并行度达到一定值时，程序的执行性能无法再大幅提升，查询性能趋于平缓。总的来说，时空调度策略不仅保证了各节点分配到的查询任务量相近，并且利用时空数据的紧耦合性，减少了时空查询时的数据复制，从而提高实时连续查询任务的效率。结果表明，随着并行度的增长，时空调度策略的查询性能较常规调度策略提升5倍以上。

为验证LSM-OCTree的合并性能，设计了不同合并数据量的对比实验，将LSM-OCTree的增量合并与常规八叉树的静态重构合并及动态逐一插入合并3种方式进行对比，结果如图8所示。由图8知，静态八叉树合并明显优于动态八叉树，LSM-OCTree合并优于静态八叉树。原因为动态八叉树合并方式为遍历被合并八叉树的叶子节点，读取的所有数据需逐一插入至目标八叉树，从插入数据到调整索引需要多次磁盘读写，效率较低。静态八叉树的合并方式为将两八叉树中的数据全部加载至内存，再重构包含2个八叉树所有节点数据的新八叉树，最后将新八叉树的所有节点写回，因此该批量读取和写入的方式更优，但如果数据量较大，则可能影响其整体性能或导致内存溢出。而LSM-OCTree使用预分区方法和批量合并算法，数据节点互不相交、互不重叠，被合并的八叉树一般为目标八叉树的子树，其最高数据父节点为目标八叉树预分区层级中一个或多个空节点。被合并八叉树的每个节点需要全部读一遍，目标八叉树在合并过程中只需从根节点开始读取到预分区层级一至多个空节点，在写回时也仅写入被修改的空节点及新增的子节点，使用内存较少，索引调整的开销也较少。

为验证LSM-OCTree的更新性能，将数据插入LSM-OCTree的速率与普通八叉树进行比较，结果如图9所示。由图9知，普通八叉树的即时更新涉及大量的磁盘I/O，随着数据的流入，其效率降至LSM-OCTree的10%左右。LSM-OCTree的更新涉及数据插入、持久化及合并3个过程，改进的预分区和批量合并算法有效减少了磁盘I/O，合并效率较高，因此块合并对数据快速插入的影响不大。

目前，面向时空流的分布式调度和存储方案常将HBase作为存储引擎，并采用Geohash等手段将高维数据一维化^［19］。处理集群的各节点时空数据后，以Geohash编码加时间戳和点ID为行键将数据存储至HBase。在执行时空查询任务时，在数据库中进行行键的范围检索并传输结果。在此基础上，基于HBase的二级索引存储方案将Geohash编码加时间段作为时空索引表的行键，以此索引原始数据，提高查询效率^［21］。

时空范围查询对应的常见场景是某一时间段内位于某空间范围的数据点，如前1 min位于某区域半径1 km范围的点。本实验在不同的空间范围和时间范围内，将结合动态时空调度和LSM-OCTree的分布式存储方案与HBase及基于HBase的二级时空索引存储方案进行对比，结果如图10所示。其中，图10（a）为固定随机选取时间范围后不同区域半径范围的平均时空查询时延，图10（b）为固定随机选取区域半径范围后不同时间范围的平均时空查询时延。由图10可知，HBase虽然可以通过指定行键范围避免全表扫描，但仍较二级时空索引多处理了时空索引层筛选后删除的数据，查询效率最低。本文提出的基于LSM-OCTree实现的分布式时空流存储方案的查询效率较HBase方案提升了20%以上。原因为HBase等键值数据库利用Z曲线等索引技术将高维数据转化为一维数据进行顺序存储。在查询时通过前缀匹配顺序筛选数据，筛选结果中易包含大量冗余数据，因此，数据分布、查询条件等因素影响其查询效率。而基于LSM-OCTree的分布式调度和存储方案支持原生的时空数据存储与检索，通过时间索引和八叉树进行过滤查询，在时空查询上更为灵活，效率更高。

针对传统时空索引难以保证更新效率以及HBase等分布式数据库面向时空数据的更新查询能力不足等问题，考虑数据的时空相关性，提出了一种面向时空流的分布式时空调度和存储方案。首先，利用数据的时空邻近性进行数据划分与调度，在进行局部查询的同时减少了网络通信的开销。然后，通过预分区方式构建了LSM-OCTree索引，实现了时空流的快速插入和高效的批量合并计算，提升了查询效率。最后，提出了面向时间分片的分布式存储方案，实现对时空流的实时索引和高效时空查询。实验结果显示，时空动态调度策略优于通用的调度方法。LSM-OCTree索引的合并性能优于动态八叉树与静态八叉树的合并性能，更新性能优于常规八叉树结构。与传统的HBase方案相比，基于LSM-OCTree索引的分布式调度和存储方案的查询效率提升了20%以上。由于分布式集群存在一定限制，后续研究将考虑拓展更多的计算节点和进行网络带宽优化。