Что такое «контент» для видеохостинга? Во-первых, контент видеохостинга – это просто видео, которое представляет собой набор файлов в различных форматах, в частности, в формате FLV для просмотра пользователем через Flash Player. Эти файлы статичны, видеохостинг при загрузке пользователем видеоролика осуществляет конвертацию во все требуемые форматы с необходимым битрейтом. Хранение такого контента — это хранение обычных файлов, только довольно большого размера. Отдача контента — это, по сути, организация скачивания файлов. Во-вторых, контент видеохостинга — это «живые» потоки или вещания. Вещания не записываются на диск, не происходит их конвертация, потоки раздаются клиентам с учетом пропускной способности каналов (происходит пропуск пакетов, если канал клиента недостаточен для получения потока вещания в полном качестве). Отдача контента в данной ситуации — это раздача потока на большое количество подключенных пользователей (тысячи смотрящих).

Кроме как таковой задачи отдачи контента (корректность, работа под нагрузкой и т.п.) актуальной является проблема «приближения» контента к пользователю. Необходимо организовать доставку контента так, чтобы пользователь получал видео или вещание с сервера, который расположен близко к нему с точки зрения пропускной способности сетевых каналов, а также с точки зрения стоимости трафика для пользователя.

Данная статья, написанная по материалам доклада на конференции «РИТ: Высокие нагрузки»-2008, расскажет об одном из возможных подходов к решению поставленных задач. Рассказ будет основан на нашем опыте проектирования, разработки и поддержки видеохостинга Smotri.Сom, который является сегодня самым крупным видеохостингом Рунета. Описываемые подходы могут быть применимы в областях с похожими характеристиками контента: достаточно большой объем файлов, много файлов, различные виды вещаний и т.п.

Статья будет состоять из двух частей: в первой части речь пойдет об организации файлового хранилища для видеофайлов и об общих аспектах организации вещания. Во второй части будет представлен способ организации CDN (Content Delivery Network), то есть способ «приближения» контента к конечному потребителю, а также применение этого подхода к доставке статических файлов (файлов видео) и к потоковой трансляции (вещания).

Видео: организация файлового хранилища

Видеофайлы

Видеохостинг в процессе своего функционирования получает видео в различных форматах, которое загружается пользователями. Кроме хранения оригинального видеофайла, видеохостинг осуществляет конвертацию файла в ряд форматов: FLV, 3GP, MP4 и т.п. Все эти файлы необходимо хранить на файловых серверах, а также отдавать пользователям. Рассмотрим сначала вопрос хранения таких файлов.

Что представляют из себя эти файлы? Согласно нашим расчетам, в среднем для хранения одной секунды видео требуется 250 Кб дискового пространства (имеется в виду 250Кб/с на все форматы видео вместе взятые), при этом средняя длительность видео составляет примерно 4 минуты. Легко посчитать, что для хранения 1 млн. видеофайлов нам потребуется 60 Тб дискового пространства, что является уже достаточно внушительной цифрой. Этим объемом хранения надо эффективно управлять, а также обеспечивать раздачу такого объема контента пользователям. Кроме непосредственно видеофайлов нам придётся хранить и отдавать вырезанные из видео кадры, которых в нашем случае будет 15 штук: 5 кадров, вырезанные из разных участков видео, каждый из которых представлен в трех различных размерах (для показа информации о видео в блоках разного формата).

Доступ к файловому серверу через WebDAV

Непосредственно за хранение файла отвечает файловый сервер, в котором есть достаточно хорошо построенная дисковая подсистема в плане надежности и скорости доступа (RAID). Запросы на изменение файлов (создание новых файлов, удаление старых и т.п.) поступают с другой группы серверов: с «морд» (frontend) и с перекодировщиков. Морды – это обычные сервера, которые обслуживают подавляющее большинство запросов по HTTP как непосредственно к самому сайту, так и к его API. Перекодировщики принимают запросы от пользователей на загрузку исходных файлов видео и осуществляют их конвертацию. Итак, на морде или перекодировщике формируется заказ на операцию с файлами на файловом сервере, т.к. файловая система не является локальной, необходимо то или иное сетевое средство доступа к файловому серверу.

Самое простое решение – это NFS, которое может сохранить для кода сайта «ощущение», что файлы находятся локально, забирая при этом на себя все сложности по выполнению удаленных операций через сеть. Однако NFS может вести себя крайне ненадежно при падении сетевого соединения между мордой и файловым сервером, а также в силу того, что и морд, и файловых серверов десятки, количество кросс-маунтов NFS становится слишком большим.

