社交软件红包技术解密(十三)：微信团队首次揭秘微信红包算法，为何你抢到的是0.01元

JackJiang · 5 个月前

本文由腾讯梁中原分享，原题“红包算法揭秘！哪段代码让你只抢了0.01元？”，即时通讯网进行了排版和内容优化等。

1、引言

在上一篇《来看看微信十年前的IM消息收发架构，你做到了吗》的文章中，有用户提到想了解自己每次微信红包只能抽中 0.01 元的反向手气最佳是怎么在技术上实现的，于是就有了本篇文章的诞生。

其实，微信红包最初在产品设计上有过很多思路，最初曾以多档次、按比例分配的方式，但最后大家试用下来发现还是随机才好玩。那种看到有人抢到 100 块，有人 0.01 元的快乐无以言喻。

最初的随机算法中，领取越早获得大额红包几率越高，为了避免抢红包变成一个拼手速的游戏，后来的随机算法也对随机范围区间进行了一定调整。

本文中，我们将介绍几种主流的IM红包分配算法，相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。

社交软件红包技术解密(十三)：微信团队首次揭秘微信红包算法，为何你抢到的是0.01元_cover-opti.png

社交软件红包技术解密(十三)：微信团队首次揭秘微信红包算法，为何你抢到的是0.01元_cover-opti.png

2、系列文章

3、主流的红包算法1：普通随机法

普通随机法，简单来说其实就是剩余值随机。

普通随机：用余下的值为最大区间进行随机，但可能不均匀，有些人一把随到99，下面很多人都没得随机了。

以下是算法示例：

// 剩余值随机 ，优点：逻辑简单，缺点：随机区间步步减少，可以明显看出随机值的递减特性，
对后面玩家极不公平，且容易被抓到规律，造成舆论不满。
// 做抢红包体验很差，稍微弥补一点的方案：shuffle一下随机数组，让看起来不那么递减明显。
$res = LeftMoneyRedbag($Moneys, $userNums,  $isEveryHave);

//余值随机红包算法 ，一般都是使用剩余值在计算一把。
function LeftMoneyRedbag($Moneys, $userNums, $isEveryHave = 1, $baseMoney = 1)
{
    if ($Moneys <= 0 || $userNums <= 0) {
        return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
    }
    if ($isEveryHave && $userNums > $Moneys) {
        return ['code' => -4, 'msg' => '红包数量不足'];
    }

    //是否每个人都必有
    if ($isEveryHave) {
        $Moneys = $Moneys - ($userNums * $baseMoney);  //此时剩余money可能会无法随机到每一个人
    }

    $userMoney = [];
    //正式执行余值随机
    $leftMoneys = $Moneys; //可能 50分钱 分100人
    $leftUserNums = $userNums;
    while ($leftUserNums > 1) { // 考虑：就一个用户瓜分
        // echo "leftMoneys = " . $leftMoneys . " , leftUserNums = " . $leftUserNums . "<br>";
        $RandVal = 0;
        if ($leftMoneys > 0) { //考虑：剩余的钱不够分
            $RandVal = mt_rand(0, $leftMoneys);
            $leftMoneys = $leftMoneys - $RandVal;
        }
        $userMoney[] = $isEveryHave ? ($baseMoney + $RandVal) : $RandVal;
        $leftUserNums--;
    }

    //最后一位。考虑：剩余的钱太多或者就一个人
    $userMoney[] = $isEveryHave ? ($baseMoney + $leftMoneys) : $leftMoneys;

    echo "总数：" . count($userMoney) . "<br>";
    var_dump($userMoney);
    echo "总值：" . array_sum($userMoney) . "<br>";

    return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}

“mt_rand(1, 2); ”：mt_rand 包含区间前后边界的，即包含最大值和最小值，1和2都会出现。

4、主流的红包算法2：二倍均值算法

正常的算法，定好每个人的最小值，然后就是定下随机区间问题。

二倍均值：实际上就是，用剩下金额的两倍均值为最大区间进行随机，相对正态分布，区间相对合适。但人数越接近总额，分布越均匀。也可以三倍、四倍，倍数越高越随机，正态分布越扁平。

以下是算法示例：

$Moneys = 99 * 10; //单位为分
$userNums  = 990;
$isEveryHave = 0; //是否每个人都有

