4 ms·

So, it looks like they're using BGP to "program" the adjacent router a la "SDN." I'm curious as to two things: * Byzantine fault-tolerance: How does this syste

by sargun 12y ago

So, it looks like they're using BGP to "program" the adjacent router a la "SDN." I'm curious as to two things: * Byzantine fault-tolerance: How does this system handle failures when a specific node fails in a way that it fails to withdraw its routes. When a node's haproxy fails, how is BIRD informed of its failure? What if the failure is in some way that internal fault detectors don't see the failure. * How is the ECMP hashing problem handled? ECMP hashing on most gear is just a plain hash, that means when a route is withdrawn, the rest of the systems see their traffic rebalance. How does this not result in all connections being severed?

nbm 12y ago
I'm not sure about how Tumblr might do it, but one can use a combination of ECMP and ipvs (with a consistent hash) to do the lower-layer L4 load balancing. This means that even if one of the L4 load balancers go down and the connections originally going to that L4 load balancer by the switch/router get moved to another one, the consistent hash to the L7 load balancer handling the request means the connections will not be reset (except in some interesting and less-frequent cases). This two-stage process also allows for good health checking from the much-simpler Linux ipvs L4 load balancer servers to the more-complicated L7 load balancer servers. This was described in this Velocity 2013 talk - http://velocityconf.com/velocity2013/public/schedule/detail/28410 http://velocityconf.com/velocity2013/public/schedule/detail/...
- sargun 12y ago
  Yeah, this is how Facebook does it, and how we did it at Microsoft / Yammer.
aaron42net 12y ago
ECMP is used heavily in serving Anycast DNS worldwide; it's only the application to HTTP that's somewhat new. A high-end router can do stateless ECMP at 10s or 100s of millions of packets per second; it's hard to find load balancers that can compete with this. BGP has heartbeats at usually 15 to 45 second intervals depending on configuration. If BIRD stops responding, the router will withdraw its routes. BIRD can be controlled via a Unix socket. Usually people build a health-check daemon that does queries against the local app and communicates its finding to BIRD. Working through all of the failure modes here is tricky, but doable. The ECMP hash is often implemented as something like a CRC-16 of (protocol, source IP/port, dest IP/port) modulo the number of next-hops. I suspect the trick to keep TCP happy is to try keep the number of next-hops (shards) constant for each route.
- sargun 12y ago
  At least on most chips today, they use modulo-N hashing, which results in potentially breaking existing connections, see: http://tools.ietf.org/html/rfc2992 http://tools.ietf.org/html/rfc2992 The reason that this isn't really a problem on the internet, is because you're typically not using ECMP, and just plain anycast.
donavanm 12y ago
There was a related story of ECMP load balancing a while back. There were good comments on some of this benefits & challenges, https://news.ycombinator.com/item?id=7811412 https://news.ycombinator.com/item?id=7811412. To your first point use an external node, outside te data path, as your control plane. To the second the simplest is to mange layer 3 ecmp on top of mobile layer 2 address assignments. Think bgp to carp'd next hops. Depending on your router implementation you also have more choices than simple 5 tuple for the ecmp hash inputs.

by sargun 12y ago

nbm 12y ago

I'm not sure about how Tumblr might do it, but one can use a combination of ECMP and ipvs (with a consistent hash) to do the lower-layer L4 load balancing. This means that even if one of the L4 load balancers go down and the connections originally going to that L4 load balancer by the switch/router get moved to another one, the consistent hash to the L7 load balancer handling the request means the connections will not be reset (except in some interesting and less-frequent cases). This two-stage process also allows for good health checking from the much-simpler Linux ipvs L4 load balancer servers to the more-complicated L7 load balancer servers. This was described in this Velocity 2013 talk - http://velocityconf.com/velocity2013/public/schedule/detail/28410 http://velocityconf.com/velocity2013/public/schedule/detail/...

sargun 12y ago
Yeah, this is how Facebook does it, and how we did it at Microsoft / Yammer.

aaron42net 12y ago

ECMP is used heavily in serving Anycast DNS worldwide; it's only the application to HTTP that's somewhat new. A high-end router can do stateless ECMP at 10s or 100s of millions of packets per second; it's hard to find load balancers that can compete with this. BGP has heartbeats at usually 15 to 45 second intervals depending on configuration. If BIRD stops responding, the router will withdraw its routes. BIRD can be controlled via a Unix socket. Usually people build a health-check daemon that does queries against the local app and communicates its finding to BIRD. Working through all of the failure modes here is tricky, but doable. The ECMP hash is often implemented as something like a CRC-16 of (protocol, source IP/port, dest IP/port) modulo the number of next-hops. I suspect the trick to keep TCP happy is to try keep the number of next-hops (shards) constant for each route.

sargun 12y ago
At least on most chips today, they use modulo-N hashing, which results in potentially breaking existing connections, see: http://tools.ietf.org/html/rfc2992 http://tools.ietf.org/html/rfc2992 The reason that this isn't really a problem on the internet, is because you're typically not using ECMP, and just plain anycast.

donavanm 12y ago

There was a related story of ECMP load balancing a while back. There were good comments on some of this benefits & challenges, https://news.ycombinator.com/item?id=7811412 https://news.ycombinator.com/item?id=7811412. To your first point use an external node, outside te data path, as your control plane. To the second the simplest is to mange layer 3 ecmp on top of mobile layer 2 address assignments. Think bgp to carp'd next hops. Depending on your router implementation you also have more choices than simple 5 tuple for the ecmp hash inputs.