Самым простым решением в такой ситуации может быть WebDAV. WebDAV является расширением HTTP, который, кстати, изначально предполагал, что содержимое World Wide Web является не статичным, а изменяемым. WebDAV делает еще один шаг вперед, добавляя в HTTP полноценные возможности по удаленному изменению, созданию, удалению файлов, каталогов, получению информации о файлах и т.п.

Внутри кластера серверов видеохостинга обращение к файловым серверам идёт по протоколу WebDAV. Скачивание файлов (в том числе проигрывание видео в Flash Player) идёт напрямую с файлового сервера, что позволяет более равномерно загрузить сетевые каналы, исключая «лишние» промежуточные звенья.

Выбор файлового сервера из кластера

Предположим, у нас есть кластер файловых серверов, все настроены, готовы отдавать файлы, а также принимать новые файлы через WebDAV. Было загружено видео. Какой файловый сервер выбрать для хранения очередного файла? Выбор можно осуществить, например, на основе следующих характеристик:

• объем свободного места/объем сервера;
• нагрузка на сервер (как измерять?);
• случайный выбор.

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

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

Необходимое ПО

Описанный выше подход требует простого и распространенного программного обеспечения: для скачивания файлов подойдет любой «быстрый» HTTP-сервер, например, nginx, lighttpd и т.п. При этом для обеспечения подгрузки FLV в плеер с любой временнóй отметки (так называемого «стриминга»), нам необходимо очень простое расширение, которое сегодня присутствует как в nginx, так и в lighttpd (flv-streaming). В качестве WebDAV-сервера подойдет Apache httpd и т.п. Для доступа к файлам по WebDAV можно использовать любой WebDAV-клиент, который есть в том или ином виде практически во всех языках программирования. Так, например, в PHP он реализован в виде PEARовского класса (который приходится «допиливать», чтобы обеспечить разумную производительность). WebDAV не обеспечивает функциональности по получению объема свободного места на диске, но это легко обойти с помощью простейшего скрипта в cron, который вывод команды df перенаправляет в файл в корне файлового сервера, а этот файл уже можно скачать по HTTP с любой морды.

Кросс-бэкап

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

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

Вещания: ретрансляция

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

Вещание представляет из себя видео и аудио потоки, которые кодируются на стороне клиента с помощью Flash Player, затем с помощью протокола RTMP отправляются на сервер вещаний, который раздает эти RTMP-потоки всем подключенным к вещанию зрителям. Здесь основной проблемой является то, что поток раздается клиентам хоть и без перекодирования (в качестве и с битрейтом, заданным автором трансляции), но количество клиентов, подключенных к вещанию, может составлять тысячи человек. При этом каждому клиенту может доставляться измененный поток в соответствие с пропускной способностью каждого клиента (пропуск пакетов в потоке). Кроме того, в RTMP-потоке кроме собственно потока вещания происходят удаленные вызовы процедур (сервер-клиент или клиент-сервер), а также транслируется состояние разделяемых объектов между всеми подключенными к вещанию клиентами.

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

Чудесная возможность Vim'а! Да поможет она повышению грамотности наших разработчиков. Проверка орфографии умная, понимает, что именно в исходном файле стоит проверять (например, комментарии), а что не стоит (например, ключевые слова).

Итак:

1. Качаем отсюда словарь: http://ftp.services.openoffice.org/pub/OpenOffice.org/contrib/dictionaries/ru_RU.zip
2. Раскрываем архив в папку /tmp/dict.
3. mkdir -p ~/.vim/spell/

Запускаем Vim, делаем:

:mkspell! ~/.vim/spell/ru /tmp/dict/ru_RU

Вуаля! Словарь готов! (Всё описанное выше - подготовительный этап, это надо сделать всего один раз).

Включение проверки на русском и английском (для текущего буфера):

:setlocal spell spelllang=ru_ru,en_us

Дополнительно о проверке орфографии:

:help spell</p></body></html>

Мы представляем начало нашего маленького проекта по выкладыванию в open-source исходного кода наших проектов (полностью или частично). Первой ласточкой становится маленькая библиотека, предназначенная для работы с Deferred из Twisted Framework в qooxdoo на JavaScript.

Практически полностью код был взят из MochiKit.Async и адаптирован под qooxdoo. Полезные нововедения: если если в течение 1 секунды не будет обработана ошибка в Deferred (выполнение дойдет до конца цепочки callback, и останется ошибка), о ней будет сообщено на консоль, как о возможно необработанном исключении.

Если Вы еще не знаете, что такое Deferred, я бы рекомендовал обратиться к Twisted Handbook. Со своей стороны обещаю как можно скорее написать о Deferred по-русски.

Итак, страничка qx.Deferred.

Пример кода:

function callRPC(method, params)
{
    this.debug("API: call " + method + " with params: ");
    this.debug(params);
    var d = new netstream.lib.Deferred();
var rpc = new qx.io.remote.Rpc();
rpc.setTimeout(10000);
rpc.setUrl(this.__api_url);
rpc.callAsync(
    function (result, ex, id)
    {
        if (ex == null)
            d.callback(result);
        else
            d.errback(ex);
    },
    method, params);

var that = this;
d.addCallback(function (result) { that.debug("API: result:"); that.debug(result); return result; });
d.addErrback(function (ex) { that.error(ex); return ex; });
return d;



};
d = callRPC("somemethod", { 'someParams' });
d.addCallback(function (result) { alert("Got result: "+result); });

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

Сегодняшний пост завершает эту серию, в нём обзорно мы поговорим о технических "мелочах":

• анализ статистики memcached;
• отладка memcached;
• "RPC" с помощью memcached.

Полный текст всех разделов в виде одной большой PDF-ки можно скачать и посмотреть здесь (в разделе "Материалы").

Статистика работы memcached

Кроме необходимости реализовать механизмы работы с memcached, необходимо постоянно заниматься мониторингом кластера memcached-серверов, чтобы быть уверенным, что мы достигли оптимальной производительности. Memcached предоставляет набор команд для получения информации о его работе.

Самая простая команда, stats, позволяет получить элементарную статистику: время работы сервера (uptime), объем используемой памяти, количество get запросов и количество хитов (hits), т.е. попаданий в кэш. Их соотношение позволяет нам судить об эффективности кэширования в целом, хотя необходимо учитывать, что в memcached ключами являются не только закэшированные выборки, но и счетчики, блокировки, тэги и т.п., так что для вычисления чистой эффективности кэширования это значение требует корректировки. Из общей статистики мы также можем узнать, сколько ключей было удалено раньше истечения срока жизни (evictions), данный параметр может сигнализировать о недостаточности объема памяти memcached.

Slab-аллокатор

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

Механизм его работы заключается в том, что вся доступная memcached память делится на slab’ы (блоки), каждый из которых будет хранить элементы определенного размера. Например, slab для хранения объектов размером 256 байт, при этом сам slab имеет размер 1 Мб, таким образом он может сохранить 4096 таких объектов. Память внутри такого slab’а выделяется только по 256 байт. Если у нас есть slab’ы для объектов размером 64, 128, 256, 1024 и 2048 байт, то максимальный размер объекта, который мы можем сохранить – 2048 байт (в последнем slabе). Если мы хотим сохранить объект размером 65 байт, под него будет выделена память в slab’е-128, 1 байт – в slab’е 64.

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

Здесь на горизонтальной оси отложены размеры slab’ов, а на вертикальной – объем памяти, используемый slab’ами данного размера. В данный момент вся память memcached занята ключами и их значениями, поэтому данный график представляет собой текущее распределение значений в памяти сервера. Легко видеть, что больше всего slab’ов выделено под ключи с относительно небольшими значениями – до 20 Кб, для больших по размеру ключей slab’ов гораздо меньше. Такое распределение адекватно нашей задаче: у нас больше всего именно маленьких ключей (счетчики, блокировки, небольшие кэши). При этом эти же ключи занимают и бóльшую часть памяти, с локальными пиками выделения под ключи размером 300 байт, 8 Кб. Если график отличается от того, который ожидается по логике задачи, это повод для беспокойства.

Отладка проектов, использующих memcached

Мы написали большую подсистему для работы с memcached, реализовали различные механизмы решения проблем, связанных с высокой нагрузкой. Как проверить, что всё действительно работает так, как нам бы этого хотелось? Высокую нагрузку, сетевые задержки и т.п. практически невозможно воспроизвести в локальном окружении, непросто это сделать и в тестовом окружении. На серверах в production нам доступны лишь те механизмы отладки, которые не затрагивают нормальное функционирование самого приложения. Способ отладки не должен вносить ощутимых временных задержек, иначе он изменит поведение приложения, и отладка станет бессмысленной.

Можно предложить следующий «трюк», который может помочь в данной ситуации: для каждого кэша (ключа в memcached) или для группы кэшей (ключей) мы заводим отдельный файл в локальной файловой системе. В этот файл в режиме append мы дописываем по одному символу в ответ на каждое логическое действие, которое произошло с кэшом. Для просмотра в реальном времени поведения кэширующей подсистемы достаточно сделать tail –f на этот файл:

