Эффективность кэширования: рабочие наборы и динамические данные

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

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

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

Другим важным фактором является размер рабочего набора кэшируемых объектов. Кэш имеет фиксированный размер. Рабочим набором (working set) кэшируемых объектов называются уникальные объекты (результаты запросов к базе данных или файлы), запрашиваемые за заданный период времени. В идеале емкость кэша должна быть достаточной для хранения всего рабочего набора; в этом случае подавляющее большинство запросов будет приводить к попаданиям в кэш. Однако на практике хранение всех нужных объектов в кэше может оказаться невозможным по целому ряду причин. В этом случае для освобождения в кэше места для новых объектов приходится использовать механизм вытеснения старых объектов. Вскоре мы рассмотрим вытеснение из кэша более подробно.

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

В Flickr используется Squid для кэширования фотографий по технологии кешируюшего прокси. Фотографии хранятся на относительно медленных и дешевых дисках большой емкости, а для предоставления фотографий пользователям применяются системы кэширования с быстрыми дисками меньшей емкости. С ростом интенсивности запросов на получение фотографий выполняется горизонтальное масштабирование количества кэширующих серверов. Также с ростом количества фотографий выполняется горизонтальное масштабирование объема долгосрочного хранилища в back-end-подсистеме.

Каждый кэширующий сервер обладает ограниченным объемом дискового пространства и памяти, используемой в качестве кэша. Рабочий набор фотографий слишком велик для размещения в кэше, поэтому кэш постепенно заполняется. Заполненному кэшу приходится постоянно принимать решения относительно того, какие объекты следует удалить из кэша, чтобы освободить место для новых объектов. Этот процесс основан на алгоритме замены, или вытеснения. Существует много разных алгоритмов вытеснения; одним из самых распространенных является алгоритм вытеснения по давности использования LRU (Least Recently Used). Принцип его работы представлен на рисунке.

По мере обращения к кэшу с запросами объекты объединяются в список в соответствии со временем последнего обращения. Если запрос не попал в кэш, то полученный от сервера источника объект помещается в начало списка. Объекты, соответствующие попаданиям в кэш, перемещаются из текущей позиции в начало списка. Таким образом, объекты сортируются от недавно использованных до тех, которые не использовались давно. Когда кэшу потребуется освободить место для новых объектов, он удаляет объекты в конце списка. Возраст самого старого объекта в списке называется эталонным возрастом LRU и наряду с частотой попаданий в кэш является показателем эффективности кэширования.

Алгоритм LRU используется в Memcached, Squid, Varnish и многих других кэширующих приложениях. Он хорошо известен, а его поведение относительно легко понять. Squid также поддерживает несколько более сложных алгоритмов вытеснения, но почти все популярные системы кэширования баз данных используют метод LRU.

Важнейшие метрики, которые должны отслеживаться при использовании любой программы кэширования: