memcached и много одновременно одинаковых запросов к нему

[BoRay]

Вечер добрый!
На собеседовании задали задачку, которую я попытаюсь объяснить на словах, хотя он ее назвал что-то вроде "проблема гонки запросов". Хочу понять что от меня требовалось И получить направления на решение это задачи.

Задача(пытаюсь пересказать):
Есть большое количество одновременных обращений к базе memcached, одинаковых обращений. Скажем 10 штук в секунду. Нужно сделать так что 1ое обращение шло в мемкешед, а 9 ждали ответа и после того как 1ый получил ответ - эти 9ть тоже получили тоже самое что первый получил.


Вопросы:
1) если кто знает "нормальное" название этой задачи - озвучте плиз
2) а если кто знает где можно посмотреть варианты решения, или какой-нибудь материал на этот вопрос - тоже буду благодарен.

ПС, не имею опыта работы с memcached. И еще меня смутило 10ть запросов в секунду... для мускла даже это мелочи, если конечно они не тяжелые.

 

[Вурдалак]

если кто знает "нормальное" название этой задачи - озвучте плиз

— это называется состояние гонки или race condition.

Совсем недавно, кстати, обсуждалось, давали ссылку: http://php.net/manual/en/memcached.cas.php

 

[DiMA]

BoRay
в какой конторе задают столь умные вопросы?
(ну, вопрос то, естественно, крайне элементарен, но на общем профанском уровне - достоин)

Разумеется, cas здесь никаком боком, т.к. очевидно смахивает на типичную задачу про перестроение сложного объекта в кеше. Если 100 потоков видят, что некий объект устарел:
а) нельзя допустить, чтобы они все перестраивали объект (выполняя, например, тяжелые SQL запросы)
б) нельзя допустить, чтобы они тупили (любой оверхер), пытаясь завладеть правом на перестройку
в) защита от зависания потока, который пошел перестраивать кеш
г) во время перестроения кеша объект опять устарел и его еще раз нужно перестраивать (+связанная с этим проблема рассинхронизации)

До таких оптимизаций Б, В, Г в той конторе вряд ли дошли.

 

[Вурдалак]

$expiresAt = $m->get('expiresAt', null, $cas);

if( $expiresAt < time() )
{
    $m->cas($cas, 'expiresAt', time() + 86400);

    if( $m->getResultCode() === Memcached::RES_SUCCESS )
    {
        // Обновление объекта в кеше
    }
}

?

 

[HraKK]

интересно кстати посмотреть на решения)
а так же на классическую задачу - paginator на мемкеш

 

[DiMA]

Ожидать от кандидатов на собеседовании, что они будут знать cas - глупая затея. Из проводимых мной ~200 собеседований в год, дай Бог о команде add знало человека 2-5 (чем оно от set/get отличается)... А ты на cas замахнулся! Не помню, сколько народа созналось, что *слышала* про cas на мастер классе, но явно не весь зал Человек 5, кажись... Из этого следует, что вопрос либо на add, либо составитель вопроса глуп, рассчитывая найти программиста, знакомого с cas.

Именно add позволяет мгновенно без оверхеда среди сотен потоков, участвующих одновременно в гонке за неким ресурсом, определить поток-счастливчик. CAS нужен, когда много поток будет что-то писать. Но мы же ничего никуда не пишем параллельно, а просто выбираем победителя гонки. Т.е. пишем побочный флаг, а само действие - выбора. Через cas этого не сделать. Cas нужен, когда цель задачи - записать некие данные (а не побочный флаг "занято"). Ну, можно применить select for update или get_lock(). Cas - это отдаленный аналог транзакций, что очевидно здесь никаким боком. Правда, совершенно не понятно что будут делать обломавшиеся потоки, после самого add, видимо, опять долбиться в флаг до посинения в цикле =) С большими оговорками и оверхедом add можно реализовать через cas и наоборот (типа изврата: блокировка через транзакции без select for update или транзакции путем блокировок).

Если рассмотреть задачу более глубоко, то она решается созданием идеального класса MemcacheLock. Да, в нем применяется add и cas. Но уже для профита от самого класса. Дело в том, что если использовать мемкеш нативно, то подобная задача займет очень много строк кода (она более сложная, чем простой add, см пункты Б, В, Г). А вот с идеальным классом Lock подобные задачи решаются реально в 1 строку кода.