MLWUHHHHHHHHHHHHHHHMLLHHHHHHHHHH

Пусть буквы имеют следующий смысл:

• M – кэш устарел (или не найден);
• L – попытка заблокироваться;
• W – запись (и построение) нового кэша;
• U – удаление блокировки;
• H – успешный запрос кэша.

Тогда по приведенной последовательности можно рассказать то, что происходило с данным кэшом: вначале он отсутствовал, мы кэш не обнаружили (M), попытались заблокироваться (L) для его построения, заблокировались, построили кэш (W), сняли блокировку (U), затем какое-то время кэш успешно работал, отдавая закэшированные данные (H). Потом в какой-то момент кэш устарел или был сброшен (M), мы попытались заблокироваться, не получилось (L), попытались еще раз (L), блокировка оказалась снята, кто-то другой построил новый кэш, мы его прочитали (H) и дальше им пользовались.

Межпроцессное взаимодействие с помощью memcached

Сложный проект состоит из отдельных компонент, сервисов, которые должны взаимодействовать друг с другом, используя механизмы RPC, вызовы API, обмениваясь информацией через БД или каким-то еще способом. Иногда для такого обмена информацией можно использовать и memcached.

В качестве примера рассмотрим сервис пользовательских вещаний: существует какое-то количество вещаний, в каждом из которых в данный момент времени находится некоторое количество зрителей. Популярность вещания определяется количеством зрителей. Актуальной информацией о количестве зрителей обладает только сервер вещаний, а список вещаний на странице вещаний формирует frontend. Конечно, можно было бы сделать так, чтобы сервер вещаний периодически сбрасывал в БД или через API в frontend информацию о количестве зрителей, или frontend мог бы через API сервера вещаний получать актуальную информацию. Однако количество зрителей – очень быстро меняющаяся характеристика, и в данной ситуации можно просто из сервера вещаний периодически (раз в несколько секунд) сохранять в memcached информацию о количестве зрителей в каждом из вещаний, а frontend, обращаясь к memcached, может получить информацию в любой удобный момент. Таким может быть межпроцессное взаимодействие, реализованное с помощью memcached.

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

Сегодня мы поговорим о тэгировании кэшей и о возможности сброса сразу группы кэшей в memcached.

Последний, шестой пост, будет посвящен различным техническим вопросам работы с memcached: анализу статистике, отладке и т.п.

Сброс группы кэшей

Если мы закэшировали какие-то данные от backend’а, например, выборку из БД, рано или поздно исходные данные изменяются, и кэш перестает быть валидным. Причем очень желательно, чтобы кэш сбрасывался сразу же за изменением, иначе пользователь после редактирования может увидеть старую версию объекта, что его, несомненно, смутит. Есть простой вариант ситуации: мы меняем информацию об объекте с ID 35, и сбрасываем кэш выборки этого объекта по параметру ID=35. На практике же чаще всего один и тот же объект явно или неявно входит в большое количество выборок, а значит и кэшей.

Рассмотрим такой пример: мы написали блогохостинг, в нем большое количество блогов. Когда один из авторов создает новый пост, меняется большое количество выборок: посты на главной странице и всех вторых страницах списка постов (т.к. все посты «сдвинулись» на один), изменилось количество записей в календаре постов, изменилась RSS-ка, и т.п. Конечно, мы могли бы поставить кэшам этих выборок небольшое время жизни, тогда через какое-то время они сбросятся и будут отображать правильную информацию, но слишком короткое время кэширования (5 секунд, например), будет давать низкое соотношение хитов в кэш, увеличивая нагрузку на БД, а более длительное будет создавать у пользователя ощущение, что информация после создания поста не обновилась, а, значит, пост не добавился. В то же время можно заметить, что в рамках блогохостинга если даже мы сбросим все кэши, связанные с данным блогом, это совсем небольшой процент от общей массы кэширования (т.к. блогов очень много). Остался вопрос: как найти и проидентифицировать все кэши данного блога? Какие-то из них мы можем легко построить, для некоторых это становится уже неудобно: например, количество кэшей постраничного списка постов зависит от количества страниц, которое еще необходимо вычислить. Что же делать?

Одно из возможных решений – тэгирование кэшей. Описанный ниже способ тэгирования по своей сути совпадает с описанным Дмитрием Котеровым в его наблах, но был нами разработан независимо. Существуют и другие варианты тэгирования, например, патч memcached-tag на memcached.

