2022華為軟件精英挑戰(zhàn)賽，最優(yōu)美代碼賽隊(duì)分享解題方案

5月21-22日，2022第八屆華為軟件精英挑戰(zhàn)賽-“普朗克計(jì)劃”總決賽及頒獎(jiǎng)典禮在深圳成功舉辦。大賽吸引了來(lái)自國(guó)內(nèi)外826所高校、3291支隊(duì)伍、2萬(wàn)余名大學(xué)生報(bào)名參賽，歷時(shí)兩個(gè)多月的激烈角逐，經(jīng)過(guò)八大賽區(qū)區(qū)域初賽、區(qū)域復(fù)賽、全球總決賽等環(huán)節(jié)的層層考驗(yàn)，最終，9支優(yōu)秀隊(duì)伍憑借優(yōu)異表現(xiàn)分享了66萬(wàn)元總獎(jiǎng)金池。其中，來(lái)自粵港澳賽區(qū)的“路路的小跟班”隊(duì)，贏得“最優(yōu)美代碼獎(jiǎng)”，賽隊(duì)撰文分享其參賽體驗(yàn)，包括解題思路、比賽收獲以及把代碼做到“最優(yōu)美”的技巧等。

1 比賽初衷

參加華為軟件精英挑戰(zhàn)賽的初衷是為了通過(guò)比賽提高自身的編程能力，開(kāi)闊個(gè)人的眼界。通過(guò)不斷的挑戰(zhàn)不同的難題，提升問(wèn)題的解決能力。同時(shí)通過(guò)比賽積累競(jìng)賽經(jīng)驗(yàn)，在各種比賽中贏得更多的獎(jiǎng)金。

2 賽題背景

提升用戶體驗(yàn)的同時(shí)降低運(yùn)營(yíng)成本是云服務(wù)競(jìng)爭(zhēng)力的關(guān)鍵。在視頻直播場(chǎng)景中, 網(wǎng)絡(luò)成本是影響服務(wù)成本的關(guān)鍵因素之一, 不同的流量調(diào)度方案會(huì)產(chǎn)生不同的網(wǎng)絡(luò)使用成本。

本屆賽題以華為云視頻直播服務(wù)流量調(diào)度問(wèn)題為基礎(chǔ), 并進(jìn)行一定的抽象、調(diào)整和簡(jiǎn)化。參賽選手需要設(shè)計(jì)高效的調(diào)度算法, 在滿足客戶要求的前提下, 通過(guò)對(duì)流量的合理調(diào)度, 最小化網(wǎng)絡(luò)使用成本。賽題中的流量調(diào)度示意圖如Figure 1所示。

Figure 1: 流量調(diào)度示意圖

3 解題思路

對(duì)于此類(lèi)優(yōu)化問(wèn)題，我們首先需要針對(duì)問(wèn)題尋找一個(gè)合法的初始解，然后再對(duì)初始解進(jìn)行優(yōu)化得到一個(gè)更優(yōu)的解。

3.1 初始解的求解思路

初始解決定了最終的解決方案的下限，由于賽題限制了運(yùn)行時(shí)間為300s，因此本次比賽最重要的一步是獲得一個(gè)較好的初始解。我們的初始解求解方案包括了對(duì)數(shù)據(jù)流削峰，邊緣節(jié)點(diǎn)帶寬均衡化，以及使用成本公式進(jìn)行流的分配三步。

3.1.1 數(shù)據(jù)流削峰處理

根據(jù)賽題描述中的單個(gè)邊緣節(jié)點(diǎn)的成本計(jì)算方法，可以知道邊緣節(jié)點(diǎn)帶寬大于其P95 帶寬值的時(shí)刻屬于免費(fèi)時(shí)刻，可以最大程度的利用。而客戶節(jié)點(diǎn)的流在每一個(gè)時(shí)刻的總量是不同的，通常會(huì)存在明顯的峰值，為了能夠在時(shí)間維度上，對(duì)整體的數(shù)據(jù)流做一個(gè)削峰處理，我們利用每一個(gè)邊緣節(jié)點(diǎn)的擁有的免費(fèi)時(shí)刻來(lái)進(jìn)行數(shù)據(jù)流的削峰，在具體的免費(fèi)時(shí)刻選擇上，我們通過(guò)計(jì)算邊緣節(jié)點(diǎn)在每個(gè)時(shí)刻承載的流量和排序，選擇前5% 時(shí)刻作為免費(fèi)時(shí)刻，然后盡可能利用該時(shí)刻邊緣節(jié)點(diǎn)的帶寬裝填數(shù)據(jù)流。在邊緣節(jié)點(diǎn)排序上，我們嘗試了多種排序方式，包括根據(jù)邊緣節(jié)點(diǎn)連接的客戶數(shù)量，邊緣節(jié)點(diǎn)總?cè)萘浚约岸呒訖?quán)的方式進(jìn)行排序。Figure 2是邊緣節(jié)點(diǎn)經(jīng)過(guò)削峰處理后在整體時(shí)間維度上的帶寬使用情況。

