пятница, 13 ноября 2009 г.

[comp.prog.thoughts] Фокусы распределенности: ответ приходит раньше, чем уходит запрос ;)

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

Представим себе, что есть покупатель (система P), магазин (система M) и склад (система S). Покупатель делает заказ в магазине, магазин выдает заказ на склад, а склад выдает покупателю информацию о сроках поставки заказа. Грубая схема такова:

  • от P в M идет синхронный запрос pay;
  • M выполняет у себя какие-то действия и возвращает P ответ pay_ack;
  • от M в S идет запрос deliver, в котором лежат координаты P;
  • S отсылает P запрос deliver_schedule.

Так вот, если M связывается с S до того, как отошлет pay_ack в P, то P может получить deliver_schedule еще до того, как М отправит в P pay_ack. Более того, даже если M отсылает в S запрос deliver после отсылки pay_ack в P, все равно deliver_schedule может придти к P раньше, чем pay_ack!

Что в этом фокусе страшного? Страшное начинается при попытке понять, к какому именно заказу относится deliver_schedule :)

В самом плохом случае в pay_ack может лежать некий уникальный ID заказа от M. Этот же ID заказа будет и в deliver_schedule. Но для P он окажется неизвестным, т.к. pay_ack до него еще не дошел.

Получается картинка: P инициировал pay и ждет ID заказа, тут к нему приходит deliver_schedule с неизвестным ID заказа. Что же с ним делать? Логировать сей печальный факт и выбрасывать. Потом получать pay_ack, фиксировать ID заказа в БД и ждать deliver_schedule. Который не больше не придет :)

Причем здесь распределенность? При том, что P в современных условиях может быть реализован в виде нескольких (десятков, сотен) автономных процессов, работающих на разных компьютерах. Поэтому простые схемы, когда P не обрабатывает deliver_schedule из-за того, что он заблокирован на ожидании pay_ack, уже не пройдут. Се ля ви.

PS. Простое решение здесь состоит в том, чтобы P мог отказываться принимать deliver_schedule с неизвестным ID. И чтобы в этом случае S перепосылал deliver_schedule через какое-то время. Но, если S не может этого делать, то P придется что-то предпринимать самому (скажем, фиксировать неизвестные ему deliver_schedule и при получении pay_ack проверять их).

PPS. А еще в распределенных системах pay_ack может просто теряться из-за сбоев оборудования или рестартов компонентов. Так что простые двухфазные обмены вроде pay/pay_ack, deliver_schedule/deliver_schedule_ack не есть хорошо. А многофазные схемы снижают пропускную способность и увеличивают время обработки, что так же не есть хорошо.

PPPS. Схема с покупателем, магазином и складом приведена просто для иллюстрации.

15 комментариев:

Skynin комментирует...

Это еще не проблема :)
Рутинная организация асинхронности, отложил неизвестный в копилку и жди.

Проблема когда источником ID может выступать каждый. Как обеспечить уникальность?
И вторая - а кто и как контролирует, "заказ" с таким ID всех кого нужно прошел?
И третья - кто-то из промежуточных наткнулся на инфу в заказе и не знает как ее обработать - кому отсылать на уточнение?

Евгений Охотников комментирует...

>Это еще не проблема :)

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

Т.е. проблема была разглядеть эту асинхронность :)

>Как обеспечить уникальность?

UUID-ами?

>И вторая - а кто и как контролирует, "заказ" с таким ID всех кого нужно прошел?

Это уже зависит от специфики задачи.

>И третья - кто-то из промежуточных наткнулся на инфу в заказе и не знает как ее обработать - кому отсылать на уточнение?

А зачем отсылать? Рецепт известен:
Рутинная организация асинхронности, отложил неизвестный в копилку и жди.
;)

Dmitry Vyukov комментирует...

Это как раз то, о чём я писал тут:
http://software.intel.com/ru-ru/blogs/2009/02/07/fifo/
(и ты, насколько я знаю, это читал ;) вообще после написания у меня было ощущение, что никто просто не понял, о чём я говорю :) )
В твоём примере middleware обеспечивает только per-producer FIFO. С ним возможны такие проблемы. Это, кстати, то, что обеспечивается в Эрланг.
Causal-FIFO значительно проще и интуитивнее, он таких проблем не вызывает.

По поводу того, что с этим делать. Я на эту тему несколько размышлял; не могу сказать, что у меня полностью сформировался однозначный взгляд, но первый вывод получился следующий.
Проблема не в per-producer FIFO, проблема в топологии системы, где есть несколько путей от одной точки до другой (сообщение по одному пути может обогнать сообщение по другому пути). Это такой red herring как циклические ссылки между объектами (некоторые говорят, а вот у нас поддерживаются циклически ссылки а вот у вас нет, а лучше бы их вообще не иметь в системе, тогда и поддержка не нужна).
Соотв. решение для ситуации в примере: M посылает S запрос deliver, S отвечает М запросом deliver_schedule, S отвечает Р запросом pay_ack.

Skynin комментирует...

Как обеспечить уникальность?
UUID-ами?

Если от "заказа" больше ничего не нужно, кроме как быть уникальным, то да :)

UUID это метка для компьютера, никак не связанная со смыслом самого "заказа". А частенько нужен порядок следования ID - чтобы когда соберутся в одном месте было понятно что этот ID идет после того ID. Миллисекунды не годятся, потому что на момент сверки может быть неизвестным - все ли "заказы" собрались?

