{"action":"created","comment":{"url":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/comments/94471897","pull_request_review_id":14997971,"id":94471897,"diff_hunk":"@@ -1,31 +1,46 @@\n ---\n layout: page\n title:  \"Large Scale Parallel Data Processing\"\n-by: \"Jingjing and Abhilash\"\n+by: \"Jingjing and Abhilash Mysore Somashekar\"\n ---\n ## Introduction\n-The growth of Internet has generated the so-called big data(terabytes or petabytes). It is not possible to fit them into a single machine or process them with one single program. Often the computation has to be done fast enough to provide practical services. A common approach taken by tech giants like Google, Yahoo, Facebook is to process big data across clusters of commodity machines. Many of the computations are conceptually straightforward, and Google proposed the MapReduce model to abstract the logic and proved to be simple and powerful. From then on, the idea inspired lots of other programming models. In this chapter, we will present how programming models evolve over time, why their execution engines are designed in certain ways, and underlying ecosystem that supports each developing thread.\n+The growth of Internet has generated the so-called big data(terabytes or petabytes). It is not possible to fit them into a single machine or process them with one single program. Often the computation has to be done fast enough to provide practical services. A common approach taken by tech giants like Google, Yahoo, Facebook is to process big data across clusters of commodity machines. Many of the computations are conceptually straightforward, and Google proposed the MapReduce framework, which separates the programming logic and underlying execution details(data distribution, fault tolerance and scheduling). The model has been proved to be simple and powerful, and from then on, the idea inspired many other programming models.\n+\n+This chapter covers the original idea of MapReduce framework, split into two sections: programming model and execution model. For each section, we first introduce the original design for MapReduce and its limitations. Then we present follow-up models(e.g. FlumeJava) to either work around these limitations or other models (e.g. Dryad, Spark) that take alternative designs to circumvent inabilities of MapReduce. We also review declarative programming interfaces(Pig, Hive, SparkSQL) built on top of MapReduce frameworks to provide programming efficiency and optimization benefits. In the last section, we briefly outline the ecosystem of Hadoop and Spark.\n+\n+Outline  \n+1. Programming Models\n+  - 1.1 Data parallelism: MapReduce, FlumeJava, Dryad, Spark\n+  - 1.2 Querying: Hive/HiveQL, Pig Latin, SparkSQL\n+  - 1.3 Large-scale parallelism on Graph: BSP, GraphX  \n+2. Execution Models\n+  - 2.1 MapReduce execution model\n+  - 2.2 Spark execution model\n+  - 2.3 Hive execution model\n+  - 2.4 SparkSQL execution model   \n+3. Big Data Ecosystem:\n+  - 3.1 Hadoop ecosystem\n+  - 3.2 Spark ecosystem\n+\n ## 1 Programming Models\n ### 1.1 Data parallelism\n-*Data parallelism* is to run a single operation on different pieces of the data on different machines in parallel. Comparably, a sequential computation looks like *\"for all elements in the dataset, do operation A\"*, where dataset could be in the order of terabytes or petabytes aka. big data and one wants to scale up the processing. The challenges to do this sequential computation in a parallelized manner include how to abstract the different types of computations in a simple and correct way, how to distribute the data to hundreds/thousands of machines, how to handle failures and so on.\n+*Data parallelism* is, given a dataset, the simultaneous execution on multiple machines or threads of the same function across groups of elements of a dataset. Data parallelism can also be thought of as a subset of SIMD (\"single instruction, multiple data\") execution, a class of parallel execution in Flynn's taxonomy. Comparably, one could think a sequential computation as *\"for all elements in the dataset, do operation A\"* on a single big dataset, whose size can reach to terabytes or petabytes. The challenges to doing this sequential computation in a parallelized manner include how to abstract the different types of computations in a simple and correct way, how to distribute the data to hundreds/thousands of machines or clusters, how to schedule tasks and handle failures and so on.\n \n <figure class=\"main-container\">\n   <img src=\"{{ site.baseurl }}/resources/img/data-parallelism.png\" alt=\"Data Parallelism\" />\n </figure>\n \n-**MapReduce** {% cite dean2008mapreduce  --file big-data %} is a programming model proposed by Google to initially satisfy their demand of large-scale indexing for web search service. It provides a simple user program interface: *map* and *reduce* functions and automatically handles the parallelization and distribution.\n-\n-The MapReduce model is simple and powerful, and quickly became very popular among developers. However, when developers start writing real-world applications, they often end up chaining together MapReduce stages. The pipeline of MapReduce forces programmers to write additional coordinating codes, i.e. the development style goes backward from simple logic computation abstraction to lower-level coordination management. In map reduce, programmers need to reason about data representation on disk or in storage services such as a database. Besides, developers need to clearly understand the map reduce execution model  to do manual optimizations[ref]. **FlumeJava** {%cite chambers2010flumejava --file big-data%} library intends to provide support for developing data-parallel pipelines by abstracting away the complexity involved in data representation and implicitly handling the optimizations. It defers the evaluation, constructs an execution plan from parallel collections, optimizes the plan, and then executes underlying MR primitives. The optimized execution is comparable with hand-optimized pipelines, so there's no need to write raw MR programs directly.\n+**MapReduce** {% cite dean2008mapreduce  --file big-data %} is a programming model proposed by Google to initially satisfy their demand of large-scale indexing for web search service. It provides a simple user program interface: *map* and *reduce* functions and automatically handles the parallelization and distribution. The underlying execution systems can provide fault tolerance and scheduling.\n \n-An alternative approach to data prallelism is to construct complex, multi-step directed acyclic graphs (DAGs) of work from the user instructions and execute those DAGs all at once. This eliminates the costly synchronization required by MapReduce and makes applications much easier to build and reason about. Dryad, a Microsoft Research project used internally at Microsoft was one such project which leveraged this model of computation.\n+The MapReduce model is simple and powerful and quickly becomes very popular among developers. However, when developers start writing real-world applications, they often end up writing many boilerplates and chaining together these stages. Moreover, The pipeline of MapReduce forces them to write additional coordinating codes, i.e., the development style goes backward from simple logic computation abstraction to lower-level coordination management. As we will discuss in *section 2 execution model*, MapReduce writes all data into disk after each stage, which causes severe delays. Programmers need to do manual optimizations for targeted performance, and this again requires them to understand the underlying execution model. The whole process soon becomes cumbersome. **FlumeJava** {%cite chambers2010flumejava --file big-data%} library intends to provide support for developing data-parallel pipelines by abstracting away the complexity involved in data representation and implicitly handling the optimizations. It defers the evaluation, constructs an execution plan from parallel collections, optimizes the plan, and then executes underlying MR primitives. The optimized execution is comparable with hand-optimized pipelines, thus there is no much need to write raw MR programs directly.","path":"chapter/8/big-data.md","position":42,"original_position":42,"commit_id":"b8ea0136877b83801707f85ca902ce033fffe360","original_commit_id":"b8ea0136877b83801707f85ca902ce033fffe360","user":{"login":"cmeiklejohn","id":44939,"avatar_url":"https://avatars.githubusercontent.com/u/44939?v=3","gravatar_id":"","url":"https://api.github.com/users/cmeiklejohn","html_url":"https://github.com/cmeiklejohn","followers_url":"https://api.github.com/users/cmeiklejohn/followers","following_url":"https://api.github.com/users/cmeiklejohn/following{/other_user}","gists_url":"https://api.github.com/users/cmeiklejohn/gists{/gist_id}","starred_url":"https://api.github.com/users/cmeiklejohn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cmeiklejohn/subscriptions","organizations_url":"https://api.github.com/users/cmeiklejohn/orgs","repos_url":"https://api.github.com/users/cmeiklejohn/repos","events_url":"https://api.github.com/users/cmeiklejohn/events{/privacy}","received_events_url":"https://api.github.com/users/cmeiklejohn/received_events","type":"User","site_admin":false},"body":"\"coordinating codes\" => \"coordinating code\"","created_at":"2017-01-03T19:52:47Z","updated_at":"2017-01-03T20:01:13Z","html_url":"https://github.com/heathermiller/dist-prog-book/pull/15#discussion_r94471897","pull_request_url":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/15","_links":{"self":{"href":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/comments/94471897"},"html":{"href":"https://github.com/heathermiller/dist-prog-book/pull/15#discussion_r94471897"},"pull_request":{"href":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/15"}}},"pull_request":{"url":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/15","id":98412057,"html_url":"https://github.com/heathermiller/dist-prog-book/pull/15","diff_url":"https://github.com/heathermiller/dist-prog-book/pull/15.diff","patch_url":"https://github.com/heathermiller/dist-prog-book/pull/15.patch","issue_url":"https://api.github.com/repos/heathermiller/dist-prog-book/issues/15","number":15,"state":"closed","locked":false,"title":"big-data v2","user":{"login":"Eyasics","id":4318390,"avatar_url":"https://avatars.githubusercontent.com/u/4318390?v=3","gravatar_id":"","url":"https://api.github.com/users/Eyasics","html_url":"https://github.com/Eyasics","followers_url":"https://api.github.com/users/Eyasics/followers","following_url":"https://api.github.com/users/Eyasics/following{/other_user}","gists_url":"https://api.github.com/users/Eyasics/gists{/gist_id}","starred_url":"https://api.github.com/users/Eyasics/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Eyasics/subscriptions","organizations_url":"https://api.github.com/users/Eyasics/orgs","repos_url":"https://api.github.com/users/Eyasics/repos","events_url":"https://api.github.com/users/Eyasics/events{/privacy}","received_events_url":"https://api.github.com/users/Eyasics/received_events","type":"User","site_admin":false},"body":"ready for final","created_at":"2016-12-16T22:17:05Z","updated_at":"2017-01-03T20:01:13Z","closed_at":"2016-12-18T21:02:28Z","merged_at":"2016-12-18T21:02:28Z","merge_commit_sha":"661a6b615fbf9ede249cd4d929279ac28e669df5","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/15/commits","review_comments_url":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/15/comments","review_comment_url":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/comments{/number}","comments_url":"https://api.github.com/repos/heathermiller/dist-prog-book/issues/15/comments","statuses_url":"https://api.github.com/repos/heathermiller/dist-prog-book/statuses/b8ea0136877b83801707f85ca902ce033fffe360","head":{"label":"heathermiller:Jingjing-Abhilash-bigdata-v2","ref":"Jingjing-Abhilash-bigdata-v2","sha":"b8ea0136877b83801707f85ca902ce033fffe360","user":{"login":"heathermiller","id":687163,"avatar_url":"https://avatars.githubusercontent.com/u/687163?v=3","gravatar_id":"","url":"https://api.github.com/users/heathermiller","html_url":"https://github.com/heathermiller","followers_url":"https://api.github.com/users/heathermiller/followers","following_url":"https://api.github.com/users/heathermiller/following{/other_user}","gists_url":"https://api.github.com/users/heathermiller/gists{/gist_id}","starred_url":"https://api.github.com/users/heathermiller/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/heathermiller/subscriptions","organizations_url":"https://api.github.com/users/heathermiller/orgs","repos_url":"https://api.github.com/users/heathermiller/repos","events_url":"https://api.github.com/users/heathermiller/events{/privacy}","received_events_url":"https://api.github.com/users/heathermiller/received_events","type":"User","site_admin":false},"repo":{"id":71059722,"name":"dist-prog-book","full_name":"heathermiller/dist-prog-book","owner":{"login":"heathermiller","id":687163,"avatar_url":"https://avatars.githubusercontent.com/u/687163?v=3","gravatar_id":"","url":"https://api.github.com/users/heathermiller","html_url":"https://github.com/heathermiller","followers_url":"https://api.github.com/users/heathermiller/followers","following_url":"https://api.github.com/users/heathermiller/following{/other_user}","gists_url":"https://api.github.com/users/heathermiller/gists{/gist_id}","starred_url":"https://api.github.com/users/heathermiller/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/heathermiller/subscriptions","organizations_url":"https://api.github.com/users/heathermiller/orgs","repos_url":"https://api.github.com/users/heathermiller/repos","events_url":"https://api.github.com/users/heathermiller/events{/privacy}","received_events_url":"https://api.github.com/users/heathermiller/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/heathermiller/dist-prog-book","description":null,"fork":false,"url":"https://api.github.com/repos/heathermiller/dist-prog-book","forks_url":"https://api.github.com/repos/heathermiller/dist-prog-book/forks","keys_url":"https://api.github.com/repos/heathermiller/dist-prog-book/keys{/key_id}","collaborators_url":"https://api.github.com/repos/heathermiller/dist-prog-book/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/heathermiller/dist-prog-book/teams","hooks_url":"https://api.github.com/repos/heathermiller/dist-prog-book/hooks","issue_events_url":"https://api.github.com/repos/heathermiller/dist-prog-book/issues/events{/number}","events_url":"https://api.github.com/repos/heathermiller/dist-prog-book/events","assignees_url":"https://api.github.com/repos/heathermiller/dist-prog-book/assignees{/user}","branches_url":"https://api.github.com/repos/heathermiller/dist-prog-book/branches{/branch}","tags_url":"https://api.github.com/repos/heathermiller/dist-prog-book/tags","blobs_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/refs{/sha}","trees_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/trees{/sha}","statuses_url":"https://api.github.com/repos/heathermiller/dist-prog-book/statuses/{sha}","languages_url":"https://api.github.com/repos/heathermiller/dist-prog-book/languages","stargazers_url":"https://api.github.com/repos/heathermiller/dist-prog-book/stargazers","contributors_url":"https://api.github.com/repos/heathermiller/dist-prog-book/contributors","subscribers_url":"https://api.github.com/repos/heathermiller/dist-prog-book/subscribers","subscription_url":"https://api.github.com/repos/heathermiller/dist-prog-book/subscription","commits_url":"https://api.github.com/repos/heathermiller/dist-prog-book/commits{/sha}","git_commits_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/commits{/sha}","comments_url":"https://api.github.com/repos/heathermiller/dist-prog-book/comments{/number}","issue_comment_url":"https://api.github.com/repos/heathermiller/dist-prog-book/issues/comments{/number}","contents_url":"https://api.github.com/repos/heathermiller/dist-prog-book/contents/{+path}","compare_url":"https://api.github.com/repos/heathermiller/dist-prog-book/compare/{base}...{head}","merges_url":"https://api.github.com/repos/heathermiller/dist-prog-book/merges","archive_url":"https://api.github.com/repos/heathermiller/dist-prog-book/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/heathermiller/dist-prog-book/downloads","issues_url":"https://api.github.com/repos/heathermiller/dist-prog-book/issues{/number}","pulls_url":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls{/number}","milestones_url":"https://api.github.com/repos/heathermiller/dist-prog-book/milestones{/number}","notifications_url":"https://api.github.com/repos/heathermiller/dist-prog-book/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/heathermiller/dist-prog-book/labels{/name}","releases_url":"https://api.github.com/repos/heathermiller/dist-prog-book/releases{/id}","deployments_url":"https://api.github.com/repos/heathermiller/dist-prog-book/deployments","created_at":"2016-10-16T15:37:26Z","updated_at":"2017-01-03T17:27:09Z","pushed_at":"2017-01-03T17:27:07Z","git_url":"git://github.com/heathermiller/dist-prog-book.git","ssh_url":"git@github.com:heathermiller/dist-prog-book.git","clone_url":"https://github.com/heathermiller/dist-prog-book.git","svn_url":"https://github.com/heathermiller/dist-prog-book","homepage":null,"size":19568,"stargazers_count":347,"watchers_count":347,"language":"CSS","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":28,"mirror_url":null,"open_issues_count":3,"forks":28,"open_issues":3,"watchers":347,"default_branch":"master"}},"base":{"label":"heathermiller:master","ref":"master","sha":"5b299d189255e04ca3481a15e15b2a2e10b29b42","user":{"login":"heathermiller","id":687163,"avatar_url":"https://avatars.githubusercontent.com/u/687163?v=3","gravatar_id":"","url":"https://api.github.com/users/heathermiller","html_url":"https://github.com/heathermiller","followers_url":"https://api.github.com/users/heathermiller/followers","following_url":"https://api.github.com/users/heathermiller/following{/other_user}","gists_url":"https://api.github.com/users/heathermiller/gists{/gist_id}","starred_url":"https://api.github.com/users/heathermiller/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/heathermiller/subscriptions","organizations_url":"https://api.github.com/users/heathermiller/orgs","repos_url":"https://api.github.com/users/heathermiller/repos","events_url":"https://api.github.com/users/heathermiller/events{/privacy}","received_events_url":"https://api.github.com/users/heathermiller/received_events","type":"User","site_admin":false},"repo":{"id":71059722,"name":"dist-prog-book","full_name":"heathermiller/dist-prog-book","owner":{"login":"heathermiller","id":687163,"avatar_url":"https://avatars.githubusercontent.com/u/687163?v=3","gravatar_id":"","url":"https://api.github.com/users/heathermiller","html_url":"https://github.com/heathermiller","followers_url":"https://api.github.com/users/heathermiller/followers","following_url":"https://api.github.com/users/heathermiller/following{/other_user}","gists_url":"https://api.github.com/users/heathermiller/gists{/gist_id}","starred_url":"https://api.github.com/users/heathermiller/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/heathermiller/subscriptions","organizations_url":"https://api.github.com/users/heathermiller/orgs","repos_url":"https://api.github.com/users/heathermiller/repos","events_url":"https://api.github.com/users/heathermiller/events{/privacy}","received_events_url":"https://api.github.com/users/heathermiller/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/heathermiller/dist-prog-book","description":null,"fork":false,"url":"https://api.github.com/repos/heathermiller/dist-prog-book","forks_url":"https://api.github.com/repos/heathermiller/dist-prog-book/forks","keys_url":"https://api.github.com/repos/heathermiller/dist-prog-book/keys{/key_id}","collaborators_url":"https://api.github.com/repos/heathermiller/dist-prog-book/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/heathermiller/dist-prog-book/teams","hooks_url":"https://api.github.com/repos/heathermiller/dist-prog-book/hooks","issue_events_url":"https://api.github.com/repos/heathermiller/dist-prog-book/issues/events{/number}","events_url":"https://api.github.com/repos/heathermiller/dist-prog-book/events","assignees_url":"https://api.github.com/repos/heathermiller/dist-prog-book/assignees{/user}","branches_url":"https://api.github.com/repos/heathermiller/dist-prog-book/branches{/branch}","tags_url":"https://api.github.com/repos/heathermiller/dist-prog-book/tags","blobs_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/refs{/sha}","trees_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/trees{/sha}","statuses_url":"https://api.github.com/repos/heathermiller/dist-prog-book/statuses/{sha}","languages_url":"https://api.github.com/repos/heathermiller/dist-prog-book/languages","stargazers_url":"https://api.github.com/repos/heathermiller/dist-prog-book/stargazers","contributors_url":"https://api.github.com/repos/heathermiller/dist-prog-book/contributors","subscribers_url":"https://api.github.com/repos/heathermiller/dist-prog-book/subscribers","subscription_url":"https://api.github.com/repos/heathermiller/dist-prog-book/subscription","commits_url":"https://api.github.com/repos/heathermiller/dist-prog-book/commits{/sha}","git_commits_url":"https://api.github.com/repos/heathermiller/dist-prog-book/git/commits{/sha}","comments_url":"https://api.github.com/repos/heathermiller/dist-prog-book/comments{/number}","issue_comment_url":"https://api.github.com/repos/heathermiller/dist-prog-book/issues/comments{/number}","contents_url":"https://api.github.com/repos/heathermiller/dist-prog-book/contents/{+path}","compare_url":"https://api.github.com/repos/heathermiller/dist-prog-book/compare/{base}...{head}","merges_url":"https://api.github.com/repos/heathermiller/dist-prog-book/merges","archive_url":"https://api.github.com/repos/heathermiller/dist-prog-book/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/heathermiller/dist-prog-book/downloads","issues_url":"https://api.github.com/repos/heathermiller/dist-prog-book/issues{/number}","pulls_url":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls{/number}","milestones_url":"https://api.github.com/repos/heathermiller/dist-prog-book/milestones{/number}","notifications_url":"https://api.github.com/repos/heathermiller/dist-prog-book/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/heathermiller/dist-prog-book/labels{/name}","releases_url":"https://api.github.com/repos/heathermiller/dist-prog-book/releases{/id}","deployments_url":"https://api.github.com/repos/heathermiller/dist-prog-book/deployments","created_at":"2016-10-16T15:37:26Z","updated_at":"2017-01-03T17:27:09Z","pushed_at":"2017-01-03T17:27:07Z","git_url":"git://github.com/heathermiller/dist-prog-book.git","ssh_url":"git@github.com:heathermiller/dist-prog-book.git","clone_url":"https://github.com/heathermiller/dist-prog-book.git","svn_url":"https://github.com/heathermiller/dist-prog-book","homepage":null,"size":19568,"stargazers_count":347,"watchers_count":347,"language":"CSS","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":28,"mirror_url":null,"open_issues_count":3,"forks":28,"open_issues":3,"watchers":347,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/15"},"html":{"href":"https://github.com/heathermiller/dist-prog-book/pull/15"},"issue":{"href":"https://api.github.com/repos/heathermiller/dist-prog-book/issues/15"},"comments":{"href":"https://api.github.com/repos/heathermiller/dist-prog-book/issues/15/comments"},"review_comments":{"href":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/15/comments"},"review_comment":{"href":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/heathermiller/dist-prog-book/pulls/15/commits"},"statuses":{"href":"https://api.github.com/repos/heathermiller/dist-prog-book/statuses/b8ea0136877b83801707f85ca902ce033fffe360"}}}}
{"actor":{"display_login":"cmeiklejohn"}}