пятница, 20 декабря 2013 г.

[prog.thoughts] Подводные камни при проектировании на конкретном примере

Описанный ниже пример, хоть и относится к SObjectizer, я вынес в блог в качестве демонстрации того, с какими неожиданными открытиями можно столкнуться при проектировании ПО. Как пример непредсказуемости и недетерминированности процесса разработки ПО. В особенности когда речь идет о разработке чего-то нового, а не очередного повторения ранее многократно проделанного. В общем, хочу показать, почему опытные ПМы умножают названные разработчиком сроки на Пи ;)

Текста довольно много, поэтому упрятано под кат для тех, кому это действительно интересно.

Я сейчас пытаюсь найти совместное решение сразу двух проблем: повышение скорости обработки сообщений и реализация механизма selective receive. Механизм selective receive -- это такая штука, которая позволяет выбрать из потока сообщений m1, m2, m3,... только одно сообщение m2, а остальные сообщения (т.е. m1, m3,...) оставить "до лучших времен" и обработать их когда-нибудь позже.

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

Механизм selective receive реализован в Erlang-е. Оттуда и хотелось перенести его в SObjectizer. Но в Erlang-е сообщения получают процессы, т.е. самостоятельные, независимые и взаимно изолированные сущности. Каждый процесс имеет свой контекст исполнения. А, следовательно, порядок очистки разными процессами своих очередей сообщений несинхронизирован. Т.е. если процессам P1 и P2 будет послана цепочка одинаковых сообщений m1, m2 и m3, то P1 может обработать их всех еще до того, как P2 извлечет m1.

Кроме того, в Erlang, насколько я знаю, у каждого процесса своя очередь сообщений и в Erlang нельзя отослать одно и то же сообщение сразу нескольким процессам -- нужно делать отдельную отсылку экземпляра сообщения каждому процессу (при этом на уровне реализации дублирования экземпляра сообщения может не происходить и, если процессы физически работают на одной ноде, то на обработку они могут получить один и тот же экземпляр, но это уже детали реализации).

В SObjectizer ситуация другая. Здесь сообщения получают не процессы, а агенты. Агенты -- это обычные объекты, которые разделяют какой-то общий контекст. В самом общем случае таким контекстом будет все адресное пространство процесса, в котором работают агенты. В более частном случае контекстом является рабочая нить SObjectizer-а, на которой агенты работают.

И это принципиальная фишка SObjectizer: каждый агент привязывается к рабочей нити и пользователь может этим управлять. Например, если агент нуждается в собственной рабочей нити, то он объявляется активным агентом и SObjectizer выделяет ему отдельную нить, на которой будет работать только этот агент. Однако, если этот агент должен делить с другими агентами какой-то общий ресурс (например экземпляр std::map со списком текущих транзакций), то доступ к этому ресурсу должен быть защищен каким-то образом (очевидный вариант -- std::mutex-ом).

Однако, если пользователь знает, что группа агентов работает с общим ресурсом (тем самым std::map-ом) и не хочет явно синхронизировать доступ к нему, то это можно сделать и неявно. Для этого достаточно привязать всю группу агентов к одной рабочей нити (объявив такую группу активной группой или привязав агентов к дефолтному диспетчеру). Вот такая возможность привязки агентов к общему контексту исполнения, а так же взаимодействие с другими агентами через отсылку сообщений, делает разработку многопоточных приложений на SObjectizer гораздо проще, чем с ручным управлением нитями и синхронизацией доступа к общим ресурсам. Но сейчас не об этом :)

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

Итак, у SObjectizer есть два важных отличия от Erlang-а: нескольким логически связанным между собой агентов можно гарантировать работу на одном контексте и отсылка сообщения в mbox может привести к возникновению событий сразу у группы агентов.

На практике это означает вот что. Допустим, есть два логически связанных агента A1 и A2, которые подписаны на один mbox и обрабатывают сообщения одного и того же типа m. Если отсылается цепочка сообщений m (например, m1, m2, m3,...), то SObjectizer обеспечивает запуск обработки этих сообщений в определенном порядке. Это будет либо A1(m1)+A2(m1), затем A1(m2)+A2(m2) и лишь затем A1(m3)+A2(m3). Либо же: A2(m1)+A1(m1), затем A2(m2)+A1(m2) и лишь затем A2(m3)+A1(m3). Но ни в коем случае не A1(m1), A1(m2), A1(m3), A2(m1), A2(m2), A3(m3). Подчеркну, это гарантируется SObjectizer. И это принципиально отличается от Erlang-а, где последовательность обработки сообщений двумя процессами может быть любой из вышеприведенных.

Теперь можно перейти непосредственно к большущему и острому подводному камню. А именно: нужно ли обеспечивать такое поведение при наличии selective receive?

Допустим, агенты A1 и A2 одинаковые, имеют два состояния, s1 и s2. В состоянии s2 они не обрабатывают сообщения m, накапливая их для последующей обработки, а ожидают сообщения k, получив которое переходят в s1. Вернувшись в s1 агенты обрабатывают все ранее накопленные сообщения m(i). Т.е. если рассматривать агента A1 и цепочку сообщений m1, m2, m3 и k1, то его поведение будет таким: A1(m1), A1(k1), A1(m2), A1(m3). Если добавить в рассмотрение еще и A2 для той же самой цепочки сообщений, то картина должна получиться такой: A1(m1)+A2(m1), A1(k1)+A2(k1), A1(m2)+A2(m2), A1(m3)+A2(m3). Что, полагаю, логично, если пытаться сохранить гарантии, которые дает SObjectizer без selective receive.

Но тогда идея по реализации selective receive, озвученная мной две недели назад, уже не работает. Потому что она базировалась на простой реализации: есть основная очередь событий агента, заявки из нее извлекаются и, если агент не заинтересован в их обработке прямо сейчас, перемещаются во вспомогательную очередь отложенных заявок. Когда агент меняет свое состояние, содержимое очереди отложенных заявок перемещается в начало основной очереди заявок агента.

Но в примитивной реализации это приведет к тому, что агенты A1 и A2 будут работать вот таким образом: A1(m1)+A2(m1), A1(k1)+A2(k1), A1(m2), A1(m3), A2(m2), A2(m3). Объясняется это том, что в момент A1(k1) отложенные заявки A1(m2), A1(m3) будут перемещены из вспомогательной очереди A1 в основную. Потом тоже самое произойдет и с A2(m2) и A2(m3). Но логическая связь между A1(m2) и A2(m2) уже будет потеряна.

Чтобы исправить эту проблему нужно сохранять в заявках их глобальный порядок следования (например, значение глобального последовательно возрастающего счетчика). А при перемещении заявок из вспомогательной очереди в основную проводить их переупорядочение с учетом порядка следования заявок других агентов. Т.е. когда срабатывают события A1(k1) и A2(k1) рабочая нить должна из двух локальных последовательностей (A1(m2), A1(m3)) и (A2(m2), A2(m3)) построить вот такую правильную глобальную последовательность вызовов A1(m2), A2(m2), A1(m3) и A2(m3).

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

А если бы я делал это в коммерческом проекте (скажем, реализовывал важную новую фичу, обещанную заказчику), все это дело нужно было бы уместить в сроки, которые бы были озвучены две недели назад и взяты, в буквальном смысле, "с потолка".

Отправить комментарий