GitHub has been at work for the last year to develop a new load balancer, the GitHub Load Balancer (GLB), aimed to be able to scale to billions of connections per day running on commodity hardware. GitHub engineers Joe Williams and Theo Julienne explained how GLB was designed.
One of the fundamental design goals for GitHub was being able to “stretch” an IP, i.e., split traffic destined for a single, public facing IP address across multiple links of equal cost. This is what Equal-cost multi-path routing (ECMP) usually achieves and is able to substantially increase bandwidth. However, ECMP does not perform well when a change in the set of ECMP nodes occurs, such as when a node fails or has to be removed from the set for maintenance, which was a major drawback for GitHub.
Given this, GitHub engineers considered an L4/L7 split strategy, where load balancing nodes are split in two tiers, called L4 and L7 based on which OSI layer provides the information used for distributing the requests across the balancers nodes. Thus, L4 routing uses source and destination IP addresses as well as TCP ports; L7 routing uses information at the application layer, which roughly means HTTP. In an L4/L7 split design, L4 tier nodes, called “directors”, use ECMP to split traffic across the nodes in the L7 tier, called “proxies”. Usually, Williams and Julienne explain, ipvs/LVS is used at the L4 tier, while L7 tier nodes run haproxy or a similar software.
The main benefit of the L4/L7 split is the possibility of removing an L7 tier node without any disruption by simply excluding it from the pool of nodes used to serve new connections, while keeping serving connections to that node until fully drained. On the other hand, this approach still suffers from disruption when an L4 node fails or is removed, which is particularly critical for GitHub due to git inability to deal with retries or resuming a broken connection.
This final problem was solved at GitHub by using a variant of Rendezvous hashing, an algorithm that allows director nodes to agree on which proxy should handle a connection. Rendezvous hashing is used by GLB in combination with Direct Server Return, which allows for the response to go directly from the proxy node to the client, thus bypassing the director that originally dispatched the request to that proxy. The basic idea in GLB implementation of Rendezvous hashing is sharing and keeping in sync a forwarding table across all director nodes. Roughly, this ensures that even when a director node is removed or fails, another director node can take its role and keep dispatching existing connection to the right proxies.
As a final remark, Williams and Julienne commented on how they could deploy the new load balancer, which is expected to be open sourced in the near future, without anyone noticing.