基于延迟调度策略的Reduce调度优化算法

在大规模的Hadoop集群中,良好的任务调度策略对提高数据本地性、减小网络传输开销、减少作业执行时间以及提高集群的作业吞吐量都有着重要的影响。本文针对Hadoop架构中Reduce任务的数据本地性较低问题,提出了一种基于延迟调度策略的Reduce任务调度优化算法,通过提高Reduce任务的数据本地性来减少作业执行时间以及提高作业吞吐量,该算法在Hadoop架构的Early Shuffle阶段,使用多级延迟调度策略来提高Reduce任务的数据本地性。最后重写原生公平调度器代码实现了该调度算法,并与原生公平调度器进行了对比实验分析,实验结果表明该算法明显减少了作业执行时间,提高了集群的作业吞吐量。     

基于禁忌搜索的流式计算平台负载均衡策略

针对大数据流式计算平台原生的调度机制存在计算负载分配不均衡、资源利用率低的问题,提出异构环境下基于禁忌搜索算法的负载均衡策略,并将其应用于Apache Flink平台。首先,通过构建作业拓扑模型将流式计算作业的拓扑结构抽象为有向无环图（directed acyclic graph,DAG）,并将每个任务槽（task slot）抽象为节点,为计算节点的性能评估奠定基础;其次,通过建立性能评估模型将有向无环图中带性能权值的节点导入性能评估模型,进行归一化处理得到节点性能的优劣;再将评估参数传入禁忌调度算法（tabu search for schedule,TBS）进行作业路径优化,从而得出最优作业路径;最后,使用Flink平台提供的CustomPatitionerWrapper接口将数据分配到最优作业路径包含的节点中,完成计算负载的均衡分配,从而提升Flink平台的整体性能。实验结果表明：通过禁忌调度算法优化后的负载均衡策略与原生的Flink平台相比,平均计算延迟降低了10~20 ms,资源利用率显著提高,平均吞吐量提升约15%,有效证明了负载均衡策略的有效性和优化效果。     

基于异构Flink集群的节点优先级调度策略

Flink流处理系统默认的任务调度策略在一定程度上忽略了集群异构和节点可用资源,导致集群整体负载不均衡。研究分布式节点的实时性能和集群作业环境,根据实际作业环境的异构分布情况,设计结合异构Flink集群的节点优先级调整方法,以基于Ganglia可扩展分布式集群资源监控系统的集群信息为依据,动态调整适应当前作业环境的节点优先级指数。基于此提出Flink节点动态自适应调度策略,通过实时监测节点的异构状况,并在任务执行过程中根据实时作业环境更新节点优先级指数,为系统任务找到最佳的执行节点完成任务分配。实验结果表明,相比于Flink默认的任务调度策略,基于节点优先级调整方法的自适应调度策略在WorldCount基准测试中的运行时间约平均减少6%,可使异构Flink集群在保持集群低延迟的同时,节点资源利用率和任务执行效率更高。     

基于Apache Flink的RDF流数据查询

目前成熟的RDF流处理（RDF Stream Processing, RSP）系统由于集中式的设计而缺乏并行处理特性,因此在查询处理大量传入的RDF流数据时,均无法实现高吞吐和低延迟。为提高查询性能,本文对RSP查询过程和Flink流计算结构进行研究,设计数据源、滤器、多路分区连接和投影4个逻辑操作符,并设计一种多流连接（Multi-Stream Join, MSJ）算法用于生成具有并行性的有向无环图的逻辑查询计划,最后以大数据流处理平台Apache Flink为底层实现逻辑操作符和逻辑查询计划。使用真实数据集SRBench和模拟数据集LUBMs进行实验验证。结果表明,与最成熟的系统C-SPARQL、CQELS相比,单机吞吐量增长高达10倍,5台机器集群的吞吐量增长高达28倍,同时在延时方面达到了毫秒级;在查询性能方面实现了处理大量RDF流数据时吞吐量的提高和延时的降低。     

Flink水位线动态调整策略

衡量大数据的数据挖掘性能有2个最重要的任务指标：一是实时性，二是准确性。流数据从数据产生到消息队列再通过数据源流入Flink进行计算，这个过程中因为网络传输速度不同，不同节点的计算性能不同等原因，流数据进入计算框架的先后顺序和数据产生的事件时间顺序会有局部乱序的现象。面对窗口作业的传统水位线机制在不确定乱序程度的流数据情况下无法同时兼顾作业结果的实时性和准确性。针对这个问题，建立了流数据微簇模型。通过局部乱序度算法，根据流数据微簇的流数据事件时间局部乱序程度计算出可以代表当前时刻流数据的乱序度。设计了水位线动态调整策略，使水位线根据流数据的乱序程度动态调整大小。最后，在Apache Flink框架中对基于事件时间窗口的水位线动态调整策略进行了实现。实验结果表明，弹性或不确定乱序流数据条件下，基于事件时间窗口的水位线动态调整策略可以有效地同时兼顾窗口作业的准确性和实时性。     

面向SDN数据中心网络最大概率路径流量调度算法

随着数据中心网络规模的迅速增长,网络带宽利用率低下导致的网络拥塞问题日益突出,通过负载均衡提高数据中心网络链路带宽利用率和吞吐量成为了研究热点.如何结合流量特征、链路状态和应用需求进行流量的合理调度,是实现网络链路负载均衡的关键.针对数据中心突发性强、带宽占用率高的大象流调度问题,提出一种面向SDN数据中心网络最大概率路径流量调度算法,算法首先计算出满足待调度流带宽需求所有路径,然后计算流带宽与路径最小链路带宽之间的带宽比,结合所有路径的带宽比为每一条路径计算路径概率,最后利用概率机制选择路径.算法不仅考虑了流带宽需求和链路带宽使用情况,而且全局地考虑了流调度和链路带宽碎片问题.实验结果表明,最大概率路径调度算法能够有效地缓解网络拥塞,提高带宽利用率和吞吐量,减少网络延迟,从而提高数据中心的整体网络性能和服务质量.     

基于Storm拓扑结构热边的调度算法

Storm分布式实时计算系统采用轮询调度算法达到任务均衡分配的目的,但Storm默认调度算法未考虑计算节点间的网络通信开销,可能造成topology处理时延高、集群吞吐量低等问题。为此,引入Storm topology热边的概念,通过减少网络传输的tuple数量,将热边关联的源executor和目标executor调度到同一工作节点执行,提升Storm集群的计算性能。实验结果表明,该调度算法能够有效降低Storm处理时延及集群节点间的通信量,提高系统吞吐量,并且有利于集群的负载均衡。     

基于Storm平台的数据恢复节能策略

作为目前主流的大数据流式计算平台之一,Storm在设计之初以性能为目的进行研究而忽视了高能耗的问题,但是其高能耗问题已经开始制约着平台的发展.针对这一问题,分别建立了任务分配模型、拓扑信息监控模型、数据恢复模型以及能耗模型,并进一步提出了基于Storm平台的数据恢复节能策略(energy-efficient strategy based on data recovery in Storm,DR-Storm),包括吞吐量检测算法与数据恢复算法.其中吞吐量检测算法根据拓扑信息监控模型反馈的拓扑信息计算集群吞吐量,并通过信息反馈判断是否终止整个集群内拓扑的任务.数据恢复算法根据数据恢复模型选择备份节点用于数据存储,并通过拓扑信息监控模型反馈的信息判断集群拓扑是否进行数据恢复.此外,DR-Storm通过备份节点内存恢复集群拓扑内的数据,并根据大数据流式计算的系统延迟与能效评估DR-Storm.实验结果表明:与现有研究成果相比,DR-Storm在减少系统计算延迟、降低集群功率的同时,有效节约了能耗.     

面向Dataflow的异构集群混合式资源调度框架研究

Dataflow模型的使用,使得大数据计算的批处理和流处理融合为一体.但是,现有的针对大数据计算的集群资源调度框架,要么面向流处理,要么面向批处理,不适合批处理与流处理作业共享集群资源的需求.另外,GPU用于大数据分析计算时,由于缺乏有效的CPU-GPU资源解耦方式,降低了资源使用效率.在分析现有的集群资源调度框架的基础上,设计并实现了一种可以感知批处理/流处理应用的混合式资源调度框架HRM.它以共享状态架构为基础,采用乐观封锁协议和悲观封锁协议相结合的方式,确保流处理作业和批处理作业的不同资源要求.在计算节点上,提供CPU-GPU资源的灵活绑定,采用队列堆叠技术,不但满足流处理作业的实时性需求,也减少了反馈延迟并实现了GPU资源的共享.通过模拟大规模作业的调度,结果显示,HRM的调度延迟只有集中式调度框架的75%左右;使用实际负载测试,批处理与流处理共享集群时,使用HRM调度框架,CPU资源利用率提高25%以上;而使用细粒度作业调度方法,不但GPU利用率提高2倍以上,作业的完成时间也能够减少50%     

Hadoop平台下计算模型中调度策略的研究

针对Hadoop平台下默认调度算法FIFO、计算能力调度算法以及公平调度算法在调度过程中遵守严格的队列顺序,导致一些任务被调度到不满足数据本地性节点上的问题,提出一个基于本地性的调度算法——延时调度。该算法在维护公平性原则的同时,当一个被调度的作业无法启动一个本地的任务时,让这个任务等待一小段时间,调度其他作业先执行。实验结果表明,此调度算法缩短了作业平均响应时间,有效增加了集群系统的吞吐量,提高了集群资源利用率。     

基于负载感知的数据流动态负载均衡策略

针对大数据流式计算平台中存在节点间负载不均衡、节点性能评估不全面的问题,提出基于负载感知算法的动态负载均衡策略,并将算法应用于Flink数据流计算平台中。首先通过有向无环图的深度优先搜索算法获取节点的计算延迟时间作为评估节点性能的依据,并制定负载均衡策略;然后基于数据分块管理策略实现流式数据的节点间负载迁移技术,通过反馈实现全局和局部的负载调优;最后通过实验评估时空代价论证算法的可行性,并讨论重要参数对算法执行效果的影响。经实验验证算法通过优化流式计算任务的负载分配提高了任务的执行效率,与采用Flink平台现有的负载均衡策略相比,任务执行时间平均缩短6.51%。     

基于流计算的电力调度网络流量监测平台

由于电力调度网出现任何网络故障都可能发生极度严重的事故,因此具有的极高可靠性及安全性的要求.而当前传统的网络监测系统在面对大数据量时,其实时处理能力和扩展能力都无法满足需求.因此对实时产生的大规模各类型数据的分析处理则需要一种专门的实时数据分析平台完成.本文结合电力调度信息网络的特点以及监测准确性及实时性的需求,构建出一个基于流计算的数据处理分析平台,以Apache Spark中的Spark Streaming为代表的开源流计算框架,加入如Kafka分布式消息队列、Redis内存数据库等组件,为数据分析平台提供稳定高效的数据来源和数据服务接口,从而实现适用于电力调度网的各类海量数据的实时分析处理完成流量异常监测场景.     

面向Flink的负载均衡任务调度算法的研究与实现

