倾斜任务调度模型及其在医疗大数据处理中的应用研究

Skew tasks are defined as the tasks with uncertain executing time due to the inner skew keys and unreliability of distributed environment. Massive skew tasks will be generated from the processing for the unstructured data such as medical history and medical advice et al. in medical information processing system. Through analyzing the actual characteristics of data-intensive and computing-intensive tasks, this project proposes a sampling based prediction algorithm for the distribution of the inner-keys comprehensive considering system performance and sample accuracy. On this basis, we firstly propose a reduce task placement algorithm to improve the task locality, a splitting/combining model of inner data fragment for tasks load balancing, and a read-write optimizing strategy for shuffle processing based on write-less technical. And then, this project proposes an evaluation model for tasks remaining time comprehensive considering the extent of data skew and current system loading, implements a heuristic speculate execution mechanism for skew tasks, which is more accurate than current researches. Based on these works, we can establish a real-time scheduling and resources allocation model for skew-aware tasks through the DAG automatic generation method, it is can solve the problem of the low system performance when executing the skew tasks. Finally, the proposed theories and prototype will be tested for performance evaluation on the supercomputer in National Supercomputing Center in Changsha, and the established prototype system will be integrated into a real medical big data processing system. The research outputs can be used to solve the application problems in tasks locality, load balancing and faulty tolerant for skew tasks. It has important theoretical and practical value.

倾斜任务是指MapRedcue框架中由于数据内部倾斜和系统不可靠性所引起的执行时间不确定的任务，医疗信息系统中对病历、医嘱等文本型非结构化数据的处理会产生大量倾斜任务。本项目拟首先通过分析医疗数据的实际特征，提出一种考虑系统性能与样本准确率的内部数据键值对分布抽样算法；同时提出一种旨在提高任务本地性，实现负载均衡的Reduce任务放置及中间数据切割与组合模型，并针对Shuffle过程提出基于写减少技术的数据读写优化策略。其次提出综合考虑数据倾斜程度与系统负载率的任务剩余时间评估模型，实现比现有研究更为准确的启发式倾斜任务推测执行机制，并由此提出DAG自动生成、实时调度与资源分配模型，解决因倾斜任务导致医疗信息系统性能低下的难题。最后对项目原型与现有医疗大数据分析系统进行集成与验证。研究成果还将有助于解决数据中心在倾斜任务的本地化、负载均衡以及容错方面的应用难题，具有较重要的理论与实际价值。

并行分布式计算框架MapReduce非常适合面向医疗大数据的离线分析和知识挖掘，并且在医疗行业已经得到了广泛的应用。本项目针对医疗大数据处理过程中源输入数据分布不均匀的情况，提出基于倾斜任务调度模型。主要研究内容按照课题计划书严格推进，现已经完成计划的内容，包括以下5个方面：.（1）本课题完成在医疗文本数据偏斜情况下使用抽样的方法对中间数据key值分布的预估模型，包括提出使用蓄水池算法和基于步长的拒绝算法，并发表论文一篇。.（2）优化了倾斜数据shuffle过程中任务负载不均衡和多对多任务通信时的跨节点/机架的网络流量过载问题，并发表了论文三篇。.（3）完成了基于树核和词向量结合的医疗文本相似度计算模型，为使用机器学习方法挖掘医疗大数据有价值信息提供技术基础，并发表论文三篇。.（4）提出基于负载感知和针对异构计算环境下的推测执行策略，解决了数据偏斜情况下容易产生缓慢任务从而导致拖延整体作业执行的情况，并发表论文四篇。.（5）提出面向医疗大数据信息挖掘的并行算法优化，基于Hadoop/Spark平台对数据挖掘领域一些常见的机器学习算法进行并行优化，并发表论文三篇。