GitHub的开源调度器GLB

GitHub平台每时每刻都有大量的请求访问，那么Github如何解决这种流量调度和负载均衡的呢？其实Github使用的是一套自研的基于ECMP，目标服务器IP的一致性哈希的调度系统GLB。此前GitHub已经开源了他们的调度系统（github：/github/glb-director），所以虫虫今天就给大家说说GitHub的开源调度系统GLB。

GitHub开源的GLB，主要针对裸机数据中心的可扩展负载平衡解决方案，目前绝大多数的GitHub的公共Web和git流量都通过GLB来运行，还提供其一些内部系统的流量调度。

GLB调度系统是运行在TCP/IP第4层负载均衡器，可在大量物理机器上扩展单个IP地址，可以实现不间断服务的对集群中的代理机器动态增删。 也支持对调度其的横向扩展。

使用ECMP扩展IP

4层负载均衡器的基本属性是能够获取单个IP地址并在多个服务器之间传播入站连接。为了扩展单个IP地址以处理比任何一台机器可以处理的流量更多的流量，需要在后端服务器之间进行分流，还需要能够扩展自己处理负载平衡的服务器。

通常情况下，每一个IP地址都指向单台物理机器，将路由器视为将数据包移动到下一个最靠近该机器的路由器。在最简单的情况下，总是有一个最佳的下一跳，路由器选择该跳并将所有网络数据包转发过去，直到到达到目的地。

实际上，大多数网络都要比这复杂。两台计算机之间通常有多条路径可用，例如，多个ISP可用，或者两台路由器通过多条物理电缆连接在一起，以增加容量并提供冗余。这就是为什么要引入等价多路径（ECMP）发挥作用的地方，通过ECMP，而不是路由器选择单个最佳下一跳，其中它们具有相同成本的多跳（通常定义为到目的地的AS的数量），它们通过其散列引流，以便在所有可用的同成本路径之间平衡连接。

通过对每个数据包进行散列来确定ECMP，以确定其中一个可用路径的相对一致的选择。计算哈希所用的函数因设备而异，一般是基于源和目标IP地址以及TCP流量的源和目标端口的一致性哈希。这样同一个正在进行的TCP连接的多个数据包通常会运行在相同的路径，即使路径具有不同的延迟，数据包也会以相同的顺序到达。值得注意的是，在这种情况下，路径可以在不中断连接的情况下进行更改，因为它们总是最终位于同一个目标服务器上，此时它所使用的路径大多无关紧要。

当我们想要跨多个服务器而不是通过多个路径到同一服务器的流量时，可以使用ECMP的替代方法。每个服务器都可以使用BGP或其他类似的网络协议宣布相同的IP地址，从而使连接在这些服务器之间进行分片，路由器就可以自动将流量分发到不同多台实际服务器。

这种方法可以实现流量负载均衡的需求，但它有一个巨大的缺点：当集群下的服务器（或沿途的任何路径或路由器发生变化）时，连接必须适配以保持平衡的连接每个服务器。路由器通常是无状态设备，只是为每个数据包做出最佳决策而不考虑它所属的连接，所以在这种情况下某些连接会中断。

在左边的上面的例子中，我们可以想象每种颜色代表一个活动的连接。添加新的代理服务器以宣布相同的IP。路由器努力调整一致性哈希，将1/3连接移动到新服务器，同时保持2/3连接。问题是，对于那些已经发出的1/3连接，数据包现在到达了不知道连接的服务器，因此会失败丢包。

拆分调度层/代理负载平衡器

以前仅使用ECMP的解决方案的问题在于它不知道给定数据包的完整上下文，也不能为每个数据包/连接存储数据。在现实中，通常使用Linux LVS 之类的工具，通过在软件中实现一些状态跟踪来帮助解决这种情况。GLB则是创建了一个新的调度层，它通过ECMP从路由器获取数据包，但不是依靠路由器的ECMP散列来选择后端代理服务器，而是通过调度层来控制散列和存储状态（选择了后端）所有正在进行的连接。当代理层服务器集有变化时，调度层不会变化，所以保证连接不会丢失。

虽然这在许多情况下效果很好，但也有一些缺点。在上面的示例中，我们同时添加了LVS控制器和后端代理服务器。新的控制器收到一些数据包，但还没有任何状态（或具有延迟状态），因此将其作为新连接进行哈希处理并可能使其出错（并导致连接失败）。 LVS的典型解决方法是使用多播连接同步来保持所有LVS控制器服务器之间共享的连接状态。这需要传播连接状态，并且仍然需要重复状态，不仅每个代理都需要Linux内核网络堆栈中每个连接的状态，而且每个LVS控制器还需要存储连接到后端代理服务器的映射。

从调度层删除状态

GLB通过使用已存储在代理服务器中的流状态作为维护来自客户端的已建立Linux TCP连接的一部分。

对于每个新访问的连接，GLB选择可以处理该连接的主服务器和辅助服务器。当数据包到达主服务器且无效时，会将数据包转发到辅助服务器。选择主/辅助服务器的散列是访问时候生成一次，并存储在调度表中，不需要在每个流或每个数据包的重新计算。添加新的代理服务器时，对于1/N连接，它将成为新的主服务器，旧的主服务器将成为辅助服务器。这允许现有连接完成，因为代理服务器可以使用其本地状态（单一事实来源）做出决策。从本质上讲，这使得数据包在到达保持其状态的预期服务器时具有可以有备选服务器。

