CN117596211A - Ip分片多核负载均衡装置及方法 - Google Patents

Abstract

本发明公开了一种IP分片多核负载均衡装置及方法，其装置包括特征提取模块、分发表及分发模块，特征提取模块提取IP分片首包的IP五元组及IP分片的IP分片三元组；分发表记录各IP报文的分发结果，采用数组方式进行组织，以IP分片三元组的哈希值作为数组索引；分发模块根据特征提取模块得到的结果将IP分片分发给处理装置；当分发IP分片首包时，根据IP五元组计算得到分发结果，并将分发结果存入分发表；当分发IP分片非首包时，查询分发表得到分发结果。本发明在多队列网卡、RPS、RFS等处理装置共享内存的软硬件场景下，实现了IP五元组级别的IP分片负载均衡，负载均衡效果好；本装置分发效率高；分发后，处理装置处理时程序局部性好，处理效率高。

Description

IP分片多核负载均衡装置及方法

技术领域

本发明涉及计算机网络和数据通信技术领域，具体是涉及一种IP分片多核负载均衡装置及方法。

背景技术

现代网络设备通常使用多队列网卡、多核处理器，并使用负载均衡装置将IP报文分发给多个相同的处理装置并行处理。对于非分片IP报文而言，负载均衡装置通常将IP五元组相同的IP报文分发给同一处理装置处理。对于IP分片而言，由于只有IP分片首包（即IP报头中Fragment offset字段的值为0的分片）有完整的IP五元组，IP分片非首包（即IP报头中Fragment offset字段的值不为0的分片）只含有IP三元组（IP源地址、IP目的地址、IP协议号），当前，在多队列网卡、RPS、RFS等处理装置共享内存的场景下，负载均衡装置选择将IP三元组相同的IP分片分发给同一装置处理。然而，相比将IP五元组相同的IP报文分发给同一处理装置处理，将IP三元组相同的IP报文分发给同一处理装置处理更容易出现负载不均衡的情况。比如，某时刻，若网络设备需要处理的IP报文的IP三元组相同但IP五元组不同，此时若将IP三元组相同的IP报文分发给同一处理装置处理，会造成多个处理装置中实际只有一个处理装置在处理IP报文，但若将IP五元组相同的IP报文分发给同一处理装置处理，会有更多的处理装置参与处理IP报文，负载更加均衡。

随机分发或轮询分发每一个IP分片可以解决负载不均衡的问题，但会造成分发后，各处理装置处理IP分片时，发生较多的缓存不命中，处理效率低。作为对比，处理装置处理IP五元组相同的报文用到的各种查找表（如ARP表，路由表）表项相同，因此将IP五元组相同的IP报文分发给同一处理装置处理可以提升各处理装置处理IP报文时的缓存命中率，从而提升处理效率。

IP分片重组后将IP五元组相同的重组后IP报文分发给同一处理装置处理的分发方式可以使得分发后各处理装置的负载较为均衡，同时处理效率较高。然而，IP分片重组需要的CPU资源多，分发效率低，负载均衡装置本身容易成为网络设备的瓶颈。公告号CN1941732A的中国发明专利可以用来优化IP分片重组过程，但当属于同一个IP报文的IP分片非首包早于IP分片首包到达负载均衡装置时，该专利仍需缓存早到的IP分片非首包。另外该专利需要维护分片首包是否到达等状态信息，实现复杂，负载均衡装置依然容易成为网络设备的瓶颈。

发明内容

本发明的目的是为了克服上述背景技术的不足，在多队列网卡、RPS、RFS等处理装置共享内存的软硬件场景下，提供一种分发逻辑简单高效同时实现IP五元组级别的IP分片负载均衡的装置及方法。

本发明的第一方面，提供一种IP分片多核负载均衡装置，包括：特征提取模块、分发表、分发模块；

所述特征提取模块，用于提取IP分片首包的IP五元组及IP分片的IP分片三元组；

其中，IP分片首包是IP报头中Fragment offset字段为0的IP分片；IP分片非首包是IP报头中Fragment offset字段不为0的IP分片；IP五元组包括源地址、目的地址、源端口号、目的端口号、协议号；IP分片三元组包括源地址、目的地址、报文ID；

