MapReduce algorithms for processing relational data Design Pattern Secondary Sorting MapReduce sorts input to reducers by key Values are arbitrarily ordered What if want to sort value also E g k v1 r v3 r v4 r v8 r Secondary Sorting Solutions Solution 1 Buffer values in memory then sort Why is this a bad idea Solution 2 Value to key conversion design pattern form composite intermediate key k v1 Let execution framework do the sorting Preserve state across multiple key value pairs to handle processing Anything else we need to do Value to Key Conversion Before k v1 r v4 r v8 r v3 r Values arrive in arbitrary order After k v1 v1 r k v3 v3 r k v4 v4 r k v8 v8 r Values arrive in sorted order Process by preserving state across multiple keys Remember to partition correctly Working Scenario Two tables User demographics gender age income etc User page visits URL time spent etc Analyses we might want to perform Statistics on demographic characteristics Statistics on page visits Statistics on page visits by URL Statistics on page visits by demographic characteristic Relational Algebra Primitives Projection Selection Cartesian product Set union Set difference Rename Other operations Join Group by aggregation Projection R1 R1 R2 R2 R3 R4 R5 R3 R4 R5 Projection in MapReduce Easy Map over tuples emit new tuples with appropriate attributes No reducers unless for regrouping or resorting tuples Alternatively perform in reducer after some other processing Basically limited by HDFS streaming speeds Speed of encoding decoding tuples becomes important Relational databases take advantage of compression Semistructured data No problem Selection R1 R2 R3 R4 R5 R1 R3 Selection in MapReduce Easy Map over tuples emit only tuples that meet criteria No reducers unless for regrouping or resorting tuples Alternatively perform in reducer after some other processing Basically limited by HDFS streaming speeds Speed of encoding decoding tuples becomes important Relational databases take advantage of compression Semistructured data No problem Group by Aggregation Example What is the average time spent per URL In SQL SELECT url AVG time FROM visits GROUP BY url In MapReduce Map over tuples emit time keyed by url Framework automatically groups values by keys Compute average in reducer Optimize with combiners Relational Joins Source Microsoft Office Clip Art Relational Joins R1 S1 R2 S2 R3 S3 R4 S4 R1 S2 R2 S4 R3 S1 R4 S3 Natural Join Operation Example Relations r s r s A B C D B D E 1 2 4 1 2 a a b a b 1 3 1 2 3 a a a b b r s A B C D E 1 1 1 1 2 a a a a b Natural Join Example sid bid day 22 101 10 10 96 58 103 11 12 96 R1 R1 sid 22 31 58 sname rating age dustin 7 45 0 lubber 8 55 5 rusty 10 35 0 S1 S1 sid 22 58 sname rating age bid day dustin 7 45 0 101 10 10 96 rusty 10 35 0 103 11 12 96 Types of Relationships Many to Many One to Many One to One Join Algorithms in MapReduce Reduce side join Map side join In memory join Striped variant Memcached variant Reduce side Join Basic idea group by join key Map over both sets of tuples Emit tuple as value with join key as the intermediate key Execution framework brings together tuples sharing the same key Perform actual join in reducer Similar to a sort merge join in database terminology Two variants 1 to 1 joins 1 to many and many to many joins Reduce side Join 1 to 1 Map keys values R1 R1 R4 R4 S2 S2 S3 S3 Reduce keys values R1 S2 S3 R4 Note no guarantee if R is going to come first or S Reduce side Join 1 to many Map keys values R1 R1 S2 S2 S3 S3 S9 S9 Reduce keys values R1 S2 What s S3 m e l b the pro Reduce side Join V to K Conversion In reducer keys values R1 S2 New key encountered hold in memory Cross with records from other set S3 S9 R4 S3 S7 New key encountered hold in memory Cross with records from other set Reduce side Join many to many In reducer keys values R1 R5 Hold in memory R8 Cross with records from other set S2 S3 S9 What s m e l b the pro Reduce side Join many to many Produce mapper output with composite key that includes foreign key and table name Reduce side Join many to many Use custom partitioning and grouping to send data with same key to a single reducer Map side Join Basic Idea Assume two datasets are sorted by the join key R1 S2 R2 S4 R4 S3 R3 S1 A sequential scan through both datasets to join called a merge join in database terminology Map side Join Parallel Scans If datasets are sorted by join key join can be accomplished by a scan over both datasets How can we accomplish this in parallel Partition and sort both datasets in the same manner In MapReduce Map over one dataset read from other corresponding partition No reducers necessary unless to repartition or resort Consistently partitioned datasets realistic to expect Map side Join Parallel Scans Sort and split both A and B before sending to mapper Mapper will produce output no reducer needed Map side Join Parallel Scans Parallel Scan Join In Memory Join Basic idea load one dataset into memory stream over other dataset Works if R S and R fits into memory Called a hash join in database terminology MapReduce implementation Distribute R to all nodes Map over S each mapper loads R in memory hashed by join key For every tuple in S look up join key in R No reducers unless for regrouping or resorting tuples In Memory Join Split A and distribute dataset B to all the mappers For each key in B iterate over all the data in A for joining In Memory Join Variants Striped variant R too big to fit into memory Divide R into R1 R2 R3 s t each Rn fits into memory Perform in memory join n Rn S Take the union of all join results Memcached join Load R into memcached Replace in memory hash lookup with memcached lookup Memcached Caching servers 15 million requests per second 95 handled by memcache 15 TB of RAM Database layer 800 eight core Linux servers running MySQL 40 TB user data Source Technology Review July August 2008 Memcached Join Memcached join Load R into memcached Replace in memory hash lookup with memcached lookup Capacity and scalability Memcached capacity RAM of individual node Memcached scales out with cluster Latency Memcached is fast basically speed of network Batch requests to amortize latency costs Source See tech report by Lin et al 2009 Which join to use In memory join map side join reduce side join Why Limitations of each In memory join memory Map side join sort order and partitioning Reduce side join general purpose Processing Relational Data Summary MapReduce algorithms for processing …
View Full Document
Unlocking...