首页 体育 教育 财经 社会 娱乐 军事 国内 科技 互联网 房产 国际 女人 汽车 游戏

自古帝王多短命,假如皇帝也懂负载均衡算法...

2020-05-21

咱们都知道古代皇帝各个都是后宫佳丽三千,而皇帝身上都天然的带着雨露均沾的精力,不想独自的宠爱一人!

图片来自 Pexels

弱水三千,又怎舍得只取一瓢饮?据传皇帝们晚上睡觉个个都怕冷,因而每晚都需求有人侍寝,那么这么多后宫,该翻谁牌子、怎样分配侍寝名额呢?

还甭说,皇帝行房事竟还挺考究的!早在《春秋》就有记载“晦阴惑疾,明谣心疾,以辟六气”。

九嫔以下,每九人中进御一人,八十一女御占九个晚上,世妇二十七人占三个晚上,九嫔占一个晚上,三夫人占一个晚上,以上共十四夜,皇后独占一个晚上,共十五夜。上半个月按上述组织进御,下半个月从十六日开端,由皇后起,再御九嫔、世妇、女御,与月亮由盛而衰相对应......

不同朝代的皇帝也有不同宠幸妃子的办法,闻名的有羊车望幸、掷筛侍寝、蝶幸、翻牌悬灯等等。

不过在我看来,假设皇帝懂负载均衡算法的话,大可不必这么折腾,一套算法便可搞定终身侍寝大事!因而咱们今日来介绍几种常用的负载均衡算法及代码完成!

先看下文章的纲要:

轮询算法 加权轮询算法 随机算法 加权随机算法 源地址 hash 算法 一致性 hash 算法 轮询算法

据史料记载,乾隆终身妃嫔就有 42 人,还不算大明湖畔的夏雨荷等鄙人江南时分留下的情。

图片来自 Pexels

弱水三千,又怎舍得只取一瓢饮?据传皇帝们晚上睡觉个个都怕冷,因而每晚都需求有人侍寝,那么这么多后宫,该翻谁牌子、怎样分配侍寝名额呢?

还甭说,皇帝行房事竟还挺考究的!早在《春秋》就有记载“晦阴惑疾,明谣心疾,以辟六气”。

九嫔以下,每九人中进御一人,八十一女御占九个晚上,世妇二十七人占三个晚上,九嫔占一个晚上,三夫人占一个晚上,以上共十四夜,皇后独占一个晚上,共十五夜。上半个月按上述组织进御,下半个月从十六日开端,由皇后起,再御九嫔、世妇、女御,与月亮由盛而衰相对应......

不同朝代的皇帝也有不同宠幸妃子的办法,闻名的有羊车望幸、掷筛侍寝、蝶幸、翻牌悬灯等等。

不过在我看来,假设皇帝懂负载均衡算法的话,大可不必这么折腾,一套算法便可搞定终身侍寝大事!因而咱们今日来介绍几种常用的负载均衡算法及代码完成!

先看下文章的纲要:

据史料记载,乾隆终身妃嫔就有 42 人,还不算大明湖畔的夏雨荷等鄙人江南时分留下的情。

假定在某个时期内,皇阿玛最宠幸的有令妃、娴妃、高贵妃、纯妃四位。那一般的轮询算法怎样去挑选呢?

咱们先界说一个妃子调集如下:

