时间:2022-12-18 10:30:01 | 来源:信息时代
时间:2022-12-18 10:30:01 来源:信息时代
动态流调度策略 : 数据流管理系统根据数据流的特点制定的动态的任务调度策略。调度策略是一种积极的优化策略,是影响系统的整体性能最关键的因素之一。理想的调度策略应当能够保证: ①在资源一定的情况下获得最优的性能; ②及时发现系统过载,并触发相应解决机制(如突发流量处理);③保证特定查询的QoS需求;④部署简单,操作方便。在部署调度策略时,主要性能指标包括: 对元组的响应时间、内存需要量、吞吐量、精确度等。在实施过程中,系统为达到各种性能指标的要求会发生冲突(例如较小的响应时间必然要求较大的内存),所以对实际系统而言,寻找各种指标的平衡至关重要。在具体的数据流管理系统中,往往会根据数据流的特点和要达到的目的,以部分牺牲其他性能为代价,选取其中的一种或一部分性能作为主要衡量指标。
数据流快速、无限、连续、实时的特点要求数据流系统能够实时地对数据进行处理。任务处理的主要目标是要在满足任务的截止时间情况下实现连续查询。在通常情况下,任务在执行过程中已经执行的时间以及还剩余多长时间才能执行完成是动态变化的。因此,数据流管理系统一般使用动态的调度策略。
目前流行的数据流管理系统中,主要研究在资源限制条件下如何提高系统的适应性、如何降低系统的平均延时,以及如何在近似查询结果质量与系统资源之间取得折衷等,但都没有针对查询关于截止期的要求给出切实可行的调度方法。因此,问题可归结为: 在资源限制、动态爆发的实时数据流环境中,针对数据流上查询主要是连续查询,如何设计可适应的、精确的、实时的批任务调度算法,降低调度开销最大化可满足各个查询截止期的元组数,最终使得近似查询结果质量最高。
数据流上可用于截止期动态调度的常见方法有两种:
一种是tuple-at-a-time调度,如TelegraphCQ系统中的Eddy的路由调度策略。每次调度一个元组,判断该元组是否会在当前执行的查询处理完之前到期,是则该查询直接跳过该元组处理下一个元组,反之则处理该元组。这种方法的优点在于,通过对每个元组动态选择路由,从而不断动态优化查询计划中的操作符顺序,具有很强的适应性。但在快速时变的数据流环境中,该调度策略具有很大的系统开销,如调度队列维护、内存管理及上下文切换开销等。特别是在数据流爆发的情况下,系统开销会大幅增加,使得各查询可在截止期内完成处理的数据流数据量大大减少。
第二种为批处理策略,典型的批调度策略有如下几种。STREAM系统使用Chain式调度方法,讨论在系统负载高峰时,如何优化资源管理以实现运行时内存使用的最小化。Aurora系统使用二级调度策略,对操作符以及数据流数据分别批处理,进而降低系统开销,提高处理效率。然而,上述批调度策略均基于统计计算(如服务开销,操作符选择度等),对每批数据的处理开销进行估计,因而也不能满足精确的截止期需求。例如,估算一批数据(100个数据流数据)中有80个可在截止期内完成,则使用降载策略(load shedder)丢掉其中20个。然而,实际上在截止期内完成的数据流数据很可能多于或少于80个。相应地,可能会多丢弃了一些可在截止期内完成处理的数据流数据,或者会浪费系统资源处理了一些过期数据,降低了近似查询结果的质量。