kv = KVStore()
kv.set("a", 5)
kv.get("a") # 5
kv.get("b") # KeyError
kv.set("b", 1)
kv.get("b") # 1
kv.set("b", 3)
kv.get("b") # 3
kv.delete("b")
kv.get("b") # KeyError

kv = KVStore()
kv.set("a", 1)
kv.get("a") # 1
kv.begin()
kv.set("a", 2)
kv.get("a") # 2 -> imply uncommited read. If no such an example is given, ask the expectation
kv.begin()
kv.set("a", 3)
kv.get("a") # 3
kv.rollback()
kv.get("a") # 2 -> imply that a rollback will rollback the last begin, instead of the first begin
kv.commit()
kv.get("a") # 2
kv.rollback() # ValueError
kv.commit() # ValueError

t1 begin
t1 set a = 1
t2 begin
t2 set a = 2
t2 commit

t3 begin
t3 get a??? 2 or 1?, should be 2
------------
assume only one thread to get kv object?

-----
kv = KVStore()
kv.set(1, 3)
kv.begin()
kv.set(1, 4)
print(kv.get(1))

This returns 4, which is an uncommitted read. Shouldn't it return 3 instead?

---------
begin()
set(x,2)

begin()
set(x,3)
get(x) -> needs to return 3

begin()
set(x,6)
commit()

get(x) -> expect to return 6 or 3? my implementation returns 3

class KVStore:
	def __init__(self):
		self.store = {}
		self.transactions_stack = []

	def set(self, key, value):
		if not self.transactions_stack:
			self.store[key] = value
			return

		self.transactions_stack[-1][key] = value

	def get(self, key):
		if not self.transactions_stack:
			if key not in self.store:
				raise KeyError("not exist")

			return self.store[key]

		for idx in range(len(self.transactions_stack) - 1, -1, -1):
			if key in self.transactions_stack[idx]:
				if self.transactions_stack[idx][key] is None:
					raise KeyError("not exist")
				return self.transactions_stack[idx][key]

		if key not in self.store:
			raise KeyError("not exist")
		return self.store[key]

	def delete(self, key):
		if not self.transactions_stack:
			del self.store[key]
			return

		# TODO what if this key never exists before, need O(transaction_n) to check
		m = self.transactions_stack[-1]
		m[key] = None  # special flag

	def begin(self):
		self.transactions_stack.append({})

	def commit(self):
		if not self.transactions_stack:
			raise KeyError("nothing to commit")

		current_transaction = self.transactions_stack.pop(-1)
		for k, v in current_transaction.items():
			if v is None:
				del self.store[k]
				return

			self.store[k] = v

	def rollback(self):
		if not self.transactions_stack:
			raise KeyError("nothing to rollback")

		self.transactions_stack.pop(-1)