抢红包设计方案_万人抢红包如何设计

    这两天做了一个抢红包的功能，这里对实现方法进行一个整理，整天的两个难点：1、如何应对红包的高并发。其实红包类似于秒杀这种功能，当一个红包从可以开始抢到全部被抢完，很可能不到一秒钟，所以性能上肯定不能有问题。2、红包的公平性，如何做到红包的相对公平以及防止出现10块钱红包10个人抢，第一个人直接抢了9.8导致后面的人可能不够分的情况。所以这里从这两个问题来展开。

做到尽可能公平的抢红包

    因为这个主要是算法，比较单一，所以先从这个来。基本上分两个思路，一个是创建红包时，就把m金额的红包拆成n份存储起来，抢到时候直接根据当前的顺序获取对应槽位上的金额就好了。这种算法好处是一开始就确定了每一个人的金额，不会出现抢着抢着后面人不够抢的情况，坏处是创建红包时太慢，并且需要存储空间存储数据。
    另一种思路就是用户抢的时候再去计算抢到了多少钱，基于这种思路，只要做到兼顾公平性和避免不够抢的情况，就比第一种思路要好。做之前看了网上的很多资料，基本都是基于第二种边抢边出金额的方式，最多的一种设计是基于一个二分法，比如100个人，10个红包，那平均每人应该是10元，所以第一个人的随机区间则是1到20,平均能抢10元。假设第一个人真的抢了10元，剩下90元和9个人，平均每人还是十元，第二个人的随机区间也是1到20，以此类推，所有人的数学期望其实都是10元，从而做到公平性。但是可能存在极端情况比如：

• 第1个人的区间是1-20，结果运气超好抢了20元
• 第2个人均值是80/9=8（这里想下区取整，方便计算也防止超出最大金额），区间就是1-16元，抢了16元。
• 第3个人均值是64/8=8，区间1-16元，抢了16元。
• 第4个人均值是48/7=6，区间是1-12元，抢了12元。
• 第5个人均值是36/6=6，区间是1-12元，抢了12元。
• 第6个人均值是24/5=4，区间是1-8元，抢了8元。
• 第7个人均值是16/4=4，区间是1-8元，抢了8元。
• 第8个人均值是8/3=2，区间是1-4元，抢了4元。
• 第9个人均值是4/2=2，区间是1-4元，抢了4元。
• 这时候就出现最后一个人没钱了

    所以在这个二分随机算法的基础上进行改版，我给没人预留一块钱，然后对剩下的金额再进行二分随机获取，如下：

• 第1个人，给10个人每人留1元：100-10=90元，对剩下的钱均分90/10=9元，第1个人的区间是1-18元，如果这个人运气特别好抢了18元，加上一开始留的1元，则一共抢了19元。
• 第2个人，红包总共剩余81元，给9个人每人留1元，81-9=72元，均值为72/9=8元，区间为1-16元，抢了16元，加上预留1元，一共17元。
• 第3个人，红包总共剩余64元，给8个人每人留1元，64-8=56元，均值为56/8=7元，区间为1-14元，抢了14元，加上预留1元，一共15元。
• 第4个人，红包总共剩余49元，给7个人每人留1元，49-7=42元，均值为42/7=6元，区间为1-12元，抢了12元，加上预留1元，一共13元。
• 第5个人，红包总共剩余36元，给6个人每人留1元，36-6=30元，均值为30/6=5元，区间为1-10元，抢了10元，加上预留1元，一共11元。
• 第6个人，红包总共剩余25元，给5个人每人留1元，25-5=20元，均值为20/5=4元，区间为1-8元，抢了8元，加上预留1元，一共9元。
• 第7个人，红包总共剩余16元，给4个人每人留1元，16-4=12元，均值为12/4=3元，区间为1-6元，抢了6元，加上预留1元，一共7元。
• 第8个人，红包总共剩余9元，给3个人每人留1元，9-3=6元，均值为6/3=2元，区间为1-4元，抢了4元，加上预留1元，一共5元。
• 第9个人，红包总共剩余4元，给2个人每人留1元，4-2=2元，均值为2/2=1元，区间为1-2元，抢了2元，加上预留1元，一共3元。
• 第10个人，红包总共剩余1元，最后一个人获得1元。

这样就避免了最后的人抢不到的情况，同时从数学上也保证了公平性。

应对高并发

    前面说过抢红包类似于秒杀场景，需要一定的性能保证，并且同时得保证红包不会抢出问题，比如10个红包，因为并发没处理好造成抢出了20个红包，那就血亏了。基于这两个原因，传统的基于数据库对红包进行扣减，会造成较大的压力。并且如果我们基于数据库的悲观锁来实现时，有可能造成堵塞，而基于乐观锁实现，又容易造成大量的失败请求，影响用户体验。所以最终决定基于redis来进行实现，redis的lua脚本本身具备原子性，同一时间不会处理多笔抢红包事件，同时redis本身的高性能（秒级10w）的操作量也能很好的承接住这种秒杀场景。
    基本的算法和设计方案敲定，再来推敲细节，redis的高性能得益于小操作，也就是你不能把一个很耗时的操作放到redis里（比如一个大循环），那可能会造成极为严重的影响，甚至堵塞住你的所有和redis相关的业务。所以我们这里仅仅将红包的扣减操作放到redis当中，设计如下：

1. 用户发放红包时，会将红包的剩余个数和剩余金额（即总个数和总金额）写入redis中，并将本次发放红包的所有详情记录记录到数据库中，数据库操作在前，redis操作在后，对整个写数据的方法增加事务，保证数据的写一致性。
2. 用户抢红包时，在服务端生成[0,1]的浮点随机数，然后带入redis的lua脚本，在脚本中实现对前面的抢红包算法，根据当前剩余红包个数和剩余金额，计算出当前用户的红包区间，再将红包区间和我们带入的[0,1]的浮点随机数相乘并向下取整得到当前用户抢到的金额数，再对redis里的剩余个数和剩余金额进行修改。
3. 从lua脚本执行结果中获取到剩余数量，剩余金额，本次抢到的金额，然后发布mq，将本次抢红包的日志记录和金额修改的操作放到异步去进行，如果mq发送失败，需要手动回滚调redis，将剩余数量自增1，将本次抢到金额也要加回剩余金额。