一不小心错过几个亿！解密微信红包算法

技术总结 评论

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

抢红包流程

红包生成，数据库中创建红包信息，把红包的ID、数量放入缓存
用户抢红包，分为抢和拆两个动作，抢动作只是决定用户是否得到红包资格，如果抢到了，进入拆动作，此时实时计算红包的金额、记录红包流水记录、入账操作
"d6wrmpwg1u"

算法满足要求

  • 每个人都要能够领取到红包；
  • 每个人领取到的红包金额总和=总金额；
  • 每个人领取到的红包金额不等，但也不能差的太离谱，不然就没趣味；
  • 算法一定要简单

微信红包算法

剩余红包金额为 M，剩余人数为 N，那么有如下公式：

每次抢到的金额 = 随机区间 （0.01， M / N X 2）

这个公式，保证了每次随机金额的平均值是相等的，不会因为抢红包的先后顺序而造成不公平。

举个栗子：

假设有 10个人，红包总额 100元。

100/10X2 = 20, 所以第一个人的随机范围是（0.01，20 )，平均可以抢到 10元。

假设第一个人随机到 10元，那么剩余金额是 100-10 = 90 元。

90/9X2 = 20, 所以第二个人的随机范围同样是（0.01，20 )，平均可以抢到 10元。

假设第二个人随机到 10元，那么剩余金额是 90-10 = 80 元。

80/8X2 = 20, 所以第三个人的随机范围同样是（0.01，20 )，平均可以抢到 10元。

以此类推，每一次随机范围的均值是相等的。

架构设计

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

微信的金额什么时候算？

金额是拆的时候实时算的，不是预先分配，采用纯内存计算，不需要计算空间存储。
采用实时计算的原因：预算需要占内存且效率低，实时效率高

红包的设计：

微信从财付通拉取金额数据，生成个数/红包类型/金额放到redis集群里，app端红包id的请求放入请求队列中，如果发现超过红包个数，直接返回。根据红包的处理成功得到令牌请求，由财付通进行一次性调用，通过像比特币一样，两边保存交易记录，交易后交给第三方服务审计，如果交易过程中出现不一致则强制回归。

并发处理：红包如何计算被抢完？

Cache会抵抗无效请求，将无效的请求过滤，实际进入后台的量不大。Cache记录红包个数，原子操作进行个数递减，到0表示被抢光。财付通按照20万笔每秒入账准备，但实际还不到8万每秒

财付通如何保持8万每秒写入？

多主sharding，水平拓展机器

数据容量多少？

一个红包占一条记录，有效期只有几天，因此不需要太多空间

查询红包分配，压力大不大？

抢到红包的人数和红包都在一条cache记录上，没有太大的查询压力

一个红包一个队列？

没有队列，一个红包一条记录，数据上有一个计数器字段

会不会出现两个最佳？

会出现金额一样的，但是最佳只有一个，先抢到的最佳。

每领一个红包就更新数据吗？

每抢到一个红包，cache更新剩余金额和红包个数

红包如何入库入账？

数据库会累加已经领取的个数与金额，插入一条领取记录。入账则是后台异步操作。

入账错了怎么办，比如红包个数没了，红包还有？

最后会有一个take all操作，另外还有一个对账来保障。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import random

# M: the all mouont the money, N: the num of person
M = 100
N = 10


remain_m = M
remain_n = N
packege = 0

for i in range(1, N):
    if remain_n == 0:
        print("no red envelope!")
    else:
        # [0.01, remain_m / remain_n * 2]
        max = remain_m / remain_n * 2
        package = random.random() * max
        if package < 0.01:
            package = 0.01
        remain_m -= package
        remain_n -= 1
        print("%.2f" % (package))

print("%.2f" % (remain_m))

运行20次每人平均抢到红包金额如下：
"png"

结论

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

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

参考链接：
https://cloud.tencent.com/developer/article/1575704
https://cloud.tencent.com/developer/article/1082036
https://www.zhihu.com/question/22625187

黄志远研发攻城狮

靡不有初 鲜克有终