Поясню пункт Б.
Окей, 100 потоков обнаружили, что некий объект устарел. Окей, мы защитились от того, чтобы все они не ломанулись перестраивать объект. Но пока объект не перестроится (допустим, за 5 секунд), все эти потоки будут долбиться в тот флаг, проверяя, можно ли завладеть правом на перестройку объекта. Это охрененная нагрузка сама по себе! Цель программиста в том, чтобы не только заняться перестройкой объекта в один поток, но еще и неким способом другим 99 собратьям (+кучу новых/будущих потоков, которые постоянно будут запускаться с целью обратиться к объекту) сообщить, что не нужно никуда больше долбиться и создавать оверхед! Короче, я про это все час распинался на мастер-классе (как свести оверхед реально к теоретически возможному минимуму).

Не хочу никого обижать, но к сожалению, судя по приведению примера из доки:
1. Это еще раз подтверждает мою статистику тотального удручающего положения, что мемкеш воспринимается как простое кеш хранилище, а не сложную в изучении базу данных, которая дает программисту КУЧУ НОВЫХ ПАТТЕРНОВ для более эффективного (близкого к идеальному, с почти нулевым оверхедом) решения широкого круга типичных каждодневных задач.
2. Знание мемкеша на уровне доки (идеально, всех команд), это где-то 5% того, что необходимо понимать о нем (знание на уровне set/get - менее 1%). О тех самых паттернах и профите от них не напишут в доке. Точно так же, как в доке по MySQL не будут никого учить программированию.

 

[MiksIr]

Мне кажется или пересказ задачи немного хромает?

 

[Вурдалак]

DiMA, ты целый час распинался именно в таком духе или была хоть какая-то конкретика?

MiksIr, скорее всего имелась в виду ситуация, когда один поток обновляет данные, а остальные ждут.

 

[DiMA]

Нет, я как раз объяснял, как правильно решать подобные задачи (теории было минут 20, во вступлении и окончании). Да это все элементарнейшие темы для тех, "кто в теме"... Честно говоря боюсь выглядеть кепом в глазах уважаемых коллег .-)

 

[zerkms]

Хотелось бы про пункт Б добавить:

Очень часто не обязательно оставшимся 99 потокам ждать новые свежие данные, очень часто бизнес устраивают и "старые" данные. В этом случае можно отдать обновление данных на отлуп 1 потоку, а остальным 99 отдать старые (и продолжать отдавать старые, пока новый кэш не будет построен).

 

[AmdY]

убираем попсовое memcached, заменяем его словом файлы и вспоминаем - ой, это же обычные блокировки при работе с файлами, которые описаны в любом нормальном учебнике http://php.net/flock.
всё же интернет и обучения на статьях-блогах-хабрах подрывает фундаментальность знаний.

 

[DiMA]

Нет, пункт Б не об этом (то, что нужно выдавать старый объект, даже если мы знает об инвалидации - очевидность из очевидностей).

Некий поток видит - объект устарел. Но этот поток еще не знает, что кто-то уже перестраивает объект. И что сделает традиционный программист в данной ситуации? Попытается поставить add (или Lock). Т.е. все 5 секунд, что пройдут до перестройки объекта, все множество других потоков будет ломится в этот флаг, означающий "занято"! Пукт Б о том, чтобы недопустить этих лишних операций. Да, они очень легкие, но в целом дадут большую нагрузку на сеть и сам мемкеш.

Цель в том, чтобы поток за одно чтение не просто узнал, что объект устарел, а так же то, что его перестройкой уже кто-то занят и не нужно пытаться поставить блокировку для обновления!

> очень часто бизнес устраивают и "старые" данные
Такой проблемы нет (почти). Просто раньше инвалидируем кеш, чтобы к нужному моменту уже все было свежем, что устроит любой бизнес. Единственное, к чему можно придраться - мы вынуждены перестраивать объект не раз в минуту, а заранее, раз в 40 секунд, например. Ну, тут уж надо выбрать - либо минимум перестроений с устаревшими данными, либо чуть выше нагрузка от перестроения, зато данные всегда свежие. В веб 2.0 таких проблем либо почти нет, либо они не существенны на фоне оптимизации по снижению оверхеда. Если мы что-то кешируем, мы уже заранее согласны, что такой тип данных не критичен (как деньги) и можно согласиться на некоторые потери.

 

[DiMA]

Да, flock больше подойдет (как и select for update / get_lock), т.к. поток без лишних телодвижений будет заморожен до момента выделения ему эксклюзивного доступа. С add/cas такие трюки не пройдут, поток не может быть заморожен.

 

[MiksIr]

Ы. Классика жанра
http://sysoev.ru/mod_accel/readme.html#busylocks

 

[Активист]

Я тут так внимательно все прочитал и есть такое предложение:

