суббота, 8 августа 2015 г.

[prog.sobjectizer] Неоднозначные стороны приоритетов событий

Под катом несколько соображений на тему приоритетной обработки событий агентами (сообщений акторами, если оставаться в рамках actor model). Надеюсь, эти соображения будут интересны не только тем, кто следит за развитием SObjectizer, но тем, кто вообще интересуется построением систем на основе очередей сообщений.

Штука нулевая: кто определяет приоритет события? Возможно, самый основополагающий вопрос. Если не ошибаюсь, в C++ Actor Framework приоритет сообщения определяет отправитель. Тогда как в SObjectizer приоритет определяется получателем.

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

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

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

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

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

Особенно важным это отличие окажется, если агенты-датчики рассылают информацию о своих измерениях широковещательно. Т.е. когда отправитель не знает кто будет получателем отсылаемых сообщений. У сообщения с текущим значением температуры может быть несколько получателей: один запишет значение в БД, второй отрисует кривую на графике, третий учтет это значение при формировании карты распределения температур, четвертый проверит попадание значения в разрешенный диапазон.

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

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


Штука первая: важность контекста обработчика события. Т.е. речь идет о том, используется ли для всех обработки событий с любым приоритетом один и тот же рабочий контекст (рабочая нить) или же под каждый приоритет выделяется свой собственный контекст (отдельная нить под каждый приоритет).

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

В SObjectizer приоритет события обозначает порядок обработки событий. События с более высоким приоритетом обрабатываются до событий с низким приоритетом. Т.е. пока есть высокоприоритетные события, дело до низкоприоритетных может не дойти вообще.

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

В этом случае есть возможность гарантировать, что обработка события с приоритетом 0 (низшим) произойдет после обработки события с приоритетом 1 (более высоким). Если же рабочих контекстов несколько, скажем, пул потоков, то тут возможны забавные варианты. Например, в очереди стоит две заявки: с приоритетом 1 и приоритетом 0. Первая нить берет заявку с приоритетом 1 и... И засыпает. Зато вторая нить берет оставшуюся заявку с приоритетом 0 и успешно ее обрабатывает. После чего просыпается первая нить и вызывает обработчик заявки с приоритетом 1. Еще веселее ситуация будет на многоядерных системах, где нити из пула смогут работать на разных ядрах. Особенно на хитрых многоядерных системах, вроде ARM.big.LITTLE, где разные ядра обладают разной производительностью.

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

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

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

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

Зато такой подход позволяет оперативно реагировать на поступление высокоприоритетных заявок. Допустим, сейчас обрабатывается заявка с приоритетом 0 на своей рабочей нити. Тут приходит заявка с приоритетом 1. Можно приостановить работу нити с приоритетом 0 и "немедленно" начать обслуживать заявку с приоритетом 1 на другой рабочей нити. Если затем приходит заявка с приоритетом 2, то нить с приоритетом 1 останавливается и т.д.

Самым интересным здесь будет вопрос о том, а как быть, если при обработке событий с разными приоритетами потребуется доступ к общим данным?

Взять, например, попытку решения проблемы overload control посредством приоритетов. Допустим, есть агент, который обрабатывает запросы. Когда очередь запросов к этому агенту превышает некоторый порог, агент должен начать обрабатывать запросы иначе. Например, если на каждый запрос агент генерирует картинку (кадр), то при увеличении потока запросов можно снизить качество генерируемой картинки (т.е. уменьшить время формирования кадров за счет более грубых алгоритмов).

Пусть обычная обработка запросов агентом выполняется на приоритете 0, а обработка сигнала о превышении порога размера очереди -- на приоритете 1. Когда приходит событие с приоритетом 1, нить обслуживания событий с приоритетом 0 приостанавливается. В произвольном месте. В каком состоянии находятся внутренности агента в этот момент непонятно. Может быть можно безопасно менять параметры его работы (скажем, уменьшать качество обработки картинки). А может быть и нет.

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

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


Штука вторая: важность пустоты :) В данном случае очереди событий.

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

Предположим, что на некоторой нити T подряд отсылается два сообщения одному и тому же получателю. Первое сообщение приводит к возникновению события с приоритетом 0, второе сообщение -- к событию с приоритетом 1. В каком порядке агент-получатель обработает эти события? А если нить T и есть та самая нить, на которой работает агент-получатель?

