ノンブロッキングでマルチリーダーでserializableなSTM戦略
前回ノンブロッキングなSTMに付いて説明したのですが、トランザクション中での読み出しに関してはあまりに適当な説明しかしていなかったです。
そこをもう少しまともに説明しようと思います。
読み出しトランザクション?
複数の箇所の読み出しをatomicに行う必要があります。
一番簡単な方法は「その値そのもので上書きしてやる」事で値を変えずに所有権を自分に移す事です。
transactional_object<int> *a,*b; const int *commited_a, *commited_b; status_t my_status = new status_t(ACTIVE); retry: transactional_object<int> *old_a = a, *old_b = b; // aを読む if(*(old_a->owner_) == COMMITTED){ commited_a = old_a->new_; } else if(*old_a->owner_) == ABORT){ commited_a = old_a->old_; } else { assert(*(old_a->owner_) == ACTIVE); cas(&old_a->owner_, ACTIVE, ABORT); // 先行してるトランザクションを殺す goto retry; // 殺すのに成功しても失敗しても非ACTIVEだと思われるので初めから } // 同様にbを読む if(*(old_b->owner_) == COMMITTED){ commited_b = old_b->new_; } else if(*old_b->owner_) == ABORT){ commited_b = old_b->old_; } else { assert(*old_b->owner_) == ACTIVE); cas(&old_b->owner_, ACTIVE, ABORT); // 先行してるトランザクションを殺す goto retry; } { // aにcommited_aを上書き(丸ごとCASして差し替えてるけど) bool result = cas(&a, old_a, new transactional_object<int>(commited_a, new int(*commited_a), my_status); if(result == false) { goto retry; } } { // 同様にbも上書き bool result = cas(&b, old_b, new transactional_object<int>(commited_b, new int(*commited_b), my_status); if(result == false) { goto retry; } } { // commit bool result = cas(my_status, ACTIVE, COMMITTED); if(result == true){ // この瞬間、aとbを自分が所有しているのでcommited_aとcommited_bの値が一貫していると思って良い // 何故なら他のスレッドがaかbを割り込んで書き換えたのならその前に自分がABORTさせられここに至れないはずだから }else{ // 他のスレッドにSATSUGAIされた my_status = new status_t(ACTIVE); goto retry; } }
正直超効率悪いです。
何より酷いのが、これだと複数のスレッドが同時に読み出しに来れないんです。
なぜかというと書き込みの時と同じ作法で所有権をぶん取っちゃってるからですね。
ナイーブな解決策としてもうひとつ挙がるのが「read committedな分離レベルでいいじゃないか」という諦めです。
スレッドがACTIVEな時はoldがcommitedな最新の値なのでそっちを読めばいいので大変楽です。
しかし一貫性については妥協しています
int commited_a = *(a->owner_) == COMMITTED ? *(a->new_) : *(a->old_); int commited_b = *(b->owner_) == COMMITTED ? *(b->new_) : *(b->old_); // この瞬間既にaは別の値になってるかも知れない commited_a; commited_b; // ←これら2つの値が一貫した値である保証はない
読みだした時に別の値になってるというのは悲しい話です。
Lock-basedなSTMなら書き込む対象しかlockせず読み出しはwait-freeなvalidation作業だけで一貫性を保証できるのでマルチリーダーは気楽なのですが*1Non-blockingなSTMで同様の事を成し遂げるのは簡単ではないです。
トランザクションとは何だったのか
ACIDを満たす操作を一瞬で行なったように見せかけるのがトランザクションだというのは学校で習うのですが、それが実際に意味するところを理解してる人はあんまり居ないんじゃないかと思います。トランザクションとは何なのか。
物理的に本当に一瞬で行う事が不可能な事は言うまでもありません。
ロックを取る事で外からみて一瞬で終わったように見せかけている？70点。
一瞬で終わったように見せかけれそうにないならやり直している？75点。
トランザクションのACIDのConsistencyが意味するところ、それはトランザクションの開始と終了までの間で「一瞬でもコミット完了時の瞬間のデータの状態が存在したことを約束する」事なのです。
なのでこのようにスナップショットを取ることが可能です。
a,b,cの値を2回読んで居ますが、ここで2回読み出す値が一致していれば少なくとも黄色い縦線のその一瞬だけは、a,b,cの値が同時に読みだした通りの値であったことを保証できます*2。ロックを取らずとも、値の一致だけでスナップショットを取得できるのです。これも立派な読み出しトランザクション！Kakkoii！！一致しなかったらもう一回やり直せばいいだけです、一致しなかったということは他の誰かが何か変更を加えたという事なので全体としてどこかで進行が起こっているはずです、つまり進行保証があるのでつまりlock-freeです。*3
それをノンブロッキングなSTM中でどう使うかというと、読みだした値全てをread-setとして保管しておき、コミット直前にもう一回read-setが一致している事を確認するだけです。拍子抜けするほど簡単ですね。
緑色がトランザクション中で読んだ値、赤線がトランザクション中で読み書きした値です。
緑色い線は前述の方法でlock-freeなスナップショットを取り、赤線は前回の日記Non-blocking STMについて頑張って説明してみる - くまメモのトランザクションコミットの方法で、ステータスをCASすることで複数のオブジェクトの論理的な最新状態を書き換えています。万一どちらかが失敗した場合はトランザクションを初めからやり直すので、今回は成功する場合だけを考えましょう。
さて問題そうに見えるのが、黄色い縦線(読み出した物のスナップショット)と、オレンジ色い縦線(書き込んだ物のスナップショット)の間にタイムラグが有ることです。このタイムラグがセーフなのか？というのが本日の話題です。
結論から言うと、セーフです。先ほど話したように「一瞬でもコミット完了時の瞬間のデータの状態が存在したことを約束する」事ができれば良いのです。必ずしも物理的にその条件を満たしているべきとは誰も言っていません。黄色い横線の間、自分がabortされない限りは書き込み途中の値は他者から読まれなくて、どの瞬間でどこに何が書かれていても一緒なので、早い話がオレンジ色い縦線は自由に左方向にずらして良いのです。論理的に同じなのです。*4
この図中のオレンジの縦線は、外に対して言い訳する分にはどこにあったことにしてもいいのです。なので論理的に再読み出しによる確認と書き込みのコミットは全く同じ瞬間に行われたということにして外部に対して保証して良いのです。これによって晴れてロックせずに一貫性も一切妥協せず複数スレッドからの読み出しが同時に行なえる事になりました。*5
本当にトランザクションは最高だぜ*6。
