PriorityMeister - Tail Latency QoS for Shared Networked Storage 论文笔记

Introduction

在云计算环境下，在共享网络存储系统中提供端到端的尾延迟QoS是非常重要的问题。通常情况下，人们会在90%或95%观察尾延迟。但是，越来越多研究机构和公司开始关心99%甚至99.99%的长延迟。本文讨论99.9%和99.99%的尾延迟。

在生产环境中的突发性工作负载下，满足尾延迟SLO是有挑战性的，主要因为下面两个原因：第一，尾延迟很大程度上受排队的影响，而突发性工作负载导致共享潜在基础设施的工作负载的排队；第二，端到端的尾延迟受到请求中所有阶段的影响（比如访问存储，通过网络发送数据），因此队列可能在不同时间、不同阶段构建起来。

之前大部分存储调度的工作都局限在更简单的问题——共享存储带宽；比起延迟QoS，共享带宽是一段时间的平均水平，不会被暂时的排队影响。有一些之前的工作研究延迟QoS，但是主要关注平均延迟；只看平均延迟会掩盖一些会引起掉队的最糟情况。

关于最近的工作，Cake已经考虑了99%比例下的尾延迟QoS，使用基于反馈控制的技术。但是，像Cake这种通过回应的方法不适用于突发的工作负载，因为突发可能会在Cake对其做出反应之前导致大量SLO违规，如下图所示。在处理多个阶段时，满足延迟SLO的困难更加复杂，因为端到端延迟是由所有阶段延迟的总和组成的。

文章介绍了PriorityMeister（PM），这是一种主动式QoS系统，它通过优先级和令牌桶速率限制的组合，在多个阶段实现了端到端尾延迟SLO。 PM通过分析每个阶段的每个工作负载的突发性和负载来工作。反过来，这用于计算每个工作负载的令牌桶速率限制，该限制限制了一个工作负载对共享系统的其他工作负载的影响。 PM中的一个关键思想是在每个阶段为每个工作负载同时使用多个速率限制器。同时使用多个速率限制器可以使我们更好地限制工作负载的突发性。在很好地限制了每个工作负载的突发性之后，我们构建了一个模型来估计最坏情况下的每个工作负载延迟。我们的模型基于网络演算，这是用于最坏情况排队估计的分析框架。

仅速率限制是不够的，因为工作负载具有不同的延迟要求和不同的工作负载突发性。因此，需要对工作负载进行不同的处理，以满足其延迟SLO，并限制对其他工作负载的影响。 PM使用优先级作为区分工作负载之间的延迟的关键机制。请注意，优先级用于避免对来自具有严格延迟要求的工作负载请求的延迟，而不是根据外部重要性概念对工作负载进行优先级排序。手动设置优先级是很典型的，但是很费力并且容易出错。确实，很难同时捕获每个工作负载的突发性对优先级较低的工作负载的影响。我们的延迟分析模型使PM可以在每个阶段快速搜索较大范围的优先顺序，以自动设置优先级以满足SLO。

PM在每个阶段还支持不同的每个工作负载优先级和速率限制（与整个过程中的单个优先级相对）。 在第一个工作负载满足其SLO而第二个工作负载不满足的情况下，我们不必让一个工作负载始终具有最高的优先级，而第二个工作负载则具有较低的优先级，我们可以在某些阶段将两个工作负载都设置为最高优先级， 别人的优先级较低。 由于工作负载可能不需要在所有地方都满足其SLO的最高优先级，因此这种混合优先级方案可能会允许更多工作负载满足其SLO。

PM做出以下主要贡献。首先，我们开发了一种算法，该算法可以自动确定每个阶段每个工作负载的优先级和速率限制，以满足端到端延迟SLO。 PM通过将网络演算与针对给定工作负载同时使用多个速率限制器的思想相结合来实现这些目标。其次，我们构建了一个由网络和存储组成的真实QoS系统，在这里我们证明PM优于Cake的最新方法。第三，我们显示PM可以抵抗错误的存储性能估计，不同程度的工作负载突发性和工作负载不当行为。第四，我们提出了一种简单的方法作为PM的起点，我们将其称为bySLO，我们发现它的表现出奇的好，也胜过Cake。

