Сбой Stack Overflow

В 2016 году Stack Overflow испытал 34-минутный перебой в работе. Причиной стало регулярное выражение, используемое для обработки пользовательского ввода:

^[\s\u200c]+|[\s\u200c]+$

Это выражение должно было находить пробелы в начале и конце строки. Проблема возникла, когда какой-то пользователь запостил комментарий, содержащий около 20 000 последовательных пробелов. Механизм обработки регулярных выражений начал проверять каждый пробел. Когда после 20 000-го пробела встретился другой символ, движок начал откатываться назад, пытаясь найти соответствие, начиная со второго пробела, третьего и так далее.

Это привело к катастрофическому возврату (catastrophic backtracking) – ошибке, которая возникает, когда движок регулярных выражений тратит чрезмерное количество времени на попытки найти соответствие шаблону, перебирая различные комбинации. Количество проверок начало лавинообразно увеличиваться и быстро достигло 199 990 000 – это вызвало значительную задержку и в итоге сбой системы.

Для решения проблемы потребовалось 10 минут на обнаружение причины, 14 минут на написание исправления и еще 10 минут на развертывание решения. В результате регулярное выражение было заменено на функцию подстроки.

Сбой Cloudflare

2 июля 2019 года произошел крупный сбой в работе платформы Cloudflare. Один из инженеров написал регулярное выражение, которое привело к действительно катастрофическому возврату – вызвало экстремальную перегрузку всей инфраструктуры. Использование процессоров выросло до 100%, а большинство сайтов, подключенных к Cloudflare, замедлились до крайности или вовсе оказались недоступными.

Коварная регулярка выглядела так:

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

Самую большую опасность в этом выражении представляет

.*(?:.*=.*)

– группа без захвата, которая может привести к чрезмерному использованию процессора при обработке определенных шаблонов. Эта конструкция вызвала серьезные проблемы с производительностью и в конечном итоге привела к массовому сбою.

Глобальный сбой Windows/CrowdStrike

19 июля 2024 года произошел самый массовый сбой в истории – из строя вышли около 8,5 млн Windows-компьютеров с ПО CrowdStrike. Причиной сбоя стало несоответствие между ожидаемым количеством входных параметров (21) и фактическим количеством параметров (20), которые были переданы в интерпретатор контента (этот компонент отвечает за обработку содержимого с использованием регулярных выражений). Когда система получила ввод с 21 параметром, интерпретатор контента попытался считать данные за пределами выделенной памяти, что и привело к сбою системы.

Привет!

Мы запустили еженедельную email-рассылку, посвященную последним новостям и тенденциям в мире бэкенда. В еженедельных письмах ты найдешь:

• Языки программирования и фреймворки для бэкенда

• Архитектура и проектирование серверных приложений

• Базы данных и управление данными

• Безопасность и защита данных

• Облачные технологии и DevOps

• API и интеграции

• Тестирование и отладка

• Инструменты и утилиты для бэкенд-разработчиков

• Лучшие практики и паттерны проектирования

🤵 Как не завалить собеседование в крупной ИТ-компании

Разработчик с 10-летним коммерческим опытом поделился провальным опытом прохождения технического собеседования в одной из лидирующих компаний. Из этого провала он извлек три основных урока:

• Перед собеседованием нужно освежить знания о структурах данных – и не только о списках, массивах и словарях. Не стоит игнорировать и те структуры, с которыми вы в последний раз сталкивались в университете и никогда не используете на практике – очереди, кучи и деревья. Автору попался как раз вопрос о деревьях, с которыми он с университетских времен не встречался и которые, скорее всего, на новой работе ему бы тоже не понадобились. Однако на собеседовании зачастую проверяются не только практические навыки, но и общая ИТ-эрудиция.

• Для тренировки нужно использовать самый простой редактор кода и таймер. Хотя в реальной работе повсеместно используются IDE с автодополнением кода и прочей ИИ-функциональностью, крупные компании при проведении теста обычно настаивают на старомодном способе решения задач, без каких-либо подсказок со стороны IDE. Писать код надо быстро – поэтому во время подготовки к собеседованию обязательно нужно пользоваться таймером для самоконтроля.

• Не надо решать задания по порядку. Необходимо прочитать все вопросы сразу и начинать с ответов на те, что попроще. Автор надолго застрял на первом вопросе, хотя мог быстро ответить на второй и успел бы выполнить третье задание. Два решенных задания, несомненно, лучше, чем незаконченный ответ на первый вопрос.