Тэг кэша

Итак, мы вводим новое понятие – тэг кэша. Один кэш может нести с собой список тэгов, с которыми он связан. Сам по себе тэг – это некоторое имя и связанная с ним версия (число). Версия тэга может только монотонно увеличиваться. Группой кэшей мы будем называть кэши, имеющие один общий тэг. Для того чтобы сбросить группу кэшей, достаточно увеличить версию соответствующего тэга.

На программном уровне мы знаем, что данная выборка должна быть закэширована и что её кэш будет связан с тэгами tag1 и tag2 (данный факт определяется логикой работы нашего приложения). При создании кэша мы записываем в него кроме данных закэшированной выборки еще текущие (на момент создания кэша) версии тэгов tag1 и tag2. При получении кэша мы считаем его валидным если не истекло время его жизни, и при этом текущии версии тэгов tag1 и tag2 равны версиям, записанным в кэше. Таким образом, если мы изменяем (увеличиваем) версию тэга tag1, все кэши, связанные с этим тэгом, которые были построены ранее, перестанут быть валидными (т.к. в них записана меньшая версия тэга tag1).

Рассмотрим пример с нашей выборкой, пусть было так:

Версии тэгов:
  tag1 -> 25
  tag2 -> 63
Кэш выборки:
  [
    срок годности: 2008-11-07 21:00
    данные кэша: [
                     …
                  ]
    тэги: [
         tag1: 25
         tag2: 63
          ]
   ]

Затем произошло некоторое событие, и мы решили сбросить все кэши, ассоциированные с тэгом tag2, т.е. мы увеличили версию тэга: tag2++. Изменились версии тэгов:

Версии тэгов:
  tag1 -> 25
  tag2 -> 64

Теперь наш кэш перестал быть валидным, не смотря на то, что его «срок годности» еще не истёк: версия тэга tag2, сохраненная в нем (63) не совпадает с текущей версией (64).

Версии тэгов

Тэги (то есть их версии) имеет смысл хранить там же, где мы и храним наши кэши, то есть в memcached. Для каждого тэга мы создадим ключ с именем, совпадающим с именем тэга, его значением будет версия тэга. Осталось решить, что использовать в качестве версии тэга? Можно было бы использовать просто числа, инкрементируя их при изменении версии тэга, но это может привести к некорректному поведению при условии возможной потери ключей. Пусть версия тэга равнялась единице, мы закэшировали выборку с этим тэгом, записали в кэш значение тэга – единицу. Затем ключ с версией тэга был удален из memcached, а в следующий момент времени мы захотели сбросить выборки, связанные с тэгом, то есть необходимо увеличить версию тэга. Так как мы потеряли значение версии тэга, мы снова поставим единицу, и теперь наш кэш будет считаться валидным, хотя он сбросился (не важно, какое значение выбирать при увеличении версии тэга, если она была потеряна – всегда возможна ситуация, что это же значение использовалось и ранее).

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

Использование текущего времени в качестве версии тэга даёт еще одно преимущество в ситуации, когда БД проекта устроена по схеме мастер-слейв репликации. При изменении исходного объекта в БД мы изменяем версию тэга, связанного с ним (записываем туда текущее время, то есть время изменения). В другом процессе мы обнаруживаем, что кэш устарел, то есть его надо перестроить, перестроение – это читающий запрос (SELECT), который необходимо отправить на слейв-сервер БД, но в силу задержек репликации слейв-сервер еще мог не получить актуальную версию объекта в БД, в результате мы кэш сбросили, но при его перестроении снова закэшировали старый вариант объекта, что неприемлемо. Можно использовать версию тэга при решении вопроса, на какой сервер БД отправить запрос: если разница между текущим временем и версией какого-либо тэга кэша меньше некоторого интервала, определяемого максимальной задержкой репликации, мы отправляем запрос на мастер-сервер БД вместо слейва.

Использование такой схемы тэгирования увеличивает количество запросов к memcached, т.к.

нам необходимо для каждого кэша получать версии его тэгов. Накладные расходы можно сократить за счет использование multi-get запросов memcached, а также за счет локального кэширования ключей memcached в пределах одного процесса (если один и тот же тэг привязан к нескольким кэшам).

Продолжение следует...

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

Следующий забавный случай взаимодействия частей Twisted Framework заставил меня потерять час времени, спешу рассказать, в надежде, что это спасет чьё-то время. Итак, в Twisted есть модуль логгинга, twisted.python.log, в котором есть удобный метод log.err(), который позволяет записать в лог информацию о текущем исключении. А trial - это framework для написания юнит-тестов из того же Twisted. Их сочетание иногда приводит к проблеме :)

