混部數(shù)據(jù)中心負(fù)載特征及其任務(wù)調(diào)度優(yōu)化分析*

王濟(jì)偉，葛浙奉，蔣從鋒，張紀(jì)林，俞 俊，林江彬，閆龍川，任祖杰，萬(wàn) 健

(1.杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江 杭州 310018；2.阿里云計(jì)算有限公司，浙江 杭州 311121； 3.國(guó)網(wǎng)電力信息通信有限公司，北京 100053；4.之江實(shí)驗(yàn)室，浙江 杭州 311121； 5.浙江科技學(xué)院信息與電子工程學(xué)院，浙江 杭州 310023)

1 引言

隨著各類(lèi)互聯(lián)網(wǎng)應(yīng)用的快速增長(zhǎng)，企業(yè)及個(gè)人用戶(hù)對(duì)云計(jì)算服務(wù)的需求與日俱增。互聯(lián)網(wǎng)數(shù)據(jù)中心IDCs(Internet Data Centers)作為承載云計(jì)算服務(wù)的基礎(chǔ)設(shè)施，發(fā)揮了越來(lái)越重要的作用。數(shù)據(jù)中心提供的服務(wù)可簡(jiǎn)單分為在線(如瀏覽型請(qǐng)求、交易型業(yè)務(wù)和支付型業(yè)務(wù)等)和離線(如科學(xué)計(jì)算、統(tǒng)計(jì)報(bào)告和數(shù)據(jù)處理等)2類(lèi)。在線類(lèi)服務(wù)要求較低的延遲，而離線批處理類(lèi)任務(wù)要求具有較高的吞吐量。另外，由于任務(wù)時(shí)延過(guò)長(zhǎng)或任務(wù)失敗重試會(huì)影響用戶(hù)體驗(yàn)，因此在線類(lèi)服務(wù)往往不可降級(jí)。而批處理任務(wù)相對(duì)于在線任務(wù)，對(duì)時(shí)延不敏感，可以接受任務(wù)失敗重試。

用戶(hù)任務(wù)負(fù)載的動(dòng)態(tài)性和多樣性，使得數(shù)據(jù)中心內(nèi)服務(wù)器資源的使用也會(huì)動(dòng)態(tài)變化，既具有一定的周期性，又具有一定的波動(dòng)性。為提高數(shù)據(jù)中心資源利用率，降低數(shù)據(jù)中心運(yùn)行成本，云計(jì)算服務(wù)提供商逐步將在線服務(wù)和離線批處理任務(wù)在數(shù)據(jù)中心進(jìn)行混合部署(以下簡(jiǎn)稱(chēng)混部)[1,2]。因此，在混部場(chǎng)景下，如何同時(shí)滿(mǎn)足在線服務(wù)和離線批處理任務(wù)的不同要求，在提高資源利用率的同時(shí)，盡量降低2類(lèi)任務(wù)之間的干擾，是目前互聯(lián)網(wǎng)數(shù)據(jù)中心任務(wù)調(diào)度面臨的關(guān)鍵挑戰(zhàn)。

目前，大型互聯(lián)網(wǎng)公司，如谷歌[3]、臉書(shū)[4]、微軟[5]和阿里巴巴[6,7]等，都采取了在線服務(wù)與離線任務(wù)混部的方式以提高數(shù)據(jù)中心的資源利用率。但是，由于在線服務(wù)和離線任務(wù)的資源需求和資源使用特性的差異，數(shù)據(jù)中心集群調(diào)度器將服務(wù)器資源在不同業(yè)務(wù)間復(fù)用和共享的同時(shí)，需要在資源競(jìng)爭(zhēng)時(shí)優(yōu)先保證高優(yōu)先級(jí)業(yè)務(wù)的資源需求。以阿里巴巴的集群管理系統(tǒng)為例，阿里巴巴的多個(gè)數(shù)據(jù)中心于2015年逐步開(kāi)始混部，通過(guò)逐年提高集群中機(jī)器的混部比例，以確保其在實(shí)際生產(chǎn)環(huán)境中的可靠性。

阿里巴巴混部集群調(diào)度管理系統(tǒng)主要由Sigma和Fuxi 2種調(diào)度器組成[8]。其中Sigma調(diào)度器負(fù)責(zé)Pouch容器[9](在線服務(wù))的調(diào)度，F(xiàn)uxi負(fù)責(zé)離線批處理作業(yè)的調(diào)度。由于同一集群上同時(shí)存在Sigma和Fuxi，機(jī)器上的CPU、內(nèi)存、磁盤(pán)、網(wǎng)絡(luò)帶寬等資源會(huì)被這2種調(diào)度器爭(zhēng)搶。為了避免機(jī)器上的資源被一方過(guò)度占用導(dǎo)致另一方無(wú)法正常工作，或者資源被閑置，無(wú)法得到充分利用，集群管理系統(tǒng)中設(shè)置了Level0模塊來(lái)協(xié)調(diào)資源的分配。目前阿里巴巴采用混部的服務(wù)器已經(jīng)達(dá)到數(shù)萬(wàn)臺(tái)以上，將原來(lái)的單一在線原生集群的日均資源利用率從10%提高到了40%，并在“雙十一”等特殊促銷(xiāo)時(shí)期，將離線批處理任務(wù)進(jìn)行業(yè)務(wù)降級(jí)處理，以滿(mǎn)足激增的在線任務(wù)的資源需求。通過(guò)混部，在確保數(shù)據(jù)中心服務(wù)質(zhì)量的同時(shí)，節(jié)省了30%以上的成本[6]。如果能夠?qū)?shù)據(jù)中心負(fù)載特征進(jìn)行更深入的分析，如負(fù)載的時(shí)間、空間特征及資源使用維度，則可以進(jìn)一步挖掘集群的混部潛力，進(jìn)而提高混部集群的資源利用率，降低數(shù)據(jù)中心運(yùn)行成本。

