Snapshot Isolation のおもちゃ

Snapshot Isolation の提唱元 Berenson 等 A Critique of ANSI SQL Isolation Levels (1995) の定義通りに動く「おもちゃ」を実用性無視で記述するのは割と簡単です。 トランザクションの開始時点でグローバル・データのスナップショットをとりトランザクションのローカル・データにします。 その後、 トランザクションごとにローカル・データを参照・更新していきます。 コミット時にスナップショット作成時点からの編集スクリプトでグローバル・データにパッチを当てます。 パッチ当ては、 楽観的排他制御でおこないます。 つまり、 パッチ当て対象の値をスナップショット作成時点の値から始めて逐一比較していき、 一つでも異なっていると衝突が発生したとして、 パッチを当てる前に戻してトランザクションをアボートします。

例外 Conflict はコミットとロールバック時に発生し、 楽観的排他制御が失敗して衝突が生じていることを表します。

class Conflict < RuntimeError; end

表を一つだけ使うことにします。 表は手抜きでハッシュ・オブジェクトにします。

class Table
  def initialize()
    @global_data = {}
  end

#@<Table#transaction@>
#@<Table#snapshot@>
#@<Table#commit@>
#@<Table#rollback@>
#@<Table#patch@>
#@<Table#synchronize@>
end

マルチ・スレッド対応にするのも簡単ですが、 今回は、 手動でトランザクションの処理の順番を入れ替えてふるまいがどうなるのかを遊ぶ目的で、 シングル・スレッドで記述します。 それでも、 どこにきわどい操作があるのかを示すために、 synchronize のダミーでガードしておくことにします。 些細なことですけど、 本当にガードするときは、 例外でアンロック処理を飛び越さないように、 ensure 節でアンロックするようにしておかないといけません。

#@<Table#synchronize@>=
  def synchronize()
    r = nil
    #begin
    # mutex_lock
    r = yield
    #ensure
    # mutex_unlock
    #end
    r
  end

トランザクションを開始するときは、 表にトランザクション・オブジェクトを作らせます。 以後、 このオブジェクトを介してスナップショットに手を入れていきます。

#@<Table#transaction@>=
  def transaction()
    Transaction.new(self)
  end

トランザクション・オブジェクトは、 グローバル・データのスナップショットを求め、 編集スクリプトのログを空にします。 衝突でアボートしたとき、 トランザクションをその時点のスナップショットで再開させて遊べるようにと、 restart メソッドを用意しておきます。

class Transaction
  def initialize(table)
    @table = table
    @local_data = @log = nil
    restart()
  end

  def restart()
    @local_data = @table.snapshot()
    @log = []
    self
  end

#@<Transaction#fetch, each@>
#@<Transaction#insert, delete, update@>
end

スナップショットの作成は排他的におこなう必要があります。 なので、 実用的な実装では、 スナップショットの作成に排他制御がほぼ不要なデータ構造を採用するのが通例です。 これは、 おもちゃなので、 グローバル・データのコピーを作成します。 浅いコピーなので、 スナップショットのレコードの内容を破壊操作してはいけないことだけは頭に入れておきましょう。

#@<Table#snapshot@>=
  def snapshot()
    synchronize do
      @global_data.dup
    end
  end

ローカル・データはトランザクション開始時点のスナップショットであり、 トランザクションごとに固有のものです。 読み出しにはロックは不要です。 ただし、 スナップショットは、 グローバル・データの浅いコピーなので、 トランザクションからグローバル・データに副作用が及ばないように用心する目的で、 レコードのコピーを作って返しておきます。

#@<Transaction#fetch, each@>=
  def fetch(id)
    @local_data.key?(id) or raise IndexError
    dup_record(@local_data[id])
  end

  def each()
    @local_data.each_value do |r|
      yield dup_record(r)
    end
    nil
  end

  def dup_record(r)
    r && {:id => r[:id].dup, :name => r[:name].dup, :v => r[:v].dup}
  end

ローカル・データへの編集は挿入・削除・変更の 3 つです。 変更は削除と挿入の組み合わせにすることもできますが、 別の編集コマンドをスクリプトに追加します。 ここで、 挿入と変更で、 新しくレコードを作ってからローカル・データのハッシュ・オブジェクトに代入しているのは大切です。 こうすることでグローバル・データへの副作用を避けています。

#@<Transaction#insert, delete, update@>=
  def insert(id, name, v)
    not @local_data.key?(id) or raise IndexError
    @local_data[id] = {:id => id, :name => name, :v => v}
    @log << [:insert, nil, @local_data[id]]
    self
  end

  def delete(id)
    @local_data.key?(id) or raise IndexError
    @log << [:delete, @local_data[id], nil]
    @local_data.delete(id)
    self
  end

  def update(id, name, n)
    @local_data.key?(id) or raise IndexError
    to = {:id => id, :name => name, :v => n}
    @log << [:update, @local_data[id], to]
    @local_data[id] = to
    self
  end

コミットとロールバックで、 表のグローバル・データにパッチを当てて、 トランザクションによる変更内容を反映させます。 平行して他のトランザクションが走っていて既にコミット済みならば、 この時点でローカル・データとグローバル・データの同期が崩れています。 なので、 リスタートで新しくスナップショットを得るまでは編集処理が失敗するように nil にしておきます。

#@<Transaction#commit, rollback@>=
  def commit()
    edit_script = @log
    @local_data = @log = nil
    @table.commit(edit_script)
    self
  end

  def rollback()
    edit_script = @log
    @local_data = @log = nil
    @table.rollback(edit_script)
    self
  end

