分布式 QoS 算法解析

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



01 什么是QoS



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



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



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

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



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



02 什么是分布式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，并不常见。

03 常见的QoS算法



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



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



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



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



mClock算法解析

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





论文认为，面对不同类型的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个请求。

04 总结



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



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