/** 
 * *一切妃子调集 
public  static final List String  PRINCESS_LIST = Arrays.asList; 

然后从列表中轮询侍寝的妃子,用一个变量 index 去记载轮询的方位。

// 记载循环的方位 
private static  Integer  index = 0; 
public  static void main { 
    for  { 
        System.out.println); 
    } 
private static String getPrincess { 
    // 超越数组巨细需求归零 
    if ) { 
        index = 0; 
    } 
    String princess = PrincessConfig.PRINCESS_LIST.get; 
    index++; 
    return princess; 

输出成果就不贴出来了。该算法的特色便是简略、简略、简略!可是也存在很大缺陷!

假设皇帝更宠爱令妃,想让她侍寝的概率更高呢?那就需求用到下面的加权轮询算法!

加权轮询便是能够片面的给每个妃子设置一个喜爱值,以操控被选中的概率,因而咱们需求界说如下的装备:

/** 
 * *一切妃子调集 
public  static final Map String,  Integer  PRINCESS_MAP = new LinkedHashMap String,  Integer  { 
    { 
        put; 
        put; 
        put; 
        put; 
    } 

这儿的装备就不再是简略的一个调集,每个妃子都对应了一个权重值,那轮询的时分怎样依据这个值去进步被选中的概率呢?

下面咱们来讲三种比较常见的完成。

加权轮询完成一

咱们的思路是把这个 map 的 key依据权重值转存到一个 list 中,然后再去轮询这个 list,假设权重值为 5,那就在 list 中添加 5 条相同的记载!

然后咱们去遍历这个 list,这样权重值越高,在 list 中呈现的概率就越高,被轮询中的概率也就越高!

// 记载循环的方位 
private static  Integer  index = 0; 
public  static void main { 
   for  { 
       System.out.println); 
private static String getPrincess1 { 
   // 遍历map放入到list中 
   List String  princessList = new ArrayList String  
   for ) { 
       int weight = PrincessConfig.PRINCESS_MAP.get; 
       // 依据权重值重复放入到一个list中 
       for  { 
           princessList.add; 
      } 
   if ) { 
       index = 0; 
   String princess = princessList.get; 
   index++; 
   return princess; 

输出成果如下:

该加权轮询算法比较简略,比较简单完成。可是也有个问题,咱们装备的权重值是 5、1、3、2,那咱们是不是也能够装备成 50、10、30、20 呢?

那依照上面的办法,咱们是不是就需求把相同的元素往 list 里边放几百个呢?这显然是比较不合理且耗内存的!

加权轮询完成二

依据上面的算法存在的问题,咱们考虑用相似占比的办法来处理。

比方咱们装备的权重值为 50、10、30、20,那在横坐标上表明便是 0_____50_60__80__110。

咱们仍是用一个 index 去记载轮询的方位,假设 index 在 0~50 之间就代表第一个妃子被选中,假设在 50~60 之间就代表第二个妃子被选中......

咱们看详细代码完成:

// 记载循环的方位 
private static  Integer indexInteger = 0; 
public  static void main { 
   for  { 
       System.out.println); 
private static String getPrincess2 { 
   //记载总权重值 
   int totalWeight = 0; 
   for ) { 
       int weight = PrincessConfig.PRINCESS_MAP.get; 
       totalWeight += weight; 
   // 归零 
   if  { 
       indexInteger = 0; 
   int  index = indexInteger; 
   String result = null; 
   for ) { 
       int weight = PrincessConfig.PRINCESS_MAP.get; 
       // 落在当时区间 直接回来 
       if  { 
           result = princess; 
           break; 
      } 
       // 没有落在当时区间 持续循环 
       index =  index - weight; 
   indexInteger++; 
   return result; 

输出成果与上面的办法一毛相同:

该加权轮询算法比较简略,比较简单完成。可是也有个问题,咱们装备的权重值是 5、1、3、2,那咱们是不是也能够装备成 50、10、30、20 呢?

那依照上面的办法,咱们是不是就需求把相同的元素往 list 里边放几百个呢?这显然是比较不合理且耗内存的!

依据上面的算法存在的问题,咱们考虑用相似占比的办法来处理。

比方咱们装备的权重值为 50、10、30、20,那在横坐标上表明便是 0_____50_60__80__110。

咱们仍是用一个 index 去记载轮询的方位,假设 index 在 0~50 之间就代表第一个妃子被选中,假设在 50~60 之间就代表第二个妃子被选中......

咱们看详细代码完成:

// 记载循环的方位 
private static  Integer indexInteger = 0; 
public  static void main { 
   for  { 
       System.out.println); 
private static String getPrincess2 { 
   //记载总权重值 
   int totalWeight = 0; 
   for ) { 
       int weight = PrincessConfig.PRINCESS_MAP.get; 
       totalWeight += weight; 
   // 归零 
   if  { 
       indexInteger = 0; 
   int  index = indexInteger; 
   String result = null; 
   for ) { 
       int weight = PrincessConfig.PRINCESS_MAP.get; 
       // 落在当时区间 直接回来 
       if  { 
           result = princess; 
           break; 
      } 
       // 没有落在当时区间 持续循环 
       index =  index - weight; 
   indexInteger++; 
   return result; 

输出成果与上面的办法一毛相同:

该加权轮询算法略杂乱于第一种,可是这两种完成都存在的一起问题是,依照咱们现在的装备去轮询会接连 5 次令妃、再 1 次娴妃、再 3 次高贵妃......

接连 5 次!就算皇阿玛再喜爱令妃,怕是令妃也有点吃不消!用核算机术语说也便是负载不是很均衡!

滑润加权轮询算法便是为了处理上面负载不均衡的状况的,该算法完成起来相比照较杂乱!

每个妃子不只有一个权重值,还有一个会改变的动态权重值来辅佐核算。

动态权重值核算逻辑如下:

这样看或许会有点不是很了解,咱们来做个核算,假定咱们仍是有如下装备:

/** 
 * *一切妃子调集 
public  static final Map String,  Integer  PRINCESS_MAP = new LinkedHashMap String,  Integer  { 
    { 
        put; 
        put; 
        put; 
        put; 
    } 

在上面的装备中总权重值 totalWeight=5+1+3+2 等于 11。

①依照上面算法的第一点,在第一次轮询方针之前她们的 dynamicWeight 都是0。

因而四位妃子的 weight 和 dynamicWeight 值如下:

②依照上面算法的第二点,在第一次轮询选中方针的时分 dynamicWeight=dynamicWeight+weight。

改变后四位妃子的 weight 和 dynamicWeight 值如下:

②依照上面算法的第二点,在第一次轮询选中方针的时分 dynamicWeight=dynamicWeight+weight。

改变后四位妃子的 weight 和 dynamicWeight 值如下:

③依照上面算法的第三点,然后找最大的 dynamicWeight,也便是 5,因而第一次轮询选中的便是令妃。

④依照上面算法的第四点,令妃的 dynamicWeight 需求减去 totalWeight。

改变后四位妃子的 weight 和 dynamicWeight 值如下:

然后第2次轮询的时分又需求依照算法的第一点设置 dynamicWeight。

设置后四位妃子的 weight 和 dynamicWeight 值如下:

然后第2次轮询的时分又需求依照算法的第一点设置 dynamicWeight。

设置后四位妃子的 weight 和 dynamicWeight 值如下:

就这样一向依照算法处理下去,轮询完 11 次后,一切妃子的 dynamicWeight 又会悉数变为 0......

假设咱们仍然仍是有点含糊,咱们只能上代码为敬了!咱们需求先界说一个实体,来寄存每个妃子及对应的 weight 及 dynamicWeight 特点:

/** 
 * *权重实体 
 * @author sullivan 
public class PrincessWeight { 
    private String princess; 
    private Integer weight; 
    private Integer dynamicWeight; 
    public PrincessWeight { 
        super; 
        this.princess = princess; 
        this.weight = weight; 
        this.dynamicWeight = dynamicWeight; 
    } 

然后界说两个大局的方针寄存方针:

// 每个妃子及对应的权重实体 
private static Map String, PrincessWeight  weightMap = new HashMap String, PrincessWeight  
// 总权重值 
private static  int totalWeight = 0; 

再进行算法的完成:

private static String getPrincess {     
    // 初始化妃子及对应的权重实体 
    if ) { 
        //将装备初始化到map中去 
        for ) { 
            // 算法的第一点:初始dynamicWeight为0 
            weightMap.put, 0)); 
            totalWeight += PrincessConfig.PRINCESS_MAP.get; 
        } 
    } 
    // 算法的第二点:设置currentWeight=设置weight+currentWeight 
    for ) { 
        weight.setDynamicWeight + weight.getDynamicWeight); 
    } 
    // 算法的第三点:寻觅最大的currentWeight 
    PrincessWeight maxPrincessWeight = null; 
    for ) { 
        if  > maxPrincessWeight.getDynamicWeight) { 
            maxPrincessWeight = weight; 
        } 
    } 
    // 算法的第四点:最大的dynamicWeight = dynamicWeight-totalWeight 
    maxPrincessWeight.setDynamicWeight - totalWeight); 
    return maxPrincessWeight.getPrincess; 

终究输出如下:

这样通过 11 次轮询,令妃相同呈现了 5 次,可是显着不会再像之前算法那样接连呈现了,会均衡得多!!!假设还有不清楚的,能够去文末的 Github 地址上下载代码自己调试及了解!

随机算法

滑润加权轮询算法能很好的进行负载了!可是皇阿玛又说了,依照轮询算法,我自己都能够推出来每晚侍寝的妃子,不影响不影响。

皇帝嘛,总喜爱来些新鲜的影响的咱们也能够了解!还好咱们有随机算法能够处理,每晚都是随机选一个,让皇帝无法提早估测,给皇帝满足的影响感!

咱们仍然先界说一个妃子调集如下:

/** 
 * *一切妃子调集 
public  static final List String  PRINCESS_LIST = Arrays.asList; 

然后使用随机函数去挑选一个方针:

public  static void main { 
    for  { 
        for  { 
            System.out.println); 
        } 
    } 
private static String getPrincess { 
    List String  princessList = new ArrayList String  
    for ) { 
        int weight = PrincessConfig.PRINCESS_MAP.get; 
        for  { 
            princessList.add; 
        } 
    } 
    Random rd = new Random; 
    int  index = rd.nextInt); 
    return princessList.get; 
加权随机完成二

加权随机完成二与上面的加权轮询完成二的思路简直一模相同,这儿也就直接上代码了:

public  static void main { 
    for  { 
        System.out.println); 
    } 
private static String getPrincess2 { 
    List String  princessList = new ArrayList String  
    int totalWeight = 0; 
    for ) { 
        int weight = PrincessConfig.PRINCESS_MAP.get; 
        totalWeight += weight; 
        for  { 
            princessList.add; 
        } 
    } 
    Random rd = new Random; 
    int  index = rd.nextInt; 
    String result = null; 
    for ) { 
        int weight = PrincessConfig.PRINCESS_MAP.get; 
        // 落在当时区间 直接回来 
        if  { 
            result = princess; 
            break; 
        } 
        // 没有落在当时区间 持续循环 
        index =  index - weight; 
    } 
    return result; 

源地址 hash 算法

咱们的工作中开发体系很常见的一个需求便是需求登录后才干拜访,这就会涉及到 session!

假设咱们没有做 session 同享,那登录后的 session 信息只会存在咱们调用登录接口的那台服务器上!

依照前面的轮询算法或许随机算法,咱们同一客户端的屡次恳求就会落在不同的服务器上,这样就会导致部分接口没权限拜访!

因而咱们需求同一个客户端屡次的恳求落在同一台服务器上,这儿常见的一种做法是对源地址进行 hash!

到这儿咱们也得让咱们的皇阿玛歇会儿了,回到咱们正常的事务场景中。假定咱们有服务器装备如下:

/** 
     * *一切服务器调集 
     */ 
    public  static final List String  SERVER_IP_LIST = Arrays.asList; 

