Узкое место
Нам хотелось бы начать с описания того, как мы избавились от узкого места в важной программе нашей вычислительной системы.
Наша входящая почта поступала к нам через одну машину, называемую шлюзом (gateway), которая объединяла нашу внутреннюю сеть с внешним Интернетом. Электронная почта, приходящая извне, – в нашу организацию, насчитывающую несколько тысяч человек, приходят десятки тысяч писем в день – поступает на шлюз и затем передается во внутреннюю сеть; такое разделение изолирует нашу локальную сеть от доступа из Интернета и позволяет указывать адрес только одной машины (этого самого шлюза) для всех членов организации.
Одной из услуг, предоставляемых шлюзом, является защита от "спама" (spam – мясные консервы, содержащие в основном сало), незатребованной почты, рекламирующей услуги сомнительных достоинств. После первых успешных испытаний спам-фильтр был установлен на шлюз и включен для всех пользователей нашей внутренней сети – и немедленно возникла проблема. Машина, исполняющая роль шлюза, уже несколько устаревшая и без того достаточно загруженная, была буквально парализована: поскольку фильтрующая программа работала слишком медленно, она отнимала гораздо больше времени, чем вся остальная обработка сообщений, и в результате доставка почты задерживалась на часы.
Это пример настоящей проблемы производительности: программа была не в состоянии уложиться во время, отводимое ей на работу, и пользователи серьезно от этого страдали. Программа должна была работать гораздо быстрее.
Несколько упрощая, можно сказать, что спам-фильтр работает примерно так: каждое входящее сообщение рассматривается как единая строка, которая обрабатывается программой поиска образцов с целью обнаружить, не содержит ли она фраз из заведомого спама – таких, как "Make millions in your spare time" (сделайте миллион в свободное время) или "XXX-rated" (крутые порно). Подобные сообщения имеют тенденцию появляться многократно, так что подобный подход достаточно эффективен, тем более что если какой-то спам проходил через фильтр, то характерные фразы из него добавлялись в список.
Ни одна из существующих утилит сравнения строк – вроде grep – не устраивала нас по соотношению производительности и возможностей, поэтому для спам-фильтра была написана специальная программа. Первоначальный код ее был весьма прост, он просматривал каждое сообщение и проверял наличие в нем заданных фраз (образцов):
Как можно сделать этот код более быстрым? Нам нужно искать в строке, а лучшим способом для этого является функция strstr из библиотеки языка С: она стандартна и эффективна.
Благодаря профилированию – технологии, о которой мы поговорим в следующем параграфе, – мы выяснили, что реализация strstг такова, что использование ее в спам-фильтре неприемлемо. Изменив способ работы strstг, можно было сделать ее более эффективной для данной конкретной проблемы.
Существующая реализация strstг выглядела примерно так:
