Русский блог по разработке для HPC

Транзакционная память – вторая часть

В прошлом посте мы рассмотрели концепцию транзакционной памяти - средство высокоуровневой организации работы параллельно выполняющихся задач. Рассмотрев основы операционной семантики, во многом совпадающие с семантикой транзакций, мы не упомянули несколько интересных расширений, предложенных в работе Composable Memory Transactions и воплощенных в языке Concurrent Haskell. О них и пойдет речь сегодня.

Оператор retry

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

Одним из первых предложений в этом направлении было введение условных критических областей (conditional critical regions, CCR) - аннотация транзакций некоторым условием, без правдивости которого транзакция не начинает выполнение. Этот подход работает, но не очень изящен, ибо требует создания новой транзакции даже тогда, когда транзакция уже запущена - то есть, только ради того, чтобы выразить семантику условного ожидания.

Современный взгляд на решение этой проблемы заключается в введении оператора retry, который сигнализирует о необходимости перезапуска транзакции - комбинация этого оператора с условным оператором предоставляет конструкт ожидания некоторого события и во многих случаях делает явную сигнализацию события избыточной. Ниже приведено сравнение реализаций блокирующей коллекции ограниченной емкости, аналогичной коллекции BlockingCollection<T> из .NET Framework 4.0 (реализация, основанная на примитивах синхронизации намеренно упрощена в целях краткости).

public class BlockingCollection<T>

{

    private Object _lock = new Object();

    public void Put(T item)

    {

        while (Monitor.Wait(_lock, Timeout.Inifinite))

        {

            try 

            {

                Monitor.Enter(_lock);

                if (_impl.Count == _maxSize) continue;

                _impl.Enqueue(item);

            }

            finally

            {

                Monitor.Pulse(_lock);

            }

        } 

    }

    public T Take()

    {

        while (Monitor.Wait(_lock, Timeout.Inifinite))

        {

            try 

            {

                Monitor.Enter(_lock);

                if (_impl.Count == 0) continue;

                return _impl.Dequeue();

            }

            finally

            {

                Monitor.Pulse(_lock);

            }

        }        

    }

}

public class BlockingCollection<T>

{

    public void Put(T item)

    {

        atomic

        {

            if (_impl.Count == _maxSize) retry;

            _impl.Enqueue(item);

        }

    }

    public T Take()

    {

        atomic

        {

            if (_impl.Count == 0) retry;

            return _impl.Dequeue();

        }

    }

}

Важно отметить, что реализация оператора retry совсем не обязана в цикле перезапускать транзакцию, занимая процессорное время и впустую растрачивая энергию - для корректной работы достаточно перезапускать транзакцию только лишь в случае, когда один из элементов данных, прочитанных транзакцией до выполнения retry, изменился. Например, для метода Take в примере выше система исполнения, обнаружив, что поток вызвал retry, приостановит его до того момента, пока не изменится ссылка на объект _impl или поле Count объекта _impl (это возможно, так как типичная реализация STM контролирует все операции с данными приложения - см. раздел "Детали реализации" предыдущего поста).

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

Комбинатор orElse

В дополнении к оператору retry, который позволяет последовательно комбинировать блокирующие транзакции (например, два подряд идущих вызова Take, которые поочередно получают элементы из различных коллекций), можно ввести оператор orElse, который позволяет комбинировать альтернативные транзакции.

Этот бинарный оператор вначале выполняет транзакцию в левой части. При успешном завершении левой части комбинатор завершает свою работу, а в случае, если эта транзакция вызвала retry, то вместо обычного ожидания она будет отменена, и будет запущена транзакция в правой части. В случае вызова retry и транзакцией в правой части, retry распространится выше по дереву транзакций. Продолжая аналогию - если retry можно рассматривать как выброс исключения, то orElse представляет собой нечто вроде блока catch (с поправкой на то, что и retry, и orElse могут обрабатываются отложенно).

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

public bool NonBlockingTake(out T item)

