图片来自网络，转载自http://www.cnblogs.com/xybaby/p/7867735.html，但内容有修改
常见互联网分布式架构如上，分为客户端层、反向代理nginx层、站点层、服务层、数据层。可以看到，每一个下游都有多个上游调用，只需要做到，每一个上游都均匀访问每一个下游，就能实现“将请求/数据【均匀】分摊到多个操作单元上执行”。
(1)【客户端层】到【反向代理层】的负载均衡，是通过“DNS轮询”实现的
(2)【反向代理层】到【站点层】的负载均衡，是通过“nginx”实现的
(3)【站点层】到【服务层】的负载均衡，是通过“服务连接池”实现的
(4)【数据层】的负载均衡，要考虑“数据的均衡”与“请求的均衡”两个点，常见的方式有“按照范围水平切分”与“hash水平切分”。
算法衡量
在我看来，当我们提到一个负载均衡算法，或者具体的应用场景时，应该考虑以下问题
第一，是否意识到不同节点的服务能力是不一样的，比如CPU、内存、网络、地理位置
第二，是否意识到节点的服务能力是动态变化的，高配的机器也有可能由于一些突发原因导致处理速度变得很慢
第三，是否考虑将同一个客户端，或者说同样的请求分发到同一个处理节点，这对于“有状态”的服务非常重要，比如session，比如分布式存储
第四，谁来负责负载均衡，即谁充当负载均衡器（load balancer），balancer本身是否会成为瓶颈
下面会结合具体的算法来考虑这些问题
负载均衡算法
轮询算法（round-robin）
思想很简单，就是提供同质服务的节点逐个对外提供服务，这样能做到绝对的均衡。Python示例代码如下
|
1
2
3
4
5
6
7
8
9
10
|
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示例代码如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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）
这个就更好理解了，随机选择一个节点服务，按照概率，只要请求数量足够多，那么也能达到绝对均衡的效果。而且实现简单很多
|
1
2
3
4
|
def
random_choose(server_lst):
import
random3
random.seed()
4
return
random.choice(server_lst)
|
加权随机算法（random）
如同加权轮训算法至于轮训算法一样，也是在随机的时候引入不同节点的权重，实现也很类似。
|
1
2
3
4
5
6
7
|
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)
|
当然，如果节点列表以及权重变化不大，那么也可以对所有节点归一化，然后按概率区间选择
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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值，然后对节点数目取模。好处就是，同一个请求能够分配到同样的服务节点，这对于“有状态”的服务很有必要
|
1
2
3
|
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，不过要考虑安全性，需要加密。
