互联网常用的负载均衡分析

 一:负载均衡简介:

     在了解Dubbo的负载均衡实现的时候,刚好去了解一下业界上,是怎么在DNS、应用层、服务层来实现负载均衡操作。

     先了解一下什么是负载均衡

         负载均衡,英文 名称为Load Balance,指由多台服务器以对称的方式组成一个服务器集合,每台服务器都具有等价的地位,都可以单独对外提供服务而无须其他服务器的辅助。通过某种 负载分担技术,将外部发送来的请求均匀分配到对称结构中的某一台服务器上,而接收到请求的服务器独立地回应客户的请求。负载均衡能够平均分配客户请求到服 务器阵列,借此提供快速获取重要数据,解决大量并发访问服务问题,这种集群技术可以用最少的投资获得接近于大型主机的性能。

        负载均衡分为软件负载均衡和硬件负载均衡,前者的代表是阿里章文嵩博士研发的LVS,后者则是均衡服务器比如F5,

二:网上比较金典的负载均衡文章:

Nginx的负载均衡处理的配置:

  http://www.dczou.com/viemall/359.html

大型网站架构系列:负载均衡详解

  http://www.cnblogs.com/itfly8/p/5043435.html

一分钟理解负载LoadAverage

http://mp.weixin.qq.com/s/bQOclyDtUKd53J3qy2J91g

一分钟了解负载均衡的一切

http://mp.weixin.qq.com/s/B9-7mALpvovnEMNM7BbHyQ

如何实施异构服务器的负载均衡及过载保护?

http://mp.weixin.qq.com/s/gxYKzG4ZgKHNLGBN00sfXA

lvs为何不能完全替代DNS轮询

http://mp.weixin.qq.com/s/4dzqbh2wfzbQzgFodP2_6Q

58到家MQ如何快速实现流量削峰填谷

http://mp.weixin.qq.com/s/3C7UZUH3eVuOVnWeea3_Ig

利用dns解析来实现网站的负载均衡

https://segmentfault.com/a/1190000002578457 

三:常用的负载均衡算法

       常用的负载均衡算法主要有随机法,轮询法,加权随机,加权轮询,最小连接数,一致性hash等。随机法,轮询法都比较简单,随机算法不考虑服务器的负载实际中很少使用,轮询算法在服务的上线下线时无法及时感应到也较少使用.  如果让我们来通过Java来实现对服务的负载均衡怎么做?

    接下来,我们通过Java代码,来实现几种非常简单的负载均衡:

轮询法:(roll poling  LoadBalance)

    注:这种方式是不断的获取下一个元素,

public class Robin {
	/**
	 * 当前标识位置
	 */
	private static volatile int position = 0;
	public static HashMap<String, Integer> serverWeightMap = new HashMap<String, Integer>();
	static {
		serverWeightMap.put("192.168.0.1", 1);
		serverWeightMap.put("192.168.0.2", 2);
		serverWeightMap.put("192.168.0.3", 3);
		serverWeightMap.put("192.168.0.4", 4);
		serverWeightMap.put("192.168.0.5", 2);
		serverWeightMap.put("192.168.0.6", 1);
		serverWeightMap.put("192.168.0.7", 5);
	}

	public String select() {
		Set<String> keySet = serverWeightMap.keySet();
		ArrayList<String> keyList = new ArrayList<String>();
		keyList.addAll(keySet);
		String server;
		synchronized (this) {
			if (position >= keyList.size()) {
				position = 0;
			}
			server = keyList.get(position);
			position++;
		}
		return server;
	}

