LVS负载均衡的十二种核心调度算法

深入解析LVS负载均衡的十种核心调度算法静态算法静态算法只根据算法本身进行调度不考虑服务器当前的负载情况RR轮询Round RobinRR算法就是按依次循环的方式将请求调度到不同的服务器上该算法最大的特点就是实现简单。轮询算法假设所有的服务器处理请求的能力都一样的调度器会将所有的请求平均分配给每个真实服务器。特点是将收到的访问请求按顺序轮流分配给集群中的各节点真实服务器中不管服务器实际的连接数和系统负载。轮询 RS分别被调度当RS配置有差别时不推荐WRR加权轮询Weighted Round RobinWRR算法就是加权轮询根据RS的配置进行加权调度主要是对轮询算法的一种优化与补充LVS会考虑每台服务器的性能并给每台服务器添加一个权值如果服务器A的权值为1服务器B的权值为2则调度器调度到服务器B的请求会是服务器A的两倍。权值越高的服务器处理的请求越多。加权轮询根据RS的配置进行加权调度性能差的RS被调度的次数少SH 源地址散列调度Source Hashing SH算法就是将来自于同一个IP地址的请求始终发往 第一次挑中的RS从而实现会话绑定先根据请求的源IP地址作为散列键Hash Key从静态分配的散列表找出对应的服务器若该服务器是可用的且并未超载将请求发送到该服务器否则返回空。它采用的散列函数与目标地址散列调度算法的相同它的算法流程与目标地址散列调度算法的基本相似。DH目标地址散列调度Destination Hashing DH算法就是第一次轮询调度至RS后续将发往同一个目标地址的请 求始终转发至第一次挑中的RS先根据请求的目标IP地址作为散列键Hash Key从静态分配的散列表找出对应的服务器若该服务器是可用的且并未超载将请求发送到该服务器否则返回空。LVS动态调度算法动态算法主要根据每个RS当前的负载状况和算法进行调度负载(overhead)较小的RS下次将会被调度LC最小连接调度Least Connections LC算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态的调度算法它通过服务器当前活跃的连接数来估计服务器的情况。调度器需要记录各个服务器已建立连接的数目当一个请求被调度到某台服务器其连接数加1当连接中断或者超时其连接数减1。适用于长连接应用。Overhead负载值 activeconns活动连接数 × 256 inactiveconns非活动连接数集群系统的真实服务器具有相近的系统性能采用最小连接调度算法可以比较好地均衡负载。WLC加权最少连接Weight Least Connections WLC算法是最小连接调度的超集各个服务器相应的权值表示其处理性能。服务器的缺省权值为1系统管理员可以动态地设置服务器的权值。加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。调度器可以自动问询真实服务器的负载情况并动态地调整其权值。默认调度方法Overhead (activeconns × 256 inactiveconns) / weight。SED 最短的期望的延迟调度Shortest Expected Delay SED算法基于WLC算法但保证了高权重优先。举个例子吧ABC三台服务器的权重分别为1、2、3 。那么如果使用WLC算法的话一个新请求进入时它可能会分给ABC中的任意一个。使用SED算法后会进行一个运算A11/12 B12/23/2 C13/34/3 就把请求交给得出运算结果最小的服务器。预期的延迟时间为Ci 1/ Ui其中 Ci 是第 i 个服务器上的连接数而 Ui 是第 i 个服务器的固定服务速率权重初始连接高权重优先Overhead(activeconns1inactiveconns) x 256/weight但是当node1的权重为1node2的权重为10经过运算前几次的调度都会被node2承接NQ最少队列调度Never Queue NQ算法在SED的基础上无需队列。如果有realserver的连接数等于0就直接分配过去不需要在进行SED运算不严谨的来说就是先轮询无空闲再SED。LBLC基于局部的最少连接调度Locality-Based Least Connections LBLC算法是动态的DH算法针对请求报文的目标IP地址的 负载均衡调度目前主要用于Cache集群系统因为在Cache集群客户请求报文的目标IP地址是变化的。这里假设任何后端服务器都可以处理任一请求算法的设计目标是在服务器的负载基本平衡情况下将相同目标IP地址的请求调度到同一台服务器来提高各台服务器的访问局部性和Cache命中率从而提升整个集群系统的处理能力。LBLC调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器若该服务器是可用的且没有超载将请求发送到该服务器若服务器不存在或者该服务器超载且有服务器处于一半的工作负载则使用’最少连接’的原则选出一个可用的服务器将请求发送到服务器。LBLCR带复制的基于局部性的最少连接Locality-Based Least Connections with Replication LBLCR算法是带复制功能的LBLC目前主要用于Cache集群系统它与LBLC算法不同之处是它要维护从一个目标IP地址到一组服务器的映射而LBLCR算法维护从一个目标IP地址到一台服务器的映射。按’最小连接’原则从该服务器组中选出一一台服务器若服务器没有超载将请求发送到该服务器若服务器超载则按’最小连接’原则从整个集群中选出一台服务器将该服务器加入到这个服务器组中将请求发送到该服务器。同时当该服务器组有一段时间没有被修改将最忙的服务器从服务器组中删除以降低复制的程度。新算法FO算法(Weighted Fail Over)FO算法常用作灰度发布会遍历lvs关联的RS链表找到未过载(未设置IP_VS_DEST_F_OVERLOAD标识)且权重最高的RS进行调度。当服务器承接大量链接我们可以对此服务器进行过载标记IP_VS_DEST_F OVERLOAD那么vs调度器就不会把链接调度到有过载标记的主机中。OVF算法(Overflow-connection)OVF算法是基于RS的活动连接数和权重值来实现。它会将新连接调度到权重值最高的RS直到其活动连接数超过它的权重值之后调度到下一个权重值最高的RS。该算法会遍历lvs关联的RS链表找到权重值最高的可用RS。可用RS需要满足以下条件未过载(未设置IP_VS_DEST_F_OVERLOAD标识)。RS当前活动连接数小于其权重值。权重值不为0。十种核心调度算法对比下表汇总了LVS负载均衡的十种核心调度算法便于快速对比和选型参考算法名称类型核心原理简述适用场景优缺点RR轮询静态按顺序循环将请求依次分配给各服务器实现简单。服务器性能相近、无状态短连接服务。优点实现简单公平分配。缺点不考虑服务器负载和性能差异性能不均时效率低。WRR加权轮询静态根据服务器权值分配请求权值越高被调度的次数越多。服务器性能有明显差异需要按性能比例分配负载。优点考虑了服务器性能差异分配更合理。缺点仍为静态分配无法感知实时负载变化。SH源地址散列静态根据请求源IP进行哈希将同一源IP的请求始终发往同一台服务器。需要会话保持Session Persistence的应用如登录状态。优点实现会话绑定保证同一用户请求到同一服务器。缺点服务器增减或故障时哈希结果会变化可能引起会话中断。DH目标地址散列静态根据请求目标IP进行哈希将同一目标IP的请求始终发往同一台服务器。Cache集群、CDN等需要提高局部性和缓存命中率的场景。优点相同目标IP的请求落到同一服务器提高缓存命中率。缺点静态哈希无法适应负载变化。LC最小连接动态将新连接分配给当前连接数最少的服务器。长连接应用如数据库连接池、WebSocket服务器性能相近。优点动态感知服务器负载负载相对均衡。缺点未考虑服务器性能差异仅以连接数衡量负载可能不准确。WLC加权最少连接动态在LC基础上引入权值使服务器的连接数与其权值成比例。服务器性能差异较大且需要动态负载均衡的场景。优点结合了权值与连接数分配更精细。缺点高权重服务器在初始阶段可能集中大量请求。SED最短期望延迟动态基于WLC改进计算连接数1/权值选择值最小的服务器保证高权重优先。需要优先调度高权重服务器且希望初始连接快速响应的场景。优点高权重服务器优先获得请求提高整体吞吐。缺点计算稍复杂权重悬殊时低权重服务器可能长期闲置。NQ最少队列动态SED的改进版若某服务器连接数为0则直接分配否则按SED计算。希望避免服务器空闲同时兼顾权重优先的场景。优点避免服务器空闲提高资源利用率。缺点仍基于SED权重差异大时低权重服务器仍可能饿死。LBLC基于局部的最少连接动态动态的DH算法针对目标IP进行调度结合“最近使用”和“最少连接”原则。Cache集群系统目标IP变化频繁需要提高访问局部性和缓存命中率。优点动态适应负载提高缓存命中率。缺点实现较复杂仅适用于特定Cache场景。LBLCR带复制的LBLC动态LBLC的带复制版本维护目标IP到一组服务器的映射支持动态增删组内服务器。大规模Cache集群需要更高可用性和负载分散的场景。优点支持复制可用性更高负载更分散。缺点实现更复杂维护成本高。说明FOWeighted Fail Over和OVFOverflow-connection属于较新的调度算法主要用于灰度发布和溢出连接控制上表未包含请参考前文“新算法”章节。