ソフトウェアトランザクショナルメモリ

計算機科学において、ソフトウェアトランザクショナルメモリ（英: software transactional memory, STM）は、データベーストランザクションに似た並行性制御機構であり、並列計算を行う際の共有メモリへのアクセス法である。この機構はロックベースの同期を用いた並行性制御の代替手段として機能し、ノンブロッキングな方法で実装される物もある。ここでいうトランザクションとは、共有メモリに対する一連の読み出しと書き込みを実行するコードを意味する。論理的にはこれらの読み出しと書き込みは、時間的なある一点で行われ、他のトランザクションからはその間の状態は見えない。トランザクションを行うためにハードウェアにサポートさせるアイデア(ハードウェアトランザクショナルメモリ)は、1986年に Tom Knight により論文と特許として出された。そのアイデアを普及させたのが Maurice Herlihy と J.Eliot B. Moss である。1995年、Nir Shavit と Dan Touitou がこのアイデアをソフトウェアのみで行うトランザクショナルメモリ (STM) に拡張した。STM は近年非常に研究が進み、実用的な実装も進展している。

パフォーマンス

現在のたいていのマルチスレッドアプリケーションでロック技術が使われているのとは異なり、STMは楽観的で、実行中の読み書きを逐一記録し、あるスレッドは他のスレッドが行っていることを考慮せずに、共有メモリに対しての変更を完了する。他の進行中の操作に悪影響を与えない責任を書き込み側に負わせる代わりに、その責任を読み込み側に負わせ、全体のトランザクションが完了した後、読み込み側にアクセス対象のメモリが並行して過去に他のスレッドから変更されていないかを検証させる。この最後の処理、つまりトランザクション中に起きた変更を検証させる処理であるが、この検証により正しいものと確認されたならば、変更は永久なものとして反映される。この処理はコミット (commit) と呼ばれる。また、トランザクションはいつでも中止されることがある（アボートと呼ぶ）。アボートされると、そのトランザクションがそれまでに行った（共有データへの）変更は取り消される（ロールバックされる）。もし、トランザクションが変更が競合したためにコミットできなかったならば、普通トランザクションはアボートされ、成功するまで最初からやり直しする。

この楽観的なアプローチの利点は並列性が向上することである。どのスレッドもリソースにアクセスするために待つ必要がなく、普通は同じロックを使って保護されているひとかたまりのデータ構造に対して、異なるスレッド同士が安全かつ同時にデータ構造内の要素に対してばらばらに変更が可能である。読み出しや変更のたびに複製を作るオーバーヘッドや、トランザクションが失敗した場合にやり直すオーバーヘッドがあるにもかかわらず、たいていの現実にあるプログラムではリソースのコンフリクトはめったに起こらないので、多数のコアを搭載した環境ではロックベースの仕組みで行う以上の良好なパフォーマンスを得られる。

しかし実際には、STM システムも少ないプロセッサ（アプリケーションにもよるが1個から4個）上では細粒度ロックベースのシステムと比較して余分な負荷を受ける。これは主にログ管理に関連するオーバーヘッドとトランザクションを完了する時にかかる時間によるものである。この様な場合でも通常2倍以上遅いわけではないので、STM の概念から得られる利益からするとこのペナルティは正当なものだと、STM 提唱者は考えている。

理論的に（最悪値では）、n個の並列で同時に動作するトランザクションが存在した場合、O(n) のメモリ及びプロセッサ時間を必要とする。実際にはこれらは実装の詳細（オーバーヘッドを避けるのに十分早くトランザクションが失敗するように作られる）によって変化する。しかし、ソフトウェアトランザクショナルメモリよりもロックベースアルゴリズムのほうが理論的に処理時間が短いことがある。

概念的な利点と欠点

パフォーマンス的な利点に加えて、STM は概念的には非常に単純でマルチスレッドプログラムを理解しやすくするので、オブジェクトやモジュールのような高レベルな抽象化を進めることができ、プログラムをよりメンテナンスしやすくできる。ロックベースのプログラミングは実際にはしばしば非常に良く知られた問題にぶつかる。

処理的に離れているもしくはどうみても関連のなさそうな箇所のコードやタスク内の処理がかぶったりすることについて考える必要がある。これは非常に難しくてプログラマに対してエラーを誘発しやすい
デッドロックやライブロック、その他処理を止めてしまうような問題を回避するために、プログラマはなんらかのロックを必要とする。このロック処理はしばしば無意識のうちに強制され誤りに陥りやすい。また、これらの問題が持ち上がった時には、それらを再現したりデバッグしたりするのが実は難しかったりする。
ロックは優先順位の逆転を引き起こす。これは優先度が高いスレッドが必要なリソースにアクセスしたいがために、優先度が低いスレッドに強制的に待たされるという現象である。

対照的にメモリトランザクションの考えは大変シンプルである。なぜなら、それぞれのトランザクションはあたかもシングルスレッドで動作しているかのように見えるからである。デッドロックやライブロックはまったく起きないか外部のトランザクションマネージャーによって制御されるので、プログラマはそのような問題について頭を悩ませる必要はまったくない。優先度逆転については課題として残るが、優先度が高いトランザクションはまだトランザクションが完了していない低い優先度のトランザクションとぶつかって処理が中断することはない。

他方、トランザクションの振る舞いにおいて、失敗したトランザクションを中止するのにも制限を設けたいこともある。たいていのI/O処理を含む、トランザクションがロールバックできない操作である。このような制限は普通実際にはバッファを作ることでやりくりする。このバッファによって、取り消せない操作をキューに入れたり、それらを他のトランザクションとは別にあとで実行したりする。

2005年に、Tim Harris、Simon Marlow、Simon Peyton Jones そして Maurice Herlihy によって STM が Concurrent Haskell 上に構築された。これは任意のアトミックな操作をより大きなアトミックな操作に合成することができる。この役に立つ考えはロックベースプログラミングでは不可能である。以下に筆者の言葉を引用する。

もしかしたら、最も根源的な意見は（中略）ロックベースプログラムは操作を合成できないことでないか。操作をくっ付けると元は正しい操作がうまくいかなくなってしまうかも知れない。例えば、スレッドセーフなハッシュテーブルに挿入と削除をすることを考えてみよう。ここで、アイテムAをテーブルt1から一つ削除し、それをテーブルt2に挿入することを考える。この時、中間の状態(すなわちアイテムAをどちらも含まない状態)は他のスレッドからは見ることができないとする。もしハッシュテーブルの実装者はこの要求を見越すことができなければ、この要求をちゃんと満たす方法はない。端的に言うと、個々に見れば正しい操作（挿入と削除）はより大きな正しい操作に作り直すことはできないのだ。
—Tim Harris et al., "Composable Memory Transactions", Section 2: Background, pg.2

STM においては、この問題は単純に解決できる。あるトランザクション中における2つの操作を単にラップしてアトミックな操作としてくっつけてしまえばよいのである。唯一の突っ込み所としてはこの処理を呼び出す側からははっきりしないことがある所である。つまり、コンポーネントが提供する方法の実装の詳細や、もし操作が失敗した場合に、そのトランザクションが再実行を試みるタイミングである。それに対して、筆者は retry コマンドを提案している。これは、トランザクションが失敗したときに生成されるトランザクションログを使って、どのメモリセルが読み出されたかを決定するものである。そして、これらのメモリセルのうちの一つが変更された時に自動的にトランザクションをリトライする。これは、少なくともある一つの値が変化するまでは、トランザクションの振る舞いは変わらないだろうという考えに拠っている。

筆者はまた、操作を合成するための代替手段を提案している。これは orElse というキーワードである。これは一つのトランザクションが走っていて、そのトランザクションが retry するならば、もう一方が実行されるというものである。もし両方リトライするならば、関連する変更がなされたらすぐに両方ともリトライしようとする。この機能は、POSIXのネットワークで使われる select() 呼び出しの特徴と比較される。orElse を使えば、呼び出し側は複数のイベントのうちどれか一つが変化するのを同時に待つことができる。この機能はまたプログラミングインタフェースを単純化できる。例えば、同期操作および非同期操作を相互に変換する機構を単純に作ることができる。

提案されている言語側のサポート

STM は概念的に単純なため、プログラマは比較的単純な文法で STM を使うことができる。Tim Harris と Keir Fraser は論文"Language Support for Lightweight Transactions"で、古典的な「条件つき排他領域」(conditional critical region, CCR) を使ってトランザクションを表現するアイデアを提示した。CCR の最も単純な形式は、「アトミック・ブロック」というものである。これは論理的には"一瞬"に実行されるコードブロックと考えることができる。

 // Insert a node into a doubly-linked list atomically
 atomic {
     newNode->prev = node;
     newNode->next = node->next;
     node->next->prev = newNode;
     node->next = newNode;
 }

