一不小心错过的几个亿还可以再回来！解密微信红包算法

前言

◆ ◆ ◆ ◆

还记得2017年，微信红包收发总量达到460亿个，2019年，除夕到初五，8.23亿人收发微信红包。一觉醒来，微信群里各种红包，顿时觉得错过了几个亿，破解了红包的规律，是不是就可以发财了呢？

红包算法主要思想

◆ ◆ ◆ ◆

我们抢红包关心的一般都是“手气最佳”，对于手气最佳，清华的毕啸天小哥哥做过一个统计，发了几亿次红包，得到如下图分析：

关于微信红包算法的重要发现是：

每个人当前抢到的微信红包金额大小服从均匀分布

[0.01，2*当前剩余红包均值两倍)

举个栗子：

在你打开红包的那一瞬间，

红包剩余m元

红包剩余个数为n个

那么你能抢到的金额为在

0.01和2*m/n之间

这个结论也在知乎大神陈鹏也提到过。

所以，如果以上结论是对的，那么结果就是！

1. 先抢后抢，期望大致相等
2. 对于第一个人来说，抽取红包大小服从均匀分布；对于之后的人来说，不服从均匀分布。
3. 越到后面，越有可能抽到一个很小的红包，也越有可能抽到一个很大的红包
4. 理论上来说，如果前面的运气都很差，最后一个人可以拿到接近总额的红包

结论就是：

1. 风险规避的人，应该尽可能往前抽取
2. 风险偏爱的人，应该尽可能往后抽取，而且越往后，增速标准差越大，极有可能抽到一个很大的红包；同理，小红包的概率也越大。

这个也是小明同学这几个月的痛……

小明有个微信群，老板每逢8,18,28发红包，手气最佳可得免单券，每次都提前预设闹钟，却一次都没有抢到，每次都是最后几个拿到最佳，如下图

经过抢的这几个月，以上结论也是可以验证的，最大的往往出现在后面，而且会比其他的大很多。

算法实现

◆ ◆ ◆ ◆

基于以上的结论，我们很容易就可以实现抢红包算法了，如下图：

以上代码仅仅供参考，实际过程不会那么简单，商用计算需要用BigDecimal。

如果想要代码或者进一步讨论的同学也可以加小明同学的微信:

miraclesComing

架构设计

◆ ◆ ◆ ◆

一个抢红包的功能当然不会那么简单，会涉及并发、缓存等等、这个也是面试的考题，下面补充几点关注点：

1. 微信的金额什么时候算？ 金额是拆的时候实时算的，不是预先分配，采用纯内存计算，不需要计算空间存储。 采用实时计算的原因：预算需要占内存且效率低，实时效率高
2. 红包的设计： 微信从财付通拉取金额数据，生成个数/红包类型/金额放到redis集群里，app端红包id的请求放入请求队列中，如果发现超过红包个数，直接返回。根据红包的处理成功得到令牌请求，由财付通进行一次性调用，通过像比特币一样，两边保存交易记录，交易后交给第三方服务审计，如果交易过程中出现不一致则强制回归。
3. 并发处理：红包如何计算被抢完？ Cache会抵抗无效请求，将无效的请求过滤，实际进入后台的量不大。Cache记录红包个数，原子操作进行个数递减，到0表示被抢光。财付通按照20万笔每秒入账准备，但实际还不到8万每秒
4. 财付通如何保持8万每秒写入？ 多主sharding，水平拓展机器
5. 数据容量多少？ 一个红包占一条记录，有效期只有几天，因此不需要太多空间
6. 查询红包分配，压力大不大？ 抢到红包的人数和红包都在一条cache记录上，没有太大的查询压力
7. 一个红包一个队列？ 没有队列，一个红包一条记录，数据上有一个计数器字段
8. 会不会出现两个最佳？ 会出现金额一样的，但是最佳只有一个，先抢到的最佳。
9. 每领一个红包就更新数据吗？ 每抢到一个红包，cache更新剩余金额和红包个数
10. 红包如何入库入账？ 数据库会累加已经领取的个数与金额，插入一条领取记录。入账则是后台异步操作。
11. 入账错了怎么办，比如红包个数没了，红包还有？ 最后会有一个take all操作，另外还有一个对账来保障。

以上架构内容参考知乎：

https://www.zhihu.com/question/22625187