解密负载均衡技术和负载均衡算法
来源 | OSCHINA 社区
作者 | 京东云开发者-纪卓志
原文链接：https://my.oschina.net/u/4090830/blog/5590456
什么是负载均衡技术
常见负载均衡算法介绍
Round Robin（轮询负载均衡算法）
Weighted Round Robin（加权轮询负载均衡算法）
加权轮询负载均衡算法描述的是在一段时间内负载的分布情况，不同的加权轮询负载均衡算法可能会产生不同的选择序列，不应该对处理下一次负载的服务器进行假设。
Least Connections（最少连接负载均衡算法）
Weighted Least Connections（加权最少连接负载均衡算法）
Resource Based（基于资源的负载均衡算法）
Fixed Weighting（固定权重负载均衡算法）
Weighted Response Time（加权响应时间负载均衡算法）
Source IP Hash（源地址哈希负载均衡算法）
服务端研发经常接触的数据库事务就适用于此场景
Consistent Hash（一致性哈希负载均衡算法）
常见负载均衡算法实现
Round Robin（轮询负载均衡算法）
public class RoundRobinLoadBalancer {
private final List instances;
private int position;
public RoundRobinLoadBalancer(List instances) {
this.instances = instances;
this.position = ThreadLocalRandom.current().nextInt(instances.size());
}
public ServiceInstance peek(HttpServletRequest request) {
int peeked = (position++) & Integer.MAX_VALUE;
return instances.get(peeked % instances.size());
}
}
当我们初始化位置时，需要将其设置为一个随机值，避免多个负载均衡器同时请求同一个服务器，造成服务器的瞬时压力
在位置自增时，需要忽略符号位，因为 Java 没有无符号整数，所以当位置的值超出整型最大值时会变成负值导致抛出异常。至于为什么不能使用绝对值，是因为整型的最小值没有对应的绝对值，得到的依旧是负值 (Spring Cloud #1074)
Weighted Round Robin（加权轮询负载均衡算法）
数组展开方式
public class WeightedLoadBalancer {
private final List instances;
private int position;
public WeightedLoadBalancer(List instances) {
this.instances = expandByWeight(instances);
}
public ServiceInstance peek(HttpServletRequest request) {
int peeked = (position++) & Integer.MAX_VALUE;
return instances.get(peeked % instances.size());
}
private List expandByWeight(List instances) {
List newInstances = new ArrayList<>();
for (ServiceInstance instance : instances) {
int bound = instance.getWeight();
for (int w = 0; weight < bound; weight++) {
newInstances.add(instance);
}
}
Collections.shuffle(newInstances);
return newInstances;
}
}
当实例按权重展开成数组的时候，可能会出现实例权重都很大，但是它们的最大公约数不为 1，这个时候可以使用最大公约数来减少展开后的数组大小。因为最大公约数的诸多限制，例如任意自然数 N 与 N+1 互质，任意自然数 N 与 1 互质，所以很容易出现优化失败的情况，因此本示例并未给出，感兴趣的可以去看 Spring Cloud 相关 PR（Spring Cloud #1140）
在实例按权重展开成数组后，需要对得到的数组进行洗牌，以保证流量尽可能均匀，避免连续请求相同实例（Java 中实现的洗牌算法是 Fisher-Yates 算法，其他语言可以自行实现）
因为是在构建负载均衡器的时候按权重展开成数组的，所以在负载均衡器构建完成后无法再改变实例的权值，对于频繁动态变更权重的场景不适用
上界收敛选择方式
public class WeightedLoadBalancer {
private final List instances;
private final int max;
private final int gcd;
private int bound;
private int position;
public WeightedLoadBalancer(List instances) {
this.instances = instances;
this.max = calculateMaxByWeight(instances);
this.gcd = calculateGcdByWeight(instances);
this.position = ThreadLocalRandom.current().nextInt(instances.size());
}
public ServiceInstance peek(HttpServletRequest request) {
if (bound == 0) {
bound = max;
}
while (instances.size() > 0) {
for (int peeked = position; peeked < instances.size(); peeked++) {
ServiceInstance instance = instances.get(peeked);
if (instance.getWeight() >= bound) {
position = peeked + 1;
return instance;
}
}
position = 0;
bound = bound - gcd;
}
return null;
}
private static int calculateMaxByWeight(List instances) {
int max = 0;
for (ServiceInstance instance : instances) {
if (instance.getWeight() > max) {
max = instance.getWeight();
}
}
return max;
}
private static int calculateGcdByWeight(List instances) {
int gcd = 0;
for (ServiceInstance instance : instances) {
gcd = gcd(gcd, instance.getWeight());
}
return gcd;
}
private static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
}
如果是短频率请求，将会一直访问高权重实例，导致在短时间窗口内负载看起来并不均匀。这个可以通过改变方向，从下界向上界逼近来解决。
每一轮后降低上界的值可以取所有权重的最大公约数，因为如果每次下降 1 的话，中间这些轮会反复请求权重最高的那些实例，导致负载不均衡。
虽然最大公约数可以减少下降次数，但是如果权重相差非常多，并且所有元素都是互质的（n 与 n+1 互质，任意自然数 n 与 1 互质，在实践中非常容易出现），那么在上界下降的过程中将会带来很多空转。这个可以参考广度优先遍历的思想，使用先入先出的队列来减少空转。
与数组展开方式遇到的问题相同，因为是在构建负载均衡器的时候计算最大公约数的值，所以对于频繁动态变更权重的场景依旧会有很大的性能开销，但是相较于数组展开方式可以避免频繁动态分配数组导致的性能与内存碎片问题
权重轮转实现
在 NGINX 中又叫做平滑加权负载均衡（Smooth Weighted Load Balancing，SWRR）。
public class WeightedLoadBalancer {
private final List instances;
public WeightedLoadBalancer(List instances) {
this.instances = instances;
}
public ServiceInstance peek(HttpServletRequest request) {
ServiceInstance best = null;
int total = 0;
for (ServiceInstance instance : instances) {
total += instance.getWeight();
instance.setCurrentWeight(instance.getCurrentWeight() + instance.getWeight());
if (best == null || instance.getCurrentWeight() > best.getCurrentWeight()) {
best = instance;
}
}
if (best != null) {
best.setCurrentWeight(best.getCurrentWeight() - total);
}
return best;
}
}
权重轮转非常适合实例变化频率非常高的集合，因为它不需要提前构建数据结构
权重轮转实现的效率与实例数量相关，时间复杂度是 O (n)，当集群服务器数量非常大时需要限制每次参与选择的服务器数量（Spring Cloud #1111）
权重轮转实现需要修改服务器实例的数据结构，当服务实例是由其他机构提供时无法使用此实现
EDF（Earliest Deadline First）实现
public class WeightedLoadBalancer {
private final PriorityQueue entries;
public WeightedLoadBalancer(List instances) {
this.entries = instances.stream().map(EdfEntry::new).collect(Collectors.toCollection(PriorityQueue::new));
}
public ServiceInstance peek(HttpServletRequest request) {
EdfEntry entry = entries.poll();
if (entry == null) {
return null;
}
ServiceInstance instance = entry.instance;
entry.deadline = entry.deadline + 1.0 / instance.getWeight();
entries.add(entry);
return instance;
}
private static class EdfEntry implements Comparable {
final ServiceInstance instance;
double deadline;
EdfEntry(ServiceInstance instance) {
this.instance = instance;
this.deadline = 1.0 / instance.getWeight();
}
@Override
public int compareTo(EdfEntry o) {
return Double.compare(deadline, o.deadline);
}
}
}
Least Connections（最少连接负载均衡算法）
遍历比较方式
public class LeastConnectionLoadBalancer {
private final List instances;
public LeastConnectionLoadBalancer(List instances) {
this.instances = instances;
}
public ServiceInstance peek(HttpServletRequest request) {
ServiceInstance best = null;
for (ServiceInstance instance : instances) {
if (best == null || instance.getConnections() < best.getConnections()) {
best = instance;
}
}
if (best != null) {
best.setConnections(best.getConnections() + 1);
}
return best;
}
}
public class LeastConnectionLoadBalancer {
private final PriorityQueue instances;
public LeastConnectionLoadBalancer(List instances) {
this.instances = instances.stream().collect(toCollection(
() -> new PriorityQueue<>(comparingInt(ServiceInstance::getConnections))));
}
public ServiceInstance peek(HttpServletRequest request) {
ServiceInstance best = instances.poll();
if (best == null) {
return null;
}
best.setConnections(best.getConnections() + 1);
return best;
}
}
Weighted Least Connections（加权最少连接负载均衡算法）
加权最少连接负载均衡算法的实现方式与最少连接负载均衡算法相同，只是在计算时增加了权重相关的参数
遍历比较方式
public class LeastConnectionLoadBalancer {
private final List instances;
public LeastConnectionLoadBalancer(List instances) {
this.instances = instances;
}
public ServiceInstance peek(HttpServletRequest request) {
ServiceInstance best = null;
for (ServiceInstance instance : instances) {
if (best == null || instance.getConnections() * best.getWeight() < best.getConnections() * instance.getWeight()) {
best = instance;
}
}
if (best != null) {
best.setConnections(best.getConnections() + 1);
}
return best;
}
}
Tips，在不等式中 a/b < c/d 与 ad < bc 等价，并且可以避免除法带来的性能与精度问题
堆维护方式
public class LeastConnectionLoadBalancer {
private final PriorityQueue instances;
public LeastConnectionLoadBalancer(List instances) {
this.instances = instances.stream().collect(toCollection(
() -> new PriorityQueue<>(comparingDouble(ServiceInstance::getWeightedConnections))));
}
public ServiceInstance peek(HttpServletRequest request) {
ServiceInstance best = instances.poll();
if (best == null) {
return null;
}
best.setConnections(best.getConnections() + 1);
best.setWeightedConnections(1.0 * best.getConnections() / best.getWeight());
return best;
}
}
Source IP Hash（源地址哈希负载均衡算法）
public class IpHashLoadBalancer {
private final List instances;
public IpHashLoadBalancer(List instances) {
this.instances = instances;
}
public ServiceInstance peek(HttpServletRequest request) {
int h = hashCode(request);
return instances.get(h % instances.size());
}
private int hashCode(HttpServletRequest request) {
String xForwardedFor = request.getHeader("X-Forwarded-For");
if (xForwardedFor != null) {
return xForwardedFor.hashCode();
} else {
return request.getRemoteAddr().hashCode();
}
}
}
面向公网提供服务的负载均衡器前面可能会经过任意多层反向代理服务器，为了获取到真实的源地址，需要先获取 X-Forwarded-For 头部，如果该头部不存在再去获取 TCP 连接的源地址
负载均衡技术扩展
服务注册表与发现（Service Registry and Service Discovery）
健康检查（Health Check）
对于网络层负载均衡器（也叫做 NLB 或 L4LB），通过建立 TCP 连接，根据是否能够成功建立连接以及建立连接所需要的时间来确定成员服务器的状态。
对于应用层负载均衡器（也叫做 ALB 或 L7LB），通过发送应用层协议（不只是 HTTP 协议）定义的用于健康检查的请求报文，并根据响应报文内容以及整个请求从建立连接到完整收到所有响应所花费的时间来确定成员服务器的状态。
慢启动（Slow Start）
总结
往期推荐
NVIDIA尝试使用SPARK语言取代C语言
微软贡献Linux内核代码，可运行多个Windows
微软在 Windows 11 的开始菜单嵌入广告
微信扫码关注该文公众号作者
戳这里提交新闻线索和高质量文章给我们。
来源: qq
点击查看作者最近其他文章