傻男人---个人博客

常见负载均衡的算法

轮询算法

算法按照顺序依次分发请求，所有服务器都分发一遍后，又会回到第一台服务器循环该步骤。

实现代码

@Slf4j
public class TrainingInRotation {

	public static final List<String> LIST = Arrays.asList(
			"172.168.0.1:8080",
			"172.168.0.2:8081",
			"172.168.0.3:8082",
			"172.168.0.4:8083",
			"172.168.0.5:8084"
	);

	//记录请求的序列号
	private static AtomicInteger requestIndex = new AtomicInteger(0);

	public static String getServer(){
		//取模,获取档次请求服务地址的下标
		int index = requestIndex.get() % LIST.size();
		String sever = LIST.get(index);
		//自增一次请求序列号，方便下个请求计算
		requestIndex.incrementAndGet();
		return sever;
	}

	public static void main(String[] args) {
		Long startTime = System.currentTimeMillis();
		for (int i = 0; i < 10; i++) {
			System.out.println("第"+ i + "个请求：" + getServer());
		}
		System.out.println("10次负载耗时："+(System.currentTimeMillis()-startTime));
	}
}

运行的结果

第0个请求：172.168.0.1:8080
第1个请求：172.168.0.2:8081
第2个请求：172.168.0.3:8082
第3个请求：172.168.0.4:8083
第4个请求：172.168.0.5:8084
第5个请求：172.168.0.1:8080
第6个请求：172.168.0.2:8081
第7个请求：172.168.0.3:8082
第8个请求：172.168.0.4:8083
第9个请求：172.168.0.5:8084
10次负载耗时：1

从上述的代码也不难看出,算法十分的简单，就是通过一个原子计算器记录当前的请求序列号，然后通过%的取余算法，得到服务器的下标值，通过下标值从服务器列表中获取当前服务的地址

优势
- 算法简单，请求分发效率高
- 能将请求均摊到集群中的每个节点中
- 易于弹性伸缩
劣势
- 无法对不同配置的服务器合理照顾，无法将高配置的服务器性能发挥出来
- 无法保证同一客户端的请求都由同一节点处理(服务器假如需要session记录状态时，无法确保一致性)
应用的场景
- 集群节点硬件配置基本相同
- 只读不写，无需保持状态的情景

随机算法

算法按照从配置的服务器列表中随机抽取一个服务器来处理

实现代码

public class RandomServer {

	public static final List<String> LIST = Arrays.asList(
			"172.168.0.1:8080",
			"172.168.0.2:8081",
			"172.168.0.3:8082",
			"172.168.0.4:8083",
			"172.168.0.5:8084"
	);

	public static String getServer(){
		return LIST.get(RandomUtils.nextInt(0,4));
	}

	public static void main(String[] args) {
		Long startTime = System.currentTimeMillis();
		for (int i = 0; i < 10; i++) {
			System.out.println("第"+ i + "个请求：" + getServer());
		}
		System.out.println("10次负载耗时："+(System.currentTimeMillis()-startTime));
	}
}

运行的结果

第0个请求：172.168.0.1:8080
第1个请求：172.168.0.4:8083
第2个请求：172.168.0.2:8081
第3个请求：172.168.0.2:8081
第4个请求：172.168.0.4:8083
第5个请求：172.168.0.2:8081
第6个请求：172.168.0.4:8083
第7个请求：172.168.0.3:8082
第8个请求：172.168.0.1:8080
第9个请求：172.168.0.4:8083
10次负载耗时：2

优势
- 算法简单，请求分发效率高
- 能将请求均摊到集群中的每个节点中
- 易于弹性伸缩
劣势
- 无法将请求均摊到每台服务器上
- 请求服务不明确性，无法记录状态请求

权重算法

