Page 225 - 《软件学报》2021年第10期

危剑豪 等:多查询共享技术研究综述 3197

量数据的工作流中存在的冗余处理问题.与文献[33]不同,他们设计了一个启发式策略在制定计划决策时支持
join 和 no-join 工作流.该算法支持在多个 MR 任务中共享公共部分的数据.该调度算法是一种贪心算法,根据作
业的软截止时间对作业进行排序,并在每次迭代中合并尽可能多的排序顺序以扫描具有相同输入的作业,得出
可行的作业时间表.实验结果表明,应用扫描共享可以使调度程序显著提高资源使用率.当许多作业争用少量文
件时,导致资源使用减少 3 倍.但 CoScan 目前的成本估算器存在一些问题,比如无法根据先前的性能预估新作业
的执行情况.
2012 年,Wolf 等人 [36] 提出了一种通用的 MR 共享作业方法,称为 circumflex.该方案分为两个阶段.
 在第 1 阶段,cyclic piggybacking 提供了一种自然而有效的技术来摊销共享扫描的成本.作业被分解为
多个子作业,这些子作业与自然优先级约束相关.与文献[23]类似,cyclic piggybacking 在系统中维护着
一直在线的扫描运算符,到达的作业在对文件进行扫描时,起始块为上一个作业正在扫描的块,然后依
次扫描到该块的前一块为止;
 在第 2 阶段,针对各种度量标准,解决了由此产生的优先级调度问题.Wolf 等人给出了最近调度算法研
究的概况,用于在此 cyclic piggybacking 范式的背景下优化调度.该调度可根据各种成本指标进行定制,
该类成本指标包括平均响应时间、平均拉伸和任何 minimax-type 指标等总共 11 个单独的标准指标.
该方案的性能较 MRShare 和 Coscan 略有不及,然而策略中各个作业立即执行,无需等待,因此对单个作业
的影响确也是 3 种策略中最小的.
2013 年,Guoping 等人 [35] 提出了两种用于 Map-Reduce 框架中的多作业共享优化技术.
 其一是通用的分组技术,该技术将多个作业合并到单个作业中,从而使合并的作业能够共享输入文件
的扫描以及公共 Map 阶段的输出;
 其二是提出了一种基于成本的两阶段优化算法来优化批量 MR 的执行计划:在第 1 阶段,Guoping 等人
为每个作业选择 Map 输出键,以最大化这批作业之间的共享机会;在第 2 阶段,他们将一批工作划分为
几组,并为每组选择处理技术,以最大程度地降低总评估成本.
值得一提的是,他们提到的 MR 工作共享策略与 MRShare 十分类似,相比之下,二者都提出了计算批量共享
2
任务的代价模型,且在代价模型上设计了启发式的查询计划算法,并且二者的时间复杂度均为 O(n ).不同之处
在于:Guoping 等人的策略在广义分组技术方面更加全面,共享的时机也更多,但也会导致更复杂的优化问题(例
如每个作业的 Map 输出键的顺序变得很重要); 根据 Guoping 等人在 Hadoop 上的实验结果表明,他们提出的方
法比 MRShare 的吞吐量提高了 107%.
2015 年,Lei 等人设计了一个为 Map-Reduce 基础架构中的重复工作量身定制的可扩展多查询共享引擎 [37] ,
称为 Helix.其主要研究内容如下:介绍了切片窗口对齐策略,用于对数据进行预处理并将其划分为较小的段.该
策略分析并且确定由查询执行的关注范围之间的差异,使用一种逻辑窗口切片方法,将重复出现的查询窗口划
分为对齐的切片,对切片的查询处理将产生部分结果,这些结果可用于以很少的开销来满足多个查询.然后,Lei
等人又开发了一个 SLA 驱动的优化器,该优化器将查询的属性(例如窗口语义和 SLA 约束)合并到交错的共享
和调度算法中,从而为给定的一组重复查询生成执行计划.优化程序利用分支和边界搜索策略以及各种修剪策
略,可以从指数搜索空间中尽早地有效修剪次优解决方案,从而在实践中使搜索变得容易.相比于 MRShare,
Helix 能够支持的共享机会更多,并且支持在重复查询中指定窗口约束和 SLA 要求.而与 CoScan 相比,Helix 适
用于正在不断变化的数据集,并且对特定的运算符进行了优化.
5.2.4 半结构化数据中的多查询共享
2003 年,Bruno 等人把共享查询技术的研究场景搬到了 XML 数据库系统中 [68] ,他们提出了两种多查询共享
技术:一种是基于索引的多查询共享技术,名为索引过滤器 index-filter,可以针对 XML 文件评估多个 XML 路径
查询,索引过滤器采用了 PathStack 算法 [69] ,并利用 XML 路径查询集的前缀树表示形式在多个查询评估期间共
享计算;另一种是基于导航的多查询共享技术,名为 Y 过滤(Y-filter).主要思想是将输入查询的前缀树表示形式
扩展为如下的不确定性有限自动机(NFA):(i) NFA 标识由所有输入路径查询的并集定义的确切“语言”;(ii) 当