容错状态交换机内应用的设计与实现

223摘要RedPlane：支持容错的有状态交换机内应用作者：Daehyeok Kim★ <$，Jacob Nelson<$，Dan R. K. Ports†，Vyas Sekar★，Srinivasan Seshan★★卡内基梅隆大学，微软这种范例;例如， 运行负载平衡器交换机故障许多最近的努力已经证明了运行数据中心功能（例如，NAT、负载均衡器、监控）。然而，一个关键的缺失仍然存在：容错。这一点尤其重要，因为网络不再是无状态的，纯粹的端点恢复是不够的。在本文中，我们设计并实现了RedPlane，一个容错状态存储的状态交换机应用程序。这为交换机内应用程序提供了对其状态的一致访问，即使它们运行的交换机出现故障或流量被重新路由到备用交换机。我们解决的关键挑战，在设计一个实用的，可证明是正确的复制协议，并实现它在交换机数据平面。我们的评估表明，RedPlane引起的开销可以忽略不计，并使端到端的应用程序从交换机故障中快速恢复CCS概念• 网络→可编程网络;网内处理;·硬件→新兴技术;·计算机系统组织→可用性。关键词可编程开关，可编程网络，容错，状态复制ACM参考格式：放大图片作者：David R.K. Ports，Vyas Sekar，Srinivasan Seshan. 2021年RedPlane：启用容错状态交换机内应用程序。在ACMSIGCOMM 2021会议（SIGCOMMDylan Evans，USA. ACM，纽约州纽约市，美国，22页。https://doi.org/10的网站上下载。1145/3452296.34729051介绍今天的数据中心交换机不再是简单的无状态数据包转发器。它们实现了复杂的网络功能，如NAT、防火墙和负载均衡器[6，39，55]，并加速了分布式应用程序[45，47，67，73，78]。云服务提供商甚至已经开始在生产网络中部署它们[7]。交换机中的这种有状态处理导致了一个新的挑战：容错。经典的网络设计遵循端到端原则[66]，仅在终端主机上保持临界状态这使得可靠性的命运共享方法成为可能[27];当交换机是无状态的时，从它们的故障中恢复只需要找到一个新的通信路径。有状态的交换机内应用程序[7]挑战本作品采用知识共享署名国际4.0许可协议进行许可SIGCOMM©2021版权归所有者/作者所有。ACM ISBN978-1-4503-8383-7/21/08。https://doi.org/10.1145/3452296.3472905可能会导致其转发状态丢失，从而中断数千个活动连接。 虽然数据中心网络设计有冗余网络路径[34，65，71]以在路由层提供容错，但没有在故障后恢复交换机内状态的能力。因此，我们需要重新考虑交换机内处理的容错性-我们在本文中的目标是确保，故障和重新路由后，相同的应用程序状态变得可用在更换开关，而不会降低性能，同时保持透明的终端主机。由于规模和资源的限制，使交换机状态具有容错性是一个独特的挑战。 像检查点和主动复制这样的技术，已经应用于软件中间盒[63，70]，是为基于服务器的系统设计的。这些技术依赖于获得一致的状态快照并缓冲输出，直到状态更新被持久地记录到其他服务器。然而，交换机的高数据包处理速度（数十亿数据包/秒[13，14，19]）及其有限的计算和存储能力使得将这些技术转化为交换机上下文是不可行的。在本文中，我们介绍了RedPlane，1一个容错状态存储在开关应用程序。RedPlane为开发人员提供API，以（重新）编写他们的有状态P4程序并使其具有容错性。这允许应用程序保持对其状态的一致访问，即使它所运行的交换机发生故障或流量被重新路由到另一个本地交换机。RedPlane通过以数据平面为中心的复制机制来实现这一点，该机制将状态更新连续复制到使用商品服务器上的DRAM实现的外部状态存储请注意，完全在数据平面通道中运行是跟上交换机全速处理速度的关键。在实践中实现这一高层次的想法需要几个挑战。首先，具有线性化能力的严格正确性和操作的精确一次语义的传统概念需要可靠的通信和输出缓冲。然而，由于其有限的能力，这在交换机数据平面上是其次，在交换机数据平面需要处理的业务量上，天真地要求与基于服务器的状态存储进行每分组协调会带来严重的性能开销。最后，交换机发生故障时的路由决策可能是不可预测的。因此，我们必须能够透明地迁移两个交换机之间的相关状态，而不管路由决策。我们解决这些挑战与以下关键思想：基于在交换机应用程序的要求，我们定义了两个实用的正确性模型。首先，基于我们观察到的网络应用程序已经对数据包丢失具有弹性，我们通过明确采用1名称表示复制的数据平面。·224SIGCOMM'21，2021年8月23日至27日，虚拟活动，美国Daehyeok Kim，Jacob Nelson，Dan R. K. Ports，VyasSekar，Srinivasan Seshan线性化的标准定义[36]，它允许在提供强一致性的同时不完成的操作。其次，对于以写为中心的应用程序（例如，监控使用草图[28]），可以容忍近似的结果，我们提出了一个宽松的一致性模式，允许一些状态在失败后丢失，但以较低的开销限制不一致性。而不是缓冲数据包使用有限的交换机资源，我们使用网络本身和状态存储器的内存作为临时存储器的捎带数据包内容的协调消息为了实现可靠的状态复制，我们构建了一个轻量级的排序和重传协议，该协议确保以正确的顺序处理状态更新，而不需要复杂的协议（例如，TCP）。为了避免由于与状态存储频繁协调而产生的开销，我们提出了一种基于租赁的状态所有权协议[33，49，57]，以提供正确性，而无需协调每个状态访问并根据需要在不同交换机之间迁移所有权。我们设计了实现我们的一致性模式的RedPlane协议，证明了它的正确性，并使用TLA+模型检查器确认了这一点[18]。 我们在P4 [11]和C++/Python中实现了RedPlane的原型，并证明了不同类型的应用程序可以使用它进行容错。 我们评估它与各种应用程序，在我们的测试床组成的两个Tofino基于可编程开关，四个常规开关，和10个服务器。我们的评估结果表明，在无故障操作下，RedPlane对于NAT等以读取为中心的应用程序具有可忽略的每个数据包延迟开销，即使在最坏的情况下，开销也小于8微秒当交换机发生故障时，RedPlane可以通过访问正确的状态在一秒钟2背景和动机网内处理近年来蓬勃发展，作为数据中心运营商对复杂网络功能的需求与可编程交换机平台的商业可用性的自然融合[8，13，14]。可编程开关是用于经典的中间盒功能[39，55]，监控[6，35]，DDoS防御系统[76，77]和加速其他网络系统[38，45-47，52，67，73，78]。这些应用程序是有状态的;即，交换机上的状态决定如何处理分组。在本文中，我们主要关注硬状态应用程序，其中状态丢失会中断网络或应用程序功能。2交换机内NAT就是一个例子，其中密钥状态是地址转换表。丢失此状态将使现有连接无法转发数据包网络模型我们考虑一种部署模型，其中可编程交换机安装到网络结构中，使得要由交换机内应用程序处理的所有流量穿过其中一个可编程交换机。这可以通过几种不同的方式来实现，具体取决于网络架构。在典型的数据中心架构中（图1），这可以通过使用2其他应用程序仅在交换机中维护软状态，并提供自己的故障恢复机制。 这些不是我们工作的重点，尽管RedPlane可能有助于简化它们的设计或提高恢复性能。核心交换机T：架顶式交换机外部平台内部平台流ID(IP，端口）内部(IP、端口）（10.0.0.1，（192.168.10.1，4321）（1234）图1：交换机故障对交换机内NAT的影响所有核心交换机或所有聚合层交换机上的交换机3例如，所有进入或离开集群的流量都将经过其中一个交换机。或者，运营商可以部署一组可编程交换机作为专用的“NF加速器”，明确地通过它们路由流量;这种方法类似于今天部署软件负载均衡器的方式[30，60]。状态分割。 我们假设应用程序状态可以使用从数据包报头中导出的某个键进行分区，并且每个数据包的处理仅使用来自相关分区的状态。在许多情况下，例如对于NAT示例，键将是IP 5元组，因此，我们可互换地使用“分区”和“流”。然而，其他应用可以使用不同的划分，例如， 根据VLAN ID进行分区，以检测特定租户的重量级流量。我们还假设网络被配置为提供尽力而为的亲和性，使得来自同一分区的分组通常到达同一交换机。标准的第3层路由协议（如ECMP）在配置为使用分区键作为哈希键时提供了此属性。可编程开关的入门当今使用的可编程开关体系结构，例如，英特尔Tofino [14]，使用有限数量的片上内存（例如， SRAM和TCAM）来提供各种有状态对象抽象，包括表、寄存器、仪表和计数器。应用程序可以使用这些来保持多个数据包的状态，例如上面NAT示例中的地址转换表。在入口和出口匹配动作流水线中，对象在每个阶段中被分配，并由数据包通过ALU访问。这些对象也可由交换机控制平面通过ASIC到CPU PCIe通道访问，该通道与ASIC的每端口带宽（Mbps（100 Gbps））相比具有有限的 此外，ASIC还提供其他内置功能，如数据包复制、再循环和镜像，以实现更高级的数据包处理。42.1交换机故障的影响交换机可能会发生故障，要么是交换机完全故障（故障停止模型），要么是个别链路失去连接。生产数据中心的测量研究表明，此类交换机故障非常普遍。例如，在Microsoft3原则上，RedPlane可以部署在架顶式（ToR）交换机上，但它可能不太有用。如果每个机架都有一个ToR交换机，并且它发生故障，则与该机架中的服务器的连接将丢失。RedPlane可以将交换机状态恢复到不同的机架上，但这取决于可能没有用处的应用程序但是，如果每个机架有两个ToR交换机，RedPlane将非常有用。4虽然我们在工作中使用基于Tofino的可编程开关，但我们相信，设计可以在其他可编程交换机ASIC上实现，因为RedPlane的交换机数据平面中利用的硬件能力（例如，分组镜像）是大多数交换机ASIC支持的一般特征。·互联网互联网CSWCSWS连接断开NAT1NAT2故障NAT1NAT2T T T TT T T T服务器机架服务器机架··225RedPlane：启用容错状态交换机内应用SIGCOMM状态访问应用交换机故障的影响NAT连接中断失败后的连接[21]，增加了服务延迟。以应用程序特定方式路由请求的其他应用程序以阅读为中心状态防火墙连接中断[55]第五十五话：SYN flood防御[77]丢弃有效数据包（例如，对于数据库[78]或键值存储[47]）也属于这一类别，因为它们需要在每次写入时更新状态（但不写中心混合读写[53]第72话不准确的检测EPC中的SGW[69]活动会话中断网络内定序器[46]不正确的定序每对象路由[47，78]选择错误的服务器网络内键值存储丢失键值对读）请求。2.2现有方法和局限性我们现在研究经典的容错机制[32，58，74]和为网络中间盒定制的机制[63，70]。在表1：有状态交换机内应用程序和IM的示例交换机故障。在Facebook的数据中心，26%的事件与交换机故障有关[54]。交换机故障可以通过两种方式影响有状态应用程序如果交换机完全失败，则它保存的所有应用程序状态都将丢失。除此之外，链路故障或不同交换机的故障可能会影响网络中的许多路径[51]，导致流量重新路由[22，34，43]。以前经过一台交换机的流量可能会路由到另一台交换机，此时相应的状态不可用。如果没有此状态，应用程序处理可能会失败。例如，如图所示。1、缺少正确的转换表条目，NAT无法为现有连接转发数据包，从而破坏开放的连接。事实上，这是一个严重的问题-云提供商基于软件的有状态负载均衡器实现了复杂的故障转移机制[30，60]。除了传统的NF（例如，NAT、负载均衡器、防火墙），但有几个交换机内应用程序（如表1所示）显示了复杂的状态访问模式。例如，许多被设计为实施QoS策略的应用（例如，速率限制）采用流算法（例如，草图），以捕捉流量的特征，如重量级人物[53，72]。交换机故障导致他们做出不准确的决策，因为统计数据丢失。这样的应用更新状态（例如，每个包上都有草图），所以我们称之为以写为中心。相比之下，许多传统的NF和DDoS防御系统（例如，SYN代理）[76，77]是以读为中心的。另一组应用程序具有混合读/写状态访问模式，通常比以写为中心的应用程序更新频率低得多该类别中的一个示例是蜂窝网络的分组核心中的NF（例如，用于LTE的演进分组核心（EPC））[17]。 诸如服务网关（SGW）之类的分组核心NF基于每个用户的状态（例如，转发状态），其在控制平面接收信令消息时被更新（例如，附设备 为了应对不断增加的信令业务量[4，10]，5最近已经努力通过将控制平面功能卸载到可编程数据平面来加速控制平面功能[5，9，61，69]。例如，在交换机上运行的SGW维护每个用户的隧道端点ID（TEID）以路由分组，并且该状态通过信令消息来更新并且通过用TEID封装的数据分组来读取。因此，当交换机发生故障时，由于SGW丢失状态，因此它无法为用户转发数据包，从而中断活动连接。受影响的用户需要重新建立5尽管增长，但预计信令业务速率仍远低于数据业务速率（例如， 5%的数据流量[56]）。在更高层次上，这些方法可以分为三类：(1) 检查点恢复，（2）回滚恢复，以及（3）状态复制。之前的所有工作都是针对基于服务器的实现。在下文中，我们将讨论为什么这些方法对交换机环境的自然适应无法确保故障期间的正确行为。检查点恢复。检查点周期性地接近快照应用状态（例如，NAT中的地址转换表）并将其提交给稳定存储器（例如， [63]）。当发生故障时，最新的快照被填充在备份节点上（即，在我们的上下文中的替代开关）。 图图2a示出了使用外部控制器经由交换机控制平面存储快照的交换机上的候选实现。 要实现一致的快照，必须暂停数据平面执行，并在快照期间缓冲数据包。现代交换机架构中有限的数据到控制平面带宽使得这不切实际。回滚恢复。 这种方法以前用于软件中间盒[70]，将每个数据包记录到稳定的存储器中，并在重建应用程序状态失败后在新设备上重放流量日志。一种自然的实现方式是将每个数据包发送到交换机控制平面，交换机控制平面将其记录到控制器（图1）。2b）。原则上，如果每个数据包都被同步记录并在失败后重放，则这种方法可以保证正确性。然而，数据业务速率（Tbps）和数据到控制平面带宽（Gbps）之间的不匹配将导致许多分组被丢弃，并且因此将是不正确的。交换机数据平面之间的状态复制 考虑使用链复制的状态机复制方法[74]，但应用于交换数据平面（图11）。2c）。数据包通过一系列交换机转发，每个交换机更新其状态，并将数据包转发到链中的下一个交换机。只有当数据包到达链的尾部时，它才会被转发到目的地。这完全是在数据平面上完成的，因此它可以高速运行这种方法只有在状态更新没有丢失的情况下才能实现正确性然而，状态更新是通过不可靠的信道传递的，并且由于交换机数据平面不能有效地支持可靠的传输协议（例如，TCP）更新可能会丢失或重新排序，从而违反正确性。此外，使用一台交换机复制另一台交换机的状态会导致数据平面（可访问的交换机存储器）的利用率低下，而数据平面是成本最高且最有限的资源。它还需要改变网络的路由策略，因为数据包需要根据数据包是否更新状态显式地路由到链中的特定交换机。外卖。从上面的讨论中，我们看到了两个关键的要点。首先，依赖于交换机控制平面的方法必须考虑控制和数据平面速度之间的不匹配。第二、226开发商P4压气机应用代码+ RedPlaneP4 API可靠状态存储交换机ASICRedPlane 复制状态议定书对记忆应用状态流水线级（RedPlane-enabledApp）SIGCOMM'21，2021年8月23日至27日，虚拟活动，美国Daehyeok Kim，Jacob Nelson，Dan R. K. Ports，VyasSekar，Srinivasan Seshan控制器控制器上游交换机数据包更新状态数据包读取状态数据平面蒂努应用状态S 流水线级应用状态管道阶段开关-1开关-2(a) 检查点恢复：交换机控制平面定期快照并向控制器提交状态。在此期间，必须缓冲所有数据包。开关-1开关-2(b) 回滚恢复：每个数据包被转发到控制平面并由控制器记录。Switch-1（头部）Switch-2（尾部）(c) 状态复制：使用链复制将状态复制数据包必须路由到正确的链节点。图2：突出显示了为什么调整现有容错方法对于硬件交换机失败虽然仅交换机数据平面的方法可以提供良好的性能，但是它们具有三个缺点：（a）引起显著的交换机资源开销;（b）由于交换机数据平面之间的不可靠通信信道而使得难以推理正确性;以及（c）它们可能另外地约束路由策略。3RedPlane概述我们的目标是设计一个容错解决方案，提供以下四个属性：正确性：交换机故障应该对应用程序透明：客户端不应该看到在没有故障的情况下不可能看到的状态。性能：在无故障操作下，每个数据包延迟的开销应该很低（比如几十）。低资源开销：它不应该过度消耗交换机路由策略的透明性：也就是说，我们必须允许数据包更新和/或读取状态，而不管数据包被路由到的交换机的位置。为此，我们提出了RedPlane，它提供了一个抽象的容错状态存储状态的开关应用程序。RedPlane提供了一种“一个大的容错开关”的错觉--其行为与运行在一个永远不会失败的开关上的相同应用程序没有区别。 为了实现这一点，RedPlane连续复制状态更新，可以在故障后恢复而不会丢失。RedPlane采用具有两个定义特征的状态复制方法：（1）交换机的状态复制机制完全在数据平面中实现，以及（2）状态存储通过外部状态存储来完成，外部状态存储是由传统服务器组成的可靠复制服务。属性（1）意味着状态复制不需要交换机的控制平面，避免了§2.2的检查点设置和回滚恢复方法的问题。属性（2）意味着复制的状态被存储在商用服务器DRAM中，与交换机数据平面存储器相比，商用服务器DRAM是相对低成本的存储介质。这避免了第2.2节中讨论的状态复制方法的高资源开销。虽然使用服务器内存作为外部存储的想法与最近关于TEA的它关注的问题是图3：RedPlane概述，突出显示交换机内应用程序的传输工作流扩展资源扩充以使交换机能够检索存储在服务器的存储器中的状态。此外，该设计只能利用直接连接到架顶式交换机的服务器。 因此，他们的设计不解决容错问题，也不提供多个交换机可以访问存储的情况下可证明的正确性。RedPlane提供了一组API（图1）。3）在P4 [11]中实现，这是一种在可编程交换机上指定数据平面程序的语言，允许开发人员轻松地将RedPlane与其有状态P4应用程序集成。一旦开发人员使用RedPlane API（重新）编写其应用程序，P4编译器就会生成加载到交换机的支持RedPlane的应用程序的二进制文件，该交换机会通过数据平面不断将更新复制到状态存储。范围和限制：在这项工作中，我们的重点是为具有可分区硬状态的有状态应用程序启用容错，其中状态丢失会中断网络或应用程序功能，如表1所示。仅具有不可分区状态的应用程序（例如，全局计数器）超出了本工作的范围。此外，我们假设应用程序中的全局状态（例如，NAT中的端口池）在状态存储服务器上被分片并由状态存储服务器管理。其他需要软状态的应用程序（例如，网络内缓存或ML加速器）不需要容错，但可以从RedPlane中受益。3.1挑战虽然通过数据平面将状态更新复制到外部状态存储似乎很有吸引力，但在实践中实现这一想法存在一些挑战：C-1.在数据平面中提供正确的复制，同时容忍不可靠的通信。传统的基于服务器的复制系统的目标是提供严格的正确性，不仅要确保线性化，而且要确保每个操作都能准确执行可以错过一些状态不正确控制平面定期数据平面状态快照恢复应用状态流水线级应用状态流水线级可以错过一些数据包不正确控制平面继续数据包日志重放数据管道阶段平面应用状态流水线级应用状态二进制····227（）下一页（）→（）RedPlane：启用容错状态交换机内应用SIGCOMM一次甚至在存在丢弃或重传消息的情况下[44，49，57]。为此，它们建立在可靠的通信信道上，如TCP。然而，交换机数据平面不能支持可靠的通信，也不能缓冲大量的流量。C-2 处理高流量。交换机数据平面以巨大的流量（每秒高达数十亿个数据包[13，19，23]）运行，而基于服务器的系统处理数百万个数据包。如果每个读取或更新状态的数据包都需要与基于服务器的状态存储进行交互，那么服务器的容量将很快被超过。它还将带来显著的性能开销。C-3对路由策略透明。交换机故障、恢复或网络路由改变可能导致最初在交换机S1处处理的业务流被路由到不同的交换机S2。然而，由于路由决策可能是不可预测的，我们不能对S2做出假设，也不能预先假设将采取哪些备份路由。也就是说，我们必须能够透明地将相关状态从S1迁移到S2，而不管S2的位置例如，当一个特定连接的数据包由另一个实例处理3.2关键思想为了应对这些挑战，我们基于四个关键理念：I-1. 开关状态的实际正确性（§4）。 我们定义了两个正确性模型的基础上的要求，在开关applica-tions。第一种是严格一致性模式，基于线性化[36]。因为我们观察到，网络应用程序已经被设计为容忍数据包丢失，我们显式地采用线性化的标准定义，它允许操作不完成，同时仍然为那些做了强一致性。其次，由于许多以写为中心的应用程序（例如，监控使用草图[28]）接受近似结果，我们提出了一个宽松的一致性模式，允许在失败后丢失一些状态，但限制不一致性。I-2. 捎带输出数据包（第5.1节）。而不是缓冲输出数据包使用有限的交换机资源，我们使用网络本身作为临时存储的捎带数据包内容的协调消息。I-3. 轻量级排序和重传（§5.2）。 为了应对交换机数据平面和状态存储之间的不可靠的通信信道与低资源开销，我们采用了协议消息的排序机制，并设计了一个轻量级的交换机侧重传机制，通过重新利用交换机ASIC的数据包镜像功能。I-4. 租赁型国有制（§5.3）。 为了减少交换机必须与状态存储协调的频率，特别是对于具有以读为中心和混合读/写工作负载的应用程序，我们采用了受先前工作启发的基于租赁的机制[33，49，57]。这允许我们避免与需要读取但不修改状态的数据包的状态存储协调同时，我们确保所有状态更新在其任何影响被外部化之前被持久地记录，从而保证线性化能力。 该机制还用作在交换机之间迁移状态以支持透明性的手段。总之，这些高层次的想法解决了上述挑战。第一，基于线性化的一致性模型再加上搭载和轻量级的排序和重传机制，允许可靠和正确地复制状态（C-1）。其次，宽松的一致性和基于租赁的国有制有助于应对高交通量（ C-2 ）。最后，基于租赁的国家所有权使RedPlane对路由策略透明（C-3）。4正确性模型RedPlane提供了两个级别的一致性，应用程序可以根据自己的需求进行选择。线性化模式提供了严格的保证，使系统与单个容错开关无法区分。 由于与状态存储频繁协调，这对于以写为中心的应用程序来说开销很高，因此RedPlane还提供了一种有界不一致模式，允许在交换机故障时丢失一些状态更新，但保证交换机状态的一致视图。4.1预赛默认情况下，RedPlane提供线性化能力[36]，这是并发系统的正确性条件。 我们将有状态的in-switch程序建模为状态机，其中输出和下一个状态完全由输入和当前状态决定：定义1（有状态交换机内程序）。 有状态程序由一个转换函数定义������，它接受一个输入数据包和当前状态，并产生零个、一个或多个输出数据包以及一个新状态。���为了简化下面的定义，我们假设每个输入包都只产生一个输出包，这是直接将它们扩展到零输出或多输出的情况。������这意味着程序的行为完全由输入数据包的序列决定，特别是它是确定性的，并且数据包被原子地处理。 虽然交换机架构是并行处理多个数据包的流水线设计[26]，但其编译器以使数据包处理显得原子的方式将状态分配给流水线阶段[24]。复制状态机语义的黄金标准是单系统线性化[36]。也就是说，所观察到的执行与程序的顺序执行相匹配，该顺序执行遵守非重叠操作的顺序。 为了适应交换机内程序的线性化，我们首先重新定义了数据包处理的历史：定义2（历史）。 历史是一系列有序的事件。这些事件可以是输入事件，其中数据包 在RedPlane交换机处被接收，或者输出事件，其中相应的输出数据包由RedPlane交换机输出。请注意，如果对事件的处理仍在进行中或由于故障，则可能存在没有相应输出事件 接下来我们将深入讨论这一点4.2可线性化模式定义3（有状态交换机内程序的线性化）。历史 是程序的可线性化执行 ，如果存在输入事件的重新排序，使得（1）存在于中的每个输出事件的值通过顺序地 在中的输入事件 上运行而给出，并且（2）如果在中 之前，则先入 。228请求或确认类型SIGCOMM'21，2021年8月23日至27日，虚拟活动，美国Daehyeok Kim，Jacob Nelson，Dan R. K. Ports，VyasSekar，Srinivasan Seshan在这里，执行顺序是明显的顺序可线性化本质上是一个安全属性，而不是活性属性：它指定了哪些输出值是可接受的，但并不保证所有操作都完成。有可能接收到一个分组，并且（1）更新交换机状态，但不产生输出，或者(2) 既不更新开关状态也不产生任何输出。 定义3反映了这一点：具有输入事件但没有输出事件的数据包仍然可以按顺序出现 。 如果它先于其他数据包的处理，那么它们会看到它的状态更新的效果。如果它出现在命令行的末尾，则对系统状态没有可见的影响虽然这些异常符合线性化的定义，但大多数复制系统旨在提供更强的属性：每个操作只执行一次，并将结果返回给客户端。 确保这一点需要几个协议级别的机制：通常，客户端重试没有收到响应的请求，副本保持状态以检测重复的请求并重新发送响应，而不执行两次[44，49，57]。正如我们所看到的（§5.2），这些技术在我们的环境中是不可行的因此，RedPlane采取了不同的方法：它明确允许这两种类型的异常。虽然这看起来令人惊讶，但它符合现代网络的语义 这两种情况分别对应于（1）RedPlane交换机与其目的地之间的数据包丢失，或（2）源与RedPlane交换机之间的数据包丢失。 网络应用程序必须已经容忍有损网络，因此它们对此类损失具有弹性。放宽正确性的定义可以实现易于处理的实现。由于不要求系统实现完全的可靠性，我们的协议可能会在故障转移期间丢弃数据包，或者在交换机和状态存储之间的消息丢失时丢弃数据包。在这些场景中，输入分组或其输出可能丢失。当然，出于性能原因，丢弃太多数据包是不可取的;这种丢失事件很少发生。4.3每流量线性化在大多数交换机内程序中，一些或所有状态与特定流相关联-由唯一密钥标识的流量子集，例如，IP 5元组、VLAN ID或特定于应用程序的对象ID。例如，NAT中的每个转换表条目基于IP5元组绑定到特定流。 对于许多应用程序，每个流状态是唯一需要一致或容错的状态-因为没有全局状态，或者因为全局状态可以容忍较弱的一致性，例如，不需要精确的业务统计计数器。RedPlane通常为每个流状态提供一致性（全局状态的一致性是可选的）：定义4（每流线性化）。如果对于每个流流，流流中的数据包的子历史流是可线性化的，则历史流是逐流可线性化的。只要程序仅使用每流状态，每流线性化能力就与全局线性化能力相同，因为线性化能力是局部的（即，可组合）属性[36]。在每个流级别上操作的好处是，这意味着不需要与不同流相关联的状态之间的同步正如我们在§5中所示L3/L4信息。的状态存储RedPlane标头ETHIPUDPSEQ类型流密钥Val1 …Valn输出分组根据邮件类型图4：RedPlane状态复制协议数据包格式。到交换机群集，使用ECMP进行负载平衡。因为这种负载平衡是在每个流的粒度上完成的，所以每个交换机负责执行流的子集的转换，并且不需要访问其他流的转换表。4.4有界不一致模式RedPlane然而，我们观察到，可编程开关中的许多以写为中心的应用程序在近似结果可接受的情况下运行，例如， 使用草图[28]或Bloom过滤器[25]进行监控。 对于这些应用程序，RedPlane提供了一个有界不一致模式，具有较低的开销.在这种模式下，RedPlane定期获取数据平面状态的快照，并异步复制它们这意味着在交换机故障时，最新的状态更新可能会丢失。但是，RedPlane确保系统在一段时间间隔内恢复到一致的状态。 RedPlane的一致性快照机制确保恢复后的状态反映系统的实际状态，这简化了对复杂数据结构正确性的推理。6在§5.4中，我们描述了如何解决在RedPlane中实现此模式的关键挑战5RedPlane设计现在，我们描述实现我们的线性化和有界不一致模式的RedPlane协议。 我们首先概述协议，并解释我们如何应对实际挑战。5.1基本设计如图3，RedPlane由（1）在商用服务器上构建的外部状态存储和（2）在交换机数据平面上运行的支持RedPlane的应用程序组成。在本节中，我们将描述组件如何通过状态复制协议协同工作为了清楚地说明，我们从简化的假设开始：交换机和状态存储之间没有分组丢失或重新排序，交换机在消息传输过程中不会失败，并且流的分组一次只路由到一个交换机我们在§5.2和§5.3中重新讨论这些假设。5.1.1外部状态存储：外部状态存储是内存中的键值存储系统。我们通过流将其划分为多个分片- 每个状态存储分片都可以使用传统机制进行复制，我们在这里不寻求创新，因为许多现有的键值存储满足我们的需求（例如，[16、48、59]）。具体来说，我们的原型是一个简单的内存存储服务器，用C++实现，使用链复制[74]，组大小为3。这允许RedPlane将程序的执行分布在多个交换机：每个交换机具有与某些流相关联的状态，并且可以处理那些流的分组。 这与许多应用程序在实践中的部署方式相匹配，例如，将部署NAT6尽管有界不一致模式可能影响某些近似数据结构的属性（例如，Bloom过滤器中没有假阴性），因为它限制了内部的不一致性 ，开发人员或网络运营商可以很容易地推断出潜在的不一致性。229142321RedPlane：启用容错状态交换机内应用SIGCOMM(a) 请求的无序传递会导致不一致。图5：RedPlane状态复制原型的基本工作流程pkt表示���������流的最小包���。5.1.2基本复制协议：支持RedPlane的应用程序通过交换如图所示格式的协议消息，将状态更新复制到状态存储中。四、 它使用标准UDP，(b)请求排序序列化复制请求。图6：使用排序序列化无序请求红色和蓝色的计数器值（cnt）分别表示交换机和状态存储的状态读取或更新状态（图中的步骤或）5）。一旦IP标头，以使用消息各自的IP地址将消息寻址到状态存储或交换机。RedPlane头由序列号、消息类型和流键组成。 根据消息类型，它还可以包括流状态和输出数据包。我们将很快讨论这些字段请注意，我们为每个RedPlane交换机分配了一个IP地址，并使用它在状态存储服务器和RedPlane交换机之间路由 这适用于一般的L3路由协议，包括ECMP和BGP。作为帮助理解协议的说明性示例，我们考虑图1所示的每个流计数器应用。5、此应用程序更新或读取每个数据包的状态。在该示例中，有两个开关和一个状态存储。我们在每个流中有多个数据包，其中第1个数据包被表示为pkt*。 此示例说明了交换机-1最初处理交换机1，但是在其故障之后，流被重新路由到交换机-2的情况状态初始化或迁移（步骤或在图5中）。当状态已经被初始化，应用可以读取状态值（即，在我们的例子中的计数器）直接（步骤3）。 当它更新状态时（即，计数器值），RedPlane将具有新值的复制请求发送到状态存储。该消息完全通过数据平面生成。 状态存储应用更新，并发送复制回复消息（步骤2）。捎带输出数据包。 当应用程序更新状态时，RedPlane不应该允许输出数据包被释放，直到状态被记录在状态存储中-否则，更新可能会在交换机故障期间丢失，从而违反正确性。这需要缓冲输出数据包，直到收到复制应答。不幸的是，交换机数据平面没有足够的存储器来以这种方式缓冲分组（并且关于如何访问存储器的各种其他约束使其不适合存储完整的分组内容）。 RedPlane将数据包附带到其复制请求消息中，状态存储将返回数据包在其答复中。当收到回复时，RedPlane解封，应用接收属于它以前从未见过的流的分组（例如， pkt1），则需要发送状态初始化请求。它通过对流键进行散列来标识对应的状态存储服务器（例如，IP 5元组），并从预配置的表中查找对应的服务器IP和UDP端口。存在两种可能的情况：（1）流是新的并且因此没有状态，或者（2）流状态先前存在于故障交换机上，并且该流的分组现在被路由到替代路径上的交换机（即，故障转移）。在情况（1）中，在接收到请求时，状态存储器恢复其状态的存储，并将响应发送回交换机（步骤1）。在情况（2）中，由于状态存储器已经具有流状态，所以它发送包含最新状态的响应（步骤4）。在接收到响应时，应用程序将返回的状态安装到相应的交换机存储器中。对于有状态存储器寄存器，这可以完全在数据平面中完成在Tofino架构上，更新以匹配表或某些其他资源需要通过交换机控制平面完成。在这种情况下，RedPlane释放数据包。实际上，这将网络和状态存储上的存储器用作延迟线存储器的形式-将交换机上丰富的网络带宽用于稀缺的数据平面存储器。请注意，当存在针对状态的正在进行的复制请求时，可以接收读取状态的数据包。在这种情况下，数据包将以相同的方式通过网络进行缓冲（使用特殊的RedPlane请求类型），直到交换机收到对最新复制请求的响应。虽然我们的基本设计在简化的假设下提供了正确性，但我们发现在更现实的环境中，它可能无法保证正确的行为。 在下面的部分中，我们将描述潜在的挑战，以及我们如何扩展基本设计来解决这些挑战。5.2测序和重传为了保证正确性，复制请求必须成功在状态存储中按顺序传递和复制比如说，通过控制平面路由处理。这可能引入复制请求（图1中的步骤）（5）必须在额外的延迟（我们在第7.1节中对此进行了测量）。然而，许多交换机内应用已经要求对新流的控制平面操作（例如，在NAT中安装新的转换映射），在这种情况下，增加的开销是最小的。秩序然而，在交换机和状态存储之间的尽力服务网络中，不能保证成功的按顺序传递。图图6a说明了为什么网络中的这种不可靠性会成为问题。我们使用相同的每流计数器作为示例。每个���������国家移民局%交换机-2Repl（key=f1，Repl（key=f1，Init（key=f1）Ack（key= f1，cnt=2）状态存储Init（key=f1）cn t=1）cnt=2）Ack（key=1）Ack（key=1）Ack（key=1）交换机-1���������ƒ11���������ƒ1���������ƒ11 2���������ƒ1���������ƒ12$开关-1①状态初始化②更新③读取失败！状态存储cnt=4 cnt=3次与开关状态开关Repl（cnt=4）cnt=3cnt=4���������ƒ1���������ƒ15$状态存储与交换机状态cnt=4cnt=3时间开关cnt=3没有犯下Repl（seq=2，cnt=4）cnt=4���������ƒ15���������ƒ1$230SIGCOMM'21，2021年8月23日至27日，虚拟活动，美国Daehyeok Kim，Jacob Nelson，Dan R. K. Ports，VyasSekar，Srinivasan Seshan计数器递增时，RedPlane将新值发送到状态存储。 如果状态存储仅按接收更新的顺序处理更新，则重新排序可能会导致较晚的计数器值被较早的计数器值替换。 请求丢失可能会导致类似的问题。传统的复制系统（如链式复制）可以通过依赖可靠的传输协议（如T