Previous Work

PM与先前的工作在两个主要方面不同。首先，它是专门为满足多租户存储环境中的尾延迟SLO而设计的。其次，PM可以推广到包括网络和存储在内的多种资源。下表比较了现有的调度程序和PM。

Tail latency

先前大多数存储调度的工作关注更简单的问题——共享存储的带宽。而关注延迟的工作大多数是以平均延迟为目标。我们仅知道两个存储调度程序 Cake 和 Avatar，它们研究尾延迟行为。

Cake是一种反应式反馈控制调度程序，可调整比例份额以满足99百分位延迟SLO。我们的目标相似，但是我们采用了不同的方法并克服了Cake的某些局限性。Cake仅处理一种对延迟敏感的工作负载，而一种处理面向吞吐量的工作负载。PM可以处理多个延迟和吞吐量SLO，并且可以自动调整它所有系统参数。此外，PM可以处理在生产级存储跟踪中发现的突发性，并且可以满足更高的百分位数延迟SLO（例如99.9％），这两种都无法使用反应式方法来实现。

Cake虽然为HBase（CPU）和HDFS（存储）分配了多种资源，但它需要一种机制来动态调整网络不容易获得的比例份额。 相反，PM使用优先级，这是一种更为简单的机制，并且在许多网络交换机中都得到了支持。 我们尝试扩展Cake以将网络速率限制用作比例份额的代理，但事实证明，这样做带来的伤害大于帮助。

Avatar 是最早截止日期优先（EDF）调度程序，具有速率限制支持。 尽管Avatar显示了尾延迟性能，但仅评估了第95个百分位（模拟）。我们的工作重点是较高的尾延迟（例如99.9％），并且我们会在实际硬件上进行评估。 Avatar发现速率限制对于提供性能隔离很重要，但是它没有解决如何设置速率限制，并且其速率限制模型无法针对突发性变化的工作负载进行配置。 PM分析工作负载跟踪以自动配置速率限制，并且可以处理突发性不同的工作负载。 最后，Avatar的重点仅在于存储，并且该解决方案不能推广到网络，因为EDF依赖于拥有一个可以对请求进行时间戳和排序的实体。

Multi-resource

最近的一些论文已经开始研究多资源调度的挑战。跨多个资源提供QoS与端到端延迟SLO非常相关，因为延迟是在所有资源阶段（例如存储，CPU，网络等）累积的。可以想象使用两种不同的QoS系统进行存储和网络访问，但是如何根据给定的总端到端SLO确定每个阶段的SLO并不明显。 PM是一个单QoS系统，它既了解存储又了解网络，并且可以自动配置系统以满足端到端延迟SLO。我们的多资源QoS体系结构与IOFlow最相似。 IOFlow为存储和网络QoS引入了一种新的软件定义的存储体系结构，但是没有解决如何配置系统以满足延迟SLO的问题。我们的工作是对IOFlow的补充，可以被认为是可以建立在IOFlow架构之上的政策。

Other related work

Bobtail 的论文还研究了云中尾延迟的问题，并且管理员发现了不良的CPU协同调度的根本原因。 我们的工作是对他们的补充，我们的工作有可能在将来合并CPU QoS。 HULL 通过速率限制和将队列转移到终端主机来解决长网络交换队列产生的延迟问题。 Xu 也解决了这个问题，但是使用网络优先级来解决。 这两篇论文都允许低带宽工作负载快速通过网络交换机，但是没有涉及如何使用不同的端到端延迟SLO处理更高带宽的工作负载。 PM 利用网络演算领域来对工作负载进行建模，并使用诸如到达曲线和服务曲线等概念。 我们的延迟分析类似于Bouillard等人的最新理论论文。

Architecture

PM基于每个工作负载提供QoS。每个负载运行在一台client VM上，访问在server VM上的存储。多个client VM的同一应用程序可以表示为具有相同SLO的多个工作负载。