本文根據(jù)阿里巴巴2018年12月公開(kāi)的具有4 034個(gè)結(jié)點(diǎn)的混部集群的任務(wù)調(diào)度日志數(shù)據(jù)(cluster-trace-v2018)[8]，系統(tǒng)分析了典型混部數(shù)據(jù)中心的負(fù)載特征，并提出了相應(yīng)的任務(wù)調(diào)度優(yōu)化策略。本文工作如下所示：

(1)對(duì)離線批處理作業(yè)與在線應(yīng)用的資源使用進(jìn)行了分析，發(fā)現(xiàn)單個(gè)在線應(yīng)用所包含的容器數(shù)量符合Zipf分布，表明混部集群中在線應(yīng)用的規(guī)模都具有明顯的傾斜現(xiàn)象(Task Skew)。該發(fā)現(xiàn)有助于集群調(diào)度相關(guān)領(lǐng)域?qū)W者與研究人員建立更為合理的調(diào)度優(yōu)化模型。

(2)計(jì)算并繪制了離線批處理作業(yè)的DAG(Directed Acyclic Graph)關(guān)系圖和每個(gè)作業(yè)的關(guān)鍵路徑，計(jì)算了任務(wù)等待時(shí)間、作業(yè)通信時(shí)間等指標(biāo)，并指出了可能的任務(wù)調(diào)度優(yōu)化空間。

2 數(shù)據(jù)集概述

2018年12月，阿里巴巴面向公眾開(kāi)放了一個(gè)具有4 034個(gè)結(jié)點(diǎn)的混部集群運(yùn)行日志數(shù)據(jù)cluster-trace-v2018(以下簡(jiǎn)稱(chēng)trace-2018)，圖1是阿里巴巴混部集群調(diào)度管理系統(tǒng)示意圖。與阿里巴巴2017年首次公開(kāi)的混部集群數(shù)據(jù)集cluster-trace-v2017(以下簡(jiǎn)稱(chēng)trace-2017)相比，trace-2018的數(shù)據(jù)更豐富，具體體現(xiàn)在：(1)時(shí)間跨度更長(zhǎng)，服務(wù)器數(shù)量更多。trace-2018中記錄了混部集群中4 034臺(tái)機(jī)器連續(xù)8天的運(yùn)行狀況，而trace-2017數(shù)據(jù)集僅包含1 300臺(tái)機(jī)器在1天內(nèi)的運(yùn)行日志；(2)trace-2018包含了以DAG形式表示的離線批處理作業(yè)中任務(wù)間的依賴(lài)信息。

Figure 1 Architecture of the Alibaba co-located cluster management system圖1 阿里巴巴混部集群管理系統(tǒng)架構(gòu)示意圖

trace-2018數(shù)據(jù)包含6個(gè)csv表格數(shù)據(jù)，涵蓋機(jī)器、離線批處理作業(yè)、在線容器3類(lèi)主體。每個(gè)主體包含1份靜態(tài)信息表與1份運(yùn)行信息表，如表1所示。接下來(lái)分別對(duì)機(jī)器、離線批處理作業(yè)、在線容器這3類(lèi)主體的數(shù)據(jù)進(jìn)行分析。

Table 1 Data tables in trace-2018表1 trace-2018數(shù)據(jù)構(gòu)成

2.1 機(jī)器

trace-2018中的機(jī)器指混部集群中的物理服務(wù)器，這些機(jī)器既運(yùn)行離線批處理作業(yè)，也作為容器宿主機(jī)，運(yùn)行在線服務(wù)。machine_meta.csv表記錄了機(jī)器靜態(tài)配置信息，主要包括機(jī)器編號(hào)(machine_id)、容錯(cuò)等級(jí)(disaster_level_1和disaster_level_2)、CPU核心數(shù)量(cpu_num)、內(nèi)存容量(mem_size)和狀態(tài)(status)。該表包含每臺(tái)機(jī)器1個(gè)或多個(gè)時(shí)間戳上的配置信息，記錄了不同時(shí)間點(diǎn)機(jī)器的配置情況(但全表中未出現(xiàn)機(jī)器配置變化)。

machine_usage.csv記錄了機(jī)器的實(shí)時(shí)運(yùn)行信息數(shù)據(jù)，包括時(shí)間戳、CPU利用率(cpu_util_percent)、內(nèi)存利用率(mem_util_percent)和硬盤(pán)帶寬利用率(disk_io_percent)等。

2.2 離線批處理作業(yè)

離線批處理作業(yè)具有作業(yè)-任務(wù)-實(shí)例3層結(jié)構(gòu)，即job-task-instance(為方便和數(shù)據(jù)集中字段參照，下文中將作業(yè)和job，任務(wù)和task，實(shí)例和instance交叉使用)。1個(gè)作業(yè)包含1個(gè)或多個(gè)任務(wù)，同一個(gè)作業(yè)的任務(wù)可能會(huì)有先后執(zhí)行順序的約束。1個(gè)任務(wù)包含1個(gè)或多個(gè)實(shí)例，同一個(gè)任務(wù)的實(shí)例沒(méi)有先后執(zhí)行順序，每個(gè)實(shí)例可以被分配到不同的機(jī)器上以并行執(zhí)行。圖2給出了ID為j_87的作業(yè)的“job-task-instance”3層結(jié)構(gòu)。

