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

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

1、引言

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

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

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

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

2、系列文章

• 《社交软件红包技术解密(一)：全面解密QQ红包技术方案——架构、技术实现等》
• 《社交软件红包技术解密(二)：解密微信摇一摇红包从0到1的技术演进》
• 《社交软件红包技术解密(三)：微信摇一摇红包雨背后的技术细节》
• 《社交软件红包技术解密(四)：微信红包系统是如何应对高并发的》
• 《社交软件红包技术解密(五)：微信红包系统是如何实现高可用性的》
• 《社交软件红包技术解密(六)：微信红包系统的存储层架构演进实践》
• 《社交软件红包技术解密(七)：支付宝红包的海量高并发技术实践》
• 《社交软件红包技术解密(八)：全面解密微博红包技术方案》
• 《社交软件红包技术解密(九)：谈谈手Q春节红包的设计、容灾、运维、架构等》
• 《社交软件红包技术解密(十)：手Q客户端针对2020年春节红包的技术实践》
• 《社交软件红包技术解密(十一)：最全解密微信红包随机算法(含演示代码)》
• 《社交软件红包技术解密(十二)：解密抖音春节红包背后的技术设计与实践》
• 《社交软件红包技术解密(十三)：微信团队首次揭秘微信红包算法，为何你抢到的是0.01元》（* 本文）
  

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;

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



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

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、更多鹅厂技术文章汇总

• 微信朋友圈千亿访问量背后的技术挑战和实践总结
• 腾讯技术分享：腾讯是如何大幅降低带宽和网络流量的(图片压缩篇)
• IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案
• 微信团队分享：iOS版微信的高性能通用key-value组件技术实践
• 微信团队分享：iOS版微信是如何防止特殊字符导致的炸群、APP崩溃的？
• 微信团队分享：微信Android版小视频编码填过的那些坑
• IM全文检索技术专题(一)：微信移动端的全文检索优化之路
• 企业微信客户端中组织架构数据的同步更新方案优化实战
• 微信新一代通信安全解决方案：基于TLS1.3的MMTLS详解
• 微信“红包照片”背后的技术难题
• 移动端IM实践：iOS版微信的多设备字体适配方案探讨
• 腾讯信鸽技术分享：百亿级实时消息推送的实战经验
• IPv6技术详解：基本概念、应用现状、技术实践（上篇）
• 腾讯技术分享：GIF动图技术详解及手机QQ动态表情压缩技术实践
• 微信团队分享：Kotlin渐被认可，Android版微信的技术尝鲜之旅
• 社交软件红包技术解密(一)：全面解密QQ红包技术方案——架构、技术实现等
• 社交软件红包技术解密(四)：微信红包系统是如何应对高并发的
• 社交软件红包技术解密(十)：手Q客户端针对2020年春节红包的技术实践
• 微信团队分享：极致优化，iOS版微信编译速度3倍提升的实践总结
• IM“扫一扫”功能很好做？看看微信“扫一扫识物”的完整技术实现
• 微信团队分享：微信支付代码重构带来的移动端软件架构上的思考
• IM开发宝典：史上最全，微信各种功能参数和逻辑规则资料汇总
• 微信团队分享：微信直播聊天室单房间1500万在线的消息架构演进之路
• 企业微信的IM架构设计揭秘：消息模型、万人群、已读回执、消息撤回等
• IM全文检索技术专题(四)：微信iOS端的最新全文检索技术优化实践
• 微信团队分享：微信后台在海量并发请求下是如何做到不崩溃的
• 微信Windows端IM消息数据库的优化实践：查询慢、体积大、文件损坏等
• 微信技术分享：揭秘微信后台安全特征数据仓库的架构设计
• IM跨平台技术学习(九)：全面解密新QQ桌面版的Electron内存优化实践
• 企业微信针对百万级组织架构的客户端性能优化实践
• 揭秘企业微信是如何支持超大规模IM组织架构的——技术解读四维关系链
• 微信团队分享：详解iOS版微信视频号直播中因帧率异常导致的功耗问题
• 微信团队分享：微信后端海量数据查询从1000ms降到100ms的技术实践
• 大型IM工程重构实践：企业微信Android端的重构之路
• IM技术干货：假如你来设计微信的群聊，你该怎么设计？
• 微信团队分享：来看看微信十年前的IM消息收发架构，你做到了吗
• 长连接网关技术专题(十一)：揭秘腾讯公网TGW网关系统的技术架构演进
• 总是被低估，从未被超越，揭秘QQ极致丝滑背后的硬核IM技术优化
• 首次公开，最新手机QQ客户端架构的技术演进实践
  

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

居然抢占了2楼！！！

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

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