$res = doubleMeanRedbag($Moneys, $userNums);
// var_dump($res);

//二倍均值算法
function doubleMeanRedbag($Moneys, $userNums, $isEveryHave = 1, $baseMoney = 1)
{
    if ($Moneys <= 0 || $userNums <= 0) {
        return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
    }
    if ($isEveryHave && $userNums > $Moneys) {
        return ['code' => -4, 'msg' => '红包数量不足'];
    }

    //是否每个人都必有
    if ($isEveryHave) {
        $Moneys = $Moneys - ($userNums * $baseMoney);  //此时money可能会无法随机到每一个人
    }

    $userMoney = [];
    //正式执行二倍均值  
    $leftMoneys = $Moneys; //可能 50分钱 分100人
    $leftUserNums = $userNums;
    while ($leftUserNums > 1) { // 考虑：就一个用户瓜分
        // echo "leftMoneys = " . $leftMoneys . " , leftUserNums = " . $leftUserNums . "<br>";
        $RandVal = 0;
        if ($leftMoneys > 0) { //考虑：剩余的钱不够分
            $doubleMeans = ceil($leftMoneys / $leftUserNums * 2);
            $RandVal = mt_rand(0, $doubleMeans);
            $leftMoneys = $leftMoneys - $RandVal;
        }
        $userMoney[] = $isEveryHave ? ($baseMoney + $RandVal) : $RandVal;
        $leftUserNums--;
    }

    //最后一位。考虑：剩余的钱太多
    $userMoney[] = $isEveryHave ? ($baseMoney + $leftMoneys) : $leftMoneys;

    // echo "总数：" . count($userMoney) . "<br>";
    // var_dump($userMoney);
    // echo "总值：" . array_sum($userMoney) . "<br>";

    return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}

5、主流的红包算法3：线段分割算法

线段分割是相对合理的红包算法，但实现逻辑会更复杂一些。

红包金额如果想随机分成 N 份，可以处理为：一个线段，随机选择 N-1 点进行切割。

以下内容将详细讲解线段分割算法。

6、常规线段分割算法

以下是常规线段分割算法示例：

//线段分割算法  -- 有个致命缺陷，随机值碰撞，分割数量越接近总金额，碰撞概率越大 ，所以最好 userNum数量与总金额差的越大越好
function lineSegmentRedbag($Moneys, $userNums, $isEveryHave = 1, $baseMoney = 1)
{
     if ($Moneys <= 0 || $userNums <= 0) {
        return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
    }
    if ($isEveryHave && $userNums > $Moneys) {
        return ['code' => -4, 'msg' => '红包数量不足'];
    }

    $cutPoints = []; //切割点数组
    $pointNums = $userNums - 1; //存放的
    $userMoney = []; //每一个用户该分得的钱
    //正式线段分割，完全随机 
    // $j = 0;
    // 当 用户数 和 总金额差距不大时，这种写法效率极差
    while ($pointNums > 0) {
        if ($isEveryHave == 1) {
            $randVal = mt_rand(1, $Moneys - 1); //每个人都有，mt_rand包含区间边界的，即包含最大值 和 最小值 ，1和2都会出现
        } else {
            $randVal = mt_rand(0, $Moneys); //所有用户，全区间随机，保证了公平，所有人概率一致 0~10。如果$Moneys设置-1，导致最后一位必定不为0
        }

        if (in_array($randVal, $cutPoints)) {  //这边会产生随机碰撞，500个随机需要2500次左右才能覆盖。
            // $j++;
            continue;
        }
        $cutPoints[] = $randVal;
        $pointNums--;
    }

    // echo "无效循环次数：" . $j . "<br>";
    // echo "最终切割点数组数量：" . count($cutPoints) . "<br>";
    // var_dump($cutPoints);
    // return;

    //根据cutPoint计算每个人所得 同时考虑：就一个人
    $lastVal = 0;
    if (count($cutPoints) > 0) {
        sort($cutPoints);
        foreach ($cutPoints as $RandPoint) {
            $userMoney[] = $RandPoint - $lastVal;
            $lastVal = $RandPoint;
        }
    }

    $lastDiff = $Moneys - $lastVal;
    $userMoney[] =  $lastDiff;

    // echo "总数：" . count($userMoney) . "<br>";
    // echo "总值：" . array_sum($userMoney) . "<br>";
    return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}