Итак, у меня был блок кода, похожий на пример ниже:

from twisted.python import log
def catcher(f):
  try:
    return f()
  except GoodException:
    return 'ERROR'
  except:
    log.err()
    raise UnknownException

По смыслу он должен был логировать все неожиданные исключения и заменять их на более разумные. Я написал юнит-тест на такую функцию примерно следующего вида:

def testCatcher():
  def raiseBadException():
    assert False 
  self.assertEquals('ERROR', catcher, raiseBadException)

При запуске юнит-тест говорил, что он завершился с ошибкой, т.к. было выброшено исключение

exceptions.AssertionError, т.е. то исключение, которое генерирует строка 3 в тесте. Но ведь оно было поймано catcher? Я долго бился с этой ситуацией (на самом деле код был сложнее, но суть его от этого не менялась), пока не понял, что если из-под trial (запускальщика юнит-тестов) сделать twisted.python.log.err, то вместо того, чтобы вывести в лог исключение, он помечает тест как ошибочный, при этом в качестве причины ошибки выводит текущее исключение! То есть тест отрабатывал штатно, но log.err() мой помечал его как ошибочный.

Вот такое вот не совсем очевидное взаимодействие...

Update: на самом деле "правильный" способ это исправить - использовать TestCase.flushLoggedErrors. Спасибо @paaleksey за наводку.

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

Продолжение следует...

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

Сегодня речь пойдет о:

• выборе ключа кэширования;
• кластеризации memcached и алгоритмах распределения ключей.

Следующий пост будет посвящен атомарности операций и счетчикам в memcached.

Ключ кэширования

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

• При изменении параметров выборки, которую мы кэшируем, ключ кэширования должен изменяться (чтобы с новыми параметрами мы не «попали» в старый кэш).
• По параметрам выборки ключ должен определяться однозначно, т.е. для одной и той же выборки ключ кэширования должен быть только один, иначе мы рискуем понизить эффективность процесса кэширования.

Конечно, мы могли бы для каждой выборки строить ключ самостоятельно, например, ‘user_158’ для выборки информации о пользователе с ID 158 или ‘friends_192_public_sorted_online’ для друзей пользователя с ID 192, которые доступно публично и притом отсортированы в порядке последнего появления на сайте. Такой подход чреват ошибками и несоблюдением условий, сформулированных выше.

Можно использовать следующий вариант (пример для PHP): если существует некоторая точка в коде, через которую проходят все обращения к БД, а любое обращение полностью описывается (содержит все параметры запроса) в некоторой структуре $options, можно использовать следующий ключ:

$key = md5(serialize($options))

Такой ключ несомненно удовлетворяет первому условию (при изменении $options будет обязательно изменен $key), но и второе условие будет соблюдаться, если мы будем все типы данных в $options использовать «канонически», т.е. не допускать строки "1" вместо числа 1 (хотя в PHP два таких значения равны, но их сериализованное представление различается). Функция md5 используется для «сжатия» данных: ключ memcached имеет ограничение по длине, а сериализованное представление может быть слишком длинным.

Кластеризация memcached

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

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

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

Исторически первой функцией распределения была функция модуля:

f(ключ) = crc32(ключ) % количество_серверов

Такая функция обеспечивает равномерное распределение ключей по серверам, однако проблемы возникают при переконфигурировании кластера memcached: изменение количества серверов приводит к перемещению значительной части ключей по серверам, что эквивалентно потере значительной части ключей.

Альтернативой для данной функции является механизм консистентного хэширования (consistent hashing), который при переконфигурации кластера сохраняет положение ключей по серверам. Этот подход был реализован в клиентах memcached впервые разработчиками сервиса Last.fm в апреле 2007 года.

Суть алгоритма заключается в следующем: мы рассматриваем набор целых чисел от 0 до 2­³², «закручивая» числовую ось в кольцо (склеиваем 0 и 2³²). Каждому сервера из пула memcached-серверов мы сопоставляем число на кольце (рисунок слева, сервера A, B и C). Ключ хэшируется в число в том же диапазоне (на рисунке – синие точки 1-4), в качестве сервера для хранения ключа мы выбираем сервер в точке, ближайшей к точке ключа в направлении по часовой стрелке. Если сервер удаляется из пула или добавляется в пул, на оси появляется или исчезает точка сервера, в результате чего лишь часть ключей перемещается на другой сервер. На рисунке 2 справа показана ситуация, когда сервер C был удалён из пула серверов и добавлен новый сервер D. Легко заметить, что ключи 1 и 2 не поменяли привязки к серверам, а ключи 3 и 4 переместились на другие сервера. На самом деле одному серверу ставится в соответствие 100-200 точек на оси (пропорционально его весу в пуле), что улучшает равномерность распределения ключей по серверам в случае изменения их конфигурации.

