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

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

1 比賽初衷

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

2 賽題背景

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

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

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

3 解題思路

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

3.1 初始解的求解思路

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

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

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

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

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

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

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

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

3.1.3 使用成本公式進行剩余流的分配

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

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

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

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

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

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

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

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

邊緣成本不增加，下稱“騰空邊緣節(jié)點”。

3.2.1.1 邊緣遷移

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

? 遷入節(jié)點是非空節(jié)點。遷入節(jié)點不能在所有時刻都沒有承載過流量。

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

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

3.2.2 騰空邊緣節(jié)點

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

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

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

約束條件包含以下三點：

? 遷入節(jié)點是非空節(jié)點。遷入節(jié)點不能在所有時刻都沒有承載過流量。

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

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

4 比賽收獲

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

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

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

5.1 可讀性

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

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

5.2 可維護性

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

Figure 5: 提高代碼的可維護性

生成海報

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