Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

code.facebook.com

Post reply on HN
Print view View original

21–30 of 40 posts

Re: Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

#21

Post by xtacy »

cperciva wrote: post #8

The most literal conclusion to draw from this story is that MRU connection pools shouldn’t be used for connections that traverse aggregated links. Not just connections which traverse aggregated links. If you're load-balancing between multiple database replicas -- or between several S3 endpoints -- this sort of MRU connection pool will cause metastable load imbalances on the targets. What I don't understand is why Fac…

I am not sure that would work either. If I understand correctly, the root cause of delayed responses is because more requests were sent on that link due to hash collisions, which delays connections on that link. So, wouldn't "most recent request sent" correlate well with "most recent response received"?

EDIT: Also, this seems like a classic load balancing problem: Simply picking the least loaded connection would have been sufficient. The response time on each connection could be computed either explicitly (a running average/standard deviation of RPC finish times) or implicitly by checking the queue backlog at any time (the queue backlong being a first-order statistic).

Re: Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

#22

Post by hueving »

ifdefdebug wrote: post #17
cperciva wrote: post #8

The most literal conclusion to draw from this story is that MRU connection pools shouldn’t be used for connections that traverse aggregated links. Not just connections which traverse aggregated links. If you're load-balancing between multiple database replicas -- or between several S3 endpoints -- this sort of MRU connection pool will cause metastable load imbalances on the targets. What I don't understand is why Fac…

Out of nothing, I'd guess their MRU worked by just pushing an incoming free connection on top of a LIFO stack, while for the "most recent request sent" strategy you had to keep track of request timing and insert incoming free connections into the middle of the stack, complicating things. Within their solution just had to convert the LIFO stack into an FIFO queue, keeping it simple.

stack implies LIFO and queue implies FIFO. Otherwise they wouldn't have different names. :)

Re: Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

#23

Post by hueving »

donavanm wrote: post #10

Color me confused. Just a week ago they posted "We also have server-side means to “hash away” and route around trouble spots, if they occur." https://code.facebook.com/posts/360346274145943/introducing-... Does the server side flow hash manipulation dependent on ip tuple manipulation? Only enabled for some hosts/devices? A bit disappointed, was hoping for clever dscp or mpls tag manipulation. If they rely on new stre…

They explicitly mention in the article that this may not apply to their new data center.

Re: Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

#24

Post by jessaustin »

This keeps all the packets of a TCP stream on the same link, avoiding out-of-order delivery.

Not a network engineer, but I had thought that TCP handles ordering itself? Packets can travel completely different routes from origin to destination, so one can't expect them to arrive in order. Destination's TCP stack can deal with it.

Again, IANANE, but ISTM that those who first designed the network introduced an untested complication with their LIFO setup. Nearly anything would have worked, including not pooling at all. They just chose something weird for the hell of it. Later FB needed more performance out of the system, and this harmful complication was hidden from sight.

Re: Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

#25

Post by darrin »

jessaustin wrote: post #24

This keeps all the packets of a TCP stream on the same link, avoiding out-of-order delivery. Not a network engineer, but I had thought that TCP handles ordering itself? Packets can travel completely different routes from origin to destination, so one can't expect them to arrive in order. Destination's TCP stack can deal with it. Again, IANANE, but ISTM that those who first designed the network introduced an untested…

Yes, TCP will reorder if necessary, but that will introduce some delay and overhead at the host. The missing sequence number (the out of order frame) will cause queuing as TCP waits for it to arrive or requests retransmit, so keeping streams in order in the network is more efficient.

Re: Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

#27

Post by The_Fox »

jessaustin wrote: post #24

This keeps all the packets of a TCP stream on the same link, avoiding out-of-order delivery. Not a network engineer, but I had thought that TCP handles ordering itself? Packets can travel completely different routes from origin to destination, so one can't expect them to arrive in order. Destination's TCP stack can deal with it. Again, IANANE, but ISTM that those who first designed the network introduced an untested…

TCP reorders segments just fine but it treats disordering as a congestion signal and slows down. That's why link aggregation frequently uses the technique of pinning flows to a single link- to minimize disordering so as to avoid triggering TCP congestion control.

In Linux, you can change the sensitivity to disordering by writing to /proc/sys/net/ipv4/tcp_reordering.

Re: Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

#28

Post by msandford »

It took two years to figure this out? When I read the first couple of paragraphs my first thought was "the low-latency links are getting dropped from the eligibility pool somehow" and it turns out that was the problem.

I think my intuition there stems from having a lot of full-stack responsibility (so the idea that it's someone else's problem was never a luxury I could afford, since it was always my problem) and having cleaned up a number of other people's very large spaghetti-code disasters.

The other possibility is that I have no special intuition into the problem (this is far more likely) but did have a fresh set of eyes, while all the people who were working on the problem were so intimately familiar with it that they couldn't see the forest for the trees.

Re: Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

#29

Post by ngbronson »

cperciva wrote: post #8

The most literal conclusion to draw from this story is that MRU connection pools shouldn’t be used for connections that traverse aggregated links. Not just connections which traverse aggregated links. If you're load-balancing between multiple database replicas -- or between several S3 endpoints -- this sort of MRU connection pool will cause metastable load imbalances on the targets. What I don't understand is why Fac…

I coded the fix. We considered some options that had a bias away from the slow links, but we thought it was safer to avoid bias completely. It was fine in my tests, but I couldn't prove that biasing toward the faster link in a 2 link setup wouldn't set up an oscillation.

Re: Solving the Mystery of Link Imbalance: A Metastable Failure State at Scale

#30

Post by mabbo »

ngbronson wrote: post #29
cperciva wrote: post #8

The most literal conclusion to draw from this story is that MRU connection pools shouldn’t be used for connections that traverse aggregated links. Not just connections which traverse aggregated links. If you're load-balancing between multiple database replicas -- or between several S3 endpoints -- this sort of MRU connection pool will cause metastable load imbalances on the targets. What I don't understand is why Fac…

I coded the fix. We considered some options that had a bias away from the slow links, but we thought it was safer to avoid bias completely. It was fine in my tests, but I couldn't prove that biasing toward the faster link in a 2 link setup wouldn't set up an oscillation.

Great reasoning. Problem: bias isn't balanced, causing complex failure. Solution A: change the bias. Solution B: remove all bias.

One of these options makes things simpler. I'm always in favor of that.

Post reply on HN