1• 9-10:30AM on Thursday, May 19, 2005• Johnson Ice Rink• All material from Lecture 16 (April 4) through Recitation 26 (May 12)• Bring your notes!• Print out the Unison paper and bring it.Atomicity ConceptsChapters 9 and 10LFS, System R, Chocolate, Unison, DurabilityLFS: MotivationRAM is cheap, so:The buffer cache will be largeReads will be “absorbed” by the buffer cacheLet’s design a filesystem that makes writes really fastLFS: On-Disk LayoutSS1 23 M1 SS2 47 23 M2mkdir(“/etc”, 0);fd = open(“/etc/group”, O_RDWR | O_CREAT);write(fd, buf, 5000);Segment SummaryInodeDataInode MapLFS: Observations• LFS uses checkpoints to decrease recovery time– Checkpoint region points to all blocks in the inode map• LFS outperforms SunOS FS for– Small writes– Many file createsLFS: Coping With a Finite Disk• Divide disk into segments of size s– Time to write s bytes >> rotational + seek latency– s << buffer cache size• Idea is to write whole segments at once• Cleaner runs periodically– Bottom line: no one really knows the cleaning overhead2Database TerminologyRecoverable and isolated.N/AAtomicApp-specified invariant is preserved.Do it all before or all after.Do it all or not at all.MeaningN/AConsistent“Consistent”Isolated“Atomic”RecoverableSystem R Terminology6.033DefinitionCommon Logging Configurations6.033 Notes,Figure 9-20LogAppCellStorageIn-memory DBAppCellStorageLogOrdinary DBAppCacheCellStorageLogHigh-perf. DBCore Memory (RAM) DiskAlyssa P. Hacker’s DBMS6.033 Notes,Problem 9.9b• On-disk log records transactions• Reference copy of all data in RAM• Checkpoint: write entire database state to the log• Recovery: start from last chpkted stateLogAppCellStorageIn-memory DBAlyssa P. Hacker’s DBMSCheckpointCrashTimeT1T2T3T4T5What if T3 nested in T2, T2 nested in T1?UndoRedoNo work neededNo work neededRedoSystem R• Take-home design points:– System R uses shadow files and write-ahead logging (WAL) to make transactions recoverable and isolated– Writes go through the buffer cache, flushed to disk when necessaryAppBufferCacheCellStorageLogSystem RCOBOL program with embedded SQLRSS actions, transactionsOperating System I/O operationsSystem R RDS Layer (not discussed much in the paper)System R RSS Layer (bulk of paper)3System R Shadow Filesdirectoryfile.currentfile.shadowDataPage 2PageTable 2PageTable 1DataPage 2CopyDataPage 1• FILE SAVE: file.shadowfile.current• FILE RESTORE: file.currentfile.shadowSystem R Write-Ahead Logging• Commit• Checkpoint• How is write-ahead logging useful?• “Golden Rule” of Recoverability– Never modify the only copy of dataSystem R Checkpoint and Recovery• Checkpoint:– Write checkpoint log record– FILE SAVE every shadow file– Remember log address of checkpoint record• Recovery:– FILE RESTORE files to their shadowed versions– Determine losers, winners– Undo or redo as necessarySystem R RecoveryTimeCheckpointCrashT1T2T3T4T5UndoRedoNo work neededNo work neededRedoIBM IMS Database System• Version 1 (1968) Isolation Protocol– A transaction may read only data that has been written by previously committed transactions.– A transaction must acquire a lock for every data item that it will write.6.033 Notes,Problem 9.3IBM IMS Database System1 BEGIN (T1);2 ACQUIRE (lock of y);3 temp1 x;4 5 67 y temp1;8 COMMIT (T1);91 BEGIN (T2);23 4 ACQUIRE (lock of x);5 temp2 y;6 x temp2;78 9 COMMIT (T2);Initially, x=3 and y=4Values after this execution completes? Have we achieved isolation?Intent: T1 assigns y=x; T2 assigns x=y4Atomicity ConceptsChapters 9 and 10LFS, System R, Chocolate, Unison, DurabilityReconciling Two Filesystems6.033 Notes,Chapter 10D• Quiesce the filesystems to be reconciled• Given left, right, last reconcile time=lrtif (modtime(left) > lrt) thencopy left to rightelsedelete leftif (modtime(right) > lrt) thencopy right to leftelsedelete rightif (modtime(left) > lrt AND modtime(right) > lrt) then/* conflict */else if (modtime(left) > lrt) thencopy left to rightelse if (modtime(right) > lrt) thencopy right to leftUnison• Reconciles a file system on a remote host• Optimistic vs. pessimistic concurrency control• State-based vs. log-based concurrency control• Detecting changes– Modification time– inode number– Cryptographic fingerprintProtecting InformationChapter 11 and Appendices,Slammer, DoS, Reflections on Trusting Trust, Why Cryptosystems Fail, Lampsons’s Hints for System DesignSlammer: Buffer OverrunsargvargcFrame pointerReturn addressbuffer[1023]buffer[0]int main(int argc, char **argv) {char buffer[1024];gets(buffer); return 0;} Increasing memory addressesHow not to read input into your program:This program could have read input from the network instead of the keyboard, resulting in a remote exploit!Stack grows downwardSlammer: Design and Lessons• Slammer exploited a similar buffer overrun in MS SQL Server 2000• Very simple exploit program– Send identical attack packets to random IPs, as fast as possible• Exponential attack rate• Lesson to users: close unused ports• Lesson to OS vendors: be secure by default5Internet Denial of Service• TCP SYN flooding– Solution: SYN cookies: push burden onto client• Reflectors– ICMP Smurf attack• Solution: ingress
View Full Document
Unlocking...