Если нить T и нить X, на которой работает получатель, -- это разные нити, то все будет зависеть от того, пуста ли на данный момент очередь событий нити X или нет.

Если очередь событий нити X пуста, то нить X может проснуться сразу же при постановке к ней в очередь первого события, т.е. события с приоритетом 0. Это событие может быть немедленно изъято из очереди заявок и обработано нитью X. Даже еще до того, как на нити T будет возвращено управление из метода send. А может быть и не так. Нить X может не успеть проснуться и нить T поставит в очередь второе событие, с приоритетом 1. Поэтому, если очередь заявок на нити X пуста, то может быть любой порядок обработки: как 1, затем 0, так и 0, а затем 1.

Такая ситуация может доставить немало сюрпризов разработчику. Он может забыть (а то и не знать) про эту особенность и будет рассчитывать, что событие с приоритетом 1 будет обрабатываться до события с приоритетом 0. И, что самое плохое, во многих случаях, т.е. когда очередь заявок не пуста, именно так и будет. Но эпизодически будут происходить ситуации, когда порядок окажется обратным: сначала приоритет 0, затем приоритет 1. Причем это будет зависеть от многих факторов, включая, возможно, и фазу луны :)

Если же нити T и X -- это одна и та же нить, то порядок будет гарантирован: сначала приоритет 1, затем приоритет 0. Это обеспечивается за счет того, что в момент send-а нить X (она же нить T) не может прервать свою работу дабы взять новую заявку из очереди. Пока на нити X (она же T) не завершится текущий обработчик, ничего не произойдет. Поэтому-то заявки в очереди будут упорядочены как положено.

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


Штука третья: взаимодействие 1-to-many (или broadcast).

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

Широковещательная рассылка -- это когда вызывается один-единственный send для сообщения, а доставляется этот экземпляр сразу нескольким получателям. Т.е. один send генерирует несколько событий для целого ряда подписчиков. Причем подписчиков может быть разное количество -- хоть 2, хоть два миллиона. Важно то, что чем больше у сообщения подписчиков, тем вероятнее возникновение проблемы, о которой речь пойдет ниже.

Предположим, что на сообщение M подписано три агента: A2, A1 и A0. Агент A2 обрабатывает сообщение M с приоритетом 2, агент A1 -- с приоритетом 1, а агент A0, соответственно, с приоритетом 0. Все три агента работают на одной общей рабочей нити X. Широковещательная отсылка M производится на какой-то другой нити T.

Вопрос: при отсылке M с нити T, в каком порядке будут запущены агенты на нити X?

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

Пусть очередь заявок на нити X пуста. В списке подписчиков для M агенты расположены следующим образом: А0, A1 и A2. Это означает, что сначала в очередь нити X будет поставлена заявка для агента A0, потом для агента A1 и лишь затем -- для A2. Т.к. очередь заявок для X была пустой, то самая первая заявка (для A0) может быть взята и обработана сразу же после постановки. Тоже самое может произойти и с заявкой для A1. Поэтому последовательность вызова обработчиков при наивной реализации широковещательной рассылки может шокировать пользователя: может быть как (A0, A1, A2), так и (A1, A0, A2), так и (A0, A2, A1) и т.д.

С другой стороны, если делать широковещательную рассылку устойчивой к данной проблеме (т.е. гарантируется порядок A2, A1, A0), то возникнут некоторые накладные расходы. Т.к. при обработке списка подписчиков нужно будет либо блокировать конкретную рабочую нить до тех пор, пока не будут выставлены заявки для всех получателей сообщения. Либо же в описании подписок нужно будет хранить информацию о приоритетах дабы не зависеть от порядка создания подписок (т.е. для M список подписчиков должен всегда выглядеть как (A2, A1, A0)).

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

Кроме того, если не блокировать рабочие нити до завершения процесса раздачи заявок, то можно получить интересные сценарии. Например, агент A2 во время обработки M отсылает сообщение L агенту A0 (это сообщение так же обрабатывается с нулевым приоритетом). Что может привести, скажем, вот к такой последовательности: (A2(M),A0(L),A1(M),A0(M)). А может и вот к такой: (A2(M),A1(M),A0(L),A0(M)). А может и к такой: (A2(M),A1(M),A0(M),A0(L)). Что, опять же, будет определяться кучей факторов, в том числе и фазой луны :)


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

Комментариев нет: