关于云计算:智能选路系统与架构

01 背景

阿里云作为亚太第一云厂商，须要服务各种各样的细分畛域客户，例如 3C、游戏、网页减速等客户。近年来，随着视频征询类客户的蓬勃发展（头条），低提早、高可用的寰球网络需要也越来越旺盛。因而，在“全站减速”架构设计之初，就须要思考如何为海量客户构建差异化的低提早网络。

阿里云目前曾经建设有 2800+ 个寰球节点，但这些节点的带宽能力、互联互通能力、对 TCP/QUIC 等传输协定兼容能力都不尽相同。因而，如何在这种简单的、多维束缚的网络环境中抉择适合的网络通道（即智能选路），就变得非常重要了。

02 海量客户的智能选路

从图论的角度看，CDN 节点、客户源站相似于图中的节点（node），节点间网络、回源网络相似于图中的 edge，由这两者组成的有向图 G(node, edge)，就是智能选路须要求解的选集。

所以智能选路零碎实质上是：在有向图 G 中寻找最“短”门路的过程。尽管这个“短”会叠加上很多定语，例如：在带宽容许的状况下，在跳数限度的状况下（因为跳数越多，老本越高）。但为了简化问题，能够先不思考这些定语，即有限资源场景下的智能选路。这在产品上线晚期，客户少、带宽等资源占用少的时候，是比拟实用的。

1. 最短门路

介绍智能选路零碎绕不开的一点，就是最短门路算法的选型。思考到理论公网中，是不会存在负权重的场景，因而只须要在 Dijkstra（单源最短门路，以下简称 D 算法）、Floyd（多源最短门路，以下简称 F 算法）中抉择即可。

乍一看，要解决海量客户的智能选路问题，仿佛就应该抉择 F 算法，但认真想想其实应该组合应用。智能选路是要解决客户端到源站的最短门路问题，它是不须要计算不同源站间的最短距离的，即它不是一个 P2P 的选路问题。随着客户源站数量的一直增长，算法所需的邻接矩阵会越来越稠密，这时候 D 算法的性能劣势就展示进去了。

当然 F 算法也不是一无是处的。把智能选路合成为 2 个子问题：CDN 节点间最短问题 + 回源网络最短问题，思考 CDN 节点间网络是强连通的浓密网络，因而求解过程用 F 算法会比 D 算法更快。在求解全链路最短问题是时再应用 D 算法。这种算法组合能获取 1 个数量级的计算耗时缩短（当然，晋升多少其实也取决于客户源站数量级）。

2. 多样门路

从高可用（即零碎稳定性）的角度看，任意 2 点间只给出 1 条最短门路是不够的。因为一旦这条门路上的光线被挖断、节点因故障下线等影响，都会导致客户服务的短时间不可用。

上述影响是比拟常见，也比拟容易构想到的问题，但其实还有数据提早（工夫）问题，因为智能选路零碎构建的网络拓扑不可能是齐全实时的，总是有肯定提早存在的。如果 T-1 时刻的网络较好，但 T 时刻网络异样时，智能选路零碎用 T-1 时刻的网络拓扑计算的选路后果必定是有问题的，而网络异样又是难以预测的，因而减少冗余的门路就显得极为重要了。

所以原则上，起码要同时提供 2 条绝对较短的门路。这在学术上个别称之为 k-shortest 门路问题。间接套用学术界的算法会有一些比拟蹩脚的问题：1）只有 k 是大于 1 的值，求解耗时个别呈指数级上涨，会导致计算太慢（即故障切换时也慢）；2）学术届个别都是思考严格意义的第 2 短、第 3 短门路等，不思考门路重叠的问题。在理论公网传输的场景中，一旦挖断的光纤是主备门路的公共段，还是会导致客户服务的短时不可用。因而须要工程化的高效的、多样的备门路能被筛选进去。

3. 分层聚合

随着客户源站接入的越来越多，智能选路零碎的算力越来越顾此失彼。尽管能够通过零碎横向扩容，通过集群化的形式解决规模问题，但扩容总是面临估算、周期等因素的影响，不太可能欲速不达。因而还是要继续优化算法

直觉的高速网络通道的抉择过程，其实和菜鸟的快递运输过程、高德的门路导航过程是高度相似的。所以，当人来抉择北京到杭州的最快、最短门路时，个别都是找 1 个最近的高速路口，先上高速，而后再找 1 个间隔杭州近的高速路口下。简直不会思考省道、县道等若干段门路的组合，教训上也是高速更快的。

这种可解释性十分好的直觉选路策略给了 2 个启发：1）应尽量抉择高速公路，在公网上绝对应的就是专线及能被双边减速的门路。单边减速的门路应该尽可能短，哪怕这部分门路有一些背道而驰也没关系，长链路上“高速公路”上的减速成果是齐全能超过这部分损失的；2）没有必要为北京东城区、海淀区的不同客户，调配不同的到杭州门路。换句话说：新接入的北京电信的客户源站，其实上能够间接复用其余北京电信客户的智能选路后果，没有必要反复算（个别算进去的也是一样的）。

