読者です 読者をやめる 読者になる 読者になる

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

さて、今日もtokyocljな訳ですが、とりあえずあれからちょろちょろ調べてたあれやこれやを整理してみます。

STM実装はMVCCをベースとして実装されており、履歴管理はsnapshot isolationを使用しています。

The Clojure STM uses multiversion concurrency control with adaptive history queues for snapshot isolation, and provides a distinct commute operation.

http://clojure.org/refs


snapshot isolationはoracleのserializable分離レベルの実装でも使ってるらしいです。

snapshot isolation is a guarantee that all reads made in a transaction will see a consistent snapshot of the database, and the transaction itself will successfully commit only if no updates it has made conflict with any concurrent updates made since that snapshot.

If built on multiversion concurrency control, snapshot isolation allows transactions to proceed without worrying about concurrent operations, and more importantly without needing to re-verify all read operations when the transaction finally commits. The only information that must be stored during the transaction is a list of updates made, which can be scanned for conflicts fairly easily before being committed.

http://en.wikipedia.org/wiki/Snapshot_isolation

まあそんなかんじ。ClojureはMVCCをつかってるので、トランザクションがうまくいく判定が正確にできれば、成功したトランザクションでの値をコミットしにいけばいいという。身もふたもない。


あとは本家で紹介されている特徴。

All reads of Refs will see a consistent snapshot of the 'Ref world' as of the starting point of the transaction (its 'read point'). The transaction will see any changes it has made. This is called the in-transaction-value.

http://clojure.org/refs

すべてのrefはトランザクション開始時点でのスナップショットをみる。これがstarting pointであり、read pointとして管理される。トランザクションは同一トランザクション内で変更された値を参照し、これをin-transaction-valueという。

All changes made to Refs during a transaction (via ref-set, alter or commute) will appear to occur at a single point in the 'Ref world' timeline (its 'write point').

http://clojure.org/refs

トランザクション内でのrefに対するすべての変更(ref-set/alter/commuteによるもの)はある時点(write point以降)で発生する。

No changes will have been made by any other transactions to any Refs that have been ref-set/altered/ensured by this transaction.

http://clojure.org/refs

ref-set/altered/ensuredした時点では、他のトランザクションでは値の変更を検知しない。

Changes may have been made by other transactions to any Refs that have been commuted by this transaction. That should be okay since the function applied by commute should be commutative.

http://clojure.org/refs

commuteを使用すると他のトランザクションでの値の変更が行われることがあり、commuteにより適用する関数は実行順序が交換可能であるべき。

Readers and commuters will never block writers, commuters, or other readers.
Writers will never block commuters, or readers.

http://clojure.org/refs

値の読み取りとcommuteによる関数の適用は、値の書き込み、commuteによる関数適用、他のトランザクションでの値の読み取りをブロックしない。値の書き込みは、commuteによる関数適用と値の読み取りをブロックしない(writeは競合するとか素直に書けばいいのにね)。

I/O and other activities with side-effects should be avoided in transactions, since transactions will be retried. The io! macro can be used to prevent the use of an impure function in a transaction.

http://clojure.org/refs

トランザクションは再実行されることがあるため、トランザクション内で副作用とI/Oを伴う操作はさけるべきである。純粋でない関数の実行については、io!マクロを使用することができる。
このio!マクロはトランザクション内で副作用が扱えるマジックかとおもったら、トランザクションが走ってたらIllegalStateにするだけ君でした。そげぶ。