所述分发表，用于记录各IP报文的分发结果，采用数组方式进行组织，以IP分片三元组的哈希值作为数组索引；

所述分发模块，根据特征提取模块得到的结果将IP分片分发给处理装置；当分发IP分片首包时，根据IP五元组计算得到分发结果，并将分发结果存入分发表；当分发IP分片非首包时，查询分发表得到分发结果。

需要强调，当属于同一个IP报文的IP分片非首包早于IP分片首包到达所述特征提取模块时，所述分发表还未记录该IP报文的分发结果，所述分发模块依然通过IP分片三元组的哈希值索引数组得到分发结果，并对IP分片非首包进行分发；

所述IP分片多核负载均衡装置无需分片重组或缓存IP分片；所述分发表无需维护每一个IP报文的IP分片首包是否到达的状态信息。

所述分发结果用处理装置编号表示，并使用能区分不同处理装置编号的最小2的整数次幂位宽的二进制数编码和存储。

所述分发表允许多个不同IP分片三元组计算得到相同的哈希值，以哈希值所有不同取值的个数作为数组的长度。

需要强调，当所述分发模块已经完成一个IP报文的IP分片首包分发，但仍有属于当前IP报文的其他IP分片未到达所述特征提取模块，此时若IP分片三元组不同但哈希值相同的下一个IP报文的IP分片首包先到达时，则所述分发模块从分发表中丢弃当前IP报文的分发结果而将下一个IP报文的分发结果存入分发表，之后，若当前IP报文的其他IP分片到达时，所述分发模块按下一个IP报文的分发结果分发当前IP报文的IP分片。

本发明的第二方面，提供一种IP分片多核负载均衡方法，包括以下步骤：

从IP分片提取分发所需的特征；

根据提取到的特征对IP分片进行分发。

所述从IP分片提取分发所需的特征步骤，具体包括如下步骤：

步骤一，提取IP分片的IP分片三元组；

步骤二，判断输入的IP分片是否为IP分片首包，若是，则提取IP分片首包的IP五元组。

所述根据提取到的特征对IP分片进行分发步骤，具体包括如下步骤：

步骤一，判断输入的IP分片是否是IP分片首包，若是，则根据IP五元组计算得到分发结果，并将分发结果存入分发表，完成分发，否则转步骤二；

步骤二，以IP分片三元组查找分发表，按查询的分发结果进行分发。

与现有技术相比，本发明的特征提取模块提取IP分片首包的IP五元组及IP分片的IP分片三元组；分发表记录各IP报文的分发结果，采用数组方式进行组织，以IP分片三元组的哈希值作为数组索引；再通过分发模块根据特征提取模块得到的结果将IP分片分发给处理装置；当分发IP分片首包时，根据IP五元组计算得到分发结果，并将分发结果存入分发表；当分发IP分片非首包时，查询分发表得到分发结果。因此本发明实现了IP五元组级别的IP分片负载均衡，因此负载均衡效果好，同时分发后，处理装置处理时程序局部性好，处理效率高；另外，本发明实现简单，分发效率高。

附图说明

本发明可以通过参考下文中结合附图所给出的详细描述而得到更好的理解，其中在所有附图中使用了相同或相似的附图标记来表示相同或相似的部件，所述附图连同下面的详细说明一起包含在本说明书中并形成说明书的一部分，用来进一步举例说明本发明的优选实施例和解释本发明的原理和优点。在附图中：

图1是本发明的IP分片多核负载均衡装置的结构示意图；

图2是处理装置处理一个IP报文不同IP分片时的工作流程示意图；

图3本发明的特征提取模块的流程示意图；

图4是本发明的分发模块的流程示意图；

附图标号：

101、特征提取模块；102、分发表；103、分发模块。

具体实施方式

在下文中将结合附图对本发明的示范性实施例进行描述。为了清楚和简明起见，在说明书中并未描述实际实施方式的所有特征。然而，应该了解，在开发任何这种实际实施例的过程中必须做出很多特定于实施方式的决定，以便实现开发人员的具体目标，例如，符合与系统及业务相关的那些限制条件，并且这些限制条件可能会随着实施方式的不同而有所改变。此外，还应该了解，虽然开发工作有可能是非常复杂和费时的，但对得益于本公开内容的本领域技术人员来说，这种开发工作仅仅是例行的任务。

