MKSE 212: Scalable and Cloud Computing (Fall 2011)

Location

Towne 311, Tuesday/Thursday 4:30-6:00pm

Instructor

Andreas Haeberlen
Location: 560 Levine Hall
Office hour: Wednesdays 2:30-3:30pm

Teaching assistants

Arjun Narayan, narayana@cis.upenn.edu
Office hour: Mondays 1:00-2:00pm (Levine 612)

Mingchen Zhao, mizhao@cis.upenn.edu
Office hour: Fridays 9:30-10:30am (Levine 612)

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, Second 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

Course discussion forum: http://groups.google.com/group/mkse212-fall2011

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.

Assignments

Homework assignments are available for download here.

Schedule

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