李堅 王平 徐金波

摘要：一種隨機比例算法，可應(yīng)用于資源的負載均衡選擇。主要目的在于當(dāng)需要同類型資源選擇時，保持資源實體的按照預(yù)設(shè)的比例，讓資源隨機被選中。這種方法可應(yīng)用于短信服務(wù)的多接入商的主備服務(wù)商動態(tài)選擇場景，保持主流量落到主通道，輔助流量落到多個備用通道，規(guī)避依賴于某個SP第三方而產(chǎn)生的單點故障的問題發(fā)生。并且主備切換時只需改變其資源的占比參數(shù)就能動態(tài)的進行調(diào)整。

關(guān)鍵詞：正態(tài)分布 隨機比例 負載均衡 網(wǎng)絡(luò)環(huán)境

一、研究背景

設(shè)定有限資源（1～N個），在特定條件下應(yīng)用場景下實現(xiàn)，保持相對穩(wěn)定的比例同時按照隨機序列的方式對資源進行選擇，例如：A，B，C這3個資源，每次隨機的選擇一個資源，在進行例如1000次的選擇中，出現(xiàn)A，B，C三個資源總比例保持在預(yù)先設(shè)定的比例值中成正態(tài)分布。

二、應(yīng)用場景

其中一種應(yīng)用場景是，多服務(wù)商接入的短信服務(wù)平臺。為保證系統(tǒng)的健壯性排除單點故障風(fēng)險，會同時接入幾個（兩家以上）通道服務(wù)商。在發(fā)送短信時不固定用某一家通過隨機的方式進行選擇，但是因為存在短信通道服務(wù)商的價格與性能差異，需要區(qū)分主通道與備用通道，即主流量從主通道走，備用通道零散的分配一些流量。當(dāng)接收到業(yè)務(wù)的短信發(fā)送請求時，按照預(yù)先設(shè)定的比例隨機選擇使用哪個通道發(fā)送短信。

三、研究內(nèi)容

例如：有3個供應(yīng)商（后面簡稱SP），每次從中選擇一個SP提供服務(wù)，但是需要保持每次是進行隨機的選擇，但命中率要保持總量相對穩(wěn)定的比例;

如要保持這樣的比例：1號SP 5%，2號SP 25%，3號SP 70%，總量在1000次以上的分配中保持按照指定的比例均衡分布。

以上的應(yīng)用舉例是實際運行于生產(chǎn)環(huán)境的業(yè)務(wù)邏輯，短信服務(wù)中通道發(fā)送選擇時通道資源的使用占比控制，即要保持備用通道不能閑置，又要保證主流量從主通道走，還要保持每次選擇是隨機非線性的。

隨機比例選擇另一個關(guān)鍵點是要解決長時間連續(xù)選擇同一個資源的情況，規(guī)避在業(yè)務(wù)過程中，某個資源突然出現(xiàn)軟故障（即非直接阻斷業(yè)務(wù)報錯的故障，如某個環(huán)節(jié)少做了一些非決定向的非重要動作，較難第一時間發(fā)現(xiàn)）時，而此資源又被線性的持續(xù)被使用較長時間，以至持續(xù)被用戶感知出現(xiàn)大面積故障。

算法解法：

要同時解決按比例的產(chǎn)生隨機值，最終要達到這個結(jié)果，因此算法需要有個假設(shè)，即保持產(chǎn)生的隨機數(shù)數(shù)量需要保持一個基數(shù)之上（比如：1000次或上萬次），那么基數(shù)越大隨機數(shù)的分布態(tài)就能接近這個隨機比例值，數(shù)據(jù)量越小偏移越大，所以此算法不可用于產(chǎn)生隨機數(shù)量基數(shù)過小的情況。

以此為前提，可導(dǎo)出一個將其稱之為的丟球的算法，原理如下圖。

準(zhǔn)備一個一維數(shù)組槽位，按照需求比例在槽位中事先放入三個對象A，B，C。設(shè)選中對象的概率分別為：A是30%，B是10%，C是60%。

那么需要建立坑位數(shù)為10個的槽位，其中3洞放入A，1個洞放B，6個洞放C，總共10個坑位。

由隨機數(shù)發(fā)生器，產(chǎn)生0-9中的任意一個數(shù)N，把球丟到槽位洞中N中，取出命中的對象，并記錄這個對象名。

如此循環(huán)，不斷的產(chǎn)生隨機數(shù)往里面丟，經(jīng)過測試當(dāng)生成的隨機數(shù)總量超過槽位數(shù)10倍以上后，命中A，B，C這三個對象的占比會呈現(xiàn)出預(yù)先設(shè)定好的比例（A：30%，B：10%，C：60%）中的正態(tài)分布情況。

實際的線上生產(chǎn)環(huán)境的數(shù)據(jù)：

上表為生產(chǎn)環(huán)境中一周短信負載發(fā)送量的匯總信息，左三列為短信每日的發(fā)送量，右側(cè)三列是每個SP通道的比例分布，主通道是【SP：創(chuàng)*】另兩個是備用通道。經(jīng)過算法選擇器每日1.5萬次左右的選擇結(jié)果觀察，可以看出發(fā)送比例相對穩(wěn)定的控制在 25%，15%，60%。雖然會有微小的漂移，但是總體符合算法的預(yù)期結(jié)果。

以下為在實際用生產(chǎn)環(huán)境中的php語言實現(xiàn)代碼：

/** 隨機數(shù)百分比計算*/

class RandomProportion{

private $_aPool = []; //緩沖池

private $_iPoolLen = 0; //緩沖池大小

/**

* 初始化

* @param array $aParam

* <li>['key'=>'int 比例值'，...]</li>

* <li>example：['1'=>'55'，'2'=>'20'，'3'=>'15'，'4'=>'10']</li>

* @return void

*/

public function init（$aParam）{

$this->_aPool = [];

$this->_iPoolLen = 0;

if （！empty（$this->_aPool））{

unset（$this->_aPool）;

}

foreach （$aParam as $sKey => $iVal）{

$iVal = abs（intval（$iVal））;

if （$iVal > 0）{ //大于0才分配槽位

for （$i=0; $i<$iVal; $i++）{

$this->_aPool[] = $sKey;

}

}

}

$this->_iPoolLen = count（$this->_aPool）;

}

/**

* 擲骰子

* <li>必須先調(diào)用init（）初始化函數(shù)后，再用此函數(shù)返回一個選中的key</li>

*/

public function rollDice（）{

return $this->_aPool[rand（0，$this->_iPoolLen-1）];

}

}

//使用方式

$o = new RandomProportion（）;

$o->init（['1'=>'55'，'2'=>'20'，'3'=>'15'，'4'=>'10']）;

$o->rollDice（）; //調(diào)用次函數(shù)后可獲取一個隨機值為（1～4）的值

優(yōu)化方案：

根據(jù)上面的邏輯，在實際使用中生成一維數(shù)組的長度的條件為，待選擇的資源數(shù)量 * 比例值 * 基數(shù)長度。而三個值相乘的值必須為正整數(shù)（原因分配內(nèi)存槽位時必須是正整數(shù)）。

例如：A*34.5%*N，B*1.3%*N，C*58.7%*N，D*5.5%*N;那么此時N的取值需要=1000才能保證總槽位是正整數(shù)，然后分配內(nèi)存。

實際應(yīng)用中，這個重建過程需要消耗存儲資源。例如：php開發(fā)環(huán)境因其特性使得web服務(wù)php-fpm是工作在多進程而不是多線程，所以法共享內(nèi)存區(qū)塊，需要由進程在每次激活時都要重建一次這樣的區(qū)塊存儲槽位，當(dāng)高并發(fā)的時候?qū)⒉煌５纳蓛?nèi)存區(qū)間，填入實體編號，再選擇其中一個值，從而導(dǎo)致了資源與cpu的浪費。因此我們優(yōu)化其邏輯使得可以不必生成坑位數(shù)組存儲區(qū)間，只需按照對象生成一個小巧的二維數(shù)組（a[2～2+N][2]），例如：A（0）：25%，B（1）：15%，C（2）：60%，生成的二數(shù)組每個維度下標(biāo)只存儲兩個值0：0～24，1：25～39，2：40～99;數(shù)組結(jié)構(gòu)如下所示：

a[0][0]=0; a[0][1]=24;

a[1][0]=25; a[1][1]=39;

a[2][0]=40; a[2][1]=99;

接著通過隨機數(shù)發(fā)生器，生成0-99之間的一個隨機數(shù)，在數(shù)組中比較落入哪個區(qū)間內(nèi)，取命中的數(shù)組一維下標(biāo)，0-2對應(yīng)到A～C即可選中資源。

小結(jié)

本算法邏輯簡單可以用任何開發(fā)語言實現(xiàn)，無需依賴第三方資源，僅用數(shù)組加隨機數(shù)發(fā)生器就能實現(xiàn)需要的功能。實際的代碼已經(jīng)在線上生產(chǎn)環(huán)境運行了將近兩年，穩(wěn)定的解決了按比例隨機選擇資源的需求。

對于此算法的泛化應(yīng)用還可使用在優(yōu)惠券抽獎的環(huán)節(jié)。比如提前準(zhǔn)備了固定資源總量的獎勵，按照隨機比例的方式來抽取，這樣的好處是可盡量規(guī)避活動一開始就將一二等獎抽光的情況發(fā)生，導(dǎo)致后剩下的都是三等獎。

參考文獻

[1] 文天才，劉保延，何麗云，白文靜，閆世艷，李洪皎，呂曉穎，王鑫，張艷寧.最小化隨機算法形式化定義與優(yōu)化[J].中國數(shù)字醫(yī)學(xué)，2017：105-108.

[2] 尹貴祥，劉新茂.隨機選擇算法的研究[J].現(xiàn)代電子技術(shù)，2011：89-91.

[3] 劉克劍，劉心松，吳艾.一種多資源負載平衡算法———RLBA[J].計算機應(yīng)用，2005：42-43+46.

[4]韓世遷. （2011）. 概率論與數(shù)理統(tǒng)計. 化學(xué)工業(yè)出版社.

[5]蘭榮杰. （2016）. 從概率不確定性解讀復(fù)雜性. 系統(tǒng)科學(xué)學(xué)報，v.24;No.94（02），12-15+24.

[6] 瞿威.網(wǎng)絡(luò)服務(wù)的負載均衡探究[J].中國金融電腦，2009：57-59+63.

[7] 張永強.支持高負載的短信服務(wù)軟件性能研究[J].微計算機信息，2007：197+237-238.