长尾延迟优化的在线数据密集型计算运行环境支撑技术研究

With the development of the web search, online social networks and E-commerce, Online Data Intensive (OLDI) applications have become hot topics in both industry and academic fields. OLDI’s large scale, bounded latency and service correlation pose stringent requirements for the interactive latency performance for the online computing. However, the “long-tail” problem of the OLDI significantly hurt clients’ experiences. This project will perform research on the measurement, analysis and optimization of the long-tail latency for supporting the low-latency runtime environment of the OLDI applications. 1. According to the latency-measurement requirement of the directed acycline graph (DAG) structured OLDI applications, this project will study multi-dimensional decomposition techniques and realize the light-weight high-precision long-tail latency collection via the computing structure decomposition and the matrix factorization. 2. According to the online query and data mining requirements of the tail characteristics of the OLDI applications, this project will study sketching techniques and spatial-temporal analysis for the long-tail latency, realize the constant-time latency-distribution queries for DAG structured OLDI applications, and detect intensive-communication regions that result in severe long-tail latencies. 3. According to the millisecond-scale online computing requirement, this project will design holistic wide-area detour routing and data-center network multi-replica scheduling optimization techniques, and realize the tail-optimized OLDI runtime environment.

随着网络搜索、在线社会网络、电子商务的发展，在线数据密集型（OLDI）应用已经成为工业界和学术界广泛关注的热点。OLDI具有的规模巨大、延迟受限、服务关联性等特性，对在线计算的交互延迟性能提出迫切需求，然而OLDI的“长尾延迟”问题导致用户体验严重下降。本项目将针对支撑OLDI应用低延迟运行环境的长尾延迟测量、建模与优化等方面开展研究。1.面向具有有向无环图计算结构的OLDI应用延迟测量需求，研究基于多维分解的测量技术，通过计算结构分解与矩阵分解，实现低开销的高精度长尾延迟收集。2.针对OLDI延迟尾部特征在线查询与挖掘需求，研究长尾延迟的概要表示结构与时空分析技术，实现常数时间的有向无环图结构延迟分布查询，发现造成严重长尾效应的密集通信区域。3.面向毫秒级在线计算需求，设计一体化的广域网绕道路由与数据中心网络多副本调度优化机制，实现长尾优化的OLDI网络运行环境。

互联网、移动计算、物联网的技术突破产生了大规模的人-机-物生态环境，涌现出亿级用户规模的网络搜索、在线社会网络、电子商务、视频监控、智能助理在线数据密集型应用．然而，在线数据密集型应用（OLDI）在对大规模数据集进行在线实时计算时遇到了严重的“长尾”延迟问题：即存在一定比例的处理响应时间远大于所有处理时间的平均值，严重影响了任务关键型应用的实时控制能力，以及在线用户体验质量。.根据著名的Amdahl定律可知，任何一个位置的延迟上升必然增大端到端延迟，因此，需要对请求-响应全过程进行测量和优化。首先，我们提出了自修复的数据中心网络高精度单向延迟测量方法，提出了自稳定的广域网分布式网络延迟预测方法，设计并实现了高精度的网络延迟测量系统。其次，针对长尾延迟的概要表示需求，我们提出了假阳性和带宽优化的树型Bloom过滤器，设计了基于遗传算法的多目标参数优化算法，实现了高效精确的树型查询机制。在测量机制的支撑下，我们构建了面向网络空间的低度量理论框架，设计了基于分布式网络延迟聚类的覆盖网结构，提出了面向广域网的分布式邻近搜索和绕道路由方法，以及面向数据中心网络的基于相似副本的BitTorrent相似文件共享方法和面向多节点失效的纠删码方法。.本项目录用与发表高水平学术论文9篇，其中发表计算机学会A 类顶级期刊IEEE/ACM Transactions on Networking（ToN）论文3 篇，ACM 学会下属的计算机性能评测旗舰期刊ACM TOMPECS 1篇和计算机性能评测旗舰会议ACM SIGMETRICS 1 篇。形成专利1项。其中，SCI检索4篇（含网络出版待检索1篇），EI检索5篇。