maglev

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

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 由控制器（Controller）和转发器（Forwarder）组成：

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

转发器的设计和实现

Google Maglev 转发器结构”>}}

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

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

Google Maglev 快速包处理”>}}

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

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

对于 Seering：

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

对于 Muxing：

网卡将 Sent 所指的数据包发出去，并向前移动指针。
将被重写的数据包放入队列中，并向前移动 Ready 指针。
同时将已被发送的包归回给数据包池，并向前移动 Recycled 指针。
整个过程都没有包拷贝。

后端选择

Maglev首先检查本地的连接跟踪表，看看该数据包是否属于任何一个已有的连接，如果连接已经建立，则直接将数据包发到该连接对应的服务器上去。

如果连接没有建立，此时就需要一致性哈希函数选择一个后端服务器了，并添加到连接跟踪表。

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

有一个共享的Entry表，可以通过Entry[Hash % M]选择对应后端，M为Entry表大小。
每个后端对所有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。
以此类推，直至填满。