抢红包算法的实现与思考

微信抢红包成了逢年过节必不可少的一个环节,每次抢红包都要人品大爆发才能抢到大红包。站在程序员的角度上,该如何设计抢红包的算法呢?并考虑到实际应用场景,微信是如何设计上亿用户的抢红包系统,高并发下对抢红包算法会带来一些挑战,如何去应对这种挑战?本文设计了一个类似微信的红包算法,并做了简单的性能分析以及考虑到实际部署时需要考虑的情况。

基本要求

  • 所有抢到红包的金额等于红包金额;
  • 每个人至少抢到0.01元;
  • 保证所有人抢到金额的几率相等;

一个简单的抢红包算法

M为剩余红包的金额,剩余人数为N,每个人抢的红包的金额为:

每次抢到的金额 = 随机区间(0, M / N * 2)

这样能够满足上述的要求:

1
2
3
4
5
6
7
8
9
10
11
12
import random
def redenvelope(money, n):
redmoney = []
while n != 1:
get_money = round(random.random() * 2 * money / n, 2)
redmoney.append(get_money)
money -= get_money
n -= 1
redmoney.append(round(money, 2))
return redmoney

简单测试QPS能够达到8w,但是这种算法能够抢到的最大红包数只能是平均值的2倍,微信使用的肯定不是这种算法。


裂变方法

从红包金额中随机n-1个随机数,然后对红包进行切割,这种方法最接近接近微信的实现,比较完整的实现如下:

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
26
27
import random
def money_val(min, max):
return min if min > max else random.randint(min, max)
def redenvelope(money, n, min = 0.01):
"""
:param money: 红包金额
:param n: 抢红包的人数
:param min: 抢到红包的最小金额
:return: 每个人抢到红包的金额
"""
money_list = []
if money < n * min:
return money_list, u'Invalid Value'
for i in range(1, n):
safe_total = (money - (n - i) * min) / (n - i)
get_money = round(money_val(min * 100, int(safe_total) * 100) / 100, 2)
money -= get_money
money_list.append(get_money)
money_list.append(round(money, 2))
random.shuffle(money_list)
return money_list, u'success'

测试发现裂变式的QPS只有1.2w,相对第一个方法,这种方法更加贴合微信中拆红包的实现。


进一步的思考

裂变方法实现的抢红包算法应用于小型系统中没有问题,但是对于微信这种百亿红包,峰值达到百万级别的系统来讲,上述算法还不能够很好的满足这样的需求。有没有更好的解决办法?可以通过预分配的思想去解决,通过事先大量随机一些值存到内存中,这样把红包的生成算法转换为查询操作,可以提高并发。