【SoCC2018 论文】DAGOR：微信「大规模微服务过载控制系统」

大规模在线服务系统的有效过载控制对于防止系统后端过载至关重要，微信团队自研的过载控制方案 DAGOR 已经在微信业务系统中运行了五年多，为微信后端的健康发展提供了重要的保障。

DAGOR 的论文发表在 SoCC2018，本文为该论文的中文翻译版本，英文版本在(https://arxiv.org/pdf/1806.04075.pdf)，对原文感兴趣的同学可以点击”。

摘要

大规模在线服务系统的有效过载控制对于防止系统后端过载至关重要。通常，过载控制的设计是针对单个服务的。但是由于复杂的服务依赖或服务实现的缺陷，特定于服务的过载控制可能会对整个系统造成损害。在服务开发过程中，开发人员通常难以准确地预估实际工作负载的变化。因此，过载控制与服务逻辑分离显得至关重要。本文针对面向帐户的微服务体系结构提出了一种过载控制方案 DAGOR。DAGOR 是服务无感知并且以系统为中心的。它从微服务粒度上管理过载，从而使得每个微服务能够实时地监控其负载状态，并且当检测到过载时，能够和相关服务通过协作方式触发减载(load shedding)。DAGOR 已经在微信后台使用了 5 年。实验结果表明，DAGOR 能够在系统过载时获得较高的服务成功率，同时保证过载控制的公平性。

关键词

过载控制，服务准入控制，微服务架构，微信

1. 介绍

过载控制旨在减轻系统出现过载时的服务无响应。这对于需要确保实现 24×7 服务可用性的大规模在线应用程序来说是至关重要的，尽管出现了不可预测的负载激增。虽然云计算有助于按需配置，但仍无法解决过载问题——服务提供商受到其可从云提供商处购买的计算资源的限制，因此云提供商需要对其提供的云服务进行过载控制。

传统用于简单服务架构的过载控制假定服务组件数量少，依赖关系小。对于独立服务，过载控制主要针对操作系统、运行环境和应用程序[2,24,29]。对于简单的多层服务，服务入口点的网关监视整个系统的负载状态，并在必要时拒绝客户端请求，例如减载，以防止服务过载[5、7、23]。

然而，现代在线服务在架构和依赖性方面变得越来越复杂，远远超出了传统过载控制的设计目标。现代在线服务通常采用面向服务的架构（SOA）[12]，该架构将传统的单一服务体系结构划分为通过网络协议连接的子服务。微服务架构，作为 SOA 的一种特殊化，通常由数百至数千个子服务（即微服务）组成，以支持复杂的应用程序[9,21]。每个微服务在一台或多台机器上运行一组进程，并通过消息传递与其他微服务通信。通过分离不同微服务的实现和部署，微服务体系结构促进了对每个微服务的独立开发和更新，而不管底层编程语言和框架。这就为复杂的在线应用程序的跨团队开发提供了灵活性和生产力。

大型微服务系统的过载控制必须考虑系统的复杂性和高动态性，这在实际应用中是非常具有挑战性的。首先，所有的微服务都必须被监控。如果任何微服务不在监控范围内，则可能会在该位置出现潜在的过载，并进一步波及到相关的上游微服务。因此，系统可能会出现级联过载，并最终挂起，导致受影响服务的高延迟。然而，依靠一些特定的微服务或机器仲裁来监视负载状态是极其困难的，因为单个微服务或机器没有快速发展的部署视图。

其次，由于服务依赖关系的复杂性，让微服务独立地处理过载可能有问题。例如，假设处理客户端的请求需要依赖 k 个服务，但是这些服务当前都出现过载并且都独立的以概率 p 来拒绝请求。这种情况下，完成客户端的请求的期望值是(1-p)K。如果 p 接近 1 或者是 k 很大，系统的吞吐量在这种情况下就趋于消失。但是系统过载并不会因为工作负载的削减而减轻，因为失败请求已经被处理的部分仍然会消耗计算资源。这将导致系统进入一种难以避免的雪崩状态。

第三，过载控制需要适应服务变化、工作负载动态和外部环境。如果每个微服务都对其上游服务执行服务级别协议（SLA），那么它将极大地减慢这个微服务及其下游服务的更新进度，从而破坏了微服务体系结构的主要优势。类似地，如果微服务必须以协作方式交换大量的消息来管理过载，它们可能无法适应负载激增，因为过载控制消息可能会由于系统过载而被丢弃，甚至进一步恶化系统的过载状况。

为了应对上述挑战，我们提出了一种用于大规模、面向帐户的微服务架构的过载控制方案，称为 DAGOR。DAGOR 的总体工作原理如下：当一个客户端请求到达入口服务时，它被分配了一个业务优先级和一个用户优先级，这样所有随后触发的微服务请求都会被强制在相同的优先级上被一致地接受或拒绝。每个微服务都为准入请求维护自己的优先级阈值，并通过检查系统级资源指标，如待处理队列中请求的平均等待时间，来监视自己的负载状态。如果检测到过载，那么微服务会使用自适应算法调整其负载削减阈值，该算法会尝试减少一半的负载。同时，微服务还将阈值的变化通知其直接的上游微服务，以便在微服务管道的早期阶段可以拒绝客户端请求。

DAGOR 过载控制只使用了少量的阈值和微服务之间的边际协调。这种轻量级机制有助于提高过载处理的有效性和效率。DAGOR 也是服务无感知的，因为它不需要任何特定服务的信息来进行过载控制。例如，虽然业务逻辑多种多样，但 DAGOR 已经部署在微信的业务系统中，以满足所有微服务的过载控制。此外，DAGOR 对服务变更、工作负载动态和外部环境都具有自适应性，这使得它能够适应于快速发展的微服务系统。

虽然网络路径中的减载问题在文献中已经得到了广泛的研究[8,10,15]，但是本文更侧重于如何为运营微服务系统建立一个实用的过载控制解决方案。本文的主要贡献在于：（1）介绍了 DAGOR 的设计，（2）分享微信业务系统中操作过载控制的经验，（3）通过实验验证 DAGOR 的性能。

本文剩余的部分组织如下：第二节介绍了微信后端的整体服务架构以及它通常面临的工作负载动态。第三节描述微信微服务架构下的过载场景。第四节介绍了 DAGOR 过载控制的设计及其在微信中的应用。在第五节我们进行实验以评估 DAGOR，在第六节回顾相关工作并最后在第七节进行全文总结。

2. 背景

作为背景，我们介绍了微信后端的服务架构，该架构支持 3000 多种移动服务，包括即时通讯，社交网络，移动支付和第三方授权。

2.微信服务架构

微信后端是基于微服务体系结构构建的，其中公共服务递归地组合成具有广泛功能的复杂服务。微信中不同服务之间的相互关系可以被建模为一个有向无环图（DAG），其中顶点表示服务，边表示两个服务之间的调用路径。具体来说，我们将服务分为两大类：基础服务( basic service)和中转服务(leap service)。在服务 DAG 中，一个基础服务的出度（节点出边数）为 0，而中转服务的出度为非 0。换句话说，中转服务可以调用其他服务，如基础服务或者其他中转服务，来触发下游服务任务，而任何任务最终都会汇入到基础服务，不再进一步调用任何其他服务。特别地，在服务 DAG 中，入度边数为 0 的中转服务被称为入口服务。用户发出的任何服务请求的处理总是从一个入口服务开始，以一个基础服务结束。

图 1 展示了微信后端的微服务架构，该架构被分层为三层。数以百计的入口服务停留在顶层。所有的基本服务都放置在底层。中间层包含除了入口服务以外的所有中转服务。每个服务任务都是以自顶向下的方式通过微服务体系结构来构建和处理的。特别地，所有基础服务被所有中转服务共享调用，并且都是服务于用户级目的 1 的最终服务。此外，中间层的中转服务由所有入口服务以及其他中转服务共享。大部分微信服务都属于这一层。

图 1：微信微服务架构

对于微信来说，每天入口服务的请求总数通常为 1010∼1011 次。每个入口服务请求随后对协作微服务触发更多的请求，以实现用户期望的行为。因此，微信后端基本上每秒钟需要处理数亿个服务请求，处理如此规模数据的系统显然具有挑战性。

2.2 微信服务部署

在微信业务系统中，微信微服务系统容纳了超过 3000 个运行在 20000 台机器上的服务，并且随着微信的日益普及，这些数字还在不断增加。该微服务架构允许不同的开发团队独立地部署和更新各自开发的服务。随着微信的不断发展，微信的微服务系统也在经历着服务更新的快速迭代。例如，从 2018 年 3 月到 5 月，微信的微服务系统平均每天经历了近 1000 次的变更。根据我们维护微信后端的经验，任何集中式或基于 SLA 的过载控制机制都很难支持如此大规模的快速服务变更。

2.3 动态工作负载

微信后台处理的工作负载总是随时间变化，并且不同情况下的波动模式也有所不同。通常，高峰时间的请求量比日平均请求量大 3 倍左右。在个别情况下，例如农历新年期间，高峰期的工作负载可能会高达日平均工作负载的 10 倍左右。在服务请求量差距如此大的情况下，处理好这种动态工作负载是很有挑战性的。虽然过量配置的物理机器可以承受如此巨大的工作负载波动，但该解决方案显然是不经济的。相反地，通过仔细设计过载控制机制，使其能够自适应地容忍系统运行时的负载波动，显得更加可取和实际。

3. 微信中的过载

微服务架构中的系统过载可能由多种原因造成的。其中最常见的包括：负载激增、服务协议变更导致的服务器容量降低、网络中断、系统配置改变、软件缺陷和硬件故障。典型的过载场景包括过载的服务和相关调用路径上的服务请求。在本节中，我们描述了三种基本的服务过载形式，它们是完整的，并且能够用来构成其他复杂形式的服务过载。图 2 展示了这三种基本形式，其中过载的服务由警告标志标记，沿调用路径关联的请求由箭头表示。

图 2：常见的过载场景

3.1 过载场景

在形式 1 中，如图 2.a 所示，过载发生在服务 M。在微信业务系统中，服务 M 通常是一种基础服务。这是因为在微服务架构中基础服务代表了服务 DAG 中的接收节点，因此它们是最活跃的服务。在图 2.a 中，箭头表示一种通过服务 A 调用服务 M 的请求类型。当服务 M 过载时，发送到服务 M 的所有请求都会受到影响，从而导致响应延迟甚至请求超时。更糟糕的是，过载服务的上游服务（如服务 A）也会受到影响，因为它们在等待过载服务的响应。这将导致过载从过载服务向其上游服务进行逆向传播。

虽然形式 1 在 SOA 中很常见，但形式 2 和 3 是大规模微服务体系结构 2 所独有的。如图 2.b 所示，形式 2 类似于形式 1，但涉及从服务 A 到服务 M 的多次调用。在一些业务逻辑中需要这样的多次调用。例如，在加密/解密应用程序中，服务 A 首先可以调用服务 M 来解密某些数据，然后在本地操作明文数据，最后再次调用服务 M 来加密最终数据。我们将相应的过载场景称为组合过载(subsequent overload)，其正式定义如下：

组合过载是指存在多个过载服务，或者单个过载服务被关联的上游服务多次调用的过载场景。

在组合过载的场景中，上游服务发起的任务被成功执行的条件是当且仅当其所有发出的请求都得到了成功的响应。否则，如果发送到过载服务的任何服务请求未得到满足，则认为服务任务处理失败。显然，形式 2（图 2.b）和形式 3（图 2.c）都属于组合过载。形式 2 中的组合过载是由于对单个过载服务的连续调用，而形式 3 中的组合过载则是由于对不同过载服务的分开调用导致的。

组合过载增加了有效过载控制的挑战性。直观地讲，当服务过载时随机执行减载可以让系统维持饱和的吞吐。但是，组合过载可能会出乎预料地大大降低系统吞吐量。这是由调用过载服务的连续成功服务约束所导致的。例如，在图 2.b 所示的形式 2 中，假设服务 A 调用服务 M 两次，服务 M 配置为容量 C，并且在服务过载时随机执行减载。我们进一步假设服务 M 当前的工作负载为 2C，而服务 M 仅由服务 A 调用。结果，服务 M 预计会拒绝一半的请求，因此服务 M 单次调用的成功率为 50%。从服务 A 的角度来看，其对服务 M 的调用成功率为 50%×50%=25%。换句话说，服务 A 发送 C 个任务，2C 的调用请求将被发送到服务 M，但是服务 A 只有 0.25C 的请求被接受。相反，如果服务 A 的工作负载为 0.5C，那么服务 M 只是饱和，没有过载，因此服务 A 任务的成功数量为 0.5C。由此可以看出，如果每个服务 A 任务不得不多次调用服务 M，那么组合过载会导致服务 A 的成功率非常低。同样的论点也适用于图 2.c 所示的形式 3，唯一的区别就是服务 A 的成功率依赖于服务 M 和服务 N 的请求成功率的乘积。

在上述三种基本的服务过载形式中，形式 1 和形式 2 在微信业务系统中占主导地位，而形式 3 相对较少。为了有效地进行过载控制，我们强调在运行工作负载很大时，必须正确处理组合过载，以维持系统吞吐量。否则，在请求服务超载时，简单地采用随机减载可能会导致客户端请求的成功率极低（例如接近零）。这种“服务挂起”现象在我们以前维护微信后端的实践中已经被观察到，这促使我们研究适合微信微服务架构的过载控制设计。

3.2 大规模过载控制的挑战

与面向 Web 的三层架构和 SOA 的传统过载控制相比，微信微服务架构的过载控制存在两个独特的挑战。

首先，对于发送到微信后端的服务请求没有单一的入口点。 这使得在全局入口点（如网关）处的集中式负载监控的传统方法失效。此外，一个请求可以通过复杂的调用路径来调用多个服务。即使对于相同类型的请求，相应的调用路径也可能完全不同，这取决于特定于请求的数据和服务参数。因此，当某个特定的服务过载时，不可能精确地确定应该丢弃哪种请求来减轻过载的情况。

其次，即使在分布式环境中采用去中心化过载控制，过多的请求中止不仅会浪费计算资源，还会因服务响应的高延迟而影响用户体验。特别是，当组合过载发生时情况会变得严重。这就要求在请求类型、优先级、调用路径和服务属性方面进行某种协调，以正确地管理减载。然而，由于微服务体系结构中的服务 DAG 极其复杂，并且在不断地演化，因此，维护成本以及与过载服务进行有效协调的系统开销被认为过于昂贵。

4. DAGOR 过载控制

为微信微服务架构设计的过载控制方案称为 DAGOR。其设计旨在满足以下要求：

• 服务无感知： DAGOR 需要适用于微信微服务架构中的各种服务，包括内部和外部第三方服务。为此，DAGOR 不应该依赖任何特定于服务的信息来执行过载控制。这种服务无感知的设计考虑有两个优点：首先，过载控制机制具有高度可扩展性，以支持系统中大量的服务，同时适应服务部署的动态性。这对于不断发展的微信业务至关重要，因为微信业务系统中部署的各种服务经常更新，例如上线新服务、升级现有服务和调整服务配置等。其次，可以将过载控制的语义与服务的业务逻辑解耦。因此，服务配置不当并不影响过载控制的有效性。相反，过载检测可以帮助发现导致服务运行时过载的隐藏配置缺陷。这不仅有利于服务的开发和调试/调优，而且还提高了系统的可用性和健壮性。

• 独立但协作： 在微服务体系结构中，服务通常部署在一组物理机器上，以实现可伸缩性和容错。实际上，工作负载很难均衡地分布在这些机器上，并且每台机器的负载状态可能会出现剧烈且频繁的波动，只有少数常见的模式在不同机器之间共享。因此，过载控制应该在单个机器的粒度上运行，而不是在全局范围内。另一方面，机器间协作的过载控制对于处理组合过载也是必要的。不同机器之间的协作需要以服务为导向，以便上游服务的成功率可以与过载服务的响应率相匹配，尽管组合过载会出现。

• **高效和公平：**当由于过载而不可避免地进行减载时，DAGOR 应该能够维持最好的服务成功率。这意味着在失败的服务任务上所浪费的计算资源（即 CPU 和 i/O）被最小化。需要注意的是这些被立即中止的任务所耗费的计算量很小，因此可以为其他有用的处理让出资源；相反，部分处理但最终被放弃的任务会使得在这些任务上所花费的计算被浪费。因此，过载控制的高效是指该机制如何能够最小化在服务任务的部分处理上所消耗的计算资源。此外，当某个服务过载时，其上游服务也应该都能够维持大致相同的饱和吞吐量，而不管上游服务任务对过载服务进行了多少次调用。这反映了过载控制的公平性。

4.1 过载检测

DAGOR 在服务器粒度上采用去中心化的过载控制，因此每个服务器都会监视其负载状态，以便及时检测潜在的过载。对于针对单个服务器过载的监控，广泛的性能指标已经被现有的文献所研究，包括吞吐量、延迟、CPU 利用率、包速率、等待请求数、请求处理时间等[20, 25, 31]。DAGOR 设计使用等待队列中请求的平均等待时间（或排队时间）来分析服务器的负载状态。请求的排队时间是由请求到达服务器与其在服务器上被启动处理之间的时间差来衡量的。

通过监控排队时间来检测过载的理由初看起来并不明显。一个直接的问题是：为什么不考虑使用响应时间 3 来代替呢？我们认为排队时间比响应时间更准确地反映负载状态。与排队时间相比，响应时间额外计算请求处理时间。特别地，处理一个基础服务请求的时间纯粹由本地处理决定，而中转服务请求的处理时间进一步涉及处理下游服务请求的耗时。这导致了响应时间沿服务调用路径被递归地测量，使得指标不能单独反映服务或服务器的负载状态。相反，排队时间只受服务器本地处理能力的影响。当服务器由于资源耗尽而过载时，排队时间与超额的工作负载成比例增加。另一方面，如果服务器有足够的资源来消费传入的请求，则排队时间会保持在一个较低的水平上。即使下游服务器可能响应速度较慢，只要上游服务器有足够的资源来处理等待的服务任务，其排队时间也不会受到影响，尽管其响应时间确实会由于下游服务的响应缓慢而增加。换句话说，只要下游服务器的响应时间增加，服务器的响应时间就会增加，即使服务器本身并没有过载。这有力地证明了队列时间可以反映服务器的实际负载状态，而响应时间很容易出现过载误报。

另一个问题是：为什么不使用 CPU 利用率作为过载指示？诚然，服务器中 CPU 利用率高表明服务器正处于高负载状态。然而，高负载并不一定意味着过载。只要服务器能够及时地处理请求（例如，排队时间较短反映了这一点），即使其 CPU 利用率保持较高，也不应该认为服务已经过载。

DAGOR 的负载监控是基于窗口的，并且窗口约束由一个固定的时间间隔和该时间间隔内的一个最大请求数组成。在微信业务系统中，只要满足任一个标准，每台服务器每秒或每隔 2000 次请求刷新一次平均请求排队时间的监控状态。这种复合约束确保了在工作负载动态的情况下，监控可以立即跟上负载的变化。对于过载检测，给定微信中每个服务任务的默认超时值为 500ms，而表示服务器过载的平均请求排队时间阈值设置为 20ms。这种经验配置已经在微信业务系统中应用了五年多，其有效性已被微信业务活动的系统健壮性所证明。

4.2 服务准入控制

一旦检测到过载，相应的过载控制就基于服务准入控制。DAGOR 包含了一组服务准入控制策略。本文首先介绍了 DAGOR 过载控制中采用的两种基于优先级的准入控制，然后扩展了该技术，以进一步支持自适应和协同的准入控制。

4.2.1 面向业务的准入控制

微信服务根据其业务意义和对用户体验的影响进行内部优先级排序，相应的服务请求也是如此。例如，登录请求具有最高的优先级，因为用户只有在成功完成登录后才能与其他服务交互。另一个例子是，微信支付请求比即时消息请求具有更高的优先级。这是因为用户往往对其与金钱相关的交互（如移动支付）比较敏感，而他们通常能够接受消息传递服务中的一定程度的延迟或不一致性。微信的运行日志显示，当微信支付和即时消息服务出现类似的服务不可用期时，用户对微信支付服务的投诉比对即时通讯服务的投诉高出 100 倍。类似的情况也适用于即时消息与朋友圈，因为用户期望即时消息的内容传递比朋友圈更及时。

DAGOR 中面向业务的准入控制是为每个用户请求分配一个业务优先级，并强制其所有后续请求继承相同的业务优先级。当服务过载时，其减载策略将优先放弃低优先级请求，为高优先级请求让出资源。用户请求以及它在调用路径上的后续请求的业务优先级是由要在入口服务中执行的操作类型决定的。由于微信的微服务架构中存在着数百个入口服务，所以在入口服务中执行的不同操作的数量有数百个。业务优先级被预先定义并存储在哈希表中，该哈希表被复制到负责入口服务的所有微信后端服务器中。哈希表中的项记录了从操作 ID（表示不同类型的操作）到优先级值的映射。图 3 展示了操作优先级哈希表的逻辑结构。注意，该哈希表并不包含所有类型的操作。默认情况下，哈希表中缺少的操作类型对应于最低优先级。在哈希表中只记录那些有意排序的操作类型，优先级值越小，表示操作的优先级越高。这导致哈希表中只包含几十个条目。由于在入口服务中执行的优先级操作集合在经验上是稳定的，所以尽管微信业务快速发展，哈希表仍然是紧凑的，很少有变化。

每当一个服务请求触发对下游服务的后续请求时，业务优先级值就会被复制到下游请求。通过递归，属于同一调用路径的服务请求共享相同的业务优先级。这是基于这样的假设，即任何服务请求的成功都依赖于它对下游服务的所有后续请求的联合成功。由于业务优先级独立于任何服务的业务逻辑，因此基于业务优先级的 DAGOR 服务准入控制是服务无感知的。而且，上述面向业务的准入控制易于维护，特别是对于复杂且高度动态的微服务架构（如微信后端）。一方面，通过引入操作优先级哈希表，业务优先级的分配在入口服务中完成，并且该哈希表很少随时间变化 4，这使得业务优先级分配策略相对稳定。另一方面，微信的微服务架构的动态一般反映在基础服务和中转服务的变化上，而不是入口服务。由于变化频繁服务的请求的业务优先级是从上游服务请求继承而来的，因此这些服务的开发人员可以简单地将面向业务的准入控制功能作为黑盒来应用，而不必考虑业务优先级 5 的设置。

图 3：微信入口服务中执行的操作的业务优先级哈希表

4.2.2 面向用户的准入控制

上面提到的面向业务的准入控制限制了是否丢弃请求取决于请求的业务优先级。换句话说，对于服务过载时的减载，面向业务的准入控制假定具有相同业务优先级的请求要么全部被丢弃，要么全部被接受。但是在过载服务中，对相同业务优先级的请求进行部分放弃有时是不可避免的。当过载服务的业务优先级的准入级别围绕其“理想最优性”波动时，这种必然性就会出现。为了详细说明，让我们考虑以下场景：过载服务中的减载完全基于面向业务的准入控制。假设当前业务优先级的准入级别为τ，但服务仍然过载。然后服务将准入级别调整为τ-1，即所有业务优先级值大于或等于τ的请求都被服务丢弃。然而，系统很快就发现，使用这种准入级别使得服务处于低负载状态。结果，准入级别被设为τ，然后服务很快又会过载。上述情景将继续重复。结果，上述场景中，业务优先级等于τ的相关请求实际上被服务部分丢弃。

部分丢弃具有相同业务优先级的请求可能会导致组合过载引发的问题。因为在这种情况下，这些请求实际上是被随机丢弃的。为了解决这一问题，我们提出了面向用户的准入控制，作为对面向业务的准入控制的补偿。DAGOR 中面向用户的准入控制是基于用户优先级的。准入服务通过一个以用户 ID 为参数的哈希函数动态生成用户优先级。每个准入服务每小时更改其哈希函数。因此，来自同一用户的请求可能会在一小时内被分配同一用户优先级，但在不同时间段分配不同的用户优先级。上述用户优先级生成策略具有双重的合理性。一方面，1 小时周期的哈希函数交替允许用户在长时间段内获得相对一致的服务质量。另一方面，哈希函数的交替考虑了用户之间的公平性，因为高优先级在一天中的每个小时内被授予不同的用户。与业务优先级类似，用户优先级也绑定到属于同一调用路径的所有服务请求中。

面向用户的准入控制与面向业务的准入控制是相互协调的。对于业务优先级等于过载服务业务优先级准入级别的请求，相应的减载操作优先于用户优先级高的业务。一旦服务 A 对过载服务 M 的请求得到成功的响应，服务 A 对服务 M 的后续请求也很有可能得到成功的响应。这就解决了由形式 2 的组合过载引起的问题，如图 2.b 所示。此外，图 2.c 所示的形式 3 的组合过载也可以用类似的方式正确处理。假设上游服务 A 按顺序调用两个过载的依赖服务，即服务 M 和服务 N。如果服务 M 的业务和用户优先级的准入级别比服务 N 的准入级别更严格，那么在形式 3 中的组合过载可以被消除。这是因为由于服务 N 宽松的准入级别，一个请求被服务 M 接受意味着其后续请求也被服务 N 接受。由于靠前的服务容易出现更严重的过载，因此形式 3 中相关服务之间的这种准入级别的条件通常存在于微信业务系统中。

4.2.3 面向会话的准入控制

除了面向用户的准入控制之外，我们还提出了面向会话的准入控制，以解决单纯应用面向业务的准入控制所带来的同样问题。面向会话的准入控制基于会话优先级，会话优先级的生成和功能与前面描述的用户优先级类似。唯一的区别是，生成会话优先级的哈希函数将会话 ID 作为参数。当用户成功登录时，会向其分配一个会话 ID，表示用户会话的开始。会话通常以用户执行确认注销结束。当同一用户在其先前注销后执行另一次登录时，将创建另一个具有不同会话 ID 的会话，从而会相应地生成一个新的会话优先级，尽管哈希函数保持不变。在 DAGOR 中的过载控制方面，面向会话的准入控制与面向用户的准入控制一样有效。但我们在微信业务系统中的操作经验表明，面向会话的许准入控制会降低用户体验。这是由微信用户在遇到应用程序服务不可用时，经常选择注销并立即重新登录的自然用户行为造成的。同样的现象也经常出现在其他移动应用中。通过注销和立即登录，用户将获得一个刷新的会话 ID。因此，面向会话的准入控制为用户分配了一个新的会话优先级，该优先级可能足够高，以至于过载的服务后端接受他/她的服务请求。用户可能会逐渐发现通过重新登录使他/她能够摆脱服务不可用状态的“诀窍”。当一个技巧被反复验证为有效时，它往往会成为用户习惯。然而，这种技巧并不能帮助减轻系统后端上实际发生的服务过载。此外，由于出现了误导性的注销和登录，会引入额外的用户请求，进一步恶化过载的情况，最终影响了大多数用户的使用体验。相反，用户的即时重新登录不会影响面向用户的准入控制中他/她的用户优先级。因此，在 DAGOR 过载控制中，我们更倾向于面向用户的准入控制，而不是面向会话的准入控制。

4.2.4 自适应准入控制

微服务系统中的负载状态总是动态变化的。服务在过载时对其负载状态的变化非常敏感，因为相应的减载策略依赖于超额负载的数量。因此，基于优先级的准入级别应该能够适应负载状况，有效地减少负载，最大限度地降低对整体服务质量的影响。当过载情况严重时，应将准入级别限制为拒绝更多的进入请求；相反，当过载情况缓和时，应放宽准入级别。在复杂的微服务体系结构中，过载服务的准入级别调整必须是自动的和自适应的。这就要求在 DAGOR 过载控制中必须进行自适应准入控制。

DAGOR 根据过载服务的负载状态来调整服务的准入级别。如图 4 所示，DAGOR 使用由业务和用户优先级组成的复合准入级别。每个业务优先级的准入级别与 128 个用户优先级准入级别相关联。设 B 和 U 分别表示业务优先级和用户优先级，复合准入级别表示为**(B，U)。图 4 中用箭头表示的游标表示当前的准入级别 6 为(2，3)，这表示为所有带有 B>2 的请求和带有 B=2 但 U>3**的请求都将被过载的服务丢弃。向左移动光标表示提高准入级别，即限制业务和用户优先级。

图 4：复合准入级别

如§4.2.1 所述，DAGOR 保持了几十种不同的业务优先级准入级别。随着每一个业务优先级别与 128 个用户优先级别的准入级别相联系，由此产生的复合准入级别的数量将达到数万。复合准入级别是以用户优先级为粒度进行调整。为了根据负载状态搜索合适的准入级别，一种简单的方法是从最低级别开始逐级尝试，即在图 4 中，将光标从最右边向左移动。注意，对于准入级别的每个设置，服务器必须花一些时间来验证其有效性，因为负载状态是在某个时间间隔内聚合的。由于传入的请求不可能均匀地分布在准入级别上，这种简单的方法往往很难找到合适的设置。这是因为在该方法中对准入级别的每一次调整，即把光标向左移动一个用户优先级，对过载情况产生的影响很小，但需要时间来验证其充分性。因此，通过简单的扫描来调整准入级别难以满足自适应准入控制的实时性要求。基于上述简单方法的一个即时改进是执行二分搜索而不是线性扫描。这使得搜索复杂度从 O(n)降低到 O(logn)，n 表示复合准入级别的总数。考虑到微信的实际准入级别数量在 104 量级上，**O(logn)**搜索涉及到十几次调整准入级别的尝试，这仍然被认为是不够效率的。

为了提高自适应准入控制的效率，DAGOR 利用一个请求直方图，快速计算出适合负载状态的准入级别设置。直方图有助于显示请求在准入优先级上的大致分布。特别地，每个服务器维护一个计数器数组，其中每个计数器对应于一个由**(B,U)索引的复合准入级别。每个计数器计算与对应的业务和用户优先级相关的已接受请求的数目。DAGOR 周期性地调整减载的准入级别并重置计数器。调整周期与§4.1 所述的过载检测窗口大小一致，例如，每隔 1 秒或每 2000 次微信业务系统请求。在每个周期，如果检测到过载，服务器将下一周期的期望传入请求量下调α**（百分比）,该值小于当前周期的传入请求量；否则，下个周期的期望请求数量将提高β(百分比)。从经验上讲，我们在微信业务系统中设置了α=5%和β=1%。给定期望的准入请求数量，准入级别是根据接近该数量的直方图中的最大前缀和来计算的，并且根据当前状态以及是否检测到过载来进行调整。设 B∗和 U∗分别表示业务优先级和用户优先级的准入级别的最佳设置。当检测到过载时，最佳的复合准入级别**(B∗,U∗)的设置由(B,U)≤(B∗,U∗)**7 的计数器的总和刚好不超过期望请求数量的约束所确定。算法 1 总结了 DAGOR 中自适应准入控制的过程。请注意，即使系统在某些时候没有过载，由于当前的准入级别设置，某些请求仍可能被丢弃，尤其是当系统正在从上个过载状态恢复时。显然，上述方法每次调整准入级别都只涉及到一次验证的试验。因此，它比上述的朴素方法更有效，能够满足自适应准入控制的实时性要求。

算法 1：自适应准入控制

4.2.5 协同准入控制

DAGOR 通过基于优先级的准入控制来强制过载服务器执行减载。对于消息传递，注定被下游过载服务器丢弃的请求仍然必须从上游服务器发送，并且下游服务器随后将相应的响应发送回上游服务器以通知拒绝该请求。这种不成功请求处理的消息来回传递不仅浪费网络带宽，而且消耗过载服务器的紧张资源，例如，序列化/反序列化网络消息。为了节省网络带宽和减轻过载服务器处理多余请求的负担，建议在上游服务器早期拒绝注定要丢弃的请求。为此，DAGOR 支持在过载服务器及其上游服务器之间进行协同准入控制。特别是，服务器将其当前的准入级别**(B,U)**附加到它发送给上游服务器的每个响应消息中。当上游服务器接收到响应时，它将了解下游服务器的最新准入级别。通过这样做，只要上游服务器打算向下游服务器发送请求，它就会根据存储的下游服务器准入级别对请求执行本地准入控制。结果，注定要被下游服务器拒绝的请求往往在上游服务器就被丢弃，而从上游服务器实际发送的请求往往会被下游服务器接受。因此，虽然服务器中的准入控制策略是由服务器本身独立决定的，但实际的减载操作由其相关的上游服务器执行。在微服务架构中，上游和下游服务器之间的这种协作极大地提高了过载控制的效率。

4.3 过载控制的工作流程

基于前面提到的服务准入控制策略，我们现在描述 DAGOR 过载控制的总体工作流程，如图 5 所示。

1. 当一个用户请求到达微服务系统时，它将被路由到相关的入口服务。入口服务将业务和用户优先级分配给请求，所有后续的对下游服务的请求都继承被封装到请求头中的相同优先级。

2. 每个服务根据业务逻辑调用一个或多个下游服务。服务请求和响应通过消息传递。

3. 当一个服务接收到一个请求时，它根据当前的准入级别执行基于优先级的准入控制。服务根据负载状态定期调整其准入级别。当服务打算向下游服务发送后续请求时，它根据存储的下游服务准入级别执行本地准入控制。上游服务只发送本地准入控制所允许的请求。

4. 当下游服务向上游服务发送响应时，它将其当前的准入级别附加到响应消息中。

5. 当上游服务收到响应时，它从消息中提取准入级别的信息，并更新下游服务在本地的相应记录。

图 5:DAGOR 过载控制工作流

DAGOR 满足在本节开始时提出的微服务架构对过载控制的所有要求。首先，DAGOR 是服务无感知的，因为服务准入控制策略是基于与业务逻辑正交的业务和用户优先级。这使得 DAGOR 普遍适用于微服务系统。第二，DAGOR 的服务准入控制是独立但协同的，因为准入级别是由单个服务决定的，而准入控制则由相关的上游服务协同执行。这使得 DAGOR 具有高度可扩展性，可用于大规模、适时演变的微服务架构。第三，DAGOR 过载控制是有效和公平的。由于属于同一调用路径的所有服务请求共享相同的业务和用户优先级，因此它可以有效地消除组合过载导致的性能下降。这使得上游服务能够在下游服务过载的情况下保持其饱和吞吐量。

5. 评估

DAGOR 在微信业务系统中的应用已经有五年多的时间了。它极大地增强了微信服务后台的健壮性，帮助微信在各种高负荷运行的情况下生存下来，包括在每天的高峰时段以及特殊事件期间，如中国农历新年前夕。在本节中，我们进行实验研究，以评估 DAGOR 的设计，并将其与最新的负载管理技术进行有效性比较。

5.1 实验设置

所有实验都在内部集群上运行，其中每个节点都配备了 IntelXeonE5-2698@2.3 GHz CPU 和 64GB DDR3 内存。集群中的所有节点都通过 10 千兆以太网连接。

工作负载：为了独立地评估 DAGOR，我们实现了一个压力测试框架，模拟在微信业务系统中使用的加密服务。具体来说，加密服务（表示为 M）专门部署在 3 个服务器上，饱和吞吐量大约是每秒 750 个查询（QPS），因此很容易过载。在另外 3 台服务器上部署了一个简单的消息传递服务（表示为 A），通过按照工作负载的请求多次调用服务 M 来处理预定义的服务任务。工作负载由 20 个应用服务器综合生成，这些应用服务器负责生成服务任务，并且在实验中从未过载。每个服务任务被编程为通过服务 A 一次或多次调用服务 M，并且任务的成功取决于这些调用的联合成功 8。设 Mx 表示对服务 M 进行 x 次调用的任务组成的工作负载。实验中使用了四种类型的工作负载，即 M1、M2、M3 和 M4。关于过载场景，M1 对应于简单过载，而 M2、M3 和 M4 对应于组合过载。

5.2 过载检测

我们首先评估 DAGOR 的过载检测，这是过载控制的切入点。特别地，我们实验验证了 DAGOR 的设计选择，即§4.1 中所讨论的采用平均请求排队时间而不是响应时间作为负载状态的指标进行过载检测。为此目的，我们另外实现了一种 DAGOR 变体，使用监视窗口（即每秒或者每 2000 个请求）上的请求的平均响应时间作为过载检测指标。设 DAGORq 为基于请求排队时间的过载检测的 DAGOR 实现(DAGORr 为基于响应时间的实现)。我们分别运行 M1 和 M2 实验，将进给速率从 250QPS 变化到 1500QPS，进行了实验。图 6 显示了 DAGORq 和 DAGORr 之间的比较。对于图 6.a 所示的简单过载，我们分别将平均排队时间和响应时间的阈值设置为 20ms 和 250ms。从实验结果可以看出，当进给速率达到 630QPS 时，DAGORr 就会开始减载，而 DAGORq 可以将减载延迟到输入量为 750QPS。这意味着基于响应时间的负载分析很容易出现过载的误报。图 6.b 通过运行 M2 工作负载，在涉及到组合过载中进一步证实了这一事实。除了图 6.a 所示的设置外，我们在图 6.b 中还测量了响应时间阈值为 150ms 和 350ms 的 DAGORr 的成功率曲线。结果表明，当响应时间阈值设置为 250ms 时，DAGORr 具有最佳性能。然而，由于请求响应时间中包含了特定于服务的请求处理时间，因此在实际中很难优化 DAGORr 的优化配置。相反，除了 DAGORq 的优越性能之外，由于请求排队时间与任何服务逻辑无关，它的配置也很容易进行调优。

图 6：不同负载分析指标下的过载检测：排队时间与响应时间。

5.3 服务准入控制

接下来，我们对 DAGOR 负载管理的服务准入控制进行了评估。如§4.2 所述，DAGOR 服务准入控制是基于优先级的，该优先级进一步设计为面向业务和面向用户。面向业务的准入控制被目前最先进的负载管理技术[25,32]普遍采用。DAGOR 的新颖之处在于它增加了面向用户的优先级以实现细粒度负载管理，从而提高了端到端的服务质量。此外，DAGOR 过载控制通过自适应准入控制，能够实时地调整服务准入级别，并通过采用协同准入控制，对减载运行时间进行了优化。这些不同的策略将 DAGOR 从机制上区别于现有的负载管理技术。因此，为了验证 DAGOR 的创新在服务准入控制方面的有效性，我们通过对所有生成的查询请求固定业务优先级的实验，将 DAGOR 与最先进的技术进行了比较，如 CoDel[25]和 SEDA[32]。此外，我们还采用了一种简单的服务准入控制方法，对过载服务 M 随机地执行减载。这种简单的方法可以作为实验的基准。

图 7 展示了分别运行 M1 和 M2 工作负载的比较结果。每张图比较了在采用不同的服务准入控制技术时，上游服务请求的成功率。此外，我们也描述了当对应的下游服务过载时，上游服务的理论最优成功率。最优的成功率由 fsat /f 计算，其中 fsat 是使下游服务饱和时的最大进给速率，而 f 是指下游服务过载时的实际进给速率。从图 7.a 可以看出，所有过载控制技术对于简单过载（即 M1）的性能大致相同。然而，当涉及到组合过载时，如图 7.b 所示，DAGOR 在 M2 的工作负载中的成功率比 CoDel 和 SEDA 高 50%左右。图 8 通过将进给速率固定到 1500QPS，随着组合过载在 M3 和 M4 的工作负载中的增加，进一步显示了 DAGOR 的优势。此外，DAGOR 提供的请求成功率在上述所有结果中都接近最优。DAGOR 的这种优越性在于它基于优先级的准入控制，尤其是面向用户的策略，对组合过载的有效抑制。

图 7：随着工作负载增加的过载控制

图 8：不同工作负载类型下的过载控制

5.4 公平性

最后，我们评估了在不同的过载情况下过载控制的公平性。公平性指的是过载控制机制是否偏向于一个或多个特定的过载形式。为此，我们运行由分布均匀的 M1、M2、M3 和 M4 请求组成的混合工作负载。请求由客户端同时发出，进给率从 250 到 2750QPS 不等。每个请求的业务优先级和用户优先级都是在固定范围内随机选择的。我们比较了 DAGOR 和 CoDel 请求成功率的公平性，结果如图 9 所示。可以看出，CoDel 偏向简单的过载（即 M1）而不是组合过载（例如 M2、M3 和 M4）。CoDel 的这种偏向使其过载控制依赖于服务工作流，在这种情况下，更复杂的逻辑往往在系统过载时更容易失败。相反，对于不同类型的请求，DAGOR 显示的成功率大致相同。这是因为基于优先级的 DAGOR 准入控制极大地减少了组合过载的发生，而不管上游对过载的下游服务的调用次数。

图 9：过载控制公平性

6. 相关工作

已有的关于过载控制的研究主要集中在实时数据库[3,14]、流处理系统[4,19,27,28,33]和传感器网络[30]。对于网络服务，过载控制技术主要是在 web 服务的背景下提出[11]。然而，这些技术大多是为传统的单一服务架构设计的，并不适用于基于 SOA 构建的现代大规模在线服务系统。据我们所知，DAGOR 是第一个专门解决大规模微服务体系结构过载控制问题的方案。由于微服务架构通常被认为属于 SOA 家族，所以我们仔细研究了新出现的用于 SOA 的过载控制技术，这些技术是基于准入控制[5-7,26,31]或资源调度[1,2,18,22,24]的。

通过捕获现代云系统的复杂交互来控制网络流，可以减轻系统过载的影响。Varys[8]利用协同流和任务抽象来调度网络流，以减少任务完成时间。但是它依赖于流大小的先验知识，同时也假定了集中式流量控制的可用性。这使得该方法只适用于有限规模的云计算基础架构。Baraat[10]采用一种类似 FIFO 的调度策略来摆脱集中控制，但以牺牲性能为代价。与这些基于协同流的控制相比，DAGOR 不仅是服务无关的，而且与网络流特性无关。这使得 DAGOR 成为适合微服务架构的非侵入式过载控制。

Cherkasova 等人[7]提出了基于会话的准入控制，它通过计算完成的会话数来监控 web 服务的性能。当 web 服务过载时，准入控制会拒绝创建新会话的请求。Chen 等人[5]进一步提出了基于 QoS 的会话准入控制，利用会话的依赖性来提高服务过载时的服务质量。然而，这些技术倾向于长期使用的会话，因此不适合使用包含大量短期和中期会话的微信应用程序。与之不同的是，DAGOR 的准入控制是面向用户的，而不是面向会话的，因此它不会在过载控制中偏向服务的任何会话相关属性。此外，以上基于会话的技术依赖于一个集中式模块来进行过载检测和过载控制。这种中心化模块往往成为系统瓶颈，从而限制了系统的可扩展性。相反，DAGOR 的设计是去中心化的，因此它具有高度的可伸缩性，以支持大规模的微服务体系结构。

Welsh 等人[31，32]提出了分级过载控制技术，该技术根据服务语义将 web 服务划分为若干阶段，并对每个阶段分别执行过载控制。每个阶段都静态地分配一个资源配额来限制负载。尽管这种机制与 DAGOR 有一定的相似性，但其服务划分和静态资源分配的前提条件使其不适用于微信后端等复杂的动态服务体系结构。相反，DAGOR 是与服务无感知的，这使得它灵活且高度适应于不断发展的微服务体系结构。

以减少响应时间为目标的网络过载控制已经得到了很好的研究[16]。从微信业务系统的运行经验来看，面向延迟的过载控制在大规模微服务体系结构中的应用效果并不理想。这就促使我们在 DAGOR 中采用排队时间来检测过载。此外，在 THEMIS 系统中讨论的技术[17]启发我们在 DAGOR 设计中考虑公平性。

7. 结论

本文提出了用于微服务体系结构的 DAGOR 过载控制方案。DAGOR 的设计是服务无感知的，独立但协作，高效和公平的。它是轻量级的，并且普遍适用于大规模的、适时演变的微服务系统，以及对跨团队敏捷开发具有友好性。我们在微信的后端实现了 DAGOR，并在微信的业务系统中运行了五年多。除了在微信实践中证明了 DAGOR 的有效性外，我们相信 DAGOR 及其设计原则对其他微服务系统也是有启发性的。

**经验教训：**在微信后端将 DAGOR 作为生产服务运行已经超过 5 年了，我们下面将分享从开发经验中获取的教训以及设计原理：

• 大规模微服务体系结构中的过载控制必须在每个服务中都是去中心化和自治的，而不是依赖于集中的资源调度。这对于过载控制框架与不断发展的微服务系统相协调是至关重要的。

• 过载控制的算法设计应该考虑多种反馈机制，而不是仅仅依赖于开环启发式算法。DAGOR 中的协同准入控制策略就是一个具体的例子。

• 过载控制的有效设计总是从实际工作负载中的处理行为全面分析中推导出来的。这是 DAGOR 在设计中使用请求排队时间进行过载检测以及设计基于优先级的两级准入控制以防止组合过载的基础。

致谢

我们感谢匿名审稿人提出的有助于改进论文的宝贵意见和建设性建议。

脚注

1. 例如，账号服务维护用户的登录名和密码，个性化设置服务维护用户的昵称和其他个人信息，联系人服务维护用户的好友列表，信息收件箱服务缓存用户收到和发送的信息。

2. 实际上，形式 2 和形式 3 在 GFS 类系统[13]中也很常见。在这里，一个大文件被分割成许多块，分布在不同的存储服务器上，并且需要检索所有块来重新构造原始文件。

3. 响应时间定义为请求到达服务器与相应响应从服务器发送之间的时间差。

4. 为了性能调优或特别的服务支持，操作优先级哈希表可能会被动态修改。但是，这种情况在微信业务系统中很少发生，例如，每年 1 次或 2 次。

5. 我们过去还为服务开发人员提供 APIs，以调整服务请求的业务优先级。然而，结果证明该解决方案不仅在不同的开发团队之间非常难以管理，而且在过载控制方面也很容易出错。因此，我们在微信业务系统中弃用用来设置特定于服务的业务优先级的 APIs。

6. 如果没有指定，我们将在本文的其余部分使用准入级别来表示复合准入级别。

7. 对于两种准入级别**(B1, U1)和(B2, U2)，我们使(B1, U1) < (B2, U2)，如果 B1<B2**，或者 B1=B2 但是 U1<U2。

8. 在发生拒绝的情况下，相同的调用请求最多将被重发三次。

参考资料

​ 本文转自微信后台团队,如有侵犯,请联系我们立即删除

OpenIMgithub 开源地址：

https://github.com/OpenIMSDK/Open-IM-Server

OpenIM 官网 ： https://www.rentsoft.cn

**OpenIM 官方论坛： ** https://forum.rentsoft.cn/

更多技术文章：

开源 OpenIM：高性能、可伸缩、易扩展的即时通讯架构https://forum.rentsoft.cn/thread/3

【OpenIM 原创】简单轻松入门 一文讲解 WebRTC 实现 1 对 1 音视频通信原理https://forum.rentsoft.cn/thread/4

【OpenIM 原创】开源 OpenIM：轻量、高效、实时、可靠、低成本的消息模型https://forum.rentsoft.cn/thread/1