论文部分内容阅读
随着计算机软硬件的发展以及应用水平的提高，事件流应用越来越多的出现在网络安全、金融分析、传感器网络等领域中。目前已用于国家网络安全监控应用的DBroker系统作为一种基于并行数据库架构的解决方案，在很长一段时间都较好的满足了事件流应用的需求，然而随着数据规模的持续增长，这种架构逐渐显露出其局限性。
分析事件流应用的特点以及DBroker的局限性之后，我们基于开源Hadoop和MySQL软件重新构建出了一个优化的事件流数据管理原型系统DBEHadoop，用以解决大规模事件流数据应用的挑战。在构建DBEHadoop原型的过程中，我们解决了系统中的多个关键问题，所做的创新性工作如下：
1.针对事件流数据的特点，提出了一种对事件流数据按照时间维度进行在线排序的方法(OSTS)。在有限的内存空间中对无穷的持续事件流进行有序化面临着很大的难度，通常的方法或者无法保证排序质量，或者难以获得好的性能。通过对真实数据的观察，我们发现了事件流数据在时间维度上呈现出相对稳定的滑动时间窗口特征。利用这个特征，我们推导出了描述流数据滑动时间窗口行为的数据模型，并根据这一模型在内存中模拟滑动窗口，在对窗口内数据排序的基础上准确控制数据子集的输出时机与粒度，从而实现对流数据进行时间有序化的目的。在这种排序模型下，我们进一步推导出性能的代价模型，从而动态选择性能较优的排序算法。我们在真实数据集以及合成数据集上对比了OSTS与分别代表理想质量和性能的另外两种排序方法，OSTS保证排序质量的前提下，最大程度的获得了好的性能，实现了质量与性能的理想平衡。
2.针对事件流数据非独立同分布的特点，提出了基于动态分片的在线聚合算法。传统在线聚合算法假设数据集的数值是独立同分布的，这在包括事件流应用在内的很多应用场景中都不成立，从而导致算法产生了很大的误差。我们通过在数据集的多个分片上同时采样，根据统计学原理使用多个局部样本综合计算，可以实现对全局数据的准确估值；通过引入动态分片调整的策略，使得分片采样计算的过程在不损失准确性的同时，最大程度减少了I/O的随机性，提高了执行性能。真实数据集上的实验表明，基于动态分片的在线聚合算法在比传统算法性能损失约13％的代价下，将执行中的最大误差从20％降低到了5％以内，平均相对误差减少了6倍左右，使得近似查询模式在现实环境中真正可用。
3.提出了在MapReduce中使用索引的方法。针对MapReduce的执行方式，对B+树索引结构进行了调整，在此基础上，引入了在MapReduce执行过程中通过并行访问索引来获取数据的机制。对于MapReduce的传统全数据扫描执行方式以及索引访问执行方式，分别给出了性能代价模型，用来进行执行方式的动态选择。实验表明，在查询条件过滤因子较小的情况下，MapReduce索引访问执行方式性能相对于全数据扫描执行方式性能最多可提升1倍；同时，通过对比真实性能和模型预测值，证明了代价模型的有效性。
4.提出了一种将数据库执行引擎与Hadoop系统相结合的方法。为了利用数据库在执行效率上的优势，我们将数据库执行引擎集成进了基于Hadoop构建的系统中，形成了DBEHadoop系统的核心。通过对数据库存储引擎的改造，使得数据库可以以数据块的粒度对存储在HDFS上的数据进行访问和计算，从而与HDFS和MapReduce充分融合在一起。这种架构利用Hadoop系统解决了大规模环境下并行性能、扩展性、容错性等方面的问题，同时保留了数据库执行引擎对内存数据计算上的高效性。实验表明，DBEHadoop很好的解决了数据库数据写入与并行执行性能的问题，相比DBroker数据写入性能提升了5倍以上，查询执行性能最多可提升一个数量级。