Figure 2: 邊緣節(jié)點(diǎn)95 百分位帶寬

3.1.2 邊緣節(jié)點(diǎn)帶寬均衡化

公式1定義了第j 個(gè)邊緣節(jié)點(diǎn)的成本計(jì)算方式，觀察可知邊緣節(jié)點(diǎn)的成本與該節(jié)點(diǎn)的承載量并不是線性的，在邊緣節(jié)點(diǎn)的P95 帶寬超過(guò)邊緣節(jié)點(diǎn)成本調(diào)整參數(shù)V 后，邊緣節(jié)點(diǎn)的成本將隨著承載量的增大以平方倍數(shù)增加。因此需要將數(shù)據(jù)流均衡分布到不同的邊緣節(jié)點(diǎn)上，以減少懲罰。

在方案設(shè)計(jì)上，我們采用了一種均衡化方法，如Figure 3所示。通過(guò)盡可能的將數(shù)據(jù)流均勻的分布到不同的邊緣節(jié)點(diǎn)上，以避免單個(gè)邊緣節(jié)點(diǎn)承載量過(guò)高帶來(lái)的額外懲罰。這里的難點(diǎn)在于，對(duì)于每個(gè)邊緣節(jié)點(diǎn)，應(yīng)該分配多少數(shù)據(jù)流總量。我們通過(guò)計(jì)算邊緣節(jié)點(diǎn)在整個(gè)時(shí)間線上，每一個(gè)時(shí)刻應(yīng)該承擔(dān)的數(shù)據(jù)流總量，具體方法是將數(shù)據(jù)流的大小平攤到數(shù)據(jù)流能夠分發(fā)的所有邊緣節(jié)點(diǎn)上，然后將每一個(gè)邊緣節(jié)點(diǎn)每一個(gè)的能夠連接到的用戶節(jié)點(diǎn)的數(shù)據(jù)流平均化求和，并進(jìn)行排序，取最大值作為整個(gè)時(shí)間序列上該邊緣節(jié)點(diǎn)的分發(fā)量。在邊緣節(jié)點(diǎn)的選擇順序上，我們采用了第一步相同的排序思路，盡可能優(yōu)先選擇連接用戶節(jié)點(diǎn)數(shù)較多以及容量較大的邊緣節(jié)點(diǎn)。

Figure 3: 邊緣節(jié)點(diǎn)流量均衡化

3.1.3 使用成本公式進(jìn)行剩余流的分配

經(jīng)過(guò)上述兩步，依然會(huì)剩下部分用戶節(jié)點(diǎn)的流未進(jìn)行分配，針對(duì)這部分流，我們采取流選邊緣節(jié)點(diǎn)的方法，在邊緣節(jié)點(diǎn)的選擇上，使用公式2計(jì)算放入當(dāng)前數(shù)據(jù)流后，中心節(jié)點(diǎn)成本與邊緣節(jié)點(diǎn)成本增加最少的邊緣節(jié)點(diǎn)，將數(shù)據(jù)流分配給該邊緣節(jié)點(diǎn)。根據(jù)邊緣節(jié)點(diǎn)和中心節(jié)點(diǎn)的成本計(jì)算出單個(gè)流增加成本最少的最優(yōu)的邊緣節(jié)點(diǎn)，并將該流放置到最優(yōu)邊緣節(jié)點(diǎn)。

對(duì)于這個(gè)賽題而言，僅采用上述三步并不能保證有可行解，對(duì)于嚴(yán)格的數(shù)據(jù)，可能需要加上數(shù)據(jù)流遷移等操作得到合法解決方案。但在實(shí)際的數(shù)據(jù)集測(cè)試中，我們僅采用上述三步就已經(jīng)產(chǎn)生了一個(gè)合法的可行解。

3.2 優(yōu)化初始解的思路

如公式2所示，賽題的目標(biāo)函數(shù)由中心節(jié)點(diǎn)成本和邊緣節(jié)點(diǎn)成本兩部分組成。為了簡(jiǎn)化模型，我們通過(guò)約束將多目標(biāo)優(yōu)化問(wèn)題簡(jiǎn)化成單一目標(biāo)優(yōu)化問(wèn)題，因此我們優(yōu)化初始解的核心思路是通過(guò)約束其中一種成本不增加的同時(shí)降低另外一種成本，包含兩個(gè)方向：

