21 | 高性能负载均衡：算法

微信抢红包架构应该至少包含两个负载均衡，一个是应用服务器的负载均衡，用于将任务请求分发到不同应用服务器，这里可以采用轮询或加速轮询的算法，因为这种速度快，适合抢红包的业务场景;另一起负载均衡是数据服务器的负载均衡，这里更适合根据红包ID进行hash负载均衡，将所有数据请求在同一台服务器上进行，防止多台服务器间的不同步问题。

看完了方乐明的对微信红包架构描述的技术文章，来回答一下问题： 有三个基本动作:发红包，抢红包，拆红包。发红包就是在数据库插一条红包库存数据，抢红包就是查询红包库存数据，拆红包就是插入一条秒杀流水并更新库存数据。 有三个难点:一是海量的并发，二是资金安全，三是良好的用户体验。资金安全决定了交易只能直接建立在数据库上，不能建立在缓存上。良好的用户体验就是要求不能出现不公平的现象，保证先抢先得，先抢的不能失败。 解决方案是: 1.分而治之，分成很多个并行的服务和数据库。相同的红包id总是分到相同的服务和数据库。所以负载均衡算法应该是hash算法 2.相同红包id的所有请求放在一个先进先出队列。然后分配一个独立的线程/进程处理。杜绝抢锁。 3.分离过期数据，减少单表数据量

负载均衡算法一共十来种之多，但经过抽取共性归纳之后就变成了4类，不仅容易记忆，即使以后再新增加其他的算法，也不外乎是进行了丰富，种类并没有什么变化，归纳为4类之后遇到类似的问题也可以用这样的方式去予以解决，从中也可以看到高手不只是机械性的记忆，而是带着思考去看待问题。 具体到微信红包的算法选择上，由于并发量特别高，需要有一个简单高效的算法，因而性能优先类算法可以不做考虑。对于微信这种级别的机房，其容器化技术必然是炉火纯青，每一台vm的配置是可以完全相同的，因而也就无需采用负载均衡类算法和权重轮询算法，剩下来的就是hash类算法和简单轮询算法。对于红包业务，最主要的操作是发红包和抢红包：不管是发个人红包还是发群红包整体业务相差不大，可以采用简单轮询算法，到任何一台服务器均可。但抢个人红包和抢群红包是不同的，抢群红包是有先后顺序，当有多个人抢同一个群红包时最好是由同一个服务器进行处理，这台服务器在收到抢红包的请求后将请求放到一个队列中，而后按照先进先出的方式进行消费，可以保证先到的人能抢到红包，后到的人后抢到红包。因而对于抢红包业务最好按照红包id进行hash负载。 如果是只选择一个负载算法的话，就是hash负载，发红包按照userid进行hash负载，抢红包按照红包id进行hash负载

看到评论说按红包id hash，上亿人抢同一个新年红包，应该只有一个红包id 吧？

发红包业务应该以红包的生命周期为思考的出发点。主要经历：发，抢，查询，回收（没抢完，返回给发红包的用户）。如果按这些细颗粒来看，抢，查询红包的并发要求最高，发红包次之，回收最低。 首先，发红包使用加权轮询，简单适用，成功后返回红包ID给客户端。 其次，抢红包，查询红包都带着ID给服务端，根据ID计算HASH，再利用一致性hash算法，找到最近的一个结点提供服务。 最后，回收应该由服务端定时触发，可以同样按抢红包处理。

一个红包对应多人去抢，服务器端要根据红包状态（是否抢完）来计算用户的结果（无法抢或抢了多少）。所以感觉最好是在同一台服务器上计算才能提高性能。那么红包和所有能够抢的用户之间应该有某个一致的关联信息（红包所在群的id），根据这个信息的负载算法负载到同一个服务器。所以我认为选hash算法合适，不知道想的对不对。

针对这个问题首先分析下抢红包的流程 1，首先一个用户在群组内发了一个红包，分成10份，并设置为随机大小。 2，假如群共有50人，都参与抢红包。 3，群里只能前10个用户可以抢到红包，并且金额随机 再来分析下业务流程 1，首先需要扣除发红包用户的红包金额。 2，按用户请求到达的先后顺序排队，进行抢红包，需要事务保证。 3，在队列中的用户抢到红包，其他用户没抢到红包。 然后再分析负载均衡的算法，主要针对抢红包的核心流程负载： 轮询，与加权轮训，都无法满足业务，此场景中存在事务，所以不合适 按机器负载，也无法满足，也是事务问题。 最后是hast，使用群id作为key进行分配，可以让同一个用户组的人负载到同一台机器，就可以完成事务。 所以我最终的负载均衡方案是选择hast算法。 我的分析是否合理？欢迎指正

有个问题想请教老师，进出的流量是不是都要通过负载均衡的那台机器。比如a是NGINX负载均衡服务器，bcd是具体的机器，http请求时是不是所有的input和output都经过负载均衡返回给客户端？

性能最优优先算法，抢发红包需要响应及时，该算法最优，但是复杂度比较好，需要不断调优。

微信抢红包，最好所有人都在红包所在server进行抢劫。适合ID hash这种算法