🛠️ Инструменты

BullMQ – библиотека для Node.js, которая реализует быструю и надежную систему очередей, основанную на Redis и предназначенную для решения всех основных задач в современных микросервисных архитектурах (сглаживание пиков нагрузки, создание надежных каналов связи между сервисами, распределение ресурсоемких задач между несколькими обработчиками и тому подобное).

Основные возможности и преимущества BullMQ:

• Точная обработка сообщений – библиотека гарантирует доставку как минимум один раз.

• Горизонтальное масштабирование – можно добавить сколько угодно обработчиков для параллельной обработки заданий.

• Высокая производительность – благодаря эффективным Lua-скриптам и конвейерной обработке.

• Минимальное использование CPU.

• Распределенное выполнение заданий на основе Redis.

• Поддержка очередей LIFO и FIFO.

• Приоритезация и отсроченное выполнение заданий.

• Запланированные и повторяющиеся задачи по расписанию.

• Настройка параллельности для каждого обработчика.

• Многопоточные (изолированные) функции обработки.

• Автоматическое восстановление после сбоев процесса.

• Поддержка зависимостей между задачами (родительские и дочерние задачи).

SigNoz – опенсорсный инструмент для мониторинга и устранения неполадок в развернутых приложениях. Это отличная бесплатная альтернатива коммерческим решениям – DataDog и New Relic.

Основная функциональность:

• Единый интерфейс для метрик, трассировок и логов.

• Визуализация метрик производительности приложений (RPS, процентили задержек, частота ошибок).

• Распределенная трассировка для выявления проблем в сервисах.

• Управление логами с продвинутым построителем запросов.

• Мониторинг инфраструктуры.

• Отслеживание исключений в различных языках программирования.

• Настраиваемые оповещения.

• Поддержка OpenTelemetry для инструментирования приложений.

• Возможность агрегации данных трассировки для получения бизнес-метрик.

Infisical – опенсорсная платформа для удобного и безопасного управления секретами и конфигурационными данными. Основные возможности:

• Централизованное хранение секретов – позволяет безопасно хранить в одном месте все важные данные (API-ключи, пароли от баз данных и другие конфиденциальные настройки приложений).

• Синхронизация между командой и инфраструктурой – гарантирует, что все члены команды и все части инфраструктуры будут получать доступ к актуальным секретам и ключам.

• Предотвращение утечек – помогает предотвратить случайное раскрытие секретной информации, например, путем коммита в Git-репозиторий.

• Управление конфигурациями – позволяет управлять общими настройками приложений для разных сред (разработка, тестирование, продакшн).

• Безопасный доступ – предоставляет инструменты (SDK, CLI, API) для безопасного получения секретов в приложениях и инфраструктуре.

• Контроль доступа – позволяет настраивать права доступа к секретам для разных пользователей и систем.

• Аудит и версионирование – ведет лог всех действий с секретами и позволяет отслеживать их изменения во времени.

• Интеграция с инфраструктурой – легко интегрируется с популярными платформами и инструментами (GitHub, AWS, Kubernetes и т. п.).

• Управление внутренней PKI – позволяет создавать и управлять собственной инфраструктурой открытых ключей для выпуска цифровых сертификатов.

KubeAI – инструмент для развертывания и управления опенсорсными LLM-моделями в среде Kubernetes. Среди основных функций и особенностей:

• Совместимость с OpenAI. Предоставляет API, совместимый с OpenAI, что позволяет легко заменить сервисы OpenAI в любых ИИ-приложениях на локальные.

• Поддержка различных моделей. Может работать с различными моделями, включая языковые (LLMs), модели для преобразования речи в текст (например, Whisper) и другие.

• Мультиплатформенность. Может работать на разных аппаратных платформах, включая системы только с CPU, системы с GPU, а в будущем планируется поддержка TPU.

• Масштабирование. Обеспечивает автоматическое масштабирование в зависимости от нагрузки, включая возможность масштабирования до нуля (когда ресурсы не используются).

• Простота развертывания. Не требует никаких дополнительных зависимостей типа Istio или Knative.

• Встроенный пользовательский интерфейс. Предоставляет чат-интерфейс OpenWebUI для взаимодействия с моделями.

• Управление серверами vLLM, Ollama и FasterWhisper.

• Интеграция с системами обмена сообщениями. Поддерживает потоковую передачу и пакетную обработку через интеграции с Kafka и другими PubSub-системами обмена сообщениями.

