Что такое — выглядит как мемкеш, ведет себя как мемкеш, но не мемкеш?

    Доброго дня, коллеги!



    Сегодня я расскажу вам о том, как не внося большого количества изменений в приложение улучшить его быстродействие. Речь пойдет о нашем небольшом «велосипеде» [1], призванном заменить memcache в некоторых случаях.

    Статья написана по моему докладу «Кругом обман или использование стандартных протоколов для нестандартных вещей» [2] на DevConf'12.

    Введение


    Недавно мы уже рассказывали об архитектуре сети мобильной рекламы Plus1 WapStart. Если вы не читали, можете ознакомиться по ссылке.

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

    Логику подбора баннера можно разбить на 3 этапа:
    1. Определение характеристик запроса.
    2. Подбор подходящих под запрос баннеров.
    3. Отсечки во время выполнения.


    Проблемным для нас оказался этап под номером 1. Причем беда пришла откуда не ждали — из
    Индии.
    Индия здесь рассматривается по той причине, что для нас она является редким траффиком и был реальный бизнес-кейз, когда Индия к нам пришла


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

    Но в случае, когда к нам приходит Индия, в кеше у нас практически ничего нет и 70-90% запросов уходит в базу. Это доставляет определенные проблемы и мы отдаем баннер чуть медленнее, чем хотелось бы.
    Пришла Индия

    И тут нам пришла идея, как можно решить проблему скорости отдачи баннера.

    Проект «Рыба»: идея


    Рыба: Идея

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

    В силу того, что для кеширования мы используем memcache, было решено использовать его протокол для реализации обозначенной идеи.

    Проект «Рыба»: итерация первая


    Рыба: Первая итерация

    Реализация достаточно стандартна. Есть набор worker'ов, которые принимают соединения (их количество конфигурируется). Worker'ы обращаются к хранилищу за получением данных. Хранилище отдает ответ. В случае, когда данных нет, мы добавляем запрос в очередь. Кроме того, существует отдельный поток наполнения, который берет запросы из очереди и просит предоставить данные о них у библиотеки. Полученные данные добавляются в хранилище.

    Библиотека может быть любая. В нашем случае она запрашивает данные из БД.

    Логику приложения мы изменили таким образом, чтобы характеристики запроса брались из нашего кеша (из запроса формируется ключ и мы просим get key_with_request_characteristics). В данной конфигурации все работало отлично за исключением нескольких проблем.

    Проблемы и их решение


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

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

    Проект «Рыба»: итерация вторая


    Рыба: Вторая итерация

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

    Первое — это Normalizer. Все запросы мы нормализуем (приводим к стандартному виду). И в хранилище ищем данные уже по нормализованному ключу.

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

    Второе — это Hasher. Он служит для сравнения данных. Теперь мы не добавляем одни и те же данные в хранилище дважды.

    Если раньше мы хранили пару ключ-значение, то сейчас мы храним ключи и данные отдельно. Между ключами и данными существует связь один-ко-многим (одни данные могут соответствовать множеству ключей).

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

    Проблемы и их решение


    Удаление производится по следующему алгоритму. Мы ищем среди ключей те, что уже устарели и удаляем их. Затем проверяем данные, если существуют такие, для которых не осталось ключей — мы их удаляем.

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

    Решение тут как мне кажется, вполне очевидно. Мы добавили индекс на время добавления ключа. Если необходимо удалить данные, мы обходим ключи по данному индексу и удаляем до лимита, тем самым минимизирую расход времени.

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

    Заключение


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

    Это конечно не последняя реализация (можно считать это альфой), мы работаем над повышением производительности и смежными задачами. Но уже сейчас код можно посмотреть на GitHub [3]. Проект получил название swordfishd [1]. Там же можно найти другие наши продукты отданные на растерзание в open-source.

    Ссылки


    1. Проект «Рыба»
    2. Презентация доклада
    3. WapStart GitHub
    WapStart
    Company
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 4

      +4
      Какая интересная статья.

      1. Судя по схемам, вы уперлись в СУБД, и к самой рыбе особых требований по скорости рассасывания очереди не предъявляется. Можно было оставить хранилище на мемкеше, и рыба работала бы просто как контроллер мемкеш-очередь-субд?

      2. Опять же если рыбу можно было бы рассматривать просто как контроллер, можно было бы реализовать на php ее? То есть приложение смотрит в memcache, если не находит там ничего, добавляет запись в очередь и отдает пустой ответ. А работающая рыба на фоне просто бы разруливала эту очередь. Была бы стандартная схема.

      3. Опять же, может имело смысл расширить функционал memcache? По сути вам надо было его научить ходить в БД, добавлять очередь.
      +3
      Интересная статья, но, кажется, можно было сделать проще. Дополнительно к мемкешу поднимается демон очереди, после чего пишется такая логика:

      * Если попали — ОК
      * Если промах — добавляем запрос в очередь
      * На другом конце очереди крутятся воркеры на Perl/Python/ваш_любимый_язык, которые ходят с запросами в базу и кладут их в мемкэш.

      Такое решение не рассматривалось?
        +2
        Мы думали об этом, более того, хотели именно так и реализовать. А потом придумали альтернативу. Мотивация была следующая:
        * Один коннект и 1 запрос к хранилищу — это всегда лучше, чем два коннекта и два запроса (к хранилищу и диспетчеру очередей). Сеть тоже надо беречь.
        * В нашем случае в приложении не пришлось ничего править.
        * Это прикольно.

        В качестве побочный продукта мы получили хранилище нужной нам структуры: у нас k=>v — это многие к одному, что в нашем случае очень хорошо.

      Only users with full accounts can post comments. Log in, please.