18-845: Internet Services
Carnegie Mellon University, Spring 2012

Syllabus (pdf) | Critiques | Individual Project (IP) | Group Project (GP)

Instructors

 Prof. David O'Hallaron, droh@cs.cmu.edu, GHC 9125, (412) 268-8199,
Office hours: Mon 4-6pm. (These are my nominal hours. Drop by any time the door is open.)

TA: Kushal Dalmia, kdalmia@andrew.cmu.edu, 232 INI (4616 Henry Street), (412) 519-9943
Office hours: Wed 4-6pm

Organization

Class times: Mon and Wed, 2:30-3:50, WeH 5409
Web page: www.ece.cmu.edu/~ece845
Class mailing list: 18-845-staff@cs.cmu.edu (includes staff and students)
Course directory: /afs/ece/class/ece845

Reference material

There is no required textbook for 18-845. The following are standard references for Linux programming and network programming:
  • Michael Kerrisk, The Linux Programming Interface: A Linux and UNIX System Programming Handbook, No Starch Press, 2010.
  • W. Richard Stevens, Bill Fenner, Andrew M. Rudoff Unix Network Programming: The Sockets Networking API, Volume 1 (3rd Edition), Prentice Hall, 2003.
The CS:APP2e text, which is available in the campus bookstore and on reserve in the Engineering library, covers system-level programming topics such as dynamic linking, process control, Unix I/O, the sockets interface, writing Web servers, and application level concurrency and synchronization:

Course schedule

Legend: IP: individual project, GP: group project

Class Date Day Topic Projects Discussion Leader
1 01/16 Mon No class (MLK day) ---
2 01/18 Wed Intro and welcome Dave O'Hallaron
3 01/23 Mon System design principles IP out Dave O'Hallaron
4 01/25 Wed Server design - basics Kushal Dalmia
5 01/30 Mon Server design - events/threads Kushal Dalmia
6 02/01 Wed Measuring server capacity Xianzhe Liang
7 02/06 Mon Clustering - request routing Yilun Cui
8 02/08 Wed Data center overview I Chi Zhang
9 02/13 Mon Data center overview II IP due, 2:30pm Jipeng Han
10 02/15 Wed Virtual machine overview Xuan Zhang
11 02/20 Mon HW/SW virtualization Alok Shankar
12 02/22 Wed VM implementations Shrikant Mether
13 02/27 Mon Nested virtualization Abraham Levkoy
14 02/29 Wed VM live migration Samartha Chandrashekar
15 03/05 Mon VM memory management GP absracts due, 2:30pm Dave O'Hallaron
16 03/07 Wed Energy-efficient computing Piyush Sharma
17 03/12 Mon No class - Spring break ---
18 03/14 Wed No class - Spring break ---
19 03/19 Mon Google search Georges Chamcham
20 03/21 Wed Google file system Anand Suresh
21 03/26 Mon Map-reduce Alexander Loria
22 03/28 Wed Table-based storage GP mid-term oral reports due Xia Wu
23 04/02 Mon Coordination systems Nathan Mickulicz
24 04/04 Wed Incremental updates Hsueh-Hao Chang
25 04/09 Mon Request tracing Prajakta Karandikar
26 04/11 Wed Key-value store Shekhar Suman
27 04/16 Mon Cloud storage systems Chen Wang
28 04/18 Wed Cloud storage systems Kai Liu
29 04/23 Mon No class - GP prep ---
30 04/25 Wed No class - GP reports due GP reports due 2:30pm Thur, 4/26, HARD DEADLINE! ---
31 04/30 Mon No class - GP reviews due GP reviews due, 2:30pm ---
32 05/02 Wed GP poster session Location: WeH 5409 all
05/06 Sun GP final reports due, 11:59pm

Detailed course schedule

Students who are not leading the discussion for a particular class should prepare a single 1-page critique. Unless explictly noted, the critique should cover all papers with a "*".

Bring a hardcopy (no email) of your critique with you to class and give it to the TA before class. He will grade it and return it to you next class.

Class 1: No class - MLK day (Mon 1/16)

Class 2: Welcome and intro (Wed 1/18)

Big picture and intellectual overview.

  • Note: No critiques are due today.
  • Eric A. Brewer, Lessons from Giant-Scale Services, IEEE Internet Computing, Vol 5, Num. 4, Aug, 2001. (pdf)

Class 3: System design principles (Mon 1/23)

  • Note: Your critique should list three other examples (not discussed by the authors) of end-to-end arguments in system design.
  • *J. Saltzer, D. Reed, and D. Clark, End-to-End Arguments in System Design, ACM Transactions on Computer Systems, Vol 2, No 4, Nov, 1984. (pdf)
  • Butler Lampson, Hints for Computer System Design ACM Operating Systems Rev. 15, 5 (Oct. 1983), pp 33-48. Reprinted in IEEE Software 1, 1 (Jan. 1984), pp 11-28. (html)

