CDN全局流量调度算法介绍
摘要
本文主要介绍了CDN全局流量调度系统。首先给出了全局流量调度系统的基本流程和设计目标，然后简述了现有的流量调度系统的工作原理和方式，重点阐述了三种新开发的全局流量调度算法：基于负载能力的调度算法、基于链路的调度算法和基于成本的调度算法。
一、流量调度的基本流程
目前CDN系统流量调度是通过DNS解析来实现的，其基本原理如下图1所示。
用户想要访问某个图片的url，分为四步：
1、用户来自某个区域（如Beijing TelCom）的用户，想访问特定Url（如http://www.taobao.com/001.jpg），应该去哪个IP地址访问
2、TGTM根据链路信息、成本信息或节点负载信息等因素，决定让该区域的用户访问CDN 1节点
3、用户根据DNS解析返回的IP地址访问CDN 1节点，并请求该图片的内容
4、CDN1节点接收并处理用户的请求，然后将客户请求的图片返回
上面的流程是在用户的浏览器或者LDNS(Local DNS)没有对DNS解析结果进行缓存的情况下的流程，对于有缓存的系统，浏览器会从缓存中取到域名解析结果，因此流量调度策略无法影响已经缓存了DNS解析结果的用户请求，这部分请求对应的访问流量并不受调度系统的指挥，这对流量调度系统有一定的影响。
二、调度目标
CDN系统目前承载者淘宝网大约90%的流量，全局流量调度系统需要解决的问题是如何将如此大的访问流量合理分配到分布在各地的CDN边缘节点。
对于全局流量调度系统而言，设计目标有两个：
(1)提升用户体验
(2)节约系统成本
这两个目标本身都包含很多的方面，但提取其最核心的要求，分别对应
(1)降低用户访问CDN节点的延迟
(2)降低CDN节点的带宽成本
本文的内容就是围绕这两个目标来介绍的。
三、现有调度策略介绍
现有的CDN全局流量调度是通过商用的F5 BigIP GTM(以前称为3DNS)来实现的。F5的系统提供了Round Robin等12种局域负载均衡算法和Global Availability等15种广域负载均衡算法，其中这些负载均衡算法按照调度策略是静态配置还是动态生成的分为静态调度方法和动态调度算法。具体的内容参考F5网站上的相关文档?F5 Networks
目前淘宝CDN系统的流量调度采用的是Topology+ratio的策略，下面对该调度策略进行具体介绍。
3.1 基本概念介绍
下面的概念摘自百科上易统整理的文档GSLB概念介绍
Classless InterDomain Routing ，是一种为解决地址耗尽，提高地址的利用效率而提出的一种措施 218.30.29.0/25 218.30.28.0/25 218.30.27.0/25 218.30.26.0/2
一组CIDR组合后的名称，主要是为了配置和检索方便 region_db user { region { name “CDN_WangSu” “FujianTelcom” “GansuTelcom” “HainanNetcom } region { name “FujianTelcom” 218.85.157.0/24 220.162.0.0/16 211.148.224.0/19 220.160.0.0/15 }
用于管理从Region到Pool之间的映射关系
topology {
// server ldns score
pool.”img01_WangSu_pool” user.”CDN_WangSu” 900
pool.”img02_WangSu_pool” user.”CDN_WangSu” 900
pool.”img03_WangSu_pool” user.”CDN_WangSu” 900
pool.”img04_WangSu_pool” user.”CDN_WangSu” 900
pool.”img01_guangdongtel_pool” user.” TB_CDN_GZ_1_MB ” 900
pool.”img02_guangdongtel_pool” user.” TB_CDN_GZ_1_MB ” 900
}
客户在使用CDN服务后将域名CNAME给CDN服务提供商的域名如image.sohu.com是用户的域名，在使用CDN服务后会CNAME到image.sohu.chinacache.net，后者就被称为wideip
wideip {
name “img02.gslb.taobao.com”
pool_lbmode topology
partition “Common”
last resort
pool “img02_tel_pool”
pool “img02_southcnc_pool”
pool “img02_northcnc_pool
}
为wideip服务的一组VIP或CNAME的集合
pool {
name “img02_southcnc_pool”
ttl 300
monitor all “tcp”
preferred rr
partition “Common”
member 218.108.237.202:80
member 218.108.237.212:80
}
供Pool调度的基本元素，在CDN系统中，member用于表示一个CDN节点
member 218.108.237.202:80
Virtual IP 配置在四层交换上的公网IP和端口的组合，通过地址映射对应四层交换后一台或多台内网设备如果没有四层交换，可以借指设备上直接配置的公网IP和端口的组合与member元素相对应
3.2 基本对象之间的关系
上述基本对象的关系如下图所示
3.3 现有的流量调度方法
现有的系统工作流程是这样的：
（1）管理员根据经验预先设置好用户区域的拓扑关系，并通过设置Topology定义好为各个区域服务的Pool
（2）当一个DNS解析请求到达时，调度系统根据用户LDNS的IP地址来判断出该用户所在区域，然后根据Topology的设定找出为该区域服务的Pool
（3）当Pool中有多个member时，所有到达该pool的请求按照各个member的ratio值来进行分配。例如，系统中有3个member，其ratio分别为100,100,200，则到达该pool的所有请求将按照25%,25%和50%的比例分配到各个member
上述策略总体上可以看成一种静态的调度策略，当系统中出现节点不可用、节点过载或者特定区域访问对应的节点延迟过大等情况时，只能等到管理员发现后对配置文件进行一定的调整之后才能解决。
四、新的流量动态调度算法
根据文中第二部分提出的调度算法设计目标，为当前系统设计了三种动态调度算法，分别是基于负载的调度算法，基于链路的调度算法和基于成本的调度算法。综合考虑链路、成本和负载的调度算法尚未进行设计和实现。
4.1 基于负载的调度算法
4.1.1 算法原理介绍
基于负载的调度算法是最早实现的一种调度算法，考虑的是在一组节点服务特定区域的用户时，用户访问这些节点的链路状况接近、节点的带宽成本也接近的前提下，如何保证访问这些节点的流量在各个节点之间按照节点的实时负载能力来分配。
举个例子来说，假设上海地区的电信用户访问cn12和cn15的链路状况类似，cn12和cn15的带宽成本也接近，如何将上海地区电信用户的访问流量按照cn12、cn15的实时负载能力来进行分配，以保证两个节点的负载相对于其负载能力来说是均衡的。
基于负载的流量调度算法采用的是负反馈调度算法。负反馈是一种基于偏差的调度算法，简而言之，当系统输出同期望值不相等时，控制系统根据系统输出和期望值之间的偏差来对系统施加控制作用，负反馈调度算法的框图如下图所示
可以看出，系统的控制量同偏差是一种负反馈的关系。
应用到基于负载的调度算法中来，当分配给某个节点的流量同其负载能力相比偏小时（偏差为负），我们应该增大分配给该节点的流量，反之，则减小分配给该节点的流量。
4.1.2 调度算法实现
基于负载的调度算法是建立在能够获取节点的服务质量（QOS）的前提下，因此如何获取节点的实时QOS是首先必须解决的一个问题。
目前CDN系统是通过部署在CDN节点内部的监控系统来获取节点的实时QOS数据。QOS数据中最重要的两项是节点的当前负载和节点的最大可用负载能力。节点的当前负载是通过统计交换机的出口流量得到的，而最大可用负载则是根据各缓存服务器的健康状况得出的。
调度系统通过监控系统提供的Web Services接口实时查询各个CDN节点的当前性能状况，然后根据负反馈调度算法生成流量分配策略。
在一定误差范围内保持同一个pool内所有节点的ratio之和固定，记为
RATIO_SUM，
设节点i的当前流量为
cur_loadi
系统内当前的总流量为
sumi=1-n(cur_load)
并设第i个ECC节点当前的负载能力（即上述的max_usable_load）记为
max_usable_loadi，
pool内所有节点的当前负载能力之和记为
sumi=1-n(max_usable_load)
则i节点在系统内应分担的负载流量比例记为
proportioni=max_usable_loadi/sumi=1-n(max_usable_load)
按照节点的当前负载能力，节点i的期望ratio是
ratioie=RATIO_SUM*proportioni
节点i的当前期望负载应为
cur_loadie=sumi=1-n(cur_load)*proportioni
节点i的实际负载与期望负载的偏差为
diffi=cur_loadi-cur_loadie
节点i当前ratio的调整值为
delta_ratioi = -P*diffi/sumi=1-n(cur_load)*RATIO_SUM
同时，为了防止流量调节过程中各节点流量出现剧烈颠簸，设置各节点ratio的调节范围为
[(1-Th)*ratioie, (1+Th)*ratioie]
总结一下：
ratio(n+1) = ratio(n) + delta_ratioi
= ratio(n)-P*diffi/sumi=1-n(cur_load)*RATIO_SUM
= ratio(n)-P*(cur_loadi-cur_loadie)/sumi=1-n(cur_load)*RATIO_SUM
= ratio(n)-P*(cur_loadi-sumi=1-n(cur_load)*proportioni)/sumi=1-n(cur_load)*RATIO_SUM
= ratio(n)-P*(cur_loadi-sumi=1-n(cur_load)*(max_usable_loadi/sumi=1-n(max_usable_load)))/sumi=1-n(cur_load)*RATIO_SUM
if(ratio(n+1) = (1+Th)*ratioie)
{
ratio(n+1) = (1+Th)*ratioie;
}
上式中的P为负反馈比例系数，可以控制负载得到期望值的时间，P越大，（在一定误差范围内）达到期望值的时间越短，同时系统流量的波动也越大。P过大甚至可能造成系统的不稳定。
4.2 基于链路的调度算法
4.2.1 总体介绍
基于链路的调度算法的最终目标是使得全网内各区域用户访问淘宝的延迟最小，这个问题是一个最优化的问题，实际解决起来很困难，只能随着对系统了解的不断深入，逐步优化算法。
目前基于链路的调度算法的目标是尽量保证用户访问淘宝的延迟在给定的阈值之内，也就是说，调度的目标是对访问延迟提供一定的保证，但并不能做到最优。
基于链路的基本思想是将链路延迟超过阈值的流量调度到链路延迟较好的链路上去，以确保所有区域的用户访问链路延迟都较好。
同基于负载的调度算法类似，基于链路的调度算法需要节点和网络的QOS数据，这里除了需要获取各个节点的当前负载、最大可用负载数据之外，还需要获得特定区域访问CDN节点的链路延迟。
各个节点的当前负载、最大可用负载等QOS数据依然是通过部署在节点内部的监控系统获取的，而各区域用户访问CDN节点的链路延迟数据则是通过淘宝的客户端链路探测工具Aliprobe的探测结果统计得到的。
目前链路探测的最主要数据有ping time和ping命令的丢包率，而区域和节点之间的链路信息则是通过综合部署在指定区域的所有Aliprobe探测客户端获取的访问指定节点的链路信息统计、综合得到的。
在基于链路的调度算法中，我们对每一个感兴趣的调度区域，根据其地理位置和系统运维经验为其指定一个默认的服务节点和一组备选的服务节点，并将这些节点组成一个pool，该pool专门为该区域的用户服务。
基于链路的调度算法必须考虑到下列异常情况：
（1）CDN节点的当前负载、最大可用负载等负载类QOS数据无法获取
（2）区域到节点的链路QOS数据无法获取
（3）节点不可用
（4）节点过载
4.2.2 算法的实现
基于链路的调度算法流程如下：
Step 1 调度周期开始，尝试获取节点的健康状况检查结果、节点类的负载类QOS数据、区域同节点之间的链路类QOS数据
Step 2 遍历所有感兴趣的区域
2.1) 将当前区域的备选节点分为以下四类：
class 1: good 节点健康、链路类QOS数据能得到并且链路延迟没有超过给定阈值、负载类QOS数据能得到、节点没有超载（所有good节点中链路延迟最小的一个节点叫做最佳备选节点）
class 2: bad 节点健康，链路类QOS数据能得到并且链路延迟超过给定阈值
class 3: unhealthy 节点不健康
class 4: other 不属于上面三类的节点
2.2） 处理区域的默认节点
2.2.1 如果默认节点不健康，则尝试将默认节点的所有流量调度到备选节点中
2.2.1.1 如果该区域有good备选节点存在，则将默认节点的流量均分到所有good备选节点
2.2.1.2 否则，报警
2.2.2 如果区域用户访问默认节点的链路不佳，则尝试将默认节点的一小部分流量（比例可配）调度到最佳备选节点中
2.2.2.1 如果该区域存在最佳备选节点，将默认节点的一小部分流量调度到该最佳备选节点
2.2.2.2 否则，报警
2.3） 处理区域的多个备选节点
2.3.1） 如果备选节点不健康
2.3.1.1） 如果默认节点可以接收更多的流量，则将不健康节点的流量都切到默认节点上，否则转下一步
2.3.1.2） 如果存在good备选节点，则将不健康节点的流量均分到good备选节点上，否则转下一步
2.3.1.3） 报警
2.3.2） 如果备选节点链路不好
2.3.2.1） 如果默认节点可以接收更多的流量，则将不健康节点流量的一部分切到默认节点上，否则转下一步
2.3.2.2） 如果存在最佳备选节点，则将不健康节点流量的一部分切到最佳备选节点上，否则转下一步
2.3.2.3） 否则，报警
2.3.3） 如果默认节点能够接受更多的流量
2.3.3.1） 如果存在good备选节点，则将所有good备选节点的部分流量切回默认节点
2.3.3.2） 如果存在other备选节点，则将所有other备选节点的部分流量切回默认节点
Step 3 遍历所有过载节点
对于每一个过载节点，首先报警，然后找出其所服务区域中所有不以该节点为默认节点的区域，尝试将区域流量的一部分切回区域对应的默认节点。如果找不到不以该节点为默认节点的区域，则报警
Step 4 开始新一轮的调度，转Step 1
其中， Step 2中根据链路延迟进行调度的流程如下图所示：
4.2.3 算法存在的问题
目前系统无法得知某一区域用户的访问流量值，所以在本调度算法中将区域访问流量在节点之间调度时的具体流量值是无法得到的，为了防止调度过程中流量出现大的波动，每个调度周期调度的流量都会很小，但调度幅度小必然导致调度效果显现的时间会比较长。
另外，目前基于链路的调度算法中会有一个比较关键的阈值（最大延迟，超过该阈值会认为链路差，否则认为链路好），该阈值是通过经验设置的，但实际上这个值在不同的时间段，不同的网络状况下应该是不同的，并且应该随着时间的变化而变化，该阈值的设置仍有较大的改进空间。
4.3 基于成本的调度算法
4.3.1 CDN节点的带宽成本模型
CDN的带宽成本可以分成保底带宽和流量成本两部分。其中保底带宽指的是只要使用该节点就必须支付的费用，而流量成本指的是在保底带宽之上，按照实际使用的流量来支付费用。节点的带宽成本模型如下图所示：
4.3.2 算法设计和实现
基于成本的调度算法的目标是使得系统的带宽成本最小，这里采用的贪婪算法来实现流量的调度
算法简述如下：
（1）如果系统当前总的流量小于所有节点的保底带宽之和，则将流量按照各节点的保底带宽占所有保底带宽之和的比来分配流量
（2）如果系统当前流量大于所有节点的保底带宽之和，则首先将所有节点的保底带宽使用满，然后依次选取各节点中带宽成本最低的节点，将该节点的负载能力用完为止。
算法流程如下图所示：
在实际实现时，由于调度过程中流量有可能出现波动，所以必须保证出现波动时不会出现问题。举例来说，如果某一节点的保底带宽是1G，如果分配给该节点的流量就是1G，但由于流量出现波动，就会出现除了需要支付保底带宽费用之外，还需要支付一部分超出保底带宽的费用，这是我们所不希望看到的。因此，我们在处理保底带宽和阶梯价格上限时留有一定的裕量。
五、总结
文中首先简要介绍了CDN全局流量调度系统的一些基本概念和基于DNS解析的流量调度实现方法，给出了CDN系统全局流量调度的目标，然后描述了现有流量调度系统的工作方式，重点介绍了三种新开发的全局动态流量调度算法：基于负载能力的调度算法、基于链路的调度算法和基于成本的调度算法。
调度算法的优化是一个持续的过程，现有的调度算法在准确性和最优性方面有一些欠缺，需要做更进一步的工作。
来源：http://rdc.taobao.com/blog/cs/?p=315
