@m_seki の

I like ruby tooから引っ越し

minrubyにDripをつける

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