图片来自网络，转载自http://www.cnblogs.com/xybaby/p/7867735.html，但内容有修改

常见互联网分布式架构如上，分为客户端层、反向代理nginx层、站点层、服务层、数据层。可以看到，每一个下游都有多个上游调用，只需要做到，每一个上游都均匀访问每一个下游，就能实现“将请求/数据【均匀】分摊到多个操作单元上执行”。

　　(1)【客户端层】到【反向代理层】的负载均衡，是通过“DNS轮询”实现的

(2)【反向代理层】到【站点层】的负载均衡，是通过“nginx”实现的

(3)【站点层】到【服务层】的负载均衡，是通过“服务连接池”实现的

(4)【数据层】的负载均衡，要考虑“数据的均衡”与“请求的均衡”两个点，常见的方式有“按照范围水平切分”与“hash水平切分”。

算法衡量

　　在我看来，当我们提到一个负载均衡算法，或者具体的应用场景时，应该考虑以下问题

　　第一，是否意识到不同节点的服务能力是不一样的，比如CPU、内存、网络、地理位置

　　第二，是否意识到节点的服务能力是动态变化的，高配的机器也有可能由于一些突发原因导致处理速度变得很慢

　　第三，是否考虑将同一个客户端，或者说同样的请求分发到同一个处理节点，这对于“有状态”的服务非常重要，比如session，比如分布式存储

　　第四，谁来负责负载均衡，即谁充当负载均衡器（load balancer），balancer本身是否会成为瓶颈

　　下面会结合具体的算法来考虑这些问题

负载均衡算法

轮询算法（round-robin）

　　思想很简单，就是提供同质服务的节点逐个对外提供服务，这样能做到绝对的均衡。Python示例代码如下

                         
SERVER_LIST 
=
[
    
'10.246.10.1'
,
    
'10.246.10.2'
,
    
'10.246.10.3'
,
]
def
round_robin(server_lst, cur 
=
[
0
]):
    
length 
=
len
(server_lst)
    
ret 
=
server_lst[cur[
0
] 
%
length]
    
cur[
0
] 
=
(cur[
0
] 
+
1
) 
%
length
    
return
ret
        
      

　　可以看到，所有的节点都是以同样的概率提供服务，即没有考虑到节点的差异，也许同样数目的请求，高配的机器CPU才20%，低配的机器CPU已经80%了

加权轮询算法（weight round-robin）

　　加权轮训算法就是在轮训算法的基础上，考虑到机器的差异性，分配给机器不同的权重，能者多劳。注意，这个权重的分配依赖于请求的类型，比如计算密集型，那就考虑CPU、内存；如果是IO密集型，那就考虑磁盘性能。Python示例代码如下

                         
WEIGHT_SERVER_LIST 
=
{ 
    
'10.246.10.1'
: 
1
,
    
'10.246.10.2'
: 
3
,
    
'10.246.10.3'
: 
2
,
}
def
weight_round_robin(servers, cur 
=
[
0
]):
    
weighted_list 
=
[]
    
for
k, v 
in
servers.iteritems():
        
weighted_list.extend([k] 
*
v)
    
length 
=
len
(weighted_list)
    
ret 
=
weighted_list[cur[
0
] 
%
length]
    
cur[
0
] 
=
(cur[
0
] 
+
1
) 
%
length
    
return
ret
        
      

随机算法（random）

　　这个就更好理解了，随机选择一个节点服务，按照概率，只要请求数量足够多，那么也能达到绝对均衡的效果。而且实现简单很多

                         
def
random_choose(server_lst):     
    
import
random3     
    
random.seed()
4
    
return
random.choice(server_lst)

加权随机算法（random）

　　如同加权轮训算法至于轮训算法一样，也是在随机的时候引入不同节点的权重，实现也很类似。

                         
def
weight_random_choose(servers):
    
import
random
    
random.seed()
    
weighted_list 
=
[]
    
for
k, v 
in
servers.iteritems():
        
weighted_list.extend([k] 
*
v)
    
return
random.choice(weighted_list)
        
      

　　当然，如果节点列表以及权重变化不大，那么也可以对所有节点归一化，然后按概率区间选择

                         
def
normalize_servers(servers):
    
