CDN全局流量调度算法介绍
作者 陈怀临 | 2010-07-06 05:54 | 类型 行业动感 | 3条用户评论 »
【陈怀临注:大荣推荐的一篇文章。愣是马(云)仔的子弟兵写的。很不错的一个总结(原文链接)】 本文主要介绍了CDN全局流量调度系统。首先给出了全局流量调度系统的基本流程和设计目标,然后简述了现有的流量调度系统的工作原理和方式,重点阐述了三种新开发的全局流量调度算法:基于负载能力的调度算法、基于链路的调度算法和基于成本的调度算法。 一、流量调度的基本流程 目前CDN系统流量调度是通过DNS解析来实现的,其基本原理如下图1所示。 用户想要访问某个图片的url,分为四步: 1、用户来自某个区域(如Beijing TelCom)的用户,想访问特定Url(如http://www.taobao.com/001.jpg),应该去哪个IP地址访问 上面的流程是在用户的浏览器或者LDNS(Local DNS)没有对DNS解析结果进行缓存的情况下的流程,对于有缓存的系统,浏览器会从缓存中取到域名解析结果,因此流量调度策略无法影响已经缓存了DNS解析结果的用户请求,这部分请求对应的访问流量并不受调度系统的指挥,这对流量调度系统有一定的影响。 二、调度目标 CDN系统目前承载者淘宝网大约90%的流量,全局流量调度系统需要解决的问题是如何将如此大的访问流量合理分配到分布在各地的CDN边缘节点。 对于全局流量调度系统而言,设计目标有两个: (1)提升用户体验 这两个目标本身都包含很多的方面,但提取其最核心的要求,分别对应 (1)降低用户访问CDN节点的延迟 本文的内容就是围绕这两个目标来介绍的。 三、现有调度策略介绍 目前淘宝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之间的映射关系 客户在使用CDN服务后将域名CNAME给CDN服务提供商的域名如image.sohu.com是用户的域名,在使用CDN服务后会CNAME到image.sohu.chinacache.net,后者就被称为wideip 为wideip服务的一组VIP或CNAME的集合 供Pool调度的基本元素,在CDN系统中,member用于表示一个CDN节点 Virtual IP 配置在四层交换上的公网IP和端口的组合,通过地址映射对应四层交换后一台或多台内网设备如果没有四层交换,可以借指设备上直接配置的公网IP和端口的组合与member元素相对应 3.2 基本对象之间的关系 上述基本对象的关系如下图所示
3.3 现有的流量调度方法 现有的系统工作流程是这样的: 上述策略总体上可以看成一种静态的调度策略,当系统中出现节点不可用、节点过载或者特定区域访问对应的节点延迟过大等情况时,只能等到管理员发现后对配置文件进行一定的调整之后才能解决。 四、新的流量动态调度算法 根据文中第二部分提出的调度算法设计目标,为当前系统设计了三种动态调度算法,分别是基于负载的调度算法,基于链路的调度算法和基于成本的调度算法。综合考虑链路、成本和负载的调度算法尚未进行设计和实现。 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之和固定,记为 if(ratio(n+1) = (1+Th)*ratioie) 4.2 基于链路的调度算法 4.2.1 总体介绍 基于链路的调度算法的最终目标是使得全网内各区域用户访问淘宝的延迟最小,这个问题是一个最优化的问题,实际解决起来很困难,只能随着对系统了解的不断深入,逐步优化算法。 目前基于链路的调度算法的目标是尽量保证用户访问淘宝的延迟在给定的阈值之内,也就是说,调度的目标是对访问延迟提供一定的保证,但并不能做到最优。 基于链路的基本思想是将链路延迟超过阈值的流量调度到链路延迟较好的链路上去,以确保所有区域的用户访问链路延迟都较好。 同基于负载的调度算法类似,基于链路的调度算法需要节点和网络的QOS数据,这里除了需要获取各个节点的当前负载、最大可用负载数据之外,还需要获得特定区域访问CDN节点的链路延迟。 各个节点的当前负载、最大可用负载等QOS数据依然是通过部署在节点内部的监控系统获取的,而各区域用户访问CDN节点的链路延迟数据则是通过淘宝的客户端链路探测工具Aliprobe的探测结果统计得到的。 目前链路探测的最主要数据有ping time和ping命令的丢包率,而区域和节点之间的链路信息则是通过综合部署在指定区域的所有Aliprobe探测客户端获取的访问指定节点的链路信息统计、综合得到的。 在基于链路的调度算法中,我们对每一个感兴趣的调度区域,根据其地理位置和系统运维经验为其指定一个默认的服务节点和一组备选的服务节点,并将这些节点组成一个pool,该pool专门为该区域的用户服务。 基于链路的调度算法必须考虑到下列异常情况: 4.2.2 算法的实现 基于链路的调度算法流程如下: Step 1 调度周期开始,尝试获取节点的健康状况检查结果、节点类的负载类QOS数据、区域同节点之间的链路类QOS数据 Step 2 遍历所有感兴趣的区域 2.1) 将当前区域的备选节点分为以下四类: class 1: good 节点健康、链路类QOS数据能得到并且链路延迟没有超过给定阈值、负载类QOS数据能得到、节点没有超载(所有good节点中链路延迟最小的一个节点叫做最佳备选节点) 2.2) 处理区域的默认节点 2.3) 处理区域的多个备选节点 Step 3 遍历所有过载节点 对于每一个过载节点,首先报警,然后找出其所服务区域中所有不以该节点为默认节点的区域,尝试将区域流量的一部分切回区域对应的默认节点。如果找不到不以该节点为默认节点的区域,则报警 Step 4 开始新一轮的调度,转Step 1 其中, Step 2中根据链路延迟进行调度的流程如下图所示: 4.2.3 算法存在的问题 目前系统无法得知某一区域用户的访问流量值,所以在本调度算法中将区域访问流量在节点之间调度时的具体流量值是无法得到的,为了防止调度过程中流量出现大的波动,每个调度周期调度的流量都会很小,但调度幅度小必然导致调度效果显现的时间会比较长。 另外,目前基于链路的调度算法中会有一个比较关键的阈值(最大延迟,超过该阈值会认为链路差,否则认为链路好),该阈值是通过经验设置的,但实际上这个值在不同的时间段,不同的网络状况下应该是不同的,并且应该随着时间的变化而变化,该阈值的设置仍有较大的改进空间。 4.3 基于成本的调度算法 4.3.1 CDN节点的带宽成本模型 CDN的带宽成本可以分成保底带宽和流量成本两部分。其中保底带宽指的是只要使用该节点就必须支付的费用,而流量成本指的是在保底带宽之上,按照实际使用的流量来支付费用。节点的带宽成本模型如下图所示: 4.3.2 算法设计和实现 基于成本的调度算法的目标是使得系统的带宽成本最小,这里采用的贪婪算法来实现流量的调度 算法简述如下: (1)如果系统当前总的流量小于所有节点的保底带宽之和,则将流量按照各节点的保底带宽占所有保底带宽之和的比来分配流量 算法流程如下图所示: 在实际实现时,由于调度过程中流量有可能出现波动,所以必须保证出现波动时不会出现问题。举例来说,如果某一节点的保底带宽是1G,如果分配给该节点的流量就是1G,但由于流量出现波动,就会出现除了需要支付保底带宽费用之外,还需要支付一部分超出保底带宽的费用,这是我们所不希望看到的。因此,我们在处理保底带宽和阶梯价格上限时留有一定的裕量。 五、总结 文中首先简要介绍了CDN全局流量调度系统的一些基本概念和基于DNS解析的流量调度实现方法,给出了CDN系统全局流量调度的目标,然后描述了现有流量调度系统的工作方式,重点介绍了三种新开发的全局动态流量调度算法:基于负载能力的调度算法、基于链路的调度算法和基于成本的调度算法。 调度算法的优化是一个持续的过程,现有的调度算法在准确性和最优性方面有一些欠缺,需要做更进一步的工作。 | |
雁过留声
“CDN全局流量调度算法介绍”有3个回复
说了一大篇根本就没有解决问题。
DNS配置管理
机房管理
平台管理
加速组管理
节点服务器
数据库服务器
带宽服务器
日志服务器
客户管理
域名管理
弯曲的首页越来越长,是不是很多作者不太熟悉wordpress,在编辑稿件时,有个button可以将文章分为两个部分,这样首页就会简洁一些,方便大家阅读。 建议首席将其作为作者指南之一。
1)CDN的节点是完全相同的,还是可以有不同?
2)新算法是基于DNS解析,还是其他?如果不是DNS解析,那么Load balancer把流量转发到各CDN节点,是不是效率低了点。有中心节点,会出现瓶颈。