OptEx: A Deadline-Aware Cost Optimization Model for Spark

最近在研究一些Spark成本優(yōu)化的東西颅崩，看了一些論文稍微總結(jié)一下思路添瓷，方便思維拓寬和希望與大家交流供屉！

本篇博文參考自：

2016 16th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing：
《OptEx: A Deadline-Aware Cost Optimization Model for Spark》

1 文章概述及問題描述

現(xiàn)如今髓帽，基本上所有的云計算服務(wù)提供商在向用戶提供計算服務(wù)時都是以虛擬機實例來提供潜圃，并且不同種類的虛擬機有不同的硬件配置（cpu荣病、I/O等），這些都是按小時來計費闸餐，并且可向用戶提供微型饱亮、小型、大型等不同規(guī)模的集群舍沙。但是目前并沒有一種方案能夠在滿足用戶時間及金錢成本等需求（SLO）的基礎(chǔ)上很準確地向用戶推薦一種規(guī)慕希或是配置的計算實例的方法或參考，并且也沒有一項成本優(yōu)化的策略來降低用戶的使用成本拂铡，因此壹无，這樣的一個問題現(xiàn)狀促使了本文對這兩個問題的探討和研究。
文中所介紹的OptEx模型感帅，是一個用于預(yù)測spark作業(yè)運行時間（平均估計錯誤率6%）斗锭，并且能夠以優(yōu)化成本為目的地去預(yù)估一個合適的集群組合來推薦給用戶，這樣的組合既可以為用戶減少使用成本留瞳，并且能夠保證用戶對作業(yè)運行時的SLO需求（預(yù)測準確率98%）

2 論文中的相關(guān)術(shù)語以及spark基礎(chǔ)

1. SLO
   全稱：Service Level Objective
   維基百科：

A service level objective (SLO) is a key element of a service level agreement (SLA) between a service provider and a customer. SLOs are agreed upon as a means of measuring the performance of the Service Provider and are outlined as a way of avoiding disputes between the two parties based on misunderstanding.
SLO與SLA易混淆拒迅，那么SLA是什么？它與SLO的關(guān)系如何她倘？：
The SLA is the entire agreement that specifies what service is to be provided, how it is supported, times, locations, costs, performance, and responsibilities of the parties involved. SLOs are specific measurable characteristics of the SLA such as availability, throughput, frequency, response time, or quality. These SLOs together are meant to define the expected service between the provider and the customer and vary depending on the service's urgency, resources, and budget. SLOs provide a quantitative means to define the level of service a customer can expect from a provider.

2. job completion time
   表示spark作業(yè)的完成時間

3. profile
   文中一直提到profile或是profiling璧微，這個是通過基準測試來獲取一些模型需要的參數(shù)后，將這些參數(shù)保存在profile中的硬梁，而這些基準測試的參數(shù)值最終會被拿來作為真實作業(yè)參數(shù)的估計前硫。

3 方法概述

OptEx模型旨在解決兩個問題：spark job的完成時間的估計；以降低成本為目標的最佳集群組合方式的估計荧止。
基本做法：
1）OptEx將spark作業(yè)分解成為更小的階段（包括the initialization phase, the preparation phase, the variable sharing phase, and the computation phase）屹电。模型將執(zhí)行時間表示為與集群大小阶剑、迭代次數(shù)、輸入大小以及模型參數(shù)配置文件的關(guān)系危号。

階段解釋：
initialization phase：執(zhí)行類加載牧愁，symbol table創(chuàng)建，對象初始化外莲，函數(shù)加載和記錄器logger初始化等活動
preparation phase：作業(yè)調(diào)度猪半，資源分配和context創(chuàng)建
variable sharing phase：處理從master向workers進行的broadcast或accumulating blocks of data。

2）OptEx將spark程序進行分類偷线，跑一些具有代表性的作業(yè)來為每種類別的作業(yè)分配一個單獨的作業(yè)配置文件磨确。而模型的參數(shù)設(shè)置是來自于作業(yè)的配置文件。
3）模型中有一個資源使用成本的目標函數(shù)声邦，在滿足SLO條件下乏奥，要盡可能地通過組合集群去使目標函數(shù)最小，從而達到一個成本優(yōu)化亥曹。

那么效果如何呢邓了？
文中驗證部分使用了spark PageRank的應(yīng)用來進行測試。亞馬遜提供30節(jié)點歇式，Xlarge集群驶悟，用戶的SLO是70小時，正常跑完后共消耗40小時和168.45美元材失，在使用了本文模型后痕鳍，共消耗60小時，84龙巨。18美元笼呆，可見在滿足SLO條件下，成本優(yōu)化很顯著旨别。

