From 9be42ea820c1b3f623ebeebaedfc3cd81107b4c9 Mon Sep 17 00:00:00 2001 From: kisalaya89 Date: Fri, 28 Oct 2016 09:56:46 -0400 Subject: Create temp.md --- chapter/2/temp.md | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) create mode 100644 chapter/2/temp.md (limited to 'chapter') diff --git a/chapter/2/temp.md b/chapter/2/temp.md new file mode 100644 index 0000000..fcefc09 --- /dev/null +++ b/chapter/2/temp.md @@ -0,0 +1,23 @@ +# What are promises ? + +- Future, promise, delay, or deferred. +- Definition + +# Historical Background + +- Algol thunk +- Incremental garbage collection of Processes - 1977 +- 1995 Joule channels +- 1997 Mark Miller - E + +# Current state of things + +- Lot of work done in Javascript +- Scala +- Finagle +- Java8 +- ? + +# Future Work + +- ? -- cgit v1.2.3 From cedc03d63afc7f837062e4b66a3bcbcc34516b56 Mon Sep 17 00:00:00 2001 From: kisalaya89 Date: Fri, 28 Oct 2016 11:25:57 -0400 Subject: Update temp.md --- chapter/2/temp.md | 1 + 1 file changed, 1 insertion(+) (limited to 'chapter') diff --git a/chapter/2/temp.md b/chapter/2/temp.md index fcefc09..0506ded 100644 --- a/chapter/2/temp.md +++ b/chapter/2/temp.md @@ -2,6 +2,7 @@ - Future, promise, delay, or deferred. - Definition +- States of promises # Historical Background -- cgit v1.2.3 From d4e0f859d700cd6a3c8a2d1b41821d0fa5da70cb Mon Sep 17 00:00:00 2001 From: Aviral Goel Date: Thu, 17 Nov 2016 16:33:14 -0500 Subject: Basic structure for introducing CAP --- ...dic-to-basic-how-the-database-ph-has-changed.md | 157 +++++++++++++++++++++ chapter/6/consistency-crdts.md | 11 -- 2 files changed, 157 insertions(+), 11 deletions(-) create mode 100644 chapter/6/acidic-to-basic-how-the-database-ph-has-changed.md delete mode 100644 chapter/6/consistency-crdts.md (limited to 'chapter') diff --git a/chapter/6/acidic-to-basic-how-the-database-ph-has-changed.md b/chapter/6/acidic-to-basic-how-the-database-ph-has-changed.md new file mode 100644 index 0000000..99b12d0 --- /dev/null +++ b/chapter/6/acidic-to-basic-how-the-database-ph-has-changed.md @@ -0,0 +1,157 @@ +--- +layout: page +title: "ACIDic to BASEic: How the database pH has changed" +by: "Aviral Goel" +--- + +## 1. The **ACID**ic Database Systems + +Relational Database Management Systems are the most ubiquitous database systems for persisting state. Their properties are defined in terms of transactions on their data. A database transaction can be either a single operation or a sequence of operations, but is treated as a single logical operation on the data by the database. The properties of these transactions provide certain guarantees to the application developer. The acronym **ACID** was coined by Andreas Reuter and Theo Härder in 1983 to describe them. + +* **Atomicity** guarantees that any transaction will either complete or leave the database unchanged. If any operation of the transaction fails, the entire transaction fails. Thus, a transaction is perceived as an atomic operation on the database. This property is guaranteed even during power failures, system crashes and other erroneous situations. + +* **Consistency** guarantees that any transaction will always result in a valid database state, i.e., the transaction preserves all database rules, such as unique keys, etc. + +* **Isolation** guarantees that concurrent transactions do not interfere with each other. No transaction views the effects of other transactions prematurely. In other words, they execute on the database as if they were invoked serially (though a read and write can still be executed in parallel). + +* **Durability** guarantees that upon the completion of a transaction, the effects are applied permanently on the database and cannot be undone. They remain visible even in the event of power failures or crashes. This is done by ensuring that the changes are committed to disk (non-volatile memory). + +

ACIDity implies that if a transaction is complete, the database state is structurally consistent (adhering to the rules of the schema) and stored on disk to prevent any loss.

