数据流系统中卸载技术研究综述

随着数据流应用系统的快速流行,流数据管理对数据库技术提出了巨大挑战。由于数据流经常是爆发性的且数据特征可能随时变化,因此要求数据流管理系统具有很好的自适应性。当输入速率超过系统处理能力时,系统会产生过载且性能下降。为了解决这一问题,卸载技术是有效的途径之一。卸载时间、卸载地点和卸载数量是与卸载技术密切相关的三个主要问题,本文主要从这三个方面来综述和分析目前各个数据流系统所采用的卸载技术。     

一种考虑实时约束的数据流卸载技术

在数据流管理系统中,流数据的高到达速率和进发性等特点会引起系统过载,为此人们提出了各种卸载技术来缓解过载问题.目前几乎所有的卸载技术都使用随机丢弃数据的方法,由于随机丢弃数据策略对数据丢弃过程没有任何控制,这对某些考虑实时约束的数据流管理系统是不适合的.本文认为更为精确的卸载模型,比如文中使用的(m,k)截止期模型,更适合于一类重要的实时数据流事件检测应用.基于(m,k)截止期模型,提出一种新的策略SOSA,该策略一方面提供了可证明的卸载能力,同时也保证了系统的时间约束.为验证SOSA的有效性,设计了一种新的数据流调度算法SOSA-DBP.理论分析与模拟实验证明了SOSA-DBP比现有的算法有更好的性能.     

一种数据流滑动窗口范围连接上基于局部特征的查询索引

在数据流上的连续查询操作中,连接操作是比较重要的一类操作.数据流上数据的变化总体上呈现一个连续性,并且在很多实际的情况下变化是逐渐发生的.数据流系统中的局部性可以表现为数据之间的局部性及连续查询之间的局部性.认为这些特性可以被用来提高数据流系统和应用当中的查询处理性能,尤其是研究相对较少的范围连接.提出的一种基于局部特征的数据流滑动窗口的范围连接索引,充分考虑了用户提交的查询所带有的局部性特征和数据流本身局部性特征,设计了LAQI结构来提高范围连接性能,然后在此基础上提出了LAAQI结构,并针对周期更新滑动窗口提出了范围连接的相应策略.实验证明,这些策略相对于传统范围的连接方法具有很好的性能.     

基于滑动窗口的数据流连接聚集查询降载策略

基于单个数据流的滑动窗口聚集查询降载技术和数据流连接技术,提出滑动窗口模型下的数据流连接聚集查询降载策略,给出判断系统是否过载的负载方程和使过载系统恢复到轻载状态的降载算法,使降载后的查询结果同时拥有较小的相对误差和最大的元组输出率。实验结果表明,该降载策略具有较好的可行性和适应性。     

数据流上加权共享滑动窗口的连接查询处理算法

在数据流应用中,系统经常需要处理大量的滑动窗口连续查询,采用共享滑动窗口技术可以有效节省存储空间,提高系统整体的查询处理能力。但是共享滑动窗口技术会增大单个查询的响应延迟,降低单个查询的服务质量。针对这个问题,论文提出了加权共享滑动窗口的概念,并提出了三种优化的连接执行算法,优先响应重要的滑动窗口查询,从而提高了系统整体的服务质量。理论分析和实验结果表明论文提出的方法是行之有效的。     

基于控制理论的数据流QoS自适应框架及卸载技术的研究

数据流管理系统中的查询处理需要满足各种服务质量(QoS)要求,其中延迟是用户非常关注的QoS参数.如何在系统资源有限、数据输入速度及特征可变,且单个元组的CPU处理代价动态变化的情况下,使系统具有自适应的能力以确保高质量的QoS,是迫切需要解决的问题.为此,提出了一种全面考虑CPU处理能力及内存容量的QoS自适应框架,并运用基于控制理论的PID控制器管理内存负载,超载时进行卸载处理;同时提出有效的清洗策略和队列调度策略,保证系统在动态环境中具有良好的自适应性.实验结果表明,该框架具有稳定性好、健壮性强的优点,在错失率相同的情况下,卸载率、系统资源利用率等几方面性能均优于其他现有方法.     

数据流与磁盘存贮表的连接计算算法

数据流与存贮表的连接查询经常出现在主动式数据仓库的维护中,与传统的关系数据库的连接计算不同,数据流快速处理的要求不允许将数据流先存入磁盘再计算,而计算机内存无法存储无界增长的数据流,因此数据流查询采用先处理再存储结果的计算方式。数据流与存贮表的连接计算算法重点要解决内存开销和处理速率二个问题。MESHJOIN算法最早提出将存贮表划分为若干个数据块,将数据块交替放入内存与数据流窗口完成连接计算。在MESHJOIN算法思想的基础上将存贮表的内存数据块也划分为若干逻辑分区,每次连接计算仅替换其中的一个逻辑分区,有效地降低了数据流滑动窗口所需的I/O代价,从而提高滑动窗口的计算速率。最后通过实验对二种算法在内存开销和计算速率进行了比较。     

挖掘滑动窗口中的数据流频繁模式

随着数据流应用的不断增多,数据流环境下的数据挖掘技术受到了越来越多的关注.文章结合数据流的特点,提出一种新的基于滑动窗口的频繁模式挖掘算法:DSFPM.算法分块挖掘数据流,在内存中维持一个用于保存所有潜在的频繁模式信息的存储结构DSFPM-Tree,并在各个基本窗口进入滑动窗口后动态更新该存储结构.算法仅处理和保存各个基本窗口的临界频繁闭合项集,极大地提高了时间和空间效率.实验结果表明,该算法具有良好的性能.     

一种支持实时性查询的数据流操作语言

论文提出一种数据流管理系统中支持实时性查询的数据流操作语言PQL。PQL以SQL_99为蓝本,引入了时间戳、快照窗口、标记窗口、滑动窗口以及连续查询等一系列相关概念,对数据流连续查询中的近似查询和查询的实时性也给出了充分的语法和语义支持。PQL充分地实现了数据流的操作特征,它不仅可以实现数据流上的选择、投影、连接等操作,支持物理时间和逻辑时间两种时间戳,而且可以实现数据流与关系表的连接操作。     

一种基于遗传算法的多边缘协同计算卸载方案

边缘计算(Edge Computing,EC)作为云计算的补充,在处理lOT设备产生的计算任务时可以保证计算的延时符合系统的要求。针对在传统卸载场景中,由于计算任务到达存在空窗期导致异地边缘云存在空闲状态,造成异地边缘云利用不充分的问题,文中提出了一种基于遗传算法的多边缘与云端协同计算卸载模型(Genetic Algorithm-based Multi-edge Collaborative Computing Offloading Model,GAMCCOM)。该计算卸载方案联合本地边缘和异地边缘进行任务卸载,并采用遗传算法进行求解,从而得到同时考虑时延和能耗的最小的系统代价。通过仿真实验结果可知,在综合考虑卸载系统的时延消耗和能量消耗的情况下,该方案相比基本的三层卸载方案系统整体代价降低了23%,在只考虑时延消耗和只考虑能量消耗的情况下依然分别能够降低系统代价17%和15%。因此针对边缘计算的不同卸载目标,GAMCCOM卸载方案对系统代价均有比较优秀的降低效果。