专栏首页微观技术最接地气的负载均衡算法(含代码)

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

随机算法

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

适用场景:

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

 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);
}

本文分享自微信公众号 - 微观技术(weiguanjishu),作者:微观技术

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一文读懂Spring Boot各模块组件依赖关系

    spring boot 作为一款开箱即用的框架,在市场上有很高的流行度。但内部依赖错踪复杂,每个模块都有自己专属职责,同时又可以做为其他模块的补充,具有很强的扩...

    用户7676729
  • 快速上手Spring-Data-Redis

    Spring Data Redis 是 Spring Data的一个子项目,主要用于操作redis,和Spring 生态结合的很好,它提供了低级别(RedisT...

    用户7676729
  • 如何通过Binlog来实现不同系统间数据同步

    互联网时代除了业务迭代速度快,还有就是数据增速也比较快。单应用、单实例、单数据库的时代早已不复返。现在,作为技术研发,如果参与的项目没有用到分库分表,都不好意说...

    用户7676729
  • B+树,索引树

    时隔一年,我又想起当初看数据库时,看到的B+树,就是数据库的索引使用的数据结构。再整理一下,看看自己没有忘记很多吧。

    烟草的香味
  • 算法原理系列:2-3查找树

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    用户1147447
  • 很短 | 图解 Raft 算法

    想象一下,我们有一个单节点系统,且作为数据库服务器,然后存储了一个值(假设为X)。然后,有一个客户端往服务器发送了一个值(假设为8)。只要服务器接受到这个值即可...

    芋道源码
  • MongoDB 副本集运维策略

    本文聊一聊 MongoDB 副本集运维窗口期的操作策略,最大程度地减少主节点不可用的时间。

    小码甲
  • (2)MongoDB副本集自动故障转移 全流程原理

    前文我们搭建MongoDB三成员副本集,了解集群基本特性,今天我们围绕下图聊一聊背后的细节。

    小码甲
  • 敖丙带你杀死面试梦魇-红黑树【图解】

    很多人会觉得这个知识点太难,不想花太多功夫去了解,也有人会认为这个数据结构在日常开发中使用的很少,因此没必要多做掌握。

    敖丙
  • 动画 | 什么是2-3-4树?

    画了一系列树的动画,从二分搜索树,到AVL树,再到2-3树,再到基于2-3树的红黑树,都可以发现这些树都跟二叉查找树很像啊。

    我脱下短袖

扫码关注云+社区

领取腾讯云代金券