Class 4: Server design - basics (Wed 1/25)

  • Note: Please write two separate critiques.
  • *V. Pai, P. Druschel, and W. Zwaenepoel, Flash: An efficient and portable Web server, Proceedings of the USENIX 1999 Annual Technical Conference, 1999. (pdf)
  • *Tim Brecht , David Pariag, and Louay Gammo, accept()able Strategies for Improving Web Server Performance, Proceedings of the USENIX 2004 Annual Technical Conference, June, 2004. (pdf)
  • D. Mosberger and T. Jin. httperf: A Tool for Measuring Web Server Performance. Performance Evaluation Review, Volume 26, Number 3, December 1998, 31-37. (Originally appeared in Proceedings of the 1998 Internet Server Performance Workshop, June, 1998.) ( pdf, download )

Class 5: Server design - events/threads (Mon 1/30)

  • Note: Please write two separate critiques.
  • *Gaurav Banga, Jeff Mogul and Peter Druschel, A scalable and explicit event delivery mechanism for UNIX, in the Proceedings of the USENIX 1999 Technical Conference, June 1999. (pdf)
  • *R. von Behren, J. Condit and E. Brewer, Why Events Are A Bad Idea (for high-concurrency servers), Proceedings of HotOS IX, Lihue, Kauai, Hawaii, May, 2003. (pdf)
  • David Pariag, Tim Brecht, Ashif Harji, Peter Buhr, and Amol Shukla, Comparing the Performance of Web Server Architectures EuroSys 2007, Lisbon, Portugal, March, 2007. (pdf)

Class 6: Measuring server capacity (Wed 2/1)

  • *G. Banga and P. Druschel, Measuring the Capacity of a Web Server under Realistic Loads, World Wide Web Journal (Special issue on World Wide Web Characterization and Performance Evaluation), 2(1), May 1999. (pdf)

Class 7: Clustering - request routing (Mon 2/6)

  • Note: Please write a single critique covering both papers.
  • *V. Pai, M. Aron, G. Banga, M. Svendsen, P. Drushel, W. Zwaenepoel, E. Nahum, Locality-aware request distribution in cluster-based network services. In Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems, October 1998. (pdf)
  • *M. Aron, D. Sanders, P. Druschel, and W. Zwaenepoel. Scalable Content-aware Request Distribution in Cluster-based Network Servers. In Proceedings of the USENIX 2000 Annual Technical Conference, June, 2000. (pdf)

Class 8: Datacenter Overview (Chapters 1-4) (Wed 2/8)

  • Note: Please write a single critique covering chapters 1-4
  • *Luiz Andre Barrosa and Urs Holzle, The Datacenter as a Computer, Morgan & Claypool, 2009. (pdf)

Class 9: Datacenter Overview (Chapters 5-8) (Mon 2/13)

  • Note: Please write a single critique covering chapters 5-8
  • *Luiz Andre Barrosa and Urs Holzle, The Datacenter as a Computer, Morgan & Claypool, 2009. (pdf)

Class 10: VM overview (Wed 2/15)

  • Note: Please write a single critique covering both papers.
  • *Mendel Rosenblum and Tal Garfinkel, Virtual Machine Monitors: Current Technology and Future Trends, IEEE Computer, May, 2005. (pdf)
  • *G. Neiger, A. Santoni, F. Leung, D. Rodgers, R. Uhlig, "Intel Virtualization Technology: Hardware Support for Efficient Processor Virtualization", Intel Technology Journal, Aug, 2006. (pdf)

Class 11: SW/HW virtualization (Mon 2/20)

  • *K. Adams, and O. Agesen, A Comparison of Software and Hardware Techniques for x86 Virtualization, In Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, 2006. (pdf)
  • Nikhil Bhatia, "Performance Evaluation of Intel EPT Hardware Assist", VWware white paper, 2009 (pdf)

Class 12: VM implementations (Wed 2/22)

  • Note: Please write a single critique covering both papers.
  • *P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, A. Warfiel, Xen and the Art of Virtualization, In Proceedings of the 19th ACM Symposium on Operating Systems Principles, October, 2003. (pdf)
  • *A. Kivity, Y. Kamay, Dor Laor, U. Lublin, A. Liguori, kvm: the Linux Virtual Machine Monitor, Proceedings of the Linux Symposium, Volume 1, pp 225-230, Ottawa, Ontario, Canada, June 2007. (pdf)