在此，还需要说明的一点是，为了避免因不必要的细节而模糊了本发明，在附图中仅仅示出了根据本发明的方案密切相关的装置结构和/或处理步骤，而省略了本发明关系不大的其它细节。

为了便于本领域技术人员理解本发明实施例的IP分片多核负载均衡装置和方法的一般工作原理，后文将结合在一个具体的WiFi路由器设备上实现RFS场景下的IP分片负载均衡的实施过程具体解释本发明的发明内容。该具体的WiFi路由器的规格和配置为，其WAN侧网口的带宽为2.5Gbps，运行Linux内核，采用单队列网卡，有4个CPU核心，其中0号核心负责处理网卡硬中断，另外3个CPU核心实际执行网络协议栈处理。

图1示出了根据本发明实施例的IP分片多核负载均衡装置的结构示意图，本发明实施例提供一种IP分片多核负载均衡装置，包括：特征提取模块101、分发表102及分发模块103。具体的，本WiFi路由器实施例中，0号核执行IP分片RFS过程，是本发明所述的负载均衡装置，1号/2号/3号核进行IP分片的网络协议栈处理，是本发明所述的处理装置。

所述特征提取模块101，用于提取IP分片首包的IP五元组及IP分片的IP分片三元组。本发明所述IP分片首包是IP报头中Fragment offset字段为0的IP分片；所述IP分片非首包是IP报头中Fragment offset字段不为0的IP分片；所述IP五元组包括源地址、目的地址、源端口号、目的端口号、协议号；所述IP分片三元组包括源地址、目的地址、报文ID；

所述分发表102，用于记录各IP报文的分发结果，采用数组方式进行组织，以IP分片三元组的哈希值作为数组索引；

所述分发模块103，根据特征提取模块101得到的结果将IP分片分发给处理装置；当分发IP分片首包时，根据IP五元组计算得到分发结果，并将分发结果存入分发表102；当分发IP分片非首包时，查询分发表102得到分发结果。

需要强调，当属于同一个IP报文的IP分片非首包早于IP分片首包到达所述特征提取模块时，所述分发表还未记录该IP报文的分发结果时，所述分发模块如何处理。分发模块依然通过IP分片三元组的哈希值索引数组得到分发结果，并对IP分片非首包进行分发，即使此时索引数组得到的分发结果并不是该IP分片所属IP报文的分发结果。

下面结合图2解释本发明做上述处理的原因，图2是本发明所述处理装置处理同一个IP报文不同IP分片时的一般工作流程图，图2中分片1、分片2、分片3……分片n先后到达负载均衡装置。考虑到，通常，处理装置处理IP分片时有分片重组的过程，对一个IP报文的不同IP分片而言，处理先到达的IP分片只需要执行解封头和加入分片缓存的操作，只有处理最后一个到达的IP分片需要额外地执行分片重组、NAT、重新分片、对分出的每个分片重新封头和发送等复杂操作。因此处理一个IP报文最后一个到达的IP分片所需的计算资源占据处理该IP报文所需的总的计算资源的绝大部分比重。而由于一个IP报文中，IP分片首包总不会晚于该IP报文的最后到达的IP分片到达，因此在分发最后到达的IP分片时，分发表一定记录过该IP分片的分发结果。对于早于分片首包到达的IP分片非首包，可以选择随机分发，但综合来看，统一按照分发表中查到的分发结果分发是最简单高效的实施方式。

注意，上述处理方式使得本发明没有实现将IP五元组相同的IP报文所有IP分片分发给同一处理装置处理，仅实现了IP五元组级别的IP分片负载均衡。

同样因为上述处理方式，本发明只适用于处理装置共享内存的场景，典型的是多队列网卡、RPS、RFS对应的多核场景，而无法适应于处理装置不共享内存的多服务器场景，典型的是Nginx网关将服务请求分发给多个后端服务器处理的场景。这是因为，多核场景下，将IP报文的多个IP分片分发给不同核心处理，IP分片依然能完成重组，但多服务器场景下，将IP报文的多个IP分片分发给不同服务器处理，IP分片无法完成重组，IP分片会被丢失。