{

    atomic

    {

        item = Take();

        return true; 

    }

    ||

    atomic

    {

        item = null;

        return false;

    }

}

Если в очереди есть элементы, то этот метод работает предсказуемо - возвращает последний элемент в out-параметре. Если же в очереди нет элементов, то транзакция, объявленная в методе Take, выполнит оператор retry, который распространится и на родительскую транзакцию, объявленную в методе NonBlockingTake, в результате чего будет выполнена правая часть комбинатора orElse и будет возвращен false.

Транзакционная память – первая часть

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

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

Как уже обсуждалось ранее, традиционная модель параллельного программирования слишком низкоуровнева, чтобы быть удобной, поэтому рассмотрим еще одну альтернативу - программную транзакционную память (software transactional memory, STM), которую далее будем называть просто "транзакционная память".

Транзакционная память

В системах управления базами данных транзакции издавна служат общепринятым средством организации корректного совместного доступа большого числа задач к разделяемому ресурсу, но применительно к управлению памятью история транзакций начинается с 1986 года, когда Том Найт опубликовал свою работу "An architecture for mostly functional languages". Изначально из-за больших накладных расходов предполагалось реализовывать технику транзакционной памяти при помощи аппаратной поддержки, но, начиная с середины 90-х, активно развивается исследование полностью программных реализаций, о которых мы и поговорим сегодня. За более подробной информацией об аппаратных реализациях транзакционной памяти любознательного читателя мы отправляем к статье исследователей из лаборатории Sun Microsystems: "Early Experience with a Commercial Hardware Transactional Memory Implementation".

Как и в случае с транзакциями СУБД, клиенты, осуществляющие транзакции STM, освобождаются от необходимости явно синхронизировать свою работу с другим задачами в системе. Код, манипулирующий разделяемой памятью, обрамляется в блок atomic {} (или аналогичную конструкцию), а система исполнения обеспечивает свойства ACID - атомарность, согласованность, изоляцию и долговечность (последнее свойство обеспечивается в том смысле, который адекватен работе с оперативной памятью).

Вот как, например, при помощи STM проверяется целостность двунаправленного телефонного справочника, реализованного при помощи двух словарей (с небольшими изменениями пример взят из документа ".NET Framework 4 Beta 1 enabled to use Software Transactional Memory (STM.NET Version 1.0), Programmers’ Guide"):

bool ValidateMapping(string name, string phone) 

