Guaranteeing the response deadline for general aggregation trees  

作　　者：Jiangfan LI Chendie YAO Junxu XIA Deke GUO 

机构地区：[1]Science and Technology on Information Systems Engineering Laboratory,National University of Defense Technology,Changsha 410073,China

出　　处：《Frontiers of Computer Science》2020年第6期97-110,共14页中国计算机科学前沿（英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant No.61772544);National Basic Research Program(973 program)(2014CB347800);the Hunan Provincial Natural Science Fund for Distinguished Young Scholars(2016JJ1002);the Guangxi Cooperative Innovation Center of Cloud Computing and Big Data(YD16507 and YD17X11).

摘　　要：It is essential to provide responses to queries within time deadlines,even if not exact and complete.To reduce the query latency,systems usually partition large-scale data computations as a series of tasks over many processes and aggregate them to reduce the response time by using aggregation trees.An obstacle is that the involved processes of a query usually differ in their speeds,thus not all processes can complete their tasks in time.This would directly degrade the response quality(the number of outputs received by the root of an aggregation tree).In this paper,we propose a general aggregation tree model,Tarot,to maximize the response quality by systematically addressing the following challenging issues:(1)fine-grained partition of the query deadline along the multi-level aggregation tree;(2)learning the distribution of durations at each level in the aggregation tree to optimize the wait durations at aggregators;(3)adaptively reassigning tasks over processes according to their status;(4)performing periodic aggregation of received outputs from the low level to avoid missing the deadline.The prior model does not consider the four aspects simultaneously.Extensive evaluations indicate that Tarot can adapt to multi-level trees and considerably improve the response quality compared to prior work while guaranteeing the query deadline.

关 键 词：aggregation query performance variations tasks reassignment 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]