	public static void main(String[] args) {
		Robin robin=new Robin();
		while(true){
			System.out.println(robin.select());
			try {
				Thread.sleep(2000);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	}
}

    Zookeeper 的链接服务选取,也是基于轮询的方式来实现服务的获取:

    http://www.dczou.com/viemall/487.html

随机(Random)法

    1、权重随机算法:

        如有4个元素A、B、C、D,权重分别为1、2、3、4,随机结果中A:B:C:D的比例要为1:2:3:4。

        总体思路:累加每个元素的权重A(1)-B(3)-C(6)-D(10),则4个元素的的权重管辖区间分别为[0,1)、[1,3)、[3,6)、[6,10)。然后随机出一个[0,10)之间的随机数。落在哪个区间,则该区间之后的元素即为按权重命中的元素。

 
public class WeightRandom {

	public static HashMap<String, Integer> serverWeightMap = new HashMap<String, Integer>();

	static {
		serverWeightMap.put("192.168.0.1", 1);
		serverWeightMap.put("192.168.0.2", 2);
		serverWeightMap.put("192.168.0.3", 3);
		serverWeightMap.put("192.168.0.4", 4);
	}

	private final Random random = new Random();

	public String select() {
		int totalWeight = 0; // 总权重
		boolean sameWeight = true; // 权重是否都一样
		int length = serverWeightMap.size(); // 总个数
		for (Entry<String, Integer> entries : serverWeightMap.entrySet()) {
			int weight = entries.getValue();
			totalWeight += weight; // 累计总权重
			if (sameWeight && serverWeightMap.containsValue(weight)) {
				sameWeight = false; // 计算所有权重是否一样
			}
		}
		if (totalWeight > 0 && !sameWeight) {
			// 如果权重不相同且权重大于0则按总权重数随机
			int offset = random.nextInt(totalWeight);
			// 并确定随机值落在哪个片断上
			return random(offset);
		}
		// 随机
		int offset = random.nextInt(length);
		return random(offset);
	}

	public String random(int offset) {
		Integer m = 0;
		String random = null;
		for (Entry<String, Integer> entries : serverWeightMap.entrySet()) {
			if (m <= offset && offset < m + entries.getValue()) {
				System.out.println("This Random Category is "+ entries.getValue());
				random = entries.getKey();
				break;
			}
			m += entries.getValue();
		}
		return random;
	}
	
	public static void main(String[] args) {
		WeightRandom random=new WeightRandom();
		while(true){
			String randomNumber=random.select();
			System.out.println(randomNumber);
			try {
				Thread.sleep(2000);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	}

}

  参考链接:

       http://www.cnblogs.com/waterystone/p/5708063.html

Dubbo 的权重随机算法的解析: RandomLoadBalance

       http://blog.csdn.net/youaremoon/article/details/51112284

随机(RoundRobin)公约权重

      Dubbo 的权重随机算法的解析: RoundRobinLoadBalance

最小连接数(Least Connections)法

      最小连接数算法比较灵活和智能,由于后端服务器的配置不尽相同,对于请求的处理有快有慢,它是根据后端服务器当前的连接情况,动态地选取其中当前

    积压连接数最少的一台服务器来处理当前的请求,尽可能地提高后端服务的利用效率,将负责合理地分流到每一台服务器

        Dubbo:LeastActiveLoadBalance

一致性hash算法

      目前在企业里面常用的基于内存的缓存服务memcached默认采用的负载均衡算法就是一致性hash算法,一致性hash算法可用保证对同一参数的请求将会是同一个服务器来处理,其原理大概如下:我们可以将可利用的服务器列表映射到一个hash环上,当客户端请求过来时,求出key的hash值映射到hash环上,然后顺时针查找,找到的第一台机器就是出来该请求的服务,如果循环完了还是没找到,那么就将请求转给hash环上的第一台机器处理,可以想象的是,如果咱们的集群足够大,可能循环很久才能找到对应的服务器,这就加大了网络IO

     如:  Dubbo: ConsistentHashLoadBalance

public class ConsistentHashingWithVirtualNode {
	private final ConcurrentMap<String, String> selectors 
	                              = new ConcurrentHashMap<String, String>();
	private List<String> servers;
	private final TreeMap<Long, String> virtualInvokers;
	private final int VIRTUAL_NODES = 5;
	public ConsistentHashingWithVirtualNode() {
		servers = new ArrayList<String>();
		servers.add("192.168.0.0:111");
		servers.add("192.168.0.1:111");
		servers.add("192.168.0.2:111");
		servers.add("192.168.0.3:111");
		servers.add("192.168.0.4:111");
		this.virtualInvokers = new TreeMap<Long, String>();
		for (String invoker : servers) {
			for (int i = 0; i < VIRTUAL_NODES; i++) {
				byte[] digest = md5(invoker + i);
				for (int h = 0; h < 4; h++) {
					long m = hash(digest, h);
					virtualInvokers.put(m, invoker);
				}
			}
		}
		/*for(Entry<Long, String> entries:virtualInvokers.entrySet()){
			System.out.println(entries.getKey());
			System.out.println(entries.getValue());
		}*/
	}

	protected String doSelect(String key) {
		String selector = selectors.get(key);
		if(selector!=null){
			return selector;
		}
		selector=select(key);
		selectors.put(key, selector);
		return  selector;
	}

	private String select(String key) {
		byte[] digest = md5(key);
		String invoker = sekectForKey(hash(digest, 0));
		return invoker;
	}

	private String sekectForKey(long hash) {
		String invoker;
		Long key = hash;
		if (!virtualInvokers.containsKey(key)) {
			SortedMap<Long, String> tailMap = virtualInvokers.tailMap(key);
			if (tailMap.isEmpty()) {
				key = virtualInvokers.firstKey();
			} else {
				key = tailMap.firstKey();
			}
		}
		invoker = virtualInvokers.get(key);
		return invoker;
	}

	private long hash(byte[] digest, int number) {
		return (((long) (digest[3 + number * 4] & 0xFF) << 24)
				| ((long) (digest[2 + number * 4] & 0xFF) << 16)
				| ((long) (digest[1 + number * 4] & 0xFF) << 8) 
				| (digest[0 + number * 4] & 0xFF)) & 0xFFFFFFFFL;
	}

	private byte[] md5(String value) {
		MessageDigest md5;
		try {
			md5 = MessageDigest.getInstance("MD5");
		} catch (NoSuchAlgorithmException e) {
			throw new IllegalStateException(e.getMessage(), e);
		}
		md5.reset();
		byte[] bytes = null;
		try {
			bytes = value.getBytes("UTF-8");
		} catch (UnsupportedEncodingException e) {
			throw new IllegalStateException(e.getMessage(), e);
		}
		md5.update(bytes);
		return md5.digest();
	}
	
	public static void main(String[] args) {
		ConsistentHashingWithVirtualNode node=new ConsistentHashingWithVirtualNode();
		for (int i = 0; i < 100; i++) {
			String keyString="www.baidu.com"+i;
			String keyString2="www.baidu.com"+i;
			String keyString3="www.baidu.com.cn"+i;
			System.out.println(node.doSelect(keyString));
			System.out.println(node.doSelect(keyString2));
			System.out.println(node.doSelect(keyString3));
		}
	}
}

一致性哈希算法及其在分布式系统中的应用

一致性hash算法 – consistent hashing

发表评论