{

    bool result1, result2; 

    string name2, phone2; 

    const int MaxOptReadOps = 16; 

    int backoffIterations = 1;

    int v1, v2; 

    int optReadOps = 0;

    while (true) 

    { 

        if (optReadOps <= maxOptReadOps) 

        { 

            // До некоторого порога используем

            // оптимистическую блокировку

            v1 = version; 

            result1 = name2phone.TryGetValue(name, 

                               out outPhone); 

            result2 = phone2name.TryGetValue(phone, 

                               out outName); 

            v2 = version; 

            if( (v1 != v2) || ((v1 & 1) != 0)) 

            { 

                // Кто-то успел обновить словарь

                // Ждем некоторое время

                // перед следующей попыткой

                var t = backoffIterations << optReadOps;

                Thread.SpinWait(t); 

                optReadOps++; 

            } 

            else 

            { 

                break; 

            } 

        } 

        else 

        { 

            // Мы несколько раз пробовали

            // оптимистическую блокировку,

            // но нас все время прерывали

            // Время переключиться в режим

            // пессимистической блокировки

            rwls.EnterReadLock(); 

            try 

            {

                result1 = name2phone.TryGetValue(name, 

                                   out outPhone); 

                result2 = phone2name.TryGetValue(phone, 

                                   out outName); 

            } 

            finally 

            { 

                rwls.ExitReadLock(); 

            } 

            break; 

    } 

    // Проверяем результаты

}

bool ValidateMapping(string name, string phone) 

{

    string outPhone = null; 

    string outName = null; 

    atomic 

    { 

        outPhone = name2phone.TryGetValue(name);

        outName = phone2name.TryGetValue(phone); 

    } 

    // Проверяем результаты

}

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

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

Операционная семантика

Основы операционной семантики транзакционной памяти во многом совпадают с интуитивным представлением о транзакциях, которое можно получить из опыта использования СУБД:

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

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

Детали реализации

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

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

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

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

Проблемы работы с разделяемой памятью

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

Оптимистичность фиксации в STM делает невозможной взаимные блокировки, но допускает возникновение их антиподов - лайвлоков (livelocks). Лайвлоки могут возникать, когда несколько транзакций одновременно меняют один и тот же элемент данных, вследствие того, что многие реализации STM в целях оптимизации задолго до фиксации определяют тот факт, что транзакции конфликтуют и отправляют их на перезапуск. Для разрешения таких ситуаций используются вариации алгоритма экспоненциальных пауз перед повторным запуском (exponential backoff).

Еще один возможный тип проблем совместного доступа к разделяемой памяти, которому подвержены системы STM - инверсия приоритетов (priority inversion). Инверсия приоритетов может возникать из-за предельной оптимистичности алгоритма фиксации, описанного выше. Так, "неудачная" или очень большая задача может быть постоянно отправляема на перезапуск из-за того, что за время каждого ее исполнения находится другая задача, которая успевает поменять используемые исходной задачей данные и зафиксировать свои изменения. Подобные проблемы обычно разрешаются присваиванием задаче ранга, который определяется по эвристической формуле на основе количества неудачных попыток выполнениям и размера задачи. В случае, если ранг превосходит некий заданный порог, выполнение задачи начинает гарантироваться пессимистическими алгоритмами (блокировками).

Недостатки транзакционной памяти

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

STM основана на том, что с любой точки исполнения транзакции могут быть отменены и корректно выполнены заново, то есть STM полагается на отсутствие в транзакциях побочных эффектов. Но, в реальной жизни зачастую приходится сталкиваться с логикой так называемого awkward squad - вводом-выводом, исключениями и так далее. Эта же логика иногда необходима и в транзакциях. Один из вариантов - запретить побочные эффекты внутри транзакций, но он слишком ограничивающий, чтобы удовлетворять все потребности программистов. С другой стороны, хороших альтернатив нет, и есть лишь ряд полумер, каждая из которых требует вмешательства программиста и подходит лишь для конкретного класса ситуаций, но не покрывает все возможные случаи изменчивой логики: 1) отложенные вызовы побочных эффектов, 2) написанные вручную компенсаторы, которые могут отменять результаты побочных эффектов того или иного типа, 3)написанные вручную альтернативы побочным эффектам, выполняемые, когда изменчивая логика вызывается из транзакции.

Далее, так как важный сценарий возможного использования STM - применение к унаследованному коду, встает вопрос о сосуществовании транзакционного и нетранзакционного способов доступа к разделяемой памяти. На обычный код не распространяется слежение системы исполнения STM за памятью, поэтому он легко может нарушить согласованность транзакций. В этом случае, равно как и в предыдущем, запретительные меры слишком строги, чтобы быть практичными, а среди альтернатив нельзя выбрать однозначно хорошую. В качестве одного из решений можно предложить ручную аннотацию критичных фрагментов унаследованного кода (.NET Framework 4 Beta 1 enabled to use Software Transactional Memory (STM.NET Version 1.0) Programmers’ Guide, раздел 6 "Atomic Compatibility Contracts").

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