03 多维束缚的智能选路

上述内容次要介绍了“有限资源场景”下的智能选路。随着客户数量的增多、客户自有带宽量的上涨，“有限资源”的简化场景就不太实用了。因而须要思考多种不同维度的限度，保障智能选路零碎在无限范畴内，抉择适合的门路。即“无限资源场景”的智能选路。

1. 节点束缚

在前文背景中也介绍了，节点带宽能力是在洽购环节就决定了，用量超过下限必然会带来不可用、谬误、提早等各种异样问题。因而须要在智能选路时思考节点容量（包含但不限于带宽、CPU 等）。

这种带限度的门路布局问题，要么应用贪婪策略：优先计算一部分客户的最短门路，扣减相干资源占用后，持续下一部分客户的门路计算；要么应用运筹优化：设定最小化指标（例如：最小化全局提早），并退出多种约束条件后，导入求解器求解。贪婪策略实用于有明确优先级划分的场景，设计上就是低优先级避让高优先级，可解释性好；运筹优化实用于无优先级场景。

所以须要依据不同业务场景，抉择不同布局算法，甚至可能是组合应用。在计算规模十分大，无奈实时（分钟级）计算时，还须要邻域搜寻等部分更新算法。

2. 网络束缚

公网中绝大部分流量都是 TCP 的，因而公网的中间设备往往对 TCP 有很多 QOS 的虐待。相比拟 UDP 的相干优化就很少，会被限速，甚至在高水位运行的网络中，还存在升高 UDP 转发优先级给 TCP 让路的行为。

因而节点间传输应用 QUIC 协定就须要“小心翼翼”，既要关注历史 UDP 峰值，察看在大流量时的提早指标是否有显著“非预期”的下滑，选路时也要多多应用这种大流量“无损”的 UDP 管道，从而保障对客户服务的稳固。

3. 稳定束缚

通过实时的网络探测来量化节点间网络间隔是常见的，与此同时，网络探测值也是带有噪声的。无论是来自节点内不同机器的负载轻微差别，还是公网中必然存在的轻微稳定，都有可能间接导致智能选路后果的变动。从纯正算法、图论的角度看是没问题的，因为每一轮算法的输入后果都是独立于上一轮的，即齐全基于动态快照式的选路。

网络流量齐全参考快照式选路后果来传输，是 100% 无损的么？并不是的。对于绝大部分有连贯的 TCP 来说，新的门路就意味着新的 TCP 连贯建设，必然有握手的开销。如果下层跑的是 HTTPS 流量，还有 SSL 握手等更大的开销。一方面这些握手有带宽老本的上涨，另一方面非 0-rrt 管道就意味着“慢”。所以，为了 3-5ms 的实践间隔缩短，付出 30-50ms 的额定握手开销是得失相当的。

所以，连接池、TFO 等 0-rtt 网络传输技术，反向要求智能选路后果是稳固的（即依赖上一轮选路后果的）。简略了解就是只有在网络显著劣化、节点故障下线时，才疾速切换。即非必要，不切换。

当然，在必须要切换的场景中，也是须要思考并设计正当的阻尼的。例如在单节点故障下线场景，对于流量切出的要求是：下一轮计算必须 100% 实现切出；而对于流量切入（次短 or 备门路）的要求则不是那么严格，即流量能够摊派到次短、次次短等多条门路上。这次要是思考次短门路全量承接，会导致刹时新建连贯洪峰，极容易打满 TCP 半连贯队列，造成 syn 包重传等减速性能的劣化。

上述稳定限度，还仅仅只是思考了动静申请（所有申请都达到源站）的减速过程。思考动态申请（节点缓存有概率能命中，不须要所有申请达到源站）的减速过程，对门路稳定的容忍度更低。因为新门路上一开始的命中率是 0%，而老门路上是 XX%。所以门路切换最好产生在缓存快要过期的时刻，这对海量缓存的实时统计，智能选路的精准切换提出了更高要求。

4. 手动束缚

无论是开发的晚期阶段，须要手动调试零碎的能力（或工具），还是在开发后的交付阶段，须要提供故障逃逸的人为染指伎俩。因为须要在齐全自动化智能选路零碎中，在一些要害节点或环节，退出人为操控是十分必要的, 就像世界上自动化水平极高的波音客机的主动驾驶，依然保留了手动驾驶模式，以避免在极其顽劣状况、零碎设计中非预期状况下，由人判断，由人决策。

综上，智能选路零碎是从一个有向图的最短门路算法集，逐渐倒退并欠缺成一个能为海量客户实时构建多维束缚的低提早、高可用网络的算法平台。