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

2018-06-14 李运华

《从 0 开始学架构》

课程介绍



讲述：黄洲君

时长:大小4.15M



负载均衡算法数量较多，而且可以根据一些业务特性进行定制开发，抛开细节上的差异，根据算法期望达到的目的，大体上可以分为下面几类。
任务平分类：负载均衡系统将收到的任务平均分配给服务器进行处理，这里的“平均”可以是绝对数量的平均，也可以是比例或者权重上的平均。
负载均衡类：负载均衡系统根据服务器的负载来进行分配，这里的负载并不一定是通常意义上我们说的“CPU 负载”，而是系统当前的压力，可以用 CPU 负载来衡量，也可以用连接数、I/O 使用率、网卡吞吐量等来衡量系统的压力。
性能最优类：负载均衡系统根据服务器的响应时间来进行任务分配，优先将新任务分配给响应最快的服务器。
Hash 类：负载均衡系统根据任务中的某些关键信息进行 Hash 运算，将相同 Hash 值的请求分配到同一台服务器上。常见的有源地址 Hash、目标地址 Hash、session id hash、用户 ID Hash 等。
接下来我介绍一下



展开全文

精选留言

姜泮昌
2018-06-14
微信抢红包架构应该至少包含两个负载均衡，一个是应用服务器的负载均衡，用于将任务请求分发到不同应用服务器，这里可以采用轮询或加速轮询的算法，因为这种速度快，适合抢红包的业务场景;另一起负载均衡是数据服务器的负载均衡，这里更适合根据红包ID进行hash负载均衡，将所有数据请求在同一台服务器上进行，防止多台服务器间的不同步问题。
作者回复: 基本正确，详细可以参考微信公开的红包高并发架构设计
84
肖一林
2018-06-14
看完了方乐明的对微信红包架构描述的技术文章，来回答一下问题：

有三个基本动作:发红包，抢红包，拆红包。发红包就是在数据库插一条红包库存数据，抢红包就是查询红包库存数据，拆红包就是插入一条秒杀流水并更新库存数据。

有三个难点:一是海量的并发，二是资金安全，三是良好的用户体验。资金安全决定了交易只能直接建立在数据库上，不能建立在缓存上。良好的用户体验就是要求不能出现不公平的现象，保证先抢先得，先抢的不能失败。

解决方案是:
1.分而治之，分成很多个并行的服务和数据库。相同的红包id总是分到相同的服务和数据库。所以负载均衡算法应该是hash算法
2.相同红包id的所有请求放在一个先进先出队列。然后分配一个独立的线程/进程处理。杜绝抢锁。
3.分离过期数据，减少单表数据量

展开
作者回复: 嗯，要根据具体业务来分析
共 3 条评论
76
孙振超
2018-07-22
负载均衡算法一共十来种之多，但经过抽取共性归纳之后就变成了4类，不仅容易记忆，即使以后再新增加其他的算法，也不外乎是进行了丰富，种类并没有什么变化，归纳为4类之后遇到类似的问题也可以用这样的方式去予以解决，从中也可以看到高手不只是机械性的记忆，而是带着思考去看待问题。

具体到微信红包的算法选择上，由于并发量特别高，需要有一个简单高效的算法，因而性能优先类算法可以不做考虑。对于微信这种级别的机房，其容器化技术必然是炉火纯青，每一台vm的配置是可以完全相同的，因而也就无需采用负载均衡类算法和权重轮询算法，剩下来的就是hash类算法和简单轮询算法。对于红包业务，最主要的操作是发红包和抢红包：不管是发个人红包还是发群红包整体业务相差不大，可以采用简单轮询算法，到任何一台服务器均可。但抢个人红包和抢群红包是不同的，抢群红包是有先后顺序，当有多个人抢同一个群红包时最好是由同一个服务器进行处理，这台服务器在收到抢红包的请求后将请求放到一个队列中，而后按照先进先出的方式进行消费，可以保证先到的人能抢到红包，后到的人后抢到红包。因而对于抢红包业务最好按照红包id进行hash负载。
如果是只选择一个负载算法的话，就是hash负载，发红包按照userid进行hash负载，抢红包按照红包id进行hash负载
展开
作者回复: 分析点基本到位了，详细可以参考微信公开的技术文档
共 2 条评论
37
Tom
2018-06-15
看到评论说按红包id hash，上亿人抢同一个新年红包，应该只有一个红包id 吧？
作者回复: 你以为是一个红包，实际上是几千上万个红包😂
共 8 条评论
17
赵正 Allen
2018-06-14
发红包业务应该以红包的生命周期为思考的出发点。主要经历：发，抢，查询，回收（没抢完，返回给发红包的用户）。如果按这些细颗粒来看，抢，查询红包的并发要求最高，发红包次之，回收最低。
首先，发红包使用加权轮询，简单适用，成功后返回红包ID给客户端。
其次，抢红包，查询红包都带着ID给服务端，根据ID计算HASH，再利用一致性hash算法，找到最近的一个结点提供服务。
最后，回收应该由服务端定时触发，可以同样按抢红包处理。
作者回复: 分析到位，详细参考微信公开的技术文章，搜微信红包高并发
共 2 条评论
13
CDz
2020-03-26
* 根据负载均衡达到的目的可分四类
    * 任务平分类：负载均衡系统收到任务平均分配给服务器进行处理，可以是绝对的平均，也可以是按比例的“加权”平均
    * 负载均衡类：突出负载的均衡，根据当前系统压力
        * CPU负载
        * IO负载
        * 网卡吞吐量
    * 性能最优类：根据服务器响应时间来任务分配
    * Hash类：根据某些关键信息进行Hash运算，同一个放在同一服务器上处理
        * 源地址hash
        * 目标地址hash
        * session ID hash
        * 用户ID hash