Непосредственно связана в вопросом производительности проблема гранулярности слежения за данными приложения. Здесь мы имеем типичную дилемму блокировок - слишком мелкозернистые блокировки непрактичны, потому что приводят к большим издержкам, слишком крупнозернистые непрактичны, потому что приводят к ложным конфликтам. Например, рассмотрим подход, выбранный авторами библиотеки STM.NET - структурировать изменения на уровне отдельных объектов (.NET Framework 4 Beta 1 enabled to use Software Transactional Memory (STM.NET Version 1.0) Programmers’ Guide, раздел 8.1 "Consistency of Aborted Transactions"). С одной стороны, он обладает лучшей производительностью по сравнению со слежением за каждым машинным словом, но, с другой стороны, порождает ложные конфликты между транзакциями, которые меняют разные поля одного и того же объекта.

Заключение

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

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

Из практических реализаций STM для платформы .NET можно отметить библиотеку NSTM, требующую явное создание оберток данных приложения, и проект STM.NET, который следит за данными неявно при помощи модифицированных CLR и JIT. Оба эти подхода имеют свои достоинства и недостатки, обсуждение которых выходит за рамки данного поста.

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

1. "Language Support for Lightweight Transactions", Tim Harris, Keir Fraser, 2003

2. "Composable Memory Transactions", Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy, 2006

3. ".NET Framework 4 Beta 1 enabled to use Software Transactional Memory (STM.NET Version 1.0), Programmers’ Guide", The STM.NET Team, Microsoft Research, 2009

4. "Software Transactional Memory: Debunked?", Brandon Werner, 2009

5. "The problem with STM: your languages still suck", Brian Hurt, 2009

6. "Software Transactional Memory Should Not Be Obstruction-Free", Rob Ennals, 2006

7. "Lowering the Overhead of Nonblocking Software Transactional Memory", Virendra J. Marathe et al., 2006

8. "Early Experience with a Commercial Hardware Transactional Memory Implementation", Dave Dice, Yossi Lev, Mark Moir, Dan Nussbaum, 2009

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

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

Во-первых, программисту доступен лишь самый низкий уровень абстракции для общения между параллельно выполняющимися задачами - разделяемое состояние (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

Windows HPC Server 2008 R2 Beta 1 доступен

Новая версия продукта, продолжающего линейку Windows HPC Server , была аннонсирована на конференции Supercomputing 2009. Стать участником программы тестирования и получить всю необходимую информацию о продукте, а также сам продукт можно через сервис Microsoft Connect по этой ссылке.

Улучшения коснулись всех ключевых компонентов системы, но особо хочется отметить очень интересную возможность использовать узлы кластера для вычисления пользовательских (UDF) функций Excel 2010. Документация, а также видео, демонстрирующее  все новые возможности Windows HPC Server 2008 R2 доступны здесь.

Чистота функций

Наряду с функциями высшего порядка еще одной отличительной чертой функционального программирования является трепетное отношение к побочным эффектам (side effects). "Should I be pure or impure?" - этот вопрос волнует не одно поколение функциональных программистов, и сегодня мы рассмотрим аргументы в пользу обеих сторон, а выбор предоставим вам.

Чистота функций (functional purity)

Функция называется чистой (pure), если 1) для одного и того же набора аргументов она всегда возвращает один и тот же результат, 2) единственный результат работы функции - ее возвращаемое значение. Антонимом этого понятия является изменчивость (impurity). Примеры:

• Оператор сложения целых чисел, синус, да и вообще все детерминированные математические функции являются чистыми.
• Функция получения текущего времени, генератор случайных чисел не являются чистыми, так их два последовательных вызова практически всегда возвращают разные значения, нарушая условие №1.
• Любая работа с пользователем и любой ввод-вывод не являются чистыми, так как нарушают условие №2, порождая побочные эффекты.
• Оператор присваивания не является чистым, так как нарушает условие №2, изменяя состояние приложения.

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

Программирование без изменчивости

Дилемма между чистотой и изменчивостью чаще всего возникает тогда, когда между двумя частями алгоритма - P1 и P2 есть зависимость, то есть P2 использует результаты работы P1 (существуют и более сложные случаи зависимостей, но для краткости мы опустим их анализ). Для разрешения такой ситуации императивное программирование предлагает переменные - изменяемое состояние, которое используется в обеих частях алгоритма (mutable shared state). Функциональный подход заключается в выделении зависимой части в отдельную функцию и передаче ей измененного состояния в аргументах (как мы убедились в прошлом посте, благодаря функциональной композиции даже небольшие фрагменты программы можно выносить в независимые, повторно используемые функции).