权重算法并不能单独配置，因为权重算法无法做到请求分发的调度，所以一般权重会配合其他基础算法结合使用。如：轮询权重算法、随机权重算法等，这样可以让之前的两种基础调度算法更为“人性化”一些。权重算法是指对于集群中的每个节点分配一个权重值，权重值越高，该节点被分发的请求数也会越多，反之同理。这样做的好处十分明显，也就是能够充分考虑机器的硬件配置，从而分配不同权重值，做到“能者多劳”。

实现代码

public class WeightRobinServer {

	private static Map<String, Integer> SERVERS = Maps.newHashMap();

	static {
		SERVERS.put("172.168.0.1:8080",1);
		SERVERS.put("172.168.0.2:8081",2);
		SERVERS.put("172.168.0.3:8082",3);
		SERVERS.put("172.168.0.4:8083",4);
		SERVERS.put("172.168.0.5:8084",5);
	}

	public static String getServer(){
		//总权重值
		int weightTotal = 0;
		for (Integer weight : SERVERS.values()) {
			weightTotal += weight;
		}
		int index = RandomUtils.nextInt(0, weightTotal - 1);
		String targetServer = "";
		for(String server : SERVERS.keySet()){
			Integer weight = SERVERS.get(server);
			//权重值大于生成随机数，则表示此次随机分配应该落入该节点
			if(weight > index){
				targetServer = server;
				break;
			}
			index = index -weight;
		}
		return targetServer;
	}

	public static void main(String[] args) {
		Long startTime = System.currentTimeMillis();
		for (int i = 0; i < 10; i++) {
			System.out.println("第"+ (i+1) + "个请求：" + getServer());
		}
		System.out.println("10次  耗时："+(System.currentTimeMillis()-startTime));
	}
}

运行的结果

第1个请求：172.168.0.3:8082
第2个请求：172.168.0.5:8084
第3个请求：172.168.0.4:8083
第4个请求：172.168.0.4:8083
第5个请求：172.168.0.4:8083
第6个请求：172.168.0.5:8084
第7个请求：172.168.0.4:8083
第8个请求：172.168.0.5:8084
第9个请求：172.168.0.1:8080
第10个请求：172.168.0.3:8082
10次  耗时：3

大概思路：

先求和所有的权重值，再随机生成一个总权重之内的索引。
遍历配置服务器列表，用随机索引与每个节点的权重值进行判断。如果小于，则代表当前请求应该落入目前这个节点；如果大于，则代表随机索引超出了目前节点的权重范围，则减去当前权重，继续与其他节点判断。
最终随机出的索引总会落入到一个节点的权重范围内，最后返回对应的节点IP。

轮询权重算法与随机权重算法的对比

轮询权重算法会从开始一直轮询，在一轮中的请求会按照权重值均摊，会造成节点在一定范围内比较集中
随机权重算法相对轮询更加合理，请求会按照权重值均摊到节点中

平滑加权轮询算法

实现代码

@Slf4j
@Data
public class Weight implements Serializable {

	/**
	 * 节点信息
	 */
	private String server;
	/**
	 * 权重值
	 */
	private Integer weight;
	/**
	 * 动态权重值
	 */
	private Integer currentWeight;

}

public class RoundRobinWeight {

	private static Map<String,Weight> weightMap = Maps.newHashMap();

	private static Map<String, Integer> SERVERS = Maps.newHashMap();

	private static int weightTotal = 0;

	static {
		SERVERS.put("172.168.0.1:8080",1);
		SERVERS.put("172.168.0.2:8081",2);
		SERVERS.put("172.168.0.3:8082",3);

		SERVERS.forEach((k,v)->{
			weightTotal += v;
			weightMap.put(k,new Weight(k,v,0));
		});
	}

	public static String getServer(){
		//每次请求，动态更改动态权重值
		for(Weight weight : weightMap.values()){
			weight.setCurrentWeight(weight.getWeight() + weight.getCurrentWeight());
		}
		Weight result = null;
		for (Weight weight : weightMap.values()){
			if(null == result || weight.getCurrentWeight() > result.getCurrentWeight()){
				result = weight;
			}
		}
		//最大的动态权重值减去所有节点的总权重值
		result.setCurrentWeight(result.getCurrentWeight()-weightTotal);
		return result.getServer();
	}

