Snapshot Isolation のおもちゃ・修正版

昨日のおもちゃは、 トランザクションで生じた編集過程をすべて記録して、 コミット時にグローバル・データの書き直しに利用していました。 そのため、 定義通りの Snapshot Isolation とは異なる挙動を示すことがありえます。 定義では、 スナップショット取得時点とコミット時点を比較して挿入・削除・変更されているレコードを使って、 グローバル・データの書き直しを楽観的排他制御でおこないます。 編集過程が影響しないのが理想です。

次の事例では、 トランザクション t2 で、 レコード 1 の値を変更しない update 編集コマンドを生成させることで、 コミット時の排他制御でレコード 1 とレコード 2 の両方がスナップショット時の値と同じかどうか調べています。 その結果、 Write skew をおこさずに t2 がアボートします。 Snapshot Isolation としては予想外のふるまいです。

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]
v12 = t1.fetch(2)[:v]
v21 = t2.fetch(1)[:v]
v22 = t2.fetch(2)[:v]
if v21 + v22 >= 200
  t2.update(1, 'b1', v21)           # 同じ値に変更
  t2.update(2, 'b2', v22 - 200)
else
  puts '-- t2 insufficient'
end
if v11 + v12 >= 200
  t1.update(1, 'b1', v11 - 200)
  t1.update(2, 'b2', v12)           # 同上
else
  puts '-- t1 insufficient'
end
t1.commit
puts '-- t1 commit'
begin
  t2.commit
  puts '-- t2 commit'
rescue Conflict
  puts '-- t2 abort'
end
#=> -- t2 abort
t3 = table.transaction
t3.each {|r| puts 't3 (%d %s %d)' % [r[:id], r[:name], r[:v]] }
t3.commit
#=> t3 (1 b1 -100)
#      (2 b2 100)

スナップショット取得時点からの変化をトランザクションで追跡すれば問題は解決します。 今度は、 どのレコードがどう変化したかだけを記録すれば良いので、 変化しているレコードだけをハッシュに収めることにします。

class Transaction
  def initialize(table)
    @table = table
    @local_data = @change = nil     # !
    restart()
  end

  def restart()
    @local_data = @table.snapshot()
    @change = {}                    # !
    self
  end

#@<Transaction#fetch, each@>        # 前稿と同じなので省略します。
#@<Transaction#insert@>
#@<Transaction#delete@>
#@<Transaction#update@>
#@<Transaction#commit, rollback@>
end

レコードが挿入できるということは、 スナップショットにレコードが存在しなかった場合と、 削除された後の場合がありえます。 削除されたということは、 当初は存在していたはずなので、 削除から変更に書き直します。 さらに、 スナップショット時点と同じ値を挿入しなおしたときは削除を取り消します。

#@<Transaction#insert@>=
  def insert(id, name, v)
    not @local_data.key?(id) or raise IndexError
    to = {:id => id, :name => name, :v => v}
    case (@change.key?(id) ? @change[id][0] : :none)
    when :none
      @change[id] = [:insert, nil, to]
    when :delete
      if @change[id][1] == to
        @change.delete(id)
      else
        @change[id][0] = :update
        @change[id][2] = to
      end
    end
    @local_data[id] = to
    self
  end

挿入したレコードを削除したときは、 当初のレコードが存在しなかった状況に戻したことになるので、 挿入を取り消します。 変更済みのレコードを削除したときは、 削除に扱いを変えます。

#@<Transaction#delete@>=
  def delete(id)
    @local_data.key?(id) or raise IndexError
    from = @local_data[id]
    case (@change.key?(id) ? @change[id][0] : :none)
    when :none
      @change[id] = [:delete, from, nil]
    when :insert
      @change.delete(id)
    when :update
      @change[id][0] = :delete
      @change[id][2] = nil
    end
    @local_data.delete(id)
    self
  end

スナップショット取得時点とは異なる値に変えたときに限って変更の扱いにします。 既に変更済みのレコードをスナップショット取得時点の値に戻したときは、 変更の扱いを取り消します。 挿入されたレコードの値を変更するときは、 相変わらず挿入の扱いのままとして、 挿入される値を更新します。

#@<Transaction#update@>=
  def update(id, name, n)
    @local_data.key?(id) or raise IndexError
    to = {:id => id, :name => name, :v => n}
    case (@change.key?(id) ? @change[id][0] : :none)
    when :none
      if @local_data[id] != to
        @change[id] = [:update, @local_data[id], to]
      end
    when :insert
      @change[id][2] = to
    when :update
      if @change[id][1] == to
        @change.delete(id)
      else
        @change[id][2] = to
      end
    end
    @local_data[id] = to
    self
  end

コミットとロールバックでは、 変化をグローバル・データに施すようにします。

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

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

Table オブジェクトのコミットとロールバックも変化を受け取るようにします。 Ruby だと字面は変化しませんが、 引数の型が配列からハッシュに変わります。

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

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

変化を記録したハッシュを使ってグローバル・データにパッチを当てます。

#@<Table#patch@>=
  def patch(h, change)
    change.each_value 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

これで抜け道を塞ぐことができました。 最初の事例でも、 両方のトランザクションのコミットが成功し、 誤った値の組み合わせが得られて、 Write skew が生じます。