【红包系统】设计核心
【红包系统】设计核心
学习核心
- 如何设计一个【红包】系统？（系统的核心功能）
- 沟通对齐
- ① 需求分析：发红包、抢红包
- ② 请求量分析：
- ③ 精准度分析：对标秒杀系统的少卖、超卖问题，红包不能少发也不能超发
- ④ 难点分析
- 高并发解决方案
- 红包分配算法
- 整体设计
- ① 服务设计（分层设计）：网关服务、业务层（红包服务）、存储层
- ② 存储设计（存储选型）：MySQL存储（数据表：红包表、记录表）
- ③ 业务设计（业务流程）：发红包（设置红包、发红包）、抢红包（抢红包、拆红包）
- 要点分析（或难点分析）
- ① 存储结构：基于MySQL存储数据结构
- ② 高并发解决方案：
- 缓存：在DB落盘之前先用缓存接收流量，然后将数据落盘，系统并发能力得到增强，但与此同时也带来了数据不一致问题
- 加锁：选用乐观锁进行加锁，可能会造成大量请求空转（比较版本，无效更新），并不能从根本上缓解数据库压力。且如果大量用户同时涌入，只有极少部分能成功，会造成用户体验感极差
- MQ（异步分治）：把海量的抢红包系统分成一个个的小型秒杀系统，采用了
set 分治、串行化队列、双维度分库分表等方案，提升单组 DB 的并发性能，以应对数亿级用户请求
- ③ 红包分配算法：从红包金额的随机性、可以接收的红包差额大小这两点进行切入
- 实时拆分：在抢红包时实时计算每个红包的金额，以实现红包的拆分过程
- 二倍均值：采用实时拆分的方式，用二倍均值法来生成随机红包，只满足随机即可，不需要正态分布（因此可能出现很大的红包差额）
- 预先生成：根据算法预先生成随机金额数组，抢红包的时候直接依次读取即可
- 实时拆分：在抢红包时实时计算每个红包的金额，以实现红包的拆分过程
- 总结陈述
学习资料
🟢【红包系统】场景核心
微信红包是一个随处可见的活动，其形式也相对简单（分为单个红包、多个红包），红包的核心功能主要是发红包、拆红包。单个红包是定向发送，不涉及概率事件，而对于多个红包来说则是一个用户塞一定的钱到红包中，分多个红包发送出来让多人进行抢拆，每个人可以抢到随机金额的红包，直到所有红包都被抢完
🚀【红包系统】场景实战
1.沟通对齐
此处的沟通对齐方向，主核心方向是需求分析、请求量分析、精准度分析、难点/要点分析，可能还有涉及到其他的一些容量、设计等方面的对齐
① 需求分析
红包系统核心功能
微信红包的实现跟抽奖系统有一定的区别，前面的抽奖每个用户相对独立，是一个独立性活动，每个人的抽奖跟其他人关联性不大，而红包的抽取过程是共享一个金额池，简单来说就是要将这个金额随机的分派到给前几个抢红包的人，有一定的关联性
- 参与人员：面向所有人员（无人员限制，所有可访问红包功能的用户均可参与）
- 中奖概率：每个人的中奖概率相同（中奖的金额则是随机）
- 奖品类型：对于红包系统，奖品类型单一（就是金额）
考虑到一些特殊活动期间肯定会有大量的用户来参与抢红包活动，因此对于抢红包这个接口来说需要考虑高并发支持
业务流程分析
红包系统最核心的业务流程就是用户发红包、抢红包（进一步细分还可分为：包红包、发红包、抢红包、拆红包）
结合系统特性分析，抢红包系统和秒杀系统类似，功能对比说明如下：
- ① 包红包（商品准备）：红包创建 =》设置红包金额、转账 =》生成红包订单
- ② 发红包（商品上架）：修改红包订单状态 =》记录发红包流水 =》红包消息通知
- ③ 抢红包（查、减库存）：查询红包库存 =》记录剩余库存
- ④ 拆红包（秒杀）：计算红包金额 =》记录拆红包流水 =》修改红包订单状态 =》转账
每次发红包都是一次商品秒杀流程，包括商品准备，商品上架，查库存、减库存，以及秒杀开始，最终的用户转账就是红包到账的过程
② 请求量分析
③ 精准度分析
④ 难点/要点分析
相比秒杀活动，微信发红包系统的用户量更大，设计更加复杂，需要重视的点更多，主要包括以下几点：
① 高并发：海量并发请求，秒杀只有一次活动，但红包可能同一时刻有几十万个秒杀活动（比如 2017 鸡年除夕，微信红包抢红包用户数高达 3.42 亿，收发峰值 76 万/秒，发红包 37.77 亿 个）
② 安全性要求：红包业务涉及资金交易，所以一定不能出现超卖、少卖的情况
- 超卖：发了 10 块钱，结果抢到了 11 块钱，多的钱只能系统补上，如此为爱发电应用估计早就下架了
- 少卖：发了 10 块钱，只抢了 9 块，多的钱得原封不动地退还用户，否则第二天就接到法院传单了
③ 严格事务：参与用户越多，并发 DB 请求越大，数据越容易出现事务问题，所以系统得做好事务一致性。这也是一般秒杀活动的难点所在，而且抢红包系统涉及金钱交易，所以事务级别要求更高，不能出现脏数据
2.整体设计（架构设计）
① 服务设计（分层设计）
② 存储设计（存储选型）
（1）数据库表设计
③ 业务设计（业务流程）
（1）基于内存的抢红包版本设计
抢红包【功能设计】
抢红包功能允许用户在群聊中发送任意个数和金额的红包，群成员可以抢到随机金额的红包，但要保证每个用户的红包金额不小于 0.01 元。让一定金额的钱随机的分配到这些红包中，总的来说还是一个概率事件问题，只不过此处是用概率来瓜分一个总数
以100元发送10个红包来讲述一下核心思路：
- （1）将100元随机分配到10个红包中（得到一个红包数组，长度n=10，索引为[0,9]）
- （2）抢红包的时候生成一个
[0,n-1]的随机数，在红包数组中弹出该红包，数组长度减1，完成一个拆红包动作 - （3）重复上述步骤，直到红包抢完即可
抢红包【概率设计】
类似于企业抽奖的设计实现，通过一个随机数完成，而对于金额的随机分配则更加复杂一些：
- （1）确保每个红包的钱数都是随机的
- （2）指定数量的红包恰好总金额分完（例如此处10个红包分100元）
- （3）红包金额差异性不能太大，即不能让大部分钱被一个红包分走（尽量保证每个红包分的钱数差异不大）
（2）基于数据库的抢红包版本设计
【发红包】交互步骤分析
① 用户设置红包的总金额和个数后，在红包表中增加一条数据，开始发红包；
② 为了保证实时性和抢红包的效率，在 Redis 中增加一条记录，存储红包 ID 和总人数 n
③ 抢红包消息推送给所有群成员
【抢红包】交互步骤分析
原始版本的抢红包是在一个接口中完成的（例如点击1次完成抢红包操作）。实际上从2015年起，微信红包的抢红包和拆红包已经分离了，用户点击抢红包之后需要进行两次操作（抢红包，拆红包），最常见的就是点击抢红包之后明明查看的时候还可以点击，但是实际点开后会发现红包已经被领取完毕，抢红包的完整交互步骤分析如下：
① 抢红包：抢操作在 Redis 缓存层完成，通过原子递减的操作来更新红包个数，个数递减为 0 后就说明抢光了
② 拆红包：拆红包时，首先会实时计算金额，一般是通过二倍均值法实现（即 0.01 到剩余平均值的 2 倍之间）
③ 红包记录：用户获取红包金额后，通过数据库的事务操作累加已经领取的个数和金额，并更新红包表和记录表
④ 转账：为了提升效率，最终的转账为异步操作，这也是为什么在春节期间，红包领取后不能立即在余额中看到的原因
上述的流程，在一般的秒杀活动中随处可见，但红包系统的复杂度并不仅限于此。此处还需进一步探讨用户量过大时高并发下的事务一致性怎么保证？数据分流如何处理？红包的数额分配如何处理？
3.要点分析
①基于内存的抢红包版本设计
接口设计
红包系统最核心的两个功能就是发红包和抢红包，因此此处最关键的接口也是这两个接口。为了便于观察红包信息，此处可以添加一个查询红包信息的接口
（1）发红包
接口名称：
setRedPackets请求地址：
/set_packet功能说明：发红包（将金额随机分配到各个红包中）
请求方式：post
请求参数：
{ "user_id": "用户ID", "money": "总金额", "num": "红包个数" }响应参数：返回抢红包相关的参数（抢红包的时候有对应关系，只有本次参与人在限定时间范围内才可以抢，例如不支持跨群抢红包，不支持抢逾期红包）
{ "code": 200, // 响应码 "msg": "get_packet?id=xxxx&user_id=1001&num=10"// 接口响应信息（包括本次发红包动作的ID、用于抢红包的参数） }
（2）领红包
接口名称：
getRedPacket请求地址：
/lottery功能说明：领红包
请求方式：get
请求参数：
{ "user_id": "用户ID", "packet_id": "发红包事件ID" }响应参数：
msg返回字符串类型（包括抢到的红包金额）{ "code": 200, // 响应码 "msg": "恭喜抢到一个红包金额为：300 "// 接口响应信息（包括获得的红包金额） }
（3）查询红包信息
- 接口名称：
getRedPacketsInfo - 请求地址：
get_packet_info - 功能说明：提供查询接口获取剩余红包信息（还剩多少个红包、金额）
- 请求方式：get
- 请求参数：无
- 响应参数：
msg返回字符串类型（包括剩余红包数、剩余金额）
并发控制
一个简易的红包系统的版本可以基于内存实现。由于红包系统也是基于内存实现，发完红包之后的信息是存在一个map中（packetList：Map<发红包ID,本次发出的红包中每个红包ID组成的切片>）。因为发红包和抢红包有并发可能性，所以这个map肯定是有并发问题的，需要采用机制进行并发安全处理（例如用并发安全的Map）
此外，在发红包的过程中，每发一个红包，这个切片应该相应减1，因此也要注意并发问题（此处可以用互斥锁进行优化）
② 基于数据库版本的抢红包版本设计
此处可以对比秒杀类系统设计，主要设计秒杀概念和money分发的问题，因此重点关注抢红包时的高并发解决方案和红包分配算法
（1）高并发解决方案
方案1：缓存（限流处理，但存在数据一致性问题）
和大多数秒杀系统设计相似，由于抢红包时并发很高，如果直接操作 DB 里的数据表，可能触发 DB 锁的逻辑，导致响应不及时
因此，可以在DB落盘之前加一层缓存，先限制住流量，再处理红包订单的数据更新。这样做的优点是用缓存操作替代了磁盘操作，提升了并发性能，这在一般的小型秒杀活动中非常有效！但是，随着微信使用发&抢红包的用户量增多，系统压力增大，各种连锁反应产生后，数据一致性的问题逐渐暴露出来：
- 少发问题：假设库存减少的内存操作成功，但是 DB 持久化失败了，会出现红包少发的问题；
- 超发问题：如果库存操作失败，DB 持久化成功，又可能会出现红包超发的问题
而且在几十万的并发下，直接对业务加锁也是不现实的，即便是乐观锁
方案2：加锁（❌不适合抢红包场景）
在关系型 DB 里，有两种并发控制方法：分为乐观锁（又叫乐观并发控制，Optimistic Concurrency Control，缩写 “OCC”）和悲观锁（又叫悲观并发，Pessimistic Concurrency Control，缩写“PCC”）
悲观锁在操作数据时比较悲观，认为别的事务可能会同时修改数据，所以每次操作数据时会先把数据锁住，直到操作完成
乐观锁正好相反，这种策略主打一个“信任”的思想，认为事务之间的数据竞争很小，所以在操作数据时不会加锁，直到所有操作都完成到提交时才去检查是否有事务更新（通常是通过版本号来判断），如果没有则提交，否则进行回滚。
在高并发场景下，由于数据操作的请求很多，所以乐观锁的吞吐量更大一些。但是从业务来看，可能会带来一些额外的问题：
- 抢红包时大量用户涌入，但只有一个可以成功，其它的都会失败并给用户报错，导致用户体验极差；
- 抢红包时，如果第一时间有很多用户涌入，都失败回滚了。过一段时间并发减小后，反而让手慢的用户抢到了红包；
- 大量无效的更新请求和事务回滚，可能给 DB 造成额外的压力，拖慢处理性能；
总的来说，乐观锁适用于数据竞争小，冲突较少的业务场景，而悲观锁也不适用于高并发场景的数据更新。因此对于抢红包系统来说，加锁是非常不适合的。
方案3：异步分治
综上所述，抢红包时不仅要解决高并发问题、还得保障并发的顺序性，所以考虑从队列的角度来设计。
每次包红包、发红包、抢红包时，也有先后依赖关系，因此可以将红包 ID 作为一个唯一 Key，将发一次红包看作一个单独的 set，各个 set 相互独立处理。
基于此就把海量的抢红包系统分成一个个的小型秒杀系统，在调度处理中，通过对红包 ID 哈希取模，将一个个请求打到多台服务器上解耦处理。且为了保证每个用户抢红包的先后顺序，把一个红包相关的操作串行起来，放到一个队列里面，依次消费。
从上述 set 分流可以看出，一台服务器可能会同时处理多个红包的操作，所以，为了保证消费者处理 DB 不被高并发打崩，还需要在消费队列时用缓存来限制并发消费数量。
抢红包业务消费时由于不存储数据，只是用缓存来控制并发。所以可以选用大数据量下性能更好的 Memcached
除此之外，在数据存储上，可以用红包 ID 进行哈希分表，用时间维度对 DB 进行冷热分离，以此来提升单 set 的处理性能。
综上所述，抢红包系统在解决高并发问题上采用了 set 分治、串行化队列、双维度分库分表 等方案，使得单组 DB 的并发性能得到了有效提升，在应对数亿级用户请求时取得了良好的效果
（2）红包分配算法
红包金额分配时，由于是随机分配，所以有两种实现方案：实时拆分和预先生成
算法1：实时拆分
实时拆分，指的是在抢红包时实时计算每个红包的金额，以实现红包的拆分过程。
这个对系统性能和拆分算法要求较高，例如拆分过程要一直保证后续待拆分红包的金额不能为空，不容易做到拆分的红包金额服从正态分布规律
二倍均值（实时拆分算法）
综合上述优缺点考虑，以及微信群聊中的人数不多（目前最高 500 人），所以采用实时拆分的方式，用二倍均值法来生成随机红包，只满足随机即可，不需要正态分布（因此可能出现很大的红包差额）
使用二倍均值法生成的随机数，每次随机金额会在 0.01 ~ 剩余平均值*2 之间。假设当前红包剩余金额为 10 元，剩余个数为 5，10/5 = 2，则当前用户可以抢到的红包金额为：0.01 ~ 4 元之间
用二倍均值法生成的随机红包虽然接近平均值，但是在实际场景下：微信红包金额的随机性和领取的顺序有关系，尤其是金额不高的情况下。
通过测验可得到一个结论：如果发出的 红包总额 = 红包数*0.01 + 0.01，比如：发了 4 个红包，总额为 0.05，则最后一个人领取的红包金额一定是 0.02
所以，红包金额算法大概率不是随机分配，而是在派发红包之前已经做了处理。比如在红包金额生成前，先生成一个不存在的红包，这个红包的总额为 0.01 * 红包总数。
而在红包金额分配的时候，会对每个红包的随机值基础上加上 0.01，以此来保证每个红包的最小值不为 0。
所以，假设用户发了总额为 0.04 的个数为 3 的红包时，需要先提取 3*0.01 到 "第四个" 不存在的红包里面，于是第一个人抢到的红包随机值是 0 ~ (0.04-3*0.01)/3。由于担心红包超额，所以除数的商是向下取二位小数，0 ~ (0.04-3*0.01)/3 ==> (0 ~ 0) = 0，再加上之前提取的保底值 0.01，于是前两个抢到的红包金额都是 0.01。最后一个红包的金额为红包余额，即 0.02。
算法2：预先生成
预先生成，指的是在红包开抢之前已经完成了红包的金额拆分，抢红包时只是依次取出拆分好的红包金额
这种方式对拆分算法要求较低，可以拆分出随机性很好的红包金额，但通常需要结合队列使用
4.总结陈述
深刻总结
- 从红包系统的核心功能切入（发红包、抢红包），对比秒杀活动的设计分析，此处将动作进行进一步拆分（发红包：设置红包、发红包；抢红包：抢红包、拆红包），并基于高并发解决方案和红包分配算法剖析红包系统的重点实现
要点牵引
- 数据表设计：红包表、记录表（可看做红包表的副表）
- 高并发解决方案：缓存机制、加锁、MQ（异步分治）
- 红包分配算法：实时拆分、预先生成、二倍均值
收尾请教