	public static void main(String[] args) {
		Long startTime = System.currentTimeMillis();
		for (int i = 0; i < 6; i++) {
			System.out.println("第"+ i + "个请求：" + getServer());
		}
		System.out.println("10次轮询的耗时："+(System.currentTimeMillis()-startTime));
	}
}

运行的结果

第0个请求：172.168.0.3:8082
第1个请求：172.168.0.2:8081
第2个请求：172.168.0.1:8080
第3个请求：172.168.0.3:8082
第4个请求：172.168.0.2:8081
第5个请求：172.168.0.3:8082
10次轮询的耗时：0

一致性哈希算法

是一种能够能够确保同一客户端的所有请求都会被分发到同一台机器的策略，不过一致性哈希算法依旧会存在问题，就是当集群中某个节点下线，或者集群出现拓展时，那么也会影响最终分发的目标机器

哈希环

可以将二的三十二次方想象成一个圆，这个圆总共由 2^32 个点组成

哈希环

圆环的正上方第一个点代表 0，0 右侧的点按照 1、2、3、4....的顺序依此类推，直到 2^32-1，也就是说 0 左侧的第一个点代表着 2^32-1。
最终这个在逻辑上由 2^32 个点组成的圆，被称为哈希环。
假设有四个节点A、B、C、D，然后通过每个节点哈希值取模 2^32，最终必然会得到一个 2^32 范围之内的整数，这个数在哈希环上定然也对应着一个点。

如果请求在B与C之间，请求到C节点，因为哈希环中，顺时针方向走，遇到的第一台服务器就是C

哈希环映射偏移问题

上图为理想的状态，可能存在以下的情况,这样大部分的请求就集中到B节点上了通过虚拟节点来减轻B节点上的压力

实现代码

public class ConsistentHash {

	public static final List<String> LIST = Arrays.asList(
			"172.168.0.1:8080",
			"172.168.0.2:8081",
			"172.168.0.3:8082",
			"172.168.0.4:8083",
			"172.168.0.5:8084"
	);

	//有序的红黑树结构，用于实现哈希环结构
	private static TreeMap<Integer, String>  nodes = new TreeMap<>();

	//每个真实节点的虚拟节点数量
	private static final int VIRTUAL_NODES = 160;
	
	static {
		for (String node:LIST) {
			nodes.put(Math.abs(node.hashCode()),node);
			for (int i = 0; i < VIRTUAL_NODES; i++) {
				nodes.put(Math.abs(HashUtil.oneByOneHash(node+i)),node);
			}
		}
	}

	public static String getServer(String ip){
		int hash = Math.abs(HashUtil.oneByOneHash(ip));
		//取模,获取档次请求服务地址的下标,得到大于该Hash值的子红黑树
		SortedMap<Integer, String> sortedMap = nodes.tailMap(hash);
		// 得到该树的第一个元素，也就是最小的元素
		Integer treeNodeKey = sortedMap.firstKey();
		// 如果没有大于该元素的子树了，则取整棵树的第一个元素，相当于取哈希环中的最小元素
		if (sortedMap == null)
			treeNodeKey = nodes.firstKey();
		// 返回对应的虚拟节点名称
		return nodes.get(treeNodeKey);
	}

	public static void main(String[] args) {
		Long startTime = System.currentTimeMillis();
		for (int i = 0; i < 7; i++) {
			System.out.println("第"+ i + "个请求：" + getServer("192.168.1.12"+i));
		}
		for (int i = 0; i < 3; i++) {
			System.out.println("第"+ i + "个请求：" + getServer("192.168.2.121"));
		}
		System.out.println("10次轮询的耗时："+(System.currentTimeMillis()-startTime));
	}
}