А зачем отсылать? Рецепт известен:
Рутинная организация асинхронности, отложил неизвестный в копилку и жди.

Не-е-е, ждать придется до бесконечности. Тот кто отослал надеется что дело свое сделал. Ждать можно если кто-то пришлет - эй, у всех все в порядке, сообщите о своих застрявших ID и причинах!

Это уже зависит от специфики задачи.
Именно так, все эти проблемы решаются по специфике.
Печаль наступает когда система работает, а вот специфика - изменилась :)

Евгений Охотников комментирует...

>Это как раз то, о чём я писал тут:
http://software.intel.com/ru-ru/blogs/2009/02/07/fifo/


Спасибо, что напомнил. Нужно будет перечитать. А то я действительно не подумал, что передача сообщений в независимые процессы одной системы может рассматриваться как вариант FIFO.

Евгений Охотников комментирует...

>А частенько нужен порядок следования ID - чтобы когда соберутся в одном месте было понятно что этот ID идет после того ID.

Метки времени Лампорта? ;)
Я у себя в таких случаях делаю объединение ID-шников в цепочки. По мере продвижения заявки по компонентам их ID провязываются в цепочки.

>Не-е-е, ждать придется до бесконечности. Тот кто отослал надеется что дело свое сделал.

Мне как раз нравится подход, когда получатель имеет возможность ответить отрицательно на запрос, который он не готов сейчас обработать. И чтобы отправитель этого запроса получив такой отрицательный ответ повторял запрос через какое-то время. Или же отменял всю операцию.

Skynin комментирует...

2Dmitry Vyukov
Не читал раньше, вот оказывается откуда головняк при разработке корпоративного софта:

В идеале, causal FIFO - это то, что всегда бы хотелось видеть конечному пользователю, ДЛЯ физически распределенных систем.

Я когда читаю постинги ФП программистов все думаю - ребят, ну каким право баловством вы занимаетесь и называете это "взрывом мозга". Тут какой год мозг взрывается от causal FIFO в корпоративе, и ничего кроме "заплаток" и писанины по месту, по конкретике от этих взрывов в голову не приходит...

Skynin комментирует...

Метки времени Лампорта? ;)
Может быть, не слышал о таких :)

Но я только начал :) "а когда прохождение заказа порождает новые заказы?"

Вобщем у меня таких вопросов - тьма :)

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

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

Вобщем нравится мне моя область. А вот то о чем ФПшники говорят - скукота. Им наверное наоборот

Евгений Охотников комментирует...

>Может быть, не слышал о таких :)

Я о них прочитал в книге о распределенных системах: http://www.rsdn.ru/article/?794

На английском здесь: http://en.wikipedia.org/wiki/Lamport_ordering

Skynin комментирует...

Метки времени Лампорта? ;)
Прочел в лекции "Синхронизация в распределенных системах":
... в большинстве случаев согласованное время может не иметь ничего общего с астрономическим временем

Если два события x и y случились в различных процессах, которые не обмениваются сообщениями, то отношения x->y и y->x являются неверными, а эти события называют одновременными.

Беда как раз в том что и к астрономическому времени имеет, и в разных системах - а НЕ одновременные :)
Но почитаю дальше, пусть осядет, и проварится в голове

Skynin комментирует...

Я о них прочитал в книге о распределенных системах
Да, спасибо, погуглю материал, думаю что иногда вполне может пригодится.

Ну и в завершение:
Опытный программиста начинающему "А ты знаешь что в сутках 25 часов? 24 говоришь?
Так как же тогда твоя система среагирует на перевод летне-зимнего времени!"

Недавно был влет у нас на эту тему - ребята не знали, а опытные вовремя не подсказали :)
И посыпались повторно сообщения. За последний час :)

Евгений Охотников комментирует...

>Недавно был влет у нас на эту тему - ребята не знали, а опытные вовремя не подсказали :)
И посыпались повторно сообщения. За последний час :)


Ну кто же перепосылку по локальному времени делает? ;) По UTC, по UTC нужно было ;))

Dmitry Vyukov комментирует...

Метки времени Лампорта? ;)

При использовании меток Лампорта, да и полных векторых часов, тоже не понятно сколько ждать. Там надо выбирать минимальный элемент из множества, а если некоторые элменты ещё не пришли по сети, то мы не можем определить минимальный пока не придут все. А когда они придут - не известно.
В системе с разделяемой памятью это можно обойти путём предугадывания/подглядывания "будущих" сообщений. А вот в распределенной системе с этим ничего хорошего не сделать.
Иногда это обходится с помощью таймаутов, но вариант тоже не идеальный. Т.к. всё равно будет либо неконсистентность либо придётся выкидывать какие-то сообщения.

Dmitry Vyukov комментирует...

По поводу меток Лампорта - это первая ссылка в моём блоге:
http://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf
Фундаментальная работа 78 года по поводу упорядочивания в распределенных системах. Этакая теория относительности применительно к CS.

Skynin комментирует...

Ну кто же перепосылку по локальному времени делает?
И кто же хранил в дате только последние 2 цифры года :D

По UTC, по UTC нужно было
Не я, только какая от этого польза,
если в чьем-то коде на входе 4 цифры, на выходе - тоже 4ре, а в глубине - 2