Показаны сообщения с ярлыком memcache. Показать все сообщения
Показаны сообщения с ярлыком memcache. Показать все сообщения

20 января, 2010

Миграция ключей

Сегодня в разговоре с одним знакомым всплыл следующий вопрос. В случае, если для дистрибуции ключей по нодам кластера используется типичная схема остатка от деления на количество серверов, какая доля ключей осуществляют миграцию, если один из серверов выводится из схемы? Интуитивным ответом является: "почти все" или "большинство". Тем не менее, если вы любите тренировать мозг, то вот вам небольшая задачка имеющая приложение в web-программировании.

Формально говоря: при заданном количестве серверов N и хеширующей функции ƒ(x) обладающей выходным множеством с мощностью P (log(P) бит, для crc32 P = 232, для md5 P = 2128) какое количество ключей осуществит миграцию в случае, если серверов станет N-1, а для дистрибуции ключей используется значение f(x) % N.

Ответом является формула описывающая зависимость количества мигрирующих ключей от изначального количества серверов и/или количества хранимых ключей.

Допущения: функция ƒ(x) имеет равномерное распределение на всем множестве входных значений, P несравнимо больше N.

Удачи!


24 августа, 2009

Что если цепь рванет?

Сегодня со мной произошел форс-мажор. Я приехал на работу на велосипеде так что, когда рабочий день закончился, я сел на вел и сопровождаемый прохладным ветерком покатил в центр города. Далеко уехать не получилось. Буквально через 40-50 метров я услышал хруст и педаль под ногой резко провалилась. Оказалось, что я поломал крепление заднего переключателя.

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

Моего веса хватило, чтобы хрупкий металл на котором переключатель крепится к раме не выдержал. Таким образом, разорвавшаяся цепь спровоцировала ситуацию, которая конструктивно не должна была произойти — высокая нагрузка на задний переключатель и его крепление. Конструктивно не должна была произойти... Лично меня как потребителя это не особо утешает. Не буду лукавить, в этом инциденте виноват в первую очередь я сам. Цепи просто так не лопаются. Не так давно во время поездки на остров Русский у меня был еще один инцидент с этой цепью. В тот день я ее починил при помощи подручных средств. Мне следовало было сменить ее по приезду домой. Теперь цепь стоимостью 300-500 рублей спровоцировала ущерб на 6000-8000 рублей. Но давайте не будем искать виноватых. Наверное, вы уже спрашиваете себя: “Это конечно прекрасно, но мы то тут причем?”. Благодаря этой ситуации в моей памяти всплыл пост Ивана Сагалаева, который не так давно написал небольшую статью о том, что “кеш не хак”. В целом, я согласен с постулатами которые излагает Иван. Кеширование действительно стало неотъемлемой частью большинства web-проектов. Все знают что такое кеш, во всех языках программирования уже есть интерфейсы к memcached и т.д. А это значит, что кеш, действительно не хак — это наши суровые будни. Но это лишь одна сторона медали. Вторая ее сторона, на мой взгляд, заключается в том, что кеш для некоторых программистов является тем самым “прямым ходом цепи, на котором нет нагрузки”. Когда в приложении появляется кеш, так легко пойти на поводу у собственной лени и сказать: “ну ладно, здесь информация быстро попадет в кеш и все будет оки доки”. Но фактически каждый раз когда вы себе это позволяете вы превращаете кеш в неотъемлемое звено вашего приложения, без которого оно возможно уже не будет работать. Существуют ситуации, когда это обоснованно. Когда кеш действительно является неотъемлемой частью системы. В этом случае он, как и все другие критичные звенья системы, дублируется. Вы дублируете свой кеш? Или может сохраняете его в persistent store чтобы предотвратить эффект “холодного старта”? Хорошо, если так. Полагаясь на кеш, вы не должны складывать с себя обязательств по обеспечению нужного уровня производительности и масштабируемости вашего storage’а. В противном случае, “когда цепь рванет” вы можете потерять что-нибудь более важное чем “просто цепь”. Например, вы можете потерять базу данных, которая не справилась с большим потоком конкурентных запросов. Конечно же, в этом случае вы скажете: “высокая нагрузка на этот агрегат конструктивно не предусмотрена”. Пользователям от этого не легче, скажу я вам. Безусловно, ситуации бывают разные, и возвращаясь к моей маленькой “трагедии”, я понимаю инженеров shimano, которые скорее всего гнались за низким весом (а это тоже очень важно) и поэтому сделали крепеж из хрупкого металла. Но это не меняет главного... В любой момент времени вы должны себе отдавать отчет в том, что произойдет с приложением, если “рванет ваша цепь”.

09 января, 2009

Terracotta v.s. Memcache

В последнее время начали сравнивать Terracotta и Memcache. Мне это сравнение кажется некорректным. Бытует мнение что terracotta - это distributed cache. Это все равно что называть автомобиль "четырехколесным мопедом", только потому, что он может ездить и у него четыре колеса.

Terracotta часто определяют как Network attached memory. И это правда, но не вся. Технически никто не мешает вам использовать terracotta как distributed (или, как его еще иногда называют, clustered) cache. Но тут возникает проблема с HA. В кластере Terracotta всегда есть координатор, который управляет потоком данных. По словам Ari Zilka (одного из основателей Terracota Inc.), именно по этой причине terracotta очень хорошо масштабируется, так как благодаря наличию координатора нет необходимости использовать multicast передачу данных. Однако, наличие координатора означает single point of failure. При использовании memcache SPOF нету, но вам необходимо самому распределять данные по нодам.

Используя terracota вы можете взять LinkedBlockingQueue<Runnable>, пометить его как shared и обрабатывать очередь задач на всех нодах кластера. Вместе с корректной имплементацией распределенных локов мы имеем отличную платформу для распределенных вычислений и возможно даже хранения данных.

С кешем все иначе. Его природа имеет несколько особенностей:

  • потерю кеша приложение должно способно пережить (не требуется HA);
  • при работе с кешем можно обойтись без атомарных его обновлений (не требуются атомарные примитивы и локи);
С первым все должно быть понятно. Если приложение не смогло пережить потерю кеша, значит там хранился оригинал каких-либо данных, а следовательно это уже не кеш. Со вторым немного сложнее. Так как значение в кеше зависит только от внешних данных (данных не хранящихся в кеше), значит невозможны операции когда новое значение кеша зависит от его предыдущего значения. А значит не нужны атомарные обновления.

Memсache отлично подходит для таких сценариев. Ну а если вы решили использовать memcache как storage, а не как кеш, то вы обречены на собственную реализацию атомарного обновления данных, как минимум.

Таким образом, memcache и terracotta - это совсем разные вещи. Первое - это просто network attached memory сервер. И без дополнительного кодирования его можно использовать только для кеширования данных. Второе - полноценная платформа для кластеризации вычислений. Как говорится, know your enemy.