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

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

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

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

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

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

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

Можно предложить следующую схему: мы больше не ограничиваем время жизни ключа с кэшом в 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 вернет ошибку «такой ключ уже существует», значит, блокировка была захвачена раньше каким-то другим процессом.