Atomic TransactionsNovember 3, 2004Jeffrey L. EppingerProfessor of the PracticeSchool of Computer Science15-4103-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger2So Who Is This Guy?Jeff Eppinger ([email protected], EDSH 229)– Ph.D. Computer Science (CMU 1988)– Asst Professor of Computer Science (Stanford 1988-1989)– Co-founder of Transarc Corp. (Bought in 1994 by IBM)•Transaction Processing Software• Distributed File Systems Software–IBM Faculty Loan to CMU eCommerce Inst. (1999-2000)– Joined SCS Faculty in 2001– Lecture Style: ¿Questioning?3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger3Do You Do ACID?• What is ACID?• The ACID Properties of a Transaction:–Atomicity: all or none– Consistency: if before than after–Isolation: despite concurrent execution, ∃ serial ordering– Durability: committed transaction cannot be undone3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger4Did You Vote?public class PresidentialElection { private static int bush = 0; private static int kerry = 0; public static void voteForBush() { bush = bush + 1; } public static void voteForKerry() { kerry = kerry + 1; }}public class VotingMachine implements Runnable { public void run() { … if (…) PresidentialElection.voteForBush(); if (…) PresidentialElection.voteForKerry(); … }}3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger5Does it Work?•Do the PresidentialElection and VotingMachine classes implement the ACID Properties?– Atomicity: yes…you either get your vote or don’t –Consistency: looks okay…it’s an app thing– Isolation: no…if two threads…and one is in the middle of…and then the other one…– Durability: no…just reboot3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger6How Do You Fix It?• Isolation: add synchronized statements– Or your favorite form of synchronization public static synchronized void voteForBush() { bush = bush + 1; }3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger7How Do You Fix It?• Durability: write it to disk private static RandomAccessFile f = …; public static synchronized void voteForKerry() throws… { f.seek(KERRY_POS); int oldValue = f.readInt(); int newValue = oldValue + 1; f.seek(KERRY_POS); f.writeInt(newValue); }• Does this work?3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger8How Does Data Get Written to Disk?• Does the OS buffer the writes?• Does the disk write happen atomically?3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger9How About This One?public class BankAccount { private static RandomAccessFile f = new Ra…("…","rws"); private long myPosInFile = …; public double getBalance() throws IOException { synchronized (f) { f.seek(myPosInFile); return f.readDouble(); } } public void setBalance(double x) throws IOException { synchronized (f) { f.seek(myPosInFile); f.writeDouble(x); } }}3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger10What Is a Transaction?• A group of sub-operations that as a whole conform to the ACID properties private BankAccount savings = new BankAccount(…); private BankAccount checking = new BankAccount(…); public void transferStoC(double amount) throws … { savings.write(savings.read()-amount); checking.write(checking.read()+amount); } public void transferCtoS(double amount) throws … { }• (Does this work?)3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger11You Need to Delineate the Transaction public void transferStoC(double amount) throws … { Transaction.begin(); savings.write(savings.read()-amount); checking.write(checking.read()+amount); Transaction.commit(); }public class Transaction { private static ThreadLocal tid = new ThreadLocal(); public static void begin() { tid.set(nextTid()); } public static void commit() { /* hard work goes here */ } public static void rollback() { /* hard work goes here */ }}3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger12How Are ACID Properties Enforced? public void transferStoC(double amount) throws … { Transaction.begin(); savings.write(savings.read()-amount); checking.write(checking.read()+amount); Transaction.commit(); }• Atomicity – logging• Consistency – app’ s problem• Isolation – locking• Durability – logging3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger13Remind You of Something?• A Relational Database– Any database3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger14How Does a Relational DB Do It? (1)• Consistency– Code must be correct• Isolation– Two-phased read-write locking– Read-intent-write lock & ordering avoid deadlocks3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger15How Does a Relational DB Do It? (2)• Atomicity & Durability– Buffer database disk pages in memory– Log all changes in a write-ahead log• When changing data pages, describe in log recs• When flushing data pages, check that log flushed• When committing, commit-record into log, flush log– Recover from the log• When rolling back, scan log and undo• When restarting after a failure, scan the log– Undo transactions without commit records, as necessary– Redo transactions with commit records, as necessary3-Nov-2004 15-411 Atomic Transactions Copyright (C) 2004 J. L. Eppinger16How Does a Relational DB Do It? (3)• More on Atomicity & Durability– Databases are very careful when they write to disk– They control the buffering of pages in memory– The log is append-only, order of records counts• If commit rec present, preceded by descrip. of changes…• If descrip of changes present, without commit rec …• We track the last log rec # that applies to ea data page…– Log recs describing changes, go out before the page w/changes– Often, we put the
View Full Document