Transactional Database: Implement a Key-Value Store with BEGIN, COMMIT, and ROLLBACK Support

Question

## Problem

Design an in-memory key-value store that supports nested transactions:
- `set(key, value)` and `get(key) -> value | None`
- `delete(key)`
- `begin()` -- start a new transaction (nestable).
- `commit()` -- commit the innermost transaction.
- `rollback()` -- undo all changes in the innermost transaction.

```python
class TransactionalDB:
    def set(self, key: str, value: str) -> None: ...
    def get(self, key: str) -> str | None: ...
    def delete(self, key: str) -> None: ...
    def begin(self) -> None: ...
    def commit(self) -> None: ...
    def rollback(self) -> None: ...
```

**Example:**
```
db.set("x", "1")
db.begin()
db.set("x", "2")
db.get("x")  -> "2"
db.rollback()
db.get("x")  -> "1"
```

## Approach

Maintain a stack of transaction layers (each a dict of staged writes). On `get`, search layers top-to-bottom then the base store. On `commit`, merge top layer into the one below.

## Follow-ups
1. How does your rollback implementation handle `delete` -- what sentinel value distinguishes deletion from absence?
2. Implement `count(value) -> int` returning how many keys currently equal a given value, efficiently.
3. How would you add durability (survive process crash) to this store?
4. Discuss isolation levels -- which one does your implementation provide?

Transactional Database: Implement a Key-Value Store with BEGIN, COMMIT, and ROLLBACK Support

Question Details

Full Details

Topics

More from Square/Block