Website development
27 October 2008

Атомарность операций и счетчики в memcached

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

Сегодня речь пойдет о:
  • атомарных операциях в memcached;
  • реализации счетчиков просмотров и онлайнеров.

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


Атомарность операций в memcached


Как таковые, все одиночные запросы к memcached атомарны (в силу его однопоточности и корректных внутренних блокировок в многопоточном случае). Это означает, что если мы выполняем запрос get, мы получим значения ключа таким, как кто-то его записал в кэш, но точно не смесь двух записей. Однако каждая операция независима, и мы не можем гарантировать, например, корректность такой процедуры в ситуации конкурентного доступа из нескольких параллельных процессов:
  1. Получить значение ключа «x» ($x = get x).
  2. Увеличение значения переменной на единицу ($x = $x + 1).
  3. Запись нового значения переменной в memcached (set x = $x).

Если данный код выполняют несколько frontend’ов одновременно, может получиться так, что значение ключа x увеличится не n раз, как мы задумывали, а на меньшее значение (классическое состояние гонки, race condition). Конечно, такой подход неприемлем для нас. Классический ответ на сложившуюся ситуацию: применение синхронизационных примитивов (семафоров, мутексов и т.п.), однако в memcached они отсутствуют. Другим вариантом решения задачи является реализация более сложных операций, которые заменяют неатомарную последовательность get/set.

В memcached для решения этой проблемы есть пара операций: incr/decr (инкремент и декремент). Они обеспечивают атомарное увеличение (или, соответственно, уменьшение) целочисленного значения существующего в memcached ключа. Атомарными являются также дополнительные операции: append/prepend, которые позволяют добавить к значению ключа данные в начало или в конец, также в каком-то плане атомарными можно считать операции add и replace, которые позволяют задать значение ключа, только если он ранее не существовал, или, наоборот, заменить значение уже существующего ключа. Об еще одном варианте атомарных операций речь пойдет в разделе про реализацию блокировок средствами memcached.
Необходимо дополнительно отметить, что любая блокировка в memcached должна быть мелкозернистой (fine-grained), то есть должна затрагивать как можно меньшее число объектов, так как основная задача сервера в любом случае – обеспечивать эффективный доступ к кэшу как можно большего числа параллельных процессов.

Счетчики в memcached


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

Счетчик просмотров


Пусть в нашем проекте есть некоторые объекты (например, фото, видео, статьи и т.п.), для которых мы должны в реальном времени показывать число просмотров. Счетчик должен увеличиваться с каждым просмотром. Самый простой вариант – при каждом просмотре обновлять поле в БД, не будет работать, т.к. просмотров много и БД не выдержит такую нагрузку. Мы можем реализовать точный и аккуратный сбор статистики просмотров, их аккумулирование, и периодический анализ, который заканчивается обновлением счетчика в базе данных (например, раз в час). Однако остается задача показа текущего количества просмотров.

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

Необходимо отметить, что приведенная схема не является вполне корректной: в ней присутствует состояние гонки (race condition). Если два frontend одновременно обращаются к счетчику, одновременно обнаруживают его отсутствие, и сделают две операции set, мы потеряем один просмотр. Это можно считать не очень критичным, так как процесс аккумулирования статистики восстановит правильное значение. В случае необходимости можно воспользоваться блокировками в memcached, речь о которых пойдет ниже. Или же реализовать инициализацию счетчика через операцию add, обрабатывая её результат.

Счетчик онлайнеров


Существует еще один вид счетчиков, который без memcached или подобного ему решения вряд ли может быть реализован: это счетчик «онлайнеров». Такие счетчики мы видим на большом количестве сайтов, однако в первую очередь необходимо определить, что же именно мы имеем в виду под «онлайнером». Пусть мы хотим рассчитать, сколько уникальных сессий (пользователей) обратилось к нашему сайту за последние 5 минут. Уникальность обращения пользователя с данной сессией в течение 5 минут можно отследить, сохраняя в сессии время последнего засчитанного обращения, если прошло более 5 минут – значит это новое (уникальное) обращение.

Счетик онлайнеров

Итак, выделим в memcached шесть ключей с именами, например, c_0, c_1, c_2, …, c_5. Текущим изменяемым ключом мы будем считать счетчик с номером, равным остатку от деления текущей минуты на 6 (на рисунке это ключ c_4). Именно его мы будем увеличивать с помощью операции incr для обращения каждой уникальной в течение 5 минут сессии. Если incr вернет ошибку (счетчика еще нет), установим его значение в 1 с помощью set, обязательно указав время жизни 6 минут. Значением счетчика онлайнеров будем считать сумму всех ключей, кроме текущего (на рисунке это ключи c_0, c_1, c_2, c_3 и c_5).

Когда наступит следующая минута, текущим изменяемым ключом станет ключ c_5, при этом его предыдущее значение исчезнет (т.к. он был создан 6 минут назад с временем жизни те же 6 минут). Значением счетчика станет сумма ключей c с_0 по c_4, т.е. только что рассчитанное значение ключа с_4 уже начнет учитываться в отображаемом значении счетчика.

Такой счетчик может быть построен и на меньшем числе ключей. Минимально возможными для данной схемы являются два ключа: один обновляется, значение другого показывается, затем по прошествии 5 минут счетчики меняются местами, при этом тот, который только что обновлялся, сбрасывается. В приведенной схеме с многими ключами обеспечивается некоторое «сглаживание», которое обеспечивает более плавное изменение счетчика в случае резкого притока или оттока посетителей.

+41
6.3k 147
Comments 12