Программная модель актеров

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

Во-первых, программисту доступен лишь самый низкий уровень абстракции для общения между параллельно выполняющимися задачами - разделяемое состояние (shared state). В такой модели дополнительно к работе со данными каждая задача должна прилагать усилия по координации этой работы с другими задачами. Главная проблема здесь в том, что программисту необходимо очень детально описать логику работы и координации, что в свою очередь создает семантический разрыв между человеческим и компьютерным представлениями программы. Этот разрыв снижает эффективность выражения мыслей, ухудшает читаемость кода и в итоге приводит к ошибкам в программе (гонки за данными (contentions, races), взаимные блокировки (deadlocks), плохая масштабируемость).

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

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

Модельактеров

В 1973 году Карл Хьюитт с коллегами выпустили работу "A Universal Modular Actor Formalism for Artificial Intelligence", в которой представили резюме многолетней работы исследователей из MIT Artificial Intelligence Laboratory - "a modular ACTOR architecture and definitional method for artificial intelligence that is conceptually based on a single kind of object: actors [or, if you will, virtual processors, activation frames, or streams] ".

В такой архитектуре вычисления реализуются набором актеров, каждый из которых:

1. Имеет идентификатор, по которому он может быть опознан и адресован другими актерами.
2. Умеет общаться с другими актерами путем посылки и получения сообщений, причем для набора отправленных сообщений гарантируется только сам факт их доставки адресатам, но не порядок их получения.
3. Реализует свое поведение в реакциях на поступающие сообщения.
4. Имеет недоступное для внешнего мира состояние, которое может влиять на его поведение.
5. В ответ на некоторое сообщение может выполнить произвольную комбинацию следующих действий: а) изменить свое состояние, б) изменить логику обработки последующих сообщений, в) послать одно или несколько асинхронных сообщений, г) создать одного или нескольких новых актеров, д) завершить свою работу.

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

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

Практическая реализация

На практике актер реализуется в виде сущности, у которой есть состояние, поведение и почтовый ящик (mailbox) - асинхронная очередь необработанных сообщений (обычно почтовый ящик поддерживается библиотекой исполнения, а программист работает с ним неявно при помощи конструктов посылки и получения сообщений - в некоторых языках даже есть специальные операторы send и receive).

Программа в модели актеров представляется в виде набора параллельно работающих сущностей. Так как потенциально таких сущностей может быть очень много, то используются техники планирования на пользовательском уровне (user-mode scheduling), которые заключаются в том, что запуском актеров на исполнение управляет не операционная система, а среда исполнения (runtime). В операционных системах Windows такой подход можно реализовать при помощи файберов и UMS API.

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

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

1. Сопоставление с шаблоном (pattern matching) для удобной фильтрации сообщений.
2. Объявление собственных операторов для наглядной записи шаблонов коммуникации между актерами (например, в F# можно определить операторы "<--" и "<->" для, соответственно, посылки сообщения и посылки с последующим ожиданием ответа).
3. Поддержку сопрограмм для облегчения реализации планировщика (например, в C# можно использовать операторы yield return и yield break для возвращения управления планировщику с возможностью последующего возобновления исполнения с места остановки).
4. Наличие асинхронных API типичных операций вроде работы с файлами и сетью для предотвращения блокировки всей системы одним-единственным актером, ожидающим результата длительного синхронного вызова.

На платформе .NET преимуществами модели актеров можно воспользоваться при помощи специального языка программирования Axum, а также на привычных C# и F# (в случае F# будет гораздо меньше синтаксического шума, который прячется за встроенными в язык монадами и сопоставлению по шаблону).

Пример использования

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

Аукцион - типичное решение

Одним из типичных подходов к решению этой задачи будет разработка клиент-серверного приложения при помощи стандартного стека средств платформы .NET - WPF на клиентской стороне, LINQ to SQL/Entity Framework на стороне сервера и WCF для общения между компонентами приложения. Рассмотрим типичную реализацию сервера, заострив внимание на пропускной способности решения и абстрагировавшись от других деталей, например, от авторизации/аутентификации. Серверный API выражается двумя методами - Lot[] GetAll(), bool Bid(Guid lotId, decimal amount). Метод GetAll обращается к базе данных и выбирает оттуда все записи в таблице Lot, при помощи OR/M средства преобразуя их в объекты и отправляя клиенту. Метод Bid запрашивает текущую ставку на лот с идентификатором lotId у базы данных и, если ставка меньше, чем предложенная пользователем, метод обновляет поле highestBid в записи лота и сохраняет изменения в базу.

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

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

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

Аукцион - решение с помощью актеров

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

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

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

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

Заключение

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

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

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

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

Полезныематериалы ( наанглийском )

1. "Axum – Introduction and Ping Pong Example", Matthew Podwysocki, 2009

2. "Axum – Ping Pong with Dataflow Networks", Matthew Podwysocki, 2009

3. "F# Actors Revisited", Matthew Podwysocki, 2009

4. "Pondering Axum + F#", Matthew Podwysocki, 2009

5. "Actors in F# – The Bounded Buffer Problem", Matthew Podwysocki, 2009

6. "We haven’t forgotten about other models – honest!", Josh Phillips, Axum development team, 2009

7. "Actors that Unify Threads and Events", Philipp Haller and Martin Odersky, 2007

8. "Concurrency in Erlang & Scala: The Actor Model", Ruben Vermeersch, 2009

9. "Message Passing Conccurrency (Actor Model) in Python", "Valued Lessons" blog, 2008