habrahabr

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

  • вторник, 6 мая 2014 г. в 03:10:35
http://habrahabr.ru/post/221667/

Определение


Параллельное программирование сложно. При использовании систем с общей памятью не обойтись без синхронизации доступа параллельных процессов/потоков к общему ресурсу (памяти). Для этого используются:
  • блокировки (mutex);
  • алгоритмы без блокировки (lockless, lock-free);
  • транзакционная память.


Транзакционная память — технология синхронизации конкурентных потоков. Она упрощает параллельное программирование, выделяя группы инструкций в атомарные транзакции. Конкурентные потоки работают параллельно1, пока не начинают модифицировать один и тот же участок памяти. К примеру, операции добавления узлов в красно-чёрное дерево (анимация в заголовке) способны работать параллельно в нескольких потоках.
Скрытый текст
/* Move item from one list to another */
int move(list *from, list *to) {
    __transaction_atomic {
        node *n = pop(from);
        push(to, n);
    }
}


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

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

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

Транзакционная память — не серебряная пуля. Есть и минусы:
  • при неправильном использовании возможно падение производительности и некорректная работа;
  • ограниченность применения — в транзакции нельзя выполнять операции, действие от которых невозможно отменить;
  • сложность отладки — поставить breakpoint внутри транзакции невозможно.


Рождение технологии


Транзакции в базах данных существуют уже несколько десятилетий. Впервые идея переноса транзакций из мира баз данных в мир параллельного программирования возникла в 1980-х. Развивали и популяризовали технологию Maurice Herlihy, Ravi Rajwar, Nir Shavit. Первые исследования предлагали аппаратные реализации транзакционной памяти, которым не суждено было родиться ещё 30 лет.
В 1990-х появились первые программные реализации технологии, аппаратные реализации подтянулись к 2000-ым.

Программные реализации (Software Transactional Memory, STM)

Среди множества реализаций программной транзакционной памяти я хотел бы выделить четыре. Примеры доступны на github: JIghtuse/tm-experiments.

Clojure
Clojure — единственный язык, ядро которого поддерживает транзакционную память. Основные конструкции STM: ref (ссылка на данные, через которую данные меняются только в транзакции) и dosync (блок транзакции).

Подход к STM в Clojure называется управлением конкурентным доступом с помощью многоверсионности (MultiVersion Concurrency Control, MVCC): хранятся множественные логические версии данных, используемых в транзакции. В течение транзакции поток наблюдает снимок данных на момент её начала.
Скрытый текст

Диаграмма версий ссылок в транзакции Clojure.

Транзакции 1 и 2 начинаются в одно и то же время, получая одну копию версии ref v0. Внутри транзакций происходит обработка данных, которая меняет значение ref. Первая транзакция заканчивается раньше и выигрывает гонку за обновление ref новым значением. Затем заканчивается вторая транзакция, и её попытка обновить ref проваливается (красная стрелка на диаграмме), поскольку версия ref была не той, которая ожидалась. В этом случае транзакция перезапускается, получая копию новой версии ref. Поскольку ни одна другая транзакция не пытается изменить ref, во второй раз транзакция 2 успешно завершается.
Вычисления в транзакции 3 не меняют значения ref, поэтому перезапуск не вызывается и она успешно завершается.

Рассмотрим пример перевода средств между банковскими аккаунтами:
Скрытый текст
Программа работает в одном потоке, но потокобезопасно.
(def account1 (ref 100))
(def account2 (ref 0))
; для чтения текущего значения 'ref' используется (deref refname):
(deref account1)
100
; @refname - эквивалент (deref refname)
@account2
0

(defn transfer [amount from to]
    (dosync
       (alter from - amount)
       (alter to   + amount)))

(transfer 100 account1 account2)
100

Существуют варианты использования конкурентности, при которых среде позволяется «расслабиться» для достижения дополнительной производительности. К примеру, представьте что вы храните журнал транзакций за день. Порядок транзакций в журнале не важен, если вы знаете, что конечный баланс будет корректным. Если вы получаете два взноса в $100 и $50, очерёдность внесения их в журнал не играет роли. Взнос от двух транзакций коммутативен, и clojure предоставляет конкурентную операцию commute как раз для таких случаев.
Скрытый текст
(defn log-deposit [account amount]
     (dosync
        (println "Depositing $" amount " into account, balance now: "
            (commute account + amount))))

(def myaccount (ref 0))

(log-deposit myaccount 100)
(log-deposit myaccount 50)

; (as good as) equivalent to 

(log-deposit myaccount 50)
(log-deposit myaccount 100)

Haskell

Транзакционная память в Haskell содержится в библиотеке STM, которая входит в Haskell Platform. Некорректное использование транзакционных типов определяется на этапе компиляции программы.

