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

    Similar posts

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

    More
    Ads

    Comments 12

      +1
      полезная статья.
        0
        Есть вот такое решение для счетчиков: saterenko.ru/2008/05/10/memcounter/
        Насколько я понимаю, оно уже используется автором в одном из проектов, по описанию мне очень понравилось.
          +2
          Собственно атомарных инкремента и декремента достаточно для реализации стандартных методов синхронизации.
            +1
            Проверяем флаговую переменную. Если нет её в кеше — ставим равной единице, если есть и не ноль — цикл ожидания «освобождения» переменной. Если есть и ноль, тогда инкремент флаговой переменной. Читаем значение, если получаем — декремент. Если не получаем — лезем в базу, сет, декремент.

            Если ждем долго — генерим эксепшн по факту блокировки.
              +2
              Я в следующем посте напишу простой и корректный способ на add/delete, больше ничего не нужно ;) Для реализации двоичного семафора
            +2
            Существует еще один вид счетчиков, который без memcached или подобного ему решения вряд ли может быть реализован


            MySQL heap table + raplace. Выбор по неравенству с использованием ключа по времени. Очистка мусора, аналогичная той, которую php по-умолчанию использует для очистки старых сессий. Будет нормально работать при довольно существенной нагрузке. Счётчик числа посетителей «online» без списка самих посетителей редко когда нужен.

            Мне кажется, лучше преподносить материал как один из возможных способов, а не как истину в последней инстанции.
              +1
              Memcached работает гораздо быстрее. Это не истина в последней инстанции, но кол-во запросов в секунду, которые способен выполнить MySQL на порядки ниже аналогичной цифры в memcached.
                0
                С технологической точки зрения — да. Но, мне кажется, что кроме оптимизации ради оптимизации есть ещё много интересных занятий.

                А с точки зрения проекта видеть список присутствующих людей, а не только их количество скорее приятно, чем нет.
                  +1
                  Я не понял последний абзац про людей.

                  Эти посты — о memcached, и действительно без него или подобного ему сделать описанный счетчик вряд ли удастся на нагруженном сайте. Когда цифры будут добираться, например, до 30000 человек поситетелей, нам нужно будет инкрементировать счетчик 100 раз в секунду (если считаем онлайнеров за 5 минут = 300 секунд). 100 запросов в секунду для БД является паразитной нагрузкой, т. к. она умеет многое, но ради фактически увеличение значения ключа выполняет очень много посторонней работы, лучше те же 100 запросов в секунду отдать под полезную для БД функциональность.
                    +1
                    100 раз в секунду — как раз плюнуть.

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

                    Мне бы не понравилось если бы задача по выводу списка людей «онлайн», решалась так: «Аналитическое исследование показало, что реализация данной задачи приведёт к „паразитной“ нагрузке, исчисляемой 100 запросами каждую секунду, поэтому было принято решение отказаться от вывода списка, а выводить и вычислять только количество». Другое дело, если бы ответ был бы таким: «Вывод списка посетителей „онлайн“ потребует дополнительных вычислительных мощностей». Я могу представить, что такое может случиться, может быть, в случае проекта на 1 000 000 пользователей и 10 000 000 обращений в сутки, 5000 в пике (ткнул пальцем в небо).

                    На моей практике такого не было, скажем, даже при общей нагрузке в ~500 запросов в секунду к базе (пиковое значение) если говорить конкретно про этот способ. MySQL в умелых руках, всё же, не так плох, как его представляют.
                      0
                      juks, я не спорю, что это можно сделать с помощью MySQL. Можно с помощью локальных файлов, можно с помощью еще чего-то. Например, если у меня одна морда, можно в shared memory хранить — будет куда проще и быстрее.

                      Но memcached выдержит гораздо большую нагрузку (чем MySQL), его API в данной ситуации даже проще, чем у БД. Memcached может быть полезен для проекта не только для счетчика онлайнеров, и здесь тоже его можно применить.

                      Согласен, что фраза «только на memcached» некорректна, будет правильнее написать «что достаточно эффективно» или «гораздо лучше, чем на MySQL».
                        0
                        Рад, что мы друг друга поняли

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