Binyamin's Notes

Distributed Transactions

2 min read

Say we have a ton of data, partitioned across many machines. How do we manage a transaction that requires multiple of these machines?

ACID requires that transactions,

  1. Atomic - execute fully or not at all
  2. Consistent - obey app-specific invariants
  3. Isolated - behave as if independent
  4. Durable - persist reliably

Serializability is important but not trivial. The most lenient definition requires that execution of transactions concurrently results in some serial ordering.

Concurrency control,

  • Pessimistic - obtain locks to guarantee safety before modifying shared data
  • Optimistic - modify shared data and correct if an issue happens

In practice, pessimistic control is better for high contention, while optimistic control has less overhead in situations with low contention

Two-phase locking is a common scheme for handling locks on shared data. We acquire locks as needed and let go of locks (all at once is strict, but we can also let go of them slowly) once we’ve acquired all locks. Done naively, 2PL can result in deadlocks, but we can enforce an absolute ordering on locks to guarantee safety.

2-Phase Commit is a protocol that enables a transaction coordinator to safely run distributed transactions

  1. TC sends a prepare message to each server with the command
  2. Each server responds with a prepared message and persists the command
  3. Once TC receives a response from each server, it sends a commit message to each server
  4. Each server logs a commit and responds with a committed message

Notes,

  • Until a server commits, it must hold locks on the involved data
  • The coordinator must have a mechanism to send out missed commit messages, whether this is due to an internet issue or due to a crash (coordinator or server)
  • If the coordinator hasn’t committed, it may rollback servers that have prepared
  • The coordinator must hold on to logs of a transaction until it knows all servers have committed, however a server can forget about a transaction right after it commits, since returning back idk when the coordinator asks about the committed status tells the coordinator that it has committed (otherwise it’d still be in the prepared state)