? 邊緣節(jié)點(diǎn)的成本優(yōu)化。通過(guò)約束中心節(jié)點(diǎn)成本不增加的同時(shí)使得邊緣節(jié)點(diǎn)的成本降低；

? 中心節(jié)點(diǎn)的成本優(yōu)化。通過(guò)約束邊緣節(jié)點(diǎn)成本不增加的同時(shí)使得中心節(jié)點(diǎn)的成本降低。

3.2.1 邊緣節(jié)點(diǎn)的成本優(yōu)化

邊緣節(jié)點(diǎn)的成本是一個(gè)分段函數(shù)，根據(jù)其P95 帶寬使用不同的方式計(jì)算成本，其分段點(diǎn)是邊緣節(jié)點(diǎn)成本調(diào)整參數(shù)V，在我們的理解中這是一種變相的開(kāi)機(jī)成本。針對(duì)邊緣節(jié)點(diǎn)的成本計(jì)算方式，我們?cè)O(shè)計(jì)了兩種方案來(lái)優(yōu)化邊緣節(jié)點(diǎn)的成本，一是將邊緣節(jié)點(diǎn)A 在其P95 時(shí)刻承載的流遷移至邊緣節(jié)點(diǎn)B 后，邊緣節(jié)點(diǎn)A 的邊緣成本降低，而中心成本和邊緣節(jié)點(diǎn)B 的成本不增加，下稱(chēng)“邊緣遷移”；二是將邊緣節(jié)點(diǎn)A 所有時(shí)刻承載的流均遷移至對(duì)應(yīng)時(shí)刻的其他邊緣節(jié)點(diǎn)，消除邊緣節(jié)點(diǎn)A 的開(kāi)機(jī)成本的同時(shí)使得中心成本和其他邊緣節(jié)點(diǎn)的

邊緣成本不增加，下稱(chēng)“騰空邊緣節(jié)點(diǎn)”。

3.2.1.1 邊緣遷移

邊緣遷移主要用于降低邊緣節(jié)點(diǎn)的P95 帶寬，以達(dá)到降低邊緣成本的效果，邊緣遷移的算法框架見(jiàn)Algorithm 1。在邊緣遷移的算法框架中，首先獲得遍歷邊緣節(jié)點(diǎn)的順序，遍歷的順序比較靈活，可用的排序指標(biāo)包括邊緣節(jié)點(diǎn)的成本，P95 帶寬和P95 帶寬時(shí)刻的梯度等，這里使用的是邊緣節(jié)點(diǎn)的成本。在遍歷邊緣節(jié)點(diǎn)及其流量時(shí)刻的過(guò)程中，我們針對(duì)邊緣遷移的目的設(shè)定了兩個(gè)提前跳出循環(huán)的條件，具體可見(jiàn)代碼及注釋。最后則是邊緣遷移的核心MigrateFromSiteForSiteCost 函數(shù)，它通過(guò)遍歷對(duì)應(yīng)時(shí)刻的邊緣節(jié)點(diǎn)所承載的所有流，為這些流找到符合約束的遷入邊緣節(jié)點(diǎn)。在我們的實(shí)現(xiàn)中，設(shè)置的約束包括以下三點(diǎn)：

? 遷入節(jié)點(diǎn)是非空節(jié)點(diǎn)。遷入節(jié)點(diǎn)不能在所有時(shí)刻都沒(méi)有承載過(guò)流量。

? 待遷出流量不增加遷入節(jié)點(diǎn)的P95 帶寬。待遷出流量帶來(lái)的帶寬以及緩存量不能增加遷入節(jié)點(diǎn)的P95 帶寬。

?遷移后該時(shí)刻的中心成本不增加。遷出節(jié)點(diǎn)降低的中心成本不低于遷入節(jié)點(diǎn)升高的中心成本，即遷移后該時(shí)刻的中心成本不增加。

3.2.2 騰空邊緣節(jié)點(diǎn)

為了降低開(kāi)機(jī)成本V，我們?cè)O(shè)計(jì)了騰空邊緣節(jié)點(diǎn)的操作。算法的主要約束與邊緣遷移類(lèi)似，不同之處在于騰空邊緣節(jié)點(diǎn)的操作需要邊緣節(jié)點(diǎn)在所有時(shí)刻承載的流量都可以遷出時(shí)我們才執(zhí)行“騰空”操作。

3.3 中心節(jié)點(diǎn)的成本優(yōu)化

