Пользователь
0,0
рейтинг
23 октября 2008 в 08:10

Разработка → Кластеризация memcached и выбор ключа кэширования

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

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

Материалы

  1. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html
  2. http://www.lastfm.ru/user/RJ/journal/2007/04/10/rz_libketama_-_a_consistent_hashing_algo_for_memcache_clients
Андрей Смирнов @smira
карма
175,5
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (42)

  • +2
    за consistent hashing отдельное спасибо
    • 0
      присоединяюсь.

      но есть вопрос.
      возможно я что-то не так понял, но: если один из сереров пропадает (выключается), то всё равно все его ключи пропадут, ведь так?
      то есть consistent hashing дает лишь то, что появлении вновь этих же ключей (или похожих) они будут распределяться равномерно, а не будет создаваться их переизбыток на одном из других серверов?
      но, как я понял, и базовый способ распределения выполняет эту функцию…
      • +2
        Нет, не совсем так. Конечно, те ключи, которые были на пропавшем сервере, пропадут. Но есть существенная разница.

        Пусть у нас было 4 сервера с одинаковым весом. И один из них сломался, мы его удалили из пула. После этого стандартное распределение будет остаток от деления на 3 вместо остатка от деления на 4, очевидно, что ключи переместятся на всех серверах. То есть и на тех, которые не пострадали, то есть для нашего кода это будет выглядеть как потеря значительно больше чем 25% ключей.

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

          Было 4 сервера. На всех по 25 ключей. Потом один удалили, 25 ключей пропало, 75 лежат на трех серверах.
          Добавляются новые ключи — уже с распределением по 3 серверам. Ну или по 4, где один из них новый.

          Или я чего-то не учитываю? Например, «перемещение» — это заполнение по новой пустого места или copy-paste с одного сервера на другой.
          • 0
            Нет, тут есть один существенный момент. Ну пусть было 100 ключей, по 25 на каждом, пусть хэш каждого ключа соответствует его номеру. Функция распределения ключей: ключ % 4 + 1.

            Тогда ключи 0, 4, 8,… лежат на 1-м сервере, 1, 5, 9,… — на 2-м, 2, 6, 10,… — на 3-м и 3, 7, 11,… — на 4-м.

            Пусть 4-й сервер выходит из строя, теперь функция распределения ключей: ключ % 3 + 1.

            И теперь ключи 3, 7, 11,… — их значения потеряны (т. к. лежали на упавшем сервере), это 25%.

            Далее, берем ключ 6 — он лежал на 3-м сервере, теперь он лежит на 1-м, берем ключ 5 — раньше на 1-м, теперь на на 3-м сервере. Ну и т. д. Сколько ключей сохранили своё расположение?

            Те, для которых k % 3 = k % 4. Сколько таких?

            • 0
              Примечание: изменили расположение — изменили расположения с точки зрения клиента, то есть он за ним обратится на другой сервер, где такого ключа нет, сервера об этой перетасовке ничего не знают, поэтому для клиента переместившийся ключ == потеряный ключ.
              • +1
                вот теперь ясно=)

                а те ключи, которые «переместились==потерялись» просто будут лежать до своего срока истечения? не вызовет ли это *еще бОльших* накладных расходов?

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

                спасибо за развернутые ответы, всегда приятно когда автор доносит мысли в доступной форме.
                • 0
                  Будут лежать до истечения срока годности или будут вытеснены другими ключами, если памяти не будет хватать. Они накладных расходов в принципе не принесут, распределения размера ключей для slab-аллокатора изменить не должны.
        • +1
          На сколько я понял, основная изюминка в том, что каждому серверу ставится в соответствие много больше чем одна точка. (В описании алгоритма на это не было сделано акцента).

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

          Спасибо за статью.
          • 0
            Вроде бы не забыл:
            «На самом деле одному серверу ставится в соответствие 100-200 точек на оси (пропорционально его весу в пуле), что улучшает равномерность распределения ключей по серверам в случае изменения их конфигурации.»

            Может, было незаметно
            • +1
              >> Может, было незаметно
              На это я и хотел указать ))
              Долго думал над алгоритмом с одной точкой на сервер… и не мог понять почему к минусам не причислена увеличенная почти в двое нагрузка на след. сервер.
  • +4
    При скроллинге страницы кажется, что ключи шевелятся :)
  • 0
    То есть, выбор сервера, на котором будет храниться кэш все-таки делается в приложении? Снять эту задачу с программеров нельзя? То есть в случае с пулом мемкеш-серверов сделать так, чтобы программисты делали только cache_set, cache_get, а мемкеш уже сам решал куда днные положить и откуда их прочитать?
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        Совершенно согласен, добавлю, что сервер не знает ничего о кластере. Это сделано специально. Такой подход упрощает архитектуру сервера.
  • 0
    «По параметрам выборки ключ должен определяться однозначно, т. е. для одной и той же выборки ключ кэширования должен быть только один, иначе мы рискуем понизить эффективность процесса кэширования.»

    Я бы написал просто — ключ должен быть уникальным.
    • +1
      Так почему же не написали? Статья бы такими темпами заняла два абзаца, все бы всё поняли наверняка…
    • 0
      Обеспечить уникальность ключа (в строгом смысле) сложно. В предложенной схеме в теории возможны коллизии, когда md5() от двух разных параметров даст одинаковый ключ, хотя для практики это слишком маловероятно.

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

      Здесь речь идёт об отображениях (функциях), которые сопоставляют выборки и их ключи кэширования. Одной выборке соответствует ровно один ключ, две разные выборки имеют два разных ключа (если забыть про вероятность коллизии в md5).
      • 0
        А что будет в случае коллизии? Клиент получит не то, чего хотел, и не поймёт этого?
        • 0
          Да, именно так, но вероятность этого 2-128. Это очень маленькое число :)

          В теории есть, на практике больше вероятность получить изменения в ячейке памяти, вызванные космическими лучами ;) Или битый сектор на диске. То есть существует гораздо больше проблем, с которыми надо бороться ;)
          • 0
            про «парадокс дней рождения» слышали? Если у нас закэшировано достаточно большое количестко данных, то вероятность коллизии растёт просто катострофически. Поэтому и спросил. :)
            Если я ничего не напутал, то при 2608763571588465 элементах в кэше вероятность коллизии будет около одной десятимилионной, что уже не так уж мало.
            • 0
              Когда будет столько элементов в кэше, то я сразу же пойду сменю хэш ;)

              Есть SHA-256, SHA-512 — там добавляется такое количество бит данных, что вероятность опять дико снизится.
      • 0
        Судя по статье и комментариям, я так понимаю, что Вы используете именно md5 для ключей. Ничего п ротив не имею, лишь хочу рассказать, почему использую вот этот способ: friends_192_public_sorted_online.
        1) Ключ всегда будет уникальным, так как используются id из таблиц
        2) Формирование ключа занимает меньше времени
        3) Правила формирования всех ключей храню в одном месте, поэтому в любой момент к ним можно обратиться и узнать, из чего состоит каждый ключ.
        4) Есть самописный консольный клиент, который позволяет читать/писать/удалять из мемкэша по ключу. Очень удобно бывает. С md5-ключами работать было бы сложнее.
        5) Ключи не обязательно делать такими длинными. Вполне достаточно fr_192_pub_asc_1.
        • 0
          Не спорю, просто хочу отметить:
          1) На тему уникальности и прочего: habrahabr.ru/blogs/webdev/42972/#comment_1063460
          2) Спорный момент, накладные расходны на обращение к memcached на несколько порядков больше вычисления md5 и serialize
          3) Да, заглянув в memcached и взглянув на ключ 01234fdef345, я не скажу, что это за кэш. Согласен. Оно мне часто надо? Если очень надо, можно полное имя ключа записать в значение еще одним параметром.
          4) С md5() работать не сложнее, просто клиент от имени вычислял бы md5 перед обращением. Какая разница?
          5) Ключ становится длинным, потому что в тяжелом большом проекте выборка зависит от ооочень большого числа параметров. И там работает общий подход, каждый ключ строить руками — это можно сойти с ума.
          • 0
            Добавлю, что использование md5 и serialize — это не блажь, а невозможность для каждой выборки руками формировать ключ — выборок слишком много и слишком много разных у них параметров.
  • +2
    Думаю, стоит отметить такой момент: допустим, один из серверов с memcached «вылетел» только на время. Например, неполадки в сети или кончились коннекции. Клиент сохранит ключ на один из других серверов. А при следующем обращении старый сервер снова станет доступным и возмётся старое значение (если между выборками были изменения). Так что лучше не позволять клиенту использовать другие сервера при отказе одного.
  • +1
    Небольшое уточнение. В ключах запрещены символы с ord(char) < 33 и с ord(char) == 127.
    • 0
      Пробел (32) тоже запрещен :)
      • 0
        Сорри, схожу с ума, то есть он запрещен, но ровно то и написано в исходном коменте.
        • 0
          Да, просто я уточнил, что еще кроме пробела запрещено.
      • 0
        Это логично, поскольку 32 меньше чем 33.
  • 0
    Было бы классно получить пост о том ЧТО нужно кэшировать и КАК это делать.
    Очень часто в встречаются фразы, «кэшируйте все что можете», «если контент редко обновляется, кладите его в кэш»(например новостная лента), однако, когда дело доходит до практики, все становится совсем не так прозрачно.

    Возьмем пример по-сложнее:
    Социальная сеть. У пользователя есть друзья, пользователь может заливать фотки.
    На каждую фотку назначаются права доступа: доступна всем, доступна только владельцу, доступна друзьям, доступна выбранному кругу лиц.

    Что делать в таком случае? Кэшировать списки друзей? Как кэшировать списки фоток, если для каждого смотрящего они индивидуальны?
    • 0
      Если типов доступа не много (скажем, 3: всем, друзьям, владельцу), то можно хранить три списка. Если много, то можно кешировать записи с запасом, скажем 100 (записи о фотках очень мало будут весить) и на стороне скрипта (пхп, питон, что там у Вас) решать, какие показывать, а какие нет для конкретного пользователя.

      Если более кратко, то БД масштабируется несколько сложнее, чем web-сервера, поэтому иногда намного выгоднее закэшировать довольно большие куски данных, а потом обрабатывать их уже скриптом, чем каждый раз дергать БД.
    • 0
      Не кешировать фотки.
      Может быть Кешировать друзей…

      Почему — друзья могут потребоваться человеку при серфе( панельку тама отобразить), но у каждого человека они свои, проше кешить всю панельку :)
      А вероятность что кто-то зайдет на вашу страницу и будет копаться в ваших фотках — 1-2 человека в день.
      Это не та нагрузка где надо заморачиваться…

      Главное правило кеширования — «если в этом месте нужно извратиться и замочориться — идите заморачиваться в другое место»

      В общем ускоряйте что ускоряется, это разгрузит систему и ускорит то что не ускорялось :)
    • 0
      Для начала постройте логику без кэширования. Определите, как это работает. Кэширование — это оптимизация, ей — последняя очередь при разработке. Теперь посмотрите на логику. Спроектируйте её так, чтобы способы оптимизации — кэширование и т. п. — можно было воткнуть логику в тех точках, где это разумно (посмотрите, что можно в принципе кэшировать: контент, вывод и т. п.). Когда логика будет работать, разделять права доступа и т. п.: посмотрите, как часто дергается эта страница? какие запросы генерирует? чем отличается страница для разных пользователей? как и что лучше закэшировать? не меняя логику, добавьте кэширование в нужные точки. Проведите еще эксперименты, измените схему кэширования, и т. п.
      • 0
        К сожалению, мне не попадалось литературы и примеров, как должна быть спроектирована система, чтобы можно было легко добавить кеширование.

        В самом простом варианте реализации, имеем хранимую процедуру, на вход приходит Id юзера который хочет просмотреть фотки, и id юзера чьи фотки хотят увидеть. Процедура возвращает набор данных для показа, отфильтрованных по правам доступа.
        Однако кэшировать всю выборку вряд-ли эффективно… Стоит использовать ORM и кэшировать обьекты?

        Я понимаю, что в коментариях к топику сложно обьяснить принципы построения высоконагруженных систем однако буду очень признателен если вы укажите направление и/или основные принципы и литературу…
        • 0
          Насколько я знаю, какой-то замечательной книги, где было бы всё описано, просто не существует. Но возьмем Ваш пример с хранимыми процедурами.

          Пусть у меня есть класс StoredProcedure, и я вызываю хранимки, например, так:

          $proc = new StoredProcecudure('get_photos');
          $result = $proc->call($user->id);
          


          Тогда я в StoredProcedure::call имею возможность всегда встроить кэширование впоследствие. Если буду делать что-то типа:

          $con = ....
          $result = $con->query("SELECT get_photos({$user->id})");
          


          То вряд ли я встрою в такого рода код легко кэширование.

          А кэшировать выборки — это не такое плохое решение. Кэшировать объекты тяжело в PHP, если мы про него говорим.

          • 0
            Я занимаюсь разработкой на .net, но принципы кэширования остаются теми-же.
            Обращения к StoredProcedure идет через слой доступа к данным и встроить туда кеширование выборок не составит труда.

            Меня больше беспокоит иное:
            Процесс вычисления прав доступа к фотке отностиельно тяжелая операция, кроме того результат зависит от id пользователя.
            При этом одну и та-же фотка может попасть в разные выборки (например фото моих друзей, сборка последних, в результаты поиска..). В итоге эффективность кеширования выборки оказывается низкой. Какой подход можно использовать в такой ситуации?

            p.s. Не подумайте что я реально собрался написать еще одну соц. сеть, просто выбрал пример посложнее, поскольку как реализовать кеширование для новостного сайта я уже имею представление.
            • 0
              Попадает не фотка, как я понимаю, а информация о ней. Информация о фотографии — это 200 байт? 500? Килобайт? Не так ли страшно, что она закэшируется несколько раз? Тут всегда будет некоторый trade-off между бешеной оптимизированностью и чистотой кода.

              Результаты поиска, скорее всего, кэшироваться вообще не должны (или только самые популярные запросы). А во всех остальных ситуациях поможет сброс кэша (о нём попозже).

              То есть проблема есть, конечно, но с той или иной степенью достоверности её можно решить :)
  • 0
    Кешировать хтмл код страницы для пользователя который просматривает, потому что быстрее отдать кеш, чем сделать несколько сложных запросов сущностей при разных параметрах.
    • 0
      Это очень спорный вопрос, что лучше кэшировать: выборку или вывод (HTML). С точки зрения глобальной эффективности — лучше всего HTML, отдавать его nginx с модулем memcached. Но это в идеале, если задача позволяет. Бывают проекты (например, соц. сети), где одна и та же страница может кардинально различаться в зависимости от того, кто её смотрит. Плюс еще может быть куча отличий в зависимости от ранга пользователя, чего-то еще. В такой ситуации оказывается выгоднее кэшировать выборки, а HTML формировать на лету.

      Для новостного сайта, например, можно кэшировать HTML, вставляя на лету только нужные банеры.
      • 0
        Согласен, но новостной сайт к примеру может обновлять кеш, по мере входа информации — таким образом мы выдем нджинксом с мемкешем всю инфу сразу, не запуская даже пыха. Берем хабр, делим на блоки содзаем к примеру сущность главнйо страницы, и выдаем ее. При изменении, что кстати в 100раз реже чем загрузка главнйо страницы по ф5 выдаем кеш. Для незарегистрированных пользователей вообще не создаем сессий, перекладываем анализ на аналитикс. что бы создать сессию, если она нужна уже на странцие логина, просто вставляем 1х1 гиф на нонкешед страницу с генерацией сессии.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.