带你读《存储漫谈：Ceph原理与实践》——3.1.5 QoS-阿里云开发者社区

带你读《存储漫谈：Ceph原理与实践》——3.1.5 QoS

2023-05-31 155

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 带你读《存储漫谈：Ceph原理与实践》——3.1.5 QoS

3.1.5 QoS

QoS（Quality of Service）是一种控制机制，它提供了针对不同用户或不同数据流采用不同优先级的 I/O 读写能力服务策略，可根据程序的要求，保证数据流的性能达到一定的水准。

在存储领域，QoS 主要表现为对存储访问的 IOPS 或者带宽（Bandwith）控制，一个优秀的 QoS 算法要求能够满足每个 Client 的最低请求处理需求，同时也保证 I/O 服务能力不超过预设值限制，且能够根据优先级不同，分配不同的权重资源，mClock 就是这样的算法。令牌桶也能够实现一定的 QoS 上限能力限制，但因其无法保证 QoS 下限，本小节不做展开介绍。

1. mClock

mClock 是基于时间标签的 I/O 调度算法，适用于集中式管理的存储系统。mClock 使用 Reservation、Limit 及 Proportion 作为 QoS Spec。Client 端提供（r，l，w）参数值，Server 端根据这 3 个参数计算时间标签（计算公式见式 3-1、式 3-2、式 3-3，式中运算符号含义说明见表 3-2），并分为两个阶段处理 I/O 请求。

（1）Constraint-Based 阶段，处理所有预留时间标签满足条件的请求（预留时间标签值小于或等于当前时间）；

（2）Weight-Based 阶段，处理上限时间标签满足条件的请求，若有多个 Client 同时满足条件，则依据权重时间标签的大小决定处理顺序（即权重时间标签较小的 Client 的请求优先被处理）。

mClock 算法的伪代码如下所示。

RequestArrival (request r， time t， client Ci)
begin
if Ci was idle then
　　　　 minPtag = minimum of all P tags
　　　　 foreach active Cj do
　　　　　　　　Pj -= minPtag-t
　　 R<i, r> = max{R<i, r-1> + 1/r<i>, t}
　　 L<i, r> = max{L<i, r-1> + 1/l<i>, t}
　　 P<i, r> = max{P<i, r-1> + 1/w<i>, t}
　　 ScheduleRequest()
end
ScheduleRequest ()
begin
　　 Let E be the set of requests with R tag <= t
　　 if E not empty then
　　　　 select IO request with minimum R tag from E
　　 else
　　　　 Let E' be the set of requests with L tag <= t
　　 if E' not empty then
　　　　 select IO request with minimum P tag from E'
　　 /*Assuming request belong to client c<k>*/
　　 Subtract 1/r<k> from R tags of C<k>
end

mClock-Server 动态地工作在 Constraint-Based 和 Weight-Based 阶段，为了减少Client 之间的竞争，它总是期望请求在 Constraint-Based 阶段被处理。当某个 Client 的请求在 Weight-Based 阶段被处理，该 Client 子队列剩余请求的预留时间标签都要减去 1/r，以保留该 Client 预留时间标签的正确性，调整过程如图 3-11 所示，若不对剩余请求的预留时间标签进行处理，则第三个请求的初始的预留时间标签t+3/r 更难以满足 ConstraintBased 阶段被处理的条件，从而使得该 Client 的 I/O 请求一直在 Weight-Based 阶段被处理，无法满足预期的预留效果。

图 3-11　请求在 Weight-Based 阶段被处理时预留时间标签调整过程

mClock 存在一定的局限性，即 mClock 的应用场景为多个 Client 向同一个 Server端发送请求，但是对于分布式存储系统，需要多个 Client 端向多个 Server 端发送请求，mClock 算法在此类场景不再适用。

1 Client i 第一个到达的请求的时间设为t (t = current time)。

2. dmClock

Distributed mClock（即 dmClock）算法对 mClock 算法进行了改进，dmClock 是 mClock的分布式版本，需要在每个 Server 上都运行一个 mClock 服务端，将 QoS Spec 分到不同的Server 共同完成。

dmClock 算法与 mClock 算法之间的差异如下。

（1）分布式系统中的各个 Server 向 Client 返回的响应结果中包含其请求在哪个阶段被处理；

（2）Client 会统计各个 Server 所完成请求的个数，在向某一 Server 发送请求时，请求中会携带自上次给该 Server 下发的请求之后，其他 Server 完成的请求个数之和，分别用ρ 和δ 表示两个阶段的增量；

（3）Server 在计算请求时间标签时，不再根据步长（1/r，1/w，1/l）等长递增，而使用ρ 和δ 调整因子，使得总的处理速度满足 QoS 约束条件。

请求的时间标签计算公式见式 3-4、式 3-5、式 3-6。

如前面所讲，dmClock 也是由 Client 和 Server 两部分组成，其中 Client 的主要功能是统计每个 Server 分别在两个阶段完成请求的个数，以此来调整 Server 处理请求的速率。Server 部分是算法的核心，每个 Server 中的 dmClock-Server 队列由一个两级映射队列组成，如图 3-12 所示，一级是由各个 Client 组成的 Client queue，另一级是 Client 对应的请求子队列 request queue。

图 3-12　dmClock-Server 队列

由于请求出队列的过程涉及大量的实时排序调整，因此服务器在生成 dmClockServer 队列时，会基于 QoS 的 3 个时间标签构造 3 棵完全二叉树，每棵二叉树的节点为各个 Client 请求子队列，节点在二叉树中的位置取决于其 Client 请求子队列队首元素的时间标签，构造规则是父节点的时间标签小于子节点。

请求入队列的执行流程如图 3-13 所示。若某个 Client 向 Server 发送请求，如果Server 中该 Client 的请求子队列中不存在未处理的请求，或子队列并不存在（即新来了一个 Client，需要新创建子队列），则不仅需要让请求进入队列，还需将 Client 加入标签二叉树中，并依据标签时间的大小将其调整到正确位置。如果该 Client 的请求子队列中存在未处理的请求，则直接将该请求插入队列尾部即可。

图 3-13　请求入队列的流程

请求出队列的执行流程如图 3-14 所示。先进入预留时间标签阶段，取预留标签二叉树的 root 节点请求队列，判断其队首元素的预留时间标签是否满足出队条件，若满足，则使 root 节点队列的队首元素（req）出队列（并调整该节点在预留二叉树中的位置，同时也要调整该 root 节点对应 Client 的子队列在权重二叉树和上限二叉树中的位置）；否则进入基于上限和权重时间标签阶段，从上限二叉树的 root 节点开始，依次开始判断节点队列的队首元素的上限时间标签是否满足出队条件，将满足出队条件的请求的 ready 位标记为true，再依据权重时间标签大小将权重二叉树中队列队首元素的 ready 位被标记为 true 的节点调整到合适位置，让位于权重标签二叉树 root 节点的队首元素出队列，最后再去调整该 Client 在权重、上限、预留标签二叉树中的位置。