Principles of Data-Intensive Systems

Winter 2021
Tue/Thu 2:30-3:50 PM Pacific

This course covers the architecture of modern data storage and processing systems, including relational databases, cluster computing systems, streaming and machine learning systems. Topics include database system architecture, storage, query optimization, transaction management, fault recovery, and parallel processing, with a focus on the key design ideas shared across many types of data-intensive systems.

Find the 2022 version of this course on Canvas

Course Staff

Instructor

Matei Zaharia (Office hours: by appointment, please email me)

Teaching Assistants

Cody Coleman (Office hours: Wednesdays 4-5:30 PM Pacific, Zoom)
Daniel Kang (Office hours: Sundays 4:30-6 PM Pacific, Zoom)
Gina Yuan (Office hours: Wednesdays 10-11:30 AM Pacific, Zoom)
Peter Kraft (Office hours: Mondays 2:30-4 PM Pacific, Zoom)
Xinyi Yu (Office hours: Fridays 8:30-10 AM Pacific, Zoom)

Schedule

T, Jan 12	Introduction
Th, Jan 14	Database System Architecture Reading: A History and Evaluation of System R You can skip "The Recovery Subsystem", "The Locking Subsystem", "The Convoy Phenomeon" and "Additional Observations" on pages 643-644. Question: Why did the storage system change from "inversions" to B-trees during the project? Optional Reading: How to Read a Paper
T, Jan 19	Database Architecture 2 & Storage Assignment 1 Posted
Th, Jan 21	Storage Formats and Indexing Reading: Integrating Compression and Execution in Column-Oriented Database Systems Question: How might the conclusions of this paper change if it ran on an NVMe SSD instead? Optional Reading: C-Store: A Column-Oriented DBMS
T, Jan 26	Storage Formats and Indexing 2
Th, Jan 28	Query Execution
T, Feb 2	Query Optimization
Th, Feb 4	Query Optimization 2 Reading: Spark SQL: Relational Data Processing in Spark Question: What proof points does the paper give that Catalyst achieves its goal as an extensible optimizer? Can you think of any limitations to Catalyst's approach for supporting external extensions? Assignment 1 Due (at midnight) Assignment 2 Posted
T, Feb 9	Guest Talk: Automatically Discovering Systems Optimizations for Deep Learning Zhihao Jia, Carnegie Mellon University and Facebook Optional Readings: Beyond Data and Model Parallelism for Deep Neural Networks, TASO
Th, Feb 11	Transactions and Failure Recovery Test 1 Posted (solutions) Past Midterms for Reference: Winter 2020 (solutions), Spring 2019 (solutions), Winter 2017 (solutions)
T, Feb 16	Failure Recovery 2 Test 1 Due (at midnight)
Th, Feb 18	Concurrency
T, Feb 23	Concurrency 2 Reading: Granularity of Locks and Degrees of Consistency in a Shared Data Base Read up to page 372. You can skim the rest of the paper. Question: Draw the hierarchy of data structures in a DBMS that contains a table sorted by its primary key field with multiple pages. What locks have to be acquired if a transaction wants to move a record from one page of the table to another (by changing its primary key)?
Th, Feb 25	Concurrency 3 & Distributed Databases Optional Reading: Time, Clocks and the Ordering of Events in a Distributed System Assignment 2 Due (at midnight) Assignment 3 Posted
T, Mar 2	Distributed Databases 2 Optional Reading: Lessons from Internet Services: ACID vs. BASE
Th, Mar 4	Cloud Database Systems Optional Readings: Amazon Aurora, Dynamo, Delta Lake
T, Mar 9	Streaming Systems Optional Readings: The CQL Continous Query Language, The Dataflow Model
Th, Mar 11	Security and Data Privacy Reading: Privacy Integrated Queries Question: Give an example of a computation on data for which it's hard to provide any differential privacy. Optional Readings: Robust De-anonymization of Large Sparse Datasets, Opaque, Splinter Test 2 Posted (pdf) (docx) (solutions) Past Finals for Reference: Winter 2020 (solutions), Spring 2019 (solutions), Winter 2017 (solutions)
T, Mar 16	Guest Talk: Lakehouse Technology as the Future of Data Warehousing Reynold Xin, Databricks Enterprise data architectures usually contain many systems—data lakes, message queues, and data warehouses—that data must pass through before it can be analyzed. Each transfer step between systems adds a delay and a potential source of errors. What if we could remove all these steps? In recent years, cloud storage and new open source systems have enabled a radically new architecture: the lakehouse, an ACID transactional layer over cloud storage that can provide streaming, management features, indexing, and high-performance access similar to a data warehouse. Thousands of organizations including the largest Internet companies are now using lakehouses to replace separate data lake, warehouse and streaming systems and deliver high-quality data faster internally. I'll discuss the key trends, break down the different modules (storage, query engine, ecosystem) of the lakehouse architecture, and look at the main principles behind their design. Bio: Reynold Xin is a cofounder and Chief Architect at Databricks. Prior to Databricks, he was a PhD student at the UC Berkeley AMPLab.
Th, Mar 18	No Class (Work on Test 2) Assignment 3 Due (at midnight) Test 2 Due (at midnight)

Logistics

Announcements

All announcements will be made on our Piazza page for the class. Make sure you sign up for Piazza!

Prerequisites

Students should ideally have taken CS 145 and CS 161, or their equivalent courses. In particular, we expect students to be familiar with SQL syntax. You can take a basic SQL tutorial for an overview of SQL if needed.

Lectures and Video Recordings

Lectures for the class will be given live on Zoom and recorded. You can find our Zoom link and the lecture recordings on Canvas. Please note that these recordings might be reused in other Stanford courses, viewed by other Stanford students, faculty, or staff, or used for other education and research purposes. If you have questions about video recording, please contact a member of the teaching team.

Assignments and Tests

We will have three programming assignments and two take-home tests. The programming assignments are designed to be runnable on your personal machine and should be submitted through Gradescope.

The tests are open-book, meaning that you can use your course notes, slides, books, or online resources, except that communication is not be allowed during them (e.g., you can't ask a question on Stack Overflow or contact another student). Tests will cover material in the lectures, readings and assignments.

Readings

We have occasional readings for the lectures. We expect students to complete these and think about the questions we list for each paper on their own (you do not need to turn in answers). Our tests will cover content in the readings.

Optional Textbook

Database Systems: The Complete Book (2nd Edition), by Garcia-Molina, Ullman and Widom, covers a lot of the technical material in the course and may be helpful as a study guide. We focus on chapters 13-20. We will also cover the material in lectures, but this book is a good source of additional information.

Grading

Assignments: 18% each (total: 54%)
Test 1: 20%
Test 2: 26%

Late Policy

Students each have up to 2 late days that they may use for assignments and tests. Assignments and tests submitted after these late days have been used up will incur a penalty of 10% per extra day late. In addition, we will not accept submissions after March 20th at midnight Pacific to give the staff enough time for grading.

Auditing

The course Zoom meetings and recordings are open for auditing to any Stanford student on Canvas.

Feedback

Please post public questions about the class on Piazza. For private questions to the staff, please open a private post on Piazza. You can also email professor Zaharia at matei@cs.stanford.edu.