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

В лексиконе психологов есть два занятных слова — «суксессивный» и «симультанный», производные от английских слов successive и simultaneous (видимо, по каким-то причинам психологам так удобнее). Слова эти используют для обозначения действий, выполняемых последовательно и одновременно соответственно. Употребление этих слов вызывало удивление, а теперь складывается впечатление, что и в профессиональный язык специалистов по компьютерам необходимо ввести нечто подобное для обозначения тех действий, которые прежде всегда выполнялись последовательно, но с появлением многоядерных процессоров их приходится делать одновременно. К числу таких действий относится работа с оперативной памятью. Чтобы обеспечить памяти симультанность, ее можно построить с использованием механизма транзакций.

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

У специалистов по информационным технологиям сложилось вполне устойчивое представление о том, что такое транзакция. В словарях и энциклопедиях транзакции определяются как «группы последовательных операций, образующих логическую единицу работы с данными». Отличительное свойство транзакции, этого уникального элемента информационного обмена, заключается в ее завершенности: она может быть либо успешно выполнена, с соблюдением целостности включенных в нее данных и вне зависимости от других системных транзакций, либо, в любом ином случае, не выполнена вообще. Если случается последнее, транзакция обязана остаться невидимой, она должна уйти «по-английски», незаметно для окружения. Исходя из этих представлений, транзакции наделяют качествами, которые в совокупности обозначают аббревиатурой ACID (Atomicity, Consistency, Isolation, Durability — «неделимость, согласованность, изолированность, устойчивость»). Вот что подразумевают под этими качествами.

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

Сегодня трудно восстановить имя того, кто первым предложил идею транзакции. Однако десятилетиями аппарат транзакций ассоциировался исключительно с системами управления базами данных, которые так и называют — «транзакционные СУБД». Однако идея обмена данными на атомарном уровне и на условиях ACID существенно богаче. По своему потенциалу она гораздо шире и может использоваться и вне контекста баз данных. Среди альтернативных применений транзакционного принципа обмена данными можно упомянуть, например, сформировавшуюся за последние годы новую ветвь в программировании, так называемое «транзакционное программирование», направление, которое признают одним из важнейших в области построения Internet-систем. Технологическую основу для него составляют такие средства, как Microsoft Transaction Server и Microsoft COM+, а также платформа Sun J2EE. По сравнению с традиционными транзакционными системами, где для оркестровки данных используется инструмент Transaction Authority, в транзакционном программировании Web-сервисов в развитие этих принципов был разработан основанный на XML язык Transaction Authority Markup Language (XAML)*.

Существует и еще одно направление, с ним связывают транзакционный принцип обмена данными с оперативной памятью; соответственно его называют транзакционной памятью (Transactional Memory, TM). Транзакционная память служит одним из средств, предназначенных для автоматизации параллельного выполнения потоков команд с соблюдением принципов ACID. Реализация принципов транзакционной памяти может быть чисто программной (Software Transactional Memory, STM), аппаратной (Hardware Transactional Memory, HTM) и комбинированной, сочетающей возможности STM и HTM. Все три решения служат одной цели; вне зависимости от конкретной формы реализации предназначение транзакционной памяти состоит в упрощении работы с параллельными потоками команд, в сокрытии от прикладного программиста сложностей работы с параллельными потоками команд. Транзакционная память служит еще одной оболочкой, отделяющей приложения от «железа».

В основе управления транзакционной памятью лежат два вполне тривиальных по замыслу, но очень непросто реализуемых механизма: управление версиями данных (data versioning) и обнаружение конфликтов (conflict detection). В транзакционной памяти не используются обычные для программирования параллельных вычислений блокировки или маркеры; она целиком и полностью построена по принципу транзакций — «все или ничего». Если транзакцию удается выполнить от начала до конца, то она результативно осуществляется, и в данные Носятся те или иные изменения. Если же в процессе выполнения транзакции возникает конфликт, то в таком случае отрабатывается откат назад, возможные изменения в данных восстанавливаются, и все начинается с начала. Принципиально алгоритм транзакционной памяти похож на метод коллективного доступа с опознаванием несущей и обнаружением коллизий (Carrier Sense, Multiply Access/Collision Detection, CSMA/CD), лежащий в основе сетевой технологии Ethernet. Аналогия интересна тем, что данное допущение только на первый взгляд ведет к снижению производительности; многолетняя практика непрерывного повышения пропускной способности Ethernet доказала обратное.

Допустим, что есть некоторая реализация транзакционной памяти. Тогда, используя ее средства, процедуру копирования из одного массива в другой можно описать одной атомарной операцией:

Subroutine Move (Array A, Array B)
Atomic {
Read X from Array A
Write X to Array B
}

Директива Atomic служит указанием компилятору на то, что процедура должна быть выполнена как одна транзакция. Очевидно, что есть вероятность возникновения конфликтных ситуаций в процессе чтения и записи, особенно, если эти действия могут выполняться параллельно. В случае, если конфликтная ситуация действительно имела место, нужно прервать перепись в массив B, восстановить исходное состояние и выполнить копирование вторично. Общность с алгоритмом CSMA/CD заключается в том, что транзакционный подход изначально оптимистичен, он предполагает удачный исход, но если обнаруживается сбой, то за счет некоторых издержек сбой можно компенсировать. В итоге транзакционная память оказывается жизнеспособнее тех подходов, которые основаны на блокировках или метках. Когда в свое время появилась технология Ethernet, к ней отнеслись со скепсисом. Умозрительно было трудно представить преимущества этой сети; казалось, что допущение коллизий сведет на нет ее преимущества по сравнению с конкурентами, но опасение оказались напрасными, результаты хорошо известны.

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

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

