Non-blocking STMについて頑張って説明してみる

STMはソフトウェアトランザクショナルメモリの略です。
↓とりあえずwikipedia
http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%95%E3%83%88%E3%82%A6%E3%82%A7%E3%82%A2%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B6%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%83%A1%E3%83%A2%E3%83%AA

日本でSTMの話題を検索すると「楽観的ロックでしょ？」といった発言を見かける事が多く、確かに実用的な手法の多くはロックベースだったりしていますが、正直なところロックベースな手法のSTMはデータベースでのトランザクションと似ているフシがあったりしてデータベースに詳しい人からするとそれほど驚くような手法ではない事が多いのです。その一方でノンブロッキング(＝非ロックベース)な物は工夫がいくつも凝らしてあり、眺めて良し愛でて良しの大変エキサイティングな物になっています(パフォーマンス以外)そのあたりを少し書きたいなと思います。

STMって何？

データベースの界隈で使われる「トランザクション」をメモリに適用して並行プログラムを書きやすくしようという研究です。
初めはMaurice Herlihy先生の1993年の論文のハードウェアトランザクショナルメモリ(HTM*1 )が元だったのですが、Nir Shavit先生がそれと同様のセマンティクスをソフトウェアレベルで可能であることを示してから一気に研究が加速しました。lock-freeな論文を出していた方々の最近の研究がソフトウェアトランザクショナルメモリに染まっていて、それほどまでに魅力的なのだなというのが伝わってくると思います。*2
HTMに比べてSTMはハードウェアを取り換えずとも環境に合わせた複数の実装を試すことができ、インタフェース仕様さえ共通なら同一のトランザクションを別のトランザクショナルメモリ実装で走らせることも可能です。またハードウェアに縛られない実装が可能なのでHTMと比べて大きなトランザクションにも向いています。*3
一般にデータベースでのトランザクションはACIDと呼ばれる特性を満たしている必要がありましたが、STMのトランザクションはACIしか満たさない事が普通です。これはD(Durability=永続性)は「いつ電源が落ちても復旧可能」という意味で、そもそも揮発性メモリしか相手にしていないSTMからすると永続化は蚊帳の外の問題だからです。

住み分けはあるの？

STMを分類するなら「ノンブロッキングか否か」「オブジェクトベースかワードベースか」が挙げられると思います。*4

ノンブロッキング

ロックを使うか否かは大事な問題です。ロックを抱えたスレッドがPageFaultなどして数万クロック返ってこないという事態になった際にも全体が停止せずに済みます。端的に言うなら外乱に強くなります。またロックをしない事で優先順位の逆転が起きないのです。火星探査機を実装している方必見ですね。
しかし何でもノンブロッキングにすれば良いかと言うと今度は間接化やメモリ動的確保のオーバーヘッドが大きく性能が出ないのでそこもまた面白い所です。

オブジェクトベースorワードベース

どんな単位でメモリを保護するかというのも重要な問題です。オブジェクトベースなSTMではオブジェクト(というデータの塊)にトランザクション用のメタデータを付加して管理する場合が多いです。C以外の近代のプログラム言語ではオブジェクトに暗黙のメタデータを取り付ける事は一般化しているため、設計側に大きな変更をしなくても実装に追加するだけで自然に対応できる事が見込まれています。またデータに触れる際に一緒にメタデータもキャッシュラインに載る可能性が高いため筋が良さそうに見えます。しかし大きなオブジェクトを一つのトランザクション単位にしてしまうと「オブジェクトの別の場所に触れているので実際に衝突していなかったのに衝突扱いにされた」などという事態に陥りパフォーマンスに無駄が出る場面もあります。またオブジェクトの生存管理もトランザクショナルメモリ側で行う事になるため実装が大きくなりやすいとか。代表例としてはDynamicSTM,OSTM,RSTM,NZTMなどが挙げられます。
ワードベースなトランザクションでは、メモリは普通のメモリとして管理しつつ、そのメモリとは別にメモリのワードごとのメタデータをハッシュテーブルなどに置いて管理します。この方法なら大きなオブジェクトや長い配列の一部に対するアクセスであっても適切に衝突を検知できます。しかしメモリアクセスのたびにハッシュテーブルから引くことになるためパフォーマンスは難しいですし、キャッシュミスも頻発します。WSTMなどがありますが、具体的にはまだ追ってないです…。
どちらを選ぶにも一長一短なので、オブジェクトによってその2種類を使い分けるハイブリッド型のトランザクショナルメモリも有るのですが詳しくは知らないです。これ*5とかこれ*6とか。

どんな所で使われてるの？

既にHaskellやScalaやClojureでは実用的なライブラリが出ているようです。その多くはロックベースな物で、ノンブロッキングな物はあまり第一線では見かけません。前述の通りノンブロッキング化のオーバーヘッドに起因するパフォーマンス低下のせいじゃないかと思います。

ノンブロッキングソフトウェアトランザクショナルメモリ

中でも僕の好きなノンブロッキングなSTMに付いての話をしようと思います。具体的には論文Nonblocking memory management support for dynamic-sized data structuresを。
「ノンブロッキング」が何を意味しているのかの詳細は僕の過去の日記non-blockingの意味するところ - くまメモを見てもらうとして、一言で言うと「obstruction-freeかlock-freeかwait-freeのどれか」という事です。これまでずっとlock-free以上の特性を持ったSTMは無いんじゃないかと思ってたのですがもっと探してみるとwait-freeもどうやら可能そうという事が分かりました。*7

大雑把に言って何を使って何を行うの？

コンピュータの世界の名言に「全ての問題は間接化によって解決する」という物が有ります。ノンブロッキングSTMもその一種でまさに間接参照を用いてブレイクスルーを果たしました。
1ワード幅のCAS命令(LL/SC命令でも可)さえ有ればそれ以上強力な同期命令を必要としないので、早い話が今あなたが使っているCPUで動きます。
それによってどんなプログラムが書けるようになるかというと

atomic {
  if(x == 0){
    y += 1; // この瞬間も x==0であることが保証される
  }
}

のような雰囲気で書けます。複数ヶ所の一括更新が上限なくデッドロックの心配もなく行えます。*8

composable

何よりすごいのはcomposable(組み立て可能)であるという事です。
ちょっとググった所このcomposableについて誤解しているケースもあるので説明します。

ソフトウェアの教科書を読んだことがあれば、LRUキャッシュは双方向リストとハッシュマップを用いて実装できる事は知っていると思います。
ここで、複数のスレッドから並行にアクセス出来るLRUキャッシュを実装する場合を考えましょう。

すぐに思いつくのは普通の教科書的なLRUキャッシュを実装して単一のロックで排他する事です。これでパフォーマンスが要求を満たすならそれで充分です。
しかしパフォーマンスを高めるためにメニーコアのプロセッサの性能を使い切ろうと思った際、細粒度並行LRUキャッシュをフルスクラッチ実装するのはかなりの力量が要求され、デバッグのコストまで考えると挑戦すべきではありません。*9
双方向リストやハッシュマップの細粒度ロックやLock-freeの信頼できる実装が既に有る場合、そちらを流用して実装する事で達成しようとするのはエンジニアとして自然な考えです。

しかし、できません。

シングルスレッドな物で良いなら例えばC++ならstd::listとboost::unordered_mapの組み合わせでLRUキャッシュの実装は可能です。

しかしマルチスレッドになったとたんにそれは不可能になります。並行双方向リストの操作と並行ハッシュマップの操作を同時に行えない以上、2つのデータ構造に対する操作の間にタイムラグが発生するからです。ハッシュマップ側でlistのノードを見つけ、リストにアクセスしようとした途端に他のスレッドによってそのノードがdeleteされるかも知れません。*10
それを回避するために外から2つの操作を別のロックで括ってしまうとそもそも単一のロックで行なう程度の並列性しか得られません。*11

一般に、並行データ構造は組み合わせて使う事ができないのです。これがcomposabilityの欠如と呼ばれる物です。ついでにいうとLock-freeでもできません。これは完璧にソフトウェア工学の敗北です。
しかしSTM実装のハッシュマップと双方向リストならば操作全体をアトミックブロックで囲ってやる事で簡単に組み合わせられます。部品を使いまわしてコードを書ける上にマルチコアの恩恵に与れるのですから革新的ですね。

いいから早く実装を教えてよ

まずソフトウェアトランザクショナルメモリで保護する対象を示します。ただのポインタです。

これを保護するとしてこのような構造を作ります。

C++で書くとこんな感じです。

typedef int status_t;
template<typename T>
struct transactional_object{
  const T* const old_;
  const T* const new_;
  status_t* const owner_;
  transactional_object(const T* o, const T* n, status_t* s)
    :old_(o),new_(n),owner_(s){}
};
transactional_object* obj;

全てconstでガッチガチに固めているところがポイントです。一度作ったらstatusの実体値以外どこも書き換えません。並行処理のコードでよくあるimmutableパターンという奴ですね。volatileにすべきか迷いましたが、簡潔さのため省きます。
このオブジェクトからどう読むかというと、status_tの状態によって切り分けます。オブジェクトとステータスを別に保管するというのはノンブロッキングなトランザクショナルメモリでの頻出パターンです。これからもよく出てきます。
status_tはcommitted, abort, activeの三つのうちどれかの状態を取るので、それぞれの場合をifで切り分ければ良いです。

赤く塗られてるのが最新のコミットされた値です。C++で書くならこんな感じ

static const int COMMITTED=0;
static const int ABORT=1;
static const int  ACTIVE=2;
const T* read_value(const transactional_object* const obj){
  const status owners_status = *(obj->owner);
  if(owners_status == COMMITTED){
    return obj->new_; // COMMITTEDならnew
  }else if(owners_status == ABORT){
    return obj->old_; // ABORTならold
  }else{
    assert(owners_status == ACTIVE);
    /* 戦略によって変わるのでとりあえず割愛 */
  }
}

ここに書き込む際にはtransactional_objectごと新しく作ってCAS*12ですげ替えます。

void write_value(const transactional_object** const target, const T* const old_value, const T* const new_value, status_t owner){
  while(1){
    const transactional_object* old_target = *target;
    const transactional_object* new_object = new transactional_object(old_value, new_value, owner);
    const int result = CAS(target, old_target , new_object);
    if(result){ break; } else { delete new_object; }
  }
}

丸ごと差し替えるわけなので、図に描くとこんな感じです。

古い最新の値をoldに残して最新の値を書き込んでいる所がポイントです。
ここまででルール説明は完了です。後はCASを用いて適切に処理をするだけです。

動き方

ここからこれらのルールを生かしてどのようにトランザクションを実現するのかを説明します。

トランザクションの例として以下のような事例を考えます。典型的な銀行口座の残高移しの例です。

口座AからBに10000移す。残高がマイナスになりそうだったら取引は行わない。

C++でナイーブな物を実装するとして、トランザクション本体はこんな手順で操作を行います。

std::vector<transactional_object<int>*> accouts; // あらかじめ配列の形で保存されているとする
/* 口座A→Bに10000円移す */
const int* const A_account = read_value(accounts[A]);
const int* const B_account = read_value(accounts[B]);

// 自身のステータスを作成
const status_t* my_status = new status_t(ACTIVE);

