2. 清华信息科学与技术国家实验室(筹), 北京 100084
2. Tsinghua National Laboratory for Information Science and Technology(TNList), Beijing 100084, China
随着传感器技术的发展和互联网的普及，数据的采集和信息的传播速度达到了空前的水平。其中，以传感器数据为代表的时序数据开启了新的工业服务模式，提供了新的工业发展方向。
例如，三一重工在生产的每台重型机械(如泵车、挖掘机、起重机等)安装了各种类型的传感器，收集重型机械的各种参数如机械的开关信号、 GPS信息、发动机参数等，用以监控重型机械的运转情况。如果检测到机械有潜在的运转风险，那么工程机械制造商会提前派遣工程师进行维护，避免因机械停工给用户造成损失。
在这种应用场景下，传感器数据的极值、均值等聚合信息变得十分重要，如何快速准确获取这些聚合信息是本文的研究重点。例如，当重型机械的车身倾角大于10°时，会有发生倾覆的危险。那么，对车辆某段时间内的安全评估，需要查询
SELECTMAX(angle) FROM sensor WHERE time>t1 AND time ＜t2
要满足这类查询，数据库就必须支持在任意时间范围内，在海量数据上进行快速的聚合操作。
传统关系型数据库主要采用物化视图[1]或概要表的[2]方式达到加速聚合查询的目的[3]。其中，物化视图是对涉及表连接的查询命令进行预处理，并将结果保存在视图表中，用户发生查询时，数据库直接从视图表中查询并返回结果[4]。概要表则是在写入数据的同时，计算并保存相应的概要信息，从而发生查询时，直接从概要表中查询并返回结果。这两种方式的本质都是预先计算并保存常用的聚合信息，缩小查询范围，提高实际查询速度。其弊端是增加了数据库的膨胀率； 随着数据的增多，会出现性能退化的问题。
而在NoSQL数据库中，一些数据库采用了MapReduce[5]的方式来处理这些聚合操作[6]： 每次聚合查询实时从数据库中检出涉及的表数据，提交到分步程序中进行处理。在分步阶段，程序过滤出满足条件的数据并提交给化简程序[7]。化简程序汇总并计算出查询结果。另一些数据库如MongoDB则提出了聚合管道(aggregation pipeline)的概念[8]。它是结合MapReduce的思想和Linux系统管道的思想的产物。其原理是聚合操作直接作用在数据文件上，通过类系统的原生操作，直接过滤聚合文件中的数据。
MapReduce和聚合管道的方式都是实时计算的代表。虽然没有增加数据库的膨胀率，但查询过程中产生了大量的磁盘[9]和计算开销，低效耗时，无法满足即席查询的需求。
一些NoSQL数据库则将物化视图的思想应用其中： 预先计算计数、求和等常见统计信息，并保存在视图表中，后续持续增量更新，以达到加快查询响应的目的[10, 11]。相比在NoSQL数据库上进行MapReduce计算，这种方式速度提升非常明显，但也有其弊端。物化视图本身的形成机制决定了其不支持任意范围的查询操作[12]。另外，随着数据量的上升，查询操作的磁盘开销也会增大[13]。
基于上述问题，本文提出了一种支持NoSQL数据库聚合操作的索引机制。其基本思想是将概要表和线段树(Segment Tree)结合起来，在概要表上建立由多棵线段树构成的线段森林模型，从而避免概要表的全表扫描操作。同时，通过自底向上的方式动态构建线段森林，回避了传统线段树不支持增长的缺点。此外，查询算法通过计算直接定位索引数据，避免了对线段森林的递归遍历操作，减少了磁盘IO次数。本文在Cassandra数据库上实现了上述的索引引擎，并设计2组对比实验： 基于数据的直接查询和基于概要表的直接查询。实验结果表明： 这种索引机制有效减少了磁盘IO的次数，显著提升了查询性能。
1 概要森林的构建实现 1.1 数据模型和查询需求定义1 一个数据项D(data point)是一个三元组(s,t,v)。其中s是传感器ID，t是时间戳，s和t构成了全局唯一的标识，v是传感器的值。同一个传感器的连续时间的数据项构成了时序数据。
在此基础上，定义本文要解决的查询问题： 在时序数据上，查询时间窗口t1~t2(t1和t2为任意时刻)内的时序数据的最值、方差等统计信息。
1.2 概要森林本节借鉴概要表和线段树的思想，描述概要森林的相关概念。首先，通过对时序数据提取概要，生成概要信息序列。
定义2 在时序数据中，k个在时间上连续的数据项的统计信息及其时间窗口构成1个概要信息(data Digest)。
一个传感器在t1~t10时间内连续发送了10个数据项。假设每5个数据项构成1个概要信息，则概要信息如图1所示。
|
| 图1 10个数据项生成2个概要信息 |
通过概要信息的提取形成了概要表，大幅减少了所需查询的数据量。然而，随着时序数据的增多和概要表的增长，仍不利于快速访问。因此本文在概要表基础上建立概要森林。概要森林由概要树构成，而概要树由叶子结点和中间结点构成。
定义3 由数据项直接产生的概要信息加上特定的标记信息构成了叶子结点(leaf node)。
定义4 由2个叶子结点或2个中间结点汇总加上特定的标记信息构成了中间结点(parent node)。
为了在避免树的递归操作，实现概要森林的快速检索，本文在叶子结点和中间结点上添加了必要的标记信息： 序号(serial)和编号(code)。
定义5 初始建立索引时，依据产生顺序，每个叶子结点对应1个序号，序号由1开始递增。中间结点没有序号。
定义6 依据线段森林后序遍历的顺序，每个结点对应1个编号，编号由1开始递增。
定义7 概要森林(synopsis forest)是由结点产生的概要树构成的森林。
图2中，上半部分表示概要森林。其中灰色圆圈表示叶子结点，白色圆圈表示中间结点。每个结点左边的数字表示该结点对应的编号。叶子结点下方的数字表示该结点对应的序号。每个叶子结点包含了k个数据项的概要信息。下半部分的线段表示森林中各个结点对应的时间窗口。时间窗口是按线段森林的层次自上而下反向排列的。可以看出，直接上层结点对应的起止时间点(时间窗口)是其直接下层结点中左结点的起始时间点和右结点的终止时间点。同时，概要信息也是2个直接下层结点的统计汇总。
|
| 图2 概要森林与时间窗口 |
为了实现概要森林的动态增长，本文采用自底向上的生成方法进行的构建。在此过程中，需要定义森林中的树的合并规则。
定义8 树的合并规则为： 每当森林中有两棵紧邻的、高度相同的树时，由这两棵树的根结点生成1个新的根结点并构成一棵树。树的左右子树是原先的两棵树。
1.3.1 概要森林的生长过程概要森林的具体构建过程如图3所示：
|
| 图3 概要森林的生长过程 |
1) 当第1个叶子结点到来时，该结点自成一棵树，且概要森林仅由这棵树构成。
2) 当第2个叶子结点到来时，第2个叶子结点先自成一棵树，然后触发树的合并规则，产生一棵高度为2的新树。此时，概要森林中仅剩一棵三结点的树。
3) 当第3个叶子结点到来时，不满足森林的合并规则，该结点自成一棵树。此时，概要森林由一棵三结点的树和一棵单结点的树构成。
4) 第4个叶子结点到来时，该结点自成一棵树，接着触发森林的合并规则，产生一棵高度为2的新树，其2棵子树是原高度为1的树。继续触发树的合并规则，产生一棵高度为3的新树，其2棵子树是2棵高度为2的树。此时，概要森林又变成仅由一棵七结点的树构成。以此类推，概要森林就逐渐建立起来。
1.3.2 序号和编号的生成在上述概要森林的构建和生长过程中，每新增1个序号为i的叶子结点，需要做如下操作：
1) 若i为奇数，则直接添加该叶子结点，该叶子结点自成一棵树。此时，该叶子结点对应的序号为i，编号为2i-ones(i)。其中，ones(i)函数为i的二进制表示中1的个数。
图4中，对于序号为3的叶子结点，编号2×3-ones(i)，则第3个叶子结点的编号为6-2=4。
|
| 图4 添加序号为奇数的结点 |
2) 若i为偶数，在添加该叶子结点的同时，生成由该叶子结点触发生成的新树。此时，该叶子结点对应的序号为i，编号为(i-1)叶子结点的编号加1即2(i-1)-ones(i-1)+1。产生的树的根结点编号为2i-ones(i)，其余中间结点的编号依次为2(i-1)-ones(i-1)+2到2i-ones(i)-1。
图5中，对于序号为4的叶子结点，由上述规则得到其编号为5，同时，触发树的合并规则，产生编号为6和7的中间结点，构成以编号7为根结点的新树。
|
| 图5 添加序号为偶数的结点 |
编号为3的中间结点是先前产生，并保存到数据库中的结点，如果这里不做特殊处理，那么需要到数据库中查询出编号为3的中间结点，会造成一定的查询开销。
可以发现这些触发合并的是概要森林中高度最小且相同的根结点。例如，编号为6的中间结点合并的是两棵高度为1的概要树(编号为4和5的叶子结点)； 编号为7的中间结点合并的是两棵高度为2的的概要树(编号为3和6的中间结点)。
因此本文采取一个策略： 在内存中维护1个根结点的栈，每当产生一棵线段树时，在栈中保存这棵树的根结点； 当产生中间结点时，从栈中弹出2个根结点，作为中间结点的直接下层结点。
1.3.3 添加叶子结点的算法由序号计算编号，具体伪代码如图6所示。
|
| 图6 序号转编号算法serialToCode |
添加1个叶子结点的过程是，从内存中读取上一个当前已插入概要包的最大序号并自增1。将待处理的概要包的序号赋值为最大序号。通过序号计算出该概要包的编号。将概要包压入栈中，并添加到待持久化的队列中。如果序号是偶数，需要通过父节点生成算法生成一系列的中间结点，并将这些中间结点添加到待持久化的队列中。否则，直接把待持久化的队列持久化。具体伪代码如图7所示。
|
| 图7 添加叶子节点算法AddDigestNode |
图7中产生中间结点的过程是自叶子结点的编码数加1到最大的编码依次生成中间结点，每次从栈中弹出2个根结点，用这2个根结点生成1个新的中间结点。并将该中间结点压入栈中。具体伪代码如图8所示。
|
| 图8 生成中间节点算法generateParent |
根据线段森林的结构，可以定义出线段森林的查询过程。以查询时间窗口ta~tb对应数据项的概要信息为例，不失一般性的，ta和tb是整个线段森林所覆盖的时间段中，任意2个时间点构成的时间窗口。具体查询步骤如下：
1) 标准化时间窗口。假设tis ＜ta＜tie、 tjs＜tb＜tje，则可将查询的时间窗口划分为3个时间窗口： ta＜tie，t(i+1)s~ t(j-1)e和tjs＜tb；
2) 对于时间窗口ta＜tie和tjs＜tb，需要从数据库中直接读取ta到tie和tjs到tb的数据项，并从数据项中直接计算出这段时间窗口的概要信息；
3) 对于时间窗口t(i+1)s~ t(j-1)e，从线段森林中找出最少数量的线段(时间窗口)，使得这些线段称为时间窗口t(i+1)s~ t(j-1)e的划分。假设一共需要s个线段，依次从数据库中读取这s个线段对应的概要结点，得到s个概要信息；
4) 由步骤2和3中的(s+2)个概要信息即可计算出时间窗口ta~ tb的概要信息。
这里需要说明的是，叶子结点的数据项数量和时间窗口是可控的。当数据库为给定数据项数量和时间窗口时，叶子结点涵盖的数据项数量越多或时间窗口越大时，步骤1所需查询的数据项就越多，数据项的查询开销相应提高，而线段森林的高度就越低，线段森林的查询开销相应降低。
另外，可以证明的是，对于最高高度为h的森林，步骤3所需的线段数最多为h条。因此，该操作至多需要读取h个结点。
以上步骤的关键是对t(i+1)s~ t(j-1)e部分的查询。下面重点说明如何用线段森林进行索引查询的。
1) 根据起始时间t(i+1)s和t(j-1)e从数据库中读取出2个相应的概要包，从概要包分别得到对应的序号i和j；
2) 获取下界序号： 如果i是偶数，把t(i+1)s对应的概要包添加到待处理队列，此时下界序号为(i+1)。否则，下界序号为i；
3) 获取上界序号： 如果j是奇数，把t(j-1)e对应的概要包添加到待处理队列，此时上界序号为(j－1)。否则，上界序号为j；
4) 由上界序号计算出对应的编号，以及覆盖该序号对应结点的最上层结点的编号；
5) 由编号和最上层结点的编号计算出最上层结点覆盖的最左叶子结点的序号(简称为最左序号)；
6) 如果最左序号大于下界序号，则将最上层结点的编号加入待查询队列，并把上界序号设置为最左叶子结点的序号减1，转步骤4；
7) 如果最左序号小于下界序号，则最上层结点的编号减1，转步骤5； 相应的概要包，并将这些概要包添加到待处理队列中。
图9中，假设需要查询序号为3~11的概要信息，具体的搜索过程如下：
上界序号为奇数11，将概要包11添加到待处理队列。则上界序号变成10。
由10对应的最上层的中间结点的编号是18，18的最左结点的序号为9，9大于下界序号3，则将18加入待查询队列，上界序号减1，变成8。
8对应的最上层的中间结点的编号是15，15对应的最左结点的序号是1，1小于下界序号3，则最上层结点的编号减1，变成14。
14对应的最左结点的序号是5，5大于下界序号3，则将14加入待查询队列，上界序号减1，变成4。
4对应的最上层结点的编号是是7，7对应的最左结点的序号是1，1小于下界序号3，则最上层结点的编号减1，变成6。
6对应的最左结点的序号是3，3等于下界序号3，则将6加入待查询队列。
最后，共需要从数据库中读取编号为18、 14、 6的概要包。
|
| 图9 概要森林的搜索过程 |
上述的查询过程的具体查询伪代码如图10所示。
|
| 图10 查询过程算法query |
serialToParentCode的具体查询伪代码如图11所示。
|
| 图11 通过序号计算父亲节点编号算法serialToParentCode |
可以证明，对于n个结点，需要从数据库中读取的结点数为O(lbn)。首先，通过增加中间结点，将概要森林补充成完整的二叉树(至多补充(n-2)个叶子即可)，如图12所示。此时，一个查询操作需要查询的结点数与普通段树相同，因为普通段树的查询数为O(lbn)，所以本文的查询数也为O(lbn)。
|
| 图12 通过添加虚拟结点构建线段树 |
本文使用的实验环境为单结点的NoSQL服务器，数据库为Cassandra2.1.7 ，操作系统是Ubuntu12.04，硬件为Intel Core(TM) i7-4790K 4 GHz CPU和8 GB内存。
由定义1，本文模拟传感器产生的、连续的三元组时序数据，并将这些时序数据导入到数据库中。其中，三元组数据是等时间间隔的，数值类型为int的数据项。在导入的同时，导入程序对每100个数据项生成一个概要包，同时插入到索引数据库中。本次实验中，共计导入5亿个随机的传感器数据，产生并插入500万个概要包。一个概要包的大小是数据项的5倍，即数据库膨胀率在5%左右。
实验1 采用对原始数据的直接搜索作为基准线。该数据库设计并没有采用概要表，因此对于聚合操作，只能从数据库中扫描出在时间窗口内的数据，实时计算这些数据的概要信息。结果如图13所示。
|
| 图13 无概要表的直接聚合查询 |
可以看出，当聚合查询的时间窗口逐步扩大时，直接聚合操作的查询耗时成指数上升。当时间窗口到达到2 500 000个数据项时，做一次聚合操作的耗时已经达到15 s左右，无法满足快速即席查询的需求，因此不再在更大规模的数据上作聚合操作。
实验2 采取构建简单概要表的形式，即只做概要包抽取，不对概要包建立线段森林。查询时，对于节2具体查询步骤2对应的时间窗口，采用实验1的方式直接搜索； 对于具体查询步骤3对应的时间窗口，对概要表进行直接范围搜索。结果如图14所示。
|
| 图14 基于概要表的直接聚合查询 |
可以看出，基于概要表的直接聚合查询效率提升明显。当时间窗口在2亿个数据点以下时，一次聚合查询的耗时在4 s以下； 但当时间窗口增长到4亿个数据点时，查询耗时增加到10 s左右。随着时间窗口的扩大，查询耗时与查询的范围大小成比例上升。其原因是，概要表本质上也是一张数据表。如果没有特殊的查询机制，随着数据量的上升，概要表也会逐步变大，直到无法满足查询检索的性能需求。
一个解决办法是在概要表之上再建立概要表，形成多层次的概要表结构。但这种办法会明显增加数据库的膨胀率，也会增大导入程序和查询引擎的设计复杂度。
实验3 利用本文提出的索引结构和查询方式进行聚合查询，结果如图15所示。
|
| 图15 基于概要森林的聚合查询 |
可以看出，随着时间窗口的扩大，查询耗时变化不明显。在4亿规模的窗口查询中，查询耗时仍能控制在60 ms以内，满足即席查询的需求。
由图16可以直观看出传统概要表和基于概要森林的检索查询在性能上的差异性。
|
| 图16 概要表和概要森林的查询性能对比 |
图17和18说明了基于概要森林的聚合查询的优越性： 随着时间窗口的增长，需要查询的概要信息的数量上升不明显。节2已指出，算法所需查询的概要信息的数量和概要森林的最大树高成正比关系，而最大树高和概要信息的数量是成正对数关系，也就是说即使有21 000个概要信息，也仅需查询不到1 000个概要信息点。
|
| 图17 基于概要森林的聚合查询 |
|
| 图18 基于概要森林的聚合查询 |
本文提出支持时序数据聚合函数的索引，能够支持简单聚合操作的快速即席查询。在查询过程中，该索引机制能够避免了大量的磁盘开销，解决了物化视图和概要表随着数据量增长导致的性能下降的问题。通过对比实验可以看出，这种索引机制的效率远高于现有NoSQL数据库的索引机制。另外，这种索引机制与底层数据库无关，通过自实现的基于JAVA的查询引擎，可以轻松移植到任意数据库平台中。下一步将继续开发相应的查询引擎，使索引机制和查询引擎在分布式方面很好地配合起来，同时研究概要森林的结点的动态变更问题。
| [1] | Karaman S, Frazzoli E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7):846-894. |
| [2] | Gehrig S K, Stein F J. Collision avoidance for vehicle-following systems[J]. Intelligent Transportation Systems, IEEE Transactions on, 2007, 8(2):233-244. |
| [3] | Brandt T, Sattel T, Wallaschek J. Towards vehicle trajectory planning for collision avoidance based on elastic bands[J]. International Journal of Vehicle Autonomous Systems, 2007, 5(1-2):28-46. |
| [4] | McNaughton M, Urmson C, Dolan J M, et al. Motion planning for autonomous driving with a conformal spatiotemporal lattice[C]//Robotics and Automation (ICRA), 2011 IEEE International Conference on. Shanghai, China:IEEE Press, 2011:4889-4895. |
| [5] | Ziegler J, Stiller C. Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios[C]//Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on. IEEE Press, 2009:1879-1884. |
| [6] | Ma L, Xue J, Kawabata K, et al. Efficient sampling-based motion planning for on-road autonomous driving[J]. Intelligent Transportation Systems, IEEE Transactions on, 2015, 16(4):1961-1976. |
| [7] | Kuwata Y, Karaman S, Teo J, et al. Real-time motion planning with applications to autonomous urban driving[J]. Control Systems Technology, IEEE Transactions on, 2009, 17(5):1105-1118. |
| [8] | Lin C F, Juang J C, Li K R. Active collision avoidance system for steering control of autonomous vehicles[J]. Intelligent Transport Systems, IET, 2014, 8(6):550-557. |
| [9] | Papadimitriou I, Tomizuka M. Fast lane changing computations using polynomials[C]//American Control Conference, 2003. Proceedings of the 2003. Denver, CO, USA:IEEE Press, 2003:48-53 vol.1. |
| [10] | 付骁鑫, 江永亨, 黄德先, 等. 一种新的实时智能汽车轨迹规划方法[J]. 控制与决策, 2015, 30(10):1751-1758. FU Xiaoxin, Jiang Yongheng, Huang Dexian, et al. A novel real-time trajectory planning algorithm for intelligent vehicles[J]. Control and Decision, 2015, 30(10):1751-1758. (in Chinese) |
| [11] | Chen C, Lin J, Yücesan E, et al. Simulation budget allocation for further enhancing the efficiency of ordinal optimization[J]. Discrete Event Dynamic Systems, 2000, 10(3):251-270. |
| [12] | Ho Y, Zhao Q, Jia Q. Ordinal Optimization:Soft Optimization for Hard Problems[M]. New York:Springer US, 2007. |
| [13] | Bai L, Jiang Y, Huang D. A novel two-level optimization framework based on constrained ordinal optimization and evolutionary algorithms for scheduling of multipipeline crude oil blending[J]. Industrial & Engineering Chemistry Research, 2012, 51(26):9078-9093. |