Apache Flink是现在主流的大数据分布式计算引擎之一,其中任务调度问题是分布式计算系统中的关键问题。由于集群的异构性以及不同算子复杂度不同,大数据计算系统Flink中不可避免地会出现负载不均的情况,针对这种问题,提出了基于资源反馈的负载均衡任务调度算法RFTS。通过实时资源监控、区域划分和基于人工萤火虫优化的任务调度算法3个模块,把负载过重的机器中处于等待状态的任务分配给负载较轻的机器,来实现集群的负载均衡,提高系统集群利用率和执行效率。最后通过基于TPC-C和TPC-H数据集的实验结果表明,RFTS算法从执行时间和吞吐量2个方面有效提升了Apache Flink计算系统的性能。     

基于数据迁移策略的反压问题解决方法

流计算应用中由于上下游数据流入流出速率不匹配常常导致数据缓冲区容量不足或溢出的反压(backpressure)问题,轻则导致数据丢失、重则导致系统崩溃,亟需好的解决方法或方案.不同于向上游传递压力以解决下游反压的已有方法,本文提出了一种基于数据迁移策略的反压问题解决方法,通过其他分支的轻载节点分散处理来解决反压问题.我...     

Heron环境下基于实例重分配的传输负载优化策略

作为新一代大数据流式计算框架,Heron忽略了任务实例之间不同通信方式的差异以及节点资源利用率不均衡的问题导致系统性能下降。针对这一问题,设计了节点资源限制模型、通信开销优化模型和实例数据流关系模型,并在此基础上提出了Heron环境下基于实例重分配的传输负载优化策略(transmission load optimization strategy based on instance reallocation in Heron,TLIR-Heron)。该策略包括节点资源限制算法和实例重分配算法,通过判定实例重分配条件并执行重分配算法将节点间数据流转换为节点内数据流,从而降低通信开销。实验结果表明,在三组拓扑测试下,TLIR-Heron相较于Heron默认调度策略能够降低节点间通信开销和系统的计算延迟,并提升了计算节点资源利用的均衡性。     

基于Storm的车联网数据实时分析系统

针对传统车联网平台在处理海量数据时存在吞吐量小, 实时性差的问题, 设计了一种基于大数据流处理技术的实时分析系统. 系统分为数据采集、 数据转发、实时分析、数据存储和可视化展示5层. 为了满足系统高并发接入以及实时性的需求, 引入Storm实时计算系统进行数据的实时分析. 同时, 利用Kafka消息队列的异步通信机制将各层之间解耦, 采用Hbase进行海量数据存储, 从而提高车联网非机构化数据存储效率. 另外, 针对访问数据库开销大的问题, 采用Redis缓存策略, 进一步提高查询效率. 实验证明, 较传统的多线程处理平台, 该系统具有低延迟, 高吞吐, 可拓展等特点, 能够满足车联网大数据流处理要求.     

Optimizing checkpoint-based fault-tolerance in distributed stream processing systems: Theory to practice

Fault-tolerance is an essential part of a stream processing system that guarantees data analysis could continue even after failures. State-of-the-art distributed stream processing systems use checkpointing to support fault-tolerance for stateful computations where the state of the computations is periodically persisted. However, the frequency of performing checkpoints impacts the performance (utilization, latency, and throughput) of the system as the checkpointing process consumes resources and time that can be used for actual computations. In practice, systems are often configured to perform checkpoints based on crude values ignoring factors such as checkpoint and restart costs, leading to suboptimal performance. In our previous work, we proposed a theoretical optimal checkpoint interval that maximizes the system utilization for stream processing systems to minimize the impact of checkpointing on system performance. In this article, we investigate the practical benefits of our proposed theoretical optimal by conducting experiments in a real-world cloud setting using different streaming applications; we use Apache Flink, a well-known stream processing system for our experiments. The experiment results demonstrate that an optimal interval can achieve better utilization, confirming the practicality of the theoretical model when applied to real-world applications. We observed utilization improvements from 10% to 200% for a range of failure rates from 0.3 failures per hour to 0.075 failures per minute. Moreover, we explore how performance measures: latency and throughput are affected by the optimal interval. Our observations demonstrate that significant improvements can be achieved using the optimal interval for both latency and throughput.