关于分布式:分布式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），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 个申请。

04 总结

咱们探讨了 QoS、分布式 QoS、令牌桶等常见 QoS 算法，最初举例剖析了 mClock 和 dmClock 算法。

对于 dmClock，咱们思考一个进一步的问题。在咱们下面举例中，咱们假如三个业务 A B C 都从一个 client 中收回。如果业务 A B C 自身是分布式的，即比方业务 A 是散布在多个 client 上，从多个 client 上都会收回 A 的申请，这些申请都会依据外部存储规定发往多个后端 Server，此时 dmClock 还能实用吗？欢送大家思考和探讨。