一种随机比算法的实现方法
2021-11-18李坚王平徐金波
李坚 王平 徐金波
摘要：一种随机比例算法，可应用于资源的负载均衡选择。主要目的在于当需要同类型资源选择时，保持资源实体的按照预设的比例，让资源随机被选中。这种方法可应用于短信服务的多接入商的主备服务商动态选择场景，保持主流量落到主通道，辅助流量落到多个备用通道，规避依赖于某个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.