normalized_servers 
=
{}
    
total 
=
sum
(servers.values())
    
cur_sum 
=
0
    
for
k, v 
in
servers.iteritems():
        
normalized_servers[k] 
=
1.0
*
(cur_sum 
+
v) 
/
total
        
cur_sum 
+
=
v
    
return
normalized_servers
def
weight_random_choose_ex(normalized_servers):
    
import
random, operator
    
random.seed()
    
rand 
=
random.random()
    
for
k, v 
in
sorted
(normalized_servers.iteritems(), key 
=
operator.itemgetter(
1
)):
        
if
v >
=
rand:
            
return
k
    
else
:
        
assert
False
, 
'Error normalized_servers with rand %s '
%
rand
        
      

哈希法（hash）

　　根据客户端的IP，或者请求的“Key”，计算出一个hash值，然后对节点数目取模。好处就是，同一个请求能够分配到同样的服务节点，这对于“有状态”的服务很有必要

                         
 
def
hash_choose(request_info, server_lst):
     
hashed_request_info 
=
hash
(request_info)
     
return
server_lst[hashed_request_info 
%
len
(server_lst)]
        
      

　　只要hash结果足够分散，也是能做到绝对均衡的。

一致性哈希

　　哈希算法的缺陷也很明显，当节点的数目发生变化的时候，请求会大概率分配到其他的节点，引发到一系列问题，比如sticky session。而且在某些情况，比如分布式存储，是绝对的不允许的。

　　为了解决这个哈希算法的问题，又引入了一致性哈希算法，简单来说，一个物理节点与多个虚拟节点映射，在hash的时候，使用虚拟节点数目而不是物理节点数目。当物理节点变化的时候，虚拟节点的数目无需变化，只涉及到虚拟节点的重新分配。而且，调整每个物理节点对应的虚拟节点数目，也就相当于每个物理节点有不同的权重

最少连接算法（least connection）

　　以上的诸多算法，要么没有考虑到节点间的差异（轮训、随机、哈希），要么节点间的权重是静态分配的（加权轮训、加权随机、一致性hash）。

　　考虑这么一种情况，某台机器出现故障，无法及时处理请求，但新的请求还是会以一定的概率源源不断的分配到这个节点，造成请求的积压。因此，根据节点的真实负载，动态地调整节点的权重就非常重要。当然，要获得接节点的真实负载也不是一概而论的事情，如何定义负载，负载的收集是否及时，这都是需要考虑的问题。

　　每个节点当前的连接数目是一个非常容易收集的指标，因此lease connection是最常被人提到的算法。也有一些侧重不同或者更复杂、更客观的指标，比如最小响应时间（least response time）、最小活跃数（least active）等等。

有状态的请求的处理　　

　　首先来看看“算法衡量”中提到的第三个问题：同一个请求是否分发到同样的服务节点，同一个请求指的是同一个用户或者同样的唯一标示。什么时候同一请求最好（必须）分发到同样的服务节点呢？那就是有状态 -- 请求依赖某些存在于内存或者磁盘的数据，比如web请求的session，比如分布式存储。怎么实现呢，有以下几种办法：

　　（1）请求分发的时候，保证同一个请求分发到同样的服务节点。

　　这个依赖于负载均衡算法，比如简单的轮训，随机肯定是不行的，哈希法在节点增删的时候也会失效。可行的是一致性hash，以及分布式存储中的按范围分段（即记录哪些请求由哪个服务节点提供服务），代价是需要在load balancer中维护额外的数据。

　　（2）状态数据在backend servers之间共享

　　保证同一个请求分发到同样的服务节点，这个只是手段，目的是请求能使用到对应的状态数据。如果状态数据能够在服务节点之间共享，那么也能达到这个目的。比如服务节点连接到共享数据库，或者内存数据库如memcached

　　（3）状态数据维护在客户端

　　这个在web请求中也有使用，即cookie，不过要考虑安全性，需要加密。

本文转自lq201151CTO博客，原文链接：http://blog.51cto.com/liuqun/2044509 ，如需转载请自行联系原作者