客户端拜访的 ip 我也模拟了一个调集:

/** 
     * *客户端ip 
     */ 
    public  static final List String  CLIENT_IP_LIST = Arrays.asList; 

源地址 hash 算法的思路便是对客户端的 ip 进行 hash,然后用 hash 值与服务器的数量进行取模,得到需求拜访的服务器的 ip。只需客户端 ip 不变,那 hash 后的值便是固定的!

完成如下:

public  static void main { 
        for  { 
            int  index = Math. abs) % PrincessConfig.SERVER_IP_LIST. size; 
            String serverIp = PrincessConfig.SERVER_IP_LIST.get; 
            System.out.println; 
        } 
    } 

终究输出如下:

这样通过 11 次轮询,令妃相同呈现了 5 次,可是显着不会再像之前算法那样接连呈现了,会均衡得多!!!假设还有不清楚的,能够去文末的 Github 地址上下载代码自己调试及了解!

滑润加权轮询算法能很好的进行负载了!可是皇阿玛又说了,依照轮询算法,我自己都能够推出来每晚侍寝的妃子,不影响不影响。

皇帝嘛,总喜爱来些新鲜的影响的咱们也能够了解!还好咱们有随机算法能够处理,每晚都是随机选一个,让皇帝无法提早估测,给皇帝满足的影响感!

咱们仍然先界说一个妃子调集如下:

/** 
 * *一切妃子调集 
public  static final List String  PRINCESS_LIST = Arrays.asList; 

然后使用随机函数去挑选一个方针:

public  static void main { 
    for  { 
        for  { 
            System.out.println); 
        } 
    } 
private static String getPrincess { 
    List String  princessList = new ArrayList String  
    for ) { 
        int weight = PrincessConfig.PRINCESS_MAP.get; 
        for  { 
            princessList.add; 
        } 
    } 
    Random rd = new Random; 
    int  index = rd.nextInt); 
    return princessList.get; 

加权随机完成二与上面的加权轮询完成二的思路简直一模相同,这儿也就直接上代码了:

public  static void main { 
    for  { 
        System.out.println); 
    } 
private static String getPrincess2 { 
    List String  princessList = new ArrayList String  
    int totalWeight = 0; 
    for ) { 
        int weight = PrincessConfig.PRINCESS_MAP.get; 
        totalWeight += weight; 
        for  { 
            princessList.add; 
        } 
    } 
    Random rd = new Random; 
    int  index = rd.nextInt; 
    String result = null; 
    for ) { 
        int weight = PrincessConfig.PRINCESS_MAP.get; 
        // 落在当时区间 直接回来 
        if  { 
            result = princess; 
            break; 
        } 
        // 没有落在当时区间 持续循环 
        index =  index - weight; 
    } 
    return result; 

源地址 hash 算法

咱们的工作中开发体系很常见的一个需求便是需求登录后才干拜访,这就会涉及到 session!

假设咱们没有做 session 同享,那登录后的 session 信息只会存在咱们调用登录接口的那台服务器上!

依照前面的轮询算法或许随机算法,咱们同一客户端的屡次恳求就会落在不同的服务器上,这样就会导致部分接口没权限拜访!

因而咱们需求同一个客户端屡次的恳求落在同一台服务器上,这儿常见的一种做法是对源地址进行 hash!

到这儿咱们也得让咱们的皇阿玛歇会儿了,回到咱们正常的事务场景中。假定咱们有服务器装备如下:

/** 
     * *一切服务器调集 
     */ 
    public  static final List String  SERVER_IP_LIST = Arrays.asList; 