工作负载由从client到server再返回的请求流组成，其中每个请求都以到达时间，请求大小和请求偏移量为特征。一个请求包含三个阶段：从client到server的网络请求、server访问存储、从server到client的网络应答。对于每个网络阶段，在每台机器和网络交换机出口端口都有队列。对于每个存储阶段每个存储设备都有一个队列。每个阶段都有独立的优先级和速率限制，它们由PM决定。

PriorityMeister system design

上图展示了PM系统的QoS组件，PM在每个客户端和服务器上都有本地QoS实施模块，以控制对存储和网络资源的访问。 每个实施模块都是独立的，只需要对从我们的全局控制器接收到的QoS参数采取行动即可。 这使PM可以利用全局信息。 我们的系统架构与IOFlow中的架构相似，已证明可以扩展并容忍控制器故障。

PM自动为每个实施模块配置的两个主要QoS参数，优先级和速率限制。优先级是在工作负载之间提供延迟区分的关键机制。文章使用严格的优先级来为需要低延迟的工作负载提供良好的延迟。为了防止饿死，我们使用速率限制，并且只在工作负载的速率限制内执行优先级。PM的不同寻常之处在于，它在每个阶段为每个工作负载都部署了速率限制器。

速率限制器建立在泄漏令牌桶模型上，该模型以速率和令牌桶大小为参数。当请求到达时，会根据请求将令牌添加到令牌桶。 对于网络，添加的令牌数与请求的传输字节数相对应。 对于存储，添加的令牌数量对应于存储设备处理请求的估计时间（该估计由存储估计器执行）。如果存储桶中有足够的空间添加令牌，则允许请求继续。 否则，请求将使请求排队，直到令牌桶有足够的空间。随着令牌以配置的速率不断从存储桶中泄漏，空间变得可用。

PriorityMeister controller design

上图展示了PM控制器的设置。用户提供他们的目标，可以是延迟SLO或者吞吐量SLO，应用程序访问模式的代表性跟踪（trace可以在应用运行时被自动捕获，或者高级用户可以使用特定于应用程序的知识来选择一组更具代表性的访问模式），还有client和数据的位置（IP地址）。延迟SLO指定了请求的最大可接受延迟的值；吞吐量SLO是指定了给定追踪的的请求应该完成的总时间。

关于PM设置速率限制，我们从假想实验开始。假设优先级比较高的工作负载W，图(a) 的速率限制对（速率和令牌桶大小）都能保证W满足SLO，但是不同的选择会影响优先级较低的工作负载，图(b) 表示使用更大的令牌桶的size(例如，绿色的X)会在W出现突发性请求时导致中等优先级的工作更高的尾部延迟。图(C) 表示使用更高的速率(例如，红色的X)会在W出现突发性请求时导致低优先级工作负载饥饿。

在W上使用较小的存储桶大小和较低的速率将有助于降低优先级的工作负载，但是图(a)中的W不存在这样的（r，b）对。PM中的关键思想是在图(a) 的阴影区域中将W限制为所有（r，b）对，这给我们带来了小桶尺寸和低速率的好处。 具体来说，我们沿边界挑选了多个（r，b）对，例如所示的叉叉X，并同时为W部署了这些速率限制器；即在令牌被添加到其所有令牌桶中之前，请求都会排队等待。

PM从工作负载分析器开始，它通过生成工作负载的（r，b）对区域（例如，上图(a) ）来表征每个工作负载。接下来，优先级算法会在优先级排序的空间中进行搜索，以确定最能满足工作负载SLO的工作负载优先级。我们的算法建立在延迟分析模型的基础上，该模型以优先级顺序和速率限制（r，b）对的集合作为输入，并基于网络演算为每个工作负载输出延迟的最坏情况界限。优先级算法不会搜索所有优先级顺序，取而代之的是，开发了一种简单的贪心算法来挑选“好的”顺序，这替代了系统管理员手动设置优先级的方式。

最后，将优先级和速率限制发送到执行模块。由于我们主动分析工作负载突发，因此在用户需求发生变化（例如，更改应用程序访问模式或SLO）或者新的工作负载到来之前，无需再次运行优先级算法。发生更改时，我们将重新运行优先级算法，并可能重新调整优先级和速率限制。

Implementation

Workload analysis