Рассмотрим пример - наивное сложение чисел некоторого конечного списка. Это итеративный алгоритм, который перебирает список от начала до конца, на каждом шаге накапливая частичную сумму. Очевидно, между соседними итерациями цикла есть зависимость, так как та итерация, которая будет выполняться позже, использует результат работы предыдущей итерации - частичную сумму. Ниже приведены качественно разные варианты реализации алгоритма (если вы не знакомы с F#, то в объеме, необходимом для понимания кода, приведенного ниже, его можно освоить, прочитав ознакомительный пост; реализации приведены лишь с иллюстративной целью - в базовых библиотеках обоих языков есть встроенные функции, которые можно использовать для достижения нужного результата):

int SumAll(IEnumerable<int> list)

{

    var sum = 0;

    foreach (var element in list)

        sum += element;

    return sum;

}

let sumAll list = 

    let rec fold f acc list = 

        match list with

        | h::t -> fold f (f acc h) t

        | [] -> acc

    fold (+) 0 list

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

Полезные свойства чистых программ

Самое важное достоинство чистых программ - то, что их становится возможным анализировать при помощи математического аппарата, то есть выполнять детерминированный анализ и делать 100% верные заключения. Это помогает как человеку (разработчику), так и компьютеру (компилятору, исполнителю).

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

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

Недостатки чистых программ

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

Следующий недостаток непосредственно вытекает из неизменности состояния - массивы и структуры, представляющие сущности предметной области, создаются "на один раз" и, при необходимости быть измененными, пересоздаются заново. Так, например, упоминаемая в одном из предыдущих постов быстрая сортировка на языке Haskell: qsort (x:xs) = qsort(filter (< x) xs) ++ [x] ++ qsort(filter (>= x) xs) требует больше памяти, чем ее in-place эквивалент на языке C. Вот почему так сложилось, что исторически впервые сборщик мусора появился в функциональных языках - в императивных программах объекты обычно долгоживущие, ибо передаются по ссылке, а в функциональных языках большой процент кода обычно написан в чистом стиле (что, как показано выше, подразумевает более частую аллокацию/деаллокацию структур), поэтому явное управление памятью оказывается слишком неудобным.

Чаще всего получается, что чистая реализация алгоритма по крайней мере не уступает императивным эквивалентам по скорости написания и сложности поддержки, но иногда бывает, что императивная версия оказывается удобнее для записи и сопровождения. Эту тему отлично раскрыл Мэтью Подвысоцки в своем посте "Functionally Implementing Intersperse"

Заключение

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

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

Материалы для чтения

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

Работу с данными (функциональные структуры данных, применимость списков, сопоставление с образцом/активные образцы) мы намеренно оставляем за кадром, чтобы не выходить за рамки этого блога, поэтому по этой теме мы лишь дадим лишь ссылки на полезные документы:

1. "Purely Functional Data Structures", Chris Okasaki, 1996

2. "List comprehension", from Wikipedia, the free encyclopedia

3. "Pattern matching", from Wikipedia, the free encyclopedia

4. "Extensible Pattern Matching via a Lightweight Language", Don Syme et al., 2007

Windows HPC Server 2008: обзор управления системой

Иногда наблюдается ситуация, когда у исследователей есть большой интерес к запуску различного рода расчетных задач на Windows HPC Server 2008, но при этом в академических учреждениях отсутствуют специалисты, способные помочь с развертыванием HPC кластера. В этом случае на помощь приходит либо Microsoft, с бесплатными тренингами по развертыванию кластера для своих клиентов, либо, если есть большое желание изучить возможности HPC Server самому в режиме “evaluation”, развертывание происходит своими силами.

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