Кэширование и memcached 14

Posted by Андрей on Октябрь 16, 2008

Этим постом хочу открыть небольшую серию постов по материалам доклада на 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 из кластера, так вероятность потери снижается.

Trackbacks

Use this link to trackback from your own site.

Comments

Leave a response

  1. Алексей Пн, 20 Окт 2008 16:01:19 UTC

    Спасибо! Оч. интересно! как раз сегодня начал копать материал о memcached! и ждем продолжения!

  2. Rus Чт, 30 Окт 2008 18:17:44 UTC

    Добрый день Андрей подскажите пожалуйста в чем отличие кеша например в pear от мемкеша?

  3. Андрей Пт, 31 Окт 2008 08:10:04 UTC

    Если я правильно понял, речь идёт о пакете PEAR::Cache, я с ним не знаком близко, но, насколько я могу судить, это подсистема кэширования, для которой хранилищем данных кэша могут быть различные варианты БД, локальные файлы и т.п.

    Я не знаю точно, но, наверное, и memcached мог бы быть хранилищем кэша для PEAR::Cache. Может, меня кто-то поправит?

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

  4. Илья Пн, 14 Дек 2009 22:50:31 UTC

    Доброго времени суток!

    У меня остался один вопрос без ответа.

    Допустим, у нас есть список новостей, который прекрасным образом хранится в кэше с версиями тэгов этих новостей (как полагается).

    Если какую-либо новость меняют или удаляют, как это должно происходить, версию увеличивают или удаляют (обнуляют) соответственно.

    Вопрос заключается в том, как кеш узнает, что добавилась еще одна новость?

    Самое простое, что мне приходит в голову – это хранить где-то ассоциативный массив: тип объекта – список ключей кэшей, в который может входить этот объект.

    И при добавлении нового объекта, проверять по типу объекта из этого списка, какой из кэшей надо удалить.

    Знакомы ли Вы с каким-либо другим методом обновления кэша при добавлении новых объектов?

  5. Андрей Вт, 15 Дек 2009 08:37:01 UTC

    Илья,

    Если кэши новостей с тэгами, то, в зависимости от ситуации можно поступить по-разному.

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

    Если новости меняются очень часто (раз в минуту, например), надо более аккуратно и точно расставить тэги: по разделам, как-то еще.

  6. Илья Вт, 15 Дек 2009 21:01:23 UTC

    Аха, тоже вариант… спасибо за ответ.

    Да, и отдельное, огромное спасибо за цикл статей про тэгирование кэшей!

  7. Кирилл Сб, 27 Фев 2010 20:02:37 UTC

    Андрей, подскажите пожалуйста как быть…

    Есть веб-страница. На странице размещено 200 кратких описаний различных новостей. В одном мемкэш-ключе я храню в список идентификаторов новостей; в других ключах я храню данные о новостях.

    Таким образом, чтобы «собрать» страницу – приходится делать 200+1 запрос к мемкэшу. Разумеется, потом я эту страницу кэширую еще на одном слое – файловой системе или в том же мемкэше.

    Подскажите пожалуйста – такое кол-во запросов к мемкэшу это нормально или нет? Как избежать такой ситуации, при этом не теряя в гибкости инвалидации данных.

    Очень надеюсь на ответ.

    Спасибо.

  8. Андрей Пн, 01 Мар 2010 08:31:46 UTC

    Кирилл, конечно у memcached есть запросы вида multi-get, с помощью которых вы можете запросить за один запрос много ключей.

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

  9. Кирилл Пн, 01 Мар 2010 13:34:00 UTC

    Андрей, я так понимаю, что multi-get реализуется просто передачей в get метод не одного ключа, а массива ключей.

    А как это работает физически? Не получится ли так, что, php’шный api деает это всё через банальный foreach? Или он формирует набор команд и выполняет их через один запрос?

    Заранее Спасибо!

  10. Кирилл Пн, 01 Мар 2010 14:22:20 UTC

    Нашел, позволю себе вот такую ссылочку… http://highload.com.ua/index.php/2009/08/05/memcache-multi-get-%D0%B7%D0%B0%D1%87%D0%B5%D0%BC/

    Очень полезная информация по мультигету и особенности работы с ним

  11. Андрей Пн, 01 Мар 2010 14:25:44 UTC

    Кирилл, давно уже не писал на PHP, но он должен сделать правильный multi-get, в том числе и для кластера серверов (http://ru.php.net/manual/en/function.memcache-get.php).

  12. Дмитрий Вт, 01 Июн 2010 18:05:08 UTC

    Андрей, просвяти пожалуйста, насколько я знаю сессии в memcached как и все остальные данные имеют свои ключи… Можно ли обратится к переменной сесси обходя стандартный механизм PHP, тоесть зная идентификатор сесси и имя переменной получить или изменить её значение стандартными функциями get/set? Например get(‘h4fv68g46azt846d421g5f4dyhn98h54.name’) и т д. Объясняю для чего мне это нужно… Дело в том, что когда пользователь авторизирован в его личном блоке отображается некая персональная информация и его статистика на которую могут повлиять и другие пользователи… Но позволять левым мордам лесть в чужие сесси для того чтобы подогреть значения переменных – неприемлимо, так как стандартная функция session_start() сразу же засветит SID…

  13. Андрей Чт, 03 Июн 2010 22:15:59 UTC

    Да, конечно, можно получить. Мы делали свой обработчик сессии в memcached, тогда все становится совершенно прозрачно:

    function mmsh_ses_open($path, $name)
{
}
 
function mmsh_ses_close()
{
    if (!$GLOBALS['__mmsh_id'])
        return;
    $expire = time() + $GLOBALS['site_config']['session_lifetime'];
    CMemcache::instance()->set(mmsh_get_id($GLOBALS['__mmsh_id']), $GLOBALS['__mmsh_session'], 0, $expire);
}
 
function mmsh_ses_read($id)
{
    $data = CMemcache::instance()->get(mmsh_get_id($id));
    $GLOBALS['__mmsh_session'] = $data;
    $GLOBALS['__mmsh_id'] = $id;
    return $data;
}
 
function mmsh_ses_write($id, $data)
{
    $GLOBALS['__mmsh_session'] = $data;
    $GLOBALS['__mmsh_id'] = $id;
}
 
function mmsh_ses_destroy($id)
{
    CMemcache::instance()->delete(mmsh_get_id($id));
    unset($GLOBALS['__mmsh_session']);
    unset($GLOBALS['__mmsh_id']);
}
 
function mmsh_get_id($id)
{
    return $id;
}
 
function mmsh_ses_gc($maxlt)
{
    // garbage collection is done on the memcached server, no need to do it here...
}
 
function mmsh_bind()
{
    if ($GLOBALS['use_mmsh'] || !$GLOBALS['development_environment'])
    {
        assert(session_set_save_handler('mmsh_ses_open', 'mmsh_ses_close' , 'mmsh_ses_read', 'mmsh_ses_write', 'mmsh_ses_destroy', 'mmsh_ses_gc'));
    }
}
 
mmsh_bind();
  14. Дмитрий Пт, 04 Июн 2010 10:55:46 UTC

    Cпасибо, будем разбираться…

Comments