Problem Data growing faster than processing speeds Only solution is to parallelize on large clusters »Wide use in both enterprises and web industry How do we program these things?
Outline Data flow vs. traditional network programming Limitations of MapReduce Spark computing engine Machine Learning Example Current State of Spark Ecosystem Built-in Libraries
Traditional Network Programming Message-passing between nodes (e.g. MPI) Very difficult to do at scale: »How to split problem across nodes? • Must consider network & data locality »How to deal with failures? (inevitable at scale) »Even worse: stragglers (node not failed, but slow) »Ethernet networking not fast »Have to write programs for each machine Rarely used in commodity datacenters
Data Flow Models Restrict the programming interface so that the system can do more automatically Express jobs as graphs of high-level operators »System picks how to split each operator into tasks and where to run each task »Run parts twice fault recovery Map Reduce Biggest example: MapReduce Map Reduce Map
Example MapReduce Algorithms Matrix-vector multiplication Power iteration (e.g. PageRank) Gradient descent methods Stochastic SVD Tall skinny QR Many others!
Why Use a Data Flow Engine? Ease of programming »High-level functions instead of message passing Wide deployment »More common than MPI, especially “near” data Scalability to very largest clusters »Even HPC world is now concerned about resilience Examples: Pig, Hive, Scalding, Storm
Limitations of MapReduce MapReduce is great at one-pass computation, but inefficient for multi-pass algorithms No efficient primitives for data sharing »State between steps goes to distributed file system »Slow due to replication & disk storage
Example: Iterative Apps file system" file system" file system" file system" read write read write iter. 1 iter. 2 . . . Input file system" query 1 result 1 read query 2 result 2 query 3 result 3 Input . . . Commonly spend 90% of time doing I/O
Example: PageRank Repeatedly multiply sparse matrix and vector Requires repeatedly hashing together page adjacency lists and rank vector Same file grouped over and over Neighbors (id, edges) Ranks (id, rank) … iteration 1 iteration 2 iteration 3
Spark Computing Engine Extends a programming language with a distributed collection data-structure »“Resilient distributed datasets” (RDD) Open source at Apache »Most active community in big data, with 50+ companies contributing Clean APIs in Java, Scala, Python, R
Resilient Distributed Datasets (RDDs) Main idea: Resilient Distributed Datasets » Immutable collections of objects, spread across cluster » Statically typed: RDD[T] has objects of type T val sc = new SparkContext()! val lines = sc.textFile("log.txt") // RDD[String]! ! // Transform using standard collection operations! val errors = lines.filter(_.startsWith("ERROR"))! val messages = errors.map(_.split(‘\t’)(2))! lazily evaluated ! messages.saveAsTextFile("errors.txt")! kicks off a computation
Key Idea Resilient Distributed Datasets (RDDs) »Collections of objects across a cluster with user controlled partitioning & storage (memory, disk, ...) »Built via parallel transformations (map, filter, …) »The world only lets you make make RDDs such that they can be: Automatically rebuilt on failure
Python, Java, Scala, R // Scala: val lines = sc.textFile(...) lines.filter(x => x.contains(“ERROR”)).count() // Java: JavaRDD<String> lines = sc.textFile(...); lines.filter(new Function<String, Boolean>() { Boolean call(String s) { return s.contains(“error”); } }).count();
Fault Tolerance RDDs track lineage info to rebuild lost data file.map(lambda rec: (rec.type, 1)) .reduceByKey(lambda x, y: x + y) .filter(lambda (type, count): count > 10) map reduce filter Input file
Fault Tolerance RDDs track lineage info to rebuild lost data file.map(lambda rec: (rec.type, 1)) .reduceByKey(lambda x, y: x + y) .filter(lambda (type, count): count > 10) map reduce filter Input file
显示前 20 页。下载资料查看完整内容。
暂无评论。快来抢沙发吧！
评论 (0)
暂无评论。快来抢沙发吧！