Post main image

Кэширование

Кэширование — это один из способов оптимизации приложений. В любом приложении встречаются медленные операции (SQL запросы или запросы к внешним API), результаты которых можно сохранить на некоторое время. Это позволит выполнять меньше таких операций, а большинству пользователей показывать заранее сохраненные данные. Кэшировать нужно данные, которые медленно генерируются и часто запрашиваются. На практике это обычно:

  • Результаты запросов к внешним сервисам (RSS, SOAP, REST и так далее).
  • Результаты медленных выборок из базы данных.
  • Сгенерированные html блоки либо целые страницы.

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

Если Memcache стоит на отдельном сервере, это вызовет большой сетевой трафик и задержки. Чтобы этого избежать, можно использовать дополнительный кэш внутри самого приложения - identity map.

Время жизни, ttl — это время, после которого, данные будут удалены из кэша.

Любой кэш работает по принципу вытеснения если ему не хватает памяти. Для определения, какие именно ключи удалять, используется алгоритм LRU (Least Recently Used). Необходимо удалить прежде всего те данные, которые запрашивались очень давно (т.е. менее популярные будут удалены, а более популярные останутся).

Методика дублирования

Если есть запрос, который выполняется 10 секунд, ttl для его кэша 1 час.

Когда проходит это время, данные в кэше удаляются.

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

Чтобы этого избежать, необходимо использовать специальную методику дублирования. Для каждого тяжелого запроса создается не один, а два ключа — ttl и ttl +10 sec.

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

Также можно использовать cron задачи для обновления данных в кэше.

Тогда посетители никогда не смогут вызвать тяжелые запросы. Но в этом случае лучше использовать постоянные хранилища для кэширования (например Redis), так как Memcache не гарантирует сохранности данных.

Memcached

Описание

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

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

Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа.

Получающееся хеш-значение играет роль индекса в массиве.

Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива.

Коллизии и методы решения

Коллизией хеш-функции F(x) называется два различных входных блока данных x и y таких, что F(x)=F(y). Методы решения коллизий для хеш-таблиц:

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

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

Существует отличное ПО для кластеризации Mcrouter.

Для распределения нагрузки и достижения отказоустойчивости вместо одного сервера memcached используется кластер из таких серверов.

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

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

При работе с кластером ключи распределяются по серверам, то есть каждый сервер обрабатывает часть общего массива ключей проекта.

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

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

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

Исторически первой функцией распределения была функция модуля: f(ключ) = crc32(ключ) % количество_серверов.

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

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

Суть алгоритма заключается в следующем: мы рассматриваем набор целых чисел от 0 до 2­32, «закручивая» числовую ось в кольцо (склеиваем 0 и 232).

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

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

  • Пусть у нас было 4 сервера с одинаковым весом.
  • И один из них сломался, мы его удалили из пула.
  • После этого стандартное распределение будет остаток от деления на 3 вместо остатка от деления на 4, очевидно, что ключи переместятся (физически они остануться там же, а вот функция будет искать их в другом месте) на всех серверах.
  • То есть и на тех, которые не пострадали, то есть для нашего кода это будет выглядеть как потеря значительно больше чем 25% ключей.
  • В случае консистентного хэширования ключи, которые были на 3 серверах, которые остались в рабочем состоянии, на них же и останутся.
  • А ключи с 4-го сервера равномерно распределяться по 3-м оставшимся, мы потеряли ровно 25% ключей — возможный минимум.

Внутреннее устройство

Slab — это алгоритм выделения памяти. Он был создан для ее эффективного использования.

Вся память делится на отдельные куски — слабы (slab).

Каждый слаб содержит более мелкие куски — чанки (chunk).

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

Если память сравнить с домом, то слабы — это квартиры, а чанки — это комнаты. Это эффективно, так как не нужно постоянно искать по всей памяти какое-то свободное место. Мы просто заполняем комнату, потом переходим к следующей комнате. И так пока вся память не будет заполнена.

Для скорости работы, Memcache выделяет чанки одинакового размера. Если значение сохраняемого объекта меньше, чем размер чанка, в памяти остается “свободное место».

Это свободное пространство и определяет возможность оптимизации Memcache, так как размер чанков можно настроить. Для того, чтобы работать с объектами разных размеров Memcache создает несколько разных слабов (квартир в доме), в которых находятся чанки разных размеров (в некоторых побольше, а в некоторых поменьше).

Когда приходит объект покрупнее, Memcache использует чанки из того слаба, в котором они большие. Главное, чтобы размер объекта был меньше, чем размер чанка.

Слабы, в которых находятся чанки одинакового размера объединяются в классы (slabclass). Таким образом:

  • Slabclass определяет группу слабов с одинаковым размером чанков.
  • Slab содержит группу чанков.
  • Chunk — это кусочек памяти, в который сохраняются данные.

Если у нас большие чанки и много мелких объектов, мы рискуем использовать память очень неэффективно.

