译|A scalable, commodity data center network architecture(二)

本文涉及的产品
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: 译|A scalable, commodity data center network architecture(二)

3. 架构

在本节中,我们描述了一种将商用交换机互连成胖树拓扑的架构。我们首先说明需要对路由表结构进行轻微修改的原因。然后我们描述如何为集群中的主机分配 IP 地址。接下来,我们引入两级路由查找的概念,以协助完成跨胖树多路径路由。然后介绍在每个交换机中填充转发表的算法。我们还描述了流分类和流调度技术作为多路径路由的替代方法。最后,我们介绍了一个简单的容错方案,并描述了该方案的热量和功耗特征。

3.1 动机

为了实现最大化网络的双工带宽,需要将任何给定 pod 的输出流量尽可能均匀地分布在核心交换机之间。路由协议如 OSPF2 通常以跳数作为“最短路径”的度量标准,在 k 元胖树拓扑结构(参见 2.2 节)中,不同 pod 的任意两台主机之间有 (k/2)2 条这样的最短路径,但只能选择了一条。因此,交换机将发送到给定子网的流量集中到单个端口,即使存在其他具有相同成本的选择。此外,由于 OSPF 消息到达时间交错,可能只选择少数核心交换机,甚至只选择一个作为 pod 之间的中间链路。这将导致这些点严重拥塞,并且无法利用胖树中的路径冗余

OSPF-ECMP 等扩展,除了不可用在候选的交换机类别之外,还会导致所需前缀数量爆炸性增长。一个较低层的 pod 交换机中需要为其他每个子网存储 (k/2) 个前缀;总计 k∗(k/2)2 个前缀。

因此,我们需要一种简单、细粒度的方法,利用拓扑结构在 pod 之间进行流量扩散。交换机必须能够识别需要均匀分布的流量类别,并给予特殊处理。为此,我们提出使用两级路由表,根据目标 IP 地址的低位字节来传播输出流量(参见第 3.3 节)。

3.2 编址

我们分配私有的 10.0.0.0/8 段内所有网络 IP 地址。我们遵循熟悉的四点形式,满足以下条件:pod 交换机的地址形式为 10.pod.switch.1,其中 pod 表示 pod 编号( [0,k-1] ),switch 表示该交换机在 pod 中的位置([0,k−1],从左到右,从下到上)。我们给出核心交换机的地址形式为 10.k.j.i,其中 j 和 i 表示交换机在 (k/2)2 核心交换机网格中的坐标(每个都包含在 [1,(k/2)] 内,从左上角开始)。

主机的地址位于所连接的 pod 交换机之后;主机的地址格式为:10.pod.switch.ID,其中ID 是主机在该子网中的位置([2,k/2+1],从左到右)。因此,每个下层交换机负责 k/2 台主机的 /24 子网(k < 256)。图 3 显示了这种寻址方案的示例,对应于 k = 4 的胖树。尽管这种使用方式相对浪费可用地址空间,但它简化了路由表的构建,如下所示。而且,这种方案可以伸缩到 420 万台主机。

3.3 两级路由表

为了提供第 3.1 节提出的均匀分布机制,我们修改路由表以允许两级前缀查找。主路由表中的每个条目都可能有一个额外的指针,指向一个由(后缀,端口)条目组成的小型二级表。如果一级前缀不包含任何二级后缀,则终止,并且二级表可以被多个一级前缀指向。主表中的项是左旋的(即,/m 前缀掩码为 1m032−m),而二级表中的项是右旋的(即, /m 后缀掩码为 032−m1m)。如果最长匹配前缀搜索得到非终止前缀,则在二级表中找到最长匹配后缀并使用。

两级结构会稍微增加路由表查找延迟,但硬件中前缀搜索的并行性应该只会带来很小的损耗(见下文)。因为这些表都非常小。如下图所示,任何 pod 交换机的路由表都不会超过 k/2 个前缀和 k/2 个后缀。

3.4 两级查找实现

我们现在描述如何使用内容可寻址存储器(Content-Addressable Memory, CAM) 在硬件中实现两级查找。CAM 用于搜索密集型应用,在查找位模式的匹配时,比算法实现更快。CAM 可以在单个时钟周期内并行搜索所有条目。查找引擎使用一种特殊的 CAM,称为三元 CAM (Ternary CAM, TCAM)。除了匹配 0 和 1 之外,TCAM 还可以在特定位置存储 —don’t care 位,使得它适合存储变长前缀,例如路由表中的前缀。缺点是,CAM 的存储密度很低,非常耗电,而且每比特的成本很高。然而,在我们的架构中,路由表可以实现在一个相对较小的 TCAM 中(k 个条目,每个 32 位宽)。

图 5 显示了我们提出的两级查找引擎的实现。TCAM 存储地址前缀和后缀,又索引一个 RAM,该 RAM 存储下一跳 IP 地址和输出端口。我们在数值较小的地址中存储左旋(前缀)条目,在较大的地址中存储右旋(后缀)条目。我们对 CAM 的输出进行编码,以便输出具有数值最小匹配地址的条目。这满足了特定的二级查找应用的语义:当数据包的目标 IP 地址同时匹配一个左旋项和一个右旋项时,则选择左旋项。例如,使用图 5 中的路由表,一个目标 IP 地址为 10.2.0.3 的数据包与左旋条目 10.2.0.X 和右旋条目 X.X.X.3 匹配。数据包正确地转发到端口 0。而目标地址为 10.3.1.2 的数据包只匹配右旋 X.X.X.2,并在端口 2 上转发。

3.5 路由算法

胖树的前两层交换机充当过滤流量扩散器;任何给定 pod 中的下层和上层交换机都具有该pod 中子网的终止前缀。因此,如果一个主机将一个数据包发送到另一个同一 pod 但不同子网的主机,那么该 pod 中的所有上层交换机都具有一个指向目标子网交换机的终止前缀。

对于所有其他输出的 pod 间流量,pod 交换机有一个默认 /0 前缀,带有一个与主机 ID(目标 IP 地址的最低有效字节)匹配的二级表。我们利用主机 ID 作为确定性熵的来源;它们将使流量均匀地上行分布到核心交换机的出口链路。这也将导致到同一主机的后续数据包遵循相同的路径,从而避免数据包重排。

在核心交换机中,我们为所有网络 ID 分配终止第一级前缀,每个前缀指向包含该网络的适当 pod。一旦数据包到达核心交换机,就只有一条链路到它的目标 pod,并且该交换机将包含该数据包的 pod 的终止 /16 前缀(10.pod.0.0/16, port)。一旦一个数据包到达它的目标 pod,接收的上层 pod 交换机也将包括一个(10.pod.switch.0/24,port)前缀,以将该数据包定向到其目标子网交换机,在那里它最终被交换到其目标主机。因此,流量扩散只发生在数据包传输的前半段。

设计分布式协议可以在每个交换机中增量地建立所需的转发状态。然而,为简单起见,假设一个完全了解集群互连拓扑的中央实体。这个中央路由控制负责静态地生成所有路由表,并在网络设置阶段将这些表加载到交换机中。动态路由协议还负责检测单个交换机的故障并执行路径故障转移(见第 3.8 节)。下面,我们总结了在 pod 和核心交换机上生成转发表的步骤。

Pod 交换机

在每个 pod 交换机中,我们为包含同一 pod 中的子网分配终止前缀。对于 pod 间流量,添加一个 /0 前缀和一个与主机 ID 匹配的二级表。算法 1 展示了为上层 pod 交换机生成路由表的伪代码。输出端口模数移位的原因是避免来自同一个主机、不同底层交换机的流量流向同一个上层交换机。

对于下层 pod 交换机,我们简单地省略了 /24 子网前缀步骤(第 3 行),因为该子网自己的流量被交换,并且pod 间和 pod 内流量应该在上层交换机之间均匀分割。

核心交换机

由于每个核心交换机连接到每个 pod(端口 i 连接到 pod i),因此核心交换机只包含指向其目标 pod 的终止 /16 前缀,如算法 2 所示。该算法生成的表大小与 k 成线性关系。网络中没有交换机包含超过 k 个一级前缀或 k/2 个二级后缀的表。

路由示例

