负载均衡算法在很多地方都有使用,无论是在服务治理中或者是在分布式缓存中都大量的使用,本文主要介绍几种常见的负载均衡的算法.
1.轮询法.
轮询法,很好理解,将请求按照顺序轮流的分配到服务器上,他均衡的对待每一台后端的服务器,
不关心服务器的的连接数和负载情况.以下代码演示了这种算法.
public class BalanceServer {
public static List<String> servers = Arrays.asList("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4",
"192.168.0.5");
public static int pos = 0;
public static String getServer() {
String server = null;
if (pos >= servers.size()) {
pos = 0;
}
server = servers.get(pos);
pos++;
return server;
}
public static void main(String[] args) {
for(int i=0;i<10;i++){
System.out.println(BalanceServer.getServer());
}
}
}
轮询的策略目的在于请求的绝对均衡,但是在实际的情况下,可能服务器并不是完全一样.
导致有些性能高的服务器不能完全发挥出来.
2.随机法
通过系统的随机函数,根据后端服务器列表的大小来随机获取其中的一台来访问,随着调用量的增大,
实际效果越来越近似于平均分配到没一台服务器.和轮询的效果类似.
public class BalanceServer {
public static List<String> servers = Arrays.asList("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4",
"192.168.0.5");
public static int pos = 0;
public static String getServer() {
String server = null;
Random random = new Random();
int randomPos = random.nextInt(servers.size());
server = servers.get(randomPos);
return server;
}
}
和轮询算法比较,在并发的场景下,轮询需要加锁,随机法想比而言性能好点.
3.源地址hash法.
源地址hash法的思想是获取客户端访问的ip地址,通过hash函数计算出一个hash值,用该hash值对服
务器列表的大小进行取模运算,得到的值就是要访问的服务器的序号.
public class BalanceServer {
public static List<String> servers = Arrays.asList("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4",
"192.168.0.5");
public static int pos = 0;
public static String getServer(String ip) {
String server = null;
int hashCode = ip.hashCode();
pos = hashCode % servers.size();
server = servers.get(pos);
return server;
}
}
hash法的好处是,在服务器列表不变的情况下,每次客户端访问的服务器都是同一个服务器.利用这个
特性可以有状态的session会话.无需额外的操作就可以实现粘性会话.
- 加权轮询法.
刚刚有说道过,不同的服务器性能不同,所以不能一概而论,需要给性能低的服务器给比较低的
权重,性能高的给跟高的权重.
public class BalanceServer {
public static Map<String, Integer> serverMap = new HashMap<String, Integer>();
public static int pos = 0;
static {
serverMap.put("192.168.0.1", 1);
serverMap.put("192.168.0.2", 1);
serverMap.put("192.168.0.3", 4);
serverMap.put("192.168.0.4", 3);
serverMap.put("192.168.0.5", 3);
serverMap.put("192.168.0.6", 2);
}
public static String getServer() {
Set<String> keySet = serverMap.keySet();
Iterator<String> it = keySet.iterator();
List<String> servers = new ArrayList<String>();
while (it.hasNext()) {
String server = it.next();
Integer weight = serverMap.get(server);
for (int i = 0; i < weight; i++) {
servers.add(server);
}
}
String server = null;
if (pos >= servers.size()) {
pos = 0;
}
server = servers.get(pos);
pos++;
return server;
}
public static void main(String[] args) {
for(int i=0;i<14;i++){
System.out.println(BalanceServer.getServer());
}
}
}
5.加权随机法,
加权随机法算法和加权轮询法类似.就不多说了.
- 有关hash算法的一些补充说明
在上面的hash算法中,存在以下的几个问题
1.当一台服务器宕机了或者新添加一台机器之后,这个时候hashCode % servers.size()
需要重新计算hash值, 如果在缓存的环境中,所有的请求都会涌向数据库服务
器,给数据库服务器带来巨大的压力,可能导致整个系统不可用,形成雪崩效应.
2 .当新增了一台性能强的机器后,利用上述的hash算法无法让,新增的性能强的服务器多承担压力.
基于上面的几个问题,提出了hash算法的改进,consistent hash算法,consistent hashing
也是一种 hash 算法，简单的说，在移除 / 添加操作，它能够尽可能小的改变已存在 key 映射关系.
consistent hash算法的原理是它将hash函数的值域组织成一个
环形,整个空间按照顺时针的方式进行组织,将对应的服务器节点进行hash,将他们映射到
hash环上,假设有四台机器node1-4,hash之后如图所示:
consistent hashing.png
接下来使用相同的hash函数,计算出对应的key值和hash值,按照顺时针的方式,分布在node1和node2
的key,访问时被定位在node2,分布在node2和node4的key被定位在node4上,以此类推.假设现
在新增一个node5,假设hash之后在node2和node4之间,如图所示:
新增node.png
那么受影响的节点只有node2和node5,他们将会从新hash,而其他的key的映射将不会变化.
当然,上面描绘了一种很理想的情况,各个节点在环上分布的十分均匀.正常情况下,当节点数量少的
时候,节点分布并不均匀,这时需要引入虚拟节点机制.
总结:本篇只是概述了几种常见的均衡负载算法,有关 consistent hash算法,可以参考http://blog.csdn.net/sparkliang/article/details/5279393