// Aの口座から10000円引く
const int* const old_A = read_value(old_A_account);
if(old_A < 10000){
  throw AccountException("残高がマイナスです");
}
write_value(&accounts[A], old_A, new int(*old_A - 10000);

// Bの口座に10000円足す
const int* const old_B = read_value(old_B_account);
write_value(&accounts[B], old_B, new int(*old_b + 10000));

// コミットする
const bool result = CAS(my_status, ACTIVE, COMMITTED);

簡単ですね。図に書くならこんな感じです。

実は簡潔に説明しようとして一部エンバグしてますが大筋で大丈夫です。*13
大事なのは、write_valueする際にownerの項が同一のmy_statusを指すように書き換えてやる事です。
これによってmy_statusの1byteの状態の変化によって、同時に何万箇所でも一斉に論理的に書き換わるのです。

my_statusがCommittedになるだけで

逆に、Abortになるだけで

と、遷移します。変えているのはmy_statusの1つだけなのに、赤く塗っている箇所が複数同時に移動しているのです。これがキモです。

もしステータスがActiveだった場合にどうするかというと、一番簡単な解決方法はCASでActive→Abortに持ち込んでやって、その後で作業することです。
これにより多分このアルゴリズムを見た人の9割ぐらいが思う「書き換えた値をコミットするまでの間で誰かに上書きされたりしたらどうするの？」という疑問が解決します。答えは「上書きしにくる誰かは、必ずこっちをAbortさせてから上書きするので自分のコミットが失敗するだけ」となるわけです。

で、多分これをC++で書こうと思うと、read_valueの代わりにoperator*とかoperator Tとか使いたいですし、書き込みの代わりにoperator=とかとかしたいですし、オペレータで実現するとなると引数としてステータス渡せないしスレッドローカルストレージにポインタを置くことになるのかなーとかとか考えているわけです。

発展話題

読み出し問題

読み出ししか行わないトランザクションの場合、読んでるそばから書き変わっていってしまうとトランザクションの意味が無いのでリードロックしたいのですが、ナイーブにやるなら「その値を複製してwrite_value()を呼ぶ」事で可能です。
そんな読み出し如きで所有権を移す真似をするとマルチリーダーできないのですが、実はちょっと工夫すると一貫性を妥協せずに実現可能です。要望が有ったら書きます。

ゾンビトランザクション問題

実は読みだすうちに他のトランザクションによってコミットされた値を時間差で読んでしまう問題があります。矛盾した値を読んだトランザクションは最後のcommit挑戦時にabortするので一貫性の問題は無いのですが、トランザクション最中にそれを検知する努力をしないと無限ループや除算を書かれた場合に思いもよらない事態を引き起こします*14。Dynamic STMの論文ではIncremental Validationが提案されていた気がします。1個新しく読み出すたびに、これまでに読み出した物全てが前回読んだ値と一致する事を確かめる物です。n個読みだすなら内部的にO(n^2)回の読み出し操作を行う事になり大変です。*15

高速化

ちょっと読みたいだけなのに3回(transactional_object, owner_, old_/new_)もポインタを辿らなきゃいけないの馬鹿らしいなというのはみんな考える事のようで場合によってそれが1回になるよう工夫したOSTMや、大体の場合で2回になるよう工夫したRSTMや、競合してない限り1回で行けるNZTMなどなどが出ています。こちらも要望があったら書きます。*16

言語機能

この例示した記法が現実で使い物になるはずもなく、実際にはもっとスマートな見た目になるよう様々な工夫が凝らされます。composabilityを実現するための入れ子トランザクションの実装策はいくつもあり、あまり言語機能に興味のなかった僕はあまり追ってないのですが、一番簡単なのはトランザクション内部でのトランザクションは全て外側のトランザクションの操作として片付けてしまう事です。それを言語機能に手を加えず実現するには僕のC++力ではどうやったらいいか想像付かないので誰かCoolな策を考えてください。*17

応用

僕の修士の研究はこの方法をキーバリューストア上で行うという大変シンプルな物です。シンプル過ぎて類似研究にgkbrする日々ですけれど最近はnewSQLのほうが凄すぎてあまり喜ばれない感ございます。*18

12/2/ 12:49 PG_kuraさんに指摘いただいたところを修正(x==1 → x==0)

*1:Transactional Memory: Architectural Support for Lock-Free Data Structures

*2:僕は若干寂しかったですけれど

*3:HTMのほうはキャッシュラインの反映をどうするかという細かいトランザクションの世界を相手にしています

*4:他にも有りますが調べながら書きます

*5:Making object-based STM practical in unmanaged environments

*6:Automatic data partitioning in software transactional memories

*7:wait-free STMの具体的な実装は知らないのですが、lock-freeなSTMならRingSTMがそれっぽく見える

*8:多分C++でやるとマクロとoperatorの嵐になるんじゃないかと思いますが

*9:多分僕は喜んでやりますが

*10:これ書きながら真剣に考えたら、索引する際にはmap参照→listのポインタ獲得→map参照の順で行い一致した場合のみアクセス可能とし、消す際には必ずmapからの参照を消してからlistから消すようにし、参照をweak_ptrにすればなんとかなるようなならないような…いずれにせよ自明ではないです

*11:外からストライプロックで保護してやるというのも可能ですが、無駄なロックを取ることは避けられません

*12:知らない人は居ないと思いますがcasは「比較→一致した場合に限り代入」を一気に行うCPU命令です。慣例に従いCAS(目的のアドレス, 想定する値, その値だった時に上書きする値)という使い方をします。

*13:write_valueする際にoldの値が最新のoldじゃないとダメなのでリトライするならread_valueからやり直すべきなんだけれど説明するにはせせこましくて

*14:SQL文は多分ファントムリードによる無限ループとか発生し得ないんじゃないかなと思います

*15:最近の論文だと「ヒューリスティックを用いて回避する」とだけ書いてあったりして一体どういうヒューリスティックなのかと問い詰めたい

*16:はてなスター100個ぐらい貰えたら

*17:どんどんスレッドローカルストレージに入れていけばいいのかな…コンパイル時じゃなくて実行時解決

*18:Xeround反則だろ…