为了说明使用两级表的网络操作,我们给出一个数据包从源 10.0.1.2 到目标 10.2.0.3 的路由决策示例,如图 3 所示。首先,源主机的网关交换机(10.0.1.1)只有 /0 的第一级前缀匹配该数据包,因此会根据该前缀的二级表中的主机 ID 字节转发该数据包。在该表中,在该表中,数据包与 0.0.0.3/8 后缀匹配,该后缀指向端口 2 和交换机 10.0.2.1。交换机 10.0.2.1 也遵循相同的步骤,并转发到端口 3,连接到核心交换机 10.4.1.1。核心交换机将数据包与终止 10.2.0.0/16 前缀匹配,该前缀指向目标 pod 2 的端口 2 和交换机 10.2.2.1。这个交换机与目标子网属于同一个 pod,因此有一个终止前缀 10.2.0.0/24,该前缀指向负责该子网的交换机 10.2.0.1 的端口 0。从那里,标准切换技术将数据包传递到目标主机 10.2.0.3。

请注意,对于从 10.0.1.3 到另一个主机 10.2.0.2 的同时通信,传统的单路径 IP 路由将遵循与上述流程相同的路径,因为两个目标地都属于同一个子网。不幸的是,这将消除胖树拓扑的所有扇出优势。相反,我们的两级表查找允许交换机 10.0.1.1 基于两级表中的右旋匹配将第二条流转发到 10.0.3.1。

3.6 流分类

除了上述两级路由技术,我们还考虑了两种可选的动态路由技术,因为它们目前在一些商用路由器中可用[10,3]。我们的目标是量化这些技术的潜在好处,但承认它们会产生每个数据包的额外开销。重要的是,这些方案中维护的任何状态都是软性的,如果状态丢失,单个交换机可以回退到两级路由。

作为流量扩散到核心交换机的另一种方法,我们在 pod 交换机中执行流分类,并使用动态端口重分配,以克服可避免的局部拥塞情况(例如,当两条流竞争同一个输出端口时,即使另一个到目标具有相同成本的端口未使用)。我们将 定义为一系列的数据包,这些数据包具有相同头部字段子集(通常是源 IP 地址和目标 IP 地址、目标传输端口)。特别是 pod 交换机:

  1. 识别同一条流的后续数据包,并将它们转发到相同的输出端口。
  2. 周期性地重新分配一个最小数量的流输出端口,以最小化不同端口聚合流容量的差异。

第 1 步是针对数据包重排序的措施,第 2 步是在流大小动态变化的情况下,保证上行端口的流公平分布。第 4.2 节更详细地描述了流分类器的实现和流分布启发式方法。

3.7 流调度

已有研究表明,网络流量的传输时间和突发长度分布呈长尾分布,其特征是很少长生命周期的大数据流(占大部分带宽),而有许多短生命周期的小数据流。本文认为路由大型流在确定网络可实现的双工带宽方面,起着至关重要的作用,因此需要进行特殊处理。在这种流管理的替代方法中,我们调度大数据流以尽量减少彼此的重叠。中央调度器根据网络中所有活动的大数据流的全局信息做出此选择。在这个初始设计中,我们仅考虑每台主机一次只有一条大数据流的情况。

3.7.1 边缘交换机

与之前一样,边缘交换机最初会在本地将新流分配给负载最少的端口。然而,边缘交换机还会检测任何规模增长超过预定义阈值的输出流,并定期向指定所有活动大数据流的源和目标的中央调度器发送通知。这表示边缘交换机将该流放置非竞争路径的请求。

请注意,与第 3.6 节不同的是,该方案不允许边缘交换机独立地重新分配流的端口,无论其大小。中央调度器是唯一有权下令重新分配的实体。

3.7.2 中央调度器

中央调度器(可能是复制的)跟踪所有活动的大数据流,并试图为它们分配不冲突的路径。调度器维护网络中所有链路的布尔状态,表示它们是否可用来承载大数据流。

对于 pod 间流量,回想一下,网络中任意一对主机之间都有 (k/2)2 条可能的路径,每条路径对应一台核心交换机。当调度器收到新流的通知时,它线性搜索核心交换机,以找到对应路径组件不包含预留链路的交换机。一旦找到这样的路径,调度器将这些连接标记为保留,并通知源 pod 相关的下层和上层交换机及流选择的路径相对应的正确输出端口。对pod 间的大数据流执行类似的搜索;这次是通过上层 pod 交换机找到一条无竞争路径。调度器垃圾收集最后更新时间超过给定时间的流,清除它们的预留标记。请注意,边缘交换机不会阻塞并等待调度器执行该计算,但一开始会像处理其他流一样处理大数据流。

3.8 容错

任意一对主机之间可用路径的冗余使得胖树拓扑具有容错能力。我们提出了一种简单的故障广播协议,该协议允许交换机在下游一两跳处绕过链路或交换机故障。

