常见的负载均衡算法

架构

字数统计: 2k阅读时长: 7 min

 2020/06/24   Share

前言

上一篇文章讲了负载均衡的几种实现方式，这期就重点讲讲当请求到达负载均衡服务器时，服务器可以根据哪些算法来进行分配请求。

正文

轮询法

这种方法很简单，就是按照顺序轮流将请求分配到各个服务器上，对服务器的状态和负载情况并不关注。
由于需要对pos变量进行操作，如果是高并发场景必须加写锁，并且会导致并发吞吐量的明显下降。
以下代码实现了一个简单的轮询。

class BalanceServer:
    def __init__(self):
        self.servers = ["192.168.1.1","192.168.1.2","192.168.1.3","192.168.1.4"]
        self.pos = 0
    
    def get_server(self):
        if self.pos == len(self.servers):
            self.pos = 0
            # self.pos %= len(self.server)
        
        server = self.servers[self.pos]
        self.pos += 1
        return server

随机法

这种方法与轮询差不多，将请求进行随机分配，当分配量足够大时，相当于将请求平均分配到每个服务器上。

class BalanceServer:
    def __init__(self):
        self.servers = ["192.168.1.1","192.168.1.2","192.168.1.3","192.168.1.4"]
        self.pos = 0
    
    def get_server_by_random(self):
        return self.servers[random.randint(0,len(self.servers)-1)]

源地址hash法

这种方法是通过获取访问客户端的ip地址，通过hash函数算出ip地址的hash值，然后通过hash值对服务器列表长度取模，获得访问的服务器序号。
这种方法的好处在于每次客户端访问的服务器都是同一个，便于建立有状态的session会话。
而缺点在于如果有服务器扩展或者下线时，如果通过源地址hash算法获得的服务器资源可能会不存在，如session或者缓存，导致请求的失败。如果是缓存服务器，则可能导致缓存击穿或者缓存雪崩(详见下文)。

class BalanceServer:
    def __init__(self):
        self.servers = ["192.168.1.1","192.168.1.2","192.168.1.3","192.168.1.4"]
        self.pos = 0
    
    def get_server_by_origin_hash(self,ip):
        ip_hash_code = hash(ip)
        server = self.servers[ip_hash_code % len(self.servers)]
        return server

加权轮询法（Weight Round Robin）

不同性能和配置的服务器对请求的抗压能力也不相同，让配置高，负载低的机器更高的权重，处理更多的请求，而配置低，负载高的机器则权重降低。通过权重我们可以重新构建服务器列表，然后再通过轮询获取服务器。

class BalanceServer:
    def __init__(self):
        self.servers = {
            '192.168.1.1':1,
            '192.168.1.2':3,
            '192.168.1.3':4,
            '192.168.1.4':2
        }
        self.pos = 0
    
    def get_server_by_weight_round_robin(self):
        # 这里可以避免服务器上下线
        servers_list = []
        for key in self.servers.keys():
            weight = self.servers[key]
            for i in range(weight):
                servers_list.append(key)
        
        # self.pos需要加锁
        if self.pos >= len(servers_list):
            self.pos = 0
        server = servers_list[self.pos]
        self.pos += 1
        return server

注意，这里的服务器的权重应该根据状态动态调整，而不是只是一个固定值。

加权随机法

和加权轮询法类似，只是在最后选择服务器上使用随机数，这里便不多说了。

最小连接数法

这种方法较为灵活，它是站在后端服务器的角度，根据当前服务器集群的连接情况，动态选取一台当前积压连接数最少的服务器来处理本次请求，合理的进行分流。

后续思考

使用hash算法的问题

