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

精选留言(36)

• 

  姜泮昌

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

  作者回复: 基本正确，详细可以参考微信公开的红包高并发架构设计

  2018-06-14

  

   37
• 

  肖一林

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

  作者回复: 嗯，要根据具体业务来分析

  2018-06-14

  

   32
• 

  孙振超

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

  作者回复: 分析点基本到位了，详细可以参考微信公开的技术文档

  2018-07-22

  

   14
• 

  Tom

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

  作者回复: 你以为是一个红包，实际上是几千上万个红包😂

  2018-06-15

  

   7
• 

  赵正 Allen

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

  作者回复: 分析到位，详细参考微信公开的技术文章，搜 微信红包高并发

  2018-06-14

  

   7
• 

  Leo Bright

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

  作者回复: 基本正确，详细可以参考微信公开的红包高并发架构设计

  2018-06-14

  

   4
• 

  sunlight001

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

  作者回复: 没有结合业务的特点分析，详细可以参考微信公开的红包高并发架构设计

  2018-06-14

  

   3
• 

  feifei

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

  作者回复: 红包分为发和抢，发的时候轮询就可以，抢的时候一般不是按照群id做hash，而是按照红包id做hash

  2018-06-14

  

   2
• 

  Michael

  老师好，这几天讲的负载均衡分类，算法，还有前面的reactor，proactor，这些东西我想再深细看一下，有没有什么相关的书籍可以推荐呢

  作者回复: 没有专门书籍，或者说我没有看过类似书籍，都是我逐步积累的，网络编程基础看《unix网络编程 卷1》

  2018-06-15

  

   1
• 

  大光头

  通过读你的这篇文章，我觉得到底采用哪种策略取决于业务，是否要求有session或者需要用户访问指定机器，如果是需要用hash，如果不是则考虑其它三种，轮巡和性能分配，采用哪种策略取决于性能轮巡算法的复杂度和用户体验，如果复杂度高，往往采用简单轮巡更加，用户体验对响应时间跟你敏感，也需要采用性能分配。
  微信抢红包，业务是有大量高并发请求，它不需要session，所以不用hash策论。由于用户体验是快速响应，所以应该采用性能响应时间策略

  作者回复: 你前面的理解挺好，但是对于hash的理解不全面，session可以用hash，强一致性也需要用hash，单元化也需要用hash

  2018-06-14

  

   1
• 

  黄国瑞

  随机负载以及相应的加权应该也算是一个不错的负载方式吧和轮询类似。
  
  另外TCP场景下还可以最小连接类似性能最优这种负载，然后再结合随机和加权在特定业务场景还挺好用。
  
  微信抢红包负载，个人感觉应该是一种轮询加权重加性能最优结合的吧。而且感觉里面应该还会设计hash负载，因为有可能设计数据不一致，这种高并发同步数据代价比较大，可以使用这种在里面减少这种操作。
  具体怎么搞没有细研究过。

  作者回复: 详细可以参考微信公开的红包高并发架构设计

  2018-06-14

  

   1
• 

  二戒

  抢红包时可以根据红包标识hash，将同一红包路由到一台机器以减少后端逻辑复杂度，分布式一致性等难度。不过考虑企业客户发的大红包，会不会瞬间击垮一台服务器需要斟酌。红包发到哪台机器可以采取其他均衡策略。

  作者回复: 回答正确，区分了发和抢的不同特点，详细可以参考微信公开的红包高并发架构设计

  2018-06-14

  

   1
• 

  妥协

  请教老师 最少连接数优先的算法中，负载均衡器和服务器之间不管是通过连接池，还是单个长链接方式，都可以统计当前请求数来统计，也就是发送请求加一，收到响应减一。以服务器为单位统计，为何说连接池不适合用这种算法。

  作者回复: 连接池架构中负载均衡是和服务器之间的连接数量一般是固定的

  2019-10-27

   1

  
• 

  godtrue

  1：分活策略
  1-1：平分——轮询
  1-2：我讨厌谁，就给谁多分——加权轮询
  1-3：想给就给谁——随机
  1-4：谁干的快给谁——负载均衡
  1-5：谁干的少给谁——性能最优
  1-6：前端给小云，后端给小强——哈希
  
  微信红包应该用什么分配策略？
  微信红包细分有如下环节：发、抢、拆、查、返，其中发、查、返相对容易处理，抢和拆是最难处理的，抢和拆也是关联起来的，抢的时候需要处理高并发，不能抢到拆不出红包，也不能把钱分多或分少啦！
  发的时候随机到那台机器生产红包的记录就行
  抢的时候需要排队抢先到先得，用哈希把抢的人都分到一个红包所在的机器上排队强
  拆的时候就是查看抢了多少钱也是用哈希
  查是在看一下自己抢了多少钱，随机一台机器查下就行
  返把没抢完的返回去随机一台就行吧
  

  作者回复: 抢和拆一起的吧，抢到后拆就简单一些

  2019-08-28

  

  
• 

  gkb111

  轮训，加速轮询，性能最低优先，负载最低优先，hash类

  2019-02-20

  

  
• 

  小狮子辛巴

  微信红包可能的方案有
  1、加权轮询 因为有不同配置的机器，不能简单的采用最普通的轮询
  2、负载最低优先， 对于微信红包业务应该用”CPU负载“来衡量服务器负载

  作者回复: 你的思路不太符合红包的场景，你看看其它评论

  2018-11-15

  

  
• 

  水月洞天

  红包逻辑是先发红包，再抢红包，最后拆红包。。关键点是红包的拆开金额不能超过当前红包金额。鉴于性能考虑，发红包时最好按照红包id负载红包库存。用户抢红包时根据红包id负载到不同的队列上，并处理拆红包业务。

  作者回复: 思路正确👍

  2018-09-27

  

  
• 

  Sky

  你好，请问：红包id做hash路由，负载均衡器要解析抢红包协议，来得到红包id，然后分派到不同的业务服吗？

  作者回复: 可以这样做，也可以将红包id放到url中

  2018-08-26

  

  
• 

  文竹

  采用ID hash的负载均衡算法。根据红包ID做Hash运算，这样同一个红包的请求被分到一个机器上做运算，处理比较方便。若对同一个红包的请求被分散在不同的机器上，需要使用分布式锁协助，处理起来较麻烦。

  作者回复: 需要按场景分析，参考其他人的答案

  2018-08-20

  

  
• 

  文竹

  使用红包ID进行hash负载均衡。

  作者回复: 分析太简单了，看看其它评论或者上网找资料

  2018-08-09

  

  