Class 13: Nested virtualization (Mon 2/27)

  • *M. Ben-Yehuda, M. Day, Z. Dubitzky, M. Factor, N. HarEl, A. Gordon, A. Liguori, O. Wasserman, B. Yassour, The Turtles Project: Design and Implementation of Nested Virtualization, OSDI, 2010. Awarded best paper. (pdf)

Class 14: VM live migration (Wed 2/29)

  • *Christopher Clark, Keir Fraser, Steven Hand, Jacob Gorm Hanseny, Eric July, Christian Limpach, Ian Pratt, Andrew Warfield, "Live Migration of Virtual Machines", NSDI '05. (pdf)

Class 15: VM memory management (Mon 3/5)

  • *D. Gupta, S. Lee, M. Vrable, S. Savag, A. Snoeren, G. Barghese, G. Voelker, and A. Vahdat, Difference Engine: Harnessing Memory Redundancy in Virtual Machines, OSDI '08, Dec, 2008. Awarded best paper. (pdf)

Class 16: Energy-efficient computing (Wed 3/7)

  • Note: Please write a single critique covering both papers.
  • *David Andersen, Jason Franklin, Michael Kaminsky, Amar Phanishayee, Lawrence Tan, Vijay Vasudevan, FAWN: A Fast Array of Wimpy Nodes, SOSP 2009, Big Sky, MT. October 2009. Awarded best paper. (pdf)
  • *V. Vasudevan, D. Andersen, M. Kaminsky, L. Tan, J. Franklin, I. Moraru Energy-efficient Cluster Computing with FAWN: Workloads and Implications, Proceedings of e-energy, 2010, invited paper. (pdf)

Class 17: No class - Spring break (Mon 3/12)

Class 18: No class - Spring break (Wed 3/14)

Class 19: Google search (Mon 3/19)

  • Note: Please write a single critique covering both papers.
  • *Sergey Brin and Larry Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, Seventh International World Wide Web Conference / Computer Networks 30(1-7): 107-117. 1998. (pdf)
  • *Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd, The PageRank Citation Ranking: Bringing Order to the Web, 1998. (pdf)
  • Ian Rogers, The Google Pagerank Algorithm and How It Works (html) May, 2002.

Class 20: Google file system (Wed 3/21)

  • *Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, The Google File System, in Proceedings of the 19th ACM Symposium on Operating Systems Principles, October, 2003. (pdf)

Class 21: Map-reduce (Mon 3/26)

  • *J. Dean, and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, in Proceedings of Sixth Symposium on Operating System Design and Implementation, December, 2004. (pdf)

Class 22: Table-based storage (Wed 3/28)

  • *F. Chang, J. Dean, S. Ghemawat, W.C. Hsieh, D.A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber, Bigtable: A Distributed Storage System for Structured Data, in Proceedings of the Seventh Symposium on Operating System Design and Implementation, December, 2006. (pdf)

Class 23: Coordination services (Mon 4/2)

  • *M. Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems, in Proceedings of the Seventh Symposium on Operating System Design and Implementation, December, 2006. (pdf)

Class 24: Incremental updates (Wed 4/4)

  • *D. Peng and F. Dabek, Large-scale Incremental Processing Using Distributed Transactions and Notifications, OSDI, 2010. (pdf)

Class 25: Request tracing (Mon 4/9)

  • *Benjamin H. Sigelman, Luiz Andre Barroso, Mike Burrows, Pat Stephenson, Manoj Plakal, Donald Beaver, Saul Jaspan, Chandan Shanbhag, Dapper, a Large-Scale Distributed Systems Tracing Infrastructure, Google Technical Report dapper-2010-1, April 2010. (pdf)

Class 26: Key-value stores (Wed 4/11)

  • *H. Lim, B. Fan, D. Andersen, M. Kaminsky, SILT: A Memory-Efficient, High-Performance Key-Value Store, SOSP, Oct, 2011. (pdf)

Class 27: Cloud storage systems (Mon 4/16)

  • *B. Calder, et al Windows Azuer Storage: A Highly Available Cloud Storage Service with Strong Consistency SOSP, Oct, 2011. (pdf)

Class 28: Cloud storage systems (Mon 4/18)

  • *D. Beaver, S. Kumar, H. Ki, J. Sobel, P. Vajgel Finding a needle in a Haystack: Facebook's photo storage OSDI, 2010. (pdf)

Class 29: No class - GP prep (Mon 4/23)

Class 30: No class - GP reports due (Wed 4/25)

Class 31: No class - GP reviews due (Mon 4/30)

Class 32: GP poster session (Wed 5/2)