Если объекты большие и много мелких чанков, то эти чанки не будут использованы.

В обоих случаях мы не используем все место, которое можем.

В Memcache настройка размеров чанков и их количества производится с помощью фактора роста. Это соотношение размера большего чанка к меньшему.

Установка

Инструкции по установке специфичны для различных ОС. Подробнее можно почитать тут.

Настройка

Настройка происходит довольно быстро: нужно просто указать в конфигурационном файле (/etc/memcached.conf), или во время запуска сервера Memcached, нужные параметры.

  • -m — определяет размер отводимой под кэш памяти. Значение по умолчанию — 64
  • -l — адрес к которому подключаются приложения. Для localhost параметр будет таким: -l 127.0.0.1, то есть сервер будет доступен только из локально хоста.
  • -p — порт к которому подключаются приложения.
  • -u — назначает пользователя, от имени которого запускается memcached
  • -n — минимальная длина записи. Значение по умолчанию 48 bytes.
  • -f — фактор роста, который определеяет размер чанков. Значение по умолчанию 1.25

После сохранения сохранения файла конфигурации необходимо перезагрузить memcached - /etc/init.d/memcached restart.

Опция -L заставляет Memcache во время старта подготовить всю выделяемую ему память для использования. Это значит, что во время старта Memcache сделает инициализацию слабов и чанков.

Когда Memcache доходит до ограничения в памяти, он начинает удалять объекты по принципу LRU.

Количество удаленных объектов фиксируются в параметре evictions внутренней статистики. Значение evictions должно быть нулевым либо очень небольшим. Большие значения — это сигнал для расширения. В таких случаях нужно проделать оптимизацию размеров чанков и слабов.

После этого — устанавливать дополнительно оборудование.

Использование

Memcached доступен как по TCP, так и по UDP.

По-умолчания memcached запускается на 11211 порту.

Чтобы запустить на другом порту используется команда memcached -p 11111 -U 11111 -u user -d, где

  • -p — TCP-порт,
  • -U — UDP-порт,
  • -u — имя пользователя,
  • -d — запустить как демон.

Для подключения к memcached используется telnet (telnet 127.0.0.1 11211). Подключения из Java new MemcachedClient(new InetSocketAddress("127.0.0.1", 11211));.

  • Добавление или перезапись значения — если ключ уже есть, то значение перезаписывается. Memcached отвечает STORED при успехе, CLIENT_ERROR содержит описание ошибки, ERROR говорит при ошибке.
      MBP-Pavel:manual zinvapel$ telnet localhost 11211
      Trying ::1...
      Connected to localhost.
      Escape character is '^]'.
    
      set key(ключ) flags(32-битное натуральное число, возвращается с get) exptime(в секундах, 0 — бесконечно) bytes(длина данных) [noreply](флаг - сервер ничего не ответит)
      value(значение для кеширования)
    
  • Добавление значения — если ключ уже есть, то возвращается NOT_STORED. Memcached отвечает STORED при успехе.
      add key flags exptime bytes [noreply]
      value
    
  • Замена значения — если ключа нет, то возвращается NOT_STORED. Memcached отвечает STORED при успехе.
      replace key flags exptime bytes [noreply]
      value
    
  • Добавление к значению — если ключа нет, то возвращается NOT_STORED. Memcached отвечает STORED при успехе, CLIENT_ERROR при ошибке.
      append key flags exptime bytes [noreply]
      value
    
  • Добавление к значению спереди — если ключа нет, то возвращается NOT_STORED. Memcached отвечает STORED при успехе, CLIENT_ERROR при ошибке.
    prepend key flags exptime bytes [noreply]
    value
    
  • Сравнить и установить значение (CAS) — — новое значение будет сохранено только если другие клиенты не обновили его со времени последнего обращения этим клиентом. STORED — успешно, ERROR об ошибке. EXISTS говорит, что значение поменял кто-то другой. NOT_FOUND, что ключа не существует.
      cas key flags exptime bytes unique_cas_token(уникальный ключ, полученный с помощью команды get) [noreply]
      value
    
  • Получение значения
      get key1 key2 key3
    
  • Получение значения для CAS - последнее число — это unique_cas_token
      gets key
    
  • Удаление значения - DELETE — удалено, ERROR — ошибка, NOT_FOUND — ключ отсутствует.
      delete key [noreply]
    
  • Увеличение/уменьшение целого числа — NOT_FOUND нет значения по ключу, CLIENT_ERROR нечисловое значение.
      incr key increment_value
      decr key decrement_value
    
  • Получение статистики
      stats
    
  • Получение статистики, сгруппированной по слабам
      stats items
    
  • Получение статистики по слабам
      stats slabs
    
  • Информация о размере хранимых объектов
      stats sizes
    
  • Информация о памяти
      stats malloc
    
  • Опции stats - detail, sizes, reset
  • Очистка данных
    flush_all [time](задержка) [noreply]
    
  • version - узнать версию.
  • quit - закончить telnet-сессию.