Taiji: Managing Global User Traf

摘要

论文地址
这个系统想要完成2个目标 去管理用户的请求在large-scale 的网络服务上

1. 平衡数据中心的利用率
2. 减少用户请求的网络延迟

做法是：

1. edge-to-datacenter traffic routing 转换为 一个 assignment的问题
2. 使用一个带约束的优化solver产生一个optimal routing table 去定义每个edge node 到 不同的dc的比例。
3. Taiji 会持续调整 路由表 来适配动态的用户请求和失败的事件。

背景

image.png

facebook 有着世界各地的用户。他们拥有很多edge node。 和许多DATA CENTER。 用户访问facebook 的时候，会首先到达edge node, 所有静态资源会从cdn里获取，而动态资源，比如说news feed, 就需要call 到 dc(data center) 去获取。 那么用户的请求如何从edge node 分发到dc 就是一个值得考虑的问题。

image.png
上图中是一个不好的情况，所有请求都被分到一个dc造成了负载的不均衡。

一般的策略是，应该把请求路由到最近的dc，这样可以有最低的延迟。但是我们知道dc的负载不均衡的问题依然存在。很有可能会出现异常火爆的dc请求，这个时候为了缓解某个dc的压力，我们可以选择稍远一点的反而更快。

另外dc在对用户内容做运算的时候，大量数据是会被缓存。当某一组强关联的好友，他们打开fb看到的内容也是非常相似的。那么把他们的请求都发送到某一个dc 则可以很好利用缓存的局部性，提高缓存命中率。减少对data store层的压力，并减少延迟。

总结一下，上面就有3个目标：

1. 平衡dc的负载
2. 最小化延迟
3. 利用局部性，提高缓存利用率

要达到这3个目标是非常有挑战的。

1. 用户的请求是变动的，而且变动在每个地区是不同的。

   
   image.png
2. 数据中心就是变动的，他们可能需要升级，重启，废除。因此dc能力时刻变化，而且会有新的dc发布。
3. failure 在这么大规模的机器中是很常见的。从丢一台机器到整个dc挂掉。当某个dc挂了，我们必须有能力把请求都分配到其他好的dc上。

在15年之前，fb 都是使用静态映射的策略。就是一张固定的流量分配表，告诉某个edge node 该怎么往dc分发流量。
经过统计，这种方式会造成dc负载分配不均匀，并且在高峰时段，有些dc负载过高，超过了安全的threshold （超过之后，会增加延迟，timeout, 甚至打挂机器)

image.png

解决方案 - Taiji

首先taiji 是一个持续操作交互的系统，负责管理edge 到 dc的traffic，会根据用户的请求数量情况，容量的变化，失败发生的情况 去 智能的分发请求。使得可以达成之前提到的3大目标。

image.png

taiji的架构分为2块，对应了2个基础问题。

1. 我给分配多少traffic 从每个edge 到 dc? 对应balance & minimize latency
2. 如何去route users? 对应 cache efficiency

image.png

第一个模块它决定了edge node 到 dc 的分配比率。
第二个模块，在知道了分配比率的情况下，去把分配每个用户应该进哪个dc。

image.png

要完成第一个目标，我们就需要算一个 当前的总的rps， 和当前每个dc 能handle的 rpc 的总和。 这个数值做除法，就是每个dc最理想的利用率。比如下图。
(4+4) / (6+4+6) = 50%

image.png

同时admin 也可以根据自定义policy 来决定 是重点考虑平衡 还是 延迟。比如上图，有25%的请求会被发到较高延迟的dc。

image.png

这个问题就被转化一个 带限制条件的最优化问题。这个设计同时也可以让service owner 去 实验不同的routing policy 去找到最好的效果。

第一个模块根据policy 和 dc 监控的反馈数据，用算法最后能算出最适合当前的比例。

image.png
格式为
{edge:{datacenter:fraction}}
例子就是
{edge1:{dc1:50%, dc2:50%}}

下面介绍第二个模块

第二个模块会知道每个dc需要分配多少的流量，但是具体哪个用户会落到哪个dc是第二个模块去算的。而他的优化目标，是尽可能把connected users 发到同一个dc。
这里使用了social hash的技术，来把当前的用户集合一分为2， 2边数量一致的情况下，使得2个子集合的联系(connection)最少。这样递归的拆分。就可以获得一颗完全二叉树。那么到底拆分几次（树高为多少？） 就是一个trade-off的问题。
如果层数过少，那么路由的粒度会很粗，好比你想调整1%，但是你的叶子节点的粒度就是5%，你就没办法做调整。
如果层数过多，那么就会把一些原本强相互的用户被迫拆开了。
所以这边fb 选取了 一个 0.01%的粒度。

image.png

有了这颗树之后，我们就可以对每个bucket 去根据第一个模块传来的比例，去分配到的对应的dc。
上面这个步骤是离线算的，因为要对全量用户计算，所以一周只会算1次。

下面就是把用户分配进哪个dc，这个是在线算的。其实这边只是算一下每个dc会有哪个bucket. 然后把 bucket -> dc 的 map 给分发到所有的edge节点，这个数据量大小非常小。而把用户-> dc 的数据发到edge的话，会占用非常多的网络资源和内存资源。所以当一个用户新来的时候，请求是不知道他属于哪个bucket（edge上不存），所以会先去最近的一个dc寻找（dc存），然后通过cookie的方式返回给用户，之后根据cookie就可以知道他属于哪个bucket，再根据edge的map表知道该去哪个dc获取动态数据。
这样就使得，connection比较多的用户会去同一个dc，获取数据。增加了cache efficency。

算法伪代码

这个算法背后的思想，就是尽可能的把一个大的子树放进一个dc，然后用叶子节点去微调以达到balance 负载的效果。为了确保在每个edge上，在线算的结果大方向接近一致。 segment 的唯一排序是 使用随机排列为每个数据中心生成 (P) dc name的seed去算的。有了固定的 seed ，排序就会统一。（代码第8行）

image.png

代码第10行，会把bucket 和 segment 给map起来。
代码第11行， tuple 代表(dc, bucket)的pair,从数据中心对bucket所属的segment的preference开始
所有这些元组都是 按字典顺序排序，按preference顺序，然后是dc，最后bucket(第14行)。
tuple按排序顺序遍历，bucket被贪心的分配给数据中心， 直到一个数据中心拥有它想要的权重

评估

balance

image.png

有了taiji 之后，80%的时间，负载不均衡不会超过3%

image.png

分歧是由于连续部署，也就是图上的峰值。持续部署会关闭机器来部署新代码，这可能会导致不平衡。即使是连续部署，taiji也能够保持负载的平衡。

latency

taiji 相比 2015 的 静态策略，有效降低了延迟在平衡balance 的基础上。lower bound 是根据假设所有dc都有无限的cap，然后把请求都按照最近的dc来分配算出来的极限最优值。

cache efficency

把强关联的用户组合在一起，发送到一个dc，有效的减少了对后端存储的17%的读请求（都从cache拿到了）

image.png image.png

局限性

1. 首先，taiji 只考虑 edge 到 dc 的延迟。但是，服务所有者关心端到端延迟。例如，之前提到过的，当延迟最优路由策略(所有请求都打给最近的dc，不考虑balance)可能获得edge -> dc的低延迟，但是由于dc压力很大，需要排队和更高的处理时间时间。在这种情况下，平衡利用率将实现更好的端到端延迟。我们依靠服务所有者来配置Taiji来解决这个问题。

2. 第二，太极只考虑前端利用率，而不考虑后端利用率。我们通过运行连续的负载测试来验证后端服务的配置大小是否合适来解决这个问题。