同样因为上述处理方式，本发明所述IP分片多核负载均衡装置无需分片重组或缓存IP分片，所述分发表无需维护每一个IP报文的IP分片首包是否到达的状态信息。因此本发明实现简单，分发效率高。

为了便于理解，介绍所述处理装置在几种场景下的含义。在多队列网卡场景下，所述负载均衡装置决定IP分片所加入的接收队列，最终IP分片由接收队列绑定的CPU核心处理。在Linux内核的RPS/RFS场景下，所述负载均衡装置决定IP分片所加入的backlogqueue，最终IP分片由backlog queue绑定的CPU核心处理。在这三种场景下，处理装置事实上都是运行对应处理程序的CPU核心。

优选地，为了减少存储分发表所需内存空间，以及简化分发表存取分发结果的操作，本发明所述分发结果用处理装置编号表示，并使用能区分不同处理装置编号的最小2的整数次幂位宽的二进制数编码和存储。比如，若有3个、4个处理装置，分发结果用2bit编码表示，若有5个、6个、7个、8个处理装置，分发结果有4bit编码表示。具体的，WiFi路由器实施例中，有3个处理装置，分发结果用2bit编码表示。

本发明所述由IP分片三元组计算作为数组索引的哈希值所使用的哈希函数由本发明的实施人指定，本装置允许哈希函数将多个不同的IP分片三元组映射到相同的哈希值；本装置以哈希值的所有可能取值的个数作为数组的长度。

需要强调，当装置已经完成一个IP报文的IP分片首包分发（分发表已存在该IP报文的分发结果）但该IP报文仍有其他IP分片未到达装置，此时若另外一个IP分片三元组不同但哈希值相同的IP报文的IP分片首包先到达装置，所述分发模块如何处理。所述分发模块直接将下一个IP报文的分发结果写入分发表数组，效果上等价于，所述分发模块从分发表中丢弃当前IP报文的分发结果而将下一个IP报文的分发结果存入分发表。之后，若当前IP报文的其他IP分片到达装置，所述分发模块按下一个IP报文的分发结果分发当前IP报文的IP分片。

上述处理方式会使得，前一个IP报文的后续IP分片没有分发到对应的处理装置处理，造成处理装置处理时的缓存不命中，降低处理效率。然而，理论分析和实验验证能够知道，当分发表的数组长度足够大（比如大于1024）时，上述情况在实际场景下发生的比例很低，对处理装置处理效率造成的影响可忽略。

为了减少分发表的数组长度，减少处理装置所需的存储资源，同时保证处理装置的处理效率，考虑到实际场景中，相同源IP地址、目的IP地址的连续IP报文的IP ID字段是递增的，本领域的技术人员实施本发明在选择将IP分片三元组映射为数组索引的哈希函数时，优选地，数组索引的低10bit保留IP ID的低10bit，数组索引的高bit由本发明实施人根据具体实施场景设定。具体的，WiFi路由器的实施例中，设定数组索引位宽14bit，内容为IPID的低14bit，因此分发表数组长度为2¹⁴，存储分发表数组的内存空间大小为4KB，后文中该分发表数组记为dispatch[16384]。

下面将结合图3和图4描述特征提取模块101和分发模块103执行的操作。

特征提取模块101提取所有IP分片的IP分片三元组S301，判断输入的IP分片是否为IP分片首包S302，若是，则提取IP分片首包的IP五元组S303。具体的，WiFi路由器实施例中，IP五元组信息用flow_keys数据结构表示，其格式如下表（一）所示：

表（一）

提取IP分片三元组时直接存储IP分片三元组对应的哈希值，连同IP分片是否是IP分片首包的标识信息一起用frag_cb数据结构表示，其格式如下表（二）所示：

表（二）

所述由IP五元组计算分发结果的计算或映射规则由本发明的实施人自由指定。具体的，本WiFi路由器实施例中，选择的映射规则为cpu_core = siphash(key) % 3 + 1，其中key是一个具体的IP五元组，是一个flow_keys类型的变量，siphash是Linux 5.4内核进行RPS时使用的哈希函数，得到分发结果记为cpu_core，即CPU编号1/2/3。分发模块103的输入是特征提取模块101得到的IP五元组（flow_keys类型的变量key）和/或IP分片三元组（frag_cb类型的变量cb）。分发模块103执行如下操作，