Figure 2 Internal structure of batch job j_87圖2 批處理作業(yè)j_87的內(nèi)部結(jié)構(gòu)

2.3 在線服務(wù)容器

容器用于承載在線任務(wù)，常用于用戶(hù)端內(nèi)容搜索、電商平臺(tái)交易等業(yè)務(wù)。在線任務(wù)具有很強(qiáng)的時(shí)延敏感性，其服務(wù)質(zhì)量將直接影響在線服務(wù)的用戶(hù)體驗(yàn)。因此，在線任務(wù)具有很高的優(yōu)先級(jí)。1臺(tái)機(jī)器上通常部署多個(gè)容器且不間斷地運(yùn)行。

container_meta.csv記錄了容器的靜態(tài)配置信息，包括容器編號(hào)(container_id)、容器所在機(jī)器編號(hào)(machine_id)、容器所屬的應(yīng)用組(app_du)、容器狀態(tài)(status)、請(qǐng)求CPU核心數(shù)量(cpu_request)、CPU核心使用數(shù)量限制(cpu_limit)和容器請(qǐng)求的內(nèi)存使用量(mem_size)。container_usage.csv表記錄了容器的實(shí)時(shí)運(yùn)行信息，包括CPU資源使用率(cpu_util_percent)、每指令時(shí)鐘周期(cpi)、每千條指令緩存缺失次數(shù)(mpki)、內(nèi)存使用率(mem_util_percent)、內(nèi)存帶寬使用率(mem_gps)、磁盤(pán)IO使用率(disk_io_percent)、接收網(wǎng)絡(luò)數(shù)據(jù)包數(shù)量(net_in)和發(fā)送網(wǎng)絡(luò)數(shù)據(jù)包數(shù)量(net_out)。

3 作業(yè)調(diào)度特征

離線批處理作業(yè)擁有“job-task-instance”3層結(jié)構(gòu)，我們將job、task和instance的數(shù)量進(jìn)行統(tǒng)計(jì)，如表2所示。

Table 2 Number of elements in “job-task-instance” hierarchy表2 “job-task-instance”層次結(jié)構(gòu)中的元素?cái)?shù)量

根據(jù)同一個(gè)job的task之間的依賴(lài)關(guān)系，可以將所有task分為3種類(lèi)型，如表3所示。

Table 3 Example of DAG task names表3 DAG任務(wù)命名示例

(1)無(wú)DAG關(guān)系：該類(lèi)task所屬的job無(wú)DAG結(jié)構(gòu)，其執(zhí)行可以完全并行化。該類(lèi)task的名稱(chēng)有2種形式：①以“task_”加上一段隨機(jī)數(shù)字與字母組成的字符串，并以“==”結(jié)尾，本文稱(chēng)之為task_xxxx型；②“MergeTask”，本文稱(chēng)之為MergeTask型。

(2)有DAG關(guān)系、有依賴(lài)：該類(lèi)task有1個(gè)或多個(gè)前驅(qū)依賴(lài)。其名稱(chēng)是單個(gè)大寫(xiě)字母與該task在job內(nèi)序號(hào)的組合，加上“_”，后跟其依賴(lài)的task的job內(nèi)序號(hào)構(gòu)成。1個(gè)task可以有多個(gè)依賴(lài)。如表3中的示例J3_1_2表示job內(nèi)序號(hào)為3的task“J3_1_2”依賴(lài)于job內(nèi)序號(hào)為1和2的task。

(3)有DAG關(guān)系、無(wú)依賴(lài)：該類(lèi)task所屬的job有DAG結(jié)構(gòu)，但是該任務(wù)本身不依賴(lài)于任何其它task。此類(lèi)task可能成為其所屬job包含的其余task的依賴(lài)。另外，存在task名稱(chēng)中包含“_Stg”的特殊情況。如名為“M9_Stg4”的task，此處的“_Stg4”不指代任何task。

表4給出了3類(lèi)任務(wù)的占比。在所有的task中，只有少部分不具有DAG關(guān)系(15.98%)，且具有前驅(qū)依賴(lài)的task的數(shù)量幾乎占總數(shù)的一半(47.07%)。

Table 4 Classification and statistics of tasks according to DAG dependencies表4 任務(wù)分類(lèi)(有無(wú)DAG依賴(lài))

圖3展示了作業(yè)j_2041的任務(wù)依賴(lài)示意圖。為了計(jì)算上的便利，我們添加了start和end節(jié)點(diǎn)；每個(gè)節(jié)點(diǎn)表示job中的1個(gè)task，節(jié)點(diǎn)中的數(shù)字表示的是task在job內(nèi)的編號(hào)；圖3中帶箭頭的有向邊(x→y)表示2個(gè)task之間的依賴(lài)關(guān)系，如圖3中task 1、2、3、5都依賴(lài)于task 4，而task 6依賴(lài)于task 1、2、3、5，有向邊上的數(shù)字表示的是所依賴(lài)的task的實(shí)際執(zhí)行時(shí)間，如有向邊4→1上的值為5，表示task 4的執(zhí)行時(shí)間為5 s，即task 1需要等待5 s(task 4執(zhí)行完)才能開(kāi)始執(zhí)行。由于數(shù)據(jù)集中缺乏相關(guān)數(shù)據(jù)，我們沒(méi)有考慮task間數(shù)據(jù)傳輸、任務(wù)調(diào)度等帶來(lái)的其他時(shí)間開(kāi)銷(xiāo)，即僅考慮理想情況下的DAG圖；圖3中用灰色顯示的節(jié)點(diǎn)及虛線有向邊代表此DAG圖中的關(guān)鍵路徑，在該路徑上的task執(zhí)行時(shí)間之和最大。

Figure 3 DAG example of job j_2041圖3 作業(yè)j_2041的DAG圖

instance是離線作業(yè)中最細(xì)粒度的調(diào)度單位，我們根據(jù)其所屬的task是否含有DAG關(guān)系，將所有instance劃分為2類(lèi)，如表5所示。在表5中，含DAG關(guān)系的task的instance調(diào)度次數(shù)占總調(diào)度次數(shù)的96.91%，這與前述的含DAG關(guān)系的task占總task數(shù)量的84.02%有一定差別。說(shuō)明包含DAG關(guān)系的任務(wù)的規(guī)模大小不同，導(dǎo)致其中instance的調(diào)度次數(shù)不同。

Table 5 Scheduling numbers of DAG and noDAG instances表5 DAG型與noDAG型實(shí)例的調(diào)度數(shù)量

如表6所示，通過(guò)計(jì)算DAG型task與noDAG型task包含instance數(shù)量的均值，發(fā)現(xiàn)上述現(xiàn)象是由包含DAG關(guān)系的task平均包含更多數(shù)量的instance引起的。從表6可以直觀地看出，noDAG型的task不僅沒(méi)有依賴(lài)關(guān)系，在體積上也更為輕量，其包含的平均instance數(shù)量只有DAG型task的0.16倍，全體task均值的0.19倍。

Table 6 Number of instances in each type of task表6 各類(lèi)型任務(wù)包含的實(shí)例數(shù)量

為了研究DAG型和noDAG型任務(wù)在調(diào)度instance到機(jī)器的過(guò)程中是否存在偏好，本文對(duì)所有機(jī)器上運(yùn)行的DAG型和noDAG型實(shí)例進(jìn)行了統(tǒng)計(jì)，發(fā)現(xiàn)在運(yùn)行較多實(shí)例的機(jī)器上，接受的DAG型實(shí)例調(diào)度次數(shù)處于同一數(shù)量級(jí)，而noDAG型實(shí)例的調(diào)度情況則有所不同。由表7可見(jiàn)，在數(shù)據(jù)集所記錄的時(shí)間范圍內(nèi)，machine_id為m_1455的機(jī)器曾接受過(guò)133 522次noDAG型實(shí)例的調(diào)度，是所有機(jī)器中最多的。machine_id為m_3761的機(jī)器所接受的noDAG型實(shí)例調(diào)度次數(shù)位列第二，然而其數(shù)量為14 313次，僅占機(jī)器m_1455的10.72%?？梢?jiàn)，在阿里巴巴混部集群中調(diào)度器會(huì)設(shè)置特殊分工的機(jī)器，該類(lèi)機(jī)器相較于集群中的其他機(jī)器，會(huì)接受更多的來(lái)自于noDAG型task的instance調(diào)度。

Table 7 Number of scheduled instances on machine m_1455 and m_3761表7 機(jī)器m_1455與m_3761上運(yùn)行的instance數(shù)量

為了對(duì)比DAG型與noDAG型2種task的調(diào)度特征，本文將二者包含的instance在機(jī)器上的調(diào)度次數(shù)的分布按照DAG型task包含的instance調(diào)度次數(shù)升序排序，如圖4所示。由于noDAG型task包含的instance總數(shù)較少，本文將其分布進(jìn)行歸一化處理，分別以2種instance在機(jī)器上的最大調(diào)度次數(shù)為基準(zhǔn)(noDAG型不含前述的m_1455機(jī)器)。從圖4中可以看出，DAG型task包含的instance調(diào)度數(shù)量與noDAG型在機(jī)器上的分布較為相似。為了進(jìn)一步確認(rèn)，計(jì)算得出兩者的相關(guān)系數(shù)為0.75，表明調(diào)度器對(duì)有無(wú)DAG關(guān)系沒(méi)有明顯偏好(除m_1455機(jī)器)。另外，在圖4放大部分中，無(wú)論DAG型還是noDAG型task，其中instance的調(diào)度次數(shù)在機(jī)器上的分布都有較為明顯的區(qū)間分布。

Figure 4 Distribution of scheduled tasks of DAG and noDAG (normalized to the maximum value of each type)圖4 DAG型與noDAG型task包含的 instance的調(diào)度分布(以各自類(lèi)型的最大值歸一化)

圖5中圖例data表示原數(shù)據(jù)的散點(diǎn)，其縱軸為單個(gè)應(yīng)用組上容器的數(shù)量出現(xiàn)的頻次，橫軸坐標(biāo)為該頻次的排名。在圖5a中，從排名第1的數(shù)據(jù)點(diǎn)開(kāi)始擬合，得到分布參數(shù)α為0.579，C為9.49E2，決定系數(shù)R2為0.858。從第10位的數(shù)據(jù)點(diǎn)開(kāi)始擬合，得到分布參數(shù)α為0.729，C為2.270E3，決定系數(shù)R2為0.941。圖5表明，不論是否去除排名前10的重量型在線應(yīng)用，混部集群中所有在線應(yīng)用的容器規(guī)模都具有明顯的傾斜現(xiàn)象，其分布符合Zipf分布。

Figure 5 Zipf distribution on container number in a single online application group圖5 在線應(yīng)用組的容器規(guī)模的Zipf分布

混部集群中在線應(yīng)用任務(wù)規(guī)模(應(yīng)用中容器數(shù)量)的傾斜現(xiàn)象的定量分析，可以為集群調(diào)度相關(guān)領(lǐng)域研究人員建立合理的在線任務(wù)調(diào)度模型提供參考?；觳考褐械倪@一傾斜現(xiàn)象，同本文作者之前發(fā)現(xiàn)的未混部的淘寶生產(chǎn)集群中的數(shù)據(jù)傾斜現(xiàn)象相類(lèi)似[10]。

4 調(diào)度優(yōu)化

本文使用多種衡量集群調(diào)度效率的指標(biāo)，用以評(píng)價(jià)混部集群管理系統(tǒng)的可優(yōu)化潛力。本文選擇的評(píng)價(jià)指標(biāo)將任務(wù)的生命周期劃分為多個(gè)階段，通過(guò)分析各個(gè)階段的開(kāi)銷(xiāo)，可以推斷相應(yīng)的性能影響因素，有助于確定混部集群的優(yōu)化方向。

4.1 實(shí)例開(kāi)始延遲

實(shí)例開(kāi)始延時(shí)SD(Start Delay)是指某instance開(kāi)始時(shí)間與其所屬task中的第1個(gè)開(kāi)始的instance的開(kāi)始時(shí)間之間的差值。1個(gè)task的平均SD(meanSD)指的是該task中所有instance的SD平均值，最大SD(maxSD)指的是該task中所有instance的SD的最大值，1個(gè)task的第i個(gè)instance的開(kāi)始延時(shí)tSD_i如式(1)所示：

tSD_i=Tinst_i_start-Tinst_first_start

(1)

其中，Tinst_i_start表示第i個(gè)instance的開(kāi)始時(shí)間,Tinst_first_start表示此task的第1個(gè)instance的開(kāi)始時(shí)間。

圖6將具有相同instance數(shù)量的task的平均SD和最大SD通過(guò)取平均值來(lái)聚合，研究trace-2018中1個(gè)task的instance的數(shù)量對(duì)instance的調(diào)度效率的影響。其中橫軸是1個(gè)task的instance數(shù)量(取數(shù)量大于或等于2的task)，縱軸是以秒為單位的開(kāi)始延時(shí)。

Figure 6 Relationship between instance start delay and number of instances圖6 實(shí)例開(kāi)始延時(shí)與其數(shù)量之間的關(guān)系

因?yàn)榘罅縤nstance的task數(shù)量占比較少，所以在圖6中，平均SD和最大SD在橫軸103～105的區(qū)域發(fā)生了較大的波動(dòng)。但是，整體趨勢(shì)仍然可以看出，隨著task的instance數(shù)量的增長(zhǎng)，task的平均SD與最大SD都有所上升(在橫軸為2時(shí)，平均SD與最大SD相交。因?yàn)槌プ钤玳_(kāi)始的instance外，只會(huì)剩下1個(gè)instance用于求SD，此時(shí)平均SD等于最大SD)。

在理想情況下，1個(gè)task中的所有instance是同時(shí)開(kāi)始執(zhí)行的，所以SD可以衡量1個(gè)task中instance的并行效率。我們發(fā)現(xiàn)，隨著task中包含的instance數(shù)量增加，調(diào)度器對(duì)于instance的調(diào)度效率不斷下降。

4.2 任務(wù)間隙時(shí)間

當(dāng)前驅(qū)依賴(lài)的task執(zhí)行完畢，后繼task并不會(huì)立即執(zhí)行，需要等待前驅(qū)task數(shù)據(jù)傳輸、系統(tǒng)調(diào)度等，本文將這段時(shí)間記為task的間隙時(shí)間。間隙時(shí)間可以反映有前后依賴(lài)的task之間實(shí)際上未執(zhí)行計(jì)算任務(wù)的時(shí)間。間隙時(shí)間越長(zhǎng)，則表明調(diào)度器的效率越低，所以該指標(biāo)可以用于探究集群調(diào)度有依賴(lài)task開(kāi)始執(zhí)行的效率。2個(gè)有依賴(lài)關(guān)系的task的間隙時(shí)間為當(dāng)前task的開(kāi)始執(zhí)行時(shí)間與其所依賴(lài)的task的結(jié)束時(shí)間之間的差值。2個(gè)有依賴(lài)關(guān)系的task的間隙時(shí)間tinterval的計(jì)算如式(2)所示：

tinterval=Tstart-Tdep_end

(2)

其中，Tstart表示當(dāng)前task的實(shí)際開(kāi)始執(zhí)行時(shí)間，Tdep_end表示當(dāng)前task所依賴(lài)的task的實(shí)際結(jié)束時(shí)間。

本文將間隙時(shí)間分為2種情況：

(1)情況1：當(dāng)job的所有task只有1個(gè)前驅(qū)依賴(lài)的時(shí)候，則任意2個(gè)有依賴(lài)關(guān)系的task的間隙時(shí)間是由數(shù)據(jù)傳輸、調(diào)度引起的，如圖7a所示；

(2)情況2：當(dāng)1個(gè)task有多個(gè)前驅(qū)依賴(lài)的時(shí)候，且其中1個(gè)前驅(qū)依賴(lài)的task的執(zhí)行時(shí)間又特別長(zhǎng)時(shí)，則另外的前驅(qū)task與當(dāng)前task之間的間隙時(shí)間會(huì)變長(zhǎng)，如圖7b所示。

Figure 7 Interval time of two cases圖7 2種情況間隙時(shí)間示意

