Issue 47 - Speculative Modifications

Another weekend, another weekend read, this time all about Speculative Modifications.

Interactive database transactions introduce a rarely articulated capability that offers a delightful developer experience: Speculative Modifications.

A process consists of a sequence of steps, where a step is a modification of the current state of the system. A step may transition the system from a consistent state to a consistent state or from a consistent state to an inconsistent state.

proc:
  step
  step
  step
  step <- correctness violation

• Interactive Database Transactions

  Interactive database transactions alter state speculatively, allowing the developer (or the database) to reactively validate the correctness of the resulting system state after applying a modification.

• In-Memory Data Structures

  In-memory data structures alter state definitively, requiring the developer to proactively validate the correctness of the resulting system state before applying a modification.

Interactive database transactions allow developers to rollback (the effects of) a process if a correctness violation happens at the n-th step. We have to go through great length to get the same capability for an in-memory data structure.

Let’s do just that in Python

The naive approach to speculative modifications is to take a snapshot, a copy of the data structure, at the beginning of a process or at the first write. In case of rollback, the system can simply restore the snapshot. However, taking a snapshot is an expensive operation. Can we do better?

We’ll implement speculative modifications by representing state modifications using three core abstractions: Collections, Transactions, and Commands.

State modifications, that is, Inserts, Updates, and Deletes are represented as pure data structures.

@dataclass
class Insert:
  id: object
  item: object
@dataclass
class Update:
  id: object
  part: object
@dataclass
class Delete:
  id: object

The Collection is responsible for holding a set of items and applying commands to modify state.

class Collection:
  def __init__(self):
    self._items = {}
  def apply(self, action):
    if isinstance(action, Insert):
      if action.id in self._items:
        raise KeyError(f"Item with id {action.id} already exists")
      self._items[action.id] = action.item
    elif isinstance(action, Update):
      if action.id not in self._items:
        raise KeyError(f"Item with id {action.id} not found")
      for key, value in action.part.items():
        setattr(self._items[action.id], key, value)
    elif isinstance(action, Delete):
      if action.id not in self._items:
        raise KeyError(f"Item with id {action.id} not found")
      del self._items[action.id]

The Transaction maintains redo and undo stacks. Whenever a state modification is placed on the redo stack, a compensating modification is placed on the undo stack. Changes can be rolled back when desired, for example, in the event of a correctness violation.

class Transaction:
  def __init__(self, collection):
    self.collection = collection
    self.redo_stack = []
    self.undo_stack = []
  def get(self, id):
    return self.collection._items[id]
  def insert(self, id, item):
    redo = Insert(id, item)
    undo = Delete(id)
    self.redo_stack.append(redo)
    self.undo_stack.append(undo)
    self.collection.apply(redo)
  def update(self, id, part):
    item = self.collection._items[id]
    redo = Update(id, part)
    undo = Update(id, {key: getattr(item, key) for key in part})
    self.redo_stack.append(redo)
    self.undo_stack.append(undo)
    self.collection.apply(redo)
  def delete(self, id):
    item = self.collection._items[id]
    redo = Delete(id)
    undo = Insert(id, item)
    self.redo_stack.append(redo)
    self.undo_stack.append(undo)
    self.collection.apply(redo)
  def commit(self):
    self.redo_stack.clear()
    self.undo_stack.clear()
  def rollback(self):
    for action in reversed(self.undo_stack):
      self.collection.apply(action)
    self.redo_stack.clear()
    self.undo_stack.clear()

Here's how we use our implementation:

@dataclass
class User:
    name: str
    email: str
c = Collection()
t = Transaction(c)
t.insert(1, User("foo", "foo@example.org"))
t.insert(2, User("bar", "bar@example.org"))
# c = Collection(
#   (1, User("foo", "foo@example.org"))
#   (2, User("bar", "bar@example.org"))
# )
t.commit()
# c = Collection(
#   (1, User("foo", "foo@example.org"))
#   (2, User("bar", "bar@example.org"))
# )
t = Transaction(c)
t.update(1, {"email": "foo@example.com"})
t.update(2, {"email": "bar@example.com"})
# c = Collection(
#   (1, User("foo", "foo@example.com"))
#   (2, User("bar", "bar@example.com"))
# )
t.rollback()
# c = Collection(
#   (1, User("foo", "foo@example.org"))
#   (2, User("bar", "bar@example.org"))
# )

By implementing speculative capabilities in an in-memory data structure, we can enjoy a similar developer experience to database transactions to a Python application.

Happy Reading