Real Server调度算法上文提到的负载均衡技术均涉及对后端服务器的选择和转发,这是负载均衡技术(包括四层负载均衡和七层负载均衡)中非常重要的一点。 本节主要介绍常用的调度算法,这里以爱奇艺在负载均衡方面的实践方案——DPVS开源软件中的实现为例来进行阐述。 轮询(RR) 轮询算法是最常见的一种负载均衡调度算法,从字面意思即可理解,该算法会依次选择后端服务器进行调度。每台后端服务器都被选择后,该算法会再从头开始重新轮流选择一遍。 下面给出DPVS中轮询算法的核心代码: 加权轮询(WRR) 当后台服务器一台是物理机,另一台是单核的虚拟机时,两者的吞吐能力显然不是一个数量级的。这时使用轮询算法对后端服务器进行调度显然不合适。加权轮询算法就显现出了它的优势,它可以根据后台服务器的吞吐能力来分配不同的权重。 首先,在所有的服务器的权重中求出最大公约数和最大权重,并记录下来。其中,当前权重cw事实上在第一次调度时会被设置成最大权重mw,代码如下: 当要调度后端服务器时,开始轮询后端服务器的权重,当找到第一个比cw大的权重时,就停止搜索,直接选中该后端服务器。当轮询一遍后又到达最大的权重的服务器时,cw需要减去最大公约数,然后继续遍历搜索,此过程的核心代码如下: 需要注意的是,每次修改RS,都要重新生成最大公约数和最大权重值。 最少连接调度(LC) 最少连接调度一般是针对四层负载均衡的调度算法。它根据当前四层负载均衡和后端服务器之间的连接数量(包含活跃连接和非活跃连接)来选择一个连接最少的后端服务器进行调度。该调度算法的实现较为简单,只要能实时读出每台后端服务器的当前连接数目即可。该算法的代码会合并到下一节来解释。 加权最少连接调度(WLC) 加权最少连接调度是对最少连接调度的一种升级,即认为每台服务器可承受的最大连接数目是不一样的,可以自由地分配每个RS的权重,以当前连接/权重值最小的服务器作为调度目标。加权最少连接调度算法的核心代码如下: 一致性哈希(CONNHASH) 在很多场景下,我们希望同一个客户端的请求落到同一台后端服务器中,这时就会用到哈希算法。常用的哈希算法通常都会在后端服务器变动后重新统计一下哈希结果。 比如,当一台后端服务器宕机后,我们会重新计算客户端的分布,把不同的客户端请求重新分配到剩下的正常服务的后端服务器上。但是,这常常会影响其他提供正常服务的后端服务器。在理想的情况下,我们不希望使已有的分布好了的客户端请求受到影响。 又如,我们提供了一个有状态的数据库服务,多台后端服务器各自维护自己关联的客户端的数据。当一台后端服务器宕机后,受到影响的应该只有连接这台后端服务器的客户端。 但是,传统的哈希算法会对所有的客户端再进行一次哈希分布,正常提供服务的后端服务器的连接也要重新分配。这会导致大量的客户端受到影响,很多数据无法同步。这对很多服务来说是不可接受的。有没有一种办法可以使其他不变的后端服务器通过哈希算法映射到一样的位置呢?在这种场景下,一致性哈希算法应运而生。 一致性哈希算法由麻省理工学院的Karger等人提出。由于目前有很多一致性哈希算法的资料,所以下面针对一些概念进行简单的阐述,希望有助于读者理解一致性哈希算法。 1.哈希环 将从0~2 32-1的哈希键值依次分布到一个哈希环上。其中,0和2 32-1首尾相接,如下图所示,所有经过哈希算法处理后的数据的键值都会分布到哈希环上。 2.哈希环的映射 假设有4个客户端,则经过哈希算法处理后,分布到哈希环上的键值分别是key1、key2、key3、key4,如下图所示: 同时,有3台服务器,通过一定的哈希算法映射到哈希环上,即S1、S2、S3,如下图所示: 4个客户端顺时针查找离自己键值最近的服务器键值,即可找到对应的服务器。假设服务器S1宕机了,则只有之前落到服务器S1的客户端key4才会受到影响,它会落到服务器S2。 其他的客户端都还是如之前一样落到相应的服务器。假设在客户端key2和key3之间增加了一台服务器S4,则只有客户端key2才会受到影响,它会落到服务器S4。假设在服务器S3和客户端key4之间增加一台服务器S4,则不会有客户端会落到服务器S4。 从上面的实例中可以看出,通过一致性哈希算法处理得到的部分在很多时候是不均匀的。为此,一致性哈希算法引入了虚拟节点的概念。每台真实的服务器拥有多个虚拟节点。落到虚拟节点的服务器可以找到对应的真实服务器。虚拟节点的均匀分布可以大大减少大量的客户端落到单个虚拟节点上的可能性。 如图所示: 当某个客户端映射到哈希环上的keyn想找到自己对应的服务器时,它会依照一致性哈希算法先找到VS3这个虚拟节点,再根据虚拟节点的映射关系找到对应的真实的服务器Sn。 连接模板 连接模板是一种特殊的调度算法。它的存在主要是配合其他的调度算法去实现类似哈希算法。即在不改变当前调度算法的前提下,将来自同一个客户端的请求转发到同一台服务器。 当客户端连接到负载均衡器时,新建的连接模板会记录这个请求的来源、分配到的后端服务器、模板需要保持的时间。 例如,设置模板需要保持的时间是300s,如果在300s内有接收到来自同一个客户端的请求,则走这个连接模板调度的后端服务器,同时把这个连接模板的超时时间再重置为300s。 如果300s内没有来自模板内客户端的数据包,则释放连接模板。当下次再有之前的客户端请求时,重新调度后端服务器,就不能再保证和之前调度的后端服务器是一致的了。 本文给大家讲解的内容是负载均衡详细介绍-RealServer调度算法
|
|