Zed – опенсорсный многопользовательский редактор кода, предназначенный для совместной работы над проектом в реальном времени. Основные особенности и возможности:

• Написан на Rust и отличается высокой скоростью и минимальными требованиями к ресурсам.

• Предусматривает интеграцию с LLM для генерации, анализа и рефакторинга кода.

• Имеет встроенный терминал.

• Предоставляет несколько удобных функций для совместной работы – демонстрацию экрана, общие заметки и т. п.

• Разработан с учетом конфиденциальности пользователей и не собирает личные данные.

Warp – современный высокопроизводительный терминал с ИИ-функциональностью. Основные особенности и возможности:

• Производительность. Написан полностью на Rust и использует рендеринг на GPU через Metal API, что обеспечивает высокую скорость работы (60+ FPS даже на 4K- и 8K-мониторах).

• Поддержка совместной работы в реальном времени.

• Улучшенный ввод команд. Редактор ввода команд представляет собой полноценный текстовый редактор с поддержкой выделения текста, позиционирования курсора, привычных пользователям сочетаний клавиш и автодополнения.

• Встроенный чат-бот. Понимает указания на естественном языке, дает рекомендации и отвечает на вопросы.

• Блоки команд. Команды и их вывод визуально группируются в блоки, что улучшает организацию и читаемость информации в терминале.

• Совместимость с популярными оболочками. Работает с Bash, ZSH и Fish, сохраняя существующие привязки клавиш.

• Кроссплатформенность. Работает на macOS и Linux, вскоре будет поддерживать Windows и WASM.

• Продвинутый UI. В отличие от традиционных терминалов, может отображать различные элементы интерфейса (всплывающие уведомления, меню и т. д.).

Автор рассылки: Наталья Кайда

Квантифаеры (Quantifier) + * ?

Предположим, в нашем выражении один из символов может быть опциональным или повторяться несколько раз. Например, мы ищем слово cat, которое может начинаться с "ca", но последующий символ "t" может быть опциональным или повторяющимся. Здесь у нас есть несколько вариантов в зависимости от наших требований:

Символ вопроса ? или {0,1}

Симол t может отсутсвовать или присутствовать в рамках символа { } это { 0 , 1 }.

DOS атаки вошли в чат. Catastrophic Backtracking (Катастрофический возврат)

Далее переходим к выражениям, неоптимальность которых может стать уязвимостью для атак типа DOS (Denial of Service - отказ в обслуживании) а точнее RegexDOS или ReDOS. Неоптимальные и сложные регулярные выражения могут потребовать экспоненциальной сложности для их обработки. Злоумышленник, зная об этом, может заспамить нас строками, которые быстро истощат наши процессорные ресурсы. Более подробную информацию по этой теме можно найти здесь. В качестве примера рассмотрим следующий запрос:

Не стоит паниковать, так как регулярные выражения позволяют нам написать защищенные от атак типа DOS выражения.

Символ плюса + или {1, } (от 1 до бесконечности)

Предположим, что символ "t" должен присутствовать, и при этом мы допускаем его повторение. Это эквивалентно записи {1,} (от 1 до бесконечности). Для этого используем символ "+":

Символ звездочки * или {0, } (те от 0 до бесконечности)

В последнем варианте предположим, что символ "t" может быть не включен, и при этом может иметь бесконечное количество повторений. То есть это эквивалентно записи {0,} или от 0 до бесконечности:

Сравним каждый из квантифаеров

Пересмотрим еще раз каждый из них и эквивалентное к ним { }:

• ? эквивалентна { 0 , 1 }

• * эквивалентна { 0, }

• + эквивалентна { 1, }

Cимволы \w \d \s и их отрицания \W \D \S

Некоторые из этих символов я уже упомянул в первой статье, но давайте повторим и добавим немного новых:

• \w - любый алфавитный символ (a-z,A-Z) и цифры 0-9 и подчеркивание _

• \d - цифры 0-9

• \s - символ пробелов такие как - пробелы, табы, переносы строк итд

В regex есть удобная функциональность инверсии выражений. Например если вместо \d мы напишем \D то выражение будет искать все символы исключая цифры.

Также для инверсии любого общего выражения можно достичь символом ^ но указав его внутри скобок. Например любой символ кроме a-b: [^a-b]

Группировка.

Группировка - важная функциональность регулярных выражений, которая позволяет:

1. Составлять более сложные запросы.

