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

  • Article

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

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

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

Проверка целостности справочника

(реализована с использованием блокировок)

Проверка целостности справочника

(реализована при помощи STM)

 
 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