Attending lectures, in person, is mandatory. All lectures and recitations are recorded for offline review or asynchronous streaming in situations where synchronous participation wasn't feasible, but you still are expected to attend the actual lecture in person unless: (1) you were sick and have an SDS letter telling us to excuse you from class; (2) Cornell asked students to attend remotely due a Covid spike; (3) you are using up one of your 3 permitted "didn't attend" days. Sick but no letter? Then it counts towards one of these 3 days. If you plan to interview in the spring, please keep in mind that Cornell doesn't excuse you from class to interview. Interviews count against the 3 days, too.
We do not take attendance, but we do want to emphasize that in-person attendance has far better learning outcomes than watching videos. Use the videos if you have to miss a class, or to review material -- not as your primary learning tool. People who try to learn purely from videos invariably perform badly on exams and are not really comfortable with the course content by the end of the semester when asked about basic ideas in connection to their project designs. So don't try to work from home -- it just isn't a good strategy! In general we assume that most students will end up missing no more than 3 in-person lectures.
Textbooks. Many of the topics we cover are treated in one or both of the recommended textbooks. If you wish to learn more or to read about a topic from a different perspective as a way to improve your understanding or clarify some concern, we highly encourage you to look that topic up in either textbook. Both have comprehensive indices.
| Date | Topic | Remarks, Recommended reading (optional, see note above) | |
| The first group of lectures are concerned with some basic principles that govern cloud computing and scalability. The cloud is built from Linux servers but isn't the same as just logging into a Linux system and starting to build programs like you may have created in prior classes or jobs. You need to use the vendor-provided tools, and you need to be unusually aware of the way the hardware works -- otherwise your systems perform poorly or are very costly compared to the best possible (and at cloud scale, costs mount rapidly!) | |||
| 1. | 8/22 | [Cloud Overview. Internet of Things
and the Cloud IoT Edge] Overview of the course. Azure IoT model: Sensors, Azure IoT Edge roles, Azure Intelligent Edge and IoT Hub, u-services model, data center file system and database infrastructures, big-data analytics infrastructures. We focus on Azure just for coherency, but Amazon AWS has completely analogous components. If you know one cloud, you'll easily be able to adapt to any other cloud! Slides: pptx pdf video |
The first five lectures are really to help everyone get situated and
onto the same page in terms of terminology and mindset. In lecture one
we look at an end-to-end perspective on how a smart farm would work in
Microsoft Azure from data collection all the way back to data storage and
big-data analytics. The technical depth will be kind of shallow. Azure.microsoft.com: Home page for all of Azure and Azure IoT. This is actually quite a useful resource for finding more details on the topics of the first few lectures. Some of the examples in the lecture draw on work done by Professor Delimitrou in Cornell's ECE department. A paper on her Seer system can be found here: Seer: Leveraging Big Data to Navigate the Complexity. Seer depended on a suite of tools for benchmarking microservices discussed here: Benchmarking Microservices One example discussed in Lecture 1 is Microsoft's smart farms project. Read more at: FarmBeats: AI & IoT for Agriculture. |
| One big challenge with cloud computing is learning to master so much complexity. Read more about this "crisis of understandability" here! In CS5412, we will be learning basic building blocks that make the cloud understandable despite all of this complexity. By the end of the semester, you'll find that even very elaborate cloud architectures are approachable. | |||
| Scalability through a technique called "key-value sharding" is foundational in the cloud. We'll be using this extensively and testing on it, and every student needs to become proficient both in the concept and in finding clever ways to apply this even when the "match" to the problem statement may not be obvious. Understanding the tradeoffs matters too: in key-value sharding some data structures end up split over many shards, and that can introduce costs if your application is naive about how it accesses them. | |||
| 2. | 8/24 | [Scalability and Key-Value Sharding] Introduction to cloud scalability techniques: hierarchy, point of presence mini-datacenters, full datacenters, (key-value) sharding and simple fault-tolerance techniques, use of a DHT plus notifications to implement a publish-subscribe message bus, a DDS, or a message queue. Putting it all together: Akamai CDN and Facebooks massive content delivery infrastructure. Jim Gray's paper on why many lock-based products don't scale, and his argument for using sharding in cloud settings. Note that although Azure has a blob service (a key-value sharded store for binary large objects), and a sharded data store (Cosmos) and even has a NoSQL layer on top of Cosmos (CosmosDB) with all sorts of computing capability, we won't be discussing those in the main lectures -- it would take too long to look at all the options and details. So you will either see such things in recitation, as demos by the TAs, or might have to learn them on your own, from the huge amounts of online materials Azure and Amazon AWS offer. You find examples and basically copy and then customize them: in CS5412 this isn't considered to be cheating, but is the normal way people build things. But you do need to learn to find that documentation on your own, and to follow the demos and recommendations on your own. Slides: pptx pdf video |
Continuing our broad but shallow review, lecture two looks at ways of
breaking large data sets into what are called sharded key-value stores. Much of what we discuss in Lecture 2 can be found on Wikipedia in the key-value database entry. (In fact they go beyond what we will be talking about and look at the whole question of treating entire databases in a key-value manner, but in CS5412 we won't tackle the full question.) I'm not asking people to read Jim's paper, because it uses a great deal of database terminology. Instead, the two papers we'll specifically cover are concerned with Facebook's caching policy, and the RIPQ mechanism they used to adapt S4LRU to work on flash SSD. But you are only responsible for understanding the overall approach -- not the details. |
| 8/24 (recitation) 7:30 |
In this first recitation meeting we will talk about how homework and projects are handled. CS5412 will have 2 or 3 graded coding assignments (the first one will be assigned on the first day of classes!). Yifan will explain how to access CMS, how to prepare uploads and what to do to actually upload them, and how team formation will occur for the larger project that runs in the last 8 or 9 weeks of the semester. | Yifan will be running the recitations. Some are focused on class material and reviews of things that might have been confusing. A few focus on the project. . | |
| Containers play a huge role in the cloud. We'll look at the container concept, at how containers are managed by the function server, and how the function/container model differs from a cloud concept called a "microservice", which is also containerized but is managed in a different way, by the "App Server". | |||
| 3. | 8/29 | [Stateless Programming] In this
lecture, we will look at the issues raised by this idea of managed
microservices that live in elastic pools. Some of the issues involve
what is called stateless programming (we'll explain; it doesn't mean what
the word sounds like). Another issue is virtualization using a hypervisor such as Xen
versus container virtualization using Kubnetes with help from an OS like
Mesos. One topic will be Eric Brewer's CAP conjecture.
A second centers on the concept of an instance being a member of a
pool of instances. And a third will be a way to use
"versioned" key-value data as a way to make atomic updates without
locks. Slides: pptx pdf video |
We used the term "micro-service", but where did this idea come from?
What does a typical micro-service do? We'll also look at a few of the more
important micro-services found in Azure. Then we will look at the puzzle of
how these are typically implemented, and will see that some are stateless
(an easier case) and some are stateful (a much harder case). Normally,
stateless systems sit in front of stateful ones. Finally, we will see
that the App Service that manages these pools needs a simple way to deal
with the whole application as a kind of "package", and does this using
Container Virtualization. A lot of terminology, but the ideas are surprisingly simple. For example, a container is just a way to fool a normal program into thinking it is running inside a virtual machine, but without the high costs of a true virtual machine. |
| 4. | 8/31 | [Customizable platform services.] It isn't easy to build an elastic service of your own! Instead, you more commonly use some existing service provided to you as part of the cloud system. But many such services can be customized. In this lecture we learn about the concept of a triggered action, which would generally consist of a small module coded in a language like Python or C# and an associated JSON file that tells the service how to load and run your code, and what event should trigger it. Slides: pptx pdf video |
|
| 8/31 (recitation) 7:30 |
Discussion of cloud computing projects: Everything you could possibly want to know. You will even learn about why it might be valuable to watch cows chase other cows in a dairy barn! | ||
| No class on 9/5: This is a US holiday called "Labor Day" | |||
| 5. | 9/7 | More on DHTs: How can we store
complicated data sets in a DHT?] This lectures shifts back to our DHT concept and drills down on some challenges of actually squeezing complicated data into a DHT structure for scaling (the aggregated capacity of the DHT can be huge) or for speed (the shards operate independently, plus if we are careful, all the data can be held in memory). Slides: pptx pdf video Some enrichment/review slides for lectures 1-5 Note that everything we covered in class is "fair game" for prelim questions! But these slides will help you understand the basic concept that fancier thought questions might build upon. Slides: pptx pdf (there is no accompanying video for these slides) |
In a nutshell, although one could probably implement any application in any
way you like, doing so often forces us to think hard about what will work
well in the cloud and not collapse as soon as it becomes successful.
The puzzle is then this: we know how DHTs scale and why they perform well,
but how can we use them for things that don't look like (key,value) data? The hardest problem is "atomicity", and we solve that by doing what is called a "versioned" put in the DHT. Some DHT systems have slightly fancier options, but we won't discuss those in CS5412. |
| 9/7 (recitation) 7:30pm |
In this spring
version of this recitation
we were joined by Microsoft education specialist Vanessa
Villa. We will be showing and then discussing a video of her
talk. The materials she shared are not currently public, so
for now the slides and video are by Cornell netid access only, on
the Cornell box server. Slides: link. Video: link. |
Vanessa discussed the major components of building an Azure cloud application:
As she introduced this end-to-end solution, she used Azure IoT Edge, IoT Hub, Storage, Azure functions, ML, and other services. In each case she:
Knowing what services to use, and how to customize them to the applications are very helpful to the final projects. This talk can save you a lot of time of reading the documentations and large codebase on Azure websites, and help to pin down the components needed for your project. |
|
| State Machine Replication Model, Paxos, Derecho. These lectures look at how we can start with the idea of a shard that replicates data and formalize that model, then build optimal solutions to implement the best protocols. | |||
| 6. | 9/12 | [The State Machine Replication Model] Sharded data often must be replicated for higher availability. We will discuss various ways that systems have approached this, starting with really simple ways and will also see some of the potential issues, such as inconsistency or data loss. This will lead us to define the gold standard computing model for keeping backups: state machine replication. Chain replication is one way to solve this problem. Slides: pptx pdf video |
One big puzzle with a system split between sensors at the edge,
cloud-hosted middle services, and then perhaps back-end computing on massive
data sets, is that sooner or later elements will definitely fail and
restart. This lecture looks at the best ways to have your system keep
running even after a stumble. Optional reading: Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. Fred B. Schneider. ACM Comput. Surv. 22, 4 (Dec. 1990), 299–319. DOI:https://doi.org/10.1145/98163.98167 Chain replication for supporting high throughput and availability.Robbert van Renesse and Fred B. Schneider. In Proceedings of the 6th conference on Symposium on Operating Systems Design & Implementation - Volume 6 (OSDI’04). USENIX Association, USA, 7. |
| 7. | 9/14 | [Paxos and Derecho] In our Tuesday lecture we only scratched the surface on state machine replication and fault-tolerance concepts. Today we will discuss Paxos and Cornell's Derecho system, which is a cutting-edge version of the Paxos idea, but restructured to match better with fast datacenter networking. You'll also hear about how we are creating Cascade, a new cloud DHT, using Derecho. In the suggested readings (pane to the right) you'll find a paper on understanding Paxos, a really nice paper comparing 10 different replication protocols (including Derecho, which we covered in class), and then the Derecho paper itself. Slides: pptx pdf video [Enrichment and review material] Slides: pptx pdf video |
Paxos Made Moderately Complex. R Van Renesse and D
Altinbuken. ACM Comput. Surv. 47, 3, Article 42 (February 2015), DOI:
10.1145/2673577 Odyssey: The Impact of Modern Hardware on Strongly-Consistent Replication Protocols. Vasilis Gavrielatos, Antonios Katsarakis, Vijay Nagarajan . EuroSys ’21, April 26–28, 2021, Online, United Kingdom Derecho: Fast State Machine Replication for Cloud Services. Sagar Jha, Jonathan Behrens, Theo Gkountouvas, Matthew Milano, Weija Song, Edward Tremel, Sydney Zink, Kenneth P. Birman, Robbert van Renesse. ACM Transactions on Computing Systems (TOCS), 2019. |
| 9/14 (recitation) 7:30pm |
This recitation will focuson the idea of a versioned atomic put in a DHT from Lecture 5. It tends to show up on exams but many peope find the concept a bit hard to get used to when they first encounter it. We will look at some examples of how this might arise and how you would use this idea. | ||
|
These next lectures look at a
variety of issues that arise when a cloud interacts with the outside
world, scales beyond one data-center, and deals with temporal data. |
|||
| 8. | 9/19 | [IoT sensor registration. Risk of
sensor inaccuracy.] The Azure IoT hub and the concept of a secure sensor with a managed life-cycle. Sensor properties. Fault-tolerance. The META system and its model of fault-tolerance for IoT devices. Slides: pptx pdf video |
To start drilling down, we'll look closely at how end-users connect
devices like cameras, drones, microphones (Cortana/Siri/Alexa) and so forth
to the cloud. Azure IoT Hub is a microservice for secure sensor
management. Then we will study an example of a case where an IoT sensor malfunctions to start thinking about what this even means, how we could compensate, and what corrective actions might be appropriate. Tools for Distributed Application Management. K. Marzullo, M. Wood, K. Birman and R. Cooper. IEEE Computer, Aug. 1991, 24(8):42-51. Also valuable from this lecture is the training material for Azure IoT Edge, mentioned on slide 21 and 22. The Microsoft documentation can be accessed via this GitHub site (scroll down, past the index of folders and files). |
| 9. | 9/21 | [Time and Causality - Actual Clocks, Logical
Clocks] Timestamped data. Clocks and clock synchronization. Causal ordering and causal clocks. Snapshots and consistent cuts Slides: pptx pdf video [Enrichment and review material for time-related concepts] Slides: pptx pdf video |
Deep dive into underlying technology by looking at the issue of temporality
in modern IoT settings, where sensors might have some form of clock. Time, clocks, and the ordering of events in a distributed system. L. Lamport. Commun. ACM 21, 7 (July 1978), 558-565. Distributed snapshots: determining global states of distributed systems. K. Mani Chandy and Leslie Lamport. ACM Trans. Comput. Syst. 3, 1 (February 1985), 63-75. |
| 9/21 (recitation) 7:30pm |
This recitation will be a closer look at Paxos. Paxos is often covered on our exams and it is important to understand the basic "roles" that arise in the protocol (client, leader, acceptor, learner), the concept of a log with slots, the idea of a quorum for writes (updates) and for reads (queries), and how Paxos overcomes various kinds of failures. | ||
| 10. | 9/26 | [Challenges of Dealing with
Timestamped IoT Data] How Cascade implements the fancy snapshots we saw in lecture 9. Indexing into DHT data. Issues of heavy temporal computing and some of the solutions people are starting to propose. Slides: pptx pdf video |
In this lecture we will look at how Cascade was able to provide accurate
snapshots, but also at some of the challenges time and causality create when
we build IoT systems and want to do things like searching for a repeated
pattern over a long period of time. Lecture 10 pulls together everything from lectures 1-9. In one single system we end up seeing key-value sharding, customization with lambdas and/or functions, Derecho used because of its mix of virtual synchrony, atomic multicast and Paxos, consistent cuts, versioning for lock-free key-value updates... everything all at once. This is kind of insane, but it does explain why we built Cascade the way we did, and why it does so well on C+A microservices. If you understood lectures 1-9, you should be able to follow lecture 10! |
| 11. | 9/28 | [Strongly Consistent Geoscale Computing] Availability zones. WAN replication. Mirroring versus active update models. Google's Spanner system. 5G mobility. Slides: pptx pdf video |
If you depend on the cloud, clearly you need your
cloud to be reliable. Yet datacenters do fail. An availability
zone is a set of 2 or 3 side-by-side cloud datacenters that the vendor
manages to ensure that (if possible) at most 1 would be down at any time.
Because the distances are so tiny, latencies are similar to intra-datacenter
delays. WAN replication arises when datacenters are located at very long distances, maybe even globally. Yet we can still do strongly consistent data replication even at that scale, as Google's Spanner demonstrates. Spanner: Google’s Globally Distributed Database. James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. 2013. ACM Trans. Comput. Syst. 31, 3, Article 8 (August 2013), 22 pages. |
| 9/28 (recitation) 7:30pm |
|||
| 12. | 10/3 |
[Tracking state in big data-center systems] This lecture will look at the concept of gossip communication protocols, where we use little one-to-one data exchanges to track information like the total storage capacity available on the Amazon S3 storage servers. We'll discuss the concept of gossip, and then will look at two examples of how gossip can be used. One of them was invented by the CTO of Amazon when he was still at Cornell, and the S3 system was originally based on it (over time, of course, it evolved and became different). Slides: pptx, pdf video |
When systems get huge, even the overheads of keeping track of load and
capacity can be a burden. Gossip is appealing because it imposes very
low, controlled costs. The best package I know of for using Gossip in large datacenter settings is Lonnie Princehouse's open-source MiCA platform. |
| 13. | 10/5 |
[Case studies in disaster: How datacenter gossip can go wrong!] The idea of tracking storage capacity in S3 using gossip was a big success at Amazon... but it also revealed some really bizarre and unexpected issues with gossip that required more work in their deployment. We'll talk about some of the stories that became public and how Amazon fixed the issues. Slides: pptx, pdf video Some review slides for lectures 12-13 Slides: pptx pdf (there is no accompanying video for these slides) |
|
|
Prelim: October 5,
in the recitation time slot and room: 7:30-9:30pm, Gates G01. This exam is designed to require 1 hour, but we are providing 2 hours for anyone who wants more time, even without an SDS accommodation letter. |
|||
| Fall break: Oct 8-Oct 11. | |||
| 14. | 10/12 | [BlockChains] Definitions. Anonymity, Byzantine DDoS attacks. Using Ethereum or Hyperledger to encode smart contracts. Permissionless and permissioned models, and how they differ. Gossip in wide-area environments. Proof of work, proof of stake, proof of elapsed time. Slides: pptx pdf video [Enrichment and Review Material for Key BlockChain Concepts] Slides: pptx pdf video |
You
can read more about BlockChains of both permissioned and non-permissioned
flavor in this
wonderful survey, and also on Wikipedia.
Datacenter blockchains are permissioned, but because they run in a known
datacenter with known membership, are actually more like Paxos replicated
logs with crash failures. What makes something a permissioned
blockchain rather than a Paxos log is that we run it in a wide-area setting,
and anticipate Byzantine attacks. The founder of Ethereum talks about what Blockchains can and cannot do in this nice interview with the NY Times (accessible with your Cornell netid) You can read about one issue with Blockchains (use by criminals) here. In class we will be discussing the ethics of cryptocurrency and blockchain research. There are always two perspectives to any story -- and sometimes more than two. Just the same, it is important to be informed and to make decisions based on reality, so learning about reality is valuable no matter where you end up on the issue. |
| 10/12 (recitation) 7:30pm |
|||
| These next lectures drill down on Blockchain, but not cryptocurrency -- we will focus on how blockchains work and how the cloud uses them, especially for IoT. | |||
| 15. | 10/17 |
[BlockChain Puzzles and Concerns] Vegvisir. Open questions: BlockChain has been adopted so enthusiastically that early users are seemingly ignoring a great many puzzles. We'll discuss a few of them. Slides: pptx pdf video |
The main paper we will discuss is this:
Vegvisir: A Partition-Tolerant Blockchain for the Internet-of-Things, Kolbeinn Karlsson ; Weitao Jiang ; Stephen Wicker ; Danny Adams ; Edwin Ma ; Robbert van Renesse ; Hakim Weatherspoon. 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), Vienna, 20 A more recent system, Wayfarer, takes this idea one step further by adding "provenance awareness" (a form of credential-based authentication). Tamperproof Provenance-Aware Storage for Mobile Ad Hoc Networks. Danny Adams, Gloire Rubambiza, Paulo Fiori, Xinwen Wang, Hakim Weatherspoon, and Robbert Van Renesse. June 2020. |
| 16. | 10/19 | [Blockchain with multiple
organizations.] A puzzle for big enterprises is that many activities span more than one company, and each might need to keep its own blockchain. We'll look at how this makes access control and querying more difficult than it would have been with just one company using the blockchain. Slides: pptx pdf video |
|
| 10/19 (recitation) 7:30pm |
|||
| Privacy in the cloud, This is really a security topic, and Cornell has entire classes on security. We'll just have a single lecture on it, focused on a tool you can easily download and use. | |||
| 17. | 10/24 | [Privacy in Cloud Computing] Privacy isn't our main topic, but lecture 16 touched on it (HiPPA issues for electronic health care records). What's the best we can do on a cloud platform? Slides: pptx pdf video |
The main tool we will be talking about is CryptDB, an open source platform
you can download from
http://GitHub.com/CryptDB The work was done at MIT by Ralucca Popa, who is now a professor at UC Berkeley |
| 18. | 10/26 |
[SQL and database querying] This lecture will look at the SQL language, and how we can use it to access and even "transform" databases and other types of structured data collections. Slides: pptx pdf video |
Not everyone has taken a database class, and yet SQL is very widely used in cloud programming. This will be a one-lecture introduction to SQL. |
| 10/26 (recitation) 7:30pm |
|||
| Collections are a valuable tool for accessing data in a highly parallel way. We'll see the concept, but then we'll look at a particularly tricky case involving huge social-networking graphs and applications that run on those. | |||
| 19. | 10/31 | [Accessing collections from modern
programming languages] In this lecture we will look at technologies for accessing databases or other kinds of collections from programming languages like Python or C++. Specifically, we'll look first at Pandas, which is a Python add-on package for doing database accesses right in your program. Then we'll pivot to Azure and will look at LINQ, a general framework available from every programming language offered by Microsoft. Slides: pptx pdf video |
A big chunk of this lecture will be just looking at documentation web pages
that show how Pandas and LINQ are used. The ones we will focus on are
these
https://docs.microsoft.com/en-us/dotnet/csharp/linq/query-expression-basics
https://docs.microsoft.com/en-us/dotnet/csharp/linq/query-expression-basics
|
| 20. | 11/2 |
[Making The Cloud Friendlier for Object-Oriented Computing] Many modern systems are object oriented, yet Linux was born in a world of record-oriented databases and files containing things like binaries or text data. As a result there has been a push to make the cloud more object-friendly. We saw this in lecture 18 when we discussed the LINQ tools for embedding database access directly into programming languages by extending the concept of a collection with a variety of OO primitives. Today we will see that this extends into settings like Apache. This is a two-part lecture. First, we will discuss Ceph, an open-source file system designed using the Apache architecture that has a number of optimizations for object oriented computing (Ceph is not a component of Apache "per se" but is very often used in Apache applications). Next, we will look at an overhead issue that can arise when an object oriented application buys fully into this always-distributed, multiple-component mindset, and also at how that issue was solved in a specific setting (an air traffic control system in Europe). Slides: pptx pdf video |
While many big-data systems start with unstructured data (like web pages),
there are growing needs to work with higher-level "objects" through file
system APIs. Ceph is a new and very popular file system that scales super
well, has HPC extensions for people doing supercomputing research, and with
a built-in layer for "object" storage that bypasses the POSIX file system
API. Ceph: A Scalable High-Performance Distributed File System. Sage A. Weil, Scott A. Brandt, Ethan L. Miller, Darrell D. E. Long, and Carlos Maltzahn. 2006. In Proceedings of the 7th symposium on Operating systems design and implementation (OSDI '06). USENIX Association, Berkeley, CA, USA, 307-320. Ceph Object storage |
| 11/2 (recitation) 7:30pm |
|||
| 21. | 11/7 |
[MapReduce, Spark.] In ML settings, we often need to train ML models on really big sharded data sets. This motivated a very famous approach called the MapReduce pattern. Today we'll see what MapReduce does, but then will learn about the ecosystem of tools for MapReduce programming in the Apache platform (Hadoop and associated mechanisms). Hadoop became the basis of the Berkeley Spark project. The clever idea in Spark is to package LINQ-style logic as small containerized functions that can have "names" and yield cacheable results, which are simple files stored as objects into the HDFS or Ceph file system but that can be cached in memory too. RDDs are the name Spark introduced for this kind of object. They can be recomputed if needed, cached, and saved on a disk file to avoid recomputing them, if they need to be evicted from cache and it would be costly to recreate the contents. Slides: pptx pdf video |
The Hadoop version of MapReduce used to be slow until a Berkeley project called Spark came up with a clever new caching concept centered on resilient distributed data objects or RDDs. We'll look at how these work, and how they can talk to temporal data from sensors. Spark: Cluster Computing with Working Sets. Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, Ion Stoica. HotCloud 2010. Improving MapReduce Performance in Heterogeneous Environments, M. Zaharia, A. Konwinski, A.D. Joseph, R. Katz and I. Stoica, OSDI 2008, December 2008. |
| 22. | 11/9 | [More Apache big-data tools Apache hosts the Hadoop MapReduce platform and has a solution for every conceivable big-data scenario. Interestingly, the Ceph architecture is almost a "template" for Apache: many tools use that same architecture. Slides: pptx, pdf video. |
In this lecture we will review a few more of the Apache infrastructure tools. You'll want to check out awesome video about Kafka! |
| 11/9 (recitation) 7:30pm |
|||
| 23. | 11/14 |
[FLP Result] Fault-tolerance: Hard limits on what can be achieved. A strange theorem, known as the FLP result: "fault tolerance is impossible!" This can be confusing because Paxos, Derecho, Hadoop/Spark and Zookeeper all work perfectly well, despite this limitation. None of them is able to somehow escape the theoretical proof, but each of them has a way to avoid actually experiencing FLP-related crashes. We deep-dive to see how they do it in Lecture 24. Slides: pptx pdf video |
In this lecture we discuss the Fischer, Lynch and Patterson impossibility
result. The paper is not simple to read, although it is short.
Here is a pointer to it, and then a pointer to a much easier to follow paper
about some other limitations on fault-tolerance that might interest you: Impossibility of distributed consensus with one faulty process. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. J. ACM 32, 2 (April 1985), 374-382. DOI=http://dx.doi.org/10.1145/3149.214121 Easy impossibility proofs for distributed consensus problems. Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. In Proceedings of the fourth annual ACM symposium on Principles of distributed computing (PODC '85), Michael Malcolm and Ray Strong (Eds.). ACM, New York, NY, USA, 59-70.1985. DOI=http://dx.doi.org/10.1145/323596.323602 |
| 24. | 11/16 |
[Fault tolerance in practice] Fault-tolerance turns out to be easy in Hadoop and Spark! In this lecture we will see why the HDFS append-only policy, combined with Apache Zookeeper to sense failures, lets Spark offer "exactly once" computation guarantees. Slides: pptx pdf video |
Many people are surprised to learn that even though Hadoop's HDFS file system can be used more or less like a normal file system, in fact Hadoop only allows programs to append to files, not to do arbitrary updates. Why did they impose this rule? We'll see that it comes down to fault-tolerance in Hadoop. |
| Final exam: November 16. Similar
in format and difficulty to the prelim, in the recitation time slot
and room: 7:30-9:30pm, Gates G01. This exam is designed to require 1 hour, but we are providing 2 hours for anyone who wants more time, even without an SDS accommodation letter. |
|||
| Hardware accelerators do most or all of the heavy lifting for scaled-out cloud applications. We'll see how this is done, why adoption of accelerators has posed big challenges, how you use them in settings where they are available, and how accelerators are reshaping the cost-of-computing story. But we will also see that accelerators can be hard to leverage without "special sophistication". | |||
| 25. | 11/21 | [Social networking data: How the cloud
deals with huge graphs] We will look at one example of an existing big data infrastructure (Facebook TAO) and how modern systems access social networking graphs. Slides: pptx pdf video |
TAO: Facebook's Distributed Data Store for the Social Graph. Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov Dmitri Petrov, Lovro Puzar, Yee Jiun Song, Venkat Venkataramani. 2013 USENIX Annual Technical Conference (USENIX ATC '13). |
| Thanksgiving break 11/23-11/27 | |||
| 26. | 11/28 | [Hardware accelerators] These days, anyone who follows the cloud literature sees endless rave reviews of hardware devices like RDMA, NVMe, GPU and GPU clusters, TPU and TPU clusters, FPGA. How important are accelerators for cloud intelligence? How do you get access to them, and can you use them without learning obscure languages like Verilog? Slides: pptx pdf video |
In the cloud accelerators matter, a lot.
Many kinds of cloud intelligence applications center on very costly
computations, and we have to find ways to do them quickly and cost-effectively.
But this dimension of the cloud centers on its ability to leverage
highly specialized
hardware. We'll do a mile-high review of the most important
accelerators. You don't normally access these directly: instead, you
use u-services that already are integrated with them. But there are
exceptions: GPU and TPU are sometimes accessible to users, and there are
many software layers that have special permission to access other devices,
too. This drives us towards u-services: there just isn't any
other way to get the needed performance at reasonable cost. TensorFlow: A System for Large-Scale Machine Learning Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2016. In Proceedings of the 12th USENIX conference on Operating Systems Design and Implementation (OSDI'16). USENIX Association, Berkeley, CA, USA, 265-283. |
| 27. | 11/30 | [The challenge (nightmare?) of
rolling out new hardware] Why can't we just use hardware accelerators everywhere for computing, and use RDMA for all our data movements, and avoid "copying"? We'll focus on the RDMA version of this question. First we should understand why copying is such a costly operation, and why zero-copy nonetheless remains a holy grail. Then we'll look at the challenges of introducing RDMA into big data centers (and how to view those challenges as a "warning" for other future accelerators that people may want to deploy at scale!) Slides: pptx pdf video |
|
| 11/30 (recitation) 7:30pm |
|||
| 28. | 12/5 | [Wrapup: How the Business of Cloud
Computing Shapes the Future of Cloud Computing] This lecture will shift gears and focus on questions about how the cloud area has evolved as a line of business. What we will see is that very big investment decisions tend ot be determined by very big business opportunities and revenue streams: Cloud companies don't just randomly wander in various directions. Today's cloud is already a trillion dollar industry and investment. Some of the questions we will explore are: Up to now, how did big business ideas shape big data and cloud computing? Where is the financial centrism for today's cloud, and how is it changing? Can we assess IoT and edge computing using insights from the cloud business perspective? Slides: pptx pdf video |
|
| CS5412 final project presentations will be on the 3 days 12/6-12/8. | |||