一種隨機(jī)比算法的實(shí)現(xiàn)方法

李堅(jiān) 王平 徐金波

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

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

一、研究背景

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

二、應(yīng)用場景

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

三、研究內(nèi)容

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

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

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

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

算法解法：

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

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

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

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

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

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

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

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

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

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

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ù)返回一個(gè)選中的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ù)后可獲取一個(gè)隨機(jī)值為（1～4）的值

優(yōu)化方案：

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

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

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

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

小結(jié)

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

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

參考文獻(xiàn)

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

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

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

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

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

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

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