运行的结果

第0个请求：172.168.0.5:8084
第1个请求：172.168.0.3:8082
第2个请求：172.168.0.1:8080
第3个请求：172.168.0.2:8081
第4个请求：172.168.0.1:8080
第5个请求：172.168.0.4:8083
第6个请求：172.168.0.2:8081
第0个请求：172.168.0.5:8084
第1个请求：172.168.0.5:8084
第2个请求：172.168.0.5:8084
10次轮询的耗时：1

算法过程如下：

启动时先根据指定的数量，映射对应的虚拟节点数量在哈希环上。
通过计算客户端哈希值，然后在哈希环上取得大于该值的节点，然后返回对应的 IP。由于哈希环是取顺时针方向的第一个节点作为处理请求的目标服务器，所以获取大于该哈希值的节点中的第一个节点即可。
如果哈希环中没有大于客户端哈希值的节点，那么则将这些客户端的请求分发到整个 Map 上的第一台服务器，从此实现哈希闭环。

最小活跃数算法

会根据线上的实际情况进行分发，能够灵活的检测出集群中各个节点的状态，能够自动寻找并调用活跃度最低的节点处理请求。

实现代码

@Data
public class Server implements Serializable {

	private String ip;

	private AtomicInteger active;

	public Server(){}

	public Server(String ip){
		this.ip = ip;
		this.active = new AtomicInteger(0);
	}

	public String getIp() {
		// 每分发一个请求时自增一次活跃数
		active.incrementAndGet();
		return ip;
	}
}

public class ActiveServer {

	public static final List<Server> LIST = Arrays.asList(
			new Server("172.168.0.1:8080"),
			new Server("172.168.0.2:8081"),
			new Server("172.168.0.3:8082"),
			new Server("172.168.0.4:8083"),
			new Server("172.168.0.5:8084")
	);

	// 活跃度衰减器->活跃度不为0,每隔 2 秒中衰减一次活跃度
	static {
		new Thread(() -> {
			for (Server server : LIST) {
				if (server.getActive().get() != 0) {
					server.getActive().getAndDecrement();
				}
			}
			try {
				Thread.sleep(2000);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}).start();
	}

	public static String getServer(){
		// 初始化最小活跃数和最小活跃数的节点
		int leastActive = Integer.MAX_VALUE;
		Server leastServer = new Server();
		// 遍历集群中的所有节点
		for (Server server : LIST) {
			// 找出活跃数最小的节点
			if (leastActive > server.getActive().get()){
				leastActive = server.getActive().get();
				leastServer = server;
			}
		}
		// 返回活跃数最小的节点IP
		return leastServer.getIp();
	}

	public static void main(String[] args) {
		Long startTime = System.currentTimeMillis();
		for (int i = 0; i < 10; i++) {
			System.out.println("第"+ i + "个请求：" + getServer());
		}
		System.out.println("10次轮询的耗时："+(System.currentTimeMillis()-startTime));
	}

}

运行的结果

第0个请求：172.168.0.1:8080
第1个请求：172.168.0.2:8081
第2个请求：172.168.0.1:8080
第3个请求：172.168.0.2:8081
第4个请求：172.168.0.3:8082
第5个请求：172.168.0.4:8083
第6个请求：172.168.0.5:8084
第7个请求：172.168.0.1:8080
第8个请求：172.168.0.2:8081
第9个请求：172.168.0.3:8082
10次轮询的耗时：1

原理：

先从注册中心中拉取所有的服务实例，然后找出活跃数最小的节点。
如果只有一个，那么则直接返回对应的实例节点处理本次请求。
如果存在多个，则根据每个节点配置的权重值来决定本次处理请求的具体节点。
如果权重值不同，优先选取权重值最大的实例，作为处理本次请求的节点。
如果存在相同的最大权重值，那么则通过随机的方式选择一个节点提供服务。

最优响应算法

实现代码

@Data
public class Server implements Serializable {