2. Извлекать данные из выражений.

Чтобы выделить выражение в группу, нужно обернуть его в скобки ( ). Рассмотрим ситуацию, где у нас есть записи о животных в формате "название животного дата рождения цвет" (разделенных пробелом). Давайте напишем выражение для извлечения только кошек (любого года рождения и цвета), выделив цвет и год рождения в группу:

Group 1 и Group 2 совпадают с нашими ожиданиями, но могут быть неудобными для чтения. Давайте воспользуемся еще одной возможностью и дадим им ярлыки. Для этого, внутри круглых скобок, нужно в самом начале добавить "?<label>", где "label" - это название группы. Например:

Применение регулярных выражений для промышленной задачи.

Итак, у нас перед нами задача: мы получили записи из ветклиники и хотим отфильтровать только валидные записи, а затем извлечь их для последующей аналитики.

Анализ входных данных

Теперь, когда у нас есть данные, нам нужно решить:

1. Какие данные считаются корректными?

2. Какие "отклонения" мы можем допустить?

Обычно ответы на эти вопросы предоставляются аналитиком, но в данном случае мы выполним все шаги самостоятельно. Итак, рассмотрим данные:

Из данных можно сделать вывод:

• Первые цифры определяют год, просто 4 фиксированные цифры.

• Данные разделены ";" (точкой с запятой) с потенциальными смежными пробелами.

• Последняя колонка с весом - это число с плавающей точкой.

Напишем выражение для каждой из групп

• дата (?<date>\d{4}) - ровно 4 цифры

• имя (?<name>[a-zA-Z]+) слово длины от 1 до бесконечности состоящие из букв алфавита

• животное (?<animal>(dog|cat|snake)) - лишь 3 вида допустимых животных собака, кошка, змея написанные строчными буквами

• вес (?<weight>\d+\.\d+) - два числа длины минимум 1 и до бесконечности, разделенные точкой

• между разделителями есть пробелы \s* (от нуля до бесконечности)

Итак, полученное выражение:

Предположим, что по требованиям нам нужно анализировать только собак, кошек и змей. Тогда наше конечное выражение будет выглядеть вот так:

(?<date>\d{4})\s*;\s*(?<name>[a-zA-Z]+)\s*;\s*(?<animal>dog|cat|snake)\s*;\s*(?<weight>\d+\.\d+)

Это регулярное выражение соответствует вашим требованиям для анализа записей о собаках, кошках и змеях. Оно разделяет данные на четыре группы: год, имя, вид животного и вес. Теперь проверим это выражение на наших данных:

Как мы могли бы улучшить запрос?

Наш первый вариант был слишком "жестким", и мы не предполагали, что животное может иметь заглавную букву. Давайте это поправим:

• Добавить ?i что даст нам (?i:(?<animal>dog|cat|snake)) чтобы не учитывать регистр животного

Защита от DOS атак.

Чтобы предотвратить возможность перегрузки системы, уберем использование *, + и укажем максимальный допустимый размер, используя {}.

После всех преобразований получаем:

(?<date>\d{4})\s{0,2};\s{0,2}(?<name>[a-zA-Z]{1,15})\s{0,2};\s{0,2}(?i:(?<animal>dog|cat|snake))\s{0,2};\s{0,2}(?<weight>\d{1,10}\.\d{1,5})

У нас получился классический нечитаемый регекс))

Новое выражение теперь учитывает и DOG и Cat благодаря ?i:. Все предыдущие записи были также включены, хотя все *, + были исключены из выражений.

Воспользуемые полученным выражением в Java.

Цель - отфильтровать все валидные записи и привести к типам Javav. Я не планировал сильно погружаться в детали реализации Regex классов в Java, поэтому ниже просто покажу рабочее решение:

Pattern, Matcher - классы для работы с Regex в Java.

В коде мы создаем объект класса Pattern и затем создаем Matcher на его основе. Класс Matcher позволяет обойти всe валидныe записи которые формирует наш Regex запрос используя метод matcher.find(). И затем вытаскиваем значения групп используя метод group("имя группы"). Результатом работы будет

И последнее. Полученные результаты совпадают с regex101.com, но нужно помнить, что у Java есть свои аспекты поддержки Regex, которые в редких случаях потребуют небольших изменений в регулярном выражении.

На этом рассказ про regex заканчивается, вот материалы. Материалы на которые стоит обратить внимание:

• Статья на дзене

• Документация от оракла про Regex в Java