ブロックの最後に到達すると、トランザクションは可能ならコミットし、さもなくばアボートして再実行（リトライ）される。CCR はまたガード条件を設定することを許しており、するべき仕事が生じるまでトランザクションを待たせることができる：

 atomic (queueSize > 0) {
     remove item from queue and use it
 }

ガード条件が満たされていなければ、そのトランザクションは、ガード条件に影響を与えうるコミットが（他のトランザクションにより）なされるまで待たされ、その後再実行される。このように生産者と消費者の間の結びつきを弱くすることで、スレッド間で明示的にシグナルをやりとりする方法に比べてモジュール性が改善される。"Composable Memory Transactions" では、retryコマンドを導入してこれをさらに一歩押し進めている。このコマンドは、トランザクションを（その途中の任意の箇所で）アボートし、その時点までにそのトランザクションによってリードされたいずれかの共有データが変更されるまで待ってから再実行（リトライ）するというものである。例えば...

 atomic {
     if (queueSize > 0) {
         remove item from queue and use it
     } else {
         retry
     }
 }

このように、トランザクション中のあとの段階で動的にリトライできるようにすることで、プログラミングモデルが単純になり、また新しい可能性がひらかれる。

課題の一つとして、例外がトランザクションの内から外へ伝播しようとするときにどのように振舞うべきかという点がある。"Composable Memory Transactions" では、筆者らは Concurrent Haskell では例外は予期せぬエラーを示すのが普通であり、この場合はトランザクションをアボートするのがよいと判断した。その際、例外はトランザクションの中で（リードや領域確保により）得られた情報を持ち出せるとした。これは例外の発生理由の診断に役立つ。ただし、著者らは、他の問題設定（例えば他の言語）においては他に妥当な設計判断がありうることを強調している。

不透明性

楽観的な読み出しを伴うソフトウェアトランザクショナルメモリの実装には一つ問題がある。それは、実行中の（完了していない）トランザクションは、一貫性の破れた状態を読んでしまっていることがあるというものである（つまり、他のトランザクションによる更新の前の値と後の値を混ぜて読んでいることがある）。このようなトランザクションは、たとえatomicブロック内の終端まで処理が進んだとしても必ずアボートされる運命にあるので、トランザクションシステムによって強制される一貫性条件が破られるわけではない。しかし、この仮の矛盾した状態のために、セグメンテーションフォールトやゼロ除算のような致命的な例外(fatal exception) を引き起こしたり、無限ループに陥ってしまうことはありうる。"Language Support for Lightweight Transactions" の図4にある作られた例を示す。

トランザクション A	トランザクション B
atomic { local_x = x; local_y = y; if (local_x != local_y) while (true) { } }	atomic { x++; y++; }

最初に関係 x=y が成り立っていたとすると、上記のどちらのトランザクションもこの関係を崩すことはない（不変条件になっている）。しかし、トランザクション A の処理において、x をトランザクションBによる更新前に読み、一方 y をトランザクションBによる更新後に読み、結果として無限ループに陥るということは起こり得る。これは既に致命的な状態に陥っているにもかかわらずトランザクションが継続されるためゾンビトランザクションとも呼ばれる。この問題へ対策としては、致命的な例外を横取りし、それぞれのトランザクションが正常かどうかを定期的にチェックし、異常ならばトランザクションをアボートするという方法があるが、言語によっては実装も大掛かりになりがちである。

ゾンビトランザクションに対して定期チェックなどを行わず、そもそも腐った値を読み出さない保証の事を不透明性（Opacity）と呼ぶ。不透明性を保証する方法として単純なものにIncremental Validationが挙げられる。これは新しく値を読むたびにこれまでに読んだ値が以前に読んだ値と一致している事を確かめる物である。例えばあるトランザクションの中でA,B,Cの3つの変数を読み出す場合「Aを読む→Bを読む際にAも読んで前回と一致する事を確かめる→Cを読む際にA,Bも読んで前回と一致することを確かめる」という手順を踏むこととなり、読み出し操作は変数の数に対しO(n²)でスケールする。他にグローバルバージョンクロックを用いる手法もある。トランザクションが完了するごとにインクリメントされる共有カウンタを用意しておき、値を読み出す側がカウンタをチェックする事で他のトランザクションによる書き換えを検知する方法である。カウンタの値が増えている場合にIncremental Validationと同様に再チェックを行う手法や、書き換え時のカウンタの値を保護対象のメモリと同時に書き込んでおくことによって、無駄な再チェック無しに値の非一貫性を検知する手法がある。不透明性を保証しているソフトウェアトランザクショナルメモリはこれらの手法を用いる事で非一貫な値を読みそうになった時にアボートする。