расставляй правильно приоритеты и не отвлекайся на мелочи

Проектирование высокопроизводительного поискового движка на базе MySQL для Audiogalaxy.com

Перевод: Design details of Audiogalaxy.com’s high performance MySQL search engine
Автор: Tom

Как я упоминал ранее, поиск — одна из самых интересных проблем, с которыми я работал на Audiogalaxy. Это одна из ключевых функций сайта, выполняющая иногда от 50 до 70 миллионов запросов в день. В пиковое время поисковому движку приходилось обрабатывать 1500-2000 запросов в секунду на базе данных MySQL с 200 миллионами строк. Довольно часто было тяжело проектировать при 10 или 100 кратном трафике (наш рост был настолько стремителен, что для решения проблемы, требующей нескольких недель, совершенно небыло времени) и это продолжалось до 4-го крупного изменения в кластерном дизайне, которое, как я думаю, решило проблемы роста.

Это диаграмма архитектуры с которой я закончил свою работу (разъяснение по компонентам будет ниже):

Стрелки показывают направление запросовых потоков для любой пары запрос/ответ. То, что Вы видите здесь — результат нескольких лет эволюционного улучшения, а не просто проект. В целом, сейчас кое-что изменилось, когда у меня было несколько недель для того, что-бы сфокусироваться на поиске. Этого было достаточно, для внесения улучшений, но недостаточно для того, что-бы сделать координальные изменения.

Серверы сателиты, Satellite Servers (300+ серверов, написаны на C)

Клиенты файлового шаринга (сателиты) держали открытые соединения с серверами сателитами и эти серверы являлись последней инстанцией о доступности файлов. Информация о доступности использовалась для сортировки результатов непосредственно перед выводом для пользователя.

Гейтвеи, Gateways (4 сервера, написаны на C)

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

Для обработки поисковых запросов гейтвеи были источником «текущей доступности» для каждого поискового результата. Доступность использовалась в качестве помощи при сортировке результатов — нам было необходимо показать файлы, которые на данный момент были доступны, выше, в поисковых результатах, чем те, которые были недоступны. Гейтвеи могли отвечать на эти запросы без опроса каких-либо других серверов, поэтому такая схема подходила для запроса большого количества результатов единовременно.

Кэш, Caches (4 сервера, написаны на C)

Я называл их кэширующими серверами, но в конечном счете, они делали большинство тяжелой работы для каждого поиска в дополнение к кэшированию результатов. Они принимали запросы и постраничные разбивки от веб серверов, кэшировали результаты с индексных серверов на диск, опрашивали базы данных и гейтвеи на предмет отсортированной информации и возвращали набор результатов. В ранней версии поиска результаты не кэшировались на отдельных серверах и большинство обработки делалось в PHP на веб серверах. Манипулирование большими массивами результатов в PHP было высокоэффективным, но это было поначалу, было удобно свободно оттачивать поисковый алгоритм в скриптовом языке на связываясь с перекомпиляцией и «перетрубациями».

Эти сервера также использовались для сортировки результатов по релевантности. Результаты сортировались дважды. Первая сортировка осуществлялась по сложившейся доступности и происходила в момент, когда результирующий набор (который мог состоять из множества тысяч строк) первоначально кэшировался на диск. Эта «доступность» хранилась в базе данных и ежедневно обновлялась путем добавления текущей доступности к половине предыдущей. Вторая сортировка базировалась на информации о текущей доступности с гейтвеев и происходила всякий раз, когда результирующий набор был доступен с диска. Это была не совсем честная сортировка; она просто давала уверенность в том, что не смотря на сложившуюся доступность, любая недоступная на данный момен композиция не будет показана в результатах до доступной на данный момент мелодии. Это гарантировало, что новые песни, которые могли быть загружены сразу, выпрыгивали вперед песен, которые были популярны, но на данный момент не имели доступного источника.

Кэш серверы были разделены так, что каждый уникальный поисковый запрос имел свой результирующий кэш на одном единстенном сервисе. Каждая поисковая строка была превращена в уникальный ID и этот номер использовался для определения, какой из кэш серверов должен был выдать результат. Для улучшения эффективности кэширования, я использовал в своих интересах тот факт, что наш поисковый движок игнорировал порядок слов и дублирование, поэтому я выбрасывал все дубликаты и сортировал слова перед хэшированием (переводом строки запроса в ID). Таким образом, фразы “A A B”, “B A”, или “A B B” хэшировались в одинаковый ID и имели одинаковые результаты.

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

Каждый сервер содержал многотысячные кэшированные результаты хранящиеся на диске. Для предотвращения захламления файловой системы у нас было 65K папок в двух уровнях по 256 папок в каждом, проименованных от 00 до FF. Каждый результирующий файл идентифицировался хэшем строки запроса с помощью первых 4-х шестнадцатеричных цифр, определяющих в какой папке он находится.

Индексные серверы, Index Servers (4 сервера, написаны на C)

