一種隨機比算法的實現方法

李堅 王平 徐金波

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

關鍵詞：正態分布 隨機比例 負載均衡 網絡環境

一、研究背景

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

二、應用場景

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

三、研究內容

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

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

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

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

算法解法：

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

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

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

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

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

如此循環，不斷的產生隨機數往里面丟，經過測試當生成的隨機數總量超過槽位數10倍以上后，命中A，B，C這三個對象的占比會呈現出預先設定好的比例（A：30%，B：10%，C：60%）中的正態分布情況。

實際的線上生產環境的數據：

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

以下為在實際用生產環境中的php語言實現代碼：

/** 隨機數百分比計算*/

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>必須先調用init（）初始化函數后，再用此函數返回一個選中的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（）; //調用次函數后可獲取一個隨機值為（1～4）的值

優化方案：

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

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

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

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

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

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

接著通過隨機數發生器，生成0-99之間的一個隨機數，在數組中比較落入哪個區間內，取命中的數組一維下標，0-2對應到A～C即可選中資源。

小結

本算法邏輯簡單可以用任何開發語言實現，無需依賴第三方資源，僅用數組加隨機數發生器就能實現需要的功能。實際的代碼已經在線上生產環境運行了將近兩年，穩定的解決了按比例隨機選擇資源的需求。

對于此算法的泛化應用還可使用在優惠券抽獎的環節。比如提前準備了固定資源總量的獎勵，按照隨機比例的方式來抽取，這樣的好處是可盡量規避活動一開始就將一二等獎抽光的情況發生，導致后剩下的都是三等獎。

參考文獻

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

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

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

[4]韓世遷. （2011）. 概率論與數理統計. 化學工業出版社.

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

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

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