MKSE 212: Scalable and Cloud Computing (Fall 2012)

Location

TBD, Tuesday/Thursday 4:30-6:00pm

Instructor

Andreas Haeberlen
Location: 560 Levine Hall
Office hour: TBD

Teaching assistants

(Not yet announced)

Course description

What is the "cloud"? How do we build software systems and components that scale to millions of users and petabytes of data, and are "always available"?

In the modern Internet, virtually all large Web services run atop multiple geographically distributed data centers: Google, Yahoo, Facebook, iTunes, Amazon, eBay, Bing, etc. Services must scale across thousands of machines, tolerate faults, and support thousands of concurrent requests. Increasingly, the major providers (including Amazon, Google, Microsoft, HP, and IBM) are looking at "hosting" third-party applications in their data centers - forming so-called "cloud computing" services. A significant number of these services also process "streaming" data: geocoding information from cell phones, tweets, streaming video, etc.

This course, aimed at a sophomore with exposure to basic programming within the context of a single machine, focuses on the issues and programming models related to such cloud and distributed data processing technologies: data partitioning, storage schemes, stream processing, and "mostly shared-nothing" parallel algorithms.

Topics covered

Datacenter architectures, the MapReduce programming model, Hadoop, cloud algorithms (PageRank, adsorption, friend recommendation, TF/IDF), web programming basics (servlets, AJAX, GWT), higher-level programming (Hive, Pig Latin), ...

Format

The format will be two 1.5-hour lectures per week, plus assigned readings. There will be regular homework assignments and a term project, plus a midterm and a final exam.

Prerequisites

CIS 120, Introduction to Programming
CIS 160, Discrete Mathematics
Co-requisite: CIS 121, Data Structures

Texts and readings

Hadoop: The Definitive Guide, Third Edition, by Tom White (O'Reilly)
Additional materials will be provided as handouts or in the form of light technical papers.

Grading

Homework 30%, Midterm 18%, Term project 30%, Participation 2%, Final 20%

Policies

You are encouraged to discuss your homework assignments with your classmates; however, any code you submit must be your own work. You may not share code with others or copy code from outside sources, except where the assignment specifically allows it. Plagiarism can have serious consequences.

Resources

We will be using Piazza for course-related discussions.

Term project

In two-person teams, build a small Facebook-like application using servlets and Google's Web Toolkit. Based on network analysis, the application should make friend recommendations; it should also visualize the social network.

NEW! There will be an award for the best project (sponsored by Facebook).

Assignments

Homework assignments will be available for download here.

Schedule

Date	Topic	Details	Reading	Remarks
Sep 06	Introduction	Course overview	--
Sep 11	The Cloud	Kinds of clouds; cloud applications Datacenters; utility computing Web vs. cloud vs. cluster	Armbrust et al.: A View of Cloud Computing	HW0
Sep 13	Programming at scale	Parallel architectures Challenges: Latency, failures, scalability, ... Internet basics; TCP and IP		HW1
Sep 18	Concurrency	Consistency models; CAP theorem Synchronization; locking Deadlock and livelock; solutions	Vogels: Eventually consistent	HW0 due
Sep 20	Cloud basics	Introduction to Amazon Web Services EC2 and EBS Other services	Handout: Getting Started with AWS
Sep 21	Course selection period ends
Sep 25	Cloud storage	Key-value stores; concurrency control S3 SimpleDB		HW1 MS1 due
Sep 27	Cloud case studies	Salesforce.com; Netflix Google Apps Data Warehousing at Facebook	White, Chapter 16: Case Studies NY Times article
Oct 02	MapReduce	Core concepts Programming model Examples of MapReduce algorithms	Dean and Ghemawat: MapReduce: Simplified Data Processing on Large Clusters
Oct 04	Programming in MapReduce	Using keys to group Different kinds of reduce functions Shuffle implementations	White, Chapter 6: How MapReduce Works	HW1 MS2 due
Oct 09	No class -- Andreas at OSDI
Oct 11	Midterm exam	(covers topics through Oct 04)
Oct 12	Last day to drop
Oct 16	Hadoop	Basics: Data types, drivers, mappers, reducers HDFS; dataflow in Hadoop Fault tolerance in Hadoop	White, Chapter 3: HDFS White, Chapter 5: Applications Hadoop Quick Start	HW2
Oct 18	Graph algorithms	Iterative MapReduce Graph representations; SSSP k-means; Naive Bayes; link analysis
Oct 23	Fall break
Oct 25	Random-walk algorithms	PageRank Adsorption Applications	Baluja et al.: Video suggestion and discovery for YouTube	HW2 due; HW3
Oct 30	Web programming	Client/server versus P2P Web protocols: DNS, HTTP, ... How to build a web server; threads vs events
Nov 01	Servlets	Servlet API; servlet containers; deploying servlets Managing state; cookies Web security		Team project spec
Nov 06 Nov 08	Web services and XML	Web services Data interchange XML; DTDs; DOM; XML schema
Nov 13	Dynamic content	JavaScript Ajax Google Web Toolkit		HW3 due; form project teams
Nov 15	Guest lecture?
Nov 16	Last day to withdraw
Nov 20	Beyond MapReduce	SQL JDBC and LINQ Hive	White, Chapter 12: Hive
Nov 22	Thanksgiving break -- no class
Nov 27	Hierarchical data	Beyond relations Pig Latin XQuery	White, Chapter 11: Pig
Nov 29	Peer-to-peer	P2P applications; swarming; incentives Structured and unstructured overlays; Pastry P2P security	Rodrigues and Druschel: Peer-to-Peer systems
Dec 04	Special topics	Accountability Differential privacy Network forensics
Dec 06	Second midterm exam
Dec 08	Reading days
Dec 12	Finals begin; project demos
Dec 19	Finals end