И все же привлекательность идеи ТМ привела к тому, что помимо МТИ она стала предметом исследования в университетах Беркли и Стэндфорда, а летом прошлого года был проведен первый семинар на эту тему, называвшийся TRANSACT: First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing. На семинаре обсуждались как общие вопросы, относящиеся к транзакционной памяти, так и более конкретные: программные и аппаратные подходы, а также языки и инструментальные средства программирования, ориентированные на работу с данным механизмом. Помимо представителей университетов в семинаре участвовали сотрудники исследовательской лаборатории Sun Microsystems. Эта компания, пожалуй, была наиболее активна в продвижении многоядерных процессорных архитектур, появление которых собственно и оказалось главным стимулом к возобновлению интереса к транзакционной модели в приложении к параллельным программам.

TM пока находится на исследовательской стадии, но уже сейчас очевидно — в ближайшее время транзакционная память войдет в число ключевых технологий. В этом мнении убеждает то, что во всех современных языках программирования систем высокопроизводительных вычислений, блокировки заменяются механизмом TM. Сказанное относится, прежде всего, к трем основным проектам «суперкомпьютерных» языков — Fortress от Sun, X10 от IBM и Chapel от Cray. Подходы, основанные на транзакционной памяти, находят свое применение в программировании игровых симуляторов, на конференции 2006 Principles of Programming Languages представители этой индустрии признали, что использование блокировок в их приложениях слишком трудоемко и транзакционная память остается единственной альтернативой для распараллеливания задач, решаемых в реальном времени.

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

Идею аппаратной поддержки транзакционной памяти выдвинул и запатентовал в 1986 году Том Найт. Спустя десять лет Нир Шавит и Дан Тоито, сотрудники университета Тель-Авива, предложили программную реализацию транзакционной памяти. Шавит, позже перешедший на работу в исследовательскую лабораторию Sun, является автором целого ряда публикаций с описанием исследований, связанных с STM.

Итак, одним из основных инструментов STM служит управление версиями данных. Его суть состоит в том, что по мере выполнения транзакции система должна оперировать множеством версий данных. Обновленная версия появляется только после завершения транзакции, тогда эта версия становится доступной на глобальном уровне, но до тех пор должна сохраняться старая версия на случай аварийного прерывания процесса выполнения транзакции. Сохранение версий может осуществляться по-разному, но есть два полюса, на одном из них — «энергичное создание версий» (eager versioning), а на другом — «ленивое создание версий» (lazy versioning). Эти подходы различаются тем, что именно буферизуется в процессе переписи. В первом случае сразу же создается новая версия, а старая сохраняется в буфере; если транзакция проходит успешно, то одновременно с ее окончанием готов результат, а если возникает конфликт, то восстанавливается исходная версия из буфера и транзакция повторяется. Для того чтобы сохранить атомарность, до завершения транзакции механизм «энергичного создания версий» блокирует новую результирующую версию для доступа извне. Во втором случае запись новой версии осуществляется в буфер, поэтому при возникновении конфликтной ситуации достаточно прерваться и вернуться на исходные позиции, такой подход проще, но он очевидно медленнее.

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

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

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

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

Аппаратная поддержка транзакционной памяти

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

HTM — полностью аппаратное решение. В его основе — иерархия кэш-памяти (cache hierarchy) и протокол согласования кэш-памяти (cache coherence protocol); они обеспечивают управление версиями данных и обнаружение конфликтных ситуаций. Средствами HTM просматриваются все обращения на запись и чтение в кэш, выполняемые процессором, обычно дело ограничивается кэшем первого уровня, но возможно их распространение и на низкоуровневые кэши второго и третьего уровней. Чтобы проследить эти обращения, каждая строка данных в кэш-памяти снабжается специальным полем, имеющим значение R или W. Монитор HTM задает эти значения, а когда транзакция завершается, эти поля очищаются.

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

Наконец, в подходе HASTM (hardware-accelerated STM) первичным является режим STM, но часть его функций имеет аппаратную поддержку.

Многоядерные процессоры и закон возрастающей сложности

До настоящего времени мы могли наблюдать непрерывное усложнение процессоров на фоне сохраняющейся простоты памяти. Оперативная память становилась больше и дешевле, но по сути ничего в ней не менялось. Но вот появились многоядерные и многопотоковые процессоры, замечательные тем, что из относительно простых ядер можно собирать высокопроизводительные процессоры. Казалось бы, теперь проблема сложности решена, но, как выяснилось, системная сложность не только не уменьшилась, она увеличилась, при этом просто сместилась из процессоров в память. Оказывается, для того чтобы могла работать сборка из простых процессоров, нужна существенно более сложная память. Возможно, стоит сформулировать еще один эмпирический закон, пусть он, к примеру, звучит так: «Системная сложность постоянно возрастает несмотря на упрощение отдельных компонентов».

* Язык XAML, его связь со стандартом SOAP и его использование с Web-сервисами являются отдельной темой, в данном случае он упомянут для того, чтобы подчеркнуть общность транзакционного принципа обмена данными. — Прим. автора.

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