They implemented trim with a regex? Neither Java nor .NET do that. The postmortem here should probably be "why are you reimplementing trim".
My guess is developer cleverness. As the article mentions they ended up with a less clever solution.
Stack Overflow Outage Postmortem
61–70 of 335 posts
Re: Stack Overflow Outage Postmortem
#62The lesson seems to be "Always run trim() before running regex" and "validate content as much as possible before running regex".
Or just reject this input. The server isn't the time and place to do data cleanup. Can always fix this on the frontend with JavaScript for free if it's an actual problem.
Sure you can, but you better clean up on server side, or find a way to prevent any of 7+ billion people from posting maliciously.
Re: Stack Overflow Outage Postmortem
#63> It took 10 minutes to identify the cause. I'm impressed they were able to do this so quickly.
[deleted]
Re: Stack Overflow Outage Postmortem
#64They have limits on everything (comments per second, edits per second, upvotes per day, reputation earned per day, etc), it seems like they should have an upper bound character limit on what they accept too.
Re: Stack Overflow Outage Postmortem
#65> 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.
Yes, we took a stackdump and saw the traces leading to that regex.
Re: Stack Overflow Outage Postmortem
#66We had a similar issue arising from regex parsing of our SES routes on our SaaS Platform. We had made some changes to our generated SES file which caused it to balloon to 4x in size (tens of thousands of lines). Our only clue that something had gone wrong was suddenly extremely high IIS usage. With some help from Microsoft support, we managed to trace the stack during the high-cpu event to an ISAPI filter and ultimately our 3rd party SES plugin. We managed to fix the problem by being more efficient with our regex generation and reduce the number of rules the plugin was processing but it was eye-opening how much CPU was being consumed by regex processing.
Re: Stack Overflow Outage Postmortem
#67> 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.
This is exactly what we did to diagnose (source: I was on the call). The only tricky part was figuring out which post it was, since it wasn't in the stacktrace. To do that, we grabbed the 3000 most recent posts and ran the regex against them. By that point we already had the code fix (another dev working on it in parallel), but if we hadn't we also could have gotten back up by just deleting the post.
Re: Stack Overflow Outage Postmortem
#68Ha! 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…
Since those all have a lot more code than is needed to show the basic idea of an NFA-based matcher: https://github.com/darius/sketchbook/blob/master/regex/nfa_s...
Re: Stack Overflow Outage Postmortem
#69I think this might have been the post they quoted. http://stackoverflow.com/questions/38484433/in-corona-sdk-ho...
Yeah, Nick "deleted 20507 characters in body" five hours ago:
http://stackoverflow.com/posts/38484433/revisions
Re: Stack Overflow Outage Postmortem
#70> If the string to be matched against contains 20,000 space characters in a row, but not at the end, then the Regex engine will start at the first space, check that it belongs to the \s character class, move to the second space, make the same check, etc. After the 20,000th space, there is a different character, but the Regex engine expected a space or the end of the string. Realizing it cannot match like this it backtracks, and tries matching \s+$ starting from the second space, checking 19,999 characters. The match fails again, and it backtracks to start at the third space, etc.
That's not how backtracking works. A regex engine will only backtrack to try and make the rest of the regex match, i.e. it will take characters of the RHS of the string, not try and start "from the second character off the start of the string". I mean, if the engine tried matching from the second space, what would be matching the first space? Something has to.
Which meant, that even if the regex engine was incredibly stupid and could not figure out that a greedy block of \s was never going to contain a non-\s, it would only have to check 20,001 times, not 199000 (or whatever it was).
I can't reproduce this "bug" in either Perl or Python. The time taken to match a 30,000 block of space either followed by $ or XX$ was basically identical for \s+$.
There does appear to be normal backtracking going on, roughly doubling the search time for large strings terminating in non-\s. This is expected, as it has to check 20,000 during the first gobble, then 20,000 as it backtracks from the right 20,000 times.
$ time perl -e '(" " x 100000000 . "X") =~ /\s+$/ && print "MATCH"'
real 0m0.604s
user 0m0.509s
sys 0m0.094s
$ time perl -e '(" " x 100000000) =~ /\s+$/ && print "MATCH"'
MATCH
real 0m0.286s
user 0m0.197s
sys 0m0.089s