preface

github 去年8月份开源了自家的 load balance策略, 主要解决ecmp情况下增删服务器导致的in-progress连接失败的情况: 新增proxy加上去之后, router将正在处理的连接转移到新的proxy上, 但是新的proxy并不清楚这些连接信息(应该交给那个服务器处理), 所以只能失败.

detail

github使用了load balancer拆分成两层, 一层是 director, 负责和router层的ecmp协议打交道, 另一层是代理层. 这样的做法是怎么解决之前的问题的呢?

首先, director会维护一份 有primary/secondary 的 跳转表, status可以区分为 active、filling、draining 三种状态. 通过 Rendezvous hashing 算法将proxy映射到row上: 每个proxy + row number 进行hash运算选择前两个分别作为primary、secondary proxy.

跳转表

状态迁移

  1. 正常流程:
    • 请求过来的时候, 通过对连接进行hash, 映射到指定的row, 将请求转发给 primary proxy
    • proxy 检查本地的本地状态, 只接受新创建的连接/本地已经创建的连接.
  2. 添加
    • director 重新进行hash运算, 更新 跳转表, 因为使用了Rendezvous hashing, 会发现, 只有部分行发生了变化, 一种是新增的proxy成为了 secondary, 这种情况下, 依然是active状态, 另一种是新增的proxy成为了 primary, row status变成了 filling,
    • 原有的请求到来的时候, 被分配到 primary proxy
    • primary proxy 发现本地不存在这个连接, 并且也不是新创建的连接, 转发给 secondary proxy(也就是这个连接的owner)
  3. 删除
    • 在跳转表中, director将 primary == 要删除的server的row的状态重置为 Draining, 同时, 将primary和secondary进行转换
    • 原有的请求到来的时候, 被分配到 primary proxy
    • primary proxy 发现本地不存在这个连接, 并且也不是新创建的连接, 转发给 secondary proxy(也就是这个连接的owner)

通过上面的流程发现, 因为 primary/secondary 的设计, 实现了 优雅关闭的特性. 但是缺点也很明显: 每次只能有一个变化发生, 但是够用的.

other

  1. dpdk的使用与优化, 通过dpdk绕过内核, 直接在用户层和nic打交道
  2. 通过gue(generic udp encapsulation) 将secondary ip放到了udp 当中, 实现二次分发; 除此之外, proxy 还可以将内容直接分发给客户端, 绕过director.
  3. 没有采用ipip策略, 而是使用了gue, 因为ipip无法放入其他server metadata.而且, 如果传递了未知ip选项, 处理速度会从几百万下降到几千; 而且大部分datacenter并不支持

reference

  1. 数据中心内负载均衡-ECMP的使用分析
  2. 官方blog
  3. github开源地址
  4. foo over udp
  5. generic udp encapsulation