表の側でパッチを当てます。 おもちゃなので、ジャイアント・ロックをかけ、 グローバル・データをコピーしてパッチを当てて、 成功したらグローバル・データに置き換えるという富豪な方式にしています。

#@<Table#commit@>=
  def commit(edit_script)
    synchronize do
      h = @global_data.dup
      patch(h, edit_script)
      @global_data.replace(h)
    end
    nil
  end

パッチ当ては編集スクリプトの先頭から順におこなっていき、 スナップショット取得時点の値から始めて逐一比較をしながら値が同一の場合に限って内容に手を加えていきます。 同じでないときは衝突とみなし、 例外を発生します。

#@<Table#patch@>=
  def patch(h, edit_script)
    edit_script.each do |edit_command, from, to|
      case edit_command
      when :insert
        not h.key?(to[:id]) or raise Conflict
        h[to[:id]] = to
      when :delete
        (h.key?(from[:id]) and h[from[:id]] == from) or raise Conflict
        h.delete(from[:id])
      when :update
        (h.key?(from[:id]) and h[from[:id]] == from) or raise Conflict
        h[to[:id]] = to
      end
    end
  end

ロールバックでも、 パッチを当てます。 これにより、 変更対象のレコードの内容がスナップショット取得時点と同じかどうかのチェックをすることになります。 内容が変わっていたら、 ロールバックすることができなかったことになるので例外が発生します。 コミットと違い、 パッチ当てに成功してもグローバル・データは元のままにして手をつけません。

#@<Table#rollback@>=
  def rollback(edit_script)
    h = snapshot()
    patch(h, edit_script)
    nil
  end

これで仕掛けができあがったので、 動かしてみます。 まずは、 Snapshot Isolation で、 Phantom Read が生じないのを見てみます。 もちろん、 Dirty Read も Non-Repeatable Read も生じません。 初期状態として 2 つのレコードを登録してコミットしておきます。 続いて、 2 つのトランザクションを得て、 t1 の方で読み取りを、 t2 で更新します。 t2 のコミット前で t1 からの読み出しは変化しないので、 Dirty Read になっていません。 t2 でコミットしても t1 からの読み出しは変化せず Non-Repeatable Read を生じませんし、 t2 による挿入・削除も影響しないので、 Phantom Read にもなっていません。 もちろん、 t2 のコミット後に新しく作った t3 で読むと、 t2 の変更が反映されています。

table = Table.new
t0 = table.transaction
t0.insert(1, 'alice', 100)
t0.insert(3, 'carrol', 100)
t0.commit

t1 = table.transaction
t2 = table.transaction

t1.each {|r| puts 't1 (%d %s %d)' % [r[:id], r[:name], r[:v]] }
#=> t1 (1 alice 100)
#   t1 (3 carrol 100)

t2.update(1, 'alice', 50)
t2.insert(2, 'bob', 100)
t2.delete(3)

t1.each {|r| puts 't1 (%d %s %d)' % [r[:id], r[:name], r[:v]] }
#=> t1 (1 alice 100)
#   t1 (3 carrol 100)

t2.commit

t3 = table.transaction
t3.each {|r| puts 't3 (%d %s %d)' % [r[:id], r[:name], r[:v]] }
#=> t3 (1 alice 50)
#   t3 (2 bob 100)
t3.commit

t1.each {|r| puts 't1 (%d %s %d)' % [r[:id], r[:name], r[:v]] }
#=> t1 (1 alice 100)
#   t1 (3 carrol 100)
t1.commit

Snapshot Isolation は更新対象のレコードによる楽観的排他制御しかしないので、 Write skew が生じることも見てみましょう。 2つのトランザクションを作成した後は、 どのように処理とコミットの順番を並べ替えても、 Write skew の結果が変化しないことを試してみるのも良いでしょう。 文面上で直列に t1 で update して commit し、 その後に t2 で update して commit しても、 アボートせずに結果が異常になるのは同じです。

table = Table.new
t0 = table.transaction
t0.insert(1, 'b1', 100)
t0.insert(2, 'b2', 100)
t0.commit

t1 = table.transaction
t2 = table.transaction              # こっちでも結果は同じ
v11 = t1.fetch(1)[:v]               # v11 = t1.fetch(1)[:v]
v12 = t1.fetch(2)[:v]               # v12 = t1.fetch(2)[:v]
v21 = t2.fetch(1)[:v]               # if v11 + v12 >= 200
v22 = t2.fetch(2)[:v]               #   t1.update(1, 'b1', v11 - 200)
if v21 + v22 >= 200                 # else
  t2.update(2, 'b2', v22 - 200)     #   puts '-- t1 insufficient'
else                                # end
  puts '-- t2 insufficient'         # t1.commit
end                                 # v21 = t2.fetch(1)[:v]
if v11 + v12 >= 200                 # v22 = t2.fetch(2)[:v]
  t1.update(1, 'b1', v11 - 200)     # if v21 + v22 >= 200
else                                #   t2.update(2, 'b2', v22 - 200)
  puts '-- t1 insufficient'         # else
end                                 #   puts '-- t2 insufficient'
t1.commit                           # end
t2.commit                           # t2.commit
t3 = table.transaction
t3.each {|r| puts 't3 (%d %s %d)' % [r[:id], r[:name], r[:v]] }
#=> t3 (1 b1 -100)
#   t3 (2 b2 -100)
t3.commit