Comments 42
за consistent hashing отдельное спасибо
присоединяюсь.
но есть вопрос.
возможно я что-то не так понял, но: если один из сереров пропадает (выключается), то всё равно все его ключи пропадут, ведь так?
то есть consistent hashing дает лишь то, что появлении вновь этих же ключей (или похожих) они будут распределяться равномерно, а не будет создаваться их переизбыток на одном из других серверов?
но, как я понял, и базовый способ распределения выполняет эту функцию…
но есть вопрос.
возможно я что-то не так понял, но: если один из сереров пропадает (выключается), то всё равно все его ключи пропадут, ведь так?
то есть consistent hashing дает лишь то, что появлении вновь этих же ключей (или похожих) они будут распределяться равномерно, а не будет создаваться их переизбыток на одном из других серверов?
но, как я понял, и базовый способ распределения выполняет эту функцию…
Нет, не совсем так. Конечно, те ключи, которые были на пропавшем сервере, пропадут. Но есть существенная разница.
Пусть у нас было 4 сервера с одинаковым весом. И один из них сломался, мы его удалили из пула. После этого стандартное распределение будет остаток от деления на 3 вместо остатка от деления на 4, очевидно, что ключи переместятся на всех серверах. То есть и на тех, которые не пострадали, то есть для нашего кода это будет выглядеть как потеря значительно больше чем 25% ключей.
В случае консистентного хэширования ключи, которые были на 3 серверах, которые остались в рабочем состоянии, на них же и останутся. А ключи с 4-го сервера равномерно распределяться по 3-м оставшимся, мы потеряли ровно 25% ключей — возможный минимум.
Пусть у нас было 4 сервера с одинаковым весом. И один из них сломался, мы его удалили из пула. После этого стандартное распределение будет остаток от деления на 3 вместо остатка от деления на 4, очевидно, что ключи переместятся на всех серверах. То есть и на тех, которые не пострадали, то есть для нашего кода это будет выглядеть как потеря значительно больше чем 25% ключей.
В случае консистентного хэширования ключи, которые были на 3 серверах, которые остались в рабочем состоянии, на них же и останутся. А ключи с 4-го сервера равномерно распределяться по 3-м оставшимся, мы потеряли ровно 25% ключей — возможный минимум.
То есть ключи, лежащие на трех оставшихся серверах (при использовании базового способа), будут распределяться заново?
Так и не понял, откуда потери больше 25%=)
Было 4 сервера. На всех по 25 ключей. Потом один удалили, 25 ключей пропало, 75 лежат на трех серверах.
Добавляются новые ключи — уже с распределением по 3 серверам. Ну или по 4, где один из них новый.
Или я чего-то не учитываю? Например, «перемещение» — это заполнение по новой пустого места или copy-paste с одного сервера на другой.
Так и не понял, откуда потери больше 25%=)
Было 4 сервера. На всех по 25 ключей. Потом один удалили, 25 ключей пропало, 75 лежат на трех серверах.
Добавляются новые ключи — уже с распределением по 3 серверам. Ну или по 4, где один из них новый.
Или я чего-то не учитываю? Например, «перемещение» — это заполнение по новой пустого места или copy-paste с одного сервера на другой.
Нет, тут есть один существенный момент. Ну пусть было 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, 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. Сколько таких?
Примечание: изменили расположение — изменили расположения с точки зрения клиента, то есть он за ним обратится на другой сервер, где такого ключа нет, сервера об этой перетасовке ничего не знают, поэтому для клиента переместившийся ключ == потеряный ключ.
вот теперь ясно=)
а те ключи, которые «переместились==потерялись» просто будут лежать до своего срока истечения? не вызовет ли это *еще бОльших* накладных расходов?
проблема, очевидно, пропадет, скажем, если выключенный сервер сразу заменят (с тем же порядковым номаром). ну разве что будет немного потерь за время между выключением/включением.
спасибо за развернутые ответы, всегда приятно когда автор доносит мысли в доступной форме.
а те ключи, которые «переместились==потерялись» просто будут лежать до своего срока истечения? не вызовет ли это *еще бОльших* накладных расходов?
проблема, очевидно, пропадет, скажем, если выключенный сервер сразу заменят (с тем же порядковым номаром). ну разве что будет немного потерь за время между выключением/включением.
спасибо за развернутые ответы, всегда приятно когда автор доносит мысли в доступной форме.
На сколько я понял, основная изюминка в том, что каждому серверу ставится в соответствие много больше чем одна точка. (В описании алгоритма на это не было сделано акцента).
Из-за этого при падении одного, нагрузка на следующий по кольцу сервер не удваивается (это в случае если по одной точке на сервер — как на картинке), а распределяется равномерно (при многих точках для каждого). + специфика алгоритма не заставляет перераспределять ключи, уже лежащие на оставшихся серверах.
Спасибо за статью.
Из-за этого при падении одного, нагрузка на следующий по кольцу сервер не удваивается (это в случае если по одной точке на сервер — как на картинке), а распределяется равномерно (при многих точках для каждого). + специфика алгоритма не заставляет перераспределять ключи, уже лежащие на оставшихся серверах.
Спасибо за статью.
При скроллинге страницы кажется, что ключи шевелятся :)
То есть, выбор сервера, на котором будет храниться кэш все-таки делается в приложении? Снять эту задачу с программеров нельзя? То есть в случае с пулом мемкеш-серверов сделать так, чтобы программисты делали только cache_set, cache_get, а мемкеш уже сам решал куда днные положить и откуда их прочитать?
«По параметрам выборки ключ должен определяться однозначно, т. е. для одной и той же выборки ключ кэширования должен быть только один, иначе мы рискуем понизить эффективность процесса кэширования.»
Я бы написал просто — ключ должен быть уникальным.
Я бы написал просто — ключ должен быть уникальным.
Так почему же не написали? Статья бы такими темпами заняла два абзаца, все бы всё поняли наверняка…
Обеспечить уникальность ключа (в строгом смысле) сложно. В предложенной схеме в теории возможны коллизии, когда md5() от двух разных параметров даст одинаковый ключ, хотя для практики это слишком маловероятно.
Однако уникальность обеспечить тяжело, длина ключа ограничена, не всегда в этих условиях мы можем построить уникальный ключ. Параметры выборки уникальны, md5 от них — не факт.
Здесь речь идёт об отображениях (функциях), которые сопоставляют выборки и их ключи кэширования. Одной выборке соответствует ровно один ключ, две разные выборки имеют два разных ключа (если забыть про вероятность коллизии в md5).
Однако уникальность обеспечить тяжело, длина ключа ограничена, не всегда в этих условиях мы можем построить уникальный ключ. Параметры выборки уникальны, md5 от них — не факт.
Здесь речь идёт об отображениях (функциях), которые сопоставляют выборки и их ключи кэширования. Одной выборке соответствует ровно один ключ, две разные выборки имеют два разных ключа (если забыть про вероятность коллизии в md5).
А что будет в случае коллизии? Клиент получит не то, чего хотел, и не поймёт этого?
Да, именно так, но вероятность этого 2-128. Это очень маленькое число :)
В теории есть, на практике больше вероятность получить изменения в ячейке памяти, вызванные космическими лучами ;) Или битый сектор на диске. То есть существует гораздо больше проблем, с которыми надо бороться ;)
В теории есть, на практике больше вероятность получить изменения в ячейке памяти, вызванные космическими лучами ;) Или битый сектор на диске. То есть существует гораздо больше проблем, с которыми надо бороться ;)
про «парадокс дней рождения» слышали? Если у нас закэшировано достаточно большое количестко данных, то вероятность коллизии растёт просто катострофически. Поэтому и спросил. :)
Если я ничего не напутал, то при 2608763571588465 элементах в кэше вероятность коллизии будет около одной десятимилионной, что уже не так уж мало.
Если я ничего не напутал, то при 2608763571588465 элементах в кэше вероятность коллизии будет около одной десятимилионной, что уже не так уж мало.
Судя по статье и комментариям, я так понимаю, что Вы используете именно md5 для ключей. Ничего п ротив не имею, лишь хочу рассказать, почему использую вот этот способ: friends_192_public_sorted_online.
1) Ключ всегда будет уникальным, так как используются id из таблиц
2) Формирование ключа занимает меньше времени
3) Правила формирования всех ключей храню в одном месте, поэтому в любой момент к ним можно обратиться и узнать, из чего состоит каждый ключ.
4) Есть самописный консольный клиент, который позволяет читать/писать/удалять из мемкэша по ключу. Очень удобно бывает. С md5-ключами работать было бы сложнее.
5) Ключи не обязательно делать такими длинными. Вполне достаточно fr_192_pub_asc_1.
1) Ключ всегда будет уникальным, так как используются id из таблиц
2) Формирование ключа занимает меньше времени
3) Правила формирования всех ключей храню в одном месте, поэтому в любой момент к ним можно обратиться и узнать, из чего состоит каждый ключ.
4) Есть самописный консольный клиент, который позволяет читать/писать/удалять из мемкэша по ключу. Очень удобно бывает. С md5-ключами работать было бы сложнее.
5) Ключи не обязательно делать такими длинными. Вполне достаточно fr_192_pub_asc_1.
Не спорю, просто хочу отметить:
1) На тему уникальности и прочего: habrahabr.ru/blogs/webdev/42972/#comment_1063460
2) Спорный момент, накладные расходны на обращение к memcached на несколько порядков больше вычисления md5 и serialize
3) Да, заглянув в memcached и взглянув на ключ 01234fdef345, я не скажу, что это за кэш. Согласен. Оно мне часто надо? Если очень надо, можно полное имя ключа записать в значение еще одним параметром.
4) С md5() работать не сложнее, просто клиент от имени вычислял бы md5 перед обращением. Какая разница?
5) Ключ становится длинным, потому что в тяжелом большом проекте выборка зависит от ооочень большого числа параметров. И там работает общий подход, каждый ключ строить руками — это можно сойти с ума.
1) На тему уникальности и прочего: habrahabr.ru/blogs/webdev/42972/#comment_1063460
2) Спорный момент, накладные расходны на обращение к memcached на несколько порядков больше вычисления md5 и serialize
3) Да, заглянув в memcached и взглянув на ключ 01234fdef345, я не скажу, что это за кэш. Согласен. Оно мне часто надо? Если очень надо, можно полное имя ключа записать в значение еще одним параметром.
4) С md5() работать не сложнее, просто клиент от имени вычислял бы md5 перед обращением. Какая разница?
5) Ключ становится длинным, потому что в тяжелом большом проекте выборка зависит от ооочень большого числа параметров. И там работает общий подход, каждый ключ строить руками — это можно сойти с ума.
Думаю, стоит отметить такой момент: допустим, один из серверов с memcached «вылетел» только на время. Например, неполадки в сети или кончились коннекции. Клиент сохранит ключ на один из других серверов. А при следующем обращении старый сервер снова станет доступным и возмётся старое значение (если между выборками были изменения). Так что лучше не позволять клиенту использовать другие сервера при отказе одного.
Небольшое уточнение. В ключах запрещены символы с ord(char) < 33 и с ord(char) == 127.
Было бы классно получить пост о том ЧТО нужно кэшировать и КАК это делать.
Очень часто в встречаются фразы, «кэшируйте все что можете», «если контент редко обновляется, кладите его в кэш»(например новостная лента), однако, когда дело доходит до практики, все становится совсем не так прозрачно.
Возьмем пример по-сложнее:
Социальная сеть. У пользователя есть друзья, пользователь может заливать фотки.
На каждую фотку назначаются права доступа: доступна всем, доступна только владельцу, доступна друзьям, доступна выбранному кругу лиц.
Что делать в таком случае? Кэшировать списки друзей? Как кэшировать списки фоток, если для каждого смотрящего они индивидуальны?
Очень часто в встречаются фразы, «кэшируйте все что можете», «если контент редко обновляется, кладите его в кэш»(например новостная лента), однако, когда дело доходит до практики, все становится совсем не так прозрачно.
Возьмем пример по-сложнее:
Социальная сеть. У пользователя есть друзья, пользователь может заливать фотки.
На каждую фотку назначаются права доступа: доступна всем, доступна только владельцу, доступна друзьям, доступна выбранному кругу лиц.
Что делать в таком случае? Кэшировать списки друзей? Как кэшировать списки фоток, если для каждого смотрящего они индивидуальны?
Если типов доступа не много (скажем, 3: всем, друзьям, владельцу), то можно хранить три списка. Если много, то можно кешировать записи с запасом, скажем 100 (записи о фотках очень мало будут весить) и на стороне скрипта (пхп, питон, что там у Вас) решать, какие показывать, а какие нет для конкретного пользователя.
Если более кратко, то БД масштабируется несколько сложнее, чем web-сервера, поэтому иногда намного выгоднее закэшировать довольно большие куски данных, а потом обрабатывать их уже скриптом, чем каждый раз дергать БД.
Если более кратко, то БД масштабируется несколько сложнее, чем web-сервера, поэтому иногда намного выгоднее закэшировать довольно большие куски данных, а потом обрабатывать их уже скриптом, чем каждый раз дергать БД.
Не кешировать фотки.
Может быть Кешировать друзей…
Почему — друзья могут потребоваться человеку при серфе( панельку тама отобразить), но у каждого человека они свои, проше кешить всю панельку :)
А вероятность что кто-то зайдет на вашу страницу и будет копаться в ваших фотках — 1-2 человека в день.
Это не та нагрузка где надо заморачиваться…
Главное правило кеширования — «если в этом месте нужно извратиться и замочориться — идите заморачиваться в другое место»
В общем ускоряйте что ускоряется, это разгрузит систему и ускорит то что не ускорялось :)
Может быть Кешировать друзей…
Почему — друзья могут потребоваться человеку при серфе( панельку тама отобразить), но у каждого человека они свои, проше кешить всю панельку :)
А вероятность что кто-то зайдет на вашу страницу и будет копаться в ваших фотках — 1-2 человека в день.
Это не та нагрузка где надо заморачиваться…
Главное правило кеширования — «если в этом месте нужно извратиться и замочориться — идите заморачиваться в другое место»
В общем ускоряйте что ускоряется, это разгрузит систему и ускорит то что не ускорялось :)
Для начала постройте логику без кэширования. Определите, как это работает. Кэширование — это оптимизация, ей — последняя очередь при разработке. Теперь посмотрите на логику. Спроектируйте её так, чтобы способы оптимизации — кэширование и т. п. — можно было воткнуть логику в тех точках, где это разумно (посмотрите, что можно в принципе кэшировать: контент, вывод и т. п.). Когда логика будет работать, разделять права доступа и т. п.: посмотрите, как часто дергается эта страница? какие запросы генерирует? чем отличается страница для разных пользователей? как и что лучше закэшировать? не меняя логику, добавьте кэширование в нужные точки. Проведите еще эксперименты, измените схему кэширования, и т. п.
К сожалению, мне не попадалось литературы и примеров, как должна быть спроектирована система, чтобы можно было легко добавить кеширование.
В самом простом варианте реализации, имеем хранимую процедуру, на вход приходит Id юзера который хочет просмотреть фотки, и id юзера чьи фотки хотят увидеть. Процедура возвращает набор данных для показа, отфильтрованных по правам доступа.
Однако кэшировать всю выборку вряд-ли эффективно… Стоит использовать ORM и кэшировать обьекты?
Я понимаю, что в коментариях к топику сложно обьяснить принципы построения высоконагруженных систем однако буду очень признателен если вы укажите направление и/или основные принципы и литературу…
В самом простом варианте реализации, имеем хранимую процедуру, на вход приходит Id юзера который хочет просмотреть фотки, и id юзера чьи фотки хотят увидеть. Процедура возвращает набор данных для показа, отфильтрованных по правам доступа.
Однако кэшировать всю выборку вряд-ли эффективно… Стоит использовать ORM и кэшировать обьекты?
Я понимаю, что в коментариях к топику сложно обьяснить принципы построения высоконагруженных систем однако буду очень признателен если вы укажите направление и/или основные принципы и литературу…
Насколько я знаю, какой-то замечательной книги, где было бы всё описано, просто не существует. Но возьмем Ваш пример с хранимыми процедурами.
Пусть у меня есть класс StoredProcedure, и я вызываю хранимки, например, так:
Тогда я в StoredProcedure::call имею возможность всегда встроить кэширование впоследствие. Если буду делать что-то типа:
То вряд ли я встрою в такого рода код легко кэширование.
А кэшировать выборки — это не такое плохое решение. Кэшировать объекты тяжело в PHP, если мы про него говорим.
Пусть у меня есть класс StoredProcedure, и я вызываю хранимки, например, так:
$proc = new StoredProcecudure('get_photos');
$result = $proc->call($user->id);
Тогда я в StoredProcedure::call имею возможность всегда встроить кэширование впоследствие. Если буду делать что-то типа:
$con = ....
$result = $con->query("SELECT get_photos({$user->id})");
То вряд ли я встрою в такого рода код легко кэширование.
А кэшировать выборки — это не такое плохое решение. Кэшировать объекты тяжело в PHP, если мы про него говорим.
Я занимаюсь разработкой на .net, но принципы кэширования остаются теми-же.
Обращения к StoredProcedure идет через слой доступа к данным и встроить туда кеширование выборок не составит труда.
Меня больше беспокоит иное:
Процесс вычисления прав доступа к фотке отностиельно тяжелая операция, кроме того результат зависит от id пользователя.
При этом одну и та-же фотка может попасть в разные выборки (например фото моих друзей, сборка последних, в результаты поиска..). В итоге эффективность кеширования выборки оказывается низкой. Какой подход можно использовать в такой ситуации?
p.s. Не подумайте что я реально собрался написать еще одну соц. сеть, просто выбрал пример посложнее, поскольку как реализовать кеширование для новостного сайта я уже имею представление.
Обращения к StoredProcedure идет через слой доступа к данным и встроить туда кеширование выборок не составит труда.
Меня больше беспокоит иное:
Процесс вычисления прав доступа к фотке отностиельно тяжелая операция, кроме того результат зависит от id пользователя.
При этом одну и та-же фотка может попасть в разные выборки (например фото моих друзей, сборка последних, в результаты поиска..). В итоге эффективность кеширования выборки оказывается низкой. Какой подход можно использовать в такой ситуации?
p.s. Не подумайте что я реально собрался написать еще одну соц. сеть, просто выбрал пример посложнее, поскольку как реализовать кеширование для новостного сайта я уже имею представление.
Попадает не фотка, как я понимаю, а информация о ней. Информация о фотографии — это 200 байт? 500? Килобайт? Не так ли страшно, что она закэшируется несколько раз? Тут всегда будет некоторый trade-off между бешеной оптимизированностью и чистотой кода.
Результаты поиска, скорее всего, кэшироваться вообще не должны (или только самые популярные запросы). А во всех остальных ситуациях поможет сброс кэша (о нём попозже).
То есть проблема есть, конечно, но с той или иной степенью достоверности её можно решить :)
Результаты поиска, скорее всего, кэшироваться вообще не должны (или только самые популярные запросы). А во всех остальных ситуациях поможет сброс кэша (о нём попозже).
То есть проблема есть, конечно, но с той или иной степенью достоверности её можно решить :)
Кешировать хтмл код страницы для пользователя который просматривает, потому что быстрее отдать кеш, чем сделать несколько сложных запросов сущностей при разных параметрах.
Это очень спорный вопрос, что лучше кэшировать: выборку или вывод (HTML). С точки зрения глобальной эффективности — лучше всего HTML, отдавать его nginx с модулем memcached. Но это в идеале, если задача позволяет. Бывают проекты (например, соц. сети), где одна и та же страница может кардинально различаться в зависимости от того, кто её смотрит. Плюс еще может быть куча отличий в зависимости от ранга пользователя, чего-то еще. В такой ситуации оказывается выгоднее кэшировать выборки, а HTML формировать на лету.
Для новостного сайта, например, можно кэшировать HTML, вставляя на лету только нужные банеры.
Для новостного сайта, например, можно кэшировать HTML, вставляя на лету только нужные банеры.
Согласен, но новостной сайт к примеру может обновлять кеш, по мере входа информации — таким образом мы выдем нджинксом с мемкешем всю инфу сразу, не запуская даже пыха. Берем хабр, делим на блоки содзаем к примеру сущность главнйо страницы, и выдаем ее. При изменении, что кстати в 100раз реже чем загрузка главнйо страницы по ф5 выдаем кеш. Для незарегистрированных пользователей вообще не создаем сессий, перекладываем анализ на аналитикс. что бы создать сессию, если она нужна уже на странцие логина, просто вставляем 1х1 гиф на нонкешед страницу с генерацией сессии.
Sign up to leave a comment.
Кластеризация memcached и выбор ключа кэширования