+ +Because of the strong guarantees this model simplifies the life of the developer and has been traditionally the go to approach in application development. It is instructive to examine how these properties are enforced. + +Single node databases can simply rely upon locking to ensure *ACID*ity. Each transaction marks the data it operates upon, thus enabling the database to block other concurrent transactions from modifying the same data. The lock has to be acquired both while reading and writing data. The locking mechanism enforces a strict linearizable consistency. An alternative, *multiversioning* allows a read and write operation to execute in parallel. Each transaction which reads data from the database is provided the earlier unmodified version of the data that is being modified by a write operation. This means that read operations don't have to acquire locks on the database. This enables read operations to execute without blocking write operations and write operations to execute without blocking read operations. + +This model works well on a single node. But it exposes a serious limitation when too many concurrent transactions are performed. A single node database server will only be able to process so many concurrent read operations. The situation worsens when many concurrent write operations are performed. To guarantee *ACID*ity, the write operations will be performed in sequence. The last write request will have to wait for an arbitrary amount of time, a totally unacceptable situation for many real time systems. This requires the application developer to decide on a **Scaling** strategy. + +## 2. Transaction Volume + +To increase the volume of transactions against a database, two scaling strategies can be considered + +**Vertical Scaling** is the easiest approach to scale a relational database. The database is simply moved to a larger computer which provides more transactional capacity. Unfortunately, its far too easy to outgrow the capacity of the largest system available and it is costly to purchase a bigger system each time that happens. Since its not commodity hardware, vendor lock-in will add to further costs. + +**Horizontal Scaling** is a more viable option and can be implemented in two ways. Data can be segregated into functional groups spread across databases. This is called *Functional Scaling*. Data within a functional group can be further split across multiple databases, enabling functional areas to be scaled independently of one another for even more transactional capacity. This is called *sharding*. + +Horizontal Scaling through functional partitioning enables high degree of scalability. However, the functionally separate tables employ constraints such as foreign keys. For these constraints to be enforced by the database itself, all tables have to reside on a single database server. This limits horizontal scaling. To work around this limitation the tables in a functional group have to be stored on different database servers. But now, a single database server can no longer enforce constraints between the tables. In order to ensure *ACID*ity of distributed transactions, distributed databases employ a two-phase commit (2PC) protocol. + +* In the first phase, a coordinator node interrogates all other nodes to ensure that a commit is possible. If all databases agree then the next phase begins, else the transaction is canceled. + +* In the second phase, the coordinator asks each database to commit the data. + +2PC is a blocking protocol and is usually employed for updates which can take from a few milliseconds up to a few minutes to commit. This means that while a transaction is being processed, other transactions will be blocked. So the application that initiated the transaction will be blocked. Another option is to handle the consistency across databases at the application level. This only complicates the situation for the application developer who is likely to implement a similar strategy if *ACID*ity is to be maintained. + +# The part below is in bits and pieces. A lot of details need to be filled in. + +## 3. A Distributed Concoction + +**I am a cute diagram for the paragraph below.** + +In the network above, all messages between the node set G1 and G2 are lost due to a network issue. The system as a whole detects this situation. There are two options - + +* The system allows any application to read and write to data objects on these nodes as they are **available**. The application writes to a data object. This write operation completes in one of the nodes of G1. Due to **network partition**, this change is not propagated to replicas of the data object in G2. Subsequently the application tries to read the value of that data object and the read operation executes in one of the nodes of G2. The read operation returns the older value of the data object, thus making the application state not **consistent**. + +## 4. The volatile network + +Network Partition is a contentious subject among distributed database architects. While some maintain that network partitions are rare, other point to their. 9 + + +## 4. The spicy ingredients + + +This simple observation shows a tension between three issues concerning distributed systems - + +**Consistency** is the guarantee of total ordering of all operations on a data object such that each operation appears indivisible. This means that any read operation must return the most recently written value. This provides a very convenient invariant to the client application that uses the distributed data store. This definition of consistency is the same as the **Atomic**ity guarantee provided by relational database transactions. + +**Availability** is the guarantee that every request to a distributed system must result in a response. However, this is too vague a definition. Whether a node failed in the process of responding or it ran a really long computation to generate a response or whether the request or the response got lost due to network issues is generally impossible to determine by the client and willHence, for all practical purposes, availability can be defined as the service responding to a request in a timely fashion, the amount of delay an application can bear depends on the application domain. + +**Partitioning** is the loss of messages between the nodes of a distributed system. + + +This observation led Eric Brewer to conjecture in an invited talk at PODC 2000 - + +
It is impossible for a web service to provide the following three guarantees: +Consistency +Availability +Partition Tolerance
+ +It is clear that the prime culprit here is network partition. If there are no network partitions, any distributed service will be both highly available and provide strong consistency of shared data objects. Unfortunately, network partitions cannot be remedied in a distributed system. + + + + + +## 3. Strong Consistency + + + + + + + + + +We observed how in the event of a network partition, we could not have both availability and consistency at the same time. Let's study their pairwise interaction - + + +For many applications *ACID*ic datastores impose a more severe consistency guarantee than is actually needed and this reduces their availability. By relaxing the constraints on data consistency one can achieve higher scalability and availability. + +### 2. The **BASE**ic distributed state + +When viewed through the lens of CAP theorem and its consequences on distributed applications we realize that we cannot commit to perfect availability and strong consistency. But surely we can explore the middle ground. We can guarantee availability most of the time with sometimes inconsistent view of the data. The consistency is eventually achieved when the communication between the nodes resumes. This leads to the following properties of the current distributed applications, referred to by the acronym BASE. + +**Basically Available** services are those which are partially available when partitions happen. Thus, they appear to work most of the time. +**Soft State** services provide no strong consistency guarantees. They are not write consistent. Since replicas may not be mutually consistent, applications have to accept stale data. +**Eventually Consistent** services try to make application state consistent whenever possible. + + +### What's the right pH for my distributed solution? + +Whether an application chooses to an *ACID*ic or *BASE*ic service depends on the domain. An application developer has to consider the consistency-availability tradeoff on a case by case basis. *ACID*ic databases provide a very simple and strong consistency model making application development easy for domains where data inconsistency cannot be tolerated. *BASE*ic databases provide a very loose consistency model, placing more burden on the application developer to understand the limitations of the database and work around that, retaining sane application behavior. + +## References + +https://neo4j.com/blog/acid-vs-base-consistency-models-explained/ +https://en.wikipedia.org/wiki/Eventual_consistency/ +https://en.wikipedia.org/wiki/Distributed_transaction +https://en.wikipedia.org/wiki/Distributed_database +https://en.wikipedia.org/wiki/ACID +http://searchstorage.techtarget.com/definition/data-availability +https://aphyr.com/posts/288-the-network-is-reliable +http://research.microsoft.com/en-us/um/people/navendu/papers/sigcomm11netwiser.pdf +http://web.archive.org/web/20140327023856/http://voltdb.com/clarifications-cap-theorem-and-data-related-errors/ +http://static.googleusercontent.com/media/research.google.com/en//archive/chubby-osdi06.pdf +http://www.hpl.hp.com/techreports/2012/HPL-2012-101.pdf +http://research.microsoft.com/en-us/um/people/navendu/papers/sigcomm11netwiser.pdf +http://www.cs.cornell.edu/projects/ladis2009/talks/dean-keynote-ladis2009.pdf +http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf +https://people.mpi-sws.org/~druschel/courses/ds/papers/cooper-pnuts.pdf +http://blog.gigaspaces.com/nocap-part-ii-availability-and-partition-tolerance/ +http://stackoverflow.com/questions/39664619/what-if-we-partition-a-ca-distributed-system +https://people.eecs.berkeley.edu/~istoica/classes/cs268/06/notes/20-BFTx2.pdf +http://ivoroshilin.com/2012/12/13/brewers-cap-theorem-explained-base-versus-acid/ +https://www.quora.com/What-is-the-difference-between-CAP-and-BASE-and-how-are-they-related-with-each-other +http://berb.github.io/diploma-thesis/original/061_challenge.html +http://dssresources.com/faq/index.php?action=artikel&id=281 +https://saipraveenblog.wordpress.com/2015/12/25/cap-theorem-for-distributed-systems-explained/ +https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed +https://dzone.com/articles/better-explaining-cap-theorem +http://www.julianbrowne.com/article/viewer/brewers-cap-theorem +http://delivery.acm.org/10.1145/1400000/1394128/p48-pritchett.pdf?ip=73.69.60.168&id=1394128&acc=OPEN&key=4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E6D218144511F3437&CFID=694281010&CFTOKEN=94478194&__acm__=1479326744_f7b98c8bf4e23bdfe8f17b43e4f14231 +http://dl.acm.org/citation.cfm?doid=1394127.1394128 +https://en.wikipedia.org/wiki/Eventual_consistency +https://en.wikipedia.org/wiki/Two-phase_commit_protocol +https://en.wikipedia.org/wiki/ACID +https://people.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf +http://www.johndcook.com/blog/2009/07/06/brewer-cap-theorem-base/ +http://searchsqlserver.techtarget.com/definition/ACID +http://queue.acm.org/detail.cfm?id=1394128 +http://www.dataversity.net/acid-vs-base-the-shifting-ph-of-database-transaction-processing/ +https://neo4j.com/developer/graph-db-vs-nosql/#_navigate_document_stores_with_graph_databases +https://neo4j.com/blog/aggregate-stores-tour/ +https://en.wikipedia.org/wiki/Eventual_consistency +https://en.wikipedia.org/wiki/Distributed_transaction +https://en.wikipedia.org/wiki/Distributed_database +https://en.wikipedia.org/wiki/ACID +http://searchstorage.techtarget.com/definition/data-availability +https://datatechnologytoday.wordpress.com/2013/06/24/defining-database-availability/ +{% bibliography --file rpc %} diff --git a/chapter/6/consistency-crdts.md b/chapter/6/consistency-crdts.md deleted file mode 100644 index fcb49e7..0000000 --- a/chapter/6/consistency-crdts.md +++ /dev/null @@ -1,11 +0,0 @@ ---- -layout: page -title: "Consistency & CRDTs" -by: "Joe Schmoe and Mary Jane" ---- - -Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. {% cite Uniqueness --file consistency-crdts %} - -## References - -{% bibliography --file consistency-crdts %} \ No newline at end of file -- cgit v1.2.3 From 607c2f97c8c032b912bc64c553b43b694f10f693 Mon Sep 17 00:00:00 2001 From: msabhi Date: Thu, 17 Nov 2016 16:59:19 -0500 Subject: Update big-data.md --- chapter/8/big-data.md | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'chapter') diff --git a/chapter/8/big-data.md b/chapter/8/big-data.md index e2ff3e3..cf13efa 100644 --- a/chapter/8/big-data.md +++ b/chapter/8/big-data.md @@ -1,7 +1,7 @@ --- layout: page title: "Large Scale Parallel Data Processing" -by: "Joe Schmoe and Mary Jane" +by: "JingJing and Abhilash" --- Though highly efficient and one of the first major programming models for distributed batch processing, it too has a few limitations.
@@ -32,5 +32,7 @@ Apache Giraph is an open source implementation of Pregel in which new features l ## References +"Bulk synchronous model" http://www.cse.unt.edu/~tarau/teaching/parpro/papers/Bulk%20synchronous%20parallel.pdf. +"Pregel: A System for Large-Scale Graph Processing." +"One trillion edges: graph processing at Facebook-scale" -{% bibliography --file big-data %} -- cgit v1.2.3 From 37e2fe6098829d50679546be27d744487918d488 Mon Sep 17 00:00:00 2001 From: msabhi Date: Thu, 17 Nov 2016 16:59:38 -0500 Subject: Update big-data.md --- chapter/8/big-data.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'chapter') diff --git a/chapter/8/big-data.md b/chapter/8/big-data.md index cf13efa..f1e53e0 100644 --- a/chapter/8/big-data.md +++ b/chapter/8/big-data.md @@ -33,6 +33,6 @@ Apache Giraph is an open source implementation of Pregel in which new features l ## References "Bulk synchronous model" http://www.cse.unt.edu/~tarau/teaching/parpro/papers/Bulk%20synchronous%20parallel.pdf. -"Pregel: A System for Large-Scale Graph Processing." +"Pregel: A System for Large-Scale Graph Processing."
"One trillion edges: graph processing at Facebook-scale" -- cgit v1.2.3 From 3fc056ab35031b0c47df3a52c65a812428383250 Mon Sep 17 00:00:00 2001 From: msabhi Date: Thu, 17 Nov 2016 17:01:47 -0500 Subject: Update big-data.md --- chapter/8/big-data.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'chapter') diff --git a/chapter/8/big-data.md b/chapter/8/big-data.md index f1e53e0..4c1f060 100644 --- a/chapter/8/big-data.md +++ b/chapter/8/big-data.md @@ -34,5 +34,5 @@ Apache Giraph is an open source implementation of Pregel in which new features l ## References "Bulk synchronous model" http://www.cse.unt.edu/~tarau/teaching/parpro/papers/Bulk%20synchronous%20parallel.pdf. "Pregel: A System for Large-Scale Graph Processing."
-"One trillion edges: graph processing at Facebook-scale" +"One Trillion Edges: Graph Processing at Facebook-Scale." Accessed November 17, 2016. http://www.vldb.org/pvldb/vol8/p1804-ching.pdf. -- cgit v1.2.3 From b2870df267d95cf93754165ced84e2be4cbfe50a Mon Sep 17 00:00:00 2001 From: James Larisch Date: Thu, 17 Nov 2016 17:30:00 -0500 Subject: FIRST DRAFT --- chapter/7/langs-consistency.md | 115 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 111 insertions(+), 4 deletions(-) (limited to 'chapter') diff --git a/chapter/7/langs-consistency.md b/chapter/7/langs-consistency.md index 3ac6ceb..6eddfc5 100644 --- a/chapter/7/langs-consistency.md +++ b/chapter/7/langs-consistency.md @@ -1,11 +1,118 @@ --- layout: page -title: "Languages for Consistency" -by: "Joe Schmoe and Mary Jane" +title: "Languages Built For Consistency" +by: "James Larisch" --- +# Languages Built For Consistency + +## What's the problem? + As processors become expensive and the limits of Moore's Law are pushed, programmers lately find themselves in situations where they need to connect multiple computers together using a network cable. Perhaps it's not even due to cost or performance constraints; perhaps your company has servers in New York and San Fransisco, and there is some global state that requires synchronization across the country. Problems requiring solutions of this nature can be described as "distributed systems" problems. Your data / processing power / entry points are distributed for some reason. In many ways, web developers deal with distributed systems problems every day: your client and your server are in two different geographical locations, and thus, some coordination is required. + + As Aviral discussed in the previous section, many computer scientists have done a lot of thinking about the nature of distributed systems problems. As such, we realize that it's impossible to completely emulate the behavior of a single computational machine using multiple machines. For example, the network simply is not reliable - and if we wait for it to be reliable, we sacrifice things like timeliness. After discussing the Consistency/Availability/Partition-tolerance theorem, Section 6 discussed how we can make drill down into the CAP pyramid and choose the properties of our systems. As stated, we can't perfectly emulate a single computer, but once we accept that fact... there are plenty of things we *can* do! + +## The Shopping Cart + Let's bring all these theorem talk back to reality. Let's say you're working at a new e-commerce startup, and you'd like to revolutionize the electronic shopping cart. You'd like to give the customer the ability to do the following: + * Log in to the site and add a candle to the cart while traveling Beijing. + * Take a HyperLoop train (3 hours) from Beijing to Los Angeles. + * Log back into the site, remove the candle from their cart, and add a skateboard to their cart. + * Take another HyperLoop train from Los Angeles to Paris (5 hours). + * Log back into the site, add another skateboard, and checkout. + + Let's assume you have a server in every single country, and customers connect to the geographically closest server. + + If you only had 1 user of your website, this wouldn't be too hard. You could constantly send out messages to all of your servers and personally make sure the state of the customer's shopping cart is consistent across every single server. But what happens when you have millions of customers and thus millions of shopping carts? That would be impossible to keep track of personally. Luckily, you're a programmer - this can be automated! You simply need to make sure that all of your computers stay i-sync, so if the customer checks her cart in Beijing, then in Paris, she sees the same thing. + + But as Section 6 already explained, this is not so trivial. Messages between your servers in Beijing and Paris could get dropped, corrupted, reordered, duplicated, or delayed. Since you have no guarantees about when you'll be able to synchronize state between two servers, it's possible that the customer could see two different cart-states depending on which server she asks. + + If you're confident that the servers' state will eventually converge, you could present the user with an error message until the states have converged. That way, you know the user is looking at consistent state. [I may be overlapping too much with Aviral's section here. will wait until I see his draft before continuing. + + Mention Amazon's Dynamo + shopping cart. + +### Example + + Let's take a look at the following Javascript. For simplicity's sake, let's pretend users can only add things to their shopping cart. + + ```javascript + class Cart { + constructor(peers, socket) { + this.mySocket = socket; + this.peers = peers; + this.items = new Set(); + } + + addItem(item) { + this.items.add(item); + } + + synchronize() { + peers.forEach(function(peer) { + peer.send(items); + }); + } + + receiveState(items) { + this.items = this.items.union(items); + } + + run() { + var clientAddition = Interface.receiveInput(); // contrived + this.addItem(clientAddition); + var receivedState = mySocket.nonBlockingRead(); // contrived + if (receivedState !== undefined) { + this.receiveState(receivedState); + } + synchronize(); + sleep(10); + run(); + } + } + + // theoretical usage + + var socket = new UDPSocket(); // contrived + var cart = new Cart(peerSockets, socket); // peerSockets is an array of UDP sockets + cart.run(); + ``` + + Here is an (almost) fully functional shopping cart program. You can imagine this code running across multiple nodes scattered over the world. The meat of the program lies in the `run()` method. Let's walk through that: + 1. Program receives an addition to the cart from the user. + 2. Program adds that item to the current local state. + 3. Program checks its UDP socket for any messages. + 4. If it received one, it's means another instance of this program has sent us its state. What is state in this case? Simply a set of cart items. Let's handle this set of items by unioning it with our current set. + 5. Synchronize our current state by sending our state to every peer that we know about. + 6. Sleep for 10 seconds. + 7. Repeat! + + Hopefully it's clear that if a client adds an item to her cart in Beijing and then 10 seconds later checks her cart in Paris, she should see the same thing. Well, not exactly - remember, the network is unreliable, and Beijing's `synchronize` messages might have been dropped. But no worries! Beijing is `synchronizing` again in another 10 seconds. + + This is the *Strong Eventual Consistency* concept that Aviral introduced in Section 6. It's *eventual* because given a long enough timeline the clients' states will sync up: they are constantly trying to synchronize. [mention you can't remove things trivially, this is actually a CRDT, union is a monotonic operation] + +### The Intern + Unfortunately Jerry, the intern, has found your code. He'd like to make a few changes. He messes it up somehow. I'm not entirely sure how yet. + +### Guarantees + The original Javascript we wrote down exhibits the property from Section 6 known as *monotonicity*. The union operation ensures that a given node's state is always "greater than or equal to" the states of the other nodes. However, how can we be *sure* that this property is maintained throughout the development of this program? As we've seen, there's nothing stopping an intern from coming along, making a mindless change, and destroying this wonderful property. Ideally, we want to make it impossible (or at least very difficult) to write programs that violate this property. Or, at the very least, we want to make it very easy to write programs that maintain these types of properties. + + But where should these guarantees live? In the above Javascript example, the guarantees aren't guarantees at all, really. There's no restriction on what the programmer is allowed to do - the programmer has simply constructed a program that mirrors guarantees that she has modeled in her brain. In order to maintain properties such as *monotonicity*, she must constantly check the model in her brain against the code. We haven't really helped the programmer out that much - she has a lot of thinking to do. + + At the disk hardward level, there are certain mechanisms in place to ensure that data does not become corrupted when multiple things attempt to write bits to the same physical location. This is considered a type of IO-consistency. It doesn't help much with our shopping cart, but it's certainly necessary. These important guarantees facilitate the higher level abstractions by ensuring low-level safety. It would be unreasonable to expect our disks to enforce monotonicity, for example, since this would restrict usage of disks to monotonic programs only (more on this later!). But on the other hand, as we've seen, pushing the consistency to the application/programmer level is also unreasonable. Our tools should work for us. + + Why not push the consistency guarantees in between? Is there any reason why you as the programmer couldn't program using tools that facilitate these types of monotonic programs? If you're familiar with formal systems -- why not construct a formal system (programming language / library) in which every theorem (program) is formally guarunteed to be monotonic? If it's *impossible* to express a non-monotonic program, the programmer needn't worry about maintaining a direct mapping between their code and their mental model. + + Wouldn't it be great if tools like this existed? + +### Bloom + The dudes/dudettes at Berkeley seem to think so too. + +#### Restriction & Danger + [Bloom restricts you, it's different, and it's dangerous] + +### Lasp + [Library not language, embeddable, not dangerous] + Instead of trying to do it all (and accepting danger), it tries to be embeddable (and truly restrictive.) + -Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. {% cite Uniqueness --file langs-consistency %} ## References -{% bibliography --file langs-consistency %} \ No newline at end of file +{% bibliography --file langs-consistency %} -- cgit v1.2.3 From fc4363ffb32d2f0a25e572c6f0598d0c4ffeae09 Mon Sep 17 00:00:00 2001 From: Muzammil Date: Fri, 18 Nov 2016 11:28:39 -0500 Subject: Start --- chapter/1/rpc.md | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'chapter') diff --git a/chapter/1/rpc.md b/chapter/1/rpc.md index b4bce84..392d9ab 100644 --- a/chapter/1/rpc.md +++ b/chapter/1/rpc.md @@ -1,9 +1,11 @@ --- layout: page -title: "Remote Procedure Call" -by: "Joe Schmoe and Mary Jane" +title: "RPC is Not Dead: Rise, Fall and Rise of RPC" +by: "Muzammil Abdul Rehman and Paul Grosu" --- +## + Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. {% cite Uniqueness --file rpc %} ## References -- cgit v1.2.3 From 92c6d66ba7e4c8c837004932974264411130b979 Mon Sep 17 00:00:00 2001 From: Muzammil Date: Fri, 18 Nov 2016 12:59:45 -0500 Subject: Outline --- chapter/1/rpc.md | 238 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 237 insertions(+), 1 deletion(-) (limited to 'chapter') diff --git a/chapter/1/rpc.md b/chapter/1/rpc.md index 392d9ab..d1d48ed 100644 --- a/chapter/1/rpc.md +++ b/chapter/1/rpc.md @@ -4,7 +4,243 @@ title: "RPC is Not Dead: Rise, Fall and Rise of RPC" by: "Muzammil Abdul Rehman and Paul Grosu" --- -## +## Introduction + +*Remote Procedure Call* (RPC) is a design *paradigm* that allow two entities to communicate over a communication channel in a general request-response mechanism. It was initially built as a tool for outsourcing computation to a server in a distributed system, however, it has evolved over the years to build + +* Define what RPC is. +* The main idea of our paper: +* RPC was initially built as a tool for outsourcing computing. +* RPC is relevant to this day as a language for building and connecting scalable modularized, language-agnostic systems. +* It is the design and idea of remote computation, the driving force behind RPC, gave rise to truly distributed systems and different communication schemes between different entities. +* Why is RPC relevant? +* Microservices +* Asynchronous Bidirectional communication for connecting services and devices +* GRPC, Finagle, Thrift, SOAP, CORBA, RMI +* It has influenced other programming designs. +* Evolved with Time +* REST, HTTP + + +* The main idea of our paper: + + * RPC was initially built as a tool for outsourcing computing. + + * RPC is relevant to this day as a language for building and connecting scalable modularized, language-agnostic systems. + + * It is the design and idea of remote computation, the driving force behind RPC, gave rise to truly distributed systems and different communication schemes between different entities. + +* Why is RPC relevant? + + * Microservices + + * Asynchronous Bidirectional communication for connecting services and devices + + * GRPC, Finagle, Thrift, SOAP, CORBA, RMI + + * It has influenced other programming designs. + + * Evolved with Time + + * REST, HTTP + +## Remote Procedure Calls: + +* Local and remote endpoints, communication protocol. + + * Diagram. + +* Initially: there was a registry involved(now they’ve moved), kept an open connection,. + +* Now: + + * Security(Authentication and authorization) + + * Fault tolerance. + + * Asynchronously + + * Load Balancing + +* Examples: + + * One could view the internet as example of RPC.e.g TCP handshake(both act as server and client). + + * First: Google Maps API(REST) + + * SSL Handshake. + +Suggestions from Heather: + +* Be aware of Chris's thing: https://christophermeiklejohn.com/pl/2016/04/12/rpc.html + +* Thrift vs gRPC. + +## Evolution of RPC: + +* RPC has evolved from what it was originally proposed. + +* Chris’s thing: https://christophermeiklejohn.com/pl/2016/04/12/rpc.html + +* 1980’s + + * RPC origin. + + * Implementing RPC: [https://dl.acm.org/citation.cfm?id=357392](https://dl.acm.org/citation.cfm?id=357392) + + * The RPC thesis(Nelson) + + * More examples + +* 1990’s + + * The fall of RPC/Criticism of RPC + + * Limitations + + * [http://www.cs.vu.nl//~ast/afscheid/publications/euteco-1988.pdf](http://www.cs.vu.nl//~ast/afscheid/publications/euteco-1988.pdf) + + * Systems that use message passing. + +* 2000-* + +## Remote Method Invocation: + +* Pros and Cons + +## CORBA: + +* Pros and Cons + +## XML-RPC and SOAP: + +* Pros and Cons + +## Thrift: + +* Pros and Cons + +## Finagle: + +* Pros and Cons + +## gRPC: + +## Discussion 1(change heading): + +* gRPC vs Thrift (maybe also Finagle) + +## Applications: + +* RPC and shared state (Persistence Layer): + + * [http://ieeexplore.ieee.org/document/1302942/?arnumber=1302942&tag=1](http://ieeexplore.ieee.org/document/1302942/?arnumber=1302942&tag=1) + + * http://ieeexplore.ieee.org/document/918991/?arnumber=918991 + +* Grid computing: + + * https://link.springer.com/article/10.1023/A:1024083511032 + +* Mobile Systems(offloading and battery requirements): [https://link.springer.com/article/10.1007/s11036-012-0368-0](https://link.springer.com/article/10.1007/s11036-012-0368-0) + +* Embedded RPC: + + * https://dl.acm.org/citation.cfm?id=1127840 + +* Micro services architecture(ecosystem) + +* Streaming + +* RPC can be async + +* Shared State + +* microservices + +## RPC in Streaming Protocols: + +* Streaming requests and buffered responses + +## RPC in microservices ecosystem: + +* Creating new services. + +* Bootstrapping + +* Load balancing + + * Creating new services in Actor-Like model + + * Fault tolerance + + * Self-recovery + +* Business and Persistence Layer were combined and the Persistence layer is not shared anymore, where each endpoints has its own persistent state: + + * [https://help.sap.com/saphelp_nwmobile711/helpdata/de/7e/d1a40b5bc84868b1606ce0dc72d88b/content.htm](https://help.sap.com/saphelp_nwmobile711/helpdata/de/7e/d1a40b5bc84868b1606ce0dc72d88b/content.htm) + +## Security in RPC: + +* Initially it was separate. + + * Authentication, authorization issues have been resolved + +* Now embedded in the protocol + +* Security and Privacy in RPC + + * Bugs in the libraries. + + * Trust Issues between client and the server. + + * [http://static.usenix.org/publications/library/proceedings/sec02/full_papers/giffin/giffin_html/](http://static.usenix.org/publications/library/proceedings/sec02/full_papers/giffin/giffin_html/) + + * Brewer’s view: https://people.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf + + * E programming language: distributed object model/VAT + +## Discussion: + +* RPC vs REST and other services. RPC influence. + +* The future of RPC + + * Where it shines. Not in message passing. + +## Conclusions: + + Some conclusion. + +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Class: Functional Programming for Distributed Computing + +Theme: The idea of communicating and invoking remote functions for distributed computation. + +Target Audience: Networks background, and wants to learn RPC. + +-> RPC is not XYZ (HTTP, REST, …) though it has influenced. The + +RPC influence in XYZ design, though + +* RPC started in 1980’s and still continues as a relevant model of performing distributed computation, which initially was developed for a LAN and now can be globally implemented. + +* RPC started as a separate implements of REST, Streaming RPC, and now made possible of integration of all these implementations as a single abstraction for a user endpoint service. + + * (subsection) How RPC influenced other models of communication. + +* RPC Models: + + * One Server Model + +* Methods of invoking remote function. + +* Discuss the evolution and pitfalls as they developed to an optimized + +* Software-As-A-Service: End-User focused. + + Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. {% cite Uniqueness --file rpc %} -- cgit v1.2.3 From 912052c70b4a97e830815401bda0fc013b3dca2f Mon Sep 17 00:00:00 2001 From: Fangfan Li Date: Sun, 20 Nov 2016 16:45:11 -0500 Subject: draft streaming --- chapter/9/streaming.md | 44 ++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 42 insertions(+), 2 deletions(-) (limited to 'chapter') diff --git a/chapter/9/streaming.md b/chapter/9/streaming.md index cab6dea..44caca1 100644 --- a/chapter/9/streaming.md +++ b/chapter/9/streaming.md @@ -1,10 +1,50 @@ --- layout: page title: "Large Scale Streaming Processing" -by: "Joe Schmoe and Mary Jane" +by: "Fangfan Li" --- -Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. {% cite Uniqueness --file streaming %} +The previous chapter discusses the systems around batch layer, where the computation involves the pieces of data stored across the distributed file system. Those systems satisfy the requirements such as scalablibility and fault-tolerance for applications that deal with 'big data' stored in a distributed way. The batch processing systems are suitable for processing *static* datasets, where the input data do not change overtime during the whole process, thus the system can distribute the computation and perform synchronization assuming the inputs would stay the same during the whole computation. In such *static* model, the processing system can first *pull* data from the disk, and then perform the computation over the pulled data. However, a large number of networking applications are not *static*, instead, the data is constantly in motion, and the inputs would be provided as *stream*, as new data constantly arrives. In the *stream* model, data is *pushed* to the processor. This fundamental difference makes the traditional batch processing system un-suitable for streaming applications, as even the slightest change in the dataset would require the batch processer to *pull* the whole dataset and perform the computation again. Thus in this chapter, we would introduce the history and systems that are created for the streaming processing. + +There are many challenges for implementing large scale streaming processing system. Similar to large scale batch processing sytems, large scale streaming systems also have to deal with consistency and fault-tolenrace due to the distributed nature of those systems. Moreover, latency at the scale of several minutes is at most a nuisance in batch processing while latency is not as tolerable in large streaming processing. + +In the rest of this chapter, we would fist introduce the 1) History of streaming processing 2) How to represent the input data stream 3) What are the practices to process data stream 4) The state-of-the-art systems used by applications. + +1.Data in constant motion + +This concept of streaming data can trace back to TelegraphCQ, which aims at meeting the challenges that arise in handling large streams of continuous queries over high-volume, high-variable data streams. In contrast to trafitional view that data can be found statically in known locations, the authors of TelegraphCQ realized that data becomes fluid and being constantly moving and changing. The examples of applications that use *data in motion* include: event-based processing, query processing over streaming data sources such as network monitoring. TelegraphCQ is one example of the query processing systems that deals with data stream. The fundamental difference between TelegraphCQ to other traditional query system is the view of input data, instead of handling a query with detailed static data, TelegraphCQ has to react to the newly arrived data and process the queries *on-the-fly*. + +The important concepts of TelegraphCQ include *continuous queries*, where the queries are constantly running and as new data arrives, the processor would route it to the set of active queries that are listening. TelegraphCQ also uses *shared processing* to avoid the overhead of processing each query individually, the queries with some commonality can be combined together to improve the performance. + +TelegraphCQ shows the importance of modeling data as stream and how can we process such data stream. But TelegraphCQ was only implemented in a non-distributed prototype, we would then discuss how data steam is processed in a large scale. + +2.How to represent data stream + +Before dive into the details of the large scale processing, we would first introduce a few concepts: producer, processor and consumer. In this section, we would discuss the component between producers and processors-the data stream. + +We have been talking about the stream of data, but this is a bit under-specified, since the data can be collected from many producers (i.e. different monitors), how do we combine those data into actual streams and send the them to the processors? What does a data stream really look like? + +A natural view of a data stream can be an infinite sequence of tuples reading from a queue. However, a traditional queue would not be sufficient in large scale system since the consumed tuple might got lost or the consumer might fail thus it might request the previous tuple after a restart. The alternative queue design is a multi-consumer queue, for example Apache Kafka provides que that allows users to rewind the stream and replay everything from the point of failure, ensuring that the processed events are in the order of their origination. + +3.How to process data stream + +We would then talk about the processors that cosume the data stream. There are two main approaches in processing data stream. The first approach is the continuous queries model, similar TelegraphCQ, where the queries keep running and the arrival of data intiates the processing. Another approach is micro-batching, where the streaming computation becomes a series of stateless, deterministic batch computations on small time intervals, and the timer would triger the processing in those systems. We would discuss Apach Storm as an example for the fist design and Spark Streaming as an example for the second approach. + +a) Continuous queries(operators) + +Apache Storm + +b) Micro-batch + +Spark Streaming + +4.The systems being used nowadays, how ideas combined and products produced + +a) Twitter's Heron (real-time analytic platform that is fully API-compatible with Storm) + +b) Spotify (Google's DataFlow) + +{% cite Uniqueness --file streaming %} ## References -- cgit v1.2.3 From 4d364efe97868d268ed190e003d764571c537252 Mon Sep 17 00:00:00 2001 From: Muzammil Date: Mon, 21 Nov 2016 11:06:27 -0500 Subject: RPC: Commit 1 --- chapter/1/rpc.md | 201 ++++++++++++++++++------------------------------------- 1 file changed, 64 insertions(+), 137 deletions(-) (limited to 'chapter') diff --git a/chapter/1/rpc.md b/chapter/1/rpc.md index d1d48ed..a05022f 100644 --- a/chapter/1/rpc.md +++ b/chapter/1/rpc.md @@ -1,248 +1,175 @@ --- layout: page -title: "RPC is Not Dead: Rise, Fall and Rise of RPC" +title: "RPC is Not Dead: Rise, Fall and the Rise of RPC" by: "Muzammil Abdul Rehman and Paul Grosu" --- ## Introduction -*Remote Procedure Call* (RPC) is a design *paradigm* that allow two entities to communicate over a communication channel in a general request-response mechanism. It was initially built as a tool for outsourcing computation to a server in a distributed system, however, it has evolved over the years to build +*Remote Procedure Call* (RPC) is a design *paradigm* that allow two entities to communicate over a communication channel in a general request-response mechanism. It was initially built as a tool for outsourcing computation to a server in a distributed system, however, it has evolved over the years to build modular, scalable, distributed, language-agnostic ecosystem of applications. This RPC *paradigm* has been part of the driving force in creating truly revolutionizing distributed systems and giving rise to various communication schemes and protocols between diverse systems. -* Define what RPC is. -* The main idea of our paper: -* RPC was initially built as a tool for outsourcing computing. -* RPC is relevant to this day as a language for building and connecting scalable modularized, language-agnostic systems. -* It is the design and idea of remote computation, the driving force behind RPC, gave rise to truly distributed systems and different communication schemes between different entities. -* Why is RPC relevant? -* Microservices -* Asynchronous Bidirectional communication for connecting services and devices -* GRPC, Finagle, Thrift, SOAP, CORBA, RMI -* It has influenced other programming designs. -* Evolved with Time -* REST, HTTP +RPC *paradigm* has been implemented in various forms in our every-day systems. From lower level applications like Network File Systems{% cite sunnfs --file rpc %} and Remote Direct Memory Access{% cite rpcoverrdma --file rpc %} to access protocols to developing an ecosystem of microservices, RPC has been used everywhere. Some of the major examples of RPC include SunNFS{% cite sunnfs --file rpc %}, Twitter's Finagle{% cite finalge --file rpc %}, Apache Thrift{% cite thrift --file rpc %}, Java RMI{% cite rmipaper --file rpc %}, SOAP, CORBA{% cite corba --file rpc %}, Google's gRPC{% cite grpc --file rpc %}. +* adds paragraph about rise and fall -* The main idea of our paper: +RPC has evolved over the years. Starting off as a synchronous, insecure, request-response system, RPC has evolved into a secure, asynchronous, fault-tolerant, resilient *paradigm* that has influenced protocols and programming designs, like, HTTP, REST, and just about anything with a request-response system. It has transitioned to an asynchronous bidirectional communication for connecting services and devices across the internet. RPC has influenced various design paradigms and communication protocols. - * RPC was initially built as a tool for outsourcing computing. - - * RPC is relevant to this day as a language for building and connecting scalable modularized, language-agnostic systems. - - * It is the design and idea of remote computation, the driving force behind RPC, gave rise to truly distributed systems and different communication schemes between different entities. - -* Why is RPC relevant? - - * Microservices - - * Asynchronous Bidirectional communication for connecting services and devices - - * GRPC, Finagle, Thrift, SOAP, CORBA, RMI - - * It has influenced other programming designs. +## Remote Procedure Calls: - * Evolved with Time +* Diagram of RPC: Local and remote endpoints, communication protocol. - * REST, HTTP +*Remote Procedure Call paradigm* can be defined, at a high level, as a set of two language-agnostic communication *endpoints* connected over a network with one endpoint sending a request and the other endpoint generating a response based on that request. In the simplest terms, it's a request-response paradigm where the two *endpoints*/hosts have different *address space*. The host that requests a remote procedure can be referred to as *caller* and the host that responds to this can be referred to as *callee*. -## Remote Procedure Calls: +The *endpoints* in the RPC can either be a client and a server, two nodes in a peer-to-peer network, two hosts in a grid computation system, or even two microservices. The RPC communcation is not limited to two hosts, rather could have multiple hosts or *endpoints* involved {% cite anycastrpc --file rpc %}. -* Local and remote endpoints, communication protocol. +* explain the diagram here. - * Diagram. +One important feature of RPC is different *address space* {% cite implementingrpc --file rpc %} for all the endpoints, however, passing the locations to a global storage(Amazon S3, Microsoft Azure, Google Cloud Store) is not impossible.In RPC, all the hosts have separate *address spaces*. They can't share pointers or references to a memory location in one host. This *address space* isolation means that all the information is passed in the messages between the host communicating as a value (objects or variables) but not by reference. Since RPC is a *remote* procedure call, the values sent to the *remote* host cannot be pointers or references to a *local* memory. However, passing links to a global shared memory location is not impossible but rather dependent on the type of system(see *Applications* section for detail). -* Initially: there was a registry involved(now they’ve moved), kept an open connection,. +Originally, RPC was developed as a synchronous, language-specific marshalling service with a custom network protocol to outsource computation{% cite implementingrpc --file rpc %}. It had registry-system to register all the servers. One of the earliest RPC-based system{% cite implementingrpc --file rpc %} was implemented in the Cedar programming language in early 1980's. The goal of this system was to provide similar progamming semantics as local procedure calls. Developed for a LAN network with an inefficient network protocol and a *serialization* scheme to transfer information using the said network protocol, this system aimed at executing a *procedure*(also referred as *method* or a *function*) in a remote *address space*. The single-thread synchronous client and the server were written in an old *Cedar* programming language with a registry system used by the servers to *bind*(or register) their procedures. The clients used this registry system to find a specific server to execute their *remote* procedures. -* Now: +Modern RPC-based systems are language-agnostic, fault-tolerant, asynchronous, load-balanced systems. Authenticaiton and authorization to these systems have been added as needed along with other security features. - * Security(Authentication and authorization) +RPC programs have a network, therefore, they need to handle remote errors and be able to communication information successfully. Error handling generally varies and is categorized as *remote-host* or *network* failure handling. Depending on the type of the system, and the error, the caller(or the callee) return an error and these errors can be handled accordingly. For asynchronous RPC calls, it's possible to specify events to ensure progress. - * Fault tolerance. +RPC implementations use a *serialization*(also referred to as *marshalling* or *pickling*) scheme on top of an underlying communication protocol(traditionally TCP over IP). These *serialization* schemes allow both the caller *caller* and *callee* to become language agnostic allowing both these systems to be developed in parallel without any language restrictions. Some examples of serialization schemes are JSON, XML, or Protocol Buffers{% cite grpc --file rpc %}. - * Asynchronously +RPC allows different components of a larger system to be developed independtly of one another. The language-agnostic nature combined with a decoupling of some parts of the system allows the two components(caller and callee) to scale separately and add new functionalities. - * Load Balancing +Some RPC implementations have moved from a one-server model to a dynamically-created, load-balanced microservices. * Examples: - * One could view the internet as example of RPC.e.g TCP handshake(both act as server and client). - * First: Google Maps API(REST) - * SSL Handshake. -Suggestions from Heather: - -* Be aware of Chris's thing: https://christophermeiklejohn.com/pl/2016/04/12/rpc.html - -* Thrift vs gRPC. ## Evolution of RPC: -* RPC has evolved from what it was originally proposed. +RPC started in 1980’s and still continues as a relevant model of performing distributed computation, which initially was developed for a LAN and now can be globally implemented. +* RPC has evolved from what it was originally proposed. * Chris’s thing: https://christophermeiklejohn.com/pl/2016/04/12/rpc.html +* diagram(maybe not): 4 lines, (y-axis: -1 to 1, x-axis 1980's 2016) -* 1980’s +### The Rise: All Hail RPC - * RPC origin. +* RPC origin. - * Implementing RPC: [https://dl.acm.org/citation.cfm?id=357392](https://dl.acm.org/citation.cfm?id=357392) + * Implementing RPC: [https://dl.acm.org/citation.cfm?id=357392](https://dl.acm.org/citation.cfm?id=357392) + * The RPC thesis(Nelson) + * More examples - * The RPC thesis(Nelson) +### The Fall: RPC is Dead - * More examples +* The fall of RPC/Criticism of RPC + * Limitations + * http://www.cs.vu.nl//~ast/afscheid/publications/euteco-1988.pdf + * Systems that use message passing. -* 1990’s +### The Rise, Again: Long Live RPC - * The fall of RPC/Criticism of RPC +* gRPC +* XML SOAP +* Java RMI +* Finagle +* Thrift +* Apache Etch +* Sun RPC(ONC RPC) - * Limitations - * [http://www.cs.vu.nl//~ast/afscheid/publications/euteco-1988.pdf](http://www.cs.vu.nl//~ast/afscheid/publications/euteco-1988.pdf) +#### Java Remote Method Invocation: +Java RMI (Java Remote Method Invocation){% cite rmibook --file rpc %} is a Java implementation for performing RPC (Remote Procedure Calls) between a client and a server. The client using a stub passes via a socket connection the information over the network to the server. The Remote Object Registry (ROR){% cite rmipaper --file rpc %} on the server contains the references to objects that can be accessed remotely and through which the client will connect to. The client then can request of the invocation of methods on the server for processing the requested call and then responds with the answer. RMI provides some security by being encoded but not encrypted, though that can be augmented by tunneling over a secure connection or other methods. - * Systems that use message passing. -* 2000-* -## Remote Method Invocation: +#### CORBA: +CORBA (Common Object Request Broker Architecture){% cite corba --file rpc %} was created by the Object Management Group {% cite corbasite --file rpc %} to allow for language-agnostic communication among multiple computers. It is an object-oriented model defined via an Interface Definition Language (IDL) and the communication is managed through an Object Request Broker (ORB). Each client and server have an ORB by which they communicate. The benefits of CORBA is that it allows for multi-language implementations that can communicate with each other, but much of the criticism around CORBA relates to poor consistency among implementations. -* Pros and Cons - -## CORBA: - -* Pros and Cons +#### XML-RPC and SOAP: -## XML-RPC and SOAP: +SOAP (Simple Object Access Protocol) is a successor of XML-RPC as a web-services protocol for communicating between a client and server. It was initially designed by a group at Microsoft {% cite soaparticle1 --file rpc %}. The SOAP message is a XML-formatted message composed of an envelope inside which a header and a body is provided. The body of the message contains the request and response of the message, which is transmitted over HTTP or SMTP. The benefits of such a protocol is that provides the flexibility for transmission of multiple tranport protocol, though parsing such messages could become a bottleneck. -* Pros and Cons - -## Thrift: -* Pros and Cons +#### Thrift: +Thrift is a RPC created by Facebook and now part of the Apache Foundation {% cite thrift --file rpc %}. It is a language-agnostic IDL by which one generates the code for the client and server. It provides the opportunity for compressed serialization by customizing the protocol and the transport after the description file has been processed. -## Finagle: +#### Finagle: +Finagle was generated by Twitter and is an RPC written in Scala and can run on an JVM. It is based on three object types: Service objects, Filter objects and Future objects{% cite finagle --file rpc %}. The Future objects acts by asynchronously being requested for a computation that would return a response at some time in the future. The Service objects are an endpoint that will return a Future upon processing a request. A Filter object transforms requests for further processing in case additional customization is required from a request. +#### Open Network Computing RPC: * Pros and Cons -## gRPC: +#### gRPC: -## Discussion 1(change heading): +### The Contenders for the Throne: gRPC, Thrift or RMI * gRPC vs Thrift (maybe also Finagle) ## Applications: * RPC and shared state (Persistence Layer): - - * [http://ieeexplore.ieee.org/document/1302942/?arnumber=1302942&tag=1](http://ieeexplore.ieee.org/document/1302942/?arnumber=1302942&tag=1) - + * http://ieeexplore.ieee.org/document/1302942/?arnumber=1302942&tag=1 * http://ieeexplore.ieee.org/document/918991/?arnumber=918991 * Grid computing: - * https://link.springer.com/article/10.1023/A:1024083511032 -* Mobile Systems(offloading and battery requirements): [https://link.springer.com/article/10.1007/s11036-012-0368-0](https://link.springer.com/article/10.1007/s11036-012-0368-0) +* Mobile Systems(offloading and battery requirements): + * https://link.springer.com/article/10.1007/s11036-012-0368-0 * Embedded RPC: - * https://dl.acm.org/citation.cfm?id=1127840 * Micro services architecture(ecosystem) -* Streaming - * RPC can be async * Shared State * microservices -## RPC in Streaming Protocols: +* Futures and promises: RPC? -* Streaming requests and buffered responses +### Streaming requests and buffered responses -## RPC in microservices ecosystem: +### RPC in microservices ecosystem: + +RPC started as a separate implements of REST, Streaming RPC, and now made possible of integration of all these implementations as a single abstraction for a user endpoint service. * Creating new services. * Bootstrapping * Load balancing - * Creating new services in Actor-Like model - * Fault tolerance - * Self-recovery * Business and Persistence Layer were combined and the Persistence layer is not shared anymore, where each endpoints has its own persistent state: - - * [https://help.sap.com/saphelp_nwmobile711/helpdata/de/7e/d1a40b5bc84868b1606ce0dc72d88b/content.htm](https://help.sap.com/saphelp_nwmobile711/helpdata/de/7e/d1a40b5bc84868b1606ce0dc72d88b/content.htm) + * https://help.sap.com/saphelp_nwmobile711/helpdata/de/7e/d1a40b5bc84868b1606ce0dc72d88b/content.htm ## Security in RPC: - * Initially it was separate. - * Authentication, authorization issues have been resolved - * Now embedded in the protocol - * Security and Privacy in RPC - * Bugs in the libraries. - * Trust Issues between client and the server. - - * [http://static.usenix.org/publications/library/proceedings/sec02/full_papers/giffin/giffin_html/](http://static.usenix.org/publications/library/proceedings/sec02/full_papers/giffin/giffin_html/) - + * http://static.usenix.org/publications/library/proceedings/sec02/full_papers/giffin/giffin_html/ * Brewer’s view: https://people.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf - * E programming language: distributed object model/VAT ## Discussion: - * RPC vs REST and other services. RPC influence. - * The future of RPC - * Where it shines. Not in message passing. + * RPC is not XYZ (HTTP, REST, …) though it has influenced. -## Conclusions: - - Some conclusion. - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - -Class: Functional Programming for Distributed Computing - -Theme: The idea of communicating and invoking remote functions for distributed computation. - -Target Audience: Networks background, and wants to learn RPC. - --> RPC is not XYZ (HTTP, REST, …) though it has influenced. The - -RPC influence in XYZ design, though - -* RPC started in 1980’s and still continues as a relevant model of performing distributed computation, which initially was developed for a LAN and now can be globally implemented. - -* RPC started as a separate implements of REST, Streaming RPC, and now made possible of integration of all these implementations as a single abstraction for a user endpoint service. - - * (subsection) How RPC influenced other models of communication. - -* RPC Models: - - * One Server Model - -* Methods of invoking remote function. - -* Discuss the evolution and pitfalls as they developed to an optimized - -* Software-As-A-Service: End-User focused. - +## Conclusions(maybe not a heading): +RPC is not dead: long live the Remote Procedure calls. -Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. {% cite Uniqueness --file rpc %} ## References -- cgit v1.2.3 From 74473b82407edd9bc5f442103715985e1adc5859 Mon Sep 17 00:00:00 2001 From: Jingjing Ren Date: Thu, 24 Nov 2016 22:15:48 -0500 Subject: add mapreduce+flumejava+skeleton --- chapter/8/big-data.md | 113 ++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 106 insertions(+), 7 deletions(-) (limited to 'chapter') diff --git a/chapter/8/big-data.md b/chapter/8/big-data.md index 4c1f060..34a14f1 100644 --- a/chapter/8/big-data.md +++ b/chapter/8/big-data.md @@ -1,18 +1,116 @@ --- layout: page title: "Large Scale Parallel Data Processing" -by: "JingJing and Abhilash" +by: "Jingjing and Abhilash" --- +## Introduction +`JJ: Placeholder for introduction` The booming Internet has generated big data... + + +This chapter is organized in JJ: need to fill in more stuff + +- **Data paralleling**: + - MapReduce {% cite dean2008mapreduce --file big-data %} + - FlumeJava {% cite chambers2010flumejava --file big-data %} + - ... +- **Graph paralleling**: + - Pregel + - ... + +For each programming model, we will discuss the motivation, basic model, execution model, fault-tolerance and performance. + + +Ideas: get a table of what to include in the context +Idea: instead of data/graph, maybe add one more layer (unstructured vs. structured) + +# Data paralleling + +## MapReduce (2004) +MapReduce {% cite dean2008mapreduce --file big-data %} is a programming model that allows programmers to express the simple computations for terabytes data on thousands of commodity machines. + +**Basic & Examples** +This model applies to computations that are usually parallelizable: A `map` function can operate on each logical "record", this generates a set of intermediate key/value pairs, and then a `reduce` function applies on all values that share the same key and generate one or zero output value. + +Concretely, considering the problem of counting the number of occurrence of each word in a large collection of documents: each time, a `map` function that emits a word plus its count 1; a `reduce` function sums together all counts emitted for the same word + +``` +map(String key, String value): + // key: document name + // value: document contents + for each word w in value: + EmitIntermediate(w, "1"); + +reduce(String key, Iterator values): + // key: a word + // values: a list of counts + int result = 0; + for each v in values: + result += ParseInt(v); + Emit(AsString(result)); +``` + +Conceptually, the map and reduction functions have associated **types**: +``` +map (k1,v1) -> → list(k2,v2) +reduce (k2,list(v2)) -> list(v2) +``` +The input keys and values are drawn from a different domain than the output keys and values. The intermediate keys and values are from the same domain as the output keys and values. The implementation given by the authors essentially pass strings and it is users' responsibility to convert between strings and appropriate types. + +More formalized descriptions about the `map` and `reduce` function can be found in the original paper {% cite dean2008mapreduce --file big-data %}. + +**Execution** +At high level, when the user program calls *MapReduce* function, the input files are split into *M* pieces and it runs *map* function on corresponding splits; then intermediate key space are partitioned into *R* pieces using a partitioning function; After the reduce functions all successfully complete, the output is available in *R* files. The sequences of actions {% cite dean2008mapreduce --file big-data %} are shown in the figure below. We can see from label (4) and (5) that the intermediate key/value pairs are written/read into disks, this is a key to fault-tolerance in MapReduce model and also a bottleneck for more complex computation algorithms. + +
+ MapReduce Execution Overview +
+ + +**Fault Tolerance** +In this model, there are two parts that could fail: the master and the worker. +- Worker failure: The master pings every worker periodically and if no response in a certain amount of time, master marks the worker as failed and re-assign it to an idle worker. +- Master Failure: If the master fail, MapReduce function fails. The model itself assumes that master won't fail and they have separate mechanics to backup the master, which is out of the scope of our discussion. + +The output from distributed computation should be same as one from non-faulting sequential execution of the entire program. And the model relies on the atomic commits of map and reduce task outputs to achieve this. The basic idea is to create private temporary files and rename them only when the task has finished. + +There are some practices in this paper that make the model work very well in Google, one of them is **backup tasks**: when a MapReduce operation is close to completion, the master schedules backup executions of the remaining in-progress tasks ("straggler"). The task is marked as completed whenever either the primary or the backup execution completes. + +`JJ: what about other refinement: ` + +**Performance** +In the paper, the authors measure the performance of MapReduce on two computations running on a large cluster of machines. One computation *grep* through approximately 1TB of data. The other computation *sort* approximately 1TB of data. Both computations take in the order of a hundred seconds. In addition, the backup tasks do help largely reduce execution time. In the experiment where 200 out of 1746 tasks were intentionally killed, the scheduler was able to recover quickly and finish the whole computation for just a 5% increased time. +Overall, the performance is very good for conceptually unrelated computations. + + +## FlumeJava (2010) +Many real-world computations involves a pipeline of MapReduces, and this motivates additional management to chain together those separate MapReduce stages in an efficient way. FlumeJava {% cite chambers2010flumejava --file big-data %} can help build those pipelines and keep computations modular. At core, FlumeJava are a couple of classes that represent immutable parallel collections. It defers evaluation and optimization by internally constructing an execution plan dataflow graph. + +**Core Abstraction** + +- `PCollection`, a immutable bag of elements of type `T` +- `recordOf(...)`, specifies the encoding of the instance +- `PTable`, a subclass of `PCollection>`, a immutable multi-map with keys of type `K` and values of type `V` +- `parallelDo()`, can be expressed both the map and reduce parts of MapReduce +- `groupByKey()`, same as shuffle step of MapReduce `JJ: clear this in MapReduce` +- `combineValues()`, semantically a special case of `parallelDo()`, a combination of a MapReduce combiner and a MapReduce reducer, which is more efficient than doing all the combining in the reducer. + +**Deferred Evaluation** +`(JJ: placehoder) join, deferred/materialized; execution plan; figure 1 initial execution plan` + +**Optimizer** +`(JJ: placehoder) parallelDo Fusion; MSCR; overall goal to produce the fewest, most efficient MSCR operations in the final optimized plan` + +# Graph paralleling Though highly efficient and one of the first major programming models for distributed batch processing, it too has a few limitations.
Map Reduce doesn’t scale easily and is highly inefficient for iterative / graph algorithms like page rank and machine learning algorithms. Iterative algorithms requires programmer to explicitly handle the intermediate results (writing to disks). Hence, every iteration requires reading the input file and writing the results to the disk resulting in high disk I/O which is a performance bottleneck for any batch processing system.
Also graph algorithms require exchange of messages between vertices. In case of PageRank, every vertex requires the contributions from all its adjacent nodes to calculate its score. Map reduce currently lacks this model of message passing which makes it complex to reason about graph algorithms.
-### Bulk synchronous parallel model +## Bulk synchronous parallel model This model was introduced in 1980 to represent the hardware design features of parallel computers. It gained popularity as an alternative for map reduce since it addressed the above mentioned issues with map reduce to an extent.
-In BSP model -+ Computation consists of several steps called as supersets. +In BSP model ++ Computation consists of several steps called as supersets. + The processors involved have their own local memory and every processor is connected to other via a point-to-point communication. -+ At every superstep, a processor receives input at the beginning, performs computation and outputs at the end. ++ At every superstep, a processor receives input at the beginning, performs computation and outputs at the end. + Barrier synchronization synchs all the processors at the end of every superstep.
A notable feature of the model is the complete control on data through communication between every processor at every superstep. BSP preserves data in memory across supersteps and helps in reasoning iterative graph algorithms.
@@ -20,7 +118,7 @@ A notable feature of the model is the complete control on data through communica Pregel is highly scalable, fault-tolerant and can successfully represent larger complex graphs. Google claims the API becomes easy once a developer adopts “think like a vertex” mode. Pregel’s computation system is iterative and every iteration is called as superstep. The system takes a directed graph as input with properties assigned to both vertices and graph. At each superstep, all vertices executes in parallel, a user-defined function which represents the behavior of the vertex. The function has access to message sent to its vertex from the previous superstep S-1 and can update the state of the vertex, its edges, the graph and even send messages to other vertices which would receive in the next superstep S+1. The synchronization happens only between two supersteps. Every vertex is either active or inactive at any superstep. The iteration stops when all the vertices are inactive. A vertex can deactivate itself by voting for it and gets active if it receives a message. This asynchronous message passing feature eliminates the shared memory, remote reads and latency of Map reduce model.
Pregel’s API provides
-+ compute() method for the user to implement the logic to change the state of the graph/vertex at every superstep. It guarantees message delivery through an iterator at every superstep. ++ compute() method for the user to implement the logic to change the state of the graph/vertex at every superstep. It guarantees message delivery through an iterator at every superstep. + User defined handler for handling issues like missing destination vertex etc. + Combiners reduce the amount of messages passed from multiple vertices to the same destination vertex. + Aggregators capture the global state of the graph. A reduce operation combines the value given by every vertex to the aggregator. The combined/aggregated value is passed onto to all the vertices in the next superstep. @@ -32,7 +130,8 @@ Apache Giraph is an open source implementation of Pregel in which new features l ## References +{% bibliography --file big-data %} + "Bulk synchronous model" http://www.cse.unt.edu/~tarau/teaching/parpro/papers/Bulk%20synchronous%20parallel.pdf. "Pregel: A System for Large-Scale Graph Processing."
"One Trillion Edges: Graph Processing at Facebook-Scale." Accessed November 17, 2016. http://www.vldb.org/pvldb/vol8/p1804-ching.pdf. - -- cgit v1.2.3 From e2e0995491d8f3588d6214a2b21351063f17e9e3 Mon Sep 17 00:00:00 2001 From: Jingjing Ren Date: Thu, 24 Nov 2016 22:28:51 -0500 Subject: mv ref to .bib --- chapter/8/big-data.md | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-) (limited to 'chapter') diff --git a/chapter/8/big-data.md b/chapter/8/big-data.md index 34a14f1..d49d5a1 100644 --- a/chapter/8/big-data.md +++ b/chapter/8/big-data.md @@ -14,7 +14,7 @@ This chapter is organized in