觀察中心節(jié)點(diǎn)的成本計(jì)算方式，易得核心優(yōu)化思路是盡可能地將同一時(shí)刻同一類(lèi)型的流量放在同一個(gè)邊緣節(jié)點(diǎn)，下稱(chēng)“流量聚合”。為了實(shí)現(xiàn)流量聚合，我們?cè)O(shè)計(jì)了“中心遷移”算法，算法框架見(jiàn)Algorithm 2。中心遷移算法的整體框架與邊緣節(jié)點(diǎn)類(lèi)似，最主要的區(qū)別在于改變了遷移的約束條件，中心遷移的

約束條件包含以下三點(diǎn)：

? 遷入節(jié)點(diǎn)是非空節(jié)點(diǎn)。遷入節(jié)點(diǎn)不能在所有時(shí)刻都沒(méi)有承載過(guò)流量。

? 待遷出流量不增加遷入節(jié)點(diǎn)的P95 帶寬。待遷出流量帶來(lái)的帶寬以及緩存量不能增加遷入節(jié)點(diǎn)的P95 帶寬。

? 遷移后中心帶寬降低。遷移后，遷出節(jié)點(diǎn)減少的中心帶寬需要大于遷入節(jié)點(diǎn)增加的中心帶寬。

4 比賽收獲

在本次比賽中，比較高興的是我們獲得了最優(yōu)美代碼獎(jiǎng)，比較遺憾的是最終因?yàn)橐粋€(gè)題意理解錯(cuò)誤產(chǎn)生的BUG 失去了更進(jìn)一步的機(jī)會(huì)。不過(guò)這次比賽收獲頗豐，不但認(rèn)識(shí)到自身的不足，而且認(rèn)識(shí)了很多新的朋友。這不僅是一次比賽，更是一場(chǎng)旅行，感謝華為主辦方的悉心安排，感謝工作人員在比賽過(guò)程中辛勤付出，感謝小伙伴之間的思維碰撞，希望未來(lái)仍有機(jī)會(huì)與大家相聚。

5 對(duì)于“最優(yōu)美代碼”的理解

軟挑是一個(gè)團(tuán)隊(duì)比賽，為了減少溝通成本和提高編碼效率，我們隊(duì)伍主要規(guī)范了代碼的可讀性和可維護(hù)性。

5.1 可讀性

在團(tuán)隊(duì)協(xié)作中，讓隊(duì)友快速讀懂你的代碼是非常重要的，為此我們隊(duì)伍統(tǒng)一使用Google C++ 編程風(fēng)格。團(tuán)隊(duì)成員統(tǒng)一編程風(fēng)格并遵守約定意味著可以很容易根據(jù)“模式匹配”規(guī)則來(lái)推斷各種標(biāo)識(shí)符的含義。我們的編碼風(fēng)格如圖4所示。

Figure 4: 統(tǒng)一的編碼風(fēng)格

5.2 可維護(hù)性

軟挑的正式賽是需要現(xiàn)場(chǎng)編碼新需求的，因此代碼的可維護(hù)性尤為重要。在編碼過(guò)程中，我們盡量保持方法的原子性，提高代碼內(nèi)聚，并將實(shí)現(xiàn)的功能模塊化，做到即插即用。如圖5所示，我們對(duì)賽題進(jìn)行了抽象和封裝，設(shè)計(jì)出對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)。同時(shí)，我們將諸如將流在節(jié)點(diǎn)之間進(jìn)行遷移的通用操作解耦出來(lái)，提高代碼的內(nèi)聚性，使得類(lèi)似的功能能夠即插即用。當(dāng)然，我們也在一些關(guān)鍵點(diǎn)使用assert 等工具進(jìn)行判斷，提高代碼的測(cè)試效率。

Figure 5: 提高代碼的可維護(hù)性

生成海報(bào)

免責(zé)聲明：本網(wǎng)站內(nèi)容主要來(lái)自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請(qǐng)進(jìn)一步核實(shí)，并對(duì)任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對(duì)有關(guān)資料所引致的錯(cuò)誤、不確或遺漏，概不負(fù)任何法律責(zé)任。任何單位或個(gè)人認(rèn)為本網(wǎng)站中的網(wǎng)頁(yè)或鏈接內(nèi)容可能涉嫌侵犯其知識(shí)產(chǎn)權(quán)或存在不實(shí)內(nèi)容時(shí)，應(yīng)及時(shí)向本網(wǎng)站提出書(shū)面權(quán)利通知或不實(shí)情況說(shuō)明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實(shí)情況證明。本網(wǎng)站在收到上述法律文件后，將會(huì)依法盡快聯(lián)系相關(guān)文章源頭核實(shí)，溝通刪除相關(guān)內(nèi)容或斷開(kāi)相關(guān)鏈接。