LVS调度算法

内核中的连接调度算法

IPVS在内核中的负载均衡调度是以连接为粒度的。在HTTP协议(非持久中),每个对象从WEB服务器上获取都需要建立一个TCP连接,同一用户的不同请求会被调度到不同服务器上,所以这种细粒度的调度在一定程度上可以避免单个用户访问的突发性引起服务器间的负载不平衡。

在内核中的连接调度算法上,IPVS已实现了以下八种调度算法:

  • 轮叫调度(Round-Robin Scheduling)
  • 加权轮叫调度(Weighted Round-Robin Scheduling)
  • 最小连接调度(Least-Connection Scheduling)
  • 加权最小连接调度(Weighted Least-Connection Scheduling)
  • 基于局部性的最少链接(Locality-Based Least Connections Scheduling)
  • 带复制的基于局部性最少链接(Locality-Based Least Connections with Replication Scheduling)
  • 目标地址散列调度(Destination Hashing Scheduling)
  • 源地址散列调度(Source Hashing Scheduling)

1、轮叫调度

该算法是以轮叫的方式依次将请求调度不同的服务器,即每次调度执行i = (i + 1)mod n,并选出第i台服务器。算法的优点是简单,它无需记录当前所有连接的状态。它是一种无状态调度。

在系统实现时,我们引入一个额外条件,当服务器的权值为零时,表示该服务器不可用而不被调度。这样做的目的是将服务器切出任务(如屏蔽服务器故障和维护),同时与其他加权算法保持一致。所以,算法要作相应的改动,算法流程如下:

假设有一组服务器S = {S0, S1, …, Sn-1},一个指示变量i表示上一次选择的
服务器,W(Si)表示服务器Si的权值。变量i被初始化为n-1,其中n > 0。

j = i;
do {
	j = (j + 1) mod n;
	if (W(Sj) > 0) {
		i = j;
		return Si;
	}
} while (j != i);
return NULL;  

轮叫调度算法假设所有服务器性能均相同,不管服务器当前连接数和响应速度,该算法简单,不适用于服务器组中处理性能不一样的情况,而且当请求服务时间比较大时,轮叫调度算法容易导致服务器间的负载不平衡。

2、加权轮叫调度

该算法可以解决服务器间性能不一的情况,它是相应的权值表示服务器的处理性能,服务器的缺省值为1。假设服务器A的权值为1,B的权值为2,则表示服务器的处理性能是A的两倍。加权轮叫算法是按权值的高低和轮叫方式分配请求到各台服务器。加权值高的先收到的连接,权值高的服务器处理更多的连接,相同权值的服务器处理相同的连接数。算法流程如下:

假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个
指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)
表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大
公约数。变量i初始化为-1,cw初始化为零。

while (true) {
  i = (i + 1) mod n;
if (i == 0) {
     cw = cw - gcd(S); 
     if (cw <= 0) {
       cw = max(S);
       if (cw == 0)
         return NULL;
     }
  } 
  if (W(Si) >= cw) 
    return Si;
}

  例如,有三个服务器A、B和C分别有权值4/3/2,则在一个调度周期内,顺序为AABABCABC.次方法也比较简单,高效。当请求的服务时间变化很大,单独的加权轮叫调度算法依然会导致服务器之间负载不平衡

3、最小连接调度

该算法是将新的连接请求分配到当前连接数最小的服务器,最小调度是一种动态调度算法,它通过服务器当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个服务器已连接的数目,当一个请求被调度到某台服务器时,其连接数加1;当连接中止或超时,其连接数减一。

在系统实现时,我们也引入当服务器权值为零时,表示该服务器不可用或不可被调度,算法流程如下:

假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。

for (m = 0; m < n; m++) {
	if (W(Sm) > 0) {
		for (i = m+1; i < n; i++) {
			if (W(Si) <= 0)
				continue;
			if (C(Si) < C(Sm))
				m = i;
		}
		return Sm;
	}
}
return NULL;