在该方案中,网络中的每台交换机都与其每个邻居维护一个双向转发检测会话(BFD),以确定链路或邻居交换机何时发生故障。从容错的角度来看,可以承受两类故障:(a) 在 pod 间的下层交换机和上层交换机之间,(b) 在核心交换机和上层交换机之间。显然,较低层的交换机故障将导致直接连接的主机断开连接;叶子上的冗余交换机元件是容忍这种故障的唯一方法。我们在这里描述链路故障,因为交换机故障会触发相同的 BFD 警报,并引发相同的响应。

3.8.1 下层到上层交换机

当下层和上层交换机之间发生链路故障时,会影响三类流量:

  1. 从下层交换机发出的 pod 间和内的输出流量。在这种情况下,本地流分类器将该连接的“成本”设置为无穷大,并且不为其分配任何新流,并选择另一个可用的上层交换机。
  2. 使用上层交换机作为中介的 pod 内流量。作为响应,该交换机广播一个标签,通知同一 pod 中的所有其他底层交换机链路故障。在分配新流时,这些交换机将检查预期的输出端口是否属于这些标记,并尽可能规避。
  3. 进入上层交换机的 pod 间流量。连接到上层交换机的核心交换机将其作为访问该 pod的唯一入口,因此上层交换机向其所有核心交换机广播此标记,表明其无法将流量传送到下层交换机的子网。这些核心交换机依次将此标签镜像到它们连接到其他 pod 的所有上层交换机。最后,上层交换机在将新数据流分配给该子网时,规避单个受影响的核心交换机。

3.8.2 上层到核心交换机

当上层交换机与核心交换机之间发生链路故障时,会影响两类流量:

  1. pod 间的输出流量,本地路由表将受影响的链路标记为不可用,并在本地选择另一台核心交换机。
  2. pod 间的输入流量。在这种情况下,核心交换机向它直接连接的所有上层交换机广播一个标记,表示它无法将流量传送到整个 pod。和之前一样,上层交换机在分配流向pod 的数据流时,会避免使用核心交换机。

自然地,当故障链路和交换机恢复并重新建立 BFD 会话时,上述步骤将被反转以抵消其效果。此外,调整第 3.7 节的方案适应链路和交换机故障相对简单。调度器将任何被报告为 down 的链路标记为繁忙或不可用,从而取消任何包含它的路径的候选资格,最终大型流绕过故障路由。

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
目录
相关文章
|
人工智能 数据可视化 决策智能
【CAMEL】Communicative Agents for “Mind”Exploration of Large Scale Language Model Society
【CAMEL】Communicative Agents for “Mind”Exploration of Large Scale Language Model Society
347 0
|
缓存 负载均衡 网络协议
译|A scalable, commodity data center network architecture(三)
译|A scalable, commodity data center network architecture(三)
109 0
|
存储 分布式计算 网络协议
译|A scalable, commodity data center network architecture(一)
译|A scalable, commodity data center network architecture
136 0
《Data infrastructure architecture for a medium size organization tips for collecting, storing and analysis》电子版地址
Data infrastructure architecture for a medium size organization: tips for collecting, storing and analysis
88 0
《Data infrastructure architecture for a medium size organization tips for collecting, storing and analysis》电子版地址
|
弹性计算
Structuring the Backend Service Architecture of a Mobile Card Game
2014 saw the rise of intense action mobile card games, and 2015 ushered in the age of real-time battles.
1445 0
Structuring the Backend Service Architecture of a Mobile Card Game
|
Java 虚拟化 C++
Stack based vs Register based Virtual Machine Architecture
进程虚拟机简介 一个虚拟机是对原生操作系统的一个高层次的抽象,目的是为了模拟物理机器,本文所谈论的是基于进程的虚拟机,而不是基于系统的虚拟机,基于系统的虚拟机可以用来在同一个平台下去运行多个不同的硬件架构的操作系统,常见的有kvm,xen,vmware等,而基于进程的虚拟机常见的有JVM,PVM(python虚拟机)等,java和python的解释器将java和python的代码编译成JVM和P
3681 0
|
SQL 分布式计算 分布式数据库
Big Data Application Case Study – Technical Architecture of a Big Data Platform
How should we design the architecture of a big data platform? Are there any good use cases for this architecture?
2250 0