红包金额分配算法优化

前言

红包业务上线生产环境后，进行过很多次真实场景的测试，目前常规场景下功能基本没什么问题了。但还是存在需要优化的地方，比如上次聚餐时测试出的两个问题：

高并发情况下，打劫红包会出现打劫失败的情况。这是一个遗留问题，对高并发情况的处理比较复杂，并且这种情况发生概率较小，因此这个问题就没有处理
红包金额的分配差异有些大。

本篇记录一下对红包分配算法进行优化的过程。

目前使用的算法

微信的处理(2015年)，参考：社交软件红包技术解密(十一)：最全解密微信红包随机算法(含代码实现)

我们目前使用的红包分配算法，与上面微信提到的算法是一样的：分配的金额在 0.01 ~ 剩余总金额平均值 × 2 之间

发100块钱，总共10个红包，那么平均值是10块钱一个，那么发出来的红包的额度在0.01元～20元之间波动。当前面3个红包总共被领了40块钱时，剩下60块钱，总共7个红包，那么这7个红包的额度在：0.01～（60/72）=17.14之间。

这种算法有一个问题：如果前面的人领到的红包都很小，那么越往后用户可以分配到的金额范围就越大。

测试目前使用的算法

对目前采用的红包分配算法进行了测试，结合柱状图分析数据。测试 30 个人抢 500 元的红包，重复 10000 次，测试结果如下：

我选取了几次测试中几组金额差异较大的数据：

然后看一下执行 1000 次后，每个用户抢到的红包平均值（统计每个位置分配到的红包金额均值）

执行 1w 次的均值

执行 10w 次的均值

从均值来看，金额分配还是较为均等的；而从单次来看，偶尔会出现领到的金额差异较大的情况。

目前算法存在的缺陷

对这些出现金额差异巨大的数据进行了对比，发现他们都是 某几个金额很大，而其他的金额都是正常的；并且这个很大的金额经常出现最后几个红包中，准确的说基本都是出现在最后三个红包中。在这篇讨论中：微信红包的随机算法是怎样实现的？ - 知乎，有对这个现象详细的调查，如下：

上面的异常金额就是这样出现的：如果前面的人领到的红包都很小，那么越往后用户可以分配到的金额范围就越大。

算法优化

没有找到现成的更优化的红包分配算法，考虑按如下两种思路进行优化：

允许极值的出现。仍然使用现在的算法，由于极值经常出现在最后3个红包中，那么就在金额分配完毕后，再对已分配的金额进行一次随机打乱的操作。
避免极值的出现。方案1：限定分配的最大金额。最大金额按照一定的规则指定，如果分配的金额超过最大金额，那么就 整体重新生成 或者 部分重新生成。方案2：让每人分配到的金额更接近总金额的平均值。30 人抢 500 元红包，每人先分 5 元，剩下依次给每人分发随机金额，分发的随机金额固定范围，比如在 0.01 ~ 10 之间，直到分完。

目前采用的是第二种处理：避免极值的出现，限定分配的最大金额，超限后整体重新分配，并且在分配的金额返回前再进行一次随机排列操作，防止极值经常出现在固定位置，优化后的算法如下：

public static List<BigDecimal> randomDivideList(BigDecimal money, final int count) {
    return randomDivideList(money, count, 3);
}

/**
 * 随机拆分
 *
 * @param money
 * @param count
 * @param recurseCount 金额超限后，可以重新生成的次数
 * @return list
 */
public static List<BigDecimal> randomDivideList(BigDecimal money, final int count, int recurseCount) {
    if (count == 1) {
        return Collections.singletonList(money);
    }
    int leftCount = count;
    BigDecimal leftMoney = formatAmount(money);
    // 最大金额计算公式：(总金额 / 总人数) * 总人数的平方根(超过3.5按照3.5算)
    double seed = Math.min(Math.sqrt(leftCount), 3.5);
    BigDecimal maxMoney = leftMoney.multiply(new BigDecimal(String.valueOf(seed))).divide(new BigDecimal(leftCount), 2, RoundingMode.DOWN);
    List<BigDecimal> resultList = new LinkedList<>();
    BigDecimal allocateMoney;
    while (leftCount > 0) {
        allocateMoney = randomDivide(leftMoney, leftCount);
        // 最多递归3次
        if (allocateMoney.compareTo(maxMoney) > 0 && recurseCount > 0) {
            logger.error("分配的金额超出限额：{}，重新分配...", allocateMoney);
            return randomDivideList(money, count, recurseCount - 1);
        }
        leftMoney = leftMoney.subtract(allocateMoney);
        resultList.add(allocateMoney);
        leftCount--;
    }
    // 将分配后的金额随机排列，避免极值经常出现在最后几个红包中的情况
    Collections.shuffle(resultList);
    return resultList;
}