7、使用array_rand优化后的线段分割算法

以下是array_rand优化后的线段分割算法示例：

//利用array_rand一次拿出多个随机值时，随机且去重,且随机区间包括首尾。
function lineSegmentOptimize($Moneys, $userNums, $isEveryHave = 1) //$baseMoney = 1默认为1
{
    if ($Moneys <= 0 || $userNums <= 0) {
        return ['code' => -3, 'msg' => '红包金额或拆红包总人数不合法'];
    }
    if ($isEveryHave && $userNums > $Moneys) {
        return ['code' => -4, 'msg' => '红包数量不足'];
    }

    $cutPoints = [];
    $userMoney = [];

    if ($isEveryHave) {
        $MoneysArr = array_fill(1, $Moneys - 1, 0); //转成数组时,去掉头尾得-1，如果10，则下标是1-9
    } else {
        $MoneysArr = array_fill(0, $Moneys + 1, 0); //转成数组,为了保留头尾得+1，如果10，则下标是0-10，array_rand区间包含首尾
    }

    if ($userNums == 1) {
        $userMoney[] = $Moneys;
        return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
    }

    $cutPoints = array_rand($MoneysArr, $userNums - 1); //多随机、且去重、且区间包含首尾，array_rand第二个值不可为0
    sort($cutPoints);
    $lastVal = 0;
    foreach ($cutPoints as  $randPoint) {
        $diff = $randPoint - $lastVal;
        $userMoney[] =  $diff;
        $lastVal = $randPoint;
    }
    $lastDiff = $Moneys - $lastVal;
    $userMoney[] =  $lastDiff;

    // echo "总数：" . count($userMoney) . "<br>";
    // var_dump($userMoney);
    // echo "总值：" . array_sum($userMoney) . "<br>";
    return ['code' => 0, 'msg' => "success", 'redbag' => $userMoney];
}

8、验证array_rand的随机特性

在写线段分割算法时，发现当全区间 mt_rand 后，出现重复切点需要去重，生成非重复的切点。

这里第一时间想到了使用 array_rand，但不确定 array_rand 的随机特性，不知道它的随机特性是否有去重处理。

经过验证：array_rand($arr, 8) 同时随机取多个索引下标时有去重处理，且随机特性很好。

事实证明：array_rand 一次拿出多个随机值时，随机且去重，且随机区间包括首尾。

代码示例如下：

$res = checkRand(10, 10000);
var_dump($res);
function checkRand($range, $num)
{
    $statiArr = array_fill(0, 100, 0);
    $sourceArr = range(0, 99);
    for ($i = 0; $i < 10000; $i++) {
        $indexArr = array_rand($sourceArr, 4); //array_rand随机性可以，且去重性也可以
        
        foreach ($indexArr as $index) {    //中途也用array_unique统计，是否单把拿值重复
            $statiArr[$index]++;
        }
    }
    return $statiArr;
}

一次随机取2个时，平均200左右：

array(100) { [0]=> int(196) [1]=> int(210) [2]=> int(206) [3]=> int(202)  ，，，，[97]=> int(196) [98]=> int(197) [99]=> int(188) }

一次随机取4个时，平均400左右：

array(100) { [0]=> int(372) [1]=> int(428) [2]=> int(394) [3]=> int(441) ,,,,, [97]=> int(382) [98]=> int(388) [99]=> int(358) }

一次随机取99个时，平均9900左右：

array(100) { [0]=> int(9892) [1]=> int(9890) [2]=> int(9913) [3]=> int(9909) ,,,,[97]=> int(9908) [98]=> int(9903) [99]=> int(9908) }

事实证明：array_rand一次拿出多个随机值时，随机且去重。

9、主流的红包算法的耗时和效果对比

最后，我们对全文提到的红包算法的随机性以及计算性价比进行一个整体比较。

以下是测试代码：

function microTime_float()
{
    //$usec 精确到微秒  ，$sec 秒   1秒(second) = 1000毫秒(millisecond) = 1000,000微秒(microsecond)
    list($usec, $sec) = explode(' ', microtime());
    return ((float)$usec + (float)$sec); //float保留小数点后四位
}