Данный алгоритм был реализован во многих клиентах memcached в различных языках программирования, однако реализация иногда отличается деталями, что приводит к несовместимости хэширования. Данный факт делает консистентное хэширование неудобным для использования при доступе к одному пулу серверов memcached из различных языков программирования. Простейший алгоритм с crc32 и модулем реализован во всех клиентах на всех языках одинаково, что обеспечивает одинаковое хэширование ключей по серверам. Поэтому в случае отсутствия необходимости обращаться к memcached из различных клиентов на разных языках программирования более привлекательным выглядит подход с консистентным хэшированием.

Продолжение следует...

Материалы

Этим постом хочу открыть небольшую серию постов по материалам доклада на HighLoad++-2008. Впоследствии весь текст будет опубликован в виде одной большой PDF-ки.

Введение

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

Кэширование сегодня является неотъемлемой частью любого Web-проекта, не обязательно высоконагруженного. Для каждого ресурса критичной для пользователя является такая характеристика, как время отклика сервера. Увеличение времени отклика сервера приводит к оттоку посетителей. Следовательно, необходимо минимизировать время отклика: для этого необходимо уменьшать время, требуемое на формирование ответа пользователю, а ответ пользователю требует получить данные из каких-то внешних ресурсов (backend). Этими ресурсами могут быть как базы данных, так и любые другие относительно медленные источники данных (например, удаленный файловый сервер, на котором мы уточняем количество свободного места). Для генерации одной страницы достаточно сложного ресурса нам может потребоваться совершить десятки подобных обращений. Многие из них будут быстрыми: 20 мс и меньше, однако всегда существует некоторое небольшое количество запросов, время вычисления которых может исчисляться секундами или минутами (даже в самой оптимизированной системе один могут быть, хотя их количество должно быть минимально). Если сложить всё то время, которое мы затратим на ожидание результатов запросов (если же мы будем выполнять запросы параллельно, то возьмем время вычисления самого долгого запроса), мы получим неудовлетворительное время отклика.

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

Memcached и кэширование

Принцип локальности

Кэш или подход кэширования мы встречаем повсюду в электронных устройствах, архитектуре программного обеспечения: кэш ЦП (первого и второго уровня), буферы жесткого диска, кэш операционной системы, буфер в автомагнитоле. Чем же определяется такой успех кэширования? Ответ лежит в принципе локальности: программе, устройству свойственно в определенный промежуток времени работать с некоторым подмножеством данных из общего набора. В случае оперативной памяти это означает, что если программа работает с данными, находящимися по адресу 100, то с большей степенью вероятности следующее обращение будет по адресу 101, 102 и т.п., а не по адресу 10000, например. То же самое с жестким диском: его буфер наполняется данными из областей, соседних по отношению к последним прочитанным секторам, если бы наши программы работали в один момент времени не с некоторым относительно небольшим набором файлов, а со всем содержимым жесткого диска, буферы были бы бессмысленны. Буфер автомагнитолы совершает упреждающее чтение с диска следующих минут музыки, потому что мы, скорее всего, будем слушать музыкальный файл последовательно, чем перескакивать по набору музыки и т.п.

В случае web-проектов успех кэширования определяется тем, что на сайте есть всегда наиболее популярные страницы, некоторые данные используются на всех или почти на всех страницах, то есть существуют некоторые выборки, которые оказываются затребованы гораздо чаще других. Мы заменяем несколько обращений к backend’у на одно обращения для построения кэша, а затем все последующие обращения будет делать через быстро работающий кэш.

Кэш всегда лучше, чем исходный источник данных: кэш ЦП на порядки быстрее оперативной памяти, однако мы не можем сделать оперативную память такой же быстрой, как кэш – это экономически неэффективно и технически сложно. Буфер жесткого диска удовлетворяет запросы за данными на порядки быстрее самого жесткого диска, однако буфер не обладает свойством запоминать данные при отключении питания – в этом смысле он хуже самого устройства. Аналогичная ситуация и с кэшированием в Web’е: кэш быстрее и эффективнее, чем backend, однако он обычно в случае перезапуска или падения сервера не может сохранить данные, а также не обладает логикой по вычислению каких-либо результатов: он умеет возвращать лишь то, что мы ранее в него положили.

