DistOS 2014W Lecture 21 - Revision history

Ronak at 09:21, 25 April 2014

2014-04-25T09:21:15Z

@@ Line 30: / Line 30: @@
 == MapReduce ==
-A clever observation that a simple solution could solve most distributed problems.  It's all about programming to an abstraction that is efficiently parallelizable.  Note that it's not actually a simple solution, because it sits atop a mountain of code.  It requires something like BigTable which requires something like GFS, which requires something like Chubby. Despite this, it allows for programmers to easily do distributed computation using a simple framework that hides the messy details of parrallelization.
+MapReduce is a programming model and an associated implementation for processing and generating large data sets.A clever observation that a simple solution could solve most distributed problems.  It's all about programming to an abstraction that is efficiently parallelizable.  Note that it's not actually a simple solution, because it sits atop a mountain of code.  It requires something like BigTable which requires something like GFS, which requires something like Chubby. Despite this, it allows for programmers to easily do distributed computation using a simple framework that hides the messy details of parrallelization.
 * Restricted programming model
@@ Line 50: / Line 50: @@
 ** Map takes a single input key-value pair (eg. a named document) and converts it to an intermediate (k,v) representation. A list of new key-values.
 ** Reduce: Take the intermediate representation and merge the values.
 === Implementation ===

Cdelahou: /* Naiad */

2014-04-20T02:57:39Z

Naiad

← Older revision		Revision as of 02:57, 20 April 2014
Line 72:		Line 72:
	* Their model is super complicated. It doesn't minimize our cognitive load.		* Their model is super complicated. It doesn't minimize our cognitive load.
	* Doesn't scale at all. After about 40 nodes, there is no improvement in performance. MapReduce can scale to thousands of nodes and scales forever.		* Doesn't scale at all. After about 40 nodes, there is no improvement in performance. MapReduce can scale to thousands of nodes and scales forever.
	* Nobody wants to use it because the abstraction ~~sucks~~.		* Nobody wants to use it because the abstraction is complicated.

Cdelahou: Niad

2014-04-20T02:50:40Z

Niad

← Older revision		Revision as of 02:50, 20 April 2014
Line 61:		Line 61:

	Where MapReduce was suited for a specific family of solutions, Naiad tries to generalize the solution to apply parallelization to a much wider family. Naiad supports MapReduce style solutions, but also many other solutions. However, the tradeoff was simplicity. It's like we took MapReduce and took away its low barrier to entry. The idea is to create a constrained graph that can easily be parallelized.		Where MapReduce was suited for a specific family of solutions, Naiad tries to generalize the solution to apply parallelization to a much wider family. Naiad supports MapReduce style solutions, but also many other solutions. However, the tradeoff was simplicity. It's like we took MapReduce and took away its low barrier to entry. The idea is to create a constrained graph that can easily be parallelized.
	* ~~Complicated~~ than Map Reduce
			* More complicated than Map Reduce
	* Talks about Timely dataflow graphs		* Talks about Timely dataflow graphs
	* Its all about Graph algorithms - Graph abstraction		* Its all about Graph algorithms - Graph abstraction
	* Restrictions on graphs so that they can be mapped to parllel computation		* Restrictions on graphs so that they can be mapped to parllel computation
	* How to fit anything to this model is a big question.		* How to fit anything to this model is a big question.
	* More general than map reduce		* More general than map reduce.
	* ~~Not very useful~~.
			* After reading the MapReduce paper, you could easily write a map reduce job. After reading the Naiad, you can't. Naiad is super complicated.
			* Their model is super complicated. It doesn't minimize our cognitive load.
			* Doesn't scale at all. After about 40 nodes, there is no improvement in performance. MapReduce can scale to thousands of nodes and scales forever.
			* Nobody wants to use it because the abstraction sucks.

Cdelahou: More on M/R

2014-04-20T02:43:08Z

Cdelahou: MapReduce stuff

2014-04-20T02:40:45Z

MapReduce stuff

← Older revision		Revision as of 02:40, 20 April 2014
Line 30:		Line 30:
	== MapReduce ==		== MapReduce ==

	A clever observation that a simple solution could solve most distributed problems. It's all about programming to an abstraction that is efficiently parallelizable. Note that it's not actually a simple solution, because it sits atop a mountain of code. It requires something like ~~BigTables~~ which requires something like GFS, which requires something like Chubby.		A clever observation that a simple solution could solve most distributed problems. It's all about programming to an abstraction that is efficiently parallelizable. Note that it's not actually a simple solution, because it sits atop a mountain of code. It requires something like BigTable which requires something like GFS, which requires something like Chubby. Despite this, it allows for programmers to easily do distributed computation using a simple framework that hides the messy details of parrallelization.

			* Restricted programming model
	* ~~Simplification~~
	* Interestingly large scale problems can be implemented with this		* Interestingly large scale problems can be implemented with this
	* Easy to program, powerful for certain classes, it scales like no ones business.		* Easy to program, powerful for certain classes, it scales like no ones business.
	* Kind of empoweraged model		* Kind of empoweraged model
	Programming to an abstraction that is efficiently parllel. We have learnt all about infrastructure until now.		Programming to an abstraction that is efficiently parllel. We have learnt all about infrastructure until now.
	Classic OS abstractions were about files.		Classic OS abstractions were about files. Now we used programming abstraction.

			Example: word frequency in a document.

			=== How does it work? ===

			* Two steps. Map and Reduce. The user writes theses.
			** Map takes a single input key-value pair (eg. a named document) and converts it to an intermediate (k,v) representation. A list of new key-values.
			** Reduce: Take the intermediate representation and merge the values.

			=== Implementation ===

			* Uses commodity HW and GFS.
			* Master/Slave relationship amongst machines. Master delegates tasks to slaves.
			* Intermediate representation saved as files.
			* Many MapReduce jobs can happen in sequence.

	== Naiad ==		== Naiad ==