* 轮询
    * 优点简单
    * 缺点不关心服务器状态
        * 如果有一个服务器死循环CPU过高，还是会发送任务
* 加权轮询
    * 根据不通服务器的配置差异，不同的权重设置
* 负载最低优先
    * 不同任务类型、不同业务场景、选择不同指标
        * LVS是4层负载，以连接数来判断服务器状态
        * Nginx是7层负载，以HTTP请求数来判断服务器状态
    * 自己开发，还需要注意，考虑选择的指标
        * IO密集型
        * CPU密集型
    * 复杂性问题：
        * 连接数优先算法
            * 要求：每个请求都会发送给服务器进行处理
            * 不适合：固定连接池方式
        * CPU负载
            * 收集信息的方式
                * 收集时间长度
                    * 1分钟长度与15分钟长度效果不同，并不一定15分钟就好
                * 收集动作消耗性能
        * 代码复杂度
            * 轮询可能10行代码
            * 负载可能1000行
                * 并且需要多方面调试
* 性能最优类
    * 站在客户端进行分配任务
    * 谁的性能此时最好，分配给谁
    * 高复杂度
        * 收集分析过程中，本身收集就会消耗性能
        * 为了减少性能消耗
            * 设置合适的采样率
                * 越大性能消耗越大
            * 合适的周期
                * 多久采样一次
* Hash类
    * 源地址Hash
        * 适合存在事务、会话业务
        * 网上银行：生成临时会话信息
    * ID Hash
        * 根据某个ID的业务分配服务器处理
        * session ID也可以解决网上银行的例子
展开
7
Leo Bright
2018-06-14
一个红包对应多人去抢，服务器端要根据红包状态（是否抢完）来计算用户的结果（无法抢或抢了多少）。所以感觉最好是在同一台服务器上计算才能提高性能。那么红包和所有能够抢的用户之间应该有某个一致的关联信息（红包所在群的id），根据这个信息的负载算法负载到同一个服务器。所以我认为选hash算法合适，不知道想的对不对。
作者回复: 基本正确，详细可以参考微信公开的红包高并发架构设计
7
feifei
2018-06-14
针对这个问题首先分析下抢红包的流程
1，首先一个用户在群组内发了一个红包，分成10份，并设置为随机大小。
2，假如群共有50人，都参与抢红包。
3，群里只能前10个用户可以抢到红包，并且金额随机
再来分析下业务流程
1，首先需要扣除发红包用户的红包金额。
2，按用户请求到达的先后顺序排队，进行抢红包，需要事务保证。
3，在队列中的用户抢到红包，其他用户没抢到红包。

然后再分析负载均衡的算法，主要针对抢红包的核心流程负载：
轮询，与加权轮训，都无法满足业务，此场景中存在事务，所以不合适
按机器负载，也无法满足，也是事务问题。
最后是hast，使用群id作为key进行分配，可以让同一个用户组的人负载到同一台机器，就可以完成事务。

所以我最终的负载均衡方案是选择hast算法。

我的分析是否合理？欢迎指正