Memcached

Memcached представляет собой огромную хэш-таблицу в оперативной памяти, доступную по сетевому протоколу. Он обеспечивает сервис по хранению значений, ассоциированных с ключами. Доступ к хэшу мы получаем через простой сетевой протокол, клиентом может выступать программа, написанная на произвольном языке программирования (существуют клиенты для C/C++, PHP, Perl, Java и т.п.)

Самые простые операции – получить значение указанного ключа (get), установить значение ключа (set) и удалить ключ (del). Для реализации цепочки атомарных операций (при условии конкурентного доступа к memcached со стороны параллельных процессов) используются дополнительные операции: инкремент/декремент значения ключа (incr/decr), дописать данные к значению ключа в начало или в конец (append/prepend), атомарная связка получения/установки значения (gets/cas) и другие.

Memcached был реализован Брэдом Фитцпатриком (Brad Fitzpatrick) в рамках работы над проектом ЖЖ (LiveJournal). Он использовался для разгрузки базы данных от запросов при отдаче контента страниц. Сегодня memcached нашел своё применение в ядре многих крупных проектов, например, Wikipedia, YouTube, Facebook и другие.

Общая схема кэширования

В общем случае схема кэширования выглядит следующим образом: frontend’у (той части проекта, которая формирует ответ пользователю) требуется получить данные какой-то выборки. Frontend обращается к быстрому как гепард серверу memcached за кэшом выборки (get-запрос). Если соответствующий ключ будет обнаружен, работа на этом заканчивается. В противном случае следует обращение к тяжелому, неповоротливому, но мощному (как слон) backend’у, в роли которого чаще всего выступает база данных. Полученный результат сразу же записывается в memcached в качестве кэша (set-запрос). При этом обычно для ключа задается максимальное время жизни (срок годности), который соответствует моменту сброса кэша.

Такая стандартная схема кэширования реализуется всегда. Вместо memcached в некоторых проектах могут использоваться локальные файлы, иные способы хранения (другая БД, кэш PHP-акселератора и т.п.) Однако, как будет показано далее, в высоконагруженном проекте данная схема может работать не самым эффективным образом. Тем не менее, в нашем дальнейшем рассказе мы будем опираться именно на эту схему.

Архитектура memcached

Каким же образом устроен memcached? Как ему удаётся работать настолько быстро, что даже десятки запросов к memcached, необходимых для обработки одной страницы сайта, не приводят к существенной задержке. При этом memcached крайне нетребователен к вычислительным ресурсам: на нагруженной инсталляции процессорное время, использованное им, редко превышает 10%.

Во-первых, memcached спроектирован так, чтобы все его операции имели алгоритмическую сложность O(1), т.е. время выполнения любой операции не зависит от количества ключей, которые хранит memcached. Это означает, что некоторые операции (или возможности) будут отсутствовать в нём, если их реализация требует всего лишь линейного (O(n)) времени. Так, в memcached отсутствуют возможность объединения ключей «в папки», т.е. какой-либо группировки ключей, также мы не найдем групповых операций над ключами или их значениями.

Основными оптимизированными операциями является выделение/освобождение блоков памяти под хранение ключей, определение политики самых неиспользуемых ключей (LRU) для очистки кэша при нехватке памяти. Поиск ключей происходит через хэширование, поэтому имеет сложность O(1).

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

По сути, можно сказать, что время отклика сервера memcached определяется только сетевыми издержками и практически равно времени передачи пакета от frontend’а до сервера memcached (RTT). Такие характеристики позволяют использовать memcached в высоконагруженных web-проектов для решения различных задач, в том числе и для кэширования данных.

Потеря ключей

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

1. Ключ был удален раньше окончания его срока годности в силу нехватки памяти под хранение значений других ключей. Memcached использует политику LRU, поэтому такая потеря означает, что данный ключ редко использовался и память кэша освобождается для хранения более популярных ключей.
2. Ключ был удален, так как истекло его время жизни. Такая ситуация строго говоря не является потерей, так как мы сами ограничили время жизни ключа, но для клиентского по отношению к memcached кода такая потеря неотличима от других случаев – при обращении к memcached мы получаем ответ «такого ключа нет».
3. Самой неприятной ситуацией является крах процесса memcached или сервера, на котором он расположен. В этой ситуации мы теряем все ключи, которые хранились в кэше. Несколько сгладить последствия позволяет кластерная организация: множество серверов memcached, по которым «размазаны» ключи проекта: так последствия краха одного кэша будут менее заметны.

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

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

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

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