LVS的调度算法

LVS的负载调度算法

LVS的调度算法分为静态与动态两类。

最常用的有四种；轮询（rr）、加权轮询(wrr)、最少连接(lc)和加权最少连接(wlc)。

一、静态调度算法

静态调度算法：只根据算法本身去调度，不考虑服务器本身

1. 轮询调度（RR）

轮询调度 (Round Robin 简称‘RR‘) 算法就是按依次循环的方式将请求调度到不同的服务器上，该算法最大的特点就是实现简单。轮询算法假设所有的服务器处理请求的能力都一样的，调度器会将所有的请求平均分配给每个真实服务器。

2. 加权轮询调度(WRR)

加权轮询 (Weight Round Robin 简称‘WRR‘) 算法主要是对轮询算法的一种优化与补充，LVS 会考虑每台服务器的性能，并给每台服务器添加一个权值，如果服务器 A 的权值为 1，服务器 B 的权值为 2，则调度器调度到服务器 B 的请求会是服务器 A 的两倍。权值越高的服务器，处理的请求越多。

3. 目标地址散列调度（DH）

目标地址散列调度 (Destination Hashing 简称‘DH‘) 算法先根据请求的目标 IP 地址，作为散列键 (Hash Key) 从静态分配的散列表找出对应的服务器，若该服务器是可用的且并未超载，将请求发送到该服务器，否则返回空。

第一次轮询调度至RS，后续将发往同一个目标地址的请求始终转发至第一次挑中的RS，典型使用场景是正向代理缓存场景中的负载均衡,如: Web缓存

4. 源地址散列调度（SH）

源地址散列调度 (Source Hashing 简称‘SH‘) 算法先根据请求的源 IP 地址，作为散列键 (Hash Key) 从静态分配的散列表找出对应的服务器，若该服务器是可用的且并未超载，将请求发送到该服务器，否则返回空。它采用的散列函数与目标地址散列调度算法的相同，它的算法流程与目标地址散列调度算法的基本相似。

将来自于同一个IP地址的请求始终发往第一次挑中的RS，从而实现会话绑定

二、动态调度算法

动态调度算法：主要根据每RS当前的负载状态及调度算法进行调度Overhead=value 较小的RS将被调度

5. 最少连接调度(LC)

最少连接调度 Least-Connection Scheduling 简称‘LC‘) 算法是把新的连接请求分配到当前连接数最少的服务器。最少连接调度是一种动态的调度算法，它通过服务器当前活跃的连接数来估计服务器的情况。调度器需要记录各个服务器已建立连接的数目，当一个请求被调度到某台服务器，其连接数加 1; 当连接中断或者超时，其连接数减 1。

适用于长连接应用

(集群系统的真实服务器具有相近的系统性能，采用最小连接调度算法可以比较好地均衡负载。)

 Overhead=activeconns*256+inactiveconns

6. 加权最小连接调度（WLC）

加权最少连接 (Weight Least Connections 简称‘WLC‘) 算法是最小连接调度的超集，各个服务器相应的权值表示其处理性能。服务器的缺省权值为 1，系统管理员可以动态地设置服务器的权值。加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。调度器可以自动问询真实服务器的负载情况，并动态地调整其权值。

 Overhead=(activeconns*256+inactiveconns)/weight

7. 基于局部的最少连接（LBLC）

基于局部的最少连接调度 (Locality-Based Least Connections 简称‘LBLC‘) 算法是针对请求报文的目标 IP 地址的 负载均衡调度，目前主要用于 Cache 集群系统，因为在 Cache 集群客户请求报文的目标 IP 地址是变化的。这里假设任何后端服务器都可以处理任一请求，算法的设计目标是在服务器的负载基本平衡情况下，将相同目标 IP 地址的请求调度到同一台服务器，来提高各台服务器的访问局部性和 Cache 命中率，从而提升整个集群系统的处理能力。

LBLC 调度算法先根据请求的目标 IP 地址找出该目标 IP 地址最近使用的服务器，若该服务器是可用的且没有超载，将请求发送到该服务器; 若服务器不存在，或者该服务器超载且有服务器处于一半的工作负载，则使用‘最少连接‘的原则选出一个可用的服务器，将请求发送到服务器。

8. 带复制的基于局部性的最少连接（LBLCR）

带复制的基于局部性的最少连接 (Locality-Based Least Connections with Replication 简称‘LBLCR‘) 算法也是针对目标 IP 地址的负载均衡，目前主要用于 Cache 集群系统，它与 LBLC 算法不同之处是它要维护从一个目标 IP 地址到一组服务器的映射，而 LBLC 算法维护从一个目标 IP 地址到一台服务器的映射。按‘最小连接‘原则从该服务器组中选出一一台服务器，若服务器没有超载，将请求发送到该服务器; 若服务器超载，则按‘最小连接‘原则从整个集群中选出一台服务器，将该服务器加入到这个服务器组中，将请求发送到该服务器。同时，当该服务器组有一段时间没有被修改，将最忙的服务器从服务器组中删除，以降低复制的程度。

9. 最短的期望的延迟

最短的期望的延迟调度 (Shortest Expected Delay 简称‘SED‘) 算法基于 WLC 算法。举个例子吧，ABC 三台服务器的权重分别为 1、2、3 。那么如果使用 WLC 算法的话一个新请求进入时它可能会分给 ABC 中的任意一个。使用 SED 算法后会进行一个运算

A：(1+1)/1=2 B：(1+2)/2=3/2 C：(1+3)/3=4/3 就把请求交给得出运算结果最小的服务器。

10. 最少队列调度

最少队列调度 (Never Queue 简称‘NQ‘) 算法，无需队列。如果有台realserver的连接数＝0就直接分配过去，不需要在进行sed运算。

内核版本 4.15 版本后新增调度算法：FO和OVF

FO（Weighted Fail Over）调度算法,在此FO算法中，遍历虚拟服务所关联的真实服务器链表，找到还未过载（未设置IP_VS_DEST_F_OVERLOAD标志）的且权重最高的真实服务器，进行调度

OVF（Overflow-connection）调度算法，基于真实服务器的活动连接数量和权重值实现。将新连接调度到权重值最高的真实服务器，直到其活动连接数量超过权重值，之后调度到下一个权重值最高的真实服务器,在此OVF算法中，遍历虚拟服务相关联的真实服务器链表，找到权重值最高的可用真实服务器。一个可用的真实服务器需要同时满足以下条件：

-未过载（未设置IP_VS_DEST_F_OVERLOAD标志） -真实服务器当前的活动连接数量小于其权重值

-其权重值不为零

LVS的调度算法

原文：https://www.cnblogs.com/quhz/p/15123138.html