负载均衡的常用算法

水深无声 2022-09-24 00:21 198阅读 0赞

在集群中，假设有五台服务器，他们之间的地位相同（主备模式不是我们要讨论的内容），都对外提供服务。当浏览器大量请求到达时，如何决定哪个请求到达哪个服务器上，这就是我们这次讨论的核心内容。

负载均衡的策略分为应用服务器和分布式缓存集群两种适应场景。

为什么这么分呢？简单的说，应用服务器只需要转发请求就可以了。但分布式缓存集群，比如redis、Memcached等，更多的是需要再次读取数据的。也正是因为这样，当新加入一台机器后，要尽量对整个集群的影响小。

# 1、应用服务器 #

## NO.1—— Random 随机 ##

这是最简单的一种，使用随机数来决定转发到哪台机器上。

优点：简单使用，不需要额外的配置和算法。  
缺点：随机数的特点是在数据量大到一定量时才能保证均衡，所以如果请求量有限的话，可能会达不到均衡负载的要求。

## NO.2—— Round Robin 轮询 ##

这个也很简单，请求到达后，依次转发，不偏不向。每个服务器的请求数量很平均。

缺点：当集群中服务器硬件配置不同、性能差别大时，无法区别对待。引出下面的算法。

## NO.3—— Weighted Round Robin 加权轮询 ##

这种算法的出现就是为了解决简单轮询策略中的不足。在实际项目中，经常会遇到这样的情况。

比如有5台机器，两台新买入的性能等各方面都特别好，剩下三台老古董。这时候我们设置一个权重，让新机器接收更多的请求。物尽其用、能者多劳嘛！

这种情况下，“均衡“就比较相对了，也没必要做到百分百的平均。

## NO.4—— Least Connections 最少连接 ##

这是最符合负载均衡算法的一个。需要记录每个应用服务器正在处理的连接数，然后将新来的请求转发到最少的那台上。

## NO.5—— Source Hashing 源地址散列 ##

根据请求的来源ip进行hash计算，然后对应到一个服务器上。之后所有来自这个ip的请求都由同一台服务器处理。

# 2、分布式缓存集群 #

好了，有了前面的基础，再看分布式缓存集群就简单多了。我们只需要多考虑两点就够了。

## NO.1—— 取模 ##

这是最简单但最不实用的一个。

以redis为例，假设我们有5台机器，要想取模肯定先得转换为数字，我们将一个请求的key转成数字（比如CRC16算法那），比如现在五个请求转换成的数字后对5取模分别为0、1、2、3、4，正好转发到五台机器上。

这时意外来了，其中一台宕机了，现在集群中还有4台。之后再来请求只能对4取模。问题就暴露出来了，那之前按照5取模的数据命中的机率大大降低了，相当于每宕机一台，之前存入的数据几乎都不能用了。

因此，不推荐此种做法。

## NO.2—— 哈希 ##

这种算法叫哈希有些笼统了，具体可以分为ip哈希和url哈希（类似原地址散列）。这里就不多说了。重点说下redis中的设计。

redis中引入了哈希槽来解决这一问题。16384个哈希槽，每次不再对集群中服务器的总数取模，而是16384这个固定的数字。然后将请求分发。这样就可以避免其中一台服务器宕机，原有数据无法命中的问题。

## NO.3—— 一致性哈希 ##

终于到重头戏了，不过有了前面的介绍，这个也就不难理解了。  
一致性哈希在memcached中有使用，通过一个hash环来实现key到缓存服务器的映射。

这个环的长度为2^32，根据节点名称的hash值将缓存服务器节点放在这个hash环上。如下图中的node1、node2等。

这时要保存的数据key仍旧进行hash运算，运算之后的值会落在这个hash环上的某一处（图中粉色的节点），当然这还没结束，因为他还没有落到node上。之后这个粉色的节点会沿顺时针落到离他最近的node上，over。

![这里写图片描述][20160721174211747]

### 改进 ###

当其中某个结点宕机后，比如node4，这时如果有结点落在了node2和node4之间，本来应该归为node4的，但这时候他宕机了，就都放在了下一个node3中。

这时，每个结点的数据量就会有很大出入了，平衡性很难保证。因此，引入“虚拟结点”。

