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

31–40 of 40 posts

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

#31

Post by cperciva »

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.

I wondered if that was it, but a 1/RTT loading behaviour seems safe enough to me -- after all, that's exactly what TCP does, and you're presumably not seeing any uncontrolled oscillations from that.

I guess it depends how much minimizing the size of your connection pool matters.

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

#32

Post by jerf »

mabbo wrote: post #5

"The breakthrough came when we started thinking about the components in the system as malicious actors colluding via covert channels." That's probably the piece of that article that I'm going to remember for a long time.

This is definitely one of the most powerful debugging techniques for hard problems in my toolkit, though I phrase it as "If I wanted to produce this problem on purpose, how would I go about doing it?", since that is a general debugging technique and their phrasing is specific to communicating actors.

This results in me exclaiming every 4-6 months or so that I wouldn't know how to create this particular bug on purpose if I wanted to, which I suppose doesn't make much sense as a complaint about a bug until you start thinking this way. Anyhow, it isn't perfect and you will sometimes be defeated by the sheer perversity of bugs and their behavior. (I also find these are the tiny ones, like OR instead of XOR or something equally simple and at times even one-character, that produce mind-blowing behavior off that one error. The architectural bugs tend to give way to this analysis much more readily.) But it's a useful tool much of the time.

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

#33

Post by jerf »

msandford wrote: post #28

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 havi…

"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."

Well, sure, it's obvious when you're reading a prepared text that is carefully leading you up to that conclusion and has removed all extraneous information. Almost all bugs are shallow once you already know the answer.

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

#34

Post by ngbronson »

msandford wrote: post #28

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 havi…

One of the reasons this took a long time to figure out is that it was a failure amplifier, so there was always a more typical network problem preceding it. Network failures in a data center cause lots of changes to the packets, because of retries, failover, and automatic load balancing, so there were a lot of trees to look at.

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

#35

Post by ifdefdebug »

hueving wrote: post #22
ifdefdebug wrote: post #17

Earlier quoted context omitted.

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. :)

well FIFO stack still exists as a synonym for queue, but you're right, stack and queue would have qualified my point good enough :) anyway, looking at newer answers it seems that topic was not of concern for their solution...

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

#36

Post by ngbronson »

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…

When the pool was originally coded, MySQL had one thread per open connection. That made the auto-sizing MRU pool a pretty big win, because it kept the connection counts as low as possible while using the warmest database threads. MySQL has matured since then, so this optimization is no longer important.

Out-of-order delivery causes TCP to shrink the congestion windows, which cuts throughput. Connection pools help here (in addition to their reduction in setup and teardown work), because they let the windows widen and stay open. We disable tcp_slow_start_after_idle to take advantage of this.

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

#37

Post by msandford »

jerf wrote: post #33
msandford wrote: post #28

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 havi…

"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." Well, sure, it's obvious when you're reading a prepared text that is carefully leading you up to that conclusion and has removed all extraneous information. Almost all bugs are shallow once you alrea…

The stability of it is the giveaway. It's not a meta-stable failure state, it's a fully stable failure state. There is positive feedback; increased latency on a link begets further link usage; which causes more latency, etc.

Had there been some kind of negative feedback (in the electrical engineering sense of the word) and this still happened somehow it might be a lot more difficult to track down. But introducing negative feedback is what they did to solve the problem, so perhaps it wouldn't have still happened.

http://en.wikipedia.org/wiki/Feedback

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

#38

Post by api »

This is one of the best engineering write-ups I've ever read. It's also a principle I'll remember, since I work a lot with distributed systems and p2p networks: when debugging, imagine systems as adversaries and frame it as a security problem.

Thanks!

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

#39

Post by ngbronson »

msandford wrote: post #37
jerf wrote: post #33

Earlier quoted context omitted.

"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." Well, sure, it's obvious when you're reading a prepared text that is carefully leading you up to that conclusion and has removed all extraneous information. Almost all bugs are shallow once you alrea…

The stability of it is the giveaway. It's not a meta-stable failure state, it's a fully stable failure state. There is positive feedback; increased latency on a link begets further link usage; which causes more latency, etc. Had there been some kind of negative feedback (in the electrical engineering sense of the word) and this still happened somehow it might be a lot more difficult to track down. But introducing neg…

Metastability comes in when you think about the problem that originally triggered congestion. A normal network overload caused by a bulk transfer, for example, can be fixed by canceling the transfer. Once you add the feedback loop, however, you need to both cancel the transfer and remove lots of other load. I use the term metastable because although it is fully stable (that's the problem!) it isn't the "ground state". Another way to say it is that the metastable states are only local attractors.

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

#40

Post by msandford »

ngbronson wrote: post #34
msandford wrote: post #28

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 havi…

One of the reasons this took a long time to figure out is that it was a failure amplifier, so there was always a more typical network problem preceding it. Network failures in a data center cause lots of changes to the packets, because of retries, failover, and automatic load balancing, so there were a lot of trees to look at.

That makes a lot more sense. It would have been nice to include some of the troubleshooting process so people can learn from that too. Thanks for sharing!
Post reply on HN