关系感知路由与全球流量调度 · SOSP 2019
『看看论文』是一系列分析计算机和软件工程领域论文的文章，我们在这个系列的每一篇文章中都会阅读一篇来自 OSDI、SOSP 等顶会中的论文，这里不会事无巨细地介绍所有的细节，而是会筛选论文中的关键内容，如果你对相关的论文非常感兴趣，可以直接点击链接阅读原文。
本文要介绍的是 2019 年 SOSP 期刊中的论文 —— Taiji: Managing Global User Traffic for Large-Scale Internet Services at the Edge[^1]，该论文介绍的 Taiji 是 Facebook 在大规模互联网服务中动态管理用户流量的系统，通过该系统我们可以平衡各个数据中心的资源利用率并降低用户请求的网络延迟。
Taiji 会利用用户之间的关系将一批强相关的用户路由到相同的数据中心，这种关系感知路由策略能够降低 17% 的后端存储负载。多数的服务都会使用静态映射将用户请求从边缘节点路由到数据中心，但是静态的映射很难处理大规模的全球数据中心，不同地区的边缘节点的不同负载和高峰时段会带来以下的一些挑战：
- 容量短缺（Capacity crunch）— 如果服务的容量超过了采购计划，我们可能无法服务全部的用户请求，而静态的映射调度可能会使某些数据中心处于资源短缺或者而另外一些处于过度供应的状态；
- 产品异构（Product heterogeneity）— 随着产品的逐渐迭代，我们可能会在交互方面提升用户的体验，当请求需要用户设备与数据中心维持固定的会话时，静态映射很难管理用户流量；
- 硬件异构（Hardware heterogeneity）— 底层基础设施的演变会影响数据中心能够处理的流量，例如：服务器的更新、容量的增减、网络设备性能的提升；
- 错误容忍（Fault tolerance）— 当基础设施变得越来越复杂，边缘节点或者数据中心会有更高的几率出现网络错误、断电以及软件错误等问题，静态映射难以快速响应问题并缓解故障；
为了解决上述的问题，Facebook 的工程师设计出了全球用户流量管理系统，该系统将边缘节点到数据中心的路由过程看做分配问题（Assignment Problem），我们会通过约束优化器生成路由表，路由表能够决定处理用户请求的数据中心，边缘节点会遵循路由表转发用户请求。
架构
在成熟的内容分发网络（Content Delivery Network、CDN）中，边缘节点可以处理用户的绝大多数请求，它能够低成本地、快速地提供静态资源，静态资源的分发和流量调度已经有了一些比较成熟的解决方案，但是动态的内容往往需要具有更多计算和存储资源的数据中心处理，在不同数据中心之间快速、稳定的平衡负载是一个比较复杂的问题，Taiji 会使用如下所示的架构控制从边缘节点到数据中心的流量来解决该问题：
图 1 - Taiji 架构 Taiji 系统由两个主要的组件构成，分别是运行时（Runtime）和流量管道（Traffic Pipeline），这两者在系统中起到了如下所示的作用：
- 运行时会根据流量负载、数据中心利用率、边缘节点与数据中心的延迟以及服务级别策略生成路由表；
- 流量管道会将路由表翻译成细粒度的规则，利用关系感知路由为边缘节点上的负载均衡生成路由配置并将用户的请求到转发特定的数据中心；
如上图所示，边缘节点的负载均衡解析所有的用户请求并将用户映射到合适的桶中，然后根据路由配置将用户请求转发到桶对应的数据中心。
运行时
运行时组件会负责生成路由表，该路由表指定了部分用户流量从边缘节点转发到的数据中心，路由表由以下的一组元组构成：
{edge:{datacenter:fraction}}为了生成由上述元组组成的路由表，Taiji 的运行时会从监控系统中读取两种类型的动态数据：
- 基础设施的运维状态，例如：容量、健康状态、边缘节点和数据中心的利用率；
- 测量数据，例如：边缘节点的流量以及从边缘节点到数据中心的访问延迟；
上述的这些数据都是未经处理的原始数据，我们在整个系统中会引入读取层抽象，帮助我们对原始数据进行读取、标准化以及聚合，这样能够减少运行时其他部分的工作量，可以更好地对问题进行建模：
runtime-architecture
图 2 - 运行时架构
Taiji 的运行时会使用每秒的请求数（RPS）衡量无状态服务的流量，使用用户会话数量衡量有状态服务的流量，该模型可以允许无状态流量路由到任意可用的数据中心，并将有状态的流量约束到相同的机器上避免影响建立的会话。
在每一个时间周期（Epoch）中，Taiji 都会根据数据中心的资源利用率重新评估全局的流量分配决策，在重新评估的过程中，该系统会使用如下所示的步骤改变数据中心的路由以满足服务指定的策略：在两个数据中心之间切换一单位的流量、识别当前最优的路由策略、不断迭代直到不能实现更好的结果。除此之外，为了保证整个系统的稳定，运行时还需要控制流量调度的频率，避免对单个数据中心造成较大的抖动以影响整个系统。
流量管道
流量管道会消费运行时模块输出的路由表并使用关系感知路由在配置文件中生成特定的路由规则，当我们生成了新的路由规则之后，该模块会通过配置管理服务（Configuration Management Service、CMS）将规则同步到所有的边缘负载均衡上，整个过程大概也只需要一分钟左右的时间。
关系感知路由构建在请求相同内容的用户流量具有局部性的特点上，这对数据的缓存和其他后端系统有积极的作用，正是因为流量具有这样的特点，我们才会将高度关联的用户路由到相同的数据中心进行处理，降低系统的延迟。
图 3 - 关系感知路由
如上图所示，关系感知路由根据所属的社区将用户分到了不同的桶中，它会使用平衡树保证每一个用户桶中都有数量差不多的用户，同时也最大化桶中用户的关联程度。然而桶的大小对系统的性能有着很重要的影响，过小的桶可能会使大的社区被分割，从而降低缓存的有效性；而过大的桶会提高缓存的有效性，不过会影响路由的精度，Taiji 期望每个桶的流量占全局流量的 0.01%，这样才能在缓存有效性和路由精度之间做出平衡。
- 离线任务 — 用户、桶分配；
- 在线任务 — 桶、数据中心分配；
上述的这种方式可以让同一个社区转发到相同数据中心的流量从 55% 提高至 75%，能够非常明显地提高后端服务的资源利用率，接下来我们将分别介绍上述两种不同的任务以及边缘节点负载均衡处理请求的过程。
离线模块
系统中的社区层级会以完全二叉树的结构表示，二叉树的叶节点是用户组成的桶，内部的节点表示子树中的所有桶，我们会使用社交哈希（Social Hash）构造整棵树。因为树的构造是离线的，同时也需要非常大的计算量，所以系统会以周的频率定期更新二叉树。
虽然使用二叉树的方式分割用户比较有效，但是也无法适用于全部的场景，它在以下两种情况中并不能很好地工作：
- 用户访问高度连通的实体，例如：各种明星以及名人，这种场景更类似于发布和订阅消息；
- 一次性的交互，例如：支付等一次性的临时操作，类似的交互不会被系统看做用户之间存在关联；
在线模块
流量管道的在线模块会根据离线模块生成的树状结构、每个桶的流量以及数据中心的容量为桶分配合适的数据中心，该过程会尽量将一组相邻的桶分配到同一个数据中心以提高数据的访问局部性。
边缘负载均衡转发
既然边缘节点需要负责将用户的请求转发到特定的数据中心，那么所有的边缘节点都需要存储路由表以确定处理当前请求的数据中心，不过直接存储用户到数据中心的路由表需要占用非常大的内存，所以边缘节点只会存储桶到数据中心的映射，当用户向边缘节点发出动态内容请求时会经过以下过程：
- 初始用户请求没有桶的信息，用户会把它路由到最近的数据中心；
- 最近的数据中心会存储用户对应的桶，我们会将用户的桶写入 Cookie；
- 之后的请求都会携带 Cookie，边缘负载均衡会把请求直接路由到特定的数据中心；
关系感知路由会在原有的请求处理路径上带来可以忽略不计的额外开销，桶到数据中心的映射文件会每五分钟同步一次，大小约为 15KB，这样的内容在网络中的传输开销几乎是可以忽略不计的。
总结
Facebook 在这篇论文中介绍的 Taiji 系统能够在数据中心的维度对系统整体的负载进行调节，Facebook 作为社交网络的巨头，它的很多业务都与社交和用户关系相关，而该系统基于的关系感知路由也是为它的业务量身定做的，正是因为高度关联的用户会请求类似的内容，所以基于关系的路由才能优化系统，将用户请求路由到最近的、利用率低的集群，也能够提升系统的访问局部性并减少计算资源的消耗。