minrubyにDripのSTMぽいやつをつける実験 1
Dripという自分しか使ってないライブラリがあります。追記しかできないストリーム型のストレージで、某所のRWikiの全文検索や画像アップローダーのバックエンドで使われています。
全てのデータには時刻から計算されるユニークな識別子がつき、さらに重複可能なタグ（名前）も設定できます。
タグをキーに見立てると、バージョンつきのキーバリューストアのようにも使えます。
DripはgithubにあるしThe dRuby Bookにもあるので見てね。
アプリケーションがあるキーの値を参照し、計算し、格納するケースを想像してください。計算のために参照した値が、格納するまでに変更されていたとしたら、その計算は無効になってしまいます（というユースケースを妄想しよう！）。
そこでアプリケーションが値を参照する際に、そのバージョン番号をメモしておき、格納するときにそのバージョン番号が最新であるか確認できれば、計算をやり直すことができるはずです。
Dripの書き込みにはwrite_if_latestという変わったメソッドがあります。あるタグの最新のデータの識別子と、引数で与える条件の組みとを比較して、一致したときだけ書き込みが成功するメソッドです。
つまり任意のキーのバージョンをチェックしてから書き込むプリミティブです。バージョンチェックと書き込みはアトミックに行われるので、バージョンチェックと書き込みの間に、別のコンテキストが書き込むことはできません。
Dripのサーバーにはトランザクション的な状態は一切持たずに、似たようなことができるのでお得です。
こんな感じです。（MyDripはDripに入ってるおまけ）
require 'my_drip'
MyDrip.invoke
def root
Root.new
end
class Root
class VersionMismatchError < RuntimeError; end
def initialize
@visited = {}
end
def visited
@visited.collect do |key, age|
[key, age]
end
end
def [](key)
found ,= MyDrip.head(1, key)
age, value, = found
@visited[key] = age || 0
value
end
def []=(key, value)
it = MyDrip.write_if_latest(visited, value, key)
raise(VersionMismatchError) if it.nil?
@visited[key] = it
value
end
end
if __FILE__ == $0
3.times do |n|
Thread.new(n) do |x|
root = Root.new
10.times do
begin
count = root['count'] || 0
sleep(rand * 3)
p [root['count'] = count + 1, x]
rescue
p [:retry, x]
retry
end
end
end
end
gets
end
この仕組みは前からあって意識して書けばうまく機能します。
minrubyに入れる
（ちょっと苦しいんだけど）意識しなくても使えるように考えてみました。minrubyでデータベースの更新をするだけのプログラムを書いたとして、更新に矛盾が起きそうなときはプログラム全体を再起動する、ってことにします。
db = root()
count = db['count'] = db['count'] + 1
p count
たとえばこういうやつ。root()でデータベースのインターフェイスを手に入れて、db['count']の値に+1して保存します。もしも参照したdb['count']が別のプロセスによって変更されていたら、プログラム全体を再起動します。
もとのminrubyインタプリタの最後の方を次のように変更すればできそう。ただし、minrubyで実装されていないrescueやらretryやらがあるので、minruby自身でminrubyを実行することはできなくなります。そこは我慢。
str = minruby_load()
begin
tree = minruby_parse(str)
genv = {
"p" => ["builtin", "p"],
"require" => ["builtin", "require"],
"minruby_parse" => ["builtin", "minruby_parse"],
"minruby_load" => ["builtin", "minruby_load"],
"minruby_call" => ["builtin", "minruby_call"],
"root" => ["builtin", "root"]
}
lenv = {
}
evaluate(tree, genv, lenv)
rescue Root::VersionMismatchError
p :retry
retry
end
なお実行が速過ぎてなかなか「やりなおし」が起こせないので、evaluate()の冒頭でsleepさせることにしました。
def evaluate(tree, genv, lenv)
sleep(rand * 0.3)
case tree[0]
全体のコードはgistにあります。
minruby + STM · GitHub
シェルを駆使して（すみません。コピペしました。もっとうまくかけるはず）同時にたくさんプロセスを起動するとretryする様子が見えます。
$ (ruby -I. stm-interp.rb test-1.rb &) ; (ruby -I. stm-interp.rb test-1.rb&) ;(ruby -I. stm-interp.rb test-1.rb&) ;(ruby -I. stm-interp.rb test-1.rb &) ;(ruby -I. stm-interp.rb test-1.rb &) ;(ruby -I. stm-interp.rb test-1.rb &) ;(ruby -I. stm-interp.rb test-1.rb &) ;(ruby -I. stm-interp.rb test-1.rb&)
$ :retry
:retry
:retry
:retry
:retry
31
30
32
33
:retry
:retry
34
35
36
37
テストプログラムに10回ループしてdb['count']を更新する例があります。これを二つのプロセスで実行すると、矛盾を検知するたびにプログラム全体が再起動されてしまい、10回のループをやり直すので、運が悪いとやり直しが交互に発生してなかなか終われなくなります。賽の河原の石積みを連想させる、ダメなサンプルでした。
gist.github.com
