Designing Modern Web-Scale Applications

Course Description

The last decade has seen an enormous shift in computing, with the rise of cloud computing and big data processing, powered by web-scale applications. This course discusses the principles, key technologies and trends in the design of web-scale applications. The course will examine and compare the architectures and implementation of several types of web-scale applications. Students will learn how these applications are designed to achieve high scalability, reliability and high availability.

This is a seminar-style course in which students will be required to read, analyze, present and discuss seminal and cutting-edge research in this area. The aim is to both learn from prior work and extract exciting research questions. A course project will provide concrete experience and deeper understanding of the material.

The course covers advanced topics, broadly in the area of distributed systems, storage and databases, with a focus on web-scale applications. The goal is provide a survey of research in this area, rather than focus on a specific topic.

Prerequisites

This course builds on the following undergraduate courses: operating systems (ECE344) and distributed systems (ECE419). It assumes that students are knowledgeable about the contents of these courses.

Students are expected to have strong coding skills and be experienced in a language like Java, Python, or C++. They should have experience building and debugging a significant software system. If unsure, consult with the instructor.

Textbooks

There are no required textbooks for this course. The optional textbooks are

• Distributed Systems: Concepts and Design (Fifth Edition), by George Coulouris, Jean Dollimore Tim Kindberg and Gordon Blair, 2011.
• Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems, by Martin Kleppmann, 2017.
• Guide to Reliable Distributed Systems: Building High-Assurance Applications and Cloud-Hosted Services, by Kenneth P. Birman, 2012.

Mailing List

Please subscribe to the class mailing list by joining the UofT ECE1724 Google Group. Subscribing to the group may require the instructor's approval.

The instructor will use this group to send instructions and reminders. You can send email to the class by sending mail to this list. If you have a specific question for the instructor, please send an email to the instructor directly.

Grading Policy

Grades will be based on class presentations, a class project, and class participation. There will be no final exam in this course. The grading breakup is as follows:

• Class presentation: 30%
• Class project: 50%
• Class participation: 20%

Note: If a student is unable to attend a class, he or she will lose 2% for non-participation.

Class Presentation

Each week this class will cover a group of papers that focuses on a specific aspect of the course. Students are expected to read all the papers in the group that will be presented. At the beginning of the term, each paper will be assigned to a student who will be presenting the paper. Presentations will be limited to roughly 20 minutes.

More details about the presentation format. Please read very carefully.

Assignments

There will be no assignments in this course.

Class Project

A major component of this course is devoted to a term-long project. The topic of the project is largely up to you, but to help you choose a project, a sample list of projects is provided below. This list should help students determine whether their own projects are of reasonable size and scope.

Students will generally work in groups on a term project that pushes the state-of-the-art in the design of a web-scale application. Students will typically be required to implement and evaluate a significantly large software system.

More details about the project format. Please read very carefully.

Project Ideas

Here is a list of project ideas.

Readings

This is a tentative list. Most of these papers can be accessed from the ACM web site. If you cannot access ACM articles directly, please read the following instructions for accessing the papers.

Jan 10, Week 1: Introduction

1. Overview of the course.
2. Introduction to the course. Slides modified from Ken Birman's course on Cloud Computing 2019.
3. A View of Cloud Computing. CACM 2010.
4. The Dangers of Replication and a Solution. SIGMOD 1996.
5. Efficient Readings of Papers in Science and Technology.
6. How (and How Not) to Write a Good Systems Paper. Operating Systems Review 1983.

Jan 17, Week 2: Consensus and Coordination

1. In Search of an Understandable Consensus Algorithm. USENIX ATC 2014. Sari
2. ZooKeeper: Wait-free Coordination for Internet-scale Systems. USENIX ATC 2010. Daniel

     Optional reading:

1. Paxos Made Simple.
2. Replication Management using the State Machine Approach.
3. The Chubby lock service for loosely-coupled distributed systems. OSDI 2006.

Jan 24, Week 3: Cluster Storage Systems

1. The Google File System. SOSP 2003. Sari
2. Bigtable: A Distributed Storage System for Structured Data. OSDI 2006. Zhou

     Optional reading:

1. The Hadoop Distributed File System. MSST 2010.
2. Fast Crash Recovery in RAMCloud. SOSP 2011.

Jan 31, Week 4: Wide Area Storage Systems

1. Dynamo: Amazon's Highly Available Key-value Store . SOSP 2007. Kevin
2. Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency. SOSP 2011. Alexander

     Optional reading:

1. Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS. SOSP 2011.
2. Sharding the Shards: Managing Datastore Locality at Scale with Akkio. OSDI 2018.
3. Spanner: Google’s Globally Distributed Database. ACM TOCS 2013.

Feb 7, Week 5: Transactional Stores

1. Sinfonia: A New Paradigm for Building Scalable Distributed Systems. SOSP 2007. Yuqiu
2. Fast Distributed Transactions and Strongly Consistent Replication for OLTP Database Systems. TODS 2014. Pengyu

      Optional reading:

1. Transaction chains: achieving serializability with low latency in geo-distributed storage systems. SOSP 2013.

Feb 14, Week 6: RDMA Transactional Stores (first report due)

1. No compromises: distributed transactions with consistency, availability, and performance. SOSP 2015. Lino
2. FaSST: Fast, Scalable and Simple Distributed Transactions with Two-Sided (RDMA) Datagram RPCs. OSDI 2016. Pengyu

      Optional reading:

1. FaRM: Fast Remote Memory. NSDI 2014.
2. Fast and General Distributed Transactions using RDMA and HTM. Eurosys 2016.

Feb 21, Week 7: Data Parallel Frameworks

Note: This is reading week, but we are covering up for another week when I am away. Please let me know if you will not be able to make it to class.

1. MapReduce: Simplified Data Processing on Large Clusters. OSDI 2004. Raghav
2. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. NSDI 2012. Zhou

      Optional reading:

1. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks. Eurosys 2007.
2. Distributed aggregation for data-parallel computing: interfaces and implementations. SOSP 2009.
3. Tachyon: Reliable, Memory Speed Storage for Cluster Computing Frameworks. SoCC 2014.
4. Latency-Tolerant Software Distributed Shared Memory. USENIX ATC 2015.

Feb 28, Week 8: Scheduling

1. Sparrow: Distributed, Low Latency Scheduling. SOSP 2013. Gilkara
2. Apollo: Scalable and Coordinated Scheduling for Cloud-Scale Computing. OSDI 2014. Raghav

      Optional reading:

1. Improving MapReduce Performance in Heterogeneous Environments. OSDI 2008.
2. Quincy: Fair Scheduling for Distributed Computing Clusters. SOSP 2009.
3. Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling. Eurosys 2010.
4. Omega: flexible, scalable schedulers for large compute clusters. Eurosys 2013.

Mar 6, Week 9: Stream Processing

1. Storm @Twitter. SIGMOD 2014. Alexander
2. MillWheel: Fault-Tolerant Stream Processing at Internet Scale. VLDB 2013. Kevin

     Optional reading:

1. Kafka: a Distributed Messaging System for Log Processing. NetDB 2011.
2. Naiad: A Timely Dataflow System. SOSP 2013.
3. Discretized Streams: Fault-Tolerant Streaming Computation at Scale. SOSP 2013.
4. Building a Replicated Logging System with Apache Kafka. VLDB 2015.
5. Apache Flink™: Stream and Batch Processing in a Single Engine. 2015.
6. Drizzle: Fast and Adaptable Stream Processing at Scale. SOSP 2017.
7. SVE: Distributed Video Processing at Facebook Scale. SOSP 2017.
8. Structured Streaming: A Declarative API for Real-Time Applications in Apache Spark. SIGMOD 2018.

Mar 13, Week 10: Graph Processing (second report due)

1. Pregel: A System for Large-Scale Graph Processing. SIGMOD 2010. Yuqiu
2. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. OSDI 2012. Beibei

     Optional reading:

1. A Lightweight Infrastructure for Graph Analytics. SOSP 2013.
2. GraphX: Graph Processing in a Distributed Dataflow Framework. OSDI 2014.
3. Chaos: Scale-out Graph Processing from Secondary Storage. SOSP 2015.
4. Gemini: A Computation-Centric Distributed Graph Processing System. OSDI 2016.
5. Scalability! But at what COST?. HotOS 2015.

Mar 20: No Class

Instructor is away at a conference.

Mar 27: No Class

Apr 3, Week 11: Graph Mining

We will resume class online from this week. Instructions about online access will be provided via the class mailing list.

1. Arabesque: A System for Distributed Graph Mining. SOSP 2015. Beibei
2. AutoMine: Harmonizing High-Level Abstraction and High Performance for Graph Mining. SOSP 2019. Lino

     Optional reading:

1. RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine. OSDI 2018.
2. Fractal: A General-Purpose Graph Patern Mining System. SIGMOD 2019.

Apr 10, Week 12: Machine Learning Systems

1. Scaling Distributed Machine Learning with the Parameter Server. OSDI 2014. Gilkara
2. TensorFlow: A System for Large-Scale Machine Learning. OSDI 2016. Daniel

     Optional reading:

1. Project Adam: Building an Efficient and Scalable Deep Learning Training System. OSDI 2014.
2. Ray: A Distributed Framework for Emerging AI Applications. OSDI 2018.
3. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. OSDI 2018.
4. Gandiva: Introspective Cluster Scheduling for Deep Learning. OSDI 2018.
5. Pretzel: Opening the Black Box of Machine Learning Prediction Serving Systems. OSDI 2018.
6. PipeDream: Generalized Pipeline Parallelism for DNN Training. SOSP 2019.

Apr 17, Week 13: Project Presentations (final report due)