Stack Overflow оказался недоступен из-за работы регулярного выражения

Сегодня на Stack Status появился пост, в котором сотрудник сети Stack Exchange, к которой относится сервис Stack Overflow, рассказал о том, почему вчера в течение часа ресурс был недоступен.

Причиной нестабильности сервиса стала повышенная нагрузка на сервера, связанная с обработкой одного из опубликованных вопросов. Дело в том, что публикуемые на Stack Overflow вопросы перед отображением на странице анализируются набором регулярных выражений, в числе которых следующее: ^[\s\u200c]+|[\s\u200c]+$ — оно служит для обрезания пробелов (в том числе в Unicode) с концов строки. И камнем преткновения стал пост, который содержал в середине текста последовательность из 20 000 (!) пробелов.

Вышеупомянутое регулярное выражение обрабатывало такую строку следующим образом: найдя первый пробел, оно переходил к следующему, затем к следующему и т.д. до самого последнего пробела в последовательности. После ожидался конец строки, однако строка из пробелов оказалась в середине поста, поэтому движок конец строки там, естественно, не обнаруживал. Тогда предпринималась попытка найти соответствие в следующей возможной последовательности символов, и движок принимался анализировать ту же строку, начиная со второго пробела, затем переходя к третьему, затем — к четвертому и т.д. до конца. Его поиск, естественно, снова не увенчивался успехом и на очереди оказывалась подстрока, начиная с третьего символа и т.д. В итоге движку пришлось анализировать 20 000 + 19 999 + 19 998 + … + 1 = 199 990 000 символов!

Дополнительные пояснения на тему работы регулярный выражений вы можете найти в нашем руководстве.

Сложность такого действия составляет O(N²) — и хотя, как отмечает автор публикации, это, конечно, не экспоненциальная сложность, но так вышло, что пост-вредитель попал на домашнюю страницу сервиса и вынудил сервера обрабатывать текст регулярным выражением для огромного числа посетителей сервиса, заходящих на него через главную страницу. Это привело к тому, что домашняя страница стала с большими задержками отвечать на запросы. Балансировщик нагрузки Stack Overflow, в свою очередь, оценивает доступность сервиса по доступности домашней страницы, и поэтому воспринял задержку в ответах на запросы как знак того, что работу сервиса необходимо приостановить.

К слову, исправлена ситуация была очень быстро: 10 минут потребовалось на поиск причины, 14 — на написание кода для ее исправления, и 10 — на внедрение фикса.