> 虚拟结点是实际结点在hash空间的复制品，为了保证平衡性，一个实际node被划分成了若干个虚拟node。

如下图所示：

服务器之间的交错关系会改变，每个虚拟node之间的相对关系是不一定的，比如每个node1的虚拟节点后面可以是node2的也可以跟node3的。

此时，如果红色的node宕机了，那么将要落在这台机器上的数据可能落到蓝色，也可能是绿色的。这就保证了一定程度的平衡性。

![这里写图片描述][20160722165712798]

[20160721174211747]: /images/20220720/d030723d491e473a9c6ffc39385d7f11.png
[20160722165712798]: /images/20220720/bc3b58fa156c4be4a2eabd4d015acfad.png

发表评论取消回复

表情：

评论列表（有 0 条评论，198人围观）

还没有评论，来说两句吧...

相关阅读

相关负载均衡算法的几种常用方案

总结下负载均衡的常用方案及适用场景轮询调度以轮询的方式依次请求调度不同的服务器；实现时，一般为服务器带上权重；这样有两个好处： 1. 针对服务器的性...

系统管理员/ 2024年04月17日 05:41/ 0 赞/ 78 阅读

相关几种常用负载均衡

当前大多数的互联网系统都使用了服务器集群技术，集群即将相同服务部署在多台服务器上构成一个集群整体对外提供服务，这些集群可以是Web应用服务器集群，也可以是数据库服务器集群，还可

约定不等于承诺〃/ 2023年02月10日 05:03/ 0 赞/ 40 阅读

相关负载均衡的常用算法

在集群中，假设有五台服务器，他们之间的地位相同（主备模式不是我们要讨论的内容），都对外提供服务。当浏览器大量请求到达时，如何决定哪个请求到达哪个服务器上，这就是我们这次讨论的核

水深无声/ 2022年09月24日 00:21/ 0 赞/ 199 阅读

相关 Java 常用负载均衡算法解析

前言负载均衡在Java领域中有着广泛深入的应用，不管是大名鼎鼎的nginx，还是微服务治理组件如dubbo，feign等，负载均衡的算法在其中都有着实际的使用负载均

灰太狼/ 2022年09月07日 05:59/ 0 赞/ 247 阅读

相关负载均衡算法

1.轮询算法提供同质服务的节点逐个对外提供服务，概率相同 2.加权轮询算法在轮询算法的基础上，考虑到机器的差异性，分配给机器不同的权重，能者多劳。 3.随机算法

清疚/ 2022年06月02日 04:49/ 0 赞/ 227 阅读

相关负载均衡算法

1.轮询所有请求依次分发到每台应用服务器上，即每台服务器需要处理的请求数目都相同。 2.加权轮询在轮询的基础上，根据配置的权重将请求分发到不同的服务器上。

刺骨的言语ヽ痛彻心扉/ 2022年05月29日 09:16/ 0 赞/ 285 阅读

相关负载均衡技术(二）———常用负载均衡服务介绍

此文已由作者张小刚授权网易云社区发布。欢迎访问[网易云社区][Link 1]，了解更多网易技术产品运营经验。在上一篇文章中，介绍了负载均衡服务，常用的负

ゞ浴缸里的玫瑰/ 2022年04月16日 01:19/ 0 赞/ 398 阅读

相关常用负载均衡

HTTP 重定向对于HTTP 重定向，你一定不陌生，它可以将 HTTP 请求进行转移，在 Web 开发中我们经常会用它来完成自动跳转，比如用户登录成功后跳转到相应的管理页面

深藏阁楼爱情的钟/ 2022年03月25日 01:10/ 0 赞/ 222 阅读

相关负载均衡算法

前言 -------------------- 　　之前写过一个多进程异步服务系统的小项目，里面对于多个进程之间使用的负载均衡算法。就是最简单的轮询办法，但是这种算法存在

谁借莪１个温暖的怀抱￠/ 2021年10月23日 15:12/ 0 赞/ 450 阅读

相关负载均衡算法

1、轮询法将请求按顺序轮流地分配到后端服务器上，它均衡地对待后端的每一台服务器，而不关心服务器实际的连接数和当前的系统负载。 private stati

╰半橙微兮°/ 2021年06月24日 13:58/ 0 赞/ 499 阅读