转载和积累系列 - L4负载均衡的设计与实现
目录
简介
负载均衡分为L4负载均衡（例如LVS）、L7负载均衡（例如nginx），L4负载均衡工作在传输层其主要功能就是转发， 本文讲述的负载均衡为L4。
传统上通过采购硬件的负载均衡（例如F5）作为L4转发，部署一个高可用集群需要数台硬件设备进行冗余，能用钱解决的问题都不是问题。
这里我们讨论的是如何用软件实现一个高性能的L4负载均衡，下面将讲述Google、Facebook等大厂如何用软件方式实现高性能的负载均衡，我们需要学习大厂经验后去实现设计一款高性能的L4负载均衡。
一、LVS的局限性
1. 数据包转发性能问题
LVS是基于内核netfilter开发的应用程序，而netfilter是运行在内核协议栈的一个hook框架，这就意味着当数据包到达LVS时，已经经过了一段很长的协议栈处理。
中断是影响LVS性能最重要的一个因素，假如我们一秒需要处理600万的数据包，每6个数据包产生一个硬件中断的话，那一秒就会产生100万个硬件中断， 每一次产生硬件中断都会打断正在进行密集计算的负载均衡程序，中间产生大量的cache miss，对性能的影响异常大。
针对这两个问题，解决方法是使用轮询模式的驱动以及做kernelbypass，而DPDK提供的用户态PMD驱动恰好可以解决这两个问题。国内知名的互联网企业不约而同使用了DPDK加速数据包转发性能，DPDK PMD模型很好的解决内核中断问题。
下文将提到Facebook用到最新的内核技术XDP进行更高速的数据包加速。
2. HA-主备结构的浪费
LVS本身没有高可用相关的设计，传统上利用keepaalived+LVS部署主备结构，用于防止单点故障，实现服务的高可用或热备。
keepalived顾名思义就是保持在线，通过VRRP协议实现多台机器之间的故障转移服务。
VRRP是一种路由容错协议，也可以叫做备份路由协议，它保证当主机的下一跳路由器出现故障时，由另一台路由器来代替出现故障的路由器进行工作，从而保持网络通信的连续性和可靠性。
利用VRRP进行LB主备，当巨大的流量流入时单节点就捉襟见肘了，所以就需要部署多套keepalived+LVS，永远都有一半机器处于backup状态，主备模式利用率低，不能横向平行扩展。
3. 转发模式的优缺点
LVS实现了四种转发模式：NAT、DR、TUNNEL、FULLNAT，8种连接调度算法，对LVS的转发模式比较熟的读者可以跳过本节。
DR模式性能较高，回程报文不需要经过LVS，能保留源IP地址；缺点：RealServer 和 LVS 在必须同一个VLAN中，不支持端口映射，大规模应用有困难。
NAT请求和响应都需要通过LVS，后端伸缩能力有限，容易形成性能瓶颈，只适用于小并发的实验性应用。
TUNNEL模式服务器和调度器可以跨VLAN，但RealServer上需要部署 IP/IP模块等，网络需要连通外网，不需要调度应答报文，负载能力强
FULLNAT最大的问题是丢失源IP信息，相比于NAT的局域网，FULLNAT是相对于没有那么局限，它是限制在内网中的，对于运维比较方便。
二、google maglev负载均衡
maglev每天为超过10亿用户提供服务。为了提供这些服务的最佳可用性和用户体验，Google设计的均衡基础架构中按需扩展，有效利用资源，确保安全性并针对延迟进行了优化。
与传统的负载平衡解决方案不同，Google的每个负载均衡解决方案均设计为可扩展且具有高度弹性的大规模分布式软件定义系统。
Maglev Consistent Hash
自2008年开始投入生产以来，Maglevs负载均衡了Google数据中心的所有流量，并将流量分配到网络边缘的前端引擎。使用由源和目标IP地址，协议以及源和目标端口组成的5元组哈希将第4层流量分发到一组区域后端实例。
核心路由通过ECMP协议来将网络包均匀的发送给maglev节点，借助于Maglev Consistent Hash均分流量。
Maglev是传统负载均衡器的一个突破，它是基于软件的，并在主动横向扩展架构中运行。借助Maglev Consistent Hash，基于Maglev的负载均衡器将流量平均分配到数百个后端，并最大程度地减少了意外错误对面向连接的协议的负面影响。
Maglev hashing的核心思想是，让每个后端服务实例按照一定的规则去填满lookup table中的空位(偏好位置)，确保所构造出来的lookup table的元素中，所有后端服务器出现的次数尽可能相等，以达到流量均衡的目的。
假设M为表的大小，每个服务节点的偏好列表被保存在permutation[i]中，偏好列表是一个随机的序列，取值为[0,m-1]。为了生成这个序列，我们首先为每个服务节点起一个名字。然后用两种不同的hash算法计算名字的hash值，分别作为offset和skip。最后用这两个值来生成序列M必须是一个素数以保证skip的值是和M互质的。
假设N为单个服务的后端实例的数量。next[i]表示后端服务实例i在permutation[i]中的下一个入口。按下面的伪码可生成最终的lookup table。
该算法的平均时间复杂度为 O(MlogM)，最差时间复杂度为 O(M^2)。当后端服务实例个数和 lookup table 大小一致，且所有后端服务实例 hash 后的排列一致时，为最差场景，因而在M的取值上，应当保证MN。
Google下一步是什么？
Google是Envoy和Istio开源计划的重要贡献者。为了实现业务敏捷性，许多人正在从单一应用程序过渡到微服务，寻求一种统一的方式来创建和管理具有安全性，可观察性和弹性的异构和多云服务。
这就是ServiceMesh用武之地，可为包括负载均衡在内的服务提供软件定义的网络（SDN）。使用Service Mesh，网络复杂性被抽象到服务网格的数据平面，该数据平面通过诸如Envoy之类的服务代理实现，使您可以*地专注于构建业务逻辑。Envoy是一种高性能，功能丰富且开源的服务网格数据平面。
三、facebook katran
第一代 L4LB
他们使用了简单的IP-in-IP封装，这样就可以将L4LB和后端主机放置在不同的机架中。他们使用了IPVS内核模块，后端服务器的回送接口上配置了相应的VIP，所以它们可以将返回的数据包直接发送到客户端（而不是 L4LB）。
Katran ：利用XDP更高速处理数据包
facebook利用了两项最新的内核工程技术XDP与eBPF研发新一代负载均衡：Katran，通过完全重新设计转发面板，显著提高之前版本的性能，主要开发语言为cpp。
K8S开源网络组件cilium也使用到同样的技术，社区火热，由于依赖Linux 4.16+版本内核，该项内核优化并没有大范围在国内厂商使用。
XDP提供了一种高速的可编程网络数据路径，无需使用完整的内核旁路方法，并可与 Linux 网络栈结合使用，附录链接提供了BPF+XDP实战指南。
eBPF虚拟机：提供了一种灵活、高效且更可靠的方式来与 Linux 内核进行交互，并通过在内核中的特定点运行用户程序来扩展功能。eBPF 已经为几个领域带来了巨大的改进，包括追踪和过滤，高性能程序来转发数据包。在驱动器模式下启用 XDP 时，数据包处理例程（BPF 程序）会在网络接口卡（NIC）收到数据包之后以及在内核截获之前运行。XDP在每个传入数据包上调用BPF程序。如果 NIC 具有多个队列，则为每个队列并行调用该程序。用于处理数据包的 BPF 程序是无锁的，并使用单 CPU 内核版本的 BPF 映射。因为具备了这种并行性，性能与 NIC 的 RX 队列数量呈线性关系。
开销更小的哈希：Katran 使用google Maglev 哈希算法的扩展版来选择后端服务器。扩展版哈希算法具备了更好的弹性，能够更均匀的分布负载，可以为不同的后端服务器设置不同的权重。
其中最后一项最为重要，他们因此能够轻松处理 PoP 和数Packet Proces据中心的硬件更新：通过设置适当的权重来更新硬件。计算哈希值的代码体积很小，完全可以放入 L1 缓存中。
更具弹性的本地状态：Katran 在处理数据包和计算哈希值时需要与本地状态表发生交互。他们发现，通常情况下，计算哈希值比查找本地状态表中的5元组更容易，因为在本地状态表中有时候需要遍历到最后一级缓存才能找到目标。为此，他们将查找表实现为 LRU 缓存。LRU 缓存大小可在启动时配置，并作为可调参数，以便在计算和查找之间取得平衡。此外Katran 提供了一个运行时“仅计算”开关，以便在主机发生灾难性内存压力的情况下完全忽略 LRU 缓存。
RSS 封装：接收端伸缩（Received Side Scaling，RSS）是针对 NIC 的一项重要优化，旨在通过将数据包发送到单独的 CPU 来均匀地在 CPU 之间分布负载。
不同流中的数据包使用不同的外部 IP 来封装，但相同流中的数据包总是被分配相同的外部 IP。
四、设计高性能负载均衡
在大流量的数据中心, 在业务快速增加的情况下，随着架构变化（物理机、虚拟机到容器），用户所需的负载均衡功能的部署时间变得越来越短。为了应对这种挑战，实现网络化的敏捷性，建立具有管理系统的可扩展性软件L4负载平衡器集群是非常必要的。
软件定义的负载均衡，它不基于实例或设备的解决方案，因此不会受限于负载均衡的基础架构，也不用面对基于实例的负均衡的固有的HA、规模和管理难题。
无缝的自动扩缩随着用户和流量的增长而调整，轻松处理数量巨大的瞬间意外峰值。自动扩缩功能无需预热，您可以在短短几秒的时间里从零调节至所需的容量。
本章将讲述基于Fd.io VPP加速实现可扩展的L3DSR L4LB系统， 它不仅提供了线性、快速、可扩展的转发性能，而且还提供了LB群集的快速部署和稳定运行，在数据中心的Clos架构上实现零停机。
高速数据包处理 ：基于VPP-DPDK
DPDK开源的数据处理项目，它允许通过绕开Linux内核从用户空间进行非常快速的数据包处理。
VPP运行于用户空间，支持多种收包方式，常用的是DPDK，VPP主要有两个主要功能：框架可展；成熟的交换/路由功能。VPP配套完善的文档、控制端、丰富网络协议栈支持。
DPDK 提供函数库充分利用 CPU 和网卡的能力从而达到了单机 10G 线速的转发性能。
-
用户空间驱动，完全 Zero-Copy；
-
采用批处理摊销单个报文处理的成本；
-
充分利用硬件特性；
-
Intel DataDirect I/OTechnology (Intel DDIO)
-
NUMA
-
Huge Pages，CacheAlignment，Memory channel use
通过 RSS 直接将网卡队列和 CPU Core 绑定，消除线程的上下文切换带来的开销，线程间采用高并发无锁的消息队列通信。
通过DPDK实现在具有商用CPU的商用NIC上实现NIC线路速率处理，并轻松扩展调度层，以处理大量的入站流量。这在DDoS攻击中尤为重要，避免负载均衡调度器成为网络瓶颈。
现代NIC都支持SR-IOV，使用这种技术可以使单个NIC从操作系统的角度看起来像多个NIC。
下图为国内某公司用DPDK实现LB性能比对图：
水平扩展：基于ECMP+BGP+Maglev
通常情况下，每一个IP地址都指向单台物理机器，将路由器视为将数据包移动到下一个最靠近该机器的路由器。在最简单的情况下，总是有一个最佳的下一跳，
路由器选择该跳并将所有网络数据包转发过去，直到到达到目的地。L4负载均衡的基本属性是能够获取单个IP地址并在多个服务器之间传播入站连接。
为了扩展单个IP地址以处理比任何一台机器可以处理的流量更多的流量，需要在后端服务器之间进行分流，还需要能够扩展自己处理负载平衡的服务器。
ECMP(Equal-costmulti-path)
数据中心的网络拓扑通常采用CLOS结构，主机之间常存在多条路径。数据中心为满足吞吐量敏感型流量的需求会提供大量的带宽资源。
那么利用数据中心这种网络拓扑已知，路径资源、带宽资源丰富的特性，可以更好的实现负载均衡，将数据流分布到不同路径上进行数据传输，避免拥塞，提高数据中心内的资源利用率。
ECMP是一个逐跳的基于流的负载均衡策略，当路由器发现同一目的地址出现多个最优路径时，会更新路由表，为此目的地址添加多条规则，对应于多个下一跳。可同时利用这些路径转发数据，增加带宽。
当开启ECMP功能时，便可同时利用两条路径，进行基于流的负载均衡。
BGP
每个服务器都可以使用BGP网络协议宣布相同的IP地址，从而使连接在这些服务器之间进行分片，路由器就可以自动将流量分发到不同多台实际服务器。
这种方法可以实现流量负载均衡的需求，但它有一个巨大的缺点：当集群下的服务器（或沿途的任何路径或路由器发生变化）时，连接必须适配以保持平衡的连接每个服务器。
路由器通常是无状态设备，只是为每个数据包做出最佳决策而不考虑它所属的连接，所以在这种情况下某些连接会中断。
路由器努力调整一致性哈希，将1/3连接移动到新服务器，同时保持2/3连接。问题是，对于那些已经发出的1/3连接，数据包现在到达了不知道连接的服务器，因此会失败丢包。
Maglev ConsistentHash
上面详细介绍了Google Maglev Consistent Hash对LB的显著影响，将流量平均分配到数百个后端，最大程度地减少了意外错误对面向连接的协议的负面影响。
查阅了大部分厂商公开的资料，基本上都借鉴使用了Google Maglev Consistent Hash用于LB服务。
转发模式：基于L3DSR
上文我们盘点了LVS多种转发模式， 其中DR模型性能最好，但是其缺陷是只能在同vlan下工作， yahoo公司在很多年前设计出L3DSR。
DR模型需要通过负载平衡器和所有位于相同2层广播域内 Virtual IP 上的主机进行网络通信，但是这有一个严重的限制，它会严重阻碍单个连续的单个子网上扩展到规模型的VIP服务。
L3DSR克服了上述的限制。相比其他3层负载均衡方法，L3DSR允许雅虎在单个硬件负载平衡器上同时服务十多倍的 VIPs。
为了克服2层的限制，使用IPv4头部校验上的6位DSCP（6-bit Differentiated Services Code Point） 来传输消息到服务器上。服务器检测头部校验并基于 DSCP 映射到目的地的值改写目的地址。
容错设计：健康检查和故障自动转移
故障的处理是负载均衡重要的功能， 对于给定的转发表条目/客户端具有指定的主次服务器的设计，可以通过从每个调度器来运行健康检查来解决单点故障。
通过运行一个名为healthcheck的服务，它不断验证每个后端服务器的任意HTTP端口， 该模块可复用部分k8s提供的健康检查代码。
当服务器出现故障时，通过将交换主/次服务器，对服务器执行"软释放"，这为连接进行正常故障转移提供了最佳机会。如果健康检查失败是误报，则连接不会收到任何影响，它们只会漏了一条稍微不同的路径。
附录：
VPP
2016年2月11号，Linux基金会创建FD.io项目。Cisco将VPP代码的开源版本加入该项目，目前已成为该项目的核心。
VPP平台可以用于构建任何类型的数据包处理应用。比如负载均衡、防火墙、IDS、主机栈，也可以是一个组合，比如给负载均衡添加一个vSwitch。
DPDK
全称为Date planedevelopment kit，是一个用来进行包数据处理加速的软件库。与传统的数据包处理相比，DPDK具有以下特点：
-
轮询：在包处理时避免中断上下文切换的开销
-
用户态驱动：规避不必要的内存拷贝和系统调用，便于快速迭代优化
-
亲和性与独占：特定任务可以被指定只在某个核上工作，避免线程存多通道交错访问提高内存访问有效带宽
-
软件调优：cache行对齐，预取数据，多元数据批量操作
netfilter
提供一整套的hook函数的管理机制，使得诸如数据包过滤、网络地址转换(NAT)和基于协议类型的连接跟踪
来源
[1]Maglev: A Fast andReliable Software Network Load Balancer
[2]LVS介绍: https://www.cnblogs.com/centos2017/p/8024180.html
[3]DPDK:https://dpdk.org/
[4]VPP: https://fdio.org/
[5]Katran: https://github.com/facebookincubator/katran
[6]BPF 和 XDP 参考指南：http://arthurchiao.art/blog/cilium-bpf-xdp-reference-guide-zh/
[7]Vortex:https://www.infoq.cn/article/Maglev-Vortex/
注：本文参考了多家方案与论文，时间关系参考来源内容和依据未能一一注明