客户端拜访的 ip 我也模拟了一个调集:

/** 
     * *客户端ip 
     */ 
    public  static final List String  CLIENT_IP_LIST = Arrays.asList; 

源地址 hash 算法的思路便是对客户端的 ip 进行 hash,然后用 hash 值与服务器的数量进行取模,得到需求拜访的服务器的 ip。只需客户端 ip 不变,那 hash 后的值便是固定的!

完成如下:

public  static void main { 
        for  { 
            int  index = Math. abs) % PrincessConfig.SERVER_IP_LIST. size; 
            String serverIp = PrincessConfig.SERVER_IP_LIST.get; 
            System.out.println; 
        } 
    } 

终究输出如下:

这样不论履行多少次,相同的客户端 ip 恳求得到的服务器地址都是相同的!

这种完成很简略,但也很软弱!由于咱们服务器的数量是或许改变的,今日下线一台机器明日添加一台机器是很常见的!

服务器数量一旦改变,那源地址 hash 之后取模的值或许就改变了,获取到的服务器的 ip 天然就也会发生改变!

比方咱们服务器去掉一台 192.168.4.10 的机器再看下输出成果:

比照输出成果咱们就能看到,影响简直是大局的!那咱们能不能有一种计划就算是服务器数量改变,也能削减受影响的客户端呢?这就需求用到下面的一致性 hash 算法!

一致性 hash 算法

加权轮询算法完成二中咱们讲到过把权重值转化为横坐标展现,咱们这儿是不是也能够用相同的思路呢?

客户端 ip 进行 hash 后不便是一个 int32 的数字嘛,那咱们就能够把一个 int32 的数字分为几个段,让每个服务器担任一个段的恳求!

