Проблема одновременного перестроения кэшей

    Серия постов про “Web, кэширование и memcached” продолжается. Начало здесь: 1, 2 и 3.
    В этих постах мы поговорили о memcached, его архитектуре, возможном применении, выборе ключа кэширования, кластеризации, атомарных операциях и реализации счетчиков в memcached.

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

    Следующий пост будет посвящен тэгированию кэшей.

    Одновременное перестроение кэшей


    Данная проблема характерна в первую очередь для высоконагруженных проектов. Рассмотрим следующую ситуацию: у нас есть выборка из БД, которая используется на многих страницах или особо популярных страницах (например, на главной странице). Эта выборка закэширована с некоторым «сроком годности», т.е. кэш будет сброшен по прошествии некоторого интервала времени. При этом сама выборка является относительно сложной, её вычисление заметно нагружает backend (БД). В какой-то момент времени ключ в memcached будет удален, т.к. истечет срок его жизни (срок жизни был установлен у кэша), в этот момент несколько frontend’ов (несколько, т.к. выборка часто используется) обратятся в memcached по этому ключу, обнаружат его отсутствие и попытаются построить кэш заново, осуществив выборку из БД. То есть в БД одновременно попадет несколько одинаковых запросов, каждый из которых заметно нагружает базу данных, при превышении некоторого порога запрос не будет выполнен за разумное время, еще больше frontend’ов обратятся к кэшу, обнаружат его отсутствие и отправят еще больше запросов в базу данных, с которыми база данных тем более не справится. В результате сервер БД получил критическую нагрузку, и «прилёг». Такая ситуация называется dog-pile effect (см. также, например: korchasa.blogspot.com/2008/04/dog-pile.html). Что делать, как избежать такой ситуации?

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

    Можно предложить следующую схему: мы больше не ограничиваем время жизни ключа с кэшом в memcached – он будет там находиться до тех пор, пока не будет вытеснен другими ключами. Но вместе с данными кэша мы записываем и реальное время его жизни, например:

    {
        годен до: 2008-11-03 11:53,
        данные кэша:
        {
           ...
        }
    }
    

    Теперь при получении ключа из memcached мы можем проверить, истёк ли срок жизни кэша с помощью поля «годен до». Если срок жизни истёк, кэш надо перестроить, но мы будем делать это с блокировкой (о блокировках речь пойдет в следующем разделе), если не удастся заблокироваться, мы можем либо подождать еще (раз блокировка уже есть, значит кэш кто-то перестраивает), либо вернуть старое значение кэша. Если заблокироваться удастся, мы строим кэш самостоятельно, при этом другие frontend’ы не будут перестраивать этот же кэш, так как увидят нашу блокировку. Основное преимущество хранения в memcached без указания срока годности – именно возможность получить старое значение кэша в случае, если кэш уже перестраивается кем-то. Что именно делать – ждать, пока кэш построит кто-то другой, и получать новое значение из memcached, или возвращать старое значение, – зависит от задачи, насколько приемлемо старое значение и сколько можно провести времени в состоянии ожидания. Чаще всего можно позволить себе 2-3 секундное ожидание с проверкой удаления блокировки и, если кэш так и не построился (что маловероятно, получается что выборка происходит больше чем за 2-3 секунды), вернуть старое значение, освобождая frontend для других задач.

    Пример такого алгоритма


    1. Получаем доступ к кэшу cache, его срок жизни истёк.
    2. Пытаемся заблокироваться по ключу user cache_lock.
      • Не удалось получить блокировку:
        • ждём снятия блокировки;
        • не дождались: возвращаем старые данные кэша;
        • дождались: выбираем значения ключа заново, возвращаем новые данные (построенный кэш другим процессом).
      • Удалось получить блокировку:
        • строим кэш самостоятельно.

    Такая схема позволяет исключить или свести к минимуму ситуации «заваливания» backend’а одинаковыми «тяжелыми» запросами, когда реально запрос достаточно выполнить лишь один раз. Остается последний вопрос, как обеспечить корректную блокировку? Очевидно, что так как проблема одновременного перестроения возникает на разных frontend’ах, то блокировка должна быть в общедоступном для них всех месте, то есть в memcached.



    Блокировки в memcached


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

    Пусть мы хотим заблокироваться по ключу ‘lock’: пытаемся получить значения ключа с помощью операции get. Если ключ не найден, значит блокировки нет, и мы с помощью операции set устанавливаем значение этого ключа, например, в единицу, а время жизни устанавливаем в небольшой интервал времени, который превышает максимальное время жизни блокировки, например, в 10 секунд. Теперь, если frontend завершится аварийно и не снимет блокировку, она автоматически уничтожится через 10 секунд. Итак, с помощью set мы блокировку установили, выполнили все необходимые действия, после этого снимаем блокировку просто удаляя соответствующий ключ командой del. Если на первой операции get мы получили значение ключа, это означает, что блокировка уже установлена другим процессом, наша операция блокировки неуспешна.

    Описанный способ обладает недостатком: наличием состояния гонки (race condition). Два процесса могут одновременно сделать get, оба могут получить ответ, что «ключа нет», оба сделают set, и оба будут считать, что установили блокировку успешно. В ситуациях, как одновременное перестроение кэшей, этого может быть допустимо, т.к. здесь цель не исключить все другие процессы, а резко уменьшить количество одновременных запросов к БД, что может обеспечить и этот простой, некорректный вариант.

    Второй вариант корректен, и даже проще первого. Для захвата блокировки достаточно выполнить одну команду: add, указав имя ключа и время жизни (такое же маленькое, как и в первом варианте). Команда add будет успешной только в том случае, если ключа в memcached еще нет, то есть наш процесс и есть тот единственный процесс, которому удалось захватить блокировку. Тогда нам надо выполнить необходимые действия и освободить блокировку командой del. Если add вернет ошибку «такой ключ уже существует», значит, блокировка была захвачена раньше каким-то другим процессом.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 34

      0
      Планируются ли после цикла теоритических статей практические примеры?
        +1
        Практическим примером могло бы быть выкладывание нашего frameworkа, но он большой, толстый, тесно связанный друг с другом, и вряд ли он был бы хорошим примером. Если будет большой интерес, можно было бы его зарефактирить, и отдельные компоненты выложить в open-soruce.

        Если, конечно, к этому делу есть большой интерес.

        Хотя, так или иначе, все описанные подходы реализованы описанным или похожим образом в различных framework'ах, но единого места я не знаю.
        0
        Я думаю, что хабрасообществу было бы очень интересно почитать о методах слежением за кешем (попаданиями в кэш и т. д.), используя, например тот же cacti.
          0
          Как мониторить memcached? Я, если честно, не админ. Но это, имхо, тривиальная задача: берем любой язык программирования с клиентом Memcached, отправляем запрос статистики, получаем результат, нужные нам числа, отдаем их в мониторинг. Немного о сборе статистики будет в шестом посте, он будет опубликован в субботу.

          Или я не понял процесса?
            0
            Я имел ввиду в боевых условиях, когда нагрузка большая и нужно следить за работой сайта с кэшем в том числе.
              0
              Под Java я собираюсь делать MBean (JMX), который при вызове метода (например getBytes). Будет лезть в Memchached (то есть по факту в драйвер, который будет ходить по серверам и брать с них данные) и забирать из него строку со статистикой, потом она парсится и из неё выбирается свойство 'bytes' и возвращается. Потом кто-то соединяется JMX клиентом, вызывает этот метод и получает данные.
            +2
            Если кому-то данная тема интересна, могу попробовать сам написать подробную статью по настройке и использованию в боевых условиях cacti для слежения за кэшем.
              0
              Это было бы замечательно!
            +2
            Недавно отказался от блокировок через мемкешед
            Как работало — да также как и описано, только блокировка для исключения гонок была обернута два раза
            (блокировка самой блокировки, блокировка нужного ключа, разблокировка блокировки ээ блокировки)
            Если заблокироваться не получилось — ждал 5 миллисекунд и пробовал еще раз

            Учитывая что у меня 60% обращений к кешеду идут через блокировку — за один рендер страницы получал до 17 таких обращений( итого по статистике базы 47% getов уходили в missы )

            Решение на самом деле простое — еАкселератор :)
            у него есть lock\unlock — нативно на мутексах. Скорость работы — в сотни раз быстрее чем кешед( потому что мутекс, локально и не надо «ждать» «ручками»)

            Одна проблема — у меня 3 фронтенда, а локи акселератора — локальны.
            Но получается так что ОЧЕНЬ редко уходить в реген кеша на двух серверах всеже лучше чем тормозить с «глобальной» блокировкой мемкешедом.

            Либо я ее криво реализовал
              +1
              Именно криво.
              В данном случае идиально работать так:
              Если данные устарели — memcache_add — если true, запускаем регенерацию данных. если memcache_add вернул false — просто выводим старые данные. В итоге гарантированно только один процесс будет обновлять данные. А ждать их обновления ИМХО бесмысленно, лучше вывести старые данные, ведь задержка в 1 секунду в обновлении погоды не делает.
                0
                Тогда вот хитрый вопрос — срок годности хранить вместе с кэшируемыми данными или отдельным ключиком($name.':expires')
                Вариант 1- необходимость качать больше данных
                Вариант 2- удваивает колво запросов, благо есть batch варианты работы…

                Имхо все мои проблемы в том что кеш у меня экспайриться честно.
                Вот он был, и вот его нет
                  0
                  И что из этого? Добавляете к данным expire, либо делаете 2 ключа и batch вариант (хотя я бы лучше просто сделал бы $mem->set('key', array($_SERVER['REQUEST_TIME'] + $expire, $data), null, $expire + 10);
                  В итоге у вас в кеше данные есть всегда, когда один из процессов ставит блокировку, остальные имеют доступ к пусть и старым данным, но актуальность в милисекунды не такая уж и большая, так что их можно просто выводить, а когда блокировка снимется, в кеше будут уже свежие данные. В среднем у вас не будет расхождения даже в секунду, так что практически идиальное решение из всех предложенных, что я видел если кол-во серверов у вас > 1, в больших проектах особенно актуально будет :) Для проектов в 1 сервер можно обойтись APC, XCache, eAccelerator (в этом смысле хорошо написать небольшую прослойку, которая работает с несколькими backend).

                  Кстати, кто знает как сделаны блокировки в Zend Framework и есть ли они там вообще для memcache и ему подобных? :)
                0
                А вас не смущает нарушение целостности кэша?
                Если фронтенды ваши используются для распределения нагрузки и клиент рэндомно попадает на один из них, то несколько «рефрешей» одной и той же страницы могут легко вернуть ему разные результаты в зависимости от того, когда обновлялся кэш на каждом из фронтендов.
                Не говоря уже о полной избыточности кэша, что приводит к неэффективному использованию памяти.

                Кстати, сама идея двойной блокировки звучит как-то мутно, похоже на «костыль».
                  0
                  Я в жизни какбы нормальный С програмер.
                  Тама двойная обвертка мутексами — нормальное дело

                  А как у меня в принципе и без кеша страницы генеряться быстро — с кешем просто еще быстрее
                  Но самое главное — очень низкое покрытие страниц пользователями.
                  Меньше чем 1 пользователь на страницу глобально, и меньше 2х пользователей на элемент кеша в секунду, а генерация страницы — меньше полсекунды.
                  На пустом сервере так вообще бывает по 10мсек.

                  Итого считаем вероятность того что сервера начнут рефрешить контент одновременно…
                  В телефонии есть понятие «эрланг» в геймдеве — «фейк», а у нас пускай будет «плотность запросов на рефреш кеша»

                  по мне так намного эфективнее и «круче» будет отойти от «базовой» работы с кешедом и перейти на batch варианты…

                  Недавно пробовал «ручками» собрать страницу когда она не линейно рендерилась а вначале был большой такой memcache_get(array) потом разбор, потом при необходимости большой set

                  вот это дает просто фантастические результаты(у меня 5 демонов) несравнимые с моей костыльной оптимизацией локов…
                  но блин, как смастерить это не ручками под тест а в промышленных масштабах под все сайты- убейте не понимаю.

                    0
                    А как у меня в принципе и без кеша страницы генеряться быстро — с кешем просто еще быстрее
                    Но самое главное — очень низкое покрытие страниц пользователями.
                    Меньше чем 1 пользователь на страницу глобально, и меньше 2х пользователей на элемент кеша в секунду, а генерация страницы — меньше полсекунды.
                    На пустом сервере так вообще бывает по 10мсек.

                    ИМХО вам тогда кэш вообще не нужен :)

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

                    Вот над этим и стоит работать :)
                      0
                      Без кеша никуда :(
                      Запросов в секунду много.
                      Запросов одномоментно тоже много
                      если скрипты будут чуть дольше работать — увеличиться колличество одномоментных обработок.
                      А процессор не резиновый — время генерации глобально увеличиться…
                      Замкнутый круг

                      >Вот над этим и стоит работать :)
                      Это должна быть какая-то очень хитрая и умная модель, и чую хрен автоматизируешь :(
                        0
                        Модель можно придумать, как всегда вопрос упирается в эффективность и прочее. На самом деле, если бы обращения к memcached не были бы синхронными, можно было бы сделать асинхронную модель, когда генерация по сути идёт параллельно, и мы параллельно ждем выборок из memcached.

                        Моя мечта в этом плане — концпеция Deferred из Twisted, то, что я описываю, на опыте PHP, там, к сожалению, так не сделаешь.

                        А вообще более правильный уход от кэширования — это тот или иной Application Server, когда бы мы могли держать в памяти объекты, а не результаты выборок по их представлением в БД. Но это всё мечты в разных направлениях.

                        В суровой модели оптимизации кода вида БД+PHP+Memcached+что-то еще надо двигаться во всех направлениях, начиная от клиентской оптимизации заканчивая запросами из БД, кол-вом обращений в memcached, мониторингом серверов. Это такой бесконечный бой за производительность, причем memcached — далеко на самая большая проблема.
                0
                можно тупой вопрос: чем add отличается от set?
                  +1
                  add сработает только тогда, если такого ключа уже ещё нету. set же либо обновит данные, либо добавит с таким ключём
                    0
                    Чёрт, промазал. sunnybear это тебе :)
                      0
                      нее, в принципиальном смысле. Почему в конце утверждается, что add лучше, чем set? Они этих операции унарны
                        0
                        Принципиально и различаются тем, что set всё равно, есть ли уже данные в кеше или нет. А вот add добавляет только тогда, когда данных в кеше нету. В остальном они одинаковы.
                          +1
                          Не нашел этого места. А для локов — таки да, лучше add, чем set+get, ибо атомарен.
                            0
                            Как совершенно верно написал korchasa, add лучше, чем get+set, именно в силу атомарности. Одна операция атомарна, а две уже нет.
                        –1
                        Кстати, если я правильно понял идею автора, то в качестве ключа блокировки нужно использовать не просто 'lock', а '<имя_ключа>_lock'.
                        Ведь одновременно могут устареть сразу несколько ключей и возникнет конфликт имён.

                        Кстати, недавно читал идею по устранению dogpile-эффекта родными (а значит — быстрыми) методами memcached. Минус один — размер кэша вырастает в 2 раза. Но это лишь идея, которую можно развивать дальше.
                          0
                          Ну конечно, блокировка должна зависеть от имени ключа, иначе будет одна блокировка на все кэши :) Просто чтобы не городить подробности написал так.
                        • UFO just landed and posted this here
                            +1
                            В таком подходе есть минус — если есть такие долгие выборки и кэш по ним перестраивает фронтенд (клиентский запрос), то какой-то незадачливый клиент будет долго-долго ждать пока у него загрузится страница.

                            Я долгие перестроения кэша делаю двойной буферизацией, когда свежую версию кэша формирует параллельный процесс по крону, а в это время фронтендам отдается версия из буфера.
                              +1
                              Я совершенно согласен, долгие выборки должны делаться отдельно, по ним могут строиться вспомогательные таблицы или кэши в разных ситуациях.

                              Однако бывают иногда ситуации, когда в процессе работы БД запрос, который был раньше быстрым, становится «медленным», сама по себе это несмертельно может быть, но в сочетании с описанным эффектом может быть критично для функицонирования сервиса. Рассмотренный выше подход можно рассматривать как такой «ремень безопасности», который не позволяет ситуации выйти на критический уровень.
                              0
                              Отличная серия статей — спасибо! (:
                              Что вы думаете если использовать смешаные схемы кеширования/блокировки?
                              Например memcached для хранения кэша, а eaccelerate для семафоров блокировки?
                                +1
                                eAccelerator, как и любое другое локальное (по отношению к frontend) решение нельзя использоваться для «честной» блокировки, если frontendов больше одного, т. к. блокировка будет действовать на один frontend. В данном конкректном случае это может быть приемлемо, если frontendов мало, тогда вероятность одновременно несколькими мордами формировать кэш остается невысокой.
                                  0
                                  Ясно, про множествой frontend-ов я не подумал.

                                  Даже с блокировками на основе memcached есть вероятность одновременой перестройки кеша.
                                  Так как команды последовательной записи / чтения блокировок не атомарны.

                                  Идея kashey блокировки блокировок смотрится даже очень аправданой, имхо.
                                    +1
                                    Прав был смира.
                                    Операция add также атомарна как и все остальные.
                                    Только если я после этого начинал «ждать» (usleep) то хитроумный просто отдавал контент который «все еще был в кеше»
                                    Вчера уже переписал свой код и работаем по новому.
                                    На скорость не появлияло(у меня редкие взаимные блокировки) зато совесть и за сервер спокойно :)

                                    Еще круче конечно было бы при экспайре кеша заносить ИД страницы в некую таблицу( заносить ИД кеша всеже не реально )
                                    Потом демоном апдейтить эти страницы по мере сил и способностей.
                                      0
                                      Нет, при корректной блокировке в memcached вероятности одновременного перестроения нет.

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