1. Одновременно - не значит параллельно, да, придел времени между запросами будет стремиться к нулю.
2. Один процесс видит, что данные устарели, обновляет данные - старыми данными, соответственно другие процессы будут думать, что данные уже новые, и пускай остальным запросам отдают старые данные, в то время, процесс, который выполнил обновление - старыми данными может форкать еще один процесс, который в свою очередь выполнит обновление необходимого кеша, предаварительно проверив - есть ли еще процесс, если есть - просто уйдет по exit(0).

Наверное опять скажите - нифига не понятно, пишешь плохо, вот так думаю понятней.
Бекэнд:
1. Данные устарели;
2. Обновить информацию старыми данными;
3. Запустить независимый процесс обновления кеша. (назовем "процесс дб кеш");
4. Отдать на запрос "старые данные";
5. ...;
6. Закончено.

Процесс дб кеш:
1. Проверить, есть ли еще один конкретный запрос такого же типа, проверить, жив ли, если жив - уйте, если freeze - убить;
2. Выполнить необходимые действия;
3. Обновить данные;
4. Закончено.

Зачастую, "Процесс дб кеш" реализовывается в виде отдельного работающего демона.

 

[MiksIr]

>и пускай остальным запросам отдают старые данные
Это кто за меня решил?

> обновляет данные - старыми данными
И тут внезапно оказывается, что в кеше вообще нет таких данных.

 

[BoRay]

BoRay
в какой конторе задают столь умные вопросы?
(ну, вопрос то, естественно, крайне элементарен, но на общем профанском уровне - достоин)
....
До таких оптимизаций Б, В, Г в той конторе вряд ли дошли.

Контору называть не хочется, но сайты у них крутятся с посещаемостью от 200-300к хитов в сутки.

Я тут так внимательно все прочитал и есть такое предложение:
...

На мой взгляд - алгоритм логичен, и подходит под решение описанных проблем ДиМой, кроме как проблемы "г) во время перестроения кеша объект опять устарел и его еще раз нужно перестраивать (+связанная с этим проблема рассинхронизации)".

Может ДиМа прокомментирует алгоритм?


ПС. спасибо за активность в теме!

 

[Активист]

MiksIr
> Это кто за меня решил?
За тебя никто ничего не решал, это мое предложение реализации.

Ну если внезапно так произошло, то "логика" Сысоева в реализацию. Твой алгоритм по этому поводу хотелось бы услышать, а не просто флейм, конкретики нам конкретики.

Вообще, решение подобных задач требует анализа важности актуальности данных, если актуальность данных не критична, но критично ожидание ответа, то можно и отдавать старые/дефултные значения, если актуальность важна - то в очередь, а если на эти данные идет множество конкурентных запросов ежесекундно - то будьте добры, позаботитесь об их актуальности заранее, а не дожидайтесь, пока они окончательно устареют и выпиливаться из кеша, если нагрузка происходит ВНЕЗАПНО на короткий срок и актуальность данных критична - очередь.

Кстати, вот решение Сысоева про busy lock - оно ведь опять же подразумевает использование мемкеша или добротного демона-прокси?

 

[DiMA]

> 200-300к хитов в сутки

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

MiksIr

То, что ты написал, классические типичные ошибки. Не первый раз слышу этот боян, что мол давайте эту задачу на кеширующий веб-сервер переложим. Как раз на мастер-классе кто-то это же заявил. Это чушь и попытка переложить решение важной задачи на дядю (еще регулярно слышу аналогичную чушь: нафига я вещаю про честное горизонтальное масштабирование, есть же готовое масштабирование в MongoDB, Cassanda, MySQL кластер и т.д.). Наш объект в общем случае не имеет ни малейшего отношения к веб-страницам. Скрипты, которые перестраивают и юзают объект в общем случае не являются веб-контролами, а, например, крон-скриптом обрабатывающим статистику.

BoRay

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

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

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

 

[MiksIr]

> Ну если внезапно так произошло, то "логика" Сысоева в реализацию.
А внезапно так и произойдет, в случае с мемкешом

> Твой алгоритм по этому поводу хотелось бы услышать
Я велосипеды не выдумываю

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

> Кстати, вот решение Сысоева про busy lock - оно ведь опять же подразумевает использование мемкеша или добротного демона-прокси?
Флаги в шаренной памяти. Это очень старое решение (я не про бизи лок, а вообще про mod_accel), так что тогда одного фронт-енда с кешом казалось достаточно
Но в общем я эту ссылку дал именно с точки зрения алгоритма и возможных таймаутов.