负载均衡的那些算法们
今天跟大伙儿聊的是负载均衡相干的1些算法。老王在百度的时候（估计是5⑹年前），写过1个通用的基础库（不知道现在还有无部门在用），用来做不同系统间负载均衡。太细节的东东估计想不起来了，不过基本的算法可以跟大家做做分享。
那第1个问题：what's load-balance?
假定我有两个模块（或两个系统）：module-A和module-B，A依赖B提供服务。当用户要求过来的时候，A就会去要求B，让B根据要求进行某些处理（比如：根据单词id查对应的单词），完成后把结果返回给A，A再对这个结果进行处理。但是，为了保证服务稳定，有可能B服务有很多台机器，A遇到这个时候就犯难了：我该去找B的哪台机器取数据呢？
最多见的1个case就是nginx：比如我们的web逻辑服务器是jetty或tomcat，1般会有多台，nginx就需要配置这多台机器：
upstream simplemain.com {
server 192.168.1.100:8080;
server 192.168.1.101:8080;
}
那这些机器是怎样样选择的呢？实际就是负载均衡算法。
老王对负载均衡的理解，他应当包括两个层面：
1、负载：就是后端系统的承载能力。比犹如等条件下，1个1核cpu⑴G内存的机器的承载能力1般会比8核cpu⑻G内存的机器要差；相同配置下，1个cpu利用率为80%的机器比30%的承载能力1般要差等等。
2、均衡：保证后端要求的平衡。比如：在同等情况下，分配到多台机器的要求要相当；有些情况下，同1用户尽量分配到同1台机器等等。
所以，负载均衡的算法实际上就是解决跨系统调用的时候，在斟酌后端机器承载情况的条件下，保证要求分配的平衡和公道。
那第2个问题随之而来：why？
为何要有负载均衡呢？
1、很明显，如果我们不去斟酌后真个承载情况，有可能直接就把某台机器压垮了（比如cpu利用率已80%了，再给大量的要求直接就干死了），更严重的会直接造成雪崩（1台压死了，对应的要求又压倒其他某台机器上，又干死1台……），从而导致服务瘫痪。
2、如果我们均衡算法选的不好，就会致使后端资源浪费。比如：如果选择1致Hash算法，可以很好利用cache的容量。而如果用随机，有可能就会让cache效果大打折扣（每台机器上都要缓存几近相同的内容）。
所以，用负载均衡应当是1个比较好的选择。
那就解决第3个问题吧：how？
依照之前的思路，我们还是分成两个部份来说：负载& 均衡。
1、先来看负载算法：
既然要解决后端系统的承载能力，那我们就有很多方式，常见的有以下几种：
A、简单粗鲁有效的：手工配置！
大家是否是觉得这个听起来很山寨呢？其实不是。这类方式对中小系统来说是最有效最稳定的。由于后端机器的性能配置、上脸部署了哪些服务、还能有多大的承载能力等等，我们是最清楚的。那我们在配置的时候，就能够明确的告知调用者，你只能分配多大的压力到某台服务器上，多了不行！
比如，我们常常看到nginx的配置：
upstream simplemain.com {
server 192.168.1.100:8080 weight=30;
server 192.168.1.101:8080 weight=70;
}
就是说，虽然有两台后真个服务器，但是他们承载能力是不1样的，有1个能力更强，我们就给他70%的压力；有1个更弱，我们就给他30%的压力。这样，nginx就会把更多的压力分配给第2台。
这类方式配置简单，而且很稳定，基本不会产生分配的抖动。不过，带来的问题就是分配很固定，不能动态调剂。如果你的后端服务器有1段时间出现性能抖动（比如有其他服务扰动了机器的稳定运行，造成cpu利用率1段时间升高），前端调用者就很难根据实际的情况重新分配要求压力。所以，引入了第2种方法。
B、动态调剂。
这类方案会根据机器当前运行的状态和历史平均值进行对照，发现如果当前状态比历史的要糟，那末就动态减少要求的数量。如果比历史的要好，那末就能够继续增加要求的压力，直到到达1个平衡。
具体怎样做呢？
首先，刚开始接入的时候，我们可以计算所有机器对要求的响应时间，算1个平均值。对响应较快的机器，我们可以多分配1些要求。如果要求多了致使响应减慢，这个时候就会逐渐和其他机器持平，说明这台机器到达了相应的平衡。
接着，当接入到达平衡以后，就能够统计这台机器平均的响应时间。如果某1段响应要求变慢了（同时比其他机器都要慢），就能够减少对他要求的分配，将压力转移1部份到其他机器，直到所有机器到达1个整体的平衡。
这类方案是否是看起来很高级呢？他的好处在于可以动态的来平衡后面服务器的处理能力。不过，任何事物都有两面性。这类方案如果遇到极端情况，可能会造成系统雪崩！当某台机器出现短暂网络抖动的时候，他的响应便可能变慢，这个时候，前端服务就会将他的要求分配给其他的机器。如果分配的很多，就有可能造成某些机器响应也变慢。然后又将这些机器的要求分配给另外的……如此这般，那些勤勤奋恳的机器终将被这些要求压死。
所以，更好的方案，将二者结合。1方面静态配置好承载负荷的1个范围，超过最大的就扔掉；另外一方面动态的监控后端机器的响应情况，做小范围的要求调剂。
2、均衡算法
均衡算法主要解决将要求如何发送给后端服务。常常会用到以下4种算法：随机（random）、轮训（round-robin）、1致哈希（consistent-hash）和主备（master-slave）。
比如：我们配置nginx的时候，常常会用到这样的配置：
upstream simplemain.com {
ip_hash;
server 192.168.1.100:8080;
server 192.168.1.101:8080;
}
这个配置就是按ip做hash算法，然后分配给对应的机器。
接下来我们详细的看看这几个算法是如何来工作的。
A、随机算法。
顾名思义，就是在选取后端服务器的时候，采取随机的1个方法。在具体讲这个算法之前，我们先来看看1个例子，我们写以下C语言的代码:
#include <stdlib.h>
#include<stdio.h>
int main()
{
srand(1234);
printf("%d\n", rand());
return0;
}
我们用srand函数给随机算法播了1个1234的种子，然后再去随机数，接着我们编译和链接gcc rand.c -o rand
按理想中说，我们每次运行rand这个程序，都应当得到不1样的结果，对吧。可是……
可以看到，我们每次运行的结果都是1样的！！出了甚么问题呢？
我们说的随机，在计算机算法中通常采取的是1种伪随机的算法。我们会先给算法放1个种子，然后根据1定的算法将种子拿来运算，最后得到1个所谓的随机值。我们将上面的算法做1个小小的改动，将1234改成time(NULL)，效果就不1样了：
#include <stdlib.h>
#include <stdio.h>
#include<time.h>
int main()
{
srand((int)time(NULL));
printf("%d\n", rand());
return 0;
}
time这个函数会获得当前秒数，然后将这个值作为种子放入到伪随机函数，从而计算出的伪随机值会由于秒数不1样而不同。
具体来看1下java源代码里如何来实现的。我们经常使用的java随机类是java.util.Random这个类。他提供了两个构造函数：
public Random() {
this(seedUniquifier() ^ System.nanoTime());
}
public Random(long seed) {
if (getClass() == Random.class)
this.seed =new AtomicLong(initialScramble(seed));
else {
//subclass might have overriden setSeed
this.seed =new AtomicLong();
setSeed(seed);
}
}
我们可以看到，这个类也是需要1个种子。然后我们获得随机值的时候，会调用next函数：
protectedintnext(int bits) {
long oldseed, nextseed;
AtomicLong seed =this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed *multiplier +addend) &mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed>>> (48 - bits));
}
这个函数会利用种子进行1个运算，然后得到随机值。所以，我们看起来随机的1个算法，实际上跟时间是相干的，跟算法的运算是相干的。其实不是真实的随机。
好了，话归正题，我们用随机算法怎样样做要求均衡呢？比如，还是我们之前那个nginx配置：
upstream simplemain.com {
server 192.168.1.100:8080 weight=30;
server 192.168.1.101:8080 weight=70;
}
我们有两台机器，分别需要承载30%和70%的压力，那末我们算法就能够这样来写（伪代码）：
bool res = abs(rand()) % 100 < 30
这句话是甚么意思呢？
1、我们先产生1个伪随机数：rand()
2、将这个伪随机数的转化为非负数: abs(rand())
3、将这个数取模100，将值转化到[0,100)的半开半闭区间：abs(rand()) % 100
4、看这个数是不是落入了前30个数的区间[0,30)：abs(rand()) % 100 < 30
如果随机是均匀的话，他们落到[0,100)这个区间里1定是均匀的，所以只要在[0,30)这个区间里，我们就分给第1台机器，否则就分给第2台机器。
其实这里讲述的只是1种方法，还有很多其他的方法，大家都可以去想一想。
随机算法是我们最最最最最最经常使用的算法，绝大多数情况都使用他。首先，从几率上讲，它能保证我们的要求基本是分散的，从而到达我们想要的均衡效果；其次，他又是无状态的，不需要保持上1次的选择状态，也不需要均衡因子等等。整体上，方便实惠又好用，我们1直用他！
B、轮训算法。
轮训算法就像是挨个数数1样（123⑴23⑴23……），1个个的轮着来。
upstream simplemain.com {
server 192.168.1.100:8080 weight=30;
server 192.168.1.101:8080 weight=70;
}
还是这个配置，我们就能够这样来做（为了方便，我们把第1台机器叫做A，第2台叫做B）：
1、我们先给两台机器做个排序的数组：array = [ABBABBABBB]
2、我们用1个计数指针来标明现在数组的位置：idx = 3
3、当1个要求来的时候，我们就把指针对应的机器选取出来，并且指针加1，挪到下1个位置。
这样，10个要求，我们就能够保证有3个1定是A，7个1定是B。
轮训算法在实际中也有使用，但是由于要保护idx指针，所以是有状态的。我们常常会用随机算法取代。
C、1致哈希算法。
这个算法是大家讨论最对，研究最多，神秘感最强的1个算法。老王当年刚了解这个算法的时候，也是花了很多心思去研究他。在百度上搜：“1致hash”，大概有321万篇相干文章。
大家到网上搜这个算法，1般都会讲将[0,232)所有的整数投射到1个圆上，然后再将你的机器的唯1编码（比如：IP）通过hash运算得到的整数也投射到这个圆上（Node-A、Node-B）。如果1个要求来了，就将这个要求的唯1编码（比如：用户id）通过hash算法运算得到的整数也投射到这个圆上（request⑴、request⑵），通过顺时针方向，找到第1个对应的机器。以下图：
当时老王看了这些文章也觉得很有道理，但是过了1段时间就忘了……自己揣摩了1段时间，不断的问自己，为何要这样做呢？
过了很久，老王有了1些体会。实际上，1致Hash要解决的是两个问题：
1、散列的不变性：就是同1个要求（比如：同1个用户id）尽可能的落入到1台机器，不要由于时间等其他缘由，落入到不同的机器上了；
2、异常以后的分散性：当某些机器坏掉（或增加机器），原来落到同1台机器的要求（比如：用户id为1，101，201），尽可能分散到其他机器，不要都落入其他某1台机器。这样对系统的冲击和影响最小。
有了以上两个原则，这个代码写起来就很好写了。比如我们可以这样做(假定要求的用户id=100）：
1、我们将这个id和所有的服务的IP和端口拼接成1个字符串：
str1 = "192.168.1.100:8080⑴00"
str2 = "192.168.1.101:8080⑴00"
2、对这些字符串做hash，然后得到对应的1些整数：
iv1 = hash(str1)
iv2 = hash(str2)
3、对这些整数做从大到小的排序，选出第1个。
好，现在来看看我们的这个算法是不是符合之前说的两个原则。
1、散列的不变性：很明显，这个算法是可重入的，只要输入1样，结果肯定1样；
2、异常以后的分散性：当某台机器坏掉以后，本来排到第1的这些机器就被第2位的取代掉了。只要我们的hash算法是分散的，那末得到排到第2位的机器就是分散的。
所以，这类算法其实也能到达一样的目的。固然，可以写出一样效果的算法很多很多，大家也能够自己揣摩揣摩。最根本的，就是要满足以上说的原则。
1致Hash算法用的最多的场景，就是分配cache服务。将某1个用户的数据缓存在固定的某台服务器上，那末我们基本上就不用多台机器都缓存一样的数据，这样对我们提高缓存利用率有极大的帮助。
不过硬币都是有两面的，1致Hash也不例外。当某台机器出问题以后，这台机器上的cache失效，本来压倒这台机器上的要求，就会压到其他机器上。由于其他机器本来没有这些要求的缓存，就有可能直接将要求压到数据库上，造成数据库瞬间压力增大。如果压力很大的话，有可能直接把数据库压垮。
所以，在斟酌用1致Hash算法的时候，1定要估计1下如果有机器宕掉后，后端系统是不是能承受对应的压力。如果不能，则建议浪费1点内存利用率，使用随机算法。
D、主备算法。
这个算法核心的思想是将要求尽可能的放到某个固定机器的服务上（注意这里是尽可能），而其他机器的服务则用来做备份，如果出现问题就切换到另外的某台机器的服务上。
这个算法用的相对不是很多，只是在1些特殊情况下会使用这个算法。比如，我有多台Message Queue的服务，为了保证提交数据的时序性，我就想把所有的要求都尽可能放到某台固定的服务上，当这台服务出现问题，再用其他的服务。
那怎样做呢？最简单的做法，我们就对每台机器的IP：Port做1个hash，然后按从大到小的顺序排序，第1个就是我们想要的结果。如果第1个出现问题，那我们再取第2个：head(sort(hash("IP:Port1"), hash("IP:Port2"), ……))
固然，还有其他做法。比如：老王做的Naming Service就用1个集中式的锁服务来判定当前的主服务器，并对他进行锁定。
好了，关于负载均衡相干的算法就大体上说这么多。其实还有1个相干话题没有说，就是健康检查。他的作用就是对所有的服务进行存活和健康检测，看是不是需要提供给负载均衡做选择。如果1台机器的服务出现了问题，健康检查就会将这台机器从服务列表中去掉，让负载均衡算法看不到这台机器的存在。这个是给负载均衡做保障的，但是可以不划在他的体系内。不过也有看法是可以将这个也算在负载均衡算法中。由于这个算法的实现其实也比较复杂，老王这次就不讲这个算法了，可以放到接下来的文章中来分析。
====感谢的分割线 ====
1、上周做了1个问卷，想了解1下大家都关注哪些技术方向。好多盆友都投了票，给老王提了建议和想法，让老王对接下来的扯淡有了更多的思考；
2、有几位盆友问老王怎样没开通评论和打赏，准备要给老王打个赏。更有1位姓姜的盆友加了老王的微信，硬给老王发了红包（是老王收到的第1个赏哦，老王会永久记住的）。让老王感动的不行。本来老王写这些东东没太想其他的，就想把多年的积累记录下来，分享给更多的人，所以收到大家的赞美真的很感动。也巧，这周收到微信的原创约请和评论了~
3、好几位盆友还将自己未来的发展方向找老王来聊。这是把自己的未来跟老王做分享和交换，这是对老王最大的信任！
所以，老王要对所有支持我的朋友深深的鞠1躬，谢谢各位的支持与信任！
有兴趣的盆友，可以继续关注老王：simplemain