展开
作者回复: 红包分为发和抢，发的时候轮询就可以，抢的时候一般不是按照群id做hash，而是按照红包id做hash
4
sunlight001
2018-06-14
性能最优优先算法，抢发红包需要响应及时，该算法最优，但是复杂度比较好，需要不断调优。
作者回复: 没有结合业务的特点分析，详细可以参考微信公开的红包高并发架构设计
3
summer
2018-06-28
微信抢红包，最好所有人都在红包所在server进行抢劫。适合ID hash这种算法
作者回复: 抢红包，别抢劫😂
2
9527
2018-06-15
老师好，这几天讲的负载均衡分类，算法，还有前面的reactor，proactor，这些东西我想再深细看一下，有没有什么相关的书籍可以推荐呢
作者回复: 没有专门书籍，或者说我没有看过类似书籍，都是我逐步积累的，网络编程基础看《unix网络编程卷1》
2
while (1)等;
2021-08-05
有个问题想请教老师，进出的流量是不是都要通过负载均衡的那台机器。比如a是NGINX负载均衡服务器，bcd是具体的机器，http请求时是不是所有的input和output都经过负载均衡返回给客户端？
作者回复: nginx的反向代理是这样的，但是LVS做负载均衡的时候，返回的流量可以不经过LVS，具体你可以查查LVS的TUN和DR模式
1
民工597
2020-12-10
简单来讲，就三个字，接化发
作者回复: 年轻人武德不错：）
共 2 条评论
1
慎独明强
2020-08-03
负载均衡在面试中经常被问到，任务分配，负载分配，性能分配，hash。任务分配有轮询，加权轮询，随机。负载分配有最小连接，还有看cpu计算密集还是io密集等指标来负载分配。性能分配主要看响应时间，hash主要是将同一类业务分配到同一台服务器
1
小喵喵
2018-06-17
什么hash算法，轮循加权完全看不懂啊，是不是数据结构的知识，数据结构和算法全部还给老师了。
作者回复: hash都不懂哇，赶紧去学😭
1
大光头
2018-06-14
通过读你的这篇文章，我觉得到底采用哪种策略取决于业务，是否要求有session或者需要用户访问指定机器，如果是需要用hash，如果不是则考虑其它三种，轮巡和性能分配，采用哪种策略取决于性能轮巡算法的复杂度和用户体验，如果复杂度高，往往采用简单轮巡更加，用户体验对响应时间跟你敏感，也需要采用性能分配。
微信抢红包，业务是有大量高并发请求，它不需要session，所以不用hash策论。由于用户体验是快速响应，所以应该采用性能响应时间策略
作者回复: 你前面的理解挺好，但是对于hash的理解不全面，session可以用hash，强一致性也需要用hash，单元化也需要用hash
1
黄国瑞
2018-06-14
随机负载以及相应的加权应该也算是一个不错的负载方式吧和轮询类似。

另外TCP场景下还可以最小连接类似性能最优这种负载，然后再结合随机和加权在特定业务场景还挺好用。

微信抢红包负载，个人感觉应该是一种轮询加权重加性能最优结合的吧。而且感觉里面应该还会设计hash负载，因为有可能设计数据不一致，这种高并发同步数据代价比较大，可以使用这种在里面减少这种操作。
具体怎么搞没有细研究过。
展开
作者回复: 详细可以参考微信公开的红包高并发架构设计
1
二戒
2018-06-14
抢红包时可以根据红包标识hash，将同一红包路由到一台机器以减少后端逻辑复杂度，分布式一致性等难度。不过考虑企业客户发的大红包，会不会瞬间击垮一台服务器需要斟酌。红包发到哪台机器可以采取其他均衡策略。
作者回复: 回答正确，区分了发和抢的不同特点，详细可以参考微信公开的红包高并发架构设计
1
rs勿忘初心
2021-08-29
方乐明【微信红包后台系统可用性设计实践】https://www.sohu.com/a/150354603_355140，供参考
Master
2021-05-23
我觉得可以通过日常生活实际体验来想，公司群大老板过年过节发了个包，员工们抢，有时候会发现，怎么明明我抢到了点开反而提示我红包已经抢完。所以我觉得首先微信红包的过程，发包，分包，拆包，发和分都是事先就根据一定的算法就直接完成了，等于一个红包任务建立，分成了n个待拆任务，那么大家开始抢了，考虑抢红包必须要考虑数据高可用，以及体验性，所以最终抢的结果必须数据一致，并且先来后到，不多发不少发不冲突，50个包就是50个，综上所以我觉得抢的动作是按照hash轮训，保证一个包的任务，都在一台机器上执行完成，包括抢互斥（50个，51个人抢到，开头说的问题，也无妨吧现在看来），拆包（实际拆包算金额，这就考虑到“库存”）统一在一台服务器执行完成比较简单直接。而且结合实际，群发红包记得也有金额上限，拆包上限，我觉得肯定就是为了方式单台出现性能问题，而且我觉得微信那边肯定会做好类似云原生等的保证红包这种核心业务的高可用性。
展开