為了對(duì)2種情況的間隙時(shí)間作說(shuō)明，對(duì)DAG圖進(jìn)行擴(kuò)展，在有向邊上增添了2個(gè)task的間隙時(shí)間，有向邊上括號(hào)外的數(shù)值表示task的執(zhí)行時(shí)間，括號(hào)內(nèi)的數(shù)值表示2個(gè)task的間隙時(shí)間，如圖7a有向邊1→2的標(biāo)簽為“69(3)”，表示task 1的執(zhí)行時(shí)間為69 s，task 1與task 2的間隙時(shí)間為3 s。圖7a中job(j_1084)的任意2個(gè)task的間隙時(shí)間完全是由數(shù)據(jù)傳輸、調(diào)度等所造成的；而圖7b中job(j_2959)的task 4同時(shí)依賴(lài)于task 1和task 3，task 4需要等待task 1和task 3執(zhí)行完才能執(zhí)行，而task 1的執(zhí)行時(shí)間為233 s，task 3的執(zhí)行時(shí)間為2 s，所以task 3很快就執(zhí)行完，而task 1仍需執(zhí)行相當(dāng)一段時(shí)間，造成task 3與task 4的間隙時(shí)間為239 s，此間隙時(shí)間不僅由數(shù)據(jù)傳輸、調(diào)度等造成，還與等待task 1執(zhí)行完有關(guān)。

4.3 任務(wù)等待時(shí)間

batch_task.csv表中字段start_time記錄的是每個(gè)task在job master的注冊(cè)時(shí)間，而task實(shí)際開(kāi)始執(zhí)行的時(shí)間為該task中首個(gè)instance開(kāi)始執(zhí)行的時(shí)間，將task實(shí)際開(kāi)始時(shí)間與注冊(cè)時(shí)間之間的差值定義為task的等待時(shí)間twaiting：

twaiting=Tfirst_inst_start-Tregister

(3)

其中，Tfirst_inst_start表示該task中最早開(kāi)始的instance的時(shí)間，即task的實(shí)際開(kāi)始時(shí)間，Tregister表示task的注冊(cè)時(shí)間。

Task的等待時(shí)間是由于此task的前驅(qū)task的執(zhí)行所耗費(fèi)的時(shí)間、task間的數(shù)據(jù)通信及調(diào)度等帶來(lái)的時(shí)間開(kāi)銷(xiāo)所造成的，所以task的等待時(shí)間可以視為衡量task調(diào)度效率的指標(biāo)，task的等待時(shí)間越長(zhǎng)則說(shuō)明調(diào)度效率越低。

4.4 作業(yè)通信時(shí)間

由于job的task間含有DAG關(guān)系，有前驅(qū)依賴(lài)的task需要等待其所依賴(lài)的task完成后才能執(zhí)行，而前驅(qū)依賴(lài)的task執(zhí)行完之后，并不會(huì)立即執(zhí)行當(dāng)前task，當(dāng)前task需要等待前驅(qū)task數(shù)據(jù)傳輸、系統(tǒng)調(diào)度等，才能開(kāi)始執(zhí)行。所以，完整執(zhí)行1個(gè)job的時(shí)間由2部分組成：(1)job中task的執(zhí)行時(shí)間(關(guān)鍵路徑長(zhǎng)度)；(2)task間通信、調(diào)度等帶來(lái)的時(shí)間開(kāi)銷(xiāo)。為此我們定義job的通信時(shí)間為關(guān)鍵路徑上task之間的數(shù)據(jù)通信、調(diào)度等時(shí)間開(kāi)銷(xiāo)。該指標(biāo)可以反映job執(zhí)行效率，縮短作業(yè)通信時(shí)間可在很大程度上縮短job的持續(xù)時(shí)間。

作業(yè)通信時(shí)間tcomm通過(guò)計(jì)算job的總耗時(shí)與關(guān)鍵路徑上的所有task的執(zhí)行時(shí)間之間的差值得到：

tcomm=tjob-tcritical

(4)

其中，tjob表示1個(gè)job的總執(zhí)行時(shí)間，tcritical表示DAG圖中關(guān)鍵路徑上的task的執(zhí)行時(shí)間之和。

4.5 作業(yè)執(zhí)行時(shí)間

1個(gè)作業(yè)的總執(zhí)行時(shí)間為其關(guān)鍵路徑上所有任務(wù)的總執(zhí)行時(shí)間(關(guān)鍵路徑長(zhǎng)度)與作業(yè)的通信時(shí)間之和。為了分析job的總執(zhí)行時(shí)間與上述二者之間的關(guān)系，給出了如圖8所示的job執(zhí)行時(shí)間、關(guān)鍵路徑長(zhǎng)度和job通信時(shí)間的累積分布函數(shù)CDF(Cumulative Distribution Function)圖，并對(duì)三者進(jìn)行比較,結(jié)果如表8所示。

Figure 8 CDF of job execution time,critical path length,and job communication time圖8 job執(zhí)行時(shí)間、關(guān)鍵路徑長(zhǎng)度和job通信時(shí)間CDF圖

表8 關(guān)鍵路徑長(zhǎng)度、job通信時(shí)間和job執(zhí)行時(shí)間對(duì)比 s

圖8給出了作業(yè)執(zhí)行時(shí)間、關(guān)鍵路徑長(zhǎng)度和作業(yè)通信時(shí)間的CDF圖，其中縱軸為累積分布，實(shí)線為job執(zhí)行時(shí)間，點(diǎn)劃線為關(guān)鍵路徑長(zhǎng)度，虛線為job通信時(shí)間。從圖8可以看出，橫坐標(biāo)在0～500左右處，job執(zhí)行時(shí)間和關(guān)鍵路徑長(zhǎng)度的CDF曲線近似直線，說(shuō)明在該時(shí)間段內(nèi)job執(zhí)行時(shí)間和關(guān)鍵路徑長(zhǎng)度分布得較為均勻，而job通信時(shí)間主要分布在0～25 s左右區(qū)間內(nèi)。

