近年來大規(guī)模視頻直播經(jīng)歷了飛速的發(fā)展。諸如抖音、快手等直播平臺(tái)在全球范圍內(nèi)獲得了前所未有的關(guān)注。為了盡可能滿足用戶的觀看體驗(yàn)，直播內(nèi)容提供商租用云服務(wù)廠商提供內(nèi)容分發(fā)服務(wù)，因而云服務(wù)廠商在內(nèi)容分發(fā)過程中起到了至關(guān)重要的作用。相較于傳統(tǒng)的云服務(wù)任務(wù)（比如計(jì)算任務(wù)），大量的直播間和分散的用戶請(qǐng)求使得分發(fā)過程中會(huì)產(chǎn)生大量的帶寬成本，特別是大量的回源成本，高額的帶寬成本將會(huì)嚴(yán)重影響內(nèi)容提供商的進(jìn)入門檻。華為云算法創(chuàng)新lab聯(lián)合清華大學(xué)，針對(duì)大規(guī)模直播視頻的云服務(wù)業(yè)務(wù)，提出一種通過匯聚各區(qū)域分散用戶，減少邊緣節(jié)點(diǎn)個(gè)數(shù)并減低回源帶寬的方法。該方法上線華為云一年內(nèi)，在保障服務(wù)質(zhì)量的同時(shí)節(jié)省15%+的回源帶寬成本。

傳統(tǒng)LocalDNS調(diào)度的問題

對(duì)現(xiàn)網(wǎng)數(shù)據(jù)采用分桶統(tǒng)計(jì)，按照流行度（觀眾數(shù)量）將16000+直播間進(jìn)行間隔分桶，并對(duì)桶內(nèi)直播間瓶頸使用的節(jié)點(diǎn)數(shù)作為該流行度對(duì)應(yīng)的邊緣節(jié)點(diǎn)使用數(shù)量。統(tǒng)計(jì)結(jié)果如下圖所示：

對(duì)于不同直播間（圖1），當(dāng)直播間觀眾較少時(shí)，仍占有大量邊緣節(jié)點(diǎn)（ 直播間觀眾為100人時(shí)，仍占據(jù)50+邊緣節(jié)點(diǎn)），此時(shí)回源帶寬利用率極低。

對(duì)于同一直播間（圖2），各個(gè)邊緣節(jié)點(diǎn)負(fù)載分布差異巨大，有35個(gè)節(jié)點(diǎn)只服務(wù)了25-的觀眾。

故在觀眾地理分布廣、直播源頭數(shù)量多的情況下，LocalDNS就近原則會(huì)導(dǎo)致邊緣節(jié)點(diǎn)利用率低下。

本論文方法

為了解決上述問題，本文提出了AggCast: 一種基于冷熱流的邊緣節(jié)點(diǎn)帶寬資源優(yōu)化方法。 其決策邏輯主要分為直播間分類階段和調(diào)度階段，如下圖所示：

直播間分類

如圖1所示，當(dāng)觀眾人數(shù)少時(shí)，隨著直播間人數(shù)增加（<100人），邊緣節(jié)點(diǎn)數(shù)量迅速增加，而當(dāng)直播間流行度夠大（>2000人），邊緣節(jié)點(diǎn)數(shù)趨于穩(wěn)定。故需要找出流行度較低的冷流直播間，并對(duì)其進(jìn)行優(yōu)化，降低回源成本。

• 流行度預(yù)測(cè)：隱馬爾可夫模型

因?yàn)橹辈?chǎng)景中，絕大多數(shù)用戶傾向于在不同直播間切換，隱馬爾可夫模型作為一種基于狀態(tài)轉(zhuǎn)移的概率預(yù)測(cè)模型，可以通過捕捉隱狀態(tài)的變化進(jìn)行預(yù)測(cè)。

下面我們具體給出隱馬爾可夫模型的模型定義。我們用$X_t$來表示 $t$ 時(shí)刻某一直播間的用戶數(shù)量，用$S_t\in \mathcal{S}=\{S_0,S_1,...,S_{n?1}\}$ 來表示隱變量的狀態(tài)。則由隱馬爾可夫模型的定義，$S_t$ 為隨機(jī)變量，因此我們可以定義其概率分布為${\pi }_t=(P(S_t=S_0),...,P(S_t=S_{n?1}))$。隱馬爾可夫模型假設(shè)狀態(tài)遷移遵循馬爾可夫過程（Markov process），即當(dāng)前狀態(tài)的分布只和上一步狀態(tài)有關(guān)。從數(shù)學(xué)形式上，我們可以寫為：