4、加权最小连接调度

该算法是最小连接调度的超集,各个服务器用相应的权值表示其处理能力。服务器的缺省值为1,系统管理员可以动态的设置服务器的权值。加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。

假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。所有服务器当前连接数的总和为
CSUM = ΣC(Si)  (i=0, 1, .. , n-1)。当前的新连接请求会被发送服务器Sm,
当且仅当服务器Sm满足以下条件
  (C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)}  (i=0, 1, . , n-1)
  其中W(Si)不为零
因为CSUM在这一轮查找中是个常数,所以判断条件可以简化为
  C(Sm) / W(Sm) = min { C(Si) / W(Si)}  (i=0, 1, . , n-1)
  其中W(Si)不为零

因为除法所需的CPU周期比乘法多,且在Linux内核中不允许浮点除法,服务器的
权值都大于零,所以判断条件C(Sm) / W(Sm) > C(Si) / W(Si) 可以进一步优化
为C(Sm)*W(Si) > C(Si)* W(Sm)。同时保证服务器的权值为零时,服务器不被调
度。所以,算法只要执行以下流程。

for (m = 0; m < n; m++) {
	if (W(Sm) > 0) {
		for (i = m+1; i < n; i++) {
			if (C(Sm)*W(Si) > C(Si)*W(Sm))
				m = i;
		}
		return Sm;
	}
}
return NULL;

  参考:http://www.linuxvirtualserver.org/zh/lvs4.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯云serverless的专栏

使用 Serverless 进行 AI 预测推理

本文演示如何使用腾讯云的 SCF 无服务器云函数来实现 AI Serving 能力。

6.2K61
来自专栏ATYUN订阅号

将Keras深度学习模型部署为Web应用程序

建立一个很酷的机器学习项目确实很不错,但如果你希望其他人能够看到你的作品怎么办呢?当然,你可以将整个项目放在GitHub上,但这只能给程序员看,如果你想给自己家...

5681
来自专栏ChaMd5安全团队

三个有趣的脱壳例子

最近看了youtube上的一些视频教程,看到了几个有趣的脱壳方式。这里介绍下。具体的视频教程在MalwareAnalysisForHedgehogs和hashe...

4045
来自专栏专知

推荐一些有助于理解TensorFlow机制的资料(二)

1923
来自专栏大数据文摘

手把手:我的深度学习模型训练好了,然后要做啥?

3752
来自专栏点滴积累

geotrellis使用(十七)使用缓冲区分析的方式解决单瓦片计算边缘值问题

Geotrellis系列文章链接地址http://www.cnblogs.com/shoufengwei/p/5619419.html 目录 前言 需求分析 ...

3206
来自专栏AI研习社

Github 项目推荐 | 半自动图像标记工具

在构建可以从任何场景检测物体的人工智能系统时,我们需要一个庞大的数据集来训练和测试模型,并发现模型的缺点。现有的图像注释工具能够提供一定的帮助,但是开发者仍要付...

1383
来自专栏Python小屋

Python使用matplotlib进行可视化时精确控制图例位置

在进行数据可视化或者科学计算可视化时,显示图例会显得很高大上,但是如果能够精确控制图例的显示位置,无疑会显得档次更高。 本文以matplotlib.pyplot...

3536
来自专栏量子位

简化深度学习实践流程:新鲜出炉的TensorFlow项目模板来了

林鳞 编译自 GitHub 量子位 出品 | 公众号 QbitAI 新的TensorFlow项目模板来了。 昨天,用户mrgemy95在Reddit上发帖,称这...

4434
来自专栏AI研习社

Github 项目推荐 | 基于 Unity/OpenAI Gym/PyTorch/TF 的深度强化学习研究框架

SLM Lab 是一个基于 Unity, OpenAI Gym, PyTorch, Tensorflow 的深度增强学习研究框架。

2242

扫码关注云+社区

领取腾讯云代金券