4 主要貢獻

提出OptEx模型用于對spark運行過程進行建模诗赌。
提出一種用于估計集群組合方式來降低成本的策略。

5 OptEx方法介紹

1秸弛、OptEx將spark分為上述幾個不同的階段后铭若，將其每個階段的時間具體化為與集群大小、迭代次數(shù)递览、輸入數(shù)據(jù)大小以及模型參數(shù)之間的關(guān)系定拟。OptEx參考了ARIA框架的實現(xiàn)原理丝格，該框架是適用于hadoop的調(diào)度朴下，OptEx使用與目標作業(yè)所屬類別相對應(yīng)的特定作業(yè)配置來估計模型參數(shù)囱嫩。
Spark內(nèi)部使用RDD來基于內(nèi)存進行迭代，spark內(nèi)部基于RDD封裝了一些庫供不同需求的計算任務(wù)所使用儿捧，例如MLlib荚坞、SQL等挑宠。對于一個app的計算階段，將會調(diào)用相應(yīng)的庫來進行計算颓影，而計算階段包含worker間的通信以及變量共享各淀，和RDD的執(zhí)行計算部分。變量共享階段與執(zhí)行計算階段的長度與輸入的變量（集群大小诡挂、數(shù)據(jù)量等）成相關(guān)關(guān)系揪阿，尤其是變量共享和計算階段會隨著迭代而不斷重復(fù)
2、對于集群組合的優(yōu)化是通過最小化約束條件的目標函數(shù)來實現(xiàn)的咆畏，而這個成本目標函數(shù)是基于作業(yè)執(zhí)行模型來構(gòu)建的。

6 用于模型參數(shù)估計的profiling

關(guān)于這個profiling吴裤，我不知道如何簡潔的解釋旧找，之前看到一篇hadoop性能預(yù)測的論文Starfish中這個詞用的很多，大致意思就是先跑了很多基準測試麦牺，然后記錄并尋找到這些基準測試的時間變化統(tǒng)計規(guī)律或是資源消耗規(guī)律等钮蛛，用于反推到真實作業(yè)下的時間消耗等。
Starfish：《Starfish: A Selftuning System for Big Data Analytics》《Profiling, Whatif Analysis, and Costbased Optimization of MapReduce Programs》《MapReduce Programming and Costbased Optimization Crossing this Chasm with Starfish》
常見的估計給定job性能表現(xiàn)的手段是使用一個標準的配置工具剖膳，基于一些基準測試魏颓，這個工具能夠測量真實的性能表現(xiàn)（例如每個階段的時間或是資源消耗等）的統(tǒng)計數(shù)據(jù)，并生利用代表性的基準job來為目標job生成一個profile吱晒。OptEx先將作業(yè)類型進行分類甸饱，然后對于每一類的作業(yè)進行一些基準測試并產(chǎn)生相應(yīng)的profiles。

6.1 應(yīng)用分類

根據(jù)spark自帶的幾種業(yè)務(wù)邏輯仑濒，本文對spark app進行分類：
1）Spark SQL
2）Spark Streaming
3）MLlib
4）GraphX

6.2 為每一個類選擇具有代表性的job

怎樣為每一類job分配具有代表性的job呢叹话？文中定義滿足以下條件即可：
（我理解的具有代表性的job就是相應(yīng)的基準測試的app。假設(shè)基準測試app用a表示墩瞳，對應(yīng)的真實作業(yè)用j表示）那么如果：
1）a的RDD包含全部j的RDD
2）j和a都是迭代的或者都不是迭代的
3）使用同一種spark lib提供的業(yè)務(wù)計算框架
根據(jù)以上條件驼壶，文中所選取的相應(yīng)的基準測試案例為：
1）Spark Streaming：the web page of Spark Streaming library，數(shù)據(jù)集為Twitter dataset
2）MLlib：the movie rating application MovieLensALS
3）GraphX：PageRank
4）Spark SQL：AMPLab研發(fā)的Big Data Benchmark

6.3 用profile來估計模型的參數(shù)

模型需要一些通過基準測試獲得的參數(shù)喉酌，這些參數(shù)都保存在profiles里面热凹，這些參數(shù)的含義如下所示：

初始化階段的時間長度額準備階段的時間長度隨著輸入變量的額變化而保持不變。執(zhí)行階段的時間和變量共享階段的時間與輸入變量呈正相關(guān)關(guān)系泪电。有這樣的關(guān)系后般妙，基準測試的profile中的參數(shù)值可以被用來作為參考基準，用來估計真實作業(yè)中相關(guān)階段的時間長度歪架。
根據(jù)以上參數(shù)展示以及前面討論的階段劃分股冗，job的完成時間可表示為如下模型：