比照输出成果咱们就能看到,影响简直是大局的!那咱们能不能有一种计划就算是服务器数量改变,也能削减受影响的客户端呢?这就需求用到下面的一致性 hash 算法!

加权轮询算法完成二中咱们讲到过把权重值转化为横坐标展现,咱们这儿是不是也能够用相同的思路呢?

客户端 ip 进行 hash 后不便是一个 int32 的数字嘛,那咱们就能够把一个 int32 的数字分为几个段,让每个服务器担任一个段的恳求!

下面为了直观咱们把服务器 192.168.2.10、192.168.2.20、192.168.2.30、192.168.2.40 分别用 IP1、IP2、IP3、IP4 表明,如上图:

可是专业一点的表明都会把这个横坐标掰弯,构成一个环,就叫所谓的 hash 环,如下图:

这样看就更直观了!假设有天 IP4 这台服务器宕机,那本来需求到 IP4 的恳求就会悉数转移到 IP1 服务器进行处理。

这样对部分客户端的恳求仍然会有影响,但至少影响也仅仅部分的,如下图:

这样看就更直观了!假设有天 IP4 这台服务器宕机,那本来需求到 IP4 的恳求就会悉数转移到 IP1 服务器进行处理。

这样对部分客户端的恳求仍然会有影响,但至少影响也仅仅部分的,如下图:

这样就能够了吗?咱们考虑两个问题:

处理问题 1 的计划便是不再人为分配结点地点的方位,而是依据服务器的 ip 核算出 hash 值,再看 hash 值落在环上的哪个方位!

这样存在的一个问题是每个集群的服务器 ip 都会不同,因而核算后落在环上的方位或许便是不可控的。

如上面四台服务器核算后地点的方位或许会如下图所示:

很显着,这种状况是极为不均匀的,会形成数据的歪斜!上面问题 2 的问题其实也是宕机导致的数据歪斜!

环的左上部分那么空,咱们是不是能够把现在的 4 台服务器再依据其他的规矩在左上方生成一些结点呢?这样是不是恳求就会略微均匀一点呢?

这便是所谓的虚拟结点!虚拟结点便是同一个服务器 ip 会依据某个规矩生成多个 hashcode,这样在环上就存在多个结点了。

如下图所示:

很显着,这种状况是极为不均匀的,会形成数据的歪斜!上面问题 2 的问题其实也是宕机导致的数据歪斜!

环的左上部分那么空,咱们是不是能够把现在的 4 台服务器再依据其他的规矩在左上方生成一些结点呢?这样是不是恳求就会略微均匀一点呢?

这便是所谓的虚拟结点!虚拟结点便是同一个服务器 ip 会依据某个规矩生成多个 hashcode,这样在环上就存在多个结点了。

如下图所示:

这儿仅仅模拟了每台服务器有两个虚拟结点,实践在开发中会更多!这样就算 IP4 机器挂掉,恳求也不会悉数压到某一台服务器上去!

讲了这么多,但完成起来也不难,下面就该上代码了:

//虚拟结点数量100 
private static final  Integer VIRTUAL_NODES = 100; 
public  static void main { 
    // 遍历服务器ip,生成对应的虚拟结点 
    TreeMap Integer, String  nodeMap = new TreeMap Integer, String  
    for  { 
        for  { 
            nodeMap.put, serverIp); 
        } 
    } 
    for  { 
        //这儿使用的TreeMap的特性,不清楚的能够去自己去了解一下tailMap办法的效果 
        SortedMap Integer, String  subMap = nodeMap.tailMap); 
        Integer firstKey =  null; 
        try { 
            firstKey = subMap.firstKey; 
        } catch  { 
        } 
        if  { 
            firstKey = nodeMap.firstKey; 
        } 
        System.out.println); 
    } 

到此,几种常用的负载均衡算法及代码完成都已介绍结束!还有不清楚能够去同性交友网下载示例代码自己调试:

https://github.com/sujing910206/load-balance 

作者:苏静

简介:有过多年大型互联网项目的开发经历,对高并发、分布式、以及微服务技能有深化的研讨及相关实践经历。经历过自学,热衷于技能研讨与共享!格言:始终保持虚心学习的情绪!

热门文章

随机推荐

推荐文章