	private String IP;

	public Server(){}
	public Server(String IP) {
		this.IP = IP;
	}

	public String ping(){
		// 生成一个1000~3000之间的随机数
		int random = ThreadLocalRandom.current().nextInt(1000, 2000);
		try {
			// 随机休眠一段时间，模拟不同的响应速度
			Thread.sleep(random);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		// 最后返回自身的IP
		return this.IP;
	}
}

@Slf4j
public class ResponseTime {

	public static final List<Server> LIST = Arrays.asList(
			new Server("172.168.0.1:8080"),
			new Server("172.168.0.2:8081"),
			new Server("172.168.0.3:8082"),
			new Server("172.168.0.4:8083"),
			new Server("172.168.0.5:8084")
	);

	//创建一个定长的线程池，用于去执行ping任务
	static ExecutorService pingServerPool = Executors.newFixedThreadPool(LIST.size());

	public static String getServer() throws InterruptedException {
		CompletableFuture cfAnyOf;
		final Server resultServer = new Server();
		CompletableFuture[] cfs = new CompletableFuture[LIST.size()];

		for (Server server : LIST) {
			int index = LIST.indexOf(server);
			CompletableFuture<String> cf = CompletableFuture.supplyAsync(server::ping,pingServerPool);
			cfs[index] = cf;
		}
		cfAnyOf = CompletableFuture.anyOf(cfs);

		cfAnyOf.thenAccept(resultIP -> {
			System.out.println("最先响应检测请求的节点为：" + resultIP);
			resultServer.setIP((String) resultIP);
		});
		//  阻塞主线程一段时间，防止CompletableFuture退出
		Thread.sleep(3000);

		return resultServer.getIP();
	}


	public static void main(String[] args) throws InterruptedException {
		Long startTime = System.currentTimeMillis();
		for (int i = 0; i < 10; i++) {
			System.out.println("第"+ i + "个请求：" + getServer());
		}
		System.out.println("10次轮询的耗时："+(System.currentTimeMillis()-startTime));
	}
}

运行的结果

最先响应检测请求的节点为：172.168.0.1:8080
第0个请求：172.168.0.1:8080
最先响应检测请求的节点为：172.168.0.1:8080
第1个请求：172.168.0.1:8080
最先响应检测请求的节点为：172.168.0.3:8082
第2个请求：172.168.0.3:8082
最先响应检测请求的节点为：172.168.0.4:8083
第3个请求：172.168.0.4:8083
最先响应检测请求的节点为：172.168.0.1:8080
第4个请求：172.168.0.1:8080
最先响应检测请求的节点为：172.168.0.1:8080
第5个请求：172.168.0.1:8080
最先响应检测请求的节点为：172.168.0.5:8084
第6个请求：172.168.0.5:8084
最先响应检测请求的节点为：172.168.0.4:8083
第7个请求：172.168.0.4:8083
最先响应检测请求的节点为：172.168.0.5:8084
第8个请求：172.168.0.5:8084
最先响应检测请求的节点为：172.168.0.5:8084
第9个请求：172.168.0.5:8084
10次轮询的耗时：30057

并非越智能的算法越好，越是并发高、流量大的场景下，反而选用最基本的算法更合适上面所有算法都是未基于业务逻辑，按照通俗易懂的来弄的

注意：本文归作者所有，未经作者允许，不得转载

常见负载均衡的算法

常见负载均衡的算法

轮询算法

实现代码

运行的结果

随机算法

实现代码

运行的结果

权重算法

实现代码

运行的结果

平滑加权轮询算法

实现代码

运行的结果

一致性哈希算法

哈希环

哈希环映射偏移问题

实现代码

运行的结果

最小活跃数算法

实现代码

运行的结果

最优响应算法

实现代码

运行的结果

全部评论: 0 条

热门文章

最新发布

最新评论