Google Maglev 简介

Google Maglev 是一个牛逼的负载均衡器,之所以牛逼,是因为它不用部署专门的物理设备,不像 LVS 一样工作在内核,它是运行在通用 Linux 服务器上的大型分布式软件系统。

Google Maglev 工作流程

Google Maglev 工作流程

每个 Google 服务都有一个或者多个 VIP,一个 VIP 和物理 IP 的区别在于 VIP 没有绑给某个特定的网卡。

VIP 宣告:

Maglev 关联每个 VIP 到具体的 Endpoint,然后通过 BGP 将 VIP 宣告给上游路由器,然后路由器再把 VIP 宣告给 Google 的骨干网,这样使得 VIP 能被访问到。

当用户访问 www.google.com 时:

  • 浏览器先发送一个 DNS 请求, DNS 服务返回 VIP。 然后浏览器尝试与该 VIP 建立连接。
  • 当路由器接收到 VIP 数据包,通过 ECMP 将数据包路由到 Maglev 集群中的某台机器上。
  • 当 Maglev 的机器接收到数据包, 从关联到该 VIP 的 Endpoint 中选择一个, 然后用 GRE 封包发送,外层的 IP 即 Endpoint 的物理 IP。
  • 当 Endpoint 处理完数据包进行响应时,源地址用 VIP 填充,目的地址为用户 IP。 使用直接服务返回(Direct Server Return, DSR) ,将响应直接发送给路由器, 这样 Maglev 无需处理响应包。

Google Maglev 结构

Maglev 结构

Maglev 由控制器(Controller)和 转发器(Forwarder)组成:

  • 控制器向路由器宣告 VIP。控制器周期性地检查转发器的健康状态,来宣告或者撤回 VIP。确保路由器只转发包到健康的 Magvel。
  • 转发器转发 VIP 流量到 Endpoint。每个 VIP 都有一个后端池(BP),BP 可能包含 Endpoint 的 IP,也有可能包含其它 BP。每个 BP 会对 Endpoint 进行健康检查,保证数据包转发到健康的 Endpoint。

转发器的设计和实现

转发器结构

转发器结构

转发器直接从网卡接收数据包,通过 GRE/IP 封包,再将它们发回网卡。 Linux 内核不参与这个过程。

  • Steering 处理从 NIC(网卡)接收来的数据包,通过五元组(IP地址,源端口,目的IP地址,目的端口和传输层协议)哈希,然后交给不同的接收队列。
  • 包重写线程从接收队列取包,然后进行后端选择,用 GRE 封包后,发送到传输队列。
  • Muxing 轮询从所有的传输队列取包,再发送给网卡。

快速包处理

转发器包处理

Maglev 在包处理时绕开了 Linux 内核,因为内核开销非常严重。

如图,转发器和网卡共用数据包池(Packet Pool),转发器中的 Steering 和 Muxing 都通过指针的环形队列,指向该池。

对于 Seering:

  • 当网卡接收到数据包时,放在 Recieved 所指位置,并向前移动指针。
  • 分发包到接收队列时,向前移动Processed 指针。
  • 预留未使用数据包,放入队列中并向前移动 Reserved 指针。

对于 Muxing:

  • 网卡将 Sent 所指的数据包发出去,并向前移动指针。
  • 将被重写的数据包放入队列中,并向前移动 Ready 指针。
  • 同时将已被发送的包归回给数据包池,并向前移动 Recycled 指针。

整个过程都没有包拷贝。

后端选择

Maglev首先检查本地的连接跟踪表,看看该数据包是否属于任何一个已有的连接,如果连接已经建立,则直接将数据包发到该连接对应的服务器上去。如果连接没有建立,此时就需要一致性哈希函数选择一个后端服务器了,并添加到连接跟踪表。

Maglev 一致性哈希的基本思想就是:

  • 有一个共享的Entry表,可以通过Entry[Hash % M]选择对应后端,MEntry表大小。
  • 每个后端对所有Entry表位置有自己的优先级排序,存在permutation表里。
  • 所有的后端通过优先级顺序轮流填充Entry 中的空白位置,直至填满。每次都填充自己优先级最高的空位置。

例如,假设M = 6,且

B0: permutation[] = { 3, 0, 4, 1, 5, 2, 6 }
B1: permutation[] = { 0, 2, 4, 6, 1, 3, 5 }
B2: permutation[] = { 3, 4, 5, 6, 0, 1, 2 }

permutation优先级是从大到小,那么最后填充后的Entry表为:

Entry[] = { B1, B0, B1, B0, B2, B2, B0 }

说明:

  • B0 的优先级最高的位置是Entry[3],其为空,则Entry[3] = B0
  • B1 是Entry[0],则Entry[0]=B1
  • B2 是Entry[3],但是已被占,下一个是Entry[4],为空,则Entry[4]=B2
  • 以此类推,直至填满。

操作经验

VIP 匹配

VIP匹配

有时候,我们需要利用 Maglev 封包将流量重定向到其他的集群中的相同服务,这就有点麻烦了,因为集群间是独立的,我们不知道其它集群相同服务的 VIP。

VIP 可以通过最长前缀匹配,来决定集群,利用最长后缀匹配决定那个后端池。

如图中的例子,当请求 173.194.71.1 时,通过最长前缀(173.194.71.0/24)选择 C2 集群,通过最长后缀(0.0.0.1/8)决定是 Service 1 后端池。

假定 Maglev 需要将流量转发到 C3(173.194.72.0/24),只需要用相同的后缀构造出 VIP (173.194.72.1)进行转发,即可转发到 Maglev 的 Service 1 后端池。

分片处理

分片时,非首个分片只包含三元组(目的IP地址,目的端口和传输层协议),这便无法正确决定如何转发,因为转发根据的是五元组。

解决方法是:

每个 Maglev 配置了一个特殊的后端池,包含所有的 Maglev 机器。

一旦接收到分片, Maglev 用三元组哈希选择特定的 Maglev 作为后端进行转发,将它们重定向给相同的 Maglev。

Maglev 为未分片数据包和第二跳的首分片使用相同的后端决策算法,以保证非分片、首个分片和非首个分片选择同一个后端。

Magelv 维护了一个固定大小的分片表,记录了首分片的转发决策。 当 Maglev 收到一个第二跳非首分片, 会从分片表中查找,若匹配则立即转发; 否则,会缓存到分片表中,直到首分片收到或者老化。