Как одно изменение ускорило загрузку правил фильтрации в Safari в 5 раз

Сегодня я хочу поделиться историей о паре регулярных выражений — небольшая неточность в них в конечном итоге стоила миру более 50 миллионов часов процессорного времени на устройствах iOS.

Предупреждение: в этом посте много технических деталей, и его сложно читать, если вы не умеете программировать.

Как работают блокировщики контента в Safari

Сначала объясню, как работают блокировщики рекламы в Safari — без этого сложно двигаться дальше. AdGuard на iOS использует встроенный механизм Safari — Content blockers (блокировщики контента).

Также поддерживается альтернативный подход — declarativeNetRequest (DNR), частично совместимый с Chrome и Firefox. Интересно, что в случае Safari правила DNR незаметно переводятся в правила блокировщиков контента Safari.

Самая первая версия AdGuard для iOS была выпущена в октябре 2015 года, и мы сразу же столкнулись с неприятной проблемой. Исторически сложилось так, что блокировщики рекламы всегда использовали свой собственный синтаксис правил фильтрации. Он мощный и специально разработан для веб-фильтрации. Однако Apple представила свой собственный подход, который значительно отличался от того, к чему привыкло сообщество разработчиков фильтров.

Забегая немного вперёд: когда Chrome представил declarativeNetRequest, они также пошли своим путём. По крайней мере, когда дело дошло до сопоставления URL, их синтаксис был гораздо ближе к тому, к которому мы привыкли.

Вот пример того, как стандартное правило AdGuard преобразуется в синтаксис, поддерживаемый Safari:

Обратите внимание на то, что происходит с шаблоном URL. В фильтрах AdGuard мы используем синтаксис, похожий на подстановочные знаки и специально разработанный для URL-адресов. Причина проста: традиционные регулярные выражения слишком медленны для этой задачи.

Регулярные выражения

Блокировщики контента Safari, с другой стороны, полагаются на регулярные выражения — хотя и в очень упрощённой форме, чтобы их всё ещё можно было скомпилировать в структуру, ускоряющую сопоставление.

Если вам интересно узнать о внутреннем устройстве: Safari создаёт байт-код DFA из шаблонов регулярных выражений, который затем выполняется пользовательским интерпретатором: DFABytecodeInterpreter.cpp.

Регулярные выражения более универсальны, чем стандартный синтаксис блокировщика рекламы. К сожалению, эта гибкость не имеет большого значения для фильтрации веб-контента. На деле мы получаем очень медленную компиляцию правил, которая потребляет много ресурсов, а также строгие ограничения на количество правил, которые могут содержать фильтры. Мы уже писали о проблемах Safari, и большинство из них по-прежнему актуальны.

Преобразование шаблонов 1.0

Итак, в 2015 году нам нужно было выяснить, как преобразовать шаблоны URL-адресов AdGuard в регулярные выражения, которые бы принимал Safari.

В то время перед нами стояли две основные задачи.

Во-первых, нам нужно было сократить общее количество правил в окончательном наборе. Тогда у Safari был жёсткий лимит в 50 000 правил. Мы описывали, как справились с этой задачей, в посте о блокировке рекламы в Safari.

Впоследствии лимит был увеличен до 150 000 правил. Однако из-за ограничений памяти процесса на практике можно использовать только около 60–80 тысяч. Мы несколько раз сообщали об этом Apple (отчёты Apple Feedback Assistant: FB19728743, FB13282146), но безрезультатно.

Вторая задача заключалась в том, чтобы убедиться, что сгенерированные нами регулярные выражения были достаточно эффективными для быстрой работы и достаточно лёгкими, чтобы iOS мог их скомпилировать. В те дни мы иногда видели, как система убивала процесс com.apple.Safari.ContentBlockerLoader, потому что он потреблял слишком много ресурсов.

После множества ручных тестов мы остановились на том, что казалось оптимальными правилами преобразования:

• Символ || (начало URL) стал ^[htpsw]+://([a-z0-9-]\.)?
• Символ ^ (разделитель) — [/:&?]

Мы были уверены, что сделали всё необходимое, поэтому перестали об этом беспокоиться и оставили всё как есть — почти на десять лет.

Мы ошибались

Всё началось с другого сообщения об ошибке. Проблема заключалась в том, что наш стандартный метод преобразования слегка изменил семантику специального символа ||. На iOS он в конечном итоге соответствовал только одному уровню поддомена, в то время как во всех других версиях AdGuard он соответствовал всем уровням.

Простым решением было использовать регулярное выражение, первоначально предложенное разработчиками WebKit ещё в 2015 году — то самое, которое мы тогда отвергли как «неоптимальное». Но мы были настолько уверены в своём выборе, что до недавнего времени даже не удосужились его перепроверить.

Изменения, которые мы должны были внести, были предельно просты:

• Заменить || на ^[^:]+://+([^:/]+\.)?
• Заменить ^ в большинстве случаев на [/:]

Была ли разница настолько велика? Оказалось — да, была.

Ох, как же мы ошибались

После замены на новые регулярные выражения мы провели несколько быстрых тестов, и результаты поразили нас. Скорость загрузки правил в Safari не просто немного улучшилась — она взлетела до небес.

Если говорить цифрами: компиляция Фильтра счётчиков и систем аналитики в Safari стала в 5,5 раз быстрее, а компиляция Базового фильтра — в 2,8 раз быстрее.

Чтобы было понятнее, посмотрите видео ниже:

Если посчитать количество пользователей AdGuard за последнее десятилетие и количество раз, когда приложению приходилось перекомпилировать фильтры, то количество потраченного впустую времени процессора составляет как минимум 50 миллионов дополнительных часов на устройствах iOS.

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

Так в чём же заключалась наша ошибка? Думаю, всё дело в несовершенной методологии тестирования. Мы пытались судить «на глаз», вместо того чтобы:

1. Определить чёткий набор критериев: использование памяти, скорость и фактическая производительность блокировщика контента в браузере.
2. И, что наиболее важно, научиться точно измерять эти показатели. Не визуально оценивая монитор активности или top, а используя нормальный профилировщик.

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