profile獲取的方式：
profiling時，基準測試的用例在單節(jié)點上進行部署和測試和蚪，同時止状，前面提到的四個階段的時間長度均會被記錄在profile中烹棉。對于初始化和準備階段，可以對找到作業(yè)類型從profile文件中直接獲取這兩個階段的時間怯疤。
而變量共享階段的時間是與集群規(guī)模和迭代次數(shù)呈正相關(guān)的浆洗，因此，這個階段的時間可以表示為：其中n表示節(jié)點個數(shù)集峦，iter表示迭代次數(shù)伏社，coeff表示系數(shù)，這個系數(shù)是通過不斷地基準測試曲線擬合得到的塔淤。

計算階段的時間是由通信階段時間+執(zhí)行階段時間組合而來摘昌，通信階段的時間可用如下表示：

執(zhí)行階段是要根據(jù)不同類型RDD來進行估計，本文使用包含代表性Spark應(yīng)用程序a的每個單元RDD任務(wù)組件k的平均運行時間來表示高蜂。

7 spark job執(zhí)行模型的推導(dǎo)

7.1 模型輸入

模型的輸入看侠瑁可以由用戶很固定地根據(jù)job配置而給出：輸入數(shù)據(jù)量、節(jié)點個數(shù)备恤、app類型稿饰。而迭代次數(shù)可以從簡短的代碼中得到。
當(dāng)對目標job進行建模時露泊，用戶給模型輸入一個iter的上限喉镰，當(dāng)運行目標job時，用戶會給一個iterexec作為迭代次數(shù)的參數(shù)去運行惭笑，而這個兩個iter可能會不相同Ｂ履贰！不相同的話會導(dǎo)致：1）不可預(yù)測的資源消耗脖咐；2）無法滿足SLO铺敌。如果發(fā)生這種情況，要重新使用新的參數(shù)進行估計屁擅。

7.2 模型的公式化

前面表示出了整體job的模型偿凭，其中關(guān)于執(zhí)行階段，我們討論過派歌，是由每一個RDD來決定的弯囊，而RDDtask的數(shù)量n是與數(shù)據(jù)量、迭代次數(shù)呈正相關(guān)的胶果，因此RDD task的數(shù)量n能夠表示為：

前面討論過初始化階段和準備階段的時間不隨其他因素而變化匾嘱，因此可以直接用profile中的時間來估計。
變量共享階段和計算階段也可由前面提到的兩個公式來計算早抠。但是由前面的分析知道霎烙，計算階段可以進一步分解為通信階段和執(zhí)行階段，而執(zhí)行階段依賴于1）給定job的RDD集合的運行次數(shù)；2）迭代次數(shù)iter悬垃；3）job的stage個數(shù)游昼；4）job的并行度；5）節(jié)點間RDD變量的共享尝蠕，因此執(zhí)行時間可以表示為一個和的形式：包含j的所有RDD task計算時間之和烘豌，如下公式所示：

根據(jù)前面的公式推導(dǎo)，上式可以具體化為：

到這里我們可以結(jié)合前面的推導(dǎo)得出目標job的執(zhí)行時間模型：

其中B等于：

8 基于成本優(yōu)化的集群組合估計

最佳的集群大小的組合用下式表示：其中nt是t類型虛擬機實例的個數(shù)靖榕，m是所有的虛擬機實例的總個數(shù)标锄。

總成本用C表示，用ct表示t類型的單個虛擬機實例的單位小時成本茁计。
基于上述定于鸯绿，我們可以得到如下成本目標函數(shù)：

關(guān)于約束條件，很顯然就是用戶的SLO簸淀，即job時間<SLO，而job的估計時間可用7節(jié)中的模型進行預(yù)測毒返。

9 實驗環(huán)境

1租幕、實驗環(huán)境以及數(shù)據(jù)集是需要每次積累和對比的。
2拧簸、本文實驗環(huán)境是Spark-1.2.1劲绪，部署在6臺EC2-8core-15GBRAM-10GBEBS。backend：HDFS
3盆赤、供使用了三種算法：MovieLensALS贾富，PageRank，Wordcount
數(shù)據(jù)集：
MovieLensALS：10-M MovieLens
PageRank：社交網(wǎng)絡(luò)數(shù)據(jù)LiveJournal
Wordcount：Wikipedia

我的博客 : https://NingSM.github.io

轉(zhuǎn)載請注明原址牺六，謝謝颤枪。