Pull to refresh

Comments 22

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

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


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


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

Проблема cache stampede (hit miss storm) также называется dog-pile effect и вариант решения описывался здесь habrahabr.ru/post/43540

Спасибо за замечание, добавил еще один вариант названия

Посмотрите на такой простой кусочек кода:

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

Этот код приведен как раз для того, чтобы продемонстрировать определенную проблему, о чем сказано ниже. Как он может быть боевым? ;)

Прочитайте, пожалуйста, мой коммент внимательнее. Сам код, а не что он делает, плох.

А можете привести пример как бы вы его написали читабельнее, используя нормальные практики программирования ?

Мы в Badoo решаем эту проблему тем, что пишем данные во все кэширующие серверы сразу. Благодаря этому при чтении мы можем использовать общий механизм выбора сервера — в коде можно использовать обычный механизм шардирования по User ID, и при чтении не нужно ничего знать про специфику этого «горячего» ключа. В нашем случае это работает, поскольку у нас сравнительно немного серверов (примерно десять на площадку).

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


А вы полностью сами написали распределенный кэш? Почему индустриальный лидеры: hazelcast и ignite — не подошли? Там и шардирование есть, и репликация.

Записывать кэш на все 10 серверов — это, кажется, супер дорого, поправьте меня, пожалуйста. Особенно, если вы ждёте Аков от всех нод, а не какого-то кворума.

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


Я нашёл меньше 20 групп ключей, использующих схему со всеми серверами. Обычно это какие-то счётчики или кэши конфигурации по странам/городам, которые обновляются только фоновыми скриптами (т.е. мы исключаем параллельные обновления). В онлайне эти ключи только читаются и не отличаются от остальных.


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

Вынос обновлений в фон

А если проекты маленькие, но проблема с параллельными вычислениями все же присутствует? Выносить в фон выглядит немного дороговато- переписывать чужой код, кто-то должен
поддерживать, помнить про это, убедить остальную команду, клиента…
Тоже есть небольшой опыт с метками (boolean), метками времени, но если что перегружается, то все остается в «воздухе». Что если на момент вычисления блокировать какой-нибудь файл? Если основной процесс с вычислениями помрет, то файл будет автоматом разблокирован(?) и другой процесс в очереди сможет подхватить работу, при этом основной процесс может записывать какие-то промежуточные вычисления в этот файл, что позволит следующему начать уже не с нуля. Это конечно все нагрузка на диск, но опять же это не для крупных проектов.
Дальше можно нарастить более сложную логику: если на «холодный старт» много что нужно вычислить, то может не ставить в очередь другие процессы, а дать им что «повычислять»? Т.е. по кол-ву «вычислений» появятся что-то вроде «мастер» процессов, а остальные останутся в очереди, когда «мастер» процесс завершает свой кусочек вычислений для кэша он становится в очередь к остальным, как-то только все «мастер» процессы выполнят свои задачи, то все процессы отдадут ответы из кэша. -Пока лишь фантазии…

Честно говоря, вариант с мастер-процессом не выглядит проще в реализации, чем фоновое обновление (хотя сложно "лечить по фотографии").


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

Я себе такой велосипед изобретал против параллельного обновления кэша: обернул методы set/get кэша, добавил внутри сеттера в сам кэш данные о ttl и датах создания-протухания, а потом в геттере проверял, сколько кэш уже живёт в момент обращения к нему. Если прожил 90% от своего срока, то продлевал ему время жизни ещё немного, но наружу всё равно возвращал false. В итоге код, запрашивающий данные, получал false и шёл обновлять их думая что их нет, но все прочие клиенты получали старые данные следующие пару секунд.
Отличная идея! Но есть вопрос.
Что будет, если бд по какой то причине не сможет обновлять кеш некоторое время? Ведь в этом случае практически все клиенты вместо null будут получать «протухшие» значения, до тех пор пока не возобновится обновление. Возможно это допустимое поведение, но его нужно учитывать.

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

Есть ли готовая библиотека для PHP, которая реализует кэш, инкапсулирует решение проблем, описанных в статье (cache stampede и обработка сбоев при обновлении кэша), и подходит хотя бы для небольших проектов?

Я такой не видел.


Достаточно просто найти реализацию согласованного хеширования (оно есть, например, в расширении memcached), а вот всё остальное в виде отдельной библиотеки мне не попадалось...

Блокировка перед началом выполнения операции пересчёта/ загрузки данных
function getContactsCountCached1(int $user_id) : ?int
	{
		$contacts_count = \Contacts\Cache::getContactsCount($user_id);
		if ($contacts_count !== false) {
			 return $contacts_count;
		}
		
		if ($lock->get() === true) {
			while($lock->get() === true){
				sleep(DB_TIME_OUT / 10); //wait n/10 sec
			}
			return getContactsCountCached($user_id);
		}
		
		$lock->lock(DB_TIMEOUT); // set on n sec
		$contacts_count = $this->getContactsCount($user_id, DB_TIMEOUT);
		$lock->unlock();
		if (is_null($contacts_count)) {
			 return null;
		}

		\Contacts\Cache::setContactsCount($user_id, $contacts_count);
		return $contacts_count;
	}

Спасибо за отличную статью! Мотивирует!
Было бы здорово, если бы вы прогнали тест с XFetch и дали бы возможность сравнить с остальными.

Что-то подобное есть в дополнительных материалах, которые я приводил:


Репозиторий на GitHub с описанием и тестами разных способов

Там в директории samples/ есть log-файлы с результатами теста разных способов (правда никакой визуализации нет и не очень удобно сравнивать способы друг с другом).

Не судите строго за мой вопрос — я наткнулся на согласованное хеширование при изучении L4 балансировщиков. Правильно ли я понимаю, что данный алгоритм хеширования используется при большом количестве балансировщик, которые могут быть увечеличены горизонтально. В таком случае слоты — это балансировщики в данном алгоритме, правильно ли я понимаю? Если у нас есть 10 балансировщиков, каждый из них независимо друг на друга будет считать хеш для тех пакетов, которые на него пришли (LB на схеме)?
image
Sign up to leave a comment.