关于负载均衡的一切：总结与思考在计算机世界里，这就是我们熟悉的负载均衡（loadbalancing）。所谓负载均衡，是指如果一组计算机节点（或一组进程）提供相同（同质）的服务，那么对该服务的请求应该平均分布在这些节点之间。负载均衡的前提必须是“由多台服务器提供单一互联网服务”。这些提供服务的节点被称为服务器场、服务器池或后端服务器。这里的服务是广义的，可以是简单的计算，也可以是数据的读取或存储。负载均衡并不是一个新事物。这种想法在多核CPU时代就已经存在了。然而，在分布式系统中，负载均衡无处不在。这是由分布式系统的自然特性决定的。分布式就是利用大量的Computer节点进行单台计算机无法完成的计算和存储服务。由于计算机节点数量众多，均衡调度就显得尤为重要。负载均衡的意义在于让所有节点以最低的成本、最好的状态对外提供服务，使系统对用户有最大的吞吐量、更高的性能、更短的请求时间。此外，负载均衡增强了系统的可靠性，最大限度地降低了单个节点过载甚至崩溃的可能性。不难想象，如果一个系统的大部分请求都落在同一个节点上，那么这些请求的响应时间会很慢，如果该节点降级或崩溃，所有请求都会转移到下一个节点，引发雪崩。其实网上介绍负载均衡算法的文章很多，大同小异。这篇文章更多的是我自己对这些算法的总结和思考。一分钟了解负载均衡本章的标题和内容摘自文章一分钟了解负载平衡。当然，原文章的??标题有点夸张，但是文章列出了一个大型网站的每一层是如何使用负载均衡的，一目了然。常见的互联网分布式架构如上，分为客户端层、反向代理nginx层、站点层、服务层、数据层。可以看出，每个下游都有多个上游调用。它只需要确保每个上游均匀地访问每个下游，然后“将请求/数据[均匀]分发给多个操作单元执行”。(1)[clientlayer]到[reverseproxylayer]的负载均衡是通过“DNS轮询”实现的(2)[reverseproxylayer]到[sitelayer]的负载均衡是通过“nginx”实现的负载均衡(3）【站点层】到【服务层】是通过“服务连接池”实现的（4）【数据层】的负载均衡要考虑“数据均衡”和“请求均衡”两点，常见的方式有“横向”根据范围分段”和“水平散列分段”。数据层的负载均衡在我之前的《带着问题学习分布式系统之数据分片》有详细介绍。算法度量在我看来，当我们提到一个负载均衡算法或者一个具体的应用场景时，我们应该考虑以下几个问题。第一，你有没有意识到不同节点的服务能力是不同的，比如CPU、内存、网络、地理位置第二，你有没有意识到节点的服务能力是动态变化的，高端的机器也可能导致处理速度慢由于一些意想不到的原因？第三，是否考虑将同一个客户端，或者同一个请求分布到同一个处理节点，这对于“有状态”的服务来说非常重要，比如session，比如分布式存储。第四，谁来负责负载均衡，即谁来充当负载均衡器（loadbalancer），均衡器本身是否会成为瓶颈以下，这些问题都会用具体的算法来考虑。负载均衡算法（round-robin）的思想很简单，就是提供同质服务的节点一个一个提供服务，这样就可以做到绝对均衡。Python示例代码如下SERVER_LIST=['10.246.10.1','10.246.10.2','10.246.10.3',]defround_robin(server_lst,cur=[0]):length=len(server_lst)ret=server_lst[cur[0]]%length]cur[0]=(cur[0]+1)%lengthreturnret可以看出所有节点以相同的概率提供服务，即不考虑节点之间的差异，可能同样的请求数，高配置机器的CPU只有20%，低配置机器的CPU已经80%了。,有能力的人应该做更多的工作。请注意，此权重的分配取决于请求的类型。比如如果是计算密集型的，那就考虑CPU和内存；如果是IO密集型，那就考虑磁盘性能。Python示例代码如下WEIGHT_SERVER_LIST={'10.246.10.1':1,'10.246.10.2':3,'10.246.10.3':2,}defweight_round_robin(servers,cur=[0]):weighted_list=[]fork,vinservers.iteritems():weighted_list.extend([k]*v)length=len(weighted_list)ret=weighted_list[cur[0]%length]cur[0]=(cur[0]+1)%lengthreturnret随机算法（random）这个比较容易理解。随机选择一个节点进行服务。按照概率来说，只要请求数量足够大，也可以达到绝对平衡的效果。而实现上就简单多了defrandom_choose(server_lst):importrandomrandom.seed()returnrandom.choice(server_lst)加权随机算法（random）就像加权循环算法。至于round-robin算法，也是随机引入不同节点的权值，实现方式类似。defweight_random_choose(servers):importrandomrandom.seed()weighted_list=[]fork,vinservers.iteritems():weighted_list.extend([k]*v)returnrandom.choice(weighted_list)当然如果节点列表和权重变化不大，然后也可以对所有节点进行归一化，然后根据概率区间选择defnormalize_servers(servers)：normalized_servers={}total=sum(servers.values())cur_sum=0fork,vinservers.iteritems():normalized_servers[k]=1.0*(cur_sum+v)/totalcur_sum+=vreturnnormalized_serversdefweight_random_choose_ex(normalized_servers):importrandom,operatorrandom.seed()rand=random.random()fork,vinsorted(normalized_servers.iteritems(),key=operator.itemgetter(1)):ifv>=rand:returnkelse:assertFalse,'Errornormalized_serverwithrand%s'%rand散列法（hash）根据客户端的IP或请求的“Key”计算一个散列值，然后对节点数取模。优点是可以将同一个请求分配给同一个服务节点，这是“有状态”服务所必需的hashresult足够分散也可以达到绝对平衡。一致性哈希算法的缺陷也很明显。当节点数量发生变化时，请求将大概率分配给其他节点，从而导致一系列问题，例如粘性会话。而在某些情况下，比如分布式存储，是绝对不允许的。为了解决这种哈希算法的问题，引入了一致性哈希算法。简单的说就是一个物理节点映射到多个虚拟节点。散列时，使用虚拟节点的数量而不是物理节点的数量。当物理节点发生变化时，虚拟节点的数量不需要改变，只涉及虚拟节点的重新分配。而且，调整每个物理节点对应的虚拟节点的个数，相当于对每个物理节点赋予不同的权重。最少连接算法（leastconnection）之上的很多算法要么没有考虑节点间的差异性（round-robin,random,hash），要么节点间的权重是静态分配的（weightedround-robin,weightedrandom,consistenthash).考虑这样一种情况，某台机器出现故障，不能及时处理请求，但是新的请求还是会以一定的概率源源不断地分配给这个节点，导致请求积压。因此，根据节点的真实负载动态调整节点的权重是非常重要的。当然，获取连接节点的真实负载并不是一概而论的。如何定义负载，是否及时收集负载，是需要考虑的问题。当前每个节点的连接数是一个非常容易收集的指标，所以leaseconnection是最常提到的算法。还有一些指标侧重于不同的或更复杂和客观的指标，例如最小响应时间（leastresponsetime）、最小活跃数（leastactive）等。关于有状态请求的一点思考首先，我们看一下《算法测评》中提到的第三个问题：同一个请求是否分发到同一个服务节点，同一个请求指向同一个用户或者同一个唯一标识。同一个请求什么时候最好（必须）分发到同一个服务节点？那就是有状态的——请求依赖于存在于内存或者磁盘中的一些数据，比如一个web请求的session，比如分布式存储。如何实现，有以下几种方式：(1)请求分发时，保证将同一个请求分发到同一个服务节点。这个要看负载均衡算法，比如简单的循环训练，随机肯定是不行的，而且hash方法在节点增删时也会失效。可行的是一致性哈希，在分布式存储中按范围分段（即记录哪些请求由哪个服务节点服务），代价是在负载均衡器中维护额外的数据。(2)后端服务器共享状态数据，保证同一个请求分发到同一个服务节点。这只是一种手段，目的是请求相应的状态数据。如果可以在服务节点之间共享状态数据，也可以实现这一点。比如服务节点连接共享数据库，或者在客户端维护内存数据库如memcached(3)状态数据，web请求中也会用到，也就是cookies，但是安全必须被考虑并且需要加密。关于负载均衡器接下来回答第四个问题：关于负载均衡器，其实就是指在哪里做负载均衡，是客户端还是服务端，是请求的发起者还是请求者3.具体，或者在客户端，根据服务节点的信息进行选择，然后直接向选择的服务节点发送请求；或者在服务节点集群前面放一个中心化的代理（proxy），由proxy负责请求分发。无论哪种方式，至少你需要知道当前服务节点列表的基本信息。如果在客户端实现负载均衡，客户端首先要知道服务器列表，要么是静态配置的，要么有简单的接口查询，但是后端服务器的详细负载信息不适合通过客户端查询。因此，客户端的负载均衡算法要么比较简单，如round-robin（加权轮询）、random（加权随机）、hash算法等。只要每个客户端足够随机，根据大数定律，服务节点的负载也是均衡的。要在客户端使用更复杂的算法，比如根据后端的实际负载，需要去额外的负载均衡服务（externalloadbalancingservice）去查询这些信息。在grpc中，使用的就是这个方法。可以看到负载均衡器与grpc服务器通信获取grpc服务器的负载等具体细节，然后grpc客户端从负载均衡器获取这些信息，最后grpc客户端直接连接到选择好的grpc服务器。基于代理的方式比较常见，比如7层的Nginx，4层的F5，LVS，既有硬件路由，也有软件分发。集中式的特点是易于控制，可以很容易地实现一些更精密复杂的算法。但缺点也很明显。首先，负载均衡器本身可能成为性能瓶颈；第二，可能会引入额外的延迟。请求必须先到达负载均衡器，然后再到达真正的服务节点。负载均衡代理对请求的响应，要么不经过代理，比如LVS；或者通过代理，比如Nginx。下图是LVS的示意图，如果响应也使用了负载均衡代理，那么整个服务过程对客户端是完全透明的，同时也避免了客户端尝试连接后台服务器，提供了一层安全！值得注意的是，负载均衡代理不能成为单点故障，所以一般设计成高可用的主从结构。其他在本文中提到，负载均衡是一种推送模型，它肯定会选择一个服务节点，将请求推送过去。换个思路，使用消息队列就变成了拉模式：空闲的服务节点主动拉取请求进行处理，各个节点的负载自然就均衡了。与负载均衡相比，消息队列的优点是服务节点不会被大量请求压垮，更容易增加服务节点；缺点也很明显，请求并没有真正被处理。想想另一个例子。比如在gunicorn的pre-fork模型中，master（gunicorn中的Arbiter）会fork出指定数量的worker进程，worker进程监听同一个端口。谁先监听到网络连接请求，谁就提供服务，这也是worker进程之间的负载均衡。
