Chapter 5: Data-Intensive Applications

Question 1

What are the challenges of large-scale data processing?

Answer 1

Writing efficient parallel and distributed processing jobs is hard
■ Extremely high performance/throughput possible
■ Problem: Highly parallel environment
■ Developers dont want to deal with concurrency issues, fault tolerance
● Needed: Suitable abstraction layer for developers

Question 2

What are the three Requirements for Data- Intensive Applications as an abstraction layer?

Answer 2

1. Developers don‘t have to think about parallelization
   ♦ Can continue to write sequential code
   ♦ Code is independent of degree of parallelism at runtime
2. Developers don‘t have to think about fault tolerance
   ♦ Abstraction layer takes care of failed nodes
   ♦ Re-executes lost parts of computations if necessary
3. Developers don‘t have to think about load balancing
   ♦ Abstraction layer is in charge of distributing the work evenly across the available compute nodes

Question 3

What is Map and Reduce?

Answer 3

MapReduce is a Programming Model.
Map and reduce is a second order function which takes first order functions provided by the developer as an input. It operates on a key-value model, meaning data is passed as KV pairs at all phases.

Question 4

What are the Signature and Guarantees of the Map Function?

Answer 4

Signature: (k1, v1) → list(k2, v2)
● Guarantees to the first-order function
■ First-order function is invoked once for each KV pair
■ Can produce a [0,*] KV pairs as output
● Useful for projections, selection, …

Question 5

What are the Signature and Guarantees of the Reduce Function?

Answer 5

Signature: (k2, list(v2)) → list(k3, v3)
● Guarantees to the first-order function
■ All KV-pairs with the same key are presented to the same invocation of the first-order function
● Useful for aggregation, grouping, …

Question 6

Name the five steps of Map and Reduce.

Answer 6

• Input Data
• Map Phase
• Shuffle Phase - Group intermediate results of map phase by key
• Reduce phase
• Output Data

Question 7

Explain how MapReduce works. (Example Word Count)

Answer 7

1. Input:KV pairs as are transferd as an Input for the Map function
2. Map Phase: Map function is executed on the KV pair > Intermediate results for each word per line
3. Schuffle phase groups the results from the map phase by key
4. Reduce Phase: execute function (count) on the grouped KV pairs.

Question 8

Explain the Map function?

Answer 8

■ First-order function provided by user

■ Specifies what happens to the data in job‘s map phase

Question 9

Explain the Mapper?

Answer 9

■ A process running on a worker node

■ Invokes map function for each KV pair

Question 10

Explain the Reduce function?

Answer 10

■ First-order function provided by user

■ Specifies what happens to the data in job‘s reduce phase

Question 11

Explain the Reducer?

Answer 11

■ Process invoking reduce function on grouped data

Question 12

How does the Distributed Execution of MapReduce work?

Answer 12

1. Client partitions input file into input splits
2. Client submits job to master
3. Mapper started for each input splits
4. Reducers pull data from mappers over network

Question 13

What are the Limitation of MapReduce?

Answer 13

1. Assumes finite input (files only)
   Limitation of finite input prevents streaming processing
2. Data between MR jobs must go to Google File System
   Constraint to write to GFS especially detrimental for iterative algorithms

Question 14

What are three scenarios of possbile MapReduce fault?

Answer 14

1. Mapper fails
2. Reducer fails
3. Entire worker node fails

Question 15

How can a Mapper fault be corrected?

Answer 15

■ Master detects failure through missing status report

■ Mapper is restarted on diff. node, re-reads data from GFS

Question 16

How can a Reducer fault be corrected?

Answer 16

■ Again, detected through missing status report

■ Reducer is restarted on different node, pulls intermediate results for its partition from mappers again

Question 17

How can an entire worker node fault be corrected?

Answer 17

■ Master re-schedules lost mappers and reducers

■ Finished mappers may be restarted to recompute lost intermediate results

Question 18

Explain master-worker pattern an MapReduce.

Answer 18

Master
■ Responsible for job scheduling
■ Monitoring worker nodes, detecting dead nodes
■ Load balancing
Workers
■ Executing map and reduce functions
■ Storing input/output data (in traditional setup)
■ Periodically report availability to master node

Question 19

Analytics Cluster Setup.

Answer 19

• Applications
• Processing Frameworks
• Resource Management System
• Distributed File System

Question 20

Comparison to HPC.

Answer 20

HPC:
- Flexible and fast low-level code
- Architecture-specific implementations
- High-performance hardware
Data-intensive Apps/ Distr. Dataflows:
- High-level dataflows
- Scalable fault-tolerant distr. engines
- Commodity Clusters

Question 21

GFS (Goolge File System).

Answer 21

Criteria:

• Scalability
• High performance
• Support for commodity clusters
• Fault-tolerance

Question 22

Distributed Storage.

Answer 22

Distributed file system and system on top, running on commodity servers. Fault tolerance and parallel access through replication.

Question 23

HDFS (Hadoop Distributed File System).

Answer 23

All data is stored in blocks, replicated on multiple data nodes. For scalability: Write-once-read-many filesystem.

Question 24

Google Bigtable.

Answer 24

Efficiently retrieve structured data. High-throughput NoSQL store through multi-dimensional sorted map on top of GFS.

Question 25

Spark.

Answer 25

At core are parallel transformations of Resilient Distributed Datasets (RDDs). For streaming Spark discretizes stream to Microbatches.

Question 26

Flink.

Answer 26

At core is a streaming dataflow engine that supports both batch and stream processing. Directed acyclic graph (DAG), master-slave paradigm.

Question 27

Spark vs. Flink.

Answer 27

• Flink has lower latency (‘Real’ Streaming: tuple-wise processing)
• Spark has higher throughput (Microbatches: processing of small batches of tuples)