Эти сервера были реализованы как обратные индексы для всего поискового содержимого в нашей базе MySQL. Индекс имел 2 компоненты: гигантскую хэш-таблицу слов (которая держалась в памяти) и дисковое хранилище строк с ID, которые соответствовали каждому слову. Очевидно, что индексные серверы обрабатывали запросы, но они также следили за двумя типами изменений в базе данных. Первое, каждый сервер искал новые строки в основной таблице. Второе, они искали новые строки в обновленных базах, которые использовались для того, что-бы сказать поисковому движку о необходимости переиндексации существующих строк. Из-за того, что там могло быть несколько тысяч миллионов проиндексированных строк, для поискового движка было бы накладно постоянно «обшаривать» целую таблицу. Поэтому, я использовал обновленные таблицы с триггерами при изменениях, когда я удалял или редактировал строку, которая уже была в индексе.

Для обработки запросов я использовал алгоритм инвертного индекса прямо из «Управляя Гигабайтами» (Managing Gigabytes). Каждый запрос был разбит на слова и каждое слово использовалось как ключ из хэш-таблицы. Запись хэш-таблицы содержала счетчик, сколько строк совпадает с этим словом и расположение на диске для чтения полного списка ID. Затем сервис мог повторять очередную итерацию для слов от наименьшего количества строк к наибольшему и выявлять списки пересечений слова. Выполняя эффективное пересечение списков, мы можем «проходить» небольшой список и делать двоичный поиск в следующем — большом. Каждое пересечение производит новый список, который был пересечен со следующим большим списком.

Сам по себе алгоритм простой и мощный, но первой сложной частью было управление дисковым вводом-выводом, который всегда являлся узким местом для таких сервисов как этот. Мне был не нужен поиск для неявных слов (The UncommonWords) тянущий за собой все ID которые бы использовали слово the. Вторая сложная часть управлялась с организацией обновлений на индексах. Если сервис индексировал новую строку со словом the, я не хотел рисковать, и записывать полный список слов на диск. Поэтому, сервис держал список мелких ID в памяти и комбинировал его с дисковыми списками, если такое было необходимо. Периодически, списки из памяти комбинировались с основными и сбрасывались на диск.

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

Веб сервера, Web Servers (Apache, PHP скрипты)

После того, как все было спроектировано и реализовано, веб серверам не надо было выполнять много работы . Они подсоединялись через TCP соединение к соответствующему кэш серверу, отправляли поисковую строку и то, какое количество результатов они хотели получить на странице, в ответ получали ID найденных строк и индексы их популярности. Затем, они искали найденные строки в базе данных MySQL, что-бы получить оригинал их данных и выводили страницу.

Коммуникационные протоколы, Communication Protocols

Все коммуникации между моими сервисами использовали свой собственный протокол, не SOAP или какой-нибудь, основанный на HTTP. Основная масса пропускной способности между сервисами утилизировалась рассылкой длинных списков целочисленных ID, в обратном и прямом направлениях, и свой протокол легко с этим справлялся, оптимизируя коммуникации. Я думаю, что это также упрощало использование «долгоживущих» соединений между кэширующим и индексным уровнем.

Жизненный цикл запроса, The Life Of A Query

Итак, давайте соберем все это вместе. Что происходило, когда пользователь запускал поиск:

  • Пользователь жмет “Search” и HTTP POST отправляется на один из веб серверов балансирующих нагрузку.
  • Веб сервер обрезает из поисковой строки дубликаты, сортирует слова, хэширует результат и использует полученное значение для работы с кэш сервером. Он устанавливает TCP соединение с кэш сервером и отправляет запрос, блокируя процесс до того времени, пока не вернется результат.
  • Кэш сервер принимает запрос с веб сервера. Если для запроса еще нет результатов по искомому файлу, то он случайным образом выбирает один из индексных серверов и используя пул соединений отправляет запрос дальше.
  • Индексный сервер принимает запрос и строит список строк с ID используя алгоритм инвертного индексирования описанный выше. Он отправляет список ID обратно к кэш серверу.
  • Принимая то, что у нас не было готового кэш результата, кэш сервер принимает ID список назад с индексного сервера. Затем он опрашивает базу данных для получения сложившейся доступности файлов. Используя это, он сортирует результаты и записывает их на диск.
  • Используя отсортированные результаты (либо с диска или из памяти, если они только что получены от индекс сервера), кэш сервер отправляет список ID к случайному гейтвей серверу, который сообщает о текущей доступности каждого файла.
  • Кэш уровень корректирует результирующий порядок на основании текущей доступности. Затем, он индексируется в результаты основанные на запрошенном интервале от веб сервера и небольшая порция ID записывается обратно на веб сервер.
  • Веб сервер снимает блокировку процесса и принимает найденные ID от кэш сервера. Он опрашивает базу данных для получения всего необходимого, чтобы сформировать страницу, форматирует результаты, сжимает это все gzip’ом и отправляет веб браузеру.
  • Пользователь получает результат и радуется (надеюсь).

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

Моей любимой частью всего этого был запуск tail -f на логах индексных серверов. У нас был превосходный коэффициент эффективности поиска на кэш уровне, поэтому на индексных серверах, и я действительно это видел, были только запросы с серьезными орфографическими ошибками и забавными словами.

Во всяком случае, надеюсь, что это будет кому-то полезно. Когда я писал это, я думал, что этот пост поможет разъяснить эволюцию проектирования и позволит приобрести некоторые полезные знания.