其中$P=\{p_{i,j}\}$為轉(zhuǎn)移概率矩陣，$p_{i,j}=P(S_t=s_i|S_{t?1}=s_j)$表示狀態(tài)由上一時(shí)刻$s_j$切換至下一時(shí)刻$s_i$的概率。在轉(zhuǎn)移概率矩陣的基礎(chǔ)上，我們可以通過下式計(jì)算下一時(shí)刻各個(gè)狀態(tài)的概率：

最后，在已知隱狀態(tài)$S_t$的基礎(chǔ)上，下一時(shí)刻用戶數(shù)量$X_t$的概率分布（也被稱為發(fā)射概率）為：

即概率分布滿足高斯分布（我們?cè)趪L試了不同的概率分布后，高斯分布的效果最好）。與其他常用回歸模型的效果比較如下（其中衡量指標(biāo)采用歸一化絕對(duì)值誤差）：

• 冷熱流閾值計(jì)算

按百分比設(shè)定閾值門限 $threshol{d}_{\text{冷}\text{流}\text{門}\text{限}}$。 通過對(duì)觀眾數(shù)量對(duì)直播間排序，將觀眾數(shù)量排名末位的 $threshol{d}_{\text{冷}\text{流}\text{門}\text{限}}?\text{直}\text{播}\text{間}\text{總}\text{數(shù)}$ 個(gè)直播間，定義為冷流直播間，其余為熱流直播間。

服務(wù)質(zhì)量保證的用戶調(diào)度

在調(diào)度中，需要保證的服務(wù)質(zhì)量主要包括延遲（首屏?xí)r長）和卡頓（百秒卡頓時(shí)長、百秒卡頓頻率）。本文通過實(shí)驗(yàn)驗(yàn)證：地理位置的遠(yuǎn)近和網(wǎng)絡(luò)鏈路的遠(yuǎn)近并不等價(jià)，地理就近接入節(jié)點(diǎn)并非時(shí)延最優(yōu)節(jié)點(diǎn)?？D主要受限于邊緣節(jié)點(diǎn)的接入帶寬，當(dāng)邊緣節(jié)點(diǎn)不發(fā)生過載時(shí)，卡頓與是否跨區(qū)域接入無關(guān)。因此只要保證匯聚過程不過載，AggCast 的匯聚邏輯將不會(huì)影響到用戶質(zhì)量。

• 區(qū)域?qū)蛹?jí)CFLP問題

因?yàn)橹辈ラg數(shù)量遠(yuǎn)遠(yuǎn)大于邊緣區(qū)域數(shù)量，預(yù)測(cè)開銷極大，且實(shí)驗(yàn)表明，對(duì)于單個(gè)直播間，每個(gè)區(qū)域的觀眾隨時(shí)間變化劇烈。而將區(qū)域內(nèi)所有冷流直播間看作一個(gè)整體時(shí)，單個(gè)區(qū)域內(nèi)的所有冷流直播間的觀眾總數(shù)隨時(shí)間變化穩(wěn)定。故在邊緣區(qū)域?qū)?/span>而非直播間層面建立優(yōu)化問題。

將某個(gè)區(qū)域內(nèi)的所有冷流直播間用戶定義為這個(gè)區(qū)域內(nèi)的被匯聚用戶，AggCast對(duì)相同區(qū)域內(nèi)的被匯聚用戶采用相同的匯聚邏輯。

設(shè)邊緣節(jié)點(diǎn)的數(shù)量為$E$，邊緣區(qū)域的數(shù)量為$M$，區(qū)域$m\in M$中被匯聚的用戶數(shù)量為 $R_m$，邊緣節(jié)點(diǎn)$e$的最大接入帶寬為 $C_e$，將區(qū)域$m$的用戶接入到邊緣節(jié)點(diǎn)$e$的首屏?xí)r長記為 $d_{m,e}$。在任意時(shí)刻，AggCast的決策變量包括兩個(gè)：首先，AggCast需要決定哪些節(jié)點(diǎn)作為用戶匯聚使用的邊緣節(jié)點(diǎn)，為此我們使用一個(gè)0/1變量 $y_e$ 來表示是否使用邊緣節(jié)點(diǎn)$e$（若$y_e=1$則使用，否則不使用）；其次，在得到了目標(biāo)邊緣節(jié)點(diǎn)之后，AggCast還需要決定每個(gè)節(jié)點(diǎn)應(yīng)該服務(wù)區(qū)域$m$中的觀眾數(shù)量。為此，我們使用 $x_{m,e}$ 來表示區(qū)域 $m$ 中，被節(jié)點(diǎn) $e$ 服務(wù)的觀眾占比。綜上，該服務(wù)質(zhì)量保證的調(diào)度問題可以被定義為：

從數(shù)學(xué)形式上，該問題表示的優(yōu)化問題和資源受限下工廠選址問題（Capacitated Facility Location Problem，CFLP）等價(jià)（我們問題中的邊緣節(jié)點(diǎn)即對(duì)應(yīng)原問題中的工廠）。資源受限下工廠選址問題在運(yùn)籌學(xué)領(lǐng)域被廣泛研究，雖然該問題是NP-難問題，但很多算法均被證明可以取得非常好的效果，最常見的算法有模擬退火和拉格朗日松弛。綜合考慮實(shí)現(xiàn)難度和算法效果，我們最終選擇模擬退火求解。

• 實(shí)時(shí)求解

結(jié)合隱馬爾可夫模型以及各邊緣區(qū)域比例計(jì)算得用戶數(shù)量 $R_m$ ；通過邊緣服務(wù)器監(jiān)控帶寬上限 $C_e$ ； 通過區(qū)域 $m$中使用邊緣節(jié)點(diǎn) $e$ 的 用戶數(shù)據(jù)的均值近似 $d_{m,e}$ ，因此構(gòu)建出一個(gè)時(shí)延查找表，表中每個(gè)元素表示對(duì)應(yīng)區(qū)域和邊緣節(jié)點(diǎn)的鏈接延遲。 使用探索-利用（Exploration and Exploitation，E2）算法來更新時(shí)延查找表。即如果區(qū)域 $m$ 和邊緣節(jié)點(diǎn) $e$ 之間有用戶接入，則拿用戶延遲更新 $d_{m,e}$ ，否則用其他已測(cè)得的 $d_{m,e}$ 的均值近似。此方法雖開始時(shí)會(huì)略有誤差，但隨求解過程會(huì)逐漸探索到全部真實(shí)情況，且效率較高。

• 冷熱流邊界

對(duì)AggCast而言，考慮到預(yù)測(cè)模型的誤差以及直播間流行度變化的劇烈程度，某一些直播間可能會(huì)在冷熱流之間來回切換，且頻繁切換會(huì)使得AggCast的匯聚邏輯失效。故 AggCast 在冷流轉(zhuǎn)換為熱流之前，會(huì)根據(jù)流行度預(yù)測(cè)結(jié)果和冷熱流劃分的閾值，估算切換為熱流的帶寬收益大小，以決定是否切換。

• 減少問題規(guī)模

若全量求解，則求解時(shí)間超過三分鐘，不滿足實(shí)時(shí)性的要求。故通過KNN對(duì)邊緣節(jié)點(diǎn)的距離進(jìn)行聚類，對(duì)每類并行解決優(yōu)化問題，能有效的將單步?jīng)Q策的時(shí)間降低到2s-。

實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)室測(cè)試

采用華為云2020年6月真實(shí)數(shù)據(jù)，覆蓋18w+直播間，2000w+觀眾IP，觀眾來自300+地區(qū)，使用超過200+邊緣節(jié)點(diǎn)。華為云作為國內(nèi)最大的云服務(wù)廠商之一，為包括快手、抖音在內(nèi)的直播平臺(tái)提供服務(wù)，因此針對(duì)其數(shù)據(jù)集的測(cè)量結(jié)果具有代表性和普適性。

本實(shí)驗(yàn)對(duì)比就近接入（按IP地理位置就近接入）、Rildish（盡量將用戶調(diào)度到服務(wù)質(zhì)量最優(yōu)的邊緣節(jié)點(diǎn)）、最小成本最大流MCMF（將調(diào)度問題轉(zhuǎn)化為最大流），其回源成本與服務(wù)質(zhì)量對(duì)比如圖所示。

AggCast在回源成本的降低和服務(wù)質(zhì)量的保障上，整體表現(xiàn)最優(yōu)。

線上測(cè)試

AggCast在華為云上進(jìn)行了超過8個(gè)月的A/B測(cè)試，參與實(shí)驗(yàn)的直播間5w+個(gè)。如下圖所示，在整個(gè)測(cè)試階段，AggCast在80%的時(shí)間里都能獲得15%+的回源帶寬收益。