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

Stack Overflow Outage Postmortem

stackstatus.net

Post reply on HN
Print view View original

71–80 of 335 posts

Re: Stack Overflow Outage Postmortem

#71

Post by viraptor »

unethical_ban wrote: post #59
sklivvz1971 wrote: post #34

Earlier quoted context omitted.

It finds a space, tries to match the rest of the string, fails, rolls back to it and goes forward one, finds a space... The trick is that there's no guarantee, in general, that a match failing at character N is due to character N, so the regex engine backtracks.

I guess I need to buff up on my automata, but I would have thought that for positional delimiters, there would be optimizations. If the pattern is \s+$, then I can look from the back of the line, see if there is a space, and if so, go backward until I find a non-space character.

That's just special casing the end of line. If it was "\s+x" you'd still have the same problem.

Re: Stack Overflow Outage Postmortem

#72

Post by tgb »

mh- wrote: post #44
wheaties wrote: post #21

Earlier quoted context omitted.

SO is I/O bound most of the time. If you've set up your system to handle high workloads of I/O bound traffic, then hitting CPU bounds throws a real wrench in your cogs. To put this another way, SO is one of the most traffic'd sites on the internet. So a page that's loaded 10k+ times a second is going to push that number much, much, higher. If the CPU can't clear 10k+ req in under the regular time it takes, everything…

> To put this another way, SO is one of the most traffic'd sites on the internet. I've seen this said several times here, but never bothered to ask.. by what measure is this true?

Alexa puts it at rank 50 globally. Honestly this seems suspiciously high and I wonder if their sampling method is biased. Regardless, it's a lot of traffic.

http://www.alexa.com/siteinfo/stackoverflow.com

Re: Stack Overflow Outage Postmortem

#74

Post by mamcx »

chubot wrote: post #9

Ha! The same bug happened internally at my company. In that case it was a regex matching a URL taking so much CPU as to cause a DOS of a proxy server. I won't be surprised if it's happened to someone here too. This is very timely, because minutes ago, I made a link to Russ Cox's articles in my Kernighan awk repo: https://github.com/andychu/bwk https://swtch.com/~rsc/regexp/regexp1.html If you are not familiar with th…

Sadly not much Thompson's libraries are implemented. I have tried to find one for F# but are just toy projects.

Re: Stack Overflow Outage Postmortem

#75

Post by teh_klev »

ww520 wrote: post #46
kilroy123 wrote: post #23

> It took 10 minutes to identify the cause. I'm impressed they were able to do this so quickly.

System not responsive. Look at the CPU load. Look at the process peaking at 100%. Force dump the stack track of the process couple times. Hmm. All of them stuck in the regex engine. Look back up the stack track to see who calls it. Oh, it's on the home page's text cleansing code. Something like that.

ADPlus + WinDBG + SOS possibly.

Re: Stack Overflow Outage Postmortem

#76

Post by phasmantistes »

StavrosK wrote: post #29

I don't understand something: the regex expected a space character, followed by the end of the string. If the last character wasn't a space, this could never match. Why did the engine keep backtracking, even though it's easy to figure out that it could never match the regex?

Most simple regular expression evaluators are basically state machines. They hold a few variables:

a) what part of the regex am I currently trying to match

b) what point in the string am I currently starting at

c) how much of the string has this piece of the regex consumed so far

Then the state machine basically has three transitions:

* if (b+c) terminally matches (a), increment both (a) and (b) and reset (c)

* if (b+c) matches (a), but more could be consumed, increment (c) and check again

* if (b+c) doesn't match (a), increment (b) and reset (c)

So yeah, you could put in short cuts for things like "well this didn't match because the next piece of the regex is matching on a line ending", but keeping it simple is straightforward and generally smiled upon.

Re: Stack Overflow Outage Postmortem

#77

Post by alexbecker »

I remember the day I learned that Python's "re" module uses backtracking for non-extended regexes. My tests covered lots of corner cases in the regex logic, but were too short for me to notice the performance penalty. Luckily I only caused a partial outage in production.

I actually got to talk to Raymond Hettinger (Python core team) about why re uses a potentially exponential-time algorithm for regexes when there is a famous linear-time algorithm, and (I suspect) most programmers would assume linear complexity. As it turns out, there was an attempt to re-write re to fix this, but the re-write never managed to present exactly the same (extremely large) API as the existing module. He advised me that "the standard library is where code goes to die."

Re: Stack Overflow Outage Postmortem

#78

Post by xigency »

chubot wrote: post #9

Ha! The same bug happened internally at my company. In that case it was a regex matching a URL taking so much CPU as to cause a DOS of a proxy server. I won't be surprised if it's happened to someone here too. This is very timely, because minutes ago, I made a link to Russ Cox's articles in my Kernighan awk repo: https://github.com/andychu/bwk https://swtch.com/~rsc/regexp/regexp1.html If you are not familiar with th…

The key quote here is:

"Regular expressions are one of computer science's shining examples of how using good theory leads to good programs ..."

"Today, regular expressions have also become a shining example of how ignoring good theory leads to bad programs. The regular expression implementations used by today's popular tools are significantly slower than the ones used in many of those thirty-year-old Unix tools."

The alarming thing is that regex are supposed to be compiled before use, and the class of expressions that need quadratic or exponential time is distinct from the class that needs linear time. Why don't these popular, widely-used regex implementations perform any optimizations?

Re: Stack Overflow Outage Postmortem

#79

Post by johncoltrane »

A few months ago, a Stack Overflow representative asked me if their presence at a dev conference was justified. My positive answer more or less revolved around the importance SO took in the daily life of programmers everywhere.

If only she was there to witness the effect of a 34 minute downtime on an open space full of mobile/back/front developers.

Re: Stack Overflow Outage Postmortem

#80

Post by bhandziuk »

mplewis wrote: post #41

I think this might have been the post they quoted. http://stackoverflow.com/questions/38484433/in-corona-sdk-ho...

> deleted 20507 characters in body - Nick Craver

You are very likely right. Though it looks like they permanently deleted those characters because they don't show up on the edit history.

Post reply on HN