Всем кому интересен мир разработки приглашаю в мой канал

Регулярные выражения, можно сказать, представляют собой своего рода язык запросов, благодаря которому можно выполнять следующие ключевые задачи:

• Валидировать строки

• Искать нужные подстроки в строках

• Извлекать необходимые данные

Regex не ограничивается только языком Java.

Этот язык используется повсеместно в области информационных технологий. Зная его, вы можете применять свои навыки в множестве контекстов. Поддержка регулярных выражений присутствует в большинстве языков программирования, и множество программ полагаются на регулярные запросы. В какой-то мере regex является стандартом, который полезно знать каждому.

Regex часто кажется сложным для понимания, особенно новичкам.

К сожалению, регулярные выражения, особенно если они написаны неоптимально, могут требовать много усилий для разбора конкретного выражения.

Существует множество решений для упрощения написания и тестирования регулярных выражений.

К счастью, существуют готовые онлайн-решения, которые существенно облегчают процесс понимания. Например, regex101.com - сервис, который мы будем использовать далее. Вот пример того, как мы валидируем формат даты:

Самые основы. Ищем котов.

Давайте начнем с самых основ. Допустим, у нас есть задача: мы хотим найти все упоминания слова 'cat' в строке 'catdogbananacat'. Выражение для этой задачи будет очень простым: 'cat'. Именно так, просто слово.

Теперь давайте посмотрим, что мы найдем, используя утилиту regex101.com:

Символ начала строки ^

Теперь найдем только котов которые стоят в самом начале строки а не в середине или конце, для этого воспользуемся симоволом ^ (циркумфлекс символ или символ "домика" или "крышечки" или caret на английском).

И так среди вариантов мы нашли 2 котов которые начинают строку.

Символ конца строки $

Также, аналогично предыдущему, давайте найдем только те варианты, где 'cat' будет заканчивать строку. Для этого воспользуемся символом $. Итак, наше выражение будет cat$.

Усложняем задачу, находим двух котов между которыми есть цифра. Символ числа \d

Теперь усложним задачу и найдем двух котов, между которыми есть цифра. Для этого мы используем \d (от слова 'digit' - цифра). Итак, искомое выражение будет 'cat\dcat'.

Знакомимся с \w и последовательностью +

Теперь предположим, что мы ищем двух котов, между которыми может быть несколько цифр, букв или подчеркиваний. Для этого воспользуемся \w, а затем добавим символ +, подсказыва регексу, что символов может быть больше одного. Конечное выражение: cat\w+cat

Перечисляем допустимые символы. Символ [ ]

Теперь сузим поиск и предположим, что мы ищем пару двух котов, между которыми есть лишь буквы a, b, c (либо их вариации). Для перечисления используем квадратные скобки: [abc], и добавим +, чтобы указать, что букв может быть несколько.

Указываем минимальную и максимальную длину. Символ { }

Теперь сузим поиск еще сильнее, предположим что в сумме букв a,b,c между котами может быть не менее 1 и не более 5 символов. Для этого воспользуемся фигурными скобками и получим выражение cat[abc]{1,5}cat

Добавляем вариации. Логическое ИЛИ. Символ |

Теперь допустим мы ищем всех котов между которыми может быть:

• Уже знакомый вариант с a,b,c которых не более 5 и не менее 1

• Либо слово dog

Для этого воспользуемся логическим выражением или используя | символ. Также чтобы указать что между двумя котами может быть лишь 1 вариант нам нужно использовать круглые скобки чтобы объединить их. Круглые скобки играют еще и другие роли (об этом будет позже). Итого наше выражение cat([abc]{1,5}|dog)cat

Резюмируя первую часть статьи.

И так мы хорошо поработали, теперь мы научились работать с такими иероглифами как:

• ^ начало строки, $ конец строки

• + несколько последовательных символов (неограниченное количество)

• \d любое число 0-9

• \w любой алфавитный, цифровой символ и подчеркивание

• [ ] - перечисление допустимх символов

• { } - указание минимальной, максимальной длины повторений

• | - логическое ИЛИ которое для большинства случаев требует наличие скобок ( )

Что дальше?

Итак, мы познакомились с довольно простыми вещами, которые не слишком иллюстрируют всю мощь регулярных выражений. В следующих частях мы узнаем еще больше магических символов и применим их для первых промышленных задач.

Тем, кто интересуется разработкой и всем, что с ней связано, приглашаю в мой телеграм канал.

Спасибо за внимание.