上文提到使用源地址hash算法选取服务器的问题，在有服务器上下线的情况下，缓存在对应的机器上没有，可能会导致诸多问题，轻一点的就是session消失，用户需要重新登录，而如果严重一点的话则会导致瞬间大量的请求获取不到缓存，从而把大量请求直接往db中打，轻则阻塞，重则宕机。我们举个例子：
假设刚开始有4台缓存服务器，分别为0,1,2,3号，hash(ip) = 6 ，那么hash(ip) % 4 = 2，那么我们就应该去2号缓存服务器上拿缓存。假设此时多了一台服务器4号，那么hash(ip) % 5 = 1，我们就变成了去1号缓存服务器拿缓存，那么可想而知，如果请求量够大，一瞬间就有去新服务器拿旧服务器的缓存，而新服务器没有缓存，就会去数据库中查找，相当于大规模的缓存瞬间失效了，导致缓存雪崩。

缓存穿透，缓存击穿，缓存雪崩

这三个概念不是本文重点，这里只是提个概念。
缓存穿透是指请求查询了一个不存在的数据，导致每次都去数据库查询，缓存服务器相当于失效，这种情况叫做缓存穿透。
缓存击穿是指大量的请求同时查询了一个已经失效的缓存，导致这些请求集体请求数据库。
缓存雪崩则是指某个时间发生了大规模的缓存失效问题，如缓存服务器宕机，或者是上文讲的由于hash取模所带来的问题。

一致性hash算法

由于常用的hash(obj) % N算法在对机器添加或者删除之后，会导致原来的许多数据无法找到，所以一致性hash算法诞生了。
一致性hash算法首先需要将0(2^32)-1的数字形成一个环，可以想象成一个时钟。接着我们先将数据存储在环上，用上文的例子，即
hash(ip1)=key1,hash(ip2)=key2,hash(ip3)=key3，
这些key就是在环上的数字。接着我们同样通过hash算法将服务器的hash值映射到环上，例如
hash(server1)=KEY1,hash(server2)=KEY2,hash(server3)=KEY3,hash(server4)=KEY4，
我们假设KEY1KEY4分别在环的12点，3点，6点，9点钟方向，key1~key3分别在1点，4点，8点钟位置。
接着我们便可将key缓存到顺时针离自己最近的服务器上。即key1缓存在hash值KEY2的服务器上，key2缓存在KEY3的服务器上，key3缓存在KEY4的服务器上。
接下来是机器的删除与添加。

删除
假设2号服务器宕机，即hash值为KEY3的服务器移除了，也就是6点钟的服务器移除了，那么影响到的只有key2，key2的映射位置从2号服务器移到3号服务器，也就是只有原本2号服务器上的数据收到影响，而没有改变其他服务器。
添加
假设添加了一台服务器，hash(server5)位于时钟的2点钟方向，那么根据顺时针迁移，则key1的数据迁移到该服务器上，其他对象没有影响。

一致性hash算法将数据的迁移达到了最小，只有一部分数据需要迁移，而不是所有数据都进行迁移，这样的算法对于高并发，分布式的服务是十分合适的，避免了大量数据的迁移，减小了服务器压力。
如果文字讲解不够清楚的话，推荐可以看看图解。

总结

本文讨论了负载均衡的几种算法，并对hash算法带来的数据迁移问题进行讨论，讲解了一致性hash算法来解决问题。本文对于缓存服务出现的三种问题并没有深入讨论，没有提出解决方案，这部分内容之后也会单独写写。那么这个高并发系列就还剩下数据库的主从复制。
ps.由于图床的原因，最近的文章都没有添加图片，主要是不好管理，虽然有备份，但图床失效后，后续迁移工作十分繁琐，所以作者尽量不添加图片来讲述原理，望理解。

原文作者：Zer0e

原文链接：https://re0.top/2020/06/24/load_balancing_algorithm/

发表日期：June 24th 2020, 5:10:00 pm

更新日期：June 25th 2020, 3:36:44 pm

Next Post

浅谈数据库主从复制
Previous Post

浅谈负载均衡

CATALOG

1. 前言
2. 正文
3. 总结