工作负载分析的作用是基于该工作负载访问模式的代表性追踪为每个工作负载生成速率限制，保证一个工作负载不会因速率限制而被阻碍。也就是说，我们沿着上图(a) 的蓝色边界计算（r，b）对的集合。要计算（r，b）对，我们选择一个速率r，并使用具有该速率的无限制令牌桶来重播工作负载追踪。我们将存储桶大小b设置为最大令牌存储桶使用量，该值对应于使工作负载不受阻碍的最小令牌存储桶大小。我们在一系列速率上执行此操作，以获得整个（r，b）对的集合。

Estimator

评估器用作工作负载分析的一部分，并在存储执行器中决定一个请求对应的token数量。它们提供了一种将各种请求类型（例如，读，写）和请求大小抽象成一个单个公共量度的方法。PM目前支持两种类型的评估器：存储和网络。对于存储，我们使用“工作”为通用指标，以时间为单位进行度量。“工作”意味着在没有排队影响下请求所花费的时间。对于网络，我们使用被传输的字节作为通用量度，该量度在不同的链路带宽下不会改变。

Storage estimator

我们的存储估计器类似于基于表的方法。 我们对存储设备进行了先验配置，以便为（i）带宽和（ii）服务请求的基本时间构建表。 我们的表格通过请求类型（例如，读取，写入），请求偏移量以及后续请求偏移量之间的距离（即，偏移量-先前的偏移量）进行参数化。 此外，我们保留捕获连续访问请求的历史记录，并假设连续访问的基准时间为0。然后我们评估服务请求的存储时间为 request size / bandwidth + base time.

Network estimator

网络估计器负责估计请求发送的字节数。 我们根据请求类型和请求大小使用一个简单的估算器，发现它足够了。 对于读取请求，有一个小的请求发送到服务器，而有一个很大的响应从服务器返回。 对于写请求，有一个很大的请求发送到服务器，而有一个很小的响应从服务器返回。

Prioritizer algorithm

优先级排序算法负责查找可以满足工作负载SLO的优先级排序。也就是说，我们要确定每个工作负载的每个阶段的优先级，以使通过延迟分析模型计算出的工作负载的最坏情况下的延迟小于工作负载的SLO。虽然搜索空间的大小在工作负载数量上是组合显示的，但我们有一个关键的见解可以使搜索变成多项式时间：如果工作负载可以满足给定的低优先级的SLO，则高优先级工作负载的特定顺序就无关紧要。仅优先级较高的工作负载的累积影响很重要。因此，我们的算法尝试为每个工作负载分配最低的优先级，并且可以将满足最低要求的SLO的任何工作负载分配给该优先级，并将其从搜索中删除。然后，我们的算法以下一个最低优先级迭代其余工作负载。如果到了剩下的工作负载都无法满足最低优先级的SLO的地步，那么我们将利用在每个阶段为工作负载分配不同的优先级的优势。

Storage enforcer

存储的执行会为每个存储设备调度请求。PM当前的实现是以NFS挂载的方式公开存储，而存储执行器则作为NFS之上的插入层而构建。由于NFS基于SunRPC，因此PM能够在RPC层挂接到NFS，而无需对内核进行修改。 存储执行器为每个工作负载创建队列，并根据PM全局控制器分配的优先级和速率限制在不同工作负载之间执行仲裁。

Network enforcer

网络的执行对来自每个工作负载的网络流量进行优先级排序和速率限制。网络执行器构建在现有的Linux Traffic Control（TC）基础结构之上。TC基础结构允许用户构建用于网络的任意QoS排队结构。 由于分层令牌桶（HTB）队列只能支持两个速率限制器，因此我们将多个HTB队列链接在一起，以表示每个工作负载的多个速率限制器。 然后，我们使用DSMARK标记数据包为DSCP标志，这些标志指示网络交换机如何确定数据包的优先级。 我们的网络交换机为每个端口提供7级优先级，使用这些优先级仅需要在交换机上启用DSCP。 为了在主机和交换机上获得优先级，我们最后添加了PRIO队列。 为了通过正确的TC队列识别和路由数据包，我们使用基于源和目标地址的过滤，每个虚拟机都不同。