负载均衡在分布式系统中异常地重要，下面主要讲解一下几种负载均衡算法的实现。
先给个基本类，下面的类都是在这个类的基础上实现的
public class IpMap {
public static HashMap<String, Integer> serverMap = new HashMap<>();
static {
serverMap.put("192.168.1.1", 1);
serverMap.put("192.168.1.2", 1);
serverMap.put("192.168.1.3", 3);
serverMap.put("192.168.1.4", 1);
serverMap.put("192.168.1.5", 4);
serverMap.put("192.168.1.6", 1);
serverMap.put("192.168.1.7", 1);
serverMap.put("192.168.1.10", 2);
serverMap.put("192.168.1.11", 1);
serverMap.put("192.168.1.12", 1);
}
}
RoundRobin 轮询法
轮询法，是按公约后的权重设置轮询比率，到达边界之后，继续绕接。主要分为普通轮询和权重轮询
普通轮询法
public class RoundRobin {
// 轮询的位置
private static Integer position = 0;
public static String getString () {
// 本地保留服务端列表，避免服务器上下线导致并发问题
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);
// 获取服务端ip列表
Set<String> keySet = serverMap.keySet();
List<String> serverList = new ArrayList<>(keySet);
String server = null;
// 防止并发问题
synchronized (position) {
// 环形轮询
if (position >= keySet.size()) {
position = 0;
}
server = serverList.get(position);
position++;
}
return server;
}
}
IpMap.serverMap是动态变化的，上下线宕机都是随时随地的。为了避免IpMap.serverMap被多线程修改导致并发问题，特此将列表缓存在本地。但是这样可能会导致服务端列表修改后，不能及时同步，这个时候就需要集群容错策略了。
对于当前轮询的位置变量position，为了保证服务器选择的顺序性，需要在操作的时候加锁或者cas
- 优点：能够做到流量分配的绝对平衡
- 缺点：需要对position加锁，并发吞吐量明显下降
加权轮询法
public class WeightRoundRobin {
private static AtomicInteger position = new AtomicInteger(0);
public static String getString () {
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);
List<String> serverList = new ArrayList<>();
serverMap.forEach((serverIp, weight) -> {
for (int i = 0; i < weight; i++) {
serverList.add(serverIp);
}
});
if (position.get() >= serverList.size()) {
position.set(0);
}
position.getAndIncrement();
return serverList.get(position.get());
}
}
与轮询法类似，但是列表中根据权重会增加serverIp的个数，权重多的访问的就多。
轮询法分析
- 轮询法其实主要还是想打到一种绝对的流量平衡，但是进行了并发控制，会比较影响并发和吞吐量
- 如果某一服务器响应过慢，但是还没达到宕机的地步，这会导致多个请求打到同一台机器上，产生数据倾斜
随机法
随机法主要分为普通随机和权重随机
普通随机法
public class Random {
public static String getString () {
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);
Set<String> keySet = serverMap.keySet();
List<String> serverList = new ArrayList<>(keySet);
java.util.Random random = new java.util.Random();
return serverList.get(random.nextInt(keySet.size()));
}
}
这块其实就是在整体的server列表进行随机。
加权随机法
public class WeightRandom {
public static String getString () {
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);
List<String> serverList = new ArrayList<>();
serverMap.forEach((serverIp, weight) -> {
for (int i = 0; i < weight; i++) {
serverList.add(serverIp);
}
});
Random random = new Random();
return serverList.get(random.nextInt(serverList.size()));
}
}
这块不解释了
随机法分析
- 既然是随机法，可理解为，当请求量比较大的时候，请求分布会相对均匀一些。类似于硬币，当你抛100000次，基本上正反面出现次数是1比1。而且没有加锁，对并发和吞吐会比较友好
- 请求量比较低的时候，可能会出现数据倾斜
- 非对等集群组网，硬件配置较大时，会导致各个节点负载不均匀
哈希法
哈希法主要分为普通哈希和一致性hash
普通哈希法
public class OriginHash {
public static String getString () {
Map<String, Integer> serverMap = new HashMap<>(IpMap.serverMap);
Set<String> keySet = serverMap.keySet();
List<String> serverList = new ArrayList<>(keySet);
String clientIp = "127.0.0.1";
int clientIpHashcode = clientIp.hashCode();
return serverList.get(clientIpHashcode % keySet.size());
}
}
主要是根据客户端某一个数据进行hash，可以为ip，mac等信息
一致性哈希
一致性hash最初是为了memcache提出的负载均衡算法，但是由于该算法优良，性能比较好，所以目前已经用于各种分布式架构上了。
基本概念
一致性hash将整个hash空间组织成一个虚拟的圆环，普通的hash算法可能是对服务器的数量进行取模，而一致性hash是对2^32取模， 也就是说，哈希函数的H值的空间为0-(2^32 - 1)
[站外图片上传中...(image-456ebf-1563700555907)]
整个空间按顺时针组织，0 和 2^32 - 1重合
下面将各个服务端的服务器进行hash，hash的key可以为ip或主机名或mac，这样每台机器能够确定在这个环中的位置，假设四台服务端服务器用ip地址映射到下面的环上
接下来使用如下算法定位数据访问的相应服务器：将数据key（客户端服务器）使用相同的函数hash计算出哈希值，确定在环中的位置，从这个位置沿着顺时针遍历，第一台遇到的服务器就是定位到的服务器
假设有A，B, C, D四个客户端，经过hash后，位置在环上如下位置
通过一致性hash的算法，可以看出，最终A定位在NodeA上，B定位在NodeB上，C定位在NodeC上，D定位在NodeD上。
性质分析
分析一下一致性hash的容错性和可扩展性。假设C不行宕机，客户端ABD都不会受到影响，只有C受到影响。假设增加一台服务器X，如下图所示
其实也只是影响了C一个客户节点。则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。
这个时候考虑如果是普通的hash算法，看下表：
| hashcode | 3个服务端节点编号 | 4个服务端节点编号 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 0 | 3 |
| 4 | 1 | 0 |
| 5 | 2 | 1 |
可以看到，其实全乱了....
虚拟节点
如果一致性hash中节点较少，会产生因为节点分布不均匀的数据倾斜问题。
会导致大部分数据集中在A上，少量定位在B上，为了解决这个问题，引入了虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：
那么虚拟节点其实最终指向的也是实际节点
实现
public class ConsistentHash<T> {
/**
* 节点的复制因子
*/
private int numberOfReplicas;
/**
* 虚拟节点个数
*/
private final SortedMap<Integer, T> circle = new TreeMap<>();
/**
* 初始化节点
* @param numberOfReplicas
* @param nodes
*/
public ConsistentHash (int numberOfReplicas, Collection<T> nodes) {
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}
/**
* 将节点加入环内
* @param node
*/
public void add (T node) {
for (int i = 0; i < numberOfReplicas; i++) {
String nodeStr = node.toString() + i;
System.out.println("nodeStr:" + nodeStr);
int hashCode = nodeStr.hashCode();
System.out.println("hashCode:" + hashCode);
circle.put(hashCode, node);
}
}
/**
* 从环中删除节点
* @param node
*/
public void remove (T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.remove(node.toString() + i);
}
}
/**
* 从环中查找对应的数据
* @param key
* @return
*/
public T get (Object key) {
if (circle.isEmpty()) {
return null;
}
int hash = key.hashCode();
if (!circle.containsKey(hash)) {
// 从环中hash的位置开始，找到值大于hash的列表
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
// 如果为空，说明已经到末尾了，取第一个；如果非空，取最近的第一个节点
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
public long getSize () {
return circle.size();
}
public void testBalance () {
Set<Integer> set = circle.keySet();
SortedSet<Integer> sortedSet = new TreeSet<>(set);
System.out.println(sortedSet);
System.out.println("------------------------------------");
}
public static void main (String[] args) {
Set<String> nodes = new HashSet<>();
nodes.add("a");
nodes.add("b");
nodes.add("c");
ConsistentHash<String> consistentHash = new ConsistentHash<>(2, nodes);
consistentHash.add("d");
System.out.println("hash circle size:" + consistentHash.getSize());
consistentHash.testBalance();
System.out.println(consistentHash.get("a3"));
}
}
其实上面例子中的节点并不是很好，取的a,b,c,d，导致hash的比较集中，但是意思是这样，具体时间尽量避免节点集中，而且虚拟节点要选好散列
服务调用时延
消费者会缓存所有服务提供者的服务调用时延，周期性地计算服务调用平均时延，然后计算每个服务提供者服务调用时延与平均时延的差值，根据差值大小调整权重，尽量保证服务调用时延大的接受更少的请求
粘滞连接
粘滞连接用于有状态的服务，尽可能让客户端总是像同一服务提供者发起服务调用，除非它宕机。但是服务一般都是无状态的，所以很少使用
