簡単な正規表現が原因で Stack Overflow がダウン

経緯

1. 昨晩 Stack Overflow がダウンしてたらしい (/r/programming)
2. 問題は正規表現 ^[\s\u200c]+|[\s\u200c]+$
   1. これは行頭と行末の空白（ Unicode 空白を含む）を除去する処理
   2. \s+$ でも同じ障害に至る
3. 原因となったのは DOS 攻撃ではなく普通の投稿
   1. もう削除されてるけど 連続した空白を 2 万個含んでいた
4. backtraking 型の正規表現エンジンで、連続した空白の後に空白でない文字があった場合
   1. 最初の空白を見つけたら、その後の文字列を 1 個ずつチェックしていき
   2. 空白でない文字を見つけたら最初に戻って次の空白から同じように 1 個ずつチェックしていくため
   3. 空白が 2 万個続いていたら 20,000+19,999+19,998+… = 199,990,000 回チェックすることになる
5. Stack Overflow ではトップページでヘルスチェックをしているが
   1. 原因の投稿がトップページに載った時、上の動作で応答に時間がかかって
   2. 全サーバーに障害があると判定されてしまい、ロードバランサーから外されてしまったためサイトがダウン

所感

10年位前、同僚が簡単な正規表現を使ってるところをレビューしてて

1. 僕「ここ trim 使った方が良い」
2. 彼「でも正規表現でも良いじゃん」
3. 僕「いやいや、処理コストが全然違うじゃん」
4. 彼「可読性が重要で処理コストはトレードオフして良い（ほどハードが進化してる）、っていつも言ってるじゃん」
5. 僕「trim の方が可読性も良いと思うんだけど」
6. 彼「それは主観の問題で周辺で正規表現がいくつも使われてるから、ここも正規表現で」
7. （僕の直感は trim にするべきと言ってるが...説明するの大変そう...）
   という会話があり、彼もベテランだったのでその時は深く追求しなかったが、その長年の引っかかりに反論できそうな事例。