1)判断输入的IP分片是否为IP分片首包S401；具体的，本实例中，即检查cb的is_first字段是否置位。

2)若是，则根据IP五元组计算得到分发结果S402；具体的，本实例中，即执行cpu_core = siphash(key) % 3 + 1。

3)而后，将分发结果存入分发表S403；具体的，本实例中，即执行dispatch[cb.index] = cpu_core。

4)若判断输入的IP分片不是分片首包，则以IP分片三元组查找分发表，按查询的分发结果进行分发S404；具体的，本实例中，即执行cpu_core = dispatch[cb.index]。

本发明申请人在完成所述WiFi路由器实施例后，实验验证，各处理装置的CPU使用量相近，负载均衡效果好；相比Linux内核原有的RPS方案，未显著增加处理相同吞吐量分片流时处理装置总的CPU使用资源，说明分发后，处理装置处理时程序局部性好，处理效率高；相比Linux内核原有的RPS方案，负载均衡装置仅多消耗了0.5%的CPU资源，说明本发明分发效率高。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、服务器或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质（包括但不限于磁盘存储器和光学存储器等）上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备（系统）、服务器和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

Claims (6)

1.一种IP分片多核负载均衡装置，其特征在于，包括：特征提取模块、分发表、分发模块；

所述特征提取模块，用于提取IP分片首包的IP五元组及IP分片的IP分片三元组；

其中，IP分片首包是IP报头中Fragment offset字段为0的IP分片；IP分片非首包是IP报头中Fragment offset字段不为0的IP分片；IP五元组包括源地址、目的地址、源端口号、目的端口号、协议号；IP分片三元组包括源地址、目的地址、报文ID；

所述分发表，用于记录各IP报文的分发结果，采用数组方式进行组织，以IP分片三元组的哈希值作为数组索引；

所述分发模块，根据特征提取模块得到的结果将IP分片分发给处理装置；当分发IP分片首包时，根据IP五元组计算得到分发结果，并将分发结果存入分发表；当分发IP分片非首包时，查询分发表得到分发结果。

2.根据权利要求1所述的IP分片多核负载均衡装置，其特征在于，当属于同一个IP报文的IP分片非首包早于IP分片首包到达所述特征提取模块时，所述分发表还未记录该IP报文的分发结果，所述分发模块依然通过IP分片三元组的哈希值索引数组得到分发结果，并对IP分片非首包进行分发。

3.根据权利要求1所述的IP分片多核负载均衡装置，其特征在于，所述分发结果用处理装置编号表示，并使用能区分不同处理装置编号的最小2的整数次幂位宽的二进制数编码和存储。

4.根据权利要求1所述的IP分片多核负载均衡装置，其特征在于，所述分发表允许多个不同IP分片三元组计算得到相同的哈希值，以哈希值所有不同取值的个数作为数组的长度。

5.根据权利要求1所述的IP分片多核负载均衡装置，其特征在于，当所述分发模块已经完成一个IP报文的IP分片首包分发，但仍有属于当前IP报文的其他IP分片未到达所述特征提取模块，此时若IP分片三元组不同但哈希值相同的下一个IP报文的IP分片首包先到达时，则所述分发模块从分发表中丢弃当前IP报文的分发结果而将下一个IP报文的分发结果存入分发表，之后，若当前IP报文的其他IP分片到达时，所述分发模块按下一个IP报文的分发结果分发当前IP报文的IP分片。

6.一种IP分片多核负载均衡方法，其特征在于，包括以下步骤：

从IP分片提取分发所需的特征；

根据提取到的特征对IP分片进行分发；

所述从IP分片提取分发所需的特征步骤，具体包括如下步骤：

提取IP分片的IP分片三元组；

判断输入的IP分片是否为IP分片首包，若是，则提取IP分片首包的IP五元组；

所述根据提取到的特征对IP分片进行分发步骤，具体包括如下步骤：

步骤一，判断输入的IP分片是否是IP分片首包，若是，则根据IP五元组计算得到分发结果，并将分发结果存入分发表，完成分发，否则转步骤二；

步骤二，以IP分片三元组查找分发表，按查询的分发结果进行分发；

其中，所述分发表记录各IP报文的分发结果，采用数组方式进行组织，以IP分片三元组的哈希值作为数组索引。