即使调度器仍然会将连接发送到错误的服务器，该服务器也知道如何将数据包转发到正确的服务器。就TCP数据流而言，GLB调度层是完全无状态的：调度器服务器可以随时增减，并且总是选择相同的主/辅服务器，只需匹配调度表既可。

调度表：集群散列维护

GLB调度器设计的核心归结为始终如一地选择主服务器和辅助服务器，并允许代理层服务器根据需要增加和删除。每个代理服务器都有一个状态，通过调整状态作为添加和删除服务器的方法。

创建一个静态二进制转发表，它在每个控制器服务器上以相同方式生成，以将新建连接映射到给定的主服务器和辅助服务器。通过调度表匹配每一个链接，该表每行包含主服务器和辅助服务器IP地址。它作为二进制扁平数组存储在内存中，每个表大约512kb。当数据包到达时，计算其散列匹配到该表中的同一行（使用散列作为数组的索引），从而提供了一致的主服务器和辅助服务器对。

每个服务器在主要和辅助字段中大致相同，并且永远不会出现在同一行中。当添加新服务器时，调整某些行使其主服务器成为辅助服务器，并且新服务器将成为主服务器。同样，删除服务器时，在它是主服务器的任何行中，调整改行辅助服务器成为主服务器，而另一个服务器则成为辅助服务器。基本规则如下：

当更改服务器集时，应保持现有服务器的相对顺序。

服务器的顺序应该是可计算的，除了服务器列表之外没有任何其他状态。

每个服务器在每行中最多应出现一次。

每个服务器在每列中的出现次数应大致相同。

为了满足这些条件， GLB选择了Rendezvous哈希算法，每个服务器都与行号一起进行散列，服务器按该散列进行排序，并且获得该给定行的服务器的唯一顺序。分别将前两个作为主要和次要服务器。无论包含哪些其他服务器，每个服务器的哈希都是相同的。生成表所需的唯一信息是服务器IP。由于只是对一组服务器进行排序，因此服务器只出现一次。最后，如果我们使用随机散列函数，则排序将是随机（伪随机数），其分布符合均匀分布，可以保证调度的负载均衡。

DPDK用于10G +线速数据包处理

GLB还使用一个开源的数据处理项目DPDK，它允许通过绕开Linux内核从用户空间进行非常快速的数据包处理。通过DPDK实现在具有商用CPU的商用NIC上实现NIC线路速率处理，并允许轻松扩展调度层，以处理大量的入站流量。这在DDoS攻击中尤为重要，避免负载均衡调度器成为网络瓶颈。

GLB最初的目标之一是负载均衡器可以在商用数据中心硬件上运行，而无需任何特定于服务器的物理配置。 GLB调度器和代理服务器都和数据中心的其他普通服务器一样。每个服务器都有一对绑定的网卡，这些网卡在GLB调度器服务器上的DPDK和Linux之间共享。

现代NIC都支持SR-IOV，使用这种技术可以使单个NIC从操作系统的角度看起来像多个NIC。这通常由虚拟机管理程序使用，以要求真实NIC为每个VM创建多个虚拟NIC。为了使DPDK和Linux内核能够共享NIC，GLB使用flow bifurcation，它将特定流量发送到虚拟功能的DPDK进程，同时将其余数据包留给Linux内核的网络堆栈。

GLB调度器使用DPDK数据包分发器模式将数据包封装在机器上的任意数量的CPU核心上，并且由于它是无状态的，因此可以高度并行处理。

GLB调度器通过在匹配期间对数据包的内层洞悉，支持匹配和转发包含TCP有效负载的入站IPv4和IPv6数据包，以及用作路径MTU发现的一部分的入站ICMP分段请求消息。

健康检查和故障自动转移

GLB设计时候还考虑了对服务器故障处理。对于给定的转发表条目/客户端具有指定的主次服务器的设计，可以通过从每个调度器来运行健康检查来解决单点故障。通过运行一个名为glb-healthcheck的服务，它不断验证每个后端服务器的GUE隧道和任意HTTP端口。

当服务器出现故障时，通过将交换主/次服务器，对服务器执行"软释放"，这为连接进行正常故障转移提供了最佳机会。如果健康检查失败是误报，则连接不会收到任何影响，它们只会漏了一条稍微不同的路径。

使用iptables实现二次调度

GLB的最后一个组件是运行在每一台代理节点上的Netfilter模块和iptables，提供"第二次机会"来实现正确调度。

此模块提供了一个简单的任务，根据Linux内核TCP堆栈确定每个GUE数据包内的内部TCP/IP数据包是否在本地有效，如果不是，则将其转发到下一个代理服务器（辅助服务器）而不会在本地对其解包。

在数据包是SYN（新连接）或在本地对已建立的连接有效的情况下，它会在本地接受它。然后，我们使用作为Linux内核4.x GUE提供的fou模块来接收GUE数据包并在本地处理它。