$starTime = microTime_float();  //0.35529400 1616661516

for ($i = 0; $i < 100000; $i++) {
    lineSegmentRedbag($Moneys, $userNums, $isEveryHave); 
    // lineSegmentOptimize($Moneys, $userNums, $isEveryHave);
    // doubleMeanRedbag($Moneys, $userNums, $isEveryHave);
}

$endTime = microTime_float();

$diff = floatval($endTime)  - floatval($starTime);

echo "线段分割时间差：" . floatval($diff) . "<br/>";   //时间差：0.33733010292053   //Optimize时间差：0.11269283294678
exit;

社交软件红包技术解密(十三)：微信团队首次揭秘微信红包算法，为何你抢到的是0.01元_1.png

如上图所示：线段分割算法与二倍均值相比，随机区间更大。

社交软件红包技术解密(十三)：微信团队首次揭秘微信红包算法，为何你抢到的是0.01元_2.png

如上图所示：线段分割普通版，随着红包总额与红包人数相近时（即切点接近总值时），随机碰撞率显著升高，性能下降。但经过优化后的线段分割算法，性能比二倍均值还优秀。

10、参考资料

[1] 微信红包随机算法初探
[2] 微信红包算法的分析
[3] 微信红包的架构设计简介
[4] 微信红包的随机算法是怎样实现的？
[5] IM开发宝典：史上最全，微信各种功能参数和逻辑规则资料汇总
[6] 微信本地数据库破解版(含iOS、Android)，仅供学习研究 [附件下载]
[7] 全面解密QQ红包技术方案——架构、技术实现等》
[8] 解密微信摇一摇红包从0到1的技术演进》
[9] 微信摇一摇红包雨背后的技术细节
[10] 微信红包系统是如何应对高并发的
[11] 微信红包系统是如何实现高可用性的
[12] 微信红包系统的存储层架构演进实践
[13] 支付宝红包的海量高并发技术实践
[14] 全面解密微博红包技术方案
[15] 谈谈手Q红包的功能逻辑、容灾、运维、架构等
[16] 手Q客户端针对2020年春节红包的技术实践
[17] 解密微信红包随机算法(含代码实现)
[18] 解密抖音春节红包背后的技术设计与实践

11、更多鹅厂技术文章汇总

2 楼: cqhigh · 5 个月前

还是没搞清楚为什么我抢的是0.01

3 楼: cqhigh · 5 个月前

居然抢占了2楼！！！

4 楼: JackJiang · 5 个月前

引用：cqhigh 发表于 2024-06-03 13:40
还是没搞清楚为什么我抢的是0.01

别纠结，搞不清楚就算了，代码直接用

本文目录

1、引言

2、系列文章

3、主流的红包算法1：普通随机法

4、主流的红包算法2：二倍均值算法

5、主流的红包算法3：线段分割算法

6、常规线段分割算法

7、使用array_rand优化后的线段分割算法

8、验证array_rand的随机特性

9、主流的红包算法的耗时和效果对比

10、参考资料

11、更多鹅厂技术文章汇总

MobileIMSDK (v6.5精编版)

MobileIMSDK-Web (有偿开源)

RainbowAVnew (有偿开源)

RainbowChat (技术转让)

RainbowChat-Web (技术转让)

精华之王

白金版主

终身成就

即时通讯网

友情链接[友链交换]

关于

微信公众号new

本文目录

1、引言

2、系列文章

3、主流的红包算法1：普通随机法

4、主流的红包算法2：二倍均值算法

5、主流的红包算法3：线段分割算法

6、常规线段分割算法

7、使用array_rand优化后的线段分割算法

8、验证array_rand的随机特性

9、主流的红包算法的耗时和效果对比

10、参考资料

11、更多鹅厂技术文章汇总

MobileIMSDK(v6.5精编版)

MobileIMSDK-Web(有偿开源)

RainbowAVnew(有偿开源)

RainbowChat(技术转让)

RainbowChat-Web(技术转让)

精华之王

白金版主

终身成就

即时通讯网

友情链接[友链交换]

关于

微信公众号new

MobileIMSDK (v6.5精编版)

MobileIMSDK-Web (有偿开源)

RainbowAVnew (有偿开源)

RainbowChat (技术转让)

RainbowChat-Web (技术转让)

即时通讯网　