_____________ SECTION4 Irene Zhang _____________ Table of Contents _________________ 1 Transaction model .. 1.1 Canonical example .. 1.2 ACID Examples .. 1.3 Distributed Challenges 2 ACID semantics .. 2.1 Atomic .. 2.2 Consistency .. 2.3 Durability .. 2.4 Isolation 3 ACID in other contexts vs transactions .. 3.1 Atomicity .. 3.2 Durability .. 3.3 Isolation vs Consistency 4 Concurrency control .. 4.1 Strict 2-Phase Locking .. 4.2 Multi-versioned concurrency control ..... 4.2.1 OCC ..... 4.2.2 Snapshot Isolation .. 4.3 Distributed CC 5 Transaction logging .. 5.1 Replicated databases 6 Distributed Atomicity .. 6.1 2PC ensures atomicity 1 Transaction model =================== - a group of operations over a set of objects 1.1 Canonical example ~~~~~~~~~~~~~~~~~~~~~ - bank account balance - I want to move $10 to my friends bank account if A - 10 >= 0: A = A - 10 B = B + 10 - But not so easy 1.2 ACID Examples ~~~~~~~~~~~~~~~~~ - You want only A to be decremented if B is incremented, not one or the other (atomicity) - You don't want A or B < 0 (consistency) - You want A and B to be written and read at one point, so you don't want a context switch after the if statement (isolation) - Once A and B are changed, you want that change not to be lost (durability) 1.3 Distributed Challenges ~~~~~~~~~~~~~~~~~~~~~~~~~~ - A and B might be distributed across partitions/shards - A and B might also be replicated or cached - Today, we'll look at how you build transactions for a single node, Tom will talk about 2PC tomorrow, which is a way for guaranteeing atomicity across nodes - I will talk briefly about how to achieve other properties in a distributed system 2 ACID semantics ================ 2.1 Atomic ~~~~~~~~~~ - all ops in transaction commit or none - done with a commit point, usually a log to disk 2.2 Consistency ~~~~~~~~~~~~~~~ - state of the database after each transaction satisfies a set of constraints - is not the same as cache consistency! - Ignore this, it's some weird database idea, blame researchers for not coordinating terms! 2.3 Durability ~~~~~~~~~~~~~~ - once transaction is committed, won't be lost - usually done with a disk log 2.4 Isolation ~~~~~~~~~~~~~ - ordering of concurrent transactions appears as if single core running one transaction at a time - Many, many different levels, somewhat equivalent to consistency: - Serializable appears to be a single core system to programs running on it (transactions have a single ordering) - Strict Serializable appears to be a single core system to users (the transaction ordering matches when transactions commit), also called Linearizable (blame Google for messing this term up!) - Snapshot Isolation, every transaction runs on a snapshot of the data. Almost .. Serializable, but not due to write skew anomalies (basically not detecting read-write conflicts), sometimes labeled serializable in production databases like Oracle and Postgres before 9.1 - Also, read-committed and read-uncommitted, basically just see anything that has been committed, but doesn't keep others from changing it and read-uncommitted can see things that aren't even committed, so may disappear (if the transaction aborts) - Many production databases use very weak isolation levels, somewhere between read-committed and read-uncommitted 3 ACID in other contexts vs transactions ======================================== 3.1 Atomicity ~~~~~~~~~~~~~ - can be either single object or multi-object - Single object example: test-and-set instruction - Multi object example: take $10 out of my bank account and move to my friend's bank account 3.2 Durability ~~~~~~~~~~~~~~ - File system example: fsync - Transaction commit implies fsync (although many DBs don't do this!) 3.3 Isolation vs Consistency ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - Consistency describes single object, whereas isolation is for a multi-object/multi-op transaction - Consistency is always a total ordering, whereas isolation is a partial ordering - Terms were decided by different communities, so don't match and is often confusing! 4 Concurrency control ===================== - ensures isolation by scheduling transactions to appear as if they ran at a single point in time - most common is locking or multi-versioned concurrency control (MVCC) 4.1 Strict 2-Phase Locking ~~~~~~~~~~~~~~~~~~~~~~~~~~ - keep one lock per object or database tuple - usually single writer/multi-reader locks - acquire all locks in first phase (execution), then release all in second phase (commit) - transaction must hold lock for every touched object to commit - transaction can be serialized at any time when all locks are held 4.2 Multi-versioned concurrency control ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - most common MVCC is Snapshot Isolation (both a isolation level and a CC technique) or Optimistic Concurrency Control (OCC) - use versions to ensure transaction appears as if it ran at a single point - keep version for each object/tuple - version id is either incremented or transaction time when the version was written 4.2.1 OCC --------- - collect versions of everything read - check if that is still the latest version on commit, if not, abort 4.2.2 Snapshot Isolation ------------------------ - get snapshot of the database at start of transaction - only read from that snapshot - if anything the transaction wants to write is updated since the snapshot, then abort, otherwise commit - can miss read-write conflicts 4.3 Distributed CC ~~~~~~~~~~~~~~~~~~ - What happens if objects are distributed over partitions or shards? - Basically can just grab locks at each partition or run OCC checks at each 5 Transaction logging ===================== - Each transaction gets one entry with its complete read and write set - Used as the commit point (i.e., once written in the log, transaction is considered committed) - Transaction write to log before putting in updates to tables. - Database state can be recreated by re-executing the log in order 5.1 Replicated databases ~~~~~~~~~~~~~~~~~~~~~~~~ - Writes to disk can be combined with replication or replaced - Can be done in a few ways: primary-backup or Paxos - Send transaction log from primary to backup like your view service, instead of get and put ops 6 Distributed Atomicity ======================= - What happens if one shard commits a transaction, but other one crashes or aborts it? Atomicity is violated 6.1 2PC ensures atomicity ~~~~~~~~~~~~~~~~~~~~~~~~~ - Tom will talk about tomorrow