网站首页 实验室介绍 科学研究 学术交流 人才队伍 开放课题 招聘信息 联系我们
业内动态

 
 
 分布式QoS算法解析

2020-09-12 12:48:22


       QoS对于服务多租户多业务的整体系统来说,不管对网络还是存储,都格外重要,没有QoS,会造成不同租户及业务之间对资源的抢占。我们今天就来讨论一下分布式存储系统中的QoS算法。进入正题之前,我们先来了解背景知识,即什么是QoS,分布式QoS又是什么,有哪些常见的QoS算法。最后我们再来讨论本文正题:mClock算法和dmClock算法。

什么是QoS

       QoS是Quality of Service的缩写,它起源于网络技术,用以解决网络延迟和阻塞等问题,能够为指定的网络通信提供更好的服务能力。

       放到存储系统中,QoS用来保证一定的存储服务质量,具体一般指如下几个方面:

       1. 为高优先级的业务提供更高的服务质量(包括IOPS、带宽、延时等数据访问服务)。系统服务能力有限,为高优先级业务配置更高的QoS,为低优先级业务配置更低的QoS,合理分配资源,满足不同级别业务的需求。

       2. 控制资源抢夺:比如当存储系统发生故障恢复时,避免集群内部恢复抢夺资源,保证用户业务不受影响。

       可见QoS并没有增加系统服务能力,它只是通过对系统能力的优化分配,保证关键业务服务质量,同时满足普通业务的基本需求。比如系统能力是100,为高优先级业务数据库分配90,为低优先级的后台备份业务分配资源10。

什么是分布式QoS

       那么QoS如何实现?如果所有业务都会通过一个入口进入系统,则系统能感知每个业务对系统资源的用量,在这个入口上做流控,就能做到对资源访问的调控。

       比如在一个Linux服务器上跑多个业务,它们共享同一个ext4本地文件系统,目标要控制每个业务的带宽。我们将QoS算法运行在该服务器上,通过感知每个业务的实时带宽,就能做对各个业务的QoS控制。

       如果有多个Linux服务器上面跑了多个业务,它们通过NFS共享远端同一个ext4文件系统,目标仍然是控制每个业务的带宽。此时QoS算法如果实现在业务端,因为业务跑在多个服务器上,相互间无法感知其它Linux服务器带宽用量,继而无法实现整体的QoS控制。比如服务器A上只跑了一个低优先业务,它认为自己独占存储,继而大压力读写,抢夺了服务器B上高优先级业务的带宽,因此对于分布式业务,通常很难在客户端实现对整体集群的QoS控制。

       但这个场景中,QoS算法可以实现在共享的ext4文件系统端,即NFS server端,因为所有业务流量都会流向这里,故而能感知和控制各个业务端对文件系统的流量要求。

       近年来基于x86服务器的分布式存储系统流行,即在多个x86服务器部署分布式存储软件,构建出一套分布式存储系统,对外提供一套统一的存储服务。如果是分布式块存储,用户可以将这套分布式块存储集群看成一个集中的SAN设备。如果是分布式文件存储,用户则可以将这套分布式文件存储集群当成一个本地文件系统(如ext4, xfs)来用。

       但问题来了,在这样的分布式存储中如何做QoS?

       分布式块存储比较特别,一个虚拟块设备一般仅被一个地方挂载使用,故而可以在这个挂载点做QoS,分布式块存储的QoS也较为成熟和常见。

       所以我们今天主要讨论分布式文件存储。文件系统一般都通过client端mount后进行使用,一个文件系统会服务多个client端,用户业务分布在各个client,因而无法在client端做QoS算法,因为client间对其它client资源用量是不感知的。我们似乎也无法在存储端做QoS算法,尤其是分布式并行文件系统,因为存储端各节点是分布式的,业务数据从不同client端发起,直接流向不同的存储端节点。

       我们将这种场景称之为分布式QoS场景。相比单机QoS场景,它更具挑战。事实上,在分布式文件存储市场上,不管是开源还是商业产品,对共享目录级别的QoS,并不常见。

常见的QoS算法

       令牌桶(token bucket)算法,漏桶(leaky bucket)算法,这是最为常见的两种单机QoS算法。这两种算法网上资料和示例有很多,这里只简单描述。

       令牌桶算法中,系统以指定策略(比如匀速)往桶中放入令牌,业务请求被处理时,需要先从桶中获取令牌。当桶中没有令牌时,业务请求将不被处理。这样能通过控制令牌生成的速率,来控制业务请求被处理的速率。

       漏桶算法中,设想一个漏桶接水,桶里的水将匀速流出。不管业务请求到来有多快,这些请求被处理(即从漏桶流出)的速率都是恒定的。

       二者的区别是,漏桶算法能强行限制业务请求速率,而令牌桶除了能限速之外,还能允许一定的突发请求处理。一般在实现中会结合漏桶和令牌桶算法。

       mClock算法解析

       mClock算法来自VMWare发表于OSDI 2010的论文《mClock: Handling Throughput Variability for Hypervisor IO Scheduling》。

       他们认为,在服务器上跑多个虚拟机(VM),VM里跑各种各样的用户业务,hypervisor需要做好资源管理。CPU、内存方面已有很多成熟方法,但对共享存储资源的管理上并没有太好的方法。正如论文中举例(上面论文截图右表)一样,VM5独占共享存储时,性能很高,当运行更多VM,共享存储面临更大IO压力时,VM5性能受影响下降了40%,不满足业务需求。

       论文认为,面对不同类型的VM,一个合适的QoS算法要求能满足每个VM的最低需求,同时不超过预设设置,且能根据优先级不同,分配不同权重的资源。mClock就是这样的算法,mClock能解决上面例子中VM5受影响而性能下降的问题。

       mClock的算法思想是,

       1. 指定权重(Weight, W)、预留(Reservation, R)和上限(Limit, L):给定一组分布在不同服务器上的VM,根据业务需求,为每个VM指定一组参数,参数有三类,分别是Weight、Reservation和Limit。如果VM更重要,可以为之指定更大的Weight。Reservation表示必须满足的最低需求。如果指定了Limit,则表示该业务所得资源最多不会超过指定值。

       2. 在共享存储侧,每个VM的IO请求到来时,mClock算法根据Weight、Reservation和Limit配置给请求打上三个独立的标签。打标签算法如下图公式,其中R表示Reservation标签,L表示Limit标签,P表示Proportional标签,亦即Weight标签。

       共享存储侧根据标签值给IO请求排序,并按序处理。

       通过举例来理解打标签、按标签值排序的含义和效果。假设有三个用户A、B、C,其Weight分别是1/2、1/3、1/6。假设每个用户都连续地发请求,则根据公式,每个请求以1/w为间隔打标签,则:

  • A用户请求的Weight标签序列为:2, 4, 6, 8, 10, ...
  • B用户请求的Weight标签序列为:3, 6, 9, 12, ...
  • C用户请求的Weight标签序列为:6, 12, 18, 24, ...

       排序后为A2, B3, A4, A6, B6, C6, A8, B9, A10, B12, C12, A14, B15, A16, ..., 或简化成ABAABCABAABCABA。

       共享存储按这个序列来处理请求,最终达到的效果是处理的A请求占总数的1/2,处理的B请求占总数的1/3,处理的C请求占总数的1/6。即是遵循Weight配置的。

