PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14MapReduce: Simplified Data Processing on large ClustersWhat is MapReduce?Slide 17MapReduceSome ApplicationsWhat is behind MapReduce?How MapReduce WorksSlide 23Slide 24Fault ToleranceLocality and Backup tasksRefinements and ExtensionRefinements and ExtensionsTests run on cluster of 1800 machines: 4 GB of memory Dual-processor 2 GHz Xeons with Hyper threading Dual 160 GB IDE disks Gigabit Ethernet per machine Bandwidth approximately 100 Gbps Two benchmarks: Grep 1010 100-byte records to extract records matching a rare pattern (92K matching records) Sort 1010 100-byte records (modeled after TeraSort benchmark)GrepNormal No backup tasks 200 processes killedDiscussionSlide 33Slide 34Slide 35Slide 36Slide 37Google dataSlide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53ACMS: The Akamai Configuration Management SystemAlex Sherman, Philip A. Lisiecki , Andy Berkheimer and Joel WeinAkamai Technologies, Inc.Columbia UniversityPolytechnic University.Presented at NSDI 2005Most slides are reproduced from the authors’ original presentationThe Akamai Platform•Akamai operates a Content Delivery Network of 15,000+ servers distributed across 1,200+ ISPs in 60+ countries•Web properties (Akamai’s customers) use these servers to bring their web content and applications closer to the end-usersProblem: configuration and control•Even with the widely distributed platform customers need to maintain the control of how their content is served•Customers need to configure their service options with the same ease and flexibility as if it was a centralized, locally hosted systemWhy difficult?•15,000 servers must synchronize to the latest configurations within a few minutes •Some servers may be down or “partitioned-off” at the time of reconfiguration•A server that comes up after some downtime must re-synchronize quickly•Configuration may be initiated from anywhere on the network and must reach all other serversProposed Architecture•Front-end – a small collection of Storage Points responsible for accepting, storing, and synchronizing configuration files•Back-End – reliable and efficient delivery of configuration files to all of the edge servers - leverages the Akamai CDN15,000 Edge ServersStorage PointsPublisherPublisherSPSPSPSPSPSPAgreement•A publisher contacts an accepting SP•The accepting SP replicates a temporary file to a majority of SPs•If replication succeeds the accepting SP initiates an agreement algorithm called Vector Exchange•Upon success the accepting SP “accepts” and all SPs upload the new fileStorage PointsPublisherPublisherSPSPSPSPSPSPSPSPVector Exchange•For each agreement SPs exchange a bit vector.•Each bit corresponds to “commitment” status of a corresponding SP.•Once a majority of bits are set we say that “agreement” takes place •When any SP “learns” of an agreement it can upload the submissionVector Exchange Guarantees•If a submission is accepted at least a majority have stored and agreed on the submission •The agreement is never lost by a future quorum. Why?–Any future quorum contains at least one SP that saw an initiated agreement.Recovery Routine•Each SP runs a recovery routine continuously to query other SPs for “missed” agreements. •If SP finds that it missed an agreement it downloads the corresponding configuration file•Overtime they keep a snaphot, a list of latest versions of all accepted filesBack-end: Delivery•Processes on edge servers subscribe to specific configurations via their local Receiver process•Receivers periodically query the snapshots on the SPs to learn of any updates.•If the updates match any subscriptions the Receivers download the files via HTTP IMS requests. Storage PointsSPSPSPSPSPSPEvaluation•Evaluated on top of real Akamai network•48 hours in the middle of a week•14,276 files submissions with five SPs–Most (40%) are of small sizes, than 1k–Some 3% were greater in 10M – 100MSubmission and propagation•Randomly sampled 250 edge servers to measure propagation time.•55 seconds on avg. •Dominated by cache TTL and polling intervalsPropagation vs. File Sizes•Mean and 95th percentile propagation time vs. file size•99.95% of updates arrived within 3 minutes•The rest delayed due to temporary connectivity issuesDiscussion•Availability of majority SPs guarantees agreement–Can SP’s availability metric be somehow used to construct the quorum with smaller size?•How many SPs should be there for 15,000 edge servers? –It experiments with 5. Is it too small?•How these SP’s are selected?MapReduce: Simplified Data Processing on large ClustersJeffrey Dean and Sanjay GhemawatGoogle, Inc.What is MapReduce?•A programming model or design framework or design pattern.•Allows distributed processing at back-end with parallelization, fault-tolerance, data distribution and load balancing.•Several Projects are built on MapReduce such as Skynet, Hadoop, etc.What is MapReduce?•Terms are borrowed from Functional Language (e.g. Lisp)•(map square ‘(1 2 3 4))–(1 4 9 16)•(reduce + ‘(1 4 9 16))–(+ 16 (+ 9 (+ 4 1) ) )–30Map•Map()–Process a key/value pair to generate intermediate key/value pairs.Welcome EveryoneHello EveryoneWelcome 1Everyone 1 Hello 1Everyone 1 Input <filename, file text>Reduce•Reduce()–Merge all intermediate values associated with the same keyWelcome 1Everyone 1 Hello 1Everyone 1 Everyone 2 Hello 1Welcome 1Some Applications•Distributed Grep:–Map - emits a line if matches the supplied pattern–Reduce - Copies the the intermediate data to output•Count of URL access frequency–Map – process web log and outputs <URL, 1>–Reduce - emits <URL, total count>•Reverse Web-Link Graph–Map – process web log and outputs <target, source>–Reduce - emits <target, list(source)>•Google News, Google Search … …What is behind MapReduce?•Make it distributed:1.Partition input key/value pairs into chunks, run map() tasks in parallel.2.After all map()s are complete, partition the stored values.3.Run reduce() in parallelHow MapReduce Works•User to do list:–indicate:•Input/output files•M: number of map tasks•R: number of reduce tasks•W: number of machines–Write map and reduce functions–Submit the job•This requires no knowledge of
View Full Document
Unlocking...