CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Run the pipeline by hand (20 minutes)

The pages visited are: /x, /y, /x, /z, /y, /x, /x. Show the output after each step of the sort, count, sort and head pipeline with head set to 2.

Done when: five stage outputs and the final top two.

Hint

After the first sort, equal pages are side by side. uniq -c counts those runs.

Easy 2: Map and reduce a word count (20 minutes)

Input lines: "to be", "or not to be". Write the mapper output, the grouped input of each reducer and the final counts.

Done when: three lists and counts for the words.

Hint

The mapper emits (word, 1) for every word.

Easy 3: Pick the join (20 minutes)

For each case pick sort-merge, broadcast hash or partitioned hash: a 10 MB country list against a 5 TB log; two 3 TB tables both split by customer id into 100 partitions; two 3 TB tables, one split by customer and one by product.

Done when: three choices with a reason.

Hint

Check the sizes first, then whether both sides are split the same way.

Medium

Medium 1: Skew arithmetic (30 minutes)

A job has 10 reducers. Key K has 40 percent of 1 billion records, and the rest are even over the other keys. Each reducer handles 10 million records per minute. How long does the job take? How long if K is spread over 4 reducers?

Done when: two times and a note on what else must be copied.

Hint

Work out the busiest reducer's records. 400 million records at 10 million per minute is 40 minutes.

Medium 2: Fix a bad output step (30 minutes)

A job writes recommendations straight into the production database from 500 reducers. List three things that can go wrong. Redesign the output step and show how to switch and roll back.

Done when: three failure cases and a four-step redesign.

Hint

Think of failed tasks, retried tasks, and partial data being visible.

Medium 3: Plan a sessionization (30 minutes)

Log files are spread over 20 web servers. Describe a job that creates sessions where a gap of 30 minutes starts a new session. State the key, the sort and what the reducer does.

Done when: a map step, a shuffle key, a sort rule and a reduce step in plain words.

Hint

Use the user id as the key and sort by time.

Hard

Hard 1: Daily top 100 (45 minutes)

Design a workflow of jobs to find the 100 most viewed products each day from 2 TB of view logs. Include how to handle a product that has 30 percent of all views, and the final ranking step.

Done when: a list of jobs with their keys and a plan for the hot key.

Hint

A two-stage count spreads the hot product, then a second job merges the partial counts.

Hard 2: Rebuild or update (45 minutes)

A search index covers 500 million documents. Each day 1 million change. Compare a full nightly rebuild with an incremental update. Give times with made-up speeds, the risk of each and the step that makes the swap safe.

Done when: a table with cost, risk and recovery for both, and a recommendation.

Hint

A nightly rebuild is simpler but touches all the documents. Incremental is cheaper but harder to verify.

Hard 3: MapReduce or dataflow (50 minutes)

A recommendation workflow has 40 chained jobs, each writing 5 TB to HDFS with 3 copies. Estimate the extra storage and I/O compared with a dataflow engine that keeps most intermediate data in memory. Explain what extra rule recomputation after a failure demands of the code.

Done when: storage and I/O numbers with working and a statement on deterministic code.

Hint

40 jobs times 5 TB times 3 copies is 600 TB written.