最接地气的负载均衡算法(含代码)

回复” 架构 “免费下载一线大厂架构资料

随机算法

从可用的节点中,随机挑选一个节点来访问。 一般通过生成一个随机数来实现

适用场景:

实现比较简单,在请求量远超可用服务节点数量的情况下,各个服务节点被访问的概率基本相同,主要应用在各个服务节点的性能差异不大的情况下。

protected Referer<T> doSelect(Request request) {

List<Referer<T>> referers = getReferers();

int idx = (int) (ThreadLocalRandom.current().nextDouble() * referers.size());

for (int i = 0; i < referers.size(); i++) {

Referer<T> ref = referers.get((i + idx) % referers.size());

if (ref.isAvailable()) {

return ref;

}

}

return null;

}

轮询算法

按照固定的顺序,把可用的服务节点,挨个访问一次。 轮询算法能够保证所有节点被访问到的概率是相同的。

在实现时,轮询算法通常是把所有可用节点放到一个数组里,然后按照数组编号,挨个访问。比如服 务有 10 个节点,放到数组里就是一个大小为 10 的数组,这样的话就可以从序号为 0 的节点开始访问,访问后序号自动加 1,下一次就会访问序号为 1 的节点,以此类推。

适用场景:

跟随机算法类似,各个服务节点被访问的概率也基本相同,也主要应用在各个服务节点性能差异不大的情况下。

protected Referer<T> doSelect(Request request) {

List<Referer<T>> referers = getReferers();

int index = getNextNonNegative();

for (int i = 0; i < referers.size(); i++) {

Referer<T> ref = referers.get((i + index) % referers.size());

if (ref.isAvailable()) {

return ref;

}

}

return null;

}

加权轮询算法

轮询算法能够保证所有节点被访问的概率相同,而加权轮询算法是在此基础上,给每个节点赋予一个 权重,从而使每个节点被访问到的概率不同,权重大的节点被访问的概率就高,权重小的节点被访问的概率就小。

适用场景:

主要被用在服务节点性能差异比较大的情况。比如经常会出现一种情况,因为采购时间 的不同,新的服务节点的性能往往要高于旧的节点,这个时候可以给新的节点设置更高的权重,让它承担更多的请求,充分发挥新节点的性能优势。

protected Referer<T> doSelect(Request request) {

if (holder == emptyHolder) {

return null;

}

RefererListCacheHolder<T> h = this.holder;

Referer<T> r = h.next();

if (!r.isAvailable()) {

int retryTimes = getReferers().size() - 1;

for (int i = 0; i < retryTimes; i++) {

r = h.next();

if (r.isAvailable()) {

break;

}

}

}

if (r.isAvailable()) {

return r;

} else {

noAvailableReferer();

return null;

}

}

最少活跃连接算法

因为不同节点处理请求的速 度不同,使得同一个服务消费者同每一个节点的连接数都不相同。 连接数大的节点,可以认为是处理 请求慢,而连接数小的节点,可以认为是处理请求快。 所以在挑选节点时,可以以连接数为依据,选 择连接数最少的节点访问。

适用场景

与加权轮询算法预先定义好每个节点的访问权重不同,采用最少活跃连接算 法,客户端同服务端节点的连接数是在时刻变化的,理论上连接数越少代表此时服务端节点越空 闲,选择最空闲的节点发起请求,能获取更快的响应速度。 尤其在服务端节点性能差异较大,而 又不好做到预先定义权重时,采用最少活跃连接算法是比较好的选择。

protected Referer<T> doSelect(Request request) {

List<Referer<T>> referers = getReferers();

int refererSize = referers.size();

int startIndex = ThreadLocalRandom.current().nextInt(refererSize);

int currentCursor = 0;

int currentAvailableCursor = 0;

Referer<T> referer = null;

while (currentAvailableCursor < MAX_REFERER_COUNT && currentCursor < refererSize) {

Referer<T> temp = referers.get((startIndex + currentCursor) % refererSize);

currentCursor++;

if (!temp.isAvailable()) {

continue;

}

currentAvailableCursor++;

if (referer == null) {

referer = temp;

} else {

if (compare(referer, temp) > 0) {

referer = temp;

}

}

}

return referer;

}

一致性Hash算法

一致性 hash 算法,是通过某个 hash 函数,把同一个来源的请求都映射到同一个节点上。 一致性 hash 算法最大的特点就是同一个来源的请求,只会映射到同一个节点上,可以说是具有记忆功能。 只有当 这个 节点不可用时,请求才会被分配到相邻的可用节点上。

适用场景:

因为它能够保证同一个客户端的请求始终访问同一个服务节点,所以适合服务端节点处理不同客户端请求差异较大的场景。比如服务端缓存里保存着客户端的请求结果,如果同一客户端一直访问一个服务节点,那么就可以一直从缓存中获取数据。

protected Referer<T> doSelect(Request request) {

int hash = getHash(request);

Referer<T> ref;

for (int i = 0; i < getReferers().size(); i++) {

ref = consistentHashReferers.get((hash + i) % consistentHashReferers.size());

if (ref.isAvailable()) {

return ref;

}

}

return null;

}


private int getHash(Request request) {

int hashcode;

if (request.getArguments() == null || request.getArguments().length == 0) {

hashcode = request.hashCode();

} else {

hashcode = Arrays.hashCode(request.getArguments());

}

return MathUtil.getNonNegative(hashcode);

}

精彩文章

END

我们热衷于收集&分享高并发、系统架构、微服务、消息中间件、 RPC框架、高性能缓存、搜索、分布式数据框架、分布式协同服务、分布式配置中心、中台架构、领域驱动设计、系统监控、系统稳定性等技术知识。

https://github.com/aalansehaiyang/technology-talk

活到老、学到老,用技术普惠世界

关注 【微观技术】

共创世界,探寻人生价值

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章