請讀下面的這句繞口令：ResourceManager中的Resource Estimator框架介紹與演算法剖析
歡迎大家前往 ofollow,noindex" target="_blank">騰訊雲+社群 ，獲取更多騰訊海量技術實踐乾貨哦~
本文首先介紹了Hadoop中的ResourceManager中的estimator service的框架與執行流程，然後對其中用到的資源估算演算法進行了原理剖析。
一. Resource Estimator Service的出發點與目標
估計作業執行使用資源是大資料處理叢集的一個重要且具有挑戰性的問題。隨著使用者使用的叢集資源越來越多，這一需求被逐漸放大。當前現有的解決方案一般是依賴於使用者的經驗來對作業資源需求進行估計，這樣即繁瑣又低效。根據對叢集工作負載的分析，可以發現大部分工作(超過60%)是重複工作，這樣我們便有機會根據作業歷史資源使用情況來估計作業下一次的資源需求量。同時，在未來，希望能提出一種與框架無關的黑盒解決方案。這樣，即使作業來自不同的計算框架，我們也能對重複性作業進行資源需求估算。
二. Resource Estimator Service的框架結構
Hadoop-resource estimator主要由三個模組組成：Translator，SkylineStore和Estimator。下面分別介紹這三部分。
1.ResourceSkyline用來表徵作業在其生命週期中的資源利用率。它使用RLESparseResourceAllocation記錄容器分配的資訊。RecurrenceId用於標識重複pipeline的特定執行。pipeline可以包含多個作業，每個作業都有一個ResourceSkyline來表徵其資源利用率。
2.Translator用來解析作業日誌，提取他們的ResourceSkylines並將它們儲存到SkylineStore。SingleLineParser解析日誌流中的一行並提取ResourceSkyline。
3.SkylineStore充當Hadoop-resource estimator的儲存層，由2部分組成。HistorySkylineStore儲存由轉換程式提取的ResourceSkylines。它支援四種操作：addHistory，deleteHistory，updateHistory和getHistory。addHistory將新的ResourceSkylines附加到定期pipeline，而updateHistory刪除特定定期pipeline的所有ResourceSkyline，並重新插入新的ResourceSkylines。PredictionSkylineStore儲存由Estimator生成的預測RLESparseResourceAllocation。它支援兩個操作：addEstimation和getEstimation。
4.Estimator根據歷史記錄執行預測重複出現的pipeline資源需求，將預測儲存到SkylineStore並在YARN上進行資源預留。Solver讀取特定定期pipeline的所有歷史ResourceSkylines，並預測其包含在RLESparseResourceAllocation中的新資源需求。目前，Hadoop-resource estimator提供了一個LPSOLVER來進行預測（其中用到的演算法模型會在後面進行講解）。
三.以示例demo演示其執行流程
Resource Estimator Service的URI是 http://0.0.0.0，預設服務埠是9998
(在$ ResourceEstimatorServiceHome/conf/resourceestimator-config.xml” 中配置)。 在$ ResourceEstimatorServiceHome/data中，有一個示例日誌檔案resourceEstimatorService.txt，其中包含2次執行的tpch_q12查詢作業的日誌。進行資源預測主要有以下幾個步驟：
1.解析作業日誌：
POST http://URI:port/resourceestimator/translator/LOG_FILE_DIRECTORY
傳送
POST http://0.0.0.0:9998/resourceestimator/translator/data/resourceEstimatorService.txt
underlying estimator將從日誌檔案中提取ResourceSkylines並將它們儲存在jobHistory SkylineStore中。
2.查詢作業的歷史ResourceSkylines：
GET http://URI:port/resourceestimator/skylinestore/history/{pipelineId}/{runId}
傳送
GET http://0.0.0.0:9998/resourceestimator/skylinestore/history/*/*
underlying estimator將返回歷史SkylineStore中的所有記錄。在示例檔案中能夠看到兩次執行tpch_q12的ResourceSkylines：tpch_q12_0和tpch_q12_1。
3.預測作業的資源使用情況：
GET http://URI:port/resourceestimator/estimator/{pipelineId}
傳送
http://0.0.0.0:9998/resourceestimator/estimator/tpch_q12
estimator將根據其歷史ResourceSkylines預測新執行的作業資源需求，並將預測的資源需求儲存到jobEstimation SkylineStore。
4.查詢作業的預測資源情況：
GET http://URI:port/resourceestimator/skylinestore/estimate/{pipelineId}
傳送
http://0.0.0.0:9998/resourceestimator/skylinestore/estimation/tpch_q12
估算器將返回tpch_q12作業資源預測情況。
5.刪除作業的歷史資源情況資料：
DELETE http://URI:port/resourceestimator/skylinestore/history/{pipelineId}/{runId}
傳送
http://0.0.0.0:9998/resourceestimator/skylinestore/history/tpch_q12/tpch_q12_0
underlying estimator將刪除tpch_q12_0的ResourceSkyline記錄。重新發送
GET http://0.0.0.0:9998/resourceestimator/skylinestore/history/*/*
underlying estimator只返回tpch_q12_1的ResourceSkyline。
四.資源預測演算法中用到的資料介紹
Hadoop-resource estimator的Translator元件會解析日誌並將其按照一定規範的格式進行拼接，下面給出了示例中的資源歷史使用資料和預測資源資料，可以看到作業的歷史資源使用資料是同一個job的兩次run，分別為tpch_q12_0和tpch_q12_1,其主要給出了隨時間變化的memory和cpu的使用情況。其中第0時間單位表示的是container規格，為memory:1024,vcores:1，第25時間單位為作業結束時刻，memory和cpu皆為0。可以看到預測資料根據歷史資料給出了10~25時間單位的資源預測資料。
歷史資源使用資料:
[[{"pipelineId":"tpch\_q12","runId":"tpch\_q12\_0"},
[{"jobId":"tpch\_q12\_0","jobInputDataSize":0.0,"jobSubmissionTime":0,"jobFinishTime":25,"containerSpec":{"memory":1024,"vcores":1},
"skylineList":
{"resourceAllocation":{
"0":{"memory":1024,"vcores":1},
"10":{"memory":1099776,"vcores":1074},
"15":{"memory":2598912,"vcores":2538},
"20":{"memory":2527232,"vcores":2468},
"25":{"memory":0,"vcores":0}}}}]],
[{"pipelineId":"tpch\_q12","runId":"tpch\_q12\_1"},
[{"jobId":"tpch\_q12\_1","jobInputDataSize":0.0,"jobSubmissionTime":0,"jobFinishTime":25,"containerSpec":{"memory":1024,"vcores":1},
"skylineList":
{"resourceAllocation":{
"0":{"memory":1024,"vcores":1},
"10":{"memory":813056,"vcores":794},
"15":{"memory":2577408,"vcores":2517},
"20":{"memory":2543616,"vcores":2484},
"25":{"memory":0,"vcores":0}}}}]]]
預測資料:
{"resourceAllocation":
"10":{"memory":1083392,"vcores":1058},
"15":{"memory":2598912,"vcores":2538},
"20":{"memory":2543616,"vcores":2484},
"25":{"memory":0,"vcores":0}}}
五.Resource Estimator Service演算法框架與原理
在本部分將重點介紹一下estimator中用到的資源預測演算法原理。此演算法由微軟提出，其連結在文末參考資料中給出。下圖是estimator的執行框架，可以看到其主要由三部分組成，下面分別介紹這三部分。
image
- Automatic interence,提取出作業的執行時間和歷史資源使用情況。 (a) Extractor of target,能提取出作業的執行開始與結束時間。 (b) Job resource model,能提取出作業的資源使用情況,例如作業資源隨時間執行的變化情況和資源使用總量。
- Recurring Reservation,此部分包括有Job Resource Model，可以根據作業歷史執行時間與作業歷史資源使用情況給出下一任務的資源使用情況。 (a) 通過改變引數α，可以控制estimator在分配資源的時候是側重過分配還是側重欠分配。 (b) 根據作業資源預測模型給出的預測值為作業在原來分配的資源的基礎上新增資源新增agenda。此job下一個run就執行在此資源分配的基礎上。
- Dynamic Reprovisioning，此部分根據前面給出的資源agenda,動態調整作業的每個執行階段的資源分配。
六.演算法原理剖析
微軟提出的此資源分配演算法本質上是一種最優化演算法，其優化的目標函式是由兩部分組成的線性組合，下文中stage的概念是指每個job的執行期間按照一定規則劃分成多個時間片，每個時間片稱之為一個stage，下面分步驟闡述其演算法原理。
1.首先定義一個目標函式，也可以稱之為損失函式，即我們優化的目標。在此演算法中由過分配和欠分配組成的線性組合組成損失函式costfunction。目標就是minimize(cost=αA0(s)+(1−α)Au(s))。其中A0(s)表示在當前stage的資源過分配值，其是由當前stage的分配值減去此stage的歷史資源使用均值然後取平均得到，其公式表示為A0(s)=1N∑Ni=1∑k(sk−si,k)+,sk即為當前的資源分配值，si,k即為第i次run的歷史資源使用值;Au(s)表示當前stage的欠分配值，其是由上一stage的欠分配值加上當前stage的欠分配值得到，公式表示如下：Di,k(s1,...,sk)=(Di,k+si,k−sk)+,Au(s)=1N∑Ni=1Di,k(s),下圖比較直觀的顯示了estimator在預測資源時的一種過分配與欠分配的情況。
2.針對每個stage,此演算法的策略就是選擇可以使得costfunction最小的資源分配方式，即選擇一個值使得costfunction最小，即得到Sk,即每一個stage上的資源分配值。 因為分配值是固定規格的倍數，所以在實現時可以通過簡單的for迴圈或者一些最優化演算法比如爬山法或者蟻群演算法就可以快速得到最小值。
3.總結：演算法中的做法是針對一個job，根據其歷史執行時間拿到其作業開始和結束時間，在這時間段內按照一定規則劃分時間片，每一個時間片為一個stage，根據同一job多次run的歷史資源使用情況來預測下一run的資源使用情況。其每次配置的策略是使得costfunction最小。costfunction是過分配與欠分配的一個線性組合。
七.演算法的測試效果
在本次測試中執行tpch_q12作業9次，並在每次執行中收集作業的資源skylines。然後，在Resource Estimator Service中執行日誌解析器，從日誌中提取ResourceSkylines並將它們儲存在SkylineStore中。下面繪製了作業的ResourceSkylines以進行演示。
在Resource Estimator Service中執行估算器來預測新執行的資源需求,下面繪製了預測的資源需求資料。可以看到預測資料根據歷史資源使用情況較好地表徵了下一次執行的資源使用資料，有一定的參考意義。另外在實際場景業務上的測試效果還有待考證。
八.參考
1. Resourcemanager Estimator Service
2. 微軟演算法文章