Nested Transactions

Databases let you group changes into a transaction: either all of them happen, or you roll back and none of them do. Transactions can also nest, so a part of a job can be undone without undoing the whole job. Build TransactionalStore, an in-memory key-value store with nested transactions.

• set(key, value) stores value under key.
• get(key) returns the value stored under key, or None if there is none.
• delete(key) removes key and returns True, or returns False if there is no such key.
• count(value) returns how many keys currently hold value.
• begin() opens a new transaction, inside the one that is open already (if any).
• rollback() undoes every set and delete made since the most recent open begin(), and closes that transaction. It returns True, or False (changing nothing) if no transaction is open.
• commit() closes the most recent open transaction and keeps its changes. Those changes now belong to the transaction around it, so if that one is rolled back later, they are undone too. When the outermost transaction is committed, its changes are permanent. It returns True, or False if no transaction is open.
• depth() returns how many transactions are open.

Changes made while no transaction is open are permanent at once.

Examples

db = TransactionalStore()
db.set('a', 10)
db.begin()
db.set('a', 20)
db.begin()
db.set('a', 30)
db.get('a')        # returns 30
db.rollback()      # returns True
db.get('a')        # returns 20
db.commit()        # returns True
db.get('a')        # returns 20
db.rollback()      # returns False, no transaction is open

db = TransactionalStore()
db.set('x', 'red')
db.set('y', 'red')
db.begin()
db.delete('x')     # returns True
db.set('y', 'blue')
db.count('red')    # returns 0
db.rollback()
db.count('red')    # returns 2

Constraints

• Keys and values are strings or integers
• Up to 200,000 calls, transactions nested up to 10,000 deep, and up to 100,000 keys in the store
• begin, set, get, delete and count should each take about the same time however big the store and however deep the nesting; rollback and commit should take time in proportion to the number of keys the closed transaction changed, not the size of the store