【文章內(nèi)容簡(jiǎn)介】 ?Users implement interface of two primary methods: ?1. Map: (key1, val1) → (key2, val2) ?2. Reduce: (key2, [val2]) → [val3] Map operation ? Map, a pure function, written by the user, takes an input key/value pair and produces a set of intermediate key/value pairs. ?. (doc—id, doccontent) ? Draw an analogy to SQL, map can be visualized as groupby clause of an aggregate query. Reduce operation ? On pletion of map phase, all the intermediate values for a given output key are bined together into a list and given to a reducer. ? Can be visualized as aggregate function (., average) that is puted over all the rows with the same groupby attribute. Pseudocode map(String input_key, String input_value): // input_key: document name // input_value: document contents for each word w in input_value: EmitIntermediate(w, 1)。 reduce(String output_key, Iterator intermediate_values): // output_key: a word // output_values: a list of counts int result = 0。 for each v in intermediate_values: result += ParseInt(v)。 Emit(AsString(result))。 MapReduce: Execution overview MapReduce: Example MapReduce in Parallel: Example MapReduce: Fault Tolerance ? Handled via reexecution of tasks. ? Task pletion mitted through master ? What happens if Mapper fails ? ? Reexecute pleted + inprogress map tasks ? What happens if Reducer fails ? ? Reexecute in progress reduce tasks ? What happens if Master fails ? ? Potential trouble !! MapReduce: Walk through of One more Application MapReduce : PageRank ? PageRank models the behavior of a “random surfer”. ? C(t) is the outdegree of t, and (1d) is a damping factor (random jump) ? The “random surfer” keeps clicking on successive links at random not taking content into consideration. ? Distributes its pages rank equally among all pages it links to. ? The dampening factor takes the surfer “getting bored” and typing arbitrary URL. ????? ni iitCtPRddxPR1 )()()1()(PageRank : Key Insights ? Effects at each iteration is local. i+1th iteration depends only on ith iteration ? At iteration i, PageRank for individual nodes can be puted independently PageRank using MapReduce ? Use Sparse matrix representation (M) ? Map each row of M to a list of PageRank ―credit‖ to assign to out link neighbours. ? These prestige scores are reduced to a single PageRank value for a page by aggregating over them. PageRank using MapReduce Map: distribute PageRank “credit” to link targets Reduce: gather up PageRank “credit” from multiple sources to pute new PageRank value Iterate until convergence Source of Image: Lin 2022 Phase 1: Process HTML ? Map task takes (URL, pagecontent) pairs and maps them to (URL, (PRinit, listofurls)) ?PRinit is the ―seed‖ PageRank for URL ?listofurls contains all pages pointed to by URL ? Reduce task is just the identity function Phase 2: PageRank Distribution ? Reduce task gets (URL, url_list) and many (URL, val) values ?Sum vals and fix up with d to get new PR ?Emit (URL, (new_rank, url_list)) ? Check for convergence using non parallel ponent MapReduce: Some More Apps ? Distributed Grep. ? Count of URL Access Frequency. ? Clustering (Kmeans) ? Graph Algorithms. ? Indexing Systems MapReduce Programs In Google Source Tree MapReduce: Extensions and similar apps ? PIG (Yahoo) ? Hadoop (Apache) ? DryadLinq (Microsoft) Large Scale Systems Architecture using MapReduce User App MapReduce Distributed File Systems (GFS) BigTable: A Distributed Storage System for Structured Data Introduction ? BigTable is a distributed storage system for managing structured data. ? Designed to scale to a very large size ? Petabytes of data across thousands of servers ? Used for many Google projects ? Web indexing, Personalized Search, Google Earth, Google Analytics, Google Finance, … ? Flexible, highperformance solution for all of Google‘s products Motivation ? Lots of (semi)structured data at Google ? URLs: ? Contents, crawl metadata, links, anchors, pagerank, … ? Peruser data: ? User preference settings, recent queries/search results, … ? Geographic locations: ? Physical entities (shops, restaurants, etc.), roads, satellite image data, user annotations, … ? Scale is large ? Billions of URLs, many versions/page (~20K/version) ? Hundreds of millions of users, thousands or q/sec ? 100TB+ of satellite image data Why not just use mercial DB? ? Scale is too large for most mercial databases ? Even if it weren‘t, cost would be very high ? Building internally means system can be applied across many projects for low incremental cost ? Lowlevel storage optimizations help performance significantly ? Much harder to do when running on top of a database layer Goals ? Want asynchronous processes to be continuously updating different pieces of data ? Want access to most current data at any time ? Need to support: ? Very high read/write rates (millions of ops per second) ? Efficient scans over all or interesting subsets of data ? Efficient joins of large onetoone and onetomany datasets ? Often want to examine data changes over time ? . Contents of a web page over multiple crawls BigTable ? Distributed multilevel map ? Faulttolerant, persistent ? Scalable ? Thousands of servers ? Terabytes of