clojureでのref実装について(中編)

全後半で分けようかと思ったのですが、想像していたより複雑な内容なので、tokyoclj3では整理しきれませんでした。ということで、refの内部構造とトランザクションのアボートを考慮しないref-setでのrefのオブジェクトツリーの状態遷移を整理してみます。

次回tokyoclj4あたりで、もう一歩踏み込んでコードを読んでみようかと思います。ポイントを使用した平行性制御についてはまだ完全に整理できていないので、一部説明が逃げ腰です。また、間違いがあればご指摘ください。


僕は構造からつかみにいくタイプなので、関連を整理してクラス図を書いてみました。


ソースにコメントがないので責務を推測します(余談ですが、java.util.concurrent下のコードはコメントが詳しく書いてあったり、実装根拠の論文へのリンクがあったりするので、面白いです)。

◆ Ref
STMのトランザクション内で変更可能な値を表現します。この値の実態のオブジェクトは内部クラスのTValで表現します。

Refは、TValとトランザクション制御のための値を保持します。

トランザクション制御のためにRefが保持する値には、id、history、トランザクションのコミットに失敗した回数、TValの値を読み出すためのロック ReentrantReadWriteLock、自分自身がどのトランザクションで扱われているか識別するための情報 LockingTransaction.Info、があります。

◆ Ref.TVal
refがラップする値を表現します。トランザクションを開始するとこのオブジェクトがトラザクションに対応する値として振る舞います。
値の履歴は循環リストで保持します。この理由はまださっぱりわかってません。

◆ LockingTransaction
トランザクションを表現します。clojureのSTMはトランザクションごとに値をコピーする実装であり、トランザクションで扱える値のコピーを保持します。

トランザクションはポイントと開始時間、トランザクションローカルな値のコピーを保持し、平行性制御に使用します。

ポイントはいくつか種類があるのですが、まだよくわかってません。
開始時間は、トランザクションのタイムアウトの制御に使用されます。トランザクションが開始から10000000nano secondを超えている場合、トランザクションはkillされる可能性があります。
トランザクション値のローカルなコピーは、valsです。valsはRefの参照と値のマップです。
その他、sets/commutes/ensuresがあります。setsはトランザクション内で扱うrefの集合です。comutesはcommuteで適用する関数の集合です。ちなみに、alterでの関数適用は即時にref-setに置き換えられるので、ref-setで表現されています。ensuresは、多分commuteするときに読み込みロックをとったオブジェクトを入れておくためで、再実行と関連してトランザクション単位でもってるのではないかと推測しています。

◆ LockingTransaction.Info
トランザクション実行中の情報を保持します。このオブジェクトは、refの更新時にトランザクションがそのrefを占有していることを表現するため、transactionとrefで参照を共有します。

占有時点のポイント、トランザクションの実行状態、ラッチを保持します。

トランザクションが開始された時点のポイントは、平行性制御に使用します。
トランザクションの状態には、running/commiting/retry/killed/commitedがあります。
ラッチは、割り込み、リトライ、停止のイベントが発生した際に、他のトランザクショントランザクションの再開を通知するために使用します。

◆ LockingTransaction.RetryEx
トランザクションを再実行させるためのエラーです。例外がスローされるとトランザクションをアボートする仕組みなので、エラーが発生したら再実行、ということにしているようです。

◆ LockingTransaction.AbortException
トランザクションがアボートされたことを表現する例外です。


では、dosync内でref-setするときの、ref/transactionの状態遷移をみてみます。図は、オブジェクト図のつもりですが、UMLの規約には準拠していません。空気を読んでもらえればと思います。

下記のコードを実行するシナリオで、状態遷移を見ていきます。

(def current-track (ref "initial state of current track"))
(dosync (ref-set current-track "changed"))


状態遷移はざっくり四つに分け、オブジェクト図的なものを書きました。

1. ref生成時
2. ref-set transactionをrun
3. ref-set setの実行後
4. ref-set コミット


LockingTransaction.runInTransactionでは、トランザクション開始→dosync内部のロジックの実行→トランザクションのコミットという流れで処理が実行されます。それぞれ見ていきます。

1. ref生成時

RefとTValのオブジェクトが生成されます。refのポイントは0です。

2. ref-set transactionをrun

トランザクションが生成されます。dosyncマクロでは、LockingTransaction.runInTransactionを呼び出し、この中でトランザクションを生成しています。この時点では、RUNNINGのステータスです。トランザクションのポイントは1です。

3. ref-set setの実行後

ref.setを呼び出すと、変更対象のrefを取得してsetsに加えます。また、この時点でrefのwrite-lockを取得します。refがトランザクションに占有されていることを示すため、infoを共有します。そして、トランザクション内でのみ参照可能な値コピーをvalsに保持します。

4. ref-set コミット

LockingTransaction.runInTransactionでref.setが終わると、トランザクションをcommitしに行きます。このケースでは競合を想定していないので、write-lockを再度取得し、ref.tvalsの値を書き換えます。また、コミットが正常に終了したらstatusをCOMMITEDに書き換え、取得したwrite-lockを解放します。



次回までの課題と疑問も整理します。
・ARef/Fnなどの、clojure全体のオブジェクトモデルを理解しておく必要もありそう。making氏が良さげな資料をもってたので、今度教えてもらう。
・TValのhistoryを循環リストで表現している理由は?
・ポイントにはいろんな種類があるけど、どう使っているのか?read pointなんかはread write lockで代替できるような。
・上記の考え方の根拠はなにか?論文なんかはどこかに転がってないか?
・commuteがによって、isolation levelが大幅に下がることになる様に思えるがが、その理解は正しいか?
・commuteは参照の切り替えではなく関数適用を行うもの。遅延評価のセマンティクスが役に立っているように思うが、そこのところはどうなのか?
・commuteを使用することによってパフォーマンスが向上することは考えられるか?事実上、トランザクションが競合しないのであれば無効なだけか?関数適用の競合が頻発するケースでもcommuteのアプローチではなくserializableな分離レベルを採用すれば再実行が多発することはないのではないか?
・というか、STMのトランザクションに分離レベルという概念はあるのか?
・そもそも、STMのアプローチが有効な領域はあるのか?ユーザーインターフェイスくらい?
haskellでもSTMが実装されているはずだが、その実装との違いは?
clojureのMLとかで聞いてみればいいということにこの時点で気づくなど。


ある程度clojure STMの全体感が整理できたところで、次回からソースを追っかけていきます。