Haskell обладает мощной системой типов. Язык разделяет функции с побочными эффектами и чистые функции. Любое значение типа IO t называется действием. Для выполнения какого-либо действия атомарно в Haskell, действие предваряется словом atomically. Вызов atomically с действием в качестве аргумента даёт две гарантии:
  • атомарность — эффект от atomically act будет виден другим потокам сразу и целиком. Ни один другой поток не способен увидеть состояние внутри атомарного действия, лишь конечное состояние.
  • изоляция — во время вызова atomically act действие act выполняется абсолютно независимо от других потоков. Оно снимает состояние мира при запуске и выполняется в этом состоянии.

atomically имеет тип atomically :: STM a -> IO a. Действие типа STM a — аргумент. Как и действие IO, действие STM имеет побочные эффекты, но их диапазон значительно уже. В основном в действии STM происходит запись или чтение транзакционной переменной TVar a:
  • readTVar :: TVar a -> STM a
  • writeTVar :: TVar a -> a -> STM ()

Рассмотрим пример перевода средств между аккаунтами банка.
Скрытый текст
import System.IO
import Control.Concurrent.STM

-- Система типов защищает от чтения или записи переменные типа TVar вне транзакции
type Account = TVar Int

withdraw :: Account -> Int -> STM ()
withdraw acc amount = do
    bal <- readTVar acc
    writeTVar acc (bal - amount)

deposit :: Account -> Int -> STM ()
deposit acc amount = withdraw acc (- amount)

transfer :: Account -> Account -> Int -> IO ()
-- Перевести ’amount’ с аккаунта ’from’ на аккаунт ’to’
transfer from to amount 
    = atomically (do deposit to amount
                     withdraw from amount)

showAccount :: Account -> IO Int
showAccount acc = atomically (readTVar acc)

main = do
    from <- atomically (newTVar 200)
    to   <- atomically (newTVar 100)
    transfer from to 50
    v1 <- showAccount from
    v2 <- showAccount to
    putStrLn $ (show v1) ++ ", " ++ (show v2)

-- Программа распечатает "150, 150"

Scala

Реализация STM для Scala (ScalaSTM) разрабатывалась под впечатлением от реализаций в Haskell и Clojure. Помимо Scala, ScalaSTM вызывается из Java и Clojure. Реализация используется в популярном фреймворке для написания параллельных программ Akka.
ScalaSTM предоставляет ячейку Ref, изменяемую исключительно внутри транзакции. Структуры данных на основе неизменяемых объектов и Ref используются многими потоками.

Рассмотрим реализацию двусвязного потокобезопасного списка с использованием транзакционной памяти. К сожалению, собрать пример на Scala мне не удалось, оставляю это занятие читателю.
Скрытый текст
Полный пример на github: github.com/nbronson/scala-stm/blob/master/src/test/scala/scala/concurrent/stm/examples/ConcurrentIntList.scala

Для реализации разделяемой структуры указатели на следующий и предыдущий узел делают потокобезопасными. Если существует возможность того, что один поток записывает переменную в то же время, когда другой получает к ней доступ (читает или записывает), то используют Ref. Определим класс для узла списка и инициализируем голову списка. Список кольцевой: при создании указатели головного списка указывают на него же. Эти указатели никогда не равны null.

import scala.concurrent.stm._

class ConcurrentIntList {
  private class Node(val elem: Int, prev0: Node, next0: Node) {
    val isHeader = prev0 == null
    val prev = Ref(if (isHeader) this else prev0)
    val next = Ref(if (isHeader) this else next0)
  }

