负载均衡原理及实现

　　什么是负载均衡？
　　负载均衡（LoadBalance），顾名思义就是把任务压力进行平衡的分摊到集群中各个操作单元（或机器）上，使得避免集群中部分机器压力过大而部分机器过于空闲。经过负载均衡，使得每个机器获取适合自己的处理能力负载。
　　负载均衡的分类
　　负载均衡可分为硬件负载均衡和软件负载均衡。
　　硬件负载均衡比如F5、NetScaler等价格比较昂贵，一般开发中很难接触到。但软件负载均衡还是很容易接触到的，比如大家常见的Nginx、LVS等。
　　软件负载均衡又可以分为四层负载均衡和七层负载均衡。
　　所谓四层负载均衡就是在网络层基于IP端口的负载均衡。也就是通过报文中的目标地址和端口，在加上负载均衡设备的选择方式从而选择最终对应的服务器。
　　所谓七层负载均衡就是在四层的基础上在应用层根据用户的http请求头和URL等信息将请求转发到特定的服务器上。LVS（LinuxVirtualServer）为四层负载均衡，Nginx可以做四层也可以做七层。
　　负载均衡的常见算法
　　对于软件中实现的负载均衡，常见的负载均衡算法有轮询（RoundRobin）法、随机（Random）法、加权轮询（WeightRoundRobin）法、加权随机（WeightRandom）法、源地址哈希（Hash）法、一致性哈希（ConsistentHash）法等。
　　1、轮询（RoundRobin）法
　　将接收到的请求按照顺序依次分配给各个服务器对外提供服务。
　　代码如下：
　　includestdio。hintposition0；inttotalServer4；pthreadmutextmut；互斥锁charserverInfo〔〕｛192。168。1。1，192。168。1。2，192。168。1。3，192。168。1。4，｝；chargetServerUrl（）｛charretNULL；pthreadmutexlock（mut）；if（positiontotalServer）position0；position；retserverInfo〔position〕；pthreadmutexunlock（mut）；returnret；｝
　　轮询就是对各个服务节点依次顺序遍历，当请求的次数position达到最大服务节点数量时，重新从0开始。
　　其实可以把服务节点列表想象成一个圆中的各个圆点，当访问请求次数到达最大值时也就循环是一周，然后在从0开始。
　　优点：对于各个服务节点对外提供服务的次数绝对均衡。
　　缺点：由于使用了position获取服务节点，因此对position的修改要做到互斥，所以对性能会造成一定的影响，同时对于低承载能力的服务节点不友好，因为它要和高承载能力的服务节点接受同样的压力。
　　2、随机（Random）法
　　根据后端服务节点的个数，从中随机选择其中一个节点对外提供服务。
　　代码如下：chargetServerUrl（）｛intirand（）totalServer；returnserverInfo〔i〕；｝
　　优点：算法实现简单，当请求的次数增大时，各个服务节点处理的请求数量近似于均衡。
　　缺点：和轮训算法一样，对于低承载能力的服务节点不友好。
　　3、加权轮询（WeightRoundRobin）法
　　上述的轮询法和随机法存在一个共同的缺点，就是各个服务器节点负载相对均衡，但是当各个服务器节点载能力不同时，会对低承载能力的服务器节点压力过大。
　　正是由于这个缺点，后续有了加权轮询法、加权随机法，该算法的实现就是给不同配置的服务器节点，配置不同的权重值，后续分配请求时，对权重高的服务器节点，多分配点，对权重低的服务器节点，少分配点。
　　如下实现了一个加权轮询算法：
　　includestdio。hincludestdlib。hincludestring。hdefineIPLEN22typedefstruct｛intweight；intcurweight；哪个server当权权重最大，就分配个谁charip〔IPLEN〕；｝serverInfo；intgetWeightSum（intweight，intsize）｛inti0；inttotal0；for（i0；isize；i）｛totalweight〔i〕；｝returntotal；｝serverInfoinitServer（charips，intweight，intsize）｛inti0；serverInfoserverscalloc（size1，sizeof（serverInfo））；for（i0；isize；i）｛servers〔i〕。weightweight〔i〕；memcpy（servers〔i〕。ip，ips〔i〕，IPLEN）；servers〔i〕。curweight0；｝returnservers；｝该算法参看nginx中平滑的加权轮询算法，该算法会保证生成的序列比较均匀而普通的加权轮询算法在某种权重下会出现不均匀的序列intgetServerUrlIndex（serverInfos，intsize）｛inti0；intindex0；记录当前权重最大的server索引inttotal0；记录权重总和for（i0；isize；i）｛s〔i〕。curweights〔i〕。weight；totals〔i〕。weight；记录权重最大的索引节点if（s〔index〕。curweights〔i〕。curweight）｛indexi；｝｝把当前权重最大的减去权重总和，这时候当前权重会减小，所以下次分配就不一定还是该server了s〔index〕。curweighttotal；返回当前权重最大的server索引returnindex；｝voidgetServerUrl（serverInfos，intweight，intsize）｛inti0；intindex0；inttotalgetWeightSum（weight，size）；for（i0；itotal；i）｛indexgetServerUrlIndex（s，size）；printf（getserverissd，s〔index〕。ip，s〔index〕。weight）；｝｝intmain（）｛inti0；intweight〔〕｛5，2，3｝；charips〔〕｛192。168。1。1，192。168。2。2，192。168。3。3｝；intsizesizeof（weight）sizeof（int）；serverInfosinitServer（ips，weight，size）；for（i0；isize；i）｛printf（serverinitissd，s〔i〕。ip，s〔i〕。weight）；｝printf（getServerUrl：）；getServerUrl（s，weight，size）；return0；｝得到结果如下：serverinitis192。168。1。15serverinitis192。168。2。22serverinitis192。168。3。33getServerUrl：getserveris192。168。1。15getserveris192。168。3。33getserveris192。168。2。22getserveris192。168。1。15getserveris192。168。1。15getserveris192。168。3。33getserveris192。168。1。15getserveris192。168。2。22getserveris192。168。3。33getserveris192。168。1。15
　　优点：加权轮询能够使用权重解决不同承载能力的服务器节点。
　　缺点：需要使用一定的机制解决某些情况下生成的序列是不均匀的问题。
　　4、源地址哈希（Hash）法
　　根据客户端的ip经过hash获取一个hash值，然后根据该hash值和服务器节点总数进行取模运算，取得对应的服务器节点。chargetServerUrl（）｛intihashcode（clientIP）totalServer；returnserverInfo〔i〕；｝
　　优点：当服务器列表不变时，只要请求源地址不变，总会请求到相同的目标服务器，这样就可以在客户端服务器之间构建一个有状态session。
　　缺点：当有大量的获取客户端时，会造成部分服务器过于繁忙，导致负载不均衡。另外，当某个服务器节点挂掉后，后续hash到该节点的所有请求都会得不到响应。
　　5、一致性哈希（ConsistentHash）法
　　传统的hash算法一般就是key和节点总数进行mod运算mod（key，n），但这样会带来一个问题，就是当扩容或者缩容时，他们的映射关系就变成了mod（key，n1）或mod（key，n1），这会导致所有的key都会出现新的映射关系，因此很多key就会出现映射失败。
　　为了解决普通hash这种扩展能力和容错能力差的问题，就出现了一致性hash（ConsistentHashing）的概念，采用一致性hash时，当出现扩容或者缩容时，影响的key只有少数部分，对全局影响不大。
　　一致性hash采用对每个服务节点进行计算hash值，该hash值的范围在（021）中，我们把这些数字收尾相连构成一个范围在（021）的hash环中，然后把各个服务器节点经过hash运算得到对应的值，然后散列到hash环中，如下图，
　　当请求到来时，根据请求的唯一标志，比如请求的客户IP等经过hash运算得到一个hash值，然后根据该值从hash环上以顺时针的方向查找，得到一个离自己最近的服务器节点，该服务器节点也就是该请求对应的服务器。如下图，客户端请求经过hash，从hash环中顺时针找到node2服务节点。
　　经过上述介绍我们可以发现一个问题，也就是当服务节点较少时，会出现数据倾斜问题，也就失去了平衡性，如下图，我们会发现很多都分配给了node2节点了。
　　为了防止这种数据倾斜，我们采用虚拟节点来保证平衡性。虚拟机节点其实就是服务器节点的复制，我们把一个服务器节点映射多个虚拟节点，当请求经过hash运算后从hash环上以顺时针的方向查找到虚拟机节点时，我们就把虚拟节点对应的实际服务节点作为服务器。虚拟节点如下图
　　比如客户端请求到来，根据客户端的key1经过hash计算映射到hash环中如下图，从该点顺时针找到了服务器节点3的虚拟节点，因此把服务器节点3作为请求对应的服务器。
　　当某个服务节点宕机（比如服务节点2），那么请求对象最终落到了服务节点3，对于整个系统的影响也就是key1和node2之间的范围。如下图，
　　新增服务节点同理，当key1和node3之间新增了一个服务节点2，那么key1经过hash查找服务节点时会找到服务节点2。
　　一致性hash的实现
　　本次分析一下开源项目ketama中的一致性hash算法的实现。
　　在ketama中为了平衡性也采用了虚拟机节点，同时为了不同的服务节点的承载能力也使用了权重，因此权重高的，相应的虚拟机节点也就相应的多，服务器节点也就处理的请求多。
　　ketama中使用如下结构记录服务节点信息。typedefstruct｛unsignedintpoint；圆环上的点charip〔22〕；实际服务节点ip｝mcs；服务器信息，主要记录服务器的ip地址和权重值typedefstruct｛charaddr〔22〕；服务器ip地址unsignedlongmemory；权重值｝serverinfo；以下数据结构就是continuum环上的结点，环上的每个点其实代表了一个ip地址，该结构把点和ip地址一一对应起来。typedefstruct｛intnumpoints；在环上的点的总数同时也是array数组元素的总个数voidmodtime；更改时间voidarray；mcs数组该数组时以mcs中point从小到大排过序的，为了方便从环上找响应的服务节点｝continuum；
　　一致性hash环的创建
　　一致性hash环的创建该函数是创建continuum的核心函数，它先从配置文件中读取集群服务器ip和端口，以及权重信息。创建continuum环，并把这些服务器信息和环上的数组下标对应起来。staticintketamacreatecontinuum（keytkey，charfilename）｛。。。unsignedintnumservers0；该变量来记录共从配置文件中共读取了多少个服务器unsignedlongmemory；该变量是配置文件中所有服务器权重值的总和serverinfoslist；从配置文件中读取到的服务器信息，包括ip地址，端口，权重值从配置文件filename中读取服务器信息，把服务器总数保存到变量numservers中，把所有服务器的权重值保存到memory中slistreadserverdefinitions（filename，numservers，memory）；以下代码开始构建continuum环平均每台服务器要在这个环上布160个点，这个数组的元素个数就是服务器个数160。具体多少个点，需要根据事情的服务器权重值进行计算得到。为什么要选择160个点呢？主要是通过md5计算出来的是16个整数，把这个整数分成4等分，每份是4位整数。而每进行一次hash计算，我们可以获得4个点。mcscontinuum〔numservers160〕；unsignedinti，k，cont0；for（i0；inumservers；i）遍历所有服务器开始在环上部点｛floatpct（float）slist〔i〕。memory（float）memory；计算服务器i在所有服务器权重的占比由于计算一次可以得到4个点，所有对每一台机器来说，总的计算只需要计算40numservers次。按权重占比进行划分，就是以下的计算得到的次数unsignedintksfloorf（pct40。0（float）numservers）；ks是每个ip地址对应的总点数for（k0；kks；k）计算出总次数，每次可以得到4个点｛40hashes，4numbersperhash160pointsperservercharss〔30〕；unsignedchardigest〔16〕；通过计算hash值来得到下标值，该hash值是字符串：n，其中的n是通过权重计算出来的该主机应该部点的总数4。sprintf（ss，sd，slist〔i〕。addr，k）；ketamamd5digest（ss，digest）；计算其字符串的md5值，该值计算出来后是一个unsignedchar〔16〕的数组，也就是可以保存16个字节inth；for（h0；h4；h）共有16个字节，可以处理4次，得到4个点的值｛把计算出来的连续4位的数字，进行移位。把第一个数字移到一个整数的最高8位，后面的一次移动次高8位，后面一次补零，这样就得到了一个32位的整数值。continuum〔cont〕。point（digest〔3h4〕24）（digest〔2h4〕16）（digest〔1h4〕8）digest〔h4〕；复制对应的ip地址到该点上memcpy（continuum〔cont〕。ip，slist〔i〕。addr，22）；cont；｝｝｝free（slist）；Sortsinascendingorderofpoint以下代码对计算出来的环上点的值进行排序，方便进行查找这里要注意：排序是按照point的值（计算出来的整数值）进行的，也就是说原来的数组下标顺序被打乱了。Sortsinascendingorderofpointqsort（（void）continuum，cont，sizeof（mcs），（compfn）ketamacompare）；到这里算法的实现就结束了，环上的点（032整数范围内）都已经建立起来，每个点都是0到232的一个整数和ip地址的结构。这样查找的时候，只是需要hash（key），并在环上找到对应的数的位置，取得该节点的ip地址即可。。。。return1；｝
　　hash环的构建也很简单：
　　1、从配置文件中读取服务器信息列表，获取总的权重值。
　　2、创建numservers160个point点也就是虚拟机节点，然后根据权重进行hash运算分配这些point点，权重高的分配的越多。同时对这些point点进行从小到大排序，为何后续查找方便。
　　在环上查找元素
　　计算key的hash值的实现方法unsignedintketamahashi（charinString）｛unsignedchardigest〔16〕；对key的值做md5计算，得到一个有16个元素的unsignedchar数组ketamamd5digest（inString，digest）；取数组中的前4个字符，并移位，得到一个unsignedint的hash值return（unsignedint）（（digest〔3〕24）（digest〔2〕16）（digest〔1〕8）digest〔0〕）；｝在环上查找相应的结点mcsketamagetserver（charkey，ketamacontinuumcont）｛unsignedinthketamahashi（key）；计算key的hash值，并保存到变量h中inthighpcontnumpoints；该变量contnumpoints是总的数组埋点数mcs（mcsarr）〔contnumpoints〕contarray；数组结点的值intlowp0，midp；unsignedintmidval，midval1；pideandconquerarraysearchtofindserverwithnextbiggestpointafterwhatthiskeyhashestowhile（1）｛从数组的中间位置开始找注意此时的数组是按照point的值排好序了midp（int）（（lowphighp）2）；若中间位置等于最大点数，直接绕回到0位置if（midpcontnumpoints）return（（mcsarr）〔0〕）；ifattheend，rollbacktozeroth取的中间位置的point值midval（mcsarr）〔midp〕。point；获取midp上限和下限，若midp为0则midval1为0，否则取midp1的point，也即是获取h在如下范围内（mcsarr）〔midp1〕。pointh（mcsarr）〔midp〕midval1midp0？0：（mcsarr）〔midp1〕。point；把h的值和取的两个值point值进行比较，若在这两个point值之间说明h值应该放在较大的那个point值的下标对应的ip地址上if（hmidvalhmidval1）return（（mcsarr）〔midp〕）；if（midvalh）否则继续二分查找lowpmidp1；elsehighpmidp1；if（lowphighp）若没有找到，直接返回0位置的值，这种情况应该很少return（（mcsarr）〔0〕）；｝｝
　　查找服务器节点如下：
　　1、根据请求的key进行hash得到一个整数。
　　2、根据该整数从环上查找到一个比该整数大最近虚拟机节点，获取到的服务器节点就是要找的服务器。
　　以上就是hash一致性算法的实现。
　　优点：具有较好的扩展性和容错性，同时保证了数据的平衡性。
　　缺点：当某个客户端发送很多请求，后端hash到同一个服务器节点，会导致服务器负载过大，也即是没有解决热点问题。
　　总结
　　负载均衡就是通过一定方式把客户端的请求分配到相应的服务节点上，保证各个服务器节点能够在自己的承载范围内提供服务。负载均衡分为硬件负载均衡和软件负载均衡，一般接触到最多的是软件负载均衡，软件负载均衡有不同的负载均衡算法，各个负载均衡算法有各自的优缺点，可以根据适当的场景采用对应的算法。