Nelaturuk: /* Test */

2014-03-27T21:01:15Z

Test

← Older revision		Revision as of 21:01, 27 March 2014
Line 6:		Line 6:
	* marked mostly on presentation, not content		* marked mostly on presentation, not content
	* basically we want to communicate the basic structure of the paper, and do so in a way that isn't boring		* basically we want to communicate the basic structure of the paper, and do so in a way that isn't boring

	~~=== Test ===~~

	=== Content ===		=== Content ===

Nelaturuk: /* Marking */

2014-03-27T21:00:58Z

Marking

← Older revision		Revision as of 21:00, 27 March 2014
Line 6:		Line 6:
	* marked mostly on presentation, not content		* marked mostly on presentation, not content
	* basically we want to communicate the basic structure of the paper, and do so in a way that isn't boring		* basically we want to communicate the basic structure of the paper, and do so in a way that isn't boring

			=== Test ===

	=== Content ===		=== Content ===

Nelaturuk: /* Naiad */

2014-03-27T15:21:51Z

Naiad

← Older revision		Revision as of 15:21, 27 March 2014
Line 43:		Line 43:

	Where MapReduce was suited for a specific family of solutions, Naiad tries to generalize the solution to apply parallelization to a much wider family. Naiad supports MapReduce style solutions, but also many other solutions. However, the tradeoff was simplicity. It's like we took MapReduce and took away its low barrier to entry. The idea is to create a constrained graph that can easily be parallelized.		Where MapReduce was suited for a specific family of solutions, Naiad tries to generalize the solution to apply parallelization to a much wider family. Naiad supports MapReduce style solutions, but also many other solutions. However, the tradeoff was simplicity. It's like we took MapReduce and took away its low barrier to entry. The idea is to create a constrained graph that can easily be parallelized.
			* Complicated than Map Reduce
			* Talks about Timely dataflow graphs
			* Its all about Graph algorithms - Graph abstraction
			* Restrictions on graphs so that they can be mapped to parllel computation
			* How to fit anything to this model is a big question.
			* More general than map reduce
			* Not very useful.

Nelaturuk: /* MapReduce */

2014-03-27T15:21:37Z

MapReduce

← Older revision		Revision as of 15:21, 27 March 2014
Line 31:		Line 31:

	A clever observation that a simple solution could solve most distributed problems. It's all about programming to an abstraction that is efficiently parallelizable. Note that it's not actually a simple solution, because it sits atop a mountain of code. It requires something like BigTables which requires something like GFS, which requires something like Chubby.		A clever observation that a simple solution could solve most distributed problems. It's all about programming to an abstraction that is efficiently parallelizable. Note that it's not actually a simple solution, because it sits atop a mountain of code. It requires something like BigTables which requires something like GFS, which requires something like Chubby.


			* Simplification
			* Interestingly large scale problems can be implemented with this
			* Easy to program, powerful for certain classes, it scales like no ones business.
			* Kind of empoweraged model
			Programming to an abstraction that is efficiently parllel. We have learnt all about infrastructure until now.
			Classic OS abstractions were about files.

	== Naiad ==		== Naiad ==

	Where MapReduce was suited for a specific family of solutions, Naiad tries to generalize the solution to apply parallelization to a much wider family. Naiad supports MapReduce style solutions, but also many other solutions. However, the tradeoff was simplicity. It's like we took MapReduce and took away its low barrier to entry. The idea is to create a constrained graph that can easily be parallelized.		Where MapReduce was suited for a specific family of solutions, Naiad tries to generalize the solution to apply parallelization to a much wider family. Naiad supports MapReduce style solutions, but also many other solutions. However, the tradeoff was simplicity. It's like we took MapReduce and took away its low barrier to entry. The idea is to create a constrained graph that can easily be parallelized.

Sdp: Added MapReduce notes

2014-03-27T15:16:55Z

Added MapReduce notes

@@ Line 26: / Line 26: @@
 * don't read slides
 * no whole sentences on slides
-* look at talk by Mark Shuttleworth
+* look at talks by Mark Shuttleworth

← Older revision		Revision as of 02:43, 20 April 2014
Line 34:		Line 34:
	* Restricted programming model		* Restricted programming model
	* Interestingly large scale problems can be implemented with this		* Interestingly large scale problems can be implemented with this
	* Easy to program, powerful for certain classes, it scales like ~~no ones business~~.		* Easy to program, powerful for certain classes of problems, it scales well.
	* ~~Kind of empoweraged model~~		* MapReduce job model is VERY limited though. You can't do things like simulations.
			* MapReduce is problem specific.
			** Naiad is less problem specific and allows you to do more.

	Programming to an abstraction that is efficiently parllel. We have learnt all about infrastructure until now.		Programming to an abstraction that is efficiently parllel. We have learnt all about infrastructure until now.
	Classic OS abstractions were about files. Now we used programming abstraction.		Classic OS abstractions were about files. Now we used programming abstraction.

	Example: word frequency in a document.		Example: word frequency in a document.


	=== How does it work? ===		=== How does it work? ===