Concury：快速轻量级软件云负载平衡器

1790Concury：一种快速且轻量级的软件云负载均衡器0Shouqian Shisshi27@ucsc.edu加州大学圣克鲁兹分校0Google Minghao Xie 加州大学圣克鲁兹分校0Google Xiaozhou Li Celer Network Ying Zhang Facebook0Chen Qian qian@ucsc.edu加州大学圣克鲁兹分校0摘要负载均衡器（LB）是云服务中平衡资源负载的重要网络功能。运行在通用服务器上的有状态软件LB提供了灵活性、成本效益和数据包一致性。然而，当前的设计存在两个主要限制：1）状态以摘要的形式存储，可能由于摘要碰撞导致数据包不一致；2）数据平面需要为每个新连接进行更新，频繁的更新会影响吞吐量和数据包一致性。在本工作中，我们提出了一种名为Concury的新型软件有状态LB，它是解决这些问题的第一个解决方案。Concury的关键创新是一种新的方法，用于在大量连接到来时维护大型网络状态，该方法在内存成本、网络变化的一致性和更新成本方面具有简洁性。评估结果显示，与其他LB算法相比，Concury算法提供了4倍的吞吐量，并且占用更少的内存，同时为真实和合成数据中心流量提供了加权负载平衡和无误击自由。我们实现了Concury并对其进行了评估0*Ye Yu和XinLi分别在肯塔基大学和加州大学圣克鲁兹分校攻读博士期间参与了这个项目。0未经费用允许，可以为个人或课堂使用部分或全部作品的数字或硬拷贝，前提是不为盈利或商业优势进行拷贝或分发，并且拷贝上带有本通知和第一页的完整引用。对于ACM拥有的此作品组件，必须尊重版权。允许带有信用的摘要。要进行其他复制、重新发布、在服务器上发布或重新分发到列表中，需要事先获得特定的许可和/或费用。请向permissions@acm.org请求权限。SoCC'20，2020年10月19日至21日，虚拟活动，美国©2020年计算机协会。ACMISBN 978-1-4503-8137-6/20/10...$15.00https://doi.org/10.1145/3419111.34212790在两个真实网络中进行了评估。在一台廉价台式计算机上，以100GbE为基础，实现了每秒67.2 Gbps的单线程吞吐量。0CCS概念∙网络→中间盒/网络设备；云计算。0关键词0负载均衡；软件负载均衡器；云计算；数据中心；移动边缘计算0ACM参考格式：Shouqian Shi，Ye Yu，Minghao Xie，XinLi，Xiaozhou Li，Ying Zhang和ChenQian。2020年。Concury：一种快速且轻量级的软件云负载均衡器。在ACM云计算研讨会（SoCC'20）上，于2020年10月19日至21日，美国虚拟活动。ACM，纽约，美国，14页。https://doi.org/10.1145/3419111.342127901引言负载均衡器（LB）是数据中心的基本网络功能，提供互联网服务。为了满足大规模的热门服务需求，如搜索引擎、电子邮件、照片共享/存储或消息发布和交互，数据中心维护多个后端服务器，每个服务器都携带一个直接IP（DIP）。对于特定的服务，客户端将其请求发送到一个公开可见的IP地址，称为虚拟IP（VIP）。每个VIP都映射到一组DIP。LB使用不同的DIP替代服务请求中的VIP，并平衡服务器之间的负载，以确保没有服务器过载以破坏服务。LB通常在第4层或更高层上运行。传统的基于硬件的LB[8，10，11]在可扩展性、可用性、灵活性和成本效益方面存在局限性[23]。因此，一些主要的网络服务，如Google [23]、Microsoft [32]和Facebook[7、22]，已经开始依赖有状态的软件LB，通过在通用服务器上运行分布式数据平面来提供高可用性、灵活性和成本效益。有状态意味着数据包属于连接，并且连接的先前数据包已经转发到DIP。否则，数据包是无状态的。有状态LB的主要功能包括以下几个方面。1）对于无状态数据包，LB算法应根据后端服务器的当前容量作为加权随机器。2）对于有状态数据包，LB将其转发到接收到先前数据包的特定DIP，保持数据包一致性。有状态LB算法面临的主要挑战是在网络动态下（包括新连接的到来和由于服务器故障或更新而导致的DIP更改）保持数据包一致性。大多数现有的LB算法使用哈希表将连接状态作为数据平面的解决方案[23,32]存储起来。这些有状态LB经常出现存储数据包状态的大内存开销或数据包处理能力低的问题。它们需要大量的通用服务器来扩展，例如，根据Microsoft [25]和Google[23]的报告，数据中心规模的3.5％-10％。因此，一些LB使用连接的摘要（例如，连接的5元组的哈希值）而不是完整的连接状态（例如，5元组）来减少内存成本并提高吞吐量[23]。这种设计有两个主要弱点：1）使用较长的摘要仍可能需要大量内存，而使用较短的摘要会导致数据包一致性的违反；2）大量的新连接会导致非常频繁的数据平面更新-现代集群每秒可能很容易经历数千个新连接[28]这会严重影响数据包处理吞吐量，并可能导致数据包一致性的违反。现有的依赖于快速和并发的哈希表读写的方法[24,26]无法轻松应用于LB算法，因为它们只适用于完整的状态键而不是摘要。最近的工作使用可编程交换机上的ASICs进行快速表查找[28]，但进一步增加了基础设施成本。我们提出了第一种解决当前限制的有状态LB算法，称为Concury。它的关键创新和贡献是一种新颖的方法，用于在大量新到来的连接下维护大规模网络状态，该方法在内存成本、网络变化的一致性和数据平面更新频率方面具有简洁性。这种方法可能适用于许多有状态网络功能，如NAT和LTE Evolved Packet Core，但本文仅关注LB。1800SoCC'20，2020年10月19日至21日，虚拟活动，美国Shouqian Shi，Ye Yu，Minghao Xie，Xin Li，Xiaozhou Li，Ying Zhang和Chen Qian01Concury的名字来自于罗马女神Concordia和罗马神话中的信使神Mercury，分别代表着平衡与和谐以及消息和旅行者，后者以其极速闻名。0与现有的有状态LB[7，23，25，28，32]相比，Concury提供了两个主要优势。1）我们意识到软件LB的当前限制来自于状态维护和查找的算法设计：存储摘要的哈希表。为了减少内存成本，现有的LB存储状态的摘要，而不是完整的状态标识符（例如，5元组）[23,28]。缺点包括由于摘要碰撞引起的假表命中[28]和由于删除摘要的困难而导致的表扩展。Concury使用一种数据结构以简洁的方式表示所有数据包状态（只是两个小数组），通过利用最小完美哈希的理论基础[18,20,21,27,39]。Concury设计成以这样一种方式找到有状态数据包的特定目的地，并且对于有状态数据包表现为加权随机器，具有很小的内存开销和数据包一致性。然而，应用理论上的OthelloHashing并不直接。需要克服几个系统构建上的挑战：支持高效快速的查找，管理有限资源下的连接以及无误击。2）现有LB的数据平面更新发生在每个传入连接上。Concury包括数据和控制平面之间的协调，以便Concury不需要为每个传入的连接更新其查找表。相反，Concury数据平面仅在后端服务器更改（DIP更改）时进行更新，这种情况比新状态到达频率要低得多。与现有解决方案相比，Concury的状态维护和更新要简单得多，这使得Concury能够维持高查找吞吐量和一致性。此外，Concury可以用于复杂的互联网应用程序和新兴的边缘云[33,34,37,38]。1）它符合边缘云的条件，边缘LB通常具有受限资源-边缘LB可能只由一台服务器托管，并且可以与服务器上的其他服务共存[34,38,41]。2）传统云LB考虑每个TCP连接的状态。在现代云或边缘中，状态可能是多连接状态，并且在设备级或进程级[34,38,41]，即属于同一设备的数据包应发送到相同的DIP。例如，用户设备可以将其视频数据转移到边缘服务器，让服务器处理数据，然后从服务器请求分析结果[34]。这整个过程由多个TCP流和具有UDP的伪流组成，所有这些都应发送到一致的DIP。与先前的设计不同，Concury的性质可以轻松支持多连接状态。3）现代云和边缘服务器在计算、存储和带宽方面可能具有异构能力[34,38]。Concury对由于服务器故障或负载动态而导致的权重更改做出快速反应。我们进行了几个关键的知识贡献：1810Concury：一种快速且轻量级的软件云负载均衡器SoCC’20，2020年10月19日至21日，虚拟活动，美国0（1）Concury的工作流程旨在实现内存效率、高吞吐量、负载均衡、一致性和无错误命中。（2）我们提出了一种在控制平面中维护动态状态集并可以在DIP池更改时即时生成新的查找结构来更新数据平面的新方法。（3）我们将加权随机化器和大规模连接状态维护功能添加到LB中。 （4）我们使用DPDK[2]实现了Concury，以展示其在两个真实网络中的高性能。我们还构建了一个P4原型，以展示其对可编程交换机的兼容性。源代码可以在此处访问[14]，我们的结果可以进行再现。0Concury在文献中报告的数据包处理吞吐量最高（在廉价的桌面计算机上单线程达到67.2 Gbps（不包括100GbENIC，价格低于800美元））和低内存成本（0个错误命中），相比现有的有状态LB。我们认为Concury是一个重大改进，因为它实现了三个方面的最佳表现：性能、成本效益和一致性（正确性）。它适用于新的应用和系统。它还包括一种理想的解决方案，用于动态状态维护，对其他网络功能也有用。本文的平衡部分组织如下。第2节介绍相关工作。我们在第3节中正式模拟了LB算法。第4节介绍了一些背景算法。我们在第5节中详细介绍了Concury的设计。系统实现和评估结果在第6节中展示。我们在第7节中总结了这项工作。这项工作不涉及任何伦理问题。02相关工作LB是数据中心网络的重要组成部分，用于将传入流量分配到不同的后端服务器或其他网络功能[7，23，25，32，36]。传统的硬件负载均衡器价格昂贵且不灵活。因此，许多大型云服务选择使用软件负载均衡器[7，12，23，25，32]。此外，LB对于边缘数据中心[17，34，35，41]也很重要，边缘数据中心允许路径上的异构设备提供存储和计算资源。有状态负载均衡器。Ananta[32]是一种三层架构中的软件有状态LB，包括运行ECMP的数据中心路由器，多个运行在普通服务器上的软件复用器（SMuxes）以及每个后端服务器上的主机代理。然而，每个Ananta实例的数据包处理速度非常慢，如[25]所示。Duet[25]利用普通交换机上的转发和ECMP表来存储VIP-DIP映射。在DIP池频繁更改的情况下，Duet可能无法维护PCC[28]。0Maglev[23]是Google的分布式软件负载均衡器，运行在普通服务器上。Maglev的核心算法是使用哈希表作为负载均衡的连接摘要以及一种新的一致性哈希算法，以应对DIP池变化。SilkRoad[28]在最先进的可编程交换ASIC上实现了LB功能，需要超过50MB的SRAM。它支持高流量低延迟，并保持一致性。部署SilkRoad会引入额外的硬件成本，每个SilkRoad交换机的成本为6.5K美元，并且每个集群需要多个交换机。此外，Maglev和SilkRoad可能在连接查找时包含错误命中，因为使用摘要而不是完整的状态信息。错误命中会导致两个主要问题。1）数据包可能被转发到不提供其VIP正确服务的DIP，然后失败。2）多个状态可能共享表中的一个摘要。很难判断何时删除一个摘要。删除已完成状态的摘要可能会终止一个活动状态，如果它们的摘要发生碰撞。因此，随着时间的推移，表的大小可能会急剧增大，或者一些活动状态可能会被终止。上述方法中可以用来维护状态的典型数据结构是CuckooHashing[31]。Bonomi等人提出使用近似并发状态机（ACSM）来维护动态网络状态[19]，但此方法不能用于LB。我们在表1中将Concury与现有的有状态LB进行了比较，表中列出了实验值，这些值基于6.2中的DIP-V16M状态网络的使用。无状态负载均衡器。最近提出了Beamer [30]和Faild[17]作为无状态LB。它们的转发逻辑不存储连接状态，而是使用简单的映射算法（静态或一致哈希）。它们在每个数据包头中写入一个新字段来携带其DIP。端点服务器需要检查每个数据包头，以确保数据包与该服务器上的状态一致。如果不一致，服务器会对数据包执行覆盖重定向到正确的DIP。此方法要求对每个服务器的网络栈进行内核修改以添加额外的网络处理。因此，计算和内存开销转移到服务器端，并且是基于每个数据包的。当状态是短期的时，覆盖重定向可能不是一个重大问题。然而，对于长期的多连接状态，无状态LB可能导致大多数有状态数据包的重定向，因为经过一段时间后，映射将变得非常不同。与这些方法相比，Concury只需要每个服务器在应用层运行一个轻量级的状态跟踪程序，而不会改变网络栈。有状态和无状态LB的性能比较将是不可比较的，因为开销发生在不同的位置。我们不打算宣布有状态和无状态LB之间的明显胜利。本文的目的是改进1820SoCC’20，2020年10月19日至21日，虚拟活动，美国Shouqian Shi，Ye Yu，Minghao Xie，Xin Li，Xiaozhou Li，Ying Zhang和Chen Qian0LB算法 查找（Mpps）内存（MB）加权LB误命中 数据包类型额外硬件更新中断0ECMP +哈希表（Ananta [32]）低 高 不清楚 任何类型 否 频繁0哈希表带摘要（Maglev [23]）14.63 18.63 是 存在 仅TCP 否 频繁0多个哈希表带摘要（SilkRoad [28]）16.11 4.36 否 存在 仅TCP ASIC 频繁0Concury（本文） 66.28 3.84 是 否 任何类型 否 偶尔0表1：有状态LB算法的比较及示例结果。这些数字值是使用1M并发连接进行的微基准测试的结果。更多结果可以在ğ 6中找到。0具有VIP的数据包01. LB数据平面确定每个数据包的目的地DIP02. LB控制平面03. 更新0具有DIP的数据包0具有不同DIP的服务器0维护状态并计算数据平面0图1：有状态LB的一般模型0有状态LB设计并将有状态和无状态LB之间的选择留给网络运营商。0云/边缘数据中心提供的服务由一个公开可见的IP地址（称为虚拟IP（VIP））标识。客户端将其服务请求发送到VIP。负载均衡器（LB）将负载分配到云/边缘服务器上，以确保没有服务器过载并中断服务。每个后端服务器由直接IP（DIP）标识。因此，LB的核心功能是根据数据包的头信息（例如，其5-tuple或其他状态标识符）将VIP映射到DIP。每个VIP与其DIP池相关联，该池包括提供由VIP标识的服务的服务器的DIP。VIP的DIP池可能因服务规模和环境（云端或边缘）而异。如果服务器维护数据包的状态，则必须将数据包发送到服务器的DIP。状态可以是正在进行的连接或多连接。满足LB在ğ1中提出的所有要求是具有挑战性的。简单的无状态算法（如“一致性”哈希）无法保证一致性。这是因为当存在DIP池或权重更改时，分布算法需要更改，然后有状态的数据包可能会映射到另一个服务器。最近的有状态LB设计[23，28]需要存储连接状态，并确保所有与状态匹配的数据包始终映射到相同的DIP。我们总结了有状态LB的一般模型（如图1所示），分析了该模型的组成部分，并指出了设计目标。01.LB数据平面（LB-DP）。LB-DP处理数据包并为携带VIP的每个数据包找到一个DIP。DIP应从VIP后面的DIP池中选择，代表提供此VIP服务的服务器集合。核心算法应提供两个功能：i）为每个有状态数据包查找相应的服务器（DIP），ii）根据给定的权重为每个无状态数据包分配一个可用的服务器（DIP）。LB-DP的设计目标是实现高数据包处理吞吐量和内存成本的效率，因为高速内存在通用服务器（缓存）和硬件交换机（ASIC）上都是宝贵的资源。此外，LB-DP应根据反映每个服务器当前容量的权重来平衡无状态数据包，这可能是异构和动态的。例如，如果一个服务器正在服务许多大型连接，则它在不久的将来必须接收较少的新状态。因此，我们将“权重”确定为LB的重要输入，并且我们期望LB作为新状态的加权随机器。2.LB控制平面（LB-CP）。LB-CP接收来自服务器的状态更改，包括新状态的建立和状态的删除。许多现有的设计使用TCPSYN数据包作为新状态的指示器，并允许LB-DP直接通知LB-CP。然而，对于UDP或多连接状态，这种方法不起作用。LB-CP的设计目标是高效地维护所有入站数据包的状态，并在需要更新LB-DP时快速构建新的LB-DP以反映数据包的一致性。确保将连接的所有数据包都传递给同一台服务器对于LB来说至关重要，因为恢复中断的连接通常需要很长时间，并且严重影响用户体验。在没有统一数据管理层的边缘或云中，来自单个设备的不同流的数据包应该发送到同一台服务器。实现设备级一致性可以避免许多新兴应用（如媒体卸载）的覆盖式重新路由。3.更新。LB-CP将通知LB-DP在某些网络动态下进行必要的更改，例如DIP池和权重更改。更新过程的设计目标是减少更新的频率，因为它会中断LB-DP上的数据包处理。11011110 01001011011110 01001011011110 0100101830Concury：一个快速且轻量级的软件云负载均衡器SoCC'20，2020年10月19日-21日，虚拟活动，美国0� value � � � � � �0�1 01650�2 10100�3 11120�4 00130�5 10420图2：布鲁米尔过滤器的构造0虽然Concury需要服务器发送状态通知，但服务器不需要像以前的有状态负载均衡器那样维护任何状态。在其他设计中，服务器到负载均衡器的消息对于加权负载均衡是必要的。04个背景算法我们提议使用最小完美哈希的数据结构和算法[18, 20, 21, 27,39]来实现Concury负载均衡器。一个众所周知的基于完美哈希的数据结构是布鲁米尔过滤器[20,21]。最近提出的奥塞罗哈希[39,40]利用布鲁米尔过滤器支持可编程网络中的转发信息库，包括布鲁米尔过滤器的一种变体作为其数据平面，控制平面中的构造程序，以及两个平面的交互协议。奥塞罗找到了布鲁米尔过滤器的设置，以在动态网络环境中实现良好的时间/空间折衷。尽管它并非为LB设计，但奥塞罗基于三个原因非常适合LB：1）奥塞罗数据平面的查找超快且内存高效；2）查找是无碰撞的，尽管数据平面中没有存储完整的键；3）我们设计了控制平面与数据平面之间的异步更新算法，同时保持PCC和加权负载平衡始终存在。我们在本节中说明了前两点，第三点在第5节中详细介绍。0布鲁米尔过滤器不是用作过滤器，而是用作一组键值对的映射。令S为键的集合，n=|S|。每个键的查找返回一个与该键对应的l位映射。奥塞罗控制平面中的布鲁米尔过滤器构造。我们使用图2中的例子来展示一组五个键值对的布鲁米尔过滤器。数组A和B分别建立了ma和mb个元素，其中ma=n，mb=1.33n。数组的每个元素都是一个l位值。在这个例子中，l=2，并且为了更好地说明，我们假设m=ma=mb=8。对于A中的每个值i，我们放置顶点ui，对于B中的每个值j，我们放置顶点wj。使用两个哈希函数ha和hb来计算所有键的整数哈希值[0，m-1]，然后对于每个键，我们在对应于其哈希值的两个顶点之间放置一条边。例如，ha(k1)=6，hb(k1)=5，因此放置一条边连接u6和w5。对于一个键k及其对应的值v，布鲁米尔的要求是0�0�0（a）查找在构造期间已知的键：指定的结果011 ⊕ 10 = 010�0�0（b）查找在构造期间未知的键：确定的随机000 ⊕ ? = ?0图3：布鲁米尔过滤器的查找0在这个例子中，对于密钥k1，u6 ⊕ w5 = 012 =1。灰色着色的顶点代表了不关心的元素。值得注意的是，在放置所有密钥的边之后，双分图G需要是无环的。证明了如果G是无环的，那么可以轻松找到一个有效的元素分配，以满足所有密钥的值。如果发现一个环，构造需要找到另一对哈希函数来重新构建G。证明了在构造n个密钥期间，重新哈希的期望总次数小于1.51，当n≤0.75m。构造n个密钥的G的期望时间成本为O(n)，删除或更改密钥的时间为O(1)，添加密钥的时间为摊销O(1)。该设计可以轻松扩展到l>2。奥塞罗数据平面中的布鲁米尔过滤器查找。奥塞罗查找结构只是一个包含两个位图A和B的布鲁米尔过滤器，如图3(a)所示。要查找k1的值，我们只需要计算ha和hb，它们映射到A的第6个位置和B的第5个位置（从0开始）。然后我们计算两个位的异或并得到值012。因此，查找结果是τ(k) = a[ha(k)] ⊕b[hb(k)]。查找是内存高效且快速的。1)数据平面只需要维护这两个数组。密钥本身不存储在数组中。因此空间成本较小（每个密钥2m/n）。2)每次查找只需要两次内存访问操作，分别从A和B中读取一个元素。它适用于可编程网络架构：数据平面只需要存储查找结构、两个数组，而控制平面存储密钥-值对和无环双分图G。当有任何更改时，控制平面更新这两个数组并让数据平面接受新的数组。当一个布鲁米尔过滤器执行查找不存在的密钥时，它返回一个任意值。例如，在图3(b)中，k6不在S中，它的结果可能是一个任意值。我们将利用这一特性构建一个加权随机器。值得注意的是，更新可能需要重新哈希，尽管这种情况发生的概率较低（O(1/n)），但仍需要O(n)的时间，并可能对控制平面的响应时间产生显著的延迟。因此，我们提出了一种先进的1840SoCC '20，2020年10月19日至21日，虚拟活动，美国Shouqian Shi，Ye Yu，Minghao Xie，Xin Li，Xiaozhou Li，Ying Zhang和Chen Qian0数据包的VIP索引：i VIP Array0存储VIP索引到BAS地址的映射BAS-10BAS-i ...数据包的5元组0DIP Array ... 2D Array DA：DA [i] [Dcode] =DIP0控制平面0更新0图4：Concury数据平面的工作流程0一种名为OthelloMap的数据结构，始终在控制平面中保持最新的查找结构，以将响应时间限制在微秒级，如在ğ5.4中解释的那样。05CONCURY设计5.1系统概述符号。网络中VIP数量为M。为每个VIP vi分配一个索引i，并且其DIP池包含ti个DIP。VIPvi的状态数为ni。Concury遵循ğ3中介绍的DP模型，包括数据平面和控制平面。Concury数据平面（Concury-DP）的输入是一个目的地地址为VIP的数据包，输出是目的地已被替换为DIP的相同数据包。在每个后端服务器上（由DIP标识），都有一个轻量级的应用层程序，用于跟踪该服务器上的当前状态，这已经被现有的数据中心LB使用[25]。状态跟踪程序将向Concury控制平面（Concury-CP）报告新建和终止的状态。只有当VIP的DIP池发生更改时，即服务器故障/添加和服务器权重更改时，Concury-CP才会更新Concury-DP。更新仅适用于Concury-DP的一小部分。设计目标已在ğ3中讨论。设计Concury的挑战。Concury的一个关键创新是放弃先前LB设计的传统的“查找然后分发”工作流程，采用一种同时实现“查找”和“分发”的新方法。然而，Bloomier和Othello最初并不是为LB设计的。应用Bloomier的挑战包括：1）如何调整Bloomier以进行活动状态查找和加权随机化；2）如何设计数据平面以最小化内存成本并最大化吞吐量；3）如何解决虚假命中问题，而无需修改服务器网络堆栈；4）如何在数据平面中放宽对每个新状态的更新要求。05.2 Concury数据平面0Concury使用Bloomier过滤器作为表示状态到DIP映射的查找结构和加权随机化器。如ğ4中介绍的，Bloomier过滤器基于0Concury中的每个键是一个状态的标识符，即5元组。与键对应的值是一个DIP代码（Dcode），它最终将转换为DIP，即持有状态的后端服务器的地址。注意，布隆过滤器提供状态到DIP的映射，但实际上不存储键。因此，内存成本显着降低。构建Concury的状态到DIP查找结构有两种可能的方法。1）所有VIP共享单个查找结构。2）每个VIP都有一个单独的Bloomier过滤器作为查找结构，称为Bloomier数组集（BAS），仅存储此特定VIP的状态到DIP映射。这需要M个BAS。我们使用此方法而不是单个统一的BAS，因为：1）更改VIP的DIP池时，只需要更新此VIP的Dcodes。其他保持不变。2）分离不同的VIP进一步确保数据包不会转发到另一个VIP池中的DIP。3）实验结果表明，单独的查找结构比统一的查找结构提供了5％的更快查找速度。注意，保持每个VIP结构也可以由其他有状态LB（如Maglev[23]）使用，以避免交叉VIP问题。然而，它仍然无法解决ğ2中所述的摘要删除问题。Concury之所以独特，是因为它可以处理这两种类型的问题。Concury数据平面的工作流程如图4所示，包括三个主要步骤。查找操作简单快速，仅包括四次读取操作和哈希计算。第1步。当Concury接收到一个数据包时，首先使用数据包头中的VIPvi通过表查找或计算获取VIP索引i。由于VIP由边缘/云操作员确定，可以简单地为所有VIP分配一个单一前缀，例如22位前缀，然后可以使用VIP的最后10位作为VIP索引，支持1KVIP。Concury维护一个VIP数组，其中存储不同BAS的内存地址，使用索引作为VIP索引的静态数组。第1步的结果是VIPvi的BAS的内存地址。该数组小且静态。第2步。使用第1步的内存地址，Concury找到VIPvi的BAS，表示为BAS-i。BAS-i仅包括两个数组A和B，用于支持查找结果τ（k）= A [ha（t）]⊕ B[hb（t）]，其中t是k的4元组，与5元组相比，不包括目的地IP地址。结果是一个称为DIP代码的l位值，表示为Dcode。每个DIP代码将在第3步映射到一个实际的DIP，它是一对多映射。两个不同的DIP代码可能映射到一个单个的DIP。第3步。此步骤使用l位Dcode查找实际的DIP。Concury维护一个称为DIP数组的2D数组，表示为DA。元素DA [i][Dcode]是VIPvi的Dcode的DIP。这个2D数组与当前状态的数量无关，不占用太多内存。假设有1850Concury：一种快速轻量级软件云负载均衡器SoCC '20，2020年10月19日至21日，虚拟活动，美国0512个VIPs和l=12。内存成本约为2MB。注意DA [i][Dcode]对于Dcode的任何l位值都是VIPvi的有效DIP。为了进一步减少内存成本，DA [i][Dcode]可以是可以转换为具有一个以上静态表查找的DIP的DIP索引。数据平面复杂性分析和比较。1）时间成本。Concury-DP非常简单快速。每次查找为O（1），包括从静态数组中最多进行6次读取操作，2次哈希计算（每次32位）和一次异或计算。这个成本比Cuckoo + digest小，Cuckoo +digest是一种常用的LB表设计[23,28]，对于有状态和无状态的数据包都需要更多的读取操作和哈希计算。2）空间成本。设n为总状态数，ld为Dcode的长度，lv为DIP表中DIP索引的长度。Concury-DP的总内存成本为2.33ldn + 64m +2ldlvm + 48 * 2lv位，这比实际设置中的Cuckoo +digest要小得多。05.3加权负载均衡使用DIP代码的原因。可以注意到，为了处理新状态的第一个数据包，Concury获取Dcode，然后将其转换为DIP，而不是直接将DIP作为BAS的查找结果。我们的方法减少了存储成本，因为DIP长度为32位，而DIP代码可以更短，例如10位。不同的DIP代码的总数，2ld，可以大于DIP的数量，例如大于一个数量级，以提供加权随机化的粒度。Dcode到DIP的映射由LB如何在这个VIP的DIP之间分配权重决定。例如，如果Dcode有4位，并且有4个DIP，所有DIP具有相等的权重，那么我们可以将Dcode在[0000,0011]中映射到DIP1，在[0100,0111]中映射到DIP2，在[1000,1011]中映射到DIP3，以及在[1100,1111]中映射到DIP4。我们可以将Dcode视为一个球，每个DIP视为一个箱子。如何实现加权负载均衡。我们首先展示对于未知状态，BAS返回特定Dcode的概率在所有可能的Dcode值之间均匀分布。对于新状态c，BAS的查找结果是Dcode =τ（c）= A [ha（c）] ⊕ B [hb（c）]，其中A [ha（c）]和B[hb（c）]都是l位值。假设A [ha（c）]（B[hb（c）]）在数组A（数组B）中的任何元素都具有相等的概率，这在ha和hb是均匀哈希的情况下是正确的。A或B中的每个元素可以是“确定的”或“自由的”。确定的元素对应于Fig.2中的白色顶点，其值应在构建期间固定以提供当前状态的正确查找。'自由'元素对应于灰色顶点，其值为'不关心'。我们为每个自由元素分配均匀随机值。0因此，如果A [ha(c)]和B[hb(c)]都确定，Dcode就确定了。如果A [ha(c)]和B[hb(c)]中的一个自由，那么Dcode就是随机的。我们知道A和B都有m个元素，A [ha(c)]和B[hb(c)]之间有m2个可能的配对。其中，只有n个配对产生确定的Dcode值，比例为n/m2 <1/n。因此，结果中只有一小部分是确定的，其他部分可以被视为均匀随机的。我们使用实验结果验证了这种均匀性。图5展示了一个典型的例子。我们将值长度l =10。因此，有1024个可能的Dcode。我们枚举了A和B的所有可能的索引组合，并计算了结果的Dcode。Concury使用的哈希函数是CRC32。我们观察到使用Concury，这些组合（无状态数据包）非常均匀地分布在不同的Dcode上，最小值、10%分位数、均值、90%分位数和最大值分别为925、980、1024、1066和1120。其他实验的结果类似。我们将Concury与MD5和SHA256进行比较。虽然MD5和SHA256不严格均匀，但在实践中被认为是足够均匀的。我们表明Concury在均匀性方面与它们相媲美，并且足够好地用于实际系统。我们进行了两个著名的统计检验，卡方检验和Kolmogorov-Smirnov检验，将Concury、MD5和SHA256与均匀分布进行比较。如图6和7所示，它们每个都在10％左右的测试中失败，因为它们不是严格均匀的。Concury不比MD5或SHA256差，特别是当ld > 11（Dcode数量 >2048）时。在我们的实现中，我们设置ld =12。我们将进一步评估向DIP的负载分布在第6.4节中。0基于均匀的Dcode分布，我们可以使用Dcode-DIP映射来实现加权随机化。Dcode的数量应比DIP的数量大一定比例，例如>8倍。然后，DIP的权重由表DA中的条目数反映。例如，如果DIP d1的权重为1.0，而DA中有100个指向d1的条目，则对于权重为2.0的DIPd2，DA应该有200个指向d2的条目。如果d2接近满载（这是不太可能的），则应降低d2的权重以反映其当前剩余容量，并且新的连接以较小的概率进入d2。此权重更改将导致Concury的控制平面和数据平面之间进行完全同步，详见第5.5节。05.4 Concury控制平面Concury控制平面（Concury-CP）的任务有两个：1）跟踪现有状态；2）在需要数据平面更新时生成新的数据平面结构，主要是新的BAS。一种简单的解决方案是使用哈希表来存储一组状态-DIP对。当进行更新时010002000300040005000010203040500102030405001020304050111010011000 0011001111860SoCC’20，2020年10月19日至21日，美国虚拟活动，施寿前，余晔，谢明豪，李欣，李晓舟，张颖和钱晨0图5：Dcode的无状态数据包分布01024 2048 4096 8192 Dcode数量0故障率（%）0图6：卡方检验01024 2048 4096 8192 Dcode数量0故障率（%）0图7：Kolmogorov-Smirnov检验08K 16K 32K 64K 128KVIP的状态数0DP构建时间（ms）0图8：Concury-DP构建的响应时间0�0�0查找第�(�)个元素0索引 状态 DIP0更新Othello以进行元素添加/删除0用于存储状态-DIP映射的数组C Othello O用于获取C中元素的索引0图9：OthelloMap的查找/更新0所需的，新的BAS是从该集合构建的。我们的创新思路是设计一种称为OthelloMap的新数据结构，用于维护所有当前状态的状态-DIP对和BAS。注意，如果网络包括M个VIP，则控制平面有M个OthelloMap。使用OthelloMap的目的是在发生网络动态时快速生成新的Concury-DP。OthelloMap的组成部分。如图9所示，VIPv的OthelloMap包括两个部分。1）大小为n的数组C，其中n是VIPv的当前状态数。C的每个元素存储一个状态-DIP对。2）使用当前状态集合构造的BASO。使用状态标识符（ID）c进行O的查找结果是索引i，使得C[i]存储c的状态-DIP对。注意i的长度不小于�log2n�位。对OthelloMap进行集合查询。集合查询是OthelloMap的基本功能。输入是可能的状态IDc'，输出要么是相应的DIP，要么是“不存在”。为了进行集合查询，OthelloMap使用c'对BASO进行查找，得到一个值i。如果状态存在，则C[i]包含DIP。否则，存储在C[i]中的连接与c'不匹配。因此，它可以返回“不存在”。此过程需要O（1）时间。向OthelloMap添加/删除。要将状态-DIP对�c，DIP�添加到OthelloMap中，我们首先对c应用集合查询。如果c存在，则将C[i]修改为�c，DIP�。如果c不存在，则将�c，DIP�存储到C[n+1]。然后将�c，n+1�添加到BASO。此过程的平摊时间复杂度为O（1）。要从OthelloMap中删除状态-DIP对�c，DIP�，我们对c应用集合查询。如果c不存在，则不执行任何操作。否则，c及其DIP存储在C[j]中。我们从C [j]中删除它们，并将0在C [n]中的元素，记为�c'，DIP'�，到C [j]。然后，我们将BASO中对应于c'的值从n修改为j。此过程需要O（1）时间。Concury-CP的内存成本分析。令li为索引i的长度，lk为每个状态-DIP对信息的长度。Concury-CP的内存成本为2.33li n + （lk +ld）n + 64m + 2ldlvm + 48 ∙ 2lv，其中2.33li n是BASO的开销，（lk +ld）n是数组C的开销，其余部分用于需要更新到数据平面的VIP数组和DIP数组。使用OthelloMap的性能增益。我们比较构建新的DP的时间，使用和不使用OthelloMap。结果如图8所示。OthelloMap显著减少了控制平面在Concury更新期间的响应时间超过50％。Concury-CP和主机Agent的交互。Concury-CP从在不同DIP服务器上运行的主机Agent接收状态到达/终止报告。收到报告后，Concury-CP对应执行添加/删除操作到相应的OthelloMap