MVCC transaction

mvcc_read_committed.py

# In-memory MVCC transaction of read-committed isolation level.

next_xid = 1
active_xids = set()
records = []

def new_transaction():
  global next_xid
  print('Txn %d: start' % next_xid)
  xid = next_xid
  next_xid += 1
  active_xids.add(xid)
  return Transaction(xid)

class Transaction:
  def __init__(self, xid):
    self.xid = xid
    self.rollback_actions = []

  def get(self, key):
    global records
    value = None
    for record in records:
      if record['key'] == key and self._is_visible(record):
      value = record['value']
    print('Txn %d: get %d => %s' % (self.xid, key, value))

  def update(self, key, value):
    print('Txn %d: update %d => %s' % (self.xid, key, value))
    self._delete(key)
    self._insert({"key": key, "value": value})

  def delete(self, key):
    print('Txn %d: delete %d' % (self.xid, key))
    self._delete(key)

  def _insert(self, record):
    record['created_xid'] = self.xid
    record['expired_xid'] = 0
    self.rollback_actions.append(["delete", len(records)])
    records.append(record)

  def _delete(self, key):
    for i, record in enumerate(records):
      if self._is_visible(record) and record['key'] == key:
      if self._is_locked(record):
        self.abort()
        else:
          record['expired_xid'] = self.xid
          self.rollback_actions.append(["undelete", i])

  def _is_locked(self, record):
    return (record['expired_xid'] != 0 and
      record['expired_xid'] in active_xids)

  def _is_visible(self, record):
    # The record was created in active transaction that is not our
    # own.
    if (record['created_xid'] in active_xids and
    record['created_xid'] != self.xid):
      return False

    # The record is expired or and no transaction holds it that is
    # our own.
    if (record['expired_xid'] != 0 and
    (record['expired_xid'] not in active_xids or
        record['expired_xid'] == self.xid)):
      return False

    return True

  def commit(self):
    print('Txn %d: commit' % self.xid)
    active_xids.discard(self.xid)

  def rollback(self):
    print('Txn %d: rollback' % self.xid)
    self._rollback()

  def get_all_visible(self):
    global records
    visible_records = []
    for record in records:
      if self._is_visible(record):
      visible_records.append(record)
    print('Txn: %d, visible records: %s' % (self.xid, visible_records))
    return visible_records

  def _abort(self):
    print('Txn %d: abort' % self.xid)
    self.rollback()

  def _rollback(self):
    for action in reversed(self.rollback_actions):
      if action[0] == 'undelete':
      records[action[1]]['expired_xid'] = 0
      elif action[0] == 'delete':
      records[action[1]]['expired_xid'] = self.xid
    active_xids.discard(self.xid)

if __name__ == '__main__':
  txn1 = new_transaction()
  txn1.update(key=1, value="A")
  txn1.update(key=2, value="B")
  txn1.commit()

  txn2 = new_transaction()
  txn2.update(key=1, value='C')

  txn3 = new_transaction()
  txn3.get(key=1)

  txn2.update(key=2, value='D')
  txn2.update(key=3, value='E')
  txn2.commit()

  txn3.get(key=1)
  txn3.get(key=2)
  txn3.get(key=3)