從表8可以發(fā)現(xiàn)，關(guān)鍵路徑的最大值(175 453)與job執(zhí)行時(shí)間的最大值(175 460)較為接近，它們都出自j_2724077，而j_2724077的通信時(shí)間僅為7 s；job通信時(shí)間的最大值為4 691 s，與關(guān)鍵路徑和job執(zhí)行時(shí)間最大值相差較大?？梢酝茰y(cè)job通信時(shí)間與job中關(guān)鍵路徑上的task執(zhí)行的總時(shí)間長(zhǎng)短并沒(méi)有直接關(guān)系。關(guān)鍵路徑長(zhǎng)度平均值為134.97 s(占job平均執(zhí)行時(shí)間71.20%)，而job通信時(shí)間平均值為54.59 s(占job平均執(zhí)行時(shí)間28.80%)，表明大多數(shù)job的通信時(shí)間較短，job執(zhí)行時(shí)間的增長(zhǎng)主要是由于關(guān)鍵路徑長(zhǎng)度增長(zhǎng)導(dǎo)致的，但仍有一部分job的通信時(shí)間相當(dāng)長(zhǎng)，有潛在的優(yōu)化空間以減少job的總執(zhí)行時(shí)間。

4.6 任務(wù)執(zhí)行優(yōu)化

為了研究task等待時(shí)間與其前驅(qū)task的執(zhí)行時(shí)間與間隙時(shí)間之間的關(guān)系，給出了如圖9所示的task等待時(shí)間、執(zhí)行時(shí)間和間隙時(shí)間的CDF圖。

Figure 9 CDF of task interval time圖9 間隙時(shí)間的CDF圖

上文介紹間隙時(shí)間時(shí)，提出了2種間隙時(shí)間情況：(1)情況1：job中所有task只依賴(lài)一個(gè)task；(2)情況2：job中存在task依賴(lài)多個(gè)task。圖9a為間隙時(shí)間為情況1的CDF圖，圖9b為間隙時(shí)間為情況2的CDF圖。根據(jù)圖9a發(fā)現(xiàn)，當(dāng)task等待時(shí)間較小時(shí)(約3 s)，task等待時(shí)間與間隙時(shí)間CDF曲線非常接近，而當(dāng)?shù)却龝r(shí)間逐漸增大時(shí)，間隙時(shí)間的CDF曲線高于等待時(shí)間的CDF曲線，即此時(shí)task間隙時(shí)間對(duì)等待時(shí)間影響逐漸減?。欢鴪D9b中等待時(shí)間和間隙時(shí)間的曲線保持高度一致，但需注意的是情況2的間隙時(shí)間受所依賴(lài)task的執(zhí)行時(shí)間影響，即task間的間隙時(shí)間會(huì)由于其中一個(gè)依賴(lài)task的執(zhí)行時(shí)間過(guò)長(zhǎng)而變長(zhǎng)，從而導(dǎo)致task等待時(shí)間變長(zhǎng)。因此可以得出結(jié)論，task等待時(shí)間受task執(zhí)行時(shí)間和間隙時(shí)間共同影響，但task執(zhí)行時(shí)間受task規(guī)?；蛘咛幚磉壿嫷臉O大影響，很難直接減少task的執(zhí)行時(shí)間。所以，有必要重視對(duì)task間隙時(shí)間的優(yōu)化，以減少整體task的等待時(shí)間。且由于離線批處理作業(yè)對(duì)時(shí)效不敏感，我們可以調(diào)整其執(zhí)行順序，通過(guò)將多個(gè)job聯(lián)合考慮以提升整體完成效率。

5 相關(guān)工作

對(duì)數(shù)據(jù)中心運(yùn)行日志的分析一直都是研究服務(wù)器性能瓶頸和優(yōu)化潛力的重要環(huán)節(jié)。針對(duì)阿里巴巴2017年發(fā)布的數(shù)據(jù)集trace-2017，多位學(xué)者給出了相應(yīng)的混部集群特征分析結(jié)果[11 - 15]。本文根據(jù)2018年發(fā)布的數(shù)據(jù)集trace-2018，針對(duì)出現(xiàn)的新特性，進(jìn)一步豐富了混部集群的相關(guān)研究。

除了阿里巴巴公開(kāi)的混部集群數(shù)據(jù)集，目前還有大量利用自有數(shù)據(jù)中心運(yùn)行日志分析結(jié)果進(jìn)一步優(yōu)化調(diào)度性能的案例。Jiang等[16,17]使用模擬的混合負(fù)載測(cè)試多種虛擬化平臺(tái)，利用運(yùn)行日志充分比較各平臺(tái)之間的優(yōu)勢(shì)與劣勢(shì)，為數(shù)據(jù)中心調(diào)度系統(tǒng)設(shè)計(jì)者提供了重要參考。Qiu等[18]設(shè)計(jì)了一種結(jié)合了日志采集的簡(jiǎn)化虛擬機(jī)調(diào)度框架，節(jié)省了37.07%～49.98%的服務(wù)器功耗。