If a constraint on the validity of a value of a Ref that is being changed depends upon the simultaneous value of a Ref that is not being changed, that second Ref can be protected from modification by calling ensure. Refs 'ensured' this way will be protected (item #3), but don't change the world (item #2).

http://clojure.org/refs

同一トランザクションで複数のrefを変更する場合には、ensureによって変更の適用を制御する。というようなことをいってるぽいけど何いってるか正直わかりません。

The Clojure MVCC STM is designed to work with the persistent collections, and it is strongly recommended that you use the Clojure collections as the values of your Refs. Since all work done in an STM transaction is speculative, it is imperative that there be a low cost to making copies and modifications. Persistent collections have free copies (just use the original, it can't be changed), and 'modifications' share structure efficiently. In any case:

http://clojure.org/refs

ClojureのMVCCによるSTMは永続的なコレクションも扱えるようにしてあり、refはClojureのコレクションを使用することを強く推奨する。理由は、すべての作業がトランザクション内で投機的に実行され、コピーと変更のコストは小さくなければならないからである。永続的なコレクションはコピーフリーであり、修正は構造を共有しているため効率的である。

※永続的ななんとかという下りは、プログラミングclojureの128pが参考になります。リストへの値の追加は、すべてのリストを再作成するわけではなく、古いリストと新しい値をくっつけたオブジェクトで構成されたりします。

The values placed in Refs must be, or be considered, immutable!! Otherwise, Clojure can't help you.

http://clojure.org/refs

refの値はimuutableでなければならない。


あと、haskellのSTM。

Control.Concurrent.STM.TArray
Control.Concurrent.STM.TChan
Control.Concurrent.STM.TMVar
Control.Concurrent.STM.TVar
Control.Monad.STM

http://hackage.haskell.org/package/stm

Arrayは配列、ChanはChannnel、TMVarはなにそれ?、Varは変数(変数とかいうとおこられると思うけど)。Channelも気になる。と、頭のTはTransactionalの略っぽいですね。

ClojureのTValも、たぶんTransactional Valueか、in-transaction-valueみたいなものの略なんでしょう。なんでこんな中途半端に略すのかは個人的には疑問です。

HaskellのSTMは、このへんが根拠っぽいです。
http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/index.htm

これはおもしろそう。そういえば、haskell hack-a-thonとかないのかな。


あとは、ClojureのMLに書いてあったことなど。

I've added io! blocks, which will throw an exception when run in a
transaction:

http://groups.google.com/group/clojure/browse_thread/thread/25145e80e3b0a211/5234a7a27e1d047a?lnk=gst&q=Dave+Griffith#5234a7a27e1d047a

io!のはなし。まあマクロとかサポートしているので、どこかでioが発生するようなあれやこれやがトランザクション内で呼ばれるかもしれないので、こういうのが必要なのかもしれません。

It seems like it should be possible to extend the STM semantics of
Clojure to allow this sort of thing to Just Work. From the user point
of view, one would call dosync-external, rather than dosync, and pass
it an external (JTA?) transaction manager along with the operations to
be executed.

http://groups.google.com/group/clojure/browse_thread/thread/aa22a709501a64ac

STMのセマンティクスでJTAとかの外部のトランザクションまで扱おうとする試み。

1. Normal transactions
A successful commit on an external transaction can be (and usually is)
a side-effect, so it breaks the assumption that transactional
operations are side-effect free and can be retried by the STM.

Maybe if the external commit can be delayed until the end of the transaction, when it is certain that the in-memory operations succeeded, it could work. I think this is the most promising way of implementing this.

http://groups.google.com/group/clojure/browse_thread/thread/aa22a709501a64ac

DBの普通のトランザクションを扱おうとすると副作用が発生するので、STMのトランザクション内では扱えない。STMのトランザクションを合成するという手もあるけど。。
まあ、インメモリの処理が終わった後に外部txをコミットするならいいんじゃないの、という感じ。

2. XA transactions
If Clojure's STM works similar to an XA transaction, it would still be
difficult to delegate the coordination to a JTA transaction manager.
XA-capable resources MUST have stable storage for crash recovery,
which definitely isn't the case (and also wouldn't make sense) with
the STM.

http://groups.google.com/group/clojure/browse_thread/thread/aa22a709501a64ac

XAはJTAとマジ連携なので、永続化いるしSTMでやるのはだめ。STMはACIまでやるけどDは保証してないし、再実行のからみでDは保証できない。ようするにSTM-XAは無理。そげぶ。

As near as I can tell, the current STM
implementation commits by
1) locking all the written refs
2) checking if the writes of the transactions are non-conflicting. If
any conflict, retry the whole transaction
3) then writing to the refs
4) unlocking the refs