  private val header = new Node(-1, null, null)

Если x является Ref, то x() получает значение, сохранённое в x, а x() = v задаёт его равным величине v.
Ref читаются и записываются только внутри атомарного блока (транзакции). Это проверяется во время компиляции. Далее демонстрируется использование транзакции.
def addLast(elem: Int) {
    atomic { implicit txn =>
      val p = header.prev()
      val newNode = new Node(elem, p, header)
      p.next() = newNode
      header.prev() = newNode
    }
  }

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

C/C++ (GCC 4.7+)

Начиная с версии 4.7, GCC поддерживает транзакционную память. Реализация представляет собой библиотеку времени выполнения libitm, для компиляции указывается флаг -fgnu-tm (-mrtm, -mhle). Библиотека разрабатывалась с оглядкой на черновик транзакционных конструкций для C++ (предлагается включение в стандарт языка).

Большинство реализаций аппаратной транзакционной памяти используют принцип наибольшего усилия. Поэтому практичные реализации используют объединение технологий аппаратурной и программной транзакционной памяти. Такие системы называют системами «гибридной транзакционной памяти». К ним относится, в частности, реализация GCC.

В язык вводятся ключевые слова:
  • __transaction_atomic { … } — указание, что блок кода — транзакция;
  • __transaction_relaxed { … } — указание, что небезопасный код внутри блока не приводит к побочным эффектам;
  • __transaction_cancel — явная отмена транзакции;
  • attribute((transaction_safe)) — указание транзакционно-безопасной функции;
  • attribute((transaction_pure)) — указание функции без побочных эффектов.


Для демонстрации использования транзакционной памяти в C будем заполнять гистограмму данных в конкурентных потоках.
Скрытый текст
Полная реализация на github: github.com/JIghtuse/tm-experiments/blob/master/histogram/src/hist.c

Используется один блок транзакции на цикл обновления гистограммы. Библиотека времени выполнения (либо аппаратное обеспечение) определит, когда и какие транзакции перезапустить.
#ifdef _USE_TSX
    __transaction_atomic {
#endif
        for (i = 0; i < d->sz; ++i) {
            struct pixel p = d->pixels[i];

            unsigned int luminance = rY * p.red + gY * p.green + bY * p.blue;

#if defined _USE_TSX
            ++histogram[luminance/BORDER];
#elif defined _USE_MUTEX
            pthread_mutex_lock(&mut);
            ++histogram[luminance/BORDER];
            pthread_mutex_unlock(&mut);
#endif
        }
#ifdef _USE_TSX
    }
#endif


Аппаратные реализации (Hardware Transactional Memory, HTM)

Лишь в последнее время начали появляться аппаратные реализации транзакционной памяти.

Sun Rock (SPARC v9) 2007-2008




Микропроцессор Rock от компании Sun Microsystems был первым микропроцессором с аппаратной поддержкой транзакционной памяти. 64-разрядный процессор архитектуры SPARC v9 имел 16 ядер.

В 2007 компания объявила о поддержке технологии. Для функционирования транзакционной памяти были добавлены две новые инструкции chkpt и commit и один новый статусный регистр cps. Инструкция chkpt <fail_pc> использовалась для начала транзакции, а инструкция commit для её завершения. При отмене транзакции происходил переход на <fail_pc>, в это время можно было проверить регистр cps для определения причины отмены. Транзакции прерывались по причинам конфликтов данных, промахов TLB, прерываний, сложных инструкций. Тем не менее, во многих случаях использование транзакционной памяти в процессоре Rock давало преимущества в синхронизации.

В 2008 инженеры Sun представили интерфейс транзакционной памяти и симулятор Adaptive Transactional Memory Test Platform. После покупки компании Sun корпорацией Oracle проект Rock был закрыт: «Этот процессор имел два потрясающих свойства: он был невероятно медленным и потреблял громадное количество энергии. Он был настолько горячим, что им пришлось поставить сверху 12 дюймов охлаждающих вентиляторов, чтобы процессор не перегревался. Было бы безумием продолжать этот проект.»2

IBM BlueGene/Q (PowerPC A2) 2011



Суперкомпьютер Sequoia с архитектурой BlueGene/Q стал первой коммерческой системой с аппаратной поддержкой транзакционной памяти. Технология работает в 32-мегабайтном кэше второго уровня процессора PowerPC A2 (PowerPC BQC 16C). Данные в кэше имеют метку “версия”, и кэш способен хранить несколько версий одних и тех же данных.

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

Технология версионных меток в PowerPC A2 также используется для спекулятивного выполнения. Вместо ожидания новой версии данных поток может выполнить вычисления с имеющимися данными, спекулятивно производя полезную работу. Если данные были такими же, как и после обновления, поток завершает (commit) работу из кэша. Производительность выше: поток выполнил работу до получения финального значения. В противном случае результаты спекулятивной работы отклоняются и поток производит вычисления с корректными значениями.

Поддержка транзакционной памяти — в некотором роде логическое расширение возможности, давно присутствующей в процессорах PowerPC — “load-link/store-conditional”, или LL/SC. LL/SC — примитивная операция, которая может использоваться как строительный блок для всех потокобезопасных конструкций. Первая часть LL/SC — load-link — используется программой для получения данных из памяти. Далее поток изменяет данные и записывает их обратно в память с помощью store-conditional. Команда завершается успешно, если данные не менялись. В противном случае программа повторяет действия с данными с начала.

Транзакционная память — LL/SC на стероидах: потоки выполняют операции LL на множестве различных областей памяти, а операция завершения транзакции атомарно изменяет все области памяти или отменяет транзакцию (как SC).

Ruud Haring, который представил работу IBM по транзакционной памяти на Hot Chips, признался, что при реализации компания столкнулась со множеством нетривиальных проблем. При всей сложности, реализация имеет ограничения: она не предоставляет межпроцессорной поддержки транзакций. Проблема не актуальна для Sequoia и в то же время позволяет оценить выигрыш от использования транзакционной памяти.

IBM zEnterprise EC12 (Z/Architecture) 2012


Первый коммерческий сервер с поддержкой инструкций транзакционной памяти. При использовании транзакционной памяти IBM обнаружила рост производительности в 45% по сравнению с машиной z196 в базе данных DB2 и работах в виртуализированных серверных нагрузках.

IBM Power8 (Power) 2013



Контроллеры памяти Power 8 поддерживают транзакционную память. Поддержка технологии в ядре Linux появилась начиная с версии ядра 3.9.
Информации по HTM в Power8 удалось найти не так много, надеюсь она ещё появится.

Intel Haswell (x86) 2013



В 2012 компания Intel объявила о введении расширений транзакционной синхронизации (Transactional Syncrhonization Extensions, TSX) в набор инструкций x86. Расширения позволяют программистам помечать отдельные участки кода как транзакции.
В 2013 с выходом поколения процессоров Haswell аппаратная поддержка транзакционной памяти впервые становится доступной на потребительском уровне.

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

TSX состоит из двух частей. Аппаратное исключение блокировок (Hardware Lock Elision, HLE) предоставляет простую конвертацию программ на основе блокировок в транзакционные программы, причём полученные программы будут обратно совместимы с существующими процессорами. Ограниченная транзакционная память (Restricted Transactional Memory, RTM) является более полной реализацией транзакционной памяти.

Hardware Lock Elision

HLE слегка модифицирует инструкции для изменения участка памяти. Технология добавляет префиксы — инструкции, не производящие каких-либо действий, но меняющие интерпретацию следующей инструкции — для модификации инструкций взятия и освобождения блокировки (XACQUIRE и XRELEASE соответственно).

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

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

Технология обратно совместима с процессорами без поддержки HTM. Операции по управлению блокировкой остаются, но со специальным префиксом. Процессоры Haswell будут учитывать префикс и использовать транзакционное исполнение вместо манипуляций с блокировками. Любой другой процессор будет игнорировать префикс и просто управлять блокировкой, используя традиционное поведение на основе блокировок. Инструкции XACQUIRE и XRELEASE уже существуют, но не несут какого-либо смысла, пока не используются со специфичными инструкциями.

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

HLE на простом примере
Операционные системы реализуют блокировки в ядре как участки памяти, обычно используя типичный для процессора целый тип. Берущий блокировку поток делает нечто с этим участком памяти, к примеру увеличивает значение с 0 на 1. Для освобождения блокировки применяется обратная операция (к примеру, декремент с 1 до 0). Изменения видимы каждому процессорному ядру и каждому потоку в системе, поэтому другие потоки сразу же определяют, что не могут взять блокировку и должны ждать её освобождения (приобретение значения 0).

С префиксами XACQUIRE/XRELEASE попытка взятия блокировки завершается успешно, и процесс полагает, что блокировка принадлежит ему и работает далее. Однако глобального изменения значения блокировки не происходит. Таким образом, поток с блокировкой будет полагать, что её значение равно 1, а остальные потоки системы будут по-прежнему видеть 0. Это позволяет другим потокам одновременно брать блокировку, и процессор вновь будет им лгать. Поток будет видеть блокировку взятой, а другие потоки так не будут считать.

Такое поведение объясняет название HLE: вместо изменения значения с 0 на 1 и обратно, оно просто остаётся равным 0. “Необязательная” запись исчезла.


Restricted Transactional Memory

RTM требует большего участия: он уходит от обратной совместимости и вводит три новых инструкции. В то время как HLE неявно использует транзакции, позволяя коду на основе блокировок работать параллельно, RTM делает начало, завершение и прерывание транзакций явными. Поток начинает транзакцию инструкцией XBEGIN, предоставляя “запасную” функцию, которая запускается в случае прерывания транзакции. Транзакция завершается инструкцией XEND, при этом процессор проводит транзакцию если не было конфликтов или прерывает её, переходя в запасную функцию. Транзакции явно прерываются в программе инструкцией XABORT.
Благодаря явному использованию границ и “запасному выходу”, RTM позволяет контролировать транзакции полнее, чем HLE. В долгосрочной перспективе RTM упростит реализацию возможностей транзакций.

Выводы


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

Примечания


  1. О разнице понятий «конкурентность» и «параллелизм» грамотно выразился Rob Pike в выступлении "Concurrency is not Parallelism": «Конкурентность — работа с множеством вещей за один раз, параллелизм — выполнение множества вещей за один раз»
  2. Да-да, помимо пачки отличных программных продуктов (OpenSolaris, MySQL, OpenOffice) Oracle забросила и перспективную аппаратную технологию

Источники


Считаете ли вы технологию транзакционной памяти перспективной?

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

Проголосовало 311 человек. Воздержалось 86 человек.

Интересен ли пост, требуется moar?

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

Проголосовал 271 человек. Воздержалось 95 человек.