為了促進(jìn)業(yè)界與學(xué)術(shù)界對(duì)于集群調(diào)度的研究，Google于2012年公開(kāi)了其異構(gòu)集群的跟蹤數(shù)據(jù)集(clusterdata-2011-2)[19]，包含了集群內(nèi)12 500臺(tái)服務(wù)器在29天內(nèi)的負(fù)載數(shù)據(jù)[20]。作為Google目前正在使用的大規(guī)模集群管理系統(tǒng)，Borg采用了類(lèi)似于Alibaba集群管理系統(tǒng)的混部機(jī)制。該調(diào)度器隱藏了2種負(fù)載間資源分配與錯(cuò)誤處理的細(xì)節(jié)，讓開(kāi)發(fā)者能夠?qū)Ｗ⒂跇I(yè)務(wù)的開(kāi)發(fā)[21]。Borg是少數(shù)幾個(gè)在萬(wàn)臺(tái)服務(wù)器以上規(guī)模集群獲得較高彈性與可靠性的系統(tǒng)。Google部署B(yǎng)org至今已經(jīng)超過(guò)10年，混部比例高達(dá)98%。Google曾經(jīng)統(tǒng)計(jì)過(guò)，如果不使用這樣的機(jī)制，應(yīng)對(duì)相同的工作負(fù)載，機(jī)器的數(shù)量需要額外增加20%～30%[3]。

由于大規(guī)模集群跟蹤數(shù)據(jù)集的稀缺性，該數(shù)據(jù)集成為了許多相關(guān)領(lǐng)域科研人員的研究對(duì)象。據(jù)統(tǒng)計(jì)，已經(jīng)有超過(guò)450篇發(fā)表的論文在實(shí)驗(yàn)過(guò)程中使用到了Google的跟蹤數(shù)據(jù)集[22]。許多研究工作通過(guò)分析該數(shù)據(jù)集，對(duì)大型集群的負(fù)載特征、故障處理、調(diào)度機(jī)制等進(jìn)行了深入探究[23,24]。

除此之外，由于Google數(shù)據(jù)集在權(quán)威性、數(shù)據(jù)量方面的優(yōu)勢(shì)，眾多的研究工作利用Google跟蹤數(shù)據(jù)集來(lái)評(píng)估算法或系統(tǒng)的性能。其中，Islam等[25]提出了一種基于循環(huán)神經(jīng)網(wǎng)絡(luò)RNN(Recurrent Neural Network)的集群故障預(yù)測(cè)算法，利用Google數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測(cè)試，預(yù)測(cè)準(zhǔn)確率達(dá)到了87%。Han等[26]將Google跟蹤數(shù)據(jù)集作為參考，設(shè)計(jì)出了可以產(chǎn)生不同類(lèi)型負(fù)載的基準(zhǔn)工具，用以研究云服務(wù)的性能瓶頸。Xu等[27]利用真實(shí)電價(jià)與Google跟蹤數(shù)據(jù)集等數(shù)據(jù)，測(cè)試提出的基于區(qū)塊鏈的去中心化資源管理系統(tǒng)在降低電力成本方面的效果。Dabbagh等[28]針對(duì)過(guò)度承諾資源的云服務(wù)，設(shè)計(jì)出一套高效能的虛擬機(jī)預(yù)測(cè)與遷移框架，并在Google數(shù)據(jù)集的測(cè)試下證明該框架能夠顯著降低電力消耗。此外，還有很多資源分配方面的研究利用Google數(shù)據(jù)集，提出了有價(jià)值的資源調(diào)度算法[29 - 33]。

大型集群的運(yùn)行日志數(shù)據(jù)對(duì)于推動(dòng)相關(guān)領(lǐng)域的研究是大有裨益的。然而，Google跟蹤數(shù)據(jù)集已經(jīng)公開(kāi)將近7年，整個(gè)互聯(lián)網(wǎng)環(huán)境都發(fā)生了較大的變化，使用該數(shù)據(jù)集得出的結(jié)論對(duì)于當(dāng)今的環(huán)境是否適用有待考證。并且，大量的集群調(diào)度研究工作集中在單一的數(shù)據(jù)集上，容易使研究結(jié)論陷入過(guò)擬合的誤區(qū)。如果要進(jìn)一步得出有價(jià)值的研究成果，選擇更為多樣、更為新穎的數(shù)據(jù)集是很有必要的。因此，本文的分析工作對(duì)于研究目前的混部集群的任務(wù)負(fù)載特征和調(diào)度優(yōu)化具有較高的參考價(jià)值。

6 結(jié)束語(yǔ)

作為開(kāi)放集群跟蹤項(xiàng)目(Open Cluster Trace Program)的一部分，阿里巴巴繼2017年開(kāi)放實(shí)際生產(chǎn)中的混部集群日志cluster-trace-v2017后，于2018年末開(kāi)放了時(shí)間跨度更長(zhǎng)、機(jī)器數(shù)量更多、包含離線批處理任務(wù)間依賴(lài)關(guān)系的cluster-trace-v2018。

在本文中，我們分析了cluster-trace-v2018的新特性，詳細(xì)介紹了在“job-task-instance”3層結(jié)構(gòu)下DAG形式的task間依賴(lài)的表達(dá)方式。對(duì)數(shù)據(jù)集中靜態(tài)、動(dòng)態(tài)運(yùn)行情況下的調(diào)度情況進(jìn)行了統(tǒng)計(jì)分析?；诨觳考哼\(yùn)行時(shí)特征，使用了開(kāi)始延時(shí)、間隙時(shí)間、等待時(shí)間等多種指標(biāo)來(lái)評(píng)價(jià)含有DAG形式依賴(lài)關(guān)系的批處理作業(yè)調(diào)度效率，并分析對(duì)其進(jìn)一步優(yōu)化的方向與可能性。最后，在未來(lái)的工作中，希望可以根據(jù)本文中分析的混部集群特性與可優(yōu)化潛力，提出DAG形式離線任務(wù)在混部場(chǎng)景下的優(yōu)化方案，可以在不同混部搭配條件下有效提升機(jī)器硬件資源使用率。