The idea is that between 3) and 4) you would attempt to commit any
external transactions. If that requires a rollback, rollback the in-
memory transaction as well. Similarly, if there are any conflicts in
2), rollback any external transactions.

http://groups.google.com/group/clojure/browse_thread/thread/aa22a709501a64ac

ロックの解放前に外部のトランザクションをコミットしにいく実装。「まあ、インメモリの処理が終わった後に外部txをコミットするならいいんじゃないの、という感じ。」の実装ですね。いちおうパッチもあったりとか 。

コードベース古いのでなんともですが、外部txの実行に失敗したあとにSTMをロールバックできるタイミングなのかとか結構疑問だったりします(というか、できてないっぽい)。


結局全体がトランザクショナルになる挙動にはできないかなという感じ。トランザクションのステータスをCOMMITEDにする直前に外部txをコミット→ステータスの変更、だと、STMがロールバックされるかもだし、ステータスの変更→トランザクションのステータスをCOMMITEDにする直前に外部txをコミットだと、外部txがロールバックされるかも。

STMでステータスをもって2pcとかになるのでしょうか?

If you want to do I/O from a transaction, just use an agent to do the
I/O.

http://groups.google.com/group/clojure/browse_thread/thread/d967171ed4b0f20c/9f55aead761f3e99?lnk=gst&q=STM#9f55aead761f3e99

I/Oしたいならagentつかえばいいじゃない。

Potentially interesting library for clojurians. Java STM
implementation: http://www.deucestm.org/

http://groups.google.com/group/clojure/browse_thread/thread/417ba3d62f5137e4/092c3240c4bfdc0a?lnk=gst&q=STM#092c3240c4bfdc0a

javaのSTM実装もあるよ、的なはなし。何で盛り上がってるのかはみてない。

Reading into the Java code, ensure puts a lock on the ref, which, once
in place, guarantees that the transaction doing the ensuring has an
exclusive right to modify the ref until it commits / retries... or
something, my Java-fu is still nothing to boast about, regrettably.
At any rate, my current understanding is that, in Garth's example, the
ensure gives (alter r f) all the time it needs to modify r's value
while putting all other transactions which attempt to modify r on
hold. alter, by itself, never interferes with background transactions;
should something disappear from under its feet, it expects to be
retried.

http://groups.google.com/group/clojure/browse_thread/thread/7edd12e22eb120ea/207888a0d12ade38?lnk=gst&q=STM#207888a0d12ade38

競合が発生しすぎるならensureしてロックをとってしまえばいいっぽい。まあ理屈ではある。

The Clojure STM is just a Java library. You could use clojure.lang.Ref
and LockingTransaction directly from Java/Scala/etc.
runInTransaction takes a Callable, and the values placed in Refs can
be anything immutable.

http://groups.google.com/group/clojure/browse_thread/thread/9d4fbd65d85f8e2e/fa65cb90dabf2df0?lnk=gst&q=STM#fa65cb90dabf2df0

他の言語でも使えないのか的な。clojureのjarに依存していいならjavaで実装してるだけなので、使えるっちゃ使える。どこかでrubyで使えるようにしてた人がいました。


http://groups.google.com/group/clojure/browse_thread/thread/5c7a962cc72c1fe7/f951b5c75a5c2fb7?lnk=gst&q=STM#f951b5c75a5c2fb7
http://groups.google.com/group/clojure/browse_thread/thread/82497ffad880de2b/5bd6282438e63e04?lnk=gst&q=STM#5bd6282438e63e04
あとなんか面白かったので。

You can find the article at http://ociweb.com/mark/stm/article.html.

http://groups.google.com/group/clojure/browse_thread/thread/d0a2b88b0db8e3f9/5e214fd80d91786f?lnk=gst&q=STM#5e214fd80d91786f

にたようなことをしてるひとがいたり。