考虑几种场景,

       场景1:如果C用户“恶意”发送超过权重的请求,是否会抢占AB的资源?比如发送顺序是ABCCCCCCAAB,C超发请求的标签值很快就变得很大,在ABC整体标签排序中,C超发请求会被排在后面,因此不会因为发的快而抢占AB的资源。

       场景2:如果AB发出的请求很少,C发出的请求多,标签队列中有大量C的标签,C请求会被处理,资源不会被闲置。

       场景3:如果A刚开始发出的请求少,但后面某时突然“爆发”,是否会使得BC被“饿死”?并不会,因为根据标签算法,A“爆发期”请求的标签值会考虑当时的时间值(我们可将时间序列理解为1、2、3这样递增的序列,用以表示逻辑时间,而非17点55分这种物理时钟),A先期请求少,“爆发期”请求(p+1/w)也会小,如果不考虑t,则“爆发期”请求标签都小,会“饿死”BC的请求。但max(p+1/w, t)之后了,则不会有饿死现象。

       Reservation、Limit标签队列类似于Weight标签队列,形成多个队列。而标签在含义上跟时间相关,因此mClock算法可理解为是multi-Clock的缩写。

       mClock算法结合处理Weight, Reservation, Limit三个队列后的效果是:

       1. 如果系统资源不够所有人分,则优先满足Reservation和Limit。

       2. 如果系统资源足够分,则按Weight去分配。

       以上是对mClock算法直观的理解,更严谨的理解、更多的场景分析请参考论文。有了这些直观理解之后,我们不妨还可以去思考一下它和令牌桶算法的区别。

       dmClock算法解析

       dmClock意为distributed mClock,这里distributed何解?

       mClock处理的场景仍是单机场景,尽管在论文举例中,请求来自分布在多个服务器上的VM,但mClock算法仍是运行在“单一节点”上的,即运行在共享存储侧的服务器上。

       在前面部分我们讨论了“分布式QoS”,即请求来自于多个client端,发往多个server端。这种场景下mClock不再适用,因为mClock是单机的,如果在每个server上都运行一个mClock算法,这些算法实例是相互独立的。比如假设A请求Reservation为Ra,A请求均匀地发到3个server S1 S2 S3上,S1 S2 S3分别会满足Ra,最终结果是S1 S2 S3整体满足3*Ra,是指定Reservation的3倍。

       似乎需要S1 S2 S3上的mClock算法实例需要相互间建立联系,沟通彼此处理的请求情况,相互协调一下,才能使QoS的结果正确。

       但显然这样的协调成本是很高的,这也不是dmClock的做法。dmClock算法在mClock基础上,对打标签公式做了微调:

       流程上类似mClock,仍是先为不同业务指定(W, R, L),据此在client侧为不同业务请求打标签,比如打Weight标签时,不再是+1/w,而是+delta/w。关键是理解这里的delta。

       仍用上面分析mClock时采用的例子,假设某个client上有三个业务A B C,Weight分别是1/2, 1/3, 1/6,假定ABC按Weight匀速地发请求,则请求序列为ABAABCABAABCABA,请求会按内部存储规则发往ServerA,ServerB或ServerC,比如:

       选定ServerB收到的第3个请求A,它的标签值的+delta/w中的delta=2,含义是ServerB上次收到请求,和这次收到请求直接,这个client向其他Server发送了2个请求。

总结

       我们讨论了QoS、分布式QoS、令牌桶等常见QoS算法,最后举例分析了mClock和dmClock算法。

       关于dmClock,我们思考一个进一步的问题。在我们上面举例中,我们假设三个业务A B C都从一个client中发出。如果业务A B C本身是分布式的,即比如业务A是分布在多个client上,从多个client上都会发出A的请求,这些请求都会根据内部存储规则发往多个后端Server,此时dmClock还能适用吗?欢迎大家思考和讨论。

来源:焱融科技

 

 

[ 字体大小: 14 12 9 ] [ 打印]

高效能服